Pengantar Penyesuaian Bundel — Metode Kuadrat Terkecil Nonlinier yang Memperbaiki Posisi Kamera dan Titik 3D Secara Bersama-sama

Posisi kamera dan titik 3D yang diperoleh Structure from Motion dan Visual-SLAM melalui triangulasi dan PnP, paling banter, hanyalah nilai awal kasar dari aproksimasi linier dan pemrosesan sekuensial. Derau per gambar, kesalahan kuantisasi pada titik korespondensi, dan kesalahan yang merambat dari estimasi sekuensial semuanya menumpuk, menghasilkan rekonstruksi yang secara internal tidak konsisten. Bundle Adjustment (BA) adalah optimasi pemolesan akhir yang menyelesaikan ketidakkonsistenan ini dengan menggerakkan setiap parameter kamera dan setiap titik 3D sekaligus, meminimalkan jumlah kesalahan reproyeksi di semua titik yang diamati. Nama "bundle" berasal dari penyesuaian berkas sinar cahaya yang mengalir dari setiap titik 3D ke setiap kamera, semuanya sekaligus, sehingga sesuai dengan posisi yang diamati.

0. Ringkasan 30 Detik

• Penyesuaian Bundel (Bundle Adjustment) adalah masalah kuadrat terkecil nonlinier yang variabel tak diketahuinya adalah parameter intrinsik/ekstrinsik kamera dan koordinat titik 3D, meminimalkan jumlah kuadrat kesalahan reproyeksi di semua pengamatan.

• Masalah ini diselesaikan secara iteratif dengan metode Gauss-Newton atau Levenberg-Marquardt (LM). LM melakukan interpolasi secara halus, melalui parameter \lambda, antara metode Gauss-Newton yang tidak stabil tetapi cepat dan metode penurunan curam yang lambat tetapi stabil.

• Karena satu kamera hanya terhubung ke titik-titik yang benar-benar dilihatnya, Jacobian dan aproksimasi Hessian mengambil bentuk struktur blok yang jarang dan terorganisir berdasarkan kamera × titik. Kerapatan ini adalah kunci yang membuat masalah skala besar dapat diatasi.

• Trik komplemen Schur memanfaatkan fakta bahwa blok titik 3D saling independen (blok-diagonal), dengan terlebih dahulu menghilangkan titik-titik untuk menyelesaikan "sistem kamera yang disederhanakan" yang hanya melibatkan kamera. Inilah yang memungkinkan penyelesaian masalah pada skala puluhan ribu titik dan ribuan kamera dalam waktu yang realistis.

• Penyesuaian Bundel (Bundle Adjustment) adalah kerabat dekat optimasi Grafik Pose SLAM, yang berbeda karena variabel yang tidak diketahui mencakup titik-titik 3D itu sendiri. Ini adalah teknologi dasar yang sama, digunakan baik untuk menyelesaikan SfM maupun untuk optimasi lokal/global SLAM.

1. Apa yang Diterima sebagai Input, dan Apa yang Diselesaikannya?

Input terdiri dari tiga estimasi awal berikut, yang diperoleh sebagai hasil sementara dari SfM atau Visual-SLAM:

• Nilai awal untuk pose kamera \{K_i, R_i, \mathbf{t}_i\} (i=1,\dots,m; dalam banyak kasus parameter intrinsik K_i diketahui atau tetap)
• Nilai awal untuk titik 3D \{\mathbf{X}_j\} (j=1,\dots,n; koordinat kasar yang diperoleh dari triangulasi)
• Korespondensi kamera mana yang mengamati titik mana — yaitu, koordinat gambar \mathbf{u}_{ij} untuk setiap pengamatan (posisi piksel di mana kamera i melihat titik j)

Output adalah pose kamera dan titik 3D, semuanya disesuaikan secara simultan, yang lebih konsisten secara internal di setiap pengamatan. Fakta bahwa Bundle Adjustment bukanlah metode untuk membangun solusi dari awal, melainkan optimasi penyelesaian yang secara lokal memoles nilai awal yang sudah "kira-kira benar", penting untuk pembahasan konvergensi di bawah ini.

2. Fungsi Biaya: Kesalahan Reproyeksi

Ketidaksesuaian antara di mana titik 3D \mathbf{X}_j diproyeksikan ke kamera i dan koordinat gambar yang sebenarnya diamati \mathbf{u}_{ij} disebut kesalahan reproyeksi. Dengan menuliskan pose kamera i sebagai R_i, \mathbf{t}_i dan fungsi proyeksi sebagai \pi(\cdot) (peta nonlinier yang mengubah koordinat homogen menjadi koordinat piksel), residual untuk satu pengamatan adalah

Bundle Adjustment meminimalkan jumlah kuadrat residual ini di seluruh himpunan pasangan yang diamati \mathcal{O}=\{(i,j)\}.

\rho adalah fungsi kerugian yang kuat seperti kerugian Huber, yang mencegah satu outlier besar dari ketidaksesuaian mendistorsi seluruh optimasi. Persamaan ini persis sama dengan bentuk yang telah dilihat di Panduan SfM — Penyesuaian Bundel menangani inti komputasi dari penyelesaian masalah minimisasi ini.

3. Penyelesaian sebagai Kuadrat Terkecil Nonlinier: Dari Gauss-Newton ke Levenberg-Marquardt

Mengumpulkan setiap variabel yang tidak diketahui ke dalam satu vektor \mathbf{x} (semua pose kamera dan semua titik 3D disusun bersama), dan menulis seluruh himpunan residual sebagai \mathbf{r}(\mathbf{x}), target minimisasi adalah \|\mathbf{r}(\mathbf{x})\|^2. Karena \mathbf{r} bersifat nonlinier, kita menggunakan ekspansi Taylor orde pertama di sekitar estimasi saat ini \mathbf{x}_k : \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} adalah Jacobian. Dengan mensubstitusikan ini dan menyelesaikan untuk \Delta\mathbf{x} akan menghasilkan persamaan normal metode Gauss-Newton:

H=J^\mathsf{T}J adalah aproksimasi Hessian (aproksimasi Gauss-Newton, dengan mengabaikan suku orde kedua). Menyelesaikan persamaan ini untuk \Delta\mathbf{x} , memperbarui \mathbf{x}_{k+1}=\mathbf{x}_k+\Delta\mathbf{x} , dan mengulangi operasi ini hingga residual konvergen adalah keseluruhan prosedurnya.

Metode Gauss-Newton konvergen dengan cepat ketika nilai awal mendekati solusi, tetapi cenderung divergen dengan nilai awal yang buruk. Levenberg-Marquardt (LM), yang diusulkan secara independen oleh Levenberg (1944) dan Marquardt (1963), mempermudah hal ini dengan menambahkan suku redaman pada persamaan normal.

D biasanya merupakan diagonal dari J^\mathsf{T}J (atau matriks penskalaan yang setara), dan \lambda adalah koefisien redaman. Ketika \lambda kecil, ini berperilaku mendekati Gauss-Newton dan konvergen dengan cepat; ketika \lambda besar, ia mengambil langkah-langkah kecil dan aman yang lebih dekat ke penurunan paling curam. Melalui skema kontrol adaptif — mengecilkan \lambda untuk mempercepat setiap kali biaya berkurang pada setiap iterasi, dan memperbesar \lambda untuk menolak dan memperpendek langkah setiap kali biaya meningkat — LM menjembatani kecepatan Gauss-Newton dengan stabilitas penurunan paling curam. Hampir setiap implementasi praktis dari Bundle Adjustment (Ceres Solver, g2o, SBA, dan lainnya, yang akan dibahas di bawah) mengadopsi LM atau metode trust-region yang terkait erat.

4. Mengapa Jacobian Jarang?

Yang tidak diketahui dalam Bundle Adjustment adalah pose kamera (6 derajat kebebasan — 3 rotasi ditambah 3 translasi, jika parameter intrinsik tetap) × m kamera, dan titik 3D (3 derajat kebebasan) × n titik, yang berjumlah hingga 6m+3n dimensi. Dalam masalah SfM nyata dengan puluhan ribu pengamatan atau lebih, memperlakukan J^\mathsf{T}J ini secara naif sebagai matriks padat membutuhkan biaya O((6m+3n)^3) — tidak dapat diselesaikan dalam waktu yang realistis.

Yang menyelamatkan di sini adalah struktur bahwa kesalahan reproyeksi r_{ij} "hanya bergantung pada parameter kamera i dan parameter titik j." Turunan parsial terhadap kamera k\neq i atau titik l\neq j lainnya adalah nol.

Dengan kata lain, baris Jacobian yang dihasilkan oleh satu pengamatan hanya memiliki entri bukan nol di blok untuk kamera yang sesuai dan blok untuk titik yang sesuai. Jumlah baris bertambah sebanding dengan jumlah pengamatan, tetapi jumlah entri bukan nol per baris tetap konstan (kamera 6 + titik 3, atau sedikit lebih banyak jika parameter intrinsik disertakan). Kerapatan ini terlihat, ketika Anda melihat J^\mathsf{T}J, sebagai struktur blok berikut.

• B : interaksi antar parameter kamera. Ini bernilai nol kecuali jika kamera i dan k mengamati titik yang sama, sehingga memiliki struktur blok yang jarang.

• C : interaksi antar parameter titik 3D. Karena 3 derajat kebebasan satu titik j tidak pernah terhubung dengan titik lain, ini adalah matriks blok-diagonal — premis untuk trik komplemen Schur di bagian selanjutnya.

• E : interaksi antara kamera dan titik (blok bukan nol muncul untuk setiap pengamatan (i,j) ).

5. Alur Kerja Dasar

Diagram 1 · Use the button to switch views

6. Trik Komplemen Schur: Mengubah Kerapatan Menjadi Komputasi yang Dikurangi

Menggunakan struktur blok dari bagian sebelumnya, kita dapat menulis persamaan normal (J^\mathsf{T}J+\lambda D)\Delta\mathbf{x}=-J^\mathsf{T}\mathbf{r} yang dibagi menjadi pembaruan kamera \Delta\mathbf{c} dan pembaruan titik \Delta\mathbf{p} sebagai

(di mana B', C' adalah blok setelah menambahkan suku peredaman). Karena C' adalah matriks blok-diagonal, independen per titik 3D, setiap blok 3×3 dapat dibalik secara individual, dengan biaya yang kira-kira sebanding dengan jumlah titik n. Dengan menggunakan C'^{-1} untuk menghilangkan \Delta\mathbf{p}, sistem kamera yang direduksi, yang hanya melibatkan kamera, akan menghasilkan:

Sisi kiri B'-EC'^{-1}E^\mathsf{T} disebut komplemen Schur. Matriks ini memiliki ukuran 6m\times 6m (hanya bergantung pada jumlah kamera, bukan pada jumlah titik n), dan setelah \Delta\mathbf{c} diselesaikan, pembaruan setiap titik dapat dipulihkan dengan mudah menggunakan

Dalam masalah SfM yang umum, jumlah titik n dapat puluhan kali lipat jumlah kamera m, jadi alih-alih menyelesaikan sistem dengan dimensi 6m+3n secara naif, Anda hanya perlu menangani komplemen Schur, dengan dimensi 6m. Inilah ide inti yang membuat Bundle Adjustment praktis dapat dipecahkan bahkan pada skala puluhan ribu titik. Secara teoritis, ide ini diorganisir oleh Triggs dkk. dalam "Bundle Adjustment — A Modern Synthesis" (2000), dan merupakan implementasi internal standar dalam pustaka saat ini seperti Ceres Solver dan g2o.

Ceres Solver menawarkan beberapa opsi untuk menyelesaikan sistem yang direduksi ini: DENSE_SCHUR, yang menyelesaikannya sebagai matriks padat (hingga beberapa ratus kamera); SPARSE_SCHUR, yang memanfaatkan sparsitas melalui penataan ulang (ribuan kamera); dan ITERATIVE_SCHUR, yang menerapkan gradien konjugasi pada komplemen Schur (untuk masalah skala yang lebih besar). Memilih di antara opsi-opsi ini berdasarkan skala masalah adalah aturan praktis yang umum.

7. Kebebasan Pengukur: Arah-arah di Mana Solusi Tidak Ditentukan Secara Unik

Penyesuaian Bundel mempertahankan derajat kebebasan yang dapat menggerakkan seluruh rangkaian parameter tanpa mengubah nilai fungsi biaya. Menggerakkan setiap kamera dan setiap titik 3D bersama-sama dengan rotasi, translasi, dan skala yang sama membuat kesalahan reproyeksi sama sekali tidak berubah (untuk kasus monokular saja, skala absolut juga tidak dapat ditentukan). Derajat kebebasan ini disebut kebebasan pengukur. Jika tidak ditangani, hal itu membuat J^\mathsf{T}J menjadi singular (kekurangan peringkat), yang membuat persamaan normal tidak dapat dipecahkan, atau secara numerik tidak stabil.

Dalam praktiknya, hal ini diatasi dengan memperbaiki posisi dua kamera pertama atau satu panjang garis dasar, atau dengan mengandalkan fakta bahwa istilah peredaman LM sendiri \lambda D secara implisit meregulasi arah singular ini. Ketika informasi skala absolut atau posisi absolut tersedia — misalnya dari GPS atau IMU — wajar untuk menggunakannya sebagai batasan tambahan untuk memperbaiki pengukur.

8. Perbedaan dari Optimasi Grafik Pose

Optimasi Grafik Pose, yang dibahas dalam Panduan Penutupan Loop, juga termasuk dalam kerangka matematika yang sama dengan Penyesuaian Bundel dalam arti bahwa ia meminimalkan, dengan kerugian yang kuat, residual kuadrat terkecil nonlinier yang dibangun dengan peta \mathrm{Log}. Perbedaannya terletak pada apa sebenarnya yang tidak diketahui.

Dalam sistem Visual-SLAM yang sebenarnya, umum untuk melihat pembagian kerja: penyesuaian bundel lokal (BA lokal), termasuk titik 3D, menyempurnakan area di sekitar keyframe berdasarkan per frame, sementara optimasi Pose Graph yang ringan tanpa titik 3D eksplisit dengan cepat mengoreksi lintasan global setiap kali penutupan loop terdeteksi. Penyesuaian bundel penuh termasuk titik 3D (BA global) lebih akurat tetapi secara komputasi mahal, sehingga tidak dapat dijalankan sering dalam situasi yang membutuhkan kinerja waktu nyata.

9. Implementasi Representatif

• Ceres Solver: sebuah pustaka kuadrat terkecil nonlinier serbaguna yang dikembangkan oleh Google, digunakan dalam produksi sejak tahun 2010. Pustaka ini memiliki solver berbasis Schur yang terintegrasi, dan digunakan sebagai backend penyesuaian bundel untuk banyak implementasi SfM/SLAM, termasuk COLMAP.

• g2o: sebuah kerangka kerja optimasi graf yang diterbitkan oleh Kümmerle dkk. di ICRA 2011, mampu menangani optimasi Pose Graph SLAM dan penyesuaian bundel dalam kerangka kerja yang sama. Kerangka kerja ini telah banyak digunakan sebagai backend dari keluarga ORB-SLAM.

• SBA (Sparse Bundle Adjustment): sebuah implementasi awal yang tersedia untuk umum yang dikhususkan untuk penyesuaian bundel jarang, diterbitkan oleh Lourakis dan Argyros di ACM Transactions on Mathematical Software pada tahun 2009. Implementasi ini sering dirujuk sebagai contoh representatif yang secara eksplisit mengimplementasikan trik komplemen Schur.

• BA bawaan COLMAP: secara internal menggunakan Ceres Solver, secara otomatis beralih antara penyesuaian bundel lokal dan global pada setiap langkah SfM Inkremental.

10. Kondisi Sulit dan Kasus Kegagalan Umum

• Nilai awal yang buruk: Penyesuaian Bundel adalah optimasi lokal — jika nilai awal jauh dari solusi sebenarnya, ia dapat konvergen ke solusi lokal yang salah, atau gagal konvergen sama sekali. Kualitas nilai awal yang diperoleh dari triangulasi atau PnP menentukan akurasi akhir.
• Titik dengan sedikit pengamatan atau paralaks kecil: sebuah titik yang diamati hanya dari sejumlah kecil gambar, atau dengan sedikit paralaks, cenderung memiliki Jacobian yang tidak terkondisi dengan baik, dan dapat meninggalkan kesalahan residual besar yang terkonsentrasi murni di sepanjang arah kedalaman.

• Kontaminasi outlier yang berat: dengan banyak ketidaksesuaian yang bercampur, bahkan kerugian yang kuat pun tidak dapat sepenuhnya menyerapnya, dan titik-titik tetangga yang benar dapat berakhir terseret dan terdistorsi juga.

• Masalah skala sangat besar: untuk rekonstruksi skala kota dengan jumlah pengamatan mencapai jutaan, bahkan dengan komplemen Schur, biaya komputasi dan memori menjadi tidak dapat diabaikan, sehingga masalah tersebut perlu dipisah dan diparalelkan, atau dikombinasikan dengan teknik perkiraan (seperti memperhalus wilayah kepercayaan LM).

• Kebebasan gauge yang tidak ditangani: seperti yang disebutkan di atas, melupakan untuk memperbaiki gauge menyebabkan ketidakstabilan numerik, yang menyebabkan kegagalan konvergensi, atau menyimpang ke solusi yang tidak fisik.

11. Pilihan Praktis

• Jika Anda membutuhkan akurasi padat sebagai tahap akhir SfM, menjalankan penyesuaian bundel penuh di akhir — terlepas dari apakah Anda menggunakan strategi Inkremental atau Global — adalah aturan standar. Mengikuti pengaturan default dari implementasi yang ada seperti COLMAP kemungkinan besar tidak akan membawa Anda jauh dari tujuan.

• Untuk SLAM waktu nyata, penyesuaian bundel penuh pada setiap frame terlalu mahal secara komputasi. Desain praktis menggabungkan penyesuaian bundel lokal hanya pada kumpulan keyframe terbaru, dengan optimasi Pose Graph yang hanya aktif saat penutupan loop.

• Jika Anda membangun pipeline sendiri dari awal, masuk akal untuk membangunnya di atas pustaka seperti Ceres Solver atau g2o. Menulis implementasi komplemen Schur dari nol memberikan sedikit manfaat pembelajaran dibandingkan dengan biaya verifikasi kebenarannya.
• Untuk rekonstruksi skala besar, skala kota, daripada mengandalkan penyesuaian bundel tunggal, pertimbangkan metode yang membagi masalah berdasarkan wilayah dan mengintegrasikannya secara hierarkis (ini juga umum dilakukan sebagai tahap awal yang mengarah ke Multi-View Stereo, yang dibahas di bawah).

12. Ringkasan

Penyesuaian Bundel adalah masalah kuadrat terkecil nonlinier yang secara simultan meminimalkan kesalahan reproyeksi di setiap kamera dan setiap titik 3D, yang diselesaikan secara iteratif melalui metode Levenberg-Marquardt. Trik komplemen Schur, yang memanfaatkan kelangkaan hubungan pengamatan titik kamera, adalah yang membuat optimasi ini dapat diselesaikan dalam waktu yang realistis bahkan pada skala puluhan ribu titik. Meskipun memiliki kerangka kerja matematika yang sama dengan optimasi Pose Graph, pilihan antara keduanya bergantung pada apakah titik 3D dipegang secara eksplisit, dan ini adalah teknologi dasar bersama yang pada akhirnya mendukung akurasi SfM dan SLAM.

Referensi

• 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)
• Dokumentasi resmi Ceres Solver: Non-linear Least Squares
• Dokumentasi resmi Ceres Solver: Penyelesai Linier Berbasis Schur
• Hartley & Zisserman, Geometri Tampilan Ganda dalam Visi Komputer (halaman resmi penulis)