Wyniki wyszukiwania - BazTech

1

Równoległy algorytm RANSAC na potrzeby rejestracji chmur punktów

Koguciuk D., Harasymowicz-Boggio B.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2016

|

z. 195, t. 2

427--436

PL

Artykuł przedstawia projekt oraz implementację równoległego algorytmu RANSAC w architekturze CUDA w zadaniu rejestracji chmur punktów na potrzeby manipulacji obiektami codziennego użytku. Na początku pracy krótko omówiono szeregową wersję algorytmu oraz wspomniano o kilku jego modyfikacjach znanych z literatury, po czym przeprowadzono rozumowanie projektowe a następnie implementacyjne wersji równoległej. Testy porównawcze udowodniły poprawność działania algorytmu przy jednoczesnym kilkudziesięciokrotnym zysku czasowym. Wynikiem pracy jest realizacja znalezienia lokalnego układu współrzędnych obserwowanego obiektu na scenie w czasie bliskim czasowi rzeczywistemu. Kod źródłowy programu udostępniono w Internecie jako część projektu Heuros.

EN

In this paper a project and implementation of the parallel RANSAC algorithm in CUDA architecture are presented. The goal is to register point clouds for munipulation of everyday object as fast as possible. In the beginning a serial algorithm with a variety of modifications from the literature is introduced whereupon the idea and CUDA implementation details are discussed. The comparative test has proven the proper working of the implementation together with a significant program execution acceleration. The result is finding local coordinate system of the object in the scene in the near real-time conditions. The source code is shared in the Internet as a part of the Heuros system.

2

Rozwiązania analityczne związane z obsługą procesu orientacji zdjęć oraz wykonywaniem opracowań wektorowych w programie Bundlab

Kolecki J.

Archiwum Fotogrametrii, Kartografii i Teledetekcji

|

2015

|

Vol. 27

61--70

PL

Program Bundlab powstał jako narzędzie głównie dla celów dydaktycznych i badawczych. Niniejszy artykuł stanowi niejako raport opisujący aktualny stan rozwoju tej autorskiej aplikacji, ze szczególnym uwypukleniem stosowanych rozwiązań analitycznych. W pierwszej kolejności przedstawiono ogólną charakterystykę programu, szybko przechodząc do opisu procedury orientacji zdjęć, rozpoczynającej się orientacją wzajemną. Zastosowane tu rozwiązanie bazuje na równaniach komplanarności parametryzowanych macierzą fundamentalną z odpowiednimi warunkami. Problem przekształcany jest do postaci umożliwiającej znalezienie rozwiązania metodami geometrii algebraicznej. W dalszej kolejności realizowane jest rozwiązanie oparte o kryterium najmniejszej sumy kwadratów odchyłek. Łączenie zorientowanych modeli w blok jak również procedurę orientacji bezwzględnej oparto o metodę Horna. W dalszej części przedstawiono narzędzia służące tworzeniu opracowań wektorowych koncentrując się na rozwiązaniach usprawniających pracę operatora i podnoszących dokładność produktu. W ramach artykułu przedstawiono także elementy pochodzące z wykonanych w programie prac. Podano też możliwe dalsze ścieżki rozwoju programu.

EN

The Bundlab software has been developed mainly for academic and research application. This work can be treated as a kind of a report describing the current state of the development of this computer program, focusing especially on the analytical solutions. Firstly, the overall characteristics of the software are provided. Then the description of the image orientation procedure starting from the relative orientation is addressed. The applied solution is based on the coplanarity equation parametrized with the essential matrix. The problem is reformulated in order to solve it using methods of algebraic geometry. The solution is followed by the optimization involving the least square criterion. The formation of the image block from the oriented models as well as the absolute orientation procedure were implemented using the Horn approach as a base algorithm. The second part of the paper is devoted to the tools and methods applied in the stereo digitization module. The solutions that support the user and improve the accuracy are given. Within the paper a few exemplary applications and products are mentioned. The work finishes with the concepts of development and improvements of existing functions.

3

Półautomatyczne modelowanie brył budynków na podstawie danych z lotniczego skaningu laserowego

Marjasiewicz M., Malej T

Archiwum Fotogrametrii, Kartografii i Teledetekcji

|

2014

|

