Cost-optimal reversible integer wavelet constructions: minimal expansion factors, tiling geometry of rounded lifting, and cost-optimal lifting factorizations

The 1998 paper of Calderbank, Daubechies, Sweldens, and Yeo gave two general ways to turn a finite wavelet filter bank into a transform that maps integers to integers and is exactly invertible on the integer lattice: (i) a precoding/expansion construction with uniform or per-channel expansion factors, and (ii) executing the lifting factorization of the filter bank with reversible rounding. The paper left the quantitative cost of these constructions without a theory. Later literature extensively developed the one direction the authors explicitly flagged — spatially adaptive integer wavelet transforms — and settled the algebraic uniqueness question for lifting factorizations, but it did not settle the remaining cost questions. The open core is: for arbitrary finite perfect-reconstruction filter banks, (a) determine provably minimal expansion factors and fundamental regions satisfying the paper's nonoverlap conditions, (b) characterize the geometry of the tiling regions induced by rounded lifting steps and its effect on bit growth and coding efficiency, (c) characterize lifting factorizations that minimize implementation cost (number of steps, final scaling, intermediate dynamic range), and (d) delimit when modular-arithmetic implementations can be combined with or outperform lifting-based ones. These components share one objective: a quantitative theory of the dynamic-range cost of reversible integer wavelet transforms, replacing the ad hoc constructions and examples of the source paper.

Background

Digital images and many other signals are integer-valued, and lossless (reversible) compression requires every processing step to be invertible on integer data. A wavelet or subband decomposition applies two-channel perfect-reconstruction filter banks — pairs of a low-pass filter $h$ and a high-pass filter $g$ with real (non-integer) coefficients whose outputs can be recombined to recover the input exactly — followed by decimation (keeping only every other sample of each filtered channel), so even integer input produces non-integer output, and rounding naively destroys invertibility. The paper 'Wavelet Transforms That Map Integers to Integers' (Calderbank, Daubechies, Sweldens, Yeo, Applied and Computational Harmonic Analysis, 1998) solved the existence problem by two constructions. First, generalizing the Laroia–Tretter–Farvardin precoding scheme originally devised for intersymbol-interference channels (channels whose dispersive response smears one transmitted symbol into its neighbors), it perturbs the input by fractional-part corrections so that the linear filter outputs land on integers; to make this possible for general filters one first expands the dynamic range by a factor $\alpha$ (uniformly, or by separate factors $\alpha_L,\alpha_H$ for the low- and high-pass polyphase components — the polyphase components being the even- and odd-phase subsequences of each filter), and invertibility hinges on translated fundamental regions $\Lambda$ and $\Gamma$ of the subband operator — sets that tile the input space under integer translations, one per subband — satisfying the paper's nonoverlap conditions (2.10)/(2.11), which state that the translates of these regions by integer vectors must not overlap. For example, with the Haar filters one can take $\alpha_L=1/\sqrt 2$, $\alpha_H=\sqrt 2$ (so $\alpha_L\alpha_H=1$) and recover the classical integer S transform (the lossless integer Haar transform, the earliest reversible integer wavelet). Second, the paper factors any finite two-channel perfect-reconstruction filter bank into lifting steps: split the signal into even and odd samples (the 'lazy wavelet'), alternate dual (predict) steps $d^{(i)}=d^{(i-1)}-\sum_k p^{(i)}_k s^{(i-1)}_{\cdot-k}$ and primal (update) steps $s^{(i)}=s^{(i-1)}-\sum_k u^{(i)}_k d^{(i)}_{\cdot-k}$, and finish with a scalar scaling $K$; rounding each step with $\lfloor x+1/2\rfloor$ is exactly reversible, which produced concrete integer versions of the S, TS, and S+P transforms (progressively richer reversible integer wavelets built by adding prediction and update steps) used with a Said–Pearlman multiresolution entropy coder (a well-known embedded bit-plane coder for image compression) for lossless image compression. The paper's evaluation found no single transform uniformly best, and this construction family was subsequently standardized: reversible whole-sample-symmetric lifting specifications appear in Parts 1 and 2 of the ISO/IEC JPEG 2000 still image coding standard. The factorization into lifting steps is not unique (one may aim for $K$ near 1, or add three steps to force $K=1$), and the rounded lifting map partitions the input space into regions $\Sigma_{\mathbf n}$ indexed by integer output vectors $\mathbf n$, which the paper notes are complex and not Cartesian products. Two cost objectives recur in the paper's design discussion: minimizing the low-pass expansion factor, because the low-pass channel is iterated in a multiresolution decomposition and its growth compounds at each level, and minimizing the product $\alpha_L\alpha_H$ for separable two-dimensional transforms, because it governs overall bit growth. What the paper provides are constructions and worked examples; what it does not provide is any optimality theory: how small the expansion can be, what the tiling regions look like, which factorization costs least, and how these costs compare with modular-arithmetic reversible schemes — alternative integer constructions that compute everything modulo a fixed word size, so that no bit growth occurs but values wrap around, which can produce large-magnitude signed errors after unwrapping. Those are the questions left open.

