Using RANSAC for 3D point cloud segmentation

• Autorzy: Luchowski L. , Kowalski P.

Warianty tytułu

PL

Wykorzystanie algorytmu RANSAC dla segmentacji chmur punktów 3D

• Języki publikacji: EN

Abstrakty

EN

The article presents a method for 3D point cloud segmentation. The point cloud comes from a FARO LS scanner - the device creates a dense point cloud, where 3D points are organized in the 2D table. The input data set consists of millions of 3D points - it makes widely known RANSAC algorithms unusable. We add some modifications to use RANSAC for such big data sets

PL

Artykuł prezentuje metodę segmentacji chmury punktów 3D. Segmentacja znajduje w chmurze (kracie) punktów kwadryki. Źródłem danych są chmury punktów uzyskane przy pomocy skanera FARO LS. Skany wykonane przy wykorzystaniu tego skanera charakteryzują się zapisem punktów w tablicy (stąd określenie 'krata' punktów), przy czym jej rozmiary są znaczne - w eksperymentach wykorzystano kratę liczącą 9600x3960, co daje 38 016 000 punktów, podkreślając znaczenie czynnika złożoności pamięciowej algorytmów. Przedstawione rozwiązanie uwzględnia ten problem wywołując czasochłonny algorytm RANSAC jedynie dla wycinków analizowanej sceny, a następnie wykorzystuje uzyskane rezultaty do dalszej analizy. W artykule zaprezentowano szczegółowo algorytm RANSAC i zasady analizy wycinków skanu. Dane wejściowe dla algorytmu reprezentują scenę utworzoną przez człowieka (wnętrze pomieszczenia), co oznacza pojawianie się wielu płaszczyzn i innych prostych obiektów geometrycznych (np. wycinków walca). Prezentowane rozwiązanie pozwala na odnalezienie w scenie kwadryk, rozwiązanie takie pozwala objąć wiele kształtów tworzonych przez człowieka. W przeprowadzonych eksperymentach analizowano skan jadalni Willi Caro - dziewiętnastowiecznej willi, będącej jedną z siedzib Muzeum w Gliwicach. Wybór takiego przedmiotu eksperymentów jest powiązany z jednym z docelowych zastosowań - skanowaniem obiektów dziedzictwa kulturowego celem dokonania ich inwentaryzacji architektonicznej. Wyznaczenie kwadryk opisujących fragmenty skanu pozwala dobrać dokładność skanowania (zwiększenie dokładności dla wybranych fragmentów - detali artystycznych) w zależności od złożoności powierzchni. Ilustracje 1-3 prezentują analizowany skan, ilustracja nr 4 przedstawia punkty przypisane do kwadryk (wszystkich znalezionych przez oprogramowanie), a nr 5 zintegrowane kwadryki dla jednej ze ścian jadalni. W wyniku analizy znaleziono 299 kwadryk (o rozmiarach od 210 do 20512), które po integracji utworzyły 85 zintegrowanych powierzchni (wiele z nich to jednak pojedyncze kwadryki z pierwszego etapu przedstawiania, dla których nie znaleziono odpowiedników).

Słowa kluczowe

EN

3D segmentation; point cloud; RANSAC

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2013
• Tom: Vol. 25, No. 2
• Strony: 105--117
• Opis fizyczny: Bibliogr. 21 poz., rys.

Twórcy

autor

Luchowski L.

• Institute of Theoretical and Applied Informatics, Polish Academy of Science, ul. Bałtycka 5, Gliwice, Poland

autor

Kowalski P.

• Institute of Theoretical and Applied Informatics, Polish Academy of Science, ul. Bałtycka 5, Gliwice, Poland

Bibliografia

