JP2004229150A - Motion vector searching method and device - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a device and a method for searching a motion vector at a high speed by reducing a decrease in searching accuracy to a minimum. <P>SOLUTION: In a multiple step search, in which coarse search is performed first and then fine search focusing on the result of the coarse search is performed, two or more adjoining blocks are searched by the gross in the first step search, and one motion vector for each unit of two or more searched blocks is detected. In the second step search, each block is searched focusing on the result of the first step search, and a motion vector for each block is sought. <P>COPYRIGHT: (C)2004,JPO&NCIPI

Description

[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to a motion compensated predictive coding technique, and more particularly to a motion vector search method and apparatus used in a multi-stage search method, and a computer system.
[0002]
[Prior art]
In compression encoding when recording or transmitting a moving image signal, an encoding method using correlation between image frames is generally used in order to increase encoding efficiency. A coding method using correlation between image frames is called motion compensation prediction coding, and is adopted in MPEG (Moving Picture Experts Group) 2 or the like.
[0003]
In motion-compensated prediction coding, information on motion of a video between frames (motion vector) and a difference image (prediction error) between a predicted image generated by the motion vector and a frame being encoded are encoded. If the correlation between the image frames is large, the prediction error becomes small, the amount of information to be encoded can be reduced, and the compression ratio can be improved. In the motion compensation prediction coding, a frame is generally divided into blocks of a fixed size such as 16 × 16 pixels, and a motion vector is assigned to each of the divided blocks.
[0004]
Specifically, from among frames (reference frames) that have already been encoded, a location where the correlation is highest for each block is searched for, a difference between the blocks is obtained, and encoding is performed. The process of searching for a place where the correlation becomes large is called a motion vector search. The magnitude of the correlation can be evaluated by summing up the differences of each pixel in the block between the reference frame and the frame being encoded.
[0005]
An optimum motion vector can be obtained by simply searching all points in the designated search range and examining the magnitude of the correlation. However, this method is extremely unrealistic because the amount of calculation is extremely large. In general, in order to reduce the amount of calculation, it is common to first perform a coarse first-stage search and then perform a fine second-stage search centering on the search result. Such a method is called a multistage search method and is disclosed in, for example, Non-Patent Document 1. Hereinafter, the multi-stage search method will be briefly described.
[0006]
FIG. 7A is a schematic diagram showing a pixel array for explaining a general multistage search method, and FIG. 7B is a sequence diagram showing a state of a second stage search. For example, first, a two-pixel accuracy search (search for a position labeled “1” in FIG. 7A) is executed as a first-stage search, and a position having the largest correlation is determined. Subsequently, a one-pixel accuracy search (search for a position labeled “2” in FIG. 7A) is executed as a second-stage search centering on the position that is the first-stage search result. The position where the correlation becomes maximum is determined as the final motion vector.
[0007]
Usually, the first-stage motion vector search uses frame data whose resolution is reduced by sub-sampling the frame. For example, the first-stage motion vector search is performed by halving the frame data both vertically and horizontally, and the second-stage search is executed at the original resolution with the surrounding area of the search result as a search range to obtain a final motion vector. For example, as shown in FIG. 7B, when the search range of the second stage is a range of ± 1 pixel in the vertical and horizontal directions, all positions within the search range ((a) in FIG. 7B) ~ (I)) matching is performed.
[0008]
Non-Patent Literature 2 discloses an example of a method of searching for a motion vector by reducing the resolution in this way. In the method described in Non-Patent Document 2, two types of searches, a motion vector search using an image reduced in resolution and reduced, and a motion vector search using an image of the original resolution are performed, and a search result that reduces a prediction error is adopted. .
[0009]
For example, in the search with reduced resolution, first, both the encoding target image and the reference image are subsampled in the horizontal direction at N: 1, and a motion vector search is performed on the subsampled image. At this time, the size of the block is also reduced on the sub-sampled image, but the matching unit is the same as the block size of the original resolution. That is, when the block size at the original resolution is 16 pixels in the horizontal direction and 16 pixels in the vertical direction, the block size is 16 / N pixels in the horizontal direction and 16 pixels in the vertical direction by subsampling only in the horizontal direction. The operation is performed with 16 pixels in the horizontal direction and 16 pixels in the vertical direction. Therefore, N blocks adjacent in the horizontal direction are searched at once. As a result, if the search result of the search with the reduced resolution is adopted, adjacent N blocks have the same motion vector. The accuracy of the motion vector at this time depends on the size of the sub-sampled image. For example, a search is performed by subsampling in the horizontal direction 2: 1. When the search result is adopted as a final motion vector, a search equivalent to a search of skipping one pixel is considered in terms of the original resolution. Accuracy.
[0010]
In addition, in the motion detection method disclosed in Patent Document 1 (Japanese Patent Laid-Open No. Hei 10-191347), a semi-global block obtained by combining two blocks is obtained, and a motion vector of a block adjacent thereto is detected. Detect rough movement of blocks. Then, a motion vector for each block is detected by using the detected rough position as a search target. Similarly, in the motion detection method disclosed in Patent Document 2 (Japanese Patent Application Laid-Open No. 10-13835), a search is performed on behalf of one of a plurality of blocks.
[0011]
[Non-patent document 1]
"A new three-step search algorithm for block motion estimation", IEEE Transactions on Circuits and Systems for Video Games. 4, No. 4, August, 1994, p. 438-441
[Non-patent document 2]
Kanda et al. “Wide-area search of motion vectors by downsampling”, Video Media Processing Symposium (IMPS96), 1996, pp. 99-100
[Patent Document 1]
JP-A-10-191347 (abstract, 0029-0031).
[Patent Document 2]
JP-A-10-13835 (abstract, 0018).
[0012]
[Problems to be solved by the invention]
However, the method disclosed in Non-Patent Document 2 has a problem that the amount of calculation increases because the search is performed using two types of motion vector search methods.
[0013]
When the search result of the search with reduced resolution is adopted, the same motion vector is obtained in a plurality of adjacent blocks, and the search result obtained by the coarse search becomes the final motion vector as it is. For this reason, there is also a problem that it is not possible to cope with fine movements in the image, and the search accuracy is reduced.
[0014]
Further, in the method disclosed in Patent Literature 1, since the motion of the semi-global block is represented by the motion of an adjacent block, the motion of the semi-global block itself is not detected. The method of Patent Document 2 also employs a similar representative search. For this reason, the search accuracy may be greatly reduced.
[0015]
An object of the present invention is to provide a novel motion vector search method and apparatus and a computer system capable of searching for a motion vector at high speed.
[0016]
Another object of the present invention is to provide a motion vector search method and apparatus and a computer system that can search for a motion vector at high speed while minimizing a decrease in search accuracy.
[0017]
[Means for Solving the Problems]
A motion vector search device and method according to the present invention reduce a vertical direction and a horizontal direction of a target image and a reference image to generate a reduction target image and a reduced reference image, respectively, and based on the reduction target image and the reduced reference image, A first motion vector is searched for in a search unit including a plurality of adjacent blocks. Within the search range determined by the detected first motion vector, the second motion vector is searched for in units of one block based on the image resolution before reduction, and the motion vector is determined. Furthermore, it is desirable to determine the complexity of the motion of the moving image and change the size of the search unit according to the motion complexity.
[0018]
In the ordinary hierarchical motion vector search, in both the first-stage search and the second-stage search, a search is performed for each block to detect a motion vector of each block. According to the present invention, adjacent motions are detected in the first-stage search. Search multiple blocks at once. When N blocks adjacent in the horizontal direction and M blocks adjacent in the vertical direction are collectively searched for, one motion vector is detected for each N × M block. In the second-stage search, a search is performed for each block centering on the position obtained as the search result of the first-stage search, and a final motion vector is determined. Since the final motion vector is detected for each block, it is possible to prevent a decrease in search accuracy.
[0019]
As described above, in the first-stage search, the number of vectors to be detected is reduced by searching in a search unit in which a plurality of blocks are put together. Therefore, the amount of calculation for vector detection is reduced, and a high-speed motion vector search can be realized. In addition, in the second stage search, since a motion vector is obtained for each block, a decrease in the accuracy of the motion search is minimized.
[0020]
Further, by searching a plurality of blocks at once in the first-stage search, the difference between the finally obtained motion vectors between adjacent blocks is reduced. Therefore, the code amount required for coding the motion vector can be reduced, and a larger code amount can be allocated for coding the block data. Therefore, a decrease in image quality is minimized.
[0021]
BEST MODE FOR CARRYING OUT THE INVENTION
FIG. 1 is a block diagram showing a first embodiment of a motion vector search device according to the present invention. In FIG. 1, data of a frame being encoded is stored in a current frame buffer 101, and reference frame data is stored in a reference frame buffer 102. The sub-sampling processing unit 103 receives the current frame data and the reference frame data from the current frame buffer 101 and the reference frame buffer 102, respectively, and generates reduced current frame data and reduced reference frame data by sampling.
[0022]
The first-stage motion search processing unit 104 performs a motion search using the reduced current frame data and the reduced reference frame data, and converts the position information of the first-stage motion vector obtained as a result of the search into the second-stage motion search process. Output to the unit 105. The second-stage motion search processing unit 105 receives the original current frame data and the reference frame data from the current frame buffer 101 and the reference frame buffer 102, and performs a detailed motion vector search centering on the position of the first-stage motion vector. Execute Thus, a final motion vector is determined.
[0023]
The sub-sampling process 103 includes a reduction processing unit 111 that performs vertical / horizontal reduction. The reduced current frame data and reduced reference frame data reduced by the reduction processing unit 111 are stored in a reduced current frame buffer 112 and a reduced reference frame buffer 113. Each is stored. The first stage motion search processing unit 104 includes a matching single extraction unit 114 and a matching calculation processing unit 115 described later. Next, the overall operation of the present embodiment will be described in detail.
[0024]
FIG. 2 is a flowchart showing the overall operation of the first embodiment. First, the reduction processing unit 111 inputs the current frame data to be encoded from the current frame buffer 101 and performs sub-sampling (step S201). Similarly, the reduction processing unit 111 inputs the reference frame data from the reference frame buffer 102 and performs sub-sampling (step S202).
[0025]
Next, in order to start the first stage search processing from the beginning of the frame, the pointer is set to the first block of the reduced current frame (step S203), and the first stage motion search using the reduced data is started. . First, the matching unit extraction unit 211 of the first-stage motion search processing unit 104 extracts a predetermined matching unit (N blocks in the horizontal direction × M blocks in the vertical direction) composed of a plurality of blocks (step S204). Here, N and M are integers of 1 or more.
[0026]
Subsequently, the matching operation processing unit 212 performs a motion vector search on the reduced image using the extracted N × M block area as a matching unit (step S205), and performs a search on the reduced image of the current frame and the reduced image of the reference frame. The position where the correlation is highest between is determined. When the search for the first block is completed, the pointer is moved to an adjacent block that has not been searched yet (step S206), and the same motion vector search is performed until the search is completed for all blocks in the frame. It repeats (step S207). In the first-stage search, since a collective search is performed using the N × M block area as a matching unit, one motion vector is detected not for each block but for each N × M block.
[0027]
When the first-stage motion vector search ends (YES in step S207), the second-stage motion search processing unit 105 sets the pointer to the first block of the current frame (step S208). Then, the motion vector search is started at the original image resolution centering on the motion vector determined in the first stage search. That is, in the second-stage motion search, a matching process is performed using one block as a matching unit centering on the position obtained as a result of the first-stage motion search (step S209). When the search for the first block is completed, the pointer is moved to the next block (step S210), and the second-stage motion search is sequentially executed until the search for all blocks is completed (steps S209 to S211). If the search has been completed for all the blocks in the frame, the second-stage search is completed (YES in step S211), and the position determined to have the largest correlation is set as the final motion vector.
[0028]
The first-stage motion vector search in the above-described first embodiment is executed using, as a matching unit, pixel data including N blocks adjacent in the horizontal direction and M blocks adjacent in the vertical direction. Therefore, the number of detected motion vectors can be reduced, and as a result, the amount of calculation required for search is reduced, and the speed of motion vector search is increased.
[0029]
In the first-stage motion search processing unit 104, as described above, since the collective search is performed using the N × M block area as a matching unit, the same motion vector is used for N × M blocks. In the second embodiment of the present invention described below, it is possible to minimize a decrease in search accuracy by changing the matching unit according to the motion of the image.
[0030]
FIG. 3 is a block diagram showing a second embodiment of the motion vector search device according to the present invention. In FIG. 3, blocks having the same functions as those in the first embodiment shown in FIG. 1 are denoted by the same reference numerals, and description thereof will be omitted. In the second embodiment, the configuration and operation of the first-stage motion search processing unit 304 are different from those of the first embodiment. Therefore, the first-stage motion search processing unit 304 will be described below.
[0031]
As shown in FIG. 3, the first-stage motion search processing unit 304 in the second embodiment includes a motion complexity determination unit 314, a matching unit determination unit 315, a matching unit extraction unit 316, and a matching calculation processing unit 317. Have been.
[0032]
The motion complexity determining unit 314 inputs the reduced current frame data and the reduced reference frame data from the sub-sampling processing unit 103, and determines the complexity of the motion based on statistical information of past motion vectors, the magnitude of prediction error, and the like. I do. For example, if the directions of the vectors do not match in a plurality of neighboring blocks for which a motion vector has already been obtained, that is, if the motion vectors point in different directions, it is determined that the motion is complicated. The motion complexity may be determined by quantifying the degree of coincidence of the directions of the motion vectors in a plurality of neighboring blocks (eg, deviation of the direction distribution).
[0033]
The matching unit determination unit 315 changes the matching unit according to the determined complexity of the motion. Specifically, when it is determined that the movement is complicated, the matching unit is reduced. This makes it possible to cope with complicated movements. If the motion is determined to be monotonous, the matching unit is increased. As a result, the amount of calculation required for the search can be reduced.
[0034]
The matching unit extraction unit 316 extracts the determined matching unit, and then, as described above, the matching calculation processing unit 317 executes the matching process on the extracted matching unit.
[0035]
FIG. 4 is a flowchart showing the overall operation of the second embodiment. First, the reduction processing unit 111 inputs the current frame data to be encoded from the current frame buffer 101 and performs sub-sampling (step S401). Similarly, the reduction processing unit 111 inputs the reference frame data from the reference frame buffer 102 and performs sub-sampling (step S402).
[0036]
Next, in order to start the first stage search processing from the beginning of the frame, the pointer is set to the first block of the reduced current frame (step S403), and the first stage motion search using the reduced data is started. . First, the motion complexity determination unit 314 determines the complexity of the motion based on the past motion vector statistical information, the magnitude of the prediction error, and the like (step S404), and the matching unit determination unit 315 determines the complexity of the determined motion. The size of the matching unit is determined accordingly (step S405).
[0037]
Specifically, the matching unit (N blocks in the horizontal direction × M blocks in the vertical direction) becomes smaller where the motion complexity is relatively large, and the matching unit is smaller where the motion complexity is relatively small (where the motion is monotonous). For example, the values of N and M are determined in advance and stored in a table so as to increase. The matching unit extraction unit 211 extracts a matching unit according to the determined size of the matching unit (step S406).
[0038]
Subsequently, the matching calculation processing unit 317 performs a motion vector search on the reduced image using the extracted N × M block area as a matching unit (step S407), and performs a search on the reduced image of the current frame and the reduced image of the reference frame. The position where the correlation is highest between is determined. When the search for the first block is completed, the pointer is moved to an adjacent block that has not been searched yet (step S408), and the same motion vector search (step S408) is performed until the search is completed for all the blocks in the frame. Steps S404 to S408) are repeated (step S409). In the first-stage search, since the N × M block area is searched collectively using the matching unit as the matching unit, the first-stage search result is the same motion vector for N × M blocks.
[0039]
When the first-stage motion vector search ends (YES in step S409), the second-stage motion search processing unit 105 sets the pointer to the first block of the current frame (step S410). Then, matching processing is performed using one block as a matching unit with the motion vector determined in the first stage search as a center (step S411). When the search for the first block is completed, the pointer is moved to the next block (step S412), and the second-stage motion search is sequentially executed until the search for all blocks is completed (steps S411 to S412). If the search has been completed for all blocks in the frame, the search in the second stage is completed (YES in step S413), and the position determined to have the largest correlation is set as the final motion vector.
[0040]
As described above, a search is performed in a small matching unit in a place where a motion is complicated, and a search is performed in a large matching unit in a place where a motion is monotonous. Therefore, a decrease in search accuracy is reduced, and a high-speed motion vector search becomes possible. .
[0041]
【Example】
Next, the motion vector search method according to the present invention will be described with a specific example in which a moving image having 720 pixels in the horizontal direction and 480 pixels in the vertical direction is encoded.
[0042]
It is assumed that the encoding method adopts a method in which 16 pixels in the horizontal direction and 16 pixels in the vertical direction are treated as one block and a motion vector is assigned to each block. X It is assumed that one block is set in the vertical direction.
[0043]
FIG. 5 is a schematic flowchart for explaining one embodiment of the motion vector search method according to the present invention. First, original frame data 501 of 720 horizontal pixels × 480 vertical pixels is sub-sampled at a predetermined reduction ratio (here, 1/2 in the horizontal and vertical directions) to generate reduced frame data 502 of 360 horizontal pixels × 240 vertical pixels. I do. At this time, the size of one block is 8 horizontal pixels × 8 vertical pixels.
[0044]
Using the reduced frame data 502, the first-stage multiple block collective search is performed using a size of 16 horizontal pixels × 8 vertical pixels, which is equivalent to two 8 × 8 blocks in the horizontal direction, as a matching unit. As described above, in each block, all points within the search range specified in advance are searched to find a position where the correlation becomes maximum. Here, it is assumed that the first-stage search has specified a motion vector (−6, 3) of 6 pixels (−6) left and 3 pixels below the search center.
[0045]
Next, the pixel positions of the search result obtained in the first-stage search are mapped to the pixel positions of the original resolution. Here, it is mapped to a position (-12, 6) doubled in the horizontal and vertical directions. The mapped position (−12, 6) and its surroundings are searched using one block (16 × 16) as a matching unit. That is, for each of the two blocks that have been collectively searched for in the first stage, the second stage search is performed based on (-12, 6). As described above, the search result of the first stage is the same for two adjacent blocks, but since the search of the second stage is performed for each block, the motion vector finally obtained is a block. Will be different for each.
[0046]
By performing the motion vector search in this way, it is possible to detect a motion vector at higher speed and with higher accuracy than a normal search.
[0047]
FIG. 6 is a block diagram showing a computer system which is another embodiment of the motion vector search device according to the present invention. This computer system is equipped with a program control processor 601. The program control processor 601 includes, in addition to the current frame buffer 611 and the reference frame buffer 612, a program memory 602 storing necessary programs, a reduced frame buffer 603 including a reduced current frame buffer 613 and a reduced reference frame buffer 614, Is connected.
[0048]
In the program memory 602, in addition to the main program for executing the motion vector search according to the present invention, the above-described reduction processing unit 615, matching unit extraction processing unit 616, and first-stage motion search processing unit that searches a plurality of blocks collectively 617, a program module that functionally implements a second-stage motion search processing unit 618 that performs a search for each block is stored. The program memory 602 further stores a motion complexity determining unit and a matching unit determining unit, and can implement the second embodiment of the present invention. When the main program and each functional module are executed by the program control processor 601, the motion vector search according to the present invention is executed.
[0049]
【The invention's effect】
As described above, the motion vector search method and apparatus according to the present invention perform a collective search for a plurality of adjacent blocks when performing the first search by performing subsampling. With this configuration, the amount of calculation is reduced, and the speed of motion vector search can be increased. Further, in the second search, a search is performed for each block, so that a decrease in the accuracy of the motion vector search can be minimized.
[0050]
Furthermore, since a plurality of adjacent blocks are searched collectively when the first search is executed, a difference between motion vectors of adjacent blocks is reduced. For this reason, it is possible to reduce the code amount required for coding the motion vector, and it is possible to allocate a larger code amount for coding the block data. Therefore, a slight decrease in search accuracy is found in the motion vector search, but a decrease in image quality can be minimized.
[0051]
Further, according to the present invention, in the first search, the matching unit can be changed according to the complexity of the motion. For this reason, it is possible to perform an appropriate search according to the motion, for example, by reducing the matching unit in a place where the motion is complicated, and to increase the unit in a case where the motion is monotonous. It is possible to search for a suitable motion vector.
[Brief description of the drawings]
FIG. 1 is a block diagram showing a first embodiment of a motion vector search device according to the present invention.
FIG. 2 is a flowchart showing an overall operation of the first embodiment.
FIG. 3 is a block diagram showing a second embodiment of the motion vector search device according to the present invention.
FIG. 4 is a flowchart showing an overall operation of the second embodiment.
FIG. 5 is a schematic flowchart for explaining one embodiment of a motion vector search method according to the present invention.
FIG. 6 is a block diagram showing a computer system which is another embodiment of the motion vector search device according to the present invention.
FIG. 7A is a schematic diagram showing a pixel array for explaining a general multi-stage search method, and FIG. 7B is a sequence diagram showing a state of a second-stage search.
[Explanation of symbols]
101 Current frame buffer 102 Reference frame buffer 103 Sub-sampling processing unit 104 First-stage motion search processing unit 105 Second-stage motion search processing unit 111 Reduction processing unit 112 Reduced current frame buffer 113 Reduced reference frame buffer 114 Matching unit extraction unit 115 Matching Arithmetic processing unit 314 Motion complexity degree determination unit 315 Matching unit determination unit 316 Matching unit extraction unit 317 Matching arithmetic processing unit 601 Program control processor 602 Program memory 603 Reduced frame buffer 611 Current frame buffer 612 Reference frame buffer 613 Reduced current frame buffer 614 Reduced reference frame buffer 615 Reduction processing 616 Matching unit extraction 617 First-stage search with multiple blocks 618 Second-stage search for each block Rope

