JP3189655B2 - Apparatus and method for detecting motion vector - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

[0001] 1. Field of the Invention [0002] The present invention relates to a motion vector detecting apparatus and method for use in motion compensated predictive coding, which is a technique for compressing digital moving images.

[0002]

2. Description of the Related Art A block matching method is generally used for detecting a motion vector. As shown in FIG. 15, the block matching method
This is a method of detecting a candidate vector having the highest correlation from a plurality of candidate vectors by performing pattern matching on one block. In the motion vector detection used in the motion compensation prediction coding, each image frame of a digital moving image including a plurality of continuous frames is divided into a plurality of blocks including a plurality of pixels, and a target frame including a target image 156 to be coded. The best match block 152 having the highest correlation with the target image 156 is detected from the search range image 154 of the search frame 153 different from 155, and the difference between its coordinate position and the coordinate position of the target image is detected as the motion vector 151. are doing. Generally, a square error or an absolute value error is used as an evaluation value of the degree of correlation.

When searching for a motion vector using the block matching method, there are roughly two types. The sub-sampling method of sub-sampling both the search range image and the target image to reduce candidate vectors, and the full search method of searching for all candidate vectors in the search range without sub-sampling both the search range image and the target image is there.

In the case of the sub-sampling method, as disclosed in Japanese Patent Application Laid-Open No. Hei 5-49023, both the search range and the target image are sub-sampled, and the detection accuracy is reduced. The detection accuracy has been improved.

Further, as disclosed in Japanese Patent Application Laid-Open No. 5-49023, when detecting a motion vector with an accuracy higher than one pixel accuracy, it is necessary to search in more stages.

Further, in the case of the full search method, it is necessary to store the entire search range in the search range memory, and a memory capacity several times to several tens times that of the target image is required.

[0007]

In the conventional motion vector detection, in the case of a sub-sample, it is necessary to perform a multi-step search in order to increase the detection accuracy. In the case of a full search, the memory for storing the search range becomes large.

The first object of the present invention is to solve the above-described problem. The first object of the present invention is to perform sub-sampling on a block image in a search range, but to perform a motion without deteriorating detection accuracy in a one-step search. An object of the present invention is to provide a motion vector detecting device and a method for detecting a vector.

A second object of the present invention is to provide a motion vector detecting apparatus for detecting a motion vector without lowering the detection accuracy in a one-step search even when detecting a motion vector with an accuracy higher than one pixel accuracy. It is to provide the method.

A third object of the present invention is to provide a motion vector detecting device which realizes the saving of the search range memory while detecting the same number of candidate vectors as in the full search method by one-step search. It is in.

[0011]

According to the first aspect of the present invention, in a motion vector detecting apparatus using a block matching method in the case of compressing a digital moving image by motion compensated predictive coding, a search range image is horizontally or vertically shifted. A sub-sampling unit that performs sub-sampling in at least one of the directions, and a calculation of a degree of correlation of a corresponding one pixel pair between the sub-sampled image output from the sub-sampled unit and the target image. And a vector detection unit that detects a motion vector from the correlation degree output from the correlation degree calculation unit.

According to a second aspect of the present invention, in the first aspect of the present invention, the image processing apparatus further comprises an interpolation section for interpolating the target image, wherein the correlation degree calculating section includes a sub-sample image output from the sub-sample section and the It is configured to calculate the degree of correlation with the interpolated image output by the interpolating unit with an accuracy smaller than one pixel.

According to a third aspect of the present invention, in the first aspect of the present invention, the apparatus further comprises a search range memory for storing an output of the sub-sampling section, and a target image memory for storing a target image. The unit is configured to calculate the degree of correlation between the output of the search range memory and the output of the target image memory for each pixel.

