Block-matching algorithm
≈ 9 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
A Block Matching Algorithm is a way of locating matching macroblocks 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 involves dividing the current 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 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.…
A Block Matching Algorithm is a way of locating matching macroblocks 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 involves dividing the current 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 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 image restoration inverse problems such as noise reduction and deblurring in both still images and digital video. Mean difference or Mean Absolute Difference (MAD) = \frac{1}{N^2}\sum_{i=0}^{n-1}\sum_{j=0}^{n-1} |C_{ij}-R_{ij}| Mean Squared Error (MSE) = \frac{1}{N^2}\sum_{i=0}^{n-1}\sum_{j=0}^{n-1} (C_{ij}-R_{ij})^2 where N is the size of the macro-block, and C_{ij} and R_{ij} are the pixels being compared in current macroblock and reference macroblock, respectively. The motion compensated image that is created using the motion vectors and macroblocks from the reference frame is characterized by Peak signal-to-noise ratio (PSNR), \text{PSNR} = 10 \log_{10}\frac {(\text{peak to peak value of original data})^2}{\text{MSE}} Set step size S = 4 and search parameter 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 Set the new search origin to the above picked location Set the new step size as S = S/2 Repeat the search procedure until S = 1 The resulting location for S=1 is the one with minimum cost function and the macro block at this location is the best match. There is a reduction in computation by a factor of 9 in this algorithm. For p=7, while ES evaluates cost for 225 macro-blocks, TSS evaluates only for 25 macro blocks. Select an initial step size say, S = 8 Search for 4 locations at a distance of S from center on the X and Y axes Find the location of point with least cost function If a point other than center is the best matching point, Select this point as the new center 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 Search 8 locations +/- S pixels with S = 4 and 8 locations +/- S pixels with S = 1 around location (0,0) Pick among the 16 locations searched, the one with minimum cost function If the minimum cost function occurs at origin, stop the search and set motion vector to (0,0) If the minimum cost function occurs at one of the 8 locations at S = 1, set the new search origin to this location Check adjacent weights for this location, depending on location it may check either 3 or 5 points The one that gives lowest weight is the closest match, set the motion vector to that location If the lowest weight after the first step was one of the 8 locations at S = 4, the normal TSS procedure follows Pick among the 9 locations searched, the one with minimum cost function Set the new search origin to the above picked location Set the new step size as S = S/2 Repeat the search procedure until S = 1 Thus this algorithm checks 17 points for each macro-block and the worst-case scenario involves checking 33 locations, which is still much faster than TSS • Start search with three locations, one at center (A) and others (B and C), 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 • If (MAD(A)>=MAD(B) and MAD(A) =MAD(C)), select points in second phase quadrant III • Second Phase: • Find the location with lowest weight • Set the new search origin as the point found above • Set the new step size as S = S/2 • Repeat the SES search procedure until S=1 • 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. Set step size S = 2, (irrespective of search parameter p) Search 8 locations +/- S pixels around location (0,0) 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 step size as S = S/2 (that is S = 1) Repeat the search procedure from steps 3 to 4 Select location with the least weight as motion vector If the minimum weight is found at one of the 8 locations other than the center: Set the new origin to this location Fix the step size as S = 2 Repeat the search procedure from steps 3 to 4. Depending on location of new origin, search through 5 locations or 3 locations Select the location with the least weight If the least weight location is at the center of new window go to step 5, else go to step 6 Set step size 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 If the minimum weight is found at center for search window, go to SDSP step If the minimum weight is found at one of the 8 locations other than the center, set the new origin to this location Repeat LDSP 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 This algorithm finds the global minimum very accurately as the search pattern is neither too big nor too small. Diamond Search algorithm has a peak signal-to-noise ratio close to that of Exhaustive Search with significantly less computational expense. Set step size S = max (|X|,|Y|), where (X,Y) is the coordinate of predicted motion vector Search for rood pattern distributed points around the origin at step size S Set the point with least weight as origin Search using small diamond search pattern (SDSP) around the new origin Repeat SDSP search until least weighted point is at the center of SDSP Rood pattern search directly puts the search in an area where there is a high probability of finding a good matching block. The main advantage of ARPS over DS is if the predicted motion vector is (0, 0), it does not waste computational time in doing LDSP, but it directly starts using SDSP. Furthermore, if the predicted motion vector is far away from the center, then again ARPS saves on computations by directly jumping to that vicinity and using SDSP, whereas DS takes its time doing LDSP.
References
Text derived from https://en.wikipedia.org/w/index.php?oldid=1373726807 under CC BY-SA 4.0; modifications have been made.