Method and apparatus for detecting motion vectors based on hierarchical motion estimation

• US 5,926,231 A
• Filed: 12/09/1996
• Issued: 07/20/1999
• Est. Priority Date: 08/10/1995
• Status: Expired due to Term

• Current Assignee: Wi-LAN Inc.
• Original Assignee: Daewoo Electronics Company Limited (Dayou Holdings Co.,Ltd.)
• Inventors: Jung, Hae-Mook
• Primary Examiner(s): Le, Vu
• Application Number:
  US08/764,121
• Time in Patent Office: 953 Days
• Field of Search: 348/699, 348/416, 348/413, 348/407, 348/408, 348/402
• US Class Current: 348/699
• CPC Class Codes: H04N 19/53 Multi-resolution motion estimation; Hierarchical motion estimation

Abstract

Motion vectors are determined between a current frame and a preceding frame within a frame duration by employing a time-sharing multi-tier hierarchical motion estimation approach, wherein the candidate blocks being grouped into a multiple number of hierarchical search areas. The motion vector determination scheme is initiated by performing a motion estimation of a highest hierarchy for all of the search blocks; and an error function and a motion vector of the highest hierarchy are stored. Subsequently, motion-estimation of a lower hierarchy is performed for each of the selected search blocks which have the error functions greater than the threshold value of the highest hierarchy. In the next step, the error functions of the highest and the lower hierarchies are compared for each of the selected search blocks and a smaller error function is selected therefrom to thereby update each of the stored potential motion vectors with the motion vector corresponding to the selected error function. The updating process is repeated for the next hierarchies and the stored potential motion vectors are provided as the motion vectors of the current frame when updating process for the stored potential motion vector for a predetermined lowest hierarchy is accomplished or the frame duration is exhausted.

Claims

1. A method for encoding a video signal having a current frame and a preceding frame based on motion vectors between the current and the preceding frames estimated within a frame duration, wherein the current frame is divided into a plurality of search blocks of an identical size and the preceding frame is divided into a corresponding number of search regions, each search region being further divided into a multiplicity of candidate blocks of said identical size, which comprises the steps of:

(a) grouping the candidate blocks for each search region into a multiple number of search areas of different hierarchies from a highest hierarchy to a lowest hierarchy, each hierarchy having a different threshold value, wherein the search area of the highest hierarchy includes a smaller number of candidate blocks than that of the lowest hierarchy;

(b) motion-estimating each of the search blocks corresponding to each search area starting from the highest hierarchy to the lowest hierarchy to provide a estimated motion vector for each of the search blocks, wherein the motion vector represents the displacement between each of the search blocks and a candidate block which yields a minimum error function smaller than a threshold value of a hierarchy containing the candidate block; and

(c) providing the estimated motion vectors obtained from the step (b) as the motion vectors of the current frame.

2. The method as recited in claim 1, wherein the step (b) includes the steps of:

(b1) motion-estimating each of the search blocks in the current frame corresponding to each search area of the highest hierarchy having a threshold value to provide a potential motion vector and a minimum error function for each of the search blocks, said potential motion vector representing the displacement between each of the search blocks and a candidate block which yields said minimum error function;

(b2) storing the minimum error function and the potential motion vector for each of the search blocks;

(b3) comparing the minimum error function for each of the search blocks with the threshold value of the highest hierarchy to thereby select search blocks having minimum error functions greater than the threshold value of the highest hierarchy as the selected search blocks;

(b4) motion-estimating each of the selected search blocks corresponding to each search area of a lower hierarchy having a threshold value to provide a potential motion vector and a minimum error function of the lower hierarchy for each of the selected search blocks, said potential motion vector of the lower hierarchy representing the displacement between each of the selected search blocks and a candidate block which yields said minimum error function of the lower hierarchy;

(b5) selecting, for each of the selected search blocks, a minimum error function having a smaller value between the stored minimum error function corresponding to said each of the selected search blocks and the minimum error function of the lower hierarchy and generating a selection signal representing the selected minimum error functions for the selected search blocks;

