Source: https://patents.google.com/patent/KR100677562B1/en
Timestamp: 2020-08-03 10:08:16
Document Index: 553500432

Matched Legal Cases: ['art;\n2', 'art,\n2', 'art;\n3', 'arts 1', 'art 1', 'art 2', 'art 1', 'art 1', 'art 2', 'art 1']

KR100677562B1 - Motion estimation method and motion estimation apparatus - Google Patents
Motion estimation method and motion estimation apparatus Download PDF
KR100677562B1
KR100677562B1 KR1020050010228A KR20050010228A KR100677562B1 KR 100677562 B1 KR100677562 B1 KR 100677562B1 KR 1020050010228 A KR1020050010228 A KR 1020050010228A KR 20050010228 A KR20050010228 A KR 20050010228A KR 100677562 B1 KR100677562 B1 KR 100677562B1
KR1020050010228A
KR20060089950A (en
2005-02-03 Priority to KR1020050010228A priority Critical patent/KR100677562B1/en
2006-08-10 Publication of KR20060089950A publication Critical patent/KR20060089950A/en
2007-02-02 Publication of KR100677562B1 publication Critical patent/KR100677562B1/en
Disclosed is a motion estimation method and apparatus capable of reducing a calculation amount according to the present invention.
According to an exemplary embodiment of the present invention, there is provided a motion estimation method comprising: storing inter-block matching differences calculated for a previous matching block on which motion estimation is to be performed; and using the stored inter-block matching differences, for a current matching block to perform motion estimation. Calculating a match between blocks and performing motion estimation on a current matching block by using the match between blocks calculated for the current matching block. According to the present invention as described above, by using the matching difference obtained with respect to the previous matching block for the matching difference calculation for the current matching block, it is possible to reduce the amount of computation in motion estimation and reduce the hardware.
1 is a conceptual diagram illustrating a process of interframe interpolation by motion estimation according to the prior art;
2A is a concept of a guard block used for motion estimation according to the prior art,
2B is a conceptual diagram illustrating a process of interframe interpolation by motion estimation using a guard block according to the prior art;
3 is an example of a matching block for executing SAD according to the present invention;
4A and 4B are examples of a previous matching block and a current matching block for explaining a motion estimation method according to the present invention;
5A is an example of a search area for SAD execution and a first search block in a search area for a previous matching block according to the present invention;
FIG. 5B shows the SAD for the search block shown in FIG. 5A, FIG.
6A is an example of a search area for SAD execution for a previous matching block and a search block moved by one on the x-axis than the search block shown in FIG. 5A according to the present invention;
FIG. 6B illustrates the SAD for the search block shown in FIG. 6A;
7A is an example of a search area for SAD execution with respect to a previous matching block and a search block moved by one on the y axis than the search block shown in FIG. 5A according to the present invention;
FIG. 7B illustrates the SAD for the search block shown in FIG. 7A;
8A is an example of a search area for SAD execution and a last search block in a search area for a previous matching block in accordance with the present invention;
8B illustrates the SAD for the search block shown in FIG. 8A;
9A is an example of a search area for SAD execution and a first search block in a search area for the current matching block according to the present invention;
9B illustrates the SAD for the search block shown in FIG. 9A;
FIG. 10A illustrates an example of a search area for SAD execution for a current matching block and a search block moved by one on the x-axis from the search block shown in FIG. 9A according to the present invention;
FIG. 10B illustrates the SAD for the search block shown in FIG. 10A;
FIG. 11A illustrates an example of a search area for SAD execution for a current matching block and a search block moved by one in the y-axis from the search block shown in FIG. 9A according to the present invention; FIG.
FIG. 11B illustrates the SAD for the search block shown in FIG. 11A;
12A is an example of a search area for SAD execution and a last search block in a search area for the current matching block according to the present invention;
12B illustrates the SAD for the search block shown in FIG. 12A;
FIG. 13 is a reference diagram for explaining a part of overlapping calculation between an SAD of a previous matching block and a current matching block according to the example shown in FIGS. 5A to 12B;
14 is a schematic block diagram of a motion estimation apparatus according to the present invention;
FIG. 15 is a detailed block diagram of a prediction unit and a MAD storage unit shown in FIG. 14;
FIG. 16 is a view for explaining an example of sampling a pixel used for SAD calculation in a matching block to reduce a calculation amount according to the present invention; FIG.
The present invention relates to a motion estimation method and a motion estimation apparatus.
In general, a PC or HDTV performs frame rate conversion in order to be compatible with programs having various broadcast signal standards such as PAL or NTSC. Frame rate conversion means converting the number of frames output per second. In particular, when the frame rate is increased, a process of interpolating a new frame is necessary.
On the other hand, according to the development of broadcasting technology, after compressing video data by video compression methods such as MPEG (Moving Picture Experts Group) and H.263, frame rate conversion is performed. In the field of image processing, video signals have redundancy because, in most cases, autocorrelation is large. Therefore, by eliminating redundancy during data compression, the data compression effect can be improved. At this time, in order to efficiently compress a video frame that changes in time, it is necessary to remove redundancy in the time axis direction.
The elimination of redundancy in the time axis direction is based on the idea that even if there is no motion in a frame or there is motion, a similar portion can be drastically reduced in the amount of data to be transmitted by taking and filling the previous frame or the like.
To this end, it is necessary to find the most similar block between the previous frame and the current frame. This is called motion estimation (ME), and the motion vector (MV) is used to represent the displacement of the block. It is called.
On the other hand, a block matching algorithm (hereinafter referred to as "BMA") is generally used in the motion estimation method in consideration of the accuracy of motion, real-time processing, hardware implementation, and the like. Intermediate image synthesis between frames for frame rate conversion (FRC) mainly uses the BMA as described above, and the intermediate image synthesis method using the BMA can be simply represented as shown in FIG. 1.
1, an estimate of the block and the motion between the block F n in the current frame in the previous frame F n-1 to synthesize the previous frame F n-1 and an intermediate image frame between the current frame F n F i To synthesize a block of the intermediate image frame F i .
BMA is easy to implement and suitable for real-time processing, and is used in compression standards such as MPEG2 / 4 and H.262 / 264 as well as frame rate conversion. However, its performance is excellent for motion estimation with only horizontal and vertical motion, but its performance is not good for image rotation or zooming.
In order to increase accuracy using BMA, the size of the matching block must be increased. As the block size increases, the accuracy increases, but the computational amount and the detailed expression become difficult. Smaller block sizes result in less computation and more detail, but less accuracy.
In the prior art, there is a method of performing motion estimation using a block having a guard block in order to enable a finer representation while increasing the accuracy of matching. As shown in FIG. 2A, motion estimation is performed using M × M blocks, and N × N blocks are used for motion compensation.
Referring to FIG. 2B, motion estimation performs motion estimation using a large block of M × M including a guard block, and actual motion compensation uses a motion compensation block of N × N. Therefore, the accuracy of matching can be improved and the accuracy of representation can be increased by synthesizing using N × N blocks. The problem with this method is that it still increases the amount of computation.
An object of the present invention is to provide a motion estimation method and apparatus for solving the above problems to reduce the amount of calculation.
One feature of the present invention for solving the above problems is, in the motion estimation method, storing the matched inter-block matching for the previous matching block to perform the motion estimation, and the matched inter-block matching Computing the inter-block matching for the current matching block to perform the motion estimation using the step, and performing the motion estimation for the current matching block using the inter-block matching difference calculated for the current matching block It is to include.
Preferably, the matching block is larger than the block to perform motion compensation.
In addition, when calculating the inter-block matching, it is preferable to calculate the inter-block matching by sampling pixels constituting the matching block.
According to another aspect of the present invention, there is provided a motion estimation method comprising: reading a right half portion of items constituting an inter-block matching with respect to a previous matching block from a memory, and a block for a current matching block to perform motion estimation. Calculating a right half portion of the items constituting a match between the two; adding the read right half portion and the calculated right half portion to obtain an inter-block match with respect to the current matching block; Performing motion estimation on the current matching block using the inter-matching difference.
The performing of the motion estimation may include determining a search block having a minimum match among interblock matching differences obtained for the entire search area, and determining a motion vector based on the determined search block and the current search block. It is preferable to include the step of.
According to still another aspect of the present invention, a motion estimation apparatus includes: a matching difference storage unit for storing the matched inter-block difference calculated with respect to a previous matching block, and a current matching to perform motion estimation using the stored match between blocks. And a motion vector determiner configured to estimate a match between blocks for the block, and a motion vector determiner for performing motion estimation on the current matched block using the matched block match calculated for the current matching block.
In still another aspect of the present invention, there is provided a motion estimation apparatus comprising: a matched difference storage unit configured to store a right half of items constituting an inter-block matched position with respect to a previous matching block, and a current matched block to perform motion estimation. Calculate the right half of the items constituting the interblock match for the block, and add the right half read from the match storage and the calculated right half to obtain an interblock match for the current matching block. And a motion vector determiner for performing motion estimation on the current matching block using the obtained interblock matching.
3 illustrates a matching block for SAD execution in accordance with the present invention.
Referring to FIG. 3, a block consisting of a, b, c, and d represented by a dotted line represents a matching block (that is, a previous matching block) calculated in a previous step, and a block consisting of b, d, e, and f represents a current Represents a matching block (i.e., current matching block) to be calculated in step. At this time, since the parts consisting of b and d overlap, by using the SAD values for the b and d parts calculated in the previous step in the current step, if only the part consisting of e and f is calculated, the entire b, d, e, f It is possible to find all the SADs for SAD is a difference between the matching block and the search block, and more specifically, the sum of the absolute value of the difference between the pixels of the matching block and the pixels of the search block.
First, the principle of reducing the amount of calculation in half through the equation will be described.
The SAD value for the previous matching block is represented as follows.
Here, (k, l) represents the coordinates of the pixel in the upper left corner of the previous matching block, i, j represents the x-axis index, y-axis index of the points included in the previous matching block, respectively. fn represents the current frame and fn-1 represents a previous frame adjacent to the current frame. In summary, fn (k + i + x, l + j + y) represents pixel values contained in the matching block when the coordinate of the pixel at the upper left corner of the matching block is (k, l), and fn-1 (k + i, l + j) represents pixel values contained in the search block for this matching block.
The SAD value for the current matching block is represented as follows.
SAD value for the current matching block-The SAD value for the previous matching block can be represented as follows.
In addition, the SAD value for the current matching block-the SAD value for the previous matching block can be collectively developed as follows.
Therefore, if the above equation is summarized, the SAD value for the current matching block can be divided into parts 1 and 2 as follows.
That is, part 1 of the SAD values for the current matching block is for the left half of the SAD values to be obtained for the current matching block, and part 2 is for the right half of the SAD values to be obtained for the current matching block. admit.
However, part 1, that is, the left half of the SAD value for the current matching block, corresponds to the right half of the SAD value for the previous matching block. Accordingly, the present invention contemplates that the value for the right half part calculated for the previous matching block is stored, and the value stored in this manner is used when calculating the SAD value for the current matching block.
Now, an example where the calculations overlap is described.
4A illustrates an example of a previous matching block for motion estimation according to the present invention.
Referring to FIG. 4A, a block to perform matching including an overlapping portion arranged around a previous motion compensation block and a previous motion compensation block includes S 1,1 , S 1,32 , S 32,1 , S 32,32 It is a block composed of.
4B illustrates an example of a current matching block for motion estimation according to the present invention.
Referring to FIG. 4B, a block to perform matching, including an overlapping portion arranged around the current motion compensation block and the current motion compensation block, includes S 1,17 , S 1,48 , S 32,17 , S 32,48 It is a block composed of.
5a to 8b show the position of the search block in the search area and the corresponding SAD value with respect to the previous matching block.
5A shows the search region for the previous matching block and the position of the first search block in this search region for SAD execution according to the present invention.
5A, the search region to be searched for the previous matching block is R 1,1 . An area constituted by R 1,64 , R 64,1 , R 64,64 , and the first search block in this search area is R 1,1 , R 1,32 , R 32,1 , R 32,32 It is a block composed of.
The SAD calculation performed based on the search block and the previous matching block as shown in FIG. 5A is shown in FIG. 5B.
SAD (old) 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 region for the previous matching block and the position of the search block moved by one on the x-axis than the position of the first search block in this search region for SAD execution according to the present invention.
Referring to FIG. 6A, a search block moved by one on the x axis from the position of the first search block in the search area is a block constituted by R 1,2 , R 1,33 , R 32,2 , and R 32,33 . to be.
The SAD calculation performed based on the search block and the previous matching block as shown in FIG. 6A is shown in FIG. 6B.
SAD (old) 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 region for the previous matching block and the position of the search block moved by one on the y axis than the position of the first search block in this search region for SAD execution according to the present invention.
Referring to Figure 7a, in the y-axis than the first position of the search block in the search range for the first search block is moved by R 2,1, R 2,32, R 33,1 , a block composed of the R 33,32 to be.
The SAD calculation performed based on the search block and the previous matching block as shown in FIG. 7A is shown in FIG. 7B.
SAD (old) 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 ｜
8A shows the search region for the previous matching block and the position of the last search block in this search region for SAD execution according to the present invention.
Referring to Figure 8a, the final search block in the search area is a block composed of the R 33,33, R 33,64, R 64,33 , R 64,64.
The SAD calculation performed based on the search block and the previous matching block as shown in FIG. 8A is shown in FIG. 8B.
SAD (old) 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 ｜
9A-12B show the position of a search block in the search area and the corresponding SAD value with respect to the current matching block.
9A shows the search region for the current matching block and the location of the first search block in this search region for SAD execution according to the present invention.
Referring to FIG. 9A, a search region to be searched for the current matching block is R 1,17 . An area constituted by R 1,80 , R 64,17 , R 64,80 , and the first search block in this search area is R 1,17 , R 1,48 , R 32,17 , R 32,48 It is a block composed of.
A SAD calculation performed based on the search block and the current matching block as shown in FIG. 9A is shown in FIG. 9B.
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 2,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 region for the current matching block and the position of the search block moved by one on the x-axis than the position of the first search block in the search region for SAD execution according to the present invention.
Referring to FIG. 10A, a search block moved by one on the x axis from the position of the first search block in the search area is a block constituted by R 1,18 , R 1,49 , R 32,18 , and R 32,49 . to be.
The SAD calculation performed based on the search block and the previous matching block as shown in FIG. 10A is shown in FIG. 10B.
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 2,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 region for the current matching block and the position of the search block moved by one on the y axis than the position of the first search block in the search region for SAD execution according to the present invention.
Referring to Figure 11a, the y-axis than the first position of the search block in the search range for the first search block is moved by the block composed of the R 2,17, 2,48 R, R 33,17, 33,48 R to be.
An SAD calculation performed based on the search block and the current matching block as shown in FIG. 11A is shown in FIG. 11B.
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 ｜
12A illustrates the search region for the current matching block and the location of the last search block in this search region for SAD execution according to the present invention.
Referring to FIG. 12A, the last search block in the search region is a block constituted by R 33,49 , R 33,80, R 64,49 , and R 64,80 .
A SAD calculation performed based on the search block and the current matching block as shown in FIG. 12A is shown in FIG. 12B.
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 ｜
However, when comparing the SAD values of the previous matching block and the current matching block, as shown in FIG. 13, half of the items constituting the SAD for each SAD are common to the previous matching block and the current matching block.
Referring to FIG. 13, it can be seen that the items for the right half of the items of the SAD (previous) are the same as the items for the left half of the items of the SAD (current).
That is, the right half (1310) of SAD (previous) 1,1 is the same as the left half (1315) of SAD (current) 1,1 , and the right half (1330) of SAD (previous) 1,2 is SAD (current). ) Same as left half (1335) of 1,2 , right half (1350) of SAD (previous) 2,1 equals left half (1355) of SAD (current) 2,1 , SAD (previous) 32 The right half (1370) of , 32 is the same as the left half (1375) of SAD (present) 32,32 .
Therefore, instead of calculating all the items in each SAD calculation, the right half of the items in the previous SAD is stored, and only the right half of the items in the current SAD calculation is stored, and the items in the right half of the previous SAD are stored in the left half. Import and use to perform calculations quickly with less hardware.
14 is a schematic block diagram of a motion estimation apparatus according to the present invention.
Referring to FIG. 14, the motion estimation apparatus 1400 may include a reference buffer 1410, a search buffer 1420, a predictor 1500, a MAD storage 1430, a motion vector determiner 1440, and the like. And a motion vector storage unit 1450.
The reference buffer 1410 stores a reference frame that is a current input image frame. The pixels in the matching block in the reference frame are divided into brightness and color elements, and the reference buffer stores only the brightness values. The matching block extracted from the reference frame of the reference buffer 1410 is input to the predictor 1500.
The search buffer 1420 stores the previous frame adjacent to the image frame stored in the reference buffer. The search buffer stores brightness values of all pixels in the search area for motion estimation of the current frame. The search region extracted from the search frame of the search buffer 1420 is input to the predictor 1500.
The prediction unit 1500 calculates an MAD value for the right half of the current matching block by using the matching block from the reference buffer 1410 and the search area block from the search buffer 1420, and then calculates the MAD value from the MAD storage unit 1430. Receives the MAD value for the right half of the previous matching block (this corresponds to the left half of the current matching block) and adds the MAD value for the right half of the current matching block and the MAD value for the left half of the current matching block. The MAD value is generated and the final MAD value is output to the motion vector determiner 1440. In addition, the prediction unit 1500 stores the MAD value calculated for the right half of the current matching block in the MAD storage unit 1430 in order to use the MAD value of the next matching block.
The motion vector determiner 1440 receives 32 × 32 MAD values from the predictor 1500, determines a search block having the smallest MAD value among them, calculates a motion vector from the determined search block, and then stores the motion vector. (1450).
The motion vector storage unit 1450 stores the motion vectors determined by the motion vector determiner 1440.
FIG. 15 is a detailed block diagram of the prediction unit and the MAD storage unit shown in FIG. 14.
Referring to FIG. 15, the prediction unit 1500 includes a total of 32 prediction elements of the first prediction element 1510, the second prediction element 1520, and the thirty-first prediction element 1530.
Each prediction element executes MAD for any one of the search blocks in the search region, and since 32 prediction elements included in the prediction unit operate simultaneously, MAD for 32 search blocks is executed at one time. Therefore, for example, a total of 32 executions are required to execute all the MADs for the search block of the search area as shown in FIG. 5A. That is, in one execution, the first predictive element calculates MAD 1,1 , the second predictive element calculates MAD 1,2 , and the 32 predictive element calculates MAD 1,32 to calculate 32 MADs. At the same time, it outputs to the motion vector determiner. In two executions, the first predictive element calculates MAD 2,1 , the second predictive element calculates MAD 2,2 , and the 32 predictive element calculates MAD 2,32 to calculate 32 MADs . Are simultaneously output to the motion vector determiner. If 32 executions are performed in this manner, MADs for 32 × 32 search blocks can be calculated.
Each prediction element includes a right half calculator and a MAD calculator.
The right half calculation unit receives the matching block from the reference buffer, receives the search block from the search buffer, calculates the SAD of the items for the right half of the SAD values that should be calculated for the target, and calculates the calculated SAD by using an operation such as shifting. Calculate The right half calculator outputs the partial MAD calculated as described above to the MAD calculator 1512 and also to the MAD storage unit 1430 to store it for use in the next matching block.
The MAD calculator 1512 receives the MAD for the right half from the right half calculator 1511 and from the MAD storage 1430 the MAD for the right half of the previous matching block, that is, the MAD for the left half of the current matching block. Read and add the MAD for the right half and the MAD for the left half and output it to the motion vector determiner 1440.
The MAD storage unit 1430 includes a total of 32 memory elements of the first memory element 1431, the second memory element 1432, and the thirty-first memory element 1433. Each memory element is composed of 32 memory cells, so that a total of 32 MADs can be stored. For example, the MAD stored in the memory element at a predetermined clock may be input to the MAD calculator after 32 execution units to be used for the calculation of the next MAD.
The operation will be described with reference to the example shown in FIG.
The MAD storage unit 1430 stores MAD values for the previous matching block. The right half 1310 of MAD1,1 is stored in the first memory cell of the first memory element 1431, and the right half 1330 of MAD1,2 is stored in the first memory cell of the second memory element 1432. The right half of MAD1,32 is stored in the first memory cell of the thirty-second memory element 1433.
When calculating the MAD for the current matching block, the lower half calculator 1511 of the first prediction element 1510 calculates the right half 1320 of MAD1,1, and outputs the value for the calculated right half to the MAD calculator. The MAD calculator generates MAD0 by adding the MAD 1320 for the received right half and the MAD 1315 for the left half read from the memory. The remaining second to thirty-first predictive elements also generate and output the MAD in this manner.
Meanwhile, as described above, the present invention of estimating the motion using the value calculated in the previous step using half of the MAD calculation is an overlapped block-based estimation method using an overlapping matching block that samples the pixels of the matching block for motion estimation. based motion estimation (OBME) can further reduce the amount of computation.
The OBME method performs motion estimation using a matching block (ME-block) that is larger than a block for motion compensation (MCI-block). An important point is the motion estimation using a matching block composed of sampled pixels to reduce the amount of computation. Is to run.
Referring to FIG. 16, the size of the matching block and the motion compensation block is composed of 32x32 pixels and 16x16 pixels, respectively. It is assumed that the sample rate of the matching block is 1/4. Thus, the effective number of pixels of the matching block is 16x16. The sample rate can be converted as needed. If the sample rate is changed, the design contents need to be changed, but the basic principle of the design method is not changed.
Even in the case where the matching block is sampled as described above, the principle when the matching block is sampled at 2: 1 to confirm that the calculation amount can be reduced according to the present invention will be described.
That is, part 1 of the SAD values for the current matching block is the value for the left half of the SAD values to be obtained for the current matching block, and part 2 is the value for the right half of the SAD values to be obtained for the current matching block. to be.
However, part 1, that is, the left half of the SAD value for the current matching block corresponds to the right half of the SAD value for the previous matching block. Therefore, even when the matching block is sampled at 2: 1, the value for the right half calculated for the previous matching block is stored in the same way as the case where the matching block is not sampled, and the value stored in this way when the SAD value for the current matching block is calculated Can be used.
According to the present invention as described above, by using the matching difference obtained with respect to the previous matching block for the matching difference calculation for the current matching block, the amount of calculation can be reduced in motion estimation and hardware can be reduced.
In the motion estimation method,
Storing the inter-block matching differences calculated for the previous matching block on which motion estimation is to be performed;
Calculating a match between blocks for the current matching block to which motion estimation is to be performed using the stored match between blocks;
And performing motion estimation on the current matching block by using the inter-block matching difference calculated for the current matching block.
And the matching block is larger than a block to perform motion compensation.
And calculating a match between blocks by sampling pixels constituting the matching block when calculating the match between blocks.
Reading the right half of the items from the memory for calculating the inter-block matching for the previous matching block;
Calculating a right half portion of the items for calculating the inter-block matching for the current matching block on which motion estimation is to be performed;
Adding the read right half portion and the calculated right half portion to obtain an inter-block match for the current matching block;
And performing motion estimation on the current matching block using the obtained interblock matching result.
Performing the motion estimation,
Determining a search block having a minimum match among interblock matching differences obtained for the entire search area;
And determining a motion vector based on the determined search block and the current search block.
In the motion estimation apparatus,
A matched storage unit for storing the matched inter-block matched for the previous matching block;
A prediction unit configured to calculate a match between blocks with respect to a current matching block to perform motion estimation using the stored match between blocks;
And a motion vector determiner configured to perform motion estimation on the current matching block by using the inter-block matching difference calculated for the current matching block.
And the prediction unit calculates a match between blocks by sampling pixels constituting the matching block when calculating the match between blocks.
And a matching difference storage unit for storing a right half portion of items for calculating an inter-block matching difference for the previous matching block.
Compute the right half of the items for calculating the inter-block matching for the current matching block to perform the motion estimation, and add the right half and the calculated right half to the current matching. A prediction unit for obtaining a match between blocks for a block,
And a motion vector determiner configured to perform motion estimation on the current matching block using the obtained interblock matching result.
The prediction unit,
The motion vector determiner,
And a search block having a minimum match among interblock matching differences obtained for the entire search area, and determining a motion vector based on the determined search block and the current search block.
KR1020050010228A 2005-02-03 2005-02-03 Motion estimation method and motion estimation apparatus KR100677562B1 (en)
KR1020050010228A KR100677562B1 (en) 2005-02-03 2005-02-03 Motion estimation method and motion estimation apparatus
US11/338,745 US7889795B2 (en) 2005-02-03 2006-01-25 Method and apparatus for motion estimation
CN 200610004203 CN100563343C (en) 2005-02-03 2006-01-28 The method and apparatus that is used for estimation
KR20060089950A KR20060089950A (en) 2006-08-10
KR100677562B1 true KR100677562B1 (en) 2007-02-02
KR19990055733A (en) * 1997-12-27 1999-07-15 이계철 A method of expanding the search area in an all-area search block matching device
KR20040079086A (en) * 2003-03-06 2004-09-14 삼성전자주식회사 Method and apparatus for generating the motion vector of interpolated image using the adaptive bi-directional motion estimation
GB2378345B (en) 2001-07-09 2004-03-03 Samsung Electronics Co Ltd Motion estimation apparatus and method for scanning a reference macroblock window in a search area
TW564645B (en) * 2002-06-13 2003-12-01 Avision Inc Gamma table establishing method and gamma correcting method executed based on the gamma table
EP1590957A1 (en) * 2003-01-23 2005-11-02 Philips Electronics N.V. Background motion vector detection
2005-02-03 KR KR1020050010228A patent/KR100677562B1/en not_active IP Right Cessation
2006-01-25 US US11/338,745 patent/US7889795B2/en active Active
2006-01-28 CN CN 200610004203 patent/CN100563343C/en not_active IP Right Cessation
CN100563343C (en) 2009-11-25
US20060171464A1 (en) 2006-08-03
CN1816154A (en) 2006-08-09
KR20060089950A (en) 2006-08-10
US7889795B2 (en) 2011-02-15
JP6411615B2 (en) 2018-10-24 Predictive decoding method
US9621917B2 (en) 2017-04-11 Continuous block tracking for temporal prediction in video encoding
CN107318026B (en) 2019-12-24 Video encoder and video encoding method
JP2015536092A (en) 2015-12-17 Standard-based model-based video encoding and decoding
TWI248313B (en) 2006-01-21 Apparatus capable of performing both block-matching motion compensation and global motion compensation and method thereof
US10412409B2 (en) 2019-09-10 Encoding system using motion estimation and encoding method using motion estimation
KR100727989B1 (en) 2007-06-14 Method and apparatus for inter-mode decision in video coding
KR20120026092A (en) 2012-03-16 Method, apparatus and device for obtaining video image motion information and template construction method
KR100541953B1 (en) 2006-01-10 Pixel-data selection device for motion compensation, and method of the same
KR101393824B1 (en) 2014-05-13 System and method for low complexity motion vector derivation
KR100605746B1 (en) 2006-07-31 Motion compensation apparatus based on block, and method of the same