Source: http://www.google.com/patents/US20060171464?dq=6,073,142
Timestamp: 2014-07-23 10:09:16
Document Index: 728425362

Matched Legal Cases: ['art 1', 'art 2', 'art 1', 'art 2', 'art 1', 'art 1', 'art 2', 'art 1', 'art 2', 'art 1']

Patent US20060171464 - Method and apparatus for motion estimation - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign in<nobr>Advanced Patent Search</nobr>PatentsA method and apparatus for motion estimation in which the amount of computation can be reduced are provided. The method for motion estimation includes storing an interblock match difference calculated for a previous matching block to be motion estimated, calculating an interblock match difference for...http://www.google.com/patents/US20060171464?utm_source=gb-gplus-sharePatent US20060171464 - Method and apparatus for motion estimationAdvanced Patent SearchPublication numberUS20060171464 A1Publication typeApplicationApplication numberUS 11/338,745Publication dateAug 3, 2006Filing dateJan 25, 2006Priority dateFeb 3, 2005Also published asCN1816154A, CN100563343C, US7889795Publication number11338745, 338745, US 2006/0171464 A1, US 2006/171464 A1, US 20060171464 A1, US 20060171464A1, US 2006171464 A1, US 2006171464A1, US-A1-20060171464, US-A1-2006171464, US2006/0171464A1, US2006/171464A1, US20060171464 A1, US20060171464A1, US2006171464 A1, US2006171464A1InventorsTae-Hyeun HaOriginal AssigneeSamsung Electronics Co., Ltd.Export CitationBiBTeX, EndNote, RefManReferenced by (4), Classifications (11), Legal Events (1) External Links: USPTO, USPTO Assignment, EspacenetMethod and apparatus for motion estimationUS 20060171464 A1Abstract A method and apparatus for motion estimation in which the amount of computation can be reduced are provided. The method for motion estimation includes storing an interblock match difference calculated for a previous matching block to be motion estimated, calculating an interblock match difference for a current matching block to be motion estimated using the stored interblock match difference, and performing motion estimation on the current matching block using the interblock match difference calculated for the current matching block. Images(17) Claims(18)
DETAILED DESCRIPTION OF THE INVENTION FIG. 3 illustrates a matching block for calculation of a sum of absolute differences (SAD) according to the present invention. Referring to FIG. 3, a block composed of sub-blocks a, b, c, and d, which is marked with dotted lines, indicates a matching block (i.e., a previous matching block) that has been previously calculated and a block composed of sub-blocks b, d, e, and f indicates a matching block (i.e., a current matching block) that is to be currently calculated. Here, since the sub-blocks b and d of the previous matching block and the current matching block overlap, an SAD for the current matching block composed of b, d, e, and f can be obtained by calculating only an SAD for the sub-blocks e and f using an already calculated SAD for the sub-blocks b and d. An SAD is a difference between a matching block and a search block and, more specifically, a sum of absolute differences between pixels of the matching block and pixels of the search block. First, a principle of reducing the amount of computation using equations will now be described. An SAD for the previous matching block is given by SAD ( k , l ) ⁡ ( x , y ) = ∑ i = 1 32 ⁢ ∑ j = 1 32 ⁢  f n ⁡ ( k + i + x , l + j + y ) - f n - 1 ⁡ ( k + i , l + j )  where (k, l) represents coordinates of a pixel at the top-left corner of a previous matching block, i and j represent an x-axis index and y-axis index of points included in the previous matching block, respectively, fn represents a current frame, and fn-1 represents a previous frame that is adjacent to the current frame. To sum up, fn (k+i+x, l+j+y) represents pixel values included in a matching block when coordinates of a pixel at the top-left corner of the matching block are (k, l) and fn-1 (k+i, l+j) represents pixel values included in a search block for the matching block. An SAD for the current matching block is expressed as SAD ( k + 16 , l ) ⁡ ( x , y ) = ∑ i = 1 32 ⁢ ∑ j = 1 32 ⁢  f n ⁡ ( k + 16 + i + x , l + j + y ) - f n - 1 ⁡ ( k + i , l + j )  A result of subtracting the SAD for the previous matching block from the SAD for the current matching block can be expressed as SAD ( k + 16 , l ) ⁡ ( x , y ) - SAD ( k , l ) ⁡ ( x , y ) = ∑ i = 1 32 ⁢ ∑ j = 1 32 ⁢ S ( i , j ) ⁡ ( k + 16 , l ) - ∑ i = 1 32 ⁢ ∑ j = 1 32 ⁢ S ( i , j ) ⁡ ( k , l ) if , S ( i , j ) ⁡ ( k , l ) ≡  f n ⁡ ( k + i + x , l + j + y ) - f n - 1 ⁡ ( k + i , l + j )  S ( i , j ) ⁡ ( k + 16 , l ) =  f n ⁡ ( k + 16 + i + x , l + j + y ) - f n - 1 ⁡ ( k + 16 + i , l + j )  = S ( i + 16 , j ) ⁡ ( k , l ) Thus, the result can be arranged and developed as follows. SAD ( k + 16 , l ) ⁡ ( x , y ) - SAD ( k , l ) ⁡ ( x , y ) = ∑ i = 1 32 ⁢ ∑ j = 1 32 ⁢ S ( i , j ) ⁡ ( k + 16 , l ) - ∑ i = 1 32 ⁢ ∑ j = 1 32 ⁢ S ( i , j ) ⁡ ( k , l ) ⁢ = ∑ i = 1 32 ⁢ ∑ j = 1 32 ⁢ S ( i + 16 , j ) ⁡ ( k , l ) - ∑ i = 1 32 ⁢ ∑ j = 1 32 ⁢ S ( i , j ) ⁡ ( k , l ) = ∑ i = 33 48 ⁢ ∑ j = 1 32 ⁢ S ( i , j ) ⁡ ( k , l ) - ∑ i = 1 16 ⁢ ∑ j = 1 32 ⁢ S ( i , j ) ⁡ ( k , l ) ⁢ ∵ ∑ m = 33 48 ⁢ ∑ j = 1 32 ⁢ S ( m , j ) ⁡ ( k , l ) = ∑ m = 17 32 ⁢ ∑ j = 1 32 ⁢ S ( m , j ) ⁡ ( k , l ) + ∑ m = 33 48 ⁢ ∑ j = 1 32 ⁢ S ( m , j ) ⁡ ( k , l ) ∑ i = 1 32 ⁢ ∑ j = 1 32 ⁢ S ( i , j ) ⁡ ( k , l ) = ∑ i = 1 16 ⁢ ∑ j = 1 32 ⁢ S ( i , j ) ⁡ ( k , l ) + ∑ i = 17 32 ⁢ ∑ j = 1 32 ⁢ S ( i , j ) ⁡ ( k , l ) SAD ( k + 16 , l ) ⁡ ( x , y ) = SAD ( k , l ) ⁡ ( x , y ) + ∑ i = 33 48 ⁢ ∑ j = 1 32 ⁢ S ( i , j ) ⁡ ( k , l ) - ∑ i = 1 16 ⁢ ∑ j = 1 32 ⁢ S ( i , j ) ⁡ ( k , l ) Thus, by re-arranging the above equation, the SAD for the current matching block can be divided into a part 1 and a part 2 as follows. ∴ SAD ( k + 16 , l ) ⁡ ( x , y ) = ∑ i = 17 32 ⁢ ∑ j = 1 32 ⁢ S ( i , j ) ⁡ ( k , l ) _ PART ⁢ ⁢ 1 - ∑ i = 33 48 ⁢ ∑ j = 1 32 ⁢ S ( i , j ) ⁡ ( k , l ) _ PART ⁢ ⁢ 2 As can be seen from the above equation, the part 1 is a left half of the SAD for the current matching block and the part 2 is a right half of the SAD for the current matching block. The part 1 which is the left half of the SAD for the current matching block, corresponds to a right half of the SAD for the previous matching block. Thus, in the present invention, a result of calculation of the right half of the SAD for the previous matching block is stored and the stored result is used for calculation of the SAD for the current matching block. Overlapped calculations will now be described with examples. FIG. 4A illustrates a previous matching block for motion estimation according to the present invention. Referring to FIG. 4A, a block to be matched includes a previous motion compensation block and overlapping portions adjacent to the previous motion compensation block and is formed by four points S1,1, S1,32, S32,1, and S32,32. FIG. 4B illustrates a current matching block for motion estimation according to the present invention. Referring to FIG. 4B, a block to be matched includes a current motion compensation block and overlapping portions adjacent to the current motion compensation block and is formed by four points S1,17, S1,48, S32,17, and S32,48. FIGS. 5A through 8B illustrate positions of search blocks in a search area for a previous matching block and SADs according to the positions. FIG. 5A illustrates a search area for a previous matching block for calculation of an SAD and a position of a first search block in the search area. Referring to FIG. 5A, a search area for a previous matching block is formed by R1,1, R1,64, R64,1, and R64,64 and a first search block that is first searched in the search area is formed by R1,1, R1,32, R32,1, and R32,32. FIG. 5B illustrates an equation for calculation of the SAD based on the first search block and the previous matching block shown in FIG. 5A. SAD ⁡ ( previous ) 1 , ⁢ 1 = ⁢  S 1 , 1 - R 1 , 1  +  S 1 , 2 - R 1 , 2  + � +  S 1 , 16 - R 1 , 16  ⁢ ⁢ +  S 1 , 17 - R 1 , 17  + � + ⁢  S 1 , 32 - R 1 , 32  +  S 2 , 1 - R 2 , 1  +  S 2 , 2 - R 2 , 2  + ⁢ � +  S 2 , 16 - R 2 , 16  +  S 2 , 17 - R 2 , 17  + � + ⁢  S 2 , 32 - R 2 , 32  + � +  S 32 , 1 - R 32 , 1  + ⁢  S 32 , 2 - R 32 , 2  + � +  S 32 , 16 - R 32 , 16  + ⁢  S 32 , 17 - R 32 , 17  + � +  S 32 , 32 - R 32 , 32  FIG. 6A illustrates the search area for the previous matching block for calculation of an SAD and a position of a search block that is moved from the first search block by 1 along the x-axis in the search area. Referring to FIG. 6A, the search block that is moved from the position of the first search block by 1 along the x-axis is formed by R1,2, R1,33, R32,2, and R32,33. FIG. 6B illustrates an equation for calculation of an SAD based on the search block shown in FIG. 6A and the previous matching block. SAD ⁡ ( previous ) 1 , ⁢ 2 = ⁢  S 1 , 1 - R 1 , 2  +  S 1 , 2 - R 1 , 3  + � +  S 1 , 16 - R 1 , 17  ⁢ ⁢ +  S 1 , 17 - R 1 , 18  + � + ⁢  S 1 , 32 - R 1 , 33  +  S 2 , 1 - R 2 , 2  +  S 2 , 2 - R 2 , 3  + ⁢ � +  S 2 , 16 - R 2 , 17  +  S 2 , 17 - R 2 , 18  + � + ⁢  S 2 , 32 - R 2 , 33  + � +  S 32 , 1 - R 32 , 2  + ⁢  S 32 , 2 - R 32 , 3  + � +  S 32 , 16 - R 32 , 17  + ⁢  S 32 , 17 - R 32 , 18  + � ⁢  S 32 , 32 - R 32 , 33  FIG. 7A illustrates the search area for the previous matching block for calculation of an SAD and a position of a search block that is moved from the position of the first search block by 1 along the y-axis in the search area. Referring to FIG. 7A, the search block that is moved from the position of the first search block by 1 along the y-axis is formed by R2,1, R2,32, R33,1, and R33,32. FIG. 7B illustrates an equation for calculation of an SAD based on the search block shown in FIG. 7A and the previous matching block. SAD ⁡ ( previous ) 2 , ⁢ 1 = ⁢  S 1 , 1 - R 2 , 1  +  S 1 , 2 - R 2 , 2  + � +  S 1 , 16 - R 2 , 16  ⁢ ⁢ +  S 1 , 17 - R 2 , 17  + � + ⁢  S 1 , 32 - R 2 , 32  +  S 2 , 1 - R 3 , 1  +  S 2 , 2 - R 3 , 2  + ⁢ � +  S 2 , 16 - R 3 , 16  +  S 2 , 17 - R 3 , 17  + � + ⁢  S 2 , 32 - R 3 , 32  + � +  S 32 , 1 - R 33 , 1  + ⁢  S 32 , 2 - R 33 , 2  + � +  S 32 , 16 - R 33 , 16  + ⁢  S 32 , 17 - R 33 , 17  + � ⁢  S 32 , 32 - R 33 , 32  FIG. 8A illustrates the search area for the previous matching block for calculation of an SAD and a position of a last search block in the search area. Referring to FIG. 8A, the last search block in the search area is formed by R33,33, R33,64, R64,33, and R64,64. FIG. 8B illustrates an equation for calculation of an SAD based on the last search block shown in FIG. 8A and the previous matching block. SAD ⁡ ( previous ) 32 , 32 = ⁢  S 1 , 1 - R 32 , 32  +  S 1 , 2 - R 32 , 33  + � + ⁢ ⁢  S ⁢ 1 , 16 - R ⁢ 32 , 48  +  S 1 , 17 - R 32 , 49  + � + ⁢  S 1 , 32 - R 32 , 64  +  S 2 , 1 - R 33 , 32  +  S 2 , 2 - R 33 , 33  + ⁢ � +  S 2 , 16 - R 33 , 48  +  S 2 , 17 - R 33 , 49  + � + ⁢  S 2 , 32 - R 33 , 64  + � +  S 32 , 1 - R 64 , 32  + ⁢  S 32 , 2 - R 64 , 33  + � +  S 32 , 16 - R 64 , 48  + ⁢  S 32 , 17 - R 64 , 49  + � +  S 32 , 32 - R 64 , 64  FIGS. 9A-through 12B illustrate positions of search blocks in a search area for a current matching block and SADs according to the positions. FIG. 9A illustrates a search area for a current matching block for calculation of an SAD and a position of a first search block in the search area. Referring to FIG. 9A, the search area for the current matching block is formed by R1,17, R1,80, R64,17, and R64,80 and the first search block that is first searched in the search area is formed by R1,17, R1,48, R32,17, and R32,48. FIG. 9B illustrates an equation for calculation of an SAD based on the first search block shown in FIG. 9A and the current matching block. SAD ⁡ ( current ) 1 , ⁢ 1 = ⁢  S 1 , 17 - R 1 , 17  +  S 1 , 32 - R 1 , 32  + � + ⁢ ⁢  S ⁢ 1 , ⁢ 33 - R ⁢ 1 , ⁢ 33  +  S 1 , 48 - R 1 , 48  + � + ⁢  S 1 , 17 - R 2 , 17  +  S 2 , 32 - R 2 , 32  +  S 2 , 33 - R 2 , 33  + ⁢ � +  S 2 , 48 - R 2 , 48  + � +  S 32 , 17 - R 32 , 17  + � + ⁢  S 32 , 32 - R 32 , 32  +  S 32 , 33 - R 32 , 33  + � + ⁢  S 32 , 48 - R 32 , 48  FIG. 10A illustrates the search area for the current matching block for calculation of an SAD and a position of a search block that is moved from the position of the first search block by 1 along the x-axis in the search area. Referring to FIG. 10A, the search block that is moved from the position of the first search block by 1 along the x-axis direction is formed by R1,18, R1,49, R32,18, and R32,49. FIG. 10B illustrates an equation for calculation of an SAD based on the search block shown in FIG. 10A and the current matching block. SAD ⁡ ( current ) 1 , 2 = ⁢  S 1 , 17 ⁢ - ⁢ R 1 , 18  + � +  S 1 , 32 ⁢ - ⁢ R 1 , 33  + ⁢  S 1 , 33 ⁢ - ⁢ R 1 , 34  + � +  S 1 , 48 ⁢ - ⁢ R 1 , 49  + ⁢  S 2 , 17 ⁢ - ⁢ R 32 , 18  + � +  S 2 , 32 ⁢ - ⁢ R 2 , 33  + ⁢  S 2 , 33 ⁢ - ⁢ R 2 , 34  + � +  S 2 , 48 ⁢ - ⁢ R 2 , 49  + � + ⁢  S 32 , 17 ⁢ - ⁢ R 32 , 18  + � +  S 32 , 32 ⁢ - ⁢ R 32 , 33  + ⁢  S 32 , 33 ⁢ - ⁢ R 32 , 34  + � +  S 32 , 48 ⁢ - ⁢ R 32 , 49  FIG. 11A illustrates the search area for the current matching block for calculation of an SAD and a position of a search block that is moved from the position of the first search block by 1 along the y-axis in the search area. Referring to FIG. 11A, the search block that is moved from the position of the first search block by 1 along the y-axis is formed by R2,17, R2,48, R33,17, and R33,48. FIG. 11B illustrates an equation for calculation of an SAD based on the search block shown in FIG. 11A and the current matching block. SAD ⁡ ( current ) 2 , 1 = ⁢  S 1 , 17 ⁢ - ⁢ R 2 , 17  + � +  S 1 , 32 ⁢ - ⁢ R 2 , 32  + ⁢  S 1 , 33 ⁢ - ⁢ R 2 , 33  + � +  S 1 , 48 ⁢ - ⁢ R 2 , 48  + ⁢  S 2 , 17 ⁢ - ⁢ R 3 , 17  + � +  S 2 , 32 ⁢ - ⁢ R 3 , 32  + ⁢  S 2 , 33 ⁢ - ⁢ R 3 , 33  + � +  S 2 , 48 ⁢ - ⁢ R 3 , 48  + � + ⁢  S 32 , 17 ⁢ - ⁢ R 33 , 17  + � +  S 32 , 32 ⁢ - ⁢ R 33 , 32  + ⁢  S 32 , 33 ⁢ - ⁢ R 33 , 33  + � +  S 32 , 48 ⁢ - ⁢ R 33 , 48  FIG. 12A illustrates the search area for the current matching block for calculation of an SAD and a position of a last search block in the search area. Referring to FIG. 12A, the last search block in the search area is formed by R33,49, R33,80, R64,49, and R64,80. FIG. 12B illustrates an equation for calculation of an SAD based on the last search block shown in FIG. 12A and the current matching block. SAD ⁡ ( current ) 32 , 32 = ⁢  S 1 , 17 ⁢ - ⁢ R 33 , 49  + � +  S 1 , 32 ⁢ - ⁢ R 33 , 64  + ⁢  S 1 , 33 ⁢ - ⁢ R 33 , 65  + � +  S 1 , 48 ⁢ - ⁢ R 33 , 80  + ⁢  S 2 , 17 ⁢ - ⁢ R 34 , 49  + � +  S 2 , 32 ⁢ - ⁢ R 34 , 64  + ⁢  S 2 , 33 ⁢ - ⁢ R 34 , 65  + � +  S 2 , 48 ⁢ - ⁢ R 34 , 80  + � + ⁢  S 32 , 17 ⁢ - ⁢ R 64 , 49  + � +  S 32 , 32 ⁢ - ⁢ R 64 , 64  + ⁢  S 32 , 33 ⁢ - ⁢ R 64 , 65  + � +  S 32 , 48 ⁢ - ⁢ R 64 , 80  From comparisons between the SADs for the previous matching block and the current matching block, it can be seen that a half of an equation for calculation of each SAD is common between the previous matching block and the current matching block as shown in FIG. 13. Referring to FIG. 13, a right half of the equation for the SAD (previous) is the same as a left half of the SAD (current). In other words, a right half 1310 of SAD(previous)1,1 is the same as a left half 1315 of SAD(current)1,1, a right half 1330 of SAD(previous)1,2 is the same as a left half 1335 of SAD(current)1,2, a right half 1350 of SAD(previous)2,1 is the same as a left half 1355 of SAD(current)2,1, and a right half 1370 of SAD(previous)32,32 is the same as a left half 1375 of SAD(current)32,32. Thus, instead of calculating all the items of an equation for a current SAD, a calculated right half of a previous SAD is stored, and only a right half of the current SAD is calculated and a left half of the current SAD is substituted by the stored right half of the previous SAD, thereby performing calculation rapidly while reducing hardware. FIG. 14 is an exemplary schematic block diagram of an apparatus for motion estimation according to the present invention. Referring to FIG. 14, an apparatus 1400 for motion estimation includes a reference buffer 1410, a search buffer 1420, a predicting unit 1500, a mean of absolute differences (MAD) storing unit 1430, a motion vector determining unit 1440, and a motion vector storing unit 1450. The reference buffer 1410 stores a reference frame that is a current input image frame. Pixels in a matching block of the reference frame are divided into luminance components and chrominance components, and the reference buffer 1410 stores only the luminance components. A matching block extracted from the reference frame stored in the reference buffer 1410 is input to the predicting unit 1500. The search buffer 1420 stores a previous frame that is adjacent to the reference frame stored in the reference buffer 1410. The search buffer 1420 stores luminance components of all the pixels in a search area for motion estimation of a current frame. A search area extracted from the search (previous) frame stored in the search buffer 1420 is input to the predicting unit 1500. The predicting unit 1500 calculates an MAD for a right half of a current matching block using the matching block from the reference buffer 1410 and a block of the search area from the search buffer 1420, receives an MAD for a right half of a previous matching block (corresponding to a left half of the current matching block) from the MAD storing unit 1430, adds the MAD for the right half of the current matching block and the MAD for the left half of the current matching block to obtain a final MAD, and outputs the final MAD to the motion vector determining unit 1440. The predicting unit 1500 stores the calculated MAD for the right half of the current matching block in the MAD storing unit 1430 for use in calculation of an MAD for a next matching block. The motion vector determining unit 1440 receives 32�32 MADs from the predicting unit 1500, determines a search block having the smallest MAD among the received MADs, calculates a motion vector of the determined search block, and stores the calculated motion vector in the motion vector storing unit 1450. The motion vector storing unit 1450 stores motion vectors determined by the motion vector determining unit 1440. FIG. 15 is an exemplary detailed block diagram of the predicting unit 1500 and the MAD storing unit 1430 shown in FIG. 14. Referring to FIG. 15, the predicting unit 1500 includes a total of 32 prediction elements including a first prediction element 1510, a second prediction element 1520, . . . , and a thirty-second prediction element 1530. Since each of the 32 prediction elements included in the predicting unit 1500 calculates an MAD for at least one of search blocks in a search area and the 32 prediction elements operate simultaneously, MADs for 32 search blocks are calculated at a time. Thus, for example, to calculate MADs for search blocks in the search area as shown in FIG. 5A, a total of 32 calculations are required. In other words, in a first calculation, the first prediction element 1510 calculates MAD1,1, the second prediction element 1520 calculates MAD1,2, and the thirty-second prediction element 1530 calculates MAD1,32, and a total of 32 MADs calculated are output to the motion vector determining unit 1440 at a time. In a second calculation, the first prediction element 1510 calculates MAD2,1, the second prediction element 1520 calculates MAD2,2, and the thirty-second prediction element 1530 calculates MAD2,32, and a total of 32 MADs calculated are output to the motion vector determining unit 1440 at a time. Through 32 calculations performed in this way, MADs for 32�32 search blocks can be obtained. The right half calculation unit 1511 receives a matching block from the reference buffer 1410 and a search block from the searching buffer 1420, calculates a right half of an SAD based on the received matching block and search block, and calculates an MAD by performing an operation such as a shift on the calculated right half of the SAD. The right half calculation unit 1511 outputs the calculated partial MAD to the MAD calculation unit 1512 and to the MAD storing unit 1430 to store the same for use in calculation of an MAD for a next matching block. The MAD calculation unit 1512 receives the MAD for the right half for the current matching block from the right half calculation unit 1511, reads an MAD for a right half for a previous matching block, i.e., an MAD for a left half for a current matching block, from the MAD storing unit 1430, adds the received MAD and the read MAD, and outputs the result of the addition to the motion vector determining unit 1440. The MAD storing unit 1430 includes a total of 32 memory elements including a first memory element 1431, a second memory element 1432, . . . , and a thirty-second memory element 1433. Each of the 32 memory elements is composed of a total of 32 memory cells that store 32 MADs. For example, an MAD stored in a memory element at a predetermined clock time is input to the MAD calculation unit 1512 after 32 calculations for use in calculation of an MAD for a next matching block. Operations of the predicting unit 1500 and the MAD storing unit 1430 will now be described with reference to FIGS. 13 and 15. The MAD storing unit 1430 stores MADs for a previous matching block. The right half of MAD1,1, which is calculated by performing an operation such as a shift on the right half 1310 of an SAD, is stored in a first memory cell of the first memory element 1431, the right half of MAD1,2, which is calculated by performing an operation such as a shift on the right half 1330 of an SAD, is stored in a first memory cell of the second memory element 1432, and the right half of MAD1,32, which is calculated by performing an operation such as a shift on the right half 1350 of an SAD, is stored in a first memory cell of the thirty-second memory element 1433. In calculation of MADs for a current matching block, the right half calculation unit 1511 of the first prediction element 1510 calculates a right half of 1320 MAD1,1 and outputs the calculated right half 1320 to the MAD calculation unit 1512, and the MAD calculation unit 1512 adds the received right half 1320 and the left half 1315 read from the first memory element 1431 to obtain MAD0. Similarly, other second through thirty-second prediction elements obtain and output MADs. In the present invention where a half of a previously calculated MAD is used for motion estimation, the amount of computation can be reduced through overlapping block-based motion estimation (OBME) using sampled pixels of a matching block for motion estimation. In OBME, motion estimation is performed using a matching (ME) block that is larger than a motion compensation (MCI) block. The important point is that a matching block composed of sampled pixels is used for motion estimation to reduce the amount of computation. Referring to FIG. 16, a matching block has a size of 32�32 pixels and a motion compensation block has a size of 16�16 pixels. A sampling rate of the matching block is assumed to be �. Thus, the number of valid pixels of the matching block is 16�16. The sampling rate can be changed if necessary. A change in the sampling rate may require a change in a design, but does not change the basic principle of a design method. To confirm that the amount of computation can be reduced through sampling of the matching block, a principle where the matching block is 2:1 sampled will now be described. An SAD for a previous matching block is given by SAD ( k , l ) ⁡ ( x , y ) = ∑ i = 1 16 ⁢ ∑ j = 1 16 ⁢  f n ⁡ ( k + 2 ⁢ ⁢ i + x , l + 2 ⁢ j + y ) - f n - 1 ⁡ ( k + 2 ⁢ i , l + 2 ⁢ j )  An SAD for the current matching block is given by SAD ( k + 16 , ⁢ l ) ⁡ ( x , y ) = ∑ i = 1 16 ⁢ ∑ j = 1 16 ⁢  f n ⁡ ( k + 16 + 2 ⁢ i + x , l + 2 ⁢ j + y ) - f n - 1 ⁡ ( k + 2 ⁢ i , l + 2 ⁢ j )  A result of subtracting the SAD for the previous matching block from the SAD for the current matching block can be given by SAD ( k + 16 , l ) ⁡ ( x , y ) - SAD ( k , l ) ⁡ ( x , y ) = ⁢ ∑ i = 1 16 ⁢ ∑ j = 1 16 ⁢ S ( i , j ) ⁡ ( k + 16 , l ) - ⁢ ∑ i = 1 16 ⁢ ∑ j = 1 16 ⁢ S ( i , j ) ⁡ ( k , l ) if , ⁢ S ( i , j ) ⁡ ( k , l ) ≡  f n ⁡ ( k + 2 ⁢ i + x , l + 2 ⁢ j + y ) - f n - 1 ⁡ ( k + 2 ⁢ i , l + 2 ⁢ j )  S ( i , j ) ⁡ ( k + 16 , l ) = ⁢  f n ⁡ ( k + 16 + 2 ⁢ i + x , l + 2 ⁢ j + y ) - f n - 1 ⁡ ( k + 16 + 2 ⁢ i , l + 2 ⁢ j )  = ⁢  f n ⁡ ( k + 2 ⁢ ( 8 + i ) + x , l + 2 ⁢ j + y ) - f n - 1 ⁡ ( k + 2 ⁢ ( 8 + i ) , l + 2 ⁢ j )  = ⁢ S ( i + 8 , j ) ⁡ ( k , l ) Thus, the result can be arranged and developed as follows. SAD ( k + 16 , l ) ⁡ ( x , y ) - SAD ( k , l ) ⁢ ( x , y ) = ⁢ ∑ i = 1 16 ⁢ ∑ j = 1 16 ⁢ S ( i , j ) ⁢ ( k + 16 , l ) - ⁢ ∑ i = 1 16 ⁢ ∑ j = 1 16 ⁢ S ( i , j ) ⁡ ( k , l ) = ⁢ ∑ i = 1 16 ⁢ ∑ j = 1 16 ⁢ S ( i + 8 , j ) ⁡ ( k , l ) - ⁢ ∑ i = 1 16 ⁢ ∑ j = 1 16 ⁢ S ( i , j ) ⁡ ( k , l ) = ⁢ ∑ m = 9 24 ⁢ ∑ j = 1 16 ⁢ S ( m , j ) ⁡ ( k , l ) - ⁢ ∑ i = 1 ⁢ 16 ⁢ ∑ j = 1 ⁢ 16 ⁢ S ( i , ⁢ j ) ⁡ ( k , l ) = ⁢ ∑ i = 17 24 ⁢ ∑ j = 1 16 ⁢ S ( i , j ) ⁡ ( k , l ) - ⁢ ∑ i = 1 ⁢ 8 ⁢ ∑ j = 1 ⁢ 16 ⁢ S ( i , ⁢ j ) ⁡ ( k , l ) ⁢ ∵ ∑ m = 9 24 ⁢ ∑ j = 1 16 ⁢ S ( m , j ) ⁡ ( k , l ) = ∑ m = 17 24 ⁢ ∑ j = 1 16 ⁢ S ( m , j ) ⁡ ( k , l ) + ∑ m = 9 16 ⁢ ∑ j = 1 16 ⁢ S ( m , j ) ⁡ ( k , l ) ∑ i = 1 16 ⁢ ∑ j = 1 16 ⁢ S ( i , j ) ⁡ ( k , l ) = ∑ i = 1 8 ⁢ ∑ j = 1 16 ⁢ S ( i , j ) ⁡ ( k , l ) + ∑ i = 9 16 ⁢ ∑ j = 1 16 ⁢ S ( i , j ) ⁡ ( k , l ) SAD ( k + 16 , l ) ⁡ ( x , y ) = SAD ( k , l ) ⁡ ( x , y ) + ∑ i = 17 24 ⁢ ∑ j = 1 16 ⁢ S ( i , j ) ⁡ ( k , l ) - ∑ i = 1 8 ⁢ ∑ j = 1 16 ⁢ S ( i , j ) ⁡ ( k , l ) Thus, by re-arranging the above equation, the SAD for the current matching block can be divided into a part 1 and a part 2 as follows. ∴ SAD ( k + 16 , l ) ⁡ ( x , y ) = ∑ i = 9 16 ⁢ ∑ j = 1 16 ⁢ S ( i , j ) ⁡ ( k , l ) _ PART ⁢ ⁢ 1 - ∑ i = 17 24 ⁢ ∑ j = 1 16 ⁢ S ( i , j ) ⁡ ( k , l ) _ PART ⁢ ⁢ 2 As can be seen from the above equation, the part 1 is a left half of the SAD for the current matching block and the part 2 is a right half of the SAD for the current matching block. The part 1 which is the left half of the SAD for the current matching block, corresponds to a right half of the SAD for the previous matching block. Thus, like a case where the matching block is not 2:1 sampled, a result of calculation of the right half of the SAD for the previous matching block is stored and the stored result is used for calculation of the SAD for the current matching block. As described above, according to the present invention, a match difference obtained for a previous matching block is used for calculation of a match difference for a current matching block, thereby reducing the amount of computation and hardware resources required for motion estimation. While the present invention has been particularly shown and described with reference to exemplary embodiments thereof, it will be understood by those of ordinary skill in the art that various changes in form and details may be made therein without departing from the spirit and scope of the present invention as defined by the following claims. Referenced byCiting PatentFiling datePublication dateApplicantTitleUS7639888Nov 10, 2004Dec 29, 2009Fotonation Ireland Ltd.Method and apparatus for initiating subsequent exposures based on determination of motion blurring artifactsUS8294748Dec 11, 2009Oct 23, 2012DigitalOptics Corporation Europe LimitedPanorama imaging using a blending mapDE112011103011T5Sep 9, 2011Nov 7, 2013Digitaloptics Corporation Europe Ltd.Stereoskopische (3D) Panoramaerstellung auf tragbaren Ger�tenWO2011069698A1Sep 24, 2010Jun 16, 2011Tessera Technologies Ireland LimitedPanorama imagingClassifications U.S. Classification375/240.17, 375/240.12, 375/E07.101, 375/240.16, 375/240.24International ClassificationH04N11/02, H04N7/12, H04N11/04, H04B1/66Cooperative ClassificationH04N19/00509European ClassificationH04N7/26L4ALegal EventsDateCodeEventDescriptionJan 25, 2006ASAssignmentOwner name: SAMSUNG ELECTRONICS CO., LTD., KOREA, REPUBLIC OFFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:HA, TAE-HYEUN;REEL/FRAME:017506/0676Effective date: 20060113RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google