(iv) Judgement of Termination 
If the detection of division point process finds no new feature 
points or iteration number of process reaches a predefined 
number, process is terminated. Otherwise return to step (ii). 
4.2.2 Competition Process with Edge Constraint Model: 
The competition process is carried on with the edge constraint 
model described in section 3.1. Because triangulation applied to 
real image does not always give the ideal segmentation due to 
the influence of light condition or shadow, inhomogeneity or 
similarity of ground features on image, and so on. Therefore the 
triangulation result will not be applied in competition process. 
42.3 Consensus Process with  Multi-cluster Model: 
Consensus operation with area-based multi-cluster approach is 
performed according to the flow shown in Figure 8. 
(i) Search of Neighbouring Triangles 
At the first step, neighbouring triangles are searched for each 
target triangle, forming the Neighbouring Triangle Management 
(NTM) table which specifies neighbouring triangle's ID. Here, 
neighbouring triangles that difference in average and standard 
deviation of brightness is beyond thresholds when compared to 
the target one are not registered in NTM table. 
(ii) Calculation of Depth Map 
In this step by using parallax shift and absolute orientation 
parameters, depth map in world coordinate system is calculated 
for each pixel of image. Depth map for pixels among sub-area's 
grids are calculated by interpolation. 
(iii) Approximation of Plane 
The depth value of each triangle is evaluated and approximated 
by a plane in world coordinate system. As an ideal model, it is 
desirable to estimate each triangle as different planes, which are 
represented by their normal vectors. However for simplification, 
only planes that are regarded as horizontal are targeted for the 
remaining processes. Approximated horizontal planes are 
obtained by plane estimation with least squares method and 
evaluation for angle of elevation. Each of the resulted plane is 
assigned an index expressed as altitude. 
(iv) Region Merge 
Region merge process is only applied for triangles that are 
successfully approximated as horizontal plane. By referring to 
the NTM table, regions are merged based on the following rules. 
(a) Whether regions can merge is judged by comparing altitude 
of neighbouring triangles. 
(b) If both of a target triangle and neighbouring triangle(s) to be 
merged do not belong to any merged area, the ID of all triangles 
to be merged are registered as new entry to be grouped into the 
Merged Region Management (MRM) table. The new altitude of 
grouping region in MRM table is calculated from altitude of 
integrated triangles weighted by their area size. 
(c) If one of the triangles to be merged already belongs to a 
merged region, the rest of them are grouped into a merged 
region with the smallest ID, simultaneously entry of MRM table 
is modified. Also the altitude of merged region is modified. 
(v) Modification of Mapping 
By previous process, multi-clustering of altitude is performed. 
In this step inverse transformation from altitude of merge 
regions (world coordinate) to shift vectors in image 
(photographic coordinate) is processed for the next competition 
process. Regions to be modified are identified with MRM table. 
  
Search of Neighbouring Y 
    
  
  
  
  
  
  
  
  
  
Triangles | Approximation of Plane 
Y Y 
Calculation of Depth Map Region Merge 
— Y 
  
Modification of Mapping 
  
  
  
Figure 8. Flow of region segmentation 
4.2.4 Judgement of Convergence: Rules of convergence 
judge are the same as the standard ANM Process. The process 
of area-based multi-cluster ANM is repeatedly executed until 
reaching a predefined iterative number, and consequently 
clustered regions are expected to reform so as to reflect 
building's shape or other linear structures. 
5. EXPERIMENTS AND RESULTS 
5.1 Contents of Experiments 
To verify mapping characteristics of the proposed area-based 
multi-cluster ANM model, we have performed preliminary 
experiments with stereo aerial photos of urban area. The aerial 
photos were A/D converted at the resolution of 1200 dpi. The 
stereo model was rectified so as to remove y-parallax (see 
section 2.4). The mapping results by typical ANM model and 
enhanced multi-cluster ANM model are compared and 
discussed from the viewpoint of qualitative characteristics. 
5.2 Experimental Results and Discussion 
Mapping was processed from left image to right image in the 
stereo model. To illustrate the movement of mapping, shift 
vectors are indicated on equally divided grids. For comparing 
reconstruction ability of DSM, depth maps are calculated with 
parallax information derived from the mapping result. The 
depth maps are expressed as gray-scale image based on its 
altitude by projected onto the original left image for comparison. 
Figure 9 shows a pair of stereo aerial photos for experiments. 
Figure 10 shows detected and matched edge results, and Figure 
11 is a region segmentation result. Figure 12 and 13 illustrate 
the experimental results (shift vector and depth map) of typical 
ANM model and the results based on ANM with enhanced 
multi-cluster model. Figure 14 is the enlarged illustration of 
depth map. 
Comparison of depth map indicates that in some buildings 
regions depth integrations occurred in the inside and sharp 
topographical shifts on boundaries in the case of enhanced 
multi-cluster ANM model. It implies that mapping results have 
been modified and improved by enhanced ANM model where 
plane approximations were adequately performed. 
     
s 
  
(a) Left image (b) Right image 
Figure 9. Original stereo images 
—B8—