Block-matching algorithm - Revision history

ColRad85: Disambiguating links to Image restoration (link changed to Digital photograph restoration) using DisamAssist.

2024-09-12T12:05:10Z

Disambiguating links to Image restoration (link changed to Digital photograph restoration) using DisamAssist.

← Previous revision		Revision as of 12:05, 12 September 2024
Line 6:		Line 6:
	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.		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 \|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]].		[[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 ==		== Motivation ==

Jlwoodwa: Reverted 1 edit by Thomas-pegot (talk): Self-promo

2024-08-26T14:23:37Z

Reverted 1 edit by Thomas-pegot (talk): Self-promo

← Previous revision		Revision as of 14:23, 26 August 2024
Line 187:		Line 187:

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

	3. [https://github.com/thomas-pegot/esp32-motion/blob/master/block_matching.c C example] using the Adaptative Root Pattern Search algorithm

	{{DEFAULTSORT:Block-Matching Algorithm}}		{{DEFAULTSORT:Block-Matching Algorithm}}

Thomas-pegot: Adding C code for ARPS algorithm

2024-08-26T14:18:55Z

Adding C code for ARPS algorithm

← Previous revision		Revision as of 14:18, 26 August 2024
Line 187:		Line 187:

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

			3. [https://github.com/thomas-pegot/esp32-motion/blob/master/block_matching.c C example] using the Adaptative Root Pattern Search algorithm

	{{DEFAULTSORT:Block-Matching Algorithm}}		{{DEFAULTSORT:Block-Matching Algorithm}}

59.6.139.249: /* Algorithms */

2024-07-03T05:26:48Z

Algorithms

← Previous revision		Revision as of 05:26, 3 July 2024
Line 37:		Line 37:
	However this is the most computationally extensive block matching algorithm among all. A larger search window requires greater number of computations.		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) ===

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

59.6.139.249: /* Exhaustive Search */

2024-07-03T05:23:23Z

Exhaustive Search

← Previous revision		Revision as of 05:23, 3 July 2024
Line 37:		Line 37:
	However this is the most computationally extensive block matching algorithm among all. A larger search window requires greater number of computations.		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) ===

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

73.217.103.80: /* Algorithms */ Needs further inline citations throughout ~~~~

2024-01-08T00:35:06Z

Algorithms: Needs further inline citations throughout ~~~~

← Previous revision		Revision as of 00:35, 8 January 2024
Line 30:		Line 30:

	== Algorithms ==		== Algorithms ==
			{{More citations needed\|date=January 2024}}
	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.		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.

Ffffrr: Importing Wikidata short description: "System used in computer graphics applications"

2023-09-04T13:23:54Z

Importing Wikidata short description: "System used in computer graphics applications"

← Previous revision		Revision as of 13:23, 4 September 2023
Line 1:		Line 1:
			{{Short description\|System used in computer graphics applications}}
	A '''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.		A '''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]]		[[File:Block-matching algorithm.png\|thumb\|405x405px]]

Headbomb: Alter: journal. | Use this tool. Report bugs. | #UCB_Gadget

2023-09-04T13:20:23Z

Alter: journal. | Use this tool. Report bugs. | #UCB_Gadget

← Previous revision		Revision as of 13:20, 4 September 2023
Line 72:		Line 72:
	=== New Three Step Search ===		=== 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 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.		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 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:		The algorithm runs as follows:
Line 93:		Line 93:
	=== Simple and Efficient Search ===		=== 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 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.		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 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:		SES algorithm improves upon TSS algorithm as each search step in SES is divided into two phases:
Line 118:		Line 118:

	=== Four Step Search ===		=== 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 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.		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 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:		The algorithm runs as follows:
Line 138:		Line 138:

	=== Diamond Search ===		=== 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.~~ 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.		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= 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,		Two different types of fixed patterns are used for search,
Line 163:		Line 163:

	=== Adaptive Rood Pattern Search ===		=== 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\|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 (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 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:		Adaptive rood pattern search runs as follows:

2001:388:608C:6906:DC00:4A13:2698:D470: /* Two Dimensional Logarithmic Search */

2023-05-01T01:45:07Z

Two Dimensional Logarithmic Search

← Previous revision		Revision as of 01:45, 1 May 2023
Line 66:		Line 66:
	## Select this point as the new center		## Select this point as the new center
	# If the best matching point is at the center, set S = S/2		# If the best matching point is at the center, set S = S/2
	## Repeat steps 2 to 3		# Repeat steps 2 to 3
	# If S = 1, all 8 locations around the center at a [[distance]] S are searched		# 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		# Set the motion vector as the point with least cost function

2001:388:608C:6906:DC00:4A13:2698:D470: /* Two Dimensional Logarithmic Search */

2023-05-01T01:44:40Z

Two Dimensional Logarithmic Search

← Previous revision		Revision as of 01:44, 1 May 2023
Line 65:		Line 65:
	# If a point other than center is the best matching point,		# If a point other than center is the best matching point,
	## Select this point as the new center		## 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		# 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		# 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		# Set the motion vector as the point with least cost function