Advanced video coded pictures—reduced cost computation of an intra mode decision in the frequency domain

A method of intra mode prediction uses a block of pixels and their horizontal Hpos and vertical Vpos pixel positions and adjacent horizontal and vertical pixels within an input picture frame signal as inputs for a method for selecting a lowest Sum of Absolute Transformed Differences (SATD) intra mode among intra modes among the horizontal, vertical, and steady state (DC) intra modes for use in advanced video coding algorithms, such as MPEG-4 Part 10 and H.264/AVC. Associated costs are calculated for each of the intra modes are used to select the output of the best intra mode. The method reduces the unimproved computational cost of three 2D 4×4 Hadamard transformations (which is equivalent to 24 1D 4 point transformations) to just 4 1D 4 point transformations for a significant computational improvement. As horizontal and vertical panning is frequently used in video imagery, this improvement may reduce encoder processing by 80%.

CROSS-REFERENCE TO RELATED APPLICATIONS

Not Applicable

Not Applicable

Not Applicable

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention pertains generally to video encoding, and more particularly to intra mode decisions within advanced video encoding (such as H.264/AVC or MPEG-4 Part 10) standards.

2. Description of Related Art

H.264/AVC, alternatively known as MPEG-4 Part 10 and by several other monikers, is representative of improved data compression algorithms. Improved data compression, however, comes at the price of greatly increased computational requirements during the encoding processing phase.

In particular, the H.264/AVC contains a very computationally expensive section where an optimal intra mode is calculated that yields the lowest sum of absolute transformed differences (or SATD) between an input 4×4 pixel block, and its compressed version. Examples of prior attempts to reduce this computational cost include A. C. Yu, G. R. Martin, and H. Park, in “A Frequency Domain Approach to Intra Mode Selection in H.264/AVC”, incorporated by reference in its entirety, U.S. patent publication US 2006/0209948 A1, incorporated herein by reference in its entirety, and U.S. patent publication US 2006/0251330 A1, incorporated herein by reference in its entirety.

BRIEF SUMMARY OF THE INVENTION

Accordingly, one aspect of the invention is a method of selecting an intra mode in a video image encoder, comprising:

(a) selecting a lowest Sum of Absolute Transformed Differences (SATD) intra mode among intra modes while using [x], {right arrow over (h)}, {right arrow over (v)}, Hpos, Vpos;

(b) wherein [x] is a 4×4 block of pixels within a picture and

(c) wherein Hposis a horizontal pixel position of the 4×4 block within the image;

(d) wherein Vposis a vertical pixel position of the 4×4 block within the image;

(e) wherein the lowest SATD intra mode is determined among a group comprising: (i) a horizontal intra mode; (ii) a vertical intra mode; and (iii) a steady state (DC) intra mode; and

The outputting step may comprise:

(a) calculating a horizontal predictor {right arrow over (H)}≡(H0,H1,H2,H3)T, a vertical predictor {right arrow over (V)}≡(V0,V1,V2,V3)T, and a steady state (DC) predictor D;

(b) calculating a horizontal cost precursor Chsand a vertical cost precursor Cvsusing the horizontal predictor {right arrow over (H)}, the vertical predictor {right arrow over (V)}, and the steady state (DC) predictor D; and

(c) calculating a horizontal intra mode cost CH, a vertical intra mode cost CV, and a steady state (DC) intra mode cost CDusing the horizontal cost precursor Chsand the vertical cost precursor Cvs.

The calculating of the horizontal predictor {right arrow over (H)}, the vertical predictor {right arrow over (V)}, and the steady state (DC) predictor D may comprise:

A relatively inefficient calculation of the horizontal cost precursor Chsand the vertical cost precursor Cvsmay begin with steps comprising: (a) calculating the values Xi,0, X0,ifor iε0, 1, 2, 3 using the relationship

In another aspect of the invention, a more computationally efficient calculation of the Xi,0, X0,ifor iε0, 1, 2, 3 values may comprise: providing the input [x] matrix and the [T4] matrix; then calculating:

Chs=∑i=13⁢⁢Xi,0
and vertical cost precursor

Cvs=∑j=13⁢⁢X0,j
may be calculated.

The horizontal intra mode cost CHmay then be calculated by

The vertical intra mode cost CVmay be calculated by

The steady state (DC) intra mode cost CDmay be calculated by CD=|D−X0,0|+Chs+Cvs.

The calculating may further comprise: selecting the lowest SATD intra mode with a lowest associated intra mode cost among the group consisting of: the horizontal intra mode cost CH, the vertical intra mode cost CV, and the steady state (DC) intra mode cost CD. This calculating process is typically achieved through a series of logical operations.

Another aspect of the invention is a computer readable medium comprising a programming executable capable of performing on a computer the method described above.

A still further aspect of the invention is an advanced video encoder comprising the method described above. This advanced video encoder may take the form of a specially designed video encoder signal processor embedded within a consumer device, such as a hand held high definition television (HDTV) device.

Yet another aspect of the invention is a method of intra mode prediction, that comprises:

(a) providing a 4×4 block of pixels [x] within a picture, wherein

h→=[x0,-1x1,-1x2,-1x3,-1]
immediately to the left of the bock [x] in the picture when available;

v→=[x-1,0x-1,1x-1,2x-1,3]
immediately above the block [x] in the picture when available;

(d) providing a horizontal pixel position (Hpos) of the 4×4 block within the picture;

(e) providing a vertical pixel position (Vpos) of the 4×4 block within the picture; and

(f) outputting a lowest Sum of Absolute Transformed Differences (SATD) intra mode among intra modes while using [x], {right arrow over (h)}, {right arrow over (v)}, Hpos, Vpos, wherein the lowest SATD intra mode is selected from the group consisting of: i. a horizontal intra mode; ii. a vertical intra mode; and iii. a steady state (DC) intra mode.

The 4×4 pixel block [x] is typically oriented in the same sense as the original picture it is taken from, i.e. the indices increase in the same directions both horizontally and vertically. (Note that in the H.264 standard, the orientation is that pixel coordinate 0,0 is at the upper left of the picture.) In this orientation, the {right arrow over (h)} is immediately adjacent to the left side of the 4×4 pixel block [x], and the {right arrow over (v)} is immediately adjacent the top of the 4×4 pixel block [x].

It is readily apparent that the methods above may be easily modified for {right arrow over (h)} aligned on the right edge of the 4×4 pixel block [x], and the {right arrow over (v)} may be aligned with the bottom of the 4×4 pixel block [x]. Similarly, the picture or the 4×4 pixel block [x] indices may be readily reoriented with the orientation of pixel 0,0 being in any quadrant, while still performing the methods described here.

Additionally, the methods described herein may be readily applied to other H.264 pixel blocks, such as the 16×16 macroblock, or indeed generalized to block of size p×q where p and q may be independently selected from a group consisting of 2, 4, 8, 16, 32, 64, and 128.

In another aspect of the invention, the aforementioned steps may be incorporated into a more generalized method. The resultant generalized method of selecting an intra mode in a video image encoder may comprise:

(a) selecting a lowest Sum of Absolute Transformed Differences (SATD) intra mode among intra modes using inputs [x], Hpos, Vpos, {right arrow over (h)}, and {right arrow over (v)};

(c) wherein Hposis a horizontal pixel position of the p×q block within the image;

(d) wherein Vposis a vertical pixel position of the p×q block within the image;

(e) wherein {right arrow over (h)} is a horizontal vector immediately left of the p×q block [x], defined as {right arrow over (h)}≡(x0,−1, x1,−1, . . . , xp−1,−1)Trelative to the indexing of the elements of [x];

(f) wherein {right arrow over (v)} is a horizontal vector immediately above the p×q block [x], defined as {right arrow over (v)}≡(x−1,0, x−1,1, . . . , x−1,q−1)Trelative to the indexing of the elements of [x];