Claims (8)

In an apparatus for searching for a motion vector in video coding,
Image reduction means for reducing the vertical direction and the horizontal direction of the target image and the reference image to generate a reduction target image and a reduced reference image, respectively;
A first search unit that searches for a first motion vector in a search unit including a plurality of adjacent blocks based on the reduction target image and the reduced reference image;
A second search unit that searches for a second motion vector in block units based on the image resolution before the reduction in the search range determined by the first motion vector and determines the motion vector;
A motion vector search device comprising: The first search means further comprises:
Motion complexity determining means for determining the complexity of the motion of the moving image;
A search unit determining unit that changes a size of the search unit according to the motion complexity;
2. The motion vector search device according to claim 1, comprising: In a method of searching for a motion vector in video coding,
Reduce the vertical and horizontal directions of the target image and the reference image to generate a reduction target image and a reduced reference image, respectively,
A first motion vector is searched for in a search unit including a plurality of adjacent blocks based on the reduced target image and the reduced reference image,
Within the search range determined by the first motion vector, the motion vector is determined by searching for a second motion vector in block units based on the image resolution before the reduction.
A motion vector search method, characterized in that: 4. The motion vector search method according to claim 3, wherein the size of the search unit is changed according to the complexity of the motion of the moving image. In a computer system that executes a motion vector search in encoding of a moving image,
A target image buffer for storing target image data;
A reference image buffer for storing the reference image;
A memory for storing a program consisting of instructions for causing a computer to execute a motion vector search in video encoding,
A program control processor that executes the program;
And the program comprises at least:
An image reduction unit that reduces the target image and the reference image, and generates a reduction target image and a reduced reference image, respectively;
A first search unit that searches a plurality of adjacent blocks at a time as a search unit when searching for a first motion vector based on the reduction target image and the reduced reference image;
A second search unit that searches for a second motion vector for each block based on the image resolution before reduction within the search range of the position determined by the first motion vector to determine the motion vector;
A computer system comprising: The computer system according to claim 5, wherein the number of blocks in the search unit is increased or decreased according to the complexity of the motion of the moving image. A computer program comprising instructions for causing a computer to execute a motion vector search in encoding of a moving image,
Generating a reduced target image and a reduced reference image by reducing the vertical direction and the horizontal direction of the target image and the reference image, respectively;
A first search step of searching for a first motion vector in search units consisting of a plurality of adjacent blocks based on the reduction target image and the reduced reference image;
A second search step of determining the motion vector by searching a second motion vector for each block in the search range determined by the first motion vector with the image resolution before the reduction,
A computer program comprising: 8. The computer program according to claim 7, wherein the number of blocks in the search unit is increased or decreased according to the complexity of the motion of the moving image.

Images