📘

Winner-Take-All Disparity

Find the disparity that minimizes matching cost along an epipolar line.

In stereo matching, we search along the horizontal scanline (after rectification) to find the best matching pixel. The winner-take-all (WTA) strategy selects the disparity with minimum cost:

$d^* = \arg\min_d C(x, d)$

where $C(x, d)$ is the matching cost (e.g., SAD) at position $x$ for disparity $d$ .

This function implements a basic scanline stereo algorithm:

For each candidate disparity $d$ from 0 to max_disparity
Extract a block around $(x, y)$ in left image
Extract corresponding block at $(x-d, y)$ in right image
Compute SAD and track minimum

Example:

Input:

find_disparity([0,0,0,100,100,100,0,0], [100,100,100,0,0,0,0,0], 3, 5, 4)

Output:

Reasoning:

Searching for best disparity at x=4, block_size=3: Left block around x=4: [100, 100, 100] (indices 3,4,5)

Disparity 0: Right block [0, 0, 0] → SAD = 300
Disparity 1: Right block [100, 0, 0] → SAD = 200
Disparity 2: Right block [100, 100, 0] → SAD = 100
Disparity 3: Right block [100, 100, 100] → SAD = 0 ← minimum! Disparity 4: Right block [100, 100, 100] (would go to index 0)

Best disparity = 3 (perfect match)

Constraints:

left_row: intensity values from left image scanline
right_row: intensity values from right image scanline
block_size: width of matching window (odd number)
max_disparity: maximum disparity to search
x: center position in left image
Return disparity with minimum SAD

More from CV: Depth Estimation

Plane Sweep StereoHard Block Matching DisparityHard Epipolar Line VisualizationHard Ordinal Depth Ranking LossMedium Depth Map NormalizationEasy

In this problem, you are implementing the winner-take-all (WTA) step of a basic local stereo matching algorithm along a scanline: for each pixel, you evaluate a matching cost over candidate disparities and pick the disparity with minimum cost. This produces a disparity map that encodes relative depth from a rectified stereo pair.

1. Background Knowledge (Key Concepts)

Stereo matching & disparity After rectification, corresponding points in the left and right images lie on the same horizontal line (same $y$ ), but shifted in $x$ . The disparity $d$ at position $(x,y)$ is the horizontal shift between the matching pixels:

d = x_\text{left} - x_\text{right}

Larger disparity generally corresponds to closer objects (inversely related to depth).

Matching cost and cost volume For each pixel $(x,y)$ in the left image and each candidate disparity $d$ , you compute a matching cost $C(x,y,d)$ that measures how similar the left patch at $(x,y)$ is to the right patch at $(x-d,y)$ . Common local costs include sum of absolute differences (SAD) or sum of squared differences (SSD) over a window. Collectively, these costs form a 3D cost volume over $(x,y,d)$ .
Winner-Take-All (WTA) Given the cost volume, WTA simply picks, for each pixel, the disparity with minimum cost:

d^*(x,y) = \arg\min_d C(x,y,d)

It is a local decision (no smoothness constraints), easy to implement and a building block for more advanced methods.

2. Algorithm / General Approach

The general pattern for local stereo with WTA:

Loop over all pixels in the left image (or over a single scanline, depending on the task).
For each pixel, loop over all candidate disparities $d \in [0,$ \text{max_disparity} $)$ .
For each disparity:

Extract a window around $(x,y)$ in the left image.
Extract the shifted window around $(x-d,y)$ in the right image.
Compute the SAD cost between the two windows.

Track the disparity with minimum cost; assign it as the disparity for that pixel.

This is a straightforward brute-force search along the epipolar line using block matching.

3. Step-by-Step Strategy (Implementation Breakdown)

Assume:

Left image: left
Right image: right
Window radius: r (so window size is (2r+1) x (2r+1))
max_disparity given

Steps:

Initialize output

Create a disparity map disp of same width/height as input, e.g. np.zeros((H, W)).

👑

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

🔒

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.