Kamera Pushbroom Linier

Rajiv Gupta dan Richard I. Hartley

General Electric Corporate R&D1 River Rd, Schenectady, NY, 12301Ph : (518)-387-7333, Fax : (518)-387-6845Email: gupta@crd.ge.com

Abstrak

Pemodelan sensor pushbroom yang biasa digunakan pada pencitraan satelit cukup sulit dan intensif secara komputasi karena gerak satelit yang mengorbit dalam hubungannya dengan rotasi bumi, dan non-linieritas model matematiknya termasuk dinamika orbit. Dalam paper ini, model sederhana sensor pushbroom (model pushbroom linier) diperkenalkan. Model ini mempunyai kelebihan pada kesederhanaan komputasi dan juga memberikan hasil yang sangat akurat jika dibandingkan dengan model pushbroom orbit penuh (full orbiting). Di samping penginderaan jauh, model linear pushbroom juga berguna pada banyak aplikasi pencitraan lainnya.

Solusi non-iterative sederhana digunakan untuk menyelesaikan masalah fotogrametrik standar utama untuk model linear pushbroom: komputasi parameter model dari ground- control point; penentuan parameter model relatif dari hubungan citra (image correspondence) antara dua citra; dan rekonstruksi scene dari image correspondence dan ground-control point.

Model linear pushbroom mengarah ke theoretical insight yang kira-kira akan valid untuk full model juga. Geometri epipolar dari kamera pushbroom linier diinvestigasi dan terbukti benar-benar berbeda dari kamera perspektif. Meskipun demikian, analogi matriks terhadap matriks fundamental kamera perspektif terbukti ada untuk sensor linear pushbroom. Dari hal ini dapat dilihat bahwa scene ditentukan hingga transformasi affine dari dua view dengan kamera pushbroom linier.

Kata kunci: sensor pushbroom, matriks fundamental, kamera satelit, fotogrametri.

Gambar 1: Geometri akuisisi kamera pushbroom

1. Sensor Real Pushbroom

Gambar 1 menunjukkan gambaran sensor pushbroom. Pada umumnya, kamera pushbroom terdiri dari sistem optik yang memproyeksikan citra pada sensor linear array, khususnya CCD array. Pada tiap saat hanya titik-titik yang dicitrakan tersebut yang terletak pada bidang yang didefinisikan oleh pusat optik dan garis yang berisi array sensor. Bidang ini disebut bidang view instantaneous atau secara sederhana disebut bidang view (view plan).

Sensor pushbroom dipasang pada wahana (platform) yang bergerak. Ketika platform bergerak, view plane menyapu suatu ruang wilayah tertentu. Array sensor, dan demikian juga view plane, kira-kira tegak lurus terhadap arah gerak. Besarnya charge yang terakumulasi oleh tiap sel detektor pada selang waktu tetap, disebut dwell time, menunjukkan nilai piksel pada lokasi tersebut. Sehingga, pada interval waktu yang teratur (regular), citra view plane 1-dimensi di-capture. Satu pasang citra 1-dimensi ini mewakili citra 2-dimensi.

Umumnya, kamera tidak mempunyai bagian yang bergerak. Fakta ini, yang berkontribusi secara signifikan pada kualitas geometrik internal superior, mengimplikasikan bahwa salah satu dari dimensi citra bergantung hanya pada gerak sensor.

Sensor pushbroom biasa digunakan pada kamera satelit, terutama satelit SPOT untuk generasi citra 2-D permukaan bumi. Meskipun istilah “kamera pushbroom” paling prevalensi pada bahasa penginderaan jauh dimana istilah tersebut digunakan untuk menjelaskan tipe spesifik kamera yang dipasang di satelit, prinsip akuisisi citra yang dijelaskan di atas dapat diterapkan pada banyak situasi pencitraan lainnya. Misalnya, citra yang diperoleh dari side-looking airborne radar (SLAR), tipe tertentu proyeksi CT, dan citra pada pengaturan pengukuran sinar-X dapat juga dimodelkan sebagai citra pushbroom. Sebelum melanjutkan pada formalisasi model ini, kita menjelaskan secara ringkas dua aplikasi nyata pencitra pushbroom.

Citra SPOT. Kamera HRV pada satelit SPOT merupakan contoh sistem pushbroom yang cukup dikenal baik. Untuk SPOT, sensor linear array terdiri dari 6000 pixel array sensor elektronik yang menjangkau sudut 4.2 derajat. Array sensor ini meng-capture baris citra pada interval waktu 1.504 ms (sehingga, dwell time = 1.504 ms). Ketika satelit mengorbit di atas bumi, strip kontinu citra dihasilkan. Strip ini dibagi ke citra, masing-masing terdiri dari 6000 baris. Dengan demikian, citra berukuran 6000 x 6000 piksel dapat di-capture dalam waktu 9 detik oleh satelit. Citra tersebut mencakup satu wilayah persegi (square) dengan panjang sisi kira-kira 60 km di bumi.

Pemodelan citra satelit SPOT benar-benar merupakan sesuatu yang rumit (kompleks) dan beberapa faktor harus dimasukkan dalam perhitungan.

Menurut Hukum Kepler, satelit bergerak pada orbit elliptical dengan pusat bumi sebagai salah satu fokus elips. Kecepatannya tidak konstan, tetapi bervariasi sesuai dengan posisi satelit pada orbitnya.

Bumi berotasi terhadap bidang orbit satelit, sehingga gerak satelit terhadap permukaan bumi cukup kompleks.

Satelit berotasi secara perlahan sehingga kurang lebih bisa tetap terhadap frame koordinat orthogonal yang didefinisikan sebagai berikut: sumbu-z mengarah lurus ke bawah; sumbu-x terletak di bidang yang didefinisikan oleh vektor kecepatan satelit dan sumbu z; sumbu-y tegak

lurus terhadap sumbu x dan sumbu z. Kerangka koordinat ini disebut kerangka orbit lokal ( local orbital frame). Dalam satu kali orbit, kerangka orbit lokal mengalami revolusi penuh terhadap sumbu y-nya.

Arah satelit mengalami beberapa variasi terhadap kerangka orbit lokal.

Arah view plane terhadap satelit mungkin tidak diketahui.

Beberapa parameter gerak satelit bergantung pada ketetapan fisika dan konstanta astronomik (misalnya konstanta gravitasi, massa bumi, periode rotasi bumi). Parameter lain seperti sumbu mayor, sumbu minor dan arah orbit satelit diberikan sebagai data ephemeris dengan kebanyakan citra. Dan lagi, fluktuasi arah satelit terhadap kerangka orbit lokal diberikan sebagaimana juga arah view plane. Namun demikian, telah terbukti untuk memperoleh akurasi yang lebih besar diperlukan perbaikan data ephemeris dengan menggunakan ground-control point.

Meskipun orbit satelit diketahui secara pasti, metode untuk menemukan koordinat titik citra pada ruang (space) relative rumit. Tidak ada ekspresi bentuk-tertutup (closed-form expression) yang menentukan waktu ketika satelit yang mengorbit akan melintasi suatu titik di orbitnya (waktu untuk perigee) – perlu menggunakan perkiraan. Selanjutnya, cara menentukan kapan waktu (time instant) ketika titik di bumi (ground point) akan dicitrakan harus diselesaikan dengan prosedur iteratif, seperti metode Newton. Hal ini berarti bahwa komputasi eksak citra yang dihasilkan dengan sensor pushbroom membutuhkan waktu.

Pengukuran Sinar-X. pada bentuk pencitra sinar-X paling umum yang digunakan untuk pengukuran sinar-X atau inspeksi sebagian, obyek yang akan dilihat ditempatkan antara titik sumber sinar-X dan detektor linear array. Ketika obyek digerakkan tegak lurus terhadap pancaran berkas sinar-X, citra 2-D terdiri dari beberapa proyeksi 1-D yang dikumpulkan. Tiap citra yang terkumpul dengan cara semacam itu dapat dianggap sebagai citra pushbroom yang ortografik pada arah gerak dan perspektif pada arah orthogonal. Hasil yang sangat bagus telah diperoleh dalam pemodelan setup pencitra ini seperti pada kamera linear pushbroom (lihat [1] untuk detailnya).

1.1. Overview

Pada paper ini, aproksimasi linier untuk model pushbroom diperkenalkan. Model baru ini menyederhanakan komputasi yang terlibat dalam pembuatan citra dengan pushbroom. Asumsi penyederhanaan utama yang digunakan pada penurunan model kamera ini adalah: (1) array sensor bergerak dalam garis lurus, dan (2) arahnya konstan selama durasi akuisisi citra.

