JPH07162864A - Motion vector detection method - Google Patents

Abstract

(57) [Summary] [Purpose] The optimum motion vector is detected at high speed while ensuring the accuracy of the search by searching for search points that are farther from the center point. A motion vector generation device 3 generates a motion vector of the current block based on the block data from the blocking device 2 and the reference block from the reference block generation device 7. The optimum search point determination device 8 calculates the matching error between the current block and the reference block, stops the search when the matching error is below a certain threshold, and sets that point as the motion vector of the current block. The search point output from the search point output device 5 is gradually moved to a position farther in a spiral around the search point of the first block matching.

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 method for obtaining a motion vector of a digital moving image.

[0002]

2. Description of the Related Art A predictive coding method called motion-compensated interframe prediction has been conventionally used as a moving picture coding method, but it is necessary to detect a moving area in an image in order to improve prediction efficiency. Become.

Conventionally, a block matching method is often used as a motion vector detecting method in the motion compensation interframe predictive coding method. In this block matching method, a motion detection target block (N × N pixel area) is matched with an image within a limited search range in a reference image for every position in pixel units, and a matching evaluation function is calculated. This is a method in which the best matched position is used as the detected motion vector. As the matching evaluation function, for example, for all pixels in the block, the sum of the absolute values of the pixel value errors (absolute value error sum) is used.

However, the block matching method can detect the vector with the highest similarity within the search range,
Since the number of searches is large, there is a problem that the amount of calculation becomes huge when this system is realized. Therefore, a multi-stage search method (this is called a three-step search method, for example, "motion compensation interframe coding of conference television signal").
(Refer to IEICE Technical Report IE81-54 1981-7)) and various other simplification methods have been proposed.

In the three-step search method, instead of the all-pixel position search, the first step is to perform a search at a coarse search point interval, and to search for the search point interval centered on the best matching position. The search for the second stage is performed with the half of the first stage. This is a method in which the same processing is repeated a plurality of stages to narrow down the intervals of the search points from coarse to fine and detect the motion vector.

[0006]

The above-mentioned three-step search method can reduce the amount of calculation to a great extent compared to matching all the search ranges one by one, but if an erroneous detection is made in the first stage, the direction that should be obtained should be obtained. Will detect a completely different motion vector.

As another example of the motion vector detecting method,
(A) A search point that is dense and rough around the center is prepared in advance in a table, and the optimum search point selected in the previous frame (or an adjacent block of the same frame) is centered and searched according to the table. A motion vector detecting device (see Japanese Patent Application Laid-Open No. 3-123285), (b) in a multi-stage search, if the matching error is less than a threshold value when the search range is small, the search is aborted on the spot, and the position where the matching error is the minimum. If the distance is far, the search range is further expanded.
Motion compensation interframe coding apparatus for V signal (Japanese Patent Laid-Open No. 63-
181585), (c) The size of the motion vector is predicted by comparing the block at the same position in the previous frame and the current block, and when the predicted motion vector is small, it is in a narrow range and when it is large. Motion vector detection method for searching in a wide range (Japanese Patent Laid-Open No. 63-14462).
(See Japanese Patent No. 6).

Each of these methods uses the property that the optimum search point has a high probability of being close to the center point, and adopts a method of determining the optimum point with the minimum number of searches. However, in each method, search points are prepared in a table, and the order of search is not considered.

It is an object of the present invention to provide a motion vector detecting method for detecting an optimum motion vector at high speed while ensuring the accuracy of the search by searching for search points which are distant from the center point.

[0010]

In order to achieve the above object, according to the invention of claim 1, an input digital video signal is divided into a plurality of blocks, and each divided block is a block with a previous frame. In the motion vector detection method of detecting a motion vector by performing matching, the position of the block of the previous frame at the same position as the current frame is set as the search point for the first block matching, and the search position is gradually spiraled around the position. To a position far away from
The feature is that the search is immediately stopped when the matching error is equal to or less than a predetermined threshold value, and the point is set as the motion vector of the current block.

According to a second aspect of the present invention, in the motion vector detecting method, the input digital video signal is divided into a plurality of blocks, and each divided block is subjected to block matching with a previous frame to detect a motion vector.
The point of the motion vector selected in the immediately preceding block is used as the search point for the first block matching, and the search point is moved to a position gradually spiraling toward the position of the block of the previous frame at the same position as the current frame. , When the matching of the position of the block of the previous frame located at the same position as the current frame is completed, the search point is successively moved to a position gradually distant from the first search point in a spiral shape, and the matching error becomes a predetermined value. When it is less than the threshold value, the search is immediately stopped and the point is set as the motion vector of the current block.

According to a third aspect of the present invention, in the motion vector detecting method, the input digital video signal is divided into a plurality of blocks, and each divided block is subjected to block matching with a preceding frame to detect a motion vector.
The point of the motion vector selected in the immediately preceding block is set as the search point for the first block matching, and the search position is spirally moved gradually to the farther position with this position as the center, and the matching error is predetermined. When the value is less than or equal to the threshold of, the search is immediately stopped and the point is set as the motion vector of the current block.

The invention according to claim 4 is characterized in that a plurality of patterns of the order of moving search points are provided.

According to a fifth aspect of the invention, the pattern is switched according to the motion vector selected in the immediately preceding block.

According to the sixth aspect of the present invention, when the block matching within the predetermined range is completed and the matching error does not fall below the predetermined threshold value at all the search points, the search range is expanded and the search is continued. It has a feature.

[0016]

It is generally known that the optimum motion vector generation frequency is higher as the motion amount is smaller. The present invention utilizes such a property to perform block matching gradually from a search point having a small amount of motion to a distance, and immediately terminates the search when it is determined that the degree of similarity is high, thereby reducing the number of matching times. Let Also, by using the motion vector of the immediately preceding block, the optimum motion vector can be obtained faster. Unlike the multi-step search, the method of the present invention searches in order, so there is little possibility of erroneous detection, and when it is determined that an appropriate search point cannot be found even after performing predetermined block matching. Expands the search range to facilitate optimal block matching.

[0017]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the present invention will be specifically described below with reference to the drawings. <Embodiment 1> FIG. 1 is a configuration diagram according to Embodiment 1 of the present invention. The input digital image data is stored in the current frame memory 1. The image data output from the current frame memory 1 is output to the previous frame memory 6 and the blocking device 2, and is divided into a plurality of blocks by the blocking device 2.

The reference block generation device 7 generates a reference block based on the search points output from the search point output device 5 and the previous frame image data output from the previous frame memory 6, and the motion vector generation device 3 Entered in.
The motion vector generating device 3 generates a motion vector of the current block based on the block data and the reference block from the blocking device 2. In the optimum search point determination device 8,
The matching error between the current block and the reference block is calculated, and when the matching error is less than or equal to a threshold value, it is determined that the optimum matching has been performed, the search is immediately stopped, and the point is set as the point of the motion vector of the current block.

The order in which the search according to the present invention is performed is, for example, as shown in FIG. 3, the position of the block of the previous frame at the same position as the current frame (hereinafter referred to as the center point A) is searched for the first block matching. The point A is set, and the search position (indicated by a circle) is spirally moved gradually to a far position with this position as the center. These search points are sequentially output from the search point output device 5.

<Embodiment 2> In this embodiment, a motion vector storage device 4 is added to the construction of the first embodiment. The motion vector of the current block output from the optimum search point determination device 8 is also output to the motion vector storage device 4 and used for detecting the motion vector of the next block. The search point output device 5 determines a search point based on the motion vector of the previous frame read from the motion vector storage device 4.

<Third Embodiment> FIG. 4 is a diagram for explaining a second search method according to the present invention. In this search method, the optimum search point B of the immediately preceding block is set as the search point for the first block matching, and the search point is gradually moved toward the center point A in a spiral shape to match the center point. When is finished, next, the search point is moved to a position gradually distant from the initial position B in a spiral manner. The search order is indicated by arrows in the figure.

<Embodiment 4> FIG. 5 is a diagram for explaining a third search method according to the present invention. In this search method, the optimum search point of the immediately preceding block is set as the search point for the first block matching, and the search position is spirally moved to a position farther away from this position as the center. The search order is indicated by an arrow.

<Fifth Embodiment> In the fifth embodiment, a plurality of types of the above-described search order patterns are prepared. For example, the search pattern shown in FIG. 6 is prepared. In addition, the pattern of the order of moving search points is switched according to the determined motion vector of the immediately preceding block. For example, when the motion vector of the immediately preceding block is a strong vector in the horizontal direction as shown in FIG. 6, the search is prioritized in the horizontal direction as in the search pattern of FIG.

Further, when the block matching within a certain range is completed and the matching error does not fall below a certain threshold value at all the search points, the search range is expanded and the search is continued. For example, in FIG. 7, if 21 is a predetermined search range, the search is performed with a spiral pattern 22 wider than that. FIG. 8 is a processing flowchart in the case of FIGS. 4 to 7 described above, in which the search point output device 5 determines a search point based on the motion vector of the immediately preceding block (step 101), and the reference block generation device 7 Generates a reference block based on the search point and the previous frame (step 10
2) The motion vector generator 3 detects the motion vector of the current block (step 103).

FIG. 9 shows the configuration of an embodiment of the search point output device 5. The motion vector determined in the immediately preceding block is
Output to the buffer 11 and the buffer 12, and the buffer 12
Is output to the search direction indicating device 13. The search direction instruction device 13 shifts the previous search point (Pi) stored in the buffer 12 to any of the up, down, left and right in accordance with the pattern instructed by the search pattern instructing device 14 to move the next search point (Pj). Output. The next search point (P
j) is written in the buffer 12, and the search direction indicator 13 outputs the next search point (Pk) again according to the pattern instructed by the search pattern indicator 14. In this way, the spiral search points as in the above-described embodiment are output.

