Martyna Por Ba 
  
François Goulette 
  
  
AUTOMATYCZNA DETEKCJA PŁASZCZYZN W CHMURZE PUNKTÓW W OPARCIU O ALGORYTM RANSAC I ELEMENTY TEORII GRAFÓW RANSAC ALGORITHM AND ELEMENTS OF GRAPH THORY FOR AUTOMATIC PLANE DETECTION IN 3D POINT CLOUD

Keywords: chmura punktów, segmentacja, RANSAC, graf, algorytm najbli szego s siada, etykietowanie, spójny komponent

STRESZCZENIE: 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

WPROWADZENIE

Rekonstrukcja trójwymiarowych modeli budynków odgrywa w ostatnich latach znacz c rol w dziedzinie fotogrametrii i widzenia komputerowego. Rozwój technologii skaningu laserowego w aspekcie szybko ci pomiaru, precyzji punktów oraz rozdzielczo ci otworzył nowe horyzonty bada , zawłaszcza w temacie modelowania zabudowy na podstawie nieuporz dkowanej chmury punktów. Istotnym etapem przetwarzania i analizy danych jest segmentacja maj ca na celu wyodr bnienie fragmentów o tym samym znaczeniu semantycznym. Jako kryterium jednorodno ci przyjmuje si na ogół poło enie punktów, krzywizn czy kierunek wektora normalnego. W wiecie realnym budynki w znacznej mierze formowane s jako kombinacja płaszczyzn. Segmentacja automatyczna ma na celu rozkład chmury punktów na podzbiory punktów reprezentuj ce poszczególne płaszczyzny. Istniej ce metody segmentacji chmur punktów stanowi rozwini cie dobrze znanych algorytmów, dedykowanych pierwotnie cyfrowemu przetwarzaniu obrazów. Zapewniaj one minimalizacj strat informacji przestrzennej wyst puj cych w przypadku konieczno ci konwersji danych 3D do postaci 2D. Krótki przegl d metod i algorytmów mo liwych do zastosowania przedstawiony przez [START_REF] Vosselman | Recognising structure in laser scanner point clouds[END_REF] i [START_REF] Boulaassal | Segmentation et modélisation géométrique de façades de bâtiments à partir de relevés laser terrestres[END_REF] pozwala wyró nić dwie kategorie metod segmentacji. Pierwsza rodzina obejmuje algorytmy działaj ce na zasadzie ł czenia, takie jak metoda rosn cych płaszczyzn (and. surface growing) czy algorytm dziel-ł cz (ang. split -merge). Drug grup stanowi techniki umo liwiaj ce automatyczn rekonstrukcj form zdefiniowanych poprzez prymitywy geometryczne w postaci sfery, płaszczyzny, cylindra lub sto ka. Zalicza si do nich transformat Hougha (ang. Hough Transformation) i algorytm RANSAC (ang.

RANdom SAmple Consensus).

Przeprowadzone badania literaturowe pokazuj i na etapie segmentacji danych dominuj metody rosn cych płaszczyzn czy te te oparte o algorytm RANSAC. W swoich pracach [START_REF] Bauer | Segmentation of building from dense 3D point-clouds[END_REF] i (Boulaassal, 2010) wykorzystuj algorytm RANSAC dla celów detekcji fasad budynków. Aby zoptymalizować działanie tego estymatora w procesie wyodr bniania płaszczyzn, został on poddany licznym modyfikacjom. [START_REF] Literatura Awwad | An improved segmentation approach for planar surfaces from unstructured 3D point clouds[END_REF] oraz [START_REF] Delmerico | Building Facade Detection, Segmentation, and Parameter Estimation for Mobile Robot Localization and Guidance[END_REF] proponuj uwzgl dnienie kierunku wektora normalnego obliczonego w ka dym punkcie chmury. Algorytm [START_REF] Yang | Plane Detection in Point Cloud Data[END_REF] polega na podziale chmury punktów na małe bloki, zawieraj ce nie wi cej ni trzy płaszczyzny. Nast pnie w ka dym wokselu aproksymowane s p łaszczyzny, których liczba weryfikowana jest poprzez zasad MDL (ang. Minimum Description Length). Wykryte płaszczyzny ł czone s ostatecznie ze sob w oparciu o pewne parametry lokalne. Metody [START_REF] Deschaud | Traitements de nuages de points denses et modélisation 3D d'environnement par système mobile LIDAR/Caméra[END_REF], (Tuttas et al., 2010) bazuj natomiast na algorytmie rosn cych płaszczyzn polegaj cym kolejno na identyfikacji płaszczyzny pierwotnej, a nast pnie jej ekspansji, czyli grupowaniu punktów według pewnych ustalonych parametrów okre laj cych ich wzajemne podobie stwo. Istnieje ponadto wiele wariantów metody rosn cych płaszczyzn, ró ni cych si mi dzy sob sposobem wyboru płaszczyzn pocz tkowych jak równie kryterium rozrostu. Liczne s równie prace porównuj ce rezultaty segmentacji chmur punktów przeprowadzonych z u yciem wymienionych algorytmów. [START_REF] Jarz Bek-Rychard | Porównanie algorytmów RANSAC oraz rosn cych płaszczyzn w procesie segmentacji danych z lotniczego skaningu laserowego[END_REF] konfrontuje wydajno ć estymatora RANSAC z metod rosn cych płaszczyzn. Przeprowadzone testy polegaj ce na detekcji połaci dachowych w danych z lotniczego skaningu laserowego pozwalaj stwierdzić, i RANSAC jest rozwi zaniem lepszym w przypadku segmentacji modeli nieskomplikowanych geometrycznie. Z drugiej jednak strony jest on bardziej podatny na ł czenie w jedn płaszczyzn matematyczn punktów przynale cych do ró nych, w rzeczywisto ci odr bnych obiektów. W podobnym kontek cie realizuje swoje studium porównawcze (Tarsha-Kurdi, 2008) testuj c algorytm RANSAC i transformat Hougha. Stwierdza on, e RANSAC jest bardziej przystosowany do przetwarzania danych przestrzennych.

