Automatyczna detekcja płaszczyzn w chmurze punktów w oparciu o algorytm RANSAC i elementy teorii grafów

• Autorzy: Poręba M. , Goulette F.

Warianty tytułu

EN

RANSAC algorithm and elements of graph thory for automatic plane detection in 3D point cloud

• Języki publikacji: PL

Abstrakty

PL

Artykuł przedstawia metodę automatycznego wyodrębniania punktów modelujących płaszczyzny w chmurach punktów pochodzących z mobilnego bądź statycznego skaningu laserowego. Zaproponowany algorytm bazuje na odpornym estymatorze RANSAC umożliwiającym iteracyjną detekcję płaszczyzn w zbiorze cechującym się znacznym poziomem szumu pomiarowego i ilością punktów odstających. Aby zoptymalizować jego działanie, dla każdej wykrytej płaszczyzny uwzględniono relacje sąsiedztwa pomiędzy punktami przynależnymi. W tym celu zastosowano podejście oparte na teorii grafów, gdzie chmura punktów traktowana jest jako graf nieskierowany, dla którego poszukiwane są spójne składowe. Wprowadzona modyfikacja obejmuje dwa dodatkowe etapy: ustalenie najbliższych sąsiadów dla każdego punktu wykrytej płaszczyzny wraz z konstrukcją listy sąsiedztwa oraz etykietowanie spójnych komponentów. Rezultaty uzyskane pokazują iż algorytm poprawnie wykrywa płaszczyzny modelujące, przy czym niezbędny jest odpowiedni dobór parametrów początkowych. Czas przetwarzania uzależniony jest przede wszystkim od liczby punktów w chmurze. Nadal jednak aktualny pozostaje problem wrażliwości algorytmu RANSAC na niską gęstość chmury oraz nierównomierne rozmieszczenie punktów.

EN

Laser scanning techniques play very important role in acquiring of spatial data. Once the point cloud is available, the data processing must be performed to achieve the final products. The segmentation is an inseparable step in point cloud analysis in order to separate the fragments of the same semantic meaning. Existing methods of 3D segmentation are divided into two categories. The first family contains algorithms functioning on principle of fusion, such as surface growing approach or split-merge algorithm. The second group consists of techniques making possible the extraction of features defined by geometric primitives i.e.: sphere, cone or cylinder. Hough transform and RANSAC algorithm (RANdom SAmple Consensus) are classified to the last of aforementioned groups. This paper studies techniques of point cloud segmentation such as fully automatic plane detection. Proposed method is based on RANSAC algorithm providing an iterative plane modelling in point cloud affected by considerable noise. The algorithm is implemented sequentially, therefore each successive plane represented by the largest number of points is separated. Despite all advantages of RANSAC, it sometimes gives erroneous results. The algorithm looks for the best plane without taking into account the particularity of the object. Consequently, RANSAC may combine points belonging to different objects into one single plane. Hence, RANSAC algorithm is optimized by analysing the adjacency relationships of neighbouring points for each plane. The approach based on graph theory is thus proposed, where the point cloud is treated as undirected graph for which connected components are extracted. Introduced method consists of three main steps: identification of k-nearest neighbours for each point of detected plane, construction of adjacency list and finally connected component labelling. Described algorithm was tested with raw point clouds, unprocessed in sense of filtration. All the numerical tests have been performed on real data, characterized by different resolutions and derived from both mobile and static laser scanning techniques. Obtained results show that proposed algorithm properly separates points for particular planes, whereas processing time is strictly dependent on number of points within the point cloud. Nevertheless, susceptibility of RANSAC algorithm to low point cloud density as well as irregular points distribution is still animportant problem. This paper contains literature review in subject of existing methods for plane detection in data set. Moreover, the description for proposed algorithm based on RANSAC, its principle, as well as the results is also presented.

Słowa kluczowe

PL

chmura punktów; segmentacja; RANSAC; graf; algorytm k najbliższego sąsiada; etykietowanie; spójny komponent

EN

point cloud; segmentation; RANSAC; graph; k-nearest neighbour algorithm; labelling; connected component

• Wydawca: Zarząd Główny Stowarzyszenia Geodetów Polskich
• Czasopismo: Archiwum Fotogrametrii, Kartografii i Teledetekcji
• Rocznik: 2012
• Tom: Vol. 24
• Strony: 301--310
• Opis fizyczny: Bibliogr. 13 poz.

Twórcy

autor

Poręba M.

• Akademia Górniczo-Hutnicza w Krakowie, Katedra Geoinformacji, Fotogrametrii i Teledetekcji Środowiska, tel. [phone]
• MINES ParisTech, CAOR Centre de Robotique, Mathématiques et Systèmes

autor

Goulette F.

• MINES ParisTech, CAOR Centre de Robotique, Mathématiques et Systèmes, tel. [phone]

Bibliografia

• 1. Awwad T. M., Zhu Q., Du Z., Zhang Y., 2010. An improved segmentation approach for planar surfaces from unstructured 3D point clouds. The Photogrammetric Record, 25(129), s. 5-23.
• 2. Bauer J., Karner K., Schindler K., Klaus A., Zach C., 2005. Segmentation of building from dense 3D point-clouds. In Proceedings of the ISPRS. Workshop Laser scanning Enschede Netherlands, September 12-14.
• 3. Boulaassal, H., 2010. Segmentation et modélisation géométrique de façades de bâtiments à partir de relevés laser terrestres. PhD Thesis, Université de Strasbourg.
• 4. Delmerico J. A., David P., Corso J. J., 2011.Building Facade Detection, Segmentation, and Parameter Estimation for Mobile Robot Localization and Guidance. In Proceedings of IROS International Conference on Intelligent Robots and Systems.
• 5. Deschaud, J-E., 2010. Traitements de nuages de points denses et modélisation 3D d’environnement par système mobile LIDAR/Caméra. PhD Thesis, MINES ParisTech.
• 6. Fischler, M. A., Bolles, R. C., 1981. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM, 24(6), s.381-395.
• 7. Hartley R., Zisserman A., 2003. Multiple view geometry in computer vision. Cambrige University Press,Second edition, s.117-121.
• 8. Jarząbek-Rychard M., Borkowski A., 2010. Porównanie algorytmów RANSAC oraz rosnących płaszczyzn w procesie segmentacji danych z lotniczego skaningu laserowego. Archiwum Fotogrametrii, Kartografii i Teledetecji, vol. 21, s.119-129.
• 9. Tarsha Kurdi, F., 2008. Extraction et reconstruction de bâtiments en 3D à partir de relevés lidar aéroportés. PhD Thesis, Université de Strasbourg.
• 10. Tuttas S., Stilla U., 2011. Window Detection In Sparse Point Clouds Using Indoor Points. International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, vol. 38 (3/W22), s.131-136.
• 11. Vosselman G., Gorte B.G.H., Sithole G., Rabbani T., 2004. Recognising structure in laser scanner point clouds. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol. XXXVI, s. 33-38.
• 12. Yang M.Y., Forstner W., 2010. Plane Detection in Point Cloud Data, Technical Report Nr.1, Department of Photogrammetry, University of Bonn.
• 13. Zuliani M., 2012. RANSAC for Dummies, Technical Report. http://vision.ece.ucsb.edu/~zuliani/Research/RANSAC/docs/RANSAC4Dummies.pdf