Skip to main content
Top

2015 | OriginalPaper | Chapter

From Metric to Topology: Determining Relations in Discrete Space

Authors : Matthew P. Dube, Jordan V. Barrett, Max J. Egenhofer

Published in: Spatial Information Theory

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This paper considers the nineteen planar discrete topological relations that apply to regions bounded by a digital Jordan curve. Rather than modeling the topological relations with purely topological means, metrics are developed that determine the topological relations. Two sets of five such metrics are found to be minimal and sufficient to uniquely identify each of the nineteen topological relations. Key to distinguishing all nineteen relations are regions’ margins (i.e., the neighborhood of their boundaries). Deriving topological relations from metric properties in \( {\mathbb{R}}^{2} \) vs. \( {\mathbb{Z}}^{2} \) reveals that the eight binary topological relations between two simple regions in \( {\mathbb{R}}^{2} \) can be distinguished by a minimal set of six metrics, whereas in \( {\mathbb{Z}}^{2} \), a more fine-grained set of relations (19) can be distinguished by a smaller set of metrics (5). Determining discrete topological relations from metrics enables not only the refinement of the set of known topological relations in the digital plane, but further enables the processing of raster images where the topological relation is not explicitly stored by reverting to mere pixel counts.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Ackoff, R.L.: From data to wisdom: presidential address to ISGSR, 1988. J. Appl. Syst. Anal. 16(1), 3–9 (1989) Ackoff, R.L.: From data to wisdom: presidential address to ISGSR, 1988. J. Appl. Syst. Anal. 16(1), 3–9 (1989)
2.
go back to reference Alexandroff, P.: Elementary Concepts of Topology. Dover Publishers Inc., New York (1961)MATH Alexandroff, P.: Elementary Concepts of Topology. Dover Publishers Inc., New York (1961)MATH
3.
go back to reference Bittner, T., Winter, S.: On ontology in image analysis. In: Agouris, P., Stefanidis, A. (eds.) ISD 1999. LNCS, vol. 1737, pp. 168–191. Springer, Heidelberg (1999)CrossRef Bittner, T., Winter, S.: On ontology in image analysis. In: Agouris, P., Stefanidis, A. (eds.) ISD 1999. LNCS, vol. 1737, pp. 168–191. Springer, Heidelberg (1999)CrossRef
4.
go back to reference Blaser, A.D., Egenhofer, M.J.: A visual tool for querying geographic databases. In: Proceedings of the Working Conference on Advanced Visual Interfaces, pp. 211–216. ACM (2000) Blaser, A.D., Egenhofer, M.J.: A visual tool for querying geographic databases. In: Proceedings of the Working Conference on Advanced Visual Interfaces, pp. 211–216. ACM (2000)
5.
go back to reference Câmara, G., Egenhofer, M.J., Fonseca, F., Vieira Monteiro, A.M.: What’s in an image? In: Montello, D.R. (ed.) COSIT 2001. LNCS, vol. 2205, pp. 474–488. Springer, Heidelberg (2001) Câmara, G., Egenhofer, M.J., Fonseca, F., Vieira Monteiro, A.M.: What’s in an image? In: Montello, D.R. (ed.) COSIT 2001. LNCS, vol. 2205, pp. 474–488. Springer, Heidelberg (2001)
6.
go back to reference Clementini, E., Sharma, J., Egenhofer, M.J.: Modelling topological spatial relations: strategies for query processing. Comput. Graph. 18(6), 815–822 (1994)CrossRef Clementini, E., Sharma, J., Egenhofer, M.J.: Modelling topological spatial relations: strategies for query processing. Comput. Graph. 18(6), 815–822 (1994)CrossRef
7.
go back to reference Di Sciascio, E., Mongiello, M.: Query by sketch and relevance feedback for content-based image retrieval over the web. J. Vis. Lang. Comput. 10(6), 565–584 (1999)CrossRef Di Sciascio, E., Mongiello, M.: Query by sketch and relevance feedback for content-based image retrieval over the web. J. Vis. Lang. Comput. 10(6), 565–584 (1999)CrossRef
8.
go back to reference Dube, M.P., Egenhofer, M.J.: An ordering of convex topological relations. In: Xiao, N., Kwan, M.-P., Goodchild, M.F., Shekhar, S. (eds.) GIScience 2012. LNCS, vol. 7478, pp. 72–86. Springer, Heidelberg (2012)CrossRef Dube, M.P., Egenhofer, M.J.: An ordering of convex topological relations. In: Xiao, N., Kwan, M.-P., Goodchild, M.F., Shekhar, S. (eds.) GIScience 2012. LNCS, vol. 7478, pp. 72–86. Springer, Heidelberg (2012)CrossRef
9.
go back to reference Dube, M.P., Egenhofer, M.J.: Surrounds in partitions. In: Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 233–242. ACM (2014) Dube, M.P., Egenhofer, M.J.: Surrounds in partitions. In: Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 233–242. ACM (2014)
10.
go back to reference Eckhardt, U., Latecki, L.J.: Topologies for the digital spaces \( {\mathbb{Z}}^{2} \) and \( {\mathbb{Z}}^{3} \). Comput. Vis. Image Underst. 90(3), 295–312 (2003) Eckhardt, U., Latecki, L.J.: Topologies for the digital spaces \( {\mathbb{Z}}^{2} \) and \( {\mathbb{Z}}^{3} \). Comput. Vis. Image Underst. 90(3), 295–312 (2003)
11.
go back to reference Egenhofer, M.J.: Query processing in spatial. J. Vis. Lang. Comput. 8(4), 403–424 (1997)CrossRef Egenhofer, M.J.: Query processing in spatial. J. Vis. Lang. Comput. 8(4), 403–424 (1997)CrossRef
12.
go back to reference Egenhofer, M.J.: Spherical topological relations. In: Spaccapietra, S., Zimányi, E. (eds.) Journal on Data Semantics III. LNCS, vol. 3534, pp. 25–49. Springer, Heidelberg (2005)CrossRef Egenhofer, M.J.: Spherical topological relations. In: Spaccapietra, S., Zimányi, E. (eds.) Journal on Data Semantics III. LNCS, vol. 3534, pp. 25–49. Springer, Heidelberg (2005)CrossRef
13.
go back to reference Egenhofer, M.J., Al-Taha, K.K.: Reasoning about gradual changes of topological relationships. In: Frank, A.U., Campari, I., Formentini, U. (eds.) Theories and Methods of Spatio-Temporal Reasoning in Geographic Space. LNCS, vol. 639, pp. 196–219. Springer, Heidelberg (1992)CrossRef Egenhofer, M.J., Al-Taha, K.K.: Reasoning about gradual changes of topological relationships. In: Frank, A.U., Campari, I., Formentini, U. (eds.) Theories and Methods of Spatio-Temporal Reasoning in Geographic Space. LNCS, vol. 639, pp. 196–219. Springer, Heidelberg (1992)CrossRef
14.
go back to reference Egenhofer, M.J., Dube, M.P.: Topological relations from metric refinements. In: Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 158–167. ACM (2009) Egenhofer, M.J., Dube, M.P.: Topological relations from metric refinements. In: Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 158–167. ACM (2009)
15.
go back to reference Egenhofer, M.J., Franzosa, R.F.: Point-set topological spatial relations. Int. J. Geogr. Inf. Syst. 5(2), 161–174 (1991)CrossRef Egenhofer, M.J., Franzosa, R.F.: Point-set topological spatial relations. Int. J. Geogr. Inf. Syst. 5(2), 161–174 (1991)CrossRef
16.
go back to reference Egenhofer, M.J., Herring, J.R.: Categorizing Binary Topological Relations Between Regions, Lines, and Points in Geographic Databases. Technical report, Department of Surveying Engineering, University of Maine (1990) Egenhofer, M.J., Herring, J.R.: Categorizing Binary Topological Relations Between Regions, Lines, and Points in Geographic Databases. Technical report, Department of Surveying Engineering, University of Maine (1990)
17.
go back to reference Egenhofer, M.J., Mark, D.M.: Naive Geography. In: Frank, A., Kuhn, W. (eds.) COSIT 1995. LNCS, vol. 988, pp. 1–15. Springer, Heidelberg (1995) Egenhofer, M.J., Mark, D.M.: Naive Geography. In: Frank, A., Kuhn, W. (eds.) COSIT 1995. LNCS, vol. 988, pp. 1–15. Springer, Heidelberg (1995)
18.
go back to reference Egenhofer, M.J., Shariff, A.R.: Metric details for natural-language spatial relations. ACM Trans. Inf. Syst. 16(4), 295–321 (1998)CrossRef Egenhofer, M.J., Shariff, A.R.: Metric details for natural-language spatial relations. ACM Trans. Inf. Syst. 16(4), 295–321 (1998)CrossRef
19.
go back to reference Egenhofer, M.J., Sharma, J.: Topological relations between regions in \( {\mathbb{R}}^{2} \) and \( {\mathbb{Z}}^{2} \). In: Abel, D.J., Ooi, B.C. (eds.) SSD 1993. LNCS, vol. 692, pp. 316–336. Springer, Heidelberg (1993) Egenhofer, M.J., Sharma, J.: Topological relations between regions in \( {\mathbb{R}}^{2} \) and \( {\mathbb{Z}}^{2} \). In: Abel, D.J., Ooi, B.C. (eds.) SSD 1993. LNCS, vol. 692, pp. 316–336. Springer, Heidelberg (1993)
20.
go back to reference Egenhofer, M.J., Sharma, J., Mark, D.M.: A critical comparison of the 4-intersection and 9-intersection models for spatial relations: formal analysis. In: McMaster, R.B., Armstrong, M.P. (eds.) Autocarto 11, pp. 1–11 (1993) Egenhofer, M.J., Sharma, J., Mark, D.M.: A critical comparison of the 4-intersection and 9-intersection models for spatial relations: formal analysis. In: McMaster, R.B., Armstrong, M.P. (eds.) Autocarto 11, pp. 1–11 (1993)
21.
go back to reference Fallah, N., Apostolopoulos, I., Bekris, K., Folmer, E.: Indoor human navigation systems: a survey. Interact. Comput. 25(1), 21–33 (2013) Fallah, N., Apostolopoulos, I., Bekris, K., Folmer, E.: Indoor human navigation systems: a survey. Interact. Comput. 25(1), 21–33 (2013)
22.
go back to reference Friedl, M.A., McIver, D.K., Hodges, J.C.F., Zhang, X.Y., Muchoney, D., Strahler, A.H., Woodcock, C.E., Gopal, S., Schneider, A., Cooper, A., Baccini, A., Gao, F., Schaaf, C.: Global land cover mapping from MODIS: algorithms and early results. Remote Sens. Environ. 83(1), 287–302 (2002)CrossRef Friedl, M.A., McIver, D.K., Hodges, J.C.F., Zhang, X.Y., Muchoney, D., Strahler, A.H., Woodcock, C.E., Gopal, S., Schneider, A., Cooper, A., Baccini, A., Gao, F., Schaaf, C.: Global land cover mapping from MODIS: algorithms and early results. Remote Sens. Environ. 83(1), 287–302 (2002)CrossRef
23.
go back to reference Galton, A.: The mereotopology of discrete space. In: Freksa, C., Mark, D.M. (eds.) COSIT 1999. LNCS, vol. 1661, pp. 251–266. Springer, Heidelberg (1999) Galton, A.: The mereotopology of discrete space. In: Freksa, C., Mark, D.M. (eds.) COSIT 1999. LNCS, vol. 1661, pp. 251–266. Springer, Heidelberg (1999)
24.
go back to reference Giudice, N.A., Bakdash, J.Z., Legge, G.E.: Wayfinding with words: spatial learning and navigation using dynamically updated verbal descriptions. Psychol. Res. 71(3), 347–358 (2007)CrossRef Giudice, N.A., Bakdash, J.Z., Legge, G.E.: Wayfinding with words: spatial learning and navigation using dynamically updated verbal descriptions. Psychol. Res. 71(3), 347–358 (2007)CrossRef
25.
go back to reference Huo, M.L.: The basic topology model of spherical surface digital space. In: Proceedings of the 20th International Society for Photogrammetry and Remote Sensing Congress, pp. 1–6 (2004) Huo, M.L.: The basic topology model of spherical surface digital space. In: Proceedings of the 20th International Society for Photogrammetry and Remote Sensing Congress, pp. 1–6 (2004)
26.
go back to reference Kaufman, A., Cohen, D., Yagel, R.: Volume graphics. Computer 26(7), 51–64 (1993)CrossRef Kaufman, A., Cohen, D., Yagel, R.: Volume graphics. Computer 26(7), 51–64 (1993)CrossRef
27.
go back to reference Khalimsky, E., Kopperman, R., Meyer, P.R.: Computer graphics and connected topologies on finite ordered sets. Topology Appl. 36(1), 1–17 (1990)CrossRefMathSciNetMATH Khalimsky, E., Kopperman, R., Meyer, P.R.: Computer graphics and connected topologies on finite ordered sets. Topology Appl. 36(1), 1–17 (1990)CrossRefMathSciNetMATH
28.
go back to reference Klippel, A.: Spatial information theory meets spatial thinking: is topology the rosetta stone of spatio-temporal cognition? Ann. Assoc. Am. Geogr. 102(6), 1310–1328 (2012)CrossRef Klippel, A.: Spatial information theory meets spatial thinking: is topology the rosetta stone of spatio-temporal cognition? Ann. Assoc. Am. Geogr. 102(6), 1310–1328 (2012)CrossRef
29.
go back to reference Klippel, A., Li, R., Yang, J., Hardisty, F., Xu, S.: The egenhofer-cohn hypothesis or, topological relativity? In: Raubal, M., Mark, D., Frank, A. (eds.) Cognitive and Linguistic Aspects of Geographic Space, pp. 195–215. Springer, Heidelberg (2013)CrossRef Klippel, A., Li, R., Yang, J., Hardisty, F., Xu, S.: The egenhofer-cohn hypothesis or, topological relativity? In: Raubal, M., Mark, D., Frank, A. (eds.) Cognitive and Linguistic Aspects of Geographic Space, pp. 195–215. Springer, Heidelberg (2013)CrossRef
30.
go back to reference Kong, T.Y., Rosenfeld, A.: Digital topology: a comparison of the graph-based and topological approaches. In: Reed, G.M., Roscoe, A.W., Wachter, R.F. (eds.) Topology and Category Theory in Computer Science, pp. 273–289. Oxford University Press, Oxford (1991) Kong, T.Y., Rosenfeld, A.: Digital topology: a comparison of the graph-based and topological approaches. In: Reed, G.M., Roscoe, A.W., Wachter, R.F. (eds.) Topology and Category Theory in Computer Science, pp. 273–289. Oxford University Press, Oxford (1991)
31.
go back to reference Kurata, Y.: The 9+-intersection: a universal framework for modeling topological relations. In: Cova, T.J., Miller, H.J., Beard, K., Frank, A.U., Goodchild, M.F. (eds.) GIScience 2008. LNCS, vol. 5266, pp. 181–198. Springer, Heidelberg (2008)CrossRef Kurata, Y.: The 9+-intersection: a universal framework for modeling topological relations. In: Cova, T.J., Miller, H.J., Beard, K., Frank, A.U., Goodchild, M.F. (eds.) GIScience 2008. LNCS, vol. 5266, pp. 181–198. Springer, Heidelberg (2008)CrossRef
32.
go back to reference Kurata, Y., Egenhofer, M.J.: The 9+-intersection for topological relations between a directed line segment and a region. In: Gottfried, B. (ed.) Workshop on Behaviour and Monitoring Interpretation, Technical report 42, Technologie-Zentrum Informatik, pp. 62–76. University of Bremen, Germany (2007) Kurata, Y., Egenhofer, M.J.: The 9+-intersection for topological relations between a directed line segment and a region. In: Gottfried, B. (ed.) Workshop on Behaviour and Monitoring Interpretation, Technical report 42, Technologie-Zentrum Informatik, pp. 62–76. University of Bremen, Germany (2007)
33.
go back to reference Lipson, H., Kurman, M.: Fabricated: The New World of 3D Printing. Wiley, Indianapolis (2013) Lipson, H., Kurman, M.: Fabricated: The New World of 3D Printing. Wiley, Indianapolis (2013)
34.
go back to reference Mark, D.M., Comas, D., Egenhofer, M.J., Freundschuh, S.M., Gould, M.D., Nunes, J.: Evaluating and refining computational models of spatial relations through cross-linguistic human-subjects testing. In: Frank, A., Kuhn, W. (eds.) COSIT 1995, LNCS, vol. 988, pp. 553–568. Springer, Heidelberg (1995) Mark, D.M., Comas, D., Egenhofer, M.J., Freundschuh, S.M., Gould, M.D., Nunes, J.: Evaluating and refining computational models of spatial relations through cross-linguistic human-subjects testing. In: Frank, A., Kuhn, W. (eds.) COSIT 1995, LNCS, vol. 988, pp. 553–568. Springer, Heidelberg (1995)
35.
go back to reference Mezaris, V., Kompatsiaris, I., Strintzis, M.G.: Region-based retrieval using an object ontology and relevance feedback. Eurosip J. Appl. Sig. Process., 886–901 (2004) Mezaris, V., Kompatsiaris, I., Strintzis, M.G.: Region-based retrieval using an object ontology and relevance feedback. Eurosip J. Appl. Sig. Process., 886–901 (2004)
36.
go back to reference Nedas, K.A., Egenhofer, M.J., Wilmsen, D.: Metric details of topological line-line relations. Int. J. Geogr. Inf. Sci. 21(1), 21–48 (2007)CrossRef Nedas, K.A., Egenhofer, M.J., Wilmsen, D.: Metric details of topological line-line relations. Int. J. Geogr. Inf. Sci. 21(1), 21–48 (2007)CrossRef
37.
go back to reference Nittel, S., Stefanidis, A., Cruz, I., Egenhofer, M., Goldin, D., Howard, A., Labrinidis, A., Madden, S., Voisard, A., Worboys, M.: Report from the first workshop on geo sensor networks. ACM SIGMOD Rec. 33(1), 141–144 (2004)CrossRef Nittel, S., Stefanidis, A., Cruz, I., Egenhofer, M., Goldin, D., Howard, A., Labrinidis, A., Madden, S., Voisard, A., Worboys, M.: Report from the first workshop on geo sensor networks. ACM SIGMOD Rec. 33(1), 141–144 (2004)CrossRef
38.
go back to reference Randell, D.A., Cui, Z., Cohn, A.G.: A spatial logic based on regions and connection. In: Nebel, B., Rich, C., Swartout, W.R. (eds.) KR 1992, pp. 165–176 (1992) Randell, D.A., Cui, Z., Cohn, A.G.: A spatial logic based on regions and connection. In: Nebel, B., Rich, C., Swartout, W.R. (eds.) KR 1992, pp. 165–176 (1992)
40.
go back to reference Shariff, A.R.B., Egenhofer, M.J., Mark, D.M.: Natural-language spatial relations between linear and areal objects: the topology and metric of english-language terms. Int. J. Geogr. Inf. Sci. 12(3), 215–245 (1998) Shariff, A.R.B., Egenhofer, M.J., Mark, D.M.: Natural-language spatial relations between linear and areal objects: the topology and metric of english-language terms. Int. J. Geogr. Inf. Sci. 12(3), 215–245 (1998)
41.
go back to reference Sridhar, M., Cohn, A.G., Hogg, D.C.: From video to RCC8: exploiting a distance based semantics to stabilise the interpretation of mereotopological relations. In: Egenhofer, M., Giudice, N., Moratz, R., Worboys, M. (eds.) COSIT 2011. LNCS, vol. 6899, pp. 110–125. Springer, Heidelberg (2011)CrossRef Sridhar, M., Cohn, A.G., Hogg, D.C.: From video to RCC8: exploiting a distance based semantics to stabilise the interpretation of mereotopological relations. In: Egenhofer, M., Giudice, N., Moratz, R., Worboys, M. (eds.) COSIT 2011. LNCS, vol. 6899, pp. 110–125. Springer, Heidelberg (2011)CrossRef
42.
go back to reference Sutherland, W.A.: Introduction to Metric and Topological Spaces, 2nd edn. Oxford University Press, Oxford (1975)MATH Sutherland, W.A.: Introduction to Metric and Topological Spaces, 2nd edn. Oxford University Press, Oxford (1975)MATH
44.
go back to reference Winter, S.: Topological relations between discrete regions. In: Egenhofer, M.J., Herring, J.R. (eds.) SSD 95, LNCS, vol. 951, pp. 310–327. Springer, Heidelberg (1995) Winter, S.: Topological relations between discrete regions. In: Egenhofer, M.J., Herring, J.R. (eds.) SSD 95, LNCS, vol. 951, pp. 310–327. Springer, Heidelberg (1995)
45.
go back to reference Zlatanova, S.: On 3D topological relationships. In: DEXA Workshop 2000, pp. 913–919. IEEE Computer Society (2000) Zlatanova, S.: On 3D topological relationships. In: DEXA Workshop 2000, pp. 913–919. IEEE Computer Society (2000)
Metadata
Title
From Metric to Topology: Determining Relations in Discrete Space
Authors
Matthew P. Dube
Jordan V. Barrett
Max J. Egenhofer
Copyright Year
2015
DOI
https://doi.org/10.1007/978-3-319-23374-1_8

Premium Partner