Block-matching algorithm

<h2 id="motivation">Motivation</h2>
<p>Motion estimation is the process of determining <a href="/facts/Motion_vector/3PmP9Nfh">motion vectors</a> 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.
</p><p>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 <a href="/facts/Motion_compensation/6BM2Ylxn">motion compensation</a>. The combination of motion estimation and motion compensation is a key part of <a href="/facts/Video_compression/gMFuY4FT">video compression</a> as used by <a href="/facts/MPEG/ygmT7JBB">MPEG</a> 1, 2 and 4 as well as many other <a href="/facts/Video_codecs/e5nTCc5X">video codecs</a>.
</p><p>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.
</p>
<h2 id="evaluation-metrics">Evaluation Metrics</h2>
<p>A metric for matching a macroblock with another block is based on a cost function. The most popular in terms of computational expense is:
</p><p><a href="/facts/Mean_absolute_difference/G7HtnNdD">Mean difference</a> or Mean Absolute Difference (MAD) = 
  
    
      
        
          
            1
            
              N
              
                2
              
            
          
        
        
          ∑
          
            i
            =
            0
          
          
            n
            −
            1
          
        
        
          ∑
          
            j
            =
            0
          
          
            n
            −
            1
          
        
        
          |
        
        
          C
          
            i
            j
          
        
        −
        
          R
          
            i
            j
          
        
        
          |
        
      
    
    {\displaystyle {\frac {1}{N^{2}}}\sum _{i=0}^{n-1}\sum _{j=0}^{n-1}|C_{ij}-R_{ij}|}

</p><p><a href="/facts/Mean_Squared_Error/kz3TR7bv">Mean Squared Error</a> (MSE) = 
  
    
      
        
          
            1
            
              N
              
                2
              
            
          
        
        
          ∑
          
            i
            =
            0
          
          
            n
            −
            1
          
        
        
          ∑
          
            j
            =
            0
          
          
            n
            −
            1
          
        
        (
        
          C
          
            i
            j
          
        
        −
        
          R
          
            i
            j
          
        
        
          )
          
            2
          
        
      
    
    {\displaystyle {\frac {1}{N^{2}}}\sum _{i=0}^{n-1}\sum _{j=0}^{n-1}(C_{ij}-R_{ij})^{2}}

</p><p>where N is the size of the macro-block, and 
  
    
      
        
          C
          
            i
            j
          
        
      
    
    {\displaystyle C_{ij}}
  
 and 
  
    
      
        
          R
          
            i
            j
          
        
      
    
    {\displaystyle R_{ij}}
  
 are the pixels being compared in current macroblock and reference macroblock, respectively.
</p><p>The motion compensated image that is created using the motion vectors and macroblocks from the reference frame is characterized by <a href="/facts/Peak_signal-to-noise_ratio/FPlWpNkI">Peak signal-to-noise ratio</a> (PSNR),
</p><p>
  
    
      
        
          PSNR
        
        =
        10
        
          log
          
            10
          
        
        ⁡
        
          
            
              (
              
                peak to peak value of original data
              
              
                )
                
                  2
                
              
            
            MSE
          
        
      
    
    {\displaystyle {\text{PSNR}}=10\log _{10}{\frac {({\text{peak to peak value of original data}})^{2}}{\text{MSE}}}}

</p>
<h2 id="algorithms">Algorithms</h2>

