KR100204477B1 - Method and apparatus for motion estimation of background image - Google Patents

Abstract

The present invention relates to a motion estimation method and apparatus for a background image, the apparatus comprising: a subsampler (21) for reducing an input image to a predetermined size; A block-matching motion estimator (22) for estimating a matching error by motion estimation of each of the images reduced by the subsampler (21) for each block of a predetermined size; A comparator (23) for comparing a matching error of the corresponding block input from the block matching motion estimator (22) with a predetermined reference value (T); A memory 24 for storing an index of the block when the matching error of the block is smaller than the reference value according to the output of the comparator; A first background motion estimator (25) which receives image data corresponding to an index output by the memory from the subsampler and estimates motion by comparing the reference data with a reference image in a predetermined search area; A second background motion estimator 26 is provided to compare the original image selected in the predetermined search area with the reference image based on the motion vector output by the first background motion estimator, so that the motion vector of the background image is simply obtained. There is an effect available.

Description

Method and apparatus for motion estimation of background image

1 is a flowchart showing a flow for obtaining a motion vector of a background image according to the present invention.

2 is a block diagram of an apparatus for estimating motion of a background image according to the present invention.

3 is a diagram for explaining an image reduction applied to the present invention.

4 is a conceptual diagram illustrating extracting blocks according to the present invention.

5 is a diagram for explaining calculating a motion vector in two steps according to the present invention;

6A and 6B are diagrams of a registration image and a reference image according to the present invention.

* Explanation of symbols for main parts of the drawings

21: subsampler 22: block matching motion estimator

23: comparator 24: memory

25: 1st background motion estimator 26: 2nd background motion estimator

The present invention relates to a motion estimation method and apparatus used in an apparatus for encoding and decoding an image signal, and more particularly, to a motion vector estimation method and apparatus for obtaining a motion vector of a background image.

As is well known, the intra-frame coding method in compression encoding of a video signal is a method of reducing redundancy in the spatial domain, and the inter-frame coding method is a method of removing redundancy in the time domain. In interframe coding, motion compensation DPCM compares the previous frame with the current frame to extract information about the object's movement. Using this information to predict the current frame properly, prediction error is reduced and differential data is reduced. Done. The motion compensation technique detects a block most similar to a predetermined block of the current frame in a search window of a previous frame and transmits the position of the detected block as a motion vector, while the block of the current frame and the detected previous frame By transmitting the difference with the similar block, the receiving side restores the block of the current frame using the data of the previous frame.

On the other hand, the motions seen in successive images are a combination of several types of motion elements, which include camera panning, scaling, rotation, and object translation. have. Among such moving elements, the elements capable of compensating for motion due to hardware configuration constraints are camera panning and object translation related to parallel movement. Here, camera panning and object movement are the same two-dimensional movements in terms of local aspects, but camera panning has the characteristics that the object movement is made locally compared to the movement in common with the corresponding area.

Therefore, in case of representing the motion of the image which is made in common like camera panning as one motion vector (this is called panning vector or global vector), it is possible to compress the data as a whole rather than calculating and sending motion vectors for each block. will be. In general, since the background image has no motion, most of the motion generated in the background image is due to camera panning. Therefore, the motion vector of the background image is the same as the panning vector.

That is, in the case of holding a screen while moving the camera sideways or up and down in a conventional image processing apparatus, since the movement of the entire screen occurs between frames, the receiving end pans the previous frame when the direction and degree of movement of the screen are transmitted. By shifting by vector, the amount of data can be reduced.

The conventional method for detecting such a panning vector is a method of detecting each panning vector as a panning vector when the same motion vector among the motion vectors estimated for the previous frame is larger than other motion vectors.

However, this method requires a motion vector of each block for the current frame and compares whether the same motion vector is larger than other motion vectors among these motion vectors. There is a problem in that a case where a motion due to panning and an object motion cannot be distinguished often occurs.

Meanwhile, another conventional method of obtaining a panning vector is to calculate a motion vector of a background image after dividing the foreground and the background of the image, and this method converts the input image into the foreground image and the motion. It is difficult to separate clearly with no background image, and it takes a lot of time and computation to separate with limited data. Therefore, there is a need for a method of easily obtaining a motion vector of a background image even if the accuracy is slightly reduced in consideration of practical aspects.

Accordingly, an object of the present invention is to provide a motion estimation method and apparatus for solving the above problems and simply calculating a motion vector of a background image in response to a need.

In order to achieve the above object, the method of the present invention comprises: an image input step of inputting data of a current image and a reference image for motion estimation; An image segmentation step of dividing an input image into uniform blocks of a predetermined size; Calculating a motion vector and a matching error for each block formed by image segmentation; Selecting a block by comparing the matching error calculated in the motion vector estimating step with a predetermined reference value; Estimating a single motion vector for the entire selected block; And outputting the estimated single motion vector as a background vector.

In addition, the apparatus of the present invention for achieving the above object, and a sub-sampler for reducing the input image to a predetermined size; A block-matching motion estimator for estimating a matching error by motion estimation of each of the images abbreviated by the subsampler for each block of a predetermined size; A comparator for comparing a matching error of the corresponding block input from the block matching motion estimator with a predetermined reference value; A memory for storing an index of the corresponding block when the matching error of the corresponding block is smaller than the reference value according to the output of the comparator; A first background motion estimator that receives image data corresponding to an index output from the memory from the subsampler and estimates motion by comparing the reference data with a reference image in a predetermined search area; And a second background motion estimator configured to compare the original image and the reference image selected in the predetermined search area with respect to the motion vector output by the first background motion estimator to estimate the motion.

Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings.

1 is a flowchart illustrating a method of calculating a motion vector of a background image according to the present invention. The method of the present invention includes an image input step S1 of inputting a current image and a reference image for motion estimation; An image segmentation step (S2) of dividing the input image into uniform blocks having a predetermined size in order to estimate motion according to a block matching algorithm (BMA); Estimating a motion vector for each block formed by image segmentation (S3); Selecting a block by comparing a distortion calculated in the motion vector estimation process with a predetermined reference value (S4); Estimating a single motion vector for the entire selected block (S5); And outputting the estimated single motion vector as a background vector (S6).

In more detail, each step of the motion estimation will be described in detail. In the image input step S1, a current image for motion estimation and a previous or subsequent image (reference image) serving as a reference for motion estimation are input in a predetermined format. For example, if the format of the input image is 4: 2: 0, the size of the luminance image Y is 720 x 480, the size of the color images Cb and Cr is 360 x 240, and if the SIF format is the luminance image Y The size of is 360 x 240 and the size of the color image (Cb, Cr) is 180 x 120. In the present invention, there is no need to limit the format of the input image, and for efficiency, the motion vector is estimated using only the image of the luminance signal Y.

In the step of dividing the image (S2), the input image frame is divided into blocks having a predetermined size in order to calculate a motion vector according to a conventional block matching algorithm (BMA). For example, 16 x 16 or 8 x 8 It can be divided into blocks, but 16 x 16 is preferable. Subsequently, in the motion vector estimating step S3, a search window is formed at a predetermined size (eg, -8/7, -32/31, etc.) around the position of the reference block for motion estimation. Compare the reference block and the candidate blocks in the window to find the candidate block that produces the smallest distortion. In this case, when the average absolute error (MAE) is used to calculate the matching error, the matching error is obtained for each candidate block as follows, and the position of the candidate block with the minimum matching error is estimated as a motion vector, and this candidate block is obtained. Outputs the matching error of. In other words, comparing all candidate blocks and reference blocks in the search window is called a full search block matching algorithm. When the image (reference image) is f ₁ (x, y) and the image of the current frame is f ₂ (x, y), a and b are selected from f ₂ (x, y) and f ₁ (xa, yb). Finding the difference between f ₁ (xa, yb) and f ₂ (x, y) while changing, predicts (a, b) that the difference is the minimum as a motion vector. The minimum error between blocks is called the Mean Absolute Error (MAE) method, and the average absolute error (E _abs ) is Obtained by Where B is the block size. In order to calculate the motion vector of the background image, the motion vector is calculated in this motion vector estimating step (S3). Therefore, the reduced data of the image to be matched is used to reduce the calculation amount. It is desirable to.

Subsequently, in the matching degree determination and block selection step (S4), if the matching error calculated for each block in the previous step (S3) is compared with the predetermined reference value (T), the deformation of the object is severe or incorrect movement. It is regarded as a vector, and blocks that are less than or equal to the reference value are stored to store the block indes.

In the motion vector estimation step S5 for the selected block, a single motion vector is calculated for the entire selected block. In contrast, the selected block is different from using each block individually in the motion estimation step S3. Use the whole together to find a motion vector. At this time, in order to reduce the amount of computation in calculating the motion vector, the motion vector is calculated in two steps. In the first step, a wide range of motion vectors is obtained using the abbreviated data, and in the second step, the first image is obtained using the original image. A precise motion vector is obtained within a small range based on the motion vector obtained in the step.

2 is a block diagram showing an apparatus for calculating a motion vector of a background image according to the present invention, which includes a subsampler 21, a block matching motion estimator 22, a comparator 23, a memory 24, The first background motion estimator 25 and the second background motion estimator 26 are configured.

In FIG. 2, the subsampler 21 reduces the sub-sampling of the input image by subsampling, for example, the image in the case of reducing 1/2 each in the horizontal direction and the vertical direction is as shown in FIG. Referring to FIG. 3, the black pixels and the blank pixels are pixels of the original image input to the subsampler, and the pixels selected one by one are displayed in black because they are reduced to 1/2 in the vertical and horizontal directions, respectively. The pixels are marked with blanks. Therefore, the output of the subsampler 21 is composed of black pixels and is 1/4 the size of the original image.

The block-matching motion estimator 22 estimates the current video abbreviated by the sub-sampler 21 from the reference video (previous video for forward motion estimation and subsequent video for backward motion estimation) and matches the motion vector with a match vector. In the present invention, since the block matching motion estimator 22 is for selecting blocks, it is sufficient to output only a matching error. As already known, the block matching motion estimator 22 compares a reference block with a plurality of candidate blocks in a search window formed in a previous image (or a subsequent image) and moves the position of the candidate block having the smallest matching error to a motion vector. As described above, the matching error is calculated, and the matching error is obtained by obtaining an error between pixels of the reference block and pixels of the candidate blocks as described above.

The comparator 23 compares the matching error calculated by the block matching motion estimator 22 with a predetermined reference value (threshold value: T) and, when smaller than this reference value T, stores the index number of the corresponding block in the memory 24. If it is larger than the reference value T, the block index is regarded as an invalid motion vector for the block.

When motion estimation is completed with respect to the image of one frame input as described above, as shown in FIG. 4, an image by the selected block is formed, and the motion vector of the background image is estimated by estimating the motion vector with respect to the entire selected image. Can be obtained. Since the index of the selected image block is stored in the memory 24, the motion estimation for the background image is performed using the index.

That is, the block matching estimator 22 estimates the motion vectors individually for the blocks of a predetermined size for block selection, but the motion estimators 25 and 26 for calculating the background motion vectors are shown in FIG. A single motion vector is calculated for the entire selected block.

In order to reduce the computation of the background motion vector, two-step motion estimation is performed as shown in FIG. 5. In the first motion estimation, a wide range of motion vectors are obtained with a reduced image, and in the second motion estimation, the original image is estimated. With the data of, we obtain a precise motion vector in a small search area around the motion vector calculated in the first step. For example, in the first motion vector, if a wide range of motion vectors is obtained using data reduced in half, respectively, horizontally and vertically, in the second step, two or more search areas are set around the first motion vector. A precise motion vector is calculated using the image data. At this time, the second motion estimation is performed within a predetermined range around the motion vector MV1 obtained from the first motion estimation. The size of the search area should be at least equal to the reduction factor used in the first step. That is, when the reduction ratio is 1/2, the size of the search area should be 2 or more. Thus, the search area should be larger than the reduction rate in order to reduce the uncertainty caused by using the reduced data.

As described above, the first background motion estimator 25 performs the first step of the two-step motion estimation. The first background motion estimator 25 receives the reduced image data from the sub-sampler 21 and receives an index designated from the memory 24. The motion of the blocks is estimated from a reference image in a predetermined search area to calculate a wide range of motion vectors (MV1), and the second motion estimator 26 performs the second step of the two-step motion estimation. An accurate background motion vector MV2 is calculated by motion estimation of data of blocks designated by the index of the memory 24 from the reference image by receiving data of the original image. At this time, the secondary motion search is performed in a predetermined search area around the motion vector MV1 calculated by the primary motion estimation, and the motion vector MV2 calculated as a result of the search is output as a background motion vector. For example, if the first motion estimation is performed in the search region of about +/- 20, the second motion estimation is motion estimation in the search region of about +/- 4. Since the motion estimators 25 and 26 are motion estimators for the background image, the motion estimators 25 and 26 process a selected block as a whole and output a single motion vector, rather than each block.

As described above, when estimating the background motion vector according to the present invention, the motion vector of the background image is simply reduced without using a reduced data and performing a separate operation for distinguishing the foreground from the background. There is an effect that can be obtained.

Claims (3)

An image input step S1 of inputting data of a current image and a reference image for motion estimation; An image segmentation step (S2) of dividing an input image into uniform blocks of a predetermined size; Calculating a motion vector and a matching error for each block formed by image segmentation (S3); Selecting a block by comparing the matching error calculated in the motion vector estimating step (S3) with a predetermined reference value (S4); Estimating a single motion vector for the entire selected block (S5); And outputting the estimated single motion vector as a background vector (S6). The method of claim 1, wherein the estimating of the motion vector for the entire selected block comprises: a first motion estimating step of estimating motion in a wide range by comparing the abbreviated image with a reference image and calculating the first motion estimating step; And a second motion estimation step of estimating motion by comparing the original image with the reference image in a narrow range based on the calculated motion vector. A subsampler 21 for reducing the input image to a predetermined size; A block-matching motion estimator (22) for estimating a matching error by motion estimation of each of the images reduced by the subsampler (21) for each block of a predetermined size; A comparator (23) for comparing a matching error of the corresponding block input from the block matching motion estimator (22) with a predetermined reference value (T); A memory 24 for storing an index of the block when the matching error of the block is smaller than the reference value according to the output of the comparator; A first background motion estimator (25) which receives image data corresponding to an index output by the memory from the subsampler and estimates motion by comparing the reference data with a reference image in a predetermined search area; A second background motion estimator 26 is provided which compares the original image selected in the predetermined search area with the reference image based on the motion vector output by the first background motion estimator, and includes a motion estimation of the background image. Estimator.