The block-matching algorithm establishes a correspondence by computing the sum of absolute differences (SAD) computed between small windows in rectified, pre-filtered stereo images.

Matching is constrained by minimum disparity and number of disparity parameters. For example, for a given point (xl, y) in the left image, the search in the right image is restricted to points that lie within (xl – minimum disparity, y) and (xl – minimum disparity - number of disparities, y).

The algorithm computes SAD values for each point in the specified range and selects the location in the right image with the smallest SAD value as the match. The complexity of this algorithm is given in the following equation:

O w · h · n
where:
  • w is the width of the rectified image,
  • h is the height of the rectified image,
  • n is the number of disparities.