KR20130011608A - Apparatus and method for sampled profile based motion estimation - Google Patents

Abstract

The present invention relates to a motion estimation apparatus and method based on sample profile information, comprising: an edge image generation unit for generating an edge image of a current image by detecting an edge corresponding to an outline of an object in the current image; An image analyzer which receives the edge image and detects a horizontal max line (HmaxLine) and a vertical max line (VmaxLine) including the most edge information in the motion estimation target block; And a motion vector estimator for calculating a block matching error between the current image and the reference image based on the horizontal max line HmaxLine and the vertical max line VmaxLine, and predicting the coordinate difference of the block having the smallest difference as a motion vector. .

Description

Apparatus and method for sampled profile based motion estimation

The present invention relates to an apparatus and method for estimating motion based on sample profile information, and more particularly, to detect edges of a current image and a reference image when estimating a motion vector for block matching. By comparing the matching error of the horizontal line and the vertical line that includes the most to predict the motion vector, and to reduce the amount of computation for motion estimation, and relates to a sample profile information based motion estimation apparatus and method for enabling fast encoding.

Key elements supporting multimedia include digital compression and image compression technology. Recently, digitalization of information is rapidly developing, and accordingly, image compression technology is very important.

In general, a digital video device such as a PC, HDTV, or mobile device converts a video signal compressed by video compression such as MPEG (Moving Picture Experts Group) -2, MPEG-4, H.264 into an MPEG-based video codec. Encode and display

The image codec removes temporal redundancy based on a block matching scheme. The block matching method divides an image into small blocks and compresses a similar portion of the block of the currently encoded / decoded image by temporally searching for the previous frame or the previously encoded / decoded image and transmitting the difference value. .

To this end, it is necessary to find the most similar block between the previous frame and the current frame. This is called Motion Estimation (ME), and the motion vector (MV) is used to represent the displacement of the block. It is called.

The concept of intermediate image frame Fi synthesis using a block matching method is shown in FIG. 1.

As shown in Fig. 1, in order to synthesize an intermediate video frame Fi between the previous frame Fn-1 and the current frame Fn, the motion vector (MV) between the block in the previous frame Fn-1 and the block Fn in the current frame is shown. The motion is estimated to synthesize a block of the intermediate image frame Fi.

In motion estimation for video signal compression, the current video is divided into macroblocks, and a minimum error value such as a sum of absolute difference (SAD) or a sum of square difference (SSD) and the previous video is minimized in time. Coordinate difference with the area to be used is used as a motion vector.

In the case of H.264, the motion vector with the lowest cost is used for motion prediction by taking the cost considering the amount of data required to transmit the motion vector together with the SAD or SSD.

In order to find the motion vector, the SAD or SSD must be calculated for all the pixels of the motion search region, and the position having the minimum value must be found. For example, if the block size is N x N pixels and the motion search area is 32x32, 1024 * (2NxN-1) addition / subtraction operations are required.If the size of the image is about 100Nx80N, 8192000 * (2NxN-1) * (NxN ) Is required. This is a large amount of calculation that takes up to 50% of operations when encoding an image, which causes a system load and delays processing speed.

Korean Patent Laid-Open Publication No. 2004-0049214 (2004.06.11), title of the invention: High speed motion vector estimation apparatus and method

SUMMARY OF THE INVENTION The present invention has been made to solve the above-described problem, and includes a horizontal line that detects edges of a current image and a reference image and most includes edge information when estimating a motion vector for block matching. And by comparing the matching error of the vertical line to predict the motion vector, there is provided a sample profile information-based motion estimation apparatus and method for reducing the amount of computation for motion prediction to enable high-speed image encoding there is a technical problem.

In accordance with one aspect of the present invention, there is provided a sample profile information-based motion estimation apparatus comprising: an edge image generation unit for detecting an edge corresponding to an outline of an object in a current image and generating an edge image of the current image; An image analyzer which receives the edge image and detects a horizontal max line (HmaxLine) and a vertical max line (VmaxLine) including the most edge information in the motion estimation target block; And a motion vector estimator for calculating a block matching error between the current image and the reference image based on the horizontal max line HmaxLine and the vertical max line VmaxLine, and predicting the coordinate difference of the block having the smallest difference as a motion vector.

