KR100292355B1 - Motion vector esitmation method and apparatus in image processing system - Google Patents

Abstract

The present invention relates to a motion estimation method and apparatus for a video system, the method comprising the steps of: (a) generating a low resolution image by reducing a resolution representing a pixel constituting a reference block and a search region; (b) calculating a degree of difference between a low-resolution image of the reference block and a low-resolution image of the search area block; And (c) determining a search area block having a small degree of difference as a matching block, and obtaining a motion vector. (a) comprises: obtaining a quantization boundary value such that a quantization error of a reference block is minimized using an average absolute value error minimization quantization (MMAE); And setting an outgoing pixel boundary (? Max,? Min) by multiplying a maximum pixel value (Pmax) and a minimum pixel value (Pmin) of a reference block by a predetermined constant; Quantizing the pixel values of the reference block and the search area using a quantization boundary value and an outgoing pixel boundary to generate a low resolution image, and displaying pixels that are out of the outline pixel boundary as an outgoing pixel, Area blocks are excluded from motion estimation.

According to the present invention, the amount of calculation required for motion estimation is significantly reduced, while performance degradation is minimized.

Description

[0001] The present invention relates to a motion vector estimation method and apparatus,

The present invention relates to motion estimation of an image system, and more particularly, to a motion estimation method and apparatus for a video system that low-resolution quantizes and compares pixel values of a reference block and a search area block.

Video compression technology, which efficiently reduces massive video information, is one of the indispensable technologies for various applications of image processing such as HDTV, video telephony, video on demand, and multimedia. In the image compression technique, various techniques are used to eliminate the temporal and spatial redundancy of the moving image and the statistical redundancy of the transmitted data. In order to remove spatial redundancy, techniques such as DCT and VLC have been proposed to remove statistical redundancies.

In order to eliminate the temporal redundancy, blocking matching motion estimation is used in most moving picture compression systems such as video experts group (MPEG) and H.261. The block matching motion estimation method divides a current frame into a plurality of small blocks (hereinafter, referred to as reference blocks), and then divides the current frame into a plurality of blocks of a previous frame And calculates a dissimilarity measure (hereinafter referred to as " phase ") that is not similar to the reference block. Then, a motion vector indicating the difference between the reference block and the matching block is searched for the block having the smallest degree of difference (hereinafter, referred to as a matching block), and only the difference between the reference block and the matching block is transmitted.

The degree of difference between the reference block and the search area block can be calculated by various methods. However, in the conventional motion estimation method, the sum of absolute differences (hereinafter referred to as " sum of absolute differences & SAD) is most frequently used. At this time, a value of (u, v) that minimizes the SAD becomes a motion vector, and the search area block at this time becomes a matching block.

In the above Equation 1, the size of the reference block is NxM, the size of the search area is (p, p) to (p-1, p-1), and rb (i, j) th pixel value, and sw (i, j) represents the (i, j) th pixel value in the search area block of the previous frame.

The biggest problem in the conventional motion estimation method is that as the frame size and the frame transmission rate per second increase, the hardware to process the frame becomes larger. In order to calculate the SAD between the reference block and the search area block when the size of the reference block is 16 pixels × 16 pixels, the subtraction, the absolute value calculation, and the accumulation are required 256 times for each search area block. Therefore, 64 pixels, it is necessary to subtract 1048576 times to calculate the motion vector of one reference block.

In order to implement the existing motion estimation method in hardware, a subtractor and an accumulator are used for subtraction, absolute value calculation, and accumulation. Assuming that the resolution of each pixel is k bits, the size of the reference block is n pixels xn pixels, and the size of the search area is p pixels xp pixels, two k-bit subtractors and an accumulator (K + ₂ log ₂ n) bit accumulator is required for each cycle. In order to obtain a motion vector of one reference block per cycle, a k-bit subtractor is 2 x n ² xp ² , (k + ₂ log ₂ n) The accumulator is required by n ² xp ² .

Since the number of reference blocks to be processed per second and thus the number of subtractors and accumulators are proportional to the frame size and the frame transmission rate per second, if the frame size or the frame transmission rate per second increases, .

The motion estimation method using the SAD is a full search method, which is a method of comparing an entire search area block within a search area with a reference block. In this case, since the computation amount increases, there is a method of calculating SAD by comparing only some search area blocks with the reference block instead of the global search method in order to reduce the amount of computation. However, this method has a drawback in that the performance is significantly lower than that of the global search method because the entire search area block is not compared with the reference block.

SUMMARY OF THE INVENTION The present invention has been made to solve the above-mentioned problems occurring in the prior art, and it is an object of the present invention to provide an image processing apparatus, And a motion estimation method and apparatus of the system.

FIG. 1 shows a comparative diagram of a fast search technique in terms of reduction in computation amount.

Figure 2 shows adaptive quantization for low resolution image generation.

Figure 3 shows a block diagram of a low-resolution quantized motion estimation technique.

Figure 4 illustrates the performance improvement of the DPC.

Figure 5 shows the hardware of the PSAD.

Fig. 6 shows an escape pixel in 2-bit quantization.

FIG. 7 shows the PSNR according to the change of the K value.

Figure 8 shows a block diagram of a low-resolution quantization motion estimator.

Fig. 9 shows the operation of each functional block.

Fig. 10 shows the recycling of the search area data.

11 shows a block diagram of a low-resolution search section.

Figure 12 shows an adaptive quantizer.

13 is a block diagram of the original resolution search unit.

According to another aspect of the present invention, there is provided a motion estimation method for a video system, the method comprising: (a) dividing a current frame by a predetermined size and a pixel constituting a search area in a previous frame, (A-1) a mean absolute value error minimizing quantization (MMAE) that minimizes the mean absolute value error (MAE) is used to minimize the quantization error of the reference block so as to minimize the quantization error Obtaining a value; And (a-2) generating a low-resolution image by quantizing pixel values of the reference block and the search region using the quantization boundary value; (b) calculating a degree of difference between a low-resolution image of the reference block and a low-resolution image of a search area block in the search area; And (c) determining a search area block having a small degree of difference among the search area blocks in which the disparity is calculated as a matching block, and obtaining a motion vector.

In addition, the step (a) may include grouping the pixels constituting the reference block and the search area by a predetermined number of units to obtain an average value, and expressing the reference block and the search area block as the average value; Obtaining a quantization boundary value such that a quantization error of a reference block is minimized by an average absolute value error minimization quantization (MMAE) which minimizes an average absolute value error (MAE) with respect to a reference block represented by the average value; Obtaining a difference between a pixel of the reference block and the search area block represented by the average value and an average value of all the reference blocks; And generating a low-resolution image by quantizing a difference between the pixel value of the reference block and the average value and the average value using the quantization boundary value.

In the step (b), the absolute value of the difference obtained by subtracting the reconstructed pixel value of the low-resolution image of the search area block from the reconstructed pixel value of the low-resolution image of the reference block is all added to determine the degree of difference. The quantization boundary is preferably obtained by a binary search.

Wherein the step (c) comprises: (c-1) selecting at least two blocks (candidate position blocks) having a small degree of difference among the degrees of difference obtained through the steps (a) and (b) Determining; (c-2) comparing an image of a search area block corresponding to a motion vector candidate position for the at least two candidate position blocks with an original resolution image of the reference block using an image of the original resolution; And (c-3) determining a block having the most similar image as the matching block in the step (c-2) as a matching block and obtaining a final motion vector.

The original resolution of the pixel is represented by 8 bits, and the low resolution is represented by 2 bits.

According to another aspect of the present invention, there is provided a motion estimation method for a video system, the method comprising: (a) dividing a current frame by a predetermined size and a pixel constituting a search area in a previous frame, Generating a low-resolution image by reducing a resolution to be displayed; (b) calculating a degree of difference between a low-resolution image of the reference block and a low-resolution image of a search area block in the search area; And (c) determining a search area block having a small degree of difference among the search area blocks in which the disparity is calculated as a matching block, and obtaining a motion vector.

The step (a) includes: (a-1) setting a quantization boundary value of the reference block; And (a-2) setting an outgoing pixel boundary (? Max,? Min) by multiplying a maximum pixel value (Pmax) and a minimum pixel value (Pmin) of the reference block by a predetermined constant; (a-3) quantizing the pixel values of the reference block and the search area by using the quantization boundary value and the exit pixel boundary to generate a low-resolution image, and displaying a pixel that is out of the outline pixel boundary as an outgoing pixel , The search area block including the escape pixel in steps (b) and (c) is excluded from the motion estimation.

Wherein the step (a) comprises: expressing the reference block and the search area block as the average value by grouping the pixels constituting the reference block and the search area by a predetermined number of units and calculating an average value; Obtaining a quantization boundary value for a reference block represented by the average value; Setting an outgoing pixel boundary (? Max,? Min) by multiplying a maximum pixel value (Pmax) and a minimum pixel value (Pmin) of the reference block by a predetermined constant; Obtaining a difference between a pixel of the reference block and the search area block represented by the average value and an average value of all the reference blocks; And quantizing the difference between the pixel value of the reference block and the average value and the average value using the quantization boundary value and the leaving pixel boundary to generate a low resolution image, .

According to another aspect of the present invention, there is provided a motion estimation method for a video system, the method comprising: (a) dividing a current frame by a predetermined size and a pixel constituting a search area in a previous frame, Generating a low-resolution image by reducing a resolution to be displayed; (b) calculating a degree of difference between a low-resolution image of the reference block and a low-resolution image of a search area block in the search area; And (c) determining a search area block having a small degree of difference among the search area blocks in which the disparity is calculated as a matching block, and obtaining a motion vector.

The step (a) includes the steps of (a-1) obtaining a quantization boundary value such that a quantization error of a reference block is minimized using an average absolute error error minimization (MMAE) which minimizes an average absolute value error ; And (a-2) setting an outgoing pixel boundary (? Max,? Min) by multiplying a maximum pixel value (Pmax) and a minimum pixel value (Pmin) of the reference block by a predetermined constant; (a-3) quantizing the pixel values of the reference block and the search area by using the quantization boundary value and the exit pixel boundary to generate a low-resolution image, and displaying a pixel that is out of the outline pixel boundary as an outgoing pixel , The search area block including the escape pixel in steps (b) and (c) is excluded from the motion estimation.

Wherein the step (a) comprises: expressing the reference block and the search area block as the average value by grouping the pixels constituting the reference block and the search area by a predetermined number of units and calculating an average value; Obtaining a quantization boundary value such that a quantization error of a reference block is minimized by an average absolute value error minimization quantization (MMAE) which minimizes an average absolute value error (MAE) with respect to a reference block represented by the average value; Setting an outgoing pixel boundary (? Max,? Min) by multiplying a maximum pixel value (Pmax) and a minimum pixel value (Pmin) of the reference block by a predetermined constant; Obtaining a difference between a pixel of the reference block and the search area block represented by the average value and an average value of all the reference blocks; And quantizing the difference between the pixel value of the reference block and the average value and the average value using the quantization boundary value and the leaving pixel boundary to generate a low resolution image, .

According to another aspect of the present invention, there is provided a motion estimation apparatus comprising: a reference block which divides a current frame by a predetermined size; and a pixel which constitutes a search region in a previous frame, the average absolute value error minimization quantization Processing unit for generating a deviation pixel boundary value (? Max,? Min) calculated by multiplying a quantization boundary value calculated by the minimum pixel value (Pmax) and a minimum pixel value (Pmin) of a reference block by a predetermined constant; A low-resolution search unit for generating a low-resolution image and calculating a motion vector candidate set by calculating a number of different pixels for the entire search range; And a original resolution search unit for obtaining a final motion vector by comparing an image of a search area block corresponding to a motion vector candidate position for the plurality of candidate blocks with an image of an original resolution of the reference block using an original resolution image .

Wherein the low resolution searching unit comprises: a quantizer for generating pixels of the reference block and the search region as low resolution images in which the outgoing pixels are separated using the quantization boundary value and the leaving pixel boundary value generated by the boundary value generating unit; A difference calculator for calculating a difference between a low-resolution image of the reference block and a low-resolution image of a search area block in the search area, wherein the search area block including the exit pixel is excluded from the difference calculation; And a candidate block determination unit for determining at least two search area blocks having different degrees of disparities among the disparity calculated in the disparity calculation unit.

Wherein the preprocessing unit comprises: a block average calculation unit for calculating an average of a reference block before calculating a quantization boundary; (? Max,? Min) by multiplying a quantization boundary value calculated by an average absolute value error minimization quantization (MMAE), a maximum pixel value Pmax and a minimum pixel value Pmin of a reference block by a predetermined constant, And a quantization threshold value calculation unit.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Hereinafter, the present invention will be described in detail with reference to the accompanying drawings.

1. Low-Resolution Quantization Motion Estimation Technique

As shown in reference numeral 15 in FIG. 1, the general fast search technique is to reduce the number of search positions such as (1) selective search, hierarchical search, and motion prediction search in order to reduce the amount of computation of the global search technique, ) Reduces the number of actually compared pixels, such as pixel subsampling, or (3) adopts an approach that uses a new matching criterion. The method of reducing the number of double search positions has a large performance degradation due to the local minimum, and the method of reducing the number of pixels to be compared has a disadvantage in that the performance deterioration is large when there are many vertical lines and horizontal lines. Therefore, in order to effectively reduce the computation amount of the global search technique, it is preferable to propose a new matching criterion as shown in reference numeral 100 in FIG.

