Motion vector estimation based on statistical features of an image frame

[0002] 1. Field of the Invention

[0003] The present invention relates to methods for compressing digital video data and, more particularly, to a method for estimating motion vectors based only on the statistical features of successive frames of images.

[0004] 2. Description of the Related Art

[0005] It is well known that digital video systems such, for example, as high definition televisions and video conferencing systems require a substantial amount of digital data to represent each image frame. But transmitting the entire set of digitized video data is impractical and often beyond the capability of most video equipment. Therefore, it is necessary to compress, i.e. reduce, the amount of data needed to represent an image frame prior to its transmission.

[0006] Various video compression algorithms have been developed. For example, a spatial compression algorithm analyzes to identify similarities within an image frame and reduces or eliminates spatial redundancies in the frame. A temporal compression algorithm, on the other hand, analyzes to identify similarities between a current image frame and a preceding image frame and thereby detect moving objects between the two frames. Motion vectors indicating the displacement of the moving objects are then transmitted to a receiver which reconstructs the current frame from the prior frame and the motion vectors. A temporal compression algorithm is thus premised on the observation that video data sequences are highly correlated between successive image frames.

[0007] Temporal compression algorithms typically use block-matching techniques such as those adopted by standards H.261, H.263, MPEG1 and MPEG2. These block-matching algorithms and the like are discussed in detail by A. N. Netravali and B. G. Haskell in Digital Pictures: Representation, Compression, and Standards, 2nd Ed., AT&T Bell Laboratories, 1995, the content of which is incorporated herein by reference in its entirety.

[0008] According to a typical block matching algorithm, the current frame is divided into a plurality of search blocks. The size of a search block may range between 8×8 and 32×32 pixels. To determine a motion vector for a search block in the current frame, similarity calculations are performed between the search block of the current frame and each of a plurality of equal-sized candidate blocks included in a generally larger search region within a previous frame. An error estimating measure such as the mean absolute error or mean square error is used to carry out a similarity measurement between the search block of the current frame and each of the candidate blocks in the previous frame search region. From this, motion vectors, each representing the displacement between the search block and a candidate block which yields a minimum error measure, are generated. Since the search block is compared with all possible candidate blocks within a search region corresponding to the search block (i.e. full search block matching), this procedure involves heavy computational requirements which, in turn, requires complex hardware having the capability of very high speed processing and/or a large number of processors for real-time processing.

[0009] Attempts have been made to reduce the computational complexity of block-matching algorithms. For example, U.S. Pat. No. 5,710,603 to Lee discloses that the computational complexity involved in estimating motion vectors can be reduced by performing at least the following steps: (1) one-dimensionally comparing a search block from the current frame with a plurality of candidate blocks included in a search region corresponding to the search block, on a block-by-block basis, by employing a one-dimensional error function using horizontal and vertical integral projections to select a predetermined number of candidate blocks in an ascending order of the one-dimensional error function; and (2) two-dimensionally comparing the search block with the predetermined number of candidate blocks selected in step (1), on a block-by-block basis, by employing a two-dimensional error function to thereby select a most similar candidate block to the search block and derive a motion vector representing the displacement of pixels between the search block and the most similar candidate block so as to assign the derived motion vector as the motion vector for the search block. Lee defines integral projection as a summation value of the luminance levels of all of the pixels lying along a horizontal or a vertical pixel line in a given block.

[0010] A disadvantage of this motion vector estimating algorithm is that it does not adequately reduce computational complexity because Lee's two-dimensional error function requires a great number of multiplication operations.

[0011] It is therefore desirable to further reduce the computational complexity of motion vector estimation while maintaining acceptable picture quality, coding bitrate, coded sequences and other indicia of video performance.

[0012] The present invention accordingly provides a computationally efficient method for estimating motion vectors between two successive frames.

[0013] A preferred embodiment of the present invention provides a method for estimating motion vectors between a current frame n and a reference frame n−1 wherein the current frame is divided into a plurality of search blocks and the reference frame is defined to include a plurality of search regions corresponding to the plurality of search blocks, each of the plural search regions having a plurality of candidate blocks, including the steps of:

[0014] (a) calculating horizontal features and vertical features of a reference frame based on pixel data of the reference frame as follows: ${\hat{H}}_{n-1}\left(i,j\right)=\sum _{p=j}^{j+W-1}{\hat{F}}_{n-1}\left(i,p\right)$ ${\hat{V}}_{n-1}\left(i,j\right)=\sum _{p=i}^{i+Y-1}{\hat{F}}_{n-1}\left(p,j\right)$

[0015] where Ĥ_n−1,(i,j) denotes the horizontal feature at pixel location (i,j), {circumflex over (V)}_n−1(i,j) denotes the vertical feature at pixel location (i,j), {circumflex over (F)}_n−1(i,j) denotes the pixel intensity value at pixel location (i,j) of the reference frame, and W and Y are the one-dimensional ranges of pixels selected for summation in the horizontal and vertical directions, respectively;

[0016] (b) storing the calculated horizontal features and vertical features of the reference frame;

[0017] (c) computing horizontal features and vertical features of a k^thsearch block of the plurality of search blocks as follows: $H_{n,k}\left(i,j\right)=\sum _{p=j}^{j+W-1}{F}_n\left(i,p\right)$ $V_{n,k}\left(i,j\right)=\sum _{p=i}^{i+Y-1}{F}_n\left(p,j\right)$

[0018] where H_n,k(i,j) denotes the horizontal feature of the k^thsearch block at pixel location (i,j) of the current frame, V_n,k(i,j) denotes the vertical feature of the k^thsearch block at pixel location (i,j) of the current frame, F_n(i,j) denotes the pixel intensity value at pixel location (i,j) of the current frame, and W and Y are as defined in step (a);

[0019] (d) comparing the horizontal and vertical features of those of k^thsearch block with those of the plurality of candidate blocks of the reference frame using an error measure defined as follows: ${\mathrm{en}}_k\left(\overrightarrow{d}\right)=\sum _{\overrightarrow{l}\in L}\Vert H_{n,k}\left(\overrightarrow{l}\right)-{\hat{H}}_{n-1}\left(\overrightarrow{l}-\overrightarrow{d}\right)\Vert +\Vert V_{n,k}\left(\overrightarrow{l}\right)-{\hat{V}}_{n-1}\left(\overrightarrow{l}-\overrightarrow{d}\right)\Vert$

[0020] where {right arrow over (l)} denotes pixel position (i,j), {right arrow over (d)} denotes the displacement of a candidate block relative to {right arrow over (l)} and L is a feature space;

[0021] (e) selecting a candidate block which yields a minimal error measure for the k^thsearch block; and

[0022] (f) computing a motion vector for the k^thsearch block based on the most similar candidate block.

[0023] Other objects and features of the present invention will become apparent from the following detailed description considered in conjunction with the accompanying drawings. It is to be understood, however, that the drawings are designed solely for purposes of illustration and not as a definition of the limits of the invention, for which reference should be made to the appended claims.

[0024] In the drawings:

[0025] FIG. 1 is a block diagram of an embodiment of the motion estimator of the present invention;

[0026] FIG. 2 schematically depicts a current frame, a reference frame, and elements of a block searching algorithm; and

[0027] FIG. 3 is a flow chart describing an embodiment of the motion vector estimating algorithm in accordance with the present invention.

[0028] Schematically illustrated in FIG. 1, is a motion estimator 12 for estimating motion vectors between successive frames of images in accordance with the present invention. The motion estimator 12, typically disposed in a video signal transmitter 10, receives pixel data of a current image frame n and a reference image frame n−1 and performs similarity calculations so as to derive motion vectors for pixels of the reference image frame. The reference image frame is an immediately preceding image frame which may be reconstructed by, for example, a decoder 14 in the transmitter 10 from motion vectors for a preceding frame. Alternatively, the reference frame may be retrieved from a storage device (not shown) containing the pixel data of a previously displayed frame generated by, for example, a camera (not shown). Motion vectors computed by the motion estimator 12 are then sent to a video receiver 15 for reconstruction of the current image frame.

[0029] FIG. 2 diagrammatically depicts a current image frame 16 and a reference image frame 18. Each of the current image frame and the reference image frame includes a two-dimensional matrix of pixels at positions (i,j) wherein row i varies from 1 to M and column j varies from 1 to N. Thus, the positions of pixels lying along a row i are successively denoted (i,1), (i,2), (i,3) to (i, N); similarly, the positions of pixels lying along a column j are successively denoted (1,j), (2,j), (3,j) to (M, j).

[0030] In accordance with block-matching schemes, pixels of the current frame 16 are initially divided into a plurality of search blocks 20 and pixels of the reference frame may be grouped to form a search region or search space S as shown in FIG. 2. The search region S is defined to include pixels neighboring the corresponding or projected search block 20′ in the reference image. Pixels located in the search region S are then further subdivided into a plurality of candidate blocks 22 and similarity analysis, in accordance with the present invention, is performed, on a block-by-block basis, between the current frame search block 20 and each of the reference frame candidate blocks 22 in the search region S. After selecting from the similarity analysis the most similar reference frame candidate block, a motion vector is derived in the form of, for example, Δi and Δj for the search block 20.