Here, the image analysis unit compares the edge image with a specific value (T) and generates a feature information image recorded with 0 and 1, and generates a horizontal profile and a vertical profile of the feature information image as follows. The horizontal max line HmaxLine and the vertical max line VmaxLine may be detected by calculating the equation.

[Equation 1]

H (x) = ∑ ^N I (x, y)

&Quot; (2) "

V (y) = ∑ ^M I (x, y)

&Quot; (3) "

X = arg _x Max (∑ ^N E (x, y))

&Quot; (4) "

Y = arg _x Max (∑ ^M E (x, y))

Where MxN is the size of the block, (x, y) is the coordinate of the pixel, and I (x, y) is the intensity of the pixel at the (x, y) coordinate. H (x) and V (y) are horizontal profile and vertical profile, respectively.

The motion vector estimator may calculate a block matching error based on a luminance value of a pixel corresponding to a horizontal maxline line HmaxLine and a vertical maxline VmaxLine of the current image and a luminance value of the corresponding pixel of the reference image. Can be.

The motion vector estimator may calculate a difference between the current image and the reference image as at least one of SAD and SSD using the following equation.

[Equation 5]

SAD = {∑ | Iref (HmaxLine + X, y + Y)-Icur (HmaxLine, y) |

+ ∑ | Iref (x + X, VmaxLine + Y)-Vcur (x, VmaxLine) |} xα

[Equation 6]

SSD = {∑ | ref (HmaxLine, y)-Hcur (HmaxLine, y) | ²

+ ∑ | Vref (x, VmaxLine)-Vcur (x, VmaxLine) | ² } xα

Where α is the scale constant N / 2 (N = natural number)

On the other hand, the sample profile information based motion estimation method of the present invention for achieving the above object comprises the steps of generating an edge image of the current image by receiving the current image to detect the edge corresponding to the contour of the object in the current image; Detecting a horizontal max line (HmaxLine) and a vertical max line (VmaxLine) including the edge information in the block with the input of the edge image; Calculating a block matching error between the block of the current image and the block of the reference image based on the horizontal max line HmaxLine and the vertical max line VmaxLine of the current image; And predicting a coordinate difference between blocks having the minimum block matching error as a motion vector.

Here, the step of detecting the horizontal max line (HmaxLine) and the vertical max line (VmaxLine) containing the most edge information by receiving the edge image, by comparing the edge image with a specific value (T) by threshold processing Generating a feature information image recorded with 0 and 1; Calculating a horizontal profile and a vertical profile of the feature information image by using Equations 1 and 2 below;

[Equation 1]

H (x) = ∑ ^N I (x, y)

&Quot; (2) "

V (y) = ∑ ^M I (x, y)

The method may include detecting a horizontal max line HmaxLine and a vertical max line VmaxLine including the edge information among the horizontal profile and the vertical profile by applying the following equations (3) and (4).

&Quot; (3) "

X = arg _x Max (∑ ^N E (x, y))

&Quot; (4) "

Y = arg _x Max (∑ ^M E (x, y))

The calculating of a block matching error between the current image and the reference image based on the horizontal max line HmaxLine and the vertical max line VmaxLine of the current image may include calculating a difference between the current image and the reference image by the following equation. The calculation may include calculating at least one of SAD and SSD.

[Equation 5]

SAD = {∑ | Iref (HmaxLine + X, y + Y)-Icur (HmaxLine, y) |

+ ∑ | Iref (x + X, VmaxLine + Y)-Vcur (x, VmaxLine) |} xα

[Equation 6]

SSD = {∑ | ref (HmaxLine, y)-Hcur (HmaxLine, y) | ²

+ ∑ | Vref (x, VmaxLine)-Vcur (x, VmaxLine) | ² } xα

Where α is the scale constant N / 2 (N = natural number)

As described above, the apparatus and method for motion estimation based on the sample profile information of the present invention detects edges of the current image and the reference image and estimates the most edge information when the motion vector is estimated for block matching. By comparing the matching error of the included horizontal and vertical lines to predict the motion vector, it is possible to reduce the amount of computation for motion prediction to enable high-speed image encoding.

