Block-matching algorithm: Difference between revisions

Revision as of 06:03, 2 December 2016

Latest revision as of 12:05, 12 September 2024

(44 intermediate revisions by 31 users not shown)

Line 1:

{{Short description|System used in computer graphics applications}}

aA '''Block Matching Algorithm''' is a way of locating matching [[macroblock]]s 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.

[[File:Block-matching algorithm.png|thumb|405x405px]]

A block matching algorithm involves dividing the current [[Film frame|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 (mathematics and physics)|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 [[Digital photograph restoration|image restoration]] [[inverse problems]] such as [[noise reduction]]<ref>{{cite journal |last1= Dabov |first1= Kostadin |last2= Foi |first2= Alessandro |first3= Vladimir |last3= Katkovnik |first4= Karen |last4= Egiazarian |date= 16 July 2007 |title= Image denoising by sparse 3D transform-___domain collaborative filtering |journal= IEEE Transactions on Image Processing |volume=16 |issue= 8 |pages= 2080–2095 |doi= 10.1109/TIP.2007.901238 |pmid= 17688213 |bibcode= 2007ITIP...16.2080D |citeseerx= 10.1.1.219.5398 |s2cid= 1475121 }}</ref> and [[deblurring]]<ref>{{Cite journal|last1= Danielyan|first1= Aram|last2= Katkovnik|first2= Vladimir|last3= Egiazarian|first3= Karen|arxiv=1106.6180 |title= BM3D Frames and Variational Image Deblurring |journal= IEEE Transactions on Image Processing|volume= 21|issue= 4|pages= 1715–28|date=30 June 2011 |doi= 10.1109/TIP.2011.2176954|pmid= 22128008|bibcode= 2012ITIP...21.1715D|s2cid= 11204616}}</ref> in both still images and [[digital video]].

== Motivation ==

Line 11 ⟶ 14:

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 ==

Line 27 ⟶ 30:

== Algorithms ==

{{More citations needed|date=January 2024}}

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

=== Exhaustive Search ===

Line 33 ⟶ 37:

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) ===

==== Optimized hierarchical block matching (OHBM)<ref name="Je_spic13_ohbm">C. Je and H.-M. Park. [http://dx.doi.org/10.1016/j.image.2013.04.002 Optimized Hierarchical Block Matching for Fast and Accurate Image Registration]. Signal Processing: Image Communication, Volume 28, Issue 7, pp. 779-791, August, 2013.</ref> ====

The optimized hierarchical block matching (OHBM) algorithm speeds up the exhaustive search based on the optimized image pyramids.<ref name="Je_spic13_ohbm">{{Cite journal |doi = 10.1016/j.image.2013.04.002|title = Optimized hierarchical block matching for fast and accurate image registration|journal = Signal Processing: Image Communication|volume = 28|issue = 7|pages = 779–791|year = 2013|last1 = Je|first1 = Changsoo|last2 = Park|first2 = Hyung-Min}}</ref>

=== Three Step Search ===

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

# Start with search ___location at center

# Set step size ‘S’S = 4 and search parameter ‘p’p = 7

# Search 8 locations +/- S pixels around ___location (0,0) and the ___location (0,0)

# Pick among the 9 locations searched, the one with minimum cost function

Line 63 ⟶ 67:

# If a point other than center is the best matching point,

## Select this point as the new center

## Repeat steps 2 to 3

# If the best matching point is at the center, set S = S/2

## Repeat steps 2 to 3

# If S = 1, all 8 locations around the center at a [[distance]] S are searched

# Set the motion vector as the point with least cost function

Line 70 ⟶ 74:

=== New Three Step Search ===

TSS uses a uniformly allocated checking pattern and is prone to miss small motions. NTSS <ref name=tss>{{cite journal|last1=Li|first1=Renxiang|last2=Zeng|first2=Bing|last3=Liou|first3=Ming|title=A New Three-Step Search Algorithm for Block Motion Estimation|journal= IEEE Trans.Transactions on Circuits Andand Systems Forfor Video Technology|date=August 1994|volume=4|issue=4|pages=438–442|doi=10.1109/76.313138}}</ref> is an improvement over TSS as it provides a center biased search scheme and has provisions to stop half wayhalfway 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:

Line 91 ⟶ 95:

=== Simple and Efficient Search ===

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 <ref>{{cite journal|last1=Lu|first1=Jianhua|last2=Liou|first2=Ming|title=A Simple and Efficient Search Algorithm for Block-Matching Motion Estimation|journal= IEEE Trans.Transactions on Circuits Andand Systems Forfor Video Technology|date=April 1997|volume=7|issue=2|pages=429–433|doi=10.1109/76.564122}}</ref> 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:

Line 97 ⟶ 101:

• First Phase :

• Divide the area of search in four [[quadrant (plane geometry)|quadrant]]s

• Start search with three locations, one at center (A) and others (B and C), S=4 locations away from A in orthogonal directions

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

Line 114 ⟶ 117:

• 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.

=== Four Step Search ===

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 <ref>{{cite journal|last1=Po|first1=Lai-Man|last2=Ma|first2=Wing-Chung|title=A Novel Four-Step Search Algorithm for Fast Block Motion Estimation|journal= IEEE Trans.Transactions on Circuits Andand Systems Forfor Video Technology|date=June 1996|volume=6|issue=3|pages=313–317|doi=10.1109/76.499840}}</ref> also employs center [[bias (statistics)|bias]]ed searching and has a halfway stop provision.

The algorithm runs as follows:

# Start with search ___location at center

# Set step size ‘S’S = 2, (irrespective of search parameter ‘p’p)

# Search 8 locations +/- S pixels around ___location (0,0) as shown in figure

# Pick among the 9 locations searched, the one with minimum cost function

# If the minimum weight is found at center for search window:

## Set the new searchstep originsize as shownS in= figureS/2 7(dthat is S = 1)

## Set the new step size as S = S/2 = 1

## Repeat the search procedure from steps 3 to 4

## Select ___location with the least weight as motion vector

Line 139 ⟶ 140:

=== Diamond Search ===

Diamond Search (DS)<ref>{{cite journal|last1=Zhu|first1=Shan|last2=Ma|first2=Kai-Kuang|title=A New Diamond Search Algorithm for Fast Block-Matching Motion Estimation|journal=EEE Trans.IEEE Transactions on Image Processing|date=February 2000|volume=9|issue=12|pages=287–290|doi=10.1109/83.821744|pmid=18255398|bibcode=2000ITIP....9..287Z}}</ref> 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,

Line 149 ⟶ 150:

* LDSP:

## Start with search ___location at center

## Set step size ‘S’S = 2

## Search 8 locations pixels (X,Y) such that (|X|+|Y|=S) around ___location (0,0) using a diamond search point pattern

## Pick among the 9 locations searched, the one with minimum cost function

Line 157 ⟶ 158:

* SDSP:

## Set the new search origin

## Set the new step size as S = S/2 (that is S = 1)

## Repeat the search procedure to find ___location with least weight

## Select ___location with the least weight as motion vector

Line 164 ⟶ 165:

=== Adaptive Rood Pattern Search ===

Adaptive rood pattern search (ARPS) <ref>{{cite journal|last1=Nie|first1=Yao|last2=Ma|first2=Kai-Kuang|title=Adaptive Rood Pattern Search for Fast Block-Matching Motion Estimation|journal= IEEE Trans.Transactions on Image Processing|date=December 2002|volume=11|issue=12|pages=1442–1448|doi=10.1109/TIP.2002.806251|pmid=18249712|bibcode=2002ITIP...11.1442N|url=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}}</ref> algorithm makes use of the fact that the general motion in a frame is usually [[coherence (physics)|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: