JPH089378A - Image motion vector detection method and apparatus - Google Patents

Abstract

(57) [Abstract] [Purpose] To make it possible to greatly reduce the amount of calculation required to detect the amount of movement of a part of a moving image. [Structure] In step 1, an area to be a movement amount detection target is determined from a plurality of areas in an image, and in step 2, the degree and term of a polynomial of a curved surface that approximately expresses the distribution of the difference sum between the areas before and after the movement. Determine the number. Next, in step 3, a sufficient number of comparison areas for determining the coefficients of the polynomial, that is, the number and position of areas for which the sum of differences is calculated are determined, and in step 4, the n-th power of the sum of differences is calculated for each of the comparison areas. Ask. In step 5, the coefficient of the polynomial is calculated using the n-th power of the sum of the differences, and in step 6, the coordinate having the minimum value in the polynomial having the calculated coefficient is calculated as the coordinate of the moved area of the target area. By doing so, it is possible to reduce the number of difference summations to be calculated in order to obtain the area movement amount, and to significantly reduce the total calculation amount in order to obtain the motion vector of the image. To do.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an image motion vector detecting method and apparatus for detecting movement of a part of a moving image. Specifically, in a group of images that are temporally continuous, a certain area with an arbitrary shape and size on a certain image moves to which area of the previous (rear) image. It is suitable for use in detecting whether or not there is.

[0002]

2. Description of the Related Art Normally, an image is represented on a computer in the form of a two-dimensional set of pixels having color information. Then, in order to detect to which region in the image C, which is the previous (rear) time, of the certain region B in the certain image A, the following method has been conventionally used.

That is, in the previous (rear) image C, a plurality of regions Dxy (x = x1 .... xn, y = y1.x) having the same shape and size as the region B in the image A. ... ym) and the sum of the absolute values of the differences between the pixel values in the area B of the image A (hereinafter referred to as the sum of absolute difference), and the sum of the squares of the differences (hereinafter, The sum of squared differences and the sum of squared differences are simply referred to as sum of differences). Then, the region Dx0y0 (x1≤x0≤xn, y1≤y0≤ym) having the smallest total difference is regarded as the moving portion of the region B.

[0004]

However, when such a conventional method is used, for example, the moving destination in the image C of the area B whose range is 32 pixels in the horizontal direction and 32 pixels in the vertical direction is selected. To obtain, the size (xn−x1) × (ym−y1) of the area Dxy in the image C is 32 × 32 =
1024, and the sum of the differences between the area B and the area Dxy is 10
The destination area Dx0y0 of the area B could not be obtained without calculating 24 times.

Therefore, there has been a problem that the amount of calculation when obtaining the destination of the area B on the computer becomes very large. Therefore, in the past, in order to reduce such a calculation amount, a means for obtaining the sum of differences every other pixel was used, but it was not possible to obtain a sufficient effect.

The present invention has been made to solve such a problem, and significantly reduces the amount of calculation required to detect the movement amount of a partial area in a moving image. The purpose is to be able to.

[0007]

An image motion vector detecting method according to the present invention is a motion vector detecting method which indicates a moving amount of an area in a plurality of image groups having temporal continuity, wherein The distribution of the difference sum between the target area to be obtained and the comparison area is approximately represented by a predetermined polynomial, and the position where the difference sum is minimized using this polynomial is the area after the movement of the target area. I'm trying to ask.

Another feature of the present invention is that
In a method of detecting a motion vector indicating a movement amount of a certain region in a plurality of image groups having temporal continuity, a region determining step of determining a region to be a movement detection target from a certain image in the image group, A polynomial determination step that determines the degree and the number of terms of a polynomial that approximately expresses the distribution of the difference sum between the front and rear regions as a variable using the coordinates in the image after movement as a variable, and is sufficient to determine the coefficient of each term of the above polynomial. For each of the comparison areas determined in the comparison area determination step and the comparison area determination step for determining the number and position of the comparison areas, the total difference between the target area before the movement determined in the area determination step is obtained. , Using the difference sum total calculation step of raising the difference sum to the nth power by a predetermined multiplier n, and the n-th power value of the difference sum calculated in the difference sum calculation step,
It comprises a coefficient calculation step for calculating the coefficient of the polynomial, and a minimum value calculation step for obtaining the coordinate having the minimum value in the polynomial having the coefficient calculated in the coefficient calculation step as the coordinate of the area after the movement of the target area. .

The image motion vector detecting device of the present invention is a motion vector detecting device which indicates the amount of movement of a certain region in a plurality of image groups having temporal continuity, and detects movement from a certain image in the image group. Area determining means for determining the target area, and the degree and the number of terms of the polynomial expression of the approximated surface that approximately expresses the distribution of the difference sum between the areas before and after the movement of the target area determined by the area determining means. The polynomial determining means for determining and the number and positions of the comparison areas sufficient for determining the coefficients of the respective terms of the polynomial are determined, and the movement determined by the area determining means for each of the determined comparison areas. Difference sum calculation means for obtaining the sum of differences with the previous target area and raising the difference sum to the nth power by a predetermined multiplier n, and the n-th power of the difference sum obtained by the difference sum calculation means Used, the coefficients of the polynomial are calculated, and and a minimum value calculating means for calculating the coordinates of a minimum value in a polynomial with the coefficients as the coordinates of the region after the movement of the target region.

[0010]

The sum of the difference value Exy between the area B in the image A and the area Dxy having the same size as the area B in the image C before (after) the image A is taken on the z axis. Assuming that the position of the area Dxy on the image C is on the xy plane, the distribution of the difference sums of the actual image is as shown in FIG. Then, as shown in FIG. 3B, the distribution of the difference summation is approximately represented by a curved surface in the xyz space in which the difference sum value Ex0y0 corresponding to the destination area Dx0y0 from the area B is the minimum value of z. It turned out that it can be represented.

Here, using the tendency of the distribution of the difference summation, taking the difference summation value Exy raised to the nth power as the z-axis, n
The expression of the curved surface that approximates the distribution of the sum of the multiplied differences can be expressed by a simple polynomial such as a quadratic expression of x and y.
FIG. 4A shows the distribution of the difference sum obtained when the difference sum value Exy is raised to the sixth power, and the approximation of the curved surface of the difference sum shown in FIG. 4B obtained from this distribution. The formula is given by x × x + y × y.

The present invention focuses on such an approximated curved surface of the sum of difference values and utilizes it when detecting the movement amount of a partial region in a moving image. That is, according to the present invention, an approximate curved surface expression of the sum of difference values is obtained, and the obtained approximate curved surface expression is used to obtain an image C before (after) the image A.
The position of the area Dx0y0 having the smallest difference sum value Ex0y0 is obtained as the movement destination of the area B.

FIG. 1 shows the procedure of the method of detecting the area movement amount according to the present invention. The detection method according to the present invention mainly comprises six steps, steps 1 to 6. Each processing of these steps 1 to 6 is executed by the image motion vector detection device 11 as shown in FIG.

That is, first, in step 1, the shape of the area B to be detected by the area determining unit 13 is detected.
Determine size and position in image A. This area B
The shape, size, and position of each can be selected arbitrarily, but in consideration of the time and effort required for calculation on a computer, 16 ×
A rectangular area whose side length is a multiple of 8 is often selected, such as 16 or 32 × 16.

In step 2, the polynomial determining unit 14 considers the value of the total difference between the area B in the image A and the area D in the image C after the movement as the coordinate value of the area D in the image C. In this case, the degree and the number of terms of the polynomial representing the curved surface that closely approximates the distribution of the coordinate values are determined. The degree and the number of terms of this polynomial can be arbitrarily selected. When the degree and the number of terms of the polynomial are increased, the time and effort required for calculation increase, but at the same time, the degree of approximation increases. In practice, in consideration of these balances, a polynomial whose degree is quadratic and whose number of terms is 5 to 6 is often used.

