CN101090491B - Enhanced Block-Based Motion Estimation Algorithm for Video Compression - Google Patents

Abstract

A method, system and software are presented for obtaining blocks of a first image that are similar to blocks of a second image (a "reference image"). The blocks of the first image are processed sequentially, a plurality of candidate locations in the second image are derived for each block, and a cost function is evaluated for each candidate location. Each candidate location in the second image is replaced by a respective motion vector from the block of the first image. In the first aspect of the invention, the cost function is a function of a predicted motion vector of a future block of the first image (i.e. a block of the first image that has not yet been processed). In the second aspect of the present invention, the motion vector is given by position values which are not all of full-pixel space, half-pixel space, or 1/4-pixel space.

Description

Enhanced Block-Based Motion Estimation Algorithm for Video Compression

related application

This application claims priority to US Provisional Patent Application 60/691,181, filed June 17, 2005, which is hereby incorporated by reference in its entirety.

technical field

The present invention relates generally to methods and systems for digital signal compression, encoding and representation, and more particularly to methods and systems using multi-frame motion estimation (ME). The invention further relates to a computer program product, such as a recording medium, carrying program instructions readable by a computing device to cause said computing device to perform a method according to the invention.

Background technique

Due to the enormous size of raw digital video data (or image sequences) used by modern multimedia applications, this data must be compressed so that it can be transmitted and stored. There are many important video compression standards, including ISO/IEC MPEG-1, MPEG-2, MPEG-4 standards and ITU-TH.261, H.263, H.264 standards. The ISO/IEC MPEG-1/2/4 standard is widely used in the entertainment industry to distribute movies, digital video broadcasts including video compact discs or VCDs (MPEG-1), digital video discs or digital versatile discs or DVDs (MPEG-2 ), Recordable DVD (MPEG-2), Digital Video Broadcasting, Digital Video Broadcasting or DVB (MPEG-2), Video On Demand or VOD (MPEG-2), High Definition Television or HDTV in the US (MPEG-2 )etc. The MPEG-4 standard is more advanced than MPEG-2, and can achieve high-quality video at a lower bit rate, which makes it very suitable for the Internet, digital wireless networks (such as 3G networks), multimedia information services (MMS standard from 3GPP ) and more. MPEG-4 is adopted by the next generation High Definition DVD (HD-DVD) standard and MMS standard. The ITU-TH.261/3/4 standard is designed for low-latency video telephony and video conferencing systems. The early H.261 standard was designed to work at p ^* 64kbit/s, p = 1, 2, . . . , 31. The late H.263 standard is very successful and is widely used in modern video conferencing systems, and for video information flow in broadband networks and wireless networks, where wireless networks include multimedia information in 2.5G and 3G networks and other networks service (MMS). The latest standard, H.264 (also known as MPEG-4 version 10, or MPEG-4 AVC) is the current state-of-the-art video compression standard. It is so powerful that MPEG decided to develop it jointly with ITU-T in the framework of JointVideoTeam (JVT). The new standard is called H.264 in the ITU-T, and is called MPEG-4 Advanced Video Coding (MPEG-4 AVC), or MPEG-4 version 10. H.264 is used in the HD-DVD standard, the Direct Video Broadcasting (DVB) standard and possibly the MMS standard. Based on H.264, a related standard called Audio Visual Standard (AVS) is currently being developed in China. AVS1.0 is designed for high-definition television (HDTV). AVS-M is designed for mobile applications. H.264 has the objective and subjective video quality exceeding MPEG-1/2/4 and H.261/3 standards. In addition to using an integer 4x4 discrete cosine transform (DCT) instead of the traditional 8x8DCT, the basic coding algorithm of H.264 [1] is similar to H.263 or MPEG-4, and has additional features, including inter-frame prediction of I frames modes, multiple block sizes and multiple reference coordinate systems for motion estimation/compensation, quarter-pixel precision for motion estimation, in-loop deblocking filters, content-adaptive binary arithmetic Coding (context adaptive binary arithmetic coding), and so on.

Motion estimation is the core part of most video compression standards (such as MPEG-1/2/4 and H.261/3/4), which makes full use of time redundancy, so its performance directly affects the compression efficiency of video coding systems, Subjective video quality as well as encoding speed.

In block matching motion estimation (BMME), the most common measure of distortion between the current block and the reference block in ME is the sum of absolute differences (SAD), which for an N×N block is defined as

$\mathrm{<span\; class="notranslate">\; SAD</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; mvx</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; mvy</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; mvx</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; mvy</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; |</span>$

Where F _t is the current frame, F _t-1 is the standard frame, (mvx, mvy) represents the current motion vector (MV). For a frame with width=X, height=Y, and block size=N×N, the total number of search points in the search range ± W where the SAD needs to be evaluated to find the optimal motion vector is equal to:

$<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; x</span>}}{\mathrm{<span\; class="notranslate">\; N</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; Y</span>}}{\mathrm{<span\; class="notranslate">\; N</span>}}<span\; class="notranslate">\; )</span>{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; W</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; ,</span>$

For the case of X=352, Y=288, N=16 and W=32, it is equal to 1673100. This is a huge number that consumes huge computing power in a video encoder. Many fast algorithms [2]-[9] have been proposed to reduce the number of search points in ME, such as three-step search (TSS) [11], 2D logarithmic search [12], new three-step search (NTSS) [ 3], MVFAST[7], and PMVFAST[2]. MVFAST and PMVFAST are significantly better than the first three algorithms because they perform center-off ME using the median motion vector predictor as the search center, thereby reducing the number of bits for MV coding by smoothing the motion vector field.

The PMVFAST algorithm (which is an important improvement over MVFAST and other fast algorithms, and thus accepted by the MPEG standard [10]) initially considers a set of MV predictors, including median, zero, left, top, top right, and previous Co-located MV predictor. Figure 1 illustrates the locations of the current block, the left block, the top block, the upper right block, the upper right block, and the right block (which is a "future block", ie, a block that is processed after the current block). It computes the SAD cost for each prediction. In a later development, PMVFAST was modified to compute the RD (rate-distortion) cost [13] instead of the SAD cost using the following cost function:

J(m,λ _motion )=SAD(s,c(m))+λ _motion (R(mp))(1)

where s is the original video signal, c is the reference video signal, m is the current MV, p is the median MV predictor for the current block, λ _motion is the Lagrange multiplier, and R(mp) denotes the bits used to encode the motion information. The next step in PMVFAST is to select the MV predictor with the minimum cost, and perform either a large diamond search or a small diamond search according to the value of the minimum cost obtained from the MV predictor.

A separate but important issue in defining current video coding standards is the use of sub-pixel predetermined vectors, including half-pixel, 1/4-pixel, or possibly even 1/8-pixel motion vectors, which provide a more precise description of motion and can provide full ~1dB PSNR gain for pixel motion estimation. With half-pixel precision, motion vectors can take equally spaced position values, such as 0.0, 0.5, 1.0, 1.5, 2.0, and so on. With 1/4 pixel precision, motion vectors can take position values such as 0.00, 0.25, 0.50, 0.75, 1.00, 1.25, 1.50, 1.75, 2.00, and so on. With 1/8 pixel precision, motion vectors can be in values such as 0.000, 0.125, 0.250, 0.375, 0.500, 0.625, 0.750, 0.875, 1.000, 1.125, 1.250, 1.375, 1.500, 1.625, 1.750, 1.875, 2.000, etc. position value.

It is well known that motion vector distributions tend to be center-shifted, which means that motion vectors tend to be very close to (0,0). This is illustrated in Figure 6(a), which shows the distribution of motion vectors in a Foreman sequence using the full search (FS) algorithm for (0,0) MV. Furthermore, as shown in Fig. 6(b), the motion vector distribution is also shifted towards the median predictor (median MV), which is the median value of the motion vector left block, top block and top right block shown in Fig. 1 . In addition, as shown in Figure 6(c), the motion vector is also offset to the adjacent motion vectors (leftMV, topMV, topRightMV) in the current frame and the motion vector (preMV) set in the previous frame, as shown in Figure 6( d) as shown. These can all be considered predictors for the motion vector of the current vector, and they can be used for PMVFAST.

Contents of the invention

It is an object of the present invention to provide new and beneficial techniques for motion estimation, applicable to methods and systems for compression, coding and representation of digital signals.

In particular, the present invention seeks to provide new and beneficial efficient motion estimation techniques that can be applied, for example, in MPEG-1, MPEG-2, MPEG-4, H.261, H.263, H.264 or AVS or other related in video coding standards.

The first aspect of the invention is based on the realization that the motion estimation of the PMVFAST algorithm, although it does have advantages over the prior art, is not optimal. In principle, for each frame in the video, there exists a motion vector field {m _i,j , i=0..M-1, j=0..N-1 }:

$\mathrm{<span\; class="notranslate">\; total</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; RD</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; cost</span>}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; SAD</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; the\; s</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; m</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; R</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; m</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; ]</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$

where (i,j) denotes the (i,j)th block in a frame containing MxN blocks. For a fixed _Qp (which is the quantization parameter), λ _i,j = λ = constant, and

p _i,j =median(m _i,j-1 ,m _i-1,j ,m _i-1,j+1 )(3)

However, this is impractical considering that the full RD cost for the entire frame requires exponential computational complexity at the same time. Thus, PMVFAST and other known algorithms only consider the RD cost of only one block at a time, instead of all blocks in a frame.

In particular, neither MVFAST nor PMVFAST take into account when deriving the motion vector relative to the current block, which results in changes in the median MV predictor for the next block. This can affect the smoothing of the entire motion vector field.

In general, the first aspect of the invention proposes a new ME algorithm by improving the cost definition and motion predictor candidate selection for PMVFAST. In particular, for each current block of the first image (the current block can be 16×16, 16×8, 8×16, 8×8, 4×8, 8×4, 4×4 or other rectangular lengths, even non-rectangular), similar blocks of the second image (reference image) are selected according to a cost function consisting of two terms: (i) a term for the measure of dissimilarity (e.g. SAD, SAE) between the current block and the similar block, and (ii) a term that is a function of at least a prediction of a motion vector for a future block of the first picture.

In particular, the proposed algorithm makes it possible to improve motion field smoothness by including the current median MV predictor and also the estimated median MV predictor of future (ie not yet processed) coded blocks.

Many variations of the invention are possible. In particular, the blocks can be of any size and of any shape.

There may be multiple second images (ie multiple reference values) and the search may include candidate positions in all of the second images.

Furthermore, the new cost function may be implemented for a plurality of sub-blocks which together form a larger region in the first image and are coded in a coding order defined by a coding number. These sub-blocks need not be of the same size or shape.

The invention has another aspect, which may be used in combination with or independently of the first aspect of the invention. Generally speaking, the second aspect of the present invention proposes that when the first image (the current block can be 16×16, 16×8, 8×16, 8×8, 4×8, 8×4, 4×4, or other Rectangular size, even non-rectangular) current block is encoded using a position value selected from a set of values different from those used in known techniques (i.e. in both axis directions The motion vectors of their respective components) are encoded.

Consider a possible motion vector predictor: (0, 0). Whereas conventional techniques of integer pixels allow motion vectors to take position values such as -2.0, -1.0, 0, 1.0, 2.0 etc., the second aspect of the invention proposes to modify the set of possible position values close to the predictor. For the closest position value of 1.0 to 0, we could use another position value such as 0.85, so that allowable position values would include -2.0, -0.85, 0, 0.85, 2.0 and so on. This has the advantage that, statistically, motion vectors tend to be close to zero. And, thus by choosing a position closer to 0, we will be closer to the true motion vector and thus can give better motion compensation which can lead to higher compression efficiency.

Thus, in a particular expression of the invention, it is possible to choose a set of possible position values for at least one axis direction, so that they cannot all be written Lm, where m=-...,2,-1,0,1,2 ..., and L is constant (eg, 1 pixel interval, 1/2 pixel interval, or 1/4 pixel interval); that is, the position values are non-uniform. In particular, it is possible to choose a set of possible position values for at least one axis direction such that they cannot all be written as m/n, where m=-...,2,-1,0,1,2,...and n is a power of 1 or 2.

Note that the second aspect of the invention is not limited to selecting a position value from a non-uniform set of spatial position values; nor is it limited to selecting only the two position values closest to zero compared to a traditional set of position values . As an example, in another example of the second aspect of the invention, a position value of 2.0 could be changed to 1.9, whereby allowable position values would include -1.9 , -0.85, 0, 0.85 , 1.9 , etc.

Thus, in an alternative specific expression of the second aspect of the invention, a set of possible position values is selected (for at least one of said directions) to include one or more position values which can be written as LA _{mm m} /n, where m=-..., 2, -1, 0, 1, 2.., n is a power of 1 or 2, L is a constant (such as 1 pixel interval, 1/2 pixel interval, or 1/4 pixel interval) , and A _m is a value less than 1 but at least 0.75 (optionally different for different values of m), more preferably at least 0.80, and most preferably at least 0.85.