• 1.M. Pollefeys, Visual 3D modeling from images - tutorial notes, University of North Carolina, Chapel Hill, USA
• 2.P. V. C. Hough, Machine analysis of bubble chamber pictures, Tech. Report, CERN, 1959
• 3.R. O. Duda, P. E. Hart, Use of the Hough Transformation to Detect Lines and Curves in Pictures, Comm. ACM, vol. 15, pp. 1115, 1972
• 4.D. H. Ballard, Generalization the Hough Transform to Detect Arbitrary Shapes, Pattern Recognition, vol. 13, no. 2, pp. 111-122, 1981
• 5.M. A. Fischler, R. C. Bolles, Random samples consensus: a paradigm for model fitting with applications to image analysis and automated cartography, Comm. ACM, vol. 24, no. 6, pp. 381-395, 1981
• 6.L. Shapiro, G. Stockman, Computer Vision, Prentice Hall, 2001
• 7.G. H. Liu, Y. S. Wong, Y. F. Zhang, H. T. Loh, Error-based segmentation of cloud data for direct rapid prototyping, Computer-Aided Design, vol. 35, pp. 633-645, 2002
• 8.F. Tarsha-Kurdi, T. Landes, P. Grussenmeyer, Hough-transform and extended ransac algorithm for automatic detection of 3d building roof planes from lidar data, Proceedings of the ISPRS Workshop on Laser Scanning, pp. 407-412, 2007
• 9.R. Schnabel, R. Wahl, R. Klein, Efficient RANSAC for point-cloud shape detection, Computer Graphics Forum, vol. 26, no. 2, pp. 214-226, 2007
• 10.A. Courtial, E. Vezzetti, New 3D segmentation approach for reverse engineering selective sampling acquisition, International Journal Advances Manufactory Technology, vol. 35, pp. 900-907, 2008
• 11.Y. Liu, Y. Xiong, Automatic segmentation of unorganized noisy point clouds based on the Gaussian map, Computer-Aided Design, vol. 40, pp. 576-594, 2008
• 12.K. Skabek, P Kowalski, Building the Models of Cultural Heritage Objects Using Multiple 3D Scanners, Theoretical and Applied Informatics, vol. 21, pp. 115-129, 2009
• 13.J. A. P. Kjellander, M. Rahayem, Planar segmentation of data from a laser profile scanner mounted on an industrial robot, International Journal Advances Manufactory Technology, vol. 45, pp. 181-190, 2009
• 14.A. Golovinskiy, T. Funkhouser, Consistent segmentation of 3D models, Computer & Graphics, vol. 33, pp. 262-269, 2009
• 15. E. Li, B. Levy, X. Zhang, W. Che, W. Dong, J-.C. Paul, Meshless quadrangulation by global parametrization, Computer & Graphics, vol. 35, pp. 992-1000, 2011
• 16. F. Bergamasco, A. Albarelli, A. Torsello, A graph-based technique for semi-supervised segmentation of 3D surfaces, Pattern Recognition Letters, vol. 33, pp. 2057-2064, 2012
• 17.J. Martinez, A. Soria-Medina, P. Arias, A. F. Buffara-Antnes, Automatic processing of Terrestrial Laser Scanning data of building facades, Automation in Construction, vol. 22, pp. 298-305, 2012
• 18.L. Wang, J. Cao, Ch. Han, Multidimensional particle swarm optimization-based unsupervised planar segmentation algorithm of unorganized point clouds, Pattern Recognition, vol. 45, pp. 4034-4043, 2012
• 19.M. Meng, J. Xia, J. Luo, Y. He, Unsupervided co-segmentation for 3D shapes using iterative multi-label optimization, Computer-Aided Design, vol. 45, pp. 312-320, 2013
• 20.O. Wirjady, Survey of 3D image segmentation method, Berichte des Frauenhofer ITWM, no. 123, 2007
• 21.L. Luchowski, Adapting the RANSAC algorithm to detect 2nd-degree manifolds in 2D and 3D, Theoretical and Applied Informatics, vol. 24, no. 2., pp. 151-158, 2012