Low power, high performance transform coprocessor for video compression

First and second integer transform matrices can be used to approximate the discrete cosine transform. An input matrix of data is multiplied by a first transform matrix of integers to produce an intermediate matrix of data. The intermediate matrix is multiplied by a second transform matrix of integers to produce a transform result matrix of data. The multiplications by the first and second transform matrices can be pipelined to increase throughput. A plurality of transform data paths can also be provided in parallel to increase throughput.

TECHNICAL FIELD

This disclosure is generally directed to data processing and more specifically to video compression processing.

BACKGROUND

H.264/AVC is the latest video compression standard. It was developed by the Joint Video Team (JVT), which includes experts from the Video Coding Experts Group (VCEG) of the International Telecommunications Union (ITU-T) and the Moving Picture Experts Group (MPEG) from the International Organization for Standardisation (ISO) and the International Electrotechnical Commission (IEC). In ITU-T's documents, the formal name of the new video compression standard is ITU-T Recommendation H.264. The ISO/IEC called it the ISO/IEC 14496-10 Advanced Video Coding. For short reference, this new video compression standard is commonly referred as the H.264/AVC.

H.264/AVC has many applications, including: video broadcasting over cable, satellite and DSL; video-on-demand or multimedia streaming services; conversational services over ISDN, Ethernet, LAN, wireless and mobile networks; and interactive or serial storage on optical devices such as DVD.

The H.264/AVC was designed for higher coding efficiency. In order to obtain better compression, H.264/AVC standard adopted many advanced video coding techniques. For intra coding, H.264/AVC uses a directional spatial prediction scheme to find more redundancies among pixels within a video frame. For inter coding, H.264/AVC implements multiple frames reference, weighted prediction, de-blocking filter, variable block size and quarter sample accurate motion compensations. For transformation, H.264/AVC uses a small, block-based, integer, and hierarchical transform. For entropy coding, H.264/AVC adopts two different coding techniques. The context adaptive based arithmetic coding (CABAC) is selected for the main profile whereas the context adaptive variable length coding (CAVLC) is used for baseline, main and extended profiles. Three profiles of H.264/AVC support 15 levels. These levels specify sets of algorithms and parameters for a wide range of video applications.

Note that the integer transform of H.264/AVC has lower complexity than that of the Discrete Cosine Transform (DCT) in previous video compression standards. Fifteen levels of H.264/AVC, however, cover a wide range of video formats from SQCIF (128×96) to 16:9 (4096×2304). For real time video processing, the number of macroblocks that must be processed per second is very high and is not efficient for software implementation. For instance, to process 30 frames of CIF (352×288) video format in real time, an embedded processor must process 11,880 macroblocks, which requires 36,495,360 shift and add instructions. Without load, store and transposition operations, this complexity already costs more than 36 million instructions per second (MIPS). This computational complexity is high for most embedded applications. The 16:9 format has an even far greater computational complexity than CIF.

The Discrete Cosine Transform (DCT) is one of the most important transformations in image and video processing. It has been used in many compression standards which include JPEG, H.261, H.263, MPEG-1, MPEG-2, and MPEG-4. The DCT was first proposed by Ahmed, Natarajan, and Rao in 1974 (see document [3] above). Their landmark paper presents an N-point DCT that can be computed with a 2N-point FFT and some additional post-processing. The one-dimensional DCT can map a vector x of length N into a new vector z of transform coefficients by a linear transformation z=Hx, where H is an N×N matrix such as shown inFIG. 1, and where C1√{square root over (½)}cos (π/8), C2=√{square root over (½)}cos (2π/8), and C3=√{square root over (½)}cos (3π/8). Let X be a 4×4 input matrix, Y be a 4×4 output matrix, and Htbe the transpose matrix of H. The two-dimensional (2-D) 4×4 forward DCT is then defined as Y=HXHt.

A basic disadvantage of the 4×4 DCT is that the entries in H (FIG. 1) are irrational numbers. Hence, both the forward 4×4 DCT and the inverse 4×4 DCT require floating-point execution units. The floating-point implementation increases the hardware complexity of the coding system.

To resolve this problem, Malvar (see document [4] above) suggested a method that scales entries of the 4×4 DCT matrices to obtain integer operations. The output results are rescaled to obtain an approximation of 4×4 DCT. Malvar used the scaling factor α=2.5 (see documents [4] and [5] above). The resulting scaled matrix K is shown at21inFIG. 2.FIG. 3illustrates the use of the integer transform matrix21to perform a 4-point one-dimensional integer transform on a vector x.

The approximation of a two-dimensional 4×4 DCT is Z=(KXKt){circle around (x)}S where Z is a 4×4 matrix, and S is a 4×4 resealing matrix. The matrix S is typically incorporated into the quantization stage, which is usually implemented by lookup tables. Therefore, the approximation of a two-dimensional 4×4 DCT can be implemented completely by integer operations. With the matrix S incorporated into the quantization stage, the two-dimensional 4×4 integer transform is W=KXKt.

In view of the computational complexities associated even with integer transform processing of the various video formats supported by H.264/AVC, it is desirable to provide for integer transform processing with reduced computational complexity.

SUMMARY

Exemplary embodiments of the invention utilize first and second integer transform matrices to approximate the discrete cosine transform. An input matrix of data is multiplied by a first transform matrix of integers to produce an intermediate matrix of data. The intermediate matrix is multiplied by a second transform matrix of integers to produce a transform result matrix of data. The multiplications by the first and second transform matrices can be pipelined to increase throughput. A plurality of transform data paths can also be provided in parallel to increase throughput.

The foregoing has outlined rather broadly the features and technical advantages of the present invention so that those skilled in the art may better understand the detailed description of the invention that follows. Additional features and advantages of the invention will be described hereinafter that form the subject of the claims of the invention. Those skilled in the art will appreciate that they may readily use the conception and the specific embodiment disclosed as a basis for modifying or designing other structures for carrying out the same purposes of the present invention. Those skilled in the art will also realize that such equivalent constructions do not depart from the spirit and scope of the invention in its broadest form.

DETAILED DESCRIPTION

FIG. 4illustrates factoring of the integer transform matrix21ofFIGS. 2 and 3according to exemplary embodiments of the invention. InFIG. 4, the integer transform matrix21is factored into constituent transform matrices41and42which, when multiplied together, produce the matrix21. Considering again the 4-point one dimensional integer transform illustrated inFIG. 3, that transform requires twelve addition operations and four multiplication (typically data shift) operations. This means that a 4×4 one dimensional integer transform using the matrix21ofFIG. 3would require 48 addition operations and 16 shift operations, and a 4×4 two dimensional integer transform using the matrix21ofFIG. 3would require 96 addition operations and 32 shift operations.

However, if the integer transform operation is performed using the constituent factor transform matrices41and42of FIG.4, then a 4 point one dimensional integer transform operation of the type illustrated inFIG. 3can be performed with only 8 addition operations and 2 multiplication (shift) operations. This means that a 4×4 one dimensional integer transform operation can be performed with 32 addition operations and 8 shift operations, and a 4×4 two dimensional integer transform operation can be performed with 64 addition operations and 16 shift operations.

FIG. 5illustrates an exemplary implementation of the constituent factor transform matrices41and42ofFIG. 4according to the invention. InFIG. 5, the transform matrices41and42are used to perform a 4×4 one dimensional integer transform on a matrix51of input data, in order to produce a 4×4 transform result matrix52. The data components of input matrix51are designated by xrjinFIG. 5where r and j are the respective row and column indices of the matrix51, and where r and j can each take the values 0, 1, 2 and 3. The data components of the transform result matrix52are designated as brjinFIG. 5, where r and j are the same respective row and column indices as described above with respect to matrix51.

FIG. 6illustrates a first stage (stage1) integer transform operation associated with the implementation ofFIG. 5. In the example ofFIG. 6, the transform matrix41is used as a first stage transform matrix and is multiplied by the input data matrix51to produce an intermediate data matrix61whose components are designated as arj, where r and j are the same respective row and column indices as described above with respect to matrices51and52.

FIG. 7illustrates a second stage (stage2) integer transform operation associated with the implementation ofFIG. 5. InFIG. 7, the matrix42is used as a second stage transform matrix and is multiplied by the intermediate matrix61in order to produce the transform result matrix52(see alsoFIG. 5).

FIG. 8diagrammatically illustrates exemplary embodiments of a data processing apparatus which can perform the first and second stage operations described above with respect toFIGS. 6 and 7. The apparatus ofFIG. 8includes a matrix multiplication apparatus having a matrix multiplier81which performs the first stage matrix multiplication operation illustrated inFIG. 6, and having a matrix multiplier82which performs the second stage matrix multiplication operation illustrated inFIG. 7. As shown inFIG. 8, the first stage matrix multiplier81receives the data from the input data matrix51and performs the arithmetic operations necessary to produce the intermediate data matrix61(see alsoFIG. 6). In particular, the matrix multiplier81includes four adders connected appropriately, and with necessary inversions, to perform the four addition operations required to implement the matrix multiplication equation ofFIG. 6. The matrix multiplier82receives the data from the intermediate matrix61and performs the arithmetic operations necessary to produce the transform result matrix52(see alsoFIG. 7). The matrix multiplier82includes four adders connected appropriately, and with necessary inversions and shifters, to perform the four addition operations and two shift operations required to implement the matrix multiplication equation ofFIG. 7. Data shifters83and84each perform a single left shift (multiply by 2) operation in order to implement the two multiplication operations required by the equation ofFIG. 7.

FIG. 9illustrates in tabular format the timing of exemplary operations which can be performed by the data processing apparatus ofFIG. 8. In particular, and referring also toFIGS. 6 and 7,FIG. 9shows that the data processing apparatus ofFIG. 8can produce each column of the matrix61ofFIG. 6in a single clock cycle, and can also produce each column of the matrix52ofFIG. 7in a single clock cycle. That is, the adders of the matrix multiplier81can effectuate a multiplication of all four rows of the transform matrix41by any given column of the input matrix51in a single clock cycle, and the adders of the matrix multiplier82, together with shifters83and84, can effectuate multiplication of all four rows of matrix42by any given column of matrix61in a single clock cycle. Therefore, during clock cycle2, after the first stage matrix multiplier81has already produced the first column of intermediate matrix61during clock cycle1, the second stage matrix multiplier82can use the first column of the intermediate matrix61to produce the first column of the transform result matrix52. Thus, during clock cycle1ofFIG. 9, the matrix multiplier81produces the first column (column0) of the intermediate matrix61. Thereafter, during clock cycle2ofFIG. 9, while the matrix multiplier81is producing the second column (column1) of the intermediate matrix61, the second stage matrix multiplier82is simultaneously using the already-produced first column of intermediate matrix61to produce the first column of the transform result matrix52.

Thus, the operations of the matrix multipliers81and82can be pipelined as shown inFIG. 9in order to produce the complete transform result matrix52ofFIG. 7in five clock cycles. So the data processing apparatus ofFIG. 8can perform a 4×4 one dimensional integer transform in five clock cycles. As indicated byFIG. 9, during clock cycle5, while the second stage matrix multiplier82is producing the fourth column (column3) of the transform result matrix52ofFIG. 7, the first stage matrix multiplier81can be simultaneously operating on a subsequent input data matrix51to produce the first column of a subsequent intermediate data matrix61(see alsoFIG. 6).

FIG. 10diagrammatically illustrates exemplary embodiments of a data processing apparatus which can perform a 4×4 two dimensional integer transform according to the invention. In the example ofFIG. 10, the architecture ofFIG. 8is used to perform a horizontal transform HT and is also used to perform a vertical transform VT. In the matrix multiplication apparatus illustrated inFIG. 10, the horizontal transform portion HT performs the operations illustrated inFIG. 8to produce the transform result matrix52. This transform result matrix52is then stored in one of two buffers105and106, as selected by a selector103under control of a control signal107. A further selector104under control of a control signal108provides the content of one of buffers105and106to the vertical transform portion VT. In some embodiments, the buffers105and106can be read such that the data from the buffered transform result matrix52is provided to the vertical transform portion VT on a row-by-row basis, so the vertical transform portion VT operates on the transpose of the buffered transform result matrix52. This effective transposing of the buffered transform result matrix52is illustrated inFIG. 10by the use of the reference character52t. Transposition of the result matrix produced by horizontal transform portion HT permits the vertical transform portion VT to perform the transform in the second dimension.

FIG. 11illustrates in tabular format the timing of exemplary operations which can be performed by the data processing apparatus ofFIG. 10. In clock cycle5, the horizontal transform portion HT completes its operation on the first 4×4 input data matrix51(also designated as B1), and stage1of the HT portion has also already begun operation on the second 4×4 input data matrix51(also designated as B2). Because the horizontal transform portion finishes producing the first transform result matrix52during clock cycle5, this means the vertical transform portion VT can begin operations on the transpose52tof the first transform result matrix52during clock cycle6. The correspondence of the transposed transform result matrices52tto the input data matrices51is illustrated inFIG. 11by maintaining corresponding subscript numbers on the designators B.