Bagian 2 mendefinisikan model linear pushbroom dan menurunkan bentuk matematika dasarnya. Kita akan menunjukkan bahwa dengan asumsi di atas – sama seperti kamera perspektif – kamera linear pushbroom dapat direpresentasikan dengan matriks kamera M 3 x 4. Namun, tidak seperti kamera frame, M merepresentasikan transformasi Cremona non-linier dari ruang obyek ke ruang citra. Pada bagian berikutnya, masalah-masalah fotogrametrik standar yang berhubungan dengan penentuan parameter diselesaikan untuk model linear pushbroom. Secara khusus, tehnik linier untuk mengkomputasikan M dari satu set ground control point dijelaskan pada Bagian 3. Bagian 4 menjelaskan metode perolehan parameter kamera dari M. Semua algoritma yang didiskusikan non-iteratif, relatif sederhana, sangat cepat, dan tidak bergantung pada informasi ekstra seperti data ephemeris. Hal ini kontras dengan penentuan parameter untuk model full pushbroom, yang lambat dan membutuhkan pengetahuan mengenai parameter orbit dan ephemeris.

Selain memungkinkan efisiensi komputasi, model linear pushbroom menyediakan basis untuk analisis matematik citra pushbroom. Model full pushbroom agak sulit untuk analisisnya. Sebaliknya, kesesuaian antara model full pushbroom dan model linear pushbroom sangat dekat sehingga hasil analisis model linear pushbroom akan mudah diaplikasikan juga ke full model.

Hasil penting yang diturunkan dalam paper ini mengenai hubungan titik citra (ui, vi)T pada citra pertama dengan titik korespondensinya (ui’, vi’)T pada citra kedua (Bagian 5). Kita melihat bahwa analogi matriks terhadap matriks fundamental untuk kamera perspektif ([2, 3, 4]) ada untuk kamera linear pushbroom juga. Secara khusus, kita membuktikan bahwa terdapat matriks F, 4 x x, yang kita sebut matriks fundamental LP (linear pushbroom), seperti (ui’, ui’vi’, vi’, 1)T F(ui, uivi, vi, 1) = 0 untuk semua i. Kita juga menjelaskan tehnik non-iteratif untuk menurunkan F dari satu set korespondensi citra-ke-citra.

Sebagai contoh gain teori dan praktek yang diperoleh dengan mempelajari model linear pushbroom ada pada Theorem 5.5 dari paper ini, yang menunjukkan bahwa dua view linear pushbroom dari scene umum yang menentukan scene tersebut hingga transformasi affine. Hal ini menyebabkan timbulnya konsekuensi praktis yaitu affine invariant dari sebuah scene mungkin dikomputasikan dari dua view pushbroom. Seperti yang terlihat pada [5, 4],hasil yang sama menerapkan pada view perspektif, dimana scene ditentukan hingga proyektivitasnya dari dua view. Diharapkan model linear pushbroom yang mungkin menyediakan basis untuk pengembangan algoritma pemahaman citra lebih lanjut dengan cara yang sama dengan model kamera pinhole dapat memberikan kemajuan teori dan algoritma.

Hasil yang dijelaskan dalam paper ini dapat digunakan untuk merumuskanmetodologi lengkap untuk ekstraksi informasi stereo dari satu set yang terdiri dari dua atau lebih scene citra yang diperoleh melalui sensor linear pushbroom. Dalam metodologi ini, yang dijelaskan pada Bagian 6, tidak ada informasi mengenai arah relatif atau mutlak dan lintasan (path) sensor yang berhubungan dengan yang lainnya diperlukan. Hanya dengan menggunakan ground control point, tanpa menggunakan metode iteratif, kita dapat menentukan koordinat titik 3D yang berhubungan (korespondensi) dengan satu set matched point citra.

Kita bisa menanyakan asumsi yang menjadi dasar model linear pushbroom ketika digunakan untuk citra satelit karena array sensor mengatasi lintasan elliptical dan terlihat langsung berotasi dengan lambat. Namun, jika segmen orbit yang mana pada citra yang diperoleh kecil, dapat diperkirakan dengan garis lurus. Untuk segmen orbit yang lebih besar, kita dapat mengatasi masalah dengan cara linier piece-wise. Pada bagian akhir, akurasi model pushbroom linier didiskusikan, dan hasil beberapa algoritma yang dijelaskan disini diberikan.

Hasil eksperimen mengkonfirmasikan bahwa asumsi mengenai linieritas cukup valid sekalipun untuk orbit rendah (low-earth) dan tidak memiliki efek negatif pada akurasi. Contohnya, untuk citra SPOT dengan ukuran 6000 x 6000 piksel yang mencakup wilayah sekitar 60 x 60 km2, model linier dan full model mempunyai kesamaan dengan kurang dari setengah piksel. Hal ini terkait dengan perbedaan sekitar 6 x 10-6 radian, atau sekitar 5 meter di ground. Bagian 7 juga menjelaskan hasil eksperimen yang membandingkan model linear pushbroom dengan kamera perspektif sederhana, dan yang pasti, model orbiting pushbroom yang tidak mempunyai asumsi penyederhanaan.

2. Sensor Linear Pushbroom

Untuk menyederhanakan model kamera pushbroom yang digunakan untuk mem-fasilitasi komputasi dan untuk menyediakan basis untuk investigasi teoritik model pushbroom, asumsi penyederhanaan tertentu dapat dibuat, sebagaimana berikut.

Platform bergerak dalam garis lurus pada kecepatan konstan terhadap bumi.

Dengan demikian, arah satelit dan bidang view konstan.

Kamera ini dapat dianggap sebagai kamera perspektif yang bergerak sepanjang lintasan linier dalam ruang (space) dengan kecepatan konstan dan arah tetap (lihat Gambar 2). Lebih lanjut lagi, kamera diberi batasan sehingga setiap waktu ketika kamera mencitra hanya satu titik terletak pada satu bidang (plane), yang disebut view plane, melintasi melalui pusat kamera. Sehingga, setiap saat, proyeksi 2-dimensi view plane di atas image line terbentuk. Arah view plane tetap, dan diasumsikan bahwa gerak kamera tidak terjadi/terletak pada view plane. Akibatnya, view plane menyapu seluruh ruang sebagai waktu yang bervariasi antara -∞ dan ∞. Citra titik sembarang x dalam ruang dideskripsikan dengan dua koordinat. Koordinat pertama u mewakili waktu ketika titik x dicitrakan (yang terletak pada view plane) dan koordinat kedua v mewakili proyeksi titik pada image line.

Gambar 2. Proyeksi di bawah kamera linear pushbroom

Kami anggap kerangka koordinat orthogonal menempel (attach) pada kamera yang bergerak sebagai berikut (lihat Gambar 1). Titik origin sistem koordinat merupakan pusat proyeksi. Sumbu y terletak pada view plane sejajar (parallel) dengan bidang fokus (pada kasus ini, array sensor linier). Sumbu z terletak pada view plane tegak lurus terhadap sumbu y dan diarahkan sehingga titik yang tampak (visible) mempunyai koordinat z positif. Koordinat x tegak lurus terhadap view plane seperti sumbu x, y, dan z membentuk kerangka koordinat sebelah kanan. Ambiguitas arah sumbu y pada deskripsi di atas dapat diatasi dengan mensyaratkan bahwa gerak kamera mempunyai komponen x positif.

Pertama-tama, kita mempertimbangkan proyeksi dua dimensi. Jika koordinat titik adalah (0,y,z) terhadap frame kamera, maka koordinat titik ini dalam proyeksi 1-dimensi menjadi v = fy/z + pv dimana f merupakan panjang fokus (atau perbesaran) kamera dan pv adalah offset titik utama dalam arah v. Persamaan ini dapat dituliskan dalam bentuk

dimana w merupakan faktor skala (biasanya sama dengan z).

Agar lebih nyaman, daripada menganggap bumi stasioner dan kamera bergerak, lebih baik jika diasumsikan bahwa kamera tetap dan bumi yang bergerak. Titik pada ruang akan direpresentasikan sebagai x(t) = (x(t),y(t),z(t))T dimana t menyatakan waktu. Anggap vektor kecepatan titik terhadap frame kamera adalah –V = -(Vx,Vy,Vz)T. Tanda minus dipilih sehingga kecepatan kamera terhadap bumi adalah V. Anggap bahwa titik yang bergerak dalam ruang melintasi (cross) view plane pada waktu tim pada posisi (0,yim,zim)T. Pada citra pushbroom 2-dimensi, titik ini akan dicitrakan pada lokasi (u,v) dimana u = tim dan v dapat dinyatakan dengan menggunakan persamaan (1). Hal ini dapat dinyatakan dalam persamaan

Anggap x0 sebagai koordinat titik x yang bergerak pada waktu t = 0. Karena seluruh titik bergerak dengan kecepatan yang sama, koordinat titik sebagai fungsi waktu, dinyatakan dengan persamaan berikut

Karena view plane merupakan plane x = 0, waktu t ketika titik x menyeberangi (cross) view plane diberikan oleh t = x0/Vx. Pada waktu tersebut, titik akan berada pada posisi

Kita dapat menuliskan ini sebagai

Kombinasi persamaan ini dengan persamaan (2) memberikan persamaan

Dalam persamaan ini, (x0,y0,z0)T adalah koordinat titik x dalam frame kamera pada waktu t = 0. Normalnya, akan tetapi, koordinat titik diketahui tidak dalam sistem koordinat berbasis kamera, tetapi lebih pada beberapa sistem koordinat orthogonal eksternal tetap. Khususnya, anggap koordinat titik pada sistem koordinat semacam itu menjadi (x,y,z)T. Karena kedua kerangka koordinat orthogonal, koordinat dihubungkan dengan transformasi

