JPH06150006A - Motion vector detector - Google Patents

Abstract

(57) [Summary] [Object] To provide a motion vector detection device that does not estimate erroneous motion and the accuracy of motion estimation within one pixel based on block correlation. A block correlation is calculated by a correlation calculation circuit (104), and a corresponding block having the smallest difference is obtained in the preceding and succeeding frames. Next, the FFT calculation circuit (105) obtains the FFT coefficient of each corresponding block. FFT
The shift amount of the phase of the coefficient is calculated by the small deviation calculation circuit (106), and the small deviation between the blocks is obtained from the FFT coefficient shift amount by the least square. The deviation correction circuit (107) adds a small deviation to the coarse deviation obtained by the correlation calculation circuit and outputs it. As compared with the conventional hand using only block correlation, it is possible to obtain a motion vector with an accuracy of pixel unit or higher. In addition, the effectiveness of block correlation can be evaluated based on two points: the presence or absence of features required for motion estimation and the preservation of phase information.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a motion vector detecting device for video coding and noise reduction.

[0002]

2. Description of the Related Art A method for detecting a motion vector is described, for example, in Takahiko Fukibuki: "Digital Signal Processing of Image", Chapter 10, published by Nikkan Kogyo Shimbun (1985). Among them, in the “method of minimizing the difference between consecutive images”, the motion vector is obtained as the deviation (a, b) that minimizes (Equation 1). Here, g (x, y) represents the luminance at the screen position (x, y), and R represents the block area on the screen.

[0003]

[Equation 1]

FIG. 3 illustrates this principle. In the image of the frame at time i−1, it is obtained as a deviation to the block R ′ having the strongest correlation with the block R. In addition to the block correlation, there is a "method of obtaining the amount of movement from the ratio of Fourier transform images". This is obtained from the relationship between the spatial movement and the Fourier transform thereof (Equation 2). In (Equation 2), F {} is the Fourier transform, G is the Fourier expansion of the image g, and 2πμ and 2πν are the horizontal and vertical spatial frequencies, respectively.

[0005]

[Equation 2]

If the Fourier description is obtained for different image frames, the deviation (a, b) corresponding to the motion vector can be obtained from the ratio as shown in (Equation 3).

[0007]

[Equation 3]

Hereinafter, the "method of minimizing the difference between consecutive images" will be abbreviated as the block correlation method, and the "method of obtaining the movement amount by the ratio between the Fourier transform images" will be abbreviated as the Fourier phase method.

[0009]

The conventional motion vector detecting device based on block correlation and Fourier phase has the following problems.

(1) Basically, it is impossible to obtain a minute deviation within one pixel by block correlation. It is possible to obtain a minute deviation within one pixel from linear interpolation of a plurality of block correlation maximum positions. However, it is not easy to select the maximum position for obtaining the true correlation position from the linear interpolation of a plurality of positions.

(2) In the Fourier phase, a minute deviation within one pixel can be obtained, but as is clear from (Equation 3), the solution is not unique. If the correct motion vector can be obtained, the true excursion is limited to ± 1/2 wavelength.

(3) With block correlation, it is difficult to evaluate the reliability of block correlation. The sum of absolute values of the differences in pixel units shown in (Equation 1) tends to have a large value at a large luminance change and a small value at a small luminance change. Therefore, it is difficult to evaluate the validity of the deviation obtained using only the correlation value. The same applies when the square value of the difference is used to evaluate the correlation.

It is an object of the present invention to eliminate the above problems and provide a motion vector detection device which does not estimate motion estimation with accuracy within one pixel and erroneous motion estimation.

[0014]

In order to solve the above problems, the present invention obtains corresponding blocks in preceding and succeeding frames by block correlation, and estimates a minute deviation corresponding to a block by a Fourier phase method. It improves the accuracy and error of.

A first aspect of the present invention relates to accuracy improvement, wherein (a) a memory that holds a video signal that is encoded and is configured in frame units; and (b) a pixel of a block pair of preceding and following frames from the memory. By reading out the data, obtaining a block pair having a strong correlation, and outputting the deviation thereof, a block correlation calculation means and (c) expanding each of the block pair having a strong correlation into a plurality of two-dimensional frequency components, and Phase calculating means for obtaining a phase difference for frequency components; (d) a minute deviation calculating means for calculating a minute deviation from the phase differences of the plurality of frequency components of the block pair; and (e) the block correlation calculating circuit. It is characterized by further comprising a synthesizing calculation means for adding the deviation due to the above and the small deviation due to the small deviation calculating circuit to obtain a motion vector.

The second aspect of the present invention relates to an estimation error, (f) a memory for holding a video signal which is coded and configured in frame units, and (g) a pixel of a block pair of preceding and following frames from the memory. The two-dimensional frequency does not become a constant multiple of the block correlation calculation means that reads data, obtains a block pair having a strong correlation, and outputs the deviation, and (h) the block pair that has a high correlation by the block correlation calculation. Phase difference calculation means for calculating the magnitude and phase difference of at least three frequency components, and (i) the magnitude of the spatial frequency component is less than or equal to a threshold value or the magnitude of the magnitude and phase difference of the three or more frequency components. When the phase differences are inconsistent, it is characterized by including block correlation invalidity determining means for determining that the block correlation is invalid.

[0017]

In the first aspect of the invention, first, in the frames of the preceding and following images, the block having a strong correlation is selected by the block correlation calculating means so as to minimize the sum of absolute values of pixel value differences. As a result, the deviation of pixel accuracy is obtained. Next, for the block pair having a strong correlation, the phase difference between a plurality of frequency components is obtained by the phase calculating means. From the relationship between the phase difference and the frequency obtained by the minute deviation calculating means, the minute deviation can be obtained by the Fourier phase principle shown in (Equation 3). already,
The minute deviation is added to the deviation due to the obtained block correlation by the combining calculation means to obtain a motion vector.

Since the small deviation is limited to a small value by the block correlation calculating means, the two-dimensional spatial frequency used for the calculation by the small deviation calculating means can be increased. A high frequency, in other words, a phase difference of a short wavelength is sensitive to a minute change, so that a highly accurate motion vector can be obtained.

In the second aspect of the present invention, the block having a strong correlation is selected by the block correlation calculating means so as to minimize the sum of the absolute values of the pixel value differences in the frames of the preceding and following images. Next, with respect to the block pair determined to have a high correlation by the block correlation calculation, the phase difference calculation means calculates the magnitude and phase difference of at least three frequency components whose two-dimensional frequencies are not multiplied by other constants.

In the block correlation invalidity judgment means, if each frequency component does not have a sufficient size for calculating the Fourier phase shown in (Equation 3), there is no information necessary for motion estimation in the corresponding block pair, The deviation selected by the block correlation calculation means is invalid. Further, if the obtained small deviations are inconsistent even though the frequency components are large enough to calculate the Fourier phase shown in (Equation 3), the correlation of the block pair is erroneous. , The deviation selected by the block correlation calculation means is invalid. By selecting three or more two-dimensional spatial frequencies that do not become constant multiples in each block, it is possible to obtain three or more linear equations based on (Equation 3) that are independent of each other for the minute deviation of unknown 2. Therefore, for example, the effectiveness of block correlation can be determined from the sum of squared errors when the minute deviation is obtained by the minimum error square.

[0021]

Embodiments of the present invention will be described below with reference to the drawings. A first embodiment of the invention described in claim 1 will be described with reference to FIGS. 1, 3, and 4. FIG. 1 is a block diagram of a motion vector detecting device in the first embodiment. Figure 3 is the first
FIG. 4 is an operation explanatory diagram of deviation estimation in the embodiment of FIG. 4, and FIG. 4 is an operation explanatory diagram of minute deviation estimation in the first embodiment. Figure 1
In the figure, 101 is A / which quantizes the video analog signal.
D conversion circuits, 102 and 103 are frame memories for storing frames before and after an image, 104 is a correlation calculation circuit for performing block correlation, and 105 is an FFT calculation circuit for performing discrete Fourier transform (FFT) on each block pair. ,
Reference numeral 106 is a small deviation calculation circuit for calculating a small deviation from the FFT coefficient, and 107 is a deviation correction circuit. The processing procedure of the first embodiment configured as described above will be described below.

In this embodiment, the block for calculating the correlation and phase information is composed of vertical 8 pixels and horizontal 8 pixels.
As shown in FIG. 3, the correlation calculation circuit (104) reads the block information R from the previous frame memory (103) and at the same time changes the deviation (a, b) for each pixel, while changing the block information R of the current frame. 'Is read out and the correlation calculation shown in (Equation 1) is performed. Then, the deviation having the smallest value is searched for and obtained as the original estimation (a, b). This (a, b) is obtained with one pixel accuracy. Next, the correlation calculation circuit (10
Based on the original estimation (a, b) obtained from 4), the FFT operation circuit (105) performs FFT operation on the block information R and R '. _Let the obtained results be R _f and R _f '. Here, R _f, FFT coefficient (frequency component) of the R _f 'R _f (μ,
ν), R _f '(μ, ν), (where 0 ≦ μ ≦ 7, 0 ≦ ν
≦ 7, μ, and ν are integers). R _f (0,0) and R _f '(0,0) are DC components and are not used for minute deviation estimation. For the complex number Z, its logarithm can be expressed by (Equation 4).

[0023]

[Equation 4]

Here, argZ represents the argument of the complex number Z. Therefore, from (Equation 3) to the FFT coefficient, (Equation 5)
Can get a relationship.

[0025]

[Equation 5]

In (Equation 5), δa and δb are minute deviations. The main value of the argument argZ of the complex number Z is ArgZ (arg z = Arg Z + 2nπ, n is an arbitrary integer). Thereafter, assuming that the original estimation (a, b) by the correlation calculation circuit (104) is an error within one pixel,
(Equation 5) is the main value Arg (R _f '(μ, ν) / R _f (μ,
ν)) 0 ≦ μ ≦ excluding (μ, ν) = (0,0)
It can be considered that it holds in the range of 4, 0 ≦ ν ≦ 4. R _f obtained by the FFT operation circuit (105),
With R _f 'as an input, the minute deviation calculation circuit (106) performs the following calculation.

[0027]

[Equation 6]

[0028]

[Equation 7]

[0029]

[Equation 8]

The relations of (Equation 6) to (Equation 8) are established.
And the generalized inverse matrix of the matrix A is ⁺Then, (number
From 9), the minute deviation (δa, δb) can be obtained.

[0031]

[Equation 9]

In this embodiment, Arg (R _f '
Considering that (μ, ν) / R _f (μ, ν)) cannot be stably obtained, (μ, ν) and Arg (R _f '
Matrixes A and B having (μ, ν) / R _f (μ, ν)) as row components are used. In Table 1, Th ₁ is a threshold value for determining the magnitude of the frequency component.

[0033]

[Table 1]

The general inverse matrix A ⁺ used in this embodiment is Moo.
re-Penrose is a general inverse matrix and is given by (Equation 10). With this, the minute deviation can be obtained in a form that minimizes (Equation 11).

[0035]

[Equation 10]

[0036]

[Equation 11]

The deviation correction circuit (107) adds the minute deviation (δa, δb) thus obtained to the original estimation (a, b) and outputs it as a motion vector (a + δa, b + δb). The above principle will be described with reference to FIG. 8 in FIG.
In the block of × 8, the waveform having the frequency of (μ, ν) = (2, 0) is moved by the phase π / 2 in the horizontal positive direction. Arg (R _f '(μ, ν) / R _f (μ,
Since ν)) = π / 2, δa = 1 pixel is obtained.
In general, since an error is included, the small deviation obtained from the combination of (μ, ν) is different. Therefore, in this embodiment, (δa, δb) is obtained by the least squares method shown in (Equation 9). Since the actual deviation is obtained within 1 pixel by the block correlation, it is assumed that the minute deviation is within 1 pixel. Therefore, among the FFT coefficients in the block, the coefficient of horizontal and vertical wavelengths up to 2 pixels is used to obtain the minute deviation in the meaning of least squares. The size of the block is 8 pixels vertically and 8 pixels horizontally.
Although a pixel is used, the same configuration can be adopted even if the number of vertical and horizontal pixels is different. Although the sum of absolute values is used for the block correlation, the sum of squares may be used.

Next, an embodiment of the invention described in claim 2 will be described. In the second embodiment, the purpose is not to find a minute deviation of a motion vector obtained from an FFT coefficient, but an origin of deviation due to block correlation. It is different from the first embodiment in that the validity of the estimation is determined. This will be described with reference to FIG. FIG. 2 is a block diagram of the motion vector detecting device in the second embodiment. In FIG. 2, 201 is an A / D conversion circuit for quantizing a video analog signal, and 202 and 203 are
A frame memory for storing the preceding and succeeding frames of the image, 204 a correlation calculation circuit for performing block correlation, 20
Reference numeral 5 is an FFT operation circuit that performs a discrete Fourier transform (FFT) on each of the block pairs, 206 is a block correlation determination circuit that determines the validity of correlation from FFT coefficients, and 207 is a valid flag addition circuit. Second configured as described above
The processing procedure of this embodiment will be described below.

The operations of the A / D conversion circuit (201), the frame memories (202) and (203), the correlation calculation circuit (204) for performing block correlation, and the FFT calculation circuit (205) are the same as those in the first embodiment. It is omitted because it exists. The block correlation determination circuit creates an N × 2 matrix A and an N × 1 matrix B consisting of only row components that satisfy the conditions of Table 1. Here, the matrices A and B are the matrices shown in (Equation 7) and (Equation 8). Here, N is the number of terms that satisfy the condition.

Next, the Moore-Penrose general inverse matrix A ⁺ is obtained. The above is the same as the first embodiment. .
The following are different in the second embodiment. The block correlation determination circuit further decomposes the general inverse matrix A ⁺ into singular values to obtain singular values λ ₁ and λ ₂ (where λ ₁ > λ ₂ ). Since the number of rows is 2, two singular values are obtained. Furthermore, (Equation 12)
Thus, the squared error average E is obtained. Here, the block correlation determination is determined to be effective when the three conditions shown in Table 2 are simultaneously satisfied. In Table 2, Th ₂ and Th ₃ are thresholds for determining the condition number and the squared error, respectively.

[0041]

[Equation 12]

[0042]

[Table 2]

As described above, in this embodiment, among the conditions of Table 2,
Condition 3 and condition 4 indicate whether two or more (μ, ν) vectors necessary for motion estimation exist independently.
It is possible to invalidate the motion vector of a flat area where there is no change in brightness or an area having only vertical edges or horizontal edges. Further, under the condition 5, it is possible to invalidate the region associated with the deformation and the hiding. One alternative to the effectiveness determination performed in the present embodiment can be realized by thresholding the minimum value of (Equation 1). That is, when the block correlation value represented by (Equation 1) is large, it is invalidated.
However, the determination is greatly affected by the change of the average luminance component in the block, and is valid in a flat luminance area although it is invalid. On the other hand, in the present embodiment, since the determination is made based on the contradiction of the phase information, it is stable against the change of the average luminance.

In the two embodiments of the present invention,
Discrete Fourier transform (FF
Although T) is used as it is, an FFT having a window function may be used, or a frequency decomposition filter such as a Gerber filter may be used. In addition, in the first embodiment, the correction of the minute deviation is performed, and in the second embodiment, the validity of the block correlation is determined. It is also possible to realize a motion vector detection device that makes a determination.

[0045]

According to the first aspect of the present invention, it is possible to obtain a motion vector with an accuracy of a pixel unit or more as compared with the conventional block correlation. Further, according to the second invention, the effectiveness of the block correlation can be evaluated from the two points of the presence / absence of features necessary for motion estimation and the preservation of phase information.

[Brief description of drawings]

FIG. 1 is a configuration diagram of a motion vector detection device according to a first embodiment.

FIG. 2 is a block diagram of a motion vector detecting device according to a second embodiment.

FIG. 3 is an explanatory diagram of a block correlation operation in the motion vector detecting device and the first and second embodiments.

FIG. 4 is an explanatory diagram of a Fourier phase in the motion vector detecting device, the first and second embodiments.

[Explanation of symbols]

 101, 201 A / D converter 102, 103, 202, 203 Frame memory 104, 204 Correlation calculation circuit 105, 205 FFT calculation circuit 106 Small deviation calculation circuit 107 Deviation correction circuit 206 Block correlation determination circuit 207 Effective flag addition circuit

Claims (2)

[Claims] 1. A block that has a strong correlation with (a) a memory that holds a video signal that is encoded and configured in frame units, and (b) that reads pixel data of a block pair of preceding and following frames from the memory. A block correlation calculation unit that obtains a pair and outputs the deviation, and (c) develops a plurality of two-dimensional frequency components for each of the block pairs having a strong correlation to obtain a phase difference for the plurality of frequency components. A phase calculating means; (d) a minute deviation calculating means for calculating a minute deviation from the phase difference of the plurality of frequency components of the block pair; and (e) a deviation by the block correlation calculating circuit and the minute deviation. A motion vector detecting device having a combining operation means for adding a small deviation by a deviation operation circuit to obtain a motion vector. 2. A block having a strong correlation with (f) a memory holding a video signal which is coded and configured in frame units, and (g) reading pixel data of a block pair of preceding and following frames from the memory. The magnitude of at least three frequency components in which the two-dimensional frequency does not become a constant multiple of the block correlation calculation means that obtains the pair and outputs the deviation, and (h) the block pair that is determined to have a high correlation by the block correlation calculation. And a phase difference calculating means for calculating a phase difference,
(I) Regarding the magnitudes of the three or more frequency components and their phase differences, if the magnitudes of the spatial frequency components are less than a threshold value or the phase differences are inconsistent, it is determined that the block correlation is invalid. A motion vector detecting device having a determining means.