Stereo Matching: Sum of Absolute Differences (SAD)

mediumFREEDepth EstimationArrays, Matrix, Local MethodsComputer Vision 1

The Sum of Absolute Differences (SAD) measures similarity between image patches for stereo matching:

SAD = Σ |I_L(r,c) - I_R(r,c+d)|

over a W×W window centered at (r,c).

Given left and right images, center coordinates (r,c), and disparity d, calculate SAD cost. Use 3×3 window. Only count pixels where both indices are valid.

Constraints:

W = 3 (fixed window)
Image values: 0-255
Handle boundary cases

Examples:

| Input | Output | |-------|--------| | Same 3×3 images, r=1, c=1, d=0 | 0 | | All 0s vs all 255s, r=1, c=1, d=0 | 2295 |

Example

Input

I_L=[[10,10,10],[10,10,10],[10,10,10]], I_R=[[10,10,10],[10,10,10],[10,10,10]], r=1, c=1, d=0

Output

Reasoning

The 3×3 window centered at $r=1, c=1$ covers all pixels in both $I_L$ and $I_R$ (indices $(0,0)$ to $(2,2)$ ).
With $d = 0$ , each pixel in $I_L$ is compared to the pixel at the same position in $I_R$ .
Every corresponding pair is $10$ vs $10$ , so each absolute difference is $|10 - 10| = 0$ .
Summing all 9 differences gives $SAD = 0$ , which is the final output.

More from Computer Vision 1

Semi-Global Matching Cost Aggregationhard Compute Depth Map from Disparitymedium Stereo Rectification Checkeasy Oriented BRIEF Descriptorhard Gaussian Scale Spacemedium

Concept primer

1. Background Knowledge

Sum of Absolute Differences (SAD) is a classic block-matching cost function for stereo correspondence. It measures pixel-wise intensity differences within a window:

$\text{SAD}(r, c, d) = \sum_{i,j \in W} |I_L(r+i, c+j) - I_R(r+i, c+j+d)|$

Properties:

Simple and fast (no multiplication)
Sensitive to noise and lighting changes
Used as baseline in stereo algorithms

2. Algorithm Approach

Center window at (r, c) in left image
Center window at (r, c+d) in right image
Sum absolute differences across all pixels in window

3. Step-by-Step Strategy

Compute window bounds: half = W // 2
Iterate over window positions
Check bounds for both images
Accumulate absolute differences

4. Common Pitfalls

Off-by-one errors in window bounds
Not handling image boundary conditions
Forgetting to apply disparity offset to right image column

5. Time & Space Complexity

Aspect	Complexity
Time	O(W²) per pixel
Space	O(1)

For full disparity map: O(H × W × D × W²) where D is disparity range.