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 modular arithmetic properties of transform coefficients are studied. It is shown that these transform coefficients are redundant in modular arithmetic. Further, this redundancy can be exploited by quantizing transform coefficients critically so as to produce an effective scaled transformation with unit determinant. This forms the basis of a class of transforms referred to as modulo transforms that are reversible and unit determinant, conditions necessary for applications such as lossless compression and reversible image rotation. The theory of modulo transforms is examined in depth. Analysis based on modular arithmetic shows that two-dimensional rotations can be critically quantized, albeit with nonequal bin widths along axes. A construction procedure is derived for realizing a reversible transform with small or unit scaling factors, and a theorem is stated wherein certain Pythagorean triples can be scalar quantized to produce a reversible, normalized, scalefree transform matrix. 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.