(b6) updating the stored minimum error functions for the selected search blocks with the selected minimum error functions;

(b7) selecting, in response to the selection signal, the potential motion vectors corresponding to the selected minimum error functions as the selected potential motion vectors for the selected search blocks;

(b8) updating the stored potential motion vectors for the selected search blocks with the selected potential motion vectors;

(b9) comparing the selected minimum error function for each of the selected search blocks with the threshold value of the lower hierarchy to thereby select search blocks having selected minimum error functions greater than the threshold value of the lower hierarchy as the selected search blocks for a next lower hierarchy;

(b10) subjecting to the steps (b4) to (b9) the search blocks selected in the step (b9) until said updating process in the step (b8) above has been accomplished with respect to the stored potential motion vectors for the lowest hierarchy or the frame duration has been exhausted; and

(b11) providing the stored potential motion vectors as the estimated motion vectors of the current frame.

3. The method as recited in claim 2, wherein the search area of the highest hierarchy includes one candidate block and each of the remaining search areas has an identical number of candidate blocks.

4. The method as recited in claim 3, wherein the threshold value of the highest hierarchy is of a predetermined value and a threshold value of a lower hierarchy is determined based on the number of search blocks having error functions smaller than or equal to a threshold value of a higher hierarchy preceding to the lower hierarchy.

5. An apparatus for estimating motion vectors between a current frame and a preceding frame within a frame duration, wherein the current frame is divided into a plurality of search blocks of an identical size and the preceding frame is divided into a corresponding number of search regions, each search region being further divided into a multiplicity of candidate blocks of said identical size, which comprises:

means for grouping the candidate blocks for each search region into a multiple number of search areas of different hierarchies from a highest hierarchy to a lowest hierarchy, each hierarchy having a different threshold value, wherein the search area of the highest hierarchy includes a smaller number of candidate blocks than that of the lowest hierarchy;

estimation means for motion-estimating each of the search blocks corresponding to each search area starting from the highest hierarchy to the lowest hierarchy to provide a potential motion vector for each of the search blocks, wherein the motion vector represents the displacement between each of the search blocks and a candidate block which yields a minimum error function smaller than a threshold value of a hierarchy containing the candidate block; and

means for providing the potential motion vectors as the motion vectors of the current frame.

6. The apparatus as recited in claim 5, wherein the estimation means includes:

means for providing each of the search blocks and, in response to a first selection signal, for providing each of selected search blocks as each of target search blocks;

means for selecting the highest hierarchy having a threshold value and, in response to the first selection signal, for selecting a next lower hierarchy having a threshold value as a target hierarchy;

means for storing a minimum error function and a potential motion vector for each of the search blocks;

motion estimation means for motion-estimating each of the target search blocks corresponding to each search area of a target hierarchy to provide a potential motion vector and a minimum error function of the target hierarchy for each of the target search blocks, said potential motion vector of the target hierarchy representing the displacement between each of the selected search blocks and a candidate block which yields said minimum error function of the target hierarchy;

first selection means for selecting, for each of the target search blocks, a minimum error function having a smaller value between the stored minimum error function corresponding to each of the target search blocks and the minimum error function of the target hierarchy and generating a second selection signal representing the selected minimum error functions for the target search blocks;

first update means for updating the stored minimum error functions for target search blocks with the selected minimum error functions;

second selection means for selecting, in response to the second selection signal, the potential motion vectors corresponding to the selected minimum error functions as selected potential motion vectors for the target search blocks;

second update means for updating the stored potential motion vectors for the target search block with the selected potential motion vectors;

second comparison means for comparing the selected minimum error function for each of the target search blocks with the threshold value of the target hierarchy and for selecting search blocks having selected minimum error functions greater than the threshold value of the target hierarchy and generates the second selection signal representing the selected search blocks; and

means for providing the stored potential motion vectors as the estimated motion vectors of the current frame when said updating operations has been accomplished with respect to the stored potential motion vectors for the lowest hierarchy or the frame duration is exhausted.