According to a fifth aspect of the present invention, in the motion vector detecting method using the block matching method in the case where the digital moving image is compressed by the motion compensated predictive coding, the search range image is displayed in at least one of the horizontal direction and the vertical direction. A sub-sampling step for sub-sampling and a corresponding one of the output of the sub-sampling step and the target image
The method includes a correlation calculation step for calculating a correlation between pixel pairs, and a vector detection step for detecting a motion vector from the correlation output from the correlation calculation.

According to a sixth aspect of the present invention, in the fifth aspect of the present invention, there is provided an interpolation step of interpolating a target image, wherein the correlation degree calculating step includes an output of the sub-sampling step and an output of the interpolation step. Is calculated with an accuracy smaller than one pixel.

According to the first or fifth aspect of the present invention, only the search range image is sub-sampled and the target image is not sub-sampled, thereby reducing the number of matchings per block and reducing the number of operations. Can be reduced. In the case of the sub-sampling method in the conventional example, when the search range image and the target image are sub-sampled to １ ／, the target image searches the search range every two pixels, so that the search accuracy is reduced. When the calculation is performed with one-pixel accuracy, it is necessary to perform a one-pixel accuracy search separately, and the processing becomes complicated. However, in the motion vector search method of the present invention, since the non-subsampled target image searches the subsampled search range for each pixel, the search accuracy is not reduced and the complexity of searching in multiple stages is also eliminated.

Further, according to the present invention of claim 2 or 6, when detecting a motion vector with an accuracy smaller than one pixel accuracy, only the search range image is subsampled and the target image is interpolated. However, the conventional sub-sampling method requires a further search in addition to the detection of one-pixel accuracy. However, a search in only one stage can detect a motion vector with an accuracy smaller than one-pixel accuracy.

Further, according to the present invention, when a local buffer is provided between a main memory for storing frame data and a motion vector detecting device, a search range of several to several tens times the number of pixels of a target image is provided. By sub-sampling, the capacity of the local buffer memory for storing the search range can be significantly reduced.

[0019]

FIG. 1 is a block diagram showing a first embodiment of the present invention. Here, the target image Mh × Mv =
For 4 × 4 pixels, the search range is ± 4 pixels in both the vertical and horizontal directions, and the search range is 1 / Lh = 1 / Lv = 1/2 subsampled both horizontally and vertically.
It is assumed that a motion vector is realized with pixel accuracy. In the present invention, no sub-sampling is performed on the target image.

The outline of the present embodiment will be described with reference to the flowchart of the processing shown in FIG. First, in step 1, the entire search range image 12 × 12 pixels (both ● and ○) shown in FIG.
Generate pixels (only ●). Subsequently, in step 2, the degree of correlation between the subsampled image 6 × 6 pixels and the target image 4 × 4 pixels shown in FIG. 3A is calculated. At this time, the target image is scanned one pixel at a time in the search range before sub-sampling to calculate the degree of correlation. In step 3, the difference between the coordinate position of the search range determined to have the highest correlation with the target image from the correlation calculated in step 2 and the coordinate position of the target image is detected as a motion vector.

In FIG. 1, reference numeral 11 denotes an image storage unit storing image data composed of a plurality of frames, 12 denotes a sub-sampler for sub-sampling the search range image in both horizontal and vertical directions, and 13 denotes a sub-sampler. A correlation calculation unit that calculates the correlation between the sub-sample image in the search range output from 12 and the target image, and a coordinate position of the search range having the highest correlation from the correlation calculated by the correlation calculation unit 13 and the target position. And a vector detection unit that outputs a difference from the coordinate position of the image as a motion vector.

As shown in FIG. 3B, the sub-sampling unit 12 sub-samples both the horizontal and vertical halves from the input image of the search range image of 12 × 12 pixels (both ● and ○). Is a circuit for generating a sub-sampled image of 6 × 6 pixels (marked by ●).

