Block Matching Disparity

hardPROStereo MatchingCVCV: Depth Estimation

Implement block matching for stereo disparity estimation, a fundamental technique in stereo vision. This task involves finding the corresponding points between two images of the same scene taken from different viewpoints.

The concept of disparity is crucial here, as it represents the difference in the position of a point between the left and right images, given by $x_{left} - x_{right}$ . This disparity is inversely proportional to the depth of the point in the scene.

For each pixel in the left image, find the best matching block in the right image along the epipolar line, which for rectified images, is the same row.
Calculate the disparity for each pixel based on the position of the best match.

The matching cost is the sum of squared differences (SSD) between the $b \times b$ block centred at $(y, x)$ in the left image and the block centred at $(y, x - d)$ in the right image, for each candidate $d = 0, 1, \dots, \text{max\_disp} - 1$ . The disparity is the $d$ with the smallest SSD (the smallest $d$ wins a tie).

Pixels within $\lfloor b/2 \rfloor$ of the top, bottom or right edge, and pixels with $x < \lfloor b/2 \rfloor + \text{max\_disp}$ , are left at disparity $0$ .

d = x_{left} - x_{right}

This technique is widely used in depth estimation and 3D reconstruction applications.

Example

Input

Stereo pair

Output

Disparity map

Reasoning

Inputs: left and right are a rectified grayscale pair, block_size is the square patch side $b$ , and max_disp counts the candidate shifts $d \in \{0, \dots, \text{max\_disp}-1\}$ .
Worked example: a $3 \times 8$ pair with every row $[10, 20, 80, 30, 60, 40, 90, 50]$ on the left and $[80, 30, 60, 40, 90, 50, 10, 20]$ on the right (scene shifted 2 pixels left), $b = 3$ , 3 shifts.
At the centre-row pixel in column 5, the left block rows are $[60, 40, 90]$ $[60, 40, 90]$ ; compare with the right block centred on column $5 - d$ $5 - d$ :
- $d=0$ : $3\,(30^2 + 10^2 + 80^2) = 22200$
- $d=1$ : $3\,(20^2 + 50^2 + 40^2) = 13500$
- $d=2$ : $0$ , a perfect match, so the disparity is $2$ .
Output: a disparity map the input's shape. Columns 4 to 6 of the middle row get $2$ ; columns 0 to 3 stay $0$ because $x < \lfloor 3/2 \rfloor + 3 = 4$ (the description's rule); column 7 and rows 0 and 2 stay $0$ because the $3 \times 3$ block would cross the right, top or bottom edge.
Notice: larger disparity means a closer object.

Constraints

Input images: 2D numpy arrays (grayscale) with shape (height, width) and pixel values in [0, 255]
Block size: odd integer between 3 and 31
Disparity range: integer values between 0 and width // 2
Output disparity map: 2D numpy array with shape (height, width) and dtype uint16
The input images are assumed to be rectified, with the epipolar line being the same row for corresponding pixels

Learn this in

Depth EstimationCV Study Plan Epipolar Geometry & Stereo Vision3D Computer Vision

More from CV: Depth Estimation

Plane Sweep Stereohard Epipolar Line Visualizationhard Ordinal Depth Ranking Lossmedium Depth Map Normalizationeasy Scale-Invariant Depth Lossmedium

Block Matching Disparity

Example

Constraints

Learn this in

More from CV: Depth Estimation

Background Knowledge

Continue the full explanation

Editor locked