3B nokta bulutu için uyarlanabilir bir örtülü yüzey yeniden yapılandırma yöntemi
Son yıllarda tersine mühendislik, jeolojik arazi modelleme, akıllı şehirler, biyotıp vb. Alanlarda nokta bulutu yüzey rekonstrüksiyon teknolojisi pek çok araştırma ve geniş uygulama almıştır. Nokta bulutu yüzey rekonstrüksiyonunun özü, veri noktası modelinin yüzey modeline dönüşümünü gerçekleştirmektir. Örtük yüzey rekonstrüksiyonu, nokta bulutu modelinin yüzeyini karmaşık bir şekle daha iyi bir şekilde yeniden yapılandırabildiğinden, birçok bilim insanı çok fazla araştırma yapmıştır.
Literatürde önerilen radyal temel işlevli yüzey rekonstrüksiyon yöntemi, iyi yüzey detay özelliklerine sahiptir, ancak büyük miktarda veriye sahip bir nokta bulutu yeniden oluşturulurken, hesaplama miktarını hızla artıracak ve yüzey rekonstrüksiyonunun etkisini azaltacaktır.Ayrıca rekonstrüksiyonlar da vardır. Yüzey yeterince pürüzsüz değil. Literatürde önerilen metatabanı modelleme teknolojisine dayanan örtük yüzey yeniden yapılandırma algoritması, nesneleri keskin özellikler olmadan yaklaştırabilir, ancak kapalı olmayan modeller için deforme olacaktır. Literatürde önerilen elipsoid kısıtlamalarına dayanan örtük yüzey yeniden yapılandırma yöntemi, küçük ölçekli kapalı model nokta bulutları için etkilidir, ancak büyük ölçekli dağınık nokta bulutları için verimsizdir ve belirgin bir fazlalığa sahiptir. Literatürde önerilen özelliği koruyan örtük yüzey yeniden yapılandırma yöntemi önce nokta bulutu verilerinin sekizli topolojisini kurar, ardından yerel kuadrik yüzeyi çözer ve son olarak küresel bilinmeyen parametreleri çözer.Küçük ölçekli dağınık nokta bulutları için örnekleme noktasını ayarlayın Komşu noktaların sayısı daha iyi bir yeniden yapılandırma etkisi elde edebilir, ancak bilinmeyen miktarı elde etme sürecinde çok fazla insan müdahalesi vardır, çözüm külfetli ve verimlilik yüksek değildir. Literatür, orijinal nokta bulutunu bir sekizliye böler, kaba ve ince katman verilerini oluşturur ve ardından radyal tabanlı örtük yüzeyi yeniden oluşturur.Kapalı olmayan modelde bozulmalar olabilir ve kapalı nokta bulutu verilerinin kalitesi daha iyidir, ancak Ayar parametreleri, birden çok deney yoluyla yapay olarak seçilir ve akıllı hesaplama yapılamaz.
Yukarıdaki analize dayanarak, bu makale, büyük ölçekli dağınık nokta bulutları için örtük fonksiyon tabanlı uyarlamalı bir yeniden yapılandırma yöntemi önermektedir.İlk olarak, on binlerce noktayı ayrıştırmak ve işlemek için model yoğunluğuyla ilgili bölümlere ayrılmış alanın nokta bulutu verilerini sağlamak için uyarlanabilir bir oktree kullanılmıştır. Nokta bulutu; daha sonra, yerel yüzeyin düzgünlüğünü sağlamak için her bir alt bölgedeki radyal temel işlevine dayalı örtük bir metatabanı modeli oluşturun, metatabanı modeli örtük işlevini akıllıca çözmek için uyarlanabilir diferansiyel evrim algoritmasını kullanın; Logaritmik üstel ağırlıklı birleştirme algoritması, yüksek kaliteli bir genel yüzey modeli oluşturmak için kısmi yüzeyleri sorunsuz bir şekilde birleştirir.
1 Dağınık nokta bulutlarının segmentasyonu
Bilgisayardaki büyük miktarda veriyle dağınık nokta bulutu verilerinin yüzey rekonstrüksiyonunu gerçekleştirmek için, nokta bulutu modelinin üç boyutlu uzay sekizli yapısını oluşturmak için ayrılma ve özerklik fikri kullanılır. Bu yazıda, örnekleme noktası verileri, uydurulan yüzeyi elde etmek için girdi olarak kullanılmaktadır.Bilimlemenin son koşulu, hesaplama miktarını artıracağı ve algoritmanın verimliliğini azaltacağı için, yineleme derinliği veya kenar uzunluğu ayarlanan eşikten daha az olan geleneksel sekizli bölümleme yöntemi. Bu nedenle, bu makale bölünen uç koşulu olarak düğümde bulunan noktaların sayısına bağlı olarak uyarlanabilir bir oktree benimser Ayrıntılı adımlar literatürde gösterilmiştir.
2 Nokta bulutunun örtülü yüzey rekonstrüksiyonu
2.1 Radyal temel fonksiyonunun örtük yüzey gösterimi
Bu kağıt önce büyük ölçekli dağınık nokta bulutunu böldüğünden ve ardından yüzey yeniden yapılandırmasını gerçekleştirdiğinden, yeniden yapılandırılmış yüzeyi temsil etmek için sıkı bir şekilde desteklenen radyal temel örtük bir işlev, yani örnekleme noktalarında yüzey uydurma işlemini doğrudan gerçekleştiren metatabanı modeli işlevi kullanılır. , Normal vektör ve diğer bilgilere gerek yok. Genel şekli:
2.2 Diferansiyel evrim algoritmasına dayalı örtük yüzey çözümü
Diferansiyel Evrim (DE) algoritması, doğanın evrimsel gelişim yasasını taklit eden ve "en uygun olanın hayatta kalması ve en uygun olanın hayatta kalması" ilkesinden yararlanan rastgele bir sezgisel arama ve sürü zekası optimizasyon yöntemidir. Bu makalede, büyük ölçekli dağınık nokta bulutu bölümlere ayrılmıştır ve bölümlere ayrılmış alt bölgelerde örtük yüzey fonksiyonları oluşturulmuştur ve daha sonra C = {ck (ckx, cky, ckz) | k = 1,2 metaball merkezini uyarlamalı olarak çözmek için diferansiyel evrim algoritması kullanılmıştır. , ..., m}, metaball yarıçapı ek ve şekil parametresi? k pozu verin ve son olarak en iyi yaklaşık örtülü yüzey fonksiyonu f (x) 'i elde edin. Önce amaç işlevi ve uygunluk işlevini belirleyin ve popülasyonu başlatın; daha sonra diferansiyel evrim algoritmasının mutasyon, geçiş ve seçim işlemlerine göre sürekli yineleyin; son olarak en uygun metaball merkezini, metaball yarıçapını ve şekil parametrelerini bulun.
2.2.1 Amaç fonksiyonunun oluşturulması
Nokta bulutunun yüzey rekonstrüksiyonu, orijinal nokta bulutu verilerinin en iyi yaklaşık yüzeyine mümkün olduğu kadar uyacak, bu nedenle bu makale diferansiyel evrim algoritmasının amacı olarak minimum Kalan Ortalama Kareleri (RMS) alır ve kullanılan amaç işlevi şudur: :
Formülde pi P, orijinal nokta bulutu verilerindeki noktadır ve n, nokta bulutundaki nokta sayısıdır.
2.2.2 Fitness işlevi
Diferansiyel evrim algoritmasında, bu makalenin, çözümün artılarını ve eksilerini ölçmek ve çözümün tanımlanmasını artırmak, yani bir uygunluk işlevi oluşturmak için bir standart formüle etmesi gerekir. Bu makalenin amaç işlevi, karelerin ortalama artık toplamının en küçük olmasıdır. RMS değeri ne kadar küçükse, uygunluk değeri o kadar büyük olmalıdır. Bu, birey ne kadar iyi olursa, seçilme olasılığının o kadar yüksek olduğu anlamına gelir. Diferansiyel evrim algoritması, uygunluk işlevinin değerini en üst düzeye çıkarmayı amaçlarken, bu makaledeki metatabanı modeli parametrelerinin optimizasyon seçimi, optimizasyon sorununu en aza indirmektir, bu nedenle uygunluk işlevinin aşağıdaki gibi dönüştürülmesi gerekir:
2.2.3 Nüfus gerçek sayı kodlama ve başlatma
Bu makale, hedef işlevi en aza indiren, (ckx, cky, ckz, ek, k) olarak tanımlanabilecek metatabanı merkezini, yarıçapı ve şekil parametrelerini (toplamda 5 değişken) akıllıca optimize etmek için diferansiyel evrim algoritmasını kullanmalıdır.
(1) Kodlama
Diferansiyel evrim algoritması, gerçek sayı kodlamasını kullanır.Kodlama aralığı (arama alanı) çok büyükse, DE yavaş veya vaktinden önce yakınlaşır (yerel optimuma yakınsar) veya rastgele aramaya dönüşür. Kodlama aralığı ne kadar küçükse, DE yakınsama hızı o kadar hızlı ve kayıt verimliliği o kadar yüksek olur. Bu nedenle, sınırlı ve mümkün olduğunca küçük bir kodlama aralığı belirlemek gereklidir. Ckx, cky, ckz, ek (0, d>, k (0,100>, xmin, xmax, ymin, ymax, zmin, zmax değişkenleri X'deki nokta bulutu P'dir, Y ve Z'nin üç koordinat yönündeki minimum ve maksimum değerler, d nokta bulutu P'yi içeren oluşturulmuş küp sınırlayıcı kutunun köşegen uzunluk değeridir.
(2) Başlatma
Arama uzayında rastgele I bireyler oluşturur ve her birey J boyutlu bir vektörden oluşur.
Formülde, J = 5; TMAX ve TMIN, sırasıyla arama uzayındaki j-inci değişkeninin maksimum ve minimum değerleridir; r, 0 ile 1 arasında rastgele bir sayıdır.
2.2.4 Diferansiyel evrim işlemi
(1) Varyasyon
G. nesilde, popülasyondan rastgele olarak üç birey Tp1, Tp2 ve Tp3 seçilir ve i p1 p2 p3, ardından mutasyon işlemi:
Formülde CF varyasyon faktörü, Tp2 j (g) -Tp3 j (g) farklılaştırılmış değişkendir; p1, p2 ve p3 popülasyondaki bireyin sıra numarasını temsil eden rastgele tam sayılardır. Bireyin yakınsamasını hızlandırmak için p1 seçilebilir Çağdaş nüfusun en iyi bireyi için.
Geleneksel diferansiyel evrim algoritmasının mutasyon faktörü CF'nin tüm çözüm süreci boyunca değişmeden kalması ve bu da algoritma verimliliğinin azalmasına ve erken yakınsamaya yol açabileceği sorununu hedefleyen bu makale, uyarlanabilir mutasyon faktörü formülünü benimser.
(2) Çapraz
Çapraz geçiş işlemi nüfusun çeşitliliğini artırmaktır. Spesifik işlem:
Formülde r, 0 ile 1 arasında rastgele bir sayıdır ve CR, geçiş faktörüdür.
Geleneksel diferansiyel evrim algoritmasının tüm çözüm sürecinde sabit çapraz faktör CR'nin erken yakınsamaya ve daha yavaş yakınsamaya yol açabileceği sorununu hedefleyen bu makale, uyarlanabilir bir çapraz faktör formülü benimser.
(3) Seçim
Seçim operasyonu, yeni nesil popülasyona giren bireyleri belirlemektir, özellikle:
Formülde, ffit (vi) bireysel vi'nin uygunluk değeridir ve ffit (Ti) bireysel Ti'nin uygunluk değeridir.
3 Örtülü yüzeylerin düzgün bir şekilde birleştirilmesi
Bu makale, literatürde önerilen logaritmik üstel ağırlıklı ekleme algoritmasını seçer ve geliştirir ve orijinal nokta bulutu modeli tarafından tanımlanan tam bir yüzey elde etmek için yerel örtük yüzeyleri düzgün bir şekilde birleştirir. Bu yöntem, her bölümlü alanı birbirine bitişik çiftler halinde birleştirmektir ve sürekli yineleme yoluyla, tüm yerel yüzeylerin düzgün bir şekilde birleştirilmesi gerçekleştirilir ve nihayet tam bir yüzey modeli elde edilir. Ekleme işlevi:
Formülde f1 ve f2, birleştirilecek iki bitişik bölünmüş bölgenin örtük yüzey fonksiyonudur ve , ekleme kontrol parametresidir. 'nın değeri, eklemenin düzgünlüğü ile ilgilidir.Ilteratürde 0.1 ile 10 arasındaki değerler aralığı verilmiştir ve değerinin, çoklu deneylerin etkilerine göre yapay olarak belirlenmesi gerekir. Bu temelde, bu makale, kontrol parametresi 'nın optimal değerini uyarlamalı olarak elde etmek için diferansiyel evrim algoritmasını kullanır.
3.1 Hedef işlevi ve uygunluk işlevi oluşturun
Orijinal nokta bulutunun eklenmiş yüzeyde olabildiğince olmasını sağlamak için, belirlenen hedef işlevi şudur:
Formülde pi, iki bitişik alanın orijinal nokta bulutu içindeki noktadır ve n, iki bitişik alanın orijinal nokta bulutu numarasıdır.
O zaman ilgili uygunluk işlevi:
3.2 Algoritma adımları
Bu yazıda önerilen uyarlanabilir örtük yüzey yumuşatma algoritmasının evrimsel çalışması, makalenin 2.2 bölümündeki ile benzerdir, algoritma adımları şunlardır:
(1) Değişken alanda rastgele popülasyon M'yi başlatın;
(2) Evrim sonlandırma koşulu karşılanıncaya kadar mutasyon, çapraz geçiş ve seçim işlemlerini sırayla gerçekleştirin ve optimum a değerinin birleştirme işlevi elde edilir;
(3) Segmentli alandaki uyarlamalı diferansiyel evrim algoritmasına dayalı olarak dikiş fonksiyonunu özyinelemeli olarak çözün ve örtük yüzey dikiş işlemini gerçekleştirin;
(4) Tam yüzey modelinin çıktısını alın ve algoritma biter.
4 Deneysel sonuçlar ve analiz
Bu makale, büyük ölçekli dağınık nokta bulutu verilerinin hızlı ve yüksek dokulu yüzey yeniden yapılandırması için bir yöntem önermektedir. Önerilen algoritma C ++ ve MATLAB dilinde yazılmıştır. 3.20 GHz saat hızına sahip bir Intel Core i5-6500 ve 8 GB bellek ile çalışır. Bilgisayarda gerçekleştirildi. Örtülü yüzey işleme, sıfır eş yüzey elde etmek için Yürüyüş Küpü algoritmasını kullanır. Deneydeki tüm orijinal nokta bulutu modelleri Stanford Üniversitesi Bilgisayar Grafikleri Laboratuvarı'ndan geldi.
4.1 Farklı türdeki nokta bulutlarının yeniden yapılandırma etkileri
Bu algoritmanın etkinliğini doğrulamak için, bu algoritmanın sağlamlığını farklı ölçek nokta bulutu modellerinde yansıtmak için yeniden yapılandırmak üzere iki farklı ölçek nokta bulutuna uygulanır. Şekil 1'de görüldüğü gibi, Şekil 1 (a) bir tavşan nokta bulutu olup, model küçük ölçekli olup, Şekil 1 (b) bir tavşan yüzey modelidir.Bu yazıda yer alan algoritmanın küçük ölçekli bir modelin yüzeyini iyi bir şekilde yeniden yapılandırabildiği görülmektedir. Yüzey pürüzsüz ve detaylar iyi; Şekil 1 (c) ejderha nokta bulutu, model büyük ölçekli ve özellikler daha karmaşık; Şekil 1 (d) yeniden yapılandırılmış ejderha yüzey modelidir, yeniden yapılandırılmış yüzeyin detaylarını görebilirsiniz İndirgeme derecesi iyidir ve yüzey çok pürüzsüzdür.
Tablo 1, bu yazıda algoritma tarafından işlenen yukarıdaki iki modelin, orijinal nokta bulutu noktalarının sayısı, yeniden inşa süresi ve uydurma hatası dahil olmak üzere istatistiksel bilgilerini göstermektedir. Her orijinal noktanın koordinatlarını ekleme fonksiyonuna koyun ve ardından tüm noktaların artık karelerinin toplamını hesaplayın, maksimum uydurma hatası olarak global artık kareler toplamının maksimum değerini seçin ve ortalama olarak tüm noktaların kalan karelerinin ortalamasını hesaplayın Montaj hatası. Tablo 1'den, bu makaledeki algoritmanın farklı ölçeklerdeki nokta bulutlarına iyi uyarlanabilirliğe sahip olduğu, yeniden yapılandırma etkisinin iyi olduğu ve zaman alıcı kabul edilebilir bir aralıkta olduğu sonucuna varılabilir.
4.2 Farklı rekonstrüksiyon algoritmalarının rekonstrüksiyon sonuçlarının karşılaştırılması
Bu yazıda algoritmanın etkinliğini doğrulamak için bu yazıda yer alan algoritma literatür ve literatürdekilerle karşılaştırılmıştır. Model seçiminde, algoritmanın uyarlanabilirliğini yansıtmak için iki farklı model seçilmiştir: biri kapalı nokta bulut model atı, diğeri ise kapalı nokta bulutu model eli. İki tip modelin rekonstrüksiyon renderleri Şekil 2 ve Şekil 3'te gösterilmektedir.
Şekil 2 (a) atın orijinal nokta bulutudur; Şekil 2 (b) literatür algoritması ile yeniden oluşturulan yüzeydir, yüzeyin pürüzsüz olduğu ancak detayların kaybolduğu görülebilir; Şekil 2 (c) literatür algoritması ile yeniden oluşturulmuş yüzeydir. Detaylı özelliklerin yansıtıldığı ancak yüzeyin yeterince pürüzsüz olmadığı görülebilmektedir; Şekil 2 (d) bu yazıda algoritma ile yeniden oluşturulmuş yüzey olup, yüzey düzgün ve detaylı özellikler açıktır. Tablo 2'deki at modeli rekonstrüksiyonunun istatistiksel bilgilerinden, bu makaledeki algoritmanın yeniden yapılandırma etkisinin en iyi olduğu sonucuna varılabilir, ancak zaman açısından, orijinal nokta bulutunun bölümlere ayrılması ve daha sonra birleştirilmesi gerekir ki bu ideal değildir.
Şekil 3 (a), elin orijinal nokta bulutudur; Şekil 3 (b) 'deki yeniden yapılandırılmış yüzeyle ilgili daha bariz sorun, bilekteki şekli kontrol etmek için hiçbir nokta verisinin olmamasıdır, bu nedenle ciddi bir şekilde örtüşmüştür; Şekil 3 (c)' deki yeniden yapılandırılmış yüzey Yeniden yapılandırma sürecinde, ek bir sıfır seviye seti üretilir, bu nedenle kısmi bozulma; Şekil 3 (d), kavisli yüzeyin yüzeyini pürüzsüz hale getirmek için bu kağıdın algoritmasını kullanır, kapatılmamış bilekte fazlalık çıkıntı olmaz, etki en iyisidir. Tablo 2'deki el modeli rekonstrüksiyonunun istatistiksel bilgilerinden, bu yazıda algoritmanın yeniden yapılandırılan yüzeyinin ortalama uydurma hatasının en küçük olduğu sonucuna varılabilir.Zaman en az olmamakla birlikte algoritmanın performans oranı en yüksektir.
5. Sonuç
Bu makale, büyük ölçekli dağınık nokta bulutlarını uyarlamalı olarak yeniden yapılandırmak için, yerel nokta bulutunu bölümlere ayırmak için uyarlanabilir bir oktree kullanarak, yerel nokta bulutunun örtük yüzey işlevini akıllıca çözmek için uyarlanabilir bir diferansiyel evrim algoritması kullanarak ve gelişmiş birleştirme benimseyerek bir yöntem önermektedir. Tam bir yüzey modeli elde etmek için algoritma. Bu yazıda yöntemin rekonstrüksiyon etkisi literatür ve literatür yöntemleri ile karşılaştırılmıştır.Sonuçlar, bu yazıda yöntemle rekonstrükte edilen yüzeyin yüzeyinin düzgün, detayların net ve doğru olduğunu ve kapatılmamış alanda belirgin bir fazlalık olmadığını göstermektedir. Bu makaledeki yöntem, büyük ölçekli nokta bulutlarının yeniden yapılandırılmasında çok etkili olmasına rağmen, daha ayrıntılı özellikler sağlamak için, yeniden yapılandırma süresinde bir artışa yol açan bölümleme miktarını artırmak pahasına. Bu nedenle, yeniden yapılandırma etkisi ile zaman alan ilişkinin nasıl dengeleneceği, bir sonraki araştırma içeriğidir.
Referanslar
Mo Jianwen, Pang Jiankeng, Yuan Hua.VTK'ya Dayalı 3B Nokta Bulutu Yüzey Yeniden Yapılandırması Araştırması. Elektronik Teknolojinin Uygulanması, 2015, 41 (4): 156-158.
Fu Yanqing İyileştirilmiş radyal tabanlı fonksiyon ağına dayalı 3B örtük yüzey yeniden yapılandırma algoritması araştırması Hangzhou: Çin Jiliang Üniversitesi, 2014.
Liu Shengjun, Han Xuli, Jin Xiaogang Uzamsal örnekleme noktalarının örtülü yüzey temsili ve optimizasyonu Journal of Image and Graphics, 2011, 16 (3): 480-487.
Han Xie, Wu Jingmin, Han Huiyan, vd.Elipsoid kısıtlamasına dayalı radyal temel fonksiyonunun örtülü yüzey rekonstrüksiyonu Journal of Graphics, 2014, 35 (4): 504-510.
Tian Jianlei Bir özelliği koruyan örtük yüzey algoritması Bilgisayar Mühendisliği ve Uygulamaları, 2011, 47 (1): 208-210.
Zhang Juan, Hou Jin, Wu Tingting ve diğerleri. 3B dağınık nokta bulutu modelleri için hızlı yüzey yeniden yapılandırma algoritması. Bilgisayar Destekli Tasarım ve Grafik Dergisi, 2018, 30 (2): 235-243.
Liu Enjiang, Song Yunsheng, Liang Jiye. Veri Bölümüne Dayalı Kernel Ridge Regression Accelerated Algorithm. Journal of Science and Technology of China, 2018, 48 (4): 284-289.
Chen Long. Dağınık Nokta Bulutlarının Özellik Ayıklama ve Kümeleme Basitleştirme Teknolojisi Araştırması. Mianyang: Southwest University of Science and Technology, 2017.
BLINN J. Cebirsel yüzey çiziminin bir genellemesi. Bilgisayar Grafikleri ve Etkileşimli Teknikler Konferansı. ACM, 1982.
NISHIMURA H, HIRAI M, KAWAI T, ve diğerleri. Dağıtım fonksiyonu ile nesne modelleme ve bir görüntü oluşturma yöntemi.Japonya Elektronik ve Haberleşme Mühendisleri Enstitüsü İşlemleri, 1985, J68-D (4): 718-825.
MURAKAMI S, ICHIHARA H. Metaball tekniği ile 3 boyutlu görüntüleme yönteminde.Elektronik İletişim Dergisi, 1987, 70 (8): 1607-1615.
Yang Congrui, Qian Qian, Wang Feng, vb. İşlev optimizasyonunda gelişmiş uyarlanabilir genetik algoritmanın uygulanması Bilgisayarların Uygulama Araştırması, 2018, 35 (4): 1042-1045.
Wu Jingmin. 3B nokta bulutu işleme ve örtük yüzeyin 3B yeniden yapılandırma teknolojisinin araştırılması ve uygulanması. Taiyuan: Çin Kuzey Üniversitesi, 2014.
LORENSEN W E, CLINE H E. Yürüyen küpler: yüksek çözünürlüklü bir 3D yüzey oluşturma algoritması ACM Siggraph Computer Graphics, 1987, 21 (4): 163-169.
yazar bilgileri:
Jiang Meng 1, 2, Cai Yong 1, 2, Zhang Jiansheng 1, 2
(1. İmalat Bilimi ve Mühendisliği Okulu, Southwest Bilim ve Teknoloji Üniversitesi, Mianyang 621010, Sichuan;
2. Üretim Süreci Test Teknolojisi Eğitim Bakanlığı tarafından ortaklaşa kurulan Eğitim Bakanlığı'nın kilit laboratuvarı, Mianyang, Sichuan 621010)
