﻿

# Semi-Global Block-Matching Algorithm

NI Vision 2012 Concepts Help

Edition Date: June 2012

Part Number: 372916M-01

»View Product Info
This algorithm aims to minimize the following global energy function, E, for disparity image, D.
with P2P1

where
E(D) is the energy for disparity image, D
p, q represent indices for pixels in the image
Np is the neighborhood of the pixel p
C(p, Dp) is the cost of pixel matching with disparity in Dp
P1 is the penalty passed by the user for a change in disparity values of 1 between neighboring pixels
P2 is the penalty passed by the user for a change in disparity values greater than 1 between neighboring pixels
I[.] is the function which returns 1 if the argument is true and 0 otherwise

The minimized function produces a perfect disparity map with smoothing governed by parameters P1 and P2; however, minimizing the function for a 2D image space is an NP-complete problem. The semi-global matching function approximates the 2D minimization by performing multiple 1D, or linear, minimizations. The matching function aggregates costs on multiple paths which converge on the pixel under examination. Cost is computed for the disparity range specified by the minimum disparity and number of disparities parameters. By default, the matching algorithm aggregates costs for 5 directions. You can set the full dynamic programming parameter to true to force the algorithm to aggregate costs for 8 directions.

Let, S(p, d) be the aggregate cost for pixel p and disparity d. Then

where
r is a direction used for converging to the pixel p
Lr(p, d) is the minimum cost of the path taken in direction r from pixel (p for disparity d

The cost Lr(p, d) is given in the following equation:
The equation uses the following costs to find the disparity by adding current cost, C(p, d, to previous pixel in direction r:
• The minimum of the cost at previous pixel with disparity d
• The cost at previous pixel with disparity d - 1 and d + 1 with added penalty P1
• The cost at previous pixel with disparities less than d - 1 and greater than d + 1 with added penalty P2
In order to limit the ever increasing value of Lr(p, d) on the path, minimum value of the previous pixel is subtracted. The upper value of Lr(p, d) is bounded by Cmax + P2, where Cmax is the maximum value of cost C. The cost function C(p, d) is computed in the following manner:

where
IL and IR are left and right rectified images, respectively

The value of C is aggregated over a window of a user-defined size1. After computing S(p, d) for each pixel p for each disparity d, the algorithm chooses the disparity which provides the minimum cost for that pixel.

The complexity of this algorithm is given in the following equation:

where
w equals the width of the rectified image
h equals the height of the rectified image
n equals the number of disparities

1 Birchfield, S. and Tomasi, C. 1999. Depth Discontinuities by Pixel-to-Pixel StereoIJCV35(3):269-293.

Your Feedback!  Poor  |  Excellent    Yes No
 Document Quality?