7. The apparatus as recited in claim 6, wherein the search area of the highest hierarchy includes one candidate block and each of the remaining search areas has an identical number of candidate blocks.

8. The apparatus as recited in claim 7, wherein the threshold value of the highest hierarchy is of a predetermined value and a threshold value of a lower hierarchy is determined based on the number of search blocks having error functions smaller than or equal to a threshold value of a higher hierarchy preceding the lower hierarchy.

9. An apparatus for encoding a video signal having a current frame and a preceding frame based on motion vectors between the current and the preceding frames estimated within a frame duration, wherein the current frame is divided into a plurality of search blocks of an identical size and the preceding frame is divided into a corresponding number of search regions, each search region being further divided into a multiplicity of candidate blocks of said identical size, which comprises:

means for grouping the candidate blocks for each search region into a multiple number of search areas of different hierarchies from a highest hierarchy to a lowest hierarchy, each hierarchy having a different threshold value, wherein the search area of the highest hierarchy includes a smaller number of candidate blocks than that of the lowest hierarchy;

estimation means for motion-estimating each of the search blocks corresponding to each search area starting from the highest hierarchy to the lowest hierarchy to provide a potential motion vector for each of the search blocks, wherein the motion vector represents the displacement between each of the search blocks and a candidate block which yields a minimum error function smaller than a threshold value of a hierarchy containing the candidate block; and

means for providing the potential motion vectors as the motion vectors of the current frame.

10. The apparatus as recited in claim 9, wherein the estimation means includes:

means for providing each of the search blocks and, in response to a first selection signal, for providing each of selected search blocks as each of target search blocks;

means for selecting the highest hierarchy having a threshold value and, in response to the first selection signal, for selecting a next lower hierarchy having a threshold value as a target hierarchy;

means for storing a minimum error function and a potential motion vector for each of the search blocks;

motion estimation means for motion-estimating each of the target search blocks corresponding to each search area of a target hierarchy to provide a potential motion vector and a minimum error function of the target hierarchy for each of the target search blocks, said potential motion vector of the target hierarchy representing the displacement between each of the selected search blocks and a candidate block which yields said minimum error function of the target hierarchy;

first selection means for selecting, for each of the target search blocks, a minimum error function having a smaller value between the stored minimum error function corresponding to each of the target search blocks and the minimum error function of the target hierarchy and generating a second selection signal representing the selected minimum error functions for the target search blocks;

first update means for updating the stored minimum error functions for target search blocks with the selected minimum error functions;

second selection means for selecting, in response to the second selection signal, the potential motion vectors corresponding to the selected minimum error functions as selected potential motion vectors for the target search blocks;

second update means for updating the stored potential motion vectors for the target search block with the selected potential motion vectors;

second comparison means for comparing the selected minimum error function for each of the target search blocks with the threshold value of the target hierarchy and for selecting search blocks having selected minimum error functions greater than the threshold value of the target hierarchy and generates the second selection signal representing the selected search blocks; and

means for providing the stored potential motion vectors as the estimated motion vectors of the current frame when said updating operations has been accomplished with respect to the stored potential motion vectors for the lowest hierarchy or the frame duration is exhausted.

11. The apparatus as recited in claim 10, wherein the search area of the highest hierarchy includes one candidate block and each of the remaining search areas has an identical number of candidate blocks.

12. The apparatus as recited in claim 11, wherein the threshold value of the highest hierarchy is of a predetermined value and a threshold value of a lower hierarchy is determined based on the number of search blocks having error functions smaller than or equal to a threshold value of a higher hierarchy preceding to the lower hierarchy.

13. The apparatus as recited in claim 12, further comprising prediction means for generating a predicted current frame by using the motion vectors and the preceding frame.

14. The apparatus as recited in claim 13, further comprising transform coding means for converting a difference signal denoting a difference between the current and the predicted current frame into transform coefficient data, and quantization means for converting the transform coefficient data into quantized transform coefficient data.

15. The apparatus as recited in claim 14, further comprising statistical coding means for converting the quantized transform coefficient data and the motion vectors into statistically coded video signal.