Cry 
LIS 
re, 
leir 
ion 
ing 
of 
ad 
ing 
ear 
sed 
the 
; as 
  
  
Sagi Filin 
seed entities for registering the GIS data. This is more adequate as GIS data is linear in nature (road network, streams, etc.), 
so that relations between data sets are better captured by linear entities. Indeed, results of point-based map conflation show 
that while seed points are matched, the polylines connecting them are usually not. A line-based transformation employs the 
following steps: first counterpart line features are detected, then the whole region is partitioned into sub-regions according 
to the network of counterpart lines. Next, counterpart elements are transformed to their new positions, and all remaining 
elements within each sub-region are transformed according to the boundary transformation. 
The process is composed of three basic stages, the detection of counterpart elements, the establishment of correspondence 
between the matched entities and transformation of the data set. The first is important for automation of the process. 
Consider for example a typical topographic map. The number of linear features (or even road intersection) to be matched 
with counterpart entities is large enough to be impractical for a manual identification process. The matching itself 
establishes the geometric relations between the two data sets by modeling the distortions and the transformation is the core 
of the whole process and involves the actual transformation of the data set. Each of these aspects is non-trivial in itself. 
In this paper we are presenting a novel algorithm that was developed for this task with examples demonstrating its use. The 
counterpart linear entities that were utilized as the core for this transformation are part of a road network that was previoudy 
extracted from photogrammetry. By applying the algorithm we have managed to significantly reduce the disagreement 
between the GIS data and the rectified images, which results in a dramatic narrowing of the search space for corresponding 
objects for further applications. The whole algorithm or parts of it can be applied in other GIS applications such as data 
fusion, map generalization, change detection and other algorithms involving integration of data sets. Let us first present the 
algorithm. 
2 THE LINE-BASED MAP CONFLATION ALGORITHM 
The overall algorithm is composed of four parts. First the counterpart elements are detected, then matching is established by 
the counterpart objects. The third part of the algorithm is concerned with subdivision of the plane into closed parts in which 
the local transformation takes place. The final part involves applying the transformations to correct the distortions. We first 
address the detection of counterpart objects. 
2.1 Detection of counterpart elements 
Counterpart linear features are expected to be polylines lying a relatively short distance from one another and expected to 
have similar characteristics. The characteristics of interest are shape similarity, cumulative distance and similarity between 
emanating nodes at both end points, the first two attributes being geometric in 
nature while the third one is topological. The main hurdle with using these 
criteria is that the correspondence between linear features is not always 1:1, 
meaning that one polyline can be represented by a set of polylines in the 
counterpart set. In such a case the above characteristics are not much use 
unless they are incorporated into a more general algorithm. Figure 1 depicts 
two typical scenarios: in the first (Figure 1.a), the correspondence is between 
one polyline to three polylines thus forming a 1:N (one to many) relationship, 
the second scenario (Figure 1.b) presents correspondence between three and 
four polylines thus forming a N:M (many to many) relationship. In practice the 
relations can be between more segments in both sets and multiple candidate 
paths are not an unlikely possibility. 
  
  
  
  
  
Figure 1. Possible correspondence 
One possible approach to handling this is to extend the relations between one 
between linear features 
polyline in both data sets into multiple polylines (N:M relations) or 
sub-polylines (see Walter and Fritsch 1999, and Gabay and Doytsher 1995), 
however this complicates the modeling. An alternative solution that avoids handling such or even more complex cases is to 
reduce the problem to the detection of counterpart nodes (i.e. intersection of polylines), which are easier to manipulate and 
can be further extended to detect counterpart polylines. Working with nodes rather than edges is advantageous as it reduces 
the dimensionality of the objects concerned from 1D to OD, hence reducing the number of attributes as well as their 
complexity. Consequently, problems as that above are suppressed and detection of counterpart candidates becomes easier 
  
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 283