Abstract:
A video decoding method, system and computer program product perform inverse transforming of transform coefficients for a video image. The inverse transforming is performed with a processing circuit on a first block of transform coefficients by a transform matrix having a plurality of vectors. The coefficients are transformed into a corresponding second block of residual pixel values for the video image. The transform matrix consists of integer elements, and includes a 4 point transform as whole or partial vectors of the transform matrix. The first row of the 4 point transform includes elements a a a a. The second row includes b c −c −b. The third row includes a −a −a a. The fourth row includes c −b b −c, wherein a, b and c comply with |b 2 +c 2 −(a 2 +a 2 )|/(a 2 +a 2 )&lt;0.003, b/c being in an inclusive range of 2.1 through 2.4, and each of a, b and c being integer.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
     The present application contains subject matter related to U.S. Utility application Ser. No. 12/987,246, filed on Jan. 10, 2011, the entire contents of which being incorporated herein by reference. 
     BACKGROUND 
     1. Field 
     This technology generally is related to video decompression and compression systems, methods and computer program product, and in particular to an integer transform function performed in those systems, methods and computer program product. 
     2. Description of the Related Art 
     The “background” description provided herein is for the purpose of generally presenting the context of the disclosure. Insight provided by the present inventor, to the extent it is described in this background section, as well as aspects of the description which may not otherwise qualify as prior art at the time of filing, are neither expressly or impliedly admitted as prior art. 
     Transmission of moving pictures in real-time is employed in numerous applications such as video conferencing, “net meetings”, television (TV) broadcasting and video telephony. 
     However, representing moving pictures involves bulk information, in digital form, and is described by representing each picture element (pixel) in a picture (or image frame) with 8 bits (1 Byte). Aggregation of uncompressed video data results in very large bit quantities, and as a consequence demands large bandwidth allocation for transmission over conventional communication networks in real time due to limited bandwidth. 
     Due to significant redundancy in images between successive frames, data compression is freely applied in real time video transmission applications. Data compression may, however, compromise picture quality and so persistent efforts continue to be made to develop data compression techniques allowing real time transmission of high quality video over bandwidth limited resources. 
     In video compression systems, an objective is to represent the video information with as little “capacity” as possible, where capacity is usually measured in bits, either as a constant value or as bits/time unit. By minimizing bits, the amount of bits that need to be transmitted is reduced, and therefore, the amount of communication resources needed to support the real time transmission of video data is also reduced. 
     The most common video coding methods are described in the MPEG* (e.g., MPEG 2 and MPEG 3)and H.26* (e.g., H.263 and H.264) standards. According to these standards, the video data is exposed to four main processes before transmission, namely prediction, transformation, quantization and entropy coding. 
     The prediction process performed in a prediction processor significantly reduces the number of bits required for each frame in a video sequence to be transferred. It takes advantage of the similarity of parts of the sequence with other parts of the sequence. A decoder that decodes the bit stream has side information to assist in the decoding process. This side information is known to both encoder and decoder and so only the difference has to be transferred. This difference typically requires much less capacity for its representation than the full image. The motion estimation aspect of the prediction is mainly based on picture content from previously reconstructed pictures where the location of the content is defined by motion vectors. The prediction process is typically performed on square block sizes (e.g. 16×16 pixels), although the size of the blocks may vary. 
     Note that in some cases, predictions of pixels based on the adjacent pixels in the same picture rather than pixels of preceding pictures are used. This is referred to as intra prediction, as opposed to inter prediction. 
     The transform and quantization processes will now be discussed in more detail. The residual represented as a block of data (e.g. 4×4 or 8×8 pixels) may still contain internal correlation. A conventional method of taking advantage of this is to perform a two dimensional block transform. The ITU recommendation H.264 uses a 4×4 or 8×8 integer type transform. This transforms n×n pixels into n×n transform coefficients and they can usually be represented by fewer bits than the raw pixel representation. Transformation of an n×n array of pixels with internal correlation will often result in an n×n block of transform coefficients with much fewer non-zero values than the original n×n pixel block. 
     Direct representation of the transform coefficients is still too costly for many applications. A quantization process is carried out for a further reduction of the data representation. Hence the transform coefficients output from the transform undergo quantization. The possible value range of the transform coefficients is divided into value intervals (or gradations), each limited by an uppermost and lowermost decision value and assigned a fixed quantization value. The transform coefficients are then quantified to the quantization value associated with the intervals within which the respective coefficients reside. Coefficients being lower than the lowest decision value are quantified to zeros. It should be mentioned that this quantization process results in the reconstructed video sequence being somewhat different compared to the uncompressed sequence. 
     Summarized, a digital video picture is exposed to the following steps:
         Divide the picture into square blocks of pixels, for instance 16×16 or 8×8 pixels. This is done for luminance information as well as for chrominance information.   Produce a prediction for the pixels in the block. This may be based on pixels in an already coded/decoded picture (called inter prediction) or on already coded/decoded pixels in the same picture (intra prediction).   Form a difference between the pixels to be coded and the predicted pixels. This is often referred to as a residual.   Perform a two dimensional transformation of the residual resulting in a representation as transform coefficients.   Perform a quantization of the transform coefficients. This is the major tool for controlling the bit production and reconstructed picture quality.   Establish a scanning of the two dimensional transform coefficient data into a one dimensional set of data.   Perform lossless entropy coding of the quantized transform coefficients.       

     The above steps are listed in a natural order for the encoder. The decoder will to some extent perform the operations in the opposite order and do “inverse” operations as inverse transform instead of transform and de-quantization instead of quantization. 
     SUMMARY 
     The following paragraphs have been provided by way of general introduction, and are not intended to limit the scope of the appended claims. The described embodiments, together with further advantages, will be best understood by reference to the following detailed description taken in conjunction with the accompanying drawings. 
     The present inventor recognized limitations with conventional transform devices and methods in that they do not employ matrices that strike a desirable balance between vector length (and corresponding block size), transform element size, vector norms below a predetermined threshold, and inner products being less than a predetermined threshold. 
     In addressing these and other limitations, one aspect of the present disclosure provides a method (and device and computer program product) of transforming data in an encoder using a transform matrix, as well as inverse transforming of transform coefficients in a decoder for a video image. Because the encoding and decoding processes are inverse, the decoding processing will be described, but it should be understood that the transform matrices described herein are equally applicable to an encoding process. The inverse transforming may be performed with a processing device on a first block of transform coefficients by a transform matrix having a plurality of vectors. The coefficients are transformed into a corresponding second block of residual pixel values for the video image. The transform matrix consists of integer elements, and includes a 4 point transform as whole or partial vectors of the transform matrix. The first row of the matrix includes elements a a ag a; the second row includes b c −c −b; the third row includes a −a −a a; and the fourth row includes c −b b −c, wherein a, b and c comply with |b 2 +c 2 −(a 2 +a 2 )|/(a 2 +a 2 )&lt;0.003, b/c being in an inclusive range of 2.1 through 2.4, and each of a, b and c being integers. 
     Other aspects include a corresponding inverse method, device and computer program product, as well as video equipment, such as a video teleconferencing endpoint, that hosts the transform. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       These and other features, aspects and advantages of the present invention will become better understood with regard to the following description, appended claims and accompanying drawings where: 
         FIG. 1  is a block diagram showing a process flow in a video encoder that includes a transform operation according to the present disclosure. 
         FIG. 2  is a block diagram showing a process flow in a video decoder that includes an inverse transform operation according to the present disclosure. 
         FIG. 3  is a block diagram representing the transform process flow employed in the exemplary embodiments; and 
         FIG. 4  is a block diagram of an exemplary image processing device that can be used to perform or implement the method, device and computer program product that employs the transformation encoding and/or decoding described herein. 
     
    
    
     DETAILED DESCRIPTION 
     In  FIG. 1 , a current frame as well as one or more reference frames are input to a prediction processor  1 . The prediction processor  1  includes an intra prediction processing path  3  and a motion estimation processing path  5 , the selection of which is controlled by switch  7 . Intra prediction processing is selected for finding similarities within the current image frame, and is thus referred to as “intra” prediction. Motion estimation has a temporal component and thus involves analysis between successive frames is referred to as “inter” prediction. 
     The output of the switch  7  is combined with the pixels of the current frame in a combiner  9 , prior to being subjected to core coding  11 , which includes a transform processor  13  (often involving rate distortion control). Typically the transform is a discrete cosine transform (DCT), which is generally considered to a very good transform to be used in image and video compression. The DCT is defined with real numbers. For practical implementations there are good reasons to use a transform with integer numbers instead, as will be discussed later. The transformed data is then subjected to quantization in a quantizer  15  and then subject to an entropy encoder  17 . Entropy encoding removes redundancies without losing information, and is referred to as a lossless encoding process. Subsequently, the encoded data is arranged in network packets via a packetizer  19 , prior to be transmitted in a bit stream. The transform matrices described herein are employed in the transform processor  13 . Likewise, an inverse quantization and transform is performed at a decoder to recover the image. 
       FIG. 2  is a block diagram showing a process flow within a decoder device according to an embodiment. An input bit stream from an encoder is applied to a depacketizer and decoder  22 , which unpackages the data before sending the data to an inverse quantizer  24 . The inverse quantizer  24  provides a best-effort at providing an inverse of the quantization performed in the quantization  15  ( FIG. 1 ). The output of the inverse quantization  24  is applied to an inverse integer transform  26 , which performs an inverse to the integer transform performed in the video encoder ( FIG. 1 ). The integer transform  26  uses the same vectors as in the transform matrix to arrive at the original residue data, which was originally applied to the transform matrix in the encoder. The residue data is then subjected to a reconstruction operation using motion compensation input to produce an output video stream. 
     Most conventional video standards produce block-based residuals that undergo a two dimensional transform on the encoding side and a corresponding inverse transform on the decoding side, and separable transforms are usually used. This means that a one dimensional transform is first performed in one direction (e.g. horizontal) followed by the same one dimensional transform being used on the result in the other direction (e.g., vertical). Hence only one dimensional transforms have to be defined and used. 
     In the standards H.261, H.263, and the corresponding MPEG standards, a 8 point DCT is used. According to signal theory, the DCT is close to an optimal transform if the correlation between neighboring pixels in the residual signal is relatively high. The DCT is defined as 8 real valued basis vectors as listed below with 3 digit accuracy: 
     
       
         
               
               
               
               
               
               
               
               
             
           
               
                   
               
             
             
               
                 0.354 
                 0.354 
                 0.354 
                 0.354 
                 0.354 
                 0.354 
                 0.354 
                 0.354 
               
               
                 0.490 
                 0.416 
                 0.278 
                 0.098 
                 −0.098 
                 −0.278 
                 −0.416 
                 −0.490 
               
               
                 0.462 
                 0.191 
                 −0.191 
                 −0.462 
                 −0.462 
                 −0.191 
                 0.191 
                 0.462 
               
               
                 0.416 
                 −0.098 
                 −0.490 
                 −0.278 
                 0.278 
                 0.490 
                 0.098 
                 −0.416 
               
               
                 0.354 
                 −0.354 
                 −0.354 
                 0.354 
                 0.354 
                 −0.354 
                 −0.354 
                 0.354 
               
               
                 0.278 
                 −0.490 
                 0.098 
                 0.416 
                 −0.416 
                 −0.098 
                 0.490 
                 −0.278 
               
               
                 0.191 
                 −0.462 
                 0.462 
                 −0.191 
                 −0.191 
                 0.462 
                 −0.462 
                 0.191 
               
               
                 0.098 
                 −0.278 
                 0.416 
                 −0.490 
                 0.490 
                 −0.416 
                 0.278 
                 −0.098 
               
               
                   
               
             
          
         
       
     
     These basis vectors are said to be orthonormal, which means that (1) each vector (e.g., row) is orthogonal to all the other vectors, and (2) the norm, or square sum along each line, is equal to 1. 
     Defining now the above matrix of data T(i, j), i, j=0-7. i indicates the column number and j indicates row number. Assuming further that there is a set of 8 pixel values f(i) of an 8×8 block to be transformed into 8 transform values F(j). The following relations then apply: 
                 F   ⁡     (   j   )       =       ∑     i   =   0.7       ⁢       f   ⁡     (   i   )       *     T   ⁡     (     i   ,   j     )             ,     j   =     0   ⁢     -     ⁢   7             
Inverse transform or reconstruction of the pixels:
 
                 F   ⁡     (   i   )       =       ∑     j   =   0.7       ⁢       f   ⁡     (   j   )       *     T   ⁡     (     i   ,   j     )             ,     i   =     0   ⁢     -     ⁢   7             
The transform is then normally performed on each set of 8 pixel values of the 8×8 block, and then the whole procedure is repeated on the result vertically with the same transform matrix.
 
     This transform performs well in theory. However in practice, as recognized by the present inventor, it has a disadvantage that it is based on real number representation. In implementation this will inevitably result in some inaccuracy, which in turn will be slightly different for different implementations using different internal representations of real numbers. This may lead to a mismatch between different reconstruction procedures. The implementation is also relatively complex. For these reasons it is desirable to use transforms that are described by integer numbers only. 
     The orthonormal conditions defined above are still desirable. With integer numbers it is impossible to obtain the condition that the square sum along each line is equal to 1. It is therefore more realistic and feasible to change the requirement of the norm to be the same for all vectors, but still maintaining the first requirement that each vector shall be orthogonal to all the other vectors. 
     An example of basis vectors satisfying the last-mentioned requirements are the Walsh Hadamard vectors. 8 point Hadamard vectors are as follows: 
     
       
         
           
             
               
                 1 
               
               
                 1 
               
               
                 1 
               
               
                 1 
               
               
                 1 
               
               
                 1 
               
               
                 1 
               
               
                 1 
               
             
             
               
                 1 
               
               
                 1 
               
               
                 1 
               
               
                 1 
               
               
                 
                   - 
                   1 
                 
               
               
                 
                   - 
                   1 
                 
               
               
                 
                   - 
                   1 
                 
               
               
                 
                   - 
                   1 
                 
               
             
             
               
                 1 
               
               
                 1 
               
               
                 
                   - 
                   1 
                 
               
               
                 
                   - 
                   1 
                 
               
               
                 
                   - 
                   1 
                 
               
               
                 
                   - 
                   1 
                 
               
               
                 1 
               
               
                 1 
               
             
             
               
                 1 
               
               
                 1 
               
               
                 
                   - 
                   1 
                 
               
               
                 
                   - 
                   1 
                 
               
               
                 1 
               
               
                 1 
               
               
                 
                   - 
                   1 
                 
               
               
                 
                   - 
                   1 
                 
               
             
             
               
                 1 
               
               
                 
                   - 
                   1 
                 
               
               
                 
                   - 
                   1 
                 
               
               
                 1 
               
               
                 1 
               
               
                 
                   - 
                   1 
                 
               
               
                 
                   - 
                   1 
                 
               
               
                 1 
               
             
             
               
                 1 
               
               
                 
                   - 
                   1 
                 
               
               
                 
                   - 
                   1 
                 
               
               
                 1 
               
               
                 
                   - 
                   1 
                 
               
               
                 1 
               
               
                 1 
               
               
                 
                   - 
                   1 
                 
               
             
             
               
                 1 
               
               
                 
                   - 
                   1 
                 
               
               
                 1 
               
               
                 
                   - 
                   1 
                 
               
               
                 
                   - 
                   1 
                 
               
               
                 1 
               
               
                 
                   - 
                   1 
                 
               
               
                 1 
               
             
             
               
                 1 
               
               
                 
                   - 
                   1 
                 
               
               
                 1 
               
               
                 
                   - 
                   1 
                 
               
               
                 1 
               
               
                 
                   - 
                   1 
                 
               
               
                 1 
               
               
                 
                   - 
                   1 
                 
               
             
           
         
       
     
     However, this transform turns out to have other drawbacks and is therefore not very much used. 
     A better and expanded set of requirements for integer transforms is found via the application of the following criteria:
         1. The vectors shall be orthogonal.   2. The numbers used to define the vectors are small—typically less than 32, although as will be discussed, but also within a range representable in 1 Byte.   3. The shape of the vectors are as close as possible to the corresponding DCT.   4. The norm, or square sum along each line shall be the same for all vectors.       

     It is difficult to satisfy all the requirements—especially for larger transforms. The above requirements can therefore be considered to be listed in prioritized order. Traditionally, 1 and 2 have been considered to be mandatory, 3 may be only partly fulfilled whereas 4 may be worked around with some added complexity in the implementations. 
     In the early development of H.264/AVC the following transform was considered, but not adopted: 
     
       
         
           
             
               
                 13 
               
               
                 13 
               
               
                 13 
               
               
                 13 
               
             
             
               
                 17 
               
               
                 7 
               
               
                 
                   - 
                   7 
                 
               
               
                 
                   - 
                   17 
                 
               
             
             
               
                 13 
               
               
                 
                   - 
                   13 
                 
               
               
                 
                   - 
                   13 
                 
               
               
                 13 
               
             
             
               
                 7 
               
               
                 
                   - 
                   17 
                 
               
               
                 17 
               
               
                 
                   - 
                   7 
                 
               
             
           
         
       
     
     This vector set satisfied requirements 1, 2, 3, 4 above. The H.264/AVC standards use both 4 point and 8 point integer transforms. As for the 4 point transform, the basis vectors are: 
                 1       1       1       1           2       1         -   1           -   2             1         -   1           -   1         1           1         -   2         2         -   1               
Although this matrix was adopted in H.264/AVC, the vectors do not have the same norm, or close to the same norm. As a consequence, more numeric manipulation is required during quantization to avoid bias.
 
     The above vector set fulfills requirements 1, 2 and partly 3 above. 
     As for the 8 point transform, the basis vectors are: 
     
       
         
           
             
               
                 1 
               
               
                 1 
               
               
                 1 
               
               
                 1 
               
               
                 1 
               
               
                 1 
               
               
                 1 
               
               
                 1 
               
             
             
               
                 12 
               
               
                 10 
               
               
                 6 
               
               
                 3 
               
               
                 
                   - 
                   3 
                 
               
               
                 
                   - 
                   6 
                 
               
               
                 
                   - 
                   10 
                 
               
               
                 
                   - 
                   12 
                 
               
             
             
               
                 2 
               
               
                 1 
               
               
                 
                   - 
                   1 
                 
               
               
                 
                   - 
                   2 
                 
               
               
                 
                   - 
                   2 
                 
               
               
                 
                   - 
                   1 
                 
               
               
                 1 
               
               
                 2 
               
             
             
               
                 10 
               
               
                 
                   - 
                   3 
                 
               
               
                 
                   - 
                   12 
                 
               
               
                 
                   - 
                   6 
                 
               
               
                 6 
               
               
                 12 
               
               
                 3 
               
               
                 
                   - 
                   10 
                 
               
             
             
               
                 1 
               
               
                 
                   - 
                   1 
                 
               
               
                 
                   - 
                   1 
                 
               
               
                 1 
               
               
                 1 
               
               
                 
                   - 
                   1 
                 
               
               
                 
                   - 
                   1 
                 
               
               
                 1 
               
             
             
               
                 6 
               
               
                 
                   - 
                   12 
                 
               
               
                 3 
               
               
                 10 
               
               
                 
                   - 
                   10 
                 
               
               
                 
                   - 
                   3 
                 
               
               
                 12 
               
               
                 
                   - 
                   6 
                 
               
             
             
               
                 1 
               
               
                 
                   - 
                   2 
                 
               
               
                 2 
               
               
                 
                   - 
                   1 
                 
               
               
                 
                   - 
                   1 
                 
               
               
                 2 
               
               
                 
                   - 
                   2 
                 
               
               
                 1 
               
             
             
               
                 3 
               
               
                 
                   - 
                   6 
                 
               
               
                 10 
               
               
                 
                   - 
                   12 
                 
               
               
                 12 
               
               
                 
                   - 
                   10 
                 
               
               
                 6 
               
               
                 
                   - 
                   3 
                 
               
             
           
         
       
     
     This vector set also satisfies requirements 1, 2 and partly 3. However, three different norms are present, with fairly large differences in value. 
     As a foundation for subsequent discussions on transform reuse, several observations by the present inventor are now presented. It can be seen from the above 4 point and 8 point transforms that the 4 point transform is reused in the 8 point transform. The 8 point transform is repeated below. 
     
       
         
               
               
             
               
               
               
               
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 Basis vector 
               
               
                   
                 number 
               
               
                   
                   
               
             
             
               
                   
               
             
          
           
               
                 
                   1 
                 
                   1   
                 
                   1 
                 
                   1   
                 1 
                 1 
                 1 
                 1 
                 0 
               
               
                 12  
                 10 
                 6 
                  3 
                 −3 
                 −6 
                 −10 
                 −12 
                 1 
               
               
                 
                   2 
                 
                   1   
                   −1   
                 
                   −2 
                 
                 −2 
                 −1 
                 1 
                 2 
                 2 
               
               
                 10  
                 −3 
                 −12  
                 −6 
                 6 
                 12 
                 3 
                 −10 
                 3 
               
               
                 
                   1 
                 
                 
                   −1 
                 
                   −1   
                   1   
                 1 
                 −1 
                 −1 
                 1 
                 4 
               
               
                 6 
                 −12  
                 3 
                 10 
                 −10 
                 −3 
                 12 
                 −6 
                 5 
               
               
                 
                   1 
                 
                 
                   −2 
                 
                 
                   2 
                 
                 
                   −1 
                 
                 −1 
                 2 
                 −2 
                 1 
                 6 
               
               
                 3 
                 −6 
                 10  
                 −12  
                 12 
                 −10 
                 6 
                 −3 
                 7 
               
               
                   
               
             
          
         
       
     
     The 8 basis vectors are numbered 0 to 7. It is seen that the underlined numbers are the same as in the 4 point transform. The underlined numbers are all in the first four positions of the even basis vectors (0, 2, 4, 6). The underlined numbers are further mirrored (in the last four position on the same even basis vector) so that all the even basis vectors are described by the 4 point transform basis vectors In the present disclosure when the 4 point transform is used as “the transform matrix”, there is an identify between the vectors of the 4 point transform and the transform matrix. However, when the transform matrix is larger (e.g., 8 point, 16 point, or 32 point transform) the vectors of the 4 point transform are reproduced as parts of selected vectors in the larger transform matrix, as will be discussed and shown below. This reuse of smaller transforms in larger transforms may be referred to as an embedded transform structure. The DCT has this property, and it is also typically a property of integer transforms used in video coding. Accordingly, when considering a transform family of sizes 4, 8, 16, and 32, the following relationships follow:
         The even basis vectors of the 32 point transform are described by the 16 point transform.   The even basis vectors of the 16 point transform are described by the 8 point transform.   The even basis vectors of the 8 point transform are described by the 4 point transform.       

     This means that the 4 basis vectors for the 4 point transform are reused in all the larger transforms. Moreover, these 4 basis vectors are the building blocks of the larger transforms in the family. Written generically, the 4 point transform can be expressed in the following way: 
     
       
         
           
             
               
                 a 
               
               
                 a 
               
               
                 a 
               
               
                 a 
               
             
             
               
                 b 
               
               
                 c 
               
               
                 
                   - 
                   c 
                 
               
               
                 
                   - 
                   b 
                 
               
             
             
               
                 a 
               
               
                 
                   - 
                   a 
                 
               
               
                 
                   - 
                   a 
                 
               
               
                 a 
               
             
             
               
                 c 
               
               
                 
                   - 
                   b 
                 
               
               
                 b 
               
               
                 
                   - 
                   c 
                 
               
             
           
         
       
     
     In this notation, the 4 point transform is described by the three numbers a, b, and c with positive or negative sign as similarly expressed in the previous examples. Here a, b, c are furthermore assumed to be integer numbers. Below it is shown how the numbers a, b, c are reused in the larger transforms, that is 8 point, 16 point and 32 point transforms. The DCT transforms of size 4, 8, 16 and 32 points also have this property. In the listings below each line represents a basis vector. For the 8, 16, and 32 point transforms there are 8, 16, and 32 basis vectors, each listed in the usual order from low spatial frequency (DC) to high spatial frequency. Another way of naming this ordering is by counting the number of sign shifts for each vector, which is also indicated in the listings below. 
     
       
         
               
               
             
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
             
           
               
                   
               
               
                 8 point transform 
                 No. of Sign Changes 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 0 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
             
          
           
               
                 b 
                 c-c-b-b-c 
                 c 
                 b 
                 2 
               
             
          
           
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                   
               
             
          
           
               
                 a-a-a 
                 a 
                 a-a-a 
                 a 
                 4 
               
             
          
           
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                   
               
             
          
           
               
                 c-b 
                 b-c-c 
                 b-b 
                 c 
                 6 
               
             
          
           
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                   
               
             
          
         
       
     
     
       
         
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
           
               
                   
               
               
                 16 point transform 
                 No. of sign Changes 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 0 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
             
          
           
               
                 b 
                 c-c-b-b-c 
                 c 
                 b 
                 b 
                 c-c-b-b-c 
                 c 
                 b 
                 4 
               
             
          
           
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                   
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
             
          
           
               
                 a-a-a 
                 a 
                 a-a-a 
                 a 
                 a-a-a 
                 a 
                 a-a-a 
                 a 
                 8 
               
             
          
           
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                   
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
             
          
           
               
                 c-b 
                 b-c-c 
                 b-b 
                 c 
                 c-b 
                 b-c-c 
                 b-b 
                 c 
                 12 
               
             
          
           
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                   
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                   
               
             
          
         
       
     
     
       
         
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
           
               
                   
               
             
             
               
                 32 point transform 
                 Sign Changes 
               
               
                   
               
             
          
           
               
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 0 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
             
          
           
               
                 b 
                 c-c-b-b-c 
                 c 
                 b 
                 b 
                 c-c-b-b-c 
                 c 
                 b 
                 8 
               
             
          
           
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                   
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
             
          
           
               
                 a-a-a 
                 a 
                 a-a-a 
                 a 
                 a-a-a 
                 a 
                 a-a-a 
                 a 
                 16 
               
             
          
           
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                   
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
             
          
           
               
                 c-b 
                 b-c-c 
                 b-b 
                 c 
                 c-b 
                 b-c-c 
                 b-b 
                 c 
                 24 
               
             
          
           
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                   
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                   
               
             
          
           
               
                 32 point transform 
                 Sign Changes 
               
               
                   
               
             
          
           
               
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 a 
                 0 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
             
          
           
               
                 b 
                 c-c-b-b-c 
                 c 
                 b 
                 b 
                 c-c-b-b-c 
                 c 
                 b 
                 8 
               
             
          
           
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                   
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
             
          
           
               
                 a-a-a 
                 a 
                 a-a-a 
                 a 
                 a-a-a 
                 a 
                 a-a-a 
                 a 
                 16 
               
             
          
           
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                   
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
             
          
           
               
                 c-b 
                 b-c-c 
                 b-b 
                 c 
                 c-b 
                 b-c-c 
                 b-b 
                 c 
                 24 
               
             
          
           
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                   
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
                 x 
               
               
                   
               
             
          
         
       
     
     In the transforms, each “x” is a number, and the different x&#39;s may be different numbers. The x&#39;s are introduced to better emphasize the placement and structure of the vectors in the larger transforms as they relate to the 4 point transform discussed above. For an 8 point DCT the x&#39;s are numbers with 4 different absolute values(also recognized as 8 signed values). Other 8 point transforms may have the same property as the 8 point transform mentioned above where the 8 signed values are ±12, ±10, ±6, ±3. Similarly for a 16 point DCT the x&#39;s are numbers with 8 different absolute values, and for a 32 point DCT the x&#39;s are numbers with 16 different absolute values. 
     Example matrices with specific values for “x&#39;s” are provided below. These examples are provided to provide specific examples, and not intended to limit the disclosure in any way. 
     Example 4 Point Transform Basis Vectors 
     
         
         32 32 32 32 
         41 19−19−41 
         32−32−32 32 
         19−41 41−19
 
Example 8 Point Transform Basis Vectors
 
         32 32 32 32 32 32 32 32 
         44 38 25 9 −9−25−38−44 
         41 19−19−41−41−19 19 41 
         38 −9−44−25 25 44 9−38 
         32−32−32 32 32−32−32 32 
         25−44 9 38−38 −9 44−25 
         19−41 41−19−19 41−41 19 
         9−25 38−44 44−38 25 −9
 
Example 16 Point Transform Basis Vectors
 
         32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 
         44 44 39 35 30 22 13 5 −5−13−22−30−35−39−44−44 
         44 38 25 9 −9−25−38−44−44−38−25 −9 9 25 38 44 
         44 30 5−22−39−44−35−13 13 35 44 39 22 −5−30−44 
         41 19−19−41−41−19 19 41 41 19−19−41−41−19 19 41 
         39 5−35−44−13 30 44 22−22−44−30 13 44 35 −5−39 
         38 −9−44−25 25 44 9−38−38 9 44 25−25−44 −9 38 
         35−22−44 5 44 13−39−30 30 39−13−44 −5 44 22−35 
         32−32−32 32 32−32−32 32 32−32−32 32 32−32−32 32 
         30−39−13 44 −5−44 22 35−35−22 44 5−44 13 39−30 
         25−44 9 38−38 −9 44−25−25 44 −9−38 38 9−44 25 
         22−44 30 13−44 35 5−39 39 −5−35 44−13−30 44−22 
         19−41 41−19−19 41−41 19 19−41 41−19−19 41−41 19 
         13−35 44−39 22 5−30 44−44 30 −5−22 39−44 35−13 
         9−25 38−44 44−38 25 −9 −9 25−38 44−44 38−25 9 
         5−13 22−30 35−39 44−44 44−44 39−35 30−22 13 −5
 
Example 32 Point Transform Basis Vectors
 
         32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 
         46 46 43 42 41 38 36 33 30 28 23 20 15 11 8 3 −3 −8−11−15−20−23−28−30−33−36−38−41−42−43−46−46 
         44 44 39 35 30 22 13 5 −5−13−22−30−35−39−44−44−44−44−39−35−30−22−13 −5 5 13 22 30 35 39 44 44 
         46 41 33 23 11 −3−15−28−36−42−46−43−38−30−20 −8 8 20 30 38 43 46 42 36 28 15 3−11−23−33−41−46 
         44 38 25 9 −9−25−38−44−44−38−25 −9 9 25 38 44 44 38 25 9 −9−25−38−44−44−38−25 −9 9 25 38 44 
         43 33 15 −8−28−41−46−38−23 −3 20 36 46 42 30 11−11−30−42−46−36−20 3 23 38 46 41 28 8−15−33−43 
         44 30 5−22−39−44−35−13 13 35 44 39 22 −5−30−44−44−30 −5 22 39 44 35 13−13−35−44−39−22 5 30 44 
         42 23 −8−33−46−36−11 20 41 43 28 −3−30−46−38−15 15 38 46 30 3−28−43−41−20 11 36 46 33 8−23−42 
         41 19−19−41−41−19 19 41 41 19−19−41−41−19 19 41 41 19−19−41−41−19 19 41 41 19−19−41−41−19 19 41 
         41 11−28−46−30 8 38 42 15−23−46−33 3 36 43 20−20−43−36 −3 33 46 23−15−42−38 −8 30 46 28−11−41 
         39 5−35−44−13 30 44 22−22−44−30 13 44 35 −5−39−39 −5 35 44 13−30−44−22 22 44 30−13−44−35 5 39 
         38 −3−41−36 8 42 33−11−43−30 15 46 28−20−46−23 23 46 20−28−46−15 30 43 11−33−42 −8 36 41 3−38 
         38 −9−44−25 25 44 9−38−38 9 44 25−25−44 −9 38 38 −9−44−25 25 44 9−38−38 9 44 25−25−44 −9 38 
         36−15−46−11 38 33−20−46 −8 41 30−23−43 −3 42 28−28−42 3 43 23−30−41 8 46 20−33−38 11 46 15−36 
         35−22−44 5 44 13−39−30 30 39−13−44 −5 44 22−35−35 22 44 −5−44−13 39 30−30−39 13 44 5−44−22 35 
         33−28−38 20 42−11−46 3 46 8−43−15 41 23−36−30 30 36−23−41 15 43 −8−46 −3 46 11−42−20 38 28−33 
         32−32−32 32 32−32−32 32 32−32−32 32 32−32−32 32 32−32−32 32 32−32−32 32 32−32−32 32 32−32−32 32 
         30−36−23 41 15−43 −8 46 −3−46 11 42−20−38 28 33−33−28 38 20−42−11 46 3−46 8 43−15−41 23 36−30 
         30−39−13 44 −5−44 22 35−35−22 44 5−44 13 39−30−30 39 13−44 5 44−22−35 35 22−44 −5 44−13−39 30 
         28−42 −3 43−23−30 41 8−46 20 33−38−11 46−15−36 36 15−46 11 38−33−20 46 −8−41 30 23−43 3 42−28 
         25−44 9 38−38 −9 44−25−25 44 −9−38 38 9−44 25 25−44 9 38−38 −9 44−25−25 44 −9−38 38 9−44 25 
         23−46 20 28−46 15 30−43 11 33−42 8 36−41 3 38−38 −3 41−36 −8 42−33−11 43−30−15 46−28−20 46−23 
         22−44 30 13−44 35 5−39 39 −5−35 44−13−30 44−22−22 44−30−13 44−35 −5 39−39 5 35−44 13 30−44 22 
         20−43 36 −3−33 46−23−15 42−38 8 30−46 28 11−41 41−11−28 46−30 −8 38−42 15 23−46 33 3−36 43−20 
         19−41 41−19−19 41−41 19 19−41 41−19−19 41−41 19 19−41 41−19−19 41−41 19 19−41 41−19−19 41−41 19 
         15−38 46−30 3 28−43 41−20−11 36−46 33 −8−23 42−42 23 8−33 46−36 11 20−41 43−28 −3 30−46 38−15 
         13−35 44−39 22 5−30 44−44 30 −5−22 39−44 35−13−13 35−44 39−22 −5 30−44 44−30 5 22−39 44−35 13 
         11−30 42−46 36−20 −3 23−38 46−41 28 −8−15 33−43 43−33 15 8−28 41−46 38−23 3 20−36 46−42 30−11 
         9−25 38−44 44−38 25 −9 −9 25−38 44−44 38−25 9 9−25 38−44 44−38 25 −9 −9 25−38 44−44 38−25 9 
         8−20 30−38 43−46 42−36 28−15 3 11−23 33−41 46−46 41−33 23−11 −3 15−28 36−42 46−43 38−30 20 −8 
         5−13 22−30 35−39 44−44 44−44 39−35 30−22 13 −5 −5 13−22 30−35 39−44 44−44 44−39 35−30 22−13 5 
         3 −8 11−15 20−23 28−30 33−36 38−41 42−43 46−46 46−46 43−42 41−38 36−33 30−28 23−20 15−11 8 −3 
       
    
     It should be noted that each of these example transform matrices can be scaled by an integer multiple and once scaled, the scaled transform matrix may also be used as a transform matrix. As an example, if all of the numbers in one of the transform matrix are multiplied by 2, then the resultant matrix is may be used as a transform matrix as well. In one example, after a, b, c have been divided by a largest integer number N that result in three new integers a′=a/N, b′=b/N, c′=c/N, each of a′, b′ and c′ are represented by not more than 8 bits. 
     Now the discussion will be directed to the DC basis vector. The first vector (a a a a) is usually referred to as the DC vector since it describes a constant value of the signal. For computational reasons it is preferable, but not essential, that a is of the form a=2 n . This means that some of the multiplications can be performed by shifts—which is a simple computational operation often accomplished with a shift register or a CPU operation. The value “n” in the present application is 5 or 6 since that value “n” would correspond to a value of “a” being equal to 32 or 64. Thus, “n” is a result-effective-variable because by keeping the value reasonably low, all the numbers can be represented by a small number of bits. When a=32 each of the numbers a, b, c may be represented in 7 bits (see below). When a=64 all the numbers a, b, c may be represented in 8 bits, or 1 Byte (see below). 
     Equal Norm of the Basis Vectors 
     It is preferable, although not essential, that the 4 basis vectors have the same norm. This is fulfilled if b 2 +c 2 =a 2 +a 2 . Since integer numbers are used, it is difficult to fulfill this equation completely. The goal is ensure that the norms are close enough in practical use, for example so that the basis vectors may be treated as if they have the same norm in the quantization/inverse_quantization process. Moreover, if |b 2 +c 2 −(a 2 +a 2 )|/(a 2 +a 2 )&lt;0.003 the loss of coding efficiency due to slightly different norms of the vectors is insignificant. While the threshold of 0.003 is provided as an example, there is some tolerance about this range as it applies to practical application and human perception. For example the threshold may be as low as 0.001 and as high as 0.01, where the coding inefficiency becomes more cumbersome at the higher end. Nevertheless, if higher coding inefficiency may be overcome by computational complexity, the threshold may be even higher such as 0.099, for example. 
     The discussion now is directed to the orthogonal basis vectors. With the definition above, the 4 basis vectors are automatically orthogonal, which means that the four basis vectors respective have inner products that are 0. 
     Regarding the shape of the odd vectors, the shape of the odd vectors is defined by the numbers b and c. For the DCT the ratio between b and c is:
 
 b/c= cos(22.5 deg)/cos(67.5 deg)=1+sqrt(2)≈2.4142
 
     The DCT is a special case of the Karhunen-Loeve Transform (KLT) when the correlation (ρ) between the pixels to be transformed approaches 1. For image pixel data, ρ will typically be in the range (0.6-0.95), and so the corresponding ratio between b and c is in the range 2.08 to 2.37. Hence b/c should be in the range of 2.08 to 2.37 to define a best possible transform. 
     Now turning to a discussion on the practical limitations to be fulfilled with a=32 or 64. The maximum relative difference in norm may be expressed as |b 2 +c 2 −(a 2 +a 2 )|/(a 2 +a 2 ). It should be less than the practical limit discussed above of 0.003. The basis vector shape, as discussed above, is defined by the ratio b/c and should be in the range of 2.08 to 2.37 as discussed above, or practically 2.1 through 2.4. 
     Under these constraints, the present inventor recognized that the values of b and c that comply with these requirements when a=32 are limited. In particular, one set of numbers, namely b=41 and c=19 are defined. Therefore, all the numbers +/−32, +/−41 and +/−19 may be represented in seven bits and thus may be referred to a 7 bit precision. 
     Different transform sizes like 4 point, 8 point, 16 point and 32 point may have different bit precisions. In an embedded transform structure, it is typical that all transform sizes have the same bit precision. 
     If a=64, the limitations result in 2 possible sets of numbers b and c where [2.1&lt;b/c&lt;2.4]: b=82, c=38 and b=83, c=36. All the numbers ±64, ±83, ±82, ±38, ±36 fit into 8 bits (1 Byte). Hence this is referred to as 8 bit precision. 
     In image and video coding/decoding it is common to use two dimensional transforms. This is usually achieved by performing the transformation/inverse_transformation in 2 steps. Assuming there is a block of data called data with size N×M values to be transformed/inverse_transformed, the procedure below indicates the steps for performing a two dimensional transform, starting with the horizontal transform. 
     Step 1: Horizontal Transform 
     Perform a one dimensional N point transform of all M lines in the N×M data block. The output of each transform process is placed in a new N×M block called transform1. 
     Step 2: Vertical Transform 
     Perform a one dimensional M point transform of all N columns in the N×M transform1 block. The output of each transform process is placed in a new N×M block called transform2. 
     transform2 is then the two dimensional transform of data. 
     N and M may be Equal or Different. As Examples: 
     
         
         When N=4 and M=4 it is called a 4×4 transform. 
         When N=8 and M=8 it is called a 8×8 transform. 
         When N=4 and M=8 it is called a 4×8 transform.
 
etc.
 
       
    
     The exact formulas to be used for both one and two dimensional transformation and inverse transformation have the same structure as the corresponding formulas for DCT, as recognized in the art. 
       FIG. 3  illustrates a process flow for performing the video coding or decoding in a schematic representation. A first block of residual pixel values can be subjected to a transformation by a transform matrix formed by a number of basis vectors, to generate a corresponding second block of residual pixel values of a moving picture. For the transformation, a transform matrix is used, as described above, for any of the sizes discussed above. 
       FIG. 4  illustrates a computer system  1201  upon which the method of video coding or decoding of the present invention may be implemented. For example, the computer system  1201  may be used to implement a video conferencing endpoint that employs a video encoder and decoder that implement the teachings of the present disclosure. The computer system  1201  includes a bus  1202  or other communication mechanism for communicating information, and a processor  1203  coupled with the bus  1202  for processing the information. The computer system  1201  also includes a main memory  1204 , such as a random access memory (RAM) or other dynamic storage device (e.g., dynamic RAM (DRAM), static RAM (SRAM), and synchronous DRAM (SDRAM)), coupled to the bus  1202  for storing information and instructions to be executed by processor  1203 . In addition, the main memory  1204  may be used for storing temporary variables or other intermediate information during the execution of instructions by the processor  1203  for the coding or encoding. The computer system  1201  further includes a read only memory (ROM)  1205  or other static storage device (e.g., programmable ROM (PROM), erasable PROM (EPROM), and electrically erasable PROM (EEPROM)) coupled to the bus  1202  for storing static information and instructions for the processor  1203 . The transformation can be performed on the processor  1203  by using the main memory  1204  for data storage during processing. 
     The computer system  1201  also includes a disk controller  1206  coupled to the bus  1202  to control one or more storage devices for storing information and instructions, such as a magnetic hard disk  1207 , and a removable media drive  1208  (e.g., floppy disk drive, read-only compact disc drive, read/write compact disc drive, compact disc jukebox, tape drive, and removable magneto-optical drive). The storage devices may be added to the computer system  1201  using an appropriate device interface (e.g., small computer system interface (SCSI), integrated device electronics (IDE), enhanced-IDE (E-IDE), direct memory access (DMA), or ultra-DMA). The storage devices can be used to store results of the coding/decoding or data that has to be transformed, and to store the basic vectors of the transform matrix. 
     The computer system  1201  may also include special purpose logic devices (e.g., application specific integrated circuits (ASICs)) or configurable logic devices (e.g., simple programmable logic devices (SPLDs), complex programmable logic devices (CPLDs), and field programmable gate arrays (FPGAs)). With such special purpose logic devices, the transformation with the transform matrix can be hardware-coded to speed up the encoding or coding of the moving pictures, and to reduce the processing required on processor  1203 . 
     The computer system  1201  may also include a display controller  1209  coupled to the bus  1202  to control a display  1210 , such as a cathode ray tube (CRT), for displaying information to a computer user. Results of the coding or decoding of a moving picture can be displayed on display  1210 . The computer system includes input devices, such as a keyboard  1211  and a pointing device  1212 , for interacting with a computer user and providing information to the processor  1203 . The pointing device  1212 , for example, may be a mouse, a trackball, or a pointing stick for communicating direction information and command selections to the processor  1203  and for controlling cursor movement on the display  1210 . In addition, a printer may provide printed listings of data stored and/or generated by the computer system  1201 . 
     The computer system  1201  performs a portion or all of the processing steps of the transformation in response to the processor  1203  executing one or more sequences of one or more instructions contained in a memory, such as the main memory  1204 . Such instructions may be read into the main memory  1204  from another computer readable medium, such as a hard disk  1207  or a removable media drive  1208 . One or more processors in a multi-processing arrangement may also be employed to execute the sequences of instructions contained in main memory  1204 . In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions, as described above with respect to the special purpose logic devices. Thus, embodiments are not limited to any specific combination of hardware circuitry and software. 
     As stated above, the computer system  1201  includes at least one computer readable medium or memory for holding instructions programmed according to the teachings of the invention and for containing data structures, tables, records, or other data described herein. For example the basic vectors and moving pictures that have to be coded or decoded can be stored on such computer readable media. Examples of computer readable media are compact discs, hard disks, floppy disks, tape, magneto-optical disks, PROMs (EPROM, EEPROM, flash EPROM), DRAM, SRAM, SDRAM, or any other magnetic medium, compact discs (e.g., CD-ROM), or any other optical medium, punch cards, paper tape, or other physical medium with patterns of holes, a carrier wave (described below), or any other medium from which a computer can read. 
     Stored on any one or on a combination of computer readable media, the present invention includes software for controlling the computer system  1201 , for driving a device or devices for implementing the method of video coding or decoding, and for enabling the computer system  1201  to interact with a human user (e.g., print production personnel). Such software may include, but is not limited to, device drivers, operating systems, development tools, and applications software. Such computer readable media further includes the computer program product of the present invention for performing all or a portion (if processing is distributed) of the processing performed in implementing the invention. 
     The computer code devices of the present invention may be any interpretable or executable code mechanism, including but not limited to scripts, interpretable programs, dynamic link libraries (DLLs), Java classes, and complete executable programs. Moreover, parts of the processing of the present invention may be distributed for better performance, reliability, and/or cost. 
     The term “computer readable medium” as used herein refers to any medium that participates in providing instructions to the processor  1203  for execution. A computer readable medium may take many forms, including but not limited to, non-volatile media, volatile media, and transmission media. Non-volatile media includes, for example, optical, magnetic disks, and magneto-optical disks, such as the hard disk  1207  or the removable media drive  1208 . Volatile media includes dynamic memory, such as the main memory  1204 . Transmission media includes coaxial cables, copper wire and fiber optics, including the wires that make up the bus  1202 . Transmission media also may also take the form of acoustic or light waves, such as those generated during radio wave and infrared data communications. 
     Various forms of computer readable media may be involved in carrying out one or more sequences of one or more instructions to processor  1203  for execution. For example, the instructions may initially be carried on a magnetic disk of a remote computer. The remote computer can load the instructions for implementing all or a portion of the method of video coding or decoding remotely into a dynamic memory and send the instructions over a telephone line using a modem. A modem local to the computer system  1201  may receive the data on the telephone line and use an infrared transmitter to convert the data to an infrared signal. An infrared detector coupled to the bus  1202  can receive the data carried in the infrared signal and place the data on the bus  1202 . The bus  1202  carries the data to the main memory  1204 , from which the processor  1203  retrieves and executes the instructions. The instructions received by the main memory  1204  may optionally be stored on storage device  1207  or  1208  either before or after execution by processor  1203 . 
     The computer system  1201  also includes a communication interface  1213  coupled to the bus  1202 . The communication interface  1213  provides a two-way data communication coupling to a network link  1214  that is connected to, for example, a local area network (LAN)  1215 , or to another communications network  1216  such as the Internet. For example, the communication interface  1213  may be a network interface card to attach to any packet switched LAN. As another example, the communication interface  1213  may be an asymmetrical digital subscriber line (ADSL) card, an integrated services digital network (ISDN) card or a modem to provide a data communication connection to a corresponding type of communications line. Wireless links may also be implemented. In any such implementation, the communication interface  1213  sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information. For example, the communication interface  1213  can be used to output coded moving pictures resulting from the method of video coding, or to input encoded moving pictures to process them with the method for decoding. 
     The network link  1214  typically provides data communication through one or more networks to other data devices. For example, the network link  1214  may provide a connection to another computer through a local network  1215  (e.g., a LAN) or through equipment operated by a service provider, which provides communication services through a communications network  1216 . It is possible to deliver coded video data that was coded by the method of the present invention to external devices, in an MPEG* or H.26* standard, for example a mobile device  1217 , or other terminal devices connected to network  1216 . Due to the data reduction by encoding, the required bandwidth could be reduced. The local network  1214  and the communications network  1216  use, for example, electrical, electromagnetic, or optical signals that carry digital data streams, and the associated physical layer (e.g., CAT 5 cable, coaxial cable, optical fiber, etc). The signals through the various networks and the signals on the network link  1214  and through the communication interface  1213 , which carry the digital data to and from the computer system  1201  maybe implemented in baseband signals, or carrier wave based signals. The baseband signals convey the digital data as unmodulated electrical pulses that are descriptive of a stream of digital data bits, where the term “bits” is to be construed broadly to mean symbol, where each symbol conveys at least one or more information bits. The digital data may also be used to modulate a carrier wave, such as with amplitude, phase and/or frequency shift keyed signals that are propagated over a conductive media, or transmitted as electromagnetic waves through a propagation medium. Thus, the digital data may be sent as unmodulated baseband data through a “wired” communication channel and/or sent within a predetermined frequency band, different than baseband, by modulating a carrier wave. The computer system  1201  can transmit and receive data, including program code, through the network(s)  1215  and  1216 , the network link  1214  and the communication interface  1213 . Moreover, the network link  1214  may provide a connection through a LAN  1215  to a mobile device  1217  such as a personal digital assistant (PDA) laptop computer, or cellular telephone. 
     The present invention is useful to design integer transforms for image and video coding with improved coding efficiency and lower complexity compared to previously used integer transforms. 
     Although aspects of the invention have been described with reference to particular embodiments, it is to be understood that these embodiments are merely illustrative of the principles and applications of the present invention. It is therefore to be understood that numerous modifications may be made to the illustrative embodiment and that other arrangements may be devised without departing from the spirit and scope of the present invention as defined by the appended claims.