We have found _that the optimal value of Am depends on the video.

An advantage of certain embodiments of the second aspect of the invention is that the motion vectors they produce can be coded using the same format codes as conventional algorithms, except that the conventional codes for the position values should be interpreted separately as the possible values used by this embodiment outside the positional value. For example, if the position values used by a particular embodiment are -1.9 , -0.85 , 0, 0.85 , 1.9 , etc., then a regular code for a position value of 1.0 should be interpreted as 0.85, and a regular code for a position value of 2.0 should be interpreted as 1.9, Wait.

The method according to the second aspect of the present invention may include the steps of: defining a search area, defining a plurality of candidate positions within the search area, the plurality of candidate positions including the position defined by the new position value of the second aspect of the present invention A set of multiple locations. These position values are corresponding displacement values from candidate positions at key positions (eg, (0,0) motion vector positions, predicted motion vectors, etc.). For each candidate motion vector, we compute a cost function which is the similarity measure (e.g. SAD, SAE) function. Optionally, it may also be a function of the motion vectors: said candidate motion vector, a current predicted motion vector, and optionally, as in the first aspect of the invention, one or more future predicted motion vectors. For example, optionally, as in the first aspect of the present invention, the cost function may be given.

Description of drawings

Embodiments of the invention will now be described by way of example only with reference to the following drawings, in which:

Figure 1 shows a current block, a left block, a top block, an upper right block, an upper right block, and a right block;

Figure 2 shows a typical distribution of Diff, which is the difference between |m _i,j+1 — p _i,j+1 | and |m _i,j — p _i,j+1 |;

Fig. 3a shows the search mode of the giant diamond search as used in the first embodiment of the present invention;

Figure 3b shows the search pattern of the modified giant diamond search as used in the first embodiment of the invention;

Fig. 4 shows the search mode of the small diamond search as used in the first embodiment of the present invention;

Figure 5a and 5b compare the smoothness of the MV domain of PMVFAST and the first embodiment of the present invention;

Fig. 6 shows (a) (0,0) MV in current frame, (b) median MV, (c) adjacent MV and MV configured in previous frame, (d) MV in previous frame The MV (PreBottomRightMV) on the lower right uses the full search (FS) algorithm to obtain the motion vector distribution in the Foreman sequence;

Fig. 7 is a flowchart of the first embodiment of the present invention.

detailed description

The first embodiment of the present invention adopts many features of the PMVFAST algorithm, but improves upon PMVFAST (and other existing algorithms) by considering several neighboring blocks instead of just one. Equations (2) and (3) show that the selection of the current block MV directly affects the RD cost of neighboring blocks, including the right block (or (i, j+1)th block), the lower left block (or (i+1, j-1) block), and the following block (or (i+1, j)th block). This is because the current MV will affect the predicted MVs of these neighboring blocks, and thus in turn affect the best motion vectors for those blocks. These are "future" blocks because no motion estimation has been performed on them when the current block is processed. We cannot compute the best motion vectors for these future blocks concurrently with the current block, because we would need to compute the best motion vectors for all blocks in the whole frame simultaneously according to equation (2), which would be very complicated.

Instead, to evaluate the implications of the choice of the current MV of the current block on the right block or the (i, j+1)th block, we can add a term to the RD cost function of the current block in equation (1):

R(|m _{i, j+1} -p _{i, j+1} |) (4)

where m _i,j+1 is the best motion vector based on the right block of the current MV of the current block, and p _i,j+1 is the median MV predictor of the right block based on the current MV of the current block, i.e.

p _{i, j+1} = median(m _{i, j} , m _{i-1, j+1} , m _{i-1, j+2} )(5)

However, m _i,j+1 in equation (4) is unknown because the motion estimation of the right block (future block) has not been performed yet. However, we note that |m _i,j+1 −p _i,j+1 | can be well approximated by |m _i,j −p _i,j+1 |. Let Diff be |m _i,j+1 -p _i,j+1 | - |m _i,j -p _i,j+1 |. We experiment with many video test sequences and study the distribution of Diff. Figure 2 shows the probability density function (probability distribution function) of the Foreman sequence. As shown in Figure 2, typical results are heavily biased towards zero. This means that the two quantities are essentially the same in most cases (the same in about 70% of the cases and only differ by 1 in about 23% of the cases). This means that |m _i,j -p _i,j+1 | is a good approximation of |m _i,j+1 -p _i,j+1 |. Therefore, R(|m _i,j+1 -p _i,j+1 |) can be approximated by W*R(|m _i,j -p _i,j+1 |), where W>0. Likewise, we can add additional terms to the cost for the lower left and lower squares.

