RCC11: A Finer Topological Representation for the Alignment of Regions in Sketch Maps

Jan Sahib , Schwering Angela, Schultz Carl and Chipofya Malumbo

Abstract

During the last two decades, dozens of qualitative representations have been proposed. These representations are motivated by a wide variety of applications of spatial data processing such as Geographical Information System (GIS), robotic navigation, and high level vision. For topological reasoning, the Region Connected Calculus (RCC) is perhaps the best-known formalism. The two algebras, RCC5 and RCC8 distinguish five and eight different topological relations. The different levels of granularity provide flexibility in the selection of representations suitable for different applications. In this paper, we propose RCC11-lpc, finer versions of the RCC in which topological relations are refined using the geometric point-set approach. If one region is contained inside another or if two regions externally connect then their topological relation is further distinguished by the dimension of the intersection of their boundaries: line or point contact. This is an important spatial distinction for users of GIS to query and retrieve information from databases. We propose an algorithm to compute the RCC11-lpc topological relation between closed regions. The composition table for base relations is computed for constraint-based reasoning using the declarative spatial reasoning system CLP(QS). The proposed representation is evaluated within the application of sketch map alignment: We compute corresponding regions (city- blocks) in sketch maps and regions in geo-referenced maps. First, RCC11-lpc relations between city-blocks are extracted in the form of qualitative constraint networks. Afterwards, the evaluation of RCC11-lpc is done by matching the qualitative constraint networks from sketch and geo-referenced maps.