Block-matching algorithm: Difference between revisions

Revision as of 01:45, 1 May 2023

Revision as of 13:20, 4 September 2023

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.Transactions on Circuits and Systems for 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.Transactions on Circuits and Systems for 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 118:

=== 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 and Systems for 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 138:

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

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