“Robust surface reconstruction via dictionary learning” by Xiong, Zhang, Zheng, Cai and Liu
Conference:
Type(s):
Title:
- Robust surface reconstruction via dictionary learning
Session/Category Title: Data In, Surface Out
Presenter(s)/Author(s):
Abstract:
Surface reconstruction from point cloud is of great practical importance in computer graphics. Existing methods often realize reconstruction via a few phases with respective goals, whose integration may not give an optimal solution. In this paper, to avoid the inherent limitations of multi-phase processing in the prior art, we propose a unified framework that treats geometry and connectivity construction as one joint optimization problem. The framework is based on dictionary learning in which the dictionary consists of the vertices of the reconstructed triangular mesh and the sparse coding matrix encodes the connectivity of the mesh. The dictionary learning is formulated as a constrained ℓ2,q-optimization (0 < q < 1), aiming to find the vertex position and triangulation that minimize an energy function composed of point-to-mesh metric and regularization. Our formulation takes many factors into account within the same framework, including distance metric, noise/outlier resilience, sharp feature preservation, no need to estimate normal, etc., thus providing a global and robust algorithm that is able to efficiently recover a piecewise smooth surface from dense data points with imperfections. Extensive experiments using synthetic models, real world models, and publicly available benchmark show that our method outperforms the state-of-the-art in terms of accuracy, robustness to noise and outliers, geometric feature and detail preservation, and mesh connectivity.
References:
1. Adams, A., Gelfand, N., Dolson, J., and Levoy, M. 2009. Gaussian KD-trees for fast high-dimensional filtering. ACM Trans. Graph. 28, 3, 21:1–21:12.
2. Aharon, M., Elad, M., and Bruckstein, A. 2006. K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation. IEEE Trans. Sig. Proc. 54, 11, 4311–4322.
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. Vis. Comput. Graph. 9, 1, 3–15.
4. Alliez, P., Cohen-Steiner, D., Tong, Y., and Desbrun, M. 2007. Voronoi-based variational reconstruction of unoriented point sets. In Symposium on Geometry Processing, 39–48.
5. Amenta, N., and Kil, Y. J. 2004. Defining point-set surfaces. ACM Trans. Graph. 23, 3, 264–270.
6. Amenta, N., Choi, S., Dey, T. K., and Leekha, N. 2002. A simple algorithm for homeomorphic surface reconstruction. Int. J. Comput. Geometry Appl. 12, 1-2, 125–141.Cross Ref
7. Avron, H., Sharf, A., Greif, C., and Cohen-Or, D. 2010. l1-sparse reconstruction of sharp point set surfaces. ACM Trans. Graph. 29, 5, 135:1–135:12.
8. Berger, M., Levine, J. A., Nonato, L. G., Taubin, G., and Silva, C. T. 2013. A benchmark for surface reconstruction. ACM Trans. Graph. 32, 2, 20:1–20:17.
9. Berger, M., Tagliasacchi, A., Seversky, L. M., Alliez, P., Levine, J. A., Sharf, A., and Silva, C. T. 2014. State of the art in surface reconstruction from point clouds. Eurographics STAR (Proc. of EG’14), 161–185.
10. Bouaziz, S., Tagliasacchi, A., and Pauly, M. 2013. Sparse iterative closest point. Comput. Graph. Forum 32, 5, 113–123.
11. Boyd, S. P., Parikh, N., Chu, E., Peleato, B., and Eckstein, J. 2011. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning 3, 1, 1–122.
12. Carr, J. C., Beatson, R. K., Cherrie, J. B., Mitchell, T. J., Fright, W. R., McCallum, B. C., and Evans, T. R. 2001. Reconstruction and representation of 3D objects with radial basis functions. In SIGGRAPH, 67–76.
13. Cazals, F., and Giesen, J. 2006. Delaunay triangulation based surface reconstruction: Ideas and algorithms. In Effective Computational Geometry for Curves and Surfaces, Springer.
14. Corsini, M., Cignoni, P., and Scopigno, R. 2012. Efficient and flexible sampling with blue noise properties of triangular meshes. IEEE Trans. Vis. Comput. Graph. 18, 6, 914–924.
15. Dey, T. K., and Giesen, J. 2001. Detecting undersampling in surface reconstruction. In Symposium on Computational Geometry, 257–263.
16. Dey, T. K., and Wang, L. 2013. Voronoi-based feature curves extraction for sampled singular surfaces. Comput. Graph. 37, 6 (Oct.), 659–668.
17. Dey, T. K. 2007. Curve and Surface Reconstruction: Algorithms with Mathematical Analysis. Cambridge University Press.
18. Digne, J., Morel, J., Souzani, C., and Lartigue, C. 2011. Scale space meshing of raw data point sets. Comput. Graph. Forum 30, 6, 1630–1642.Cross Ref
19. Dyer, R., Zhang, H., and Möller, T. 2007. Delaunay mesh construction. In Symposium on Geometry Processing, 273–282.
20. Eckstein, J. 1989. Splitting methods for monotone operators with applications to parallel optimization. PhD thesis, MIT.
21. Edelsbrunner, H., and Mücke, E. P. 1994. Three-dimensional alpha shapes. ACM Trans. Graph. 13, 1, 43–72.
22. Elad, M., and Aharon, M. 2006. Image denoising via sparse and redundant representations over learned dictionaries. IEEE Trans. Img. Proc. 15, 12, 3736–3745.
23. Eldar, Y. C., Kuppinger, P., and Bölcskei, H. 2010. Block-sparse signals: uncertainty relations and efficient recovery. IEEE Trans. Sig. Proc. 58, 6, 3042–3054.
24. Gal, R., Shamir, A., Hassner, T., Pauly, M., and Cohen-Or, D. 2007. Surface reconstruction using local shape priors. In Symposium on Geometry Processing, 253–262.
25. Guennebaud, G., and Gross, M. H. 2007. Algebraic point set surfaces. ACM Trans. Graph. 26, 3, 23:1–23:10.
26. Guillemot, T., Almansa, A., and Boubekeur, T. 2012. Non local point set surfaces. In 3DIMPVT, 324–331.
27. He, L., and Schaefer, S. 2013. Mesh denoising via ℓ0 minimization. ACM Trans. Graph. 32, 4, 64:1–64:8.
28. Hoppe, H., DeRose, T., Duchamp, T., McDonald, J. A., and Stuetzle, W. 1992. Surface reconstruction from unorganized points. In SIGGRAPH, 71–78.
29. Huang, H., Li, D., Zhang, H., Ascher, U. M., and Cohen-Or, D. 2009. Consolidation of unorganized point clouds for surface reconstruction. ACM Trans. Graph. 28, 5, 176:1–176:8.
30. Huang, H., Wu, S., Gong, M., Cohen-Or, D., Ascher, U., and Zhang, H. R. 2013. Edge-aware point set resampling. ACM Trans. Graph. 32, 1 (Feb.), 9:1–9:12.
31. Jain, P., Netrapalli, P., and Sanghavi, S. 2013. Low-rank matrix completion using alternating minimization. In STOC, 665–674.
32. Kazhdan, M. M., and Hoppe, H. 2013. Screened Poisson surface reconstruction. ACM Trans. Graph. 32, 3, 29:1–29:13.
33. Kazhdan, M. M., Bolitho, M., and Hoppe, H. 2006. Poisson surface reconstruction. In Symposium on Geometry Processing, 61–70.
34. Kolluri, R. K., Shewchuk, J. R., and O’Brien, J. F. 2004. Spectral surface reconstruction from noisy point clouds. In Symposium on Geometry Processing, 11–21.
35. Lipman, Y., Cohen-Or, D., Levin, D., and Tal-Ezer, H. 2007. Parameterization-free projection for geometry reconstruction. ACM Trans. Graph. 26, 3, 22:1–22:6.
36. Mairal, J., Bach, F., Ponce, J., and Sapiro, G. 2010. Online learning for matrix factorization and sparse coding. Journal of Machine Learning Research 11, 19–60.
37. Mallat, S., and Zhang, Z. 1993. Matching pursuits with time-frequency dictionaries. IEEE Trans. Sig. Proc. 41, 12, 3397–3415.
38. Marjanovic, G., and Solo, V. 2012. On lq optimization and matrix completion. IEEE Trans. Sig. Proc. 60, 11, 5714–5724.
39. Mello, V., Velho, L., and Taubin, G. 2003. Estimating the in/out function of a surface represented by points. In Symposium on Solid Modeling and Applications, 108–114.
40. Mitra, N. J., Nguyen, A., and Guibas, L. J. 2004. Estimating surface normals in noisy point cloud data. Int. J. Comput. Geometry Appl. 14, 4-5, 261–276.Cross Ref
41. Mullen, P., de Goes, F., Desbrun, M., Cohen-Steiner, D., and Alliez, P. 2010. Signing the unsigned: Robust surface reconstruction from raw pointsets. Comput. Graph. Forum 29, 5, 1733–1741.Cross Ref
42. Nagai, Y., Ohtake, Y., and Suzuki, H. 2009. Smoothing of partition of unity implicit surfaces for noise robust surface reconstruction. Comput. Graph. Forum 28, 5, 1339–1348. Cross Ref
43. Ohtake, Y., Belyaev, A. G., and Alexa, M. 2005. Sparse low-degree implicits with applications to high quality rendering, feature extraction, and smoothing. In Symposium on Geometry Processing, 149–158.
44. Öztireli, A. C., Guennebaud, G., and Gross, M. H. 2009. Feature preserving point set surfaces based on non-linear kernel regression. Comput. Graph. Forum 28, 2, 493–501.Cross Ref
45. Rosman, G., Dubrovina, A., and Kimmel, R. 2013. Patch-collaborative spectral point-cloud denoising. Comput. Graph. Forum 32, 8, 1–12.Cross Ref
46. Schall, O., Belyaev, A. G., and Seidel, H.-P. 2007. Feature-preserving non-local denoising of static and time-varying range data. In Symposium on Solid and Physical Modeling, 217–222.
47. Sharf, A., Alexa, M., and Cohen-Or, D. 2004. Context-based surface completion. ACM Trans. Graph. 23, 3, 878–887.
48. Tošić, I., Olshausen, B. A., and Culpepper, B. J. 2010. Learning sparse representations of depth. Tech. Rep. arXiv:1011.6656, Dec.
49. Vavasis, S. A. 2009. On the complexity of nonnegative matrix factorization. SIAM J. on Optimization 20, 3, 1364–1377.
50. Wang, R., Yang, Z., Liu, L., Deng, J., and Chen, F. 2014. Decoupling noise and features via weighted l1-analysis compressed sensing. ACM Trans. Graph. 33, 2, 18:1–18:12.
51. Wright, J., Ma, Y., Mairal, J., Sapiro, G., Huang, T. S., and Yan, S. 2010. Sparse representation for computer vision and pattern recognition. Proceedings of IEEE 98, 6, 1031–1044.Cross Ref
52. Wu, C., Zhang, J., and Tai, X.-C. 2011. Augmented Lagrangian method for total variation restoration with non-quadratic fidelity. Inverse Problems and Imaging 5, 1, 237–261.Cross Ref
