SAD Block Matching Cost
Compute the Sum of Absolute Differences (SAD) between two image blocks.
SAD is a simple and efficient matching cost used in stereo correspondence:
SAD=∑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:
sad([[1,2],[3,4]], [[1,2],[3,4]])
0
-
Computing SAD for identical blocks: |1-1| + |2-2| + |3-3| + |4-4| = 0 + 0 + 0 + 0 = 0
-
Identical blocks have zero SAD (perfect match).
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)
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×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:
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.
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.