Dimana T = (Tx, Ty, Tz)T adalah lokasi kamera pada waktu t = 0 pada kerangka koordinat eksternal, dan R merupakan matriks rotasi.

Yang terakhir, dengan meletakkan ini bersama dengan persamaan (5) akan menjadi

Persamaan (7) harus dibandingkan dengan persamaan dasar yang menjelaskan pinhole, atau kamera perspektif, yaitu (wu, wv, w)T = M(x, y, z, 1)T dimana (x, y, z)T adalah koordinat titik bumi, (u, v)T yang merupakan koordinat titik citra yang berhubungan (korespondensi) dan w merupakan faktor skala. Dapat terlihat bahwa citra linear pushbroom dapat dianggap sebagai citra terproyeksi pada satu arah (arah v) dan citra orthographic pada arah lainnya (arah u).

Perbedaan penting yang harus diperhatikan antara matriks kamera dari kamera perspektif dan matriks M dari pemetaan linear pushbroom. Matriks kamera perspektif kuantitasnya homogen, yang berarti bahwa dua matriks semacam itu yang berbeda dengan faktor skala konstanta bukan-nol mengkodekan (encode) pemetaan yang sama, dan dianggap ekuivalen. Sebaliknya, matriks kamera linear pushbroom kuantitasnya tidak homogen. Pengujian persamaan dasar (u, wv, w)T = Mx menunjukkan bahwa karena perkalian matriks M dengan faktor konstanta k menghasilkan dalam perkalian koordinat titik citra u dengan k. Koordinat v, sebaliknya tidak berubah. Bahkan, dua baris terakhir M dapat dikalikan dengan faktor k tanpa mengubah pemetaan. Nilai derajat kebebasan menunjukkan bahwa baris pertama M mempunyai 4 derajat kebebasan, dimana nilai dua baris lainnya 7 derajat kebebasan, karena tidak peka skalanya. Pemetaan linear-pushbroom mempunyai 11 derajat kebebasan secara keseluruhan.

Matriks kamera M pada persamaan (7) untuk sensor linear pushbroom bisa memodelkan translasi, rotasi dan scaling koordinat bumi 3-D dan juga bisa memodelkan translasi dan scaling koordinat citra 2-D. Namun, tidak bisa menghitung rotasi pada bidang citra. Secara umum, transformasi perspektif 2-D dari citra yang diperoleh dengan kamera linear pushbroom tidak dapat dianggap sebagai citra lain yang yang diambil dari kamera linear pushbroom yang berbeda. Banyak operasi resampling – misalnya citra resampling dalam stereo pair sehingga perbedaan match point hanya pada sepanjang satu koordinat citra [6] – tidak dapat dilakukan di citra linear pushbroom tanpa memecahkan kode (encode) pemetaan (7).

Titik di depan Kamera. Mengingat bahwa kerangka koordinat kamera diatur sedemikian rupa bahwa sumbu z positif diarahkan sehingga titik yang terlihat (visible point) mempunyai koordinat z positif. Mengacu pada persamaan (1) kita lihat bahwa visible point dipetakan ke titik untuk yang w > 0. Properti ini dilindungi melalui perubahan koordinat bumi. Sehingga, mengacu pada persamaan (7), kita lihat bahwa jika titik x = (x, y, z, 1)T di depan kamera, maka (u, wv, w)T = Mx dengan w > 0, dan M didefinisikan sebagai persamaan (7).

Kita telah melihat bahwa titik citra didefinisikan oleh Mx tidak berubah jika dua baris terakhir M dikalikan dengan faktor konstanta k. Namun, jika faktor konstanta k negative, maka w berubah tanda. Hal ini tidak mengubah nilai proyeksi titik, tetapi tidak mempengaruhi penentuan titik mana yang di depan kamera dan mana yang di belakang. Sehingga, jika kita berharap untuk melindungi informasi ini, maka kita memungkinkan perkalian dua kolom terakhir M dengan konstanta positif saja. Kita dapat merangkum inti bagian ini sebagai berikut:

Preposisi 2.1. Pemetaan linear pushbroom dapat dikodekan dalam matriks M 3 x 4, yang menentukan pemetaan (u, wv, w)T = M(x, y, z, 1)T, dimana (x, y, z)T merupakan koordinat titik bumi 3D dan (u, v) adalah koordinat citra 2D yang berhubungan. Titik (x, y, z)T berada di depan kamera dan secara potensial terlihat jika dan hanya jika w > 0. Matriks M didefinisikan dengan kondisi ini hingga perkalian dua baris terakhir dengan konstanta skalar positif k.

3. Penentuan Matriks Kamera

Pada bagian ini akan ditunjukkan bagaimana matriks kamera linear pushbroom dapat dikomputasikan dengan memberikan satu set ground control point. Metodenya merupakan adaptasi dari metode Direct Linear Transformation (DLT) ([7]) yang digunakan untuk kamera pinhole. Secara khusus, menyatakan dengan tiga baris matriks M m1

T, m2T dan m3

T dan ground control point x = (x, y, z, 1)T, persamaan (7) dapat ditulis dalam bentuk tiga persamaan

Faktor yang tidak diketahui w dapat dieliminasi menjadi dua persamaan

Dengan menganggap koordinat bumi (x,y,z) dan koordinat citra (u,v) diketahui, persamaan (9) merupakan satu set persamaan linier pada masukan (entry) matriks M yang tidak diketahui. Dengan memberikan ground control point yang sesuai, kita dapat mencari solusi untuk baris pertama M.

Satu penyelesaian untuk baris pertama M tidak bergantung pada dua baris terakhir. Secara khusus, perlu diperhatikan bahwa entri pada baris m1

T hanya bergantung pada koordinat u dari ground control point. Dengan memberikan empat ground control point kita memperoleh satu set persamaan homogen pada entri m1

T, dari salah satu yang dapat mengatasi baris pertama M. Dengan lebih dari 4 titik, solusi least-square dikomputasikan.

Sama halnya dengan baris pertama, baris kedua dan baris ketiga M bergantung hanya pada koordinat v dari matriks. Dengan memberikan tujuh ground control point kita memperoleh satu set persamaan homogen dalam entri m2

T dan m3T. Persamaan – persamaan ini dapat diselesaikan untuk mencari baris

kedua dan ketiga M. Ketika lebih dari satu solusi least-square ditemukan maka lebih dari tujuh match diberikan. Solusi set persamaan non-homogen merupakan vektor tunggal yang berhubungan dengan nilai least singular dari matriks persamaan ([8]).

Dua baris terakhir M ditentukan dengan metode ini hanya sampai pada konstanta faktor yang tidak diketahui. Untuk menentukan matriks M yang secara benar menentukan titik mana yang di depan kamera, sesuai dengan Preposisi 2.1 kita bisa melakukan seperti berikut. Satu ground control point xi

dipilih dan hasil (ui, wivi, wi)T = Mxi dikomputasikan. Jika wi < 0, maka dua baris terakhir M dikalikan dengan -1. Dengan cara ini, kita memperoleh matriks yang memenuhi Preposisi 2.1. Jika data benar,

maka seluruh titik seharusnya berada di depan kamera, sehingga prosedur ini tidak bergantung pada titik xi mana yang dipilih.

Pemetaan Garis dibawah M. Untuk melihat sifat non-linier fungsi pemetaan dilakukan dengan M, yang merupakan instruksi untuk melihat bagaimana garis dalam ruang dipetakan pada bidang citra oleh M. Linear pushbroom mentransformasikan titik x ke u dan v sesuai dengan (9). Pembatasan x agar berada pada garis dalam 3-D diberikan oleh Vp + tVa, dimana Vp merupakan titik di atas garis, dan Va merupakan vektor sepanjang garis, citra dari garis ini di bawah M dinyatakan dengan

Eliminasi t dari persamaan ini, kita mendapatkan persamaan bentuk αu + βv + γuv + δ = 0, yang merupakan persamaan hiperbola pada bidang citra.

4. Pengambilan Parameter

Seperti yang telah dinyatakan, dua baris terakhir matriks M mungkin dikalikan dengan konstanta tanpa mempengaruhi hubungan antara koordinat titik bumi (x,y,z) dan koordinat citra (u,v) yang dinyatakan dengan persamaan (7). Hal ini berarti bahwa matriks M 3x4 hanya mengandung 11 derajat kebebasan. Sebaliknya, dapat diverifikasi bahwa formasi citra linear pushbroom juga dijabarkan dengan 11 parameter, yaitu posisi (3) dan arah (3) kamera pada waktu t=0, kecepatan kamera (3) dan panjang fokus serta v-offset (2). Berikutnya akan ditunjukkan bagaimana parameter linear pushbroom dapat dihitung dengan matriks M yang diberikan. Hal ini dilakukan untuk mencari faktorisasi M dari semua yang diberikan pada persamaan (7). Masalah yang berhubungan dengan kamera pinhole telah diatasi oleh Ganapthy([9]) dan Strat ([10]), tetapi lebih mudah dilakukan dengan aturan yang sama yang digunakan di bawah, variasi pada metode faktorisasi QR standar ([11]);