Vol. 26

87--96

PL

Tematem artykułu jest badanie możliwości półautomatycznego generowania brył budynków na podstawie chmury punktów pochodzącej z lotniczego skaningu laserowego. Zaproponowana metodyka oparta została o algorytm RANSAC zaimplementowanym w oprogramowaniu Cloud Compare. Algorytm umożliwia wykrywanie płaszczyzn w danych obarczonych szumem pomiarowym, dlatego dobrze sprawdza się w przypadku skaningu laserowego. W badaniach wykorzystano dane dostępne w państwowym zasobie geodezyjnym i kartograficznym – tj. chmury punktów z lotniczego skaningu laserowego pochodzące z projektu Informatycznego Systemu Osłony Kraju oraz przyziemia brył budynków z Bazy Danych Obiektów Topograficznych. Do przygotowania modeli wykorzystano pakiet oprogramowania ArcGIS oraz program SketchUP. Dokładność metody modelowania oceniono na dwóch polach testowych o różnych gęstościach chmury punktów. Zaproponowana metodyka umożliwiła stworzenie modeli charakteryzujących się dokładnością wyższą niż poziom LoD2 CityGML.

EN

The main idea of this project is to introduce a conception of semi-automated method for building model extraction from Airborne Laser Scanning data. The presented method is based on the RANSAC algorithm, which provides automatic collection planes for roofs model creation. In the case of Airborne Laser Scanning, the algorithm can process point clouds influenced with noise and erroneous measurement (gross errors). The RANSAC algorithm is based on the iterative processing of a set of points in order to estimate the geometric model. Research of using algorithm for ALS data was performed in available Cloud Compare and SketchUP software. An important aspect in this research was algorithm parameters selection, which was made on the basis of characteristics of point cloud and scanned objects. Analysis showed that the accuracy of plane extraction with RANSAC algorithm does not exceed 20 centimeters for point clouds of density 4 pts./m2. RANSAC can be successfully used in buildings modelling based on ALS data. Roofs created by the presented method could be used in visualizations on a much better level than Level of Detail 2 by CityGML standard. If model is textured it can represent LoD3 standard.

4

Using RANSAC for 3D point cloud segmentation

Luchowski L., Kowalski P.

Theoretical and Applied Informatics

|

2013

|

Vol. 25, No. 2

105--117

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).

5

Wieloobrazowe dopasowanie zdjęć bliskiego zasięgu do automatycznej rekonstrukcji fotorealistycznych modeli 3D

Zawieska D.

Prace Naukowe Politechniki Warszawskiej. Geodezja

|

2013

|

z. 50

5--96

PL