InFIG. 10, the selectors103and104are controlled by logically complementary control signals107and108such that the vertical transform portion VT is never accessing the buffer to which the horizontal transform portion HT is writing. As shown inFIG. 11, while the vertical transform portion VT is processing the transposed transform result matrix52t/B1associated with the first input matrix51/B1, the horizontal transform portion HT is simultaneously processing data from the second input data matrix51/B2in the sequence of input data matrices. The horizontal transform portion HT can complete its operation on a sequence of six 4×4 input matrices in 25 clock cycles and, by virtue of the pipelining illustrated inFIG. 11, the complete two dimensional transform of a sequence of six 4×4 input data matrices is completed in thirty clock cycles.

The output of the vertical transform portion VT inFIG. 10can be provided to a conventional quantization stage for conventional rescaling and quantizing.

FIG. 12diagrammatically illustrates exemplary embodiments of a data processing apparatus which can perform a plurality of 4×4 two-dimensional integer transforms in parallel according to the invention. The example ofFIG. 12generally uses four instances of the architecture ofFIG. 10, arranged in parallel. Therefore, the apparatus ofFIG. 12can perform two dimensional transform processing on 24 4×4 input matrices in thirty clock cycles (see alsoFIG. 11). The twenty four 4×4 input data blocks illustrated in the example ofFIG. 12are the well-known constituent blocks of a conventional H.264/AVC macroblock. Each of the four 32-bit input registers can hold four 8-bit input pixels.

FIG. 13diagrammatically illustrates exemplary embodiments of a data processing system according to the invention. The system ofFIG. 13, for example a high definition television system or a digital cinema system, includes a main processor131, a memory portion132, a user interface (I/O)133and an accelerator coprocessor134. These components are interconnected by a bus system135. In various embodiments, the accelerator coprocessor134can implement the various exemplary integer transform architectures described above with respect toFIGS. 8-12. In some exemplary embodiments, the main processor131and the coprocessor134implement respective pipelines. The coprocessor134receives instructions from the main processor131, and uses a pipeline follower to determine what instruction it must execute. To avoid congestion in the critical path, in some embodiments the coprocessor pipeline operates one clock cycle behind the main processor pipeline. After receiving a given instruction, the coprocessor loads data from the memory and performs the necessary transform operations.

In some exemplary embodiments, the main processor131is an ARM946E-S processor, the system memory portion132includes 512 kilobytes of SRAM and 4 megabytes of SDRAM, and the bus system135is a conventional high speed AMBA bus system for increased data throughput between the main processor131, the coprocessor134and the system memory132.

Referring again to the exemplary architecture ofFIG. 12, the hardware cost of the illustrated architecture is low. It requires four 32-bit registers, four 64-bit registers, 16 multiplexers, 32 adders and 256 bytes of buffer memory. The small buffer memory is implemented with D flip-flops in some embodiments. In one example using 0.18 μm CMOS technology, the footprint of theFIG. 12architecture is only 0.0838 mm2. Even with this small footprint, the architecture still provides sufficient computing power for real time video processing. At a 10 MHz clock rate, for example, the architecture can compute integer transforms for 2K×1K (2048×1024) format at 30 frames per second. For high definition video applications using 16:9 format (4096×2034) running at 60 frames per second, the architecture requires 66,355,200 clock cycles, which is equivalent to 67 MHz. The design of the architecture can be scaled to meet this real time constraint.

Note that the average power consumption of a CMOS gate due to the switching current is given by P=αCLVdd2f, where f is the system clock frequency, Vddis the supply voltage, CLis the load capacitance, and α is the switching activity. In one example of the architecture ofFIG. 12, the clock rate is 10 MHz, the global voltage is 1.55 V, and the load capacitance is 1 pf. The switching power reported by a hardware simulation for this example is 529 μW.

Besides the compact area and low power consumption, exemplary embodiments of the invention require only a small data range. FromFIGS. 5-7, the data range at the output of each stage can be easily determined. In the worst case, and assuming 8-bit pixel inputs, the outputs of the first dimensional transform (e.g. HT inFIGS. 10 and 12) are 11 bits and the outputs of the second dimensional transform (e.g. VT inFIGS. 10 and 12) are 14 bits. Hence, a 4×4 two-dimensional integer transform can be implemented with a 14-bit wide data path.

As demonstrated above, exemplary embodiments of the invention introduce a method and an apparatus to reduce computational complexity and increase the throughput of the integer transform in H.264 video compression standard. The method factors the integer transform matrix into two integer matrices with less computations. In addition, this approach also allows the integer transform be calculated in two steps, which is well suited for pipeline architecture.