Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Block-matching algorithm
open-in-new
<p>A Block Matching Algorithm is a way of locating matching <a href="/facts/Macroblock/L7XPoRNP">macroblocks</a> in a sequence of <a href="/facts/Digital_video/xsn9omqG">digital video</a> frames for the purposes of <a href="/facts/Motion_estimation/FF2TIndo">motion estimation</a>. 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 <a href="/facts/Video_compression/gMFuY4FT">video compression</a> by defining the contents of a macroblock by reference to the contents of a known macroblock which is minimally different. </p> <p>A block matching algorithm involves dividing the current <a href="/facts/Film_frame/27Uqo8WN">frame</a> 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 <a href="/facts/Vector_(mathematics_and_physics)/U8mM7A5F">vector</a> 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. </p><p>The search area for a good macroblock match is decided by the ‘search parameter’, p, where p is the number of <a href="/facts/Pixels/UzwBvXBV">pixels</a> 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. </p><p><a href="/facts/Block-matching_and_3D_filtering/y6znP66f">Block-matching and 3D filtering</a> makes use of this approach to solve various <a href="/facts/Digital_photograph_restoration/Gyt8XCrv">image restoration</a> <a href="/facts/Inverse_problems/Fe01pQ9E">inverse problems</a> such as <a href="/facts/Noise_reduction/9jrDQnAN">noise reduction</a> and <a href="/facts/Deblurring/YFxq5T6h">deblurring</a> in both still images and <a href="/facts/Digital_video/xsn9omqG">digital video</a>. </p>