(g) wherein b is the bit depth of a pixel in the picture; (h) wherein the lowest SATD intra mode is determined among a group comprising:i. a horizontal intra mode;ii. a vertical intra mode; andiii. a steady state (DC) intra mode; and

(i) outputting the lowest SATD intra mode to a computer readable medium.

The selecting step may comprise:

(b) calculating a horizontal cost precursor Chsand a vertical cost precursor Cvsusing the horizontal predictor {right arrow over (H)}, the vertical predictor {right arrow over (V)}, and the steady state (DC) predictor D; and

(c) calculating a horizontal intra mode cost CH, a vertical intra mode cost CV, and a steady state (DC) intra mode cost CDusing the horizontal cost precursor Chsand the vertical cost precursor Cvs.

In the method above, the calculating a horizontal predictor {right arrow over (H)}, a vertical predictor {right arrow over (V)}, and a steady state (DC) predictor D may comprise:

(d) if Hpos=0 and Vpos=0 then: (i) setting {right arrow over (H)}=(215−1,0,0,0)Twherein m is defined as 2m≧p×p×q×2b+1; (ii) setting {right arrow over (V)}=(215−1,0,0,0)Twherein n is defined as 2n≧q×p×q×2b+1; and (iii) setting D=128×16.

The horizontal cost precursor Chsand the vertical cost precursor Cvsmay be calculated by steps comprising:

(b) calculating the horizontal cost precursor

(c) calculating the vertical cost precursor

The horizontal intra mode cost CHmay be calculated using steps comprising: calculating

Similarly, the vertical intra mode cost CVmay be calculated with steps comprising: calculating

Finally, the steady state (DC) intra mode cost CDmay be calculated with steps comprising: calculating CD=|D−X0,0|+Chs+Cvs.

In the method above, the calculating means may comprise: selecting the lowest SATD intra mode with a lowest associated intra mode cost among the group consisting of: the horizontal intra mode cost CH, the vertical intra mode cost CV, and the steady state (DC) intra mode cost CD.

In another aspect of the invention, a computer readable medium comprising a programming executable may be capable of performing on a computer the methods described above.

In still another aspect of the invention, the methods of intra mode prediction above may be generalized for: (a) where the p dimension is selected from a group of dimensions consisting of: 2, 4, 8, 16, 32, 64, and 128; and (b) where the q dimension is selected from a group of dimensions consisting of: 2, 4, 8, 16, 32, 64, and 128. Still higher dimensions are also possible, however, they are likely computationally prohibitive nature of the increasingly complex calculations.

DETAILED DESCRIPTION OF THE INVENTION

Referring more specifically to the drawings, for illustrative purposes the present invention is embodied in the method generally depicted inFIG. 1AthroughFIG. 5. It will be appreciated that the apparatus may vary as to configuration and as to details of the parts, and that the method may vary as to the specific steps and sequence, without departing from the basic concepts as disclosed herein.

Introduction

In the H.264/AVC video compression standard, the 4×4 intra mode decision is made by performing Lagrangian rate-distortion optimization on each of the 9 intra mode possibilities. The intra mode selected is the one that provides the lowest distortion (SATD) between the original 4×4 input block, and the reconstructed block for a particular intra mode. This process is extremely computationally expensive.

The process described below reduces the computational cost of the 4×4 intra mode decision significantly, from 24 1D 4 point Hadamard transforms to merely 4 of them.

Definitions

“Computer” means any device capable of performing the steps, methods, or producing signals as described herein, including but not limited to: a microprocessor, a microcontroller, a video processor, a digital state machine, a field programmable gate array (FPGA), a digital signal processor, a collocated integrated memory system with microprocessor and analog or digital output device, a distributed memory system with microprocessor and analog or digital output device connected by digital or analog signal protocols.

“Computer readable medium” means any source of organized information that may be processed by a computer to perform the steps described herein to result in, store, perform logical operations upon, or transmit, a flow or a signal flow, including but not limited to: random access memory (RAM), read only memory (ROM), a magnetically readable storage system; optically readable storage media such as punch cards or printed matter readable by direct methods or methods of optical character recognition; other optical storage media such as a compact disc (CD), a digital versatile disc (DVD), a rewritable CD and/or DVD; electrically readable media such as programmable read only memories (PROMs), electrically erasable programmable read only memories (EEPROMs), field programmable gate arrays (FPGAs), flash random access memory (flash RAM); and information transmitted by electromagnetic or optical methods including, but not limited to, wireless transmission, copper wires, and optical fibers.

“SATD” means the Sum of Absolute Transformed Differences, which is a widely used video quality metric used for block-matching in motion estimation for video compression. It works by taking a frequency transform, usually a Hadamard transform, of the differences between the pixels in the original block and the corresponding pixels in the block being used for comparison. The transform itself is often of a small block rather than the entire macroblock. For example, in H.264/AVC, a series of 4×4 blocks are transformed rather than doing a more processor-intensive 16×16 transform.

“DCT” (Discrete Cosine Transformation) means a process that converts images from three-dimensions (3D) to two-dimensions (2D) by using the Discrete Cosine (DC) coefficient to examine the luminance of each block of pixels used to form an image. This process is typically used in MPEG and JPEG image compression.

“Hadamard Transforms” are defined below. Although the Hadamard transform has numerous applications to signal processing and analysis, this application describes specific applications of the Hadamard Transform in the context of video processing, without limitation of other, more general, applications.

Hadamard transforms are used in the intra mode estimation in the Joint Model (JM) of the Advance Video Coding (AVC) encoder. Refer now toFIG. 1A, a Hadamard transform takes an input of 4 pixels (otherwise referred to as pels) and transforms them into a Hadamard Transform of 4 pixels. Similarly, inFIG. 1B, a 4×4 block may also be selectively transformed into a Hadamard Transform of a 4×4 block while outputting only a particular horizontal row and vertical column. In this instance, selected rows or columns of the input 4×4 block may be transformed as described further below. The Hadamard transform inherently possesses characteristics of uniform scaling such that each transform coefficient has the same amplification.

The Hadamard Vector Transform of a 4 pixel input may mathematically be defined in the following manner. Let {right arrow over (s)}=[s0,s1,s2,s3]Tbe a vector consisting of 4 elements. The Hadamard transform [T4] of {right arrow over (s)} is defined as {right arrow over (S)}=[S0,S1,S2,S3]T=[T4]{right arrow over (s)} where

The Hadamard Transformation of a 4×4 Block is defined as follows.

Let [y] be a 4×4 block of pixels such that

The Hadamard transform H4×4(y) of [y] is defined as

where

Referring back toFIG. 1B, to selectively determine row zero and column zero of the Hadamard block transform. Here, an input 4×4 pixel block, such as [y], is input. A selection vector {right arrow over (u)} is used to selectively determine the column zero Hadamard transform of the input 4×4 pixel block [y], to produce

[Y0,0Y1,0Y2,0Y3,0].
Similarly, selection vector {right arrow over (u)}Tis used with the input 4×4 pixel block [y], to produce the row zero Hadamard transform of the input 4×4 pixel block [y], which results in [Y0,0Y0,1Y0,2Y0,3].

The combination of the row zero block Hadamard transform, and the column zero block Hadamard transform is denoted as TRC, indicating that only a row and column of the block transformation is to be processed. This may also be referred to as a “pruned” Hadamard transformation.

Process Overview

Referring now toFIG. 2, an overview of an embodiment of a method of determining an optimal intra mode selection200is shown. In the embodiment shown, an input 4×4 block of pixels202is used as an input to the pruned 4×4 Hadamard block transformation204to produce the vertical and horizontal frequency component of the 4×4 Hadamard block transform output206. This output206will be used subsequently as described below.

