Block-matching algorithm

src: images.slideplayer.com

A Block Matching Algorithm is a way to find macroblock matching in the order of digital video frames for motion estimation purposes. The underlying assumption behind motion estimation is that the pattern corresponding to the object and the background within the video sequence frame moves within the frame to form the corresponding object on the next frame. It can be used to find temporal redundancy in video sequences, improving the effectiveness of inter-frame video compression by defining the contents of macroblocks by referring to the contents of known macroblocks that are at least different.

A block matching algorithm involves splitting the current frame of a video into a macroblock and comparing each macro block with the corresponding block and adjacent neighbors in a nearby video frame (sometimes just the previous one). Vectors are created that model the macroblock movement from one location to another. This movement, calculated for all macro blocks consisting of a frame, is an estimated movement in the frame.

The search area for a good macroblock match is determined 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 greater the value of p, the greater the potential of motion and the possibility of finding a good partner. Full search of all potential blocks but an expensive computing task. Common input is a macroblock size of 16 pixels and search area p = 7 pixels.

Block matching and 3D filtering take advantage of this approach to solve various image restoration restoration problems such as noise reduction and debluring on both still images and digital video.

Video Block-matching algorithm

Motivation

The motion estimate is the process of determining motion vectors that illustrate the transformation from one 2D image to another; usually from adjacent frames in video sequence. Motion vectors can relate to all images (global movement estimates) or specific parts, such as rectangular blocks, random-shaped patches or even per pixel. Motion vectors can be represented by translational models or many other models that can approach the movements of real video cameras, such as rotations and translations in all three dimensions and zoom.

Apply a motion vector to the image to predict the transformation to another image, because the camera is moving or the 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.

Estimated motion-based compression movements help in saving bits by sending images of encoded differences that are inherently less entropy as opposed to sending full-coded frames. But the most expensive operation and extensive computing resources throughout the compression process is movement estimation. Therefore, a fast and computationally fast algorithm for motion estimation is the need for video compression.

Maps Block-matching algorithm

Evaluation Metrics

Metrics for macro block matching with other blocks are based on cost functions. The most popular in terms of computing costs are:

Mean difference atau Mean Absolute Difference (MAD) = ${\ displaystyle {\ frac {1} {N2}} \ jumlah {i = 0} ^ {n-1} \ jumlah _ {j = 0} ^ {n-1} | C {ij} -R_ {ij} |} Â Â$

Mean Squared Error (MSE) = ${\ displaystyle {\ frac {1} {N2}} \ jumlah {i = 0} ^ {n-1} \ jumlah _ {j = 0} ^ {n-1} (C {ij} -R {ij}) 2} Â Â$

di mana N adalah ukuran makro-blok, dan ${\ displaystyle C {ij}} Â$ dan ${\ displaystyle R_ {ij}} Â$ adalah piksel yang dibandingkan di makroblock dan referensi macroblock saat ini, masing-masing.

Motion compensation drawings made using motion vectors and macro blocks of the reference frame are marked by Peak-to-noise ratio, PSNR,

$Â\; ÂÂ\; Â\; Â\; ÂÂ\; Â\; Â\; Â\; Â\; Â{\displaystyle Â\; Â\; Â\; Â\; Â\; Â\; Â\; ÂÂ\; Â\; Â\; Â\; Â\; Â\; Â\; Â\; Â\; Â\text{PSNR}Â\; Â\; Â\; Â\; Â\; Â\; Â\; ÂÂ\; Â\; Â\; Â\; Â\; Â\; Â=Â\; Â\; Â\; Â\; Â\; Â\; Â\; Â10Â\; Â\; Â\; Â\; Â\; Â{}_{}}$ log                       10                                                                  (                               puncak ke nilai puncak dari data asli                                          )                                  2                                                      MSE                              {\ displaystyle {\ text {PSNR}} = 10 \ log _10 {\ frac {({\ text {peak to peak value dari data asli }}) 2}} {\ text {MSE}}}}  Â

src: i.ytimg.com

Algorithm

Matching algorithm blocks have been studied since the mid-1980s. Many algorithms have been developed, but only some of the most basic or commonly used ones are described below.

Full Search

This algorithm calculates the cost function at each possible location in the search window. This leads to the best possible matching of macro blocks in the reference frame with blocks in other frames. Compensated motion picture results have the highest peak-to-peak signal-to-noise ratio compared to other block matching algorithms. However this is the most computable block matching algorithm among all. The larger search window requires more calculations.

Optimized hierarchical block matching (OHBM)

Optimized hierarchical block matching (OHBM) accelerates complete search based on optimized image pyramid.

Three Step Search

This is one of the fast block matching algorithms. It goes as follows:

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

The resulting location for S = 1 is one with minimum cost function and macro block in this location is the most suitable.

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

Two-dimensional Logarithmic Search

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

1. Start with the search location in the center
2. Select the initial step size say, S = 8
3. Find 4 locations at distance S from center on X and Y axis
4. Find the location of the point with the lowest cost function
5. If a point other than a center is the best matching point,
   1. Select this point as the new center
   2. Repeat steps 2 to 3
6. If the best matching point is in the middle, set S = S/2
7. If S = 1, all 8 locations around the center at S distance are searched
8. Organize motion vectors as points with lowest cost functions

Three Steps New Search

TSS uses a uniformly allocated checking pattern and is vulnerable to skipping small movements. NTSS is an improvement over TSS as it provides a central search scheme of bias and has a provision for halfway stop to reduce computational costs. This is one of the first widely accepted fast algorithms and is often used to apply previous standards such as MPEG 1 and H.261.

The algorithm goes as follows:

1. Start with center search location
2. Find 8 locations/- S pixels with S = 4 and 8 locations/- S pixels with S = 1 around the location (0,0)
3. Choose among 16 searched locations, one with minimum cost function
4. If the minimum cost function occurs at the origin, stop the search and set the motion vector to (0,0)
5. If the minimum cost function occurs in any of the 8 locations in S = 1, set a new search origin to this location
   1. Check the adjacent weights for this location, depending on the location, can check 3 or 5 points
6. Which gives the lowest weight is the most suitable, set the motion vector to that location
7. If the lowest weight after the first step is one of 8 locations at S = 4, a normal TSS procedure will follow
   1. Choose among the 9 searched locations, one with the minimum cost function
   2. Set new search origin to the selected location above
   3. Set the size of the new step as S = S/2
   4. Repeat the search procedure until S = 1

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

Simple & Efficient Search

The idea behind TSS is that the error surface due to motion in each macro block is unimodal. The unimodal surface is a bowl-shaped surface so that the weight generated by the cost function increases monotonically from the global minimum. However unimodal surfaces can not have two minimums in opposite directions and hence 8 fixed pattern search points from TSS can be further modified to include these and store calculations. SES is an extension of TSS that combines this assumption.

The SES algorithm improves on the TSS algorithm because each search step in the SES is divided into two phases:

o First Phase:

 o Split search area in four quadrants  Â Â Â Â Â o Start search with three locations, one in the middle (A) and other (B and C),  Â Â Â Â Â S = 4 locations from A in the orthogonal direction  Â Â Â Â o Find points in the search quadrant for the second phase using weight distribution for A, B, C:  If (MAD (A) & gt; = MAD (B) and MAD (A) & gt; = MAD (C)), select the point in the second quadrant of the second phase IV  If (MAD (A) & gt; = MAD (B) and MAD (A) & lt; = MAD (C)), select the point in the second quadrant of phase I  If (MAD (A) & lt; MAD (B) and MAD (A) & lt; MAD (C)), select the point in the second phase quadrant II  If (MAD (A) & lt; MAD (B) and MAD (A) & gt; = MAD (C)), select a point in the second phase quadrant III  

o Phase Two:

 o Find the location with the lowest weight  Â Â Â Â o Set the origin of the new search as the point found above  

