Method and apparatus for determining a motion vector

• US 5,682,438 A
• Filed: 06/21/1995
• Issued: 10/28/1997
• Est. Priority Date: 06/21/1994
• Status: Expired due to Fees

• Current Assignee: Nippon Steel Corporation
• Original Assignee: Nippon Steel Corporation
• Inventors: Kojima, Kazuhito, Mizusawa, Hideyuki
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): Bella, Matthew C
• Application Number:
  US08/492,995
• Time in Patent Office: 860 Days
• Field of Search: 382/232, 382/236, 382/238, 382/251, 382/252, 382/253, 382/240, 382/246, 382/282, 382/239, 382/243, 348/699, 348/700, 348/404, 348/416, 348/407, 348/413, 348/406, 348/408, 348/409, 348/405, 348/431, 348/451, 348/452, 348/674, 342/25
• US Class Current: 382/107
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/223 using block-matching
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 5/145 Movement estimation for video coding H04N19/51

Abstract

In order to detect a motion vector representing a movement of an objective area in a first image of a plurality of successive images, first, a plurality of comparison areas are determined in a second image before or after the first image. Subsequently, a difference total sum between the objective area and each of the comparison areas is obtained with respect to the plurality of comparison areas, thereby obtaining a distribution of the difference total sums. The resultant distribution of the difference total sums is approximately expressed in the form of a predetermined polynomial. By using this polynomial, the position is obtained where the difference total sums become minimum. By treating the resultant position of the area as the position before or after the movement of the objective area, the motion vector representing the movement of the objective area is detected.

Claims

1. An image motion vector detection method of detecting a motion vector representing movement of an objective area in a first image of a plurality of successive images, said method comprising:

an objective area determining step of determining the objective area in the first image;

a polynomial determining step of determining both a degree and the number of terms of a polynomial, said polynomial including a variable corresponding to predetermined coordinates within said first image, the polynomial approximately expressing a distribution of the sum of the differences between comparison areas determined in a second image and the objective area of said first image;

a comparison area determining step of determining both the number and positions in the second image of the comparison areas, which are sufficient for determining coefficients for the terms in the polynomial;

a total sum of the differences calculating step for obtaining a value of the n-th power of a total sum of the differences of the objective area and the comparison area with respect to the plurality of comparison areas by using a predetermined power n;

a coefficient calculating step for calculating the coefficients of the polynomial by using the values of the n-th power of the total sums; and

a minimum value calculating step of obtaining coordinates, in which a minimum value is obtained in the polynomial having the calculated coefficients, as coordinates of an area in the second image representing movement of the objective area.

2. An image motion vector detection method according to claim 1, wherein the polynomial is a quadratic polynomial, the number of comparison areas is equal to or more than 5, and the power n is an integral number in the range of 1 to 8.

3. An image motion vector detection method according to claim 1, wherein the objective area is a macro block compressed according to a digital motion picture compression format.

4. An image motion vector detection apparatus for detecting a motion vector representing movement of an objective area in a first image of a plurality of successive images, said apparatus comprising:

objective area determining means for determining the objective area in the first image;

polynomial determining means for determining both a degree and the number of terms of a polynomial representing an approximate curved surface approximately expressing a distribution of the total sum of the differences between comparison areas, which are determined in a second image before or after the first image, and the objective area;

total sum of the differences calculating means for determining both the number and positions in the second image of comparison areas, which are sufficient for determining coefficients of the terms of the polynomial, and for obtaining a value of the n-th power of the total sum of the differences between the objective area and the comparison area using a predetermined power n, with respect to the plurality of comparison areas which have been determined in number and positions; and

minimum value calculating means for calculating the coefficients of the polynomial using the obtained values of the n-th power of the total sum of the differences, and for obtaining coordinates, in which a minimum value is obtained in the polynomial having the calculated coefficients, as coordinates of an area in the second image before or after the movement of the objective area.

5. An image motion vector detection apparatus according to claim 4, wherein the polynomial is a quadratic polynomial, the number of comparison areas is equal to or more than 5, and the power n is an integral number in the range of 1 to 8.

6. An image vector detection apparatus for detecting a motion vector representing movement of an objective area in a first image of a plurality of successive images, each of the plurality of the successive images including a plurality of separate areas which are obtained by division along first and second reference axes intersecting each other, said apparatus comprising:

a first total sum of the differences calculating means for selecting arbitrary number of first separate areas, which are present on the first reference axis, of the plurality of separate areas in a second image before or after the first image, and for calculating a first total sum of the differences between each of the first separate areas and the objective separate area;

a first polynomial determining means for substituting respectively the first total sum of the differences into a predetermined first polynomial including a variable corresponding to the first reference axis and a plurality of unknown first coefficients, to obtain the first coefficients to specify the first polynomial;

a first extreme value calculating means for obtaining a first extreme value of the specified first polynomial, and for detecting a first motion vector representing the movement of the separate objective area along the first reference axis on the basis of the obtained first extreme value when said first extreme value is below a predetermined first value, and when said first extreme value is above said first predetermined value, substituting a third reference axis parallel to the first reference axis;

a second total sum of the differences calculating means for selecting an arbitrary number of second separate areas, which are present on the second axis, of the plurality of separate areas in the second image, and for calculating a second total sum of the differences between each of the second separate areas and the objective separate area, with respect to the arbitrary number of second separate areas;

a second polynomial detecting means for substituting respectively the second total sum of the differences into a predetermined second polynomial including a variable corresponding to the second reference axis and a plurality of unknown second coefficients, thereby obtaining the plurality of second coefficients to specify a second polynomial; and

a second extreme value calculating means for obtaining a second extreme value of the specified second polynomial, and for detecting a second motion vector representing the movement of the separate objective area along the second reference axis on the basis of the second extreme value when said second extreme value is below a predetermined second value, and when said second extreme value is above said second predetermined value, substituting a third reference axis parallel to the second reference axis.

7. An image motion vector detection apparatus according to claim 6, wherein the first and second reference axes are coordinate axes intersecting each other.

8. An image motion vector detection apparatus according to claim 6, wherein the objective area is a macro block from motion picture compression according to a digital motion picture compression format.