More Web Proxy on the site http://driver.im/

research-article

Quality point cloud normal estimation by guided least squares representation

Authors:

Ligang LiuAuthors Info & Claims

Computers and Graphics, Volume 51, Issue C

Pages 106 - 116

https://doi.org/10.1016/j.cag.2015.05.024

Published: 01 October 2015 Publication History

Abstract

In this paper, we present a quality point cloud normal estimation method via subspace segmentation based on guided least squares representation. A structure guided low-rank subspace segmentation model has been employed in normal estimation (LRRSGNE). In order to select a consistent sub-neighborhood for a point, the subspace segmentation model is adopted to analyze the underlying structure of its neighborhood. LRRSGNE generates more faithful normals than previous methods but at the price of a long runtime which may take hours. Following its framework, two improvements are proposed. We first devise a novel least squares representation based subspace segmentation model with structure guiding (LSRSG) and design a numerical algorithm which has a natural parallelism for solving it. It segments subspaces as quality as the low-rank model used in LRRSGNE but with less runtime. We prove that, no matter whether the subspaces are independent or disjoint, it generates a block-diagonal solution which leads to a quality subspace segmentation. To reduce the computational cost of the normal estimation framework further, we develop a subspace structure propagation algorithm. Only parts of the candidate feature points' neighborhoods are segmented by LSRSG and those of the rest candidate points are inferred via the propagation algorithm which is faster than LSRSG. The experiments exhibit that our method and LRRSGNE generate comparable normals and are more faithful than other state-of-the-art methods. Furthermore, hours of runtime of LRRSGNE is reduced to just minutes. Graphical abstractDisplay Omitted HighlightsA guided subspace clustering framework and its theoretical analysis are presented.SGLRS is proposed as a special case of the framework.A rapid algorithm with a natural parallelism is devised for SGLRS.A quality normal estimation method is proposed based on SGLRS.A subspace structure propagation algorithm is designed to speed up the estimation.

References

[1]

B. Li, R. Schnabel, R. Klein, Z. Cheng, G. Dang, S. Jin, Robust normal estimation for point clouds with sharp features, Comput Graph, 34 (2010) 94-106.

Digital Library

[2]

A. Boulch, R. Marlet, Fast and robust normal estimation for point clouds with sharp features, Comput Graph Forum, 31 (2012) 1765-1774.

Digital Library

[3]

Rusinkiewicz S, Levoy M. Qsplat: a multiresolution point rendering system for large meshes. In: SIGGRAPH, 2000. p. 343-52.

Digital Library

[4]

Zwicker M, Pfister H, van Baar J, Gross MH. Surface splatting. In: SIGGRAPH, 2001. p. 371-8.

Digital Library

[5]

J. Wang, D. Gu, Z. Yu, C. Tan, L. Zhou, A framework for 3d model reconstruction in reverse engineering, Comput Ind Eng, 63 (2012) 1189-1200.

[6]

J. Wang, Z. Yu, W. Zhu, J. Cao, Feature-preserving surface reconstruction from unoriented, noisy point data, Comput Graph Forum, 32 (2013) 164-176.

[7]

C. Lange, K. Polthier, Anisotropic smoothing of point sets', Comput Aided Geom Des, 22 (2005) 680-692.

Digital Library

[8]

H. Huang, S. Wu, M. Gong, D. Cohen-Or, U.M. Ascher, H.R. Zhang, Edge-aware point set resampling, ACM Trans Graph, 32 (2013) 9.

Digital Library

[9]

Hoppe H, DeRose T, Duchamp T, McDonald JA, Stuetzle W. Surface reconstruction from unorganized points. In: Proceedings of the 19th annual conference on computer graphics and interactive techniques, SIGGRAPH 1992, 1992. p. 71-8.

Digital Library

[10]

G. Guennebaud, M.H. Gross, Algebraic point set surfaces, ACM Trans Graph, 26 (2007) 23.

Digital Library

[11]

F. Cazals, M. Pouget, Estimating differential quantities using polynomial fitting of osculating jets, Comput Aided Geom Des, 22 (2005) 121-146.

Digital Library

[12]

N.J. Mitra, A. Nguyen, L.J. Guibas, Estimating surface normals in noisy point cloud data, Int J Comput Geometry Appl, 14 (2004) 261-276.

[13]

S. Fleishman, D. CohenOr, C.T. Silva, Robust moving least-squares fitting with sharp features, ACM Trans Graph, 24 (2005) 544-552.

Digital Library

[14]

M. Yoon, Y. Lee, S. Lee, I.P. Ivrissimtzis, H. Seidel, Surface and normal ensembles for surface reconstruction, Comput Aided Des, 39 (2007) 408-420.

Digital Library

[15]

J. Zhang, J. Cao, X. Liu, J. Wang, J. Liu, X. Shi, Point cloud normal estimation via low-rank subspace clustering, Comput Graph, 37 (2013) 697-706.

Digital Library

[16]

Klasing K, Althoff D, Wollherr D, Buss M. Comparison of surface normal estimation methods for range sensing applications. In: IEEE international conference on robotics and automation, 2009. p. 3206-11.

[17]

F. Cazals, M. Pouget, Estimating differential quantities using polynomial fitting of osculating jets, Comput Aided Geom Des, 22 (2005) 121-146.

Digital Library

[18]

M. Pauly, R. Keiser, L. Kobbelt, M.H. Gross, Shape modeling with point-sampled geometry, ACM Trans Graph, 22 (2003) 641-650.

Digital Library

[19]

T.R. Jones, F. Durand, M. Zwicker, Normal improvement for point rendering, IEEE Comput Graph Appl, 24 (2004) 53-56.

Digital Library

[20]

Calderón F, Ruiz U, Rivera M. Surface-normal estimation with neighborhood reorganization for 3d reconstruction. In: Progress in pattern recognition, image analysis and applications, 2007. p. 321-30.

[21]

Alexa M, Behr J, Cohen-Or D, Fleishman S, Levin D, Silva CT. Point set surfaces. In: Proceedings, IEEE visualization 2001, October 24-26, 2001, San Diego, CA, USA, 2001. p. 21-8.

[22]

A.C. Öztireli, G. Guennebaud, M.H. Gross, Feature preserving point set surfaces based on non-linear kernel regression, Comput Graph Forum, 28 (2009) 493-501.

[23]

N. Amenta, M.W. Bern, Surface reconstruction by voronoi filtering, Discrete Comput Geom, 22 (1999) 481-504.

[24]

T.K. Dey, S. Goswami, Provable surface reconstruction from noisy samples, Comput Geom, 35 (2006) 124-141.

Digital Library

[25]

Alliez P, Cohen-Steiner D, Tong Y, Desbrun M. Voronoi-based variational reconstruction of unoriented point sets. In: Proceedings of the fifth eurographics symposium on geometry processing, Barcelona, Spain, July 4-6, 2007. p. 39-48.

Digital Library

[26]

H. Huang, S. Wu, M. Gong, D. Cohen-Or, U. Ascher, H. Zhang, Edge-aware point set resampling, ACM Trans Graph, 32 (2013) 9:1-9:12.

Digital Library

[27]

Y. Wang, H.-Y. Feng, F.-É. Delorme, S. Engin, An adaptive normal estimation method for scanned point clouds with sharp features, Comput Aided Des, 45 (2013) 1333-1348.

Digital Library

[28]

G. Liu, Z. Lin, S. Yan, J. Sun, Y. Yu, Y. Ma, Robust recovery of subspace structures by low-rank representation, IEEE Trans Pattern Anal Mach Intell, 35 (2013) 171-184.

Digital Library

[29]

Lu C, Min H, Zhao Z, Zhu L, Huang D, Yan S. Robust and efficient subspace segmentation via least squares regression, CoRR abs/1404.6736.

[30]

X. Liu, J. Zhang, R. Liu, B. Li, J. Wang, J. Cao, Low-rank 3d mesh segmentation and labeling with structure guiding, Comput Graph, 46 (2015) 99-109.

Digital Library

[31]

K. Tang, R. Liu, Z. Su, J. Zhang, Structure-constrained low-rank representation, IEEE Trans Neural Netw Learn Syst, 25 (2014) 2167-2179.

[32]

Y.-K. Lai, Q.-Y. Zhou, S.-M. Hu, J. Wallner, D. Pottmann, Robust feature classification and editing, IEEE Trans Vis Comput Graph, 13 (2007) 34-45.

Digital Library

[33]

J. Shi, J. Malik, Normalized cuts and image segmentation, IEEE Trans Pattern Anal Mach Intell, 22 (2000) 888-905.

Digital Library

[34]

J. Yang, Y. Zhang, Alternating direction algorithms for L 1 -problems in compressive sensing, SIAM J. Sci Comput, 33 (2011) 250-278.

Digital Library

[35]

Y. Boykov, O. Veksler, R. Zabih, Fast approximate energy minimization via graph cuts, IEEE Trans Pattern Anal Mach Intell, 23 (2001) 1222-1239.

Digital Library

Cited By

Huang GFang QZhang ZLiu LFu X(2024)Stochastic Normal Orientation for Point CloudsACM Transactions on Graphics10.1145/368794443:6(1-12)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687944
Xu RDou ZWang NXin SChen SJiang MGuo XWang WTu C(2023)Globally Consistent Normal Orientation for Point Clouds by Regularizing the Winding-Number FieldACM Transactions on Graphics10.1145/359212942:4(1-15)Online publication date: 26-Jul-2023
https://dl.acm.org/doi/10.1145/3592129
Huang ZCarr NJu T(2019)Variational implicit point set surfacesACM Transactions on Graphics10.1145/3306346.332299438:4(1-13)Online publication date: 12-Jul-2019
https://dl.acm.org/doi/10.1145/3306346.3322994
Show More Cited By

Recommendations

Robust Subspace Segmentation via Sparse Relation Representation
Pattern Recognition and Computer Vision
Abstract
Spectral clustering based algorithms are powerful tools for solving subspace segmentation problems. The existing spectral clustering based subspace segmentation algorithms use original data matrices to produce the affinity graphs. In real ...
Adaptive graph-regularized fixed rank representation for subspace segmentation
Abstract
Low-rank representation (LRR) has shown its great power in subspace segmentation tasks. However, by using matrix factorization skill, fixed-rank representation dominates LRR in many subspace segmentation applications. In this paper, based on the ...
Latent space robust subspace segmentation based on low-rank and locality constraints

We propose a new latent space robust subspace segmentation method.We build the connections between the proposed algorithm and robust coding methods.We devise a weighted l1-norm regularizer to capture local structures of data sets. Low-rank ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computers and Graphics

Computers and Graphics Volume 51, Issue C

October 2015

204 pages

ISSN:0097-8493

Issue’s Table of Contents

Copyright © Elsevier Ltd.

Publisher

Pergamon Press, Inc.

United States

Publication History

Published: 01 October 2015

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Huang GFang QZhang ZLiu LFu X(2024)Stochastic Normal Orientation for Point CloudsACM Transactions on Graphics10.1145/368794443:6(1-12)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687944
Xu RDou ZWang NXin SChen SJiang MGuo XWang WTu C(2023)Globally Consistent Normal Orientation for Point Clouds by Regularizing the Winding-Number FieldACM Transactions on Graphics10.1145/359212942:4(1-15)Online publication date: 26-Jul-2023
https://dl.acm.org/doi/10.1145/3592129
Huang ZCarr NJu T(2019)Variational implicit point set surfacesACM Transactions on Graphics10.1145/3306346.332299438:4(1-13)Online publication date: 12-Jul-2019
https://dl.acm.org/doi/10.1145/3306346.3322994
Zhang JCao JLiu XChen HLi BLiu L(2019)Multi-Normal Estimation via Pair Consistency VotingIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2018.282799825:4(1693-1706)Online publication date: 16-Jul-2019
https://dl.acm.org/doi/10.1109/TVCG.2018.2827998
Cao JChen HZhang JLi YLiu XZou C(2018)Normal estimation via shifted neighborhood for point cloudJournal of Computational and Applied Mathematics10.1016/j.cam.2017.04.027329:C(57-67)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1016/j.cam.2017.04.027
Mura CWyss GPajarola R(2018)Robust normal estimation in unstructured 3D point clouds by selective normal space explorationThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-018-1542-634:6-8(961-971)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1007/s00371-018-1542-6
Coeurjolly DFoare MGueth PLachaud J(2016)Piecewise smooth reconstruction of normal vector field on digital dataComputer Graphics Forum10.5555/3151666.315168335:7(157-167)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.5555/3151666.3151683
Boulch AMarlet RKobbelt LOvsjanikov MPanozzo D(2016)Deep learning for robust normal estimation in unstructured point cloudsProceedings of the Symposium on Geometry Processing10.5555/3061451.3061487(281-290)Online publication date: 20-Jun-2016
https://dl.acm.org/doi/10.5555/3061451.3061487

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents