Block-matching algorithm: Difference between revisions

Revision as of 14:01, 4 February 2019

Revision as of 14:51, 9 February 2019

Line 5:

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]]<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 |bibcode= 2007ITIP...16.2080D |citeseerx= 10.1.1.219.5398 }}</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|date=30 June 2011 |doi= 10.1109/TIP.2011.2176954|pmid= 22128008|bibcode= 2012ITIP...21.1715D}}</ref> in both still images and [[digital video]].

== Motivation ==

Line 35:

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)<ref name="Je_spic13_ohbm">C.{{Cite Jejournal and|doi H.-M.= Park. [https://dx.doi.org/10.1016/j.image.2013.04.002|title = Optimized Hierarchicalhierarchical Blockblock Matchingmatching for Fastfast and Accurateaccurate Imageimage Registration].registration|journal = Signal Processing: Image Communication,|volume Volume= 28,|issue Issue= 7,|pages pp.= 779-791,779–791|year August,= 2013.|last1 = Je|first1 = Changsoo|last2 = Park|first2 = Hyung-Min}}</ref> ====

The optimized hierarchical block matching (OHBM) algorithm speeds up the exhaustive search based on the optimized image pyramids.<ref name="Je_spic13_ohbm"/>

Line 72:

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

Line 93:

=== 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. 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 120:

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

Line 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. Image Processing|date=December 2002|volume=11|issue=12|pages=1442–1448|doi=10.1109/TIP.2002.806251|pmid=18249712}}</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: