Blockmatching

Blockmatching is an image and video processing technique in which a reference image or frame is divided into smaller rectangular areas called blocks, and for each block a search is performed within a defined window of a target image or subsequent frame to find the most similar block. The similarity is usually measured by a cost function such as sum of absolute differences, sum of squared differences, or normalized cross‑correlation. The result of the search is a motion vector that denotes the displacement of the block, which can then be used for motion compensation, compression, or error concealment.

The basic block‑matching algorithm begins by selecting a block of known size from the reference. A brute‑force search scans every possible displacement inside the search window, evaluating the chosen cost function for each candidate block in the target image. The displacement yielding the lowest cost is chosen as the best match. Because a full search is computationally expensive, several fast searching schemes have been devised. Examples include the Three‑Step Search, which reduces the search window iteratively; the Diamond Search, which uses diamond‑shaped search patterns; and the Hexagon Search, which approximates a full search with fewer candidate positions.

Blockmatching is widely used in video codecs such as H.264 and HEVC for motion estimation and compensation. It also appears in block‑based compression formats like JPEG‑2000 for intra prediction, in stereo disparity estimation, and for video quality assessment. The trade‑off between accuracy and computational load is a central concern; more sophisticated cost functions or search patterns can yield better matches but require additional processing.