The 4×1 pixels208(the 4 top elements immediately above the input 4×4 block of pixels202) are used as input into a T4Hadamard transform210to produce a vertical prediction Hadamard transform output212.

Similarly, the left 1×4 pixels214(the 4 left elements immediately left of the input 4×4 block of pixels202) are used as input into a T4Hadamard transform216to produce a horizontal prediction Hadamard transform output218.

T4Hadamard vertical212and horizontal218predictions are used to estimate the DC prediction222.

The following inputs are compared224to determine the optimal intra mode prediction226: 1) the pruned 4×4 Hadamard block transform output206; 2) the vertical prediction Hadamard transform output212; 3) the horizontal prediction Hadamard transform output218; and 4) the DC prediction222.

Only horizontal218, vertical212, and DC222predictions are used in the intra DCT mode decision coefficients. The intra predictions are performed in the frequency domain.

Refer now toFIG. 2B, which is a diagram of the various computer readable media that the selected intra mode226may be output. It may be sent to a microwave transmitter228for propagation through microwaves230to a distant connection. The intra mode226may be stored on a memory device faster or slower than the depicted USB storage device232, as well as stored on a digital or analog recording medium exemplified as a high definition video recorder234, or a still or moving digital camera236. Similarly, the intra mode226may be displayed, with or without further processing, on a graphical device such as a plasma or liquid crystal display238. The intra mode226may be transmitted through a network240, which may be wireless, or may use TCP/IP or other interconnection techniques to any other device in thisFIG. 2B. Still another output of the intra mode226may be to a multiple media device242, which may have a VHS video recorder244, or a DVD recorder246. Yet another output of the intra mode226may be to a computer248that may or may not be connected to a display device250, to be ultimately viewed by a person252. The computer248may itself have a wide variety of computer readable media available for subsequent secondary output of the intra mode226. Finally, the intra mode226may be transmitted through a wired connection254, which may have one or more conductors256of electromagnetic information, ultimately being transmitted to one or more of the devices present in thisFIG. 2B.

Estimate the Intra Macroblock DCT Coefficients

To reduce computation, only horizontal, vertical, and DC predictions are used in the estimation of the intra DCT coefficients. In particular, the intra predictions are computed in frequency domain; the DC prediction is derived from the horizontal and vertical predictions. And, finally, the prediction residue with the minimal SATD is selected as the intra mode.

Refer now toFIGS. 3A and 3B, which taken together describe the relationship300between the spatial and frequency domain intra predictor for horizontal and vertical modes. Here, an initial spatial domain representation (inFIG. 3A) of an input 4×4 block302is shown as [x] with elements xi,j, where i,jε(0,1,2,3). The frequency domain representation (inFIG. 3B) of the 4×4 transformation304is shown as the transformed matrix[X], with elements Xi,j, where i,jε(0,1,2,3).

For convenience, the 4×1 column vector to the left of vector (x0,0,x1,0,x2,0,x3,0)Twith elements (x0,−1,x1,−1,x2,−1,x3,−1)Tis denoted as {right arrow over (h)}=(h0,h1,h2,h3)T306. The Hadamard transform of h is denoted as {right arrow over (H)}=(H0,H1,H2,H3)T308.

Similarly, the 1×4 row vector above 4×4 block [x]302are (x−1,0,x−1,1,x−1,2,x−1,3), which are for convenience denoted310as {right arrow over (v)}=(v0,v1,v2,v3). The Hadamard transform of {right arrow over (v)}312is denoted {right arrow over (V)}=(V0,V1,V2,V3)T.

Compute Frequency Domain Predictors for the Intra Vertical, Horizontal, and DC Prediction Modes

This process may be followed more readily by referring toFIG. 4, which details the computation of the frequency domain predictors for the intra vertical, horizontal, and steady state (or DC) modes400.

First, input scalar index positions (Hpos,Vpos) of the top left pixels of a 4×4 pixel block [x] in a picture that begins with pixels 0,0 (the upper left corner of the picture in the H.264 design specification) and continues to pixel position values m,n. Also input the pixel block [x]402.