1 is a motion vector prediction state diagram using a block matching method;
2 is a control block diagram of a sample profile information based motion estimation apparatus according to the present invention;
3 is a flowchart of a method for estimating motion based on sample profile information according to the present invention.

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

2 is a control block diagram of a sample profile information based motion estimation apparatus according to the present invention. The current image and the reference image are required for motion vector estimation. Here, the reference video refers to a video that is temporally earlier than the current video or an image that has been processed before in the encoding / decoding sequence.

As shown in FIG. 2, the motion estimation apparatus of the present invention includes an edge image generator 110, an image analyzer 120, a motion vector estimator 130, and a motion vector storage 140.

The edge image generator 110 detects an edge of an input image and generates an edge image. The edge of the image is a discontinuity point of the image brightness and means a portion in which the brightness of the image changes from a low value to a high value or vice versa. That is, since the edge corresponds to the outline of the object in the image, if the edge is detected, pixel coordinates of the outline of the displayed object can be extracted. As a method for generating an edge image, various techniques, such as detecting a change rate of brightness, that is, a slope and taking it as an edge when the slope is more than a predetermined reference value, are used. Thus, the edge image generator 110 generates an edge image using the edge detection method introduced in the related art.

The image analyzer 120 receives an edge image and detects a horizontal line and a vertical line including the most edge information.

The image analyzing unit 120 first generates a feature information image by thresholding the edge image to a specific value T and recording the edge image as 1 when the edge value is greater than T and recording it as 0 when the edge value is smaller than T. Since the edge value is the rate of change of image brightness, only a pixel having a high possibility of being an outline of an object is recorded as 1 in the feature information image in which the critical processing is completed.

The image analyzer 120 generates a horizontal profile and a vertical profile for each block in the feature information image. Equations for calculating the horizontal profile and the vertical profile are shown in Equations 1 and 2 below.

[Equation 1]

H (x) = ∑ ^N I (x, y)

&Quot; (2) "

V (y) = ∑ ^M I (x, y)

&Quot; (3) "

X = arg _x Max (∑ ^N E (x, y))

&Quot; (4) "

Y = arg _x Max (∑ ^M E (x, y))

Where MxN is the size of the block, (x, y) is the coordinate of the pixel, and I (x, y) is the intensity of the pixel at the (x, y) coordinate. In addition, H (X) is a horizontal profile, V (Y) is a vertical profile, and X and Y represent horizontal and vertical lines of a block selected by Equations 3 and 4.

As can be understood through Equation 1 and Equation 2, the profile is the sum of the pixel values of the same vertical or horizontal lines in the 2D image.

The image analyzer 120 generates a horizontal profile and a vertical profile of each block, and then extracts one horizontal line and one vertical line including the most edge information among them. Equations for detecting the horizontal max line (HmaxLine) and the vertical max line (VmaxLine) including a lot of edge information in each block are as shown in equations (3) and (4).

&Quot; (3) "

X = arg _x Max (∑ ^N E (x, y))

&Quot; (4) "

Y = arg _x Max (∑ ^M E (x, y))

The motion vector estimator 130 calculates a matching error between the block in the reference image and the block in the current image by using the horizontal max line HmaxLine and the vertical max line VmaxLine including the most edge information. The motion vector estimator 130 calculates a matching error corresponding to a sum of absolute difference (SAD) or a sum of square difference (SSD) using a horizontal max line (HmaxLine) and a vertical max line (VmaxLine). Equation 5 and Equation 6 are as follows.

[Equation 5]

SAD = {∑ | Iref (HmaxLine + X, y + Y)-Icur (HmaxLine, y) |

+ ∑ | Iref (x + X, VmaxLine + Y)-Vcur (x, VmaxLine) |} xα

&Quot; (6) "

SSD = {∑ | ref (HmaxLine, y)-Hcur (HmaxLine, y) | ²

+ ∑ | Vref (x, VmaxLine)-Vcur (x, VmaxLine) | ² } xα