For the (i,j)th block, let medianMV denote the median MV predictor given by Equation 3. Let FmedianMV denote the future median MV predictor given by equation (5) (the median MV predictor for the right block). Thus, FmedianMV is a function of MV candidates. Here, the first embodiment is referred to as "Enhanced Predictive Motion Vector Field Adaptive Search Technique" (E-PMVFAST) for the (i,j)th block. The steps of this example are as follows.

Each step of the embodiment is as follows, shown in FIG. 7 .

For any candidate MV, the cost is defined as follows.

cost(MV)＝SAD+λ*[w*R(MV-medianMV)+(1-w)*R(MV-FmedianMV)]

(6)

1. Compute the cost of three motion vector predictors: (i) the median MV predictor (“medianMV”), (ii) the estimated motion vector of the right block (“futureMV”), which is defined as follows:

futureMV ≡ median(TopMV, TopRightMV, TopRightRightMV) and (iii) the MV predictor from the past block (“pastMV”), which is the previous co-located MV (“PreMV”) and the previous bottom right MV away from medianMV( "PreBottomRightMV"), ie

pastMV _{≡ argmax MV ∈ {PreMv, PreBottomRightMV}} {abs(MV-medianMV)}

Note that item (ii) may be supplemented or replaced by an estimated motion vector for another neighboring future block, such as the bottom left, bottom, and/or bottom right blocks.

It should also be noted that in item (iii), the previous bottom right MV can be supplemented or replaced by the previous MV predictor for another neighboring block.

Note that items (ii) and (iii) form independent aspects of the invention.

If any one of the above MV predictors is not available (eg at a frame boundary), that predictor is skipped.

2. If the minimum cost of the motion vector predictor is less than the threshold T1, stop the search and go to step 7. Otherwise, choose the motion vector with the smallest cost as currentMV (current MV) and go to the next step. Note that the costs of the 3 motion vector predictors may be computed in a predetermined order (e.g. medianMV, then futureMV, then pastMV), and at any moment, if the cost of any motion vector predictor is less than a certain threshold, the search may stop And go to step 7.

3. Perform one iteration of a directed diamond search around currentMV. The concept of directional diamond search is explained below.

4. If the minimum cost is less than the threshold T2, stop the search and go to step 7. Otherwise, choose the motion vector with the smallest cost as currentMV and go to the next step.

5. If (currentMV=medianMV) and the current minimum cost is less than threshold T3, perform a small diamond search and go to step 7.

6. If the video is not interlaced, perform a large diamond search as shown in Figure 3(a); otherwise, perform a modified large diamond search as shown in Figure 3(b). In each of these steps, a cost function is evaluated for each landmark of the diamond.

7. Choose the MV with the smallest cost.

In our experiments, a value of w around 0.8 was found to be effective.

The steps of the directed diamond search are now explained. Assume, centerMV is the current search center, and MV1, MV2, MV3 and MV4 are four surrounding search points, as shown in Fig. 4 . Compute R(MVi-medianMV) for each MVi. If R(MVi-medianMV)<R(centerMV-medianMV), calculate the SAD and cost of MVi. Otherwise, the MVi is ignored. The MV with the lowest cost is chosen as the currentMV. Note that the concept of directional block search is considered new and constitutes an independent aspect of the invention that does not have to be performed in conjunction with the concept of using futureMV.

The steps of the large diamond search and the modified large diamond search are the same, but the search is done for all sets of points shown in Figures 3(a) and 3(b), respectively.

We now consider a number of possible variants of embodiments within the scope of the invention.

First, note that the weighting coefficient w in the cost function can be different for different blocks. In addition, optionally, the w may be different for different MV candidates. In particular, the definition of w may depend on factors such as whether the MV candidate is close to medianMV and/or futureMV, or whether the X-axis component or Y-axis component of the MV candidate is the same as that of the FmedianMV Condition.

In addition, the cost function may not be limited to the form of equation (6). It may include distortion measurement items (such as SAD, sum of squared distortion (SSD), mean deviation distortion (MAD), MSD, etc.) ) Any function of the terms of the bits necessary to encode the motion vector.

Furthermore, in step 1, the definition of futureMV is not limited to the form given in step 1 above. Two possible alternative definitions for futureMV are:

futureMV≡median(leftMV, TopRightMV, TopRightRightMV)

futureMV≡median(medianMV, TopRightMV, TopRightRightMV)

Furthermore, in step 1 of the expression above, pastMV is selected as the one furthest away from medianMV in the set of lists of possible MVs (preMV and preBottomRlghtMV) in the previous frame. However, the list of MVs to consider may contain more than two possible MVs (eg preMV, preLeftMV, preRightMV, preTopMV, preTopLeftMV, preTopRightMV, preBottomMB, preBottomLeftMV, preBottomRightMV, etc.). Furthermore, MVs from more than one previously encoded frame may be included in the list (eg, if the current frame is frame N, the list may contain frames N-1, N-2, N-3, . . . ). If the current frame is a B frame, the list of previously coded frames may include future P frames.

Furthermore, in step 1, the pastMV is selected as the possible MV that is farthest from the reference MV (medianMV in step 1). Other reference MVs are also possible, including leftMV, or TopMV, or TopRightMV, or some combination. Other methods of selecting from a list of possible MVs are also possible.

In step 2, the costs of the three motion vector predictors are obtained in some predefined order. Possible predefined sequences include:

a) medianMV, followed by futureMV, followed by pastMV

b) medianMV, followed by pastMV, followed by futureMV

c) futureMV, followed by medianMV, followed by pastMV

d) futureMV, followed by pastMV, followed by medianMV

e) pastMV, followed by medianMV, followed by futureMV

f) pastMV, followed by futureMV, followed by medianMV

Furthermore, although as expressed above, one iteration of the directed diamond search was performed in step 3, more than one iteration could be applied.

Simulation results

We now present simulation results for Example E-PMVFAST. The embodiments are embedded in the H.264 reference software JM9.3 [13] and simulated using various QPs, video sequences, resolutions and search ranges. Tables 1(a-c) and 2(a-c) show some typical simulation results. PSNR (Peak Signal to Noise Ratio) Variation and BR (Bit Rate) Variation are PSNR and Bit Rate Variations relative to Full Search (FS). Simulation results show that the bitrate and PSNR of the proposed E-PMVFAST tend to be similar to full search and PMVFAST, but over a wide range of video sequences and bitrates, E-PMVFAST tends to be about 40% faster than PMVFAST. An important feature of E-PMVFAST is that its motion vector field tends to be very smooth, so that motion vectors can represent the movement of objects more accurately than other fast motion estimation algorithms.

In Figures 5(a) and 5(b), the images on the left show (as dashed lines) the motion vector field obtained by the PMVFAST algorithm, while the images on the right show the motion of the same image obtained by the described embodiment vector. The motion vector field of E-PMVFAST is significantly smoother than that of PMVFAST, especially in the circled region. Smooth motion fields are useful for classifying video motion content in perceptual trans-coding, rate control, various block size motion estimation, various standard frame motion estimation, etc.

Table 1a - Simulation results for foremanCIF sequences

Table 1b—Simulation results for the CoastguardCIF sequence

Table 1c—Simulation results for HallCIF sequences

Table 2a - Simulation results for foremanQCIF sequences

Table 2b - Simulation results for AkiyoQCIF sequences

Table 2c - Simulation results for the CoastguardQCIF sequence

We now turn to the second embodiment of the invention, which illustrates a second aspect of the invention.

As noted above, conventional full integer pixels allow motion vectors to take position values of -2.0, -1.0, 0, 1.0, 2.0, etc. in each direction. In a second embodiment of the invention, possible position values close to the predictor are selected. For the position value closest to 0, we can use (instead of 1.0) another position value, such as 0.85, so that allowed position values can include -2.0, -0.85 , 0, 0.85 , 2.0, etc. This has the advantage that motion vectors tend to be close to zero statistically. Therefore, by choosing a position closer to 0, we get closer to the true motion vector and thus can give better motion compensation which can lead to higher compression efficiency. Similarly, other position values can be changed. For example, a position value of 2.0 could be changed to 1.9, so that allowed position values would include -1.9 , -0.85 , 0, 0.85, 1.9, and so on. The advantage of the proposed change is that the same motion vector code can be used, except that a coded motion vector position of 1.0 should be interpreted as 0.85, and a coded motion vector position of 2.0 should be interpreted as 1.9.

Half-pixel precision allows motion vectors to take position values such as 0.0, 0.5, 1.0, 1.5, 2.0, and so on. We recommend modifying these location values, especially those that are close to the predictor. For a position value of 0.5 which is very close to 0, we recommend using a different value. For example, one possibility is to use 0.4 instead of 0.5. In other words, positional values will include 0.0, 0.4 , 1.0, 1.5, 2.0. Similarly, other position values can be modified. For example, a position value of 1.0 could be changed to 0.9 such that the new set of position values would include 0.0, 0.4, 0.95, 1.5, 2.0, and so on. Again, this can help improve compression efficiency. Similarly, other position values can be modified to improve compression efficiency. However, changing this position can significantly lead to higher computational efficiency at both the encoder and decoder. Typically, most of the compression efficiency gain comes from changing the position value to be closer to the predictor.

1/4 pixel precision allows motion vectors to take position values such as 0.00, 0.25, 0.50, 0.75, 1.00, etc. We can modify the position values, especially those close to the predictor. For example, we can modify them to 0.00, 0.20, 0.47, 0.73, 0.99, etc.

Note that the proposed method allows us to choose an arbitrary number of position values between each integer position value. For example, between position values 0 and 1, half-pixel precision uses 1 position value {0.5}, 1/4-pixel precision uses 3 position values {0.25, 0.50, 0.75}, and 1/8-pixel precision uses 7 Position values {0.125, 0.250, 0.375, 0.500, 0.625, 0.750, 0.875}. The proposed method allows us to choose any N position values between 0 and 1. For example, we can choose N=2 values such as 0.3 and 0.6.

The proposed non-uniform sub-pixel motion estimation and compensation does not have to be applied to every region of every frame. Instead, certain bits can be introduced into the header to indicate whether it is turned on or off for each region (eg slice) of the video frame. Apart from that, it can be directly applied to existing standards without any syntax changes, since the same motion vector codes can be applied.

The proposed non-uniform sub-pixel motion estimation and compensation was simulated using H.264JM82 software, and the results are shown in the above table, where QP stands for quantization parameter. The simulation uses position values (...-1, -0.75, -0.5, -0.15, 0, 0.15, 0.5, 0.75, 1..) in the x and y directions. That is, only the position values at -0.25 and +0.25 are modified compared to the standard method of using 1/4 pixel spatial position values. The algorithm is otherwise the same as the known H.264 standard algorithm, except that the new position values are used. As shown in the table, the second embodiment significantly reduces the bit rate while achieving similar PSNR. There is no need to modify the syntax of H.264.

Although only a few embodiments of the invention have been described above, many variations are possible within the scope of the invention.

For example, the description of the invention given above is for fixed-size blocks in a P-frame with one reference frame. However, the invention can be applied to blocks with multiple sub-block sizes, and the blocks do not have to be non-overlapping. There can be more than one reference frame, and a reference frame can be any block of the video sequence in the past or in the future relative to the current frame.

For video, a picture element (pixel) can have one or more components, such as luminance, red, green, blue (RGB) components, YUV components, YCrCb components, infrared components, X-ray or other components. Each component of an image element is a symbol that can be represented as a number, which can be a natural number, an integer, a real number, or even a complex number. In the case of natural numbers, they can be 12 bits, 8 bits, or any other bit resolution. Although pixels in video are 2-dimensional samples with a rectangular sampling grid and a uniform sampling period, the sampling grid does not have to be rectangular and the sampling period does not have to be uniform.

Industrial Applicability

Each embodiment of the present invention is suitable for use by MPEG-1, MPEG-2, MPEG-4, H.261, H.263, H.264, AVS or other related video coding standards which may be modified to include the above or Fast, low-latency and low-cost software and hardware implementation of the method. Possible applications include digital video broadcasting (terrestrial, satellite, cable), digital cameras, digital camcorders, digital video recorders, set-top boxes, personal digital assistants (PDAs), multimedia-capable cellular phones (2.5G, 3G and above), video conferencing systems, video-on-demand systems, wireless LAN devices, Bluetooth applications, web servers, video streaming servers in low- or high-bandwidth applications, video transcoders (from one format to another), and Other TV communication systems, etc.

references

The disclosures of the following references are hereby incorporated in their entirety:

[1] JointVideoTeamofITU-TandISO/1ECJTC1, "DraftITU-TRecommendationandFinalDraftinternationalStandardofJointVideoSpecification(ITU-TRec.H.264|ISO/IEC14496-10AVC)", documentJVT-G050r1, may2003

