Pengantar Struktur dari Gerakan — Memulihkan Posisi 3D dan Kamera Secara Bersamaan dari Kumpulan Foto yang Tidak Terurut

Contents — find the section you need

Mengumpulkan ratusan foto orang asing dari landmark yang sama yang diambil di tempat wisata, dan memulihkan model 3D bangunan tersebut beserta setiap posisi pengambilan gambar — itulah Struktur dari Gerak (Structure from Motion/SfM). Dari sekumpulan gambar yang urutan pengambilan gambarnya, posisi kamera relatif, dan bahkan lensa yang digunakan semuanya tidak diketahui sebelumnya, SfM secara bersamaan memulihkan awan titik 3D yang konsisten secara geometris dan pose kamera. Sementara Visual-SLAM dan VO/VIO melacak posisi "saat ini" robot atau kamera secara real-time, SfM sebagian besar dijalankan secara offline, memprioritaskan akurasi untuk membangun seluruh adegan. Artikel ini membahas struktur internal SfM dari awal, berpusat pada perbedaan ini.

0. Ringkasan 30 Detik

SfM adalah proses pemulihan baik awan titik 3D sparse suatu adegan maupun parameter intrinsik dan ekstrinsik setiap kamera secara simultan dari banyak gambar, melalui pencocokan titik fitur dan verifikasi geometris.
Secara umum terdapat dua strategi rekonstruksi: SfM Inkremental, yang menambahkan kamera satu per satu secara berurutan, dan SfM Global, yang pertama-tama menemukan pose relatif setiap pasangan dan kemudian menyelesaikan pose global sekaligus.
SfM Inkremental kuat, tetapi karena berurutan, ia rentan terhadap drift (kesalahan terakumulasi). SfM Global menyelesaikan semuanya sekaligus dan karenanya tahan terhadap drift, tetapi lebih lemah terhadap pose relatif dengan banyak outlier.
Titik 3D dan pose kamera yang diperoleh dari triangulasi, dengan sendirinya, hanyalah perkiraan kasar yang dipengaruhi oleh noise gambar. Penyesuaian Bundel yang meminimalkan kesalahan reproyeksi secara simultan adalah hal yang pada akhirnya menentukan akurasi SfM.
SfM dan Visual-SLAM memiliki geometri dasar yang sama, tetapi berbeda dalam filosofi desain: SfM adalah pemrosesan batch offline yang memprioritaskan akurasi dan kelengkapan, sedangkan SLAM adalah pemrosesan online, real-time yang memprioritaskan kecepatan dan kontinuitas.

1. Apa yang Diterima SfM sebagai Input, dan Apa yang Dihasilkannya?

Inputnya adalah sekumpulan gambar $\{I_1,\dots,I_N\}$ yang urutan pengambilan gambarnya dan posisi relatifnya tidak diketahui. Setiap gambar bahkan dapat diambil dengan kamera yang berbeda, lensa yang berbeda, dan pada waktu yang berbeda. Outputnya terdiri dari tiga hal:

Posisi kamera setiap gambar $i$ $P_i=K_i[R_i\mid\mathbf{t}_i]$ (parameter intrinsik dan ekstrinsik)
Sekumpulan titik 3D dalam adegan $\{\mathbf{X}_j\}$ (sebagian besar berupa awan titik jarang yang sesuai dengan titik fitur)
Korespondensi (jejak) gambar mana yang mengamati titik 3D mana

Di mana Panduan Kalibrasi Kamera memulihkan parameter intrinsik kamera tunggal dari pola kalibrasi tetap, SfM adalah masalah invers yang lebih besar: secara simultan memulihkan parameter intrinsik dan ekstrinsik dari banyak kamera yang belum dikalibrasi atau sebagian dikalibrasi, bersama dengan struktur adegan, murni dari batasan geometris antara titik-titik yang sesuai. Jika metadata EXIF mencakup panjang fokus, itu digunakan sebagai nilai awal, tetapi akurasi akhir bergantung pada batasan geometris dari gambar itu sendiri.

Skema hasil SfM di mana lima gambar terdaftar dan satu gambar tidak terdaftar menghasilkan perkiraan pose kamera, titik 3D yang jarang, dan jalur pengamatan — Gambar 1. Keluaran SfM tipikal. Rekonstruksi tidak hanya berisi awan titik 3D, tetapi juga status registrasi gambar, perkiraan pose kamera, dan jalur yang mencatat gambar mana yang mengamati setiap titik 3D. Ini adalah skema struktural, bukan hasil akurasi dari data terukur.

Dalam penampil hasil, pertama-tama periksa apakah kamera menyatu ke wilayah yang sangat kecil, apakah awan titik terpecah atau berlipat ganda, dan apakah ada gambar yang gagal terdaftar. Penampilan seperti bangunan saja tidak menunjukkan akurasi. Evaluasi kesalahan reproyeksi, panjang jalur, dan jumlah gambar terdaftar; jika panjang survei atau GNSS tersedia, bandingkan juga dengan skala eksternal tersebut. SfM Monokular memiliki skala global yang sembarangan, sehingga jarak yang ditampilkan oleh penampil awan titik tidak secara otomatis merupakan jarak dalam meter.

2. Alur Kerja Dasar

Langkah-langkah awal — ekstraksi fitur, pencocokan, dan verifikasi geometris — persis sama dengan teknik dasar yang dibahas dalam Panduan Deteksi Fitur dan Panduan Geometri Epipolar. Keputusan desain khusus SfM berperan pada tahap setelah setiap hubungan pasangan gambar ditemukan: bagaimana menyusun setiap gambar dan setiap titik ke dalam satu kerangka koordinat yang konsisten tanpa kontradiksi — di sinilah kedua strategi SfM Inkremental dan SfM Global berbeda.

3. SfM Inkremental: Menambahkan Kamera Satu per Satu

SfM Inkremental dimulai dengan memilih pasangan gambar awal dengan paralaks yang cukup dan korespondensi yang memadai, dan membangun rekonstruksi dua pandangan pertama dengan memperkirakan Matriks Esensial/Fundamental dari geometri epipolar. Dari sana, proses selanjutnya diulang:

Pilih gambar baru yang sudah memiliki korespondensi 2D ke titik 3D yang terdaftar, dan temukan pose gambar tersebut melalui PnP.
Triangulasi titik-titik yang belum direkonstruksi dalam 3D, dari korespondensi antara gambar baru dan gambar yang sudah ada.
Perbaiki pose dan struktur dengan penyesuaian bundel lokal atau global setiap beberapa gambar.
Kembali ke langkah 1 hingga setiap gambar telah diproses, atau tidak ada lagi gambar yang dapat ditambahkan.

Pendekatan ini, yang banyak digunakan sejak buku Photo Tourism karya Snavely dkk. (2006), juga diadopsi oleh pipeline standar COLMAP sebagai Incremental SfM. Karena hanya meningkatkan sejumlah kecil variabel yang tidak diketahui secara berurutan, ini merupakan implementasi yang kuat, dan mudah untuk mendeteksi dan mengecualikan pasangan gambar yang buruk. Di sisi lain, karena pose ditumpuk satu gambar pada satu waktu, kesalahan kecil di awal akan menyebar ke gambar selanjutnya, dan dataset yang berisi loop besar (sekelompok gambar yang mengunjungi kembali tempat yang sama) cenderung mengakumulasi pergeseran. Penyesuaian bundel periodik, bersama dengan deteksi kunjungan ulang yang setara dengan penutupan loop, adalah kunci untuk menjaga agar kesalahan yang terakumulasi ini tetap terkendali.

4. SfM Global: Menyelesaikan Semua Hubungan Berpasangan Sekaligus

SfM Global tidak mendaftarkan gambar secara berurutan — pertama-tama ia menemukan pose relatif $(R_{ij},\mathbf{t}_{ij}/\|\mathbf{t}_{ij}\|)$ untuk setiap (atau subset terpilih dari) pasangan gambar. Kemudian secara bersamaan memperkirakan seluruh grafik dalam dua tahap.

Averaging rotasi menemukan himpunan rotasi kamera yang paling tidak konsisten secara global $\{R_i\}$ dari himpunan rotasi relatif berpasangan $R_{ij}$ . Metrik kesalahan yang umum digunakan menggunakan peta logaritma pada grup Lie $SO(3)$ :

