Abstract
Matching spatial scene descriptions requires appropriate representations and algorithms based on the application at hand. This work outlines a simple model for matching qualitatively described spatial scenes extracted from sketch maps. Standard qualitative constraint networks are combined to provide a suitable qualitative representation for a sketched spatial scene. Two scenes are then matched using an implementation of the Tabu search metaheuristic, employing standard and specialised data structures. We give a detailed description of the representation and algorithm, and examine the performance of the model using an example dataset.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Grimson, W.E.L.: Object Recognition by Computer – The Role of Geometric Constraints. MIT Press, Cambridge (1990)
Egenhofer, M.: Spatial-query-by-sketch. In: Burnett, M., Citrin, W. (eds.) IEEE Symposium on Visual Languages, Boulder, CO, pp. 60–67 (1996)
Nedas, K., Egenhofer, M.: Spatial-scene similarity queries. Transactions in GIS 12(6), 661–681 (2008)
Blaser, A.: Geo-spatial sketches. Technical report, University of Maine, Department of Spatial Information Science and Engineering and National Center for Geographic Information and Analysis, Boardman Hall 321, Orono, Maine 04469, USA (1998)
Kopczynski, M., Sester, M.: Representation of sketch data for localisation in large data sets. In: XXth Congress of the International Society for Photogrammetry and Remote Sensing (ISPRS), Istanbul, Turkey (2004)
Chipofya, M., Wang, J., Schwering, A.: Towards cognitively plausible spatial representations for sketch map alignment. In: Egenhofer, M., Giudice, N., Moratz, R., Worboys, M. (eds.) COSIT 2011. LNCS, vol. 6899, pp. 20–39. Springer, Heidelberg (2011)
Chipofya, M.: A qualitative reasoning approach for improving query results for sketch-based queries by topological analysis of spatial aggregation. Master’s thesis, Universitat Jaume I, Universität Münster, Universidad Nova de Lisboa (2010)
Wallgrün, J.O., Wolter, D., Richter, K.F.: Qualitative matching of spatial information. In: Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS 2010, pp. 300–309. ACM, New York (2010)
Cohn, A.G., Renz, J.: Qualitative spatial representation and reasoning. In: van Hermelen, F., Lifschitz, V., Porter, B. (eds.) Handbook of Knowledge Representation, vol. 46, pp. 551–596. Elsevier (2008)
Renz, J., Schmid, F.: Customizing qualitative spatial and temporal calculi. In: Orgun, M.A., Thornton, J. (eds.) AI 2007. LNCS (LNAI), vol. 4830, pp. 293–304. Springer, Heidelberg (2007)
Ligozat, G., Renz, J.: What is a qualitative calculus? A general framework. In: Zhang, C., Guesgen, H.W., Yeap, W.-K. (eds.) PRICAI 2004. LNCS (LNAI), vol. 3157, pp. 53–64. Springer, Heidelberg (2004)
Ligozat, G.: Categorical methods in qualitative reasoning: The case for weak representations. In: Cohn, A.G., Mark, D.M. (eds.) COSIT 2005. LNCS, vol. 3693, pp. 265–282. Springer, Heidelberg (2005)
Montanari, U.: Networks of constraints: Fundamental properties and applications to picture processing. Information Sciences 7, 95–132 (1974)
Ladkin, P.B., Maddux, R.D.: On binary constraint problems. J. ACM 41(3), 435–469 (1994)
van Beek, P.: Reasoning about qualitative temporal information. Artificial Intelligence 58(1-3), 297–326 (1992)
Wang, J., Schwering, A.: The accuracy of sketched spatial relations: How cognitive errors influence sketch representation. In: Presenting Spatial Information: Granularity, Relevance, and Integration. Workshop at COSIT 2009, Aber Wrac’h, France (2009)
Schwering, A., Wang, J.: Sketching as interface for vgi systems. In: Geoinformatik, Kiel, Germany (2010)
Cohn, A.G., Bennett, B., Gooday, J., Gotts, N.M.: Qualitative spatial representation and reasoning with the region connection calculus. Geoinformatica 1, 275–316 (1997)
Riesen, K., Jiang, X., Bunke, H.: Exact and inexact graph matching: Methodology and applications. In: Aggarwal, C.C., Wang, H. (eds.) Managing and Mining Graph Data. Advances in Database Systems, vol. 40, pp. 217–247. Springer, US (2010)
Glover, F.: Tabu search – part 1. ORSA Journal on Computing 1(3), 190–206 (1989)
Glover, F.: Tabu search – part 2. ORSA Journal on Computing 2(1), 4–32 (1990)
Battiti, R., Tecchiolli, G.: The reactive tabu search. ORSA Journal on Computing 6(2), 126–140 (1994)
Gendreau, M., Potvin, J.Y.: Tabu search. In: Burke, E., Kendall, G. (eds.) Search Methodologies, pp. 165–186. Springer, US (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chipofya, M., Schwering, A., Binor, T. (2013). Matching Qualitative Spatial Scene Descriptions á la Tabu. In: Castro, F., Gelbukh, A., González, M. (eds) Advances in Soft Computing and Its Applications. MICAI 2013. Lecture Notes in Computer Science(), vol 8266. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45111-9_34
Download citation
DOI: https://doi.org/10.1007/978-3-642-45111-9_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45110-2
Online ISBN: 978-3-642-45111-9
eBook Packages: Computer ScienceComputer Science (R0)