Adaptive multi-modal motion estimation for video compression

[0002] The present invention relates to video compression, and more particularly to adaptive multi-modal motion estimation for video compression.

[0003] The use of motion compensation in video coding plays an important role in achieving better compression efficiency by removing the temporal redundancy in video sequences. The MPEG-2 video compression standard, as defined in ANSI-ISO/IEC 13818-2 (1995) and MPEG2 Test Model 5 (1993), uses a block-based motion estimation and compensation technique. A displaced frame difference (DFD) is a common error measure used in block matching motion estimation algorithms. The block matching process in general searches for minimum block sums of absolute DFD errors between frames at times t and t+n.

[0004] The computational cost for an exhaustive search is extremely high, especially for large search ranges. This has prompted many research activities in seeking a more efficient method. Some well-known techniques include hierarchical search, as described in Bierling's “Displacement Estimation by Hierarchical Block Matching”, SPIE Visual Communications and Image Processing 1988, Vol. 1001, pp.942-951, logarithmic search, such as described in Jains' “Displacement Measurement and its Application in Interframe Coding for Video Conferencing”, IEEE Transactions on Communications, Vol. COM-29, pp. 1779-1806 (1981), etc. These methods are designed to reduce the computational load, but further improvements are still possible.

[0005] For video compression systems operating at high bit rates, the cost of transmitting motion vectors may be negligible. But for medium to low bit rates, the cost of transmitting motion vectors has to be taken into account. A cost function C(mv) is formulated for which an optimum estimator seeks a set of displacement vectors (mv) to minimize:

[0006] C(mv)=ΣD(mv)+λ*ΣL(mv)

[0007] where D(mv) is the sum of absolute pixel DFD(mv) for each block, L(mv) is the motion vector code length, and λ is a constant that weights the relative cost of transmitting motion vectors with respect to the total bit rate. The summation is calculated over the entire frame.

[0008] To find a global minimum for the cost function is an extremely difficult problem, especially given the fact that due to differential coding the cost of L(mv) is affected by the neighboring blocks. In practice the ideal motion estimation algorithm is likely to be adaptive to the characteristics of the moving video sequences. The motion search range has to cover not only all possible movements, but also no more than is necessary. For example when the video sequence contains slow moving scenes, the search range should be correspondingly small, otherwise spurious false matching is likely to expand the cost of L(mv). On the other hand if the movements are larger than the search range, the residue error D(mv) is high and the effectiveness of the motion compensation is degraded. So the search range has to be large enough to handle fast moving video sequences.

[0009] The two factors mentioned above show that an adaptive algorithm is most likely to achieve near optimum performance. Therefore what is desired is an adaptive motion estimation algorithm for video compression that copes with the motion dynamics of the video sequences.

[0010] Accordingly the present invention provides an adaptive multi-modal motion estimation algorithm for video compression using an adaptive pivot and multi-modal search method. A luminance pyramid is built such that at the top (Nth) level each pixel represents 2{circumflex over ( )}N*2{circumflex over ( )}N pixels in the base pyramid. A basic correlation is done at the top level for images at times t and t+n, with the location of a peak level defining a global motion vector between images. The global motion vector is used as a pivot point for subsequent top-level block motion search and to define a search area. The top level image is subdivided into M×N blocks and a pivot search is carried out around the pivot point in the search area. The block motion vectors from a higher level serve as initial conditions for a finer resolution level. The results of the segmentation and refinement process determine whether a zero pivot motion search is desired, such as when a camera is tracking a fast moving object. Finally the refinement and zero pivot searches are repeated for every level of the pyramid until the base, full resolution level is done, resulting in estimated motion vectors for the image.

[0011] The objects, advantages and other novel features are apparent from the following detailed description when read in conjunction with the appended claims and attached drawing.

[0012] FIG. 1 is an illustrative view of the pivot and zero pivot searches according to the present invention.

[0013] FIG. 2 is a flow diagram view of the adaptive multi-modal estimation algorithm according to the present invention.

[0014] The following describes an adaptive motion search technique for a simple one directional block motion estimation process. For bi-directional motion search the same method may be easily extended.

[0015] First: Luma Pyramid. For every incoming field/frame, extract the full resolution luminance signal as the base level (level 0) of a Gaussian pyramid. The next higher level of the pyramid is calculated by low-pass filtering and sub-sampling the current level. At the top (Nth) level each pixel represents the equivalent spatial coverage of 2{circumflex over ( )}N*2{circumflex over ( )}N pixels in the base level.

[0016] Second: Top Level, Dominant (Global) Motion Search. Using a basic correlation technique, as described in Hall's “Computer Image Processing and Recognition”, Academic Press 1979, pp. 480-484, the top level images at times t and t+n are correlated. The location of a peak in of the resulting correlation surface is found. This location defines the dominant (global) motion vector (gdx, gdy) between the two images. The correlation is carried out using the whole image of the top-level image.

[0017] Third: Search Range and Pivot Point. The dominant vector is used as a pivot point (fixed offset) for subsequent top-level block motion search. From the dominant vector the shape and value of a search range is derived as shown in the following pseudo code:

[0018] /*Adjust search range and shape according to estimated global vector gdx, gdy.*/

[0019] void adjustrange(int gdx, int gdy, int total, int max, int min, int*xRange, int*yRange)

[0020] {

[0021] double ratio;

[0022] if(gdx<0) /*total is the total search area*/

[0023] gdx=-gdx;

[0024] if gdy<0) /*so that the total computation cost is fixed*/

[0025] gdy=-gdy;

[0026] if(gdx<min) /*min and max are limiting constants*/ gdx=min;

[0027] if(gdy<min)

[0028] gdy=min;

[0029] if(gdx>max)

[0030] gdx=max;

[0031] if(gdy>max)

[0032] gdy=max;

[0033] ratio=(double)gdx/(double)gdy,

[0034] *xRange=(int)sqrt((double)total*ratio);

[0035] *yRange=(int)sqrt((double)total/ratio);

[0036] Fourth: Block Pivot Search. Sub-divide the top-level image in M×N pixel blocks. For every block in the current top-level image, a pivot search as shown in FIG. 1 is carried out around the pivot point in the search area. The pivot point is determined by:

[0037] Px=gdx+Cx;

[0038] Py=gdy+Cy;

[0039] where Cx and Cy locate the northwest corner coordinates of the current block, Px and Py locate the northwest comer coordinates of the search area, and the search (*xRange, *yRange) is determined in step three above.

[0040] Fifth: Motion Field Segmentation and Refinement. The block motion vectors from the higher level serve as initial conditions for the next finer resolution level, such motion field segmentation and refinement being known in the art as shown in U.S. Pat. No. 5,748,247.

[0041] Sixth: Second Mode. Zero Pivot Motion Search. If the segmentation and refinement results in a small D(mv), then the zero pivot search is not necessary. The motion vector (mv) from the fifth step is chosen as the motion vector for the current block. Otherwise if D(mv) is large, it is likely that a camera is tracking a fast moving target (zero motion), with the background panning at the corresponding relative speed. In this mode of operation, which is very common for capturing sports scenes, a zero pivot motion search is necessary. A search with zero pivot and small search range constitutes this step. The motion vector that results in a smaller D(mv) between steps 5 and 6 is chosen as the motion vector for the current block.

[0042] Seventh: Working Down the Pyramid Levels. The motion field segmentation, refinement and zero pivot search steps are carried out for every block in the current pyramid level. These steps are repeated also for the next lower-pyramid level until the full resolution level is done. The result is a set of motion vectors for the full resolution image.

[0043] Thus the present invention provides an adaptive multi-modal motion estimation algorithm for video compression that adapts to the dynamics of moving video sequences and has the capability to cover very wide search ranges adaptively with a fixed computational cost.