Nokta bulutlarının otomatik birleştirilmesinde yeni bir yöntem önerisi
A new method for automatic point cloud registration
Yazar: RAMAZAN ALPER KUÇAK
Danışman: DOÇ. DR. SERDAR EROL
İstanbul Teknik Üniversitesi / Lisansüstü Eğitim Enstitüsü / Geomatik Mühendisliği Ana Bilim Dalı / Geomatik Mühendisliği Bilim Dalı
Derece: Doktora, 2021
Konu: Jeodezi ve Fotogrametri = Geodesy and Photogrammetry ; Mühendislik Bilimleri = Engineering Sciences
Dizin: Üç boyutlu dengeleme = Three dimensional adjustment

Özet:
Nokta bulutlarının birleştirilmesi geomatik, makine, inşaat mühendisliği ve mimarlık disiplinlerinin uygulama alanları için çok büyük bir öneme sahiptir. Nesnelerin bir bütün olarak veya nesneler üzerindeki detayların daha gerçekçi olarak modellenebilmesi için farklı konumlardan veya farklı çözünürlüklü tarayıcılardan elde edilen nokta bulutlarının birleştirilmesi gerekmektedir. Günümüzde kültürel mirasların dokümantasyonu, Coğrafi Bilgi Sistemi (CBS) veya 3B şehir modelleme gibi birçok alanda nokta bulutları yaygın olarak kullanılmaktadır. Bu alanlarda, nokta bulutları kullanılarak gerçekleştirilecek çalışmalarda, doğruluğu yüksek nokta bulutları ile çalışmak, 3B modelleme çalışmaları için oldukça önemlidir. Nokta bulutlarının modellenmesinde fazla sayıda nokta bulutu verilerinden ziyade; verinin modellenebilmesi için yeterli olacak nokta bulutunun ve yüksek doğrulukta noktaların kullanılması çok daha önemlidir. Bu sebeple, modelleme için kullanılacak nokta bulutu verisi için öncelikle bilinmesi gereken, verinin bütünlüğünün ve doğruluğunun araştırılması olmalıdır. Veri bütünlüğünü ve doğruluğunu artırmak için de, ya verinin çözünürlüğü artırılmalıdır, ya da gerektiği durumlarda doğruluk analizleri yapılmalıdır. Elde edilen sonuçlara göre de nokta bulutlarını birleştirme ve enterpolasyon işlemlerinin yapılması daha doğru çalışmaların yapılmasının önünü açacaktır. 
Doğruluğun ya da çözünürlüğün önemli olduğu nokta bulutu modelleme çalışmalarında, verinin analizleri yapıldıktan sonra; mevcut nokta bulutunun doğruluk ve çözünürlük açısından yeterli olduğu düşünülüyor ise birleştirme ya da modelleme aşamalarına geçilebilir. Fakat, mevcut nokta bulutunda istenilen yüzey verisi eksikse veya nokta bulutu yeterli doğruluk ve çözünürlüğe sahip değil ise; mevcut nokta bulutundan daha yüksek doğruluklu bir nokta bulutu üretip mevcut sisteme entegre etmek; üç boyutlu (3B) yüzeyler için yapılacak enterpolasyon ya da modelleme işlemleri için daha doğru bir yaklaşım olacaktır. Bu tez çalışmasında; farklı veya aynı sistemlerden üretilen 3B nokta bulutlarının otomatik olarak birleştirilmesi ve böylece objelerin 3B modellerinin hassas olarak oluşturulması amaçlanmaktadır. Böylece 3B modelleme çalışmalarında daha doğru modellerin üretilmesi ve enterpolasyon ile yüzey geçirme işlemlerinin daha hassas olarak elde edilebilmesine bir katkı sağlanması hedeflenmektedir.
Nokta bulutlarının birleştirme işlemi üç aşamadan oluşmaktadır: Öncelikle, nokta bulutları içerisindeki anahtar noktaların bulunması, tanımlanması ve nokta bulutları arasında eşlenmesi gerekmektedir. Daha sonra, elde edilen eşlenik noktalar yardımıyla nokta bulutlarının ilk hizalaması yapılır ve son olarak hassas birleştirme işlemine geçilir. İlk birleştirme işlemi, nokta bulutlarının kabaca hizalanması için tercih edilir ve ayrıca hassas birleştirme işlemi de etkili bir ilk hizalama ile başlamaktadır. 
Anahtar nokta belirleme ve tanımlama algoritmaları genellikle resim-görüntü tabanlı (RGB) veriler ile çalışmaktadır, sadece XYZ kartezyen koordinatları kullanan çok az sayıda anahtar nokta belirleme ve tanımlama algoritması bulunmaktadır. Bu tez çalışmasında, nokta bulutlarının ilk hizalanması ve tam birleştirilmesi için, yeni bir otomatik anahtar nokta tanımlama ve eşleştirme yaklaşımı önerilmiştir. Burada sunulan yeni yaklaşım, intensity (Lazerin yüzeyden yansıma enerjisi) ya da RGB gibi yansıtım değerleri ile değil, sadece XYZ koordinatlarına sahip herhangi bir nokta bulutu için uygulanabilmektedir. Çalışmada, öncül birleştirme için burada önerilen otomatik anahtar nokta tanımlama ve eşleme yaklaşımı uygulanmıştır ve sonrasında ise, dönüşüm parametrelerinin tahmini için 3B Helmert Benzerlik Dönüşümü kullanılmıştır. Ayrıca nokta bulutlarının tam birleştirilmesi için İteratif En Yakın Nokta (İEYN) Algoritması kullanılmıştır. Dönüşüm parametrelerinin tahmini, ilk birleştirmeye başlamak için en kritik aşamadır. 
Bu çalışmada önerilen otomatik tanımlama ve eşleme algoritmasında, birleştirilecek her nokta bulutu öncelikle uygun eğriliklere göre filtrelenmiştir. Ardından, her nokta bulutu için elde edilen anahtar noktalar kendi aralarındaki açı kosinüs ve mesafe değerlerine göre tanımlanmıştır. Sonrasında, her nokta bulutunda tanımlanan anahtar noktalar karşılıklı olarak birbirleriyle eşlenmiştir. Elde edilen eşlenik noktalar yardımıyla nokta bulutlarının İEYN öncesi ilk hizalaması için 3B Benzerlik Dönüşümü parametrelerinin hesaplanmasında büyük açılı ve küçük açılı Gauss-Markov ve Gauss-Helmert dengeleme modelleri kullanılmıştır. Ayrıca, ilk hizalama için dönüşüm parametrelerinin hesaplanması aşamasında, eşlenik noktalar eğrilik değerlerine göre gruplara ayrılmış ve ölçü gruplarının öncül varyans değerleri, Varyans Bileşen Tahmini (VBT) uygulanarak belirlenmiş ve daha sonra İEYN ile hassas birleştirme gerçekleştirilmiştir.
Tez çalışmasında önerilen algoritmayı literatürdeki diğer yöntemlerle karşılaştırmak için, 3 farklı veri seti kullanılmıştır. İstanbul Teknik Üniversitesi (İTÜ) Ayazağa Kampüsü'nde yer alan Yılmaz Akdoruk Öğrenci Yurdunun tüm cepheleri Riegl VMX 450 LiDAR Sistemi ve Leica C10 yersel lazer tarayıcı ile taranmıştır. İki farklı tarama sisteminden elde edilen bina ön cephesine ait yersel statik ve mobil LiDAR verileri üzerinde, önerilen yöntem uygulanarak iki farklı lazer tarama verisi birleştirilmiştir. Diğer veri setleri ise, küçük nesnelerin modellenmesi ve endüstriyel amaçlı ölçmelerde de çok sık kullanılan lazer tarayıcılardan elde edilen "Aristo heykeli" ve "Stanford Tavşan" verileridir. Tavşan verisi, Stanford Üniversitesi Bilgisayar Grafik Laboratuvarına ait bir "Cyberware 3030 MS" tarayıcı ile taranan Stanford Modeli olarak bilinir. Stanford Tavşan verileri genellikle literatürdeki anahtar nokta eşleştirme algoritmaları için örnek bir model olarak kullanılır. Aristo heykeli ise İTÜ Geomatik Mühendisliği Ölçme laboratuvarında, "Next Engine 3D Ultra HD" tarayıcı ile taranmış nokta bulutu verisidir. Bu nesnelere ait lazer tarama verileri de önerilen algoritma uygulanarak birleştirilmiş ve 3B modeller elde edilmiştir. 
Sonuç olarak, önerilen yöntem algoritmik olarak gerçeklenmiş, bahsedilen veri setlerinde uygulanmış ve bu yöntemin eksik ve üstün yönlerini ortaya çıkarmak için literatürde mevcut olarak kullanılan anahtar nokta tanımlama ve eşleme yöntemleri ile karşılaştırılmıştır. Bu çalışmada kullanılan yöntemler; 3B dönüşümün doğruluğu, dönüşüm parametrelerinin Ortalama Hata (OH) değerleri ve İEYN algoritmasının ilk ve son OH değerlerine göre değerlendirilmiştir. Gerçekleştirilen karşılaştırmalı analizler sonucunda, önerilen algoritma ile daha iyi OH değerlerine ulaşılırken, diğer algoritmalarda da (ISS+PFH ve LSP+PFH) anlamlı OH değerlerine ulaşılmıştır. Fakat bazı verilerde diğer algoritmalar ile eşlenik nokta bulunamadığından, İEYN algoritması için anlamlı bir sonuç gözlemlenememiştir. Kullanılan veriler ve karşılaştırılan yöntemlere göre, önerilen algoritma daha iyi bir ilk hizalama sonucu verdiği için, İEYN uygulandıktan sonra daha başarılı modeller oluşturulmuştur. Bu çalışmada, önerilen yöntemin, otomatik nokta eşleme literatürüne katkısı, uygulamalar ve farklı veri tipleri kullanılarak irdelenmiştir, daha doğru ve hassas 3B modellerin üretilebilmesine sağladığı katkı görülmüştür.

Abstract:
The registration of point clouds is very important for geomatics engineering and other (such as machinery and construction) engineering and architectural applications. In order to model the objects as a whole or the details on the objects more realistically, point clouds obtained from different positions or different scanners should be combined. For this reason, working with high accuracy point clouds is the basis rather than more data in the modeling of point clouds. Therefore, the use of high precision and sufficient point clouds for data modeling is very important. Various filtering methods can be applied for modeling, interpolation and surfacing operations; however, if the data are missing or incorrectly measured, modeling or interpolating of the data is always a problem. To complete this deficiency; either the resolution of data should be increased, or the accuracy analysis of point clouds should be done. According to the obtained results, combining the point clouds and performing the interpolations will pave the way for more robust works.
Working with high-accuracy points and enough data to model objects is a very important issue for point cloud studies. In point cloud studies, besides accuracy, the resolution is also important. If the point clouds are sufficient for the desired works, the registration or modeling steps can be started. However, if the desired surface data in the existing point cloud is missing, accuracy and resolution are insufficient; it will be a more appropriate approach to the combination of the existing point cloud with a more accurate and high resolution point cloud. For example, airborne Light Detection and Ranging (LiDAR) cannot collect detailed data from the facades of buildings and under the motorway bridges or in the restoration of historical monuments, and point cloud modeling has many problems on detailed surfaces. Therefore, it must be merged with point clouds produced from a different platform or a terrestrial LiDAR…etc. Supporting this type of data with different point cloud data is of great importance to increase the accuracy and resolution of the 3D model. The accuracy of 3D modeling, interpolation and surface fitting is related to how accurately the point clouds are registered. This study proposed and tested a new different approach for automatic keypoint detecting and matching in coarse registration of the point clouds before fine registration using the iterative closest point (ICP) algorithm. Hence, contributing to the quality improvement of the 3D model obtained through the fine registration process, which is carried out using the ICP method, was aimed.
The registration process of point clouds consists of three steps: First, key points in point clouds need to be determined, defined and matched. Then, with the help of the obtained conjugate points, the coarse registration of the point clouds is achieved and finally the fine registration process is started. Initial alignment is preferred for coarse registration of point clouds, and fine registration also starts with an efficient initial alignment.
Key point detection and descriptor algorithms generally work based on RGB, there are few detection and descriptor algorithms that work with Cartesian coordinates. The presented new approach works for any point cloud that has only XYZ coordinates, not reflectivity values such as intensity (laser reflection energy) or RGB. But; like any algorithm, the proposed algorithm has also advantages and disadvantages. The main contribution of this thesis is to propose a new automatic keypoint descriptor and matching method to register point clouds. For this reason, in this study, the automatic new keypoint matching approach was used for initial registration. Besides, the ICP (Iterative Closest Point) algorithm was preferred for fine registration and 3D Similarity Transformation for parameter estimation was used. In the proposed algorithm, the point clouds are firstly filtered and segmented according to optimum curvatures. Then, the key points of point clouds are identified and matched according to angle cosines and distances values. Later, transformation parameters are automatically calculated for coarse registration with Gauss Markov and Gauss Helmert adjustment models and fine registration is applied with ICP. 
In this study, Variance Component Estimation (VCE) theory is also applied. By applying VCE in the least squares adjustment (LSA) step to get the transformation parameters, the weights of the conjugate points are determined automatically and then fine registration is applied with ICP. As a result, to reveal the shortcomings and superior aspects of the algorithm, the method is compared with the previously used methods in the literature and the results are discussed.
In the tests of the point cloud registration algorithms, three datasets were used. The first dataset was obtained with the indoor measurements of Aristotle sculpture (approximate size: 6 cm  6 cm  10 cm) in Istanbul Technical University (ITU) Geomatics Engineering Department Surveying Laboratory. Next Engine 3D Laser Scanner Ultra HD was used in the scanning of the sculpture. The three dimensional accuracy of the scanner is 0.1 mm in macro mode, and 0.3 mm in wide mode. The second dataset used for testing the proposed algorithm is the bunny sculpture point clouds made available by the Stanford 3D scanning repository. The bunny data is known as one of the Stanford models, which was scanned with a Cyberware 3030 MS scanner at Stanford University Computer Graphics Laboratory. Cyberware 3030 MS scanner has 0.1 mm accuracy. This data is frequently used as sample model for testing keypoint matching algorithms in literature. Considering the size and accuracy of the used laser scanner, it is practical and cost-effective equipment for scanning in 3D model generation of small areas or object in industrial applications. The point cloud data obtained with scanning the southern facade of ITU Yilmaz Akdoruk guest-house building in Maslak Campus area is the third dataset in the study. The facades of the building were scanned using static terrestrial laser scanner (TLS) and mobile LiDAR system (MLS) techniques and the 3D models of the facades were generated by combining the point clouds data obtained from these two techniques. In TLS measurements, Leica ScanStation C10 terrestrial laser scanners with 4 mm distance measurement accuracy, 12 angle measurement accuracy and 6 mm point position accuracy (for single measurement), was used. Riegl VMX 450 mobile laser scanning system was used for MLS measurements of the building facades. In Riegl VMX-450 mobile LiDAR systems, two Riegl VQ-450 laser scanners with 8 mm position accuracy are integrated with IMU/GNSS unit.
As a result, the proposed method was implemented algorithmically, applied to the mentioned data sets, and compared with the key point identification and matching methods used in the literature to reveal the strengths and weaknesses of this method. The methods used in this study were evaluated according to the accuracy of the 3D transformation, the RMSE (Root Mean Squared Error) values of the transformation parameters, the first and last RMSE values of the ICP algorithm, and the number of iterations. As a result of the comparative analyzes performed, better RMSE values were achieved with the proposed algorithm, while significant RMSE values were achieved in other algorithms (ISS+PFH and LSP+PFH). However, since conjugate points could not be found in some data with other algorithms, a significant result could not be observed for the ICP algorithm. Since the proposed algorithm gives a better first alignment result according to the data used and the compared methods, more successful models have been created after the application of the ICP. In addition, the contribution of the proposed method to the automatic point matching literature for the 3D point cloud registration process has been examined using applications and different data types, and it has made a great contribution to the production of more accurate and sensitive 3D models.