Title of Invention	METHOD AND APPARATUS FOR DETERMINING THE QUALITY OF A BLOCK MATCH FOR A CANDIDATE MOTION VECTOR IN A VIDEO ENCODER SYSTEM
Abstract	A method and apparatus for determining the quality of a block match for a candidate motion vector in a video encoder system using motion vectors representing the difference in coordinates of a macroblock of data in a current frame of video data and coordinates of a related macroblock of data in a reference frame of video data. The method can include defining a search pattern, searching a region based on the search pattern for a candidate motion vector for evaluation, calculating a difference metric, calculating a bias based on the difference between a predictor motion vector and a candidate motion vector, determining a modified difference metric by adding the difference metric to the bias, and defining a final motion vector based on the modified difference metric.

Title of Invention

METHOD AND APPARATUS FOR DETERMINING THE QUALITY OF A BLOCK MATCH FOR A CANDIDATE MOTION VECTOR IN A VIDEO ENCODER SYSTEM

Abstract

A method and apparatus for determining the quality of a block match for a candidate motion vector in a video encoder system using motion vectors representing the difference in coordinates of a macroblock of data in a current frame of video data and coordinates of a related macroblock of data in a reference frame of video data. The method can include defining a search pattern, searching a region based on the search pattern for a candidate motion vector for evaluation, calculating a difference metric, calculating a bias based on the difference between a predictor motion vector and a candidate motion vector, determining a modified difference metric by adding the difference metric to the bias, and defining a final motion vector based on the modified difference metric.

Full Text	WO 2004/014060 PCT/US2003/023204 2 Motion Estimation is one of the most processor intensive units in a video encoding system. There are a number of existing block-based motion estimation techniques which try to strike a compromise between computational complexity and motion vector efficiency. Full search motion estimation (FSME) exhaustively compares a block in the current image frame to each pixel position located within a search window of a previously processed frame. The goodness of the block match at each pixel position is determined by measuring its corresponding distortion. A typical distortion measure used by block matching metrics is the sum of absolute difference (SAD) metric: Where,Bc is the block hi the current image frame and Bp is a block in the previous image frame. The indices m and n index the pixels within a block of N rows and M columns. A small SAD value corresponds to a good block match and a large SAD value corresponds to a poor block match. Unfortunately, FSME becomes prohibitive as the search window is increased. Another problem exists for FSME in that use of the SAD metric requires an excessive number of bits needed to encode motion vectors which results in compression inefficiency. Presently, there are several low complexity motion algorithms. All off these algorithms surfer from either offering poorer quality or from not offering enough reduction in computational complexity. There are also a few motion estimation algorithms proposed that offer somewhat improved quality at relatively reduced complexity. One possible approach is a zonal based approach. First, a motion vector predictor (PMV) is calculated as a best matching motion vector. Then, a motion vector search following a zonal pattern around the PMV is performed. This is followed by similar zonal search around a zero motion vector. At every step, there is a criterion to end the search if a good enough criterion is obtained. Unfortunately, this approach does not give consistently good results over a wide range of video sequences. A motion estimation algorithm called PMVFAST is very similar to the above described zonal approach. However, instead of a zonal search pattern, an iterative diamond search pattern is use. Large or small diamond search patterns can be used WO 2004/014060 PCT/US2003/023204 3 depending upon certain criteria. Unfortunately, this approach gives a very similar result when compared to the zonal approach. DISCLOSURE OF THE INVENTION A method and apparatus for determining the quality of a block match for a candidate motion vector in a video encoder system using motion vectors representing the difference in coordinates of a macroblock of data in a current frame of video data and coordinates of a related macroblock of data in a reference frame of video data. The method can include defining a search pattern, searching a region based on the search pattern for a candidate motion vector for evaluation, calculating a difference metric, calculating a bias based on the difference between a predictor motion vector and a candidate motion vector, determining a modified difference metric by adding the difference metric to the bias, and defining a final motion vector based on the modified difference metric. BRIEF DESCRIPTION OF THE DRAWINGS Fig. 1 is an exemplary block diagram of a video compression system according to one embodiment; Fig. 2 is an exemplary depiction of a neighborhood of a current macroblock according to one embodiment; Fig. 3 is an exemplary search pattern used during a first stage of a preferred embodiment; Fig. 4 is an exemplary search pattern used in a capture mode during a first stage of a preferred embodiment; Fig. 5 is an exemplary illustration of a search pattern used during a second stage of a preferred embodiment; Fig. 6 is an exemplary flowchart outlining the operation of the present invention according to a preferred embodiment; and Fig. 7 is an exemplary block diagram of a motion estimation circuit according to one embodiment. WO 2004/014060 PCT/US2003/023204 4 DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS The present invention gives an improved performance over a wide range of video sequences. There are several improvements and new algorithmic innovations that result in better quality. In fact, when averaged over several video sequences, the present invention can assist in improving the performance of the traditional full search algorithm in terms of achieved video compression efficiency. All the methods used in prior art focus on optimizing the block match, while, among other benefits, the present invention can explicitly take into account the number of bits needed to encode the video sequence. The present invention can also take advantage of the nature of motion encountered in real life video capture. Presently, with the wireless market taking off, there will be more requirements to enable video encoding technology on hand-held devices. Most of these devices do not have the processing capability to perform the intense computations of motion estimation. Thus, the high quality, low complexity motion estimation algorithm provided by the present invention can be extremely useful in such devices. According to one embodiment, the present invention can be performed in two stages. In the first stage several predictor motion vectors can be considered and a search around each of the candidates can be performed using a fixed search pattern. During the course of the first stage, if it is found that a good match is unlikely to be achieved, a new set of candidate motion vectors can be selected and a new search can be performed. This can be done to capture the motion of any new object that appears in the scene. In the second stage, the best result of the first stage can be considered and a new search using a moving, weighted, spiral search pattern can be performed to arrive the best block match. Fig. 1 is an exemplary block diagram of a video compression system 100 for a video encoder according to one embodiment. The video compression system 100 can include a modified sum of absolute differences (MSAD) motion estimation circuit 110, a motion compensation circuit 115, an adder 120, a discrete cosine transform circuit (DCT) 125, a quantizer 130, a variable length code (VLC) encoder 135, an inverse quantizer 140, an inverse discrete cosine transform circuit (IDCT) 145, another adder 150, and aprevious frame circuit 155. In operation, motion estimation is computed for blocks of image data from a current image frame using one or more previously processed image frames. The WO 2004/014060 PCT/US2003/023204 5 motion estimation circuit 110 outputs a motion vector corresponding to a processed block. The motion compensation circuit 115 forms a prediction block from the previous frame using the computed motion vectors. A difference image is computed by the adder 120 by subtracting the predicted image data from the current image frame. This difference image is transformed using the DCT circuit 125. Whereas the motion estimation circuit 110 and the motion compensation circuit 115 serve to reduce the temporal redundancy between image frames, the DCT circuit 125 serves to reduce the spatial redundancy within a frame. The DCT coefficients are subsequently are subject to reduced precision by the quantizer 140. The quantizer 140 increases compression while introducing numerical loss. The quantized DCT coefficients are then encoded by the VLC encoder 135 and transmitted in a compressed video bitstream along with the motion vectors. The local reconstruction loop is comprised of the inverse quantizer 140, the IDCT 145, and the adder 150. The inverse quantizer 140 reconstructs the DCT coefficients. The IDCT 145 transforms the DCT coefficients back into the spatial domain to form a quantized difference image. The reconstructed frame is computed by the adder 150 by adding the motion compensated data to the quantized difference image. This reconstructed data is then stored in the previous frame circuit 15 5 for use in processing subsequent image frames. The operation of the fast predictive motion search motion estimation circuit 110 can consist of two stages. In the first stage, a small search can be done around several motion vector predictors. These motion vector predictors (MVP) can be obtained from other motion vectors (MV). For initial definitions, an MV is the difference in co-ordinates of a block of data in the current frame of video data and the block of data in the reference frame to which it is matched. An MV has two components: X and Y. The value of an MV is described as an ordered pair (X, Y). MVPs are MVs that are used as a good "guess" of the best MV when performing a match. A macroblock (MB) is a 16xl6 block of data withinavideo frame. AMB can also refer to a blocks of data of different sizes as well (e.g. 8x8, 4x8,4x4,16x8 etc.) without loss of generality. One motion vector predictor can be based on a zero motion vector. A motion vector predictor being based on a particular motion vector can define the motion vector predictor as equal to the particular motion vector. The zero motion vector WO 2004/014060 PCT/US2003/023204 6 being a motion vector with the coordinates of (0,0). A second motion vector predictor can be based on a motion vector of the co-located macroblock in the previous frame. Fig. 2 is an exemplary illustration of the location of a current macroblock and neighboring macroblocks used to determine additional motion vectors. Thus, a third motion vector predictor can be based on the motion vector of the macroblock to the left of the current macroblock. A fourth motion vector predictor can be based on the motion vector of the macroblock to the top of or above the current macroblock. A fifth motion vector predictor can be based on the motion vector of the macroblock above and to the right of the current macroblock. A sixth motion vector predictor can be based on the median motion vector of the third, fourth, and fifth motion vector predictors. This median motion vector predictor can be computed independently for the X and Y components of the motion vector. A seventh motion vector predictor can be based on an estimated global motion vector. This global motion vector is estimated by the motion estimation circuit 110 as the average of all final motion vectors of the previous frame for which a difference metric was below a certain threshold THRESH1. The difference metric can be a sum of absolute difference metric, a sum of squares difference metric, a modified sum of absolute difference metric, or any other useful metric. In the preferred embodiment, the value of THRESH1 chosen is: THRESH1 = SAD1 + OFFSET, Where OFFSET may nominally be set to 500 Where SAD1 is given by the equation: Here m and n are indexes of the pixel. M and N are the dimensions of the block. For an example macroblock, M= N= 16. The global motion vector may also be determined by other means such as motion sensors on video cameras, other algorithms, or any other means for determining a global motion vector. Further motion vector predictors can be determined based on the result of motion estimation done for the same macroblock, but on a different previously coded frame. WO 2004/014060 PCT/US2003/023204 7 Thus, the motion estimation circuit 110 can determine the global motion vector by using an average of all final motion vectors in a previous frame for which a difference metric is below a specified threshold, hi particular, the motion estimation circuit 110 can determine the global motion vector by calculating a difference metric for each of final motion vectors in a previous frame, comparing the difference metric for each of the final motion vectors in the previous frame with a predetermined threshold, and determining the global motion vector based on the each of the final motion vectors in a previous frame with a difference metric that is below the threshold. All MVs within a small region around each MVP can be searched. Then, the MV with the lowest MSAD metric can be chosen as the candidate MV for the second stage. The MSAD metric is defined below. Thus, the motion estimation circuit 110 can perform a predictive motion search by obtaining a plurality of motion vector predictors, the motion vector predictors representing approximations of possible motion vectors for a current macroblock, defining a search pattern, searching around each motion vector predictor of the plurality of motion vector predictors using the search pattern, and determining a final motion vector. The motion estimation circuit can further calculate a difference metric representing a quality of a macroblock match, where the difference metric can be a sum of absolute differences metric, a sum of squares of differences metric, or any other metric useful in motion estimation. An example search pattern around each MVP is shown in Fig. 3. As shown, the search pattern can extend more in the horizontal direction than in the vertical direction. This can take advantage of the fact that in most real life video data, there is more motion and variations in motion hi the horizontal direction. If, after evaluating the first 6 motion vectors, the best MV has a MSAD metric higher than a threshold THRESH2, the first stage can go into capture mode. In the preferred embodiment, THRESH2 is given by: THKESH2 = 4 MMSADAVG, MMSADA VG = Average of all MMSADS (i. e. MSADS of best MVs) of the previous frame. In the capture mode, additional MVPs can be considered such as those depicted in Fig. 4. For example, the 8 points can be: WO 2004/014060 PCT/US2003/023204 8 (-12,0) (12,0) (0, -8) (0, 8) (-6, 4) (6,4) (6, -4) (-6, -4) A search around each of the MVPs is performed using the same search pattern depicted in Fig. 3. In the preferred embodiment, only 4 out of the 8 MVPs can be considered for a macroblock. For the first macroblock, the first 4 are considered. For the next macroblock the other 4 MVPs are considered and so on. This can be done to reduce the number of computations. The aim of the capture mode is to detect any new object that moves rapidly into the screen. In such a scenario, the MVPs based on neighborhood motion vectors would fail. Using the 8 new points improves the chance of getting a good motion vector match. The 8 points can be chosen to favor the horizontal direction since there often is more motion in this direction. Thus, the motion estimation circuit 110 can search around each motion vector predictor of the plurality of motion vector predictors using the search pattern, determine a best motion vector having a difference metric higher than a predetermined threshold, and perform a search pattern around a new set of motion vector predictors. In the first stage, when the search pattern around a MVP is being evaluated, an early exit criterion can be employed to terminate the search for that MVP. The search can be terminated if the MS AD obtained for the MV is higher than the current minimum MSAD (MMSAD) by a threshold THRESH3, i.e.,(if{MSAD, > (MMSAD + THRESH3)). Where MSADi is the MSAD obtained for MVPi, MMSAD is the minimum of all the MSAD values obtained until this point for the current MB. In particular, it is the MSAD of the best MV. In the preferred embodiment, the value of THRESHS can be chosen to be around 768. Thus, the motion estimation circuit 110 can perform a search pattern on the motion vector predictors, determine a current difference metric for a current motion vector, compare the current difference metric to a previous minimum difference metric, set a new minimum difference metric if the current difference metric is below the previous minimum difference metric, and terminate the search pattern if the difference metric exceeds the previous minimum metric by a predetermined amount. Then, among all the MVs searched in the first stage, the MV that gives the lowest MSAD metric is chosen and this becomes a starting point for the second stage. WO 2004/014060 PCT/US2003/023204 9 In the second stage, 1he best MV from the first stage (i.e. the one giving the lowest MSAD) is chosen and a search is performed around this MV. For example, the search can be performed in a pattern as depicted in Fig. 5. The search pattern can start from the center and can spiral out in a sequence as shown in Fig. 5 as a sequence of numbers. As soon as a better MV is found (i.e. MV which gives a lower MSAD), the search pattern is re-centered around the new MV and the spiral search pattern starts over. This process continues until one of 3 conditions are met: CONDITION 1: The MSAD is below a threshold THRESH4, given by: THRESH4 = A Q + B Where Q is the quantization step size used by the encoder for the current MB, A and B are constants. In the preferred embodiment, A = S and B = 0. CONDITION 2: The maximum number of candidates, N, have already been considered in stage 2. In the preferred embodiment, N = 30. CONDITION 3: These is no improvement in the minimum MSAD (MMSAD) during the last M candidate MVs. Here M is a function of the index of the position of the last MV candidate in the spiral search pattern. For example, the search starts from index 0. It then spirals around points 1, 2, 3..... Whenever a better MV is found, the spiral search pattern gets re-centered around this new MV and the index starts from 0 once again. This index is used to determine the value of M. hi the preferred embodiment, M is chosen from the set of values {4, 4, 4,4,4,4,4,4, 4, 5, 5, 5,5,6,6, 6, 6,7,7,7,7,7,7, 8, 8, 8, 8, 8, 9, 9} based on the index. The best MV at the end of the second stage is chosen as the best MV for the macroblock. This MV can be further refined for half-pixel, quarter-pixel or higher accuracy in a subsequent stage using well known techniques. As mentioned above, the search pattern can be chosen to give wider coverage to the horizontal direction than the vertical direction. WO 2004/014060 PCT/US2003/023204 10 The MS AD metric can be a useful part of the invention. While the modified sum of differences metric gives preferred results, any difference metric can be interchangeably used in every embodiment of the present invention requiring a sum of absolute differences metric, a modified sum of differences metric, or any other difference metric. Furthermore, the MSAD metric is particularly useful in improving the performance of all video encoder systems. In particular, the MSAD metric can replace a SAD metric, a sum of squares metric, or any other metric in a video encoder system for improved performance. For example, the MSAD metric can be used in a FSME system, a PMVFAST system, or any other video encoder system. The MSAD metric is a function of the sum of absolute differences (SAD) described above, the candidate MV being evaluated, and the predictor motion vector (PMV). The PMV is generally used by the video encoder during the encoding of the final motion vector. The final motion vector is encoded as a difference with respect to PMV, which is different from a MVP. For example, it can be a unique MV defined within H.261, H.263, MPEG-1, MPEG-2 and MPEG-4 standards for the purpose of encoding motion vectors. The SAD is the metric used hi classical motion estimation algorithms as described above. For a macro block with a given PMV and for a candidate motion vector MV, MSAD is given by MSAD = SAD + Bias Where the bias is any value that is based on a motion vector difference metric between MV and PMV. For example, MSAD = SAD + C(\MVx-PMVx\ + \MVr-PMV¥\) According to another example the bias can be based on, C ((MVx - PMVx)2 + (MVy - PMVy)2) Where SAD is the classical metric used for the matching blocks defined earlier, MVX and MVy are the X and Y components of the candidate motion vector, PMVX arid PMVy are the X and Y components of PMV, and C is a constant. In the preferred embodiment, C is approximately 5. The PMV generally stays fixed for all the candidates in an MB, while the MV changes. The MSAD metric is independent of the motion estimation algorithm and can be used to advantage in practically all algorithms. The benefit of the new metric is the WO 2004/014060 PCT/US2003/023204 11 reduced number of bits needed to encode motion vectors by biasing the algorithm towards PMV thus improving the overall compression efficiency. The MSAD for the zero motion vector, MV = (0, 0), is treated as a special case. The zero MV could potentially lead to improved compression efficiency. But this can happen only if the resultant macroblock is coded in the "not coded" mode within H.261, H.263, MPEG-1, MPEG-2 and MPEG-4 standards. This can be taken into account by biasing the SAD in the case where it is below a certain threshold: If (SAD MSAD = SAD - THRESH6 Else MSAD = SAD + C(\PMVX\ + \PMVr\) Endif C, PMVX and PMVy are as described earlier. THRESH5 = DQ + E THRESH6=F Where Q is the quanization step size. D, E and F are constants. In a preferred embodiment D is approximately 128, E-Q, and F is approximately 100. Thus, Hie motion estimation circuit 110 can calculate a difference metric, calculate a bias based on a predictor motion vector and a candidate motion vector, and determine a modified difference metric based on the difference metric and the bias. Additionally, the motion estimation circuit 110 can calculate a difference metric, calculate a bias based on a predictor motion vector and a candidate motion vector, and determine a modified difference metric based on the difference metric and the bias. The motion estimation circuit 110 can determine a modified difference metric based on the difference metric and the bias by adding the difference metric to the bias. The motion estimation circuit 110 can also calculate the bias based on a predictor motion vector and a candidate motion vector further by determining a motion vector difference metric between the predictor motion vector and the candidate motion vector, and calculating the bias based on the motion vector difference metric between the predictor motion vector and the candidate motion vector. The motion estimation circuit 110 can additionally calculate the bias based on WO 2004/014060 PCT/US2003/023204 12 a predictor motion vector and a candidate motion vector by multiplying the absolute value of difference between the predictor motion vector and the candidate motion vector by a constant. For example, the constant can be equal to about five. The motion estimation circuit 110 can furthermore calculate a bias based on a predictor motion vector and a candidate motion vector further by adding an absolute value of the difference between horizontal coordinates of the predictor motion vector and the candidate motion vector to an absolute value of the difference between vertical coordinates of the predictor motion vector and the candidate motion vector. The candidate motion vector can be one of a plurality of candidate motion vectors being evaluated for a macroblock and the predictor motion vector can stay fixed for each candidate motion vector in a macroblock. The difference metric can be a sum of absolute differences metric. The difference metric can also be a sum of squares of differences metric. The motion estimation circuit 110 can also define a final motion vector based on the candidate motion vector and output the final motion vector. According to another related embodiment the present invention provides a method for determining the quality of a block match for a candidate motion vector in a video encoder system using motion vectors representing the difference in coordinates of a macroblock of data in a current frame of video data and coordinates of a related macroblock of data in a reference frame of video data. In this embodiment, the motion estimation circuit 110 can define a search pattern, search a region based on the search pattern for a candidate motion vector for evaluation, calculate a difference metric, calculate a bias based on the motion vector difference metric between a predictor motion vector and a candidate motion vector, determine a modified difference metric by adding the difference metric to the bias, and define a final motion vector based on the modified difference metric. The final motion vector can be defined for use in a second stage of the video encoder system. The difference metric can be at least one of a sum of absolute differences metric and a sum of squares of differences metric. The motion vector difference metric can be at least one of sum of absolute differences metric and a sum of squares of differences metric. The motion, estimation circuit 110 can search the region by searching around a plurality of motion vector predictors using the search pattern. The motion estimation circuit 110 can define the final motion vector by defining a final motion vector having a modified difference metric higher than a predetermined threshold, performing a second search WO 2004/014060 PCT/US2003/023204 13 pattern around a new plurality of motion vector predictors based on the final motion vector, and determining a new final motion vector based on the results of the step of performing a second search pattern. The motion estimation circuit 110 can defining the search pattern by defining a search pattern that is more extensive in a horizontal direction than in a vertical direction. The motion estimation circuit 110 can then output a motion vector based on the final motion vector. During the search process, it can be likely that search regions of different MVPs may overlap leading to repeated candidate motion vectors. A log can be maintained of all the candidates evaluated already and they are ignored if they have been considered already. The search sequences depicted are the ones used in the preferred embodiment They have been optimized to get a good match in the quickest possible time over a wide range of video sequences. It is possible to use alternative search patterns as well. The disclosed invention does not make any assumptions on the motion vector range. Any restriction on the motion vector values can be applied on the candidates and, if they are beyond the allowed range, they can be discarded. In the second stage of the preferred embodiment, the spiral search pattern can be re-centered on obtaining a new best matched candidate MV. Thus, the next point that needs to be evaluated may not be known apriori. The next candidate to be evaluated potentially depends on the result of evaluating the current candidate. Hence it may becomes difficult to implement several candidate MSAD calculations in parallel (which some hardware architectures may want to do). To alleviate this, the re-centering of the search pattern can be done after evaluating a set of candidates, allowing the set to be processed in parallel. Fig. 6 is an exemplary flowchart 600 outlining the operation of the motion estimation circuit 110 according to one embodiment. In step 610, the flowchart begins. In step 620, the motion estimation circuit 110 determines a predictor motion vector PMV. In step 630, the motion estimation circuit 110 determines a candidate motion vector MV. In step 640, the motion estimation circuit calculates an absolute value of the difference between horizontal components of the PMV and the candidate MV. In step 650, the motion estimation circuit 110 calculates an absolute value of the difference between vertical components of the PMV and the candidate MV. In step 660, the motion estimation circuit 110 calculates the bias by multiplying the WO 2004/014060 PCT/US2003/023204 14 difference between the components of the PMV and the candidate MV by a constant. In step 670, the motion estimation circuit 110 calculates the MSAD by adding the bias to a difference metric. In step 680, the flowchart ends. Fig. 7 is an exemplary block diagram of a fast predictive motion search motion estimation circuit 110 according to one embodiment The motion estimation circuit 110 can include a difference metric calculator 710, a bias calculator 720, a MSAD calculator 730, and a motion vector determination circuit 740. The circuits operate in accordance with their like functions described with respect to the flowchart 600. According to another related embodiment, a fast predictive motion search method can be performed by two stages. In the first stage, the 7 MVP candidates can be computed as described above. Then, for each MVP, all MV candidates can be evaluated according to the search pattern in Fig. 3 and the exit criteria can be employed to break out of the MVP or go into the capture mode. Next, if in the capture mode, the search can be performed at and around the MVP depicted in Fig. 4 using the same search pattern in Fig. 3 and the same exit criteria. Then, in the second stage, the best MV from the first stage can be chosen and a search can be performed in a spiral fashion depicted in Fig. 5. The spiral can be re-centered and reset the index can be reset to zero whenever a better match is found. Finally, the process can be continued until one of the three exit criteria are found. The disclosed invention can achieve a high degree of compression efficiency while keeping the complexity low. The complexity can be similar to the complexity of APDZSand PMVFAST. However, the achieved quality is higher. When compared with the standard lull search algorithm, which is the accepted reference in the industry, the present invention achieves about 0.6% better compression efficiency for a fixed video quality. This number was obtained after averaging over 24 different QCIF video sequences. One application for this invention is in real time video encoders on hand held devices. The typical bandwidth of such encoded video is in the range 32 kbps to 512 kbps and the typical video frame size is QCIF and CIF. The method of this invention is preferably implemented on a programmed processor. However, the video compression system 100, the motion estimation circuitry 110, and other elements may also be implemented on a general purpose or WO 2004/014060 PCT/US2003/023204 15 special purpose computer, a programmed microprocessor or microcontroller and peripheral integrated circuit elements, an ASIC or other integrated circuit, a hardware electronic or logic circuit such as a discrete element circuit, a programmable logic device such as a PLD, PLA, FPGA or PAL, or the like. In general, any device on which resides a finite state machine capable of implementing the flowcharts shown in the Figures and the methods described may be used to implement the processor functions of this invention. While this invention has been described with specific embodiments thereof, it is evident that many alternatives, modifications, and variations will be apparent to those skilled in the art. For example, various components of the embodiments may be interchanged, added, or substituted in the other embodiments. Accordingly, the preferred embodiments of the invention as set forth herein are intended to be illustrative, not limiting. Various changes may be made without departing from the spirit and scope of the invention. WO 2004/014060 PCT/US2003/023204 16 CLAIMS 1. A method for determining the quality of a block match for a candidate motion vector in a video encoder system comprising: calculating a difference metric; calculating a bias based on a predictor motion vector and a candidate motion vector; and determining a modified difference metric based on the difference metric and the bias, 2. The method according to claim 1, wherein the step of determining a modified difference metric based on the difference metric and the bias comprises adding the difference metric to the bias, 3. The method according to claim 1, wherein the step of calculating a bias based on a predictor motion vector and a candidate motion vector further comprises determining a motion vector difference metric between the predictor motion vector and the candidate motion vector, and calculating the bias based on the motion vector difference metric between the predictor motion vector and the candidate motion vector. 4. The method according to claim 3, wherein the step of calculating a bias based on a predictor motion vector and a candidate motion vector further comprises multiplying the motion vector difference metric between the predictor motion vector and the candidate motion vector by a constant. 5. The method according to claim 4, wherein the constant is equal to about five. WO 2004/014060 PCT/US2003/023204 17 6. The method according to claim 1, wherein the step of calculating a bias based on a predictor motion vector and a candidate motion vector further comprises adding an absolute value of the difference between horizontal coordinates of the predictor motion vector and the candidate motion vector to an absolute value of the difference between vertical coordinates of the predictor motion vector and the candidate motion vector. 7. The method according to claim 1, wherein the step of calculating a bias based on a predictor motion vector and a candidate motion vector further comprises adding a square of the difference between horizontal coordinates of the predictor motion vector and the candidate motion vector to a square of the difference between vertical coordinates of the predictor motion vector and the candidate motion vector. 8. The method according to claim 1, wherein the candidate motion vector is one of a plurality of candidate motion vectors being evaluated for a macroblock, and wherein the predictor motion vector stays fixed for each candidate motion vector in a macroblock. 9. The method according to claim 1, wherein the difference metric is a sum of absolute differences metric. 10. The method according to claim 1, wherein the difference metric is a sum of squares of differences metric. 11. The method according to claim 1, further comprising: defining a final motion vector based on the candidate motion vector; and WO 2004/014060 PCTAJS2003/023204 18 outputting the final motion vector. 12. A method for determining the quality of a block match for a candidate motion vector in a video encoder system using motion vectors representing the difference in coordinates of a macroblock of data in a current frame of video data and coordinates of a related macroblock of data in a reference frame of video data comprising: defining a search pattern; searching a region based on the search pattern for a candidate motion vector for evaluation; calculating a difference metric; calculating a bias based on the difference metric between a predictor motion vector and a candidate motion vector; determining a modified difference metric by adding the difference metric to the bias; and defining a final motion vector based on the modified difference metric. 13. The method according to claim 12, wherein the final motion vector is defined for use in a second stage of the video encoder system. 14. The method according to claim 12, wherein the difference metric is at least one of a sum of absolute differences metric and a sum of squares of differences metric. 15. The method according to claim 12, wherein the step of searching a region further comprises: searching around a plurality of motion vector predictors using the search pattern, and wherein the step of defining a final motion vector further comprises defining a final motion vector having a modified difference metric higher than a predetermined threshold, performing a second search pattern around a new plurality of motion vector predictors based on the final motion vector, and WO 2004/014060 PCT/US2003/023204 19 determining a new final motion vector based on the results of the step of performing a second search pattern. 16. The method according to claim 12, wherein the step of defining a search pattern farther comprises defining a search pattern that is more extensive in a horizontal direction than in a vertical direction. 17. The method according to claim 12, further comprising outputting a motion vector based on the final motion vector. 18. An apparatus for determining the quality of a block match for a candidate motion vector in a video encoder system using motion vectors representing the difference in coordinates of a macroblock of data in a current frame of video data and coordinates of a related macroblock of data in a reference frame of video data comprising: a current image macroblock input; a modified sum of absolute differences motion estimation circuit including a difference metric calculator, a bias calculator, a modified sum of absolute differences calculator, and a motion vector determination circuit; and a motion vector output. 19. The apparatus according to claim 18, wherein the difference metric calculator is at least one of a sum of absolute differences calculator and a sum of squares of differences calculator. 20. The apparatus according to claim 18, wherein the bias calculator calculates a bias by deterrnining the motion vector difference metric between a predictor motion vector and a candidate motion vector. WO 2004/014060 PCT/US2003/023204 20 21. The apparatus according to claim 20, where the bias calculator further calculates a bias by multiplying the motion vector difference metric between the predictor motion vector and the candidate motion vector by a constant. 22. The apparatus according to claim 20, where the bias calculator further determines the motion vector difference metric between a predictor motion vector and a candidate motion vector by adding an absolute value of the difference between horizontal coordinates of the predictor motion vector and the candidate motion vector to an absolute value of the difference between vertical coordinates of the predictor motion vector and the candidate motion vector. 23. The apparatus according to claim 22, wherein the candidate motion vector is one of a plurality of candidate motion vectors being evaluated for a macroblock, and wherein the predictor motion vector stays fixed for each candidate motion vector in the macroblock. 24. The apparatus according to claim 20, where the bias calculator further determines the motion vector difference metric between a predictor motion vector and a candidate motion vector by adding a square of the difference between horizontal coordinates of the predictor motion vector and the candidate motion vector a square of the difference between vertical coordinates of the predictor motion vector and the candidate motion vector. WO 2004/014060 PCT/US2003/023204 21 25. The apparatus according to claim 18, further comprising a motion compensation circuit coupled to the modified sum of absolute differences motion estimation circuit. 26. The apparatus according to claim 25, further comprising an adder coupled to the current image macroblock input and coupled to the motion compensation circuit. 27. The apparatus according to claim 26, further comprising: a discrete cosine transform circuit coupled to the adder; and a quantizer coupled to the discrete cosine transform circuit. 28. The apparatus according to claim 27, further comprising: an inverse quantizer coupled to the quantizer; and an inverse discrete cosine transform circuit coupled to the inverse quantizer. A method and apparatus for determining the quality of a block match for a candidate motion vector in a video encoder system using motion vectors representing the difference in coordinates of a macroblock of data in a current frame of video data and coordinates of a related macroblock of data in a reference frame of video data. The method can include defining a search pattern, searching a region based on the search pattern for a candidate motion vector for evaluation, calculating a difference metric, calculating a bias based on the difference between a predictor motion vector and a candidate motion vector, determining a modified difference metric by adding the difference metric to the bias, and defining a final motion vector based on the modified difference metric.

Full Text

WO 2004/014060 PCT/US2003/023204
2
Motion Estimation is one of the most processor intensive units in a video encoding system. There are a number of existing block-based motion estimation techniques which try to strike a compromise between computational complexity and motion vector efficiency.
Full search motion estimation (FSME) exhaustively compares a block in the current image frame to each pixel position located within a search window of a previously processed frame. The goodness of the block match at each pixel position is determined by measuring its corresponding distortion. A typical distortion measure used by block matching metrics is the sum of absolute difference (SAD) metric:

Where,Bc is the block hi the current image frame and Bp is a block in the previous image frame. The indices m and n index the pixels within a block of N rows and M columns. A small SAD value corresponds to a good block match and a large SAD value corresponds to a poor block match. Unfortunately, FSME becomes prohibitive as the search window is increased. Another problem exists for FSME in that use of the SAD metric requires an excessive number of bits needed to encode motion vectors which results in compression inefficiency.
Presently, there are several low complexity motion algorithms. All off these algorithms surfer from either offering poorer quality or from not offering enough reduction in computational complexity. There are also a few motion estimation algorithms proposed that offer somewhat improved quality at relatively reduced complexity.
One possible approach is a zonal based approach. First, a motion vector predictor (PMV) is calculated as a best matching motion vector. Then, a motion vector search following a zonal pattern around the PMV is performed. This is followed by similar zonal search around a zero motion vector. At every step, there is a criterion to end the search if a good enough criterion is obtained. Unfortunately, this approach does not give consistently good results over a wide range of video sequences.
A motion estimation algorithm called PMVFAST is very similar to the above described zonal approach. However, instead of a zonal search pattern, an iterative diamond search pattern is use. Large or small diamond search patterns can be used
WO 2004/014060 PCT/US2003/023204
3
depending upon certain criteria. Unfortunately, this approach gives a very similar result when compared to the zonal approach.
DISCLOSURE OF THE INVENTION
A method and apparatus for determining the quality of a block match for a candidate motion vector in a video encoder system using motion vectors representing the difference in coordinates of a macroblock of data in a current frame of video data and coordinates of a related macroblock of data in a reference frame of video data. The method can include defining a search pattern, searching a region based on the search pattern for a candidate motion vector for evaluation, calculating a difference metric, calculating a bias based on the difference between a predictor motion vector and a candidate motion vector, determining a modified difference metric by adding the difference metric to the bias, and defining a final motion vector based on the modified difference metric.
BRIEF DESCRIPTION OF THE DRAWINGS
Fig. 1 is an exemplary block diagram of a video compression system according to one embodiment;
Fig. 2 is an exemplary depiction of a neighborhood of a current macroblock according to one embodiment;
Fig. 3 is an exemplary search pattern used during a first stage of a preferred embodiment;
Fig. 4 is an exemplary search pattern used in a capture mode during a first stage of a preferred embodiment;
Fig. 5 is an exemplary illustration of a search pattern used during a second stage of a preferred embodiment;
Fig. 6 is an exemplary flowchart outlining the operation of the present invention according to a preferred embodiment; and
Fig. 7 is an exemplary block diagram of a motion estimation circuit according to one embodiment.
WO 2004/014060 PCT/US2003/023204
4
DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS
The present invention gives an improved performance over a wide range of video sequences. There are several improvements and new algorithmic innovations that result in better quality. In fact, when averaged over several video sequences, the present invention can assist in improving the performance of the traditional full search algorithm in terms of achieved video compression efficiency.
All the methods used in prior art focus on optimizing the block match, while, among other benefits, the present invention can explicitly take into account the number of bits needed to encode the video sequence. The present invention can also take advantage of the nature of motion encountered in real life video capture.
Presently, with the wireless market taking off, there will be more requirements to enable video encoding technology on hand-held devices. Most of these devices do not have the processing capability to perform the intense computations of motion estimation. Thus, the high quality, low complexity motion estimation algorithm provided by the present invention can be extremely useful in such devices.
According to one embodiment, the present invention can be performed in two stages. In the first stage several predictor motion vectors can be considered and a search around each of the candidates can be performed using a fixed search pattern. During the course of the first stage, if it is found that a good match is unlikely to be achieved, a new set of candidate motion vectors can be selected and a new search can be performed. This can be done to capture the motion of any new object that appears in the scene. In the second stage, the best result of the first stage can be considered and a new search using a moving, weighted, spiral search pattern can be performed to arrive the best block match.
Fig. 1 is an exemplary block diagram of a video compression system 100 for a video encoder according to one embodiment. The video compression system 100 can include a modified sum of absolute differences (MSAD) motion estimation circuit 110, a motion compensation circuit 115, an adder 120, a discrete cosine transform circuit (DCT) 125, a quantizer 130, a variable length code (VLC) encoder 135, an inverse quantizer 140, an inverse discrete cosine transform circuit (IDCT) 145, another adder 150, and aprevious frame circuit 155.
In operation, motion estimation is computed for blocks of image data from a current image frame using one or more previously processed image frames. The
WO 2004/014060 PCT/US2003/023204
5
motion estimation circuit 110 outputs a motion vector corresponding to a processed block. The motion compensation circuit 115 forms a prediction block from the previous frame using the computed motion vectors. A difference image is computed by the adder 120 by subtracting the predicted image data from the current image frame. This difference image is transformed using the DCT circuit 125. Whereas the motion estimation circuit 110 and the motion compensation circuit 115 serve to reduce the temporal redundancy between image frames, the DCT circuit 125 serves to reduce the spatial redundancy within a frame. The DCT coefficients are subsequently are subject to reduced precision by the quantizer 140. The quantizer 140 increases compression while introducing numerical loss. The quantized DCT coefficients are then encoded by the VLC encoder 135 and transmitted in a compressed video bitstream along with the motion vectors. The local reconstruction loop is comprised of the inverse quantizer 140, the IDCT 145, and the adder 150. The inverse quantizer 140 reconstructs the DCT coefficients. The IDCT 145 transforms the DCT coefficients back into the spatial domain to form a quantized difference image. The reconstructed frame is computed by the adder 150 by adding the motion compensated data to the quantized difference image. This reconstructed data is then stored in the previous frame circuit 15 5 for use in processing subsequent image frames.
The operation of the fast predictive motion search motion estimation circuit 110 can consist of two stages. In the first stage, a small search can be done around several motion vector predictors. These motion vector predictors (MVP) can be obtained from other motion vectors (MV). For initial definitions, an MV is the difference in co-ordinates of a block of data in the current frame of video data and the block of data in the reference frame to which it is matched. An MV has two components: X and Y. The value of an MV is described as an ordered pair (X, Y). MVPs are MVs that are used as a good "guess" of the best MV when performing a match. A macroblock (MB) is a 16xl6 block of data withinavideo frame. AMB can also refer to a blocks of data of different sizes as well (e.g. 8x8, 4x8,4x4,16x8 etc.) without loss of generality.
One motion vector predictor can be based on a zero motion vector. A motion vector predictor being based on a particular motion vector can define the motion vector predictor as equal to the particular motion vector. The zero motion vector
WO 2004/014060 PCT/US2003/023204
6
being a motion vector with the coordinates of (0,0). A second motion vector predictor can be based on a motion vector of the co-located macroblock in the previous frame.
Fig. 2 is an exemplary illustration of the location of a current macroblock and neighboring macroblocks used to determine additional motion vectors. Thus, a third motion vector predictor can be based on the motion vector of the macroblock to the left of the current macroblock. A fourth motion vector predictor can be based on the motion vector of the macroblock to the top of or above the current macroblock. A fifth motion vector predictor can be based on the motion vector of the macroblock above and to the right of the current macroblock. A sixth motion vector predictor can be based on the median motion vector of the third, fourth, and fifth motion vector predictors. This median motion vector predictor can be computed independently for the X and Y components of the motion vector.
A seventh motion vector predictor can be based on an estimated global motion vector. This global motion vector is estimated by the motion estimation circuit 110 as the average of all final motion vectors of the previous frame for which a difference metric was below a certain threshold THRESH1. The difference metric can be a sum of absolute difference metric, a sum of squares difference metric, a modified sum of absolute difference metric, or any other useful metric. In the preferred embodiment, the value of THRESH1 chosen is:
THRESH1 = SAD1 + OFFSET, Where OFFSET may nominally be set to 500 Where SAD1 is given by the equation:

Here m and n are indexes of the pixel. M and N are the dimensions of the block. For an example macroblock, M= N= 16. The global motion vector may also be determined by other means such as motion sensors on video cameras, other algorithms, or any other means for determining a global motion vector.
Further motion vector predictors can be determined based on the result of motion estimation done for the same macroblock, but on a different previously coded frame.
WO 2004/014060 PCT/US2003/023204
7
Thus, the motion estimation circuit 110 can determine the global motion vector by using an average of all final motion vectors in a previous frame for which a difference metric is below a specified threshold, hi particular, the motion estimation circuit 110 can determine the global motion vector by calculating a difference metric for each of final motion vectors in a previous frame, comparing the difference metric for each of the final motion vectors in the previous frame with a predetermined threshold, and determining the global motion vector based on the each of the final motion vectors in a previous frame with a difference metric that is below the threshold.
All MVs within a small region around each MVP can be searched. Then, the MV with the lowest MSAD metric can be chosen as the candidate MV for the second stage. The MSAD metric is defined below.
Thus, the motion estimation circuit 110 can perform a predictive motion search by obtaining a plurality of motion vector predictors, the motion vector predictors representing approximations of possible motion vectors for a current macroblock, defining a search pattern, searching around each motion vector predictor of the plurality of motion vector predictors using the search pattern, and determining a final motion vector. The motion estimation circuit can further calculate a difference metric representing a quality of a macroblock match, where the difference metric can be a sum of absolute differences metric, a sum of squares of differences metric, or any other metric useful in motion estimation.
An example search pattern around each MVP is shown in Fig. 3. As shown, the search pattern can extend more in the horizontal direction than in the vertical direction. This can take advantage of the fact that in most real life video data, there is more motion and variations in motion hi the horizontal direction.
If, after evaluating the first 6 motion vectors, the best MV has a MSAD metric higher than a threshold THRESH2, the first stage can go into capture mode. In the preferred embodiment, THRESH2 is given by:
THKESH2 = 4 *MMSADAVG,
MMSADA VG = Average of all MMSADS (i. e. MSADS of best MVs) of the previous frame.
In the capture mode, additional MVPs can be considered such as those depicted in Fig. 4. For example, the 8 points can be:
WO 2004/014060 PCT/US2003/023204
8
(-12,0) (12,0) (0, -8) (0, 8) (-6, 4) (6,4) (6, -4) (-6, -4)
A search around each of the MVPs is performed using the same search pattern depicted in Fig. 3. In the preferred embodiment, only 4 out of the 8 MVPs can be considered for a macroblock. For the first macroblock, the first 4 are considered. For the next macroblock the other 4 MVPs are considered and so on. This can be done to reduce the number of computations.
The aim of the capture mode is to detect any new object that moves rapidly into the screen. In such a scenario, the MVPs based on neighborhood motion vectors would fail. Using the 8 new points improves the chance of getting a good motion vector match. The 8 points can be chosen to favor the horizontal direction since there often is more motion in this direction.
Thus, the motion estimation circuit 110 can search around each motion vector predictor of the plurality of motion vector predictors using the search pattern, determine a best motion vector having a difference metric higher than a predetermined threshold, and perform a search pattern around a new set of motion vector predictors.
In the first stage, when the search pattern around a MVP is being evaluated, an early exit criterion can be employed to terminate the search for that MVP. The search can be terminated if the MS AD obtained for the MV is higher than the current minimum MSAD (MMSAD) by a threshold THRESH3, i.e.,(if{MSAD, > (MMSAD + THRESH3)). Where MSADi is the MSAD obtained for MVPi, MMSAD is the minimum of all the MSAD values obtained until this point for the current MB. In particular, it is the MSAD of the best MV. In the preferred embodiment, the value of THRESHS can be chosen to be around 768.
Thus, the motion estimation circuit 110 can perform a search pattern on the motion vector predictors, determine a current difference metric for a current motion vector, compare the current difference metric to a previous minimum difference metric, set a new minimum difference metric if the current difference metric is below the previous minimum difference metric, and terminate the search pattern if the difference metric exceeds the previous minimum metric by a predetermined amount.
Then, among all the MVs searched in the first stage, the MV that gives the lowest MSAD metric is chosen and this becomes a starting point for the second stage.
WO 2004/014060 PCT/US2003/023204
9
In the second stage, 1he best MV from the first stage (i.e. the one giving the lowest MSAD) is chosen and a search is performed around this MV. For example, the search can be performed in a pattern as depicted in Fig. 5. The search pattern can start from the center and can spiral out in a sequence as shown in Fig. 5 as a sequence of numbers. As soon as a better MV is found (i.e. MV which gives a lower MSAD), the search pattern is re-centered around the new MV and the spiral search pattern starts over. This process continues until one of 3 conditions are met:
CONDITION 1: The MSAD is below a threshold THRESH4, given by: THRESH4 = A *Q + B
Where Q is the quantization step size used by the encoder for the current MB, A and B are constants. In the preferred embodiment, A = S and B = 0.
CONDITION 2: The maximum number of candidates, N, have already been considered in stage 2. In the preferred embodiment, N = 30.
CONDITION 3: These is no improvement in the minimum MSAD (MMSAD) during the last M candidate MVs. Here M is a function of the index of the position of the last MV candidate in the spiral search pattern. For example, the search starts from index 0. It then spirals around points 1, 2, 3..... Whenever a better MV is found, the spiral search pattern gets re-centered around this new MV and the index starts from 0 once again. This index is used to determine the value of M. hi the preferred embodiment, M is chosen from the set of values {4, 4, 4,4,4,4,4,4, 4, 5, 5, 5,5,6,6, 6, 6,7,7,7,7,7,7, 8, 8, 8, 8, 8, 9, 9} based on the index.
The best MV at the end of the second stage is chosen as the best MV for the macroblock. This MV can be further refined for half-pixel, quarter-pixel or higher accuracy in a subsequent stage using well known techniques.
As mentioned above, the search pattern can be chosen to give wider coverage to the horizontal direction than the vertical direction.
WO 2004/014060 PCT/US2003/023204
10
The MS AD metric can be a useful part of the invention. While the modified sum of differences metric gives preferred results, any difference metric can be interchangeably used in every embodiment of the present invention requiring a sum of absolute differences metric, a modified sum of differences metric, or any other difference metric. Furthermore, the MSAD metric is particularly useful in improving the performance of all video encoder systems. In particular, the MSAD metric can replace a SAD metric, a sum of squares metric, or any other metric in a video encoder system for improved performance. For example, the MSAD metric can be used in a FSME system, a PMVFAST system, or any other video encoder system.
The MSAD metric is a function of the sum of absolute differences (SAD) described above, the candidate MV being evaluated, and the predictor motion vector (PMV). The PMV is generally used by the video encoder during the encoding of the final motion vector. The final motion vector is encoded as a difference with respect to PMV, which is different from a MVP. For example, it can be a unique MV defined within H.261, H.263, MPEG-1, MPEG-2 and MPEG-4 standards for the purpose of encoding motion vectors. The SAD is the metric used hi classical motion estimation algorithms as described above.
For a macro block with a given PMV and for a candidate motion vector MV, MSAD is given by
MSAD = SAD + Bias
Where the bias is any value that is based on a motion vector difference metric between MV and PMV. For example,
MSAD = SAD + C*(\MVx-PMVx\ + \MVr-PMV¥\)
According to another example the bias can be based on,
C * ((MVx - PMVx)2 + (MVy - PMVy)2)
Where SAD is the classical metric used for the matching blocks defined earlier, MVX and MVy are the X and Y components of the candidate motion vector, PMVX arid PMVy are the X and Y components of PMV, and C is a constant. In the preferred embodiment, C is approximately 5. The PMV generally stays fixed for all the candidates in an MB, while the MV changes.
The MSAD metric is independent of the motion estimation algorithm and can be used to advantage in practically all algorithms. The benefit of the new metric is the
WO 2004/014060 PCT/US2003/023204
11
reduced number of bits needed to encode motion vectors by biasing the algorithm towards PMV thus improving the overall compression efficiency.
The MSAD for the zero motion vector, MV = (0, 0), is treated as a special case. The zero MV could potentially lead to improved compression efficiency. But this can happen only if the resultant macroblock is coded in the "not coded" mode within H.261, H.263, MPEG-1, MPEG-2 and MPEG-4 standards. This can be taken into account by biasing the SAD in the case where it is below a certain threshold:
If (SAD MSAD = SAD - THRESH6
Else
MSAD = SAD + C*(\PMVX\ + \PMVr\)
Endif
C, PMVX and PMVy are as described earlier.
THRESH5 = D*Q + E
THRESH6=F
Where Q is the quanization step size. D, E and F are constants. In a preferred embodiment D is approximately 128, E-Q, and F is approximately 100.
Thus, Hie motion estimation circuit 110 can calculate a difference metric, calculate a bias based on a predictor motion vector and a candidate motion vector, and determine a modified difference metric based on the difference metric and the bias.
Additionally, the motion estimation circuit 110 can calculate a difference metric, calculate a bias based on a predictor motion vector and a candidate motion vector, and determine a modified difference metric based on the difference metric and the bias. The motion estimation circuit 110 can determine a modified difference metric based on the difference metric and the bias by adding the difference metric to the bias. The motion estimation circuit 110 can also calculate the bias based on a predictor motion vector and a candidate motion vector further by determining a motion vector difference metric between the predictor motion vector and the candidate motion vector, and calculating the bias based on the motion vector difference metric between the predictor motion vector and the candidate motion vector. The motion estimation circuit 110 can additionally calculate the bias based on
WO 2004/014060 PCT/US2003/023204
12
a predictor motion vector and a candidate motion vector by multiplying the absolute value of difference between the predictor motion vector and the candidate motion vector by a constant. For example, the constant can be equal to about five. The motion estimation circuit 110 can furthermore calculate a bias based on a predictor motion vector and a candidate motion vector further by adding an absolute value of the difference between horizontal coordinates of the predictor motion vector and the candidate motion vector to an absolute value of the difference between vertical coordinates of the predictor motion vector and the candidate motion vector. The candidate motion vector can be one of a plurality of candidate motion vectors being evaluated for a macroblock and the predictor motion vector can stay fixed for each candidate motion vector in a macroblock. The difference metric can be a sum of absolute differences metric. The difference metric can also be a sum of squares of differences metric. The motion estimation circuit 110 can also define a final motion vector based on the candidate motion vector and output the final motion vector.
According to another related embodiment the present invention provides a method for determining the quality of a block match for a candidate motion vector in a video encoder system using motion vectors representing the difference in coordinates of a macroblock of data in a current frame of video data and coordinates of a related macroblock of data in a reference frame of video data. In this embodiment, the motion estimation circuit 110 can define a search pattern, search a region based on the search pattern for a candidate motion vector for evaluation, calculate a difference metric, calculate a bias based on the motion vector difference metric between a predictor motion vector and a candidate motion vector, determine a modified difference metric by adding the difference metric to the bias, and define a final motion vector based on the modified difference metric. The final motion vector can be defined for use in a second stage of the video encoder system. The difference metric can be at least one of a sum of absolute differences metric and a sum of squares of differences metric. The motion vector difference metric can be at least one of sum of absolute differences metric and a sum of squares of differences metric. The motion, estimation circuit 110 can search the region by searching around a plurality of motion vector predictors using the search pattern. The motion estimation circuit 110 can define the final motion vector by defining a final motion vector having a modified difference metric higher than a predetermined threshold, performing a second search
WO 2004/014060 PCT/US2003/023204
13
pattern around a new plurality of motion vector predictors based on the final motion vector, and determining a new final motion vector based on the results of the step of performing a second search pattern. The motion estimation circuit 110 can defining the search pattern by defining a search pattern that is more extensive in a horizontal direction than in a vertical direction. The motion estimation circuit 110 can then output a motion vector based on the final motion vector.
During the search process, it can be likely that search regions of different MVPs may overlap leading to repeated candidate motion vectors. A log can be maintained of all the candidates evaluated already and they are ignored if they have been considered already.
The search sequences depicted are the ones used in the preferred embodiment They have been optimized to get a good match in the quickest possible time over a wide range of video sequences. It is possible to use alternative search patterns as well.
The disclosed invention does not make any assumptions on the motion vector range. Any restriction on the motion vector values can be applied on the candidates and, if they are beyond the allowed range, they can be discarded.
In the second stage of the preferred embodiment, the spiral search pattern can be re-centered on obtaining a new best matched candidate MV. Thus, the next point that needs to be evaluated may not be known apriori. The next candidate to be evaluated potentially depends on the result of evaluating the current candidate. Hence it may becomes difficult to implement several candidate MSAD calculations in parallel (which some hardware architectures may want to do). To alleviate this, the re-centering of the search pattern can be done after evaluating a set of candidates, allowing the set to be processed in parallel.
Fig. 6 is an exemplary flowchart 600 outlining the operation of the motion estimation circuit 110 according to one embodiment. In step 610, the flowchart begins. In step 620, the motion estimation circuit 110 determines a predictor motion vector PMV. In step 630, the motion estimation circuit 110 determines a candidate motion vector MV. In step 640, the motion estimation circuit calculates an absolute value of the difference between horizontal components of the PMV and the candidate MV. In step 650, the motion estimation circuit 110 calculates an absolute value of the difference between vertical components of the PMV and the candidate MV. In step 660, the motion estimation circuit 110 calculates the bias by multiplying the
WO 2004/014060 PCT/US2003/023204
14
difference between the components of the PMV and the candidate MV by a constant. In step 670, the motion estimation circuit 110 calculates the MSAD by adding the bias to a difference metric. In step 680, the flowchart ends.
Fig. 7 is an exemplary block diagram of a fast predictive motion search motion estimation circuit 110 according to one embodiment The motion estimation circuit 110 can include a difference metric calculator 710, a bias calculator 720, a MSAD calculator 730, and a motion vector determination circuit 740. The circuits operate in accordance with their like functions described with respect to the flowchart 600.
According to another related embodiment, a fast predictive motion search method can be performed by two stages. In the first stage, the 7 MVP candidates can be computed as described above. Then, for each MVP, all MV candidates can be evaluated according to the search pattern in Fig. 3 and the exit criteria can be employed to break out of the MVP or go into the capture mode. Next, if in the capture mode, the search can be performed at and around the MVP depicted in Fig. 4 using the same search pattern in Fig. 3 and the same exit criteria. Then, in the second stage, the best MV from the first stage can be chosen and a search can be performed in a spiral fashion depicted in Fig. 5. The spiral can be re-centered and reset the index can be reset to zero whenever a better match is found. Finally, the process can be continued until one of the three exit criteria are found.
The disclosed invention can achieve a high degree of compression efficiency while keeping the complexity low. The complexity can be similar to the complexity of APDZSand PMVFAST. However, the achieved quality is higher. When compared with the standard lull search algorithm, which is the accepted reference in the industry, the present invention achieves about 0.6% better compression efficiency for a fixed video quality. This number was obtained after averaging over 24 different QCIF video sequences.
One application for this invention is in real time video encoders on hand held devices. The typical bandwidth of such encoded video is in the range 32 kbps to 512 kbps and the typical video frame size is QCIF and CIF.
The method of this invention is preferably implemented on a programmed processor. However, the video compression system 100, the motion estimation circuitry 110, and other elements may also be implemented on a general purpose or
WO 2004/014060 PCT/US2003/023204
15
special purpose computer, a programmed microprocessor or microcontroller and peripheral integrated circuit elements, an ASIC or other integrated circuit, a hardware electronic or logic circuit such as a discrete element circuit, a programmable logic device such as a PLD, PLA, FPGA or PAL, or the like. In general, any device on which resides a finite state machine capable of implementing the flowcharts shown in the Figures and the methods described may be used to implement the processor functions of this invention.
While this invention has been described with specific embodiments thereof, it is evident that many alternatives, modifications, and variations will be apparent to those skilled in the art. For example, various components of the embodiments may be interchanged, added, or substituted in the other embodiments. Accordingly, the preferred embodiments of the invention as set forth herein are intended to be illustrative, not limiting. Various changes may be made without departing from the spirit and scope of the invention.
WO 2004/014060 PCT/US2003/023204
16 CLAIMS
1. A method for determining the quality of a block match for a candidate
motion vector in a video encoder system comprising:
calculating a difference metric; calculating a bias based on
a predictor motion vector and
a candidate motion vector; and determining a modified difference metric based on
the difference metric and
the bias,
2. The method according to claim 1, wherein the step of determining a
modified difference metric based on the difference metric and the bias comprises
adding the difference metric to the bias,
3. The method according to claim 1, wherein the step of calculating a bias
based on a predictor motion vector and a candidate motion vector further comprises
determining a motion vector difference metric between
the predictor motion vector and
the candidate motion vector, and
calculating the bias based on the motion vector difference metric between the predictor motion vector and the candidate motion vector.
4. The method according to claim 3, wherein the step of calculating a bias
based on a predictor motion vector and a candidate motion vector further comprises
multiplying the motion vector difference metric between
the predictor motion vector and
the candidate motion vector by a constant.
5. The method according to claim 4, wherein the constant is equal to
about five.
WO 2004/014060 PCT/US2003/023204
17
6. The method according to claim 1, wherein the step of calculating a bias
based on a predictor motion vector and a candidate motion vector further comprises
adding
an absolute value of the difference between horizontal coordinates of the predictor motion vector and the candidate motion vector to
an absolute value of the difference between vertical coordinates of the predictor motion vector and the candidate motion vector.
7. The method according to claim 1, wherein the step of calculating a bias
based on a predictor motion vector and a candidate motion vector further comprises
adding
a square of the difference between horizontal coordinates of the predictor motion vector and the candidate motion vector to
a square of the difference between vertical coordinates of the predictor motion vector and the candidate motion vector.
8. The method according to claim 1,
wherein the candidate motion vector is one of a plurality of candidate motion vectors being evaluated for a macroblock, and
wherein the predictor motion vector stays fixed for each candidate motion vector in a macroblock.
9. The method according to claim 1, wherein the difference metric is a
sum of absolute differences metric.
10. The method according to claim 1, wherein the difference metric is a
sum of squares of differences metric.
11. The method according to claim 1, further comprising:
defining a final motion vector based on the candidate motion vector; and
WO 2004/014060 PCTAJS2003/023204
18
outputting the final motion vector.
12. A method for determining the quality of a block match for a candidate
motion vector in a video encoder system using motion vectors representing the
difference in coordinates of a macroblock of data in a current frame of video data and
coordinates of a related macroblock of data in a reference frame of video data
comprising:
defining a search pattern;
searching a region based on the search pattern for a candidate motion vector for evaluation;
calculating a difference metric;
calculating a bias based on the difference metric between a predictor motion vector and a candidate motion vector;
determining a modified difference metric by adding the difference metric to the bias; and
defining a final motion vector based on the modified difference metric.
13. The method according to claim 12, wherein the final motion vector is
defined for use in a second stage of the video encoder system.
14. The method according to claim 12, wherein the difference metric is at
least one of a sum of absolute differences metric and a sum of squares of differences
metric.
15. The method according to claim 12,
wherein the step of searching a region further comprises:
searching around a plurality of motion vector predictors using the search pattern, and
wherein the step of defining a final motion vector further comprises defining a final motion vector having a modified difference metric higher than a predetermined threshold,
performing a second search pattern around a new plurality of motion vector predictors based on the final motion vector, and
WO 2004/014060 PCT/US2003/023204
19
determining a new final motion vector based on the results of the step of performing a second search pattern.
16. The method according to claim 12, wherein the step of defining a
search pattern farther comprises defining a search pattern that is more extensive in a
horizontal direction than in a vertical direction.
17. The method according to claim 12, further comprising outputting a
motion vector based on the final motion vector.
18. An apparatus for determining the quality of a block match for a
candidate motion vector in a video encoder system using motion vectors representing
the difference in coordinates of a macroblock of data in a current frame of video data
and coordinates of a related macroblock of data in a reference frame of video data
comprising:
a current image macroblock input;
a modified sum of absolute differences motion estimation circuit including
a difference metric calculator,
a bias calculator,
a modified sum of absolute differences calculator, and
a motion vector determination circuit; and a motion vector output.
19. The apparatus according to claim 18, wherein the difference metric
calculator is at least one of a sum of absolute differences calculator and a sum of
squares of differences calculator.
20. The apparatus according to claim 18, wherein the bias calculator
calculates a bias by deterrnining the motion vector difference metric between
a predictor motion vector and a candidate motion vector.
WO 2004/014060 PCT/US2003/023204
20
21. The apparatus according to claim 20, where the bias calculator further
calculates a bias by
multiplying the motion vector difference metric between
the predictor motion vector and
the candidate motion vector
by a constant.
22. The apparatus according to claim 20, where the bias calculator further
determines the motion vector difference metric between a predictor motion vector and
a candidate motion vector by
adding
an absolute value of the difference between horizontal
coordinates of the predictor motion vector and the candidate motion vector to
an absolute value of the difference between vertical coordinates of the predictor motion vector and the candidate motion vector.
23. The apparatus according to claim 22,
wherein the candidate motion vector is one of a plurality of candidate motion vectors being evaluated for a macroblock, and
wherein the predictor motion vector stays fixed for each candidate motion vector in the macroblock.
24. The apparatus according to claim 20, where the bias calculator further
determines the motion vector difference metric between a predictor motion vector and
a candidate motion vector by
adding
a square of the difference between horizontal coordinates of the predictor motion vector and the candidate motion vector
a square of the difference between vertical coordinates of the predictor motion vector and the candidate motion vector.
WO 2004/014060 PCT/US2003/023204
21
25. The apparatus according to claim 18, further comprising a motion
compensation circuit coupled to the modified sum of absolute differences motion
estimation circuit.
26. The apparatus according to claim 25, further comprising an adder
coupled to the current image macroblock input and coupled to the motion
compensation circuit.
27. The apparatus according to claim 26, further comprising:
a discrete cosine transform circuit coupled to the adder; and a quantizer coupled to the discrete cosine transform circuit.
28. The apparatus according to claim 27, further comprising:
an inverse quantizer coupled to the quantizer; and
an inverse discrete cosine transform circuit coupled to the inverse quantizer.
A method and apparatus for determining the quality of a block match for a candidate motion vector in a video encoder system using motion vectors representing the difference in coordinates of a macroblock of data in a current frame of video data and coordinates of a related macroblock of data in a reference frame of video data. The method can include defining a search pattern, searching a region based on the search pattern for a candidate motion vector for evaluation, calculating a difference metric, calculating a bias based on the difference between a predictor motion vector and a candidate motion vector, determining a modified difference metric by adding the difference metric to the bias, and defining a final motion vector based on the modified difference metric.

Documents:

00255-kolnp-2005-abstract.pdf

00255-kolnp-2005-assignment.pdf

00255-kolnp-2005-claims.pdf

00255-kolnp-2005-correspondence-1.1.pdf

00255-kolnp-2005-correspondence-1.2.pdf

00255-kolnp-2005-correspondence.pdf

00255-kolnp-2005-description(complete).pdf

00255-kolnp-2005-drawings.pdf

00255-kolnp-2005-form-1.pdf

00255-kolnp-2005-form-18.pdf

00255-kolnp-2005-form-3.1.pdf

00255-kolnp-2005-form-3.pdf

00255-kolnp-2005-form-5.pdf

00255-kolnp-2005-international publication.pdf

00255-kolnp-2005-others.pdf

00255-kolnp-2005-p.a.pdf

00255-kolnp-2005-pct others.pdf

00255-kolnp-2005-priority document.pdf

255-KOLNP-2005-(11-04-2012)-ASSIGNMENT.pdf

255-KOLNP-2005-(11-04-2012)-CORRESPONDENCE.pdf

255-KOLNP-2005-(11-04-2012)-FORM-16.pdf

255-KOLNP-2005-(11-04-2012)-PA-CERTIFIED COPIES.pdf

255-KOLNP-2005-CORRESPONDENCE-1.3.pdf

255-KOLNP-2005-CORRESPONDENCE-1.4.pdf

255-KOLNP-2005-FORM-27.pdf

255-kolnp-2005-granted-abstract.pdf

255-kolnp-2005-granted-claims.pdf

255-kolnp-2005-granted-correspondence.pdf

255-kolnp-2005-granted-description (complete).pdf

255-kolnp-2005-granted-drawings.pdf

255-kolnp-2005-granted-examination report.pdf

255-kolnp-2005-granted-form 1.pdf

255-kolnp-2005-granted-form 18.pdf

255-kolnp-2005-granted-form 3.pdf

255-kolnp-2005-granted-form 5.pdf

255-kolnp-2005-granted-letter patent.pdf

255-kolnp-2005-granted-pa.pdf

255-kolnp-2005-granted-reply to examination report.pdf

255-kolnp-2005-granted-specification.pdf

255-KOLNP-2005-PA-1.1.pdf

255-KOLNP-2005-PA.pdf

« Previous Patent

Next Patent »

Patent Number

222156

Indian Patent Application Number

255/KOLNP/2005

PG Journal Number

30/2008

Publication Date

25-Jul-2008

Grant Date

23-Jul-2008

Date of Filing

23-Feb-2005

Name of Patentee

MOTOROLA, INC.

Applicant Address

1303 EAST ALGONQUIN ROAD, SCHAUMBURG, IL 60196

Inventors:

#	Inventor's Name	Inventor's Address
1	SUBRAMANIAN, RAGHAVAN	1919 PRAIRIE SQUARE #216, SCHAUMBURG IL 61073
2	GANDHI, BHAVAN	62 EAST DEPOT STREET, VERMON HILLS IL 60061

PCT International Classification Number

H04N

PCT International Application Number

PCT/US2003/023204

PCT International Filing date

2003-07-25

PCT Conventions:

#	PCT Application Number	Date of Convention	Priority Country
1	10/213,652	2002-08-06	U.S.A.