SAD Block Matching Cost

mediumPROStereo MatchingStereoCV: Depth Estimation

Compute the Sum of Absolute Differences (SAD) between two image blocks.

SAD is a simple and efficient matching cost used in stereo correspondence:

$SAD = \sum_{i,j} |L(i,j) - R(i,j)|$

where $L$ and $R$ are corresponding blocks from the left and right images.

Properties of SAD:

Fast to compute (no multiplications)
Robust to small intensity differences
Lower values indicate better matches
Often used with block sizes like 5×5, 7×7, or 9×9

SAD is the simplest block matching metric. SSD (sum of squared differences) and NCC (normalized cross-correlation) are more robust alternatives.

Example

Input

sad([[1,2],[3,4]], [[1,2],[3,4]])

Output

Reasoning

Inputs: block_left and block_right are two $2 \times 2$ patches of pixel intensities, one from each image of a stereo pair. Pixel $(i, j)$ of one is compared with pixel $(i, j)$ of the other.
Left block: $L = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}$ . Right block: $R = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}$ .
Per-pixel differences: $|1-1| = 0$ , $|2-2| = 0$ , $|3-3| = 0$ , $|4-4| = 0$ . The absolute value makes too dark and too bright cost the same.
Sum: $SAD = 0 + 0 + 0 + 0 = 0$ , so the output is 0.
Output: a single integer, the total mismatch over all four pixels. Zero is the minimum: a perfect match.
Notice that the cost counts every unit of disagreement: if every right pixel were 1 brighter than its left partner (say left $10, 20, 30, 40$ and right $11, 21, 31, 41$ ), SAD would be $1+1+1+1 = 4$ even though the patterns look alike.

Constraints

block_left: 2D array representing a patch from the left image
block_right: 2D array of same size from the right image
Return the SAD value (integer)

Learn this in

Depth EstimationCV Study Plan Epipolar Geometry & Stereo Vision3D Computer Vision

More from CV: Depth Estimation

Plane Sweep Stereohard Block Matching Disparityhard Epipolar Line Visualizationhard Ordinal Depth Ranking Lossmedium Depth Map Normalizationeasy

Concept primerPREVIEW

SAD (Sum of Absolute Differences) is a local matching cost used in stereo vision to compare two same-sized blocks (windows) from the left and right images and measure how similar they are. For each pixel position $(i, j)$ in the block, you take the absolute difference in intensity between the left block $L(i,j)$ and right block $R(i,j)$ and sum these differences over the whole block. Lower SAD means the blocks are more similar and thus more likely to be a correct match along the epipolar line.

In a full stereo matching pipeline, SAD is used to build a cost volume: for each pixel and candidate disparity, you compute the SAD between a block centered at that pixel in the left image and a shifted block in the right image. Then later stages (aggregation, optimization, refinement) use these costs to choose the best disparity and produce a depth map. For this coding problem, you are looking at the inner core of that process: computing the SAD value between two already-aligned blocks of equal size.

1. Background Knowledge

Block / window in an image An image can be seen as a 2D array of pixel intensities (for grayscale) or 3D (H×W×C for color). A block (or patch/window) is a small subarray, e.g., $5 \times 5$ pixels, taken from a location in the image. In stereo, you assume corresponding points lie along the same scanline (row) after rectification, so blocks are compared at shifted horizontal positions.
SAD formula For two blocks $L$ and $R$ of the same height $H$ and width $W$ :

SAD(L, R) = \sum_{i=0}^{H-1} \sum_{j=0}^{W-1} |L(i,j) - R(i,j)|

This is a simple L1 distance over the block’s pixels. It requires only subtraction, absolute value, and addition (no multiplications), so it is fast and hardware-friendly.

Relation to other costs
SSD: sum of squared differences; penalizes larger errors more strongly.
NCC: normalized cross-correlation; more robust to global brightness changes but more expensive to compute. SAD is often the baseline: simple, fast, and reasonably robust to small intensity noise, but less robust than SSD/NCC to lighting changes or low-texture regions.

2. Algorithm / Approach

For this specific problem, the pattern is straightforward:

You are given two same-sized blocks (left and right).
Iterate over all pixel positions in the block.
For each pixel:

Compute the absolute difference of the corresponding intensities.
Accumulate this into a running sum.

Return the final sum as the SAD value.

Conceptually, this is just computing the L1 distance between two vectors formed by flattening the blocks.

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.

PRO

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