Hubbry Logo
search
logo
Block-matching algorithm avatar
Block-matching algorithm
Block-matching algorithm
current hub
1913090

Block-matching algorithm

logo
Community Hub0 Subscribers
Read side by side
Block-matching algorithm
View on Wikipedia
from Wikipedia

A Block Matching Algorithm is a way of locating matching macroblocks in a sequence of digital video frames for the purposes of motion estimation. The underlying supposition behind motion estimation is that the patterns corresponding to objects and background in a frame of video sequence move within the frame to form corresponding objects on the subsequent frame. This can be used to discover temporal redundancy in the video sequence, increasing the effectiveness of inter-frame video compression by defining the contents of a macroblock by reference to the contents of a known macroblock which is minimally different.

A block matching algorithm involves dividing the current frame of a video into macroblocks and comparing each of the macroblocks with a corresponding block and its adjacent neighbors in a nearby frame of the video (sometimes just the previous one). A vector is created that models the movement of a macroblock from one location to another. This movement, calculated for all the macroblocks comprising a frame, constitutes the motion estimated in a frame.

The search area for a good macroblock match is decided by the ‘search parameter’, p, where p is the number of pixels on all four sides of the corresponding macro-block in the previous frame. The search parameter is a measure of motion. The larger the value of p, larger is the potential motion and the possibility for finding a good match. A full search of all potential blocks however is a computationally expensive task. Typical inputs are a macroblock of size 16 pixels and a search area of p = 7 pixels.

Block-matching and 3D filtering makes use of this approach to solve various image restoration inverse problems such as noise reduction[1] and deblurring[2] in both still images and digital video.

Motivation

[edit]

Motion estimation is the process of determining motion vectors that describe the transformation from one 2D image to another; usually from adjacent frames in a video sequence. The motion vectors may relate to the whole image (global motion estimation) or specific parts, such as rectangular blocks, arbitrary shaped patches or even per pixel. The motion vectors may be represented by a translational model or many other models that can approximate the motion of a real video camera, such as rotation and translation in all three dimensions and zoom.

Applying the motion vectors to an image to predict the transformation to another image, on account of moving camera or object in the image is called motion compensation. The combination of motion estimation and motion compensation is a key part of video compression as used by MPEG 1, 2 and 4 as well as many other video codecs.

Motion estimation based video compression helps in saving bits by sending encoded difference images which have inherently less entropy as opposed to sending a fully coded frame. However, the most computationally expensive and resource extensive operation in the entire compression process is motion estimation. Hence, fast and computationally inexpensive algorithms for motion estimation is a need for video compression.

Evaluation Metrics

[edit]

A metric for matching a macroblock with another block is based on a cost function. The most popular in terms of computational expense is:

Mean difference or Mean Absolute Difference (MAD) =

Mean Squared Error (MSE) =

where N is the size of the macro-block, and and are the pixels being compared in current macroblock and reference macroblock, respectively.

The motion compensated image that is created using the motion vectors and macroblocks from the reference frame is characterized by Peak signal-to-noise ratio (PSNR),

Algorithms

[edit]

Block Matching algorithms have been researched since mid-1980s. Many algorithms have been developed, but only some of the most basic or commonly used have been described below.

[edit]

This algorithm calculates the cost function at each possible location in the search window. This leads to the best possible match of the macro-block in the reference frame with a block in another frame. The resulting motion compensated image has highest peak signal-to-noise ratio as compared to any other block matching algorithm. However this is the most computationally extensive block matching algorithm among all. A larger search window requires greater number of computations.

Optimized Hierarchical Block Matching (OHBM)

[edit]

The optimized hierarchical block matching (OHBM) algorithm speeds up the exhaustive search based on the optimized image pyramids.[3]

[edit]

It is one of the earliest fast block matching algorithms. It runs as follows:

  1. Start with search location at center
  2. Set step size S = 4 and search parameter p = 7
  3. Search 8 locations +/- S pixels around location (0,0) and the location (0,0)
  4. Pick among the 9 locations searched, the one with minimum cost function
  5. Set the new search origin to the above picked location
  6. Set the new step size as S = S/2
  7. Repeat the search procedure until S = 1

The resulting location for S=1 is the one with minimum cost function and the macro block at this location is the best match.

There is a reduction in computation by a factor of 9 in this algorithm. For p=7, while ES evaluates cost for 225 macro-blocks, TSS evaluates only for 25 macro blocks.

[edit]

TDLS is closely related to TSS however it is more accurate for estimating motion vectors for a large search window size. The algorithm can be described as follows,

  1. Start with search location at the center
  2. Select an initial step size say, S = 8
  3. Search for 4 locations at a distance of S from center on the X and Y axes
  4. Find the location of point with least cost function
  5. If a point other than center is the best matching point,
    1. Select this point as the new center
  6. If the best matching point is at the center, set S = S/2
  7. Repeat steps 2 to 3
  8. If S = 1, all 8 locations around the center at a distance S are searched
  9. Set the motion vector as the point with least cost function
[edit]

TSS uses a uniformly allocated checking pattern and is prone to miss small motions. NTSS [4] is an improvement over TSS as it provides a center biased search scheme and has provisions to stop halfway to reduce the computational cost. It was one of the first widely accepted fast algorithms and frequently used for implementing earlier standards like MPEG 1 and H.261.

The algorithm runs as follows:

  1. Start with search location at center
  2. Search 8 locations +/- S pixels with S = 4 and 8 locations +/- S pixels with S = 1 around location (0,0)
  3. Pick among the 16 locations searched, the one with minimum cost function
  4. If the minimum cost function occurs at origin, stop the search and set motion vector to (0,0)
  5. If the minimum cost function occurs at one of the 8 locations at S = 1, set the new search origin to this location
    1. Check adjacent weights for this location, depending on location it may check either 3 or 5 points
  6. The one that gives lowest weight is the closest match, set the motion vector to that location
  7. If the lowest weight after the first step was one of the 8 locations at S = 4, the normal TSS procedure follows
    1. Pick among the 9 locations searched, the one with minimum cost function
    2. Set the new search origin to the above picked location
    3. Set the new step size as S = S/2
    4. Repeat the search procedure until S = 1

Thus this algorithm checks 17 points for each macro-block and the worst-case scenario involves checking 33 locations, which is still much faster than TSS

[edit]

The idea behind TSS is that the error surface due to motion in every macro block is unimodal. A unimodal surface is a bowl shaped surface such that the weights generated by the cost function increase monotonically from the global minimum. However a unimodal surface cannot have two minimums in opposite directions and hence the 8 point fixed pattern search of TSS can be further modified to incorporate this and save computations. SES [5] is the extension of TSS that incorporates this assumption.

SES algorithm improves upon TSS algorithm as each search step in SES is divided into two phases:

• First Phase : 

     • Divide the area of search in four quadrants
     • Start search with three locations, one at center (A) and others (B and C), S=4 locations away from A in orthogonal directions
     • Find points in search quadrant for second phase using the weight distribution for A, B, C:
            • If (MAD(A)>=MAD(B) and MAD(A)>=MAD(C)), select points in second phase quadrant IV
            • If (MAD(A)>=MAD(B) and MAD(A)<=MAD(C)), select points in second phase quadrant I
            • If (MAD(A)<MAD(B) and MAD(A)<MAD(C)), select points in second phase quadrant II
            • If (MAD(A)<MAD(B) and MAD(A)>=MAD(C)), select points in second phase quadrant III

• Second Phase: 

     • Find the location with lowest weight
     • Set the new search origin as the point found above

• Set the new step size as S = S/2

• Repeat the SES search procedure until S=1

• Select the location with lowest weight as motion vector SES is computationally very efficient as compared to TSS. However the peak signal-to-noise ratio achieved is poor as compared to TSS as the error surfaces are not strictly unimodal in reality.

[edit]

Four Step Search is an improvement over TSS in terms of lower computational cost and better peak signal-to-noise ratio. Similar to NTSS, FSS [6] also employs center biased searching and has a halfway stop provision.

The algorithm runs as follows:

  1. Start with search location at center
  2. Set step size S = 2, (irrespective of search parameter p)
  3. Search 8 locations +/- S pixels around location (0,0)
  4. Pick among the 9 locations searched, the one with minimum cost function
  5. If the minimum weight is found at center for search window:
    1. Set the new step size as S = S/2 (that is S = 1)
    2. Repeat the search procedure from steps 3 to 4
    3. Select location with the least weight as motion vector
  6. If the minimum weight is found at one of the 8 locations other than the center:
    1. Set the new origin to this location
    2. Fix the step size as S = 2
    3. Repeat the search procedure from steps 3 to 4. Depending on location of new origin, search through 5 locations or 3 locations
    4. Select the location with the least weight
    5. If the least weight location is at the center of new window go to step 5, else go to step 6
[edit]

Diamond Search (DS)[7] algorithm uses a diamond search point pattern and the algorithm runs exactly the same as 4SS. However, there is no limit on the number of steps that the algorithm can take.

Two different types of fixed patterns are used for search,

  • Large Diamond Search Pattern (LDSP)
  • Small Diamond Search Pattern (SDSP)

The algorithm runs as follows:

  • LDSP:
    1. Start with search location at center
    2. Set step size S = 2
    3. Search 8 locations pixels (X,Y) such that (|X|+|Y|=S) around location (0,0) using a diamond search point pattern
    4. Pick among the 9 locations searched, the one with minimum cost function
    5. If the minimum weight is found at center for search window, go to SDSP step
    6. If the minimum weight is found at one of the 8 locations other than the center, set the new origin to this location
    7. Repeat LDSP
  • SDSP:
    1. Set the new search origin
    2. Set the new step size as S = S/2 (that is S = 1)
    3. Repeat the search procedure to find location with least weight
    4. Select location with the least weight as motion vector

This algorithm finds the global minimum very accurately as the search pattern is neither too big nor too small. Diamond Search algorithm has a peak signal-to-noise ratio close to that of Exhaustive Search with significantly less computational expense.

[edit]

Adaptive rood pattern search (ARPS) [8] algorithm makes use of the fact that the general motion in a frame is usually coherent, i.e. if the macro blocks around the current macro block moved in a particular direction then there is a high probability that the current macro block will also have a similar motion vector. This algorithm uses the motion vector of the macro block to its immediate left to predict its own motion vector.

Adaptive rood pattern search runs as follows:

  1. Start with search location at the center (origin)
  2. Find the predicted motion vector for the block
  3. Set step size S = max (|X|,|Y|), where (X,Y) is the coordinate of predicted motion vector
  4. Search for rood pattern distributed points around the origin at step size S
  5. Set the point with least weight as origin
  6. Search using small diamond search pattern (SDSP) around the new origin
  7. Repeat SDSP search until least weighted point is at the center of SDSP

Rood pattern search directly puts the search in an area where there is a high probability of finding a good matching block. The main advantage of ARPS over DS is if the predicted motion vector is (0, 0), it does not waste computational time in doing LDSP, but it directly starts using SDSP. Furthermore, if the predicted motion vector is far away from the center, then again ARPS saves on computations by directly jumping to that vicinity and using SDSP, whereas DS takes its time doing LDSP.

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Block-matching algorithm

View on Grokipedia
from Grokipedia
The block-matching algorithm (BMA) is a widely used method for motion estimation in video coding and image processing, which involves dividing a video frame into non-overlapping blocks of pixels (typically 8×8 or 16×16) and searching for the most similar block in a reference frame to compute displacement vectors representing motion.[1] This approach assumes uniform translational motion within each block and minimizes a distortion metric, such as the sum of absolute differences (SAD) or mean absolute difference (MAD), to find the optimal match within a defined search window.[2] By estimating these motion vectors, BMA enables efficient temporal redundancy reduction in video sequences, forming a cornerstone of standards like MPEG and H.264.[3] In operation, the algorithm evaluates candidate blocks in the reference frame against the current block using criteria like SAD, which sums the absolute differences of corresponding pixel intensities, or alternatives such as mean squared difference (MSD) for quadratic error measurement.[1] The full-search variant exhaustively checks all positions in the search area for the minimum distortion, ensuring optimal accuracy but at high computational cost, while faster approximations limit evaluations to reduce complexity.[4] Search strategies often employ logarithmic or diamond patterns to approximate the global minimum efficiently, balancing speed and precision for real-time applications.[3] Historically, block matching emerged in the late 1980s as part of early video coding efforts, with its first standardization in the H.261 codec for videotelephony in 1990, using 16×16 macroblocks for integer-pixel motion compensation.[3] Subsequent advancements in MPEG-1 (1992) and MPEG-2 (1994) refined block sizes and added half-pixel accuracy, while H.264/AVC (2003) introduced variable block sizes down to 4×4 for better adaptability to complex motions.[3] Beyond video compression, BMA has applications in medical imaging for registering frames, such as aligning lung CT scans, and in computer vision for object tracking.[2] Variants of BMA address computational demands through techniques like three-step search, hierarchical block matching for multi-resolution analysis, or GPU-accelerated implementations that achieve up to 200-fold speedups in integer searches.[1] Despite its simplicity and effectiveness, challenges include handling non-translational motions or occlusions, prompting ongoing research into hybrid methods combining BMA with optical flow or machine learning for improved robustness.[4]

Overview

Definition and Principles

The block-matching algorithm is a core technique for motion estimation in video processing and compression, operating by dividing the current frame into fixed-size, non-overlapping blocks—commonly referred to as macroblocks, typically measuring 16×16 pixels—and identifying the most similar block in a reference frame, such as the previous consecutive frame in a video sequence.[5] This approach estimates the displacement of each block to represent local motion, enabling the prediction of pixel values across frames and reducing temporal redundancy. At its foundation, the algorithm assumes that motion within a block occurs as a uniform translation, where all pixels in the block shift by the same amount without rotation, scaling, or deformation; this pixel-level motion model supports integer pixel accuracy for computational simplicity and efficiency. The process begins by partitioning the current frame into these macroblocks. For a given block centered at position (x,y)(x, y) in the current frame, a search window—often a rectangular area centered on the corresponding position in the reference frame, with a width defined by a maximum displacement parameter (e.g., ±7 pixels)—is examined to find the best match. The displacement vector (Δx,Δy)(\Delta x, \Delta y) is then computed as the offset from the matching position in the reference frame to (x,y)(x, y) in the current frame, serving as the motion vector for that block.[5] To illustrate, consider a block extracted from the top-left corner of the current frame at coordinates (x,y)(x, y); the algorithm scans candidate blocks within the search window in the reference frame and selects the one at (x−Δx,y−Δy)(x - \Delta x, y - \Delta y) that exhibits the closest pixel correspondence, where the motion vector (Δx,Δy)(\Delta x, \Delta y) represents the displacement from the reference position to the current position, effectively capturing the block's translational shift. This vector-based representation allows for straightforward reconstruction of the current frame by shifting and differencing blocks from the reference, forming the basis for predictive coding in video systems.[5]

Historical Development

The block-matching algorithm originated in the 1980s amid early research on video compression for telephony applications, where motion compensation techniques were developed to exploit temporal redundancy in image sequences. It was first standardized in the ITU-T H.261 recommendation in 1990, introducing block-based motion estimation with 16×16 pixel macroblocks and a limited search range of ±7 pixels to enable efficient coding for video conferencing over ISDN lines at bit rates up to 2 Mbit/s.[6] The algorithm gained widespread adoption through subsequent standards in the 1990s. MPEG-1 (ISO/IEC 11172-2, 1993) incorporated block matching for motion-compensated prediction in video storage media, supporting progressive-scan formats at up to 1.5 Mbit/s for applications like CD-ROM video. MPEG-2 (ISO/IEC 13818-2, 1995) extended this framework to broadcast and DVD applications, accommodating interlaced video and higher resolutions while relying on block-based motion vectors for inter-frame prediction.[7] ITU-T H.263 (1996) further refined the approach for low-bitrate scenarios, adding half-pixel motion accuracy and optional overlapped block motion compensation to improve efficiency over H.261. A key evolution occurred in response to growing computational demands, with exhaustive search methods giving way to faster alternatives during the 1990s research surge; this shift addressed real-time encoding needs in emerging digital video systems without sacrificing significant predictive accuracy. H.264/AVC (ITU-T H.264, 2003) marked a major advancement by introducing variable block sizes (from 4×4 to 16×16 pixels), multiple reference frames, and weighted prediction, enhancing compression ratios by up to 50% over prior standards. In more recent developments through 2025, block matching has remained integral to hybrid coding frameworks. High Efficiency Video Coding (HEVC, H.265; ITU-T, 2013) expanded block structures to coding tree units up to 64×64 pixels with adaptive partitioning, balancing complexity and performance for 4K/8K video. Versatile Video Coding (VVC, H.266; ITU-T, 2020) built on this with affine motion models and decoder-side estimation, achieving about 30-50% better efficiency than HEVC, though the core block-based paradigm persists amid explorations of machine learning for alternative motion estimation.

