Bandelet surface compression: closing the theory-practice gap between the Alpert-based approximation theorem and the implemented wavelet transform, and controlling geometric rather than L2 distortion

Second-generation bandelet bases introduced by Peyré and Mallat compress geometry images and normal maps of 3D surfaces by removing the anisotropic redundancy of an orthogonal wavelet transform along an estimated multiscale geometric flow, with a proved asymptotically optimal distortion-rate bound for $C^2$-geometrically regular functions. However, the proof holds for a variant of the algorithm that replaces the 1D wavelet transform by a 1D Alpert multiwavelet transform, whereas the implemented codec uses standard 1D wavelets; the optimization criterion and the theorem are stated for the $L^2$ norm of the parameterized image, while the distortion that matters geometrically is the parameterization-invariant Hausdorff distance, currently handled only by an ad-hoc local coordinate change and triple bit allocation in the normal direction; and the codec is demonstrated only on spherical geometry images of genus-0 surfaces, although the multi-chart extension needed for arbitrary genus is stated to be possible. The problem is to close these three linked gaps: prove the optimal decay for the discrete standard-wavelet implementation actually used, establish a distortion-rate theory that directly controls the geometric Hausdorff distortion, and extend the bandelet codec to multi-chart geometry images for arbitrary-genus surfaces.

Background

A geometry image [Gu, Gortler, and Hoppe 2002] is a representation of a 3D surface obtained by cutting and parameterizing the surface onto a square domain and resampling it on a regular grid, so the three spatial coordinates become the RGB channels of an ordinary image; the surface is then compressed by an image codec. A normal map is a texture image whose pixels store the surface normal on a regular grid, used to add fine geometric detail to a coarse mesh. Spherical geometry images parameterize genus-0 (closed, sphere-like) surfaces onto a sphere before resampling, which avoids a visible cut seam but cannot represent surfaces of higher genus; multi-chart geometry images [Sander, Wood, Gortler, Snyder, and Hoppe 2003] instead cut the surface into several charts that are packed into one or several square images and can represent arbitrary surfaces, at the price of chart boundaries that a codec must handle. Natural surfaces are piecewise smooth: away from curves such as creases, the geometrically sampled function is $C^2$ (twice continuously differentiable), but its wavelet coefficients near those curves remain large at fine scales, so isotropic transforms code them poorly. A function is called $C^2$-geometrically regular when it is $C^2$ away from a finite set of edge curves that are themselves $C^2$. Bandelets, introduced in first-generation form by Le Pennec and Mallat [Le Pennec and Mallat 2005], are orthonormal bases adapted to such geometric regularity: a multiscale geometric flow, estimated in each dyadic square of a quadtree partition of the image, indicates the direction along which the function is most regular, and the transform is warped along that flow so that 1D regularity is fully exploited. In the second-generation construction of Peyré and Mallat [Peyré and Mallat 2005, surface compression], the bandeletization operates on the coefficients of an orthogonal 2D wavelet transform: wavelet subbands are re-warped, grouped into elongated dyadic bands, and re-decomposed by a 1D transform, with the geometry (segmentation and quantized flow directions) entropy-coded and the whole basis chosen by minimizing a Lagrangian that trades quantized-coefficient distortion against the rate spent on coefficients, segmentation, and geometry. Transform coding is this classical scheme of expanding the signal in an orthonormal basis, quantizing the coefficients, and entropy coding them; for a function class, a rate R code is asymptotically optimal when its distortion decays as fast as the best possible for that class. Alpert multiwavelets [Alpert 1992] are orthonormal piecewise-polynomial bases on intervals, built from several scaling functions per level rather than one, which can be discontinuous at band boundaries; because their approximation properties on elongated bands are easy to control analytically, they are the tool used in the proofs of bandelet optimality. In the surface-compression paper, the main theorem states that for a $C^2$-geometrically regular function $f$, the transform code with $R$ bits in the best bandelet basis satisfies $\|f-f_R\|^2 \le C\,R^{-2}\log_2(R)$, an optimal exponent for this class; but the theorem is proved by replacing the 1D wavelet transform of the implementation by a 1D Alpert multiwavelet transform, and the implementation instead uses standard 1D wavelet filter banks. The distortion between a mesh $M$ and its reconstruction $M_R$ is measured in practice by the symmetric Hausdorff distance $d_H$ (the worst-case distance between the two surfaces, insensitive to reparameterizations, reported as a peak-signal-to-noise ratio $\mathrm{PSNR}=20\log_{10}(\mathrm{peak}/d_H)$), whereas the theorem controls only the $L^2$ error of the parameterized image; the paper bridges the two by an ad-hoc heuristic of local coordinate changes and three times more bits for detail coefficients in the normal direction than in the tangential directions, noting that further theoretical studies remain to be done. Later surveys of 3D mesh compression [Maglo, Lavoué, Dupont, and Hudelot 2015] record that the field subsequently moved to wavelet lifting on semi-regular meshes, frame dictionaries, and spectral methods, while the bandelet line continued mainly in 2D image applications; approximation-theoretic neighbors such as optimally sparse shearlet representations of 3D data with $C^2$ surface singularities [Guo and Labate 2012] address volumetric sparse approximation with redundant frames, not the coding of parameterized surface geometry.

Problem Statement

Within the framework of second-generation bandelet compression of surfaces parameterized as geometry images and normal maps (orthogonal wavelet transform, multiscale geometric flow estimated in a quadtree segmentation, 1D re-decomposition along quantized flow directions, Lagrangian best-basis selection, entropy coding of coefficients, segmentation, and geometry), as introduced by Peyré and Mallat in Surface compression with geometric bandelets (ACM Transactions on Graphics 24(3), 2005), resolve the three linked gaps that this source paper explicitly leaves open, as one coherent objective of making the bandelet surface codec both theoretically justified and geometrically faithful: (1) Theory-practice gap: prove, or disprove, that the distortion-rate bound $\|f-f_R\|^2 \le C\,R^{-2}\log_2(R)$ for $C^2$-geometrically regular $f$, currently established only for the Alpert-multiwavelet variant of the construction, also holds for the discrete implementation actually used, in which the 1D re-decomposition is performed with standard wavelet transforms (and, in the later orthogonalized version, with Gram-Schmidt-orthogonalized geometric filters on a standard wavelet filter bank), including the effects of quantization and the rate spent on coding the geometry. (2) Geometric distortion gap: replace the ad-hoc heuristic of local coordinate changes and triple bit allocation in the normal direction, which the paper states requires 'further theoretical studies', by a distortion-rate theory that directly controls the parameterization-invariant geometric distortion of the reconstructed surface, rather than the $L^2$ error of the parameterized image, thereby justifying or replacing the $L^2$-optimal coding criterion. (3) Topological scope gap: extend the bandelet codec from spherical geometry images, which restrict the method to genus-0 closed surfaces, to multi-chart geometry images that represent surfaces of arbitrary genus, handling chart boundaries and per-chart rate allocation, and evaluate the extension against the state of the art. Progress on any one item (for instance a Hausdorff distortion-rate theorem for image-based surface coding, or a proof of the optimal exponent for the implemented discrete transform) would constitute progress on the problem even if the other items remain open; the problem is complete when the codec's rate-distortion guarantees hold for the transform actually implemented, in a geometrically meaningful metric, on surfaces of general topology.

References

1. Peyré, Gabriel; Mallat, Stéphane, Surface compression with geometric bandelets, ACM Transactions on Graphics 24(3), pp. 601-608, 2005 (SIGGRAPH 2004). DOI 10.1145/1073204.1073236, https://doi.org/10.1145/1073204.1073236.
2. Peyré, Gabriel; Mallat, Stéphane, Discrete bandelets with geometric orthogonal filters, IEEE International Conference on Image Processing (ICIP) 2005. DOI 10.1109/ICIP.2005.1529688, https://doi.org/10.1109/ICIP.2005.1529688.
3. Peyré, Gabriel; Mallat, Stéphane, Orthogonal bandelet bases for geometric images approximation, Communications on Pure and Applied Mathematics 61(9), pp. 1173-1212, 2008. DOI 10.1002/cpa.20242, https://doi.org/10.1002/cpa.20242.
4. Le Pennec, E.; Mallat, S., Bandelet Image Approximation and Compression, Multiscale Modeling and Simulation, 2005. DOI 10.1137/040619454, https://doi.org/10.1137/040619454.
5. Sander, P. V.; Wood, Z. J.; Gortler, S. J.; Snyder, J.; Hoppe, H., Multi-Chart Geometry Images, Eurographics Symposium on Geometry Processing (SGP 2003), pp. 146-155, 2003. DOI 10.2312/SGP/SGP03/146-155, https://doi.org/10.2312/SGP/SGP03/146-155.
6. Gu, Xianfeng; Gortler, Steven J.; Hoppe, Hugues, Geometry images, ACM SIGGRAPH 2002. DOI 10.1145/566570.566589, https://doi.org/10.1145/566570.566589.
7. Alpert, Bradley K., Wavelets and Other Bases for Fast Numerical Linear Algebra, in Wavelets: A Tutorial in Theory and Applications, Academic Press, 1992. DOI 10.1016/b978-0-12-174590-5.50012-5, https://doi.org/10.1016/b978-0-12-174590-5.50012-5.
8. Maglo, Adrien; Lavoué, Guillaume; Dupont, Florent; Hudelot, Céline, 3D Mesh Compression, ACM Transactions on Graphics, 2015. DOI 10.1145/2693443, https://doi.org/10.1145/2693443.
9. Guo, Kanghui; Labate, Demetrio, Optimally Sparse Representations of 3D Data with $C^2$ Surface Singularities Using Parseval Frames of Shearlets, SIAM Journal on Mathematical Analysis, 2012. DOI 10.1137/100813397, https://doi.org/10.1137/100813397.
10. Munkberg, Jacob; Akenine-Möller, Tomas; Ström, Jacob, High quality normal map compression, ACM SIGGRAPH/EUROGRAPHICS Graphics Hardware (GH '06), 2006. DOI 10.1145/1283900.1283916, https://doi.org/10.1145/1283900.1283916.
11. Hachani, M.; Ouled Zaid, A.; Puech, W., Rate-Distortion Optimized Compression Algorithm for 3D Triangular Mesh Sequences, IEEE Data Compression Conference (DCC), 2016. DOI 10.1109/dcc.2016.57, https://doi.org/10.1109/dcc.2016.57.
12. Zhou, Qingyang; Kadam, Pranav; Liu, Shan; Kuo, C.-C. Jay, Rate Distortion Optimization for Mesh Geometry Compression, IEEE International Conference on Image Processing (ICIP) 2026, pp. 1-6. DOI 10.1109/icip61757.2026.11630313, https://doi.org/10.1109/icip61757.2026.11630313.
13. Roudet, Céline, Compression adaptative de surfaces par ondelettes géométriques (Adaptive surface compression with geometric wavelets), PhD thesis, Université Claude Bernard Lyon 1 (Université de Lyon), 2008, NNT 2008LYO1022. HAL identifier tel-00589400, https://theses.hal.science/tel-00589400.
14. Krivokuća, Maja; Abdulla, Waleed Habib; Wünsche, Burkhard Claus, Progressive Compression of 3D Mesh Geometry Using Sparse Approximations from Redundant Frame Dictionaries, ETRI Journal, 2017. DOI 10.4218/etrij.17.0116.0509, https://doi.org/10.4218/etrij.17.0116.0509.
15. Sheng, Bin; Wu, Enhua, View-dependent mesh streaming using multi-chart geometry images, ACM SIGGRAPH symposium on Interactive 3D Graphics and Games (I3D), 2007. DOI 10.1145/1315184.1315242, https://doi.org/10.1145/1315184.1315242.