Motion estimation method utilizing modified rhombus pattern search for a succession of frames in digital coding system

A motion estimation method for a succession of frames in a digital coding system includes: a) with reference to a first block in a first frame, searching a second frame for a second block that corresponds to the first block; and b) estimating a motion vector of the first block on the basis of the second block in the second frame; wherein step a) includes: a1) forming a first initial search range including a virtual rhombus-shaped pattern substantially centered at a pre-determined block, and a2) expanding progressively outward a second initial search range based on the virtual rhombus-shaped pattern.

CROSS-REFERENCE TO RELATED APPLICATION

This application claims priority of Taiwanese Application No. 094108599, filed on Mar. 21, 2005.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The invention relates to a motion estimation method in video processing, more particularly to a motion estimation method utilizing a modified rhombus pattern search for a succession of frames in a digital coding system.

2. Description of the Related Art

Referring toFIG. 1, the data structure of a data stream of an MPEG coded video is shown to be formed from one or more sequences. Each sequence includes one or several groups of pictures (GOP), which refers to a group consisting of a plurality of pictures or frames. These pictures or frames can be classified into three types, i.e., intra-coded frames (I frame), predictive-coded frames (P frame), and bi-directionally predictive-coded frames (B frame), according to their attributes.

Each of the aforesaid frames can be encoded. Generally, I frames are used as cut-in points during video compression. A P frame can be predicted through motion estimation using an I frame or another P frame as a reference frame, whereas a B frame can be predicted from the motion vectors generated by both an I frame and a P frame or by two P frames which serve as reference frames. Thus, by presenting the frames successively, the MPEG video can be presented to a user.

In MPEG compression standards, each frame is divided into a plurality of slices. Each slice is further divided into a plurality of macroblocks (MB). Each macroblock is composed of four luminance blocks and a plurality of chrominance blocks. Each block is defined as the smallest coded unit of the MPEG data structure. The corresponding inverse operation of motion compensation in MPEG video coding is motion estimation. The most direct way of implementing motion estimation is to record the luminance and chrominance of each pixel in a macroblock or in a block, and use the information in a full search to find the best matched motion vector in the search area. However, such a scheme involves consumption of large amounts of resources.

With the use of motion estimation, the blocks in the current frame can be reconstructed by 1) shifting the best-matched blocks in the reference frame with the motion vectors found in the aforesaid motion estimation as well as 2) the small differential data between blocks in the current frame and best-matched blocks in the reference frame. Since it is not necessary to store a large amount of redundant data, the amount of stored data can be reduced to thereby achieve the object of data compression. Current motion estimation methods include the Full Search (FS), the Three-Step Search (TSS), the Four-Step Search (FSS), and the Diamond Search (DS).

In the conventional Diamond Search (DS), a search area in either one of the two diamond patterns is searched. This search scheme involves the following steps:

Step 1: An origin point and eight other points that surround the origin point and that lie on the boundary of a hollow diamond-shaped search area are found so that there are altogether nine search points. If the best matched point is found to be at the center of the search area, the flow proceeds to step 4. On the other hand, if the best matched point is found to be on the boundary of the search area, the flow proceeds to step 2.

Step 2: Set the center to the best matched point found in step 1, and continue the search using the hollow diamond-shaped search area.

Step 3: If the best matched point is still found to be at the center of the new search area, step 4 is performed. On the other hand, if the new best matched point is found to be on the boundary of the new search area, step 2 is repeated.

Step 4: The search area is reduced to a smaller solid diamond. The search is stopped because the (local) best matched point is found.

The aforesaid scheme is further illustrated with reference toFIG. 2A. In step 1, the initial best matched point is found to be at the center (1a) of the search area, and step 4 is therefore performed in the reduced search area, a smaller solid diamond. The search is ended when the (local) best-matched point (2a) is located.

Referring toFIG. 2B, when the initial best matched point (1b) in step 1 is found to be located on the boundary of the search area, step 2 is performed to form another hollow diamond-shaped search area centered at the initial best matched point (1b). Then step 3 is performed. Since the new best matched point (2b) is found to lie on the boundary of the new search area, step 2 is repeated to form yet another hollow diamond-shaped search area centered at the new best matched point (2b). When it is found that the latest best matched point is located at the center of the search area, step 4 is performed in the reduced search area, a smaller solid diamond. The search is ended when the ideal point (4b) is found.

However, in the conventional diamond search scheme, as the search begins with blocks on the boundary of a larger hollow diamond centered at an origin point before searching blocks in a smaller solid diamond, where probabilities that the best matched block is located are higher, the search efficiency is relatively low.

SUMMARY OF THE INVENTION

Therefore, the object of the present invention is to provide a motion estimation method utilizing a modified diamond search for a succession of frames in a digital coding system so as to increase search efficiency.

Accordingly, a motion estimation method utilizing a modified rhombus pattern search for a succession of frames in a digital coding system comprises:

a) with reference to a first block in a first frame, searching within at least one portion of a second frame for a second block that corresponds to the first block; and

b) estimating a motion vector of the first block with respect to the second block in the second frame;

wherein step a) includes: a1) forming a first initial search range including a virtual rhombus-shaped pattern substantially centered at a pre-determined block, and a2) expanding progressively outward a second initial search range based on the virtual rhombus-shaped pattern or a subset of virtual rhombus-shaped patterns.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

Referring toFIG. 3, a system for implementing the motion vector estimation method according to the present invention is shown to be embodied in a video coding device1capable of MPEG video compression. However, it should be apparent to those skilled in the art that the present invention may also be applied to a processing system that performs functions similar to video compression.

The video coding device1includes a preprocessor10, a motion estimation unit11, a motion compensation unit12, a motion vector encoding unit13, a texture encoding unit14, a bit stream composer15, and a memory16.

When an image100is input into the video coding device1, the preprocessor10initially defines the data of each macroblock in a given frame for temporary storage in the memory16. Thereafter, the motion estimation unit11calculates the data of the macroblocks in the given frame of the image100, e.g., motion vector data102of the blocks in the entire frame can be obtained by calculating the data101of the corresponding blocks in two adjacent frames for subsequent input into the motion compensation unit12. The motion compensation unit12retrieves macroblock data from a preceding or succeeding frame using the motion vectors so as to obtain reference data104. By subtracting the reference data104obtained by the motion compensation unit12from the macroblock data of the image100obtained by the preprocessor10, differential data103can be obtained. The differential data103undergo computation by the texture encoding unit14to obtain compressed texture and reconstructed reference data.

The texture encoding unit14has a discrete cosine transform unit141which applies discrete cosine transform (DCT) to the pixels of each block, and converts the DCT-pixel data from the spatial domain to the frequency domain. Then, a quantization unit143is employed to perform a quantization step to quantize DCT coefficients and to remove high-frequency portions. Moreover, an inverse quantization unit144and an inverse discrete cosine transform unit145are used to perform inverse quantization and inverse discrete cosine transform computations for feedback to the motion estimation unit11. The motion vector encoding unit13encodes and outputs each of the motion vectors to a variable length encoder151of the bit stream composer15.

Furthermore, an alternating current/direct current (AC/DC) prediction unit146is required to remove redundant information of blocks in the same frame. A zigzag scanning unit147is then used to perform a zigzag scan to rearrange the quantized DCT coefficients such that the low-frequency coefficients are placed in the front whereas the high-frequency coefficients are placed at the back. Thereafter, the rearranged DCT coefficients are subjected to run length coding (RLC). Finally, another variable length encoder152of the bit stream composer15is used to perform variable length coding (VLC) on both the low-frequency coefficients and the high-frequency coefficients for composition by the bit stream composer15, thereby completing output in the MPEG compression format.

Referring toFIGS. 3 and 4, the preferred embodiment of a motion estimation method utilizing a modified rhombus pattern search according to the present invention is adapted to be implemented in the motion estimation unit11of the video coding device1. In the method of this invention, with reference to a first block41in a first frame401(also referred to as a current frame), a second frame402(also referred to as a reference frame) adjacent to the first frame401is searched to find a second block42corresponding to the first block41. A motion vector43of the first block41is then estimated on the basis of the second block42. In the method, a first initial search range including a virtual rhombus-shaped pattern substantially at a candidate pre-determined origin block is first formed in the second frame402, and candidate blocks in the first initial search range are searched to locate a best matched block. The first initial search range is expanded progressively outward to form a second initial search range, and candidate blocks in the second initial search range are searched to locate a new best matched block, if the best matched block is on a boundary of the first initial search range.

In the preferred embodiment, the first initial search range is formed by the candidate origin block and virtual rhombus-shaped candidate blocks, or a subset of virtual rhombus-shaped candidate blocks neighboring the candidate origin block, and the second initial search range is a virtual rhombus-shaped search range that is centered at the best matched block found in the first initial search range and that overlaps partly the first initial search range.

In the preferred embodiment, an expanded search range, which is a rhombus-shaped search range that is centered at a latest best matched block and that overlaps partly a previous expanded search range, is formed and searched if the latest best matched block is found to be on a boundary of the previous expanded search range. Preferably, the expanded search range is formed and searched if the latest best matched block is found on the boundary of the expanded search range after searching only un-searched candidate blocks (which may include three or five candidate blocks) on the boundary of the expanded search range. In addition, the candidate blocks in the inner part of the expanded search range are searched only when the latest best matched block is found not to be on the boundary of the expanded search range.

The second frame402to be searched has a temporal relation with the first frame401, i.e., the second frame402precedes or succeeds the first frame401in a temporal sequence. Moreover, searching of a search range preferably proceeds along a spiral path that moves in either a clockwise or counterclockwise direction.

Referring toFIG. 5, which is a flowchart of the preferred embodiment of the motion estimation method utilizing a modified rhombus pattern search according to the present invention, in step601, an initial search range including a virtual rhombus-shaped pattern substantially centered at a candidate pre-determined origin block is defined, and all thirteen candidate blocks in the initial search range are searched to locate a best matched block. Then, step602is performed to determine whether the best matched block is located in the inner part of the initial search range. If it is determined in step602that the best matched block is located in the inner part of the initial search range, i.e., the best matched block is one of the five candidate blocks in the smaller inner rhombus, the flow skips to step606to terminate the search and to estimate the motion vector on the basis of the best matched block thus located. If it is otherwise determined that the best matched block lies on the boundary of the initial search range, i.e., the best matched block is one of the eight candidate blocks bounding the initial search range, the flow proceeds to step603. In step603, an expanded search range based on the virtual rhombus-shaped pattern and centered at the best matched block found in step601, which overlaps partly the initial search range, is defined, and un-searched candidate blocks on the boundary of the expanded search range are searched to locate a new best matched block. In particular, five un-searched candidate blocks (i.e., blocks2; seeFIG. 6C) lying on the boundary of the expanded search range will be searched if the best matched block found in step601is at a vertex of the first initial search range, whereas three un-searched candidate blocks (i.e., blocks3; seeFIG. 6B) lying on the boundary of the expanded search range will be searched if the best matched block found in step601is located on an edge of the initial search range.

Then, in step604, it is determined whether the latest best matched block is found to be on the boundary of the expanded search range. In the negative, the flow proceeds to step605to search the un-searched candidate blocks within the expanded search range for the latest best matched block. The flow goes to step606thereafter. On the other hand, if the latest best matched block is determined to be located on the boundary of the expanded search range in step604, the flow returns to step603, in which a rhombus-shaped expanded search range that is centered at the latest best matched block and that overlaps partly the previous expanded search range, is formed, and three un-searched candidate blocks (blocks3inFIG. 6B) or five un-searched candidate blocks (blocks3inFIG. 6C) on the boundary of the expanded search range are searched depending on the relative position of the latest best matched block. The search is continued in this rhombic pattern until the best matched block is found to be located within the boundary of the latest expanded search range.

The method of this invention will be further illustrated with reference toFIGS. 6A,6B and6C, in combination withFIG. 5.

Referring toFIG. 6A, a search is conducted through all thirteen candidate blocks1in an initial search range that includes a virtual rhombus-shaped pattern centered at a candidate origin block to locate a best matched block (step601). Then, a determination is made as to whether the best matched block (1v) is located in the inner part of the initial search range, i.e., one of the five candidate blocks in the smaller inner rhombus. When the best matched block (1v) is found to be located in the inner part of the initial search range, the search is terminated, and the motion vector is estimated on the basis of the best matched block thus located (step606).

Referring toFIGS. 6B and 6C, a first search is conducted through all thirteen blocks1in a virtual rhombus-shaped initial search range to locate a best matched block (step601). Since the best matched block (1v) is located on the boundary of the initial search range (step602), a second search is performed using a virtual rhombus-shaped expanded search range that is centered at the best matched block (1v) and that overlaps partly the initial search range. In particular, the three un-searched candidate blocks2(FIG. 6B) or the five un-searched candidate blocks2(FIG. 6C) on the boundary of the expanded search range are searched to locate a latest best matched block (step603). Then, a determination is made as to whether the latest best matched block (2v) is found to be on the boundary of the expanded search range (step604). Since the latest best matched block (2v) is located on the boundary of the expanded search range, a third search is performed using a rhombus-shaped expanded search range that is centered at the best matched block (2v) and that overlaps partly the previous expanded search range. In particular, the three un-searched candidate blocks3(FIG. 6B) or the five un-searched candidate blocks3(FIG. 6C) lying on the boundary of the expanded search range are searched (step603). As the latest best matched block (2v) is still the best matched block according to the result of the third search, i.e., the best matched block (2v) is now located in the inner part of the expanded search range, a fourth search is performed through the un-searched candidate blocks in the inner part of the expanded search range and closest to the best matched block (2v), and the latest best matched block (4v) is located (step605). Thereafter, the search is terminated, and the motion vector is estimated on the basis of the latest best matched block (4v) (step606).

FIGS. 7 to 9illustrate search patterns adopted in alternative embodiments of the method according to the present invention.

In the alternative embodiment shown inFIG. 7, the candidate origin block and four candidate blocks neighboring the candidate pre-determined origin blocks define an initial search range. If the best matched block is found from one of the four candidate blocks surrounding the candidate origin block, the initial search range is expanded outwardly in a rhombic pattern to result in an expanded search range that includes eight un-searched candidate blocks surrounding the initial search range. The expanded search range is further expanded outwardly in this rhombic pattern relative to the candidate origin block to locate the best matched block until the block that corresponds to the first block41in the first frame401is found to be within the rhombic boundary of the latest expanded search range.

Similarly, in the alternative embodiment shown inFIG. 8, the candidate origin block and four candidate blocks neighboring the candidate pre-determined origin block define an initial search range. When the best matched block is found from one of the four candidate blocks surrounding the candidate origin block, the initial search range is expanded outwardly in a rhombic pattern to result in an expanded search range that includes five un-searched candidate blocks closest to the best matched block, depending on the relative position of the best matched block that was located. The expanded search range is further expanded outwardly in this rhombic pattern to locate the best matched block until the block that corresponds to the first block41in the first frame401is found to be in the inner part of the latest expanded search range.

The search pattern illustrated inFIG. 9is similar to that depicted inFIG. 8. The difference resides in that, when the best matched block is one of the four candidate blocks surrounding the candidate pre-determined origin block, the initial search range is expanded outwardly in a rhombic pattern to result in an expanded search range that includes three un-searched candidate blocks which are adjacent to the best matched block, depending on the relative position of the best matched block that was located.

In sum, since motion vectors generally have radiating characteristics, in the motion estimation method according to the present invention, blocks in an initial search range including a virtual rhombus-shaped pattern are first searched, and the initial search range is expanded in a rhombic pattern with reference to a latest best matched block thus located. Since the search is first conducted in a rhombus-shaped initial search range, the present invention can save unnecessary search time, thereby enhancing the search efficiency.