BAB II KAJIAN PUSTAKA 2.1 Citra Suatu citra didefinisikan sebagai fungsi kontinu dari intensitas cahaya dalam bidang 2 dimensi, dan dinyatakan dengan f(x,y), dimana nilai atau amplitudo dari f menyatakan intensitas cahaya dari citra pada koordinat (x,y). Dan karena cahaya adalah salah satu bentuk dari energi, maka nilai f(x,y) harus berada diantara nol sampai tak terhingga. Dengan persamaan 0 < f(x,y) < ∞
Gambar 2.1 Dimensi citra 2.1.1 Dijitalisasi Citra Supaya sebuah citra dapat diproses oleh komputer, maka perlu adanya dijitalisasi. Dijitalisasi adalah proses representasi citra dari fungsi kontinu menjadi nilai-nilai diskrit. Citra yang dihasilkan dari dijitalisasi disebut citra dijital (digital image). Umumnya citra dijital berbentuk empat persegi panjang 6
7 dan dimensi ukurannya dinyatakan dengan panjang x lebar. Citra dijital yang berukuran M (panjang) x N (lebar) biasanya dinyatakan dalam bentuk matriks yang berukuran M baris dan N kolom, sebagai berikut :
Setiap elemen pada citra dijital (elemen matriks) disebut image elemet, picture element, pixel atau pel. 2.1.2 Proses Dijitalisasi Citra Proses dijitalisasi citra melalui dua tahap, yaitu : 1. Dijitalisasi spasial (x,y), disebut image sampling 2. Dijitalisasi intensitas f(x,y), disebut gray-level quantization 2.1.2.1 Image Sampling Citra kontinu dibagi-bagi menjadi grid-grid berbentuk bujur sangkar dan pada setiap grid mengandung jumlah pixel tertentu.
8
Gambar 2.2 Image Sampling Dalam
implementasi
biasanya
jumlah
sampling
diasumsikan
perpangkatan dari dua, sehingga dapat dituliskan : N = 2n, dimana : N = jumlah sampling pada suatu baris / kolom n = bilangan bulat positif
Gambar 2.3 Perbedaan image sampling 2.1.2.2 Gray-level quantization Proses kuantisasi adalah membagi skala keabuan / gray scale (0,L) menjadi sejumlah level, dinotasikan dengan G dan nilainya berupa bilangan bulat (integer), G merupakan hasil perpangkatan dari dua : G = 2m, dimana : G = derajat keabuan / gray scale
9 m = bilangan bulat positif Tabel 2.1 Grayscale
Gambar 2.3 Perbedaan Gray-level quantization Jumlah bit yang dibutuhkan untuk menyimpan citra dijital yang disampling menjadi N x N pixels dan dikuantisasi menjadi G gray level adalah : b = N x N x m dalam satuan bit 2.1.3 Terminologi Citra Dijital Terminologi yang terdapat dalam citra dijital sebagai berikut : 1. Kecerahan (Brightness) Kecerahan adalah kata lain untuk intensitas cahaya. Kecerahan pada sebuah titik (pixel) di dalam citra bukanlah intensitas riil, tetapi sebenarnya adalah intensitas rata-rata dari suatu area yang melingkupinya.
10 2. Kontras (Contrast) Kontras menyatakan sebaran terang (lightness) dan gelap (darkness) di dalam sebuah citra. 3. Kontur (Contour) Kontur adalah keadaan yang ditimbulkan oleh perubahan intensitas pada pixel - pixel bertetangga. 4. Warna (Colour) Warna adalah persepsi yang dirasakan oleh sistem visual manusia terhadap panjang gelombang cahaya yang dipantulkan oleh objek. Setiap warna mempunyai panjang gelombang (λ) yang berbeda. - Merah : panjang gelombang paling tinggi - Ungu : panjang gelombang paling rendah 5. Bentuk (Shape) Shape adalah properti intrinsik dari objek tiga dimensi, dengan pengertian bahwa shape merupakan properti intrinsik utama sistem visual manusia. 6. Tekstur (Texture) Tekstur dicirikan sebagai distribusi spasial dari derajat keabuan di dalam sekumpulan pixel-pixel yang bertetangga. Jadi tekstur tidak dapat didefinisikan hanya untuk sebuah pixel.
11 2.2 Pengolahan Citra Pengolahan citra merupakan proses pengolahan dan analisis citra yang banyak melibatkan persepsi visual dan bertujuan untuk memperbaiki kualitas citra agar mudah diinterpretasi oleh manusia atau mesin (komputer). Jadi, masukannya adalah citra dan keluarannya adalah juga citra, namun citra keluaran mempunyai kualitas lebih baik daripada citra masukan. Pada umumnya, citra yang diolah adalah dalam bentuk dijital dan disebut sebagai pengolahan citra dijital. Median filtering termasuk salah satu langkah untuk meningkatkan kualitas citra, karena median filtering cocok digunakan untuk menghilangkan noise dari suatu citra. Median filtering bekerja dengan mengevaluasi tingkat brightness dari suatu pixel dan menentukan pixel mana yang tingkat brightness-nya adalah nilai median (nilai tengah) dari semua pixel. Nilai median ditentukan dari menempatkan brightness pixel pada urutan yang bertingkat dan memilih nilai tengah, sehingga angka yang didapat dari brightness pixel yang ada menjadi kurang dari dan lebih dari nilai tengah yang didapat. Median filtering merupakan salah satu jenis low-pass filter, dibandingkan dengan neighborhood averaging, filter ini lebih tidak sensitif terhadap perbedaan intensitas yang ekstrim. Median filtering menentukan median dari suatu kernel (misal 3x3), filtering dengan metode ini merupakan filter statistical order yang paling terkenal dikarenakan kinerja yang cukup memuaskan dalam mengatasi noise terutama noise salt dan pepper dan juga efek blurring yang terjadi jauh lebih kecil jika dibandingkan dengan aritmatik filter.
12
Gambar 2.4 Proses Median Filter Proses edge detection merupakan salah satu bagian dari proses segmentasi yang bertujuan untuk mengekstrak fitur objek yang diperlukan untuk keperluan analisa. Dasar untuk melakukan edge detection adalah mencari titik-titik pixel dalam citra yang memiliki perubahan luminasi yang besar, misalnya dari warna hitam menjadi putih, atau sebaliknya untuk citra yang berformat grayscale. Ada beberapa operator yang umumnya dapat digunakan untuk melakukan edge detection, antara lain : robert, prewitt dan sobel.
13
Gambar 2.5 Edge Detection 2.3 Computer Vision Computer vision adalah ilmu dan teknologi mesin yang melihat. Sebagai suatu disiplin ilmu, computer vision berkaitan dengan teori di balik sistem buatan yang mengekstrak informasi dari citra. Data citra dapat mengambil banyak bentuk, seperti video terurut, dilihat dari beberapa kamera, atau multi-dimensi data dari scanner medis. Sebagai teknologi disiplin, computer vision berusaha untuk menerapkan teori dan sebagai model untuk pembangunan sistem computer vision. Contoh aplikasi computer vision mencakup sistem antara lain : •
Pengendalian proses, misalnya : sebuah robot industri atau kendaraan otonom.
14 •
Mendeteksi kejadian (Detecting events), misalnya : untuk pengawasan visual dan image sequences.
•
Mengorganisir informasi, misalnya : untuk pengindeksan database foto dan citra urutan.
•
Modeling objects or environments, misalnya : industri inspeksi, analisis citra medis atau topografis model.
•
Interaction, misalnya : sebagai input ke perangkat untuk interaksi manusia komputer. Computer vision berkaitan erat dengan studi tentang biological vision dan model
proses fisiologis di balik persepsi visual pada manusia dan hewan lainnya. Di sisi lain, computer vision merupakan kajian dan menggambarkan proses yang dilaksanakan dalam perangkat
lunak
dan
perangkat
keras
di
belakang
sistem
penglihatan
buatan. Interdisipliner pertukaran antara biological vision dan computer vision telah terbukti bermanfaat bagi kedua bidang. Dalam beberapa hal computer vision merupakan kebalikan dari computer graphics. Sementara computer graphics menghasilkan data citra dari model 3D, computer vision sering menghasilkan model 3D dari data citra. Ada juga kecenderungan terhadap kombinasi dari dua displin ilmu tersebut (computer vision dan computer graphics). Sub-domain
computer
vision
termasuk
scene
reconstruction,
event
detection, video tracking, object recognition, learning, indexing, motion estimation, and image restoration.
15 Hubungan antara computer vision dan berbagai bidang yang terkait :
Gambar 2.6 Bidang-bidang computer vision Banyak kecerdasan buatan (artificial intelligence) berkaitan dengan perencanaan otonom untuk sistem robotical untuk menavigasi melalui lingkungan. Informasi tentang lingkungan hidup dapat disediakan oleh sistem computer vision. Bertindak sebagai sensor dan visi tingkat tinggi yang menyediakan informasi tentang lingkungan dan robot. Kecerdasan buatan dan computer vision dalam bidang yang lain adalah pattern recognition dan teknik pembelajaran. Akibatnya, computer vision kadang-kadang dilihat sebagai bagian dari bidang kecerdasan buatan atau bidang ilmu komputer secara umum. Fisika adalah bidang lain yang terkait erat dengan computer vision. Sistem computer vision mengandalkan sensor citra yang mendeteksi radiasi elektromagnetik yang biasanya dalam bentuk cahaya infra-merah. Sensor dirancang menggunakan solid-
16 state physics. Proses yang menyebarkan cahaya dan permukaan memantul dijelaskan menggunakan optik. Sensor citra canggih bahkan memerlukan mekanika kuantum untuk memberikan pemahaman yang lengkap dari proses pembentukan citra. Selain itu, berbagai masalah pengukuran di fisika dapat diatasi dengan menggunakan computer vision, misalnya gerak dalam cairan. Bidang ketiga yang memainkan peran penting adalah neurobiology, khususnya studi tentang sistem biological vision. Selama berabad-abad terakhir, telah ada studi yang ekstensif tentang mata, neuron, dan struktur otak yang ditujukan untuk pemrosesan rangsangan visual pada manusia dan berbagai hewan. Hal ini menimbulkan pertanyaan yang rumit, yaitu deskripsi tentang bagaimana sesungguhnya sistem computer vision beroperasi dalam rangka untuk menyelesaikan tugas-tugas yang terkait visi tertentu. Hasil ini telah menyebabkan komputer subfield dalam visi, di mana sistem buatan dirancang untuk meniru perilaku pengolahan dan sistem biologi pada tingkat kerumitan yang berbeda. Selain itu, beberapa metode pembelajaran berbasis komputer yang dikembangkan dalam visi memiliki latar belakang dalam biologi. Bidang lain yang terkait dengan computer vision adalah pemrosesan sinyal. Banyak metode untuk memproses variabel satu-sinyal, biasanya waktu sinyal, dapat diperpanjang dengan cara alami untuk pengolahan sinyal dua variabel atau multivariabel sinyal dalam visi komputer. Namun karena sifat spesifik citra, ada banyak metode yang dikembangkan dalam computer vision yang tidak memiliki mitra dalam pemrosesan sinyal satu-variabel. Sebuah karakter yang berbeda dari metode ini adalah kenyataan bahwa mereka yang non-linear, bersama-sama dengan multi-dimensi dari
17 sinyal, mendefinisikan sebuah subfield dalam pemrosesan sinyal sebagai bagian dari computer vision. Contoh-contoh yang disebutkan di atas merupakan pandangan tentang computer vision. Banyak topik penelitian terkait yang juga dapat dipelajari dari sudut pandang matematika murni. Sebagai contoh, banyak metode dalam computer vision didasarkan pada statistik, optimasi atau geometri. Akhirnya, suatu bagian penting dari lapangan dikhususkan untuk aspek pelaksanaan computer vision. Bagaimana metode yang ada dapat diwujudkan dalam berbagai kombinasi perangkat lunak dan perangkat keras, atau bagaimana metode-metode ini dapat dimodifikasi untuk mendapatkan kecepatan pemrosesan tanpa kehilangan terlalu banyak waktu . Hal yang paling erat kaitannya dengan computer vision adalah pengolahan citra, analisis citra dan visi mesin. Ada tumpang tindih yang signifikan dalam berbagai teknik dan aplikasi ini. Ini berarti bahwa teknik-teknik dasar yang digunakan dan dikembangkan dalam bidang ini kurang lebih sama,.yang dapat diartikan sebagai sesuatu yang hanya memiliki satu bagian dengan nama yang berbeda. Di sisi lain, tampaknya sangat diperlukan bagi kelompok-kelompok penelitian, jurnal ilmiah, konferensi dan perusahaan untuk menampilkan atau sebagai pemilik dari salah satu bidang tersebut. Karakteristik di bawah ini relevan, tetapi tidak dianggap sebagai suatu hal yang diterima secara universal: •
Pengolahan citra dan analisis citra cenderung berfokus pada citra 2D, misalnya bagaimana mentransformasikan satu citra yang lain, misalnya dengan bijaksana pixel operasi seperti kontras tambahan, operasi lokal seperti noise ekstraksi atau penghapusan, atau transformasi geometris seperti memutar citra. Karakterisasi
18 ini menyiratkan bahwa pengolahan citra atau analisis asumsi tidak memerlukan atau menghasilkan penafsiran tentang isi citra. •
Computer vision cenderung berfokus pada adegan 3D diproyeksikan ke satu atau beberapa citra, misalnya bagaimana merekonstruksi struktur atau informasi lain tentang adegan 3D dari satu atau beberapa citra. Computer vision sering bergantung pada satu atau lebih
asumsi kompleks tentang adegan yang
digambarkan dalam citra. •
Visi mesin cenderung berfokus pada aplikasi, terutama di bidang manufaktur, misalnya robot otonom berbasis visi dan visi berbasis sistem inspeksi atau pengukuran. Ini berarti bahwa teknologi sensor citra dan teori kontrol seringkali terintegrasi dengan pengolahan data citra untuk mengendalikan robot dan yang real-time processing, yang ditekankan dengan cara yang efisien, serta implementasi di hardware dan software. Hal ini juga menyiratkan bahwa kondisikondisi eksternal seperti pencahayaan dapat dan sering lebih terkontrol dalam visi mesin daripada di computer vision pada umumnya, yang dapat memungkinkan penggunaan algoritma yang berbeda.
•
Ada juga bagian yang disebut pengambaran yang terutama berfokus pada proses untuk menghasilkan citra, tapi kadang-kadang juga berhubungan dengan pengolahan dan analisis citra. Sebagai contoh, medical imaging berisi banyak pekerjaan yang dilakukan pada analisis data citra dalam aplikasi medis.
•
Pengenalan pola (pattern recognition) merupakan bidang yang menggunakan berbagai metode untuk mengekstrak informasi dari sinyal pada umumnya,
19 terutama didasarkan pada pendekatan statistik. Sebuah bagian penting dari bidang ini dikhususkan untuk menerapkan metode ini untuk data citra. 2.4 Stereo Vision Stereo vision adalah proses rekonstruksi model 3D melalui pengolahan citra 2D. Melihat objek atau citra dari dua atau lebih posisi yang berbeda secara bersamaan memungkinkan untuk membuat kesimpulan tentang struktur 3D, yaitu dengan membandingkan titik-titik yang terkait pada citra. Sistem visual manusia dan beberapa hewan lain menggunakan ini, dan sangat penting dalam upaya untuk mengembangkan sistem visual komputer praktis. Stereo vision menggunakan dua kamera untuk mengamati lingkungan, menemukan titik yang sama di setiap citra, dan mengukur kedalaman pada titik itu dengan triangulasi, yaitu dengan melihat garis - garis yang berpotongan dari setiap kamera terhadap objek. Menemukan titik yang sama disetiap citra disebut korespondensi yang merupakan tugas yang mendasar dari computer stereo vision. Depth perception adalah proses ekstraksi kedalaman setiap pixel dalam citra yaitu, menemukan dimensi ketiga dalam citra, dilambangkan dengan (z). Sebuah citra 3D memiliki banyak keunggulan dibandingkan dengan citra 2D. Citra 2D hanya memberikan informasi yang terbatas tentang bentuk dan ukuran fisik suatu objek. Sementara citra 3D mengungkapkan geometri dalam bentuk koordinat 3D, oleh karena itu ukuran dan bentuk dari sebuah objek dapat dihitung dari koordinat 3D. Agar mesin dapat berjalan dengan benar, maka perlu untuk mengetahui seberapa jauh kemampuan mesin tersebut. Beberapa contoh dan aplikasi yang menggunakan 3D
20 informasi adalah: bin-picking, dimana robot diperlukan untuk mengidentifikasi posisi dan orientasi dari objek 3D dan kemudian mengambilnya. Satu lagi adalah aplikasi industri inspeksi untuk objek 3D. Masih banyak lagi aplikasi yang mengarah ke bidang computer vision dan rekonstruksi 3D. Skripsi ini adalah tentang stereo vision dan kedalaman citra. Kedalaman citra hanya ditemukan dengan memperkirakan korespondensi dari setiap pixel dalam citra. Dari pencarian titik korespondensi maka dapat menghitung perbedaan dari setiap pixel yang akan membentuk peta disparity. Untuk kalibrasi kamera, dapat diketahui dari panjang fokus, dan jarak antara kedua pusat kamera, yang disebut baseline. Setelah itu baru kita dapat menghitung depth map. Kamera dapat berorientasi pada cara yang berbeda, dengan orientasi paralel dan sejajar. Kamera paralel terletak pada kedua citra dimasukkan ke dalam image plane. Bila kamera terletak secara sejajar, maka akan lebih sulit untuk menganalisis, walaupun merupakan kasus yang umum bagi sebagian besar kasus praktis. Untuk memecahkan masalah setelah menemukan korespondensi objek, kita dapat menentukan batas tertentu, untuk mengkalibrasi dua kamera. Ada dua jenis parameter yang menghubungkan kamera dengan geometri vision system. Parameter tersebut dikenal sebagai parameter eksternal (ektrinsik) dan internal (intrinsik). Yang didefinisikan sebagai berikut: Parameter eksternal adalah parameter yang menentukan lokasi dan orientasi dari kerangka acuan kamera yang diketahui.
21 Parameter internal adalah parameter yang diperlukan untuk menghubungkan pixel koordinat-koordinat dari titik citra yang sesuai dengan korespondensi koordinat dalam kerangka acuan kamera. Untuk orientasi sejajar, akan dilakukan cara untuk meminimalkan pencarian titik korespondensi dari seluruh citra dengan hanya satu baris yang disebut epipolar line. Masalah stereo vision system dapat dibagi menjadi dua bagian: ■ Korespondensi: yang merupakan proses mencari titik-titik yang sesuai setiap pixel dalam dua citra. ■ Rekonstruksi: yang merupakan proses membangun model citra 3D. Setelah korespondensi didapatkan, kemudian dapat menghitung disparity, yang merupakan perbedaan posisi dari dua titik yang sesuai. Jika diketahui parameter internal dari dua kamera, yaitu panjang fokus, dan jarak antara kamera, maka dapat membentuk peta disparty, yang menunjukkan kedalaman setiap pixel dalam citra. Dari hasil tersebut, dapat dibangun model citra 3D. 2.4.1 Korespondensi Proses menentukan perbandingan antara titik dalam pasangan citra disebut korespondensi. Dengan asumsi bahwa kita memiliki dua bentuk citra yang diambil dari dua sudut pandang yang berbeda. Proses menemukan korespondensi hanya untuk menentukan titik mana pada citra kiri berhubungan dengan titik dalam citra kanan. Tetapi, salah satu kesulitan menemukan korespondensi adalah tidak semua titik di sebelah kiri terlihat dengan jelas, karena orientasi yang berbeda dari kamera. Jadi sistem stereo harus dapat
22 menentukan bagian-bagian citra yang tidak cocok. Jika ditemukan titik-titik yang cocok antara citra kiri dan kanan maka disebut pasangan konjugasi atau conjugated pair. Cara menemukan pasangan konjugasi dari sebuah titik dalam dua citra, adalah dengan memilih sebuah titik di salah satu citra dan menentukan baris pencarian pada citra lain, yang disebut garis epipolar atau epipolar line. Jadi batas pencarian selalu dapat dikurangi menjadi 1D, tergantung pada posisi relatif dari kamera. Jika dua foto akan diambil dari dua kamera pararel, maka garis pencarian baris merupakan garis yang sama pada kedua citra. Jika foto akan diambil dari dua kamera sejajar, maka garis pencarian harus garis yang melewati titik korespondensi dan titik lainnya yang disebut epipole. Ketika garis pencarian telah ditemukan, maka dapat menghitung nilai kesamaan untuk setiap titik pada garis dengan membandingkan suatu daerah di sekitar titik pada citra pertama dan daerah sekitar setiap titik pada garis pencarian. Metode ini untuk menemukan korepondensi yang disebut area-based method. Ada beberapa faktor yang menyulitkan dalam masalah korespondensi: 1. Occlusions: dimana titik dalam satu citra tidak sesuai dengan titiktitik dalam citra lain. Ini biasanya terjadi pada sebuah objek yang dekat dengan kamera, yang akan mengaburkan bagian dari citra pertama yang dapat dilihat dalam citra kedua dan sebaliknya atau suatu objek yang menghalangi suatu daerah pada satu kamera dan bukan yang lain
23
Gambar 2.7 Occlusions 2. Noise: adanya noise pada citra pertama, yang tidak berkorespondensi pada citra yang lainnya. 3. Photometric distortions: membuat intensitas yang diproyeksikan pada titik yang berbeda dalam dua jendela yaitu citra akan mencerminkan intensitas yang berbeda dari berbagai sudut. 4. Projective distortion: membuat proyeksi bentuk-bentuk yang berbeda di kedua citra. Efek ini dapat dilihat dalam dua cara: 1. Permukaan berkurang, yang terlihat dari tanda-tanda menjadi lebih kecil. 2. Permukaan condong, muncul dengan tanda-tanda yang dikompresi dalam arah kecondongan 3. Proyektif distorsi memberikan otak manusia citraan umum tentang bentuk-bentuk benda-benda dibidang visual. Otak
24 manusia dapat menggunakan informasi ini untuk membuat dugaan-dugaan tentang bentuk benda-benda yang dilihatnya. Sehingga dapat mengisi kekosongan yang ditinggalkan oleh teropong disparity.
Gambar 2.8 Projective distortion 5. Non-Texture Areas: ada bagian dimana tidak ada intensitas variasi, maka daerah ini akan memiliki jumlah yang sama dalam hal kesamaan nilai untuk seluruh bagian. Beberapa poin yang sesuai dapat diperoleh ketika tidak ada tekstur dalam suatu wilayah yang lebih besar daripada ukuran jendela. Hal ini tidak mungkin bagi kesamaan
untuk
membedakan
antara
jendela
sebelum
dan
sesudahnya. 2.4.2 Area-Based Method Area-Based Method digunakan untuk mencari korespondensi antara dua citra stereo. Dalam area-based method elemen yang cocok adalah jendela dari citra yang diambil di sekitar titik. Ini adalah jumlah kesamaan antara jendela di kedua citra, yang akan menentukan korespondensi dari sebuah titik.
25 Menemukan titik korespondensi yang sukses akan memungkinkan untuk mengukur perbedaan antara dua citra, dan menyediakan apa yang dibutuhkan untuk membangun peta disparity. Menemukan perbedaan dari dua perbandingan yang sesuai akan dijelaskan dalam bagian berikutnya. Ada dua cara untuk menemukan kesamaan nilai dari jendela di kedua citra, yaitu perbandingan dari area tersebut dengan melakukan oleh cross-correlation atau SSD (sum of squared difference).
c(x,y,d) merupakan persamaan untuk menentukan titik korespondensi, dimana η = [- n, n] adalah tinggi jendela, ξ = [- m, m] adalah panjang jendela, x dan y adalah koordinasi untuk titik di sebelah kiri citra (ImL) dan d adalah perpindahan sedangkan ImR merupakan titik di sebelah kanan citra. Area-Based Method akan digunakan untuk menemukan peta disparity dari sebuah citra stereo. 2.4.3 Disparity Disparity adalah perbedaan posisi (pergeseran) antara dua titik yang sesuai. Perbedaan ditemukan dengan mencari indeks dari nilai maksimum korelasi (SSD) dari semua perpindahan titik:
26
SSD biasanya lebih sering digunkan dari cross-correlation, karena tidak terjadi bias dengan adanya daerah yang sangat kecil atau sangat besar nilai intensitasnya. Disparity dari semua titik dalam bentuk citra disebut peta disparity, yang dapat dipindahkan sebagai citra. Setelah disparity telah ditemukan pada semua titik-titik dalam citra sebelah kiri maka kita dapat menghitung depth. Rumus depth
berasal dari
segitiga sama sisi.
Gambar 2.9 Menemukan depth dari disparity Ambil dasar Triangle 1, dan membaginya dengan ketinggian yang sama Triangle. Ini sama dengan dasar Triangle 2, dibagi dengan tinggi Triangle 2. Depth pada titik P adalah sama dengan tinggi Triangle 1. xl dan xr adalah koordinat dari pr dan pl sehubungan dengan titik-titik utama cr dan cl. Jadi, dalam contoh Gambar 2.9 xr adalah negatif dan xl adalah positif.
27
Jadi depth setiap titik yang dilihat, adalah panjang focal f kali baseline T dibagi dengan disparity dari titik itu (d). 2.4.4 Konsep Pencarian Window Beberapa metode yang disarankan untuk proses menemukan titik korespondensi dan membangun peta kedalaman yang lebih akurat antara lain: 1. Single window method. 2. Multiple window method. 3. Adaptive search window method. Metode yang berbeda ini, digunakan untuk memecahkan beberapa masalah seperti occlusion, projective distortion dan beberapa titik yang sesuai dikaitkan dengan menemukan korespondensi antara dua citra. 2.4.4.1 Single Window Method Metode ini adalah salah satu yang paling sederhana. Dengan mengasumsikan window yang cocok dengan ukuran tetap dan bentuk korespondensi selama proses pencarian. Pilihan ukuran dan bentuk jendela ditentukan oleh pengguna dari awal. Setelah ditetapkan, maka ukuran window tidak akan berubah.
28 Untuk mengoptimalkan kecepatan metode yang digunakan, kita menentukan panjang pada garis pencarian diantara nilai-nilai maksimum dan minimum. Nilai maksimum dan nilai minimum akan tergantung pada sifat dari citra itu sendiri.
Gambar 2.10 Menemukan garis paraller stereo image Keuntungan dari single window method adalah metode yang sangat sederhana dan lebih cepat daripada dua metode lainnya. Kerugian dari single window method adalah tidak dapat memecahkan masalah pada beberapa titik korespondensi, non-texture areas, projective distortion dan occlusions. Jadi tidak terlalu akurat dalam memperkirakan depth. Sebuah solusi untuk masalah beberapa titik koresponensi dengan menggunakan
single
window
method
adalah
dengan
memilih
menambahkan satu titik dimana pengujian dengan mencari satu titik korespondensi yang gagal. Hal ini dapat meningkatkan hasil, tetapi tidak akan menyelesaikan masalah secara keseluruhan. Solusi yang lebih baik
29 dengan menggunakan Multiple Window method atau Adaptive search window method. 2.4.4.2 Multiple Window Method Dalam mutiple window method digunakan sembilan window yang berbeda, yang ditunjukkan pada figure 5 di bawah, yang diambil untuk menemukan korelasi pada setiap pixel dan menghitung disparity dengan kesalahan SSD terkecil sehingga disparity akan memilih window yang tepat.
Gambar 2.11 Sembilan asimetrik korelasi window Dalam multiple window method memiliki keuntungan yaitu dengan beberapa window dapat memperkirakan disparity yang digunakan untuk menghitung ketidakpastian sebagai "perkiraan varians dari ukuran disparity yang diperoleh dalam beberapa window, dan titik-titik occlusions dari varians tak terbatas." Ini akan meningkatkan hasil di daerah yang teksturnya kurang baik.. Keuntungan
dari
multiple
window
method
yang
dapat
meningkatkan perkiraan disparity, dan memberikan depth lebih akurat. multiple window method masih lebih cepat daripada adaptive search
30 window method. Multiple window method juga dapat memecahkan masalah occlusions. Kerugiannya dari multiple window method adalah tidak dapat menangani daerah yang luas yang tidak berstruktur, dan masih tidak mampu sepenuhnya menyelesaikan masalah projective distortion. 2.4.4.3 Adaptive Search Window Untuk
memecahkan
masalah
dalam
menemukan
titik
korespondensi, salah satunya dengan adaptive search window. Algoritma mengasumsikan penggunaan berbagai bentuk dan ukuran window pencarian, dan karenanya disebut adaptive search window. Bentuk window merupakan hal yang sangat penting karena properti citra seperti intensitas, disparity dan tekstur adalah piecewise halus. Semua itu berbeda-beda kehalusannya pada kebanyakan titik, tetapi berubah secara dramatis pada batas-batas objek. Lebih jauh, karena bertindak sebagai filter pada citra, dan memperkenalkan bias sistemik ke dalam proses pencocokan. Dalam metode ini ukuran window dan bentuk yang iteratively diubah berdasarkan variasi lokal intensitas dan pekiraan depth. Adaptive search window memberikan hasil yang jauh lebih baik tapi masih mahal. Ukuran window harus cukup besar untuk memuat variasi intensitas yang memadai untuk pencocokan yang akurat dan dapat
31 diterima, tetapi juga harus cukup kecil untuk meminimalkan efek projective distortion. Window yang sangat kecil tidak dapat mencakup variasi intensitas yang cukup sehingga memberikan perkiraan kecilnya disparity karena sinyal (intensitas varias) untuk rasio noise akan rendah. Di sisi lain window yang besar dapat juga memberikan hasil buruk karena posisi korelasi maksimum atau minimum SSD tidak akan cocok karena efek projective distortions di kiri dan kanan citra. Untuk semua hal-hal di atas ukuran window harus dipilih adaptif sesuai dengan variasi intensitas.
Gambar 2.12 Window expansion Metode ini menyarankan untuk "memilih window yang tepat dengan mengevaluasi variasi lokal intensitas dan disparity". Dengan menerapkan model statistik untuk distribusi disparity dalam window harus dibangun. Model ini akan membantu untuk membangun sebuah jendela, yang mencari disparity, dengan perkiraan ketidakpastian minimum untuk setiap pixel dalam citra. Ukuran serta bentuk (persegi) dari jendela adalah adaptif.
32 Salah satu kesulitan yang berhubungan dengan Adaptive search window adalah perkiraan dari disparity. Karena perbedaan variasi adalah hasil akhir yang dicari dalam stereo vision, pada saat yang sama itu adalah salah satu kriteria yang digunakan untuk memperkirakan disparity.
Gambar 2.13 Posisi setiap ukuran dan bentuk dari window yang dipilih setelah diuji
Gambar 2.14 Window yang dipilih pada setiap posisi
33 2.5 Parallel Stereo Images Dalam kamera paralel, dapat diasumsikan bahwa sumbu optik adalah berbaris sejajar satu sama lain dan berdampingan atau lebih tepatnya, garis yang menghubungkan pusat-pusat optik yang sejajar dengan sumbu x. Ini berarti bahwa citra sebuah titik akan memiliki koordinat y yang sama untuk dua kamera. Garis yang menghubungkan pusatpusat lensa kamera disebut baseline. Dalam kasus dua kamera paralel, menemukan depth jauh lebih sederhana daripada ketika non-paralel karena setiap pasangan konjugasi harus terletak pada baris yang sama di kedua citra, yaitu nilai y akan sama. Menemukan korespondensi tidak perlu untuk memperbaiki citra, dan tidak mengubah orientasi. Proses hanya perlu memilih untuk setiap titik dalam citra kiri, cari titik korespondensi pada baris yang sama. Kriteria untuk menemukan korespondensi dapat diukur baik menggunakan cross correlation atau sum of squared difference (SSD). Salah satu dari metode yang diusulkan untuk menemukan korespondensi, yaitu Single Window, Multiple Windows atau Adaptive Search Window dapat digunakan selama proses tersebut. Pasti setiap metode akan memberikan hasil yang berbeda. 2.6 Non-Parallel Stereo Images Kasus dua kamera sejajar secara paralel bukanlah kasus umum dalam stereo vision, kamera paralel membatasi ruang daerah dimana benda-benda yang terlihat di kedua citra. Hal ini lebih umum untuk menempatkan kamera sehingga sumbu yang mengarahkan kamera ke dalam. Situasi ini disebut konvergensi kamera atau kamera sejajar. Dalam hal ini titik korespondensi pada umumnya tidak akan berada pada koordinat y yang sama.
34 Stereo geometry dengan dua citra yang diambil dari dua kamera non-paralel disebut epipolar geometry. Dalam hal ini akan memperkenalkan geometric property dikenal dalam computer vision sebagai epipolar constraint. Ada dua cara untuk mengekstraksi struktur 3-D dari pasangan citra: 1. Classic method, yang dikenal sebagai calibrated route. Pertama-tama perlu untuk mengkalibrasi kamera (atau sudut pandang), berkenaan dengan sejumlah sistem koordinat, menghitung epipolar geometry dengan mengeluarkan matriks yang penting dari sistem, dan dari menghitung ini struktur Euclidean 3-D pada scene citra. 2. Uncalibrated system adalah sebuah kuantitas yang dikenal sebagai fundamental matrix dihitung dari citra korespondensi dan kemudian digunakan untuk menentukan proyektif struktur 3-D dari scene citra. 2.6.1 Epipolar Geometry Mengingat sepasang stereo kamera setiap titik dalam ruang 3-D yang didefinisikan sebuah plane π , melewati P dan pusat proyeksi dari kedua kamera. Plane π disebut epipolar plane dan garis-garis lurus di mana π memotong image plane disebut conjugated epipolar lines. Ini adalah citra dalam satu kamera dari sebuah
sinar
melalui
pusat
optik
dan
citra
titik
di
lain
kamera. Citra dalam satu kamera kamera lain pusat proyeksi dikenal sebagai epipole. Dengan kata lain, epipole adalah titik perpotongan dari garis yang menghubungkan optik pusat, yaitu baseline, dengan image plane.
35
Gambar 2.15 Area epipolar Dengan pengecualian dari epipole, hanya satu epipolar line melewati titik citra apapun. Semua epipolar line melewati satu kamera-kamera epipole. Epipolar constraint yang menyatakan bahwa titik berkorespondensi harus terletak pada conjugated epipolar lines. epipolar geometry adalah geometri proyektif intrinsik antara dua pandangan yang independen dari struktur scene, dan hanya tergantung pada parameter internal kamera dan posisi relatif. Menentukan posisi lokasi titik objek tergantung pada citra yang cocok dengan lokasi titik objek dalam satu citra ke lokasi titik objek yang sama dalam citra lain. Pada awalnya mungkin terlihat bahwa korespondensi memerlukan pencarian melalui seluruh citra, tapi epipolar constraint mengurangi pencarian pada satu garis. Jadi titik dalam satu citra pl menghasilkan garis dalam pada titik korespondensi pr. Pencarian korespondensi dengan demikian mengurangi suatu wilayah pada garis, karena merupakan masalah 1-D.
36
Gambar 2.16 Epipolar line Hasil di atas ditemukan, menggunakan 8-titik algoritma. Setelah titik korespondensi dari kiri dan kanan citra, program menghitung Fundamental Matrix FP. Kemudian menemukan parameter epipolar line, dari koordinat titik di sebelah kiri citra dan Fundamental Matrix. Dengan menarik garis di sebelah kanan seperti yang ditunjukkan citra. Karena benar-benar memilih 8 titik korespondensi, maka dihitung Fundamental Matrix, hanyalah perkiraan, dan dengan
demikian
mengalami
kesalahan. Namun
dibandingkan
dengan
kesederhanaan dan kecepatan, 8-titik algoritma masih merupakan salah satu yang algoritma terbaik yang digunakan untuk memperkirakan geometri epipolar. 2.6.2 Essential Matrix Frame referensi kiri dan kanan kamera dihubungkan melalui parameter eksternal. Menentukan transformasi dalam ruang 3-D dengan vektor translasi T = (Or-Ol) dan sebuah matriks rotasi R. Diketahui sebuah titik P dalam ruang hubungan antara Pr dan Pl dan oleh karena itu
37 Hubungan antara titik dalam ruang 3-D dan proyeksi digambarkan oleh persamaan dari proyeksi perspektif persamaan:
Persamaan dari epipolar plane melewati P dapat ditulis sebagai perkalian cross dari vektor Pl, T dan (Pl-T) seperti di bawah ini : Menggunakan hasil dari rumus ke (5)
Menulis produk cross sebagai kekurangan pangkat matriks :
Maka (5) akan menjadi :
E matriks disebut Essential matrix.
38 Essential matrix langsung menghubungkan epipolar constraint dengan parameter eksternal dari sistem kamera. Titik essential matrix dalam satu kamera pada epipolar line di kamera kedua. Titik essential matrix dalam frame kamera melalui epipolar constraint:
Epl sebagai garis proyektif dalam right plane lr yang melewati pr dan epipole er.
Gambar 2.17 Epipolar Constrain 2.6.3 The Fundamental Matrix Seluruh pembahasan yang digunakan dalam kamera koordinat referensi Frame tetapi sebenarnya mengukur citra dari koordinat pixel.
39
Gambar 2.18 Hubungan camera frame Oleh karena itu agar dapat menggunakan essential matrix, perlu mengetahui transformasi dari koordinat kamera pixel, yaitu parameter internal. Keterbatasan ini dapat dihailangkan dengan menggunakan fundamental matrix. Fundamental matrix sering digunakan dalam rekonstruksi objek yang diambil dengan dua kamera yang tidak dikalibrasi. Ini adalah pemetaan yang sangat kuat antara citra stereo. Ini mencakup baik dengan parameter internal maupun eksternal dari sistem dan memungkinkan untuk menjelaskan epipolar geometry dari titik yang sesuai. Dengan asumsi Ml merupakan matriks parameter internal kamera kiri. Sebuah titik pada koordinat citra p^l ditulis dalam frame kamera sebagai:
Demikian pula untuk titik sebelah kanan :
40 Dengan mensubstitusikan persamaan ini pada persamaan (10) di atas, maka didapatkan:
dimana :
F di sini adalah fundamental matrix. Seperti persamaan (15), untuk fundamental matrix yang dimiliki
Persamaan (20) dapat dianggap sebagai persamaan dari projective epipolar line yang sesuai dengan titik pl. Perbedaan essential matrix dan fundamental matrix adalah bahwa fundamental matrix didefinisikan dalam bentuk koordinat pixel dan essential matrix didefinisikan dalam istilah koordinat kamera. Oleh karena itu jika dapat memperkirakan fundamental matrix dari sejumlah titik pembanding dalam pixel koordinat, maka dapat merekonstruksi epipolar geometry tanpa informasi sama sekali tentang parameter internal atau eksternal. 2.6.4 Recovering Epipolar Geometry and Eight Point Algorithm Banyak teknik yang ditemukan untuk epipolar pemulihan. Epipolar geometry dapat diturunkan dari titik yang sesuai pada citra dengan menggunakan 8-points algorithm. 8-points algorithm sering digunakan untuk menghitung fundamental matrix dari delapan pasang atau lebih titik yang koresponden.
41 Keuntungan dari 8-points algorithm adalah linear, maka dengan cepat dan mudah diimplementasikan. Jika 8 titik yang berkorespondensi diketahui, maka solusi dari serangkaian persamaan linear dapat digunakan. Kerugian dari 8-points algorithm sangat rentan terhadap noise. Tetapi translation dan scaling (normalisasi) sebelum merumuskan persamaan linier meningkatkan hasil. Transformasi tidak meningkatkan kompleksitas dari algoritma. Mengasumsikan bahwa n titik korespondensi telah dibentuk antara kiri dan kanan citra. Setiap korepondensi menyediakan persamaan linier homogen dalam bentuk:
Ada sedikitnya 8 korespondensi (n³8), sebuah sistem linear homogenya terbentuk. Jika pl = (x, y, 1) dan pr = (x ', y', 1) adalah dua titik yang sesuai di kiri dan kanan citra, dengan koordinasi yang homogen. Dari epipolar constraint, persamaan (18), untuk setiap titik i memiliki:
Dimana f1 melalui F9 adalah unsur fundamental matrix. Memperluas (21) untuk setiap salah satu titik maka akan memiliki 8 persamaan dalam bentuk:
42 Dapat disusun kembali sebagai AF = 0, di mana A adalah (n x 9) pengukuran persamaan matriks, dan F adalah fundamental matrix ditunjukkan dengan 9-vektor.
Untuk 8-points algorithm, memiliki (n = 8). Ini merupakan masalah aljabar linear standar karena jika sistem bersifat homogen, terdapat solusi unik hingga faktor skala yang tidak dikenal. Maka solusinya adalah eigenvector dengan minimum eigenvalue dari ATA. Jika kita memperluas A menggunakan Singular Value Decomposition (SVD), dengan metode ini maka dapat menulis A sebagai: Solusi sistem SVD adalah kolom V terkait dengan setidaknya nilai tunggal A. Jika A adalah matrik n x n, maka vektor tak nol x di dalam Rn dinamakan eigenvector dari A jika Ax adalah kelipatan skalar dari x, yaitu Ax = λx Untuk suatu skalar λ disebut eigenvalue dari A dan x dikatakan eigenvector yang bersesuaian dengan λ. Untuk mencari eigenvalue matrik A yang berukuran n x n maka kita menuliskannya kembali Ax = λx sebagai Ax = λIx
Ù (λI – A)x = 0
