1 
A WW UW wl M M m 
  
Chapman, David 
  
  
  
  
  
  
  
  
  
  
  
Figure 3. Panoramic image browser with *Hazmap' image (left) and Biris range image (right). 
4 DEVELOPMENT OF TOOLS FOR RANGE IMAGE SEGMENTATION 
As can be seem from the images the majority of the features in the scene can be modelled using a limited set of 
geometric primitives. In order to access the performance of the sensor on the various surfaces in the survey area 
segmentation tools focussed upon the semi-automatic identification of planar and cylindrical objects. Several techniques 
were developed and implemented within the MATLAB prototyping environment. These included plane and quadric 
extraction routines based upon: 
e Region growing from user defined seed points; 
e Random sampling within user defined region of interest (ROI); 
e Random sampling within ROI constrained by step images in the range image. 
Of these methods the second proved to be the most efficient enabling robust extraction of the various geometric entities. 
The method is uses the following algorithm which is based upon that described in more detail by Roth (Roth, 1993) 
For I = 1 to NumberOfSamples 
Extract a random minimal subset of X,Y,Z coordinates sufficient to determine 
plane or quadric parameters; 
Fit surface to subset; 
Evaluate cost function for current surface based upon all observations; 
If cost is lower than those previously computed mark as best solution; 
End; 
Reject outlying observations using parameters of best solution; 
Evaluate best-fit surface to remaining observations by least-squares estimation; 
At present the user selects the number of samples taken and the cost function with 1000 random samples generally 
being sufficient to determine a robust fit. Cost functions in implemented include least-squares measures and the 
maximum number points falling within user-set error bounds. 
4.1 Fitting of quadric surface 
The general quadric form is given by equation 1. 
ax’ + bxy’ + cz’ + 2hxy + 2gxz +2fyz +ux + vy +wz +1 = 0 (1) 
Since we are only interested in planar or cylindrical objects only the linear and quadratic forms were implemented 
requiring the determination of 3 ( uv,w) and 9 (a..w) parameters respectively. Initial values for a best fitting cylinder 
are achieved from the analysis of the 9 quadric parameters as described by Fedeema & Little (Feedema & Little, 1997). 
4.2 Determination of least-squares cylinder fit. 
Cylinder fitting is implemented using the general least squares solution through the iterative refinement of the 
parameters derived from the quadric fit. The table below shows typical differences between the quadric fit and the final 
least-squares solution for a number of data sets indicating that the random sampled quadric generally provides good 
initial values for subsequent least-square analysis (table 2). 
  
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B5. Amsterdam 2000. 125