Modelowanie obiektu, wykorzystujące obrazy cyfrowe, zostało zdefiniowane jako kompletny proces rozpoczynający się pozyskaniem obrazów, a kończący utworzeniem interaktywnego, wirtualnego modelu 3D. Teza, jaką przyjęto w niniejszej rozprawie, opiera się na założeniu, że przez dobór odpowiednich algorytmów przetwarzania obrazów cyfrowych, wykorzystywanych w środowisku fotogrametrycznym i widzeniu maszynowym (CV), umożliwia wieloobrazowe, automatyczne dopasowanie obrazów cyfrowych bliskiego zasięgu, w celu wykonania automatycznej rekonstrukcji foto realistycznych modeli 3D wybranych obiektów. Na podstawie przeglądu literatury krajowej i zagranicznej przeprowadzono analizę rozwiązań istniejących systemów pomiarowych, wykorzystywanych do modelowania 3D w fotogrametrii bliskiego zasięgu. W analizie uwzględniono takie czynniki, jak stopień automatyzacji pomiarów, liczbę, geometrię oraz jakość wykorzystywanych obrazów cyfrowych. Dokonano studium literaturowego dotyczącego charakterystyki przetwarzania obrazów, w szczególności obejmującego problematykę automatycznej detekcji narożników (punktów charakterystycznych) oraz modelowania 3D obiektów bliskiego zasięgu. Na podstawie przeprowadzonych analiz, wyodrębniono operatory, które mogą być wykorzystane dla automatycznego wykrywania punktów charakterystycznych obiektu, odwzorowanego na obrazach cyfrowych: Morayeca, Harrisa, Trajkoyica, SUSAN (ang. Smallest Univalue Segment Assimilaling Nucleus), SIFT (ang. Scale Invariant Feature Transform). Dokonano przeglądu algorytmów automatycznego dopasowywania obrazów, ze szczególnym uwzględnieniem metody ABM (ang. Area Base Matching), zintegrowanej z algorytmami stosowanymi w widzeniu maszynowym (ang. Computer Vision). Jako wynik szerokich analiz teoretycznych i eksperymentalnych, do automatycznego generowania przestrzennej chmury punktów zaproponowano ostatecznie następujący pakiet algorytmów: do wykrywania punktów charakterystycznych na obrazach cyfrowych - operator SUSAN; do do pasowywanla obrazów cyfrowych - metody ABM/lmage Dislance (opcjonalnie, w zależności od liczby wykrytych punktów na obrazie cyfrowym), ABM/CC, ABM/LSM; do obliczania tensora, na podstawie dopasowanych punktów charakterystycznych - algorytm RANSAC (ang. Random Simple Consensus). Przeprowadzone analizy i eksperymenty pozwoliły zdefiniować warunki dotyczące geometrii zdjęć, oświetlenia, jakości tekstury obiektu oraz rozdzielczości i formatu obrazu cyfrowego do opracowania autorskiego pakietu algorytmów do automatycznego generowania modeli 3D wybranych obiektów bliskiego zasięgu. Zaprojektowano modułową strukturę prototypu oprogramowania, 2 których każdy realizuje inny etap generowania modelu 3D. Udowodniono, ze dobierając algorytmy wielo obrazowego przetwarzania obrazów cyfrowych, stosowane w środowisku fotogrametrycznym i widzeniu maszynowym, można automatycznie generować powierzchnie wybranych modeli 3D bliskiego zasięgu.

EN

Modelling objects using digital images has been defined as a complete process which starts from image acquisition and is completed by creation of a virtual 3D model. The thesis which has been assumed for the present work is based on the assumption that by using specially selected algorithms applied in photogrammetry and in computer vision (CV), it is possible to perform multi-image, automatic, digital matching of close range images, in order to automatically reconstruct photorealistic 3D models of selected objects. Basing on reviews of Polish and foreign publications, an analysis of existing measuring systems has been performed, which are applied for 3D modelling in close range photogrammetry, The performed analyses considered such factors as: measurement automation level, the number, geometry and quality of applied digital images. The study of publications concerning image processing characteristics, with particular attention paid to automatic detection of corners (characteristic points), as well as 3D modelling of close range objects, has been performed. The analyses allow to select the following algorithms which might be applied for automatic detection of characteristic points of an object, visible on digital images: Moravec, Harris, Trajkovic, SUSAN (Smallest Univalue Segment Assimilating Nucleus), SIFT (Scale Invariant Feature Transform). Algorithms for automatic image matching, with particular consideration of the ABM (Area Base Matching) method, integrated with algorithms applied in computer vision, have also been reviewed. As a result of comprehensive theoretical and experimental analyses, the following package of algorithms has been finally proposed for automatic generation of a spatial point cloud: for detection of characteristic points on digital images - SUSAN algorithm; for digital image matching - successive utilization of the ABM/Image Distance method (as an option, depending on the number of points detected in me digital image), the ABM/CC, ABM/LSM method; for tensor calculations basing on matched characteristic points it is proposed to apply the RANSAC (Random Simple Consensus) algorithm. The performed analyses and experiments allow to define conditions related to image geometry, illumination, texture quality, as well as resolution and formats of digital images with respect to development of the author's package of algorithms for automatic generation of 3D models of selected close range objects. A modular structure of prototype software has been designed, in which every module performs successive stages of the 3D model generation. It was also proved that - after selection of appropriate algorithms of multi-image digital image processing, applied in photogrammetry and computer vision - it is possible to automatically generate surfaces of selected 3D close range models.

6

Segmentacja danych MLS z użyciem procedur Point Cloud Library

Grochowska M.

Archiwum Fotogrametrii, Kartografii i Teledetekcji

|

2013

|

Vol. 25

67--76

PL

Mobilny skaning laserowy jest dynamicznie rozwijającą się technologią pomiarową, która staje się coraz bardziej powszechna w zakresie pozyskiwania trójwymiarowej informacji przestrzennej. W artykule przedstawiono wstępne wyniki segmentacji danych pozyskanych techniką MLS. Dane użyte w niniejszej pracy pozyskano w ramach pomiaru inwentaryzacyjnego infrastruktury linii kolejowej na odcinku Warszawa Zachodnia – Rembertów. Pomiar chmury punktów zrealizowano za pomocą zespołu skanerów profilowych zainstalowanych na platformie kolejowej. Proces segmentacji wykonano przy zastosowaniu narzędzi programu ‘open source’ Point Cloud Library. Wykorzystano szablony biblioteki PCL, która zawiera algorytmy segmentacji do odrębnych klasterów. Algorytmy te są najlepiej dostosowane do przetwarzania chmury punktów, składającej się z określonej liczby izolowanych przestrzennie regionów. Szablon biblioteki wykonuje ekstrakcję klastra w oparciu o dopasowanie modelu poprzez metody konsensusu próbek dla różnych parametrycznych modeli (płaszczyzny, walce, kule, linie, itp.). Większość operacji matematycznych jest realizowana na podstawie biblioteki Eigen, zbioru szablonów algebry liniowej. W niniejszym referacie przedstawiono szereg zagadnień związanych z zastosowaniem oprogramowania PCL i jego możliwościami.

EN

Mobile laser scanning is dynamically developing measurement technology, which is becoming increasingly widespread in acquiring three-dimensional spatial information. Continuous technical progress based on the use of new tools, technology development, and thus the use of existing resources in a better way, reveals new horizons of extensive use of MLS technology. Mobile laser scanning system is usually used for mapping linear objects, and in particular the inventory of roads, railways, bridges, shorelines, shafts, tunnels, and even geometrically complex urban spaces. The measurement is done from the perspective of use of the object, however, does not interfere with the possibilities of movement and work. This paper presents the initial results of the segmentation data acquired by the MLS. The data used in this work was obtained as part of an inventory measurement infrastructure railway line. Measurement of point clouds was carried out using a profile scanners installed on the railway platform. To process the data, the tools of ‘open source' Point Cloud Library was used. These tools allow to use templates of programming libraries. PCL is an open, independent project, operating on a large scale for processing 2D/3D image and point clouds. Software PCL is released under the terms of the BSD license (Berkeley Software Distribution License), which means it is a free for commercial and research use. The article presents a number of issues related to the use of this software and its capabilities. Segmentation data is based on applying the templates library pcl_segmentation, which contains the segmentation algorithms to separate clusters. These algorithms are best suited to the processing point clouds, consisting of a number of spatially isolated regions. Template library performs the extraction of the cluster based on the fit of the model by the consensus method samples for various parametric models (planes, cylinders, spheres, lines, etc.). Most of the mathematical operation is carried out on the basis of Eigen library, a set of templates for linear algebra.

7

Automatyczna rekonstrukcja modeli 3D małych obiektów bliskiego zasięgu

Zawieska D.

Archiwum Fotogrametrii, Kartografii i Teledetekcji

|

2013

|

Vol. 25

295--302

EN

Reconstruction of three-dimensional, realistic models of objects from digital images has been the topic of research in many areas of science for many years. This development is stimulated by new technologies and tools, which appeared recently, such as digital photography, laser scanners, increase in the equipment efficiency and Internet. The objective of this paper is to present results of automatic modeling of selected close range objects, with the use of digital photographs acquired by the Hasselblad H4D50 camera. The author's software tool was utilized for calculations; it performs successive stages of the 3D model creation. The modeling process was presented as the complete process which starts from acquisition of images and which is completed by creation of a photorealistic 3D model in the same software environment. Experiments were performed for selected close range objects, with appropriately arranged image geometry, creating a ring around the measured object. The Area Base Matching (CC/LSM) method, the RANSAC algorithm, with the use of tensor calculus, were utilized form automatic matching of points detected with the SUSAN algorithm. Reconstruction of the surface of model generation is one of the important stages of 3D modeling. Reconstruction of precise surfaces, performed on the basis of a non-organized cloud of points, acquired from automatic processing of digital images, is a difficult task, which has not been finally solved. Creation of poly-angular models, which may meet high requirements concerning modeling and visualization is required in many applications. The polynomial method is usually the best way to precise representation of measurement results, and, at the same time, to achieving the optimum description of the surface. Three algorithm were tested: the volumetric method (VCG), the Poisson method and the Ball pivoting method. Those methods are mostly applied to modeling of uniform grids of points. Results of experiments proved that incorrect utilization of these methods results in various artifacts and deformations of models. After generation of a triangular grid of the modeled surface, results were visualized using the shading methods and texturing of the cloud of points. The accuracy of obtained reconstructions of the model surface equaled bellow 1 mm.

PL

Celem niniejszego artykułu jest prezentacja wyników automatycznego modelowania wybranych obiektów bliskiego zasięgu (głowa manekina, kamień) z wykorzystaniem obrazów cyfrowych z aparatu Hasselblad H4D50. Do obliczeń wykorzystano autorski program, realizujący kolejne etapy tworzenia modelu 3D. Proces modelowania został zaprezentowany jako kompletny proces rozpoczynający się od pozyskania obrazów, który jest ukończony wraz z utworzeniem fotorealistycznego modelu 3D, w tym samym środowisku programowym. Eksperymenty przeprowadzono na wybranych obiektach bliskiego zasięgu, z odpowiednio wykonaną geometrią zdjęć, tworzących pierścień (okrąg) wokół mierzonego obiektu. Do automatycznego dopasowania punktów, wykrytych algorytmem SUSAN, wykorzystano metodę Area Base Matching (CC/LSM), algorytm RANSAC wykorzystując rachunek tensorowy. Rekonstrukcja powierzchni generowania modelu jest jednym z bardzo ważnych etapów modelowania 3D. Rekonstrukcja precyzyjnych powierzchni na podstawie nieregularnej chmury punktów uzyskanych z automatycznego opracowania obrazów cyfrowych jest zagadnieniem otwartym. Tworzenie wielokątnych modeli, które mogą sprostać wysokim wymaganiom w zakresie modelowania i wizualizacji, potrzebne jest w wielu aplikacjach. Metoda wielokątów jest zwykle idealna drogą do dokładnego reprezentowania wyników pomiarów, a jednocześnie do uzyskania optymalnego opisu powierzchni. Przetestowano trzy algorytmy: metodę objętościową (VCG), metodę Poissona i metodę Ball Pivoting. Metody te są najczęściej stosowane do modelowania jednorodnej siatki punktów. Wyniki eksperymentów wykazały, że niewłaściwe zastosowanie tych metod powoduje różne artefakty i zniekształcenia powierzchni modelu. Po utworzeniu siatki trójkątów modelowanej powierzchni, wyniki zwizualizowano wykorzystując metodę cieniowania oraz teksturowanie chmury punktów. Dokładność uzyskanej rekonstrukcji powierzchni modelu uzyskano z poniżej 1 mm.

8

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

Poręba M., Goulette F.

Archiwum Fotogrametrii, Kartografii i Teledetekcji

|

2012

|

Vol. 24

301--310

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.

9

Implementacja w układzie reprogramowalnym wieloprocesorowego systemu realizującego algorytm RANSAC

Fularz M., Kraft M.

Pomiary Automatyka Kontrola

|

2011

|

R. 57, nr 8

914-916

PL

W artykule opisano programową, wieloprocesorową realizację algorytmu RANSAC, który umożliwia odporną estymację modelu matematycznego z danych pomiarowych zawierających znaczący odsetek wartości odstających (ang. outliers). System został zaimplementowany w układzie FPGA w oparciu o konfigurowalne soft procesory MicroBlaze. W pracy przedstawiono opis algorytmu RANSAC, sposób jego podziału w celu przetwarzania równoległego, a także proces konfiguracji systemu wieloprocesorowego. Zaprezentowano również przyrost prędkości przetwarzania w zależności od liczby zastosowanych rdzeni procesorowych, porównano te wyniki do realizacji na komputerze klasy PC i przedstawiono zużycie zasobów układu FPGA.

EN

The paper describes a multiprocessor system implementing the RANSAC algorithm [3] which enables robust estimation of a fundamental matrix from a set of image keypoint correspondences containing some amount of outliers. The fundamental matrix encodes the relationship between two views of the same scene. The knowledge of the fundamental matrix enables e.g. the reconstruction of the scene structure. The implemented system is based on three MicroBlaze microprocessors [5] (one master, two slaves) and a dedicated hardware coprocessor connected using fast simplex link (FSL) interfaces [6]. The slave microprocessors perform the task of fundamental matrix computation from point correspondences using singular value decomposition - the so called 8-point algorithm [1, 2] (hypothesis generation). The master processor, along with the connected coprocessor, is responsible for dataflow handling and hypothesis testing using the Sampson error formula (7). The hypothesize and test framework used in RANSAC allows for largely independent task execution. The design is a development of a system described in [5]. The block diagram and dataflow diagram of the proposed solution are given in Figs. 1 and 2, respectively. Tabs. 1 and 2 summarize the use of FPGA resources. With a 100 MHz clock, the designed system is capable of processing the data at the speed which is roughly equivalent to that of the Atom N270 microprocessor clocked at 1,2 GHz. The resulting solution will be targeted at applications for which small size, weight and power consumption are critical. The design is also easily scalable - addition of more slave processors will result in additional increase in the processing speed.

10

Sprzętowo-programowa realizacja algorytmu RANSAC do estymacji macierzy fundamentalnej

Kraft M.

Pomiary Automatyka Kontrola

|

2010

|

R. 56, nr 7

742-744

PL

W artykule opisano hybrydową, sprzętowo-programową realizację algorytmu RANSAC, umożliwiającego odporną estymację modelu matematycznego z danych pomiarowych zawierających znaczący odsetek wartości odstających (ang. outliers). Zaimplementowany system, oparty o mikroprocesor Microblaze wraz z dedykowanymi procesorami sprzętowymi, wykorzystywany jest do estymacji macierzy fundamentalnej. W macierzy tej zakodowany jest związek pomiędzy dwoma obrazami tej samej sceny, a jej znajomość umożliwia m. in. rekonstrukcję struktury sceny. Praca zawiera krótki opis algorytmu RANSAC, opis realizacji algorytmu w układzie FPGA, oraz podsumowanie użytych do implementacji zasobów. Przeprowadzono również porównanie szybkości działania implementacji programowej oraz sprzętowo-programowej algorytmu na procesorze Microblaze, oraz implementacji programowej na komputerze PC wyposażonym w energooszczędny procesor.

EN

The paper describes hybrid, hardware/software implementation of RANSAC algorithm, enabling the robust mathematical model estimation from measurement data containing a significant amount of outliers. The implemented system, based on the Microblaze microprocessor along with a dedicated hardware coprocessor, performs the task of fundamental matrix estimation. The matrix encodes the relationship between two views of the same scene. This enables e.g. the reconstruction of the scene structure. The system (implemented in a Virtex 5 PFGA) is capable of working with a clock speed of 100MHz. Applying the hardware coprocessor cuts the overall algorithm execution time by approximately half. The part of the algorithm that was chosen for hardware implementation (checking the consistency of measurement data with the computed model) is sped up 50 times when compared to software implementation. The resource usage is kept low by using a custom 23-bit floating point representation (see Fig. 2). Table 1 presents the summary of resources used for implementation. Fig. 1 outlines the system architecture, while Figs. 3 and 4 present the detailed coprocessor structure. The 8-point algorithm based model generation is harder to translate into hardware, because it relies on singular value decomposition for finding least-squares solution of a linear system of equations [1][2]. The future work will therefore be focused on this subject, and on integration of the described system with the processor for image feature detection [3], description and matching. The resulting solution will be targeted at applications, in which small size, weight and power consumption are critical.

11

Porównanie algorytmów RANSAC oraz rosnących płaszczyzn w procesie segmentacji danych lotniczego skaningu laserowego

Jarząbek-Rychard M., Borkowski A.

Archiwum Fotogrametrii, Kartografii i Teledetekcji

|

2010

|

Vol. 21

119--129

PL

W ostatnich latach, wraz z osiągnięciem zdolności operacyjnej i wzrostem dostępności lotniczego skanowania laserowego (LIDAR) nastąpiło również zwiększenie zainteresowania opracowaniami 3D tworzonymi na podstawie danych pozyskanych z wykorzystaniem tej techniki. Jednym z centralnych zagadnień modelowania geoinformacji na podstawie danych LIDAR jest modelowanie zabudowy. W modelowaniu tym główny nacisk kładzie się na automatyzację procesów. Dostępne oprogramowanie komercyjne charakteryzuje się bowiem znacznym poziomem interaktywności – tworzenie modelu wymaga dużego udziału operatora. W procesie trójwymiarowego modelowania zabudowy wyróżnia się na ogół cztery podstawowe etapy, przy czym kluczowym wydaje się etap polegający na segmentacji punktów należących do budynku. W procesie tym ze zbioru zawierającego zarówno punkty obarczone błędami przypadkowymi jak i grubymi wyodrębniane zostają podzbiory punktów reprezentujących (modelujących) poszczególne płaszczyzny. Wynika to z faktu, iż budynki formowane są najczęściej jako kombinacja płaszczyzn w przestrzeni 3D. W pracy przedstawiono analizę dwóch, najczęściej wykorzystywanych w celu segmentacji algorytmów: RANSAC i rosnących płaszczyzn, przy czym w tym ostatnim, wprowadzono modyfikacje, uwzględniające topologię w zbiorze danych. Podano podstawowe informacje dotyczące omawianych metod. Testy numeryczne wykonano z wykorzystaniem zarówno syntetycznych jak i rzeczywistych danych skaningu laserowego. W wyniku przeprowadzonych eksperymentów można stwierdzić, że algorytm RANSAC charakteryzuje się krótkim czasem wykonania segmentacji dla nieskomplikowanych modeli. Potrafi jednak łączyć ze sobą odrębne w rzeczywistości obiekty leżące w tej samej płaszczyźnie; dobrze nadaje się do segmentacji standardowych dachów, złożonych z małej liczby elementów. Algorytm rosnących płaszczyzn jest bardziej odpowiedni dla modeli o większym stopniu skomplikowania. Poprawnie rozdziela odrębne obiekty leżące w tej samej płaszczyźnie. Czas wykonania zależy głównie od liczby punktów w zbiorze – nie zależy od liczby wyodrębnianych płaszczyzn.

EN

In recent years, the LIDAR technique has undergone fast development. The increasing access and operating ability caused a growing interest in 3D processing of data acquired by LIDAR. One of the main tasks of geo-information modeling is to create virtual city models. As the available commercial softwares require a high level of user interactivity, the crucial issue of modeling is its automation. There are four main steps that comprise virtual building extraction. One of them, building point cloud segmentation, appears to be the core part of the whole modeling process. Segmentation allows partitioning of a data set, that contains points biased by random and gross errors, into smaller sets which represent different planes. This arises from the fact, that buildings are formed by a combination of planes in 3D space. The paper presents an analysis of two algorithms that are most commonly applied to segmentation: RANSAC and plane growing. The latter is modified, taking into consideration topology between points. The essential information about both algorithms is presented. Numerical tests based on synthetic and real laser scanning data are executed. It is inferred from the experiments that the RANSAC algorithm features short time performance for simple models. However, at times it merges different objects lying in the same plane. The algorithm is suited well for segmentation of standard roofs that contain small number of elements. The plane growing algorithm is more suitable for more complicated models. It separates different objects situated in the same plane. Time performance depends mostly on the number of points within a data set; it is not affected by the number of identified planes.

12

Wyznaczanie parametrów dystorsji kamery na podstawie zdjęć obiektów naturalnych i korekcja zdjęć

Podlasiak P.

Archiwum Fotogrametrii, Kartografii i Teledetekcji

|

2004

|

Vol. 14

1--8

PL

W referacie omówiono sposoby wyznaczenia parametrów dystorsji zdjęć wykonanych niedrogimi kamerami cyfrowymi. Do wyznaczania tych parametrów mogą zostać wykorzystane pojedyncze zdjęcia, obiektów dla których nie jest znana informacji o rzeczywistych współrzędnych 3D. Omówiono metody wykorzystują zniekształcenie odwzorowania obiektów liniowych. Przedstawiono kilka metod znajdowania parametrów dystorsji. W dalszej części omówione zostały problemy związane z korekcją zdjęć (usuwaniem zniekształceń wywołanych dystorsją).