📘

Semi-Global Matching Cost Aggregation

HardDepth Estimation 📚 Computer Vision 1

Implement the cost aggregation step of Semi-Global Matching (SGM) for one scanline direction.

Given a 2D cost volume for one scanline (rows = pixels along scanline, cols = disparity levels), along with penalties $P_1$ (for small disparity changes of $\pm 1$ ) and $P_2$ (for larger changes), compute the aggregated cost using the SGM recurrence.

For each pixel $p$ at disparity $d$ :

$L_r(p, d) = C(p, d) + \min\begin{cases} L_r(p-1, d) \\ L_r(p-1, d-1) + P_1 \\ L_r(p-1, d+1) + P_1 \\ \min_k L_r(p-1, k) + P_2 \end{cases} - \min_k L_r(p-1, k)$

where:

$C(p, d)$ is the raw matching cost at pixel $p$ for disparity $d$
$L_r(p-1, d)$ is the aggregated cost at the previous pixel
The subtraction of $\min_k L_r(p-1, k)$ prevents values from growing unboundedly

For the first pixel ( $p = 0$ ), $L_r(0, d) = C(0, d)$ .

Return the aggregated cost volume as a 2D list. Round values to 4 decimal places.

Example:

Input:

cost_volume = [[10, 20, 30],
               [15, 10, 25],
               [20, 15, 10]]
P1 = 5
P2 = 10

Output:

[[10, 20, 30], [15, 15, 35], [20, 15, 15]]

Reasoning:

We initialize the aggregated cost volume $L_r$ with the first row of the cost volume, since $L_r(0, d) = C(0, d)$ , resulting in $L_r(0, d) = [10, 20, 30]$ .
For the second pixel ( $p = 1$ ), we calculate $L_r(1, d)$ using the SGM recurrence. For example, at disparity $d = 1$ , we have $L_r(1, 1) = C(1, 1) + \min\{L_r(0, 1), L_r(0, 0) + 5, L_r(0, 2) + 5, \min_k L_r(0, k) + 10\} - \min_k L_r(0, k) = 15 + \min\{20, 10 + 5, 30 + 5, 10 + 10\} - 10 = 15 + \min\{20, 15, 35, 20\} - 10 = 15 + 15 - 10 = 20$ .
We repeat this process for all pixels and disparities, using the previously computed values of $L_r$ to calculate the next row.
The final aggregated cost volume is $L_r = [[10, 20, 30], [15, 15, 35], [20, 15, 15]]$ , which after rounding to 4 decimal places (no change in this case) gives the output.

Constraints:

cost_volume: 2D list of floats (pixels x disparities)
P1: float (penalty for disparity change of +/- 1)
P2: float (penalty for larger disparity changes, P2 >= P1)
Return: 2D list of aggregated costs
Round to 4 decimal places
Use pure Python

More from Computer Vision 1

Compute Depth Map from DisparityMedium Stereo Rectification CheckEasy Oriented BRIEF DescriptorHard Gaussian Scale SpaceMedium Non-Maximum Suppression (NMS)Easy

Background Knowledge

Semi-Global Matching (SGM) is a computer vision technique used for depth estimation in stereo vision. It's an improvement over local stereo matching methods, which can be sensitive to textureless areas and noise. SGM aggregates matching costs over multiple paths, making it more robust. The key concept here is the cost volume, which represents the matching cost between pixels in the left and right images at different disparity levels.

The cost aggregation step in SGM involves computing the aggregated cost for each pixel at each disparity level. This is done using a recurrence relation that considers the raw matching cost and the aggregated costs of neighboring pixels. The penalties $P_1$ and $P_2$ control the smoothness of the disparity map. $P_1$ is used for small disparity changes, while $P_2$ is used for larger changes. Understanding the SGM recurrence relation and how it's used to compute the aggregated cost is crucial for solving this problem.

The SGM recurrence relation is given by the equation: $L_r(p, d) = C(p, d) + \min\begin{cases} L_r(p-1, d) \\ L_r(p-1, d-1) + P_1 \\ L_r(p-1, d+1) + P_1 \\ \min_k L_r(p-1, k) + P_2 \end{cases} - \min_k L_r(p-1, k)$ . This equation shows how the aggregated cost at each pixel is computed based on the raw matching cost and the aggregated costs of neighboring pixels.

Algorithm/Approach

The algorithm for solving this problem involves iterating over each pixel in the scanline and computing the aggregated cost at each disparity level using the SGM recurrence relation. The approach can be broken down into the following steps:

Initialize the aggregated cost volume with the raw matching costs for the first pixel.
Iterate over each pixel in the scanline, starting from the second pixel.
For each pixel, iterate over each disparity level and compute the aggregated cost using the SGM recurrence relation.
Update the aggregated cost volume with the computed values.

👑

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.