Semi-Global Matching Cost Aggregation

hardPRODepth EstimationComputer 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

Learn this in

Depth EstimationCV Study Plan Epipolar Geometry & Stereo Vision3D Computer Vision

More from Computer Vision 1

Compute Depth Map from Disparitymedium Stereo Rectification Checkeasy Oriented BRIEF Descriptorhard Gaussian Scale Spacemedium Non-Maximum Suppression (NMS)easy

Concept primerPREVIEW

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.

PRO

Continue the full explanation

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