6

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

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 multi-

variabel 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 kondisi-

kondisi 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 titik-

titik 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 pusat-

pusat 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