The Discrete Cosine Transform (DCT) is widely used in image and video coding. An “n”-point DCT can be expressed as in Equation (1):
                                          X            ⁡                          [              k              ]                                =                                                    α                ⁡                                  [                  k                  ]                                            ⁢                                                ∑                                      n                    =                    0                                                        N                    -                    1                                                  ⁢                                                                  ⁢                                                      x                    ⁡                                          [                      n                      ]                                                        ⁢                                      cos                    ⁡                                          (                                                                                                    π                            ⁡                                                          (                                                                                                2                                  ⁢                                  n                                                                +                                1                                                            )                                                                                ⁢                          k                                                                          2                          ⁢                          N                                                                    )                                                        ⁢                  k                                                      =                                          0                ⁢                                                                  ⁢                …                ⁢                                                                  ⁢                N                            -              1                                      ⁢                                  ⁢                              where            ⁢                                                  ⁢                          α              ⁡                              [                k                ]                                              =                      {                                                                                                                              1                        N                                                                                                                        k                      =                      0                                                                                                                                                          2                        N                                                                                                                                                k                        =                        1                                            ,                                              2                        ⁢                                                                                                  ⁢                        …                                            ⁢                                                                                          ,                                              N                        -                        1                                                                                                        ,                                                          (        1        )            and where x[n], n=0, . . . , N−1 represents the input signal and X[k], k=0, . . . , N−1 represents the output DCT coefficient. Theoretically, for a signal that has strong local correlation, DCT approximates the optimal linear transform for de-correlation. In image coding, the image is usually divided into small blocks. A two-dimensional DCT transform, where a one-dimensional transform is performed horizontally and then another one-dimensional transform is performed vertically, is applied to de-correlate the signal within an image block. For example, in JPEG image coding schemata, the image is divided into 8×8 blocks and 8×8 DCT is applied on each block. This is also the case for intra-frame coding in MPEG-1/2/4 and H.261/H.263. In H.264, 4×4 DCT is used instead. There are many fast algorithms for 4×4 or 8×8 DCT.
Although conventional DCT works satisfactorily in image/video coding, it is applied indiscriminately in vertical and horizontal directions regardless of the actual visual characteristics of the image. Most images, however, have a “grain” that does not match the conventional vertical and horizontal DCT directions. That is, images and the blocks constituting an image typically have a directional property resulting from some visual or even non-visual uniformity along one or more axes of the image or block. Conventional DCT does not consider this directional property of images, which is very common in natural images, satellite images, and computer generated images, etc. The directional property is especially evident for visual edges and textures in images.
For those image regions which are not uniform horizontally or vertically and that show a strong uniform directional property along another axis, it is difficult to use a conventional DCT operation to de-correlate them well. To improve performance, one-dimensional DCT could be applied along the direction for which the image region is uniform, but it is not straightforward to perform DCT along an arbitrary direction.
USPTO Backgrounds
USPTO Backgrounds