Sagi Filin 
  
(there are pathological cases were a node in one data set is a degenerate representation of a broken intersection, but these 
cases are easy to track down and deal with). The algorithm for detecting counterpart nodes works as follows: first candidate 
nodes are detected according to a proximity criterion, then candidates are evaluated according to their attributes - the 
number of emanating nodes and their orientations. Due to differences in the sources from which the data were compiled, the 
acceptance criteria for candidate counterparts are relaxed so that some disagreement is permitted. Candidate counterparts 
are then validated (and either accepted or eliminated) by introducing a topological validation procedure we call a “round trip 
walk”. This procedure enables verifying the correctness of a candidate, disqualifying a candidate and also proposing a 
candidate based on topological criteria. The final stage in the algorithm is constructing the paths between nodes. Paths are 
constructed using Best First Search (BFS), a graph search algorithm that is useful for finding short paths. Candidate paths 
are then validated and fixed according to a geometric criterion that evaluates the average distance between the two paths 
(after normalizing them). For paths failing to fulfill this criterion the algorithm searches, where needed, for better candidae 
edges that minimize the distance. In complicated cases where the correspondence is very loose, the procedure may still 
associate some wrong candidates; therefore some human intervention may be required. An assessment procedure was 
developed as part of the algorithm, for evaluating the level of uncertainty in matching between counterparts. This is a 
function of the agreement between the original sources (due to the reasons outlined above) rather than the performance of 
the algorithm. Counterparts with high level of uncertainty are recommended to be checked by a user and be corrected if 
needed. Applying an editing mechanism that also re-computes the matching of related nodes to the one that was corrected, 
has shown that once one or a few nodes are corrected many other wrong node associations are automatically corrected as 
well. Therefore human intervention, even in difficult cases, is very limited. The result of the overall procedure is a set of 
counterpart paths that form a set of counterpart edges in a graph structure, when grouped together. 
2.2 Matching of counterpart objects 
Creating the graph of counterpart features is followed by computing a transformation between counterpart edges. In the 
point-based case this part is trivial as the translation of a node towards its counterpart is the translation (dx, dy) from the 
original to the new position. With lines, this becomes more complex. The main hurdle is the discrete representation of 
polylines. If polylines could have been easily described analytically, a transformation could have been given in an analytical 
form as well. However, when polylines are described by a set of vertices, analytical transformation is less likely to exist. 
This in turn requires a more precise definition of the transformation characteristics. Here we define them as the complete 
matching of the counterpart polylines, so that the transformed polyline will coalesce with its counterpart (this was not 
accomplished in the point-based matching), and maintaining the original shape of the polyline so that the original shape will 
not be distorted by the transformation. The second property relates to the view that the polyline transformation should be the 
basis for the transformation of all other elements 
within the bounded region. Maintaining the polyline 
shape prevents distortions when related elements are 
m il N transformed. 
The transformation is based on polyline projection, 
or in other words, mapping between polylines. Since 
polylines are described by vertices, the projection is 
seen as a translation of the vertices 
( I4; y;) P9 D) (xj, y;) ) from their original position to 
  
| (a) 
  
their expected position on the counterpart polyline. 
Several experiments with different projections have 
shown that the best projection is achieved by using 
the normalized cumulative distance as the measure 
for the expected position of a given vertex. Figure 2 
illustrates this concept. Having both polylines coincide, entails projecting vertices from both polylines towards each other 
(Filin and Doytsher 1999) - L,(x;,5,) = Ly(x},y;)) and Ly(x;,y;) L(x;,y;) - so the transformation becomes direction 
  
  
  
  
Figure 2. Projection by using normalized cumulative distances 
independent. 
The algorithm was further improved to cope with some distortions in the projection that could occur even though the shapes 
are similar. The distortions have mostly to do with scaling - some similar segments along the polyline may be a bit shorter 
or a bit longer then their counterparts, thus shifting all projected vertices and causing distortions (see Figure 3.a). Such 
  
284 International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000.