Winner-Take-All Disparity

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:

1. Loop over all pixels in the left image (or over a single scanline, depending on the task).
2. For each pixel, loop over all candidate disparities $d \in [0,$\text{max_disparity}$)$.
3. 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.

4. 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:

1. Initialize output

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