In step 3, the difference sum calculation unit 15 first causes the area D in the image C after the area B is moved.
The number N of i (1 ≦ i ≦ N) and the position are determined. Area Di
N is the number of equations required to determine the coefficients of the polynomial determined in step 2 above, and thus the number of difference summation values Ei sufficient to create a given number of equations above. It is the required number.

For example, when the number of polynomial terms is 5, the value of the number N of the area Di needs to be at least 5 or more, and when adopting a value larger than this, a method such as the least square method is used. Therefore, the accuracy can be further improved by effectively using the redundant sum of differences.

The sum of differences calculator 15 then proceeds to step 4
Then, using the image data temporarily stored in the image memory 3, the area D in the image C determined in step 3 is used.
difference sum E between i (1 ≦ i ≦ N) and area B in image A
i is calculated, and the difference sum value Ei is raised to the nth power with a predetermined multiplier n. Here, the reason why the sum of difference values Ei is raised to the nth power is to allow the distribution of the sum of differences to be represented by an approximated surface by a simple polynomial.

The value of n varies depending on the characteristics of the target image, but normally an integer of about 1 to 8 is used. The inevitability of this range is that when n <1, the approximation of the approximate curved surface is limited to a narrow range, and it may be difficult to follow the movement in an image with a lot of movement. Further, for n> 8, the value raised to the n-th power may deviate from the range normally handled by a computer.

In step 5, the pole calculating unit 16
The coefficient of the polynomial of the curved surface that approximates the distribution of the difference sum total determined in step 2 is calculated using the value of the nth power of the difference sum total value Ei calculated in step 4 above.

Then, in the next step 6, the coordinate value of the position where the above polynomial takes the minimum value in the image C is calculated from the coefficient of the polynomial obtained in above step 5. And image A
For the inner region B, the motion vector between the image A and the image C is calculated from the coordinate values. The calculation method used in steps 5 and 6 can be arbitrarily selected.

By sequentially performing the above steps 1 to 6, it becomes possible to detect the position of the area Dx0y0 in the image C, which is the movement destination of the area B in the image A, with a small amount of calculation. . Then, a motion vector is obtained from the position of the area Dx0y0 in the image C and the position of the area B in the image A, and is output to the processing circuit (not shown) in the next stage.

[0023]

EXAMPLE An example of the present invention will be described below. The present embodiment can be applied to the detection of a motion vector required when compressing a moving image according to, for example, MPEG (digital moving image compression format standard).

That is, as shown in FIG.
In the video compression by G format, image A is 16 ×
A plurality of regions (macroblocks) B1 each consisting of 16 pixels
It is divided into B2, B3, .... And each area B
For i, it is necessary to obtain the destination area in the image C before (after) the image A and obtain the movement amount (motion vector) Vi thereof.

Now, in FIG. 6, between image A and image C, the coordinates of a plurality of macroblocks in image A are (x
Consider that the motion vector V is obtained by detecting the coordinates (x0, y0) of the moving destination in the image C of the macroblock B which is _org, y_org).

The processing of step 1 shown in FIG.
From the multiple macroblocks in image A, the coordinates (x_org,
The process of selecting the area B of (y_org) corresponds to this. Next, in determining the polynomial of the approximated surface as the processing of step 2, various curved surfaces can be considered as the approximated surface of the absolute value difference sum. However, in the present embodiment, in order to simplify the explanation, the following (Equation 1 ), A simple quadratic equation is used.

[0027] ^{z = Exy n = ax 2 +} by 2 + cx + dy + e ... ( Equation 1) (where, x, y: position of the destination area Dxy in image C, E
xy ⁿ : ^n-th power of sum of difference between area Dxy and area B, a, b, c, d,
e: unknown coefficient, n: known constant) In this case, the degree of the polynomial is 2 and the number of terms is 5. Also,
The known constant n in (Equation 1) is used in the process of step 4.

As the processing of step 3, the above (formula 1) is used.
Since there are five unknown coefficients in the image C, the number N of the comparison areas Di necessary for the area B in the image C is set to the minimum required 5, and each area is set to D1, D2, ... D5. Further, the coordinates of the areas D1 to D5 in the image C are (x1, y1) to (x5, y5), respectively. Each of these areas D1
D5 is shown in FIG.

Next, in step 4, first, as shown in FIG.
As shown in FIG.
The absolute value difference sums E1 to E5 for the middle area B are calculated. Then, as shown in FIG. 7B, the difference sums E1 to E5 are raised to the nth power using a predetermined multiplier n. The value of this known constant n that also appears in (Equation 1) is
Determined according to the nature of the motion of the target moving image. In general, it has been found from experimental results that it is preferable to set n large for an image with a lot of motion and small n for an image with a slow motion.

As a result of the processing in steps 1 to 4 above,
Five equations can be obtained from the above (Equation 1). Putting these equations together,

[0031]

[Equation 1]

Can be expressed as

[0033]

[Equation 2]

It becomes

In step 5, by using (Equation 3) obtained as described above, each coefficient a, b, c, d, e in the polynomial in the approximated surface of the absolute value difference as shown in FIG. 8 is used. From the sum of absolute value differences E1 to E5.

Next, in the above (formula 1), z = Exy ⁿ = a (x-x0) ² + b (y-y0) ² + f (formula 4) (where x, y are regions in the image C) Dxy position, a, b, f:
Unknown coefficient, x0, y0: pole of the surface)

Here, the coordinates (x0, y0) are the poles of the approximate surface of the absolute value difference, that is, the area Dx0 in the image C where the absolute value difference with the macroblock B will be the minimum.
Considered to be the y0 coordinate. (Equation 1) and this (Equation 4)
By comparing and, x0 = −c / 2a, y0 = −d / 2b (Equation 5) is obtained.

In step 6, using this (formula 5) and the coefficients a, b, c, d obtained in step 5, the coordinates (x0, y0) giving the minimum value as shown in FIG. 9 are obtained. Ask. At this time, the motion vector V = (Vx, Vy) for the image C of the macroblock B to be calculated can be calculated by the formula (Vx, Vy) = (x0−x_org, y0−y_org) (Equation 6). . As described above, the motion vector can be obtained by sequentially executing the processing of the six steps of steps 1 to 6.

As described above, in this embodiment, the unknown coefficient
It is necessary to calculate a, b, c, d and the coordinates (x0, yo) of the destination area of the area B, but the absolute value difference is calculated 5 times,
The calculation amount can be reduced by about 100 times as compared with the conventional method.

[0040]

As described above, in the present invention,
The distribution of the difference sum between the target area for which the motion vector is to be obtained and the comparison area is approximated by a polynomial representing an approximate curved surface, and the position where the sum of the differences is minimized is obtained using this polynomial. . The number of difference summations required to obtain the approximated curved surface is determined by the shape of the approximated curved surface. According to the present invention, the number of difference summations in the image is compared with the conventional method of obtaining the difference totals pixel by pixel or every other pixel. The number of sums of differences that must be calculated in order to obtain the amount of movement of a certain area is very small. Therefore, since the motion vector of the image is obtained, the total calculation amount can be greatly reduced, and the processing speed can be increased.

[Brief description of drawings]

FIG. 1 is a flowchart showing a processing flow of an image motion vector detecting method according to the present invention.

FIG. 2 is a block diagram showing a main configuration of an image motion vector detection device of the present invention.

FIG. 3 is a diagram showing an example of distribution of difference sum values of an actual image and an example of a curved surface that approximates the distribution of difference sum values.

FIG. 4 is a diagram showing an example of distribution of values obtained by raising the sum of difference values of an actual image to the sixth power and an example of a curved surface that approximates the distribution of the sum of difference values.

