BAB II LANDASAN TEORI
2.1
Pengenalan Marka Jalan Marka jalan merupakan suatu penanda bagi para pengguna jalan untuk membantu kelancaran jalan dan menghindari adanya kecelakaan. Pada umumnya marka jalan berfungsi untuk memisahkan antara lajur satu dengan yang lainnya, atau memisahkan lajur yang berlawanan. Berdasarkan Djoko Asmoro (1990:1), marka jalan memiliki jenisjenis garis yang berbeda dengan fungsi yang berbeda-beda pula. Sebagai contoh adalah garis terputus
yang berfungsi sebagai garis sumbu dan
pemisah pada jalan 2 jalur, 2 arah dengan lebar > 5,50 m dan pada jalan lebih dari 2 jalur.
Gambar 2.1
Jalan 2 Jalur, 2 Arah Dengan Lebar > 5,50 m
Gambar 2.2
Jalan Lebih Dari 2 Jalur
Contoh lainnya yaitu garis penuh yang berfungsi sebagai garis dilarang pindah jalur dari salah satu sisi seperti gambar (2.3) dibawah ini : 5
6
Gambar 2.3
2.2
Garis Dilarang Pindah Jalur
Edge Detection Pada
skripsi
ini
dibutuhkan
edge
detection
karena
untuk
mengimplementasikan algoritma Hough Transfrom, pertama-tama citra yang akan diproses harus diubah kedalam bentuk grayscale dulu kemudian baru dicari edge-edge yang ada pada citra tersebut dan hasil edge-edge yang ditemukan tersebut akan diproses dengan mengunakan Hough Transform. Edge detection adalah suatu metode untuk mendeteksi edge dari objek-objek pada citra, yang dimana edge itu adalah batas antara dua daerah dengan nilai gray-level yang relatif berbeda atau dengan kata lain edge merupakan tempat-tempat yang memiliki perubahan intensitas yang besar dalam jarak yang pendek. Tujuan dari edge Detection ini adalah : 1. Untuk menandai bagian yang menjadi detail dari citra 2. Untuk memperbaiki detail dari citra yang kabur, yang terjadi karena error atau adanya efek dari cahaya.
7
Ada beberapa metode untuk Edge Detection yaitu : 1. Metode Laplacian Salah satu metode Edge Detection yang mendeteksi edge yang sangat berbeda dengan metode lainnya, karena metode ini berbentuk omny directional (tidak horizontal dan tidak vertikal). Metode ini menemukan edge dari semua arah dan menghasilkan edge yang lebih tajam dari metode lainnya. Cara kerja dari metode laplacian ini untuk menemukan edge adalah dengan mencari zero-crossings setelah melakukan filter citra dengan mengunakan Gaussian filter. Pada metode ini hanya akan mendeteksi edge yang kuat dari threshold yang telah ditentukan, apabila tidak ditentukan threshold nya maka dari matlabnya akan memilih nilainya secara default. 2. Metode Robert Salah satu metode edge detection yang mendeteksi edge dengan cara mencari perbedaan pada arah horizontal dan vertical. Untuk mendapatkan edge yang lebih baik, maka perlu melakukan konversi biner dengan meratakan distribusi warna hitam dan putih. Dengan kata lain metode ini lebih baik digunakan pada citra yang hanya berwarna hitam putih. Cara kerja dari metode Roberts ini untuk menemukan edge adalah dengan menggunakan pendekatan Roberts pada derivative nya. Dan hasilnya akan mengembalikan nilai edge pada titik-titik tersebut yang dimana gradient dari citra adalah maksimum. Kelebihan dari metode ini adalah bisa
8
menentukan thinning atau nothinning, thinning fungsinya untuk menghilangkan titik yang tidak ingin dideteksi sebagai edge pada citra, namun fungsi ini juga akan menambah computional cost yang dibutuhkan dalam pemrosesan. Pada metode ini hanya akan mendeteksi edge yang kuat dari threshold yang telah ditentukan, apabila tidak ditentukan threshold nya maka dari matlabnya akan memilih nilainya secara default. 3. Metode Prewitt Salah satu metode Edge Detection yang mendeteksi edge yang merupakan pengembangan dari metode Robert dengan mengunakan High Pass Filter (HPF) yang diberi satu angka nol penyangga. Metode ini mengambil prinsip dari fungsi laplacian sehingga edge yang dihasilkan lebih banyak dari metode Robert. Cara kerja dari metode prewitt untuk mendeteksi edge sama seperti pada Robert, bedanya hanya disini menggunakan pendekatan prewitt. Pada metode ini memiliki kelebihan yaitu bisa ditentukan arah pendeteksiannya yaitu horizontal, vertical, atau kedua-duanya. Pada metode ini hanya akan mendeteksi edge yang kuat dari threshold yang telah ditentukan, apabila tidak ditentukan threshold nya maka dari matlabnya akan memilih nilainya secara default. 4. Metode Sobel Salah satu metode Edge Detection yang mendeteksi edge yang juga merupakan pengembangan dari metode Robert. Kelebihannya adalah metode ini mampu mengurangi noise sebelum melakukan perhitungan
9
edge detection sehingga edge yang dihasilkan lebih banyak dibanding metode Robert maupun Prewitt. Cara kerja dari metode prewitt untuk mendeteksi edge sama seperti pada Robert dan prewitt, bedanya hanya disini menggunakan pendekatan sobel. Metode ini merupakan pengabungan dari Robert dan prewitt yang dimana bisa dilakukan thinning atau nothinning dan juga menentukan arah pendeteksiannya. Pada metode ini hanya akan mendeteksi edge yang kuat dari threshold yang telah ditentukan, apabila tidak ditentukan threshold nya maka dari matlabnya akan memilih nilainya secara default. 5. Metode Canny Metode Canny ini merupakan metode Edge Detection yang digunakan pada penelitian ini , sehingga kita akan membahas secara lebih detail tentang metode ini. Metode ini pertama kali dikembangkan oleh John F. Canny (1986:1) menggunakan algoritma multi-tahap untuk mendeteksi
berbagai edge
dalam citra. Menurut Lijun Ding (2000:2) Implementasi dari Canny Edge Detection, memiliki beberapa tahap yaitu : 1. Dengan menggunakan Gaussian Filter melakukan Smooth pada citra
untuk mengurangi detail dari citra. 2. Menentukan ukuran gradient dan arah gradient pada tiap pixel. 3. Apabila ukuran gradient pada suatu pixel lebih besar dari pixel-pixel
yang ada pada arah gradient disekitarnya maka dianggap pixel tersebut sebagai suatu edge.
10 4. Menghilangkan edge yang lemah dengan mengunakan thresholding.
Metode ini mengunakan 2 threshold, masing-masing untuk mendeteksi edge yang kuat dan edge yang lemah, dan edge yang lemah hanya bisa dideteksi apabila edge tersebut terhubung
dengan edge yang kuat.
Sehingga metode ini lebih berkemungkinan untuk mendeteksi edge yang lemah dan bisa menbedakan mana yang noise dan mana yang sebenarnya edge yang lemah.
Beberapa kelebihan dari Canny Edge Detection ini adalah: 1.
Mendeteksi dengan baik Kemampuan untuk menandai semua edge yang ada dengan baik dan juga memberikan fleksibilitas yang sangat tinggi
dalam hal
menentukan tingkat deteksi ketebalan edge sesuai yang diinginkan. 2.
Melokalisasi dengan baik Dengan canny memungkinkan menghasilkan jarak yang
minimum
antara edge yang dideteksi dengan edge yang asli. 3.
Respon yang jelas Hanya ada 1 respon untuk setiap edge, sehingga mudah terdeteksi dan tidak menimbulkan kerancuan pada pengolahan citra selanjutnya.
11
2.3
Hough Transform Pada dasarnya Hough Transform (HT) merupakan suatu teknik untuk menentukan lokasi suatu bentuk dalam citra. HT dicetuskan pertama kali oleh P.V.C. Hough (1962:2) , pertama kali dilihat berpotensi sebagai salah satu algoritma dalam pemrosesan citra oleh Rosenfeld (1969:2), kemudian diimplementasikan untuk mendeteksi garis dalam citra oleh Duda (1971:4), dan sejak itu mengalami perkembangan yang sangat luas karena banyaknya keunggulan dan besarnya potensi untuk pengembangan lebih lanjut yang ditawarkan oleh algoritma ini. Dalam implementasinya, HT melakukan pemetaan terhadap titik-titik pada citra ke dalam parameter space (hough space) berdasarkan suatu fungsi yang mendefinisikan bentuk yang ingin dideteksi. HT umumnya digunakan untuk melakukan ekstraksi garis, lingkaran atau elips pada citra, namun dalam perkembangannya, HT juga telah dapat digunakan untuk melakukan ekstraksi bentuk-bentuk yang lebih kompleks. Secara khususnya Hough Transform yang digunakan disini hanyalah untuk mendeteksi garis pada marka jalan saja yang dimana pada awalnya garis jalan ini koordinatnya dalam bentuk kartesian space (x-y) yang kemudian dirubah menjadi kurva sinusoidal pada hough space (rho & theta) menggunakan Hough Transform.
12
Gambar 2.4
Kartesian Space
(2.1) Ket: = rho koordinat y dalam bentuk hough space = theta koordinat x dalam bentuk hough space Persamaan (2.1) diatas didapatkan dari gambar (2.4) yang dimana untuk mencari nilai
harus menggunakan koordinat x dan y yang telah ditemukan
edge dan dikalikan dengan nilai
yang telah ditemukan juga. Sehingga
mendapatkan garis yang diinginkan.
Gambar 2.5
Hough Space
13
gambar diatas menjelaskan kerja dari hough transform dalam melakukan scanning pada semua kemungkinan
yang ada dan pada pixel yang paling
banyak garis sinusoidal yang melewati pixel tersebut merupakan garis yang ditemukan.
Kelebihan dan kekurangan dari Hough Transform: Kelebihan: 1. HT dapat mendeteksi keberadaan objek yang memiliki pola tertentu walaupun tidak diketahui ukuran maupun posisinya. 2. HT relatif tidak terpengaruh oleh noise atau data hilang pada citra. 3. Mampu mendeteksi garis pada bentuk geometri dengan kumpulan edge yang terputus-putus Kekurangan: 1. Kompleksitas dan ukuran accumulator array meningkat sebanding dengan bertambahnya jumlah parameter yang merepresentasikan objek yang ingin dideteksi. 2. Biaya komputasi dan kapasitas memori yang besar. 3. Hasil deteksi sensitif terhadap pemilihan nilai threshold yang sudah ditentukan, semakin kecil nilai threshold maka akan semakin banyak garis yang terdeteksi.
14
2.4
Multiresolution Hough Transform Multiresolution
Hough
Transform
sebenarnya
merupakan
pengembangan dari Hough Transform, dan Multiresolution Hough Transform ini juga banyak jenisnya tergantung dikembangkan pada bagian mananya. Pada Multiresolution Hough Transform yang digunakan disini yaitu dengan mengaplikasikan Hough Transform beberapa kali dari resolusi yang rendah sampai ke resolusi citra yang diinginkan (B.Yu and A.K. Jain, 1996:9). Maksudnya adalah pertama digunakan koordinat x dan y dengan interval resolusi citra yang rendah. 5 10 15 20 25
X
Y
Gambar 2.6
Contoh Kartesian Space Resolusi Rendah 10 20 30 40 50 X
Y
Gambar 2.7
Contoh Kartesian Space Resolusi Tinggi
Gambar (2.6) diatas merupakan resolusi citra yang masih rendah yaitu mencari setiap koordinat y terhadap koordinat x dengan interval 10 pixel. Kemudian pada gambar (2.7) melakukan proses HT yang kedua kalinya pada saat x=10 ditemukan garis. Dengan menggunakan fungsi yang sama hanya resolusi diganti menjadi resolusi yang lebih tinggi yang sudah dilokalisasi
15
dengan interval ±10, 10 disini didapatkan dari interval yang digunakan pada resolusi rendah.
0O 10O 20O Gambar 2.8 Hough Space Resolusi Rendah
0O
10O
Gambar 2.9
20O
Hough Space Resolusi Tinggi
Sebenarnya gambar (2.8) sama dengan gambar (2.6) diatas hanya satu ditampilkan pada kartesian space dan satu lagi ditampilkan pada hough space. Demikian juga pada gambar (2.9) sama dengan gambar (2.7) diatas melakukan proses HT yang kedua kalinya pada saat x=10 ditemukan garis. Perbedaannya hanya gambar (2.9) menampilkan dalam bentuk hough space. Kemudian setelah semua garis yang telah ditemukan akan disimpan pada suatu index yang nantinya akan digunakan pada pendeteksian line segment. Kelebihan dari Multiresolution Hough Transform dibandingkan dengan Hough Transform biasa adalah pada MHT ini computational cost yang diperlukan untuk menyelesaikan pendeteksian garis jauh lebih cepat
16
dibandingkan dengan HT. Ini dikarenakan pada HT harus dicari semua kemungkinan garis yang ada. Sedangkan pada MHT, pada awalnya mengunakan
resolusi
citra
yang
rendah
terlebih
dahulu
sehingga
computational cost yang dibutuhkan menjadi berkurang.
2.5
Model Kamera Pinhole Menurut Yoanes Naftalianto and Dr. Widyawardana Adiprawita (2012:1) Model kamera pinhole mendefinisikan hubungan geometris antara titik 3D dan proyeksi 2D yang sesuai ke bidang citra. Dalam model kamera pinhole ini, cahaya dari obyek masuk ke dalam kamera melalui pinhole dan terproyeksikan ke bidang citra. Sebagai hasil, citra pada bidang ini selalu dalam keadaan fokus dan ukuran citra relatif terhadap
ukuran obyek
sebenarnya ditentukan oleh satu parameter kamera, yaitu jarak fokus ( f ).
(2.2)
Pn
=
K
G
Pada persamaan diatas, Matriks Pn merupakan representasi dari bidang citra pada posisi pixel (U, V). Sedangkan Matriks G merupakan representasi dari gambar 3 dimensi. Matriks K adalah parameter intrinsik dari kamera pinhole.
17
(X, Y, Z)T
Optical Axis
(U, V)T
Titik Prinsipal Optical Center Y
Z X
f
Bidang Citra
Gambar 2.10 Hubungan Antara 2D Dan 3D Pada kamera terdapat sebuah titik prinsipal. Titik prinsipal merupakan titik yang memotong bidang citra pada sumbu optik. Dalam kamera ideal, titik prinsipal berada tepat di tengah bidang kamera. Umumnya asal dari koordinat pixel berada pada pojok kiri atas pada gambar. Namun, sebelumnya telah diasumsikan bahwa asal dari koordinat pixel terletak di tengah gambar, yaitu pada Titik Prinsipal. Titik prinsipal dinyatakan dalam dua besaran, yaitu ox dan oy dimana ox merupakan dalam sumbu x dan oy dalam sumbu y.
(2.3)
Pn
=
K
G
Kemudian dari persamaan diatas akan dicari titik koordinat dari image plane pada posisi pixel (U, V), dengan mengalikan matriks K dengan matriks G. Dengan hasil sebagai berikut.
18
(2.4) (2.5) (2.6) (2.7) (2.8)
2.6
Inverse Perspective Mapping Untuk menghitung jarak antara 2 garis dibutuhkan koordinat dalam bentuk 3 dimensi. Ada beberapa metode yang dapat digunakan untuk merubah proyeksi citra dari 2 dimensi menjadi 3 dimensi. Salah satu metodenya adalah Inverse Perspective Mapping.
(2.9)
Pn Pada
Inverse
=
Perspective
K
G
Mapping,
matriks
intrinsik
yang
merepresentasikan citra dalam 2 dimensi (U, V), mempunyai peranan penting dalam memproyeksikan citra menjadi 3 dimensi (X, Y & Z). Pada awalnya Matriks K akan berpindah ruas, sehingga kini persamaan akan berubah fungsi menjadi untuk merubah bidang citra menjadi bidang jalan, seperti yang tertera pada persamaan di bawah ini.
(2.10)
G
=
K-1
Pn
19
Kemudian akan dicari masing- masing dari nilai X, Y & Z dengan cara mengalikan Matriks K (yang sudah di inverse) dengan Matriks Pn. Akan di dapat hasil seperti di bawah ini. (2.11)
(2.12) (2.13)
Pada penelitian ini, kami hanya ingin mencari Koordinat X & Z. Koordinat Y di tentukan berdasarkan tinggi kamera konstan terhadap permukaan tanah. Sehingga
di masukkan kedalam persamaan X & Y
diatas. Yang akan menghasilkan persamaan untuk Inverse Perspective Mapping untuk koordinat X & Z pada bidang jalan. (2.14) (2.15)
2.7
Point to Line Segment Pada penelitian ini, penghitungan jarak digunakan untuk mengetahui jarak antara 2 garis paralel serta sebagai metode untuk estimasi posisi. Metode yang kami gunakan pada penelitian ini adalah Point to Line Segment. Point to a line segment adalah suatu metode untuk menghitung jarak terpendek suatu titik ke suatu garis. Untuk mendapatkan jarak terpendek tersebut caranya cukup sederhana yaitu menghitung proyeksi vektor (V1P) ke
20
vektor garis (V1V2) sehingga didapat titik baru (PL) yang berada pada garis. Vektor (PLP) tegak lurus garis sehingga untuk menghitung jarak titik P dari garis, cukup menghitung panjang vektor (PLP) PLP Ket : = titik awal = titik akhir PLP = point
(2.16)
