The sparse discrete cosine transform with application to image compression

Presented here is a description and analysis of the N-point sparse discrete cosine transform (SDCT), where N is a power of two, which retains all of the properties of the parent DCT such as linearity, energy compaction, and having a fast transform implementation, while allowing arbitrarily-many known zeros, i.e., masked elements, in the input. It has application to image and video compression in that arbitrarily shaped regions may be transformed by the two-dimensional (2D) SDCT with approximately the same resulting compression efficiency as the standard 2D DCT applied to square blocks. The solution is based on a systematic application of symmetry and additive symmetry to the input elements. The four- and eight-point solutions are presented first, with emphasis on development of a set of generating matrices, and finally a general N-point solution is described. The 8×8 SDCT was implemented in VP9 and as expected the transform was found to be perfect and also improved compression efficiency for video objects with a known mask.