\min_{\{R_i\}}\sum_{(i,j)\in\mathcal E}\rho\left(\left\|\mathrm{Log}\left(R_{ij}^\mathsf{T}R_i^\mathsf{T}R_j\right)\right\|^2\right)

$\rho$ adalah kerugian yang kuat, yang menekan pengaruh pose relatif yang salah yang bertindak sebagai outlier.

Perataan translasi, setelah rotasi diperbaiki, menemukan posisi kamera $\{\mathbf{t}_i\}$ dari himpunan arah translasi relatif $\mathbf{t}_{ij}$ . Karena translasi relatif monokular hanya memberikan arah (lihat ambiguitas skala yang dibahas dalam Panduan Geometri Epipolar), Anda perlu menyelesaikan konfigurasi yang konsisten dari banyak kendala arah berpasangan — pendekatan seperti 1DSfM, yang mencakup penghapusan outlier, telah diusulkan untuk ini.

Karena Global SfM menggunakan informasi dari setiap gambar secara bersamaan, pada prinsipnya, ia kurang rentan terhadap pergeseran berurutan yang dilihat oleh Incremental SfM, dan juga lebih mudah untuk diparalelkan secara komputasi. Tetapi jika outlier dicampur ke dalam pose relatif individu, seluruh solusi global akan terdistorsi kecuali jika dideteksi dan dikecualikan pada tahap perataan. Karya Moulon dkk. (ICCV 2013) adalah contoh representatif yang sangat meningkatkan kepraktisan Global SfM, menggabungkan perataan rotasi yang kuat dengan estimasi arah translasi menggunakan tensor trifokal.

Aspek	SfM Inkremental	SfM Global
Bagaimana rekonstruksi berlangsung	Menambahkan satu gambar pada satu waktu dari pasangan awal	Menyelesaikan semua hubungan berpasangan terlebih dahulu, kemudian mengoptimalkan secara bersamaan
Ketahanan terhadap pergeseran	Rentan terhadap propagasi sekuensial dan akumulasi kesalahan	Sedikit akumulasi kesalahan karena optimal secara global
Ketahanan terhadap outlier	Mudah dideteksi dan dihilangkan satu per satu saat menambahkan gambar	Penghapusan outlier sebelum perataan menentukan akurasi
Biaya komputasi	Sekuensial dalam jumlah gambar, cenderung menjadi berat pada skala besar	Dapat diparalelkan, tetapi memerlukan optimasi global untuk perataan
Kesulitan implementasi	Banyak contoh implementasi, mudah disetel untuk ketahanan	Teori dan implementasi perataan rotasi/translasi lebih sulit
Contoh representatif	Bundler, COLMAP (default), VisualSFM	openMVG (pipeline Global SfM), Theia

Dalam praktiknya, daripada memperlakukan keduanya sebagai pilihan yang ketat, desain hibrida juga sedang diteliti — membangun pose global kasar dengan Global SfM dan kemudian memperbaikinya secara bertahap, atau hanya menggunakan pasangan dengan kepercayaan tinggi secara Global dan menambahkan sisanya secara bertahap.

5. Triangulasi dan Manajemen Trek

Setelah pose ditemukan untuk sekelompok gambar, triangulasi titik-titik yang sesuai untuk mendapatkan titik 3D itu sendiri merupakan perluasan dari operasi geometri dua pandangan dasar. Yang spesifik untuk SfM adalah bagaimana mengelola korespondensi, yang disebut "track," ketika titik fisik yang sama diamati di tiga gambar atau lebih.

Karena pencocokan fitur dilakukan secara berpasangan, pencocokan antara gambar A–B dan B–C idealnya juga harus menyiratkan pencocokan antara A–C, tetapi dalam praktiknya, ini tidak selalu berlaku mengingat jarak deskriptor sebenarnya. Pemeriksaan konsistensi trifokal menjaga kualitas track.
Semakin banyak pengamatan yang terkandung dalam sebuah track, semakin stabil triangulasi, tetapi track yang hanya terdiri dari gambar dengan paralaks kecil di antaranya tetap menghasilkan kedalaman yang tidak stabil.
Bahkan satu kesalahan pencocokan yang tercampur dalam sebuah track tidak hanya mendistorsi posisi 3D titik tersebut — tetapi juga memengaruhi sisa penyesuaian bundel hilir secara keseluruhan. Verifikasi gaya RANSAC per track, dan penolakan track dengan kesalahan reproyeksi yang besar, keduanya diperlukan.

6. Jembatan Menuju Penyesuaian Bundel

Pose dan struktur yang diperoleh dari triangulasi linier atau PnP sekuensial, paling banter, hanyalah nilai awal. Meminimalkan kesalahan reproyeksi secara simultan di semua gambar —

\min_{\{K_i,R_i,\mathbf{t}_i,\mathbf{X}_j\}} \sum_{(i,j)\in\mathcal{O}}\rho\left(\left\|\pi\left(K_i(R_i\mathbf{X}_j+\mathbf{t}_i)\right)-\mathbf{u}_{ij}\right\|^2\right)

— adalah Penyesuaian Bundel, dan inilah yang pada akhirnya menentukan akurasi akhir SfM. Mengapa optimasi ini memiliki struktur sparse, dan mengapa komplemen Schur membuatnya dapat dipecahkan bahkan pada skala besar, adalah pertanyaan komputasi yang dibahas secara mendalam dalam Panduan Penyesuaian Bundel. Yang perlu diingat di sini adalah perbedaan cara penggunaannya: SfM Inkremental menyisipkan penyesuaian bundel lokal setiap beberapa gambar yang ditambahkan, sementara SfM Global menjalankan satu penyesuaian bundel penuh setelah setiap pose global berada di tempatnya.

7. Perbedaan dan Persamaan dengan Visual-SLAM

SfM dan Visual-SLAM menggunakan alat matematika yang sama — pencocokan fitur, geometri epipolar, PnP, dan penyesuaian bundel. Perbedaannya terletak pada tujuan dan batasannya.

Aspek	Struktur dari Gerak	Visual-SLAM
Gaya pemrosesan	Sebagian besar pemrosesan batch offline	Pemrosesan sekuensial online, waktu nyata
Urutan input	Dapat tidak berurutan (urutan apa pun, beberapa kamera yang dicampur tidak masalah)	Mengasumsikan frame yang berkesinambungan secara kronologis
Tujuan utama	Rekonstruksi 3D berkualitas tinggi yang memprioritaskan akurasi dan kelengkapan	Mempertahankan posisi diri saat ini secara waktu nyata
Lingkup optimasi	Penyesuaian bundel global di semua gambar dimungkinkan	Optimasi lokal/global terbatas pada keyframe, di bawah kendala anggaran komputasi yang ketat
Menangani kunjungan ulang	Dapat memverifikasi setiap pasangan secara offline	Harus mendeteksi dan memperbaiki penutupan loop secara online
Implementasi representatif	COLMAP, openMVG, Bundler	Keluarga ORB-SLAM, keluarga VINS

Dalam praktiknya, kombinasi seperti menggunakan peta 3D presisi tinggi yang dibangun oleh SfM sebagai peta awal atau referensi skala SLAM, atau memproses ulang lintasan keyframe SLAM secara offline dengan SfM untuk meningkatkan akurasi, juga umum. Kedua teknologi ini bukanlah teknologi yang bersaing — keduanya saling melengkapi di sepanjang sumbu waktu offline/online.

8. Implementasi Representatif

COLMAP: berpusat pada SfM Inkremental, ini adalah implementasi penelitian dan produksi yang saat ini paling banyak dirujuk, menyediakan alur kerja yang konsisten mulai dari ekstraksi fitur, pencocokan, verifikasi geometris, dan rekonstruksi hingga penyesuaian bundel dan Stereo Multi-View.
openMVG (open Multiple View Geometry): sebuah pustaka yang mengimplementasikan alur kerja SfM Inkremental dan Global. Sering dipasangkan dengan openMVS untuk rekonstruksi padat.
Bundler: implementasi SfM Inkremental perintis yang mempublikasikan hasil Photo Tourism, dan menjadi dasar perbandingan untuk banyak karya selanjutnya.
Meshroom (AliceVision): alat fotogrametri sumber terbuka dengan GUI yang menangani semuanya mulai dari SfM hingga MVS dan tekstur dalam satu kali proses.

Saat memilih pustaka, "lebih baru berarti lebih akurat" bukanlah kriteria yang tepat — pertimbangkan berdasarkan jumlah gambar yang Anda tangani, sumber daya GPU/CPU, keandalan panjang fokus EXIF, strategi pencocokan (menyeluruh/sekuensial/pohon kosakata), dan apakah Anda menginginkan satu alur kerja yang konsisten hingga MVS dan pembuatan tekstur.

9. Kondisi Sulit dan Kasus Kegagalan Umum

Adegan dengan tekstur minim atau sangat berulang: dinding seragam, permukaan berubin, dan barisan tanaman di ladang tidak menghasilkan korespondensi sama sekali, atau menghasilkan ketidakcocokan yang sering terjadi.
Kumpulan gambar dengan paralaks yang sangat kecil: foto pemandangan jauh yang diambil dengan lensa telefoto membuat triangulasi tidak stabil, menyebabkan kesalahan kedalaman yang besar.
Objek bergerak dan perubahan pencahayaan: kumpulan foto tempat wisata mencampur orang, kendaraan, dan perbedaan musiman atau waktu, memperkenalkan korespondensi yang melanggar asumsi adegan statis.
Kluster gambar terisolasi: jika bidikan terbagi menjadi dua kelompok tanpa bidang pandang yang tumpang tindih, SfM tidak dapat menyatukannya menjadi satu kerangka koordinat yang konsisten, dan rekonstruksi terfragmentasi menjadi beberapa bagian yang terputus.
Adegan simetris: fasad bangunan simetris, misalnya, dapat konvergen ke solusi cermin yang konsisten secara geometris tetapi salah secara fisik.

10. Pilihan Praktis

Jika pengambilan gambar sepenuhnya berurutan (video, atau bingkai kontinu robot), pemilihan pasangan awal SfM Inkremental menjadi mudah, dan alur kerja default COLMAP seringkali sudah cukup.
Untuk koleksi gambar skala besar seperti foto wisata internet, di mana urutan pengambilan gambar dan tumpang tindih tidak diketahui, skalabilitas SfM Global cenderung lebih unggul.
Untuk aplikasi yang membutuhkan kinerja waktu nyata (robot, AR, otomotif), pertimbangkan Visual-SLAM atau VIO sebagai pengganti SfM. Arena utama SfM adalah rekonstruksi offline dengan presisi tinggi.
Jika Anda membutuhkan bentuk 3D padat (model jala atau bertekstur), mulailah dari awan titik dan pose SfM yang jarang, lalu lanjutkan ke Multi-View Stereo.

11. Ringkasan

Structure from Motion adalah teknologi yang secara bersamaan memulihkan pose kamera dan struktur 3D, melalui pencocokan fitur dan verifikasi geometris, dari sekumpulan gambar yang tidak berurutan, menggunakan strategi Incremental SfM atau Global SfM. Incremental kuat tetapi rentan terhadap pergeseran, dan Global tahan terhadap pergeseran tetapi sensitif terhadap outlier — sebuah trade-off simetris. Di bawah strategi mana pun, akurasi akhir dicapai melalui penyesuaian bundel, yang terhubung langsung ke Visual-SLAM, teknologi saudaranya yang beroperasi pada sumbu waktu yang berbeda, dan ke Multi-View Stereo, teknologi rekonstruksi padat.

Periksa pemahaman Anda

Apakah jarak SfM yang direkonstruksi secara otomatis dalam meter?

Rekonstruksi monokular mempertahankan ambiguitas skala.

Gunakan dimensi atau informasi posisi yang diketahui untuk menetapkan skala metrik.

Referensi

What to read next

Review the backgroundPnP Primer — Memulihkan Posisi Kamera Hanya dari Titik 3D dan Sebuah Gambar Continue the seriesPengantar Penyesuaian Bundel — Metode Kuadrat Terkecil Nonlinier yang Memperbaiki Posisi Kamera dan Titik 3D Secara Bersama-sama Explore another aspect of this fieldLab kecerahan dan luminans — eksposur, gamma, dan clipping

#Structure from Motion #SfM #COLMAP #3D Reconstruction #Bundle Adjustment #Computer Vision