Nirengi (bilgisayar görüşü) - Triangulation (computer vision)

Gelen bilgisayar vizyonu nirengi iki veya daha fazla, görüntüler üzerine Tahminlerini verilen 3 boyutlu uzayda bir noktaya belirleme sürecinde ifade eder. Bu problemi çözmek için, kamera matrisleri ile temsil edilen en basit durumda, ilgili kameralar için kamera projeksiyon fonksiyonunun parametrelerini 3B'den 2'ye bilmek gerekir . Nirengi, bazen yeniden inşa veya kesişme olarak da adlandırılır .

Nirengi problemi prensipte önemsizdir. Bir görüntüdeki her nokta 3B uzayda bir çizgiye karşılık geldiğinden, 3B'de çizgi üzerindeki tüm noktalar görüntüdeki noktaya yansıtılır. İki veya daha fazla görüntüde bir çift karşılık gelen nokta bulunabilirse, bunların ortak bir 3B noktasının projeksiyonu olması gerekir x . Kesişen gereken görüntü noktaları tarafından oluşturulan çizgiler grubu x (3D noktası) ve koordinat cebirsel formülasyonun x (3D noktası) olarak aşağıdaki gibidir, çeşitli şekillerde de hesaplanabilir.

Ancak pratikte, görüntü noktalarının koordinatları keyfi doğrulukla ölçülemez. Bunun yerine, mercek bozulmasından kaynaklanan geometrik gürültü veya ilgi noktası algılama hatası gibi çeşitli gürültü türleri, ölçülen görüntü koordinatlarında yanlışlıklara yol açar. Sonuç olarak, karşılık gelen görüntü noktaları tarafından oluşturulan çizgiler her zaman 3B uzayda kesişmez. O halde sorun, ölçülen görüntü noktalarına en iyi şekilde uyan bir 3B nokta bulmaktır. Literatürde, optimalliğin nasıl tanımlanacağına ve optimal 3B noktasının nasıl bulunacağına dair birçok öneri bulunmaktadır. Farklı optimallik kriterlerine dayandıklarından, çeşitli yöntemler gürültü söz konusu olduğunda 3 boyutlu x noktasının farklı tahminlerini üretir .

Giriş

Aşağıda, iğne deliği kameraları tarafından oluşturulan iki görünümden karşılık gelen görüntü noktalarında üçgenlemenin yapıldığı varsayılmaktadır . Bu varsayımlardan genelleme burada tartışılmaktadır .

İdeal epipolar geometri durumu. Bir 3B noktası x , her kameranın odak noktası O ₁ ve O ₂ ile kesişen çizgiler (yeşil) aracılığıyla iki kamera görüntüsüne yansıtılır . Ortaya çıkan görüntü noktaları y ₁ ve y _2'dir . Yeşil çizgiler x noktasında kesişiyor .

Uygulamada, y ₁ ve y ₂ görüntü noktaları keyfi doğrulukla ölçülemez. Bunun yerine y ' ₁ ve y' ₂ noktaları tespit edilir ve nirengi için kullanılır. Karşılık gelen projeksiyon çizgileri (mavi) genel olarak 3B uzayda kesişmez ve ayrıca x noktası ile kesişmeyebilir .

Soldaki görüntü , iğne deliği modelinin bir çift stereo kamerasının epipolar geometrisini göstermektedir . Bir nokta x 3D uzayda (3D noktası) kameranın geçen bir hat (yeşil) boyunca karşılık gelen görüntü düzlemine izdüşümü bir odak noktası , ve karşılık gelen iki görüntü noktaları ile sonuçlanır ve . Verilirse ve iki kameranın geometrisi biliniyorsa, iki projeksiyon çizgisi (yeşil çizgiler) belirlenebilir ve x noktasında (3D noktası) kesişmeleri gerekir . Kesişme noktasının basit bir şekilde belirlenebileceği temel doğrusal cebir kullanılarak . ${\ displaystyle \ mathbf {O} _ {1}}$${\ displaystyle \ mathbf {O} _ {2}}$${\ displaystyle \ mathbf {y} _ {1}}$${\ displaystyle \ mathbf {y} _ {2}}$${\ displaystyle \ mathbf {y} _ {1}}$${\ displaystyle \ mathbf {y} _ {2}}$

Sağdaki resim gerçek durumu göstermektedir. Görüntü noktalarının konumu ve tam olarak ölçülemez. Nedeni, aşağıdaki gibi faktörlerin birleşimidir ${\ displaystyle \ mathbf {y} _ {1}}$${\ displaystyle \ mathbf {y} _ {2}}$

• Geometrik bozulma, örneğin lens distorsiyonu , bu, kameranın 3D'den 2D'ye eşlemesinin iğne deliği kamera modelinden saptığı anlamına gelir . Bir dereceye kadar bu hatalar, geriye kalan geometrik bir hata bırakarak telafi edilebilir.
• X (3B nokta) ' dan gelen tek bir ışık ışını, bir noktaya yayılma fonksiyonuna göre kameraların lens sistemine dağıtılır . Görüntülerdeki dağınık yoğunluk fonksiyonunun ölçümlerinden karşılık gelen görüntü noktasının kurtarılması hatalar verir.
• Dijital bir kamerada, görüntü yoğunluğu işlevi yalnızca ayrık sensör elemanlarında ölçülür. Doğru olanı elde etmek için ayrık yoğunluk fonksiyonunun tam olmayan enterpolasyonu kullanılmalıdır.
• Nirengi için kullanılan görüntü noktaları y ₁ ^' ve y ₂ ' genellikle çeşitli tiplerde özellik çıkarıcılar kullanılarak bulunur, örneğin genel olarak köşeler veya ilgi noktaları. Komşuluk işlemlerine dayalı herhangi bir özellik çıkarma türü için doğal bir yerelleştirme hatası vardır .

Sonuç olarak, ölçülen görüntü noktaları ve yerine ve şeklindedir . Ancak, projeksiyon çizgilerinin (mavi) 3B alanda kesişmesi veya x'e yaklaşması gerekmez . Aslında, bu çizgileri ancak ve ancak kesişir ve tatmin Epipolar kısıtlaması ile tanımlanır temel matris . Ölçüm gürültüsünü Verilen ve bunun Epipolar kısıt memnun değil ve projeksiyon çizgileri kesiştiği bilmediğimiz oldukça muhtemeldir. ${\ displaystyle \ mathbf {y} '_ {1}}$${\ displaystyle \ mathbf {y} '_ {2}}$${\ displaystyle \ mathbf {y} _ {1}}$${\ displaystyle \ mathbf {y} _ {2}}$${\ displaystyle \ mathbf {y} '_ {1}}$${\ displaystyle \ mathbf {y} '_ {2}}$${\ displaystyle \ mathbf {y} '_ {1}}$${\ displaystyle \ mathbf {y} '_ {2}}$

Bu gözlem, nirengi ile çözülen soruna yol açar. Hangi 3B nokta x _tahmini verilen x ve kameraların geometrisinin en iyi tahminidir ? Cevap genellikle x _est'e bağlı bir hata ölçüsü tanımlayarak ve ardından bu hatayı en aza indirerek bulunur. Aşağıdaki bölümlerde, literatürde sunulan çeşitli x _est hesaplama yöntemlerinden bazıları kısaca açıklanmaktadır. ${\ displaystyle \ mathbf {y} '_ {1}}$${\ displaystyle \ mathbf {y} '_ {2}}$

Tüm üçgenleme yöntemleri , bu durumda ve yani epipolar kısıtlama sağlandığında x _est = x üretir (tekil noktalar hariç, aşağıya bakın). Yöntemler arasında farklılık gösteren kısıtlama sağlanmadığında olan şeydir. ${\ displaystyle \ mathbf {y} _ {1} = \ mathbf {y} '_ {1}}$${\ displaystyle \ mathbf {y} _ {2} = \ mathbf {y} '_ {2}}$

Özellikleri

Bir nirengi yöntemi, bir fonksiyon açısından tanımlanabilir, öyle ki ${\ displaystyle \ tau \,}$

${\ displaystyle \ mathbf {x} \ sim \ tau (\ mathbf {y} '_ {1}, \ mathbf {y}' _ {2}, \ mathbf {C} _ {1}, \ mathbf {C} _ {2})}$

tespit edilen görüntü noktalarının homojen koordinatları nerede ve kamera matrisleridir. x (3B nokta), ortaya çıkan 3B noktanın homojen gösterimidir. İşareti olduğunu gösterir , sadece eşit olan bir vektör üretmek için gerekli olan x homojen vektörler söz konusu olduğundan, sıfır olmayan bir skaler ile bir çarpma üzere. ${\ displaystyle \ mathbf {y} '_ {1}, \ mathbf {y}' _ {2}}$${\ displaystyle \ mathbf {C} _ {1}, \ mathbf {C} _ {2}}$${\ displaystyle \ sim \,}$${\ displaystyle \ tau \,}$

Spesifik metotlara, yani spesifik fonksiyonlara bakmadan önce , metotlarla ilgili açıklanması gereken bazı genel kavramlar vardır. Belirli bir problem için hangi nirengi yönteminin seçildiği bir ölçüde bu özelliklere bağlıdır. ${\ displaystyle \ tau \,}$

Tekillikler

Yöntemlerden bazıları, bazı kombinasyonlarına karşılık gelen 3B alanın belirli bir alt kümesinde yer alıyorsa x (3B nokta) tahminini doğru bir şekilde hesaplayamaz . Bu alt kümedeki bir nokta , nirengi yönteminin tekilliğidir . Başarısızlığın nedeni, çözülecek bazı denklem sistemlerinin eksik belirlenmiş olması veya x _est'in projektif temsilinin tekil noktalar için sıfır vektörü olması olabilir. ${\ displaystyle \ mathbf {y} '_ {1}, \ mathbf {y}' _ {2}, \ mathbf {C} _ {1}, \ mathbf {C} _ {2}}$

Değişmezlik

Bazı uygulamalarda, üçgenlemenin 3B noktaları temsil etmek için kullanılan koordinat sisteminden bağımsız olması istenir; nirengi problemi bir koordinat sisteminde formüle edilir ve daha sonra başka bir koordinat sistemine dönüştürülürse, ortaya çıkan x _tahmini de aynı şekilde dönüşmelidir. Bu özellik genellikle değişmezlik olarak adlandırılır . Her üçgenleme yöntemi değişmezliği garanti etmez, en azından genel koordinat dönüşüm türleri için.

3B koordinatların homojen bir temsili için, en genel dönüşüm, bir matris ile temsil edilen yansıtmalı bir dönüşümdür . Homojen koordinatlar şuna göre dönüştürülürse ${\ displaystyle 4 \ times 4}$${\ displaystyle \ mathbf {T}}$

${\ displaystyle \ mathbf {\ bar {x}} \ sim \ mathbf {T} \, \ mathbf {x}}$

sonra kamera matrisleri ( C _k ) olarak dönüştürülmelidir

${\ displaystyle \ mathbf {\ bar {C}} _ ​​{k} \ sim \ mathbf {C} _ {k} \, \ mathbf {T} ^ {- 1}}$

aynı homojen görüntü koordinatlarını üretmek için ( y _k )

${\ displaystyle \ mathbf {y} _ {k} \ sim \ mathbf {\ bar {C}} _ ​​{k} \, \ mathbf {\ bar {x}} = \ mathbf {C} _ {k} \, \ mathbf {x}}$

Üçgenleştirme işlevi değişmez ise , aşağıdaki ilişki geçerli olmalıdır ${\ displaystyle \ tau}$${\ displaystyle \ mathbf {T}}$

${\ displaystyle \ mathbf {\ bar {x}} _ {\ rm {est}} \ sim \ mathbf {T} \, \ mathbf {x} _ {\ rm {est}}}$

onu takip eden

${\ displaystyle \ tau (\ mathbf {y} '_ {1}, \ mathbf {y}' _ {2}, \ mathbf {C} _ {1}, \ mathbf {C} _ {2}) \ sim \ mathbf {T} ^ {- 1} \, \ tau (\ mathbf {y} '_ {1}, \ mathbf {y}' _ {2}, \ mathbf {C} _ {1} \, \ mathbf {T} ^ {- 1}, \ mathbf {C} _ {2} \, \ mathbf {T} ^ {- 1}),}$   hepsi için ${\ displaystyle \ mathbf {y} '_ {1}, \ mathbf {y}' _ {2}}$

Her nirengi yöntemi için bu son ilişkinin geçerli olup olmadığı belirlenebilir. Eğer öyleyse, yalnızca yansıtmalı dönüşümlerin bir alt kümesi için, örneğin katı veya afin dönüşümler için karşılanabilir.

Hesaplama karmaşıklığı

İşlev , uygulamada nispeten karmaşık olabilen bir hesaplamanın yalnızca soyut bir temsilidir. Bazı yöntemler , kapalı formda sürekli bir fonksiyon olan a ile sonuçlanırken, diğerlerinin örneğin SVD veya bir polinomun köklerini bulmayı içeren bir dizi hesaplama adımına ayrıştırılması gerekir . Yine , bazı parametrelerin yinelemeli tahminine dayanması gereken başka bir yöntem sınıfı ortaya çıkar . Bu, hem hesaplama süresinin hem de ilgili işlemlerin karmaşıklığının farklı yöntemler arasında değişebileceği anlamına gelir. ${\ displaystyle \ tau}$${\ displaystyle \ tau}$${\ displaystyle \ tau}$

Yöntemler

Orta nokta yöntemi

İki görüntü noktasının her biri ve (yukarıda doğru resimde mavi) karşılık gelen bir çıkıntı hattı vardır, burada olarak gösterilir ve kamera matrisleri verilen tespit edilebilir, . Izin vermek , bir (3B çizgi) L ve bir x (3B noktası) arasında, ve arasındaki Öklid mesafesi olan bir mesafe fonksiyonu olsun . Orta nokta yöntemi noktası bulur X _est olan en aza indirir ${\ displaystyle \ mathbf {y} '_ {1}}$${\ displaystyle \ mathbf {y} '_ {2}}$${\ displaystyle \ mathbf {L} '_ {1}}$${\ displaystyle \ mathbf {L} '_ {2}}$${\ displaystyle \ mathbf {C} _ {1}, \ mathbf {C} _ {2}}$${\ displaystyle d \,}$${\ displaystyle d (\ mathbf {L}, \ mathbf {x})}$${\ displaystyle \ mathbf {L}}$${\ displaystyle \ mathbf {x}}$

${\ displaystyle d (\ mathbf {L} '_ {1}, \ mathbf {x}) ^ {2} + d (\ mathbf {L}' _ {2}, \ mathbf {x}) ^ {2} }$

Görünüşe göre x _est , iki izdüşüm çizgisini birleştiren en kısa çizgi parçasının tam ortasında yer almaktadır.

Doğrudan doğrusal dönüşüm

Temel matris aracılığıyla

Orada çözülmesi gereken sorun, karşılık gelen normalize edilmiş görüntü koordinatlarının nasıl hesaplanacağıdır ve . Eğer gerekli matris bilinen ve karşılık gelen döndürme ve dönüşümler tespit edilmiştir, bu algoritma (Longuet-Higgins'in yazıda anlatılan) bir çözüm sağlamaktadır. ${\ displaystyle (x_ {1}, x_ {2}, x_ {3})}$${\ displaystyle (y_ {1}, y_ {2})}$${\ displaystyle (y '_ {1}, y' _ {2})}$

Let anlamında olabildikleri satır k rotasyon matrisi : ${\ displaystyle \ mathbf {r} _ {k}}$${\ displaystyle \ mathbf {R}}$

${\ displaystyle \ mathbf {R} = {\ begin {pmatrix} - \ mathbf {r} _ {1} - \\ - \ mathbf {r} _ {2} - \\ - \ mathbf {r} _ {3 } - \ end {pmatrix}}}$

İki koordinat sistemindeki 3B koordinatlar arasındaki yukarıdaki ilişkileri ve daha önce açıklanan 3B ve 2B noktalar arasındaki eşlemeyi birleştirmek,

${\ displaystyle y '_ {1} = {\ frac {x' _ {1}} {x '_ {3}}} = {\ frac {\ mathbf {r} _ {1} \ cdot ({\ tilde {\ mathbf {x}}} - \ mathbf {t})} {\ mathbf {r} _ {3} \ cdot ({\ tilde {\ mathbf {x}}} - \ mathbf {t})}} = {\ frac {\ mathbf {r} _ {1} \ cdot (\ mathbf {y} - \ mathbf {t} / x_ {3})} {\ mathbf {r} _ {3} \ cdot (\ mathbf { y} - \ mathbf {t} / x_ {3})}}}$

veya

${\ displaystyle x_ {3} = {\ frac {(\ mathbf {r} _ {1} -y '_ {1} \, \ mathbf {r} _ {3}) \ cdot \ mathbf {t}} { (\ mathbf {r} _ {1} -y '_ {1} \, \ mathbf {r} _ {3}) \ cdot \ mathbf {y}}}}$

Bir kez belirlendiğinde, diğer iki koordinat şu şekilde hesaplanabilir: ${\ displaystyle x_ {3}}$

${\ displaystyle {\ begin {pmatrix} x_ {1} \\ x_ {2} \ end {pmatrix}} = x_ {3} {\ begin {pmatrix} y_ {1} \\ y_ {2} \ end {pmatrix }}}$

Yukarıdaki türetme benzersiz değildir. Buna göre bir ifade ile başlamak ve bir ifade türetmek de mümkündür . ${\ displaystyle y '_ {2}}$${\ displaystyle x_ {3}}$

${\ displaystyle x_ {3} = {\ frac {(\ mathbf {r} _ {2} -y '_ {2} \, \ mathbf {r} _ {3}) \ cdot \ mathbf {t}} { (\ mathbf {r} _ {2} -y '_ {2} \, \ mathbf {r} _ {3}) \ cdot \ mathbf {y}}}}$

İdeal durumda, kamera 3B noktaları mükemmel bir iğne deliği kamerasına göre eşlediğinde ve ortaya çıkan 2B noktalar herhangi bir gürültü olmadan algılanabildiğinde, iki ifade eşittir. Ancak uygulamada, bunlar değildir ve örneğin bir tür ortalama açısından iki tahmininin birleştirilmesi avantajlı olabilir . ${\ displaystyle x_ {3}}$${\ displaystyle x_ {3}}$

Yukarıdaki hesaplamaların mümkün olan başka uzantı türleri de vardır. Hazırlanmış görüntü koordinatlarının bir ifadesiyle ve primlenmemiş sistemde türetilmiş 3B koordinatlarla başladılar. Primer olmayan görüntü koordinatlarıyla başlamak ve nihayetinde prime edilmemiş 3B koordinatlara dönüştürülebilen hazır 3B koordinatlar elde etmek de mümkündür. Yine ideal durumda, sonuç yukarıdaki ifadelere eşit olmalıdır, ancak pratikte sapma gösterebilir.

Son bir açıklama, temel matrisin karşılık gelen görüntü koordinatından belirlenmesi durumunda, ki bu genellikle 3B noktaların bu şekilde belirlendiği durumda, çeviri vektörünün yalnızca bilinmeyen bir pozitif ölçeklemeye kadar bilindiği gerçeğiyle ilgilidir . Sonuç olarak, yeniden yapılandırılmış 3B noktalar da pozitif bir ölçeklendirme açısından belirsizdir. ${\ displaystyle \ mathbf {t}}$

Optimal üçgenleme

Ayrıca bakınız

• Paket ayarı
• Çizgi-çizgi kesişimi

Referanslar

• Richard Hartley ve Andrew Zisserman (2003). Bilgisayarla görüşte Çoklu Görünüm Geometrisi . Cambridge University Press. ISBN   978-0-521-54051-3 .

Dış bağlantılar

• Matlab'da iki görünüm ve çoklu görünüm üçgenleme