KR100924641B1 - Fast block matching procedure for motion estimation - Google Patents

Abstract

Provided is a block matching method for motion estimation that can reduce the amount of computation and improve coding speed. In a block matching method according to an embodiment of the present invention, using the information of one or more neighboring blocks of the current block, estimating the degree of motion of the current block and the motion degree of the current block is small (S), Dividing into a large case (L) and a middle case (M), and also finding a matching block for the current block by adaptively applying a search method for motion estimation based on the divided degree of motion. . According to one aspect of the present embodiment, when the motion of the current block is predicted to be small, an improved cross diamond search technique (UCDS) is applied, and when the motion is predicted to be large, the diamond search technique (Diamond Search) is applied. , DS), and if it is expected to be intermediate, cross three step search (CTSS) is applied.

Description

Fast block matching procedure for motion estimation

The present invention relates to a video codec, and more particularly, to a fast block matching algorithm for motion estimation in a video codec.

Video compression techniques such as MPEG-1, 2, 4 or H.264 / AVC can be used to significantly reduce the Motion Estimation and Compensation (ME / MC) procedure, Discrete Cosine Transform (DCT). It has a basic structure consisting of the transform, quantization, and entropy coding procedures. Among them, motion estimation and compensation is a technique of compressing data using characteristics of a video, that is, high spatial and temporal redundancy among components constituting an image, and a technology field having the greatest influence on the complexity of an encoder, that is, the entire encoding time. to be. This is because the redundancy of the temporal data having the most redundancy in the video can be eliminated by motion estimation and motion compensation.

The motion estimation method can be roughly divided into a pixel recursive algorithm (PRA) and a block matching algorithm (BMA). Among these, most video codec technologies use block matching algorithms in consideration of the regularity of data flow, computational complexity, and hardware implementation. The block matching algorithm refers to a procedure of finding a matching block in a predetermined search window of a reference frame by dividing a screen into 16 × 16 macroblocks (MB) or arbitrary smaller blocks. . The value indicating the position of the matching block found according to the block matching algorithm is a motion vector. In video encoding, only the difference value between the matching block and the current block and the motion vector are encoded to remove data redundancy.

Block matching algorithms generally use the full search technique. The prescan technique is to determine whether or not to match all positions in the search area in order to find an optimal matching block. Since most video coding standards use this prescan technique, the motion estimation and compensation process is one of the largest sources of the entire coding time. Therefore, various types of new block matching algorithms, that is, fast block matching algorithms, have been developed in order to improve the problem of speed delay due to pre-search.

Three Step Search Technique (TSS)

1A shows a pattern of motion estimation according to a three-stage search technique. Referring to FIG. 1A, the motion vector is determined in three steps starting from the initial pattern of the wide search interval and narrowing the search interval to 1/2 interval. More specifically, the point having the minimum block matching error is determined by first matching the eight points about 4 pixels away from the origin with respect to the origin (0, 0) (step 1). The minimum block matching error point is determined by inspecting eight points, which are two pixels half the interval of one step from the minimum block matching point determined in step 1, as in step 1 (step 2). Finally, when 8 points away from the minimum block matching error point obtained in step 2 are examined and the point having the minimum block matching error value is determined, a value indicating this point is used as a motion vector.

Figure 1b shows the minimum number of search points for each pixel when using a three-stage search technique in a search region in the ± 7 pixel range. Referring to FIG. 1B, it can be seen that the number of search points required for every pixel is 25. These results show that the three-stage retrieval technique is inefficient for low-motion images but effective for high-motion images.

New Three Step Search (NTSS)

The new three-stage search technique (NTSS) consists of a center-based search pattern. Most of the blocks in the image are 8 motion points around the origin in the 3 step search method based on the fact that the motion vectors are centered around the origin in the static image where there is no motion or the motion is low. It can be seen that the modified by adding.

2A shows a pattern of motion estimation according to a new three step search technique. Referring to FIG. 2A, a block matching error of 17 points is obtained in the first step. If the origin has the minimum block matching error, the origin is designated as the motion vector and the search ends. If the eight points adjacent to the origin have the minimum block matching error, three or five points are extended. If a point in the diagonal direction is selected around the origin, five points are further extended by one pixel in the same direction. If it is perpendicular, three points are extended. If eight points of the edge away from the origin are selected, the search is performed in the same manner as in the three-stage search technique.

Figure 2b shows the new three-stage search scheme in the pixel search range of ± 7 the minimum number of search points for each pixel. Referring to FIG. 2B, it can be seen that the new three-stage search method is more efficient than the three-stage search method but less inefficient than the three-stage search method.

Four Step Search (FSS)

FIG. 3A illustrates a pattern of motion estimation according to a four-stage search technique, which further improves a disadvantage of falling into a local minimum point common in the three-stage search technique. Referring to FIG. 3A, first, eight search points that are 2 pixels away from each other at right angles and diagonal directions are examined, and if the origin has the minimum block matching error, go to step 4 to be described later. Start (step 1). In step 2, if the value other than the origin has a minimum block matching error in step 1, 5 points in the diagonal direction and 3 points in the perpendicular direction are further extended (step 2). If there is no change in the minimum block matching error point, go to step 3. Otherwise, go to step 4. Subsequently, in step 3, the minimum block matching error of 3 or 5 points is calculated in the same manner as in step 2 (step 3). Finally, in step 4, search for 8 points in the diagonal or right direction, which is 1 pixel away from the minimum block matching error point obtained in step 3, and determine the displacement of the minimum block matching error point as the motion vector and perform the search. Finish (step 4).

Figure 3b shows a four-step search technique in the pixel search range of ± 7 the minimum number of search points for each pixel. Referring to FIG. 3B, similar to the new three-stage search method, the four-stage search method is also more efficient than the three-stage search method, but less efficient than the new three-stage search method.

Block-Based GraDient Search (BBGDS)

FIG. 4A shows a search pattern of motion estimation based on BBGDS, and is a technique using a property of motion of an image closer to the origin than a 3 step search method and a 4 step search method. Referring to FIG. 4A, first, nine points are searched around the origin, and the search ends when the origin has a minimum block matching error. If the origin is not, a two-step search is performed (step 1). In step 2, if the diagonal point from the origin is the minimum block matching error point, 5 points are extended by 1 pixel in the same direction, and in the orthogonal direction, 3 points are further extended (step 2). . Repeat this two-step process until there is no change in the minimum value.

4B shows the minimum number of search points for each pixel in the BBGDS search scheme in a pixel search range of ± 7. Referring to FIG. 4B, it is shown that BBGDS is efficient in a slow motion image but inefficient in a fast motion image.

Diamond Search (DS)

The diamond search technique is based on the assumption that the distribution of the motion vector is located near the origin, the center of the search area, and the best performance in terms of image quality and speed in comparison to the existing techniques for both large and small images. Seems. 5A shows the search pattern in the diamond search technique.

Referring to FIG. 5A, first, eight points are arranged in a large diamond search pattern (LDSP) in a right angle and a diagonal direction around an origin of a search area, and block matching is performed on each of the points. Find the block matching error point (step 1). If the point with the minimum block matching error is the origin, go to step 3. If not, go to step 2. In the case of a point perpendicular to the minimum block matching error point in step 1, five points are further extended and examined. And if the point in the diagonal direction is extended to examine the three points (step 2). If there is a change in the minimum block matching error, step 2 is continued. If there is no change in the minimum block matching error, the process proceeds to step 3. After performing a small diamond search pattern (SDSP) centering on the minimum block matching error point, the motion vector is determined by obtaining the minimum block matching error point (step 3).

5B shows that the diamond search technique in the pixel search range of ± 7 shows the minimum number of search points for each pixel. Referring to FIG. 5B, it can be seen that the diamond search method is superior to other fast search algorithms in a slow motion image, which is inefficient than a three-step search method in an image that is faster than BBGDS but is not slow or fast.

The existing fast block matching algorithms have a significant speed improvement in some cases compared to the global search scheme, but in other cases, the speed improvement is insignificant and still has a large amount of computation. For example, in the case of the three-stage search technique, the optimal block matching error point is inefficient when it exists near the origin (0, 0). In the case of the BBGDS technique, the optimal block matching error point is the origin (0, 0). Inefficient if they exist far from In addition, while other techniques complement the shortcomings of these three-stage search and BBGDS techniques, there is a problem that the amount of computation is increased to compensate for the shortcomings.

Therefore, the problem to be solved by the present invention can reduce the amount of calculation regardless of the position of the optimal block matching error point, that is, the speed of the movement of the current block (size of the motion vector), unlike the existing high-speed block matching algorithm In addition, it provides a new fast block matching algorithm that can minimize image degradation compared to prescan.

