BAB 2 LANDASAN TEORI 2.1 Kerangka Acuan Reference frames atau kerangka acuan adalah suatu sistem koordinat atau sekumpulan sumbu yang digunakan untuk mengukur posisi, dan orientasi dari suatu objek. Dalam skripsi ini ada beberapa kerangka acuan yang perlu diperhatikan, yaitu: •
Dunia/World (xw, yw, zw) Kerangka acuan yang tetap terhadap dunia, misalnya saja salah satu sudut suatu ruangan. Kerangka acuan ini berguna untuk menunjukkan hubungan posisi antar objek.
•
Kamera/Camera (xc, yc, zc) Kerangka acuan yang menempel pada kamera dan titik awalnya berada pada pusat proyeksi dari kamera, berbeda dengan world, kerangka acuan ini bisa berubah - ubah bergantung pada posisi dan orientasi kamera.
•
Bidang gambar/Image plane (x f , y f) Kerangka acuan yang berada pada bidang gambar. Pada umumnya, titik paling kiri atas dijadikan sebagai titik awal. Kerangka acuan image plane terdiri dari dua yaitu physical dan pixel. Perbedaanya terletak pada satuan yang digunakan. Physical diukur dalam satuan milimeter dan merupakan sekumpulan persegi dari photosensor. Sedangkan pixel, dinyatakan dalam satuan pixel. Sebuah pixel menunjukkan nilai integer dari sebuah sampel gambar. Yang digunakan pada gambar digital adalah satuan pixel ini.
6
7
Untuk lebih jelasnya dapat dilihat pada gambar dibawah ini:
Gambar 2.1 Reference frames dan Bidang Gambar (Sumber: Camera Parameters by Prof. George Bebis)
Gambar 2.1 (b) menunjukkan bidang gambar yang terdiri dari sekumpulan photosensor yang dikenal sebagai CCD (Charge-Coupled Device) array. Setiap kotak menunjukkan satu buah photosensor yang berfungsi untuk mengubah energi cahaya menjadi tegangan listrik. Nilai dari tegangan listrik akan dikirimkan ke sebuah alat yang dinamakan sebagai frame grabber, untuk dikonversi dari sinyal kontinu menjadi sinyal digital yang dapat diproses menggunakan komputer. Sinyal digital hasil konversi inilah yang dinamakan sebagai pixel.
8
Gambar 2.2 Digital image acquisition system (Sumber: Camera Parameters by Prof. George Bebis)
2.2 Parameter Kamera Secara umum parameter kamera yang diperlukan dalam skripsi ini terdiri dari dua yaitu extrinsic dan intrinsic.
Gambar 2.3 Transformasi antar Kerangka Acuan (Sumber: Camera Parameters by Prof. George Bebis)
Parameter extrinsic mendefinisikan posisi (Translasi) dan orientasi (Rotasi) dari kerangka acuan kamera terhadap kerangka acuan dunia. Pada stereo vision, salah satu kerangka acuan kamera dijadikan kerangka acuan dunia, biasanya kerangka acuan kamera kiri dan parameter extrinsic mendefinisikan kerangka acuan kamera kanan terhadap kerangka acuan kamera kiri.
9
Gambar 2.4 Extrinsic Parameter (Sumber: E.Trucco, A.Verri, 1998)
Parameter intrinsic mendefinisikan transformasi posisi sebuah point gambar dari koordinat kamera ke koordinat pixel. Parameter ini menunjukkan karakter geometri, digital dan optikal dari kamera yaitu koordinat principal point dan focal length, dalam satuan pixel dari setiap kamera serta distorsi yang diakibatkan oleh lensa yang digunakan kamera. Proyeksi objek pada bidang gambar dapat dinyatakan dengan persamaan:
Gambar 2.5 Proyeksi perspektif dasar (f=focal length) (Sumber: http://www.cse.psu.edu/~rcollins/CSE486/)
Sedangkan transformasi dari bidang gambar menjadi koordinat pixel:
10
x = −( xim − o x ) s x → xim = − x / s x + o x y = −( y im − o y ) s y → y im = − y / s y + o y dengan, xim = koordinat x dalam satuan pixel yim = koordinat y dalam satuan pixel x = koordinat x dalam satuan milimeter y = koordinat y dalam satuan milimeter ox = principal point sumbu x oy = principal point sumbu y sx = ukuran pixel efektif dalam arah horizontal sy = ukuran pixel efektif dalam arah vertikal Persamaan ini dapat dinyatakan dalam notasi matriks, sebagai berikut: xim − 1 / s x 0 o x x y = 0 − 1/ s o y y y im 1 0 0 1 1
2.2.1 Rodrigues’ Rotation Formula Matriks rotasi dapat diperoleh dari hasil perkalian antara tiga buah matriks, yaitu matriks rotasi sumbu x, y, dan z. Selain menggunakan ketiga buah matriks ini, rotasi juga dapat dilakukan dalam representasi sumbu-sudut (axis-angle). Formula rotasi rodrigues adalah sebuah algoritma
yang
digunakan untuk melakukan rotasi dalam representasi sumbu-sudut tersebut. Yang diketahui dalam representasi ini adalah sumbu rotasi dan besarnya sudut rotasi yang perlu dilakukan. Sumbu rotasi dinyatakan arahnya dengan sebuah vektor unit. Formula rodrigues dinyatakan sebagai: R = I cos θ + [k ]x sin θ + (1 − cos θ )kk T
11
[k ]x
0 − k3 k2 = k 3 0 − k1 − k 2 k1 0
k = (k x , k y , k z )
k adalah vektor unit yang merepresentasikan sumbu rotasi dan I adalah matriks indentitas.
2.3 Median Filter Salah satu proses low-level pada pengolahan gambar yang bertujuan untuk mengeleminasi noise pada gambar. Hal ini dicapai dengan menggantikan nilai setiap pixel yang ada pada gambar dengan nilai tengah dari nilai pixel itu sendiri dan nilai pixel yang berada disekeliling pixel tersebut. Untuk menentukan nilai tengah, maka nilai dari satu pixel dan pixel tetangganya akan diurutkan terlebih dahulu. Lebih jelasnya bisa dilihat pada gambar dibawah ini:
Gambar 2.6 Median Filtering (window 3x3) (Sumber: http://users.ecs.soton.ac.uk/msn/book/new_demo/median/)
Keunggulan dari median filter adalah dapat mengeliminasi noise dan pada saat yang bersamaan menjaga tepi (edge)
pada gambar. Tentunya hal ini juga
bergantung pada besar window yang digunakan.
12
Gambar 2.7 Contoh Median Filtering (Sumber: http://en.wikipedia.org/wiki/Median_filter)
Median filter efektif digunakan untuk mengeliminasi salt and pepper noise, yaitu noise berupa pixel hitam dan putih yang muncul secara acak pada gambar.
Gambar 2.8 Salt and Pepper Noise (Sumber: http://en.wikipedia.org/wiki/Salt_and_pepper_noise)
2.4 Canny Edge Detector Canny edge detector adalah salah satu metode yang dapat digunakan untuk mendeteksi tepi dari gambar, Tahapan-tahapan dari algoritma canny edge detector adalah:
13
•
Noise reduction, dengan melakukan konvolusi antara gambar dengan filter gaussian. Hasil yang diperoleh adalah gambar yang lebih halus (smooth) dari gambar asli, mengurangi intensitas pixel yang gradasinya berbeda jauh dengan pixel disekitarnya.
•
Finding
intensity
gradient,
menggunakan
operator
sobel
untuk
menentukan besar dan arah gradasi intensitas dari pixel-pixel gambar. Operator sobel menggunakan dua buah 3x3 matriks konvolusi, satu untuk mengestimasi gradasi pada arah x (Gx) dan satu lagi pada arah y (Gy).
Gambar 2.9 Matriks Konvolusi Operator Sobel (Sumber: Green, 2002)
Hasil pengukuran gradasi Gx dan Gy dapat digunakan untuk menentukan besar (G) dan arah (θ) gradasi menggunakan persamaan: G = Gx 2 + Gy 2
Gy Gx
θ = arctan
Arah gradasi pada suatu matriks gambar hanya terdiri dari 4 arah, yaitu horizontal, vertikal, diagonal positif dan diagonal negatif, oleh karena itu perlu dilakukan pengelompokkan arah gradasi hasil perhitungan kedalam salah satu kelompok arah ini. Hal ini dilakukan sebagai berikut:
Gambar 2.10 Pengelompokan Arah Gradasi (Sumber: Green, 2002)
14
Semua arah gradasi yang berada dalam daerah warna: *
Kuning akan dinyatakan dengan nilai arah gradasi 00 (00 - 22.50, 157.50 - 1800)
*
Hijau akan dinyatakan dengan nilai arah gradasi 450 (22.50 - 67.50)
*
Biru akan dinyatakan dengan nilai arah gradasi 900 (67.50 - 112.50)
*
Merah akan dinyatakan dengan nilai arah gradasi 1350 (112.50 157.50)
•
Non-maximum suppression, mengkonversikan tepi yang blur menjadi tepi yang lebih tipis/tajam dengan cara menolkan pixel yang tidak dianggap sebagai tepi. Pixel yang dianggap sebagai tepi pada langkah ini adalah pixel-pixel yang memiliki nilai terbesar pada suatu arah gradasi. Oleh karena itu hasil dari langkah ini adalah sebuah tepi berupa garis yang tipis.
Gambar 2.11 Ilustrasi Non-maximum Suppression (Sumber: www.cse.iitd.ernet.in/~pkalra/csl783/canny.pdf)
Besar intensitas pixel ditunjukkan dengan warna dan angka, sedangkan arah ditunjukkan dengan tanda panah. Berikut ini adalah contoh hasil dari Non-maximum suppression:
15
Gambar 2.12 Non-maximum Suppression (Sumber: www.cse.iitd.ernet.in/~pkalra/csl783/canny.pdf)
•
Hysteresis, penggunaan dua buah nilai threshold, high dan low untuk mengeliminasi streaking. Streaking adalah putusnya sebuah tepi akibat dari nilai output operator yang naik turun pada nilai threshold.
•
Lebih besar high ditandai sebagai tepi
•
Lebih kecil low tidak ditandai sebagai tepi
•
Diantara dua threshold ditandai sebagai tepi jika terkoneksi dengan pixel yang intensitasnya lebih besar dari high.
2.5 Stereo Vision Stereo vision adalah suatu kemampuan untuk memperoleh informasi struktur 3D dan kedalaman dari suatu scene melalui dua atau lebih gambar yang diambil dari sudut pandang yang berbeda (Trucco, Verri, 1998). Sistem ini dibuat dengan meniru mata manusia yang terdiri dari dua buah dan terletak pada posisi yang berbeda secara paralel, sekitar 2-3 inchi. Dengan koordinasi seperti ini akan ada dua buah informasi visual yang diperoleh dari suatu area pada suatu waktu dengan sudut pandang yang sedikit berbeda.
16
Pada computer stereo vision, mata digantikan dengan dua buah kamera yang memiliki spesifikasi yang sama dan diletakkan pada posisi bidang y dan z yang sama, namun berbeda pada sumbu horizontal, seperti halnya mata manusia. Jarak antara dua kamera pada sumbu horizontal dikenal dengan baseline.
Gambar 2.13 Geometri Stereo Vision (Sumber: http://www.cse.psu.edu/~rcollins/CSE486/)
Dengan melakukan komparasi dua buah gambar yang diperoleh maka akan didapatkan informasi berupa disparity, yang nilainya berbanding terbalik secara proporsional dengan kedalaman atau jarak suatu objek. Disparity dari semua pixel akan membentuk sebuah disparity map yang dapat ditampilkan sebagai sebuah gambar.
2.5.1 Stereo Matching Proses pencarian untuk menentukan pasangan pixel antara gambar kiri dan
17
kanan. Dalam melakukan proses pencarian ada satu gambar yang dijadikan acuan dan proses pencarian dilakukan pada gambar yang lain. Misal gambar kiri dijadikan acuan, maka pixel yang merupakan pasangan dari pixel gambar kiri, akan dicari pada gambar kanan, atau sebaliknya. Performa dari proses pencarian ini dapat dipengaruhi oleh occlusion, suatu kondisi dimana pixel tidak memiliki pasangan dan fakta bahwa suatu gambar memiliki dua dimensi yaitu x dan y.
Ada beberapa batasan yang dapat digunakan untuk mempermudah proses pencarian pasangan pixel ini, yaitu left-right consistency dan epipolar constraint. Left-right consistency, suatu batasan dimana pasangan pixel dinyatakan benar ketika proses pencarian dengan acuan gambar kiri dan acuan gambar kanan menghasilkan pasangan pixel yang sama. Hal ini untuk mengatasi masalah occlusion. Batasan yang kedua, yaitu epipolar constraint untuk mengurangi dimensi pencarian menjadi satu dimensi, hal ini didukung dengan fakta bahwa pasangan pixel berada pada conjugate epipolar lines.
Terdapat beberapa metode yang dapat digunakan untuk menentukan pixel mana yang merupakan pasangan pixel yang tepat dengan pixel acuan, salah satunya adalah metode korelasi/area. Pada metode ini, yang akan dicocokan adalah dua buah window dengan suatu ukuran yang tetap. Window yang pertama adalah window dengan pusat pixel acuan, sedangkan window yang kedua adalah window dengan pusat kandidat pixel yang berada pada gambar yang lain. Korelasi antar kedua window ini ditentukan berdasarkan suatu kriteria tertentu. Pixel kandidat yang dijadikan sebagai pasangan pixel acuan
18
adalah pixel kandidat dengan window yang paling memenuhi kriteria yang digunakan, dengan kata lain window yang paling mirip dengan window pixel acuan.
Gambar 2.14 Ilustrasi Metode Korelasi/Area
2.5.2 Disparity Perbedaan koordinat dari pasangan pixel gambar kiri dan kanan dikenal sebagai disparity. Pada sistem stereo vision yang menjadi perhatian adalah perbedaan koordinat pada sumbu x, mengingat dua buah kamera diatur agar tepat berada pada posisi yang sama pada dua sumbu yang lain, yaitu sumbu y dan z.
Gambar 2.15 Disparity (Sumber: http://www.cse.psu.edu/~rcollins/CSE486/)
19
2.5.3 Epipolar Geometry
Gambar 2.16 Epipolar Geometry (Sumber: E.Trucco, A.Verri, 1998)
Digunakan untuk mendapatkan informasi yang dibutuhkan dalam proses pencarian pasangan pixel. Geometri ini menggambarkan proyeksi suatu point pada bidang gambar kiri dan kanan (stereo). Pada gambar 2.16 ada beberapa hal yang perlu diperhatikan yaitu epipolar plane, epipole el dan er, dan epipolar line elpl dan erpr. Epipolar plane adalah sebuah bidang yang dibatasi oleh titik P, Ol dan Or. pl dan pr adalah proyeksi titik P pada bidang gambar kiri (πl) dan kanan (πr), sedangkan Pl dan Pr adalah vektor proyeksi titik P tersebut. Epipole adalah proyeksi pusat kamera pada bidang gambar yang lain. el, proyeksi pusat kamera kanan (Or) pada pada bidang gambar kiri dan er, proyeksi puat kamera kiri (Ol) pada bidang gambar kanan. Dan yang dimaksudkan dengan epipolar line adalah perpotongan antara epipolar plane dengan bidang gambar kiri dan kanan.
Dari geometri inilah bisa dibuktikan adanya epipolar constraint, jika diketahui pl maka pasangan pixel-nya pr pasti berada pada epipolar line dari epipolar plane yang sama (conjugate epipolar lines), begitu pula sebaliknya.
20
2.5.4 Rektifikasi Suatu proses untuk menentukan transformasi setiap gambar agar pasangan dari epipolar line menjadi segaris dan paralel dengan salah satu sumbu gambar, biasanya sumbu horizontal.
Gambar 2.17 Rektifikasi. Hitam sebelum rektifikasi, abu sesudah rektifikasi (Sumber: E.Trucco, A.Verri, 1998)
Setelah melakukan rektifikasi maka disparity antar pasangan pixel hanya akan berada pada sumbu horizontal saja. Proses rektifikasi terdiri dari beberapa langkah, yaitu: •
Putar kamera kanan dengan matriks rotasi R (extrinsic parameter) agar orientasi kedua kamera sama.
•
Putar kamera kiri dan kanan agar vektor translasi paralel dengan sumbu horizontal (1;0;0).
•
Aplikasikan frame yang baru diperoleh ini pada sekumpulan pasangan point/gambar input untuk mendapatkan gambar yang terektifikasi
Proses ini dapat dilakukan dengan asumsi bahwa: •
Pusat dari image reference frame adalah principal point
•
Focal length sama dengan f
21
2.5.5 Rekonstruksi 3D Proses rekonstruksi point 3D menggunakan informasi yang diperoleh dari gambar 2D. Informasi jarak (depth) dapat diperoleh melalui nilai disparity, sedangkan informasi posisi X dan Y dapat diperoleh melalui proses proyeksi balik dari gambar 2D menjadi kerangka acuan kamera/dunia.
2.6 DBSCAN Singkatan dari density-based spatial clustering of applications with noise adalah sebuah algoritma untuk mengelompokkan data, agar data yang berada dalam suatu kelompok (kluster) memiliki kesamaan dengan data lain yang berada dalam kelompok yang sama dibandingkan dengan data lain yang berada dalam kelompok yang berbeda.
Gambar 2.18 Clustering (Sumber: http://en.wikipedia.org/wiki/Cluster_analysis)
Algortima ini diusulkan oleh Martin Ester, Hans-Peter Kriegel, Jörg Sander and Xiaowei Xu pada tahun 1996. DBSCAN adalah algoritma pengelompokkan (clustering) berdasarkan pada kepadatan (density), kluster adalah kumpulan data yang lebih padat dibandingkan dengan kumpulan data yang lain, sedangkan kepadatan itu sendiri adalah jumlah data dalam radius (eps) tertentu.
22
Gambar 2.19 DBSCAN (Sumber: http://en.wikipedia.org/wiki/DBSCAN)
Konsep: •
Ada dua parameter yang diperlukan yaitu eps, suatu nilai input jarak dan minPts, jumlah data minimum untuk memulai sebuah kluster
•
Sebuah data dikategorikan sebagai inti, jika disekitarnya terdapat data lain dengan jumlah lebih besar sama dengan minPts dalam radius eps.
•
Sebuah data dikategorikan sebagai tepi, jika disekitarnya terdapat data lain dengan jumlah lebih kecil dari minPts dalam radius eps tapi masih berada dalam radius inti.
•
Sebuah data dikategorikan sebagai noise, jika tidak termasuk dalam kategori inti maupun tepi.
Gambar 2.20 Inti, Tepi dan Noise (Sumber: home.etf.rs/~vm/os/dmsw/3323_11_Milan_Micic_DBSCAN.ppt)
23
Pseudocode:
Gambar 2.21 DBSCAN Pseudocode (Sumber: http://en.wikipedia.org/wiki/DBSCAN)
Keunggulan: •
Tidak memerlukan informasi awal (input) mengenai jumlah kluster yang ada dalam sebuah kelompok data.
•
Dapat menemukan kluster dengan berbagai bentuk, bahkan menemukan kluster yang berada didalam kluster yang lain.
•
Menyadari keberadaan noise.
Kelemahan: •
Performanya bergantung pada fungsi yang digunakan untuk mengukur jarak antar data.
•
Tidak dapat mengelompokkan data dengan baik, jika kepadatan dari setiap kluster yang ada berbeda jauh.
24
2.7 Delaunay Triangulation Salah satu cara untuk menghubungkan sekumpulan titik agar membentuk sebuah mesh segitiga. Mesh yang terbentuk memenuhi suatu kriteria yaitu tidak ada satu titik pun yang berada didalam circumcircle (lingkaran yang melewati ketiga titik sudut segitiga) dari semua segitiga yang terbentuk.
Gambar 2.22 Delaunay Triangulation dengan Circumcircle (Sumber: http://en.wikipedia.org/wiki/Delaunay_triangulation)
Delaunay triangulation memaksimalkan nilai minimum dari semua sudut segitiga yang terbentuk atau dengan kata lain menghindari terbentuknya segitiga yang kurus (skinny). Delaunay triangulation biasanya diaplikasikan pada suatu kondisi untuk mengaproksimasikan ketinggian sebuah titik yang berada diantara titik-titik yang diketahui ketinggiannya.
Gambar 2.23 Contoh Delaunay Triangulation (Eguchi, 2001)
2.8 Piecewise Linear Function Sebuah fungsi yang terdiri dari dua atau lebih garis lurus, dimana setiap garis didefinisikan pada sebuah interval tertentu, biasanya dalam interval yang sama.
25
Gambar 2.24 Piecewise Linear Function (Sumber: http://en.wikipedia.org/wiki/Piecewise_linear_function)
Gambar 2.24 menunjukkan aproksimasi menggunakan piecewise linear function (merah) terhadap suatu kurva (biru) yang sudah diketahui fungsinya. Semakin kecil interval yang digunakan maka semakin akurat aproksimasi yang dihasilkan (sampai batas tertentu).
2.9 Least Square Least square adalah suatu metode standar untuk mengaproksimasi solusi dari sebuah overdetermined system, yaitu suatu sistem dimana jumlah persamaan yang diketahui lebih banyak dibandingkan dengan jumlah variabel yang tidak diketahui. Solusi least square adalah solusi yang meminimalisasi total error2 yang diperoleh dari setiap persamaan.
Least square juga dapat diartikan sebagai suatu prosedur matematika untuk menemukan kurva yang paling sesuai dalam menggambarkan sekumpulan titik yang dikethui (input) dengan meminimalisasi total dari offset2 (offset: jarak antara titik dengan kurva)
26
Gambar 2.25 Least Square (a) vertikal offset; (b), (c) kurva yang diperoleh menggunakan metode least square beserta sekumpulan titik input (Sumber: http://mathworld.wolfram.com/LeastSquaresFitting.html)
2.10 Anaglyph Suatu metode untuk menampilkan dua buah gambar dari suatu lingkungan (scene) yang sama dengan perspektif yang sedikit berbeda dalam satu buah gambar. Perbedaan gambar kiri dan kanan ditampilkan dengan dua warna yang kontras satu dan lainnya. Gambar kiri ditampilkan dengan warna merah dan gambar kanan ditampilkan dengan warna cyan (hijau+biru).
Gambar 2.26 Anaglyph Image (Sumber: http://www.cse.psu.edu/~rcollins/CSE486/)
27
Gambar 2.27 Kacamata Red-Cyan (Sumber: http://www.cse.psu.edu/~rcollins/CSE486/)
Jika melihat gambar anaglyph dengan sebuah kacamata khusus seperti yang terlihat pada gambar 2.27 maka objek pada gambar akan terlihat dalam 3D. Kacamata ini berfungsi sebagai filter, pada mata kiri terdapat filter warna merah yang mengakibatkan hanya warna merah yang akan terlihat mata kiri, begitu pula untuk mata kanan terdapat filter cyan yang mengakibatkan hanya warna cyan yang terlihat oleh mata kanan. Hal ini mengakibatkan mata kiri hanya melihat gambar kiri dan mata kanan hanya melihat gambar kanan, kedua informasi gambar ini akan diproses oleh otak dan menghasilkan sebuah tampilan berbentuk 3D.