Where Iref (x, y) and Icur (x, y) represent intensity values at (x, y) coordinates of the reference image and the current image, respectively, and (X, Y) represents candidate motion vectors. Α is a scale constant of N / 2 (N = natural number).

The motion vector estimator 130 calculates an error value such as Sum of Absolute Difference (SAD) or Sum of Square Difference (SSD) using a horizontal max line (HmaxLine) and a vertical max line (VmaxLine), and the previous image. The coordinate difference with the area where the error value of and becomes the minimum is determined as a motion vector.

The motion vector storage 140 stores the estimated motion vectors.

As described above, in the present invention, if the horizontal max line (HmaxLine) and the vertical max line (VmaxLine) containing the most edge information are found for each block of the current image, the candidate motion vectors can be used in the same manner. When comparing blocks of size, the operation of (2NxN-1) is reduced to 4N, which reduces the computation time.

For example, when N is 8, according to the prior art, 127 operations are required, but in the case of the present invention, since it is reduced to 32, the proposed method brings about a 4 times speed improvement.

3 is a flowchart of a method for estimating motion based on sample profile information according to the present invention.

First, the edge image generation unit 110 generates an edge image with respect to the current image (S110). The edge of the image is a discontinuity point of the image brightness and means a portion in which the brightness of the image changes from a low value to a high value or vice versa. That is, since the edge corresponds to the outline of the object in the image, if the edge is detected, pixel coordinates of the outline of the displayed object can be extracted.

The image analyzer 120 compares the edge image value with a specific value T and performs threshold processing, thereby generating a feature information image recorded as 0 and 1 (S112). Since the edge value is the rate of change of image brightness, only a pixel having a high possibility of being an outline of an object is recorded as 1 in the feature information image in which the critical processing is completed.

The image analyzer 120 calculates a horizontal profile and a vertical profile for each block in the feature information image (S114). The image analyzer 120 may apply Equation 1 above to generate a horizontal profile image of the feature information image, and apply Equation 2 to generate a vertical profile image. Here, the profile may be defined as a sum of pixel values of the same vertical line or horizontal line in the 2D image.

The image analyzer 120 detects a horizontal max line HmaxLine and a vertical max line VmaxLine including the most edge information based on the horizontal profile and the vertical profile values (S116). The image analyzer 120 may detect the horizontal max line HmaxLine and the vertical max line VmaxLine including the most edge information by applying Equations 3 and 4 below.

Thereafter, the difference between the block of the reference image and the block of the current image is calculated using the horizontal max line HmaxLine and the vertical max line VmaxLine (S118). The motion vector estimator 130 may calculate SAD using Equation 5 or calculate SSD using Equation 6 to calculate an error value.

The motion vector estimator 130 calculates a matching error value and estimates the coordinate difference between the reference block and the current block, which has the minimum error value, as a motion vector (S120).

Thus, those skilled in the art will appreciate that the present invention may be embodied in other specific forms without departing from the spirit or essential characteristics thereof. It is therefore to be understood that the embodiments described above are to be considered in all respects only as illustrative and not restrictive. The scope of the present invention is defined by the appended claims rather than the detailed description and all changes or modifications derived from the meaning and scope of the claims and their equivalents are to be construed as being included within the scope of the present invention do.

The present invention detects the edges of the current image and the reference image when estimating the motion vector for block matching, and compares the motion vector by comparing the matching error of the horizontal and vertical lines including the most edge information. By estimating, it can be used in a sample profile information-based motion estimation apparatus and method for reducing the amount of computation for motion prediction to enable fast encoding.

110: edge image generation unit
120: image analysis unit
130: motion vector estimation unit
140: motion vector storage

Claims (7)

