The algorithm implements a validity check suggested by Fua [4]. Validation is done by doing correlation twice by reversing the roles of two images. Valid matches are considered to be only the ones for which the disparities are equal.
An important modification to Fua's validation approach was to improve its performance for small disparity ranges. The problem with Fua's approach was that it found many invalid disparities to be valid when the disparity range was small. The reason for this is seen by an empirical observation that when matching is done in both directions the resulting match is often at the extreme points of the range. The validation process would often identify these disparities as valid while the the full algorithm would identify them as invalid.
The solution to this problem was to discard the pixels that pass Fua's validation procedure, but fall either on the minimum or maximum on the reduced disparity range. Another way of justifying this approach is that the expected disparity is more likely to be in the middle of the reduced disparity range if it is valid. In other words, if the model that produces the disparity range is correct and the range is sufficiently wide, than the found disparity should not fall at the extreme locations of the range.
The algorithm makes assumptions about the incoming images. It assumes that the epipolar lines are parallel with the image scan-lines and the epipolar lines are at the same y coordinate in the image. This is achieved by a calibration process described by Lenz and Tsai [9] . The position of the camera relative to each other, their focal lengths, and radial distortions are determined and used to correct the obtained images.
In order fairly judge the efficiency of the full algorithm the stereo algorithm was implemented recursively [3]. This means that an effort was made to reduce the amount of necessary repetition of computation. The reduction in processing was achieved by storing the correlation results of one pixel and reusing them to get the results for the neighboring pixels.
First, the correlation scores were computed for
correlation windows that correspond to one scan line of the correlation
window. These scores are noted as 
where the i,j are the coordinate of the center pixel and d is the disparity
at which the score is computed.
The horizontal scores are summed to produce the total correlation score of the window:
where 
is the size of the window.
This summation was done only for the first row. On the next row the information from above window was used to compute the correlation score without having to do the full summation:
Figure 3 shows how computing the correlation score
can be sped up by taking advantage of the results obtained in the
previous scan line. The area that is subtracted
is 
.
The area added is 
.
Figure 3: Recursive correlation
Figure 3 illustrates only the recursion in the vertical direction. The recursion is also done horizontally such that it takes advantage of the scores already computed for on the same scan line.
The recursive implementation gives an advantage to the full execution of the algorithm. The advantage comes from the fact that all the necessary information for recursion is available. In the case of the coherent algorithm the scores for the neighboring pixels may not be available. The lack of information is due to the difference in the disparity search ranges of the pixels. The coherent algorithm is therefore disadvantaged in two ways: first, it needs to do non recursive computations when the information is not available, and second, it has to check what information is available before any computation is done.