Next, from the 4 pixels immediately to the left and above the 4×4 pixel block [x] are denoted as404{right arrow over (h)}=(h0,h1, h2, h3)T, {right arrow over (v)}=(v0,v1,v2,v3).

At this point, now calculate the horizontal predictor {right arrow over (H)}=[H0,H1,H2,H3]T, the vertical predictor {right arrow over (V)}=[V0,V1,V2,V3]T, and the steady state (DC) predictor D as follows:

Here, it is assumed that the pixels can only take on 8 bits of information. In particular, the DC predictor 215−1 appearing in block418corresponds to the DC prediction for 8 bits per pixel. The predictor {right arrow over (H)}=[215−1,0,0,0]Tin414,418, and the predictor {right arrow over (V)}=[215−1,0,0,0]Tin416,418, are selected to make sure that they will have sufficiently large intra prediction cost for 8 bits per pixel, and consequently the corresponding prediction mode will not be selected as the minimal cost intra prediction mode inFIG. 5. This is consistent with the H.264/AVC standard.

Regardless of which calculation branch was taken from410,414,416, or418, next the cost is calculated420.

Compute Intra Prediction Cost

Refer now toFIG. 5, which predicts the computational costs of the various horizontal, vertical, or DC predictions500, and using these, outputs a selected intra mode with least SATD. To this evaluation is provided the {right arrow over (H)}, {right arrow over (V)}, D values determined above, as well as the input 4×4 pixel block [x], block502. Next, the values of Xi,0, X0,ifor iε0, 1, 2, 3 are determined504using the relationship described above for the pruned Hadamard block transform, i.e.

Cost precursors are then formed506

Finally, the costs are calculated508, where the cost of the horizontal prediction is

CH=∑i=03⁢⁢Hi-Xi,0+Cvs,
the cost of the vertical prediction is

Cv=∑j=03⁢⁢Vj-X0,j+Chs,
and the cost of the DC prediction is CD=[|D−X0,0]|+Chs+Cvs.

Once the predicted costs are determined, the appropriate intra mode is selected from the group of Horizontal Prediction, Vertical Prediction, and DC Prediction.

Minimal Cost Intra Mode Prediction

The intra mode with the minimal cost is selected as the intra prediction mode. In particular:

If CH≦CVand CH≦CD, then select Horizontal Prediction510;

If CH≦CVand CH>CD, then select DC Prediction512;

If CH>CVand CV≦CD, then select Vertical Prediction514; and finally,

The minimal cost prediction among CH, CV, and CDis then output as the appropriate associated predicted intra mode. From this point, the selected intra mode is used within the advanced video encoder to compress the 4×4 block.

Discussion

As previously described, in the H.264/AVC video compression standard the 4×4 intra mode decision is made by performing Lagrangian rate-distortion optimization on each of the 9 intra mode possibilities. The intra mode selected is the one that provides the lowest SATD between the original 4×4 input block, and the reconstructed block for a particular intra mode, where SATD is directly computed as the sum of absolute value of the transform of the difference. This process is extremely computationally expensive.

For selecting among the horizontal, vertical, and DC intra modes with the direct method, each SATD of these intra modes is separately computed with a 4×4 Hadamard block transform for a total of three 2D Hadamard transforms.

Each 2D 4×4 Hadamard transform is computationally equivalent to 8 of the 1D 4 point Hadamard transforms when row and column decomposition is used for the 2d transform.

In this process, the SATD is computed as the sum of the absolute value of difference of the transform coefficients, and only the horizontal, vertical, and DC transform coefficients are computed using 1D 4 point Hadamard transform. Thus, this process reduces the number of equivalent 1D Hadamard transforms of the horizontal, vertical, and DC intra modes from 24 to 4 by performing the intra mode prediction in the frequency domain, while providing the same intra mode selection as direct calculations of SATD.

Conclusion