W niniejszej pracy poruszono problematyk segmentacji chmur punktów -w pełni automatycznej detekcji płaszczyzn. Zaproponowana metoda bazuje na algorytmie RANSAC, którego działanie zostało zoptymalizowane poprzez uwzgl dnienie relacji s siedztwa pomi dzy punktami tworz cymi dan powierzchni matematyczn tak, aby współpłaszczyznowym obiektom przypisać odr bne, ograniczone płaszczyzny modeluj ce.

ALGORYTM RANSAC

Algorytm RANSAC jest iteracyjn metod stosowan w celu estymacji parametrów poszukiwanego modelu matematycznego obiektu w zbiorze danych zawieraj cym znaczn ilo ć punktów nienale cych do modelowanej powierzchni [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF], [START_REF] Zuliani | RANSAC for Dummies[END_REF]. Fakt ten, czyni estymator RANSAC szczególnie interesuj cym dla celów przetwarzania chmur punktów obarczonych szumem i bł dnymi pomiarami. Działanie algorytmu obejmuje zasadniczo dwie fazy: inicjalizacj i test, obydwie powtarzane iteracyjnie.

Etap inicjalizacji polega na wyborze w sposób losowy minimalnego zbioru punktów (kworum), niezb dnego do jednoznacznego wyznaczenia parametrów estymowanego modelu geometrycznego. W przestrzeni euklidesowej płaszczyzn definiuj cztery parametry 1÷4 , z czego trzy s niezale ne. Parametry hipotetycznego modelu M( ) wyznaczane s zatem w oparciu o trzy elementy losowej próbki. Nast pnie pozostałe punkty ze zbioru porównywane s z tak utworzonym modelem. W tej fazie niezb dne jest przyj cie progu ( ) okre laj cego zakres, w którym punkt (p) pasuje do modelu. Wszystkie punkty spełniaj ce zadane kryterium (ang. inlieres) dodawane s do zbioru CS (ang. Consensus Set) (1), a cały etap okre lany jest mianem testu.

} )) ( , ( : {      M p e N p CS M (1)
Ró nica mi dzy punktem a modelem obliczana jest na podstawie równania (2):

     n i i i def M p p p p dist M p e 1 2 * * ) ( ) , ( min )) ( , (  (2) 
gdzie p i * oznacza rzut ortogonalny punktu p na model M( ).

Dobór odpowiedniej warto ci tolerancji ( ) -szeroko ci bufora wokół płaszczyzny redniej -odgrywa wa n rol na poziomie stabilno ci algorytmu RANSAC i wpływa na jako ć wyodr bnionych płaszczyzn. Jako e skanowane obiekty nie s utworzone z idealnych powierzchni, a chmura punktów posiada pewn mi szo ć spowodowan szumem pomiarowym, wpasowanie modelu odbywa si z zachowaniem pewnej elastyczno ci. Najcz ciej tolerancja ( ) definiowana jest jako maksymalna odległo ć testowanego punktu od teoretycznego modelu. Według [START_REF] Hartley | Multiple view geometry in computer vision[END_REF] warto ć mo e zostać wyznaczona przy zało eniu, e wszystkie dane obarczone s szumem gaussowskim, czyli bł dem o rozkładzie normalnym ~ N(0, I) dla = p-p*. Zatem tolerancja ( ) okre la z prawdopodobie stwem P czy dany punkt nale y do strefy buforowej.

] ) ( [ ] [ ) ) ( , ( ( 2 2 2 1 1 2 2                    n i i n i i M P P M p e P (3) Poniewa N(0,1)    i zatem zmienna losowa 2 1 ) (   n i i    posiada rozkład chi-kwadrat
o n stopniach swobody. Ostatecznie, rozwijaj c równanie (3), przy uwzgl dnieniu powy szych zale no ci, warto ć tolerancji ( ) obliczana jest zgodnie z relacj (4):

) ( 1 2 2 P F       (4) gdzie: 1 2 2   F
-warto ć krytyczna rozkładu chi-kwadrat z liczb stopni swobody równ dwa na poziomie istotno ci P.

W ten sposób wyznaczenie warto ci progowej ( ) sprowadza si do podania prawdopodobie stwa P oraz warto ci szumu pomiarowego   .

Proces inicjalizacji i testu powtarzany jest iteracyjnie dla nowo wylosowanej próbki zbiorów minimalnych, a liczba powtórze (Iter) wyznaczana jest zgodnie z równaniem ( 5) [START_REF] Zuliani | RANSAC for Dummies[END_REF]. W przypadku gdy liczebno ć punktów card(CS) w kolejnym znalezionym zbiorze CS jest wi ksza od poprzedniego, zast puje on dotychczasowy zbiór.

) 1 log( ) 1 log( ) 1 ( ) 1 ( 3 3 W P Iter W P Iter        (5) 
Powy sza zale no e liczba iteracji obliczana jest na postawie znajomo ci prawdopodobie stwa P identyfikacji "najlepszej płaszczyzny" oraz prawdopodobie stwa W, e wszystkie punkty losowej próbki nale do ostatecznego modelu. Dobór tych parametrów odbywa si w sposób empiryczny, st d te prawdopodobie stwo P przyjmuje warto ć z przedziału 0.95 ÷ 0.99, z kolei W powinno być oszacowane w funkcji danych (6).

) (

) ( N card CS card W  (6) 
gdzie: card(N) -liczba wszystkich punktów wej ciowego zbioru danych.

Z praktycznego punktu widzenia, okre lenie parametru W mo e przysporzyć problemów dlatego te algorytm RANSAC w wersji bazowej inicjalizowany jest poprzez zgrubn estymacje tej warto ci. Rozwi zanie zaproponowane przez [START_REF] Hartley | Multiple view geometry in computer vision[END_REF] zmniejsza czas przetwarzania pozwalaj c na dynamiczny dobór maksymalnej liczby iteracji, aktualizowanej przed rozpocz ciem nast pnej sekwencji -inicjalizacji i testu.

PROPONOWANY ALGORYTM DETEKCJI PŁASZCZYZN

W niniejszej pracy algorytm RANSAC [START_REF] Zuliani | RANSAC for Dummies[END_REF] z modyfikacjami wprowadzonymi przez [START_REF] Hartley | Multiple view geometry in computer vision[END_REF] zaimplementowano sekwencyjnie, a wi c punkty przynale ce do ka dej kolejno zidentyfikowanej płaszczyzny s wył czane z dalszych poszukiwa . Algorytm ko czy swoje działanie, gdy wykryta zostanie wst pnie zało ona liczba płaszczyzn (N pl ) lub liczba punktów nie pozwala ju na poprawn estymacj modelu. Rysunek 1 ilustruje rezultat ekstrakcji trzech kolejnych płaszczyzn w chmurze punktów (N). Cech specyficzn algorytmu RANSAC jest fakt, i generuje on dwa rodzaje bł dów: powierzchniowe i liniowe, formowane przez punkty uło one w sekwencje linii lub pól rozproszonych wokół powierzchni dominuj cej. Punkty te tworz jedn płaszczyzn matematyczn lecz z punktu widzenia semantycznego nie s zgodne z rzeczywisto ci , gdy nale do ró nych obiektów. Podstawowym wyzwaniem postawionym przed rozwijanym algorytmem, decyduj cym o jego operacyjno ci, jest zdolno ć detekcji dla ka dego elementu architektonicznego odr bnej płaszczyzny modeluj cej.

Rys. 1. Rezultat detekcji trzech płaszczyzn w chmurze punktów za pomoc algorytmu RANSAC w wersji bazowej (dany kolor odpowiada jednej płaszczy nie)

Aby zoptymalizować działanie algorytmu RANSAC wprowadzono dodatkowo ograniczenie dotycz ce ł czno ci pomi dzy punktami wyodr bnionymi dla poszczególnych powierzchni. W rezultacie dla ka dego podzbioru reprezentuj cego pojedyncz płaszczyzn weryfikowane jest czy stanowi on jeden ci gły element, czy mo e zbiór rozł cznych powierzchni. Zaproponowane rozwi zanie opiera si na teorii grafów traktuj c tym samym chmur punktów jako graf nieskierowany, dla którego poszukiwane s spójne składowe. Takie podej cie umo liwia prac bezpo rednio na chmurze punktów. 

Rys. 3. Diagram czynno ci -zaproponowany algorytm detekcji płaszczyzn

Rysunek 3 przedstawia schemat zaproponowanego algorytmu detekcji płaszczyzn wzbogaconego o analiz spójnych komponentów. Wyodr bnienie spójnych składowych wymaga okre lenia trzech parametrów: promienia sfery R oraz maksymalnej liczby s siadów K, których znaczenie zostanie szczegółowo omówione w nast pnym paragrafie. Ograniczenie liczby wyodr bnianych komponentów sprowadza si do zdefiniowania parametru N min okre laj cego minimaln liczebno ć.

Lista s siedztwa

W uproszczeniu graf to zbiór wierzchołków S, w ród których niektóre poł czone s za pomoc kraw dzi

} , , : } , {{ v u S v u v u E   
. Z kolei ka da kraw d zaczyna si i ko czy w wierzchołku mog c tym samym obrazować relacje mi dzy obiektami jak na przykład s siedztwo dwóch wybranych wierzchołków. Aby usystematyzować relacje pomi dzy punktami chmury punktów -grafu, najwygodniej jest przedstawić chmur w postaci listy s siedztwa, która dla ka dego wierzchołka przyporz dkowuje list jego najbli szych s siadów -kraw dzi wychodz cych z punktu (Rys. 4). Skonstruowanie wspomnianej listy wymaga zaimplementowania algorytmu analizuj cego s siedztwo lokalne punktów. Istniej dwie najcz ciej wykorzystywane strategie okre lania s siedztwa punktu. Pierwsza, polega na wyszukaniu, dla ka dego punktu w zbiorze, ustalonej liczby K najbli szych s siadów poło onych w odległo ci minimalnej. Według innej definicji, s to wszystkie punkty zawarte w sferze o promieniu R [START_REF] Deschaud | Traitements de nuages de points denses et modélisation 3D d'environnement par système mobile LIDAR/Caméra[END_REF]. Takie rozwi zanie, w porównaniu do pierwszego, jest niezale ne od rozmieszczenia punktów, przy czym dedykowane jest g stym chmurom punktów. W niniejszej pracy poł czono zalety obu metod definiuj c s siedztwo lokalne punktu jako zbiór punktów zawartych sferze o promieniu R przy jednoczesnym ograniczeniu liczby s siadów do K.

Rys. 4. Reprezentacja grafu w postaci listy s siedztwa

Ekstrakcja spójnych komponentów

Wyszukanie spójnych składowych grafu sprowadza si do okre lenia jego maksymalnych podgrafów, czyli takich, które mo na wydzielić z całego grafu bez usuwania kraw dzi. Jedn z metod eksploracji grafów jest przeszukiwanie w gł b (ang. DFS Depth-first search). Algorytm ten mo e być zastosowany do wyznaczania spójnych komponentów grafu. Idea jest prosta -procedura rozpoczyna działanie w wybranym wierzchołku grafu oznaczanym jako odwiedzony i nadaje mu odpowiedni etykiet . Nast pnie przechodzi wzdłu kraw dzi do kolejnego, nieodwiedzonego jeszcze s siada. Eksploracja wykonywana jest do momentu natrafienia na wierzchołek, który nie posiada ju nieodwiedzonych s siadów. Wtedy procedura wraca do poprzedniego odwiedzonego wierzchołka i kontynuuje przeszukiwanie w gł b. Po wykonaniu pełnego przej cia (wszystkie wierzchołki osi galne z wierzchołka startowego zostały odwiedzone) wybierany jest nowy wierzchołek pocz tkowy, zwi kszany numer etykiety, a procedura ponownie wykonuje rekurencyjne poszukiwania. W przeciwnym wypadku algorytm ko czy działanie, gdy wszystkie wierzchołki grafu zostały ju odwiedzone, a badany graf jest spójny i stanowi jeden komponent. Poszukuj c bardziej wydajnej metody etykietowania spójnych składowych grafu zastosowana została dekompozycja Dulmage -Mendelsohn (DM) macierzy rzadkiej A zawieraj cej list wszystkich par wierzchołków s siednich. W teorii grafów umo liwia ona w unikalny sposób rozkład grafu dwudzielnego na spójne podgrafy. Z punktu widzenia praktycznego dekompozycja DM odpowiada permutacji wierszy (p) i kolumn (q) macierzy niekwadratowej A do postaci górnej blokowo trójk tnej (7):

              44 34 24 23 14 13 12 11 0 0 0 0 0 0 0 0 ) , ( A A A A A A A A q p A C (7)
Ostatecznie spójne komponenty obliczane s w oparciu o poni sze równanie:

) 1 ) 1 ( : ) (   i r i r p
(8) gdzie: r-lista wierzchołków przynale cych do tego samego spójnego komponentu.

PODSUMOWANIE

Testy numeryczne wykonano na chmurach punktów o ró nej rozdzielczo ci, pochodz cych z mobilnego i statycznego skaningu laserowego. Uzyskane wyniki pokazuj , e algorytm RANSAC wzbogacony o analiz spójnych komponentów poprawnie rozdziela punkty odpowiadaj ce poszczególnym obiektom, le cym w tej samej płaszczy nie matematycznej (Rys. 5). Wykorzystanie, nierozpowszechnionej dot d dekompozycji Dulmage-Mandelsohn przyniosło oczekiwane rezultaty, pozwalaj c na efektywne wyodr bnienie i zaetykietowanie spójnych komponentów. Najbardziej czasochłonnym etapem metody jest analiza s siedztwa punktu, a czas realizacji zadania uzale niony jest od g sto ci chmury punktów. Zaproponowany algorytm pozwala na automatyzacj procesu detekcji płaszczyzn, wymagaj c od operatora wprowadzenie jedynie kilku parametrów wej ciowych, dostosowanych do przetwarzanych danych. Algorytm jest odpowiedni dla segmentacji nieskomplikowanych modeli, w szczególno ci głównych powierzchni fasad budynków czy jezdni.

Rys. 5. Rezultat detekcji płaszczyzn w chmurze pozyskanej przez system mobilny Riegl VMX-250. Ustalone parametry: =0.01m, P=0.99; R=0.2m, K=25; N_min=200 Istotn wad RANSAC pozostaje ci gle jego wra liwo ć na nisk g sto ć chmury i nieregularne rozmieszczenie punktów. Fakt ten sprawia, e RANSAC mo e wyodr bniać "fałszywe" płaszczyzny, które nie znajduj pokrycia w rzeczywisto ci. Przeprowadzone badania pokazuj , e problem ten ujawnia si g łównie podczas pracy na surowych chmurach punktów pozyskanych przez systemy mobilne. Mo liwe przestoje platformy pomiarowej powoduj bowiem nagromadzenie w jednym rejonie znacznej ilo ci punktów.

Rys. 2 .

 2 Etapy ekstrakcji płaszczyzn: a) Detekcja płaszczyzny za pomoc RANSAC; b) Wyodr bnienie spójnych komponentów; c) Płaszczyzna zachowana po uwzgl dnieniu kryterium ł czno ci W rozwijanym algorytmie wyró nia si dwa główne etapy: sekwencyjn detekcj płaszczyzny za pomoc algorytmu RANSAC oraz analiz spójno ci sprowadzaj c si do ustalenia listy s siedztwa dla wszystkich punktów, a nast pnie etykietowania spójnych komponentów (Rys. 2). Ostatecznie dla ka dego wyznaczonego spójnego komponentu obliczana jest powierzchnia (S k ) jako pole otoczki wypukłej, czyli najmniejszego poligonu zamkni tego obejmuj cego zbiór. Region o najwi kszym polu stanowi punkty reprezentuj ce "najlepsz powierzchni ", pozostałe punkty wł czane s ponownie do pocz tkowego zbioru danych i uczestnicz w dalszych poszukiwaniach.

RANSAC ALGORITHM AND ELEMENTS OF GRAPH THEORY FOR AUTOMATIC PLANE DETECTION IN 3D POINT CLOUD

KEY WORDS: point cloud, segmentation, RANSAC, graph, k-nearest neighbour algorithm, labelling, connected component

Summary

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 an important 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.

Dane autorów:

Mgr in . Martyna Por ba e-mail: martyna.poreba@mines-paristech.fr telefon: 12 617 39 93 Prof. dr hab. in . François Goulette e-mail: francois.goulette@mines-paristech.fr telefon: (+33) 14 051 92 35