As shown in FIG. 4, the correlation degree calculator 13 calculates
4 ((Mh × Mv) / (Lh × Lv) = (4 × 4) / (2 ×
2) computing unit units 41 to 44.
Each computing unit performs computation of the degree of correlation of a corresponding one pixel pair between the sub-sampled image and the target image. Then, the adders 45 add the correlation degrees calculated by the four operation unit units 41 to 44 and output the result to the vector detection unit 14.

As shown in FIG. 5, the arithmetic unit units 41 to 44 store four target images (Lh × Lv = 2 × 2).
) Target image registers 51 to 54 and the register 5
Target image selector 55 for selecting one of the outputs 1 to 54
And a correlation degree calculator 56 for calculating the degree of correlation between the search range image and the target image by performing the absolute value of the difference,
The result of the correlation degree calculator 56 is output to the adder 45.

The detailed operation of the correlation calculating section 13 of this embodiment will be described with reference to FIGS. The target image groups a, b, c, and d in FIG. 6 are composed of four pixels in the target image in FIG. 3, the target image group a is indicated by a triangle, the target image group b is indicated by a triangle, and the target image group c. Is indicated by □, and the target image group d is indicated by Δ.

First, FIG. 6A shows the operation in the first cycle, in which α1, α of the target image group a (marked by Δ)
4, γ1, γ3 and search range images A1, A3, C
Block matching with the four pixels 1 and 3 is performed. This operation is performed in the first cycle of the timing chart of FIG.
Can be confirmed by referring to FIG. That is, in the first cycle, block matching with the target image group a is performed. At that time, the arithmetic unit 41 calculates the absolute value of the difference between the target image α1 and the search range image A1, and the arithmetic unit 42 sets the target image α3 The arithmetic unit 43 calculates the absolute value of the difference between the target image γ1 and the search range image C1, and the arithmetic unit 44 calculates the difference absolute value between the target image γ3 and the search range image C3. Calculate the absolute value. After that, the four difference absolute values calculated by the arithmetic units 41 to 44 are added by the adder 45 and output to the vector detection unit 14 as a correlation value.

In the second cycle, as shown in FIGS. 6B and 7, α2, α4, γ of the target image group b (marked by ▽)
2, 4 pixels and search range images A3, A5, C3, C
The absolute value of the difference from the four pixels of 5 is calculated, added by the adder 45, and output to the vector detection unit 14 as a correlation value.

Thereafter, the operation is performed in accordance with the timing chart of FIG.
Up to the cycle, the target image group c is used in the even cycle, and the target image group d is used in the odd cycle.
Then, the correlation value is calculated as shown in FIG. The vector detection unit 14 detects the coordinate position having the highest correlation degree (in the case of the minimum value in this embodiment) from the 81 correlation values calculated by the correlation degree calculation unit 13, and determines the coordinate position of the search range. The difference from the coordinate position of the target image is output as a motion vector. In the present embodiment, the target image registers 51 and 52 in the arithmetic unit 41 of FIG.
The target images α1, α2, β1,
β2 is stored. Similarly, target images α3, α4, β3, and β4 are stored in target image registers 51, 52, 53, and 54 in the operation unit 42, and target images are stored in target image registers 51, 52, 53, and 54 in the operation unit 43. Image γ
1, γ2, δ1, δ2 are stored in the target image registers 51, 52, 53, 54 in the arithmetic unit 44, respectively.
3, γ4, δ3, δ4 are stored respectively.

Next, a comparison is made of the number of operations between the conventional search method and the search method of the present invention. In the case where a search is performed on the entire search range image without a subsample, the following equation (1) is obtained.
(Equation 2) and the number of operations is reduced to 1/4.

[0030]

(Equation 1)

[0031]

(Equation 2)

In the conventional search using sub-samples, the number of operations becomes (Equation 3), and the number of operations is further reduced than in the present invention. It is necessary to read the peripheral pixels from the image storage unit again and calculate with one pixel accuracy.

[0033]

(Equation 3)

In the first embodiment of the present invention, the subsamples are set to 1 / Lh = 1 / Lv = 1/2 in both the horizontal and vertical directions, but Lh is a natural number of 1 to Mh, and Lv is 1 to Mh.
If L is a natural number equal to or less than v, there is no problem even if Lh and Lv are independently set.

FIG. 8 is a block diagram showing a second embodiment of the present invention. The case where the sub-sample image and the target image are the same as in FIG. 3 will be considered.

The outline of the present embodiment will be described with reference to the flowchart of the processing shown in FIG. First, in step 1, the entire search range image 12 × 12 pixels (both ● and ○) shown in FIG.
At the same time as generating the pixel (only ●), the target image of FIG. 3A is interpolated as shown in FIG. 10 to generate an interpolated pixel (x mark). Subsequently, in step 2, the subsample image 6 ×
The degree of correlation between 6 pixels and 8 × 8 pixels of the interpolated target image shown in FIG. 10 is calculated. At this time, the target image is scanned by 0.5 pixels at a time in the search range before sub-sampling to calculate the degree of correlation. In step 3, the difference between the coordinate position of the search range determined to have the highest correlation with the target image from the correlation calculated in step 2 and the coordinate position of the target image is detected as a motion vector.

In FIG. 8, reference numeral 81 denotes an interpolator for generating an interpolated image from the target image. The interpolator 81 outputs the target image and the interpolated pixels shown in FIG. Other components are the same as those in FIG.

The detailed operation of the correlation calculating section 13 of this embodiment will be described with reference to FIGS.

The target image groups a, ha, b,
hb is composed of four pixels in the interpolated target image of FIG. 10, the target image group a is indicated by a triangle, the target image group ha is indicated by an interpolated pixel x, and the target image group b is indicated by a triangle.
The mark and the target image group hb are indicated by interpolation pixels × marks.

First, FIG. 11A shows the operation in the first cycle, in which α1, α of the target image group a (△)
3, γ1, and γ3 pixels and search range images A1, A3, and C
Block matching with the four pixels 1 and 3 is performed. This operation is the same as in FIGS. 6 and 7 of the first embodiment.

In the second cycle, as shown in FIGS. 11B and 12, the absolute difference between the four interpolated pixels of the target image group ha (marked by x) and the four pixels of the search range images A3, A5, C3, C5 is obtained. The value is calculated, added by an adder 45, and output to the vector detection unit 14 as a correlation value.

Then, the operation is performed according to the timing chart of FIG. 12 until the 17th cycle, and the same operation is performed after the 18th cycle to calculate the correlation value. Vector detector 14
Detects the coordinate position having the highest correlation degree (in the case of the minimum value in the present embodiment) from the correlation values calculated by the correlation degree calculation unit 13, and determines the coordinate position between the coordinate position of the search range and the coordinate position of the target image. The difference is output as a motion vector.

FIG. 13 is a block diagram showing a third embodiment of the present invention. The case where the sub-sample image and the target image are the same as in FIG. 3 will be considered. Reference numeral 131 denotes a search range memory for storing a sub-sampled image, and 132 a target image memory for storing a target image memory. Other components are the same as those in FIG.

The search range memory 131 stores 6 × 6 sub-sample images (marked by ●). Target image memory 13
2 stores 4 × 4 pixels of the target image. As shown in FIG. 14, both the search range memory 131 and the target image memory 132 are buffer memories 1 to facilitate real-time processing.
41 and a buffer memory 142. When the buffer memory 141 receives an image, the buffer memory 142 outputs an image.
When the image input is 42, the memory selectors 143 and 144 operate so that the buffer memory 141 outputs the image.

The detailed operation of the correlation degree calculating section 13 of this embodiment is the same as that of the first embodiment described with reference to FIGS.

As in the first embodiment, the motion vector can be detected by directly accessing the image storage unit 11 storing a plurality of frames. However, in general, the image storage unit 11 for storing a large amount of images has a low transfer speed and performs a plurality of trials with a target of realizing high coding efficiency especially in motion compensation prediction coding. To make a selection, the data is accessed multiple times. Therefore, it is common practice to temporarily store the image data in the image storage unit 11 in a small-capacity local buffer capable of high-speed transfer.

However, the local buffer typified by the search range memory 131 in the third embodiment is, in the case of FIG.
Double, three times in the vertical direction, and nine times the capacity is required. In the case of the moving image compression standard MPEG, the search range can be extended to 25 times, 49 times, or more than the target image block in order to improve the image quality. As described above, the search range memory 131 for temporarily storing the search range image requires a large capacity. Furthermore, as in the present embodiment, when the search range memory 131 has a double buffer configuration in order to easily realize real-time processing, the memory capacity further increases.

For this reason, subsampling the search range as in the present invention makes it possible to reduce the capacity of the search range memory to 1/4 in the present embodiment, and to maintain the local buffer while maintaining the detection accuracy. Capacity can be reduced.

In the example of the present embodiment, in the search range memory and the target image memory, the target image (4 × 4 pixels) to be subjected to block matching and the search range image (6
(× 6 pixels) only, but there is no problem even if frame data for one screen or a plurality of frames is stored.

Although the search range memory and the target image memory of the present embodiment have a double buffer configuration to facilitate real-time processing, a single buffer configuration does not pose any problem. Further, there is no problem even in the configuration in which the interpolation unit shown in the second embodiment is added to the present embodiment.

[0051]

According to the motion vector detecting device of the present invention, only the search range image is sub-sampled and the target image is not sub-sampled. × Lv), and the processing complexity of the sub-sampling method that requires a multi-step search can be reduced. Here, Lh and Lv indicate the number of subsamples in the horizontal and vertical directions, respectively.

In the motion vector detecting method according to the fifth aspect, only the search range image is sub-sampled, and the sub-sample is not performed on the target image, so that the number of matchings per block can be reduced and the number of operations can be reduced. Therefore, high-speed processing of motion vector detection can be realized, and detection accuracy can be maintained.

The motion vector detecting device according to claim 2 is
When a motion vector with an accuracy smaller than one pixel accuracy is detected by sub-sampling only the search range image and performing interpolation on the target image, the number of operation unit is 1 / (Lh × Lv) in the case of full search. ), And the complexity of the process by the multi-step search can be reduced for both the full search method and the sub-sample method.

According to a sixth aspect of the present invention, in the motion vector detecting method,
By sub-sampling only the search range image and performing interpolation on the target image, if a conventional sub-sampling method detects a motion vector with an accuracy smaller than one pixel accuracy, a sub-sample search, one-pixel accuracy search, 0.5 Although the search in three stages of the pixel accuracy search is necessary, a motion vector with an accuracy smaller than one pixel accuracy can be detected by the search in only one stage.

According to a third aspect of the present invention,
Since the search range memory can be reduced by subsampling the search range image, the memory capacity of the local memory can be significantly reduced while maintaining the detection accuracy.

The motion vector detecting device according to claim 4 is
When performing interpolation with respect to the target image and performing detection with an accuracy smaller than one pixel accuracy, the search range memory can be reduced by subsampling the search range image, so that the detection accuracy is improved and the memory capacity of the local memory is significantly increased. Reduction can be realized.

[Brief description of the drawings]

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

FIG. 2 is a processing flowchart of a motion vector detection method according to the embodiment;

FIG. 3 is a diagram illustrating a subsample according to the present invention.

FIG. 4 is a detailed block diagram of a correlation degree calculation unit in FIG. 1;

FIG. 5 is a detailed block diagram of a computing unit in the correlation calculating section of FIG. 4;

FIG. 6 is a view for explaining a motion vector detection method according to the first embodiment of the present invention.

FIG. 7 is a timing chart for explaining a motion vector detection method according to the embodiment;

FIG. 8 is a configuration block diagram of a motion vector detection method according to a second embodiment of the present invention;

FIG. 9 is a processing flowchart of a motion vector detection method according to the embodiment;

FIG. 10 is an exemplary view for explaining interpolation of a target image according to the embodiment;

FIG. 11 is an exemplary view for explaining a motion vector detection method according to the embodiment.

FIG. 12 is a timing chart for explaining a motion vector detection method according to the embodiment;

FIG. 13 is a configuration block diagram of a motion vector detection method according to a third embodiment of the present invention.

FIG. 14 is a detailed block diagram of a search range memory and a target image memory of FIG. 13;

FIG. 15 is a view for explaining motion vector detection by a block matching method;

[Explanation of symbols]

 Reference Signs List 11 image storage unit 12 sub-sampling unit 13 correlation degree calculation unit 14 vector detection unit 41, 42, 43, 44 arithmetic unit 45 adder 51, 52, 53, 54 target image register 55 target image selector 56 correlation degree arithmetic unit 81 Interpolator 131 Search range memory 132 Target image memory 141, 142 Buffer memory 143, 144 Memory selector

──────────────────────────────────────────────────続 き Continuation of the front page (56) References JP-A-55-158784 (JP, A) JP-A-5-49023 (JP, A) JP-A-6-181568 (JP, A) JP-A-6-181568 189296 (JP, A) JP-A-6-225289 (JP, A) JP-A-7-95589 (JP, A) JP-A-7-240927 (JP, A) (58) Fields investigated (Int. Cl. ⁷ , DB name) H03M 7/36

Claims (6)

(57) [Claims] 1. A sub-sampler for sub-sampling a search range image in at least one of a horizontal direction and a vertical direction in a motion vector detecting apparatus using a block matching method for compressing a digital moving image by motion compensation predictive coding. A correlation calculation unit that calculates a correlation between a pair of pixels corresponding to a sub-sample image output from the sub-sample unit and a target image; and a motion vector based on the correlation output from the correlation calculation. A motion vector detecting device comprising: a vector detecting unit for detecting a motion vector. 2. An interpolator for interpolating a target image, wherein the correlation calculator calculates a correlation between a subsampled image output from the subsampler and an interpolated image output from the interpolator by one pixel. 2. The motion vector detecting device according to claim 1, wherein the motion vector is calculated with smaller accuracy. 3. A search range memory for storing an output of the sub-sampling section, and a target image memory for storing a target image, wherein the correlation degree calculating section stores the output of the search range memory and the target image memory. 2. The motion vector detecting apparatus according to claim 1, wherein the degree of correlation with the output is calculated for each pixel. 4. A sub-sampler for sub-sampling a search range image in at least one of a horizontal direction and a vertical direction in a motion vector detecting apparatus using a block matching method for compressing a digital moving image by motion compensation predictive coding. Unit, an interpolation unit that interpolates the target image, a search range memory that stores the output of the subsample unit, a target image memory that stores the output of the interpolation unit, an output of the search range memory, and the target image A motion vector detection device, comprising: a correlation calculation unit that calculates a correlation with an output of a memory with an accuracy smaller than one pixel; and a vector detection unit that detects a motion vector from the correlation output from the correlation calculation. . 5. A sub-sample for sub-sampling a search range image in at least one of a horizontal direction and a vertical direction in a motion vector detecting method using a block matching method in a case where a digital moving image is compressed by motion compensated predictive coding. Step, and the correspondence between the output of the sub-sample step and the target image .
A motion vector detection method comprising: a correlation degree calculation step of calculating a correlation degree of one pixel pair; and a vector detection step of detecting a motion vector from the correlation degree output from the correlation degree calculation step. 6. An interpolation step for interpolating a target image,
6. The motion vector detection method according to claim 5, wherein the correlation degree calculating step calculates a correlation degree between the output of the sub-sampling step and the output of the interpolation step with an accuracy smaller than one pixel.