o Arrange the new measure size as S = S/2

o Repeat SES search procedure until S = 1

o Choose the location with the lowest weight as the motion vector

SES is computationally very efficient compared to TSS. However the peak signal-to-noise ratio achieved is poor compared to TSS because the error surface is not completely unimodal in reality.

Four Step Search

Four Step Search is an improvement over TSS in terms of lower computational costs and better peak-to-peak signal-to-noise ratios. Similar to NTSS, FSS also uses a bias search center and has a halfway stop provision.

The algorithm goes as follows:

1. Start with center search location
2. Set step size 'S' = 2, (apart from search parameter 'p')
3. Find 8 locations/- S pixels around the location (0,0) as shown in the image
4. Choose among the 9 searched locations, one with the minimum cost function
5. If minimum weight is found in the middle for the search window:
   1. Set new search origin as shown in figure 7 (d)
   2. Set the size of the new step as S = S/2 = 1
   3. Repeat the search procedure from steps 3 to 4
   4. Choose the location with the smallest weight as the motion vector
6. If minimum weight is found in any of the 8 locations other than the center:
   1. Set new origin to this location
   2. Fix step size as S = 2
   3. Repeat the search procedure from steps 3 to 4. Depending on the location of the new origin, search through 5 locations or 3 locations
   4. Choose the location with the smallest weight
   5. If the location of the smallest weights is at the center of the new window, go to step 5, the other go to step 6

Diamond Search

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

Two different types of fixed patterns are used for search,

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

The algorithm goes as follows:

• LDSP:

1. 1. Start with center search location
   2. Set step size 'S' = 2
   3. Find 8 location pixels (X, Y) so that (| X | | Y | = S) around the location (0.0) using the diamond search point pattern
   4. Choose among the 9 searched locations, one with the minimum cost function
   5. If the minimum weight is found in the middle for the search window, go to the SDSP step
   6. If minimum weight is found in any of 8 locations other than the center, set new origin to this location
   7. Repeat LDSP

• SDSP:

1. 1. Set new search origin
   2. Set the size of the new step as S = S/2 = 1
   3. Repeat the search procedure to find the location with the least weight
   4. Choose the location with the smallest weight as the motion vector

The algorithm finds global minimums very accurate because the search pattern is neither too big nor too small. The Diamond Search algorithm has an approaching signal-to-noise ratio from Exhaustive Search with much less computational cost.

Adaptive Rood Pattern Search

The Adaptive Rood Pattern Search (ARPS) algorithm makes use of the fact that the general movement in the frame is usually coherent, ie if the macro block around the current macro block moves in a certain direction then there is a high probability that the current macro block will also have the same motion vector. The algorithm uses a motion vector from the macro block to the left directly to predict its own motion vector.

Adaptive rood pattern search is executed as follows:

1. Start with the search location in the center (origin)
2. Find the predicted motion vector for block
3. Set step size S = max (| X |, | Y |), where (X, Y) is the predicted motion vector coordinate
4. Look for pattern spots scattered around the origin at step size S
5. Specify dots with the smallest weights as origin
6. Search uses a small diamond search pattern (SDSP) around a new origin
7. Repeat SDSP search until the weighted point is at least in the center of the SDSP

Searching for rood patterns directly puts a search in an area where there is a high probability of finding a good matching block. The main advantage of ARPS over DS is that if the predicted motion vector is (0, 0), it does not waste computation time doing LDSP, but starts using SDSP immediately. Furthermore, if the predicted motion vector is far from the center, then again ARPS saves the calculation by directly jumping around it and using SDSP, while DS takes time to do LDSP.

src: slideplayer.com

References

src: i.ytimg.com

External links

1. http://www.mathworks.com/matlabcentral/fileexchange/8761-block-matching-algorithms-for-motion-estimation

2. https://www.ece.cmu.edu/~ee899/project/deepak_mid.htm

Source of the article : Wikipedia