“ℓ1-Sparse Reconstruction of Sharp Point Set Surfaces” by Avron, Sharf, Greif and Cohen-Or

We introduce an ℓ1-sparse method for the reconstruction of a piecewise smooth point set surface. The technique is motivated by recent advancements in sparse signal reconstruction. The assumption underlying our work is that common objects, even geometrically complex ones, can typically be characterized by a rather small number of features. This, in turn, naturally lends itself to incorporating the powerful notion of sparsity into the model. The sparse reconstruction principle gives rise to a reconstructed point set surface that consists mainly of smooth modes, with the residual of the objective function strongly concentrated near sharp features. Our technique is capable of recovering orientation and positions of highly noisy point sets. The global nature of the optimization yields a sparse solution and avoids local minima. Using an interior-point log-barrier solver with a customized preconditioning scheme, the solver for the corresponding convex optimization problem is competitive and the results are of high quality.

1. Adamson, A. and Alexa, M. 2006. Point-Sampled cell complexes. ACM Trans. Graph. 25, 3, 671–680.
2. Alexa, M. and Adamson, A. 2004. On normals and projection operators for surfaces defined by point sets. In Proceedings of the Eurographics Symposium on Point-Based Graphics. 149–155.
3. Alexa, M., Behr, J., Cohen-Or, D., Fleishman, S., Levin, D., and Silva, C. T. 2003. Computing and rendering point set surfaces. IEEE Trans. Visualiz. Comput. Graph. 9, 1, 3–15.
4. Amenta, N. 2004. Defining point-set surfaces. ACM Trans. Graph. 264–270.
5. Amenta, N. and Kil, Y. J. 2004. The domain of a point set surfaces. In Proceedings of the Eurographics Symposium on Point-based Graphics 1, 1, 139–147.
6. Avron, H., Ng, E., and Toledo, S. 2009. Using perturbed QR factorizations to solve linear least-squares problems. SIAM J. Matrix Anal. Appl. 31, 2, 674–693.
7. Bernardini, F., Mittleman, J., Rushmeier, H., Silva, C., and Taubin, G. 1999. The ball-pivoting algorithm for surface reconstruction. IEEE Trans. Visualiz. Comput. Graph. 5, 4, 349–359.
8. Boyd, S. and Vandenberghe, L. 2004. Convex Optimization. Cambridge University Press.
9. Candes, E. and Romberg, J. 2005. l1-Magic: Recovery of sparse signals via convex programming. In http://www.acm.caltech.edu/l1magic/.
10. Candes, E. J., Romberg, J., and Tao, T. 2006. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52, 2, 489–509.
11. Candes, E. J. and Wakin, M. B. 2008. An introduction to compressive sampling {a sensing/sampling paradigm that goes against the common knowledge in data acquisition}. IEEE Signal Process. Mag. 25, 2, 21–30.
12. Candes, E. J., Wakin, M. B., and Boyd, S. P. 2008. Enhancing sparsity by reweighted l1 minimization. J. Fourier Anal. Appl. 14, 877–905.
13. Chan, T. F., Osher, S., and Shen, J. 2001. The digital TV filter and nonlinear denoising. IEEE Trans. Image Process. 10, 231–241.
14. Chen, S. S., Donoho, D. L., and Saunders, M. A. 2001. Atomic decomposition by basis pursuit. SIAM Rev. 43, 1, 129–159.
15. Claerbout, J. and Muir, F. 1973. Robust modeling of erratic data. Geophys. 38, 5, 826–844.
16. Daniels, J. I., Ha, L. K., Ochotta, T., and Silva, C. T. 2007. Robust smooth feature extraction from point clouds. In Proceedings of the IEEE International Conference on Shape Modeling and Applications (SMI’07). 123–136.
17. Davis, T. A. 2008. Multifrontal multithreaded rank-revealing sparse qr factorization. ACM Trans. Math. Softw.
18. Davis, T. A. and Hager, W. W. 2005. Row modifications of a sparse cholesky factorization. SIAM J. Matrix Anal. Appl. 26, 3, 621–639.
19. Dey, T. K. and Sun, J. 2005. An adaptive mls surface for reconstruction with guarantees. In Proceedings of the 3rd Eurographics Symposium on Geometry Processing (SGP’05). 43.
20. Dey, T. K. and Sun, J. 2006. Normal and feature approximations from noisy point clouds. Lecture Notes in Computer Science, vol. 4337. Springer, 21–32.
21. Donoho, D. L., Elad, M., Temlyakov, V. N., and A. 2006. Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Trans. Inf. Theory 52, 6–18.
22. Elad, M., Starck, J., Querre, P., and Donoho, D. 2005. Simultaneous cartoon and texture image inpainting using morphological component analysis (mca). Appl. Comput. Harmonic Anal. 19, 3, 340–358.
23. Elsey, M. and Esedoglu, S. 2009. Analogue of the total variation denoising model in the context of geometry processing. Multiscale Model. Simul. 7, 4, 1549–1573.
24. Fleishman, S., Cohen-Or, D., and Silva, C. T. 2005. Robust moving least-squares fitting with sharp features. ACM Trans. Graph. 24, 3, 544–552.
25. Fleishman, S., Drori, I., and Cohen-Or, D. 2003. Bilateral mesh denoising. ACM Trans. Graph. 22, 3, 950–953.
26. Grant, M. and Boyd, S. 2009. CVX: Matlab software for disciplined convex programming. http://stanford.edu/boyd/cvx.
27. Guennebaud, G. and Gross, M. 2007. Algebraic point set surfaces. In Proceedings of the ACM SIGGRAPH’07 Conferenec.
28. Holland, P. and Welsch, R. 1977. Robust regression using iteratively reweighted least-squares. Commu. Statist. Theory Methods 6, 9, 813–827.
29. Jones, T. R., Durand, F., and Desbrun, M. 2003. Non-Iterative, feature-preserving mesh smoothing. In ACM SIGGRAPH Papers. 943–949.
30. Kolluri, R. 2005. Provably good moving least squares. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’05). 1008–1017.
31. Levin, A., Fergus, R., Durand, F., and Freeman, W. T. 2007. Image and depth from a conventional camera with a coded aperture. In SIGGRAPH Papers. ACM.
32. Levin, D. 2003. Mesh-independent surface interpolation. In Geometric Modeling for Scientific Visualization. 37–49.
33. Lipman, Y., Cohen-Or, D., and Levin, D. 2007a. Data-dependent mls for faithful surface approximation. In Proceedings of the 5th Eurographics Symposium on Geometry Processing (SGP’07). 59–67.
34. Lipman, Y., Cohen-Or, D., Levin, D., and Tal-Ezer, H. 2007b. Parameterization-free projection for geometry reconstruction. ACM Trans. Graph. 26, 3, 22.
35. Lipman, Y., Sorkine, O., Levin, D., and Cohen-Or, D. 2005. Linear rotation-invariant coordinates for meshes. In Proceedings of ACM SIGGRAPH. 479–487.
36. Lobo, M. S., Vandenbergheb, L., Boyd, S., and Lebret, H. 1998. Applications of second-order cone programming. Linear Algeb. Appl. 284, 193–228.
37. Mederos, B., Velho, L., and De Figueiredo, L. H. 2003. Robust smoothing of noisy point clouds. In Proceedings of the SIAM Conference on Geometric Design and Computing.
38. Oztireli, C., Guennebaud, G., and Gross, M. 2009. Feature preserving point set surfaces based on non-linear kernel regression. Comput. Graph. Forum 28, 2, 493–501.
39. Paige, C. C. and Saunders, M. A. 1982. LSQR: An algorithm for sparse linear equations and sparse least squares. ACM Trans. Math. Softw. 8, 1, 43–71.
40. Pauly, M., Keiser, R., and Gross, M. H. 2003. Multi-Scale feature extraction on point-sampled surfaces. Comput. Graph. Forum 22, 3, 281–290.
41. Pauly, M., Mitra, N., and Guibas, L. 2004. Uncertainty and variability in point cloud surface data. In Symposium on Geometry Processing (SGP’04).
42. Reuter, P., Joyot, P., Trunzler, J., Boubekeur, T., and Schlick, C. 2005. Point set surfaces with sharp features. Tech. rep., LaBRI.
43. Rudin, L., Osher, S., and Fatemi, E. 1992. Nonlinear total variation based noise removal algorithms. Physica D 60, 259–268.
44. Rudin, L. I. 1987. Images, numerical analysis of singularities and shock filters. Tech. rep. California Insitute of Technology.
45. Sharf, A., Alcantara, D. A., Lewiner, T., Greif, C., Sheffer, A., Amenta, N., and Cohen-Or, D. 2008. Space-time surface reconstruction using incompressible flow. In ACM SIGGRAPH Papers. vol. 27, 1–10.
46. Shen, C., Obrien, J. F., and Shewchuk, J. R. 2004. Interpolating and approximating implicit surfaces from polygon soup. In ACM Trans. Graph. 896–904.
47. Shepard, D. 1968. A two-dimensional interpolation function for irregularly-spaced data. In Proceedings of the 23rd ACM National Conference. 517–524.
48. Starck, J.-L., Elad, M., and Donoho, D. L. 2005. Image decomposition via the combination of sparse representations and a variational approach. IEEE Trans. Image Process. 14, 10, 1570–1582.
49. Tasdizen, T., Whitaker, R., Burchard, P., and Osher, S. 2002. Geometric surface smoothing via anisotropic diffusion of normals. In Proceedings of the Conference on Visualization (VIS’02). IEEE Computer Society, 125–132.
50. Tasdizen, T., Whitaker, R., Burchard, P., and Osher, S. 2003. Geometric surface processing via normal maps. ACM Trans. Graph. 22, 4, 1012–1033. 
51. Tomasi, C. and Manduchi, R. 1998. Bilateral filtering for gray and color images. In Proceedings of the 6th International Conference on Computer Vision (ICCV’98). 839. 
52. Tropp, J. A. 2006. Just relax: Convex programming methods for identifying sparse signals in noise. IEEE Trans. Inf. Theory 52, 3, 1030–1051.