FIG. 5 is a diagram showing a concept of motion vector detection in the MPEG standard.

FIG. 6 is a diagram showing a concept of detecting a motion vector of a certain area by an image motion vector detecting method according to an embodiment of the present invention.

FIG. 7 is a diagram showing how the sum of differences and its n-th power are calculated.

FIG. 8 is a diagram showing how a coefficient of an approximate curved surface is calculated.

FIG. 9 is a diagram showing a state of calculation of coordinates of poles.

[Explanation of symbols]

11 Image Motion Vector Detecting Device 12 Image Memory 13 Area Determining Section 14 Polynomial Determining Section 15 Difference Sum Calculation Section 16 Pole Point Computing Section A Image Containing Area to Detect Motion Vector B Area to Detect Motion Vector C Motion Vector Image after the region to be detected of is moved D The region to be compared with the region to be detected for motion vector E E Sum of difference between target region and comparison region V Motion vector a, b, c, d Approximate curved surface Coefficient of polynomial term x_org Motion vector detection target x coordinate y_org Motion vector detection target region y coordinate x0 Motion vector detection target region x coordinate after movement y0 Motion vector detection target Y coordinate after movement of the area

Claims (5)

[Claims] 1. A method for detecting a motion vector indicating movement of a certain region in a plurality of image groups having temporal continuity, wherein a difference between a target region for which the motion vector is to be obtained and its comparison region is calculated. The distribution of the total sum is approximately expressed by a predetermined polynomial, and the position of the area where the total sum of the differences is minimized is obtained using this polynomial, and this is set as the area after the movement of the target area. Image motion vector detection method. 2. A method of detecting a motion vector indicating movement of a certain area in a plurality of image groups having temporal continuity, wherein an area is determined from a certain image in the image group to determine a target area for movement detection. Step, and a polynomial determination step that determines the degree and number of terms of the polynomial that approximately expresses the distribution of the difference sum between the areas before and after the movement using the coordinates in the image after the movement as variables, and the coefficient of each term of the above polynomial. For the comparison area determination step of determining the number and position of the comparison areas sufficient to determine, and for each of the comparison areas determined in the comparison area determination step, the target area before movement determined in the area determination step Using the difference sum total calculation step of obtaining the difference sum total and raising the difference sum to the nth power by a predetermined multiplier n, and the n-th power value of the difference sum obtained in the difference sum calculation step, It consists of a coefficient calculation step to calculate the coefficient of the polynomial, and a minimum value calculation step to obtain the coordinate that takes the minimum value in the polynomial having the coefficient calculated in the coefficient calculation step as the coordinate of the area after the movement of the target area. An image motion vector detection method characterized by: 3. The image motion vector detecting method according to claim 2, wherein the polynomial is a quadratic polynomial, the number of comparison areas is 5 or more, and the multiplier n is an integer of 1 to 8. . 4. A motion vector detecting device that indicates movement of a certain region in a plurality of image groups having temporal continuity, wherein a region is determined from a certain image in the image group to determine a region to be a movement detection target. Means, a polynomial determining means for determining the degree and the number of terms of the polynomial expression of the approximated surface that approximately expresses the distribution of the difference sum between the areas before and after the movement for the target area determined by the area determining means, The number and position of sufficient comparison areas for determining the coefficient of each term are determined, and the sum of the differences with the target area before movement determined by the area determination means is obtained for each of the determined comparison areas. A coefficient of the polynomial is calculated by using a difference sum calculation means for raising the difference sum to the nth power with a predetermined multiplier n, and an n-th power value of the difference sum calculated by the difference sum calculation means, Image motion vector detecting device of the coordinate takes the minimum value in a polynomial with coefficients characterized by comprising a minimum value calculating means for calculating a coordinate of the area after the movement of the target region. 5. The image motion vector detecting apparatus according to claim 4, wherein the polynomial is a quadratic polynomial, the number of comparison areas is 5 or more, and the multiplier n is an integer of 1 to 8. .