The search point output is executed while there is an instruction to continue the search, and even if the search finishes outputting the end points (for example, the center point A in FIG. 4 and the predetermined range end point D in FIG. 7), the search is still performed. When there is an instruction to continue, the search point is output by referring to the motion vector of the immediately preceding block stored in the buffer 11. For example, in FIG. 4, when the search is continued when the end point (center point A) is output as the search point, since the buffer 11 has the search point B selected in the immediately preceding block, the search direction indicating device 13 , Search point C based on search point B
Is output.

FIG. 10 is a processing flowchart of the search point output device. The search direction indicator 13 determines whether or not the search point in the buffer 12 is the end point (step 201), and when it is the end point, checks whether or not to continue the search (step 20).
2) If the search is continued, the search point is determined based on the motion vector of the immediately preceding block in the buffer 11 (step 20).
3) The search point is output (step 204). If it is not an end point in step 201, it is checked whether or not the search is continued (step 205). If the search is continued, the search point is shifted according to the search pattern designating device 14 (step 20).
6) The search point is output, and the process ends when the search continuation is not instructed.

[0028]

As described above, according to the first aspect of the invention, search points are distant from the center point in sequence without roughening the search points, so the search is aborted. Even if it is, the search accuracy is secured. Further, since the search is immediately stopped when the matching error is equal to or less than the predetermined threshold value, the number of block matching is reduced.

According to the second aspect of the invention, since the motion vector of the immediately preceding block is used, the motion vector of the current block can be detected at high speed.

According to the third aspect of the invention, since the search point is moved in a spiral manner to a position gradually distant from the search position, there is a possibility that a motion vector completely different from the originally desired direction may be erroneously detected. Is less.

According to the fourth and fifth aspects of the present invention, the search pattern can be easily switched according to the motion vector of the immediately preceding block, and optimum block matching can be performed.

According to the sixth aspect of the present invention, since the expansion of the search range is determined at the stage when the predetermined search range is completed, the motion vector can be detected at high speed and with high reliability.

[Brief description of drawings]

FIG. 1 is a configuration diagram according to a first embodiment of the present invention.

FIG. 2 is a configuration diagram according to a second embodiment of the present invention.

FIG. 3 is a diagram illustrating a first search method according to the present invention.

FIG. 4 is a diagram illustrating a second search method according to the present invention.

FIG. 5 is a diagram illustrating a third search method according to the present invention.

FIG. 6 is a diagram illustrating a fourth search method according to the present invention.

FIG. 7 is a diagram illustrating a fifth search method according to the present invention.

FIG. 8 is a flowchart of a search process of the present invention.

FIG. 9 shows a configuration of an embodiment of a search point output device.

FIG. 10 is a processing flowchart of a search point output device.

[Explanation of symbols]

 1 Current Frame Memory 2 Blocking Device 3 Motion Vector Generation Device 4 Motion Vector Storage Device 5 Search Point Output Device 6 Previous Frame Memory 7 Reference Block Generation Device 8 Optimal Search Point Determination Device

Claims (6)

[Claims] 1. In a motion vector detecting method for detecting a motion vector by dividing an input digital video signal into a plurality of blocks and performing block matching with a previous frame for each of the divided blocks, the same position as the current frame is detected. The position of the block of the previous frame in is the search point for the first block matching, the search position is gradually moved to a position farther in a spiral around the position, and the search is immediately stopped when the matching error is less than or equal to a predetermined threshold value. , A motion vector detection method characterized in that the point is used as the motion vector of the current block. 2. A motion vector detecting method in which an input digital video signal is divided into a plurality of blocks and a motion vector is detected by performing block matching with a previous frame in each divided block, which is selected in the immediately preceding block. The point of the motion vector is used as the search point for the first block matching, and the search point is moved spirally toward the position of the block of the previous frame at the same position as the current frame, and then moved to the same position as the current frame. When the matching of the position of the block of a certain previous frame is completed, the search point is moved to a position gradually distant from the first search point in a spiral manner, and when the matching error is equal to or less than a predetermined threshold value, the search is immediately performed. Stopping, and using that point as the motion vector of the current block. 3. A motion vector detecting method for detecting a motion vector by dividing an input digital video signal into a plurality of blocks and performing block matching with a previous frame in each of the divided blocks. The point of the motion vector is set as the search point of the first block matching, and the search position is gradually moved to a position farther in a spiral around this position, and when the matching error is less than or equal to a predetermined threshold value, immediately. A motion vector detection method characterized by stopping the search and using that point as the motion vector of the current block. 4. The motion vector detecting method according to claim 1, wherein a plurality of types of patterns of the order of moving search points are provided. 5. The motion vector detecting method according to claim 4, wherein the pattern is switched according to the motion vector selected in the immediately preceding block. 6. The search range is expanded and the search is continued when the block matching within a predetermined range is completed and the matching error does not fall below a predetermined threshold value at all search points. 5. The motion vector detecting method according to any one of 5 to 5.