RANSAC algoritması

RANSAC ( İngilizce ran dom sa mple c onsensus , Almanca "rastgele bir örnekle eşleşme") bir yeniden örneklemedir - aykırı değerler ve kaba hatalar içeren bir dizi ölçüm içinde bir modelin tahmini için algoritma . Aykırı değerlere karşı sağlamlığı nedeniyle ağırlıklı olarak bilgisayarlı görü alanında otomatik ölçümlerin değerlendirilmesinde kullanılır . Burada, RANSAC - uç değerler için ayarlanmış bir veri hacmini hesaplayarak, sözde konsensüs seti - genellikle çok sayıda aykırı değerle başarısız olan en küçük kareler yöntemi gibi telafi prosedürlerini destekler .

RANSAC resmi olarak 1981 yılında Martin A. Fischler ve Robert C. Bolles tarafından ACM'nin İletişim bölümünde tanıtıldı . Her iki yazarın da üzerinde çalıştığı SRI International'da Mart 1980'de dahili bir sunum yapıldı. M tahmin edicileri , RANSAC'a bir alternatiftir . Maksimum olabilirlik tahmin edicileri gibi diğer tahmin edicilerle karşılaştırıldığında , bunlar aykırı değerlere karşı daha dayanıklıdır.

Giriş ve ilke

Bir ölçümün sonucu genellikle basınç, mesafe veya sıcaklık, ekonomik parametreler veya benzerleri gibi fiziksel değerleri temsil eden veri noktalarıdır. Bu noktalara, mümkün olduğu kadar kesin olarak uyan parametreye bağlı bir model eğrisi yerleştirilmelidir. Parametreleri belirlemek için gerekenden daha fazla veri noktası mevcuttur; yani model aşırı belirlenmiş . Ölçülen değerler aykırı değerler, yani beklenen ölçüm serisine uymayan değerler içerebilir . Dijital teknolojinin gelişmesine kadar ölçümler çoğunlukla manuel olarak yapıldığından, cerrah tarafından yapılan kontrol, aykırı değerlerin oranının genellikle düşük olduğu anlamına geliyordu. En küçük kareler yöntemi gibi o zaman kullanılan kompanzasyon algoritmaları , bu tür veri kümelerinin birkaç aykırı değerle değerlendirilmesi için çok uygundur: Onların yardımıyla, önce veri noktalarının tamamı ile model belirlenir ve ardından bir girişimde bulunulur. aykırı değerleri tespit etmek için yapılmıştır.

Tek aykırı değer, en uygun çizgiyi yukarı doğru çeker

1980'lerin başından itibaren dijital teknolojinin gelişmesiyle birlikte temeller değişti. Yeni olanaklar nedeniyle, özellikle bilgisayarlı görme alanında otomatik ölçüm yöntemleri giderek daha fazla kullanılmaya başlandı . Buradaki sonuç, genellikle çok sayıda aykırı değer içeren çok sayıda değerdir. Geleneksel yöntemler , hataların normal dağılımını varsayar ve bazen veri noktaları çok sayıda aykırı değer içeriyorsa anlamlı bir sonuç sağlamaz. Bu, yandaki resimde gösterilmiştir. Düz bir çizgi (model), noktalara (ölçülen değerler) uyarlanmalıdır. Bir yandan, düz çizgiyi belirlemeden önce geleneksel yöntemler kullanılarak 20 veri noktası arasındaki münferit aykırı değerler göz ardı edilemez. Öte yandan, konumu nedeniyle, regresyon çizgisi (kaldıraç noktası olarak adlandırılan) üzerinde orantısız olarak güçlü bir etkiye sahiptir.

RANSAC algoritması yeni, yinelemeli bir yaklaşım izler. Ölçülen tüm değerleri birbirine eşitlemek yerine, sadece model parametrelerini hesaplamak için gerektiği kadar rastgele seçilmiş değer kullanılır (düz bir çizgi durumunda bu iki nokta olacaktır). Başlangıçta seçilen değerlerin aykırı değer olmadığı varsayılır. Bu varsayım, önce rastgele seçilen değerlerden model hesaplanarak ve ardından ölçülen tüm değerlerin (yani sadece orijinal olarak seçilenlerin değil) bu modele olan uzaklığı belirlenerek kontrol edilir. Ölçülen bir değer ile model arasındaki mesafe önceden tanımlanmış bir eşik değerinden az ise, o zaman bu ölçülen değer, hesaplanan modele göre brüt bir hata değildir. Yani o destekler bunu. Ölçülen değerler modeli ne kadar desteklerse, model hesaplaması için rastgele seçilen değerlerin herhangi bir aykırı değer içermemesi o kadar olasıdır. Bu üç adım - ölçülen değerlerin rastgele seçimi, model parametrelerinin hesaplanması ve desteğin belirlenmesi - birbirinden bağımsız olarak birkaç kez tekrarlanır. Her yinelemede, hangi ölçülen değerlerin ilgili modeli desteklediği kaydedilir. Bu kümeye konsensüs kümesi denir . İdeal olarak artık herhangi bir aykırı değer içermeyen en büyük fikir birliği kümesinden , çözüm daha sonra geleneksel ayarlama yöntemlerinden biri kullanılarak belirlenir.

Uygulamalar

Belirtildiği gibi, birçok aykırı değer esas olarak otomatik ölçümlerle ortaya çıkar. Bunlar genellikle bilgisayar görüşü alanında gerçekleştirilir, bu nedenle RANSAC burada özellikle yaygındır. Bazı uygulamalar aşağıda sunulmuştur.

Alcatraz'ın dikilmiş panorama görüntüsü : Bunu yapmak için, daha sonra harmanlanabilmeleri için tek tek görüntüler uygun şekilde üst üste getirilmelidir. Bunun için çizim dosyalarında ortak özellikler bulunmalıdır.

In görüntü işleme , RANSAC iki kamera görüntü arasında homolog noktalarını belirlemek için kullanılır. İki görüntüde tek bir nesne noktasının oluşturduğu iki görüntü noktası homologdur. Homolog noktaların atanmasına uygunluk problemi denir. Otomatik analizin sonucu genellikle çok sayıda yanlış atama içerir. Uygunluk analizinin sonuçlarına dayanan prosedürler, yanlış atamaları dışlamak için RANSAC'ı kullanır. Bu yaklaşımın bir örneği, çeşitli küçük bireysel görüntülerden ( dikiş ) bir panorama görüntüsünün oluşturulmasıdır . Bir diğeri ise epipolar geometrinin hesaplanmasıdır . Bu, aynı nesnenin farklı kamera görüntüleri arasındaki geometrik ilişkileri gösteren bir geometri modelidir. Burada RANSAC, görüntüler arasındaki geometrik ilişkiyi tanımlayan temel matrisi belirlemek için kullanılır.

Otonom kara araçları yarışması olan DARPA Grand Challenge'da yol yüzeyini belirlemek ve aracın hareketini yeniden oluşturmak için RANSAC kullanıldı.

Algoritma ayrıca gürültülü üç boyutlu nokta kümelerinde silindirler veya benzerleri gibi geometrik cisimleri uyarlamak veya nokta bulutlarını otomatik olarak bölümlere ayırmak için de kullanılır . Aynı segmente ait olmayan tüm noktalar aykırı değer olarak kabul edilir. Nokta bulutunda en baskın cisim tahmin edildikten sonra, bir sonraki adımda başka cisimlerin belirlenebilmesi için bu cisme ait tüm noktalar kaldırılır. Bu işlem, nokta kümesindeki tüm cisimler bulunana kadar tekrarlanır.

Prosedür ve parametreler

RANSAC için ön koşul, model parametrelerini belirlemek için gerekenden daha fazla veri noktasının mevcut olmasıdır. Algoritma aşağıdaki adımlardan oluşur:

1. Modelin parametrelerini hesaplamak için veri noktalarından gerektiği kadar rasgele nokta seçin. Bu, bu kümenin aykırı değerlerden arınmış olacağı beklentisiyle yapılır.
2. Seçilen noktalarla model parametrelerini belirleyin.
3. Model eğrisinden uzaklığı belirli bir sınır değerinden daha küçük olan ölçülen değerlerin alt kümesini belirleyin (bu alt kümeye uzlaşma kümesi denir ). Belirli bir minimum sayıda değer içeriyorsa, muhtemelen iyi bir model bulunmuştur ve fikir birliği seti kaydedilir.
4. 1-3 arasındaki adımları birkaç kez tekrarlayın.

Birkaç yineleme gerçekleştirildikten sonra, en çok puanı içeren alt küme seçilir (eğer bulunduysa). Model parametreleri, yalnızca bu alt küme ile olağan kompanzasyon yöntemlerinden biri ile hesaplanır. Algoritmanın alternatif bir varyantı, 3. adımda modeli yeterli sayıda nokta destekliyorsa yinelemeleri zamanından önce sona erdirir. Bu varyant, önleyici - yani erken sonlandıran - RANSAC olarak adlandırılır. Bu yaklaşımla, yeterli ölçülen değerlerin modeli destekleyip desteklemediğinin değerlendirilebilmesi için aykırı değer oranının ne kadar büyük olduğu önceden bilinmelidir.

Algoritma esasen üç parametreye bağlıdır:

1. bir noktanın brüt hata olarak kabul edilmediği bir veri noktasının modelden maksimum uzaklığı;
2. iterasyon sayısı ve
3. fikir birliği kümesinin minimum boyutu , yani modelle tutarlı minimum nokta sayısı.

Bir veri noktasının modelden maksimum uzaklığı

Bu parametre, algoritmanın başarısı için esastır. Diğer iki parametrenin aksine, belirtilmelidir ( konsensüs kümesinin kontrol edilmesine gerek yoktur ve yineleme sayısı neredeyse sınırsız olacak şekilde seçilebilir). Değer çok büyük veya çok küçükse algoritma başarısız olabilir. Bu, aşağıdaki üç resimde gösterilmiştir. Her durumda bir yineleme adımı gösterilir. Yeşil model çizgisinin hesaplandığı rastgele seçilen iki nokta mavi renktedir. Hata sınırları siyah çizgiler olarak gösterilmiştir. Model çizgisini desteklemek için bu çizgilerin içinde bir nokta bulunmalıdır. Seçilen mesafe çok büyükse, çok fazla aykırı değer tanınmayacaktır, böylece yanlış bir model, doğru bir modelle aynı sayıda aykırı değere sahip olabilir (Şekil 1a ve 1b). Çok düşük ayarlanırsa, aykırı değer içermeyen bir değer kümesinden hesaplanan bir model, aykırı olmayan çok az sayıda başka değer tarafından desteklenebilir (Şekil 2).

• Hata sınırı seçiminin çok büyük veya çok küçük olmasıyla ilgili sorunlar
• 

  1 A. Doğru çözüm, iki nokta aykırıdır.

• 

  1b. İkincisi, 1a'dakiyle aynı sayıda aykırı değerle yanlış çözüm.

• 

  2. Hata sınırı çok küçük.

Bu sorunlara rağmen, bu değer genellikle ampirik olarak belirlenmelidir. Hata limiti , sadece hesaplanabilir yasalarını kullanarak olasılık dağılımı eğer standart sapma ölçüm değerleri bilinen .

yineleme sayısı

Tekrar sayısı, belirli bir olasılıkla, veri noktalarından en az bir kez aykırı değer içermeyen bir alt küme seçilecek şekilde ayarlanabilir . Eğer bir model ve hesaplanması için gerekli olan veri noktası sayısı veri aykırı nispi oranı, olasılık olduğu göz önünde her seçilmemiş aykırı değer en az bir olması durumunda tekrar ${\ görüntü stili p}$${\ görüntü stili s}$${\ görüntü stili \ epsilon}$${\ görüntü stili n}$

