“Decoupling noise and features via weighted ℓ1-analysis compressed sensing” by Wang, Yang, Liu, Deng and Chen

  • ©Ruimin Wang, Zhouwang Yang, Ligang Liu, Jiansong Deng, and Falai Chen




    Decoupling noise and features via weighted ℓ1-analysis compressed sensing


Session Title: Surfaces, Shapes, and Maps



    Many geometry processing applications are sensitive to noise and sharp features. Although there are a number of works on detecting noise and sharp features in the literature, they are heuristic. On one hand, traditional denoising methods use filtering operators to remove noise, however, they may blur sharp features and shrink the object. On the other hand, noise makes detection of features, which relies on computation of differential properties, unreliable and unstable. Therefore, detecting noise and features on discrete surfaces still remains challenging.

    In this article, we present an approach for decoupling noise and features on 3D shapes. Our approach consists of two phases. In the first phase, a base mesh is estimated from the input noisy data by a global Laplacian regularization denoising scheme. The estimated base mesh is guaranteed to asymptotically converge to the true underlying surface with probability one as the sample size goes to infinity. In the second phase, an ℓ1-analysis compressed sensing optimization is proposed to recover sharp features from the residual between base mesh and input mesh. This is based on our discovery that sharp features can be sparsely represented in some coherent dictionary which is constructed by the pseudo-inverse matrix of the Laplacian of the shape. The features are recovered from the residual in a progressive way. Theoretical analysis and experimental results show that our approach can reliably and robustly remove noise and extract sharp features on 3D shapes.


    1. H. Avron, A. Sharf, C. Greif, and D. Cohen-Or. 2010. ℓ1-sparse reconstruction of sharp point set surfaces. ACM Trans. Graph. 29, 5, 135–154.
    2. C. Bajaj and G. Xu. 2003. Anisotropic diffusion of surfaces and functions on surfaces. ACM Trans. Graph. 22, 1, 4–32.
    3. Z. Bian and R. Tong. 2011. Feature-preserving mesh denoising based on vertices classification. Comput.-Aided Geom. Des. 28, 1, 50–64.
    4. M. Botsch, L. Kobbelt, M. Pauly, P. Alliez, and B. Levy. 2010. Polygon Mesh Processing. AK Peters/CRC Press.
    5. S. Boyd and L. Vandenberghe. 2004. Convex Optimization. Cambridge University Press.
    6. E. Candes, Y. Eldar, D. Needell, and P. Randall. 2010. Compressed sensing with coherent and redundant dictionaries. Appl. Comput. Harmonic Anal. 31, 1, 59–73.
    7. E. Candes and T. Tao. 2005. Decoding by linear programming. IEEE Trans. Inf. Theory 51, 12, 4203–4215.
    8. E. Candes and M. Wakin. 2008. An introduction to compressive sampling. IEEE Signal Process. Mag. 25, 2, 21–30.
    9. E. Candes, M. Wakin, and S. Boyd. 2008. Enhancing sparsity by reweighted ℓ1 minimization. J. Fourier Anal. Appl. 14, 5–6, 877–905.
    10. U. Clarenz, U. Diewald, and M. Rumpf. 2000. Anisotropic geometric diffusion in surface processing. In Proceedings of the Conference on Visualization (VIS’00). 397–405.
    11. E. Cuthill and J. McKee. 1969. Reducing the bandwidth of sparse symmetric matrices. In Proceedings of the 24th ACM National Conference. 157–172.
    12. M. Desbrun, M. Meyer, P. Schroder, and A. Barr. 1999. Implicit fairing of irregular meshes using diffusion and curvature flow. In Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’99). 317–324.
    13. D. Donoho. 2006. Compressed sensing. IEEE Trans. Inf. Theory 25, 4, 1289–1306.
    14. F. Duguet, F. Durand, and G. Drettakis. 2004. Robust higher-order filtering of points. Tech. rep. RR-5165, INRIA. http://www-sop.inria.fr/reves/Basilic/2004/Dug04a/RR-5165.pdf.
    15. Y. Eldar and G. Kutyniok. 2012. Compressed Sensing: Theory and Applications. Cambridge University Press.
    16. H. Fan, Y. Yu, and Q. Peng. 2010. Robust feature-preserving mesh denoising based on consistent sub-neighborhoods. IEEE Trans. Vis. Comput. Graph. 16, 2, 312–324.
    17. S. Fleishman, I. Drori, and D. Cohen-Or. 2003. Bilateral mesh denoising. ACM Trans. Graph. 22, 3, 950–953.
    18. M. Habbecke and L. Kobbelt. 2012. Linear analysis of nonlinear constraints for interactive geometric modeling. Comput. Graph. Forum 31, 2, 1–10.
    19. L. He and S. Schaefer. 2013. Mesh denoising via l0 minimization. ACM Trans. Graph. 32, 4, 64:1–64:8.
    20. K. Hildebrandt and K. Polthier. 2004. Anisotropic filtering of nonlinear surface features. Comput. Graph. Forum 23, 3, 391–400.
    21. K. Hildebrandt and K. Polthier. 2007. Constraint-based fairing of surface meshes. In Proceedings of the 5th Eurographics Symposium on Geometry Processing (SGP’07). 203–212.
    22. T. Jones, F. Durand, and M. Desbrun. 2003. Non-iterative, feature-preserving mesh smoothing. ACM Trans. Graph. 22, 3, 943–949.
    23. R. B. Lehoucq, D. C. Sorensen, and C. Yang. 1998. ARPACK Users’ Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods, Vol. 6, SIAM.
    24. L. Liu, C. Tai, Z. Ji, and G. Wang. 2007. Non-iterative approach for global mesh optimization. Comput.-Aided Des. 39, 9, 772–782.
    25. F. J. Massey. 1951. The kolmogorov-smirnov test for goodness of fit. J. Amer. Statist. Assoc. 46, 253, 68–78.
    26. A. Nealen, T. Igarashi, O. Sorkine, and M. Alexa. 2006. Laplacian mesh optimization. In Proceedings of the 4th International Conference on Computer Graphics and Interactive Techniques in Australasia and Southeast Asia (GRAPHITE’06). 381–389.
    27. D. C. Sorensen. 1997. Implicitly Restarted Arnoldi/Lanczos Methods for Large Scale Eigenvalue Calculations. Springer.
    28. Z. Su, H. Wang, and J. Cao. 2009. Mesh denoising based on differential coordinates. In Proceedings of the IEEE International Conference on Shape Modeling and Applications (SMI’09). 1–6.
    29. X. Sun, P. Rosin, R. Martin, and F. Langbein. 2007. Fast and effective feature-preserving mesh denoising. IEEE Trans. Vis. Comput. Graph. 13, 5, 925–938.
    30. G. Taubin. 1995. A signal processing approach to fair surface design. In Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’95). 351–358.
    31. C. Tomasi and R. Manduchi. 1998. Bilateral filtering for gray and color images. In Proceedings of the 6th International Conference on Computer Vision (ICCV’98). 839–846.
    32. G. Wahba. 1990. Spline Models for Observational Data. SIAM, Philadelphia, PA.
    33. L. Xu, C. Lu, Y. Xu, and J. Jia. 2011. Image smoothing via L0 gradient minimization. ACM Trans. Graph. 30, 6, 174:1–174:12.
    34. H. Yagou, Y. Ohtake, and A. Belyaev. 2002. Mesh smoothing via mean and median filtering applied to face normals. In Proceedings of the Geometric Modeling and Processing — Theory and Applications (GMP’02). 124–131.
    35. Y. Zheng, H. Fu, O. K.-C. Au, and C.-L. Tai. 2010. Bilateral normal filtering for mesh denoising. IEEE Trans. Vis. Comput. Graph. 17, 10, 1521–1530.

ACM Digital Library Publication: