Parallel implementation of hybridlCP data registration

• Autorzy: Będkowski J.

Warianty tytułu

PL

Implementacja algorytmu dopasowania danych hy-bridlCP z wykorzystaniem obliczeń równoległych

• Konferencja: Konferencja Techniki Próżni. 9 ; Workshop on Field Emission from Carbonaceous Materials ; 6-9.06.2011; Cedzyna, Polska
• Języki publikacji: EN

Abstrakty

EN

In the paper new implementation of 3D data registration algorithm based on combined point to point and point to plane ICP (lterative Closest Point) methods with an application of parallel computing is shown. Modern graphic processor unit with NVIDIACUDA technology is used for k-nearest neighbor search routine based on regular grid decomposition. Proposed method of 3D space decomposition guarantees shorter time of exeoution compared to classical approach k-d tree because of no need for complex data structure building, it offers comparable convergence. In the paper empirical evaluation of proposed algorithm is shown. It is based on data set delivered by mobile robot equipped with commercial available 3D laser measurement system working in INDOOR environment. Demonstrated experiments show potential practical application of parallel computing dedicated for On-Line computation

PL

W artykule przedstawiono nową implementacje algorytmu dopasowania dwóch chmur punktów 3D realizującą połączenie dwóch klasycznych metod - point to point oraz point to plane z zastosowaniem obliczeń równoległych. Wykorzystano nowoczesny procesor GPU (Graphic Procesor Unit) z technologią NVIDIA CUDA między innymi do realizacji procedury poszukiwania najbliższych sąsiadów (k-Nearest Neighbours k-NN) działającej na bazie dekompozycji przestrzeni 3D w regularną siatkę. Proponowana metoda dekompozycji przestrzeni 3D gwarantuje krótszy czas działania w porównaniu do klasycznego podejścia drzewa typu k-d (k-d tree) ze względu na brak potrzeby budowy skomplikowanej struktury danych, zapewniając jednocześnie porównywalną zbieżność algorytmu. W artykule przedstawiono empiryczne badanie algorytmu na bazie zbioru danych dostarczonych przez robota mobilnego wyposażonego w komercyjnie dostępny laserowy system pomiarowy 3D pracującego w środowisku IN-DOOR. Przedstawione eksperymenty pokazują potencjalne praktyczne zastosowanie obliczeń równoległych w aplikacjach działających w trybie On-Line

Słowa kluczowe

EN

mobile robot; data registration; parallel computing

PL

robot mobilny; dopasowanie danych; obliczenia równoległe

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Elektronika : konstrukcje, technologie, zastosowania
• Rocznik: 2011
• Tom: Vol. 52, nr 8
• Strony: 114--118
• Opis fizyczny: Bibliogr. 25 poz., il., wykr.

Twórcy

autor

Będkowski J.

• Instytut Maszyn Matematycznych, Warszawa

Bibliografia

• [1] Soon-Yong Park and Murali Subbarao: A fast point-to-tangent plane technique for multi-view registration. International Conference on 3D Digital Imaging and Modeling, 0:276, 2003.
• [2] Segal A., Haehnel D., and Thrun S.: Generalized-ICP. In Proceedings of Robotics: Science and Systems, Seattle, USA, June 2009.
• [3] Chen Y. and Medioni G.: Object modeling by registration of multiple range images, Proceedings of the IEEE Conference on Robotics and Automation, 1991.
• [4] Besl P. J. and McKay N. D.: A method for registration of 3D shapes, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.14, no.2, pp. 239-256, 1992.
• [5] Craig Robertson, Craig Robertson, and Robert B. Fisher: Parallel evolutionary registration of range data. Computer Vision and Image Understanding, 87:39-50, 2002.
• [6] Kaustubh Pathak, Andreas Birk, Narunas Vaskevicius, and Jann Poppinga: Fast registration based on noisy planes with unknown correspondences for 3-d mapping. Trans. Rob., 26:424-441, June 2010.
• [7] Minguez J., Montesano L., and Lamiraux F.: Metric-based iterative closest point scan matching for sensor displacement estimation, IEEE Trans. on Robotics, vol. 22, no. 5, pp. 1047-1054, 2005.
• [8] Minguez J., Armesto L., and Montesano L.: A generalization of the metric-based iterative closest point technique for 3d scan matching. In IEEE International Conference on Robotics and Automation, Alaska, USA, 2010.
• [9] Mitra N. J., Gelfand N., Pottmann H., and Guibas L.: Registration of point cloud data from a geometric optimization perspective. In Symposium on Geometry Processing, pages 23-31, 2004.
• [10] Armesto L., Montesano L., Minguez J.: Experimental methodology for benchmarking ICP-like algorithms Workshop on The Role of Experiments in Robotics Research at ICRA2010 (Anchorage, Alaska, USA, May 3, 2010).
• [11] Soon-Yong Park and Murali Subbarao: An accurate and fast point-to-plane registration technique. Pattern Recogn. Lett, 24:2967-2976, December 2003.
• [12] Helmut Pottmann, Stefan Leopoldseder and Michael Hofer. Registration without ICP. Computer Vision and Image Understanding, 95:54-71, 2002.
• [13] Pulli K.: Multiview registration for large data sets, Proc. Of 2nd Intn. Conf. on 3D Digital Imaging and Modeling, 1999.
• [14] Joaquim Salvi, Carles Matabosch, David Fofi, and Josep Forest: A review of recent range image registration methods with accuracy evaluation. Image Vision Comput., 25:578-596, May 2007.
• [15] Srikumar Ramalingam, Yuichi Taguchi, Tim K. Marks, and Oncel Tuzel: 2pi: A minimal solution for registration of 3d points to 3d planes. In ECCV (5), pages 436-449, 2010.
• [16] Deyuan Qiu, Stefan May, and Andreas Nuchter: GPU-accelerat-ed nearest neighbor search for 3d registration. In Proceedings of the 7th International Conference on Computer Vision Systems: Computer Vision Systems, ICVS'09, pages 194-203, Berlin, Heidelberg, 2009. Springer-Verlag.
• [17] Rusinkiewicz S. and Levoy M.: Efficient variants of the ICP algorithm. Proc. 3D Digital Imaging and Modeling, 145-152, 2001.
• [18] Nuchter A., Lingemann K., Hertzberg J.: Cached k-d tree search for ICP algorithms, in: Proceedings of the Sixth International Conference on 3-D Digital Imaging and Modeling. IEEE Computer Society, Washington, DC, USA, 2007, pp. 419-426.
• [19] Rusinkiewicz S., Levoy M.: Efficient variants of the ICP algorithm, in: Third International Conference on 3D Digital Imaging and Modeling (3DIM), 2001.
• [20] Qiu D., May S., Nuchter A.: GPU-accelerated nearest neighbor search for 3d registration, in: Proceedings of the 7th International Conference on Computer Vision Systems: Computer Vision Systems, ICVS '09, Springer-Verlag, Berlin, Heidelberg, 2009, pp. 194-203.
• [21] Arya S., Mount D. M.: Algorithms for fast vector quantization, in: Proc. of DCC '93: Data Compression Conference, IEEE Press, 1993, pp. 381-390.
• [22] Purcell T. J., Donner C., Cammarano M., Jensen H. W., Hanrahan P.: Photon mapping on programmable graphics hardware, in: Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware, Eurographics Association, 2003, pp. 41-50.
• [23] Garcia V., Debreuve E., Barlaud M.: Fast k nearest neighbor search using GPU, in: 2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, 2008, pp. 1-6.
• [24] Foley X, Sugerman J.: Kd-tree acceleration structures for a gpu raytracer, in: Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware. HWWS 05, ACM, New York, NY, USA, 2005, pp. 15-22.
• [25] Jensen H. W.: Realistic image synthesis using photon mapping, A. K. Peters, Ltd., Natick, MA, USA, 2001.