<p>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.
</p>
<h3>Exhaustive Search</h3>
<p>This algorithm calculates the <a href="/facts/Loss_function/xv5ozuhl">cost function</a> 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.
</p>
<h3>Optimized Hierarchical Block Matching (OHBM)</h3>
<p>The optimized hierarchical block matching (OHBM) algorithm speeds up the exhaustive search based on the optimized image pyramids.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p>
<h3>Three Step Search</h3>
<p>It is one of the earliest fast block matching algorithms. It runs as follows:
</p>
<ol><li>Start with search location at center</li>
<li>Set step size S = 4 and search parameter p = 7</li>
<li>Search 8 locations +/- S pixels around location (0,0) and the location (0,0)</li>
<li>Pick among the 9 locations searched, the one with minimum cost function</li>
<li>Set the new search origin to the above picked location</li>
<li>Set the new step size as S = S/2</li>
<li>Repeat the search procedure until S = 1</li></ol>
<p>The resulting location for S=1 is the one with minimum cost function and the macro block at this location is the best match.
</p><p>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.
</p>
<h3>Two Dimensional Logarithmic Search</h3>
<p>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,
</p>
<ol><li>Start with search location at the center</li>
<li>Select an initial step size say, S = 8</li>
<li>Search for 4 locations at a distance of S from center on the X and Y axes</li>
<li>Find the location of point with least cost function</li>
<li>If a point other than center is the best matching point,
<ol><li>Select this point as the new center</li></ol></li>
<li>If the best matching point is at the center, set S = S/2</li>
<li>Repeat steps 2 to 3</li>
<li>If S = 1, all 8 locations around the center at a <a href="/facts/Distance/hbXlaEFk">distance</a> S are searched</li>
<li>Set the motion vector as the point with least cost function</li></ol>
<h3>New Three Step Search</h3>
<p>TSS uses a uniformly allocated checking pattern and is prone to miss small motions. NTSS <a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> 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 <a href="/facts/MPEG/ygmT7JBB">MPEG</a> 1 and H.261.
</p><p>The algorithm runs as follows:
</p>
<ol><li>Start with search location at center</li>
<li>Search 8 locations +/- S pixels with S = 4 and 8 locations +/- S pixels with S = 1 around location (0,0)</li>
<li>Pick among the 16 locations searched, the one with minimum cost function</li>
<li>If the minimum cost function occurs at origin, stop the search and set motion vector to (0,0)</li>
<li>If the minimum cost function occurs at one of the 8 locations at S = 1, set the new search origin to this location
<ol><li>Check adjacent weights for this location, depending on location it may check either 3 or 5 points</li></ol></li>
<li>The one that gives lowest weight is the closest match, set the motion vector to that location</li>
<li>If the lowest weight after the first step was one of the 8 locations at S = 4, the normal TSS procedure follows
<ol><li>Pick among the 9 locations searched, the one with minimum cost function</li>
<li>Set the new search origin to the above picked location</li>
<li>Set the new step size as S = S/2</li>
<li>Repeat the search procedure until S = 1</li></ol></li></ol>
<p>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
</p>
<h3>Simple and Efficient Search</h3>
<p>The idea behind TSS is that the error surface due to motion in every macro block is <a href="/facts/Unimodal/Xo3bhgeE">unimodal</a>. 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 <a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> is the extension of TSS that incorporates this assumption.
</p><p>SES algorithm improves upon TSS algorithm as each search step in SES is divided into two phases:
</p><p>• First Phase :
</p>
     • Divide the area of search in four <a href="/facts/Quadrant_(plane_geometry)/THvuEvBp">quadrants</a>
     • 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

<p>• Second Phase: 
</p>
     • Find the location with lowest weight
     • Set the new search origin as the point found above

<p>• Set the new step size as S = S/2
</p><p>• Repeat the SES search procedure until S=1
</p><p>• 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.
</p>
<h3>Four Step Search</h3>
<p>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 <a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> also employs center <a href="/facts/Bias_(statistics)/Pql981K3">biased</a> searching and has a halfway stop provision.
</p><p>The algorithm runs as follows:
</p>
<ol><li>Start with search location at center</li>
<li>Set step size S = 2, (irrespective of search parameter p)</li>
<li>Search 8 locations +/- S pixels around location (0,0)</li>
<li>Pick among the 9 locations searched, the one with minimum cost function</li>
<li>If the minimum weight is found at center for search window:
<ol><li>Set the new step size as S = S/2 (that is S = 1)</li>
<li>Repeat the search procedure from steps 3 to 4</li>
<li>Select location with the least weight as motion vector</li></ol></li>
<li>If the minimum weight is found at one of the 8 locations other than the center:
<ol><li>Set the new origin to this location</li>
<li>Fix the step size as S = 2</li>
<li>Repeat the search procedure from steps 3 to 4. Depending on location of new origin, search through 5 locations or 3 locations</li>
<li>Select the location with the least weight</li>
<li>If the least weight location is at the center of new window go to step 5, else go to step 6</li></ol></li></ol>
<h3>Diamond Search</h3>
<p>Diamond Search (DS)<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> 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.
</p><p>Two different types of fixed patterns are used for search,
</p>
<ul><li>Large Diamond Search Pattern (LDSP)</li>
<li>Small Diamond Search Pattern (SDSP)</li></ul>
<p>The algorithm runs as follows:
</p>
<ul><li>LDSP:</li></ul>
<ol><li><ol><li>Start with search location at center</li>
<li>Set step size S = 2</li>
<li>Search 8 locations pixels (X,Y) such that (|X|+|Y|=S) around location (0,0) using a diamond search point pattern</li>
<li>Pick among the 9 locations searched, the one with minimum cost function</li>
<li>If the minimum weight is found at center for search window, go to SDSP step</li>
<li>If the minimum weight is found at one of the 8 locations other than the center, set the new origin to this location</li>
<li>Repeat LDSP</li></ol></li></ol>
<ul><li>SDSP:</li></ul>
<ol><li><ol><li>Set the new search origin</li>
<li>Set the new step size as S = S/2 (that is S = 1)</li>
<li>Repeat the search procedure to find location with least weight</li>
<li>Select location with the least weight as motion vector</li></ol></li></ol>
<p>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.
</p>
<h3>Adaptive Rood Pattern Search</h3>
<p>Adaptive rood pattern search (ARPS) <a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> algorithm makes use of the fact that the general motion in a frame is usually <a href="/facts/Coherence_(physics)/NF1Rgdoa">coherent</a>, i.e. if the macro blocks around the current macro block moved in a particular direction then there is a high <a href="/facts/Probability/fgYvMhwb">probability</a> that the current macro block will also have a similar <a href="/facts/Motion_vector/3PmP9Nfh">motion vector</a>. This algorithm uses the motion vector of the macro block to its immediate left to predict its own motion vector.
</p><p>Adaptive rood pattern search runs as follows:
</p>
<ol><li>Start with search location at the center (origin)</li>
<li>Find the predicted motion vector for the block</li>
<li>Set step size S = max (|X|,|Y|), where (X,Y) is the <a href="/facts/Coordinate/Mtd0q4SP">coordinate</a> of predicted motion vector</li>
<li>Search for rood pattern distributed points around the origin at step size S</li>
<li>Set the point with least weight as origin</li>
<li>Search using small diamond search pattern (SDSP) around the new origin</li>
<li>Repeat SDSP search until least weighted point is at the center of SDSP</li></ol>
<p>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.
</p>

