-—— 
tion 
  
scanners 
;anner 
sensor x 3 
n f4.5-22 
  
ving several 
r the images 
ased on the 
register the 
rections; 
captured by 
Ar 
_, 
ages by line 
lines in the 
ures; 
nera is not 
of the CCD 
o satisfy the 
the system 
| relaxation 
  
  
  
  
Ol Oc Or Or Oc’ or 
    
  
  
  
  
  
Fig.2 (a). Matching between left and center images 
algorithm is applied to match the left and center, center 
and right images respectively. In the second step, a 
“disparity constrained refinement” algorithm is used to 
eliminate the mismatches and increase the density of the 
disparity estimation. In the last step, a model-based 
interpolation is applied to generate the final results. 
3.1 Relaxation Matching 
Relaxation process is a useful technique for using 
contextual information to reduce local ambiguity and 
achieve global consistency. Generally, the relaxation 
algorithm for image matching mainly consists of following 
four steps: 
® Selection of candidate matching points; 
® Initial matching probability/matching score 
estimation; 
€  Interactively update matching probability/ 
matching score; 
® Relaxation and termination. 
The matching algorithm used in our system also consists 
of above four basic steps. Compared with other existing 
algorithms, our algorithm has some distinguishing features. 
Instead of just matching some feature points, our algorithm 
establishes correspondence at all pixels along the scanline. 
Another advantage is that the initial disparity map is much 
denser, which makes the subsequent interpolation easier. 
The innitial matching score is defined by the correlation 
operator. A correlation operation on a given window 
between point m 1(u1,v1) in the first image and the points 
m2(u2,v2) lying within the search area in the second image 
is defined as: 
  
  
Ol Oc Or Of Oc’ Or’ 
    
  
  
  
  
  
  
Fig.2 (b). Matching between center and right images 
n m 
Y X66. 0x4, j) 
Score(m, ,m,) = FE [1] 
Jo? 0) xo*?(1,) 
Range: -1<=Score<=1 
  
Where 6,(i,j)=1,(u, +i,v, + j)—1,(u,,v,), 
i (u,v) ls theaverage at point (u,v) of 7, (f — 1,2) , and 
O(I,)|s the standard deviation of the image in the 
neighborhood of (u,v). The matching pair (m1, m2) is put 
into the candidate set if its matching score is greater than 
a threshord value. 
The matching score is updated by the supporting strength 
in the neighborhood of this candidate pair: 
score(n, , 7, ) 
meN(n,) M ' mm mn) 
Score(m,,m,) = > HN 
meN(m) 
[2] 
Where M and N are constant, and r(m1, m2, n1, n2) is the 
distance difference given by rzld(m1, m2, n1, n2)l. The 
matching sorces are updated repeatedly. The scores of 
some matching candidates become very low after several 
iterations, we delete them from the candidate set. At last, 
the candidates which have strong support from their 
neighorhood will remain in the candidate set. 
3.2 Disparity Constrained Refinement 
The initial disparity estimation, generated by the relaxation 
algorithm can be refined by using the TLS image's 
disparity constraint. As Fig.2(a,b) illustrated, Wu and 
Murai have proven that the ratio of each pixel's left and 
right disparities is constant. That means, for each pixel Pi,