An edge image generator for detecting an edge corresponding to the contour of the object in the current image and generating an edge image of the current image;
An image analyzer which receives the edge image and detects a horizontal max line (HmaxLine) and a vertical max line (VmaxLine) including the most edge information in the motion estimation target block; And
A sample including a motion vector estimator for calculating a block matching error between the current image and the reference image based on the horizontal max line HmaxLine and the vertical max line VmaxLine to predict a coordinate difference of the block having the smallest difference as a motion vector. Profile information based motion estimation device. The method of claim 1,
The image analyzer,
By comparing the edge image with a specific value T and performing threshold processing, a feature information image recorded with 0 and 1 is generated, and the horizontal and vertical profiles of the feature information image are applied to the following equation to calculate the A motion estimation device based on sample profile information characterized by detecting a horizontal max line (HmaxLine) and a vertical max line (VmaxLine).
[Equation 1]
H (x) = ∑ ^N I (x, y)
&Quot; (2) "
V (y) = ∑ ^M I (x, y)
&Quot; (3) "
X = arg _x Max (∑ ^N E (x, y))
&Quot; (4) "
Y = arg _x Max (∑ ^M E (x, y))
Where (x, y) is the coordinate of the pixel and I (x, y) represents the intensity of the pixel at the (x, y) coordinate. In addition, H (X) and V (Y) are a horizontal profile and a vertical profile, respectively, and represent a horizontal max line (HmaxLine) and a vertical max line (VmaxLine) in edge image E, respectively. The method of claim 1,
The motion vector estimating unit,
Based on sample profile information, the block matching error is calculated based on a luminance value of a pixel corresponding to a horizontal maxline line (HmaxLine) and a vertical maxline (VmaxLine) of the current image and a luminance value of a corresponding pixel of a reference image. Motion estimator .. The method of claim 1,
The motion vector estimating unit,
And a difference between the current image and the reference image is calculated using at least one of SAD and SSD using the following equation.
[Equation 5]
SAD = {∑ | Iref (HmaxLine + X, y + Y)-Icur (HmaxLine, y) |
+ ∑ | Iref (x + X, VmaxLine + Y)-Vcur (x, VmaxLine) |} xα
[Equation 6]
SSD = {∑ | ref (HmaxLine, y)-Hcur (HmaxLine, y) | ²
+ ∑ | Vref (x, VmaxLine)-Vcur (x, VmaxLine) | ² } xα
Where α is the scale constant N / 2 (N = natural number) Generating an edge image of the current image by detecting an edge corresponding to the contour of the object in the current image by receiving the current image;
Receiving the edge image and detecting a horizontal max line HmaxLine and a vertical max line VmaxLine including the most edge information;
Calculating a block matching error between the current image and the reference image based on the horizontal max line HmaxLine and the vertical max line VmaxLine of the current image; And
And predicting coordinate differences of blocks having the minimum block matching error as a motion vector. The method of claim 5,
The step of detecting the horizontal max line (HmaxLine) and the vertical max line (VmaxLine) containing the most edge information by receiving the edge image,
Generating a feature information image recorded with 0 and 1 by performing threshold processing on the edge image by comparing with a specific value T;
Calculating a horizontal profile and a vertical profile of the feature information image by using Equations 1 and 2 below;
[Equation 1]
H (x) = ∑ ^N I (x, y)
&Quot; (2) "
V (y) = ∑ ^M I (x, y)
Detecting the horizontal max line (HmaxLine) and the vertical max line (VmaxLine) including the edge information among the horizontal profile and the vertical profile by applying the following equations (3) and (4). Motion estimation method based on sample profile information.
&Quot; (3) "
X = arg _x Max (∑ ^N E (x, y))
&Quot; (4) "
Y = arg _x Max (∑ ^M E (x, y)) The method of claim 5,
Computing a block matching error between the current image and the reference image based on the horizontal max line (HmaxLine) and the vertical max line (VmaxLine) of the current image,
And calculating a difference between the current image and the reference image as at least one of SAD and SSD using the following equation.
[Equation 5]
SAD = {∑ | Iref (HmaxLine + X, y + Y)-Icur (HmaxLine, y) |
+ ∑ | Iref (x + X, VmaxLine + Y)-Vcur (x, VmaxLine) |} xα
[Equation 6]
SSD = {∑ | ref (HmaxLine, y)-Hcur (HmaxLine, y) | ²
+ ∑ | Vref (x, VmaxLine)-Vcur (x, VmaxLine) | ² } xα
Where α is the scale constant N / 2 (N = natural number)

Images