<h2 id="external-links">External links</h2>
<p>1. <a href="http://www.mathworks.com/matlabcentral/fileexchange/8761-block-matching-algorithms-for-motion-estimation">http://www.mathworks.com/matlabcentral/fileexchange/8761-block-matching-algorithms-for-motion-estimation</a>
</p><p>2. <a href="https://www.ece.cmu.edu/~ee899/project/deepak_mid.htm">https://www.ece.cmu.edu/~ee899/project/deepak_mid.htm</a>
</p>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Dabov, Kostadin; Foi, Alessandro; Katkovnik, Vladimir; Egiazarian, Karen (16 July 2007). "Image denoising by sparse 3D transform-domain collaborative filtering". IEEE Transactions on Image Processing. 16 (8): 2080–2095. Bibcode:2007ITIP...16.2080D. CiteSeerX 10.1.1.219.5398. doi:10.1109/TIP.2007.901238. PMID 17688213. S2CID 1475121. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Danielyan, Aram; Katkovnik, Vladimir; Egiazarian, Karen (30 June 2011). "BM3D Frames and Variational Image Deblurring". IEEE Transactions on Image Processing. 21 (4): 1715–28. arXiv:1106.6180. Bibcode:2012ITIP...21.1715D. doi:10.1109/TIP.2011.2176954. PMID 22128008. S2CID 11204616. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Je, Changsoo; Park, Hyung-Min (2013). "Optimized hierarchical block matching for fast and accurate image registration". Signal Processing: Image Communication. 28 (7): 779–791. doi:10.1016/j.image.2013.04.002. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Li, Renxiang; Zeng, Bing; Liou, Ming (August 1994). "A New Three-Step Search Algorithm for Block Motion Estimation". IEEE Transactions on Circuits and Systems for Video Technology. 4 (4): 438–442. doi:10.1109/76.313138. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Lu, Jianhua; Liou, Ming (April 1997). "A Simple and Efficient Search Algorithm for Block-Matching Motion Estimation". IEEE Transactions on Circuits and Systems for Video Technology. 7 (2): 429–433. doi:10.1109/76.564122. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>Po, Lai-Man; Ma, Wing-Chung (June 1996). "A Novel Four-Step Search Algorithm for Fast Block Motion Estimation". IEEE Transactions on Circuits and Systems for Video Technology. 6 (3): 313–317. doi:10.1109/76.499840. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
<li id="fn:7"><p>Zhu, Shan; Ma, Kai-Kuang (February 2000). "A New Diamond Search Algorithm for Fast Block-Matching Motion Estimation". IEEE Transactions on Image Processing. 9 (12): 287–290. Bibcode:2000ITIP....9..287Z. doi:10.1109/83.821744. PMID 18255398. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li>
<li id="fn:8"><p>Nie, Yao; Ma, Kai-Kuang (December 2002). "Adaptive Rood Pattern Search for Fast Block-Matching Motion Estimation" (PDF). IEEE Transactions on Image Processing. 11 (12): 1442–1448. Bibcode:2002ITIP...11.1442N. doi:10.1109/TIP.2002.806251. PMID 18249712. <a href="http://www3.ntu.edu.sg/home/ekkma/1_Publications_files/Adaptive%20rood%20pattern%20search%20for%20fast%20block-matching%20motion%20estimation%20%28IEEE%20TIP%20Dec%202002%29.pdf" target="_blank">http://www3.ntu.edu.sg/home/ekkma/1_Publications_files/Adaptive%20rood%20pattern%20search%20for%20fast%20block-matching%20motion%20estimation%20%28IEEE%20TIP%20Dec%202002%29.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li>
</ol>

Block-matching algorithm open-in-new

Block-matching algorithm