Mehmet ÖZTÜRK, Zeynep HASIRCI

A novel dynamic bandwidth selection method for thinning noisy point clouds

In this paper, we propose a dynamic bandwidth selection method for thinning noisy point clouds into curves. Due to the nonhomogeneous distribution of noise or varying curvature of the data, the thinning procedure requires a dynamically adjusted bandwidth along the curve. On the other hand, the selected local region must be sorted along a suitable direction vector for local curve fitting purposes. The contribution of this paper to the field is 2-folded: first, a normalized eigenvalue analysis-based method is used to determine the best local bandwidth. The second task is getting a good regression line of the local region for ordering the data. In this step, a feature that is based on the Euclidean distances between points is used to determine the best regression line in the search space. Finally, a third-order parametric polynomial is fitted to the local data using the least squares method. We adapt and test our algorithm on the widely used k-nearest neighbor and constant radius methods. Our experiments show that the proposed methods automatically produce comparable results with these methods at their best parameter, which is empirically determined. Our methods also do not require any empirically determined parameter to adjust the best bandwidth or to select a good regression axis. Moreover, this method can be used with point sets that do not have a regression axis.

Anahtar Kelimeler:

Curve reconstruction, eigenvalue analysis, point cloud processing, bandwidth selection, tangent estimation

A novel dynamic bandwidth selection method for thinning noisy point clouds

Keywords:

Curve reconstruction, eigenvalue analysis, point cloud processing, bandwidth selection, tangent estimation,

PDF

___

H. Edelsbrunner, D.G. Kirkpatrick, R. Seidel, On the Shape of a Set of Points in the Plane, University of British Columbia, Vancouver, BC, Canada, 1981.
D. Attali, “R-regular shape reconstruction from unorganized points”, Proceedings of the 13th Annual ACM Symposium on Computational Geometry, pp. 248–253, 1997.
L.H.D. Figueiredo, J.D.M. Gomes, “Computational morphology of curves”, Visual Computer, Vol. 11, pp. 105–112, 19 F. Bernardini, C.L. Bajaj, “Sampling and reconstructing manifolds using alpha-shapes”, Proceedings of the 9th Canadian Conference on Computational Geometry, 1997.
N. Amenta, M. Bern, D. Eppstein, “The crust and the beta-skeleton: combinatorial curve reconstruction”, Graphical Models and Image Processing, Vol. 60/2, pp. 125–135, 1998.
T.K. Dey, P. Kumar, “A simple provable algorithm for curve reconstruction”, Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 893–894, 1999.
T.K. Dey, K. Mehlhorn, E.A. Ramos, “Curve reconstruction: connecting dots with good reason”, Proceedings of the 15th ACM Symposium on Computational Geometry, Vol. 15, pp. 229–244, 1999. E. Althaus, K. Mehlhorn, “TSP-based curve reconstruction in polynomial time”, Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 686–695, 2000.
T.K. Dey, R. Wenger, “Reconstruction curves with sharp corners”, Proceedings of the 16th Annual Symposium on Computational Geometry, pp. 233–241, 2000.
T.K. Dey, R. Wenger, “Fast reconstruction of curves with sharp corners”, International Journal of Computational Geometry & Applications, Vol. 12, pp. 353–400, 2002.
C. Gold, “Crust and anti-crust: a one-step boundary and skeleton extraction algorithm”, Proceedings of the 15th Annual Symposium on Computational Geometry, pp. 189–196, 1999.
C.M. Gold, J. Nantel, W. Yang, “Outside-in: an alternative approach to forest map digitizing”, International Journal of Geographical Information Systems, Vol. 10, pp. 291–310, 1996.
S. Funke, E.A. Ramos, “Reconstructing a collection of curves with corners and endpoints”, Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithm, pp. 344–353, 2001.
Y. Zeng, T.A. Nguyen, B. Yan, S. Li, “A distance-based parameter free algorithm for curve reconstruction”, Computer-Aided Design, Vol. 40, pp. 210–222, 2008.
P. Kim, H. Kim, “Point ordering with natural distance based on Brownian motion”, Mathematical Problems in Engineering, Vol. 2010, Article ID 450460, 2010.
T.K. Dey, “Curve and surface reconstruction”, in Handbook of Discrete and Computational Geometry, 2nd ed., CRC Press, Boca Raton, FL, USA, 2004.
S.W. Cheng, S. Funke, M. Golin, P. Kumar, S.H. Poon, E. Ramos, “Curve reconstruction from noisy samples” Computational Geometry: Theory and Applications, Vol. 31, pp. 63–100, 2005.
I.K. Lee, “Curve reconstruction from unorganized points,” Computer Aided Geometric Design, Vol. 17, pp. 161–177, 2000.
G. Taubin, R. Ronfard, “Implicit simplicial models for adaptive curve reconstruction”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 18, pp. 321–325, 1996.
Z. Hasirci, M. Ozturk, “An eigenvalue analysis based bandwidth selection method for curve reconstruction from noisy point clouds”, 34th International Conference on Telecommunications and Signal Processing, pp. 478–482, 20