JPH104555A - Motion vector detector - Google Patents

Abstract

PROBLEM TO BE SOLVED: To reduce an arithmetic quantity required for vector detection and to improve the detection accuracy by placing a heavier weight onto an evaluation value of a vector detection object picture element more than the weight of the evaluation value of picture elements around the object. SOLUTION: Current frame data are distributed into three systems, data of a vector detection object picture element are written as they are in a memory 106 as Xm, n, data of four picture elements located upper/lower/left/right of the object picture element are averaged by a mean value calculation device 102 and the resulting data are written in the memory 106 as Xm, n', data of four picture elements located in oblique directions of the object picture element are processed by the mean value calculation device 103 and the resulting data are written in the memory 106 as Xm, n". Evaluation computing elements 108-110 obtain differential absolute values of data of each group, multiply coefficients α, β, γ, outputs of them are added by an adder 111 and the sum is used for an evaluation value to a trial vector.

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 apparatus for detecting a motion compensation vector in moving picture compression, and more particularly, to a motion compensation in pixel unit for motion estimation between motion compensated inter-frame prediction and frame interpolation. It relates to a vector detection device.

[0002]

2. Description of the Related Art JPEG (Jo
int Photograghic Expert Group) or MPEG (Moving
Picture Expert Group).

[0003] MPEG is MPEGI, MPEGII, M
Three levels of PEGIV standards are being considered. MPE
The purpose of GI is to compress moving images that can be transmitted through a 1.5 Mbps communication line, and is considered to be mainly used for videophones, videoconferencing, and the like. In MPEGI, the current NTSC video image is 320 × 240
Treat as pixel resolution and make up one frame 2
Data of only one of the fields is used.
MPEG II aims at compression that can be transmitted over a communication line exceeding 10 Mbps, and targets moving picture transmission by ISDN or the like and digital video. MPEG IV is intended for low bit rates.

The feature of MPEG is that DCT (Discrete Cos
ine Transform (discrete cosine transform) is to perform inter-frame prediction processing for compression in the time axis direction in addition to still image compression, but random access to frames is required as a precondition for moving image compression, and fast forward. Playback and rewind playback (reverse direction). Therefore, inter-frame prediction in MPEG employs both forward and backward directions. MP
Even in EG, basically MC (motion compensation) + DCT
Is used. The block size for motion compensation is 16 × 1
6 (however, there is also an 8 × 8 mode), DCT is performed on 8 × 8 blocks. This motion compensation is performed with half-pixel accuracy. Motion compensation with half-pixel accuracy is performed not only by examining a position shifted in pixel units on a reference frame used for prediction, but also by generating a position between pixels by interpolation and performing matching.

[0005] In a moving image compression apparatus that involves prediction in the time direction, prediction is performed by motion compensation in order to reduce a reduction in prediction efficiency due to movement of a camera PAN or a subject. This motion compensation detects a motion vector of a target region between a frame of interest (encoding target frame) and a reference frame (for example, a previous frame), and sets a position shifted by the motion vector in the reference frame as a reference pixel. This is a method of transmitting a difference (prediction error) from a target pixel as a prediction value. For example, in motion compensation prediction, the motion of a moving object is predicted based on the motion vector of the prediction source image, and the motion is compensated for in the original image. The motion compensation is a method of searching for a place having the smallest difference in the vicinity of the position of the block in the previous image in units of 16 × 16 pixels, and taking the difference therefrom, thereby reducing the data to be sent further. Yes, as a means for detecting a motion vector, generally, a search is performed within a certain range from the original position of a partial image to be subjected to motion compensation, and the error is minimized (ie,
A place where the degree of approximation is the highest) is detected, and this is used as a prediction signal.

[0006] In addition, a conventional moving picture compression apparatus (CCITT H.261 or MPEG.
eo), when encoding the generated motion vector, the difference between the generated motion vector and the motion vector of a nearby partial image (usually, the partial image processed immediately before) is calculated, and only the difference is encoded. Is becoming

[0007] In conventional moving image compression apparatus of this kind, M
As a C (motion compensation) detection method, for example, “Basic study of motion estimation based on one-pixel matching” (TV Engineering Report I
CS94-38 (1994.2).

One of the high-efficiency video coding techniques is the above-described inter-frame prediction. The inter-frame prediction is a method of transmitting a difference between a previous image and a current image by a compression method using a property that there is a high correlation between temporally close images. In the case of a still image, the coding efficiency is very high because there is almost no difference between the previous image and the current image,
In a moving image, the correlation decreases and the coding efficiency decreases. For this reason, a method has been used in which the amount of motion and the direction (motion vector) are detected, and a part or the whole of the image is moved using the detected amount and direction to increase the correlation between two images.

The detection of a motion vector is generally performed by block matching. The block matching method divides one frame of the current image into a plurality of blocks, examines the similarity between each block and a block of the same size in the previous image, and determines a positional relationship with a block having the highest similarity as a motion vector. This is the output method. The evaluation operation for a certain positional relationship is performed by calculating the absolute value or the square value of the difference between the pixels located at the same position in two blocks for all the pixels in the block, and accumulating the obtained values. When the block size is Μ lines × N pixels, the operation of one trial vector (i, j) is represented by Expression 1.

[0010]

(Equation 1)

[0011] This evaluation is performed by using all vectors existing in the search range to be evaluated (hereinafter referred to as trial vectors).
(I, j) that finally makes Di, j in the expression shown in Equation 1 the smallest is used as the motion vector. Thus, in the block matching method, since the vector detection is performed on a block basis, the motion vector to be obtained represents the motion of the block.

On the other hand, when attention is paid to a moving object that frequently appears in a moving image, there are two types of movements of the object and the background in the outline of the object. In the block matching method, since a plurality of different motions in one block are represented by one vector, there is a problem that a correspondence with an actual motion cannot be obtained. This problem can be solved by detecting a motion vector for each pixel.

In the above document, a motion vector for each pixel is detected based on pixel matching in which a block size is set to 1 × 1 by a block matching method. The evaluation formula of this method is represented by the formula shown in Expression 2.

[0014]

(Equation 2)

Here, i, j that minimizes Di, j is a candidate for a motion vector in pixel units. In practice, i, j below Di, j, which is a certain threshold, are considered as motion vector candidates in consideration of the influence of noise or the like. In the pixel matching, since there are many pairs of i and j selected as candidates, vectors i and j corresponding to actual motions are extracted by using another evaluation function for these pairs. Specific examples of the new evaluation function include a “block matching method”, a “method using a nonlinear weighted sum”, and a “method using a majority operation”.

The "block matching method" is a method in which a block around a pixel to be detected is detected by the block matching method. In the above-described block matching method, the vector obtained is a vector for all pixels in the block, but here, it is handled as a vector of only the center pixel of the block.

In the "method based on non-linear weighted sum", pixels located near a pixel to be detected and having similar values are grouped into one group, and all the pixels in this group are expressed by the above-mentioned equation (2). In this method, given evaluation values are accumulated, and i and j that minimize the accumulated evaluation value are used as motion vectors.

In the "method by majority operation", it is determined whether or not the evaluation value obtained by the equation (2) is equal to or less than a certain level. In this method, i and j having the largest number are used as motion vectors. In this method, not only the number is simply checked, but also the state of the lump of matched pixels is evaluated.

With the method described above, a motion vector in pixel units is detected, and the deterioration in detection accuracy when there is a plurality of motions, which has been a problem in vector detection in block units, is improved.

[0020]

However, such a conventional motion vector detecting device has the following problems.

In the conventional example using the "block matching method", the processing is simple, but since the expression shown in Equation 1 is evaluated for each pixel, there is a problem that the amount of calculation becomes enormous. When obtaining a vector in block units, it is sufficient to detect one vector in a block, but in pixel units, a calculation in proportion to the size of the detected block is required to find vectors for the number of pixels in the block. . For this reason, considering processing with the same amount of calculation, the search range for motion vector detection cannot be widened, and the detection accuracy has deteriorated for images with large motion. Furthermore, since the detection vector is representative of the motion of each pixel in the block, that is, it does not indicate the motion of only the vector detection target pixel, the improvement effect on the problem when there is a plurality of motions in the block is Had become smaller.

The "method based on non-linear weighted sum" has a problem that processing becomes complicated. That is, since a pixel having a value close to the vector detection target pixel is extracted once and then matching is performed, two types of data are used to detect one vector, and it becomes difficult to perform high-speed vector detection. I was Furthermore, since it is a precondition that pixels having similar values in the vicinity perform the same movement, in an image that does not satisfy the condition, for example, in a part where there is a joint such as a finger or a lip of a hand of an image in which a person is captured. Could find the wrong vector.

Even in the "method by majority decision", there is a problem that the processing becomes complicated as in the "method by nonlinear weighted sum". This method also evaluates the distribution of matched pixels in order to increase the detection accuracy,
More complicated processing is required.

In each of the above methods, processing is performed on a certain group including the pixel to be detected. Since the motion vector to be obtained is representative of the group, the motion vector necessarily corresponds to the motion of the vector to be detected. Was not.

An object of the present invention is to provide a motion vector detecting device capable of reducing the amount of calculation for vector detection and improving the detection accuracy.

[0026]

A motion vector detecting device according to the present invention is a motion vector detecting device for detecting a motion existing between a plurality of images on a pixel-by-pixel basis. And a block having the same size as the block of the reference image with respect to the reference image, and when evaluating the similarity between the blocks,
The weight of the vector detection target pixel with respect to the evaluation value is configured to be heavier than the evaluation values of the pixels located in the vicinity.

Further, the motion vector detecting device divides the pixels located around the vector detection target pixel into a plurality of groups, and extracts a pixel value representing each group.
The configuration may be such that the evaluation operation is performed using the vector detection target pixel and a plurality of group representative pixels.

Further, the motion vector detecting device divides the pixels located around the vector detection target pixel into one group, and extracts a pixel value representing each group.
The configuration may be such that the evaluation calculation is performed using a pixel representing the vector detection target pixel and the peripheral pixel.

Further, the grouping of the peripheral pixels may be performed according to the distance from the pixel to be detected.

[0030]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS The motion vector detecting device according to the present invention can be applied to a motion vector detecting device such as a moving image storage device using a motion detection prediction signal of a moving image.

FIG. 1 is a block diagram showing a configuration of a motion vector detecting device according to an embodiment of the present invention. The motion vector detection device shown in FIG. 1 is an example applied to a motion vector detection device that detects pixel-based motion for motion estimation in motion compensation inter-frame prediction and frame interpolation.

In FIG. 1, a motion vector detecting device 10
Are current image data input terminal 100, previous image data input terminal 101, average value calculators 102 to 105, and memory 10
6, 107, evaluation calculators 108 to 110, adder 11
1, minimum value detector 112, register 113, controller 11
4 and a motion vector output terminal 115.

The current image data input terminal 100 is an input terminal to which current image data is input.

The previous image data input terminal 101 is an input terminal to which previous image data is input.

Each of the average value calculators 102 to 105 is constituted by an adder, and is an average value calculator for generating a group representative value.

The memory 106 is a memory for the current image which holds image data and group representative value data required for vector detection.

The memory 107 is a memory for a previous image having the same purpose as the memory 106 for holding image data and group representative value data necessary for vector detection. Since the memory 107 stores a data amount according to the vector search range, a memory having a larger capacity than the memory 106 is used.

Each of the evaluation calculators 108 to 110 is an evaluation calculator including an adder (subtractor), an absolute value calculator, and a table for multiplying a coefficient of an expression shown in Expression 3 described later.

The adder 111 comprises an evaluation calculator 108 to
This is a three-input adder that adds the outputs of the 110.

The minimum value detector 112 has therein a comparator and a register for storing a temporary minimum value, compares the evaluation value of the output of the multiplier 106, and outputs a hold pulse when the minimum value is obtained. It is a value detector.

The register 113 is constituted by a D-flip-flop (FF), and holds a trial vector from the controller 114 by using a pulse output from the minimum value detector 112.

The controller 114 generates and outputs a trial vector.

The motion vector output terminal 115 is an output terminal for outputting the trial vector stored in the register 113 as a motion vector.

As described above, in the motion vector detecting device 10 according to the present embodiment, since three evaluation computing units 108 to 110 are arranged, matching of three data can be evaluated at a time. That is, the operation of the expression shown in Expression 3 described later can be performed in one cycle.

Next, the operation of the motion vector detecting device 10 configured as described above will be described.

The motion vector detection method according to the present embodiment is different from the “block matching method” described in the literature in that the weight of the evaluation value of the target pixel for vector detection is set higher than the evaluation values of the peripheral pixels, thereby obtaining the target pixel. Is intended to be accurately represented by a vector. further,
The peripheral pixels are divided into groups, pixel values representing the groups are obtained, and the representative pixels are used for vector evaluation, thereby reducing the calculation amount of the matching operation.

FIG. 2 shows the difference between the "block matching method" described in the literature and the present method. The pixel located at the center of the block (square) in FIG. 2 is the vector detection target pixel.

In the block matching method, the absolute value of the difference is obtained for each pixel, and the evaluation value is calculated by the cumulative sum. The evaluation value is calculated by the sum of the absolute values of the differences.

The group division and the calculation of the representative pixel value will be described with reference to FIG. Group division is performed based on the distance from the vector detection target pixel. As shown in FIG. 2B, the detection target pixels themselves are grouped into one group, and are grouped by four pixels in the upper, lower, left, and right directions that are in contact with the detection target pixels, and four pixels that are positioned diagonally.

The representative value of the group is obtained by weighting the average value of the four pixels in the group by the distance from the pixel to be detected. The information of a group with a short distance is made heavier, and the lighter as the distance increases.

In the embodiment described below, a motion vector for each pixel is detected using information of a total of nine pixels centered on the pixel to be detected. In the evaluation operation, an operation based on the equation shown in Expression 3 is performed for all trial vectors, and D
Let i, j when i, j is smallest be a motion vector.

[0052]

(Equation 3)

Here, Χ represents current (reference) image data, and Y represents previous (reference) image data.

[0054]

(Equation 4)

In the equation shown in the above equation 3, α, β, γ
Is a coefficient based on the distance from the detection target pixel Xm, n.

Hereinafter, the operation of the motion vector detecting device 10 will be described in detail with reference to FIG.

From the current image data input terminal 100, a total of nine pixels, that is, the vector detection target pixel data of the current frame and its surrounding pixels are input. Similarly, from the previous image data input terminal 101, all the pixels in the search range of the vector of the previous frame and its peripheral pixels are input. If the search range is -4 to +3 pixels in both the horizontal and vertical directions, 64 pixels in the search range and 36 surrounding pixels are input. The peripheral pixels use the group representative pixels for generation.

The input current frame data is divided into three systems, the target pixel for vector detection is written as it is to the memory 106 as Xm, n, and the four pixels located above, below, left and right of the target pixel are averaged by the average value calculator 102. After being digitized, it is written into the memory 106 as Xm, n '.
n ”is written to the memory 106. The memory 106
Stores three data in this way.

The previous frame data is similarly divided into three systems, two of which are intermediate value calculators 104 and 105.
To be Ym + i, n + j ', Ym + i, n + j ", and are written to the memory 107. The previous frame data is i-4 and -4, respectively.
To +3, the memory 107 stores in each system 64
192 data in total are stored.

Thereafter, in the subsequent circuit, the memories 106, 1
Using the data held in 07, the evaluation of one trial vector is performed three times to obtain a motion vector.

First, the controller 114 outputs one vector to be evaluated, that is, one trial vector. The current image data separated into three systems is output from the memory 106 and input to the evaluation calculators 108 to 110, respectively. From the memory 107, three systems of previous image data shifted by the trial vectors i and j output from the controller 114 are read out.
These are input to the evaluation calculators 108 to 110, respectively.

The evaluation calculators 108 to 110 calculate the absolute value of the difference between the data of each group, and calculate the coefficients α,
Multiply β and γ. The outputs of the evaluation calculators 108 to 110 are accumulated by the adder 111 and become the evaluation value of a certain trial vector. Therefore, the calculation of the expression shown in the above equation (3) is performed by the evaluation calculators 108 to 110 and the adder 111.

The minimum value detector 112 compares the evaluation value generated as described above with the minimum evaluation value in the trial vector that has already been evaluated. If it is determined that the newly input evaluation value is smaller, the value of the internal register is updated to the new evaluation value, and a minimum value detection pulse is output.
If it is determined that the previous minimum evaluation value is smaller, nothing is performed. In the first evaluation of the trial vector, it is determined that the minimum value is unconditionally detected.

The minimum value detection pulse output from the minimum value detector 112 is sent to the register 113. The register 113 holds the trial vector output from the controller 114 when the pulse is input, as a temporary motion vector.

When the above series of operations is completed, the controller 1
A new trial vector is output from 14, and the evaluation is performed in the same manner. When the evaluation of all the trial vectors is completed, the minimum evaluation value is held in the minimum value detector 112, and the trial vector at that time is held in the register 113.

The trial vector is output from the output terminal 115 as a motion vector, and the vector detection for one pixel is completed.

Further, a case will be described in which a motion vector of continuously adjacent pixels # m, n + 1 is obtained.

In the vector detection of the pixel Xm, n, Ym + i, n + j, Ym + i, n + j ', Ym + i, n + j "are used as reference pixels. Remains in the memory 107, so that only the newly required reference data
That is, only the end portion of the search range may be captured and overwritten on an unnecessary area. This is because when the value of j is the maximum, Ym + i, (n + 1) + j, Ym + i, (n + 1) + j ′, Ym + i, (n + 1) +
j ″ is generated, and Ym + when j on the memory 107 is the minimum is generated.
i, n + j, Ym + i, n + j ', and Ym + i, n + j "will overwrite the existing area.

An evaluation operation is performed using the previously updated previous image data, Δm, n + 1 newly input for the current image, and its surrounding pixels.

As described above, the motion vector detecting apparatus 10 according to the present embodiment divides the peripheral pixels of the pixel to be detected into groups and performs the matching operation on a group basis in detecting a motion vector in pixel units by block matching. Since the evaluation weight for the detection target pixel is set higher than the evaluation values of the surrounding pixels at the time of evaluation, the amount of calculation for vector detection can be reduced.
Detection accuracy can be improved.

That is, in the conventional method, since the matching calculation is performed for each pixel, nine matching calculations are required for processing in a 3 × 3 block. This means that nine evaluation computing units in FIG. 1 are required. Further, the adder at the next stage also adds nine data. On the other hand, in this method, 9 pixels are set to 3
Since they are grouped into types, the matching operation may be performed three times. On the other hand, in this method, it is necessary to calculate the representative pixels of the group by the average value calculation before the matching calculation. However, when adjacent pixels are continuously processed as described in the operation description, only a few representative pixels are newly calculated. It is.

Here, a specific effect of reducing the amount of calculation will be described. Assuming that the search range is -4 to +3 in both the horizontal and vertical directions, the total number of trial vectors is 64. If the block size is 3 × 3 and one matching operation for one pixel is converted into 2.5 additions, the conventional method yields 1
440 additions were required. In this method, the average value calculation of the group representative value calculation can be performed 390 times, and the matching calculation can be performed 480 times, that is, 870 times in total.
% Calculation amount.

Also, 720p to which the above-described continuous processing is applied
Considering the processing of the entire image of el × 480 lines, the conventional method requires 497,664,000 additions.
In this method, 4,147,200 is used for calculating the group representative value.
Times, the number of matching operations is 165,888,000, and the total is 170,035,200, which is reduced to about 34% of the amount of operation. Further, in the present method, since the amount of calculation required for matching itself is reduced, a larger reduction effect can be obtained if the vector search range and the size of the block are increased.

Further, in the conventional method, since each pixel has the same weight at the time of the matching operation, if there is a characteristic motion in a pixel other than the pixel to be detected, the motion of the block follows the motion of the pixel. However, this method has a problem that it does not match the motion of the search target pixel. Can be solved.

Further, in the present method, since the peripheral pixels are grouped according to the distance from the detection target pixel, accurate correction is possible even for an image including rotation and enlargement / reduction as shown in FIG. Movement can be detected. Since the motion vector that can be detected by the block matching method is limited to the parallel movement of the object, accurate motion cannot always be detected with such a motion. In the image of FIG. 3, the motion of the black pixel at the lower left of the square is While going to the white pixels of the reference frame, the method goes to the black pixels of the square frame circle. The same detection is possible by simply performing weighting in the block matching method.However, by performing grouping, the evaluation value when detecting a motion that matches rotation / enlargement / reduction is reduced, and the motion vector False detection can be reduced.

In the present embodiment, an example has been described in which the grouping is performed in units of 3 × 3 blocks based on the distance from the pixel to be detected and the evaluation weight is changed according to the group. However, the size is not limited, and other sizes may be used.

Further, the grouping method may be a method of clustering pixels located in the vicinity in addition to the distance. It goes without saying that the time difference between the input images is not limited to one frame interval but may be a plurality of frame intervals.

Further, in the present embodiment, the absolute error according to the equation shown in Expression 2 is used for evaluating pixels, but a different evaluation function such as a square error may be used.

In the present embodiment, the motion vector detecting method may be applied to a moving picture compression apparatus based on, for example, the MPEG algorithm. However, the present invention is not limited to this. It goes without saying that it is applicable to the device.

Further, it goes without saying that the numbers and types of circuits and members constituting the motion vector detecting device and the evaluation arithmetic unit are not limited to the above-described embodiment, but may be realized by software (for example, C language). It may be.

[0081]

In the motion vector detecting device according to the present invention, a block having the same size as the block of the reference image is formed in the reference image and a block having the same size as the block of the reference image in the reference image. When the similarity is evaluated, the weight for the evaluation value of the vector detection target pixel is set to be heavier than the evaluation value of the pixels located in the vicinity, so that the amount of calculation for vector detection can be reduced. It is possible to improve the detection accuracy.

[Brief description of the drawings]

FIG. 1 is a block diagram illustrating a configuration of a motion vector detection device according to an embodiment to which the present invention has been applied.

FIG. 2 is a diagram for explaining a method of calculating an evaluation value of the motion vector detection device.

FIG. 3 is a diagram for explaining an effect of a motion of an object including rotation of the motion vector detection device.

[Explanation of symbols]

Reference Signs List 10 motion vector detection device, 100 current image data input terminal, 101 previous image data input terminal, 102 to 10
5 Average value calculator, 106, 107 memory, 108 ~
110 evaluation arithmetic unit, 111 adder, 112 minimum value detector, 113 register, 114 controller, 115 motion vector output terminal

Claims (4)

[Claims] 1. A motion vector detecting device for detecting a motion existing between a plurality of images on a pixel-by-pixel basis, comprising: a block centered on a vector target pixel with respect to a reference image; A motion characterized in that, when forming blocks of the same size and evaluating the similarity between the blocks, the weight for the evaluation value of the vector detection target pixel is made heavier than the evaluation values of the pixels located in the vicinity. Vector detection device. 2. The motion vector detecting apparatus according to claim 1, wherein pixels located around the vector detection target pixel are divided into a plurality of groups, and a pixel value representing each group is extracted. A motion vector detecting device for performing an evaluation operation using a pixel and a plurality of group representative pixels. 3. The motion vector detection device according to claim 1, wherein pixels located around the vector detection target pixel are divided into one group, and a pixel value representing each group is extracted. A motion vector detecting device, wherein an evaluation operation is performed using a pixel representing a pixel and a peripheral pixel. 4. The motion vector detecting device according to claim 2, wherein the grouping of the peripheral pixels is performed according to a distance from a detection target pixel.