CMRT09: Object Extraction for 3D City Models, Road Databases and Traffic Monitoring - Concepts, Algorithms, and Evaluation 
In our approach, we only use the voting steps associated with the 
Hough transform. We describe briefly here the principle. We 
made a Hough accumulation space in the discretized parameter 
space p and 9. Each 3D point P{x,y,z) of the dataset (facade 
points) votes in all cells of the Hough space accumulation verify 
ing the following constraint: 
p = x ■ cos 9 + y ■ sin# (1) 
where p is a length of the normal of the line to the origin and 9 is 
the orientation associated to the normal vector. Each couple (p,9) 
is unique if 9 €[0,27t] and p > 0. 
The cells containing a high score correspond more or less to a 
facade. However, we aim at determining precisely and automati 
cally the best fit lines of points characterizing the building facades 
(see figure 6). In our case, we do not carry out the lines extrac 
tion step that is based on the local maxima values of the Hough 
accumulation space since this requires a very difficult tuning of 
some parameters. 
Figure 6: The usage of the Hough transform for extracting build 
ing facade lines when the different facades have similar densities. 
The local maxima often provide approximate or erroneous so 
lutions. Any partially occluded facade has a low density of 3D 
points and has thus a low vote in the Hough counting space com 
pared to the non-occluded facade. For this reason, if the vote 
threshold is too low, many lines will be extracted. Inversely, if 
the threshold is too high, many lines could be missed. In addition 
to this, the line estimation depends also on the discretization steps 
of p and 6 values. Close lines characterizing the approximation 
of the same potential line are sometimes extracted. The usage of 
a large neighborhood to determine the local maxima in the Hough 
space could reduce this effect. Nevertheless, tuning the threshold 
is a very difficult task in many cases. 
We remind that our approach deals with buildings having sim 
ple polygonal footprints. The discretization steps depend also of 
the building characteristics. The p step is related to the minimal 
distance defined between two facades planes with a similar orien 
tation, the 9 step is related to the minimal angle defined between 
two adjacent facades. 
In the urban context, certain characteristics of the building fa 
cades are a priori known. The number of facades of the buildings 
is known in advance (between 3 and 10). Our idea is to use a k- 
means clustering algorithm to replace the detection of local max 
ima in the accumulation space—the parameter space of 9 and p 
values, in order to automatically determine the exact number of 
facades and their support 2D lines. 
The fc-means algorithm is a well-known unsupervised clustering 
method commonly used to cluster n objects of the input dataset 
into k homogeneous partitions, k<n, for example (Forgy, 1965) 
and (Macqueen, 1967). We use this technique in a classic way. 
Nevertheless, several other various clustering techniques exist and 
a survey is found in (Xu and Wunsch, 2005). Mathematically, the 
k clusters are determined by minimizing an objective function 
such as the sum of the squared distances between the points and 
the corresponding centroids such as: 
k 
intra^distance = E E ((p^) {Pm) - (Pi,9i)) 2 (2) 
i=l P m €Sj 
where (p, #)(p m ) is the value of (p, 9) associated with all 3D 
points P rn (injj Pm i z m ) included in the corresponding cell, k is 
the number of clusters Si,i = 1,2,..., k, and (p*, ) is the cen 
troid of the cluster Si. The above score is simply the intra-cluster 
distance measure. More specifically, the score is calculated only 
for the cells containing a strictly positive vote in the Hough space. 
Besides, the sum in the above equation is carried out for all 3D 
point candidates even if they vote all in the same cell. 
We can also measure the inter-cluster distance, or the distance 
between clusters, which we want to be as big as possible. This 
measure is given by 
inter-distance — min {(pj,9j) — (p,, 9j)) 2 . i ^ j (3) 
Since we want both of these measures to help us determine if we 
have a good clustering, i.e., a clustering which results in compact 
clusters which are well separated, we must combine them in some 
way. The obvious way is to minimize the following objective 
function: 
,. ,., mtra-distance 
validity = - 
inter-distance 
(4) 
In our case, the fc-means algorithm is run for each k value belong 
ing to the predefined interval. Each run provides a score based on 
(4). The potential number of facades is the k value corresponding 
to the minimum of these scores. This validity measure for the de 
termination of the number of clusters in k-means clustering was 
proposed in (Ray and Turi, 1999). Thus the number of facades 
could be known even when the facades have heterogeneous den 
sities of 3D points. 
More precisely, when one run is carried out for a given k, the al 
gorithm is not guaranteed to return the global optimum because 
the convergence depends on the initial seeds selected. The k- 
means algorithm is extremely fast. For this reason, a method 
which is commonly employed is to run the algorithm several 
times and select the best clustering available for each /c-value. 
In our case, the first run is carried out by setting the initial seeds 
to the local maxima in the Hough counting space. The other runs 
are randomly initialized inside the Hough counting space. 
Now that the number of clusters k is known, one can compute 
a 2D line solution (facade support) for each detected cluster of 
points. Several solutions can be used to model the facade such 
as the use of the centroid of each cluster, or the solution with the 
68