According to an aspect of the present invention, there is provided a block matching method for motion estimation, using the information of one or more neighboring blocks of a current block to predict a degree of motion of the current block and The motion degree is divided into small (S), large (L), and middle (M) motions, and based on the separated motion degree, the current motion is applied by adaptively searching for motion estimation. Finding a matching block for the block.

According to an aspect of the embodiment, the neighboring blocks include one or more blocks among blocks located on the left side, the upper side, and the upper right side with respect to the current block, and the information of the neighboring blocks is expressed by Equation (E−). in 1), (E-2) , and (E-3) length (MV _length), the number (SP of the search point), and the sum (SAD) of absolute values of a difference between the motion vectors of the neighboring block is defined as a It may include one or more.

(E-1)

(E-1)

(E-2)

(E-2)

(E-3)

(E-3)

Here, the subscripts left, above, and above-right indicate the position of the neighboring block with respect to the current block, respectively, and MV _left , MV _above , MV _above-right respectively indicate the x-axis component (MV _x ) of the MV of the block. And y-axis components (MV _y ) are determined to be the maximum values, where operation average (x, y, z) represents the average of three numbers x, y, z, and operation int (x) points to the integer part of real x. .

In this case, at least two pieces of information among the length of the motion vector (MV _length ), the number of search points (SP), and the sum of absolute values (SAD) of the differences may be predicted to have a small degree of motion of the current block. Alternatively, when only one piece of information predicts that the motion of the current block is small and the other two pieces of information predict that the motion of the current block is medium, the step of finding a matching block for the current block is improved. An upgraded cross diamond search (UCDS) can be applied. In addition, when at least two pieces of information of the _length MV _length , the number of search points SP, and the sum SAD of the difference value are predicted to have a large degree of motion of the current block, In the step of finding a matching block for the current block, a cross three step search technique (CTSS) may be applied, and the length of the motion vector (MV _length ), the number of search points (SP), and the difference At least two pieces of information of the sum of absolute values (SAD) of the predicted motion degree of the current block is medium, and another piece of information predicts that the motion degree of the current block is medium or large, or the motion vector. length (MV _length), more number of search points (SP), and if the cost of the current block is predicted from the sum (SAD) of absolute values of difference motion about each other, the matching block for the current block of The finding steps can be applied to the diamond search technique (Diamond Search, DS).

According to another aspect of the present embodiment, the step of finding a matched block for the current block may include an improved cross diamond search (UCDS), a cross three step search (CTSS), and a diamond search. Any one of the search schemes (Diamond Search, DS) may be applied. In this case, when the degree of motion of the current block is predicted to be small, the UCDS is applied. When the degree of motion of the current block is predicted to be medium, the DS is applied. If it is expected to be large, the CTSS may be applied.

According to an embodiment of the present invention, the spatial correlation between the current block and the neighboring block is high, and the motion vector of the neighboring blocks, the number of search points, and / or the SAD are used to predict the degree of motion of the current block. According to the result, the optimal fast block matching technique is applied. In particular, according to an embodiment of the present invention, the motion vector may be estimated at high speed by selecting the most appropriate algorithm among the UCDS, DS, and / or CTSS algorithms according to the degree of motion of the current block to perform motion estimation. According to this embodiment of the present invention, it is possible to find a matching block more quickly with less computation while maintaining the same image quality as the fast block matching algorithm proposed previously.

EMBODIMENT OF THE INVENTION Hereinafter, embodiment of this invention is described with reference to an accompanying drawing.

According to the fast block matching algorithm according to an embodiment of the present invention, when the motion estimation is performed on a block-by-block basis in one frame, the fast and fast motion of the current block is predicted in advance, and then an efficient fast search algorithm is adaptively applied according to the prediction result. Select to use. That is, it predicts in advance whether the motion of the current block corresponds to a relatively small case and a relatively large case (or in between), and then adaptively applies a different search method according to the predicted type. .

6 is a flowchart illustrating a motion estimation method according to an embodiment of the present invention.

Referring to FIG. 6, first, a motion degree of a current block is predicted (S11). More specifically, in this step, it is determined whether the current block is a block having a large motion (the value of the motion vector is large), a block having a small motion (the value of the motion vector is small), or whether the motion is medium. To judge. In the embodiment of the present invention, information of neighboring blocks neighboring the current block is used to determine the degree of movement. This uses the fact that the spatial correlation between the current block and the neighboring block is high due to the characteristics of the image, which can reduce the computational complexity for calculating the degree of motion, and can find more accurate minimum block matching error points with fewer search points. have.

7 is a diagram illustrating the positions of neighboring blocks used to predict the degree of motion of the current block according to this embodiment of the present invention. Referring to FIG. 7, in the embodiment of the present invention, the left block MV _left , the upper block MV _above , and the right upper block MV _above-right are used as peripheral blocks. However, if the current block is located at the upper left side, neighboring blocks cannot be used. In this case, the movement is assumed to be the smallest. If the current block is located on the uppermost side, only one neighboring block (left) is used. If the current block is located on the leftmost or right side, two neighboring blocks (upper and upper right or left and upper) ).

According to an embodiment of the present invention, the information of the neighboring block includes a sum of a motion vector length (MV _length ), a number of search points (SP), and an absolute value of a difference (Sum of Absolute Difference, SAD). Information may be used. Equations 1, 2, and 3 are the length of the motion vector for the current block (MV _length ) from the motion vectors of the neighboring blocks, the number of search points for the current block (SP _current ) from the number of search points of the neighboring blocks, And SAD (SAD _current ) for the current block from SADs of neighboring blocks.

Here, MV _left , MV _above , and MV _above-right are determined as the maximum values of the x-axis component (MV _x ) and the y-axis component (MV _y ) of the MV of the block, respectively, and are calculated by calculating average (x, y, z) Denotes the average of three numbers x, y, and z, and the operation int (x) points to the integer part of the real number x.

And two thresholds for each of the three values, namely, the length of the motion vector for the current block (MV _length ), the number of search points for the current block (SP _current ), and the SAD (SAD _current ) for the current block. Using the first threshold T ₁ and the second threshold T ₂ ), it is determined whether the current block belongs to a large block, a small block, or a middle block. The two threshold values can be determined experimentally for each piece of information.

For example, in the case of MV _length of the motion vector, after setting the first threshold value to 2 and the second threshold value to 6, if the length MV _length of the current block is less than or equal to 2, the small motion block ( In S), it is determined that the block L has a large motion if it is 6 or more, and the block M whose motion is intermediate if the value is between 3, 4, or 5. Table 1 summarizes this.

Judgment Judgment result MV _length ≤ T ₁ (2) Small (S) T ₁ <MV _length <T ₂ (6) Medium (M) MV _length ≥ T ₂ Large (L)

In the case of the number of search points (SP _current ), the first threshold is set to 17 and the second threshold is set to 25. If the number of search points (SP _current ) of the _current block is less than or equal to 17, the block S has small movements. If it is 25 or more, it can be determined as a block L having a large movement, and a block M having a medium value, that is, a motion in between. Table 2 summarizes this. The reason why the first threshold is set to 17 and the second threshold is set to 25 as described below with reference to FIGS. 8A and 8B is based on the case of 17 and 25 search points. It depends on the technique.

Judgment Judgment result SP _current ≤ T ₁ (17) Small (S) T ₁ <SP _current <T ₂ (25) Medium (M) SP _current ≥ T ₂ Large (L)

In the case of SAD value SAD _current , the first threshold is 1100 and the second threshold is 2000. If the SAD (SAD _current ) of the current block is 1100 or less, the small block S is smaller than 2000. If the motion is a large block (L), and the value in between, that is, between 1100 and 2000 can be determined as the block (M) with a medium movement. Table 3 summarizes this. In this way, the reason for setting the first threshold value to 1100 and the second threshold value to 2000 is based on experimental results. Table 4 shows the average SAD values of 100 frames of CIF video in the MPEG-4 MV encoder. When two thresholds were arbitrarily set to T ₁ = 1100 and T ₂ = 2000, good results were obtained.

Judgment Judgment result SAD _current ≤ T ₁ (1100) Small (S) T ₁ <SAD _current <T ₂ (2000) Medium (M) SAD _current ≥ T ₂ Large (L)

6, after predicting the degree of movement of the current block, a fast block matching search technique is adaptively applied based on the prediction result (S12). In this case, the term adaptive means that another fast block matching search technique is applied to minimize the number of search points according to the predicted movement degree for the current block. Referring to FIG. 6, when the current block is predicted to be a small block S, the BBGDS is applied as the search technique, and when the motion is predicted to be the middle block M, the TSS is applied as the search technique. If the motion is predicted to be a large block (L), the motion estimation procedure is performed by applying DS as a search technique. This will be described in more detail below.

FIG. 8A shows the minimum number of search points per pixel when considering the three-stage search technique, the new three-stage search technique, the four-stage search technique, the BBGDS and the diamond search technique in the pixel search range of ± 7. 8B shows a type of fast search algorithm that has a minimum number of search points in each pixel. Referring to FIGS. 8A and 8B, considering the minimum number of search points per pixel, BBGDS is efficient in an image or a block with little or no motion, and when the motion is medium, for example, the length of the MV is 3, 4, or 5 In the case of blocks, it can be seen that the diamond search technique (DS) is advantageous. In addition, it can be seen that a three-stage search technique (TSS) is efficient for a high motion image, that is, a block having a relatively large size of a motion vector. Therefore, according to an embodiment of the present invention, when the degree of predicted movement for the current block is small in step S11 (S), the BBGDS is applied, and when the degree of predicted movement for the current block is large (L). In the case where the TSS is applied and the predicted motion for the current block is medium (M), when the DS is applied, the motion vector can be obtained more efficiently.

9 is a flowchart illustrating a motion estimation procedure according to another embodiment of the present invention.

Referring to FIG. 9, first, as in the above-described embodiment, prediction about the movement degree of the current block is performed (S21). In the present embodiment, a new fast block matching search technique is further improved in step S22 to improve the coding speed by further reducing the calculation amount according to the motion estimation in the step S22, compared to the above-described embodiment. Apply adaptively. According to the exemplary embodiment of the present invention, when the current block is predicted to have a small amount of motion, an improved cross diamond search technique (UCDS) is used instead of the BBGDS search technique. Cross Three Step Serach (CTSS) is used. In other cases, the diamond search technique is used as in the above-described embodiment. Hereinafter, the UCDS technique and the CTSS technique newly proposed in the present invention will be described in detail.

Enhanced Cross Diamond Search (UCDS) Technique

As can be seen in the analysis considering the minimum number of search points per pixel described with reference to FIGS. 8A and 8B, the BBGDS may show a tendency to decrease the number of search points in a slow image or a block. However, the Cross Diamond Search (CDS) technique or the New Cross Diamond Search (NCDS), which improves performance by improving the diamond search technique, is more useful for slow motion images or blocks. Because the CDS and NCDS methods require that the diamond search method requires at least 13 search points by performing SDSP once more after LDSP, CDS performs the initial search point by nine cross points and NCDS by the initial method. This is because the number of search points is reduced by performing 5 SDSP points around the origin.

However, when the distribution of the motion vector is examined with the distance of ± 7 for the experimental videos described in Table 5, as shown in Table 6, most of the motion vectors are distributed around the center of the search area. It can be seen that it has the largest distribution of about 62% within 1 pixel radius from the center point, about 76% within 2 pixels radius and about 84% within 3 pixels radius. The cross diamond search (CDS) technique initially performs nine cross-shaped points and the new cross diamond search (NCDS) technique performs five initial search points, resulting in an image with little or no motion, ie optimal block matching error points. The search for motion vectors distributed within one pixel of this radius shows excellent performance. However, the cruciform diamond search method and the new cruciform diamond search method do not consider the motion vectors that are distributed in the radius of 2 or 3 pixels even though there are a large amount of motion vectors in the radius of 2 and 3 pixels. It can be seen that this leads to performance degradation. Therefore, in the embodiment of the present invention, by using a new search technique called an improved cross diamond search (UCDS) technique, the block matching error is performed by considering a motion vector distributed within a radius of 2 or 3 pixels, thereby improving performance.

According to the UCDS technique, first, as shown in FIG. 10A, an optimal block is found at five points of a small cross search pattern (SCSP) centered on an origin point (0,0) (step 1). As a result of the search, if the optimal block occurs at the origin, stop the search or go to the next step. If the optimal block occurs at (1,0), we add 4 points ((2,0), (3,0), (1, -1), (1,1)) Navigate (step 2). The same logic applies when the optimal block is (-1,0), (0,1), or (0, -1) rather than (1,0). As a result of the search, if the best block occurs at (1,0) (or (-1,0), (0,1), (0-1)), the search stops and the next step is taken.

The next step can be divided into three cases (step 3). The first case is when the optimal block occurs at (2,0) (or (-2,0), (0,2), (0, -2)). In this case, as shown in FIG. 10C, two points ((2, -1) and (2,1)) are further searched. If the search results in an optimal block at (2,0) (or (-2,0), (0,2), (0, -2)), stop the search and go to the next step. The second case is when the optimal block occurs at (1, -1) (or (-1, -1), (-1,1), (1,1)). In this case, two points ((1, -2) and (2, -1)) are additionally searched as shown in FIG. 10D. As a result of the search, if the optimal block occurs at (1, -1) (or (-1, -1), (-1,1), (1,1)), the search stops and the next step is taken. The third case is when the optimal block occurs at (3,0) (or (-3,0), (0,3), (0, -3)). In this case, go to the next step.

Subsequently, a search is performed with a large diamond search pattern (LDSP) centering on the optimal block point of the previous step (step 4). As a result of the search, if it finds the best block point in the center, it moves on to the next step, otherwise it repeats this step. The search is performed with the SDSP centering on the optimal block point of the previous step (step 5).

10E and 10F are diagrams showing examples of applying the entire process of the UCDS technique, respectively. Referring to FIG. 10E, in step 1, (1,0) is selected by comparing four points around the origin (0,0), and in step 2, four points are added to calculate a block matching error, and then ( If 3,0) is selected, it proceeds to step 4 because it is 3 in the case of step 3, and if the optimal block point is at the center, it performs (5, SDSP) by performing 5 steps of SDSP. Referring to FIG. 10F, in step 1, four points are compared around the origin (0,0), and (1,0) is selected, and in step 2, four points are added and compared to determine (1, -1). Then, in the third step of adding and comparing two points ((1, -2), (2, -1)), the second case is performed to select (2, -1), and to focus on the optimal block point. After performing 4 steps of performing LDSP, 5 steps of SDSP are performed to finally determine (3, -2).

The UCDS method described in detail above performs the SDSP around the origin (0,0) to prevent the speed drop caused by the nine initial search points of the cross diamond search method, and then performs a flat diamond shape after performing the SDSP. By adding four points, we can find the point with the lowest block matching error faster than the new cross diamond search method. In particular, it can be seen that the performance is superior to other algorithms for images with little or no motion.

In fact, the results of experimenting with 100 frames of CIF video in the MPEG-4 VM encoder by selecting a low-motion video and many video are shown in Table 7. Referring to Table 7, the peak signal-to-noise ratio (PSNR) of UCDS is maintained in the small motion image similar to BBGDS, cross diamond search method, and new cross diamond search method. It can be seen that the number (Search Point, SP) is less than other algorithms. However, it can be seen that the PSNR is lower than that of the diamond search method in the high motion image. Therefore, it can be concluded that it is advantageous to use UCDS when searching for images with few movements with MV in a certain area around the origin.

Cross Three Step Search Technique

The CTSS method is similar to the three-stage search method. As an initial search, the CTSS method performs the determination on the eight points around the origin (0,0), and then narrows the search interval to 1/2 intervals. In the three-step determination, four points are first matched in the cross shape, and then two points are additionally adaptively matched along the minimum block matching error point.

More specifically, first, a point having a minimum block matching error is determined by performing matching on eight points four pixels away from the origin with respect to the origin (step 1). As shown in FIGS. 11A and 11B, it is first determined whether or not to match the four points of the cross shape two pixels apart from each other, which are half of the first step interval, based on the minimum block matching point obtained in the first step. As a result of the determination, if there is no change in the matching point, the process proceeds directly to step 3 as shown in FIG. 10A. However, if there is a change in the matching point, adaptively checking whether two points are matched as shown in FIG. 10B. After the determination, the process proceeds to step 3 (step 2). Subsequently, a determination is first made on four points in a cross form 1 pixel away from the minimum block matching error point obtained in step 2, and when the matching point does not change, as shown in FIG. 11A. Although the motion vector is determined, if there is a change in the matching point, as shown in FIG. 11B, it is adaptively determined whether to match two additional points, and then the motion vector is determined.

Table 8 shows the PSNR and the number of search points (SP) of the three-step search (TSS) technique and the cross-type three-step search (CTSS) technique for various sample images. Referring to Table 8, the TSS technique and the CTSS technique show similar PSNR, but the number of search points is relatively reduced by the CTSS technique. Therefore, in the embodiment of the present invention, it is proposed to use the CTSS instead of the TSS technique in the case of a block having a lot of motion. However, the embodiment of the present invention is not limited thereto, and the TSS technique may be used as it is, or another search technique may be used to improve the speed in a block with a lot of motion.

As described above, according to the embodiment of the present invention, in estimating the degree of motion of the current block, three pieces of information about the neighboring block, that is, the length of the motion vector (MV _length ), the number of search points (SP), and At least one piece of information may be used among the SADs. Hereinafter, as an embodiment of the present invention, a method of predicting the degree of motion of the current block using all three pieces of information will be described.

When the length of the motion vector (MV _length ), the number of search points (SP), and SAD are all used as criteria for determining the degree of motion of the current block, a combination that can be derived from the three pieces of information is 3 ³ , that is, 27 There is a branch. These 27 combinations can be classified into two cases in which any one degree of movement is shown two times or more and a case in which three degrees of movement are evenly mixed as shown in Table 9, for example. As shown in Table 10, the classification can be classified into three types, namely, a case in which the degree of motion of the current block is small, medium, and large. In each case, the embodiment described with reference to FIG. 8 or 9 may be applied. Table 10 shows a case where the embodiment described with reference to FIG. 9 is applied.

Here, if the current block is the first of the frame, motion estimation is performed by applying UCDS. This is because the edges of the frame are generally more likely to be backgrounds, and the backgrounds can be said to be the least moving parts.

Experiment Results and Analysis

In order to evaluate the performance of the proposed algorithm according to one embodiment of the present invention (when predicting the degree of motion of the current block as described in Table 10 and applying the embodiment shown in FIG. 9), MPEG-4 Experiments were performed using the VM encoder. All images were encoded with IPPP, and the rate control was applied to TM5. The video used in the experiment was CIF (352 × 288), "football," "akiyo," "bus," "news," "tempete," "waterfall," "bridge," "coastguard," "container," " Foreman, "" hallway, "" mobile, "" paris, "" silent, "" Stefan, "" table, "and" flower "were each tested for 100 frames. Search method, new three-step search method, four-step search method, BBGDS, diamond search method, hexagon-based search (HEXBS), cross diamond search method (CDS), and new cross diamond search method (NCDS) Used. The size of the macroblock used for the motion prediction is 16 × 16 pixels, and the experiment was performed by applying the displacement ± 7 of the search area.

As a performance comparison function, peak signal-to-noise ratio (PSNR) using mean squared error (MSE) was used to evaluate the quality of image quality. SAD was used. Also, to measure the performance improvement of the proposed algorithm, the number of search points per block is compared with the existing algorithms.

MSE and PSNR, functions used to compare and evaluate the performance of the search algorithm, are shown in Equations 4 and 5, respectively.

는 원영상의 화면을 나타내고,

는 움직임 예측 화면을 나타낸다.In Equation 4 and Equation 5, M and N represent the horizontal and vertical size of the image, respectively,

Indicates the screen of the original image,

Shows a motion prediction screen.

A function SAD for measuring a matching error of a block is shown in Equation 6.

은 현재 프레임을 나타내고,

은 이전 프레임을 나타낸다.In Equation 6, MB represents the horizontal and vertical size of the macro block,

Represents the current frame,

Indicates the previous frame.

The experimental results for the experimental images are shown in Table 11, Table 12, and Table 13, respectively. Table 11 and Table 12 show the three-step search method, the new three-step search method, the four-step search method, BBGDS, the diamond search method, the hexagon search method, the cross diamond search method, the new cross diamond search method, and the average PSNR of the proposed algorithm. Each of the MSE is shown, and Table 13 shows the average number of search points per block.

As shown in Tables 11 and 12, the proposed search algorithm maintains PSNR and MSE similar to the existing fast search algorithm for most images. Compared with the search technique, PSNR and MSE are better for moving images such as "football," "bus," and "Stefan."

As shown in Table 13, the number of search points is reduced on average by 16.35 search points per block when compared to the three-stage search method, and by 6.92 search points when compared with the diamond search method. . And when compared with the cross diamond search method and the new cross diamond search method, the number of search points is reduced from 4.27 to 0.85 on average.

As described in detail above, according to an embodiment of the present invention, in view of the high spatial correlation between the current block and the neighboring block, the current block using the motion vector, the number of search points, and / or the SAD of the neighboring blocks. We estimate the degree of motion and apply the optimal fast block matching technique according to the prediction result. In particular, according to an embodiment of the present invention, the motion vector may be estimated at high speed by selecting the most appropriate algorithm among the UCDS, DS, and / or CTSS algorithms according to the degree of motion of the current block to perform motion estimation. According to this embodiment of the present invention, it is possible to find a matching block more quickly with less computation while maintaining the same image quality as the fast block matching algorithm proposed previously.

1A is a diagram illustrating a pattern of motion estimation according to a three-stage search technique.

FIG. 1B is a diagram illustrating the minimum number of search points for each pixel when using a three-stage search technique in a search region in a range of ± 7 pixels.

