The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B5. Beijing 2008 
Figure 9. The representation of matching key points as ver 
tices in a graph. The top image shows a detail of the fully 
connected sub-graphs. The bottom image shows examples 
for the minimal spanning tree(s). 
While this graph fully represents the matching relation of the 
key points, when we plot the vertices and edges onto the 
corresponding image features, it does not exhibit the expected 
row and column structure we typically expect from a façade 
(see Figure 8Figure 8 second row). 
We can compute one more transformation on the graph, known 
as the minimum spanning tree. The minimum spanning tree 
problem is described by the following condition: find a subset 
of edges 7 c E which connects all vertices of the Graph and 
whose total weight is minimal. The total weight is the sum of all 
weights of the edges contained in T. One popular algorithm to 
compute the minimum spanning tree is given by Kruskal (1956). 
In our case, since we have unconnected sub-graphs, we do not 
compute a single spanning tree, but several unconnected 
spanning trees. The Euclidian distance of the key points, which 
was chosen as the weights of the edges, should favour the 
horizontal and vertical edges of the graph and partially 
eliminate edges running traverse. We can further filter the graph, 
eliminating edges which violate some boundary conditions, 
such as minimum or maximum length or direction. The result of 
the computation is shown in the bottom image of Figure 8. The 
graphic shows the main structure of the façade, exhibiting the 
strong horizontal similarity on both upper levels. The two doors 
on the lower level have absolutely no vertical connectivity. 
Figure 8. (Top) The key points detected from the LASER- 
MAP. (Middle) The fully connected sub-graphs of 
matching key points. (Bottom) The minimum spanning 
tree(s).