Theoretical Foundations

Block Partitioning and Motion Vectors

In the block-matching algorithm, the current frame $ I_t $ is divided into non-overlapping rectangular blocks $ B(i,j) $ of fixed size $ N \times N $, where $ i $ and $ j $ index the block positions along the horizontal and vertical directions, respectively, and $ N $ is typically 16 pixels to balance computational efficiency and motion approximation accuracy.[8] This partitioning assumes that motion within each small block can be adequately modeled as a uniform translation, simplifying the estimation process while capturing local displacements between consecutive frames. For each block $ B(i,j) $ in $ I_t $, a motion vector $ \mathbf{MV} = (d_x, d_y) $ is computed as the displacement to the best-matching block in the reference frame $ I_{t-1} $. The optimal vector is determined by minimizing a distortion measure $ D $ over candidate positions within a predefined search range, typically $ [-p, p] $ pixels in both directions, where $ p $ is chosen based on expected motion (e.g., $ p = 5 $). Mathematically,
MV=arg⁡min⁡(u,v)∈[−p,p]2D(B(i,j),B′(i+u,j+v)), \mathbf{MV} = \arg\min_{(u,v) \in [-p,p]^2} D\left( B(i,j), B'(i+u, j+v) \right),
with $ B' $ denoting blocks from $ I_{t-1} $ and $ D $ quantifying the mismatch, such as mean squared error.[8] These vectors enable motion-compensated prediction by shifting blocks according to their displacements, reducing temporal redundancy in video sequences. In modern implementations, such as the H.264/AVC standard, fixed block sizes have been extended to variable partitioning within 16×16 macroblocks to improve accuracy for complex motions, such as at object edges or in textured regions, versus larger blocks for uniform areas. Supported partitions include 16×16, 16×8, 8×16, 8×8, 8×4, 4×8, and 4×4 luma blocks, allowing up to 16 motion vectors per macroblock for finer granularity. To enhance precision beyond integer-pixel displacements, sub-pixel motion vectors are estimated using interpolation of reference frame pixels, achieving half- or quarter-pixel accuracy. Common methods include bilinear interpolation, which computes intermediate values as weighted averages of neighboring integer pixels, thereby refining matches and reducing prediction errors in smooth or low-contrast areas.

Matching Criteria and Cost Functions

In block-matching algorithms for motion estimation, the quality of a match between a block from the current frame ItI_t at position (x,y)(x, y) and a candidate block from the reference frame It−1I_{t-1} at displacement (dx,dy)(dx, dy) is quantified using distortion metrics that measure pixel-wise differences over the block's N×NN \times N pixels. The sum of absolute differences (SAD) is one of the most commonly employed criteria due to its computational efficiency and simplicity, defined as D=∑(i,j)∈B∣It(x+i,y+j)−It−1(x+dx+i,y+dy+j)∣D = \sum_{(i,j) \in B} |I_t(x+i, y+j) - I_{t-1}(x+dx+i, y+dy+j)|, where BB denotes the block region.[8] This metric minimizes the total absolute deviation, providing a robust estimate for uniform motion but requiring integer arithmetic only.[9] The mean absolute error (MAE), equivalently SAD normalized by the block area N2N^2, offers a per-pixel average distortion, facilitating comparisons across varying block sizes.[8] The sum of squared differences (SSD) serves as an alternative criterion, computed as D=∑(i,j)∈B[It(x+i,y+j)−It−1(x+dx+i,y+dy+j)]2D = \sum_{(i,j) \in B} [I_t(x+i, y+j) - I_{t-1}(x+dx+i, y+dy+j)]^2, which emphasizes larger pixel discrepancies through quadratic penalization and aligns with least-squares optimization principles.[8] While SSD can yield more accurate motion vectors in low-noise scenarios by amplifying significant errors, it is computationally more demanding due to multiplications and exhibits greater sensitivity to outliers compared to SAD.[9] In advanced video codecs, matching criteria incorporate rate-distortion optimization to balance prediction accuracy against encoding overhead, using a Lagrangian cost function J=D+λRJ = D + \lambda R, where DD is the distortion (e.g., SAD or SSD), RR represents the bit cost for encoding the motion vector, and λ\lambda is a Lagrange multiplier tuned to the target bitrate. This approach, integral to standards like H.264/AVC, selects motion vectors that minimize overall compression inefficiency rather than distortion alone. Despite their prevalence, SAD and SSD are susceptible to degradation from image noise, where outliers disproportionately affect SSD, and illumination variations, which introduce systematic biases in pixel intensities.[10] To mitigate these issues, robust alternatives such as the census transform have been proposed, which encodes local spatial relations into binary strings invariant to monotonic intensity changes, enhancing reliability in non-ideal conditions without delving into parametric assumptions.[11]

Applications and Motivation

Video Compression Standards

Block-matching algorithms form the core of motion-compensated prediction in major video compression standards, where they generate motion vectors (MVs) to predict blocks in current frames from reference frames, thereby reducing temporal redundancy and achieving substantial bitrate savings.[12] In these pipelines, the algorithm divides frames into blocks, searches for matching blocks in reference frames using criteria like sum of absolute differences, and encodes only the residual differences along with MVs, enabling efficient compression for applications such as streaming and broadcasting.[13] Early standards like H.261 and H.263 employ fixed 16x16 macroblocks for block-matching, with H.261 relying on integer-pixel accuracy and exhaustive or simple fast search methods within a limited range to estimate motion for real-time videoconferencing at low bitrates.[12] H.263 builds on this by introducing half-pixel precision and optional unrestricted motion vectors, while still using primarily 16x16 blocks but supporting 8x8 sub-blocks in advanced modes for better adaptation to complex motion.[13] MPEG-4 Visual, an extension for object-based coding, incorporates similar block-matching with 16x16 macroblocks and quarter-pixel accuracy in later profiles, allowing for more flexible motion compensation in diverse video content.[14] The H.264/AVC standard advances block-matching by introducing multiple reference frames (up to 16) and adaptive block partitioning modes, enabling variable block sizes from 16x16 down to 4x4 pixels to better capture fine-grained motion details.[15] This flexibility, combined with quarter-sample accuracy, contributes to up to 50% bitrate savings over predecessors like MPEG-4 and H.263 for equivalent video quality, making it suitable for high-definition broadcasting and mobile streaming.[16] Evolving further, the HEVC (H.265) standard supports larger blocks up to 64x64 pixels alongside smaller ones, incorporating parallel processing techniques to handle increased computational demands while achieving another 50% efficiency gain over H.264, particularly beneficial for 4K and 8K content delivery.[17] The Versatile Video Coding (VVC, H.266) standard, finalized in 2020, further enhances block-matching with coding tree units up to 128×128 pixels, advanced motion vector prediction, and tools like affine motion compensation, delivering approximately 30–50% bitrate reduction over HEVC for the same quality, supporting immersive formats like 360-degree video and high-frame-rate content as of 2025.[18] These implementations address key challenges in real-time encoding, where the high computational complexity of exhaustive block-matching—potentially requiring billions of operations per frame—necessitates fast search algorithms to meet bandwidth constraints without sacrificing quality.[19] By mandating or recommending such optimizations, standards ensure practical deployment in resource-limited environments like live video transmission.[15]

Other Computer Vision Tasks

Block-matching algorithms extend beyond video compression to various computer vision tasks that require estimating correspondences between image regions, enabling applications in analysis and reconstruction. These methods partition images into blocks and compute similarity metrics to identify matches, facilitating tasks such as depth perception and motion analysis without the constraints of encoding efficiency.[20] In stereo vision, block matching is widely employed for depth estimation by comparing blocks across rectified left and right images to generate disparity maps, which are then used to reconstruct 3D scenes. The process involves sliding a reference block from one image over candidate positions in the other and selecting the disparity that minimizes a cost function, such as sum of absolute differences, to determine pixel offsets corresponding to depth. This approach is particularly valuable in robotics, where disparity maps inform obstacle avoidance and navigation; for instance, mobile robots use block matching on stereo pairs to estimate distances in indoor environments, achieving real-time performance with hardware implementations. Seminal evaluations highlight block matching as a foundational local method in stereo correspondence, balancing computational simplicity with accuracy on benchmark datasets like Middlebury.[20][21][20] For optical flow computation, block matching estimates dense motion fields by tracking block displacements between consecutive frames, extending the integer motion vector concept to sub-pixel precision through interpolation or multi-resolution strategies. Unlike sparse feature tracking, this yields per-pixel flow vectors useful for understanding scene dynamics, with applications in video stabilization—where flow compensates for camera shake—and action recognition, where motion patterns classify human activities. Multiresolution block matching, in particular, refines coarse estimates at lower resolutions before propagating to finer scales, improving robustness to large motions as surveyed in comprehensive optical flow literature. Cost functions may be adapted for robustness to outliers, such as incorporating robustness to illumination changes.[22][22][22] Object tracking leverages block matching to follow regions of interest across frames in surveillance and augmented reality systems, often employing adaptive window sizes to handle scale variations or partial occlusions. By repeatedly matching a template block of the target object against search regions in subsequent images, the algorithm predicts trajectories, with refinements like predictive search patterns reducing computational load for real-time operation. In surveillance, this enables monitoring moving entities like vehicles or pedestrians, while in augmented reality, it overlays virtual elements on tracked physical objects, demonstrating effectiveness in controlled environments as explored in early block-based tracking studies.[23][23] In medical imaging, block matching facilitates registration of multimodal scans, such as aligning MRI and CT images over time to track anatomical changes or plan interventions. The technique identifies corresponding blocks across volumes using similarity measures like normalized cross-correlation, then derives a global transformation—often affine—to warp one image onto the other, improving alignment for fused visualization. Symmetric block-matching approaches enhance robustness by considering correspondences bidirectionally, reducing bias in rigid registrations of brain or pelvic scans, as validated on phantom and clinical datasets. This method supports applications like tumor monitoring in longitudinal studies, where precise correspondences mitigate artifacts from patient motion.[24][24][25]

Search Algorithms

Exhaustive Search

The exhaustive search algorithm, also known as full search, is a brute-force method that evaluates the matching cost function for every candidate displacement position within a defined search window to determine the optimal motion vector for each block. In this approach, the current frame is partitioned into non-overlapping blocks, typically of size N×NN \times N, and for each block, the cost—commonly the sum of absolute differences (SAD)—is computed across all positions in a search window centered at the block's location and extending by pp pixels in all directions. The displacement (dx,dy)(dx, dy) yielding the minimum cost is selected as the motion vector. This approach is a foundational brute-force method used in early block-matching techniques for interframe coding.[26] The selection of the motion vector can be expressed mathematically as:
\MV=arg min⁡(dx,dy)∈W\SAD(B,B(dx,dy)′) \MV = \argmin_{(dx, dy) \in W} \SAD(B, B_{(dx, dy)}')
where W=[−p,p]×[−p,p]W = [-p, p] \times [-p, p] defines the search window, BB is the block from the current frame, B(dx,dy)′B_{(dx, dy)}' is the candidate block from the reference frame shifted by (dx,dy)(dx, dy), and SAD measures the sum of absolute pixel differences between the blocks (as elaborated in the matching criteria section).[26] Assuming a frame of size M×MM \times M divided into (M/N)2(M/N)^2 blocks, the algorithm's computational complexity is O((M/N)2⋅(2p+1)2)O((M/N)^2 \cdot (2p+1)^2) per frame, arising from the exhaustive evaluation of all candidate positions for every block.[27] Exhaustive search offers the advantage of guaranteeing the global optimum motion vector, independent of motion type or scene assumptions, which establishes it as the standard reference for benchmarking other motion estimation algorithms in terms of accuracy.[26] Its main drawback is the intense computational demand, making it unsuitable for real-time applications without dedicated hardware; practicality emerged in the early 1990s via application-specific integrated circuits (ASICs) designed for full-search block matching.[28]

Three-Step Search

The Three-Step Search (TSS) algorithm, introduced by Jain and Jain in 1981, represents one of the earliest fast methods for block matching motion estimation in video coding.[26] It employs a coarse-to-fine strategy with logarithmic step size reduction to approximate the global minimum of the matching criterion efficiently, assuming the error surface is unimodal—exhibiting a single minimum within the search window—and that motions are relatively small.[26] This approach trades potential optimality for significant computational savings, making it suitable for real-time applications in the 1980s when processing power was limited.[29] The algorithm proceeds in three distinct steps, starting from the center of the search window. In the first step, an initial step size $ S $ (typically 4 or 8 pixels) is selected, and the matching cost—such as mean absolute difference (MAD)—is computed at the center and eight neighboring points located at distances $ \pm S $ horizontally and vertically, forming a cross-shaped pattern plus diagonals. The candidate with the minimum cost becomes the new search center. In the second step, the step size is halved to $ S/2 $, and eight new points are evaluated around this updated center, again excluding the previous center to avoid redundancy. The third step repeats this process with a step size of 1 pixel, evaluating another eight points to refine the motion vector. This results in a total of 25 search points (9 in the first step plus 8 each in the subsequent steps) for a typical search range of $ \pm 7 $ pixels, compared to 225 points required by exhaustive search over the same range.[30][31] TSS relies on the center-biased nature of motion in video sequences, where displacements are often small and clustered near zero, aligning with assumptions in early video compression contexts.[26] However, its performance degrades with complex or large motions, as the fixed logarithmic progression can trap the search in local minima if the error surface is multimodal, leading to inaccurate motion vectors.[30] Despite these limitations, TSS established a foundational paradigm for subsequent fast search techniques by demonstrating that structured subsampling could achieve near-exhaustive quality at a fraction of the cost.[29]

Diamond Search

The Diamond Search (DS) algorithm is a pattern-based fast block-matching motion estimation method introduced by Shan Zhu and Kai-Kuang Ma in 2000. Published in the IEEE Transactions on Image Processing, it leverages geometric diamond-shaped search patterns to reduce computational complexity while maintaining high accuracy in locating motion vectors. The approach is particularly suited to video sequences exhibiting center-biased motion vector distributions, where the majority of vectors cluster near zero motion, enabling rapid convergence to the optimal match.[32] The algorithm operates in two phases using distinct diamond patterns. It initiates with the Large Diamond Search Pattern (LDSP), which evaluates nine candidate points: a center point and eight surrounding points forming a diamond with a half-side length of 2 pixels (step sizes of 2 pixels horizontally and vertically, and 1 pixel diagonally). The matching cost—typically the sum of absolute differences or mean absolute error between blocks—is computed at these points within the search window. If the minimum cost point is the center, the process advances to the Small Diamond Search Pattern (SDSP); otherwise, the LDSP center shifts to the minimum cost location, and the pattern is reevaluated iteratively until the minimum occurs at the center. The SDSP then refines the search with five points: the center and four immediate neighbors at 1-pixel steps in cardinal directions. The final minimum cost point in the SDSP yields the motion vector. This step-by-step progression ensures efficient coverage of the search space, often terminating after a few LDSP iterations.[32] A core strength of DS lies in its adaptation to real-world video statistics, where studies of standard test sequences show over 80% of motion vectors fall within a 2-pixel radius of zero, allowing the algorithm to prioritize central regions and avoid exhaustive checks. On average, it requires only 13 to 20 search point evaluations per macroblock, a substantial reduction compared to full-search methods that may need hundreds. The algorithm was integrated into the MPEG-4 verification model and proves effective for standards like H.264/AVC, where small motion vectors predominate in typical encoding scenarios, delivering performance comparable to the new three-step search but with 20% to 25% fewer computations on average.[32] Subsequent variants extend DS for scenarios with larger search ranges and more complex motions. For instance, small-diamond-based modifications partition the extended area into overlapping or non-overlapping small diamonds, propagating outward from the center to capture larger displacements without proportional increases in evaluations, maintaining efficiency in high-motion video applications.[33]

Adaptive Rood Pattern Search

The Adaptive Rood Pattern Search (ARPS) is a fast block-matching motion estimation algorithm proposed by Nie and Ma in 2002.[34] It operates in two sequential stages: an initial search using an adaptive rood pattern to locate a coarse motion vector estimate, followed by a refined local search using a unit-size rood pattern to achieve precision. By leveraging spatial correlations among neighboring blocks, ARPS predicts the starting search position from the motion vector of the immediate left adjacent block, which reduces the number of matching evaluations needed, especially in sequences with correlated motion fields. For edge blocks without a left neighbor, a default prediction of zero motion is assumed. The initial adaptive rood pattern (ARP) forms a cross-shaped search area centered at the predicted position, consisting of four vertex points extending horizontally and vertically. The pattern size $ s $ is adaptively set as $ s = \round\left(\max(|MV_x|, |MV_y|)\right) $, where $ MV_x $ and $ MV_y $ are the horizontal and vertical components of the predicted motion vector; a fixed $ s = 2 $ applies to leftmost blocks. This checks up to five points: the center (predicted position), plus the endpoints at distance $ s $ in the four cardinal directions, omitting duplicates if the predicted point coincides with an endpoint. If the minimum block distortion measure occurs at an edge vertex, the search center shifts there, effectively extending the exploration without fixed expansion. Refinement proceeds with the unit-size rood pattern (URP), a small cross checking five points (center plus one unit in each direction), iterated until the minimum distortion is at the center. This process converges quickly due to the coarse-to-fine strategy, typically requiring only 10-15 point evaluations per block overall. ARPS performs particularly well in video sequences with smooth motion fields, where predicted starting points align closely with true vectors, minimizing iterations and preserving estimation accuracy comparable to more exhaustive methods. An optional zero-motion prejudgment further optimizes static regions by skipping the search if initial distortion falls below a threshold like 1000 in sum of absolute differences.

Hierarchical Block Matching

Hierarchical block matching, also referred to as multi-resolution block matching, is a technique designed to efficiently estimate motion vectors for large displacements in video sequences by leveraging a coarse-to-fine search strategy across multiple image resolutions. The method begins with the construction of a Gaussian pyramid for both the reference and current frames, typically comprising 2 to 3 levels, where each subsequent level is generated by downsampling the previous one by a factor of 2 using Gaussian low-pass filtering to mitigate aliasing effects and preserve essential structural information. At the coarsest pyramid level, block matching is performed using a reduced search window, producing approximate motion vectors that capture global displacements. These coarse vectors are then upsampled and scaled to the next finer resolution level, serving as starting points for localized refinement searches around the predicted positions, with progressively smaller search areas to achieve higher precision. This iterative process propagates upward through the pyramid levels until motion vectors are refined at the original full resolution, enabling the handling of large motion ranges (e.g., displacements exceeding 32 pixels) without the computational burden of exhaustive full-resolution searches. A notable variant is the Optimized Hierarchical Block Matching (OHBM) algorithm, which enhances efficiency by adaptively adjusting the search window sizes at each pyramid level based on the estimated motion smoothness and scale factor, thereby minimizing redundant computations while maintaining accuracy. In OHBM, the search at coarser levels uses broader windows to identify dominant motions, narrowing them in finer levels for detailed adjustments, resulting in a significant reduction in overall complexity to approximately one-fourth that of a standard exhaustive search at full resolution. This optimization assumes spatial continuity in motion vectors, allowing for fewer candidate evaluations per block. OHBM has been applied in image registration tasks adaptable to motion estimation, demonstrating improved speed without substantial loss in vector precision compared to traditional hierarchical approaches. The primary advantages of hierarchical block matching include its ability to robustly capture large-scale motions that single-resolution methods often miss, making it suitable for real-time video processing in standards like MPEG-4, where it supports efficient motion compensation in advanced simple profile implementations. By distributing the search effort across resolutions, it achieves a favorable trade-off between computational cost and estimation quality, particularly beneficial for sequences with significant inter-frame displacements. However, the approach incurs overhead from pyramid construction, including the time for Gaussian filtering and downsampling, which can add 10-20% to the total processing time depending on the number of levels. Additionally, inaccuracies in coarse-level estimates may propagate to finer levels, potentially leading to error accumulation in regions with complex or discontinuous motions, necessitating careful tuning of pyramid depth and refinement parameters to balance performance.[35]

Performance Evaluation

Common Metrics

The mean squared error (MSE) serves as a primary distortion metric for evaluating the accuracy of motion estimation in block-matching algorithms, quantifying the discrepancy between the original frame and the frame reconstructed via motion-compensated prediction. It is computed as the average of the squared differences across all pixels in the frames, given by
MSE=1MN∑i=1M∑j=1N(O(i,j)−P(i,j))2, \text{MSE} = \frac{1}{MN} \sum_{i=1}^{M} \sum_{j=1}^{N} \left( O(i,j) - P(i,j) \right)^2,
where OO denotes the original frame, PP the predicted frame, and M×NM \times N the frame dimensions. Lower MSE values reflect superior prediction fidelity, making it a standard benchmark for assessing overall estimation quality. Closely related, the peak signal-to-noise ratio (PSNR) extends MSE into a more interpretable quality metric, expressing the ratio of the maximum signal power to the noise power introduced by estimation errors on a logarithmic scale. Defined as
PSNR=10log⁡10(MAX2MSE), \text{PSNR} = 10 \log_{10} \left( \frac{\text{MAX}^2}{\text{MSE}} \right),
where MAX is the peak pixel intensity (typically 255 for 8-bit grayscale images), higher PSNR values indicate better reconstruction; values exceeding 30 dB generally signify good estimation quality suitable for video applications.[36] Motion-specific metrics focus on the precision of individual block matches, such as the average sum of absolute differences (SAD) per block, which measures the total pixel-wise absolute deviations between a current block and its best-matching reference block, averaged over all blocks in the frame. This yields a direct indicator of prediction error, with lower averages corresponding to more accurate motion vectors that enhance temporal redundancy exploitation. The SAD is particularly valued for its computational simplicity in both estimation and evaluation phases. Another motion-related measure is the bit-rate savings from motion vector (MV) encoding, which evaluates how effectively the block-matching process reduces the bitrate needed for MV transmission and residual data in compressed video streams. Accurate MVs with low variance enable more efficient entropy coding, often achieving significant bitrate reductions (e.g., up to several percent in rate-distortion curves) compared to naive encoding, thereby balancing quality and compression efficiency. To gauge computational efficiency, metrics like search points per block (SP/B) count the number of candidate block positions tested during the matching process, while processing time is often quantified in cycles per pixel to reflect hardware demands. Lower SP/B values (e.g., below 100 for fast algorithms versus ≈961 for exhaustive search at ±15 pixel range) indicate reduced complexity, facilitating deployment in resource-constrained environments without sacrificing substantial accuracy.

Algorithm Comparisons

Block-matching algorithms for motion estimation in video compression vary significantly in their balance of accuracy and computational efficiency, with performance measured primarily through peak signal-to-noise ratio (PSNR) for quality and search points per block (SP/B) or relative complexity for speed. Exhaustive Search (ES) serves as the benchmark, achieving the highest PSNR by evaluating all possible candidate positions within the search window but at full computational complexity, typically normalized to 100%. In contrast, fast algorithms such as Three-Step Search (TSS), Diamond Search (DS), Adaptive Rood Pattern Search (ARPS), and Hierarchical Block Matching (HBM) reduce complexity by limiting search points, often at the cost of 0.5-2 dB PSNR loss depending on the video sequence.[37][38] Key trade-offs highlight ES's optimality for precision-critical applications, where it yields PSNR values around 35 dB for low-motion sequences like news broadcasts, but its SP/B exceeds 900 at typical search ranges like ±15, making it impractical for real-time encoding. DS and TSS offer moderate speedups, with SP/B of 15-25 and PSNR losses under 1 dB for typical content, while ARPS further optimizes for small motions with SP/B below 10 and negligible quality degradation in stationary scenes. HBM excels in handling large displacements by progressively refining estimates across resolution levels, achieving 10-20% of ES complexity with PSNR close to optimal, though it requires more memory for multi-level processing.[37][39] Performance is highly sequence-dependent; for example, ARPS performs best on head-and-shoulder videos with predominant small or zero motions, maintaining PSNR within 0.1 dB of ES while using 5% complexity, whereas DS may underperform in such cases due to overstepping in large-motion areas. Modern benchmarks on HEVC test sequences like BasketballDrive and ParkScene (as of 2016) confirm these patterns, showing fast methods reduce encoding time by 30-60% with average PSNR drops under 0.1 dB and bit-rate increases around 1% across diverse content.[37][40][38]
AlgorithmAvg. SP/BPSNR Loss vs. ES (dB)Suitability
Exhaustive Search~9610High accuracy, any motion; offline use
Three-Step Search~230.5-1.0Small to medium motion; general-purpose
Diamond Search~180.7-1.5Medium motion; balanced speed/quality
Adaptive Rood Pattern Search~100.1-0.5Small/zero motion (e.g., head-and-shoulder)
Hierarchical Block Matching~20-400.2-1.0Large motion; scalable resolution
Representative values derived from benchmarks on sequences like Foreman and Claire; actual results vary by search range (±15 pixels) and block size (16x16).[37][39] Recent trends emphasize hybrid approaches that adaptively select or combine algorithms based on motion characteristics, such as initial coarse HBM followed by refined DS or ARPS, achieving 60-80% complexity reduction with PSNR losses under 0.5 dB in HEVC-compliant systems. These methods, often integrated with machine learning for pattern prediction, address sequence variability for balanced real-time performance in standards like HEVC and beyond.[41][40]

References

  1. Block Matching Algorithm - an overview | ScienceDirect Topics
  2. https://www.sciencedirect.com/science/article/pii/S235291481730045X
  3. [PDF] Motion Estimation for Video Coding
  4. Review towards the Fast Block Matching Algorithms for Video ...
  5. (PDF) Block matching algorithms for motion estimation - ResearchGate
  6. https://doi.org/10.1016/j.engappai.2012.10.015
  7. [PDF] 525-RM8.pdf - ITU
  8. [PDF] ISO/IEC 13818-2: 1995 (E) Recommendation ITU-T H.262 (1995 E)
  9. https://ieeexplore.ieee.org/document/547305
  10. Request Rejected
  11. Block matching algorithm for motion estimation based on Artificial ...
  12. How Accurate Can Block Matches Be in Stereo Vision?
  13. [PDF] Non-parametric Local Transforms for Computing Visual ...
  14. H.261 : Video codec for audiovisual services at p x 64 kbit/s
  15. H.263 : Video coding for low bit rate communication
  16. https://ieeexplore.ieee.org/document/4068824
  17. H.264 : Advanced video coding for generic audiovisual services
  18. https://ieeexplore.ieee.org/document/6077564
  19. H.265 : High efficiency video coding
  20. https://ieeexplore.ieee.org/document/931116
  21. [PDF] A Taxonomy and Evaluation of Dense Two-Frame Stereo ...
  22. [PDF] intelligent indoor mobile robot navigation using stereo vision - arXiv
  23. [PDF] Optical flow modeling and computation: a survey - Hal-Inria
  24. Block Matching for Object Tracking - SciTech Connect - OSTI.GOV
  25. Global image registration using a symmetric block-matching approach
  26. [PDF] block-matching strategies for rigid registration of multimodal medical ...
  27. Displacement Measurement and Its Application in Interframe Image ...
  28. Survey on Block Matching Motion Estimation Algorithms and ...
  29. A VLSI design for full search block matching motion estimation
  30. https://ieeexplore.ieee.org/document/313138
  31. Coding of Video Sequences Using Three Step Search Algorithm
  32. https://ieeexplore.ieee.org/document/822791
  33. Small-diamond-based search algorithm for fast block motion ...
  34. [PDF] REVIEW AND COMPARATIVE STUDY OF MOTION ESTIMATION ...
  35. https://doi.org/10.1016/j.protcy.2013.12.181
  36. Digital Image Compression Using Approximate Addition - MDPI
  37. [PDF] Evaluation and Comparison of Motion Estimation Algorithms for ...
  38. (PDF) A Comparison of Different Block Matching Algorithms for ...
  39. [PDF] Adaptive rood pattern search for fast block-matching motion estimation
  40. complexity motion estimation algorithm for high efficiency video ...
  41. A survey on video compression fast block matching algorithms
User Avatar
No comments yet.