${\ displaystyle p = 1- \ sol (1- \ sol (1- \ epsilon \ sağ) ^ {s} \ sağ) ^ {n}}$,

ve böylece her seferinde en az bir aykırı değerin seçilme olasılığı en fazla , yeterince büyük seçilmelidir. en azından daha net ol ${\ displaystyle 1-p}$${\ görüntü stili n}$

${\ displaystyle n = {\ frac {\ log \ sol (1-p \ sağ)} {\ log \ sol (1- \ sol (1- \ epsilon \ sağ) ^ {s} \ sağ)}}}$

Tekrarlar gerekli. Bu nedenle sayı yalnızca aykırı değerlerin oranına, model fonksiyonunun parametre sayısına ve en az bir aykırı değer içermeyen alt küme çizmenin belirtilen olasılığına bağlıdır. Toplam ölçülen değer sayısından bağımsızdır.

Aşağıdaki tablo, model parametrelerinin belirlenmesi için gerekli olan nokta sayısı ve aykırı değer oranına bağlı olarak gerekli tekrar sayısını göstermektedir. Tüm veri noktalarından en az bir aykırı değer içermeyen alt küme seçme olasılığı %99 olarak belirlenmiştir.

Gerekli yineleme sayısı ( ) ${\ görüntü stili p = 99 \, \%}$

örnek	Gerekli puan sayısı	Aykırı yüzde
		%10	%20	%30	%40	%50	%60	%70
Sadece	2	3	5	7.	11	17.	27	49
seviye	3	4.	7.	11	19.	35	70	169
temel matris	8.	9	26	78	272	1177	7025	70188

Konsensüs seti boyutu

Algoritmanın genel varyantında, bu değerin mutlaka bilinmesi gerekmez, çünkü eğer bir inandırıcılık kontrolünden vazgeçilirse, en büyük konsensüs seti bir sonraki kursta basitçe kullanılabilir . Ancak, erken sonlanan varyant için bunun bilgisi gereklidir. Bu durumda, konsensüs kümesinin minimum boyutu genellikle analitik veya deneysel olarak belirlenir. İyi bir yaklaşım, ölçülen değerlerin toplam miktarından verilerde şüphelenilen aykırı değerlerin oranıdır . En küçük boyut aynıdır için veri noktaları . Örneğin, 12 veri noktası ve %20 aykırı değer ile minimum boyut yaklaşık 10'dur. ${\ görüntü stili \ epsilon}$${\ görüntü stili n}$${\ displaystyle (1- \ epsilon) \ cdot n}$

Parametrelerin uyarlanabilir belirlenmesi

Toplam veri noktası miktarındaki aykırı değerlerin oranı genellikle bilinmez. Bu nedenle gerekli yineleme sayısını ve bir konsensüs kümesinin minimum boyutunu belirlemek mümkün değildir . Bu durumda, algoritma, örneğin %50'lik bir aykırı değer oranının en kötü durum varsayımıyla başlatılır ve yineleme sayısı ve fikir birliği kümesinin boyutu buna göre hesaplanır. Her yinelemeden sonra, daha büyük bir tutarlı küme bulunursa iki değer ayarlanır. Örneğin, algoritma %50'lik bir aykırı değer oranıyla başlatılırsa ve hesaplanan fikir birliği seti tüm veri noktalarının %80'ini içeriyorsa , sonuç, %20'lik aykırı değer oranı için iyileştirilmiş bir değerdir. Yineleme sayısı ve konsensüs kümesinin gerekli boyutu daha sonra yeniden hesaplanır.

örnek

Düzlemdeki bir dizi noktaya düz bir çizgi yerleştirilmelidir. Noktalar ilk resimde gösterilmiştir. İkinci resim, farklı koşuların sonucunu gösterir. Kırmızı noktalar düz çizgiyi destekler. Düz çizgiden uzaklığı hata sınırından büyük olan noktalar mavi renkle gösterilir. Üçüncü resim 1000 iterasyon adımından sonra bulunan çözümü göstermektedir.

• Düz bir çizgiyi veri noktalarına uyarlamak için RANSAC
• 

  1. Orijinal veri seti.

• 

  2. Birkaç yinelemenin animasyonu.

• 

  3. 1000 yinelemeden sonra sonuç.

gelişmeler

RANSAC'ın iki tanesi burada önemli olan bazı uzantılar vardır.

LO-RANSAC

Düz model, tüm hatasız noktalar tarafından desteklenmez.

Deneyler, teorik olarak yeterli sayıdan çoğunlukla daha fazla yineleme adımının gerekli olduğunu göstermiştir: Bir model aykırı değer içermeyen bir nokta kümesiyle hesaplanırsa, aykırı olmayan diğer tüm değerlerin bu modeli desteklemesi gerekmez. Sorun yandaki şekilde gösterilmiştir. Düz çizgi, iki doğru değer (siyah noktalar) kullanılarak hesaplanmış olsa da, görüntünün sağ üst kısmında açıkça doğru olan bazı diğer noktalar aykırı (mavi yıldızlar) olarak sınıflandırılır.

Bu nedenle, LO-RANSAC (yerel olarak optimize edilmiş RANSAC) için orijinal algoritma 3. adımda genişletilmiştir. İlk olarak, her zamanki gibi, aykırı olmayan noktaların alt kümesi belirlenir. Model daha sonra bu küme kullanılarak ve en küçük kareler yöntemi gibi herhangi bir telafi yönteminin yardımıyla yeniden belirlenir. Son olarak, bu optimize modele olan mesafesi hata sınırından daha küçük olan alt küme hesaplanır. Yalnızca bu geliştirilmiş alt küme, bir fikir birliği kümesi olarak kaydedilir.

MSAC

RANSAC, ölçülen değerlerin çoğu tarafından desteklenen modeli seçer. Bu, tüm hatasız değerlerin 0 ile girildiği ve tüm aykırı değerlerin sabit bir değerle girildiği bir toplamın minimizasyonuna karşılık gelir : ${\ görüntü stili C}$

${\ displaystyle C = \ toplam _ {i} p ({\ metin {hata}}) \ dörtlü {\ metin {ile}} \ dörtlü p = \ sol \ {{\ başlangıç ​​{dizi} {ll} 0, & {\ metin {hata varsa}} <{\ metin {hata sınırı}} \\ {\ metin {sabit}} & {\ metin {hata varsa}} \ geq {\ metin {hata sınırı}} \ bitiş {dizi} } \ sağ.}$

Hata sınırı çok yüksek ayarlanırsa hesaplanan model çok yanlış olabilir - ne kadar yüksekse, için aynı değerlere sahip çözümler o kadar fazladır . Aşırı durumda, ölçülen değerlerdeki tüm hatalar hata sınırından daha küçüktür, bu nedenle her zaman 0 olur. Bu, aykırı değerlerin tanımlanamayacağı ve RANSAC'ın zayıf bir tahmin sağladığı anlamına gelir. ${\ görüntü stili C}$${\ görüntü stili C}$

MSAC ( M -Estimator SA mple C onsensus), minimize edilecek değiştirilmiş bir amaç fonksiyonu kullanan RANSAC'ın bir uzantısıdır:

${\ displaystyle C = \ toplam _ {i} p ({\ metin {hata}}) \ dörtlü {\ metin {ile}} \ dörtlü p = \ sol \ {{\ başlangıç ​​{dizi} {ll} {\ metin {Hata,}} & {\ metin {hataysa}} <{\ metin {hata sınırı}} \\ {\ metin {sabit değer hata sınırından büyük,}} & {\ metin {hataysa}} \ geq { \ metin {Hata engeli}} \ bitiş {dizi}} \ sağ.}$

Bu fonksiyon ile aykırı değerler, hata eşiğinden daha büyük olan belirli bir “ceza” almaya devam eder. Hata sınırının altındaki değerler 0 yerine hata ile toplama dahil edilir. Bu, bahsedilen sorunu ortadan kaldırır, çünkü bir nokta toplama daha az katkıda bulunur, çünkü modele daha iyi uyar.

Bireysel kanıt

1. ^ Robert C. Bolles: SRI'daki ana sayfa . ( çevrimiçi [11 Mart 2008'de erişildi]). 
2. ↑ Martin A. Fischler: SRI'daki Ana Sayfa . ( çevrimiçi [11 Mart 2008'de erişildi]). 
3. ↑ Martin A. Fischler ve Robert C. Bolles: Rastgele Örnek Uzlaşma: Görüntü Analizi ve Otomatik Haritacılık Uygulamaları ile Model Uydurma Paradigma . Mart 1980 ( çevrimiçi [PDF; 301 kB ; 13 Eylül 2007'de erişildi]). 
4. ↑ Dag Ewering: Doğru ve nokta korelasyonlarını kullanarak model tabanlı izleme . Eylül 2006 ( çevrimiçi [PDF; 9.5 MB ; 2 Ağustos 2007'de erişildi]). 
5. ^ Martin A. Fischler ve Robert C. Bolles: RANSAC: Tarihsel Bir Perspektif . 6 Haziran 2006 ( çevrimiçi [PPT; 2.8 MB ; 11 Mart 2008'de erişildi]). 
6. ↑ Christian Beder ve Wolfgang Förstner : Yüzey normallerini kullanmadan 3B noktalardan silindirlerin doğrudan belirlenmesi . 2006 ( uni-bonn.de [PDF; 25 Ağustos 2016'da erişildi]). 
7. ^ Ondřej Chum, Jiři Matas ve Štěpàn Obdržàlek: Genelleştirilmiş Model Optimizasyonu ile RANSAC'ı Geliştirme . 2004 ( çevrimiçi [PDF; 7 Ağustos 2007'de erişildi]). 
8. ↑ PHS Torr ve A. Zisserman: MLESAC: Görüntü geometrisini tahmin etme uygulamasına sahip yeni bir sağlam tahmin edici . 1996 ( çevrimiçi [PDF; 855] kB ; 7 Ağustos 2007'de erişildi]). 

Edebiyat

• Martin A. Fischler ve Robert C. Bolles: Rastgele Örnek Uzlaşma: Görüntü Analizi ve Otomatik Haritacılık Uygulamaları ile Model Uydurma İçin Bir Paradigma. (PDF; 1,2 MB) (Artık mevcut çevrimiçi.) 1981, arşivlenmiş orijinal üzerine 5 Nisan, 2019 ; 14 Ekim 2019 tarihinde erişildi . 
• Çeşitli yazarlar: 25 Years of RANSAC, CVPR 2006 ile birlikte Çalıştay. 2006, erişildi 11 Mart 2008 . 
• Peter Kovesi: RANSAC - RANSAC algoritması (Matlab uygulaması) ile bir modeli verilere sağlam bir şekilde sığdırır. 2007, 11 Mart 2008'de erişildi . 
• Volker Rodehorst: Projektif geometri ile otomatik kalibrasyon yoluyla yakın mesafeden fotogrametrik 3D rekonstrüksiyon . wvb Wissenschaftlicher Verlag Berlin, 2004, ISBN 978-3-936846-83-6 (üniversite yayını, artı tez, TU Berlin 2004). 
• Richard Hartley, Andrew Zisserman: Bilgisayarla Görmede Çoklu Görünüm Geometrisi . 2. Baskı. Cambridge University Press, Cambridge, UK 2004, ISBN 978-0-521-54051-3 (İngilizce). 
• Tilo Strutz: Veri Uydurma ve Belirsizlik (Ağırlıklı en küçük kareler ve ötesine pratik bir giriş) . 2. baskı. Springer Vieweg, 2016, ISBN 978-3-658-11455-8 (İngilizce).