Problem Statement

The problem, in the generality left open by Calderbank, Daubechies, Sweldens, and Yeo (1998), is to replace the example-driven constructions of that paper with a quantitative theory of the dynamic-range cost of integer-to-integer wavelet transforms, for arbitrary finite two-channel perfect-reconstruction filter banks. Its linked components are: (1) Expansion minimality. For the precoding/expansion construction, determine — with proof, not examples — the smallest uniform expansion factor $\alpha$ and the best nonuniform (diagonal $\alpha_L,\alpha_H$) expansion under the paper's stated objectives (minimizing low-pass expansion for iterated decomposition, or the product $\alpha_L\alpha_H$ for two-dimensional decomposition), and construct fundamental regions $\Lambda$ and $\Gamma$ that satisfy the nonoverlap conditions (2.10)/(2.11); no general algorithm with a provable optimality guarantee is known. (2) Tiling geometry. Characterize the geometric structure of the regions $\Sigma_{\mathbf n}$ of the input space that the lifting-and-truncation construction (executing each lifting step with reversible rounding of the form $\lfloor x+1/2\rfloor$) maps to each integer output vector $\mathbf n$ — their measure, adjacency, and departure from Cartesian-product structure — and establish how this geometry governs dynamic-range growth and coding efficiency, including whether some choice of lifting factorization produces simpler tiles. (3) Cost-optimal lifting factorization. Since the lifting factorization of a given filter bank is not unique (with the options of choosing the final scaling $K$ near 1 or adding three steps to make $K=1$), characterize the factorization(s) that minimize implementation cost, assessed separately for each of the number of lifting steps, the final scaling $K$, and the intermediate dynamic-range growth — possibly within the algebraic equivalence classes fixed by group lifting structures (Brislawn's framework organizing lifting factorizations into equivalence classes under reversible group actions). (4) Comparative cost of modular arithmetic. Determine the conditions under which modular-arithmetic reversible schemes (of the kind the source paper cites) can be combined with lifting to avoid bit growth without wraparound drawbacks (values wrapping around the modulus and corrupting the decoded result), and when they help or hurt lossless compression of natural images. All four components serve the single objective of bounding and optimizing the bit-depth cost of making a wavelet transform reversible on integers; the source paper's separate suggestion of spatially adaptive integer wavelet design was subsequently developed extensively and is not part of this open core.

References

1. A. R. Calderbank, Ingrid Daubechies, Wim Sweldens, Boon-Lock Yeo, 'Wavelet Transforms That Map Integers to Integers', Applied and Computational Harmonic Analysis 5(3):332–369 (1998). DOI: 10.1006/acha.1997.0238, https://doi.org/10.1006/acha.1997.0238
2. A. R. Calderbank, Ingrid Daubechies, Wim Sweldens, Boon-Lock Yeo, 'Lossless image compression using integer to integer wavelet transforms', Proceedings of International Conference on Image Processing (ICIP '97), vol. 1, pp. 596–599 (1997). DOI: 10.1109/ICIP.1997.647983, https://doi.org/10.1109/ICIP.1997.647983
3. R. L. Claypoole, Geoffrey M. Davis, W. Sweldens, R. G. Baraniuk, 'Nonlinear wavelet transforms for image coding via lifting', IEEE Transactions on Image Processing 12(12):1449–1459 (2003). DOI: 10.1109/TIP.2003.817237, https://doi.org/10.1109/TIP.2003.817237
4. A. T. Deever, S. S. Hemami, 'Lossless image compression with projection-based and adaptive reversible integer wavelet transforms', IEEE Transactions on Image Processing 12(5):489–499 (2003). DOI: 10.1109/TIP.2003.812374, https://doi.org/10.1109/TIP.2003.812374
5. Chuo-Ling Chang, Bernd Girod, 'Direction-Adaptive Discrete Wavelet Transform for Image Compression', IEEE Transactions on Image Processing 16(5):1289–1302 (2007). DOI: 10.1109/TIP.2007.894242, https://doi.org/10.1109/TIP.2007.894242
6. G. Quellec, M. Lamard, G. Cazuguel, B. Cochener, C. Roux, 'Adaptive Nonseparable Wavelet Transform via Lifting and its Application to Content-Based Image Retrieval', IEEE Transactions on Image Processing 19(1):25–35 (2010). DOI: 10.1109/TIP.2009.2030479, https://doi.org/10.1109/TIP.2009.2030479
7. V. Kitanovski, M. Kseneman, D. Gleich, D. Taskovski, 'Adaptive lifting integer wavelet transform for lossless image compression', 2008 15th International Conference on Systems, Signals and Image Processing, pp. 105–108 (2008). DOI: 10.1109/IWSSIP.2008.4604378, https://doi.org/10.1109/IWSSIP.2008.4604378
8. Dong Chen, Yanjuan Li, Haiying Zhang, Wenpeng Gao, 'Invertible update-then-predict integer lifting wavelet for lossless image compression', EURASIP Journal on Advances in Signal Processing 2017(1) (2017). DOI: 10.1186/s13634-016-0443-y, https://doi.org/10.1186/s13634-016-0443-y
9. Christopher M. Brislawn, 'Group Lifting Structures for Multirate Filter Banks I: Uniqueness of Lifting Factorizations', IEEE Transactions on Signal Processing 58(4):2068–2077 (2010). DOI: 10.1109/TSP.2009.2039816, https://doi.org/10.1109/TSP.2009.2039816
10. Pengwei Hao, Qingyun Shi, 'Matrix factorizations for reversible integer mapping', IEEE Transactions on Signal Processing 49(10):2314–2324 (2001). DOI: 10.1109/78.950787, https://doi.org/10.1109/78.950787
11. Tony Lin, Pengwei Hao, Shufang Xu, 'Matrix factorizations for reversible integer implementation of orthonormal M-band wavelet transforms', Signal Processing 86(8):2085–2093 (2006). DOI: 10.1016/j.sigpro.2005.10.015, https://doi.org/10.1016/j.sigpro.2005.10.015
12. Yiyuan She, Pengwei Hao, Yakup Paker, 'Matrix Factorizations for Parallel Integer Transformation', IEEE Transactions on Signal Processing 54(12):4675–4684 (2006). DOI: 10.1109/TSP.2006.881227, https://doi.org/10.1109/TSP.2006.881227
13. Dan Li, Jiashu Zhang, Bormin Huang, 'Optimal Integer-to-Integer Reversible Mapping of General Linear Transforms via Diagonal Scaling and Generalized Lifting', SSRN preprint 6626950, unrefereed (2026). DOI: 10.2139/ssrn.6626950, https://doi.org/10.2139/ssrn.6626950
14. S. Srinivasan, 'Modulo transforms — an alternative to lifting', IEEE Transactions on Signal Processing 54(5):1864–1874 (2006). DOI: 10.1109/TSP.2006.872548, https://doi.org/10.1109/TSP.2006.872548
15. M. D. Adams, F. Kossentini, 'On the relationship between the overlapping rounding transform and lifting frameworks for reversible subband transforms', IEEE Transactions on Signal Processing 48(1):261–266 (2000). DOI: 10.1109/78.815499, https://doi.org/10.1109/78.815499
16. Tanja Karp, 'Fixed Wordsize Implementation of Lifting Schemes', EURASIP Journal on Advances in Signal Processing 2007(1), article 13754 (2007; Crossref online date 2006-11-12, volume year 2007). DOI: 10.1155/2007/13754, https://doi.org/10.1155/2007/13754
17. A. Said, W. A. Pearlman, 'An image multiresolution representation for lossless and lossy compression', IEEE Transactions on Image Processing 5(9):1303–1310 (1996). DOI: 10.1109/83.535842, https://doi.org/10.1109/83.535842
18. R. Laroia, S. A. Tretter, N. Farvardin, 'A simple and effective precoding scheme for noise whitening on intersymbol interference channels', IEEE Transactions on Communications 41(10):1460–1463 (1993). DOI: 10.1109/26.237880, https://doi.org/10.1109/26.237880