Greenwich Institute for Science and Technology
   Home >> Modeling & Simulation >> Automatic Comparison and Correlation Between Planar Graphs
Home
History
Staff
Partners
Contact
Automatic comparison and correlation between networks of planar graphs:


      The problem of planar graphs comparison arises from a great number of practical applications including geographic information processing, image processing, geospatial analysis, and robotics vision analysis, just to mention a few. For example, in order to update an old street map data using a current more accurate data set, every line segment in the old data set must be correlated to a matching segment in the new data set. When the two data sets are topologically identical the problem is not very difficult to solve and computer algorithms are relatively easy to construct. In reality, however, human and natural processes cause constant changes on the ground. A street found in the old map may not exist anymore in the new map, and a newly constructed street found in the new map could not be found in the old map. Negligent or incomplete survey also contributes to such discrepancies. There are also situations where parts of the old map have such a poor positional accuracy that shift of more than one kilometer from the new data may occur.
      Such a reality has caused a great deal of problems for algorithm works and forced the practices of map updating being largely a manual exercise. Similar problems of comparing topologically similar but not identical planar graphs can also be found when jointly searching through multiple geographic databases, carrying out change detections of linear features in remote sensing images, processing object outlines through a moving robotic vision image, or tracking target automatically through high resolution images.
      The algorithm problem can be roughly described as the following: given two planar graphs on the same plane find a mapping between the nodes and line segments in the two graphs so that the mapped sub-graphs are identical in topology, similar in geometry (not in strict sense), and close in position. So far there is no complete mathematical solution to the problem, although a related problem, planar graph isomorphism, has long been a subject in graph theory.

DC polyline 1 DC polyline 2

      Automatic correlation and correction of Census Bureau's TIGER lines (road rail and hydro) for Washington, DC (16,208 lines). Left and right are figures before and after the correlation/correction respectively. Red lines are old data, green lines are new data, blue lines are corrected data.


      As part of the effort for the Census Bureau's countrywide TIGER file modernization project, a highly efficient approach has been developed and it has been proven suitable for the massive large scale GIS data update process. The algorithm was tested in the process of several large counties including Galveston County, Texas, Wake County, North Carolina, Beaufort County, South Carolina and the District of Columbia. It achieved reliable 85% automation of this traditionally manual process. The processing time for a large county takes less than one hour on a 800 MHz Intel Pentium III processor. The algorithm combines analysis of topological and geometrical similarities with positional proximity. Attribute information such as road name and classification are also used whenever available. Meta data generation and QA/QC procedures are also established around the automated process.

 
2010 Greenwich Institute for Science and Technology