Tujuan penentuan parameter kamera individual, yang lebih dari hanya sekedar menggunakan matriks proyeksi M, adalah untuk mendapatkan pengetahuan (knowledge) mengenai parameter kamera yang mempengaruhi kalibrasi kamera. Misalnya, panjang fokus dan offset titik utama kamera dapat diketahui dengan cukup presisi dari spesifikasi manufacturing. Pada metode DLT untuk penentuan matriks kamera M, seperti dijelaskan pada bagian 3 bahwa tidak ada cara untuk menggabungkan informasi ini ke proses kalibrasi. Akan tetapi, satu cara dalam metode ini dapat dilakukan, yaitu memperoleh solusi awal untuk matriks kamera M, mengekstraksi parameter dari matriks dengan cara seperti yang dijelaskan pada bagian ini, menetapkan parameter yang diketahui menjadi nilai yang diketahui, dan yang terakhir melakukan penyesuaian parameter iterative pada algoritma untuk mendapatkan perkiraan pemetaan kamera yang lebih pasti. Program pemodelan kamera kita, Carmen ([12]), menggunakan pendekatan ini, memungkinkan berbagai parameter untuk ditetapkan secara absolute, atau dengan deviasi standar khusus. Parameterisasi kamera dengan cara yang berbeda memungkinkan untuk tipe knowledge pengaturan kamera yang berbeda.

Untuk menentukan parameter kamera, pertama-tama kita menentukan posisi kamera pada waktu t = 0, terhadap yang berikutnya dianggap sebagai posisi awal kamera. Dari perkalian hasil persamaan (7), dapat terlihat bahwa M merupakan bentuk (K │-KT) untuk matriks K non-singular 3 x 3. Dengan demikian, T mudah diatasi dengan menyelesaikan persamaan linier K T = -m4 dimana m4 merupakan kolom terakhir matriks M, dan K merupakan blok 3 x 3 sebelah kiri.

Selanjutnya, kita mempertimbangkan matriks K. Sesuai dengan persamaan (7), dan mengingat bahwa dua baris bawah matriks K mungkin dikalikan dengan faktor konstanta positif k, matriks K dalam bentuk

dimana R adalah matriks rotasi. Kita diberi K, dan diharapkan untuk mengkomputasi L. Untuk mencari faktorisasi ini, kita mengalikan K yang di sebelah kanan dengan urutan matriks rotasi yang diberikan untuk menguranginya ke bentuk yang diambil oleh L pada persamaan (12). Matriks rotasi yang diberikan merupakan matriks dalam bentuk

dimana c = cos(θ) dan s = sin (θ) untuk beberapa sudut θ yang dipilih untuk mengeliminasi beberapa elemen matriks kamera. Pada kasus sekarang, rotasi yang diperlukan akan berhasil dengan rotasi Rz, Ry

dan Rx dengan sudut yang dipilih untuk mengeliminasi entri K (1,2), (1,3) dan (3,2). Contohnya, rotasi pertama yaitu Rz dimana cos(θz) = k11/(k2

11 + k212)1/2 dan sin(θz) = k12/(k2

11 + k212)1/2. Sudut rotasi selanjutnya

dipilih dengan cara yang sama, kita memperoleh faktorisasi K sebagai hasil K = LR dimana R adalah matriks rotasi dan L merupakan matriks yang mempunyai nilai nol pada posisi yang diperlukan. Faktorisasi ini sama dengan faktorisasi QR dari matriks ([11]).

Pada titik ini, kita dapatkan bahwa salah satu atau kedua entri L22 dan L33 negatif. Hal ini akan menjadi kontradiktif dengan persyaratan kita bahwa L33 = k > 0, atau secara geometrik memaksakan persyaratan bahwa panjang fokus L22/L33 = f > 0. Kita bisa mengkoreksi hal ini sebagaimana berikut. Jika L33 > 0, maka kita dapat melakukan rotasi selanjutnya Ry melalui sudut π di sekitar sumbu y. Rotasi semacam itu mempunyai matriks rotasi diagonal (13) yang sama dengan diag(-1,1,-1). Sebagai tambahan, jika L22 < 0, maka kita bisa melakukan rotasi berikutnya Rz melalui sudut π di sekitar sumbu y. Rotasi ini mempunyai matriks diag(-1,-1,1). Sehingga matriks diperoleh, didefinisikan dengan kondisi K = LR dengan L22 dan L33

positif ditentukan secara khusus.

Sekarang, dengan menyamakan L dengan matriks sebelah kiri pada persamaan (12), terlihat bahwa parameter f, pv, Vx, Vy dan Vz dapat dengan mudah dibaca dari matriks L. Secara khusus, kita bisa langsung membaca nilai k = L33. Selanjutnya dua baris terakhir dari L dikalikan dengan faktor k-1 sehingga L33 = 1. Maka

Secara ringkas

Preposisi 4.2. 11 parameter kamera linear pushbroom ditentukan secara unik dan dapat dikomputasikan dari matriks kamera 3 x 4 yang didefinisikan dengan persyaratan Preposisi 2.1.

Perlu dicatat bahwa tanpa informasi mengenai bagian depan dan belakang kamera, parameter tidak dapat ditentukan secara khusus. Spesifikasi bagian depan kamera memungkinkan kita untuk menentukan matriks kamera hingga perkalian dua baris terkahir dengan faktor konstanta positif. Tanpa spesifikasi ini, matriks kamera hanya diketahui hingga faktor konstanta, positif atau negative. Dalam kasus ini, penerapan rotasi Rx(π) dengan matriks diag(1,-1,-1) akan mengubah pola dua kolom terakhir L, termasuk nilai L33 = k. Kemudian, dengan mengikuti prosedur di atas untuk penentuan parameter akan membawa ke nilai Vy dan Vz dengan pola berlawanan. Perlu diingat bahwa rotasi ini melalui π di sekitar sumbu x sesuai dengan pembalikan (flipping) kamera ke bawah dengan rotasi di sekitar sumbu yang tegak lurus terhadap instantaneous bidang view (view plane).

5. Penentuan Model Kamera Relatif

Masalah dalam menentukan penempatan kamera relatif dari dua kamera atau lebih dan penentuan konsekuen kamera pinhole telah dipertimbangkan secara luas. Yang lebih relevan pada paper baru adalah kegiatan Longuet-Higgins ([2]) yang mendefinisikan matriks esensial F. Jika {(ui, ui’)} adalah satu set match point dalam stereo pair, F didefinisikan dengan hubungan ui’T Fui = 0 untuk seluruh i. Seperti terlihat pada [3], (r, s, t)T = Fui adalah persamaan garis epipolar yang berhubungan dengan ui, pada citra kedua. (Garis (r, s, t)T pada koordinat homogen yang sesuai dengan persamaan garis ru + sv + t = 0, dalam ruang-citra) F dapat ditentukan dari delapan titik korespondensi atau lebih antara dua citra dengan tehnik linier.

Tehnik non-linier lain untuk menentukan F, lebih stabil pada kehadiran noise, telah dipublikasikan pada ([13, 14, 15, 16]). Tehnik itu sangat berhubungan sehingga disebut “kamera terkalibrasi”, untuk yang parameter internalnya dikatahui. Paper yang berhubungan dengan penentuan matriks fundamental untuk kamera tak terkalibrasi adalah [17, 18]. Adapun penentuan titik koordinat bumi melihat dari dua kamera pinhole, telah ditunjukkan pada ([5, 4]) bahwa untuk kamera tak terkalibrasi, posisi titik bumi ditentukan hingga transformasi proyektif tak diketahui oleh citranya dalam dua view terpisah.

Hasil yang sama untuk kamera linear pushbroom akan ditunjukkan di sini. Pada Bagian 5.1, matriks fundamental LP untuk kamera linear pushbroom, yang sama dengan matriks fundamental untuk kamera pinhole diperkenalkan. Geometri epipolar kamera linear pushbroom didiskusikan pada Bagian 5.2. Pada Bagian 5.3, kita membuktikan bahwa matriks fundamental LP yang mengkodekan (encode) arah relatif dua kamera linear pushbroom, menentukan titik 3-D pada ruang obyek hingga transformasi affine dari ruang. Sehingga pengetahuan arah relatif dalam kasus linear pushbroom lebih membatasi daripada untuk kamera perspektif; pada kasus berikutnya ambiguitas merupakan transformasi proyektif ruang. Bagian 5.4 dan 5.5 disediakan untuk diskusi mengenai critical set dan komputasi F dari satu set matched point.

5.1. Definisi Matriks Fundamental LP

Anggap sebuah titik x = (x,y,z)T dalam ruang seperti terlihat dengan dua kamera linear pushbroom dengan matriks kamera M dan M’. Anggap citra dua titik u = (u, v)T dan u’ = (u’, v’)T. Hal ini memberikan sepasang persamaan

Pasangan persamaan ini dapat dituliskan dalam bentuk berbeda sebagai

Matriks 6 x 6 dalam persamaan (15) akan dinyatakan sebagai A (M,M’). Anggap sebagai satu set persamaan linier dalam variabel x, y, z, w dan w’ dan konstanta 1, ini adalah satu set dari enam persamaan homogen dalam enam parameter yang tidak diketahui (anggap 1 yang akan diketahui). Jika sistem ini untuk mempunyai solusi, maka det A (M, M’) = 0. Kondisi ini menyebabkan kenaikan pada persamaan kubik p(u,v,u’,v’) = 0 dimana koefisien p ditentukan oleh entri dari M dan M’. Polinomial p disebut polinomial fundamental yang sesuai dengan dua kamera. Karena bentuk khusus dari persmaan (15), tidak ada istilah dalam u2, u’2, v2 atau v’2 pada polynomial. Konsekuensinya, terdapat matriks F 4 x 4 seperti p(u,v,u’,v’) = 0 dapat dituliskan:

Matriks F disebut matriks fundamental LP yang sesuai dengan pasangan kamera linear pushbroom {M, M’}. Matriks F merupakan cara termudah untuk menampilkan koefisien polinomial fundamental. Karena entri F bergantung hanya pada dua matriks kamera, M dan M’, persamaan (16) harus dipenuhi dengan pasangan dari titik citra yang sesuai (u,v) dan (u’,v’). Metode pembuktian dasar yang sama seperti yang digunakan di atas dapat digunakan untuk membuktikan eksistensi matriks fundamental untuk kamera pinhole ([19]).

Terlihat bahwa jika M ataupun M’ diganti dengan matriks ekuivalen dengan mengalikan dua baris terakhir dengan konstanta c, maka efeknya adalah mengalikan det A(M,M’), dan demikian juga polinomial fundamental p dan matriks F dengan konstanta yang sama c (bukan c2 seperti yang tampak pada pandangan pertama). Konsekuensinya, dua polinomial fundamental atau matriks yang berbeda dengan faktor konstanta bukan-nol akan dianggap ekuivalen. Sehingga, tidak seperti matriks kamera M dan M’, matriks fundamental F LP adalah obyek homogeny, didefinisikan hanya hingga skala bukan-nol.

Pendekatan lebih dalam matriks A(M,M’) pada persamaan (15) memperlihatkan bahwa p = det A(M,M’) mengandung yang tidak dalam istilah uu’, uvu’, uu’v’ atau uvu’v’. Dengan kata lain, bagian kiri atas submatriks F 2 x 2 adalah nol. Hal ini secara formal dinyatakan di bawah.

Teorema 5.3. Anggap ui = (ui, vi, 1)T dan ui’ = (ui’, vi’, 1) adalah koordinat citra 3-D titik-titik pi (i = 1, …,n) di bawah dua kamera linear pushbroom. Untuk semua i, terdapat matriks F = (fij), seperti

Karena F hanya didefinisikan hingga faktor konstanta, maka F mengandung tidak lebih dari 11 derajat kebebasan. Satu set yang terdiri dari 11 atau lebih korespondensi citra-ke-citra matriks F dapat

ditentukan dengan solusi satu set persamaan linier yang sama dengan kamera pinhole.

5.2. Geometri Epipolar

Salah satu perbedaan yang menarik antara kamera linear pushbroom dan kamera perspektif adalah geometri epipolar. Pertama-tama, tidak ada epipole dalam sifat/pengaturan kamera perspektif, karena dua kamera pushbroom bergerak saling memperhatikan satu sama lain. Dan tidak benar bahwa garis epipolar merupakan garis lurus.

Anggap pasangan matched point (u, v)T dan (u’, v’)T pada dua citra. Sesuai dengan persamaan (16) titik-titik ini memenuhi (u’, u’v’, v’, 1)T F(u, uv, v, 1) = 0. Sekarang, penetapan (u, v)T dan pemberian informasi untuk locus seluruh kemungkinan matched point (u’, v’)T, dan penulisan (α, β, γ, δ)T = F(u, uv, v, 1)T, kita lihat bahwa αu’ + βu’v’ + γv’ + δ = 0. Ini adalah persamaan hiperbola – epipolar loci berupa hiperbola untuk kamera linear pushbroom. F dapat digunakan dalam komputasi match point untuk melakukan batasan epipolar.

Epipolar locus sebuah titik adalah proyeksi pada citra garis lurus kedua yang mengalir dari pusat proyeksi instantaneous kamera pertama. Kurva epipolar hiperbolik diharapkan, seperti yang telah dibuktikan, di bawah garis model linear pushbroom dalam ruang dipetakan ke hiperbola pada bidang citra. Hanya satu dari dua cabang hiperbola akan tampak pada citra. Cabang yang lain akan berada di belakang kamera.

Matriks fundamental LP mengandung seluruh informasi mengenai parameter kamera relatif untuk kamera linear pushbroom yang belum terkalibrasi (uncalibrated) sepenuhnya (yaitum kamera yang mengenai segala sesuatunya belum diketahui) yang dapat diturunkan dari satu set match point. Pada bagian selanjutnya, kita mempertimbangkan informasi yang dapat diekstraksi dari F.

5.3. Ekstraksi Kamera Relatif dari Q

Longuet-Higgins ([2]) menunjukkan bahwa untuk kamera terkalibrasi, posisi relatif dan arah dua kamera dapat disimpulkan dari matriks fundamental. Hasil ini diperluas untuk kamera yang belum terkalibrasi dalam [4, 5] dimana diperlihatkan bahwa jika M1 dan M1’ merupakan pasangan (pair) kamera yang sesuai dengan matriks fundamental F dan jika M2 dan M2’ merupakan pasangan lain yang sesuai dengan matriks fundamental yang sama, maka terdapat matriks H 4 x 4 sedemikian rupa sehingga M1 = M2H dan M1’ = M2’H. Hasil ini akan ditunjukkan untuk mencapai kamera linear pushbroom dengan batasan bahwa H harus merupakan matriks yang merepresentasikan transformasi affine, yaitu baris terakhir dari H adalah (0,0,0,1).

Pertama-tama, akan ditunjukkan bahwa M dan M’ dapat dikalikan dengan matriks transformasi affine yang beruba-ubah (arbitrer) tanpa mengubah matriks fundamental LP. Anggap H sebagai matriks transformasi affine 4 x 4 dan Ĥ sebagai matriks 6 x 6

dimana I adalah matriks identitas 2 x 2. Jika A adalah matriks di dalam persamaan (15), maka dapat diverifikasi dengan sedikit usaha sehingga A(M, M’)Ĥ = A(MH, M’H), dimana asumsi baris terakhir H berupa (0,0,0,1) diperlukan. Dengan demikian, det A(MH, M’H) = det A(M, M’) det H dan sehingga

polinomial fundamental yang sesuai dengan pasangan {M, M’} dan {MH, MH’} berbeda dengan faktor konstanta dan juga ekuivalen.

Hasil yang sama dapat dibuktikan dengan cara yang lebih intuitif sebagai berikut. Matriks fundamental LP hanya bergantung pada koordinat citra dari matched point. Dengan demikian, investigasi mengenai transformasi mana yang dapat dilakukan di kamera dan titik spasial 3D tanpa mengubah koordinat citra. Kita dapat mengobservasi bahwa jika M digantikan dengan MH-1 dan tiap titik xi diganti dengan Hxi, maka (ui, wivi, wi)T = Mxi = (MH-1)(Hxi). Sehingga, koordinat citra, dan begitu juga matriks fundamental tidak berubah dengan transformasi affine titik 3D ini. Argumen yang sama digunakan pada kasus kamera pinhole, tetapi dalam kasus tersebut, H dapat berupa transformasi proyektif apapun, dan sehingga rekonstruksi dimungkinkan hanya hingga transformasi proyektif. Dapat dipelajari kenapa hal ini tidak memungkinkan pada kasus kamera linear pushbroom baru-baru ini.

Untuk transformasi proyektif yang tidak berubah (arbitrer), H, kita lihat bahwa Hxi = H(xi, yi, zi, 1)T = (xi’, yi’, zi’, ti’)T, dimana ti’ umumnya tidak sama dengan satu. Akan tetapi, dalam Preposisi 2.1 mendefinisikan pemetaan kamera LP, titik 3D harus ditulis dalam bentuk (x, y, z, 1)T dengan koordinat terakhir satuan. Untuk mendapatkan ini, kita bagi dengan t’, yang menyebabkan (MH-1)(xi’/ti’, yi’/ti’, zi’/ti’, 1)T = (ui/ti’, wivi/ti, wi/ti)T. Vektor terakhir ini merepresentasikan titik citra 2D (ui’/ti’, vi)T yang tidak sama dengan titik original (ui, vi)T. Sehingga, usulan transformasi proyektif tidak menjaga titik citra tetap. Sebaliknya, jika H adalah transformasi affine, maka baris terakhir H adalah (0, 0, 0, 1), dapat dilihat bahwa H(xi, yi, zi, 1)T = (xi’, yi’, zi’, 1)T. Dengan demikian, koordinat terakhir selalu 1, dan masalah tidak terjadi.Hasil ini menyarankan bahwa dua matriks kamera harus ditentukan hingga transformasi affine dari matriks fundamental LP. Sekarang akan diperlihatkan bahwa hal ini memang benar, dan prosedur konstruktif akan diberikan untuk mengkomputasikannya. Baru saja didemonstrasikan bahwa matriks kamera dan titik 3D bisa dikalikan dengan matriks affine H 4 x 4 yang tidak berubah (arbitrary) dan inversnya tanpa mempengaruhi matriks fundamental LP, atau titik citra 2D. Sehingga, kita bisa memilih untuk mengatur matriks M’ ke bentuk sederhana khusus (I │0) dimana I adalah matriks identitas. Bahkan, bisa dianggap M’ = (R│t). kita bisa mentransformasikan M’ menjadi (I │0) dengan menempatkan

perkalian keduanya M dan M’ dengan matriks affine . Akan terlihat bahwa dengan asumsi bahwa M’ = (I │0), matriks M yang lain ditentukan secara khusus dengan matriks fundamental LP.

Dengan asumsi bahwa M’ = (I|0), F dapat dikomputasikan secara eksplisit dalam hal entri M. Dengan menggunakan Mathematica ([20]) atau secara manual dapat dihitung bahwa

Dengan entri fij pada F yang diberikan, pertanyaannya adalah apakah mungkin memperoleh nilai entri mij. Hal ini meliputi solusi satu set yang terdiri dari 12 persamaan dalam 12 nilai mij yang belum diketahui (unknowni). Empat entri m22, m23, m32 dan m33 dapat diperoleh dengan cepat dari blok kiri bawah F. Secara khusus,

Perolehan sisa entri lebih membutuhkan triks khusus tetapi mungkin berhasil seperti berikut ini. Empat entri bukan-nol pada dua baris pertama dapat dituliskan ulang dalam bentuk berikut (menggunakan persamaan (19) untuk subtitusi m22, m23, m32 dan m33).

Dengan cara yang sama, blok sebelah kanan bawah 2x2 memberi satu set persamaan

Sepintas dapat dilihat bahwa jika kita mempunyai solusi mij, maka solusi baru bisa diperoleh dengan mengalikan m12 dan m13 dengan konstanta c bukan-nol dan membagi m21, m31, m24 dan m34 dengan konstanta c yang sama. Dengan kata lain, jika m13 = 0 tidak terpenuhi, yang dapat dengan mudah dicek, maka dapat diasumsikan m13 = 1. Dari asumsi solusi persamaan (20) dan (21) dapat disimpullkan bahwa matriks 4 x 4 dalam persamaan (20) dan (21), keduanya harus mempunyai determin nol. Dengan m13 =1, masing-masing dari persamaan (20) dan (21) memberikan persamaan kuadratik dalam m12. Untuk solusi menghadirkan matriks sought M, kedua kuadratik ini harus mempunyai akar yang umum (common root). Kondisi ini merupakan kondisi yang diperlukan untuk matriks agar menjadi matriks fundamental LP. Penyusunan kembali matriks selintas (slightly), menulis λ ataupun m12 dan menyatakan eksistensi akar umum dalam hubungannya dengan resultan menyebabkan statemen berikut.

Teorema 5.4. Jika matriks 4 x 4 matriks F = (fij) adalah matriks fundamental LP, maka

1. f11 = f12 = f21 = f22 = 0

2. resultan polinomial

dan

menghilang (vanish).

3. Diskriminan polinomial (22) dan (23) keduanya bukan-negatif.

Jika dua kuadratik mempunyai akar umum, maka akar umum ini akan menjadi nilai m12. Persamaan linier (20) kemudian dapat diselesaikan untuk m11, m21 dan m31. Sama juga, persamaan (21) dapat diselesaikan untuk m14, m24 dan m34. Jika f31f42 – f41f32 tidak hilang, tiga kolom pertama matriks (20) dan (21) tidak akan bergantung secara linier dan solusi untuk mij akan diperoleh dan nilainya unik.

Untuk merekapitulasi, jika m12 adalah akar umum dari dua polinomial kuadratik (22) dan (23), m13 dipilih agar sama dengan 1, dan f31f42 – f41f32 ≠ 0 maka matriks M = (mij) dapat ditentukan secara khusus dengan solusi satu set persamaan linier. Relaxing kondisi m13 = 1, menghasilkan solusi bentuk

Namun, pada perkalian dengan diagonal matriks affine diag(1, 1/c, 1/c, 1), semua matriks tersebut ekuivalen. Lebih lanjut, matriks M’ = (I|0) dipetakan pada matriks ekuivalen dengan perkalian diag(1, 1/c, 1/c, 1). Hal ini menunjukkan bahwa jika m12 ditentukan, pasangan matriks {M, M’} dapat dihitung secara khusus hingga ekuivalensi affine.

Yang terakhir, kita anggap kemungkinan persamaan (22) dan (23) mempunyai dua akar umum. Hal ini hanya bisa terjadi jika koefisien F memenuhi identitas terbatas tertentu yang dapat dideduksi dari persamaan (22) dan (23). Ini membuat kita menyatakan

Teorema 5.5. Matriks F 4 x 4 memenuhi kondisi Preposisi 5.4, pasangan matriks kamera {M,M’} yang sesuai dengan Fditentukan secara khusus hingga ekuivalensi affine, jika F tidak berada pada critical set dimensional yang paling rendah.

Algoritma lengkap untuk komputasi matriks kamera (hingga transformasi affine) dari matriks fundamental LP diringkas sebagai berikut.

1. Atur M’ = (I│0).

2. Atur m22 = f31, m23 = f41, m32 = -f32, m33 = -f42.

3. Atur m13 = 1 dan atur λ = m12 untuk menjadi akar umum determinan (22) dan (23).

4. Selesaikan persamaan (20) dan (21) untuk mencari sisa entri M.

5.4. Lebih Dalam Mengenai Critical Set

Investigasi lengkap mengenai critical set bukanlah menjadi tujuan di sini. Seperti yang telah dinyatakan sebelumnya, kondisi dimana ada dua akar umum pada persamaan (22) dan (23) menyebabkan dua solusi yang berbeda untuk M dapat dideduksi dari bentuk (22) dan (23). Investigasi ini akan menghasilkan kondisi dalam hal entri F. Pencerahan lebih lanjut akan menjadi kondisi dalam hal entri matriks M untuk solusi yang ambigu. Hal ini akan diinvestigasi selanjutnya.

Akan ada solusi ambigu pada masalah estimasi matriks M jika polinomial (22) dan (23) mempunyai dua akar umum. Anggap bahwa matriks F merupakan bentuk yang diberikan pada persamaan (18). Kemudian kita dapat hitung dua polinomial kuadratik dari (22) dan (23). Hasilnya (dihitung dengan menggunakan Mathematica) adalah

Seperti yang diharapkan, p1(λ) dan p2(λ) mempunyai akar umum λ = m12/m13. Akar kedua p1 dan p2 sama jika dan hanya jika dua polinomial linier (m22m31 – m21m32 – λ(m23m31 – m21m33)) dan (m22m34 – m24m32 – λ(m23m34 – m24m33)) mempunyai akar yang sama. Hal ini berlaku jika dan hanya jika

Karena bagian kanan persamaan ini merupakan produk dari dua faktor, ada dua kondisi terpisah dimana solusi ambigu ada. Kondisi pertama (m21m34 – m24m31) = 0 berhubungan secara geometrik dengan situasi dimana lintasan dua kamera bertemu di space. Hal ini dapat terlihat sebagai berikut. Titik x = (x, y, z)T

berada pada lintasan pusat proyeksi kamera dengan matriks M jika dan hanya jika M (x, y, z, 1)T = (u, 0, 0)T, untuk kondisi ini koordinat v dari citra belum didefinisikan. Khususnya, titik yang berada pada lintasan kamera M’ dengan matriks (I│0) adalah dari bentuk (x,0,0)T. Titik semacam itu juga akan ada pada lintasan kamera dengan natriks M jika dan hanya jika xm21 + m24 =xm31 +m34 = 0 untuk beberapa x; yaitu, yang jika dan hanya jika m21m34 – m24m31 = 0.

Kita mungkin melakukan verifikasi dalam kasus ini, bahkan ada dua solusi yang berbeda. Kondisi geometriknya bahwa dua lintasan tersebut bertemu. Untuk menyederhanakan, kita anggap bahwa dua lintasan bertemu pada titik origin sistem koordinat pada waktu t = 0. Dalam kasus ini, bisa diasumsikan bahwa dua matriks kamera yaitu (I│0) dan M = (K│0). Anggap k*ij = det ij, dimana ij merupakan matriks yang diperoleh dari K dengan mengeliminasi baris ke-i dan kolom ke-j. Selanjutnya, anggap entri K adalah kij. Definisikan matriks K2 dengan ekspresi

Kemudian dapat diverifikasi (misalnya menggunakan Mathematica) bahwa pasangan (I│0), (K2│0) mempunyai matriks fundamental LP yang sama, yang didefinisikan oleh persamaan (18) sebagai pasangan (I│0), (K│0).

