Open Access Open Access  Restricted Access Subscription or Fee Access

An Efficient Parallel Approach for 3D Point Cloud Image Segmentation using OpenMP

J. Ilamchezhian, Dr. V. Cyril Raj

Abstract


The 3D Point cloud segmentation process is used in Image processing to detect the edges and the 3D structure and widely used in the computer vision and robotics. The 3D point cloud segmentation consists of three major processes: Point cloud data fitting on the 3D Array (Grid), Gradient calculation and thinning process. This process is computationally expensive due to many multiplication and addition which are required to calculate the gradient for the identification of edges, to find the location where a point to be located and stored and thinning process. This is why the existing algorithms are very slow to run on a single processor sequential programming. Therefore it is necessary to make it parallel for the high performance and to speed-up the computation. In this study, a parallel processing approach was used for the segmentation of 3D Point cloud image. The proposed method uses a 3D Vector structure grid concept for the creation of Virtual Grid to store the huge number of unordered points for the fast processing in order to find the neighborhood points. Our algorithm focuses on the fast extraction of edges by segmentation using gradient 3D sobel operator in parallel approach. The results show that the parallel approach will be efficient and provides a better performance in finding the edges. We evaluated this approach with 3 artificially generated data sets in two implementations: one in sequential and the other one in parallel. This new approach produces improved speedup in the edge detections process.

Keywords


Edge Detection, Gradient Method, Laser Scanning, Normal Vector Estimation, OpenMP, Point Cloud, Principal Component Analysis (PCA), Segmentation, Terrestrial Laser Scanning (TLS).

Full Text:

PDF

References


Dina A. Hafiz, 1Walaa M. Sheta, 2Sahar Bayoumi and 1Bayumy A.B. Youssef ―A New Approach for 3D Range Image Segmentation using Gradient Method, J. Computer Sci. 7 (4): 475-487, 2011.

Golovinskiy A. and Funkhouser T,. Min-Cut Based Segmentation of Point Clouds. IEEE Workshop on Search in 3D and Video (S3DV), 39-46 (2009).

Zhan, Q; Liang, Y; Xiao, Y., Color-based segmentation of point clouds. Laserscanning09, Volume XXXVIII, 248-252 (2009).

Sedlacek D. and Zara J., Graph Cut Based Point-Cloud Segmentation for Polygonal Reconstruction, Proc. 5thInternational Symposium on Advances in Visual Computing: Part II (ISVC '09), 218--227, 2009.

Brostow G. J., J., Julien Fauqueur, Roberto Cipolla, Segmentation and Recognition Using Structure from Motion Point Clouds, Proc. 10th European Conference on Computer Vision: Part I,(ECCV '08), 44--57, (2008).

Castillo E. and Zhao H., Point Cloud Segmentation via Constrained Nonlinear Least Squares Surface Normal Estimates. Technical Report AM09-104, Computational and Applied Mathematics Department, University of California Los Angeles, (2009).

Dorninger P and Nothegger C., 3D segmentation of unstructured point clouds for building modeling, Photogrammetric Image Analysis PIA07, 35, 191—196 (2007).

Awwad, T.M., Q. Zhu, Z. Du and Y. Zhang, 2010. An improved segmentation approach for planar surfaces from unstructured 3d point clouds. Photogrammetric Record, 25: 5-23. DOI: 10.1111/j.1477-9730.2009.00564.

Boulaassal, H., T. Landes and P. Grussenmeyer,2009. Automatic extraction of planar clusters and their contours on building facades recorded by terrestrial laser scanner. Int. J. Arch. Comput., 7: 1-20. DOI: ijac20097101.

Jan Elseberg, Dorit Borrmann, Andreas Nuchter, Efficient Processing of Large 3D Point Clouds.

Han, S.H. Efficient segmentation of ALS point cloud utilizing scan line characteristic. Doctoral thesis. Seoul National University: Seoul, Korea, 2008.

Cho, W.; Jwa, Y.S.; Chang, H.J.; Lee, S.H. Pseudo-grid Based Building Extraction Using Airborne Lidar Data. Int. Arch. Photogramm Remote Sens. 2004, 35, 378-381.

Mitra N. J., Nguyen A., and Guibas L., Estimating surface normals in noisy point cloud data. Special issue of Int. J. Computational Geometry and its Applications, 14(4–5):261–276, (2004).

Yuan X., Xu H., Nguyen M.X., Shesh A., Chen B., Sketch-based segmentation of scanned outdoor environment models., Proc. eurographics workshop on sketch-based interfaces and modeling (SBIM ’05), 19—27, 2005.

Ahn, S.J., Rauh, W., Warnecke, H.J., Least-squares orthogonal distances fitting of circle, sphere, ellipse, hyperbola, and parabola. Pattern Recog. 34, 2283–2303, (2001).

Christian Teutsch*a, Erik Trostmanna, Dirk Berndta, A parallel point cloud clustering algorithm for subset segmentation and outlier detection.

Chi, J., X. Wu and C. Zhang, 2008. Medical CT image preprocessing based on edge detection and spline fitting. Proceedings of the IEEE International Symposium on IT in Medicine and Education, Dec. 12-14, IEEE Xplore, Xiamen, pp: 709-714. DOI: 10.1109/ITME.2008.4743958.

N. Haron, R. Ami, I. A.Aziz, L. T. Jung and S. R.. Shukri, Parallelization of Edge Detection Algorithm using MPI on Beowulf Cluster. Innovations in Computing Sciences and Software Engineering . 2010.

Soo Hee Han, Joon Heo, Hong Gyoo Sohn, Kiyun Yu, Parallel Processing Method for Airborne Laser Scanning Data Using a PC Cluster and a Virtual Grid, Sensors 2009, 9, 2555-2573; doi:10.3390/s90402555.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.