[0031] Preferably, prior to carrying out these block matching schemes, pixels of the reference frame are analyzed using computationally efficient threshold determining algorithms such, for example, as conditional replenishment so as to reduce the number of pixels of the reference frame required for similarity analysis. These threshold determining algorithms eliminate those reference frame pixels whose intensity values are essentially the same as those of the current frame. In other words, those pixels of the reference frame which have not undergone any motion-induced changes in the current frame will not be subjected to any similarity analysis. As schematically illustrated in FIG. 2, the reduced reference frame R may be of any shape or consist of several continguous regions (not shown).

[0032] FIG. 3 presents a flow chart describing a presently preferred method for implementing the present invention. Initially, at step S01, pixel data such, for example, as luminance and chrominance levels of the reference frame are determined. At step S02, statistical features such as the mean intensity values, the variance or the third order statistic of the pixels in the reference frame (denoted n−1) are calculated as follows: ${\hat{H}}_{n,k}\left(i,j\right)=\sum _{k=i}^{j+W-1}{\hat{F}}_n\left(i,p\right)$ ${\hat{V}}_{n,k}\left(i,j\right)=\sum _{p=i}^{i+Y-1}{\hat{F}}_{n-1}\left(p,j\right)$

[0033] where Ĥ_n−1(i,j) denotes the horizontal feature at pixel location (i,j), {circumflex over (V)}_n−1(i,j) denotes the vertical feature at pixel location (i,j), {circumflex over (F)}_n−1denotes the pixel intensity values at pixel location (i,j) of the reference frame, and W and Y are the one-dimensional ranges for the group of pixels selected for summation in the horizontal and vertical directions, respectively. The calculated values of Ĥ_n−1(i,j) and {circumflex over (V)}_n−1(i,j) are stored for access in a subsequent step.

[0034] The horizontal and vertical features may be calculated on a sub-block basis, i.e. W and Y are less than the horizontal and vertical dimensions of a search block 20, depending on the coding resolution and content of the image frames. For applications such, for example, as typical video conferencing applications which have low spatial and temporal resolution, the preferred value for W and Y is half of the corresponding rows and columns of the search block. Advantageously, this preferred range offers reduction in computational complexity while providing acceptable picture quality, coding bitrate, coded sequences, and other indicia of video performance. Alternatively, the summation range W and Y may be ¼ of the rows and columns of the search block. By way of example, for a search block of 16×16 pixels, a reduced reference frame R of 100×100 pixels, and W=Y=8 (i.e. half of the rows or columns of the 16×16 search block), the horizontal features of the reference are calculated as follows: $\begin{array}{cccc}{\hat{H}}_{n-1}\left(1,1\right)=\sum _{j=1}^8{\hat{F}}_{n-1}\left(1,j\right)& {\hat{H}}_{n-1}\left(1,2\right)=\sum _{j=2}^9{\hat{F}}_{n-1}\left(1,j\right)& \cdots & {\hat{H}}_{n-1}\left(1,93\right)=\sum _{j=93}^{100}{\hat{F}}_{n-1}\left(1,j\right)\\ {\hat{H}}_{n-1}\left(2,1\right)=\sum _{j=1}^8{\hat{F}}_{n-1}\left(2,j\right)& {\hat{H}}_{n-1}\left(2,2\right)=\sum _{j=2}^9{\hat{F}}_{n-1}\left(2,j\right)& \cdots & {\hat{H}}_{n-1}\left(2,93\right)=\sum _{j=93}^{100}{\hat{F}}_{n-1}\left(2,j\right)\\ \cdots & \cdots & \cdots & \cdots \\ {\hat{H}}_{n-1}\left(93,1\right)=\sum _{j=1}^8{\hat{F}}_{n-1}\left(93,j\right)& \cdots & \cdots & {\hat{H}}_{n-1}\left(93,93\right)=\sum _{j=93}^{100}{\hat{F}}_{n-1}\left(93,j\right)\end{array}$

[0035] For this example, pixel position (1,1) denotes the position of the pixel located at the upper left-the potential search area P of the reference frame.

[0036] Similarly, the vertical features of the reference frame are calculated as follows: $\begin{array}{cccc}{\hat{V}}_{n-1}\left(1,1\right)=\sum _{i=1}^8{\hat{F}}_{n-1}\left(i,1\right)& {\hat{V}}_{n-1}\left(1,2\right)=\sum _{i=1}^8{\hat{F}}_{n-1}\left(i,2\right)& \cdots & {\hat{V}}_{n-1}\left(1,93\right)=\sum _{i=1}^8{\hat{F}}_{n-1}\left(i,93\right)\\ {\hat{V}}_{n-1}\left(2,1\right)=\sum _{i=2}^9{\hat{F}}_{n-1}\left(i,1\right)& {\hat{V}}_{n-1}\left(2,2\right)=\sum _{i=2}^9{\hat{F}}_{n-1}\left(i,2\right)& \cdots & {\hat{V}}_{n-1}\left(2,93\right)=\sum _{i=2}^9{\hat{F}}_{n-1}\left(i,93\right)\\ \cdots & \cdots & \cdots & \cdots \\ {\hat{V}}_{n-1}\left(93,1\right)=\sum _{i=93}^{100}{\hat{F}}_{n-1}\left(i,1\right)& \cdots & \cdots & {\hat{V}}_{n-1}\left(93,93\right)=\sum _{i=93}^{100}{\hat{F}}_{n-1}\left(i,93\right)\end{array}$

[0037] Although the maximum number of rows and columns of the horizontal and vertical features tables, in this example is 93, it may alternatively be greater or less than 93 depending on the maximum range of a possible candidate block as determined by the particular block-matching algorithm, selected as a general matter of design choice.

[0038] Advantageously, the above horizontal and vertical feature calculations can be recursively calculated, that is, a subsequent to-be-calculated statistical feature, H_n−1(i, j+1) or vertical feature, V_n−1(i+1, j) can be obtained by simply adding to the previously determined statistical feature (H_n−1(i, j) or V_n−1(i, j)) the intensity value of the pixel immediately following the summed pixels and subtracting therefrom the intensity value of the pixel immediately preceding the summed pixels. Expressed mathematically, the horizontal and vertical features are recursively calculated as follows:

[0039] Ĥ_n−1(i, j+1)={circumflex over (F)}_n−1(i, j+w)+Ĥ_n−1(i, j)−{circumflex over (F)}_n−1(i, j)

[0040] where ${\hat{H}}_{n-1}\left(i,j\right)=\sum _{p=j}^{j+W-1}{\hat{F}}_{n-1}\left(i,p\right)$

[0041] and,

[0042] {circumflex over (V)}_n−1(i+1, j)={circumflex over (F)}_n−1(i+Y, j)+{circumflex over (V)}_n−1(i, j)−{circumflex over (F)}_n−1(i, j)

[0043] where ${\hat{V}}_{n-1}\left(i,j\right)=\sum _{p=i}^{p+Y-1}{\hat{F}}_{n-1}\left(p,j\right)$

[0044] At step S03, pixel data such, for example, as pixel intensity values of one of the blocks (e.g. a k^thsearch block) in the current frame are read. At step S04, the horizontal features and vertical features of the k^thsearch block are calculated as follows: $H_{n,k}\left(i,j\right)=\sum _{p=0}^{W-1}{F}_n\left(i,j+p\right)$

[0045] where i varies from i₀to (b−1), b being the vertical dimension of the search block; and j=j₀+cW, wherein c varies incrementally from 0 to (a/W)−1, i.e. c=0, . . . , (a/W)−1. $V_{n,k}\left(i,j\right)=\sum _{k=0}^{Y-1}{F}_n\left(i+p,-j\right)$

[0046] where j varies from j₀to (a−1), a being the horizontal dimension of the search and block; and i=i₀+dY, wherein d varies incrementally from 0 to (b/Y)−1, i.e. d=0, . . . , (b/Y)−1. As was defined above, W and Y are the one-dimensional ranges for the group of pixels selected for summation in the horizontal and vertical directions respectively.

[0047] In this step, the horizontal and vertical features of the search block cannot be recursively calculated in step S01. The summing operations of this step are performed for each row and column, (or a segments thereof) of the pixels in each search block as specified by W or Y and are thus non-repetitive in the sense that pixels included in a preceding calculation are excluded from succeeding calculation. Therefore, the size of the matrix containing the horizontal or vertical features of the search block is necessarily different from the recursively-calculated matrix generated in step S01.

[0048] The summing operations of this step for a 16×16 search block are exemplarily illustrated as follows: $\begin{array}{cc}{H}_{n,k}\left(i_0,j_0\right)=\sum _{p=0}^7{F}_n\left(i_0,j_0+p\right)& H_{n,k}\left(i_0,j_0+8\right)=\sum _{p=0}^7{F}_n\left(i_0,j_0+8+p\right)\\ H_{n,k}\left(i_0+1,j_0\right)=\sum _{p=0}^7{F}_n\left(i_0+1,j_0+p\right)& H_{n,k}\left(i_0+1,j_0+8\right)=\sum _{p=0}^7{F}_n\left(i_0+1,j_0+8+p\right)\\ H_{n,k}\left(i_0+2,j_0\right)=\sum _{p=0}^7{F}_n\left(i_0+2,j_0+p\right)& H_{n,k}\left(i_0+2,j_0+8\right)=\sum _{p=0}^7{F}_n\left(i_0+2,j_0+8+p\right)\\ \cdots & \cdots \\ H_{n,k}\left(i_0+15,j_0\right)=\sum _{p=0}^7{F}_n\left(i_0+15,j_0+p\right)& H_{n,k}\left(i_0+15,j_0+8\right))=\sum _{p=0}^7{F}_n\left(i_0+15,j_0+8+p\right)\end{array}$

[0049] where i₀and j₀example, the position of the pixel at the upper left hand corner of the k search block.

[0050] Similarly, the vertical features of this search block are computed as follows: $\begin{array}{cc}{V}_{n,k}\left(i_0,j_0\right)=\sum _{p=0}^7{F}_n\left(i_0+p,j_0\right)& V_{n,k}\left(i_0+8,j_0\right)=\sum _{p=0}^7{F}_n\left(i_0+8+p,j_0\right)\\ V_{n,k}\left(i_0,j_0+1\right)=\sum _{p=0}^7{F}_n\left(i_0+p,j_0+1\right)& V_{n,k}\left(i_0+8,j_0+1\right)=\sum _{p=0}^7{F}_n\left(i_0+8+p,j_0+1\right)\\ \cdots & \cdots \\ V_{n,k}\left(i_0,j_0+15\right)=\sum _{p=0}^7{F}_n\left(i_0+p,j_0+15\right)& V_{n,k}\left(i_0+8,j_0+15\right)=\sum _{p=0}^7{F}_n\left(i_0+8+p,j_0+15\right)\end{array}$

[0051] At step S05, similarity analysis is performed by comparing the horizontal and vertical features of the k^thsearch block with those of the candidate blocks on a block-by-block basis in a search region using the calculated error measure en_k: ${\mathrm{en}}_k\left(\overrightarrow{d}\right)=\sum _{\overrightarrow{l}\in L}\Vert H_{n,k}\left(\overrightarrow{l}\right)-{\hat{H}}_{n-1}\left(\overrightarrow{l}-\overrightarrow{d}\right)\Vert +\Vert V_{n,k}\left(\overrightarrow{l}\right){\widehat{-V}}_{n-1}\left(\overrightarrow{l}-\overrightarrow{d}\right)\Vert$

[0052] where {right arrow over (l)} denotes pixel position (i,j), {right arrow over (d)} denotes the displacement of a candidate block relative to {right arrow over (l)}, L denotes a feature space, and the expression represents the mean square error (MSE) or the mean absolute error (MAE) of the quantity bracketed therebetween. MAE is preferably used because it is free of multiplication operations and thus more computationally efficient than MSE, and provides comparably accurate results.

[0053] At step S06, the candidate block which yields the smallest or minimal error measure en_kfor the k^thsearch block is selected. The selected candidate block is the candidate block most similar to the k^thsearch block. Expressed in another way: ${\mathrm{mv}}_k=\arg \underset{\overrightarrow{d}\in S}{\min }{\mathrm{en}}_k\left(\overrightarrow{d}\right)$

[0054] where mv_kis the motion vector for the k^thsearch block, S is a search space.

[0055] At step S07, the motion vector between the k^thsearch block and the selected candidate block is computed. At step S08, the algorithm checks whether the k^thsearch block is the last search block of the current frame. If so, motion vectors for the entire frame have been generated, and the process ends; if not, steps S03 through S07 are repeated for the next search block.

[0056] It has been found that use of the inventive algorithm achieves data rate and picture quality results comparable to a full-search block-matching algorithm while requiring significantly less computational power and complexity than a full-search algorithm.

[0057] Thus, while there have shown and described and pointed out fundamental novel features of the invention as applied to preferred embodiments thereof, it will be understood that various omissions and substitutions and changes in the form and details of the devices illustrated, and in their operation, may be made by those skilled in the art without departing from the spirit of the invention. For example, it is expressly intended that all combinations of those elements and/or method steps which perform substantially the same function in substantially the same way to achieve the same results are within the scope of the invention. It is the intention, therefore, to be limited only as indicated by the scope of the claims appended hereto.