Dapat ditunjukkan bahwa kondisi kedua yang berhubungan secara geometrik terhadap lintasan kamera M yang paralel terhadap bidang view (view plane) kamera M’. Namun, bukti terhadap ini diabaikan, karena faktanya, kondisi ini tidak mengakibatkan ke solusi kedua. Kondisi m22m33 - m23m32 = 0 adalah sama (lihat (18)) dengan kondisi q31q42 – q41q32 = 0. Terlihat bahwa dalam kasus ini, matriks pada persamaan (20) dan (21) mempunyai pangkat 3, tetapi ruang-null-nya (null-spaces) adalah dalam bentuk (a, b, c, 0). Dengan demikian, set persamaan yang berhubungan tidak menerima solusi dengan entri akhir sama dengan 1, seperti yang diperlukan.

5.5. Komputasi Matriks Fundamental LP

Matriks F dapat dikomputasikan dari korespondensi citra hampir sama dengan cara Longuet-Higgins dalam mengkomputasi matriks fundamental perspektif ([2]). Dengan memberikan 11 atau lebih korespondensi titik-ke-titik antara pasangan citra linear pushbroom, persamaan (16) dapat digunakan untuk menyelesaikan 12 entri bukan-nol dari F, hingga perkalian dengan skala yang belum diketahui.

Penting sekali dalam implementasi algoritma linier ini, bahwa data korespondensi citra dinormalisasi dengan cara yang sama seperti yang dijelaskan pada (18). Sayangnya, dengan adanya noise, solusi yang diperoleh dengan cara ini untuk F tidak akan memenuhi kondisi kedua (5.4) secara pasti. Konsekuensinya, ketika menyelesaikan matriks M, akan ditemukan bahwa dua polinomial (22) dan (23) tidak mempunyai akar umum. Berbagai strategi memungkinkan pada tahapan ini.

Salah satu strategi adalah sebagai berikut. Anggap tiap dua akar m12 dari (22) dan dengan tiap nilai semacam itu m12 diproses sebagai berikut: Subtitusikan tiap m12 dalam gilirannya ke dalam persamaan (21). Dengan memberikan satu set dari empat persamaan dalam tiga bentuk yang belum diketahui; selesaikan persamaan (21) untuk mencari solusi least-square untuk m14, m24 dan m34. Yang terakhir terima akar dari (22) yang menghasilkan solusi least-square terbaik. Kita dapat melakukan ini dengan round lain sama halnya memulai dengan mempertimbangkan akar (23) dan menerima empat solusi terbaik yang ditemukan. Strategi berbeda adalah dengan memilih m12 menjadi angka yang terdekat untuk menjadi akar dari tiap persamaan (22) dan (23). Ini adalah algoritma yang telah kita implementasikan, dengan hasil yang bagus sampai sejauh ini.

Namun, untuk memperoleh hasil terbaik, mungkin diperlukan untuk menerapkan kondisi Proposisi 5.4 ke akun secara eksplisit dan mengkomputasikan matriks fundamental LP yang memenuhi kondisi ini dengan menggunakan asumsi eksplisit mengenai source error untuk merumuskan fungsi kosinus untuk diminimalkan. Ini telah ditunjukkan dan menjadi pendekatan terbaik untuk kamera perspektif ([21, 16]).

Pertanyaan stabilitas numerik penting dalam penerapan algoritma dengan menggunakan model linear pushbroom. Khususnya, mudah untuk mengatasi situasi dimana penentuan parameter model linear pushbroom dalam kondisi yang sangat buruk. Khususnya, jika satu set ground-control point berada pada bidang sangat mendekati planar, maka akan terlihat dengan mudah (sama seperti dengan kamera perspektif) bahwa penentuan parameter modelnya ambigu. Kita telah mengembangkan tehnik (tidak dijelaskan di sini) untuk menangani beberapa kasus ketidakstabilan, tetapi masih perlu perawatan. Algoritma yang dijelaskan di paper ini tidak dapat digunakan dalam kasus dimana set obyek berada pada sebuah bidang.

6. Rekonstruksi Scene

Jika dua matriks kamera telah ditentukan, posisi titik xi di ruang dapat ditentukan dengan penyelesaian persamaan (15). Hal ini akan menentukan posisi titik di ruang hingga transformasi affine ruang.

Dalam kasus dimana kedua titik sesuai (match) antara citra dan ground-control point tertentu, scene dapat direkonstruksi dengan menggunakan titik yang match (matched point) untuk menentukan scene hingga transformasi affine, dan kemudian menggunakan ground-control point untuk menentukan penempatan absolut scene. Jika ground-control point terlihat di kedua citra, maka mudah untuk mencari transformasi affine yang benar. Hal ini dilakukan dengan menentukan posisi ground-control point dalam rekonstruksi citra, dan kemudian menentukan transformasi affine 3-D yang akan menggunakan titik-titik ini pada lokasi ground-control absolut.

Jika ground-control point tersedia maka yang terlihat hanya pada satu citra saja, masih memungkinkan menggunakannya untuk menentukan lokasi absolut dari rekonstruksi set titik. Metode untuk melakukan ini dijelaskan pada [4] dan tidak akan diulangi di sini.

7. Hasil Eksperimen

Dua asumsi utama dibuat dalam penurunan model linear pushbroom (lihat bagian 2). Dalam konteks aplikasi penginderaan jauh, asumsi pertamanya adalah bahwa selama waktu akuisisi satu citra, variasi kecepatan satelit pada orbitnya dapat diabaikan. Dan lagi, gerak permukaan bumi dapat dimasukkan dalam gerak satelit, gerak gabungan keduanya kira-kira rectilinear. Asumsi kedua bahwa rotasi kerangka orbit lokal dan perubahan arah yang berhubungan dengan kerangka ini dapat diabaikan. Untuk sejauh mana asumsi-asumsi ini dibenarkan akan dieksplorasi di bagian ini dan beberapa eksperimen yang mengukur akurasi model linear pushbroom dijelaskan.

Pada eksperimen pertama, akurasi model linear pushbroom dibandingkan dengan full model kamera HRV SPOT. Model ini, yang dijelaskan secara detail di [22], memperhitungkan dinamika orbit (orbital dynamics), rotasi bumi, attitude drift yang terukur oleh sistem on-board, data ephemeris dan beberapa fenomena lainnya untuk membuat proses pencitraan seakurat mungkin. Model yang berbeda didiskusikan di [23].

Model linear pushbroom dibandingkan dengan full model pada pasangan citra sebenarnya (real image) dengan matched point yang dikomputasikan dengan menggunakan algoritma stereo matching. Pasangan stereo (stereo pair) citra SPOT wilayah Malibu, berpusat kira-kira pada 34 derajat 5 min utara, dan 118 derajat 32 min barat (citra dengan (J, K) = (541, 281) dan (541, 281) pada sistem referensi kisi (grid) SPOT [24]) digunakan. Kita memperkirakan model kamera untuk kedua citra ini dengan menggunakan satu set yang terdiri dari 25 ground control point, tampak pada kedua citra, dipilih bentuk peta USGS dan beberapa korespondensi citra-ke-citra yang dibuat secara otomatis dengan menggunakan STEREOSYS [25].

Tabel 1: Perbandingan ketiga model kamera.

Dua ukuran kinerja dikomputasi. Akurasi dengan model kamera mana yang memetakan ground point ke titik citra yang berhubungan sangat penting. Perbedaan RMS antara koordinat citra yang diketahui dan koordinat citra yang dikomputasi menggunakan model kamera turunan diukur. Ukuran spesifik-aplikasi, viz. Akurasi model elevasi lereng (terrain) yang dibuat dari stereo pair, juga diukur.

Sekali lagi, data dimodelkan dengan menggunakan model kamera perspektif, model linear pushbroom dan model full pushbroom.

Untuk membuat hasilnya dapat dibandingkan secara langsung, ground control point dan korespondensi citra-ke-citra yang sama digunakan untuk komputasi model kamera pada seluruh eksperimen ini. (Jumlah titik-titik yang digunakan untuk komputasi kamera perspektif merupakan perkecualian dimana

511 korespondensi citra-ke-citra, bukan 100, disediakan dalam usaha untuk menaikkan akurasi). Sebagai tambahan, model terrain juga dibuat dengan menggunakan set matched point yang sama.

Hasil ketiga eksperimen ini ditabulasikan pada Tabel 1. Baris pertama dan kedua daftar jumlah ground control point dan jumlah titik digunakan dalam komputasi model kamera. Baris ketiga menunjukkan jumlah matched point untuk titik mana pada terrain yang dibuat. Akurasi model kamera, yaitu, akurasi dengan ground point mana (x, y, z)T yang dipetakan pada titik citra yang berhubungan, didaftar pada baris keempat. Akhirnya, perbedaan RMS antara terrain buatan dan ground truth (data DMA DTED) diberikan pada baris kelima.

Usaha untuk memodelkan kamera HRV SPOT dengan kamera perspektif menghasilkan model kamera dengan kombinasi akurasi sekitar 11 piksel. Hal ini merupakan error yang besar karena untuk wahana (platform) yang tinggi seperti satelit, meskipun berupa error piksel tunggal, tetapi dapat menjadi perbedaan puluhan meter sepanjang dimensi horisontal dan vertikal (jumlah sebenarnya bergantung pada resolusi piksel dan sudut pandang). Hal ini direfleksikan dalam akurasi terrain buatan yang mana sebesar 380 m, rata-rata. Dengan demikian, seperti yang diharapkan, kamera pin-hole merupakan perkiraan yang jelek untuk kamera pushbroom. Linear pushbroom, sebaliknya, cukup kompetitif dengan model detail, baik dalam hal akurasi model kamera, dan juga akurasi terrain buatan.

Gambar 3: Rekonstruksi terrain dari model perspektif.

Entri terakhir pada baris kelima (akurasi 11,10 m untuk terrain yang dibuat dengan model kompleks) sedikit salah karena terrain buatan lebih akurat daripada akurasi yang diklaim pada ground-truth jika dibandingkan. Gambaran ini merupakan pernyataan mengenai akurasi ground-truth, bukan cara lain di sekitarnya.

Gambar 3 dan 4 menunjukkan terrain yang dibuat dengan model perspektif dan model full SPOT. Gambar 4 dapat dianggap sebagai ground-truth. Karena wilayah yang tercakup oleh stereo pair sedikit lebih besar (sekitar 60km x 60km), relief terrain ditunjukkan hanya untuk sub-citra 1024 x 1024 dan telah cukup dilebihkan dibandingkan dimensi horisontal. Kita tidak memasukkan terrain yang dibuat dengan model linear pushbroom karena secara visual tidak bisa dibedakan dengan terrain yang dibuat oleh full model (Gambar 4).

Gambar 3 mengilustrasikan distorsi yang diperkenalkan ketika proyeksi perspektif sebagian (partially) dimodelkan dengan kamera fully perspective. Untuk memahami distorsi ini dengan lebih baik, beberapa eksperimen dilakukan.

Dengan menggunakan parameterisasi model full pushbroom pada orbit sebenarnya dan data ephemeris, dan model artificial terrain, satu set ground pada korespondensi citra dikomputasi, satu ground-control point semacam itu dikomputasi setiap 120 piksel. Hal ini memberi satu kisi ground-control point 51 x 51 yang mencakup kira-kira 6000 x 6000 piksel. Selanjutnya, ground control point ini digunakan untuk memberi contoh model linear pushbroom dengan menggunakan algoritma bagian 3. Pada eksperimen ini, lokasi ground point ditetapkan untuk keduanya, baik full pushbroom maupun linear pushbroom. Perbedaan diukur antara titik citra yang berhubungan seperti yang dikomputasi dengan tiap model. Nilai error absolut bervariasi sepanjang citra ditunjukkan pada Gambar 5. Error maksimum kurang dari 0,4 piksel dengan RMS error 0,16 piksel. Seperti dapat dilihat, untuk citra SPOT lengkap, error yang disebabkan penggunaan model linear pushbroom kurang dari setengah piksel, dan lebih kecil lagi pada hampir seluruh citra.

Gambar 4: Rekonstruksi terrain dari model full pushbroom.

Gambar 5: Profil error untuk model linear pushbroom.

Gambar 6: Profil error untuk model perspektif.

Untuk menguji apakah model kamera perspektif dapat berlaku sama baiknya, satu set ground control point yang sama dimodelkan dengan menggunakan model kamera perspektif. Hasilnya adalah RMS error 16,8 piksel dengan error piksel maksimum pada 45 piksel. Gambar 6 menunjukkan distribusi error sepanjang citra.

8. Kesimpulan

Model linear pushbroom memeberikan aproksimasi yang bagus pada full model sensor pushbroom yang mengorbit, tetapi secara substansial kurang kompleks. Penyederhanaan model kamera linear pushbroom memungkinkan timbulnya banyak masalah fotogrametri standar, seperti kalibrasi kamera

dan deteksi pose, serta arah relatif yang harus diatasi dengan menggunakan algoritma non-iterative sederhana. Selain aplikasi pada sensor satelit yang mengorbit, dimana model linear pushbroom merepresentasikan aproksimasi pada model full orbiting, model LP mempunyai aplikasi pada penginderaan industrial. Model ini telah digunakan untuk pemeriksaan bagian turbine blade sinar-X. pada kasus ini, model linier sangat mendekati perkiraan geometri sebenarnya, dan sensor dapat secara akurat dikalibrasi dengan menggunakan algoritma linier yang dijelaskan di paper ini.

Referensi

[1] Alison Noble, Richard Hartley, Joseph Mundy, and James Farley, “X-ray metrology for quality assurance,” in Proc. IEEE Robotics and Automation Conference, 1994.

[2] H.C. Longuet-Higgins, “A computer algorithm for reconstructing a scene from two projections,” Nature, vol. 293, pp. 133–135, Sept 1981.

[3] R. I. Hartley, “Estimation of relative camera positions for uncalibrated cameras,” in Computer Vision - ECCV ’92,LN CS-Series Vol. 588, Springer-Verlag, 1992, pp. 579 – 587.

[4] R. Hartley, R. Gupta, and T. Chang, “Stereo from uncalibrated cameras,” in Proc. IEEE Conf. on Computer Vision and Pattern Recognition, 1992, pp. 761–764.

[5] O. D. Faugeras, “What can be seen in three dimensions with an uncalibrated stereo rig?,” in Computer Vision - ECCV ’92,LN CS-Series Vol. 588, Springer-Verlag, 1992, pp. 563 – 578.

[6] Richard Hartley and Rajiv Gupta, “Computing matched-epipolar projections,” in Proc. IEEE Conf. on Computer Vision and Pattern Recognition, 1993, pp. 549 – 555.

[7] I.E. Sutherland, “Three dimensional data input by tablet,” Proceedings of IEEE, vol. Vol. 62, No. 4, pp. 453–461, April 1974.

[8] O. Faugeras, Three Dimensional Computer Vision: A Geometric Viewpoint, The MIT Press, Cambridge, MA, 1993.

[9] S. Ganapathy, “Decomposition of transformation matrices for robot vision,” Pattern Recognition Letters, vol. 2, pp. 410–412, 1989.

[10] T.M. Strat, “Recovering the camera parameters from a transformation matrix,” in Readings in Computer Vision, M.A. Fischler and O. Firschein, Eds., pp. 93 – 100. Morgan Kaufmann Publishers, Inc., 1987, Also appeared in Proc. of DARPA Image Understanding Workshop, New Orleans, LA, pp. 264–271, 1984.

[11] Gene H. Golub and Charles F. Van Loan, Matrix Computations,Se cond edition, The Johns Hopkins University Press, Baltimore, London, 1989.

[12] Richard I. Hartley, “An object-oriented approach to scene reconstruction,” in Proc. IEEE International Conference on Systems Man and Cybernetics,Peking , October 1996, pp. 2475 – 2480.

[13] J. Weng, T. S. Huang, and N. Ahuja, “Motion and structure from two perspective views: Algorithms, error analysis and error estimation,” IEEE Trans. Patt. Anal. Machine Intell., vol. 11, no. 6, pp. 451–476, May 1989.

[14] R. Y. Tsai and T. S. Huang, “Uniqueness and estimation of three dimensional motion parameters of rigid objects with curved surfaces,” IEEE Trans. Patt. Anal. Machine Intell., vol. PAMI-6, pp. 13–27, 1984.

[15] B. K. P. Horn, “Relative orientation revisited,” Journal of the Optical Society of America,A , vol. Vol. 8, No. 10, pp. 1630 – 1638, 1991.

[16] M. E. Spetsakis and Y. Aloimonos, “Optimal visual motion estimation: A note,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. Vol. 14, No. 9, pp. 959 – 964, September 1992.

[17] O. D. Faugeras, Q.-T Luong, and S. J. Maybank, “Camera self-calibration: Theory and experiments,” in Computer Vision - ECCV ’92,LN CS-Series Vol. 588, Springer-Verlag, 1992, pp. 321 – 334.

[18] R. I. Hartley, “In defence of the 8-point algorithm,” in Proc. International Conference on Computer Vision, 1995, pp. 1064 – 1070.

[19] Olivier Faugeras and Bernard Mourrain, “On the geometry and algebra of the point and line correspondences between N images,” in Proc. International Conference on Computer Vision, 1995, pp. 951 – 956.

[20] S. Wolfram, Mathematica : A System for Doing Mathematics by Computer, Addison-Wesley, Redwood City, California, 1988.

[21] B. K. P. Horn, “Relative orientation,” International Journal of Computer Vision, vol. 4, pp. 59 – 78, 1990.

[22] Rajiv Gupta and Richard Hartley, “Camera estimation for orbiting pushbrooms,” in Proc. Second Asian Conference on Computer Vision, Singapore, Dec 1995.

[23] Ashley P. Tam, Terrain elevation extraction from digital SPOT satellite imagery, Ph.D. thesis, Masters Thesis, Dept. of Surveying Engineering, Calgary, Alberta, July 1990.

[24] SPOT Image Corporation, 1897, Preston White Dr., Reston, VA 22091-4368, SPOT User’s Handbook, 1990.

[25] M. J. Hannah, “Bootstrap stereo,” in Proc. Image Understanding Workshop,Col lege Park,MD , April 1980, pp. 210–208.