Skip to main content
main-content
Top

Hint

Swipe to navigate through the chapters of this book

2015 | OriginalPaper | Chapter

Shape Similarity Based on the Qualitative Spatial Reasoning Calculus eOPRAm

Authors: Christopher H. Dorr, Longin Jan Latecki, Reinhard Moratz

Published in: Spatial Information Theory

Publisher: Springer International Publishing

share
SHARE

Abstract

In our paper we investigate the use of qualitative spatial representations (QSR) about relative direction and distance for shape representation. Our new approach has the advantage that we can generate prototypical shapes from our abstract representation in first-order predicate calculus. Using the conceptual neighborhood which is an established concept in QSR we can directly establish a conceptual neighborhood between shapes that translates into a similarity metric for shapes. We apply this similarity measure to a challenging computer vision problem and achieve promising first results.

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 69.000 Bücher
  • über 500 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

Testen Sie jetzt 15 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 15 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 15 Tage kostenlos.

Footnotes
1
Material in this section is presented as an abridged summary of previous work by Moratz and Wallgrün [22].
 
2
Note that while this analogy makes use of three-dimensional space, our model refers to the 2D plane.
 
3
The first three letters of the symbol \(e\mathcal {OPRA}_m\) stand for elevated oriented point.
 
4
Note, that our parameters are elements of a cyclic group so that no modulo operation is required.
 
5
The stop parameter can also be defined with respect to the number of desired vertices, i.e., some pre-specified resolution. This is the approach taken in this paper to enable comparison between polylines with the same number of vertices.
 
6
For the first edge, the last edge is used as the control.
 
7
In 6.2, we present a more detailed look at the \(e\mathcal {OPRA}_m\) direction matrix comparison metric.
 
8
Currently, this is defined as \(gap\le 10\,\%\) of the shortest hull edge length.
 
9
Given the cyclic property of direction intervals in \(e\mathcal {OPRA}_m\), we are interested in the shortest-path distance from one interval to another instead of the raw absolute difference. I.e., any error greater than 2m can be expressed as \(4m-error\).
 
Literature
1.
go back to reference Barkowsky, T., Latecki, L.J., Richter, K.-F.: Schematizing maps: simplification of geographic shape by discrete curve evolution. In: Habel, C., Brauer, W., Freksa, C., Wender, K.F. (eds.) Spatial Cognition 2000. LNCS (LNAI), vol. 1849, pp. 41–53. Springer, Heidelberg (2000) CrossRef Barkowsky, T., Latecki, L.J., Richter, K.-F.: Schematizing maps: simplification of geographic shape by discrete curve evolution. In: Habel, C., Brauer, W., Freksa, C., Wender, K.F. (eds.) Spatial Cognition 2000. LNCS (LNAI), vol. 1849, pp. 41–53. Springer, Heidelberg (2000) CrossRef
2.
go back to reference Berendt, B.: Modelling subjective distances. In: Brewka, G., Habel, C., Nebel, B. (eds.) KI 1997. LNCS, vol. 1303, pp. 195–206. Springer, Heidelberg (1997) CrossRef Berendt, B.: Modelling subjective distances. In: Brewka, G., Habel, C., Nebel, B. (eds.) KI 1997. LNCS, vol. 1303, pp. 195–206. Springer, Heidelberg (1997) CrossRef
3.
go back to reference Clementini, E., Felice, P.D., Hernández, D.: Qualitative representation of positional information. Artif. intell. 95(2), 317–356 (1997) CrossRefMATH Clementini, E., Felice, P.D., Hernández, D.: Qualitative representation of positional information. Artif. intell. 95(2), 317–356 (1997) CrossRefMATH
4.
go back to reference Cohn, A.G.: Qualitative spatial representation and reasoning techniques. In: Brewka, G., Habel, C., Nebel, B. (eds.) KI 1997. LNCS, vol. 1303, pp. 1–30. Springer, Heidelberg (1997) CrossRef Cohn, A.G.: Qualitative spatial representation and reasoning techniques. In: Brewka, G., Habel, C., Nebel, B. (eds.) KI 1997. LNCS, vol. 1303, pp. 1–30. Springer, Heidelberg (1997) CrossRef
5.
go back to reference Dubba, K., Cohn, A., Hogg, D., Bhatt, M., Dylla, F.: Learning relational event models from video. J. Artif. Intell. Res. (JAIR) (to appear) Dubba, K., Cohn, A., Hogg, D., Bhatt, M., Dylla, F.: Learning relational event models from video. J. Artif. Intell. Res. (JAIR) (to appear)
6.
go back to reference Dylla, F., Wallgrün, J.O.: Qualitative spatial reasoning with conceptual neighborhoods for agent control. J. Intell. Robot. Syst. 48(1), 55–78 (2007) CrossRef Dylla, F., Wallgrün, J.O.: Qualitative spatial reasoning with conceptual neighborhoods for agent control. J. Intell. Robot. Syst. 48(1), 55–78 (2007) CrossRef
7.
8.
go back to reference Gibson, J.: The Ecological Approach to Visual Perception. Houghton Mifflin, Boston (1979) Gibson, J.: The Ecological Approach to Visual Perception. Houghton Mifflin, Boston (1979)
9.
go back to reference Gottfried, B.: Tripartite line tracks. In: International Conference on Computer Vision and Graphics, pp. 288–293 (2002) Gottfried, B.: Tripartite line tracks. In: International Conference on Computer Vision and Graphics, pp. 288–293 (2002)
10.
go back to reference Isli, A., Moratz, R.: Qualitative spatial representation and reasoning: algebraic models for relative position. Univ, Bibliothek des Fachbereichs Informatik (1999) Isli, A., Moratz, R.: Qualitative spatial representation and reasoning: algebraic models for relative position. Univ, Bibliothek des Fachbereichs Informatik (1999)
11.
go back to reference Latecki, L.J., DeMenthon, D., Rosenfeld, A.: Automatic extraction of relevant frames from videos by polygon simplification. In: Sommer, G., Krüger, N., Perwass, C. (eds.) Mustererkennung, pp. 412–419. Springer, Heidelberg (2000) Latecki, L.J., DeMenthon, D., Rosenfeld, A.: Automatic extraction of relevant frames from videos by polygon simplification. In: Sommer, G., Krüger, N., Perwass, C. (eds.) Mustererkennung, pp. 412–419. Springer, Heidelberg (2000)
12.
go back to reference Latecki, L.J., Lakämper, R.: Discrete approach to curve evolution. In: Levi, P., Schanz, M., Ahlers, R.-J., May, F. (eds.) Mustererkennung. Heidelberg, pp. 85–92. Springer, 1998 (1998) Latecki, L.J., Lakämper, R.: Discrete approach to curve evolution. In: Levi, P., Schanz, M., Ahlers, R.-J., May, F. (eds.) Mustererkennung. Heidelberg, pp. 85–92. Springer, 1998 (1998)
13.
go back to reference Latecki, L.J., Lakämper, R.: Convexity rule for shape decomposition based on discrete contour evolution. Comput. Vis. Image Underst. 73(3), 441–454 (1999) CrossRef Latecki, L.J., Lakämper, R.: Convexity rule for shape decomposition based on discrete contour evolution. Comput. Vis. Image Underst. 73(3), 441–454 (1999) CrossRef
14.
go back to reference Latecki, L.J., Lakämper, R.: Polygon evolution by vertex deletion. In: Nielsen, M., Johansen, P., Fogh Olsen, O., Weickert, J. (eds.) Scale-Space 1999. LNCS, vol. 1682, pp. 398–409. Springer, Heidelberg (1999) CrossRef Latecki, L.J., Lakämper, R.: Polygon evolution by vertex deletion. In: Nielsen, M., Johansen, P., Fogh Olsen, O., Weickert, J. (eds.) Scale-Space 1999. LNCS, vol. 1682, pp. 398–409. Springer, Heidelberg (1999) CrossRef
15.
go back to reference Latecki, L.J., Lakamper, R.: Shape similarity measure based on correspondence of visual parts. IEEE Trans. Pattern Anal. Mach. Intell. 22(10), 1185–1190 (2000) CrossRef Latecki, L.J., Lakamper, R.: Shape similarity measure based on correspondence of visual parts. IEEE Trans. Pattern Anal. Mach. Intell. 22(10), 1185–1190 (2000) CrossRef
16.
go back to reference Ligozat, G.: Qualitative triangulation for spatial reasoning. In: Campari, I., Frank, A.U. (eds.) COSIT 1993. LNCS, vol. 716, pp. 54–68. Springer, Heidelberg (1993) Ligozat, G.: Qualitative triangulation for spatial reasoning. In: Campari, I., Frank, A.U. (eds.) COSIT 1993. LNCS, vol. 716, pp. 54–68. Springer, Heidelberg (1993)
17.
go back to reference Lovett, A., Forbus, K.D.: Shape is like space: modeling shape representation as a set of qualitative spatial relations. In: AAAI Spring Symposium: Cognitive Shape Processing (2010) Lovett, A., Forbus, K.D.: Shape is like space: modeling shape representation as a set of qualitative spatial relations. In: AAAI Spring Symposium: Cognitive Shape Processing (2010)
18.
go back to reference Moratz, R.: Representing Relative Direction as a Binary Relation of Oriented Points. In: Brewka, G., Coradeschi, S., Perini, A., Traverso, P. (eds.) Proceedings of ECAI-06. Frontiers in Artificial Intelligence and Applications, vol. 141, pp. 407–411. IOS Press, The Netherlands (2006) Moratz, R.: Representing Relative Direction as a Binary Relation of Oriented Points. In: Brewka, G., Coradeschi, S., Perini, A., Traverso, P. (eds.) Proceedings of ECAI-06. Frontiers in Artificial Intelligence and Applications, vol. 141, pp. 407–411. IOS Press, The Netherlands (2006)
19.
go back to reference Moratz, R., Renz, J., Wolter, D.: Qualitative spatial reasoning about line segments. In: Proceedings of ECAI 2000, pp. 234–238 (2000) Moratz, R., Renz, J., Wolter, D.: Qualitative spatial reasoning about line segments. In: Proceedings of ECAI 2000, pp. 234–238 (2000)
21.
go back to reference Moratz, R., Tenbrink, T.: Affordance-based human-robot interaction. In: Rome, E., Hertzberg, J., Dorffner, G. (eds.) Towards Affordance-Based Robot Control. LNCS (LNAI), vol. 4760, pp. 63–76. Springer, Heidelberg (2008) CrossRef Moratz, R., Tenbrink, T.: Affordance-based human-robot interaction. In: Rome, E., Hertzberg, J., Dorffner, G. (eds.) Towards Affordance-Based Robot Control. LNCS (LNAI), vol. 4760, pp. 63–76. Springer, Heidelberg (2008) CrossRef
22.
go back to reference Moratz, R., Wallgrün, J.O.: Spatial reasoning with augmented points: extending cardinal directions with local distances. J. Spat. Inf. Sci. 5, 1–30 (2014) Moratz, R., Wallgrün, J.O.: Spatial reasoning with augmented points: extending cardinal directions with local distances. J. Spat. Inf. Sci. 5, 1–30 (2014)
24.
go back to reference Prince, S.J.: Computer vision: models, learning, and inference. Cambridge University Press, New York (2012) CrossRef Prince, S.J.: Computer vision: models, learning, and inference. Cambridge University Press, New York (2012) CrossRef
25.
go back to reference Randell, D.A., Cui, Z., Cohn, A.G.: A spatial logic based on regions and connection. In: KR 1992, pp. 165–176 (1992) Randell, D.A., Cui, Z., Cohn, A.G.: A spatial logic based on regions and connection. In: KR 1992, pp. 165–176 (1992)
26.
go back to reference Raubal, M., Moratz, R.: A functional model for affordance-based agents. In: Rome, E., Hertzberg, J., Dorffner, G. (eds.) Towards Affordance-Based Robot Control. LNCS (LNAI), vol. 4760, pp. 91–105. Springer, Heidelberg (2008) CrossRef Raubal, M., Moratz, R.: A functional model for affordance-based agents. In: Rome, E., Hertzberg, J., Dorffner, G. (eds.) Towards Affordance-Based Robot Control. LNCS (LNAI), vol. 4760, pp. 91–105. Springer, Heidelberg (2008) CrossRef
27.
go back to reference Renz, J., Nebel, B.: On the complexity of qualitative spatial reasoning: a maximal tractable fragment of the region connection calculus. Artif. Intell. 108(1), 69–123 (1999) CrossRefMathSciNetMATH Renz, J., Nebel, B.: On the complexity of qualitative spatial reasoning: a maximal tractable fragment of the region connection calculus. Artif. Intell. 108(1), 69–123 (1999) CrossRefMathSciNetMATH
28.
go back to reference Schlieder, C.: Reasoning about ordering. In: Kuhn, W., Frank, A.U. (eds.) COSIT 1995. LNCS, vol. 988. Springer, Heidelberg (1995) Schlieder, C.: Reasoning about ordering. In: Kuhn, W., Frank, A.U. (eds.) COSIT 1995. LNCS, vol. 988. Springer, Heidelberg (1995)
29.
go back to reference Schlieder, C.: Qualitative shape representation. Geogr. Objects Indeterminate Boundaries 2, 123–140 (1996) Schlieder, C.: Qualitative shape representation. Geogr. Objects Indeterminate Boundaries 2, 123–140 (1996)
30.
go back to reference Scivos, A., Nebel, B.: The finest of its class: The practical natural point-based ternary calculus lr for qualitative spatial reasoning. In: Freksa, C., Knauff, M., Krieg-Brückner, B., Nebel, B., Barkowsky, T. (eds.) Spatial Cognition IV. LNCS (LNAI), vol. 3343. Springer, Heidelberg (2005) Scivos, A., Nebel, B.: The finest of its class: The practical natural point-based ternary calculus lr for qualitative spatial reasoning. In: Freksa, C., Knauff, M., Krieg-Brückner, B., Nebel, B., Barkowsky, T. (eds.) Spatial Cognition IV. LNCS (LNAI), vol. 3343. Springer, Heidelberg (2005)
31.
go back to reference Worboys, M.F., Clementini, E.: Integration of imperfect spatial information. J. Vis. Lang. Comput. 12(1), 61–80 (2001) CrossRef Worboys, M.F., Clementini, E.: Integration of imperfect spatial information. J. Vis. Lang. Comput. 12(1), 61–80 (2001) CrossRef
32.
go back to reference Wunstel, M., Moratz, R.: Automatic object recognition within an office environment. In: Proceedings of the First Canadian Conference on Computer and Robot Vision, pp. 104–109. IEEE (2004) Wunstel, M., Moratz, R.: Automatic object recognition within an office environment. In: Proceedings of the First Canadian Conference on Computer and Robot Vision, pp. 104–109. IEEE (2004)
33.
go back to reference Zimmermann, K., Freksa, C.: Qualitative spatial reasoning using orientation, distance, and path knowledge. Appl. Intell. 6(1), 49–58 (1996) CrossRef Zimmermann, K., Freksa, C.: Qualitative spatial reasoning using orientation, distance, and path knowledge. Appl. Intell. 6(1), 49–58 (1996) CrossRef
Metadata
Title
Shape Similarity Based on the Qualitative Spatial Reasoning Calculus eOPRAm
Authors
Christopher H. Dorr
Longin Jan Latecki
Reinhard Moratz
Copyright Year
2015
DOI
https://doi.org/10.1007/978-3-319-23374-1_7

Premium Partner