2A is a diagram illustrating a pattern of motion estimation according to a new three-stage search technique.

FIG. 2B is a diagram showing the minimum number of search points for each pixel when using the new three-stage search technique in a search region in the ± 7 pixel range.

3A is a diagram illustrating a pattern of motion estimation according to a four-stage search technique.

FIG. 3B is a diagram illustrating the minimum number of search points for each pixel when using a four-stage search technique in a search region in a range of ± 7 pixels.

4A is a diagram illustrating a pattern of motion estimation according to a block-based gradient search (BBGDS) technique.

FIG. 4B is a diagram showing the minimum number of search points for each pixel when using the BBGDS technique in the search region in the range of ± 7 pixels.

5A is a diagram illustrating a pattern of motion estimation according to a diamond search technique.

FIG. 5B shows the minimum number of search points for each pixel when using the diamond search technique in a search region in the range of ± 7 pixels.

6 is a flowchart illustrating a motion estimation method according to an embodiment of the present invention.

7 is a diagram illustrating the positions of neighboring blocks used to predict the degree of motion of the current block according to an embodiment of the present invention.

FIG. 8A shows the minimum number of search points per pixel when considering a three-step search technique, a new three-step search technique, a four-step search technique, a BBGDS technique, and a diamond search technique in a pixel search range of ± 7. FIG. to be.

FIG. 8B is a diagram illustrating a kind of fast searching algorithms having a minimum number of search points in each pixel.

9 is a flowchart illustrating a motion estimation method according to another embodiment of the present invention.

10A-10F illustrate patterns of motion estimation according to an improved cross diamond search technique (UCDS).

11A and 11B illustrate a pattern of motion estimation according to a crosswise three-step search technique (CTSS).

Claims (7)

In the block matching method for motion estimation, Predicting a movement degree of the current block by using information of one or more neighboring blocks of the current block; And The degree of movement of the current block is divided into small (S), large (L), and middle (M), and an improved cross diamond search technique is based on the divided motion degree. UCDS), Cross Three Step Search (CTSS), and Diamond Search (DS) to find any matching block for the current block. The method of claim 1, wherein the neighboring blocks include one or more blocks among blocks located on the left side, the upper side, and the upper right side with respect to the current block, The information of the neighboring blocks includes the length of the motion vector (MV _length ), the number of search points (SP), of the neighboring blocks defined by Equations (E-1), (E-2), and (E-3). And one or more of the sum of absolute values (SAD) of the differences.

(E-1)

(E-2)

(E-3) Here, the subscripts left, above, and above-right indicate the position of the neighboring block with respect to the current block, respectively, and MV _left , MV _above , and MV _above-right respectively indicate the x-axis component (MV _x ) and the MV of the block. The maximum value is determined among the y-axis components MV _y , and the operation average (x, y, z) represents an average value of three numbers x, y, and z, and the operation int (x) indicates an integer part of the real number x. 3. The method of claim 2, wherein at least two pieces of information among a _length of the motion vector (MV _length ), a number of search points (SP), and a sum of absolute values of a difference (SAD) are predicted to have a small degree of motion of the current block. Or, if only one piece of information predicts that the movement degree of the current block is small and the other two pieces of information predict that the movement degree of the current block is medium, the step of finding a matching block for the current block is improved. A fast block matching method characterized by applying an upgraded cross diamond search (UCDS). The method of claim 2 or 3, wherein at least two pieces of information among the length of the motion vector (MV _length ), the number of search points (SP), and the sum of absolute values (SAD) of the differences are included in the degree of motion of the current block. In the case of predicting a to be large, the fast block matching method of applying a cross three step search technique (CTSS) in the step of finding a matching block for the current block. The method of claim 4, wherein at least two pieces of information among the length of the motion vector (MV _length ), the number of search points (SP), and the sum of absolute values of the difference (SAD) are in a medium degree of motion of the current block. The other information that predicts and predicts that the current degree of motion of the current block is medium or large or the sum of the length of the motion vector (MV _length ), the number of search points (SP), and the absolute value of the difference (SAD) If the predicted degree of motion of the current block is different from each other, the step of finding a matching block for the current block (Diamond Search, DS) is a fast block matching method, characterized in that for applying. The method of claim 1, wherein the UCDS is applied when the movement degree of the current block is predicted to be small, and the DS is applied when the movement degree of the current block is estimated to be medium. The fast block matching method, wherein the CTSS is applied when the degree is expected to be large. delete

Images