[2] A.M. Tourapis, O.C.Auand M.L.Liou, "PredictiveMotionVectorFieldAdaptiveSearchTechnique (PMVFAST)", ISO/IECJTC1/SC29/WG11MPEG2000, Noordwijkerhout, ML, March'2000

[3] R.LI, B.Zeng and M.L.Liou, "A new three-step search algorithm for block motion estimation", On Circuits and Systems for Video Technology, vol4, no4, pp438-42, Aug'94

[4] Z.L.He and M.L.Liou, "A high performance fast search algorithm for blockmatching motion estimation", IEEE Trans.on Circuits and Systems for Vld&o2Technology, vol.7, no5, pp826-8, Oct'97

[5] A.M. Tourapis, O.C.Au, and M.L. Liou, "Fast Motion Estimation using Circular Zonal Search", Proc. of SPIES Sym. Of Visual Comm. & Imagg Processin, vol2, pp. 1496-1504, Jan. 25-27, '99

[6] A, M.Tourapis, O.C.Au, M.LLiou, G.Shen, and I.Ahmad, "Optimizing the Mpeg-4Encoder-Advanced Diamond Zonal Search", inPros.of2000IEEEInter.Sym.onCircuitsandSystems, Geneva, Switzerland, May, 2000

[7] K.K.MaandP.I.Hosur, "PerformanceReportofMotionVectorFieldAdaptiveSearchTechnique(MVFAST)", inISO/IECJTC1/SC29/WG11MPEG99/m81, Noordwijkerhout, NLMar'00

[8] A.M. Tourapis, O.C.Au, and M.L.Liou, "FastBlock-MatchingMotionEstimationusingPredictiveMotionVectorFieldAdaptiveSearchTechnique (PMVFAST)", inISO/IEC/JTC1/SC29/WG11MPEG2000/M5866, Noordwijkerhout, NL, Mar'00

[9] Implementation Study Group, "Experimental conditions for evaluating encoder motion estimation algorithms", inISO/IECJTC1/SC29/WG11MPEG99/n3141, Hawaii, USA, Dec'99

[10] "MPEG-4OptimizationModelVersion1.0", inISO/IECJTC1/SC29/WG11MPEG2000/n3324, Noordwijkerhout, NL, Mar'00

[11] T, Koga, K.linuma, A.Hirano, Y.lijima, and T.Ishlguro, "Motion compensated interframe coding for video conferencing" Proc.Nat.Telecommun.Conf., NewOrleans, LA, pp.G.5.3.1-G.5.3 .5, Dec '81.

[12] J.R. Jain and A.K. Jain, "Displacement measurement and its application in interframe image coding", JEEE Trans. On Communications, vol. COM-29, pp.1799-808, Dec'81

[13] JVTreferencesoftwareJM9.2forJVT/H.264FRext

Claims (8)

1. A method of selecting a respective similar pixel block in a second image for each of a series of pixel blocks in a first image, the method comprising: selecting between a plurality of candidate positions in the second image for a current block in the series of pixel blocks of the first image, the plurality of candidate positions comprising two A set of candidate positions defined by position values, at least one of which is non-uniform for at least one of the two axis directions. 2. The method of claim 1, wherein each of the set of candidate positions is associated with a respective motion vector by a respective position value, the motion vector being different from the predicted motion vector. 3. The method of claim 1, wherein each of the set of candidate positions is associated with a respective motion vector by a respective position value, the motion vector being different from a (0,0) motion vector. 4. The method of claim 1, wherein the position value can be written as DA _m m/n, where m=-..., 2, -1, 0, 1, 2..., n is a power of 1 or 2, D is a constant, while A _m is a value less than 1 for at least one value of m, and 0.75≦A _m <1 for all values of m. 5. The method of claim 4, wherein each of the set of candidate positions is associated with a respective motion vector by a respective position value, the motion vector being different from the predicted motion vector. 6. The method of claim 4, wherein each of the set of candidate positions is associated with a respective motion vector by a respective position value, the motion vector being different from the (0,0) motion vector. 7. The method of claim 4, wherein A _m has a value of at least 0.85 for all values of m. 8. A system for selecting, for each of a series of pixel blocks in a first image, a respective similar pixel block in a second image, the system comprising a processor configured to, for the first image For the current block in the series of pixel blocks of an image, select between a plurality of candidate positions in the second image, the plurality of candidate positions comprising A set of candidate positions is defined, at least one of the position values being non-uniform for at least one of the two axis directions.