Map-Matching Algorithm Research Of Sketch-map And Vector-map Based On Topological Features

With the rapid development of urbanization in China,various provinces,cities,and regions are undergoing old city reconstruction and urban construction.The changing of appearance of urban is passing every day.The exchanges between international,inter-provincial,and inter-city are deepening,and population flows are increasing.So ‘Addressing' has become a difficult problem.At present,text,as the most common input language,is widely used in the mainstream maps such as Baidu maps and Google maps to realize the process of map addressing.However,when people use the text is hard to describe an address clearly in the addressing process,they often use a simple sketch to assist in the expression.This process could help people to form a simple spatial scene in the brain,a one-to-one correspondence is performed between sketch spatial scene with real spatial scene in the brain and finally locate the target address.Therefore,sketches,as a kind of intuitive interaction "language",take advantages of the relative invariance of their qualitative spatial relationships to map the spatial objects in the sketches and in the vector map one by one.This process is map matching,which is also the essential step to achieve map addressing and location.At present,the main process of map matching is to determine whether two spatial objects match by measuring the spatial similarity of spatial objects.The common spatial similarity measures include distance,area,shape,position,semantics,topology and direction,etc.Topological similarity,as a measure of rough matching,is often used in the process of map matching in order to reduce the matching candidate set and improve matching efficiency.And then use distance,area,shape,location and other geometric similarity features to achieve accurate map matching.Because the spatial objects in sketches do not have a standard geographic reference,so we cannot obtain the accurate spatial geography information.At the same time,people's spatial cognition always produce distortion in different degrees,its leads to make the shape and location of the spatial objects in sketches are blurred.Therefore,the matching process of sketches and vector maps can only be achieved by using the qualitative spatial relationships dominated by topological relations as constraint conditions.The main work of the thesis is summarized as follows:(1)The current research status of vector map matching and sketch map matching is summarized,and the study idea of matching sketch maps and vector maps based on topological features is proposed in this paper;(2)Analyzed the characteristics of cognitive distortions of sketch maps and obtained sketch maps have invariable qualitative spatial relationship.Based on this feature,the match process of sketch maps and vector maps can be achieved.The spatial objects extracted from sketch maps are classified into three types: point,line,and polygon.The three objects' qualitative spatial relationships and corresponding representation models with different granularity are described in detail.The qualitative spatial relations include the topological relations of street segments,the relative direction relationship at the junction,the linear sequence relationship of the landmarks along the street segment,the cyclical relations of the landmarks at the junction,the topological relationship between the landmarks and the regional blocks and the topological relations between the regional blocks.The qualitative spatial relations are laid the foundations for the match process;(3)The two storage methods of graph are described in detail: adjacency list and adjacency matrix,after summarizing their advantages and disadvantages,the conclusion that adjacency matrix can improve the efficiency of graph search is obtained.Therefore,sketch maps and vector maps are used to store the original spatial relations by adjacency matrix,and all potential matching points are used to construct the local spatial relation matrix of the global spatial relation matrix and a certain matching point.After detailed analysis of the local spatial relation matrix,the quantitative calculation is carried out,and the results are applied to matrix quality evaluation;(4)In this paper,the quantitative calculation results of the local spatial relation matrix are calculated as the fitness function in the Tabu search process.The corresponding matching points with the highest post fitness function are taken as the matching direction of the next step,and added to the matching sequence,and then iteratively calculated to complete the search by all the matching points.The matching algorithm and the quality of spatial relations are evaluated from two aspects of single constraint relation and multi constraint relation,and the feasibility and effectiveness of matching the spatial relation matrix with the improved Tabu search algorithm in the matching process of sketch map and vector map is verified.