JPH08205154A - Motion-compensated interframe prediction motion detection method and apparatus - Google Patents

Abstract

(57) [Abstract] [Purpose] To reduce the calculation time and improve the accuracy of motion estimation. [Structure] Image data is input 1 and enters a motion detector 2. The motion detector 2 detects motion based on the input image data and the data in the previous image memory 3. For the motion detection of the motion detector 2, a vector set stored in the ROM 5 is used, and the calculation of the maximum point of the similarity by matching is repeated using these vectors as a reference to calculate the motion vector. The calculated points by the motion detector 2 are stored in the RAM 6, and the image output 4 and the motion vector data output 7 are performed. As a result, the amount of calculation can be reduced and the processing time for motion detection can be shortened.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a motion detection method and device for motion-compensated interframe prediction.

[0002]

2. Description of the Related Art FIG. 16 shows an outline of motion detection. The block on the right side (the area surrounding the helicopter in the figure) in the current image of FIG. 16-2 is 16-1 in the figure.
In the image one frame before, it exists on the left side of the image. This indicates that the block moved from the left side to the right side during one frame. The vector representing this amount of motion is a motion vector, and the work of obtaining this motion vector is called motion detection. Reference numeral 16-3 in the figure indicates a motion vector of a block existing in 16-1 and 16-2.

In a typical motion detection conventionally used, blocks are matched with each other for all pixels in a motion detection area (hereinafter referred to as a search area) as shown in FIG. The block matching method for finding the block position that becomes 1 and the first 8 points in the figure and the total of 9 points, which is 1/2 the distance from the origin to the end of the search area as shown in FIG. Find the minimum matching residual for the second time, and then halve the above distance.
Various methods such as a multi-step search method for narrowing down the matching residual minimum point similarly at the second distance and the third distance are also devised, and motion detection such as MPEG is also used.

[0004]

In the conventional motion detection described above, the calculation time is increased if the accuracy of the motion prediction is increased, or the accuracy of the motion prediction is decreased if the calculation time is shortened. There is a problem. Specifically, if the search area is set wide so that a moving object in the image does not move out of the search area, the block matching method increases the calculation amount accordingly, If the multi-step search method is used to reduce the number of points, the points to be searched for the first time are separated from each other, and if the true motion obtained in the first time is different from the direction in which the motion is found, the motion prediction fails. Needless to say, the above-mentioned calculation time and the accuracy of motion estimation have a great effect when the moving image is encoded by the information source.

The object of the present invention is to solve the problems of the prior art,
(EN) Provided are a motion compensation method for motion-compensated interframe prediction that shortens the calculation time and improves the accuracy of motion prediction, and an apparatus thereof.

[0006]

Means for Solving the Problems The above-mentioned objects include means for storing previous image data, means for storing a vector set, and
Based on the input image data and the data of the previous image storage means, the vector set of the storage means is used, and the calculation of the maximum point of the similarity degree by matching is repeated based on these vectors to obtain the motion vector. This is achieved by providing a motion detector and means for storing the motion vector of the block calculated by the motion detector.

[0007]

According to the above means, a vector set consisting of a plurality of vectors is used based on the input image data and the previous image data, and the similarity is calculated by the block matching method with these vectors as a reference. By using the vector set again for the maximum point, and repeating the calculation of the maximum matching similarity based on these vectors, the matching similarity converges to the maximum point in the search area. Let the vector of the said convergence point be a motion vector. As a result, the amount of calculation is reduced and the processing time is shortened.

[0008]

EXAMPLES The present invention will be described below with reference to examples.

FIG. 1 shows an outline of motion detection according to an embodiment of the present invention. As shown in 1-1 in the figure, the upper left corner of the block in the current image is the origin. For the sake of convenience, the origin is set to the upper left, and it goes without saying that it may be another point such as the center of the block. 1-in the figure corresponding to this origin
2 is a set of vectors showing how to perform matching from a representative point such as the origin to the point of the image one frame before (hereinafter, the vector is a sample vector, and the set of vectors is a set of vector vectors). The point at which the similarity is maximized is found from the similarity obtained as a result of overlapping and matching the blocks at points within the set of sample vectors. Here, in obtaining the similarity, generally, a function that represents the similarity uses a function that returns a small value when the similarity increases, and generally, the residual sum of squares shown in Formula 1 or the formula 2 An evaluation function such as the sum of absolute difference is used.

[0010]

[Equation 1]

[0011]

[Equation 2]

The fact that the degree of similarity is maximized as shown in this equation means that the value of the evaluation function (sum of residuals squared, sum of absolute value differences) is minimized. Although the residual sum of squares is used as the evaluation function below, the same process can be performed with the sum of absolute difference. Therefore, the residual minimum point 1 at which the residual sum of squares is minimized is obtained by using the equation (1). And
A set of sample vectors is overlapped around the minimum residual point 1, and the minimum residual point 2 that minimizes the sum of squared residuals is obtained in the set of sample vectors. Similarly, the process of overlapping the set of sample vectors around the minimum residual point 2 is continued until the minimum residual point does not change. A vector is drawn from the origin to the point where the minimum residual point does not change. This is the motion vector. The sample vector set refers to a set of uniformly distributed vectors as shown in FIG. 2 or a set of vectors distributed with a center as shown in FIG. 3, but is not limited to this. As long as it is a set capable of searching a local area within the search area, it is usually a circular area, but it goes without saying that a rectangular area or the like is also possible.

FIG. 4 shows the motion detection performed by changing the sample vector set according to the magnitude of the value of the evaluation function obtained from the block matching result. The sample vector set 1 is superimposed on the origin in the figure, block matching is performed for each sample vector, and the residual minimum point 1 at which the residual sum of squares is minimized is obtained. Next, according to the residual sum of squares, the sample vector set 2 in which the size of the sample vector set and the distribution state of the sample vectors are changed is overlapped, and the minimum residual point 2 that minimizes the residual sum of squares by block matching is set. Ask. Similarly, the operation of obtaining the minimum residual point 3 from the sample vector set 3 according to the residual sum of squares is repeated until the minimum residual point does not change. The finally obtained vector from the residual minimum point to the origin is taken as the motion vector.

FIG. 5 shows the processing start positions of two points, the motion prediction point and the origin. This is to roughly estimate which one of the origin and the motion prediction point has a motion vector to be obtained at the beginning of the motion detection process, and start the process from that point. As indicated by 5-1 in the figure, the motion prediction is performed from the previous block like the motion prediction of MPEG or the like.
It is needless to say that the motion vector may be predicted using the known motion vectors of the surrounding blocks, not limited to the prediction from the previous block. 5-in the figure
The matching residuals are obtained at two points, 0'of 5-3 in the figure corresponding to the origin 0 of the block of 2 and the motion prediction point P obtained by the above-mentioned method. The process of is started.

FIG. 6 is a schematic diagram of a processing map for preventing recalculation according to an embodiment of the present invention. As shown in FIG. 6A, when the motion vector detection using the sample vector set described above is performed, the calculation is performed again at the point where the calculation is performed once. In order to prevent this, a calculated point map as shown in FIG. 6B for storing the calculated points corresponding to the search area is created, and the search is performed while searching the map.

As a concrete example, all the values of the calculated point map are set to 0 before starting the search. Then, each time the motion vector is detected, 1 is stored in the position of the calculated point. At the time of this calculation, look at the calculated point map, if 0, calculate and store 1.
If 1, the calculation is not performed and the next calculation is performed.

FIG. 7 shows an embodiment of the motion detecting apparatus of the present invention. It can be roughly classified into a case where the motion compensation interframe predictive coding is not used as in the start of the moving image information source coding process and a case where the motion compensation interframe predictive coding is used. For example, in the case of the first image at the start of encoding, the refresh image for preventing the propagation of errors due to the use of motion-compensated interframe predictive coding, the motion-compensated interframe predictive encoding is not used.

In the former case, image data is input 1,
It enters the motion detector 2, is stored in the previous image memory 3, and the image is output 4 as it is.

In the latter case, the image data is input 1,
Enter the motion detector 2. The motion detector 2 detects motion based on the input image data and the data in the previous image memory 3. Motion detection follows the process of the flowchart shown in FIG.
Find the motion vector. After that, the motion detector 2 outputs a signal that the motion vector can be detected or cannot be detected, and outputs 7 if the motion vector can be detected. Further, although the data necessary for the information source coding such as the difference data of the input image data with respect to the previous image data is output, the contents depending on such a coding technique are not particularly mentioned.

Further, as shown in FIG. 8, a concrete configuration example of the ROM 5 for the sample vector set is as follows.
i2 address, ... In address item is stored, and i address is M
The basic vectors of MAP [2], ..., In are stored in AP [1], i2, respectively.
Further, the specific configuration of the RAM 6 that stores the calculated points is
As shown in FIG. 9, vector X components X ₁ , X ₂ , ... Xn and vector Y components Y ₁ , Y _2, ... Yn are stored.

FIG. 10 is a flowchart of the motion detection algorithm of the motion detector 2. Ask. At the origin of the block, first, the minimum residual point (x, y) and the residual sum of squares D at that point
Is calculated (step 102). This residual minimum point and residual 2
The process of obtaining the sum of multiplications D is shown in FIG. The obtained residual minimum point (x, y) is determined to be the residual residual minimum point (x, y) near the residual minimum point (x_min, y_min) and the residual sum of squares D (step 105). D obtained here and D_min are compared (step 106), and if they are not equal, the residual residual minimum point (x, y) is set to (x_min, y_min) and the residual sum of squares D is obtained.
Is substituted for D_min (step 107), and step 1
The process returns from 08 to step 104 and the same process is repeated.
If they are equal, the coordinates of the minimum point are saved as a motion vector (step 109), and the process ends (step 110). All coordinate systems use a coordinate system whose origin is a block for obtaining a motion vector.

FIG. 11 is a flowchart of an algorithm for calculating the residual minimum point and the residual sum of squares. After the initialization (step 202), the loop between steps 209 is repeated until the variable i becomes equal to or larger than the total number of sample vectors used (step 203). In the loop, it is judged whether or not the component (vx, vy) (step 204) obtained by adding the residual minimum point to the sample vector component is in the calculation (step 205), and if it is not calculated yet. For example, 1 is substituted for the corresponding point of the calculated point map (step 206), the residual sum of squares D of that point is calculated (step 207), and the minimum value of the residual sum of squares D_min calculated so far is calculated.
(Step 208), and if smaller, step 20
9. If it is larger, it is saved (step 210) and then the process proceeds to step 209. If it is found in step 205 that the calculation has been completed once, the process proceeds to step 209.

FIG. 12 is a flowchart for calculating the residual sum of squares. The residual sum of squares of Equation 1 is calculated.

FIG. 13 is a flowchart of the motion detection algorithm. The minimum residual point (x1, y1) near the prediction point (px, py) of the motion vector derived from the preceding processed adjacent block and the residual sum of squares D1 of that point are obtained (step 402). Next block origin (0,0)
A residual residual minimum point (x2, y2) and a residual sum of squares D2 are obtained (step 403). The residual sum of squares D1 and the residual sum of squares D2 are compared (step 404). If the residual sum of squares D1 is less than or equal to the residual sum of squares D2, the residual minimum point (x1, x1) is set to the residual difference. The residual sum of squares D1 at the minimum point (x_min, y_min)
Is substituted for the residual sum of squares D_min (step 405). If the residual sum of squares D2 is larger, the residual minimum point (x
2, y2) is substituted for the residual minimum point (x_min, y_min), and the residual square sum D2 is substituted for the residual square sum D_min (step 406).

After that, the minimum point (x_min, y_min)
The residual residual minimum point (x3, y3) and the residual sum of squares D3 are found (step 408). D3 and D_min are compared (step 409). If the minimum residual point (x3, y3) is smaller, the minimum residual point (x3, y3) is (x_mi
Substituting the residual sum of squares D3 into D_min (n, y_min) (step 410), steps 411 to 40
Return to 7 and repeat the same processing. If the minimum point and the error minimum point are equal in step 409, the coordinates of the minimum point are saved as a motion vector (step 412), and the process is terminated (step 413).

FIG. 14 is a flow chart for obtaining the residual minimum point and the residual sum of squares used in FIG. Step 50
In step 2, the sample vector set is determined based on the value of the residual sum of squares obtained previously. The processing of the following steps 503 to 512 is the same as in FIG.

FIG. 15 is a diagram showing the configuration of a moving image transmission system which is an embodiment of the present invention. The transmitting device is
A CPU 11 that controls the overall operation of the device, an image input device 12 such as a video camera, and an image input signal (for example, NT
1 / F13 also having an A / D conversion function for converting (SC composite signal, etc.) into a digital signal, and an input image storage device 14 for storing input digital image data
A motion detecting device 15, an information source coding device 16 for coding information such as input image data and a motion vector obtained as a result of motion detection, a communication control device 17 for transmission / reception and communication control, and RS-2 connecting CPU11
It is composed of a general-purpose I / F 18 such as 32C.

Further, the receiving side device has a CPU 21 for controlling the overall operation of the device, a communication control device 22, and C
General-purpose I / F2 such as RS-232C that connects PU21
3, an information source decoding device 24, an image storage device 25 for storing the decoded image data, and a display device 27.
And an I / F 26 that connects it to the CPU 21.

[0029]

According to the present invention described above, the following effects can be obtained.

(1) The amount of calculation can be reduced as compared with the conventional motion detection method.

(2) The processing time for motion detection can be shortened by reducing the amount of calculation.

(3) The processing time of the entire system can be shortened.

[Brief description of drawings]

FIG. 1 shows an outline of motion detection according to an embodiment of the present invention.

FIG. 2 is an example 1 of a distribution state of a sample vector set.

FIG. 3 is an example 2 of a distribution state of a sample vector set.

FIG. 4 shows an outline of motion detection using a variable sample vector set according to another embodiment of the present invention.

FIG. 5 is an example of calculation of motion prediction points.

FIG. 6 is an explanatory diagram of a calculated point map used to prevent recalculation.

FIG. 7 is a motion detection device according to an embodiment of the present invention.

FIG. 8 is a configuration example of a ROM for a sample vector set used in FIG.

FIG. 9 is a configuration example of a ROM used in FIG.

10 is a flowchart 1 of the motion detection of FIG.

FIG. 11 is a flowchart for obtaining a residual minimum point and a residual sum of squares used in FIG.

12 is a flowchart for obtaining the residual sum of squares used in FIG.

13 is a flowchart 2 of the motion detection of FIG.

14 is a flowchart for calculating a residual minimum point and a residual sum of squares when a process of changing the sample vector set used in FIG. 13 is performed.

FIG. 15 is a system configuration diagram of an information source-encoded data communication device of another embodiment of the present invention.

FIG. 16 shows an outline of motion detection.

FIG. 17 shows an outline of a block matching method which is a conventional motion detection method.

FIG. 18 shows an outline of a conventional multi-stage search method which is a motion detection method.

[Explanation of symbols]

1 ... Image input, 2 ... Motion detector, 3 ... Previous image memory, 4
... image output, 5 ... sample vector set ROM, 6 ... motion vector RAM, 7 ... motion vector data output.

Claims (6)

[Claims] 1. In a motion detection method for detecting a motion vector used in motion-compensated interframe prediction, which encodes temporal correlation in source coding of a moving image, a vector set composed of a plurality of vectors. , The similarity is calculated by the block matching method using those vectors as a reference, the vector set is used again at the point where the similarity is maximum, and the maximum similarity is calculated based on these vectors. A motion detection method for motion-compensated inter-frame prediction, which is characterized by causing the point of which the similarity of matching is maximized in the search area by repeating the above, and using the vector of the convergence point as a motion vector. 2. The motion compensation frame according to claim 1, wherein the size of the vector set, or the size of the vector set and the arrangement of internal vectors are adjusted according to the similarity of the matching. Inter-prediction motion detection method. 3. Similarity of matching by a block matching method using a set of vectors for both the origin of the block for detecting the motion and the motion prediction point predicted from the adjacent block previously detected for the motion. 2. The point having the maximum degree is obtained respectively, and the obtained two points are compared to predict which point the true motion vector is near prior to the motion detection. Motion Compensation Interframe Prediction Motion Detection Method. 4. When the similarity of the matching is repeatedly obtained, the calculation of the similarity of the matching is not performed again for the calculation point used when calculating the similarity of the previous matching. The motion detection method of motion-compensated inter-frame prediction according to claim 1. 5. A motion detection device for detecting a motion vector used in motion-compensated inter-frame prediction, which encodes temporal correlation in source-coding a moving image, stores previous image data. Means, a means for storing the vector set, a vector set of the storage means based on the input image data and the data of the previous image storage means, and the maximum similarity degree by matching based on these vectors. A motion detection device for motion-compensated interframe prediction, comprising: a motion detector that repeatedly calculates a point to obtain a motion vector; and a unit that stores a motion vector of a block calculated by the motion detector. 6. A transmission-side device, which is provided with a motion detection device for motion-compensated inter-frame prediction according to claim 5, which performs information source coding and transmits, and an information source decoding of received data via a transmission path. A moving image transmission device including a receiving side device for displaying the image.