Modulo Transforms – an Alternative to Lifting

This paper introduces a new paradigm for the construction of reversible transforms that map integers to integers. Transform matrices with integer entries are first considered, and the modulo arithmetic properties of transform coefficients is studied. It is shown that these transform coefficients are redundant in modulo arithmetic. Further, this redundancy can be exploited by quantizing transform coefficients in a manner so as to produce an effective scaled transformation with unit determinant. The concept of critical quantization is introduced and forms the basis of a class of transforms referred to as modulo transforms that are reversible, effectively have rational coefficients and unit determinant. These conditions are necessary for applications such as lossless compression and reversible image rotation. The theory of modulo transforms is examined in depth. Analysis based on modulo arithmetic shows that 2D rotations can be critically quantized, albeit with non-equal bin widths along axes. A construction procedure is derived for realizing a reversible transform with small or unit scaling factors. Further, it is shown that modulo transforms based on certain Pythagorean triples can be scalar quantized to produce a reversible, normalized, scale-free transform matrix. This theory is built on 2D rotations, and extended to larger transforms such as the 4 and 8 point DCT. Modulo transforms and lifting are compared and contrasted in theory, and in experiments. The computational aspects of modulo transforms are also discussed in this paper.