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

Claim 3

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.

Claim 4

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.

Claim 5

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.

Claim 8

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.

Claim 9

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.

Claim 10

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.

Claim 13

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.

Claim 14

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.

Claim 15

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.

Claim 16

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.

Claim 17

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.

Claim 18

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.