Paket Ayarlaması Temel Bilgileri — Kamera Pozlarını ve 3B Noktaları Birlikte İyileştiren Doğrusal Olmayan En Küçük Kareler Yöntemi

Structure from Motion ve Visual-SLAM yöntemlerinin üçgenleme ve PnP (Pun-Pun) yoluyla elde ettiği kamera pozisyonları ve 3B noktaları, en iyi ihtimalle, doğrusal yaklaşımlardan ve sıralı işlemden elde edilen kaba başlangıç değerleridir. Görüntü başına gürültü, karşılık gelen noktalardaki niceleme hatası ve sıralı tahminden kaynaklanan yayılan hata birikerek, mevcut haliyle içsel olarak tutarsız bir yeniden yapılandırma bırakır. Paket Ayarlaması (BA), her kamera parametresini ve her 3B noktasını aynı anda hareket ettirerek, tüm gözlemlenen noktalardaki yeniden projeksiyon hatasının toplamını en aza indirerek bu tutarsızlığı çözen son parlatma optimizasyonudur. "Paket" adı, her 3B noktadan her kameraya giden ışık ışınlarının demetini, gözlemlenen pozisyonlarla uyumlu olacak şekilde aynı anda ayarlamaktan gelir.

0. 30 Saniyelik Özet

• Paket Ayarlaması, bilinmeyenleri kameraların içsel/dışsal parametreleri ve 3 boyutlu nokta koordinatları olan, tüm gözlemler üzerinden karelenmiş yeniden projeksiyon hatasının toplamını en aza indiren doğrusal olmayan bir en küçük kareler problemidir.

• Gauss-Newton yöntemi veya Levenberg-Marquardt (LM) yöntemi ile yinelemeli olarak çözülür. LM, \lambda parametresi aracılığıyla, kararsız ancak hızlı Gauss-Newton yöntemi ile yavaş ancak kararlı en dik iniş yöntemi arasında yumuşak bir şekilde enterpolasyon yapar.

• Tek bir kamera yalnızca gerçekten gördüğü noktalara bağlı olduğundan, Jacobian ve Hessian yaklaşımı, kamera × nokta tarafından organize edilen seyrek, blok yapılı bir biçim alır. Bu seyreklik, büyük ölçekli problemleri çözülebilir kılan anahtardır.

• Schur tamamlayıcı yöntemi, 3 boyutlu nokta bloklarının birbirlerinden bağımsız (blok-diyagonal) olmasından yararlanarak, önce noktaları ortadan kaldırıp yalnızca kameraları içeren küçük bir "azaltılmış kamera sistemi"ni çözmeyi sağlar. Bu, on binlerce nokta ve binlerce kamera ölçeğindeki problemleri gerçekçi bir sürede çözmeyi mümkün kılar.

• Paket Ayarlaması, SLAM'in Poz Grafiği optimizasyonunun yakın bir akrabasıdır ve bilinmeyenleri arasında 3 boyutlu noktaların kendilerinin de yer alması bakımından farklılık gösterir. Hem SfM'yi tamamlamak hem de SLAM'in yerel/küresel optimizasyonu için kullanılan ortak bir temel teknolojidir.

1. Giriş Olarak Ne Alır ve Ne Çözer?

Giriş, SfM veya Visual-SLAM'den ara sonuçlar olarak elde edilen aşağıdaki üç başlangıç tahmininden oluşur:

• Kamera pozisyonları için başlangıç değerleri \{K_i, R_i, \mathbf{t}_i\} ( i=1,\dots,m ; birçok durumda içsel parametreler K_i bilinir veya sabittir)
• 3B noktalar için başlangıç değerleri \{\mathbf{X}_j\} ( j=1,\dots,n ; üçgenlemeden elde edilen kaba koordinatlar)
• Hangi kameranın hangi noktayı gözlemlediğinin karşılığı — yani, her gözlem için görüntü koordinatları \mathbf{u}_{ij} (kamera i'nin j noktasını gördüğü piksel konumu)

Çıktı, ince ayarlanmış kamera pozisyonları ve 3B noktalarıdır. Aynı anda, her gözlemde daha tutarlı olan çözümler elde edilir. Paket Ayarlaması'nın sıfırdan bir çözüm oluşturma yöntemi değil, zaten "kabaca doğru" olan bir başlangıç değerini yerel olarak iyileştiren bir sonlandırma optimizasyonu olması, aşağıdaki yakınsama tartışması için önemlidir.

2. Maliyet Fonksiyonu: Yeniden Projeksiyon Hatası

Bir 3B noktası \mathbf{X}_j'un kamera i'a yansıtıldığı yer ile gerçekte gözlemlenen görüntü koordinatı \mathbf{u}_{ij} arasındaki uyumsuzluğa yeniden projeksiyon hatası denir. i kamerasının pozisyonunu R_i, \mathbf{t}_i ve projeksiyon fonksiyonunu \pi(\cdot) (homojen koordinatları piksel koordinatlarına dönüştüren doğrusal olmayan harita) olarak yazarsak, bir gözlem için artık değer şu şekildedir:

Paket Ayarlaması, gözlemlenen tüm çiftler kümesi \mathcal{O}=\{(i,j)\} üzerindeki bu artık değerin karelerinin toplamını en aza indirir.

\rho, Huber kaybı gibi sağlam bir kayıp fonksiyonudur ve uyumsuzluktan kaynaklanan tek bir büyük aykırı değerin tüm optimizasyonu bozmasını önler. Bu denklem, SfM Temel Kılavuzunda zaten görülenle tamamen aynı formdadır — Paket Ayarlaması, bu en aza indirme problemini çözmenin hesaplama çekirdeğiyle ilgilenir.

3. Doğrusal Olmayan En Küçük Kareler Olarak Çözme: Gauss-Newton'dan Levenberg-Marquardt'a

Tüm bilinmeyenleri tek bir vektör \mathbf{x} (tüm kamera pozisyonları ve tüm 3B noktaları birlikte) halinde toplayıp, artıkların tamamını \mathbf{r}(\mathbf{x}) olarak yazarsak, minimizasyon hedefi \|\mathbf{r}(\mathbf{x})\|^2 olur. \mathbf{r} doğrusal olmadığı için, mevcut tahmin \mathbf{x}_k etrafında birinci dereceden bir Taylor açılımı kullanırız: \mathbf{r}(\mathbf{x}_k+\Delta\mathbf{x})\approx \mathbf{r}(\mathbf{x}_k)+J\Delta\mathbf{x}. J=\partial \mathbf{r}/\partial \mathbf{x} ise Jacobian'dır. Bunu yerine koyup \Delta\mathbf{x} için çözdüğümüzde Gauss-Newton yönteminin normal denklemini elde ederiz:

H=J^\mathsf{T}J, Hessian yaklaşımıdır (ikinci dereceden terimleri göz ardı eden Gauss-Newton yaklaşımı). Bu denklemi \Delta\mathbf{x} için çözmek, \mathbf{x}_{k+1}=\mathbf{x}_k+\Delta\mathbf{x}'u güncellemek ve kalıntı yakınsayana kadar bu işlemi tekrarlamak tüm prosedürü oluşturur.

Gauss-Newton yöntemi, başlangıç değeri çözüme yakın olduğunda hızlı bir şekilde yakınsar, ancak kötü bir başlangıç değeriyle ıraksama eğilimindedir. Levenberg (1944) ve Marquardt (1963) tarafından bağımsız olarak önerilen Levenberg-Marquardt (LM) yöntemi, normal denkleme bir sönümleme terimi ekleyerek bunu kolaylaştırır.

D genellikle J^\mathsf{T}J'ün (veya eşdeğer bir ölçekleme matrisinin) köşegenidir ve \lambda sönümleme katsayısıdır. \lambda küçük olduğunda, Gauss-Newton'a yakın davranır ve hızlı bir şekilde yakınsar; \lambda büyük olduğunda, en dik inişe daha yakın küçük, güvenli adımlar atar. Uyarlanabilir bir kontrol şeması aracılığıyla — maliyet her yinelemede azaldığında hızlanmak için \lambda'yi küçültün ve maliyet arttığında adımı reddetmek ve kısaltmak için \lambda'i büyütün — LM, Gauss-Newton'un hızını en dik inişin kararlılığıyla birleştirir. Paket Ayarlaması'nın (Ceres Solver, g2o, SBA ve aşağıda tartışılan diğerleri) neredeyse her pratik uygulaması LM'yi veya yakından ilgili bir güven bölgesi yöntemini benimser.

4. Jacobian Neden Seyrek?

Paket Ayarlaması'nın bilinmeyenleri, kamera pozisyonu (6 serbestlik derecesi — içsel parametreler sabitse 3 dönüş artı 3 öteleme) × m kamera ve 3 boyutlu nokta (3 serbestlik derecesi) × n noktadır ve toplamda 6m+3n boyuta kadar ulaşabilir. On binlerce veya daha fazla gözlem içeren gerçek SfM problemlerinde, bunu J^\mathsf{T}J yoğun bir matris olarak ele almak O((6m+3n)^3) maliyetine yol açar — gerçekçi bir zamanda çözülemez.

Burada kurtarıcı olan şey, yeniden projeksiyon hatasının r_{ij} "yalnızca kamera i'nin parametrelerine ve nokta j'nın parametrelerine bağlı" olmasıdır. Diğer herhangi bir kamera k\neq i veya nokta l\neq j ile ilgili kısmi türevler özdeş olarak sıfırdır.

Başka bir deyişle, tek bir gözlem tarafından oluşturulan Jacobian'ın satırı, yalnızca ilgili kamera bloğunda ve ilgili nokta bloğunda sıfırdan farklı girişlere sahiptir. Satır sayısı gözlem sayısıyla orantılı olarak artar, ancak satır başına sıfırdan farklı giriş sayısı sabit kalır (kamera 6 + nokta 3 veya içsel parametreler dahil edilirse biraz daha fazla). Bu seyreklik, J^\mathsf{T}J'ye baktığınızda aşağıdaki blok yapısı olarak ortaya çıkar.

• B: kamera parametreleri arasındaki etkileşimler. Kameralar i ve k ortak bir noktayı gözlemlemedikçe bu sıfırdır, bu nedenle seyrek bir blok yapısına sahiptir.

• C: 3 boyutlu nokta parametreleri arasındaki etkileşimler. Bir noktanın j 3 serbestlik derecesi hiçbir zaman başka bir noktayla eşleşmediğinden, bu bir blok-diyagonal matristir - bir sonraki bölümde Schur tamamlayıcısı hilesinin öncülüdür.

• E: Kameralar ve noktalar arasındaki etkileşimler (her gözlem (i,j) için sıfır olmayan bir blok görünür).

5. Temel İşlem Hattı

Diagram 1 · Use the button to switch views

Her yinelemede, yeniden projeksiyon hatası yeniden hesaplanır, seyrek Jacobian oluşturulur, Schur tamamlayıcısı aracılığıyla yalnızca kamera içeren indirgenmiş sistem çözülür ve LM'nin adım kontrolü ile güncellenir. Bu, maliyetteki değişim bir eşiğin altına düşene veya maksimum yineleme sayısına ulaşılana kadar tekrarlanır.

6. Schur Tamamlama Hilesi: Seyrekliği Azaltılmış Hesaplamaya Dönüştürme

Önceki bölümdeki blok yapısını kullanarak, normal denklemi (J^\mathsf{T}J+\lambda D)\Delta\mathbf{x}=-J^\mathsf{T}\mathbf{r} kamera güncellemesi \Delta\mathbf{c} ve nokta güncellemesi \Delta\mathbf{p} olarak şu şekilde yazabiliriz:

(burada B', C' sönümleme terimi eklendikten sonraki bloklardır). C', 3B nokta başına bağımsız bir blok-diyagonal matris olduğundan, her 3×3 blok ayrı ayrı tersine çevrilebilir ve bu işlem, yaklaşık olarak nokta sayısı n ile orantılı bir maliyete sahiptir. Bu C'^{-1}'i kullanarak \Delta\mathbf{p}'yi ortadan kaldırmak, yalnızca kameraları içeren azaltılmış kamera sistemini şu şekilde bırakır:

Sol taraftaki B'-EC'^{-1}E^\mathsf{T}, Schur tamamlayıcısı olarak adlandırılır. Bu matrisin boyutu 6m\times 6m'tir (sadece kamera sayısına bağlıdır, nokta sayısına n bağlı değildir) ve \Delta\mathbf{c} çözüldükten sonra, her noktanın güncellemesi şu şekilde ucuz bir şekilde geri kazanılabilir:

Tipik bir SfM probleminde, nokta sayısı n, kamera sayısının m onlarca katı olabilir, bu nedenle 6m+3n boyutlu bir sistemi basitçe çözmek yerine, sadece 6m boyutlu Schur tamamlayıcısını ele almanız gerekir. Bu, Paket Ayarlamasını on binlerce nokta ölçeğinde bile pratik olarak çözülebilir kılan temel fikirdir. Teorik olarak Triggs ve diğerlerinin "Bundle Adjustment — A Modern Synthesis" (2000) adlı çalışmasında ele alınmıştır ve Ceres Solver ve g2o gibi güncel kütüphanelerde standart iç uygulama olarak kullanılmaktadır.

Ceres Solver, bu indirgenmiş sistemi çözmek için birden fazla seçenek sunar: DENSE_SCHUR, yoğun bir matris olarak çözer (birkaç yüz kameraya kadar); SPARSE_SCHUR, yeniden sıralama yoluyla seyrekliği kullanır (binlerce kamera); ve ITERATIVE_SCHUR, Schur tamamlayıcısına eşlenik gradyan uygular (daha büyük ölçekli problemler için). Problemin ölçeğine göre bunlar arasından seçim yapmak pratik bir kuraldır.

7. Ölçü Serbestliği: Çözümün Benzersiz Bir Şekilde Belirlenmediği Yönler

Bundle Adjustment, maliyet fonksiyonunun değerini değiştirmeden tüm parametre kümesini hareket ettirebilen bir serbestlik derecesini korur. Her kamerayı ve her 3B noktayı aynı döndürme, öteleme ve ölçekle birlikte hareket ettirmek, yeniden projeksiyon hatasını tamamen değiştirmez (sadece monoküler bir durumda, mutlak ölçek de belirsizdir). Bu serbestlik derecesine ölçüm serbestliği denir. Ele alınmadığı takdirde, J^\mathsf{T}J'yı tekil (sıralama eksikliği olan) hale getirir; bu da normal denklemi ya çözülemez ya da sayısal olarak kararsız hale getirir.

Pratikte, bu durum ilk iki kameranın pozisyonunu veya bir temel çizgi uzunluğunu sabitleyerek veya LM'nin kendi sönümleme terimi \lambda D'nin bu tekil yönü örtük olarak düzenlediği gerçeğine güvenerek aşılır. Mutlak ölçek veya mutlak pozisyon bilgisi mevcut olduğunda - örneğin GPS veya bir IMU'dan - bunu ölçümü sabitlemek için ek bir kısıtlama olarak kullanmak doğaldır.

8. Poz Grafiği Optimizasyonundan Farkı

Döngü Kapanışı Temelleri'de ele alınan Poz Grafiği optimizasyonu, sağlam bir kayıp fonksiyonuyla, \mathrm{Log} haritasıyla oluşturulan doğrusal olmayan en küçük kareler kalıntısını en aza indirgemesi anlamında, Paket Ayarlaması ile aynı matematiksel çerçeveye aittir. Fark, bilinmeyenlerin gerçekte ne olduğuyla ilgilidir.

Gerçek Görsel-SLAM sistemlerinde, iş bölümü yaygın olarak görülür: 3B noktaları içeren yerel demet ayarlaması (yerel BA), kare başına anahtar karelerin etrafındaki alanı iyileştirirken, açık 3B noktaları içermeyen hafif Poz Grafiği optimizasyonu, bir döngü kapanışı tespit edildiğinde küresel yörüngeyi hızla düzeltir. 3B noktaları içeren tam demet ayarlaması (küresel BA) daha doğrudur ancak hesaplama açısından maliyetlidir, bu nedenle gerçek zamanlı performans gerektiren durumlarda sık sık çalıştırılamaz.

9. Temsili Uygulamalar

• Ceres Solver: Google tarafından geliştirilen, 2010 yılından beri üretimde kullanılan genel amaçlı doğrusal olmayan en küçük kareler kütüphanesidir. Schur tabanlı çözücüler içerir ve COLMAP dahil olmak üzere birçok SfM/SLAM uygulamasının paket ayarlama arka ucu olarak kullanılır.

• g2o: Kümmerle ve diğerleri tarafından ICRA 2011'de yayınlanan, SLAM'ın Poz Grafiği optimizasyonunu ve paket ayarlamasını aynı çerçeve içinde ele alabilen bir grafik optimizasyon çerçevesidir. ORB-SLAM ailesinin arka ucu olarak yaygın olarak kullanılmıştır.

• SBA (Seyrek Paket Ayarlaması): 2009 yılında Lourakis ve Argyros tarafından ACM Transactions on Mathematical Software'de yayınlanan, seyrek paket ayarlaması için özel olarak geliştirilmiş, erken dönemde kamuya açık bir uygulamadır. Schur tamamlayıcısı yöntemini açıkça uygulayan temsili bir örnek olarak sıklıkla referans gösterilir.

• COLMAP'ın dahili BA'sı: Dahili olarak Ceres Solver'ı kullanır ve Artımlı SfM'nin her adımında yerel ve küresel demet ayarlaması arasında otomatik olarak geçiş yapar.

10. Zor Koşullar ve Yaygın Başarısızlık Durumları

• Kötü başlangıç değerleri: Demet Ayarlaması yerel bir optimizasyondur; başlangıç değeri gerçek çözüme uzaksa, yanlış yerel çözüme yakınsayabilir veya hiç yakınsayamayabilir. Üçgenleme veya PnP'den elde edilen başlangıç değerinin kalitesi, nihai doğruluğu belirler.

• Az sayıda gözlem veya küçük paralaks içeren noktalar: Çok az sayıda görüntüden gözlemlenen veya az paralaks içeren bir nokta, kötü koşullu bir Jacobian'a sahip olma eğilimindedir ve yalnızca derinlik yönünde yoğunlaşmış büyük bir artık hata bırakabilir.

• Aşırı aykırı değer kirliliği: Birçok uyumsuzluğun karışmasıyla, sağlam bir kayıp fonksiyonu bile bunları tamamen absorbe edemez ve doğru komşu noktalar da sürüklenip bozulabilir.

• Son derece büyük ölçekli problemler: Milyonlara ulaşan gözlem sayımlarına sahip şehir ölçekli yeniden yapılandırmalar için, Schur tamamlayıcısı ile bile, hesaplama ve bellek maliyetleri göz ardı edilemez hale gelir ve problemin bölünüp paralelleştirilmesini veya yaklaşık tekniklerle (LM'nin güven bölgesini kabalaştırmak gibi) birleştirilmesini gerektirir.

• Ele alınmayan ölçüm serbestliği: Yukarıda belirtildiği gibi, ölçümü düzeltmeyi unutmak sayısal kararsızlığa neden olur, bu da yakınsama başarısızlığına veya fiziksel olmayan bir çözüme doğru sapmaya yol açar.

11. Pratik Seçenekler

• SfM'nin son aşamasında yoğun doğruluk gerekiyorsa, artımlı veya küresel strateji kullanmış olmanızdan bağımsız olarak, sonunda tam bir demet ayarlaması çalıştırmak standart kuraldır. COLMAP gibi mevcut bir uygulamanın varsayılan ayarlarını takip etmek sizi muhtemelen çok yanlış bir yola sokmaz.

• Gerçek zamanlı SLAM için, her karede tam paket ayarlaması çok fazla hesaplama maliyeti gerektirir. Pratik bir tasarım, yalnızca en son anahtar kareler kümesi üzerinde yerel paket ayarlamasını, yalnızca döngü kapanışında tetiklenen Poz Grafiği optimizasyonu ile birleştirir.

• Kendi işlem hattınızı sıfırdan oluşturuyorsanız, Ceres Solver veya g2o gibi bir kütüphane üzerine inşa etmek mantıklıdır. Sıfırdan bir Schur-tamamlayıcı uygulaması yazmak, doğruluğunu doğrulama maliyetine kıyasla çok az öğrenme faydası sağlar.

• Büyük ölçekli, şehir ölçekli yeniden yapılandırma için, tek bir paket ayarlamasına güvenmek yerine, problemi bölgeye göre bölen ve hiyerarşik olarak entegre eden yöntemleri göz önünde bulundurun (bu, aşağıda tartışılan Çoklu Görünüm Stereo'ye beslenen ön bir aşama olarak da yaygın olarak yapılır).

12. Özet

Paket Ayarlaması, her kamera ve her 3B nokta genelinde yeniden projeksiyon hatasını eş zamanlı olarak en aza indirgeyen, Levenberg-Marquardt yöntemiyle yinelemeli olarak çözülen doğrusal olmayan bir en küçük kareler problemidir. Kamera-nokta gözlem ilişkisinin seyreklik özelliğinden yararlanan Schur tamamlayıcısı yöntemi, bu optimizasyonu on binlerce nokta ölçeğinde bile gerçekçi bir sürede çözülebilir hale getirir. Poz Grafiği optimizasyonu ile matematiksel bir çerçeve paylaşsa da, ikisi arasındaki seçim, 3B noktalarının açıkça tutulup tutulmadığına bağlıdır ve bu, nihayetinde hem SfM hem de SLAM'ın doğruluğunu destekleyen ortak bir temel teknolojidir.

Referanslar

• Triggs, McLauchlan, Hartley & Fitzgibbon, Bundle Adjustment — A Modern Synthesis (Vision Algorithms: Theory and Practice, 2000)
• Kümmerle, Grisetti, Strasdat, Konolige & Burgard, g2o: A General Framework for Graph Optimization (ICRA 2011)
• Lourakis & Argyros, SBA: A Software Package for Generic Sparse Bundle Adjustment (ACM Transactions on Mathematical Software, 2009)
• Ceres Solver resmi dokümantasyonu: Non-linear Least Squares
• Ceres Solver resmi dokümantasyonu: Schur Tabanlı Doğrusal Çözücüler
• Hartley & Zisserman, Bilgisayar Görüşünde Çoklu Görünüm Geometrisi (yazarların resmi sayfası)