In order to propose a matching criterion having a satisfactory performance while greatly reducing the amount of computation, the present invention proposes a quantization method of (1) effectively quantizing pixel values using adaptive quantization, (2) And (3) low-resolution quantization motion estimation (LRQME) using step-by-step search techniques to reduce performance degradation.

1.1 Adaptive Quantization

In order to prevent all pixel values in the reference block or search area from being truncated to the same value, it is desirable to cut such that the cut values are maximally different. From this point of view, it is effective to subtract the average value of the reference block or search area from each pixel value, and then cut the value, instead of cutting the pixel value as it is. In order to perform the optimized quantization, the quantization error is minimized considering the distribution of the pixel values rather than the uniform quantization which does not consider the distribution of the pixel values. Which is effective to reduce non-uniform quantization.

In the present invention, the average value of the reference block is obtained first for each reference block as shown in FIG. 2. Then, the average value is subtracted from the pixel value of the pixel of the reference block and the search area, and then quantized to 2 bits using Lloyd- We propose adaptive quantization which generates images. The bit resolution is determined in consideration of the computation amount and performance. The reason why only the average value of the reference block is used when the block average is subtracted from the pixel value is because the calculation amount required to calculate the average value is small.

In general Lloyd-Max quantization, the mean squared error (MSE) is used as the quantization error. However, since the quantization boundary calculation when MSE is used includes many multiplications, it is difficult to implement it in hardware. In the present invention, quantization boundaries are calculated using a mean absolute error (MAE) instead of the MSE in order to simplify the above. In order to determine the quantization boundary in the Lloyd-Max quantization, it is necessary to know the probability distribution of pixel values to be quantized. In the present invention, it is assumed that the quantized pixel values have a Gaussian distribution.

Quantization error expressed by MAE Is expressed by Equation (2). The quantization boundary that minimizes the quantization error in the Lloyd-Max quantization can be found from equation (3). For a 2-bit quantization to 4 ratio of the restored pixel values of two quantized codes, respectively 1: 2: 3: 4, place in solving the equation (3), three quantization boundary, such as Equation 4, t _1, t _2, t ₃ Can be obtained.

The quantization boundary of Equation (4) does not include multiplication and can be implemented with simple hardware. Since the probability distribution of the pixel values of the block finally found in the motion estimation as in the case of calculating the reference block average value can be assumed to be the same as that of the reference block, the quantization boundary obtained from Equation (4) As shown in FIG.

In equations (2) to (4) L denotes the number of quantization intervals, X _i denotes an i-th quantization interval, t _i denotes an i-th quantization boundary, and r _i denotes a restoration in an i-th quantization interval, respectively. Pixel value.

Adaptive quantization is much more efficient than conventional quantization, and the performance that can be obtained with 4 bit bit resolution when using uniform quantization can be obtained with 2 bits using adaptive quantization. Also, 2-bit adaptive quantization is suitable in terms of computation amount.

In the motion estimation technique, the search position where the matching criterion is minimum is determined as a motion vector. When there are several search positions where the matching criterion is minimum, only one of them is determined as a motion vector. Since the compression ratio is not the same when the matching criterion is the same, the more the plurality of search positions at which the matching criterion is minimum, the lower the performance. When the bit resolution is high, the probability of occurrence of such a problem is relatively low. However, if the bit resolution is lowered, a large number of pixels having different values are quantized to the same value. Also, if all the pixels in the search area are quantized to the same value, the motion vector can not be found because the matching reference has the same value at all search positions. In the present invention, this case will be referred to as a tie-score problem.

1.2 Matching Criteria

The present invention proposes a different pixel count (DPC), which is the number of pixels for which the quantized codes of the reference block and the search area do not coincide with each other, as shown in Equation (5) At this time Denote the quantized values of the reference block and the search area, respectively.

DPC can significantly reduce the hardware area compared to other matching standards with the same bit resolution.

1.3 Low-Resolution Quantization Motion Estimation Technique

The present invention proposes a low-resolution quantization motion estimation method comprising two steps of a low-resolution search (LRS) and a full-resolution search (FRS). A block diagram of the low-resolution quantization motion estimation technique can be shown in FIG.

In the low resolution search, DPC is calculated to obtain a candidate motion vector (CMV) set. In the original resolution search, a SAD is obtained for a candidate position of the CMV set to find a final motion vector. When the search range is (-32, -32) to (31,31), a total of 128 CMVs are determined for every four rows of search positions. The number of CMVs is determined in consideration of computation amount and performance. In order to further reduce the amount of computation, the original resolution search employs a 4: 1 alternate sub-sampling search technique. The low-resolution quantization motion estimation technique can be summarized as follows.

(1) Low resolution search

(1) Calculate the average value of the block and the quantization boundary for each reference block.

(2) The average value of the reference block is subtracted from the pixel values of the reference block and the search area, and the result is quantized into 2 bits to generate a low-resolution image.

(3) Calculate the DPC using a low-resolution image for each search position.

④ For every two search position columns, CMV determines the four search positions with the smallest DPC.

(2) Original resolution search

1) Perform a 4: 1 alternate negative sampling search technique for each CMV using original resolution images (ie, original pixel values).

(2) The CMV with the smallest SAD is determined as the final motion vector.

2. Motion Estimation Method for Exclusion Pixel Exclusion

Even if a matching criterion such as DPC is used with a small amount of computation, a large amount of computation is required to search the entire search range. One of the ways to reduce this computation amount is to estimate the motion by calculating the DPC from the average value of pixels as in the hierarchical search technique. As in the hierarchical search technique, the average value of 4x4 pixels significantly degrades the performance, so only the average value of 2x2 pixels is used in the present invention. The number of pixels to be compared is reduced to 1/4 and the number of search positions in the search range is reduced to 1/4 even if only the average value of 2x2 pixels is used. Can be reduced to 1/16. However, even if the average value of 2x2 pixels is used, the performance degradation is significant, so it is necessary to improve the performance of the DPC.

In the present invention, in order to perform effective motion estimation in a search range of ± 64 × ± 64 or more by improving the low-resolution quantization motion estimation technique, (1) searching the entire search range using the average value of 2 × 2 pixels, (2) (3) use a new matching criterion that improves the performance of the DPC, (4) introduce an outsider pixel concept to overload quantization error Outsider pixel exclusion motion estimation (OPEME) which improves the performance by excluding the search position where the motion vector is large in the motion estimation.

2.1 Use of pixel average

If the search range is large, a method of reducing the spatial resolution of a pixel as in a hierarchical search technique can be an effective way of reducing the amount of computation. Methods for reducing spatial resolution include (1) subsampling, and (2) pixel averaging. Considering the computation amount and the PSNR, it is desirable to reduce the spatial resolution by using the average value of 2x2 pixels.

2.2 Adaptive Quantization

Methods for reducing bit resolution include (1) LSB truncation using uniform quantization, and (2) adaptive quantization. 2-bit adaptive quantization is preferable in order to reduce the bit resolution in consideration of the computation amount and the PSNR.

In the present invention, mean absolute error error quantization (MMAE) is used to improve the performance of adaptive quantization. For each reference block, the three quantization boundaries m-δ, m, m + δ are determined so that the quantization error of the reference block is minimized, and the binary search is performed by the following algorithm.

m = calculate_mean (reference_block);

? = 32;

? = 16;

MAE _min = calculate_MAE (m-delta, m, m + delta);

do {

MAE ₁ = calculate_MAE (m- (? -?), M, m + (? -?);

MAE ₂ = calculate_MAE (m- (? +?), M, m + (? +?));

if min (MAE _min , MAE ₁ , MAE ₂ ) == MAE ₁ ) {

MAE _min = MAE ₁ ;

? =? -?;

} else if (MAE _min , MAE ₁ , MAE ₂ ) == MAE ₂ ) {

MAE _min = MAE ₂ ;

? =? +?;

}

? =? / 2;

} while (?! = 1)

The reason for performing the binary search is to reduce the amount of computation for calculating the quantization boundary. In the case of a wide search range, the total amount of computation required for motion estimation is very large, so that the computation amount of the binary search can be ignored as compared with the total computation amount.

2.3 Matching Criteria

DPC is advantageous in that it can greatly reduce the area when implemented in hardware, but it has a disadvantage in that it can not reflect the difference of pixel values in detail because it only compares whether or not the codes quantized with 2 bits are matched. 4, the actual SAD value when the pixel quantized with " 11 " is compared with the pixel quantized with " 01 " is larger than that when the pixel quantized with " 11 " In both cases, calculate the same.

In order to solve such a problem, the present invention proposes a PSAD (pseudo-SAD) in which a value obtained by comparing quantized codes is proportional to an actual SAD as shown in FIG. The PSAD is a value calculated in the same manner as the SAD with the reconstructed pixel value of the quantized code, and is defined as Equation (6). At this time Denotes the restored pixel values of the reference block and the search area, respectively.

Table 2 shows the values of DPC and PSAD when 2-bit quantization is performed. The PSAD is implemented in hardware as shown in FIG. 5 and has all of the advantages of DPC hardware, except that it uses 100% of the carry input of the adder tree.

2.4 Leakage pixels

When quantizing a pixel value, it is ideal to determine a quantization boundary that minimizes all of the quantization errors by examining both the reference block and the search region. Actually, however, since the search region is very wide, the quantization error of the search region pixel value is minimized A large amount of computation is required to obtain the quantization boundary. Therefore, the quantization boundary can be determined only by the pixel value of the reference block. In this case, the following problems arise.

The quantization error is divided into an overload error occurring at the end of the quantization interval and a granular error occurring in the remaining quantization interval as shown in FIG. 6 (a). The overload error occurs because the pixel values in the wide quantization interval located at both ends are quantized to the same value. Generally, even when the number of pixel values causing the overload error is small, the error is larger than the granularity error as a whole.

Since the search area is wider than the reference block, the pixel value range of the search area is generally much larger than the pixel value range of the reference block as shown in Figs. 7A and 7B. Since the quantization boundary is determined only by the pixel value of the reference block, even if the overload error occurring in the reference block is not large as shown in FIG. 7A, a very large overload error may occur in the search area as shown in FIG. 7B, In this case, performance degrades severely.

However, since the pixel value causing the overload error among the pixel values of the search region is a pixel value that greatly differs from the pixel value of the reference block, there is a possibility that a matching block most similar to the reference block exists at a search position where a large overload error occurs in the search region Is extremely small. Accordingly, in the present invention, a pixel exceeding a certain range (? _Min ,? _Max ) is defined as an outsider pixel as shown in (c) of FIG. If an escape pixel is included in a search area block corresponding to a certain search position, the search position is regarded as a large overload error and is excluded from the motion estimation. Where _{(λ max -m) = K (} p max -m), (m-λ min) = K was defined as _{(mp min), K = (} λ max -m) / (p max -m) is constant , m, p _max, p _min is a respective average, the maximum value of the reference block pixel value, minimum value, _max s, s _min is the maximum value, the minimum value of the search range for each pixel value.

If the constant K is too large, the number of pixels defined as the escape pixel becomes too small, resulting in a severe overload error and consequently degraded performance. If K is too small, too many search positions are excluded from the motion estimation, so that search positions corresponding to the correct motion vectors are excluded, resulting in a decrease in performance. In the present invention, it is preferable that K = 3/2 when the resolution is 2-bit as shown in FIG. As shown in FIG. 7, PSNR is improved by 0.84 to 1.40 dB by using an escape pixel as K = ∞.

2.5 Exit-Pixel Excluded Motion Estimation Technique

The escape pixel elimination motion estimation method is an improvement of the low-resolution quantization motion estimation method described above, and consists of two steps of low-resolution search (LRS) and full-resolution search (FRS). In the low-resolution search, a motion vector candidate set (CMV set) is determined by calculating a PSAD after generating a low-resolution image with an average value of 2 × 2 pixels. In the original resolution search, four searches corresponding to CMVs Find the SAD of the position and find the final motion vector. The outlier elimination motion estimation scheme can be summarized as follows.

(1) Low resolution search

(1) The average value of 2 × 2 pixels is obtained for both the reference block and the search area.

2) Compute the quantization boundaries m-δ, m, m + δ by the binary search in Section 2.2 for each reference block using the average of 2 × 2 pixels.

③ All pixels out of the range (λ _min , λ _max ) are classified as escape pixels.

(4) Both pixel values of the reference block and the search area are quantized to 2 bits by adaptive quantization in section 2.2 to generate a low-resolution image.

⑤ Calculate the PSAD using low-resolution images for each search position. At this time, if the escape pixel is included in the search area block corresponding to the search position, the search position is excluded from the motion estimation.

⑥ PSAD determines N least search positions as CMV set.

(2) Original resolution search

1) Calculate the SAD using the original resolution image (ie, the original pixel value, not the average of 2 × 2 pixels) for the 4N search positions corresponding to the N CMV sets. Since the average value of 2 × 2 pixels is used in the low resolution search, one CMV obtained in the low resolution search corresponds to four search positions in the original resolution search.

(2) SAD determines the smallest search position as the final motion vector.

3. Low resolution quantization, motion estimation device

3.1 Overall Architecture

The motion estimator according to the present invention has a search range of (-32.0, -32.0) to (31.5, 31.5) and simultaneously processes two motion estimation modes defined in the MPEG2 international standard for MPEG2 MP @ ML P- do. The overall block diagram of the motion estimator is as shown in FIG.

3.1.1 Function of each partial block

9 is a functional block diagram of a motion estimation apparatus according to an embodiment of the present invention. The motion estimation apparatus includes a preprocessing unit (PPU) 200 for calculating an average value of a reference block and a quantization boundary, a 2-bit low resolution image A low-resolution search unit (LRS) 210 for generating a motion vector candidate position (CMV) and calculating a different number of pixels (DPC) for the entire search range to determine a motion vector candidate position (CMV) A full-resolution search unit (FRS) 220 for determining an integer-pel motion vector (IMV) by performing an alternate sampling search, a reference block, and search area data, , An internal buffer 230 for performing an interface buffer function between LRS, FRS, and HPS.

In general, a half-pel motion vector (HMV) is determined by performing a half-pixel search on the IMV and a half-pel search unit (HPS).

The preprocessing unit 200, the low resolution search unit 210, and the original resolution search unit 220 will be described in more detail below.

The preprocessing unit 200 includes a block average calculation unit 202 and a quantization threshold value calculation unit 204. The block average calculation unit 202 calculates an average of a reference block before calculating a quantization boundary for a reference block obtained by dividing a current frame by a predetermined size and a pixel constituting a search region in a previous frame. The quantization boundary value calculation unit 204 multiplies a quantization boundary value calculated by an average absolute value error minimization quantization (MMAE), a maximum pixel value Pmax and a minimum pixel value Pmin of a reference block by a predetermined constant, Value (? Max,? Min).

The low resolution search unit 210 includes a quantization unit 212, a degree of difference calculation unit 214, and a candidate block determination unit 216. The quantization unit 212 generates pixels of the reference block and the search region as low resolution images in which the outgoing pixels are separated using the quantization boundary value and the exit pixel boundary value generated by the quantization boundary value calculation unit 204. [ The difference calculator 214 calculates the degree of difference between the low-resolution image of the reference block and the low-resolution image of the search area block in the search area, and excludes the search area block including the exit pixel from the difference calculation. The candidate block determination unit 216 determines at least two search area blocks having different degrees of disparity among the calculated degrees of difference calculated by the difference calculation unit 214.

The original resolution search unit 220 obtains a motion vector by comparing the image of the search area block corresponding to the motion vector candidate position for the plurality of candidate blocks with the image of the original resolution of the reference block using the original resolution image . The original resolution search unit 220 includes an 8x8 pixel SAD calculation and comparison unit 8x8 pixel SAD calculation and comparison and a 16x16 pixel SAD calculation and comparison unit 224 for performing a 16x16 pixel SAD calculation and comparison.

3.1.2 Use of Internal Buffers to Reduce Memory Bandwidth

The motion estimator according to the present invention adopts a method of storing the entire search area in an internal buffer in order to reduce the memory bandwidth. 10, if the entire search area is stored in the internal buffer using the property that the search areas of adjacent macro blocks overlap with each other and then reused, only the newly added pixels The memory bandwidth can be reduced because it is read.

The internal buffer includes a CSW buffer for storing the entire search area of the current macroblock, a PSW buffer for storing a search area for a half-pixel search of the previous macro block, a CRB buffer for storing the current macro block, a PRB Buffer, and an NRB buffer that stores the next macroblock.

3.2 Low resolution search section

As shown in FIG. 11, the low resolution search unit includes an adaptive quantizer, a low-resolution image register, a unit processor, and a comparator in a VLSI implementation.

The adaptive quantizer subtracts the reference block average value from the pixel value, and quantizes the pixel value to 2 bits to generate a low-resolution image. The adaptive quantizer has a structure as shown in FIG.

The unit processor compares the reference block with each column of the search range (= 16 pixels) every cycle. Since the reference block consists of 16 rows, one unit processor processes one search position every 16 cycles to calculate the DPC.

The low-resolution image register is a shift register that stores low-resolution images quantized into 2 bits and transfers them to the unit processor.

3.3 Original resolution search section

The original resolution search unit determines the four candidate positions by calculating the 8 × 8 pixel SAD for the CMV set search position and then calculates the 16 × 16 pixel SAD for the four candidate positions to determine the integer pixel motion vector. Perform an alternate negative sampling search.

The original resolution search unit includes a pixel data preprocessor, a unit processor, and a comparator as shown in FIG. 13 when implementing a VLSI. In the 4: 1 alternate sampling search, the reference block and the search area are divided into four groups and SAD is separately performed.

The motion estimation method and apparatus according to the present invention are superior in performance while reducing the amount of computation compared to the conventional fast search method in motion estimation.

Claims (21)

(a) generating a low-resolution image by reducing a resolution representing the pixel for a reference block obtained by dividing a current frame by a predetermined size and a search region for a previous frame; (b) calculating a degree of difference between a low-resolution image of the reference block and a low-resolution image of a search area block in the search area; And (c) determining a search area block having a small degree of difference among the search area blocks for which the disparity is calculated as a matching block, and obtaining a motion vector, The step (a) (a-1) obtaining a quantization boundary value such that a quantization error of a reference block is minimized using an average absolute value error minimization quantization (MMAE) that minimizes an average absolute value error (MAE); And (a-2) generating a low-resolution image by quantizing pixel values of the reference block and the search area using the quantization boundary value. 2. The method of claim 1, wherein step (c) (c-1) determining blocks (candidate position blocks) having at least two different degrees of difference among the degrees of difference obtained through the steps (a) and (b) for the plurality of search area blocks; (c-2) comparing an image of a search area block corresponding to a motion vector candidate position for the at least two candidate position blocks with an original resolution image of the reference block using an image of the original resolution; And (c-3) determining a block with the comparison result image closest to the matching block in step (c-2) and obtaining a final motion vector. 3. The method of claim 1 or 2, wherein the original resolution of the pixel is 8 bits, and the low resolution is quantized to 2 bits. 3. The method according to claim 1 or 2, wherein the step (a) Expressing the reference block and the search area block as the average value by grouping the pixels constituting the reference block and the search area by a predetermined number of units and obtaining an average value; Obtaining a quantization boundary value such that a quantization error of a reference block is minimized by an average absolute value error minimization quantization (MMAE) which minimizes an average absolute value error (MAE) with respect to a reference block represented by the average value; Obtaining a difference between a pixel of the reference block and the search area block represented by the average value and an average value of all the reference blocks; And And generating a low-resolution image by quantizing a difference between the pixel value of the reference block and the search area and the average value using the quantization boundary value. 5. The apparatus of claim 4, wherein the predetermined number of pixels Wherein the motion vector is a 2x2 pixel. 3. The method according to claim 1 or 2, wherein step (b) Wherein the absolute value of the difference obtained by subtracting the reconstructed pixel value of the low-resolution image of the search area block from the reconstructed pixel value of the low-resolution image of the reference block is all added to determine the degree of difference. 2. The method of claim 1, wherein the quantization boundary is Wherein the motion estimation is performed by a binary search. (a) generating a low-resolution image by reducing a resolution representing the pixel for a reference block obtained by dividing a current frame by a predetermined size and a search region for a previous frame; (b) calculating a degree of difference between a low-resolution image of the reference block and a low-resolution image of a search area block in the search area; And (c) determining a search area block having a small degree of difference among the search area blocks for which the disparity is calculated as a matching block, and obtaining a motion vector, The step (a) (a-1) setting a quantization boundary value of the reference block; And (a-2) setting an outgoing pixel boundary (? max,? min) by multiplying a maximum pixel value (Pmax) and a minimum pixel value (Pmin) of the reference block by a predetermined constant; (a-3) quantizing the pixel values of the reference block and the search area by using the quantization boundary value and the exit pixel boundary to generate a low-resolution image, and displaying a pixel that is out of the outline pixel boundary as an outgoing pixel , Wherein the step (b) and the step (c) exclude the search area block including the departure pixel from the motion estimation. 9. The method of claim 8, wherein step (c) (c-1) determining blocks (candidate position blocks) having at least two different degrees of difference among the degrees of difference obtained through the steps (a) and (b) for the plurality of search area blocks; (c-2) comparing an image of a search area block corresponding to a motion vector candidate position for the at least two candidate position blocks with an original resolution image of the reference block using an image of the original resolution; And (c-3) determining a block with the comparison result image closest to the matching block in step (c-2) and obtaining a final motion vector. 10. The method of claim 8 or 9, wherein the original resolution of the pixel is 8 bits, and the low resolution is quantized to 2 bits. The method as claimed in claim 8 or 9, wherein the step (a) Expressing the reference block and the search area block as the average value by grouping the pixels constituting the reference block and the search area by a predetermined number of units and obtaining an average value; Obtaining a quantization boundary value for a reference block represented by the average value; Setting an outgoing pixel boundary (? Max,? Min) by multiplying a maximum pixel value (Pmax) and a minimum pixel value (Pmin) of the reference block by a predetermined constant; Obtaining a difference between a pixel of the reference block and the search area block represented by the average value and an average value of all the reference blocks; And Quantizing the difference between the pixel value of the reference block and the average value and the average value by using the quantization boundary value and the leaving pixel boundary to generate a low resolution image and indicating that the pixel that is out of the boundary pixel is a leaving pixel A method for motion estimation of a video system. 12. The display device according to claim 11, wherein the predetermined number of pixels Wherein the motion vector is a 2x2 pixel. 10. The method of claim 8 or 9, wherein step (b) Wherein the absolute value of the difference obtained by subtracting the reconstructed pixel value of the low-resolution image of the search area block from the reconstructed pixel value of the low-resolution image of the reference block is all added to determine the degree of difference. The method of claim 1, wherein step (a) (a-1) obtaining a quantization boundary value such that a quantization error of a reference block is minimized using an average absolute value error minimization quantization (MMAE) that minimizes an average absolute value error (MAE); (a-2) setting an outgoing pixel boundary (? max,? min) by multiplying a maximum pixel value (Pmax) and a minimum pixel value (Pmin) of the reference block by a predetermined constant; (a-3) quantizing the pixel values of the reference block and the search area by using the quantization boundary value and the exit pixel boundary to generate a low-resolution image, and displaying a pixel that is out of the outline pixel boundary as an outgoing pixel , Wherein the step (b) and the step (c) exclude the search area block including the departure pixel from the motion estimation. 15. The method of claim 14, wherein step (c) (c-1) determining blocks (candidate position blocks) having at least two different degrees of difference among the degrees of difference obtained through the steps (a) and (b) for the plurality of search area blocks; (c-2) comparing an image of a search area block corresponding to a motion vector candidate position for the at least two candidate position blocks with an original resolution image of the reference block using an image of the original resolution; And (c-3) determining a block with the comparison result image closest to the matching block in step (c-2) and obtaining a final motion vector. 16. The method of claim 14 or 15, wherein the original resolution of the pixel is 8 bits, and the low resolution is quantized to 2 bits. 16. The method of claim 14 or 15, wherein step (a) Expressing the reference block and the search area block as the average value by grouping the pixels constituting the reference block and the search area by a predetermined number of units and obtaining an average value; Obtaining a quantization boundary value such that a quantization error of a reference block is minimized by an average absolute value error minimization quantization (MMAE) which minimizes an average absolute value error (MAE) with respect to a reference block represented by the average value; Setting an outgoing pixel boundary (? Max,? Min) by multiplying a maximum pixel value (Pmax) and a minimum pixel value (Pmin) of the reference block by a predetermined constant; Obtaining a difference between a pixel of the reference block and the search area block represented by the average value and an average value of all the reference blocks; And Quantizing the difference between the pixel value of the reference block and the average value and the average value by using the quantization boundary value and the leaving pixel boundary to generate a low resolution image and indicating that the pixel that is out of the boundary pixel is a leaving pixel A method for motion estimation of a video system. A quantization boundary value calculated by an average absolute value error minimization quantization (MMAE) and a maximum pixel value Pmax of a reference block are calculated for a reference block obtained by dividing a current frame by a predetermined size and a pixel constituting a search region in a previous frame, ) And a minimum pixel value (Pmin) multiplied by a predetermined constant to generate an exit pixel boundary value (? Max,? Min); A low-resolution search unit for generating a low-resolution image and calculating a motion vector candidate set by calculating a number of different pixels for the entire search range; And a original resolution search unit for comparing the image of the search area block corresponding to the motion vector candidate positions of the plurality of candidate blocks with the image of the original resolution of the reference block using the original resolution image to obtain the final motion vector With features, The low- A quantization unit for generating pixels of the reference block and the search region using a quantization boundary value and an exit pixel boundary value generated by the boundary value generation unit, as low resolution images in which the outgoing pixels are separated; A difference calculator for calculating a difference between a low-resolution image of the reference block and a low-resolution image of a search area block in the search area, wherein the search area block including the exit pixel is excluded from the difference calculation; And And a candidate block determining unit for determining at least two search area blocks having small disparity among disparity calculated by the disparity calculating unit. 19. The apparatus of claim 18, wherein the pre- A block average calculation unit for calculating an average of a reference block before calculating a quantization boundary; And The outgoing pixel boundary value (? Max,? Min) is calculated by multiplying the quantization boundary value calculated by the mean absolute error error minimization quantization (MMAE), the maximum pixel value Pmax and the minimum pixel value Pmin of the reference block by a predetermined constant And a quantization threshold value calculation unit. 19. The method of claim 18, Further comprising an internal buffer for interfacing between the preprocessing unit, the low resolution search unit and the original resolution search unit, and storing the entire search area data to reduce the memory bandwidth. A pixel value of the reference block and the search area is quantized using a predetermined quantization boundary value for a reference block obtained by dividing a current frame by a predetermined size and a pixel constituting a search area in a previous frame to generate a low resolution image ; Calculating a degree of difference between a low-resolution image of the reference block and a low-resolution image of a search area block in the search area; And Determining a search area block having a small degree of difference among the search area blocks for which the disparity is calculated as a matching block, and obtaining a motion vector.