A compact shape representation for linear geographical objects: the scope histogram

ABSTRACT

In the GIS domain we are often faced with a great amount of shape-related data. Therefore, it is a challenging task to find concise description approaches which support the efficient retrieval of specific objects. In order to address this demand we apply a method that has recently been introduced in the context of shape-based image retrieval of two-dimensional silhouettes, namely the scope histogram. Scope histograms pertain to the group of qualitative shape descriptions as they characterise a shape by the general configuration of its parts. In particular, scope histograms allow the comparison of two shapes with constant time complexity. Despite of its low complexity, the approach achieves promising retrieval results. However, up to now the definition of scope histograms is limited to closed polygons.In this paper we investigate the application of scope histograms to the GIS domain. Since the contour of silhouettes is always closed, a restriction to closed polygons is no limitation in that domain. By contrast, it frequently is when dealing with GIS data. In this domain, we are rather often faced with open polygons; think for example of courses of rivers, borders, and coastlines. Therefore, we modify the original definition of scope histograms in order to be able to handle arbitrary polygons. Although our new definition leads to a more compact description than the original one, retrieval results are even improved by this modification.

REFERENCES

• 1: James F. Allen, Maintaining knowledge about temporal intervals, Communications of the ACM, v.26 n.11, p.832-843, Nov. 1983 [doi>10.1145/182.358434]
• 2: F. Attneave. Some Informational Aspects of Visual Perception. Psychological Review, 61:183--193, 1954.
• 3: A. G. Cohn , S. M. Hazarika, Qualitative spatial representation and reasoning: an overview, Fundamenta Informaticae, v.46 n.1-2, p.1-29, May 2001
• 4: R. O. Duda and P. E. Hart. Pattern Classification and Scene Analysis. John Wiley and Sons, Inc., 1973.
• 5: M. Egenhofer and R. Franzosa. Point-Set Topological Spatial Relations. Int. Journal of Geographical Information Systems, 5(2):161--174, 1991.
• 6: G. D. Garson and R. S. Biggs. Analytic Mapping and Geographic Databases. Sage Publications, Newbury Park, CA, USA, 1992.
• 7: B. Gottfried. Reasoning about Intervals in Two Dimensions. In IEEE Int. Conf. on Systems, Man and Cybernetics, pages 5324--5332, The Hague, The Netherlands, 2004.
• 8: B. Gottfried. Shape from Positional-Contrast --- Characterising Sketches with Qualitative Line Arrangements. Doctoral dissertation, University of Bremen, Germany, 2005.
• 9: B. Gottfried. Characterising Meanders Qualitatively. In Int. Conf. on GIScience, pages 112--127, Münster, Germany, 2006.
• 10: Longin Jan Latecki , Rolf Lakämper, Shape Similarity Measure Based on Correspondence of Visual Parts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.10, p.1185-1190, October 2000 [doi>10.1109/34.879802]
• 11: L. J. Latecki, R. Lakämper, and U. Eckhardt. Shape Descriptors for Non-rigid Shapes with a Single Closed Contour. In IEEE CVPR, pages 424--429, Hilton Head Island, SC, USA, 2000.
• 12: D. A. Mitzias and B. G. Mertzios. Shape Recognition with a Neural Classifier Based on a Fast Polygon Approximation Technique. Pattern Recognition, 27:627--636, 1994.
• 13: D. A. Randell, Z. Cui, and A. G. Cohn. A Spatial Logic Based on Regions and Connection. In 3rd Int. Conf. on Knowledge Representation and Reasoning, pages 165--176, San Mateo, 1992. Morgan Kaufman.
• 14: P. L. Rosin. Assessing the Behaviour of Polygonal Approximation Algorithms. Pattern Recognition, 36:505--518, 2003.
• 15: A. Schuldt, B. Gottfried, and O. Herzog. Retrieving Shapes Efficiently by a Qualitative Shape Descriptor: The Scope Histogram. In 5th Int. Conf. on Image and Video Retrieval (CIVR 2006), pages 261--270, Tempe, AZ, USA, 2006.
• 16: A. Schuldt, B. Gottfried, and O. Herzog. Towards the Visualisation of Shape Features: The Scope Histogram. In 29th Annual German Conf. on Artificial Intelligence (KI 2006), pages 272--284, Bremen, Germany, 2006.
• 17: K. Zimmermann and C. Freksa. Qualitative Spatial Reasoning Using Orientation, Distance, and Path Knowledge. Applied Intelligence, 6:49--58, 1996.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Shape

Additional Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
        I.4.10 Image Representation
            Subjects: Statistical

General Terms:
Algorithms, Performance

Keywords:
bipartite arrangements, geographic information systems, image retrieval, linear objects, polygons, qualitative shape description, scope histogram