BAB II LANDASAN TEORI
Pada bab ini, dibahas mengenai teori-teori yang digunakan. Berdasarkan langkah Martin
Hirzer dalam pendeteksian marker, ada empat langkah utama. Berdasarkan metoda tersebut teori yang dibahasa meliputi Marker, Citra Digital, Teori Dasar Pengolahan Citra, Segmentasi Citra dan metoda Martin Hirzer sendiri. Teori tersebut tidak selalu harus penulis gunakan,
teori ini digunakan pada keadaan dimana bingkai marker tertutupi sebagian. Jika tidak ada
gangguan pada marker maka deteksi dilakukan tanpa menggunakan cara Hirzer tersebut,
cukup dengan pendeteksian default dari ARToolKit.
2.1 ARToolKit ARToolkit adalah software library untuk membangun aplikasi berbasis Augmented Reality (AR). ARToolkit merupakan integrasi antara library yang terdiri dari ARToolkit dan OpenGL, Microsoft Visual Studio C++ sebagai IDE, dan Compiler C. ARToolKit adalah software library yang akan digunakan pada pengerjaan tugas akhir ini. Struktur data yang digunakan pada modul baru yang akan dibuat disesuaikan dengan tools yang dipakai yaitu ARToolKit, agar tidak ada masalah pada saat modul baru yang dibuat disisipkan di library ARToolKit. Berikut alur kerja ARToolKit.
Gambar 2 Flow kerja ARToolKit dalam mendeteksi marker
Terdapat 5 proses utama pada ARToolKit yaitu Pendeteksian posisi marker, Menentukan posisi dan orientasi marker terhadap kamera, mencocokan id marker, menentukan posisi dan 7
BAB II Landasan Teori
8
orientasi objek 3D dan Menampilkan objek 3D pada layar. Untuk mengimplementasi metoda
yang akan digunakan hanya akan mengubah pada proses nomor 1 yaitu Pendeteksian Posisi Marker dengan input berupa video frame (image) dan output berupa info marker (posisi
marker) yang ditemukan.
2.2 Marker
Dalam bukunya, Fiala telah meninjau secara luas tentang marker (M.Fiala, 2005). Banyak
sekali sistem yang berbasis vision yang menggunakan pola 2-dimensi untuk menyimpan
informasi didalamya. Ada banyak bidang aplikasi dibidang industri yang merancang marker sebagai alat untuk membawa informasi contohnya untuk pengiriman data dimana marker
dipakai untuk lokalisasi, Augmented Reality, dan juga navigasi untuk robot. Untuk mengurangi sensitifitas dari kondisi cahaya dan pengaturan kamera planar marker system biasanya menggunakan bitonal marker yaitu marker yang hanya terdiri dari 2 warna, biasanya berwarna hitam dan putih. Jadi tidak perlu mengidentifikasi warna yang kurang jelas dan juga mempermudah pada proses penentuan keputusan warna per pixel pada saat threshold (Hirzer, 2008). Desain marker yang digunakan biasanya bergantung pada dimana akan mengaplikasikannya. Pada Gambar 3
menunjukan beberapa contoh marker dan dimana
marker tersebut diaplikasikan.
Gambar 3 Desain-desain marker diambil dari (M.Fiala, 2005)
Menurut Martin Hirzer marker di Augmented Reality hanya terdeteksi jika marker terlihat secara utuh, beruntung karena pada Augmented reality sendiri informasi yang dibawa oleh Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
BAB II Landasan Teori
9
marker tidak terlalu banyak, dengan keadaan seperti ini data dari marker yang rusak karena
tidak terbaca akibat tertutupi atau kondisi cahaya di Augmented Reality mudah untuk diperbaiki tanpa merubah banyak informasi di dalam marker (Hirzer, 2008). Marker di
Augmented Reality biasa disebut fiducial marker, marker ini umumnya berwarna hitam-putih, memiliki garis tebal yang membentuk segi empat atau disebut juga quadrilateral outline, 4
titik sudut yang berguna untuk perhitungan posisi tiga dimensi, dan suatu pola ditengah yang berfungsi sebagai id.
2.2.1 Bagian-Bagian Marker
Dalam marker Augmented Reality terdapat tiga bagian penting yang harus ada pada sebuah
marker, yaitu :
1.
Quadrilateral Outline Quadrilateral outline adalah bagian dari marker yang berfungsi sebagai tanda bahwa area di bagian dalam quadrilateral outline adalah marker selain itu quadrilateral outline adalah informasi posisi dimana marker berada karena quadrilateral outline ini menyimpan informasi letak-letak titik sudut.
Gambar 4 Quadrilateral Outline dilihat dari 4 sudut pandang berbeda
2. Titik Sudut Titik sudut ini berfungsi untuk Menentukan posisi 3D dari objek yang akan ditampilkan. Dalam teorinya Martin Hirzer menentukan titik sudut ini dari perpotongan segmentsegment garis yang diperpanjang.
Gambar 5 Titik sudut di quadrilateral outline
3. ID Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
BAB II Landasan Teori
10
Id pada Augmented Reality merupakan sebuah pola unik yang biasanya terletak dibagian
tengah marker. id ini berfungsi untuk pembeda antara satu marker dengan marker yang
lainnya, berbeda id biasanya objek yang ditampilkan juga akan berbeda. Pola pada Id tidak boleh simetris, baik secara vertikal, horizontal, maupun diagonal. Pola id yang seperti ini sebenarnya tidak akan mempengaruhi keberhasilan program dalam
menampilkan objek 3D, hanya saja objek yang di-load akan me-reset posisinya terus menerus karena kesalahan program dalam mengidentifikasi marker saat diputar atau dimiringkan pada sudut tertentu terhadap webcam. dibuat sesederhana mungkin agar proses identifikasi lebih cepat, namun meski Id juga
sederhana harus tetap bersifat unik. Poin ini harus diperhatikan terutama jika hardware
untuk mendeteksi marker yang digunakan memiliki resolusi yang tidak terlalu besar hanya sepenulisr 1,3 megapixel (Tantiohadi, et al., 2011). Ukuran optimal dari sebuah marker berkisar antara 7-15cm2 dengan kamera minimal 1,3 mega pixel (Tantiohadi, et al., 2011). Marker juga harus dicetak di kertas yang tidak memantulkan cahaya dan mengkilat agar tidak mengganggu kamera dalam penangkapan gambar marker yang di akibatkan pantulan cahaya yang berlebihan. 2.2.1.1 Quadrilateral Quadrilateral atau tetragon adalah polygon yang memiliki empat sisi dan juga empat simpul atau sudut yang dibentuk dari ujung-ujung sisi yang saling berhubungan. Quadrilateral yang digunakan sebagai marker di Augmented Reality adalah jenis quadrilateral Convex. menjelaskan tentang berbagai macam bentuk Quadrilateral yang penulis ketahui, bentukbentuk pada gambar tersebut bermacam-macam dan memiliki karakteristik yang berbeda tetapi tetap memiliki empat titik sudut.
Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
BAB II Landasan Teori
11
Gambar 6 Jenis-jenis quadrilateral
Quadrilateral convex memiliki segmen garis khusus 1. Kedua diagonal dari quadrilateral convex adalah segment garis yang menghubungkan simpul yang berlawanan
Gambar 7 Bimedian dari quadrilateral convex
Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
BAB II Landasan Teori
12
2. Kedua Bimedian dari quadrilateral convex adalah segmen garis yang menghubungkan titik tengah dari sisi yang berlawanan. Mereka berpotongan di titik pusat massa pada quadrilateral convex (Weisstein, 1999-2012).
Gambar 8 Maltitude (titik tengah ketinggian) dari quadrilateral convex
3. Keempat Maltitudes dari segiempat cembung adalah garis tegak ke sisi melalui titik tengah sisi yang berlawanan (Weisstein, 1999-2012). Dengan mengetahui tentang quadrilateral convex dapat membantu penulis dalam pendeteksian marker di Augmented Reality.
2.3 Citra Digital Citra digital adalah gambar 2D yang dapat ditampilkan pada layar monitor komputer sebagai himpunan berhingga (diskrit) nilai digital yang disebut pixel (picture elements). Berdasarkan cara penyimpanan atau pembentukannya, citra digital dapat dibagi menjadi dua jenis. Jenis pertama adalah citra digital yang dibentuk oleh kumpulan pixel dalam array 2D. Citra jenis ini disebut citra bitmap (bitmapimage) atau citra raster (rasterimage). Jenis citra yang kedua adalah citra yang dibentuk oleh fungsifungsi geometri dan matematika. Jenis citra ini disebut grafik vektor (vector graphics). Dalam pembahasan tugas akhir ini, yang dimaksud citra digital adalah citra bitmap. Citra digital (diskrit) dihasilkan dari citra analog (kontinu) melalui digitalisasi. Digitalisasi citra analog terdiri atas penerokan (sampling) dan kuantisasi (quantization). Penerokan adalah pembagian citra ke dalam elemen-elemen diskrit (pixel), sedangkan kuantisasi adalah
Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
BAB II Landasan Teori
13
pemberian nilai intensitas warna pada setiap pixel dengan nilai yang berupa bilangan bulat
(G.W. Awcock, 1996).
Citra dapat dinyatakan dalam titik-titik koordinat pada kawasan ruang (spasial) atau bidang
dan untuk menentukan warna atau menyatakan nilai keabuan suatu citra. Salah satu contoh digital adalah citra monokrom atau citra hitam putih yang merupakan citra satu bentuk citra kanal, dimana citra
f ( x, y) merupakan fungsi tingkat keabuan dari hitam ke putih; x
menyatakan variabel baris dan y menyatakan variabel kolom. Gambar x menunjukkan bentuk
citra monokrom dan bentuk matriks penyusunnya.
Gambar 9 Contoh bentuk citra monokrom dan bentuk matriks penyusunnya
2.3.1 Piksel Agar citra dapat diolah oleh sebuah komputer digital, maka sebuah citra harus disimpan pada format yang dapat diolah oleh sebuah program komputer. Cara yang paling praktis yang dapat dilakukan adalah dengan membagai citra menjadi sekumpulan sel-sel diskret, yang disebut piksel. Pada umumnya sebuah citra dibagi menjadi kisi-kisi persegi, sehingga piksel sendiri adalah sebuah kisi-kisi persegi yang kecil. Selanjutnya setiap piksel diberi nilai yang menyatakan warna atau menyatakan tingkat kecerahan piksel yang bersangkutan, yang sering disebut dengan intensitas piksel.
2.3.2 Jenis Citra Berdasarkan warna-warna penyusunnya, citra digital dapat dibagi menjadi tiga macam (Marvin Chandra Wijaya,2007) yaitu: 1. Citra berwarna Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
BAB II Landasan Teori
14
2. Citra grayscale
3. Citra biner
2.3.2.1 Citra Berwarna
Citra berwarna, yaitu citra yang nilai pixel-nya merepresentasikan warna tertentu. Banyaknya
warna yang mungkin digunakan bergantung kepada kedalaman pixel citra yang bersangkutan. Citra berwarna direpresentasikan dalam beberapa kanal (channel) yang menyatakan komponen-komponen warna penyusunnya. Banyaknya kanal yang digunakan bergantung
pada model warna yang digunakan pada citra tersebut.
Gambar 10 Citra berwarna
Intensitas suatu pada titik pada citra berwarna merupakan kombinasi dari tiga intensitas : derajat keabuan merah (fmerah(x,y)), hijau fhijau(x,y) dan biru (fbiru(x,y)). Persepsi visual citra berwarna umumnya lebih kaya dibandingkan dengan citra hitam putih. Citra berwarna menampilkan objek seperti warna aslinya (meskipun tidak selalu tepat demikian). Warnawarna yang diterima oleh mata manusia merupakan hasil kombinasi cahaya dengan panjang gelombang berbeda. Untuk mengubah citra berwarna yang mempunyai nilai matrik masing-masing r,g, dan b menjadi citra grayscale dengan nilai s, maka konversi dapat dilakukan dengan mengambil rata-rata dari nilai r,g dan b sehingga dapat dituliskan menjadi : Rumus 1 Mencari citra grayscale dari nilai citra rgb
Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
BAB II Landasan Teori
15
2.3.2.2 Citra Grayscale Citra grayscale, yaitu citra yang nilai pixel-nya merepresentasikan derajat keabuan atau
intensitas warna putih. Nilai intensitas paling rendah merepresentasikan warna hitam dan nilai intensitas paling tinggi merepresentasikan warna putih. Pada umumnya citra grayscale memiliki kedalaman pixel 8 bit (256 derajat keabuan), tetapi ada juga citra grayscale yang pixel-nya bukan 8 bit, misalnya 16 bit untuk penggunaan yang memerlukan kedalaman
ketelitian tinggi.
Gambar 11 Citra grayscale (abu-abu)
Citra grayscale merupakan citra satu kanal, dimana citra f(x,y) merupakan fungsi tingkat keabuan dari hitam keputih, x menyatakan variable kolom atau posisi pixel di garis jelajah dan y menyatakan variable kolom atau posisi pixel di garis jelajah. Intensitas f dari gambar hitam putih pada titik (x,y) disebut derajat keabuan (grey level), yang dalam hal ini derajat keabuannya bergerak dari hitam keputih. Derajat keabuan memiliki rentang nilai dari Imin sampai Imax, atau Imin < f < Imax, selang (Imin, Imax) disebut skala keabuan. Biasanya selang (Imin, Imax) sering digeser untuk alasan-alasan praktis menjadi selang [0,L], yang dalam hal ini nilai intensitas 0 meyatakan hitam, nilai intensitas L meyatakan putih, sedangkan nilai intensitas antara 0 sampai L bergeser dari hitam ke putih. Sebagai contoh citra grayscale dengan 256 level artinya mempunyai skala abu dari 0 sampai 255 atau [0,255], yang
Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
BAB II Landasan Teori
16
dalam hal ini intensitas 0 menyatakan hitam, intensitas 255 menyatakan putih, dan nilai antara
0 sampai 255 menyatakan warna keabuan yang terletak antara hitam dan putih.
Untuk mengubah citra grayscale ke citra biner bisa dilakukan dengan cara threshold ing,
penulis menentukan nilai threshold ing tertentu kemudian nilai yang ada dibawah nilai threshold nilainya dijadikan 0 dan yang ada diatas threshold nilainya dijadikan 1.
2.3.2.3 Citra Biner
Citra biner, yaitu citra yang hanya terdiri atas dua warna, yaitu hitam dan putih. Oleh karena itu, setiap pixel pada citra biner cukup direpresentasikan dengan 1 bit. Gambar 12 merupakan dan Gambar 13 merupakan representasi citra biner. contoh citra
Gambar 12 Contoh citra
Gambar 13 Representasi citra biner dari Gambar 12
Meskipun saat ini citra berwarna lebih disukai karena memberi kesan yang lebih kaya dari citra biner, namun tidak membuat citra biner mati. Pada beberapa aplikasi citra biner masih tetap dibutuhkan, misalkan citra logo instansi (yang hanya terdiri dari warna hitam dan putih), citra kode barang (bar code) yang tertera pada label barang, citra hasil pemindaian dokumen teks, dan sebagainya. Seperti yang sudah disebutkan diatas, citra biner hanya mempunyai dua nilai derajat keabuan : hitam dan putih. Pixel – pixel objek bernilai 1 dan pixel – pixel latar belakang bernilai 0. pada waktu menampilkan gambar, adalah putih dan 1 adalah hitam. Jadi Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
BAB II Landasan Teori
17
pada citra biner, latar belakang berwarna putih sedangkan objek berwarna hitam seperti
tampak pada gambar 2.1 diatas. Meskipun komputer saat ini dapat memproses citra hitam putih (grayscale) maupun citra berwarna, namun citra biner masih tetap dipertahankan
keberadaannya. Alasan penggunaan citra biner adalah karena citra biner memiliki sejumlah keuntungan sebagai berikut: 1. Kebutuhan memori kecil karena nilai derajat keabuan hanya membutuhkan representasi 1
bit. 2. Waktu pemrosesan lebih cepat dibandingkan dengan citra hitam-putih ataupun warna.
2.4 Teori Dasar Pengolahan Citra Citra merupakan suatu fungsi kontinu dari intensitas cahaya dalam bidang 2D, dengan (x,y) menyatakan koordinat citra dan nilai f pada koordinat (x,y) menyatakan tingkat kecerahan atau derajat keabuan. Citra digital merupakan array 2D dengan nilai f(x,y) nya telah dikonversi ke dalam bentuk diskrit baik pada koordinat citra maupun kecerahannya. Pengolahan citra secara umum dapat didefinisikan sebagai pemrosesan sebuah gambar 2D secara digital.
Pengolahan citra
merupakan proses pengolahan dan analisis citra yang banyak melibatkan presepsi visual. Proses ini mempunyai data masukan dan informasi keluaran yang berbentuk citra. Operasi pengolahan citra digital umumnya dilakukan dengan tujuan memperbaiki kualitas suatu gambar sehingga dapat dengan mudah diinterpretasikan oleh mata manusia dan untuk mengolah informasi yang terdapat pada suatu gambar untuk keperluan pengenalan objek secara otomatis.
2.5 Segmentasi Citra Segmentasi citra merupakan proses pengelompokan pixel-pixel tetangga yang memiliki koherenitas dari propertinya (misalnya nilai intensitas). Daerah hasil bisa merupakan objek atau merupakan bagian dari objek, dan bisa diverifikasi (atau modifikasi) mengikuti langkahlangkah analisis gambar atau pengenalan pola. Algoritma segmentasi citra pada umumnya didasarkan pada dua properti dari nilai intensitas : diskontinuitas dan similaritas. Properti pertama, pendekatan yang dilakukan adalah dengan membagi-bagi citra berdasarkan pada perubahan intensitas, seperti garis tepi pada citra. Pada properti yang kedua, pendekatan yang Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
BAB II Landasan Teori
18
dilakukan adalah berdasarkan pada pengelompokkan citra menjadi suatu daerah-daerah/
region yang memiliki kesamaan berdasarkan pada suatu kriteria yang telah ditentukan sebelumnya. Contoh dari penerapan properti ini didapat pada metode tresholding, region
growing, dan region splitting dan merging.
2.5.1 Deteksi Diskontinuitas
Ada tiga jenis diskontinuitas pada citra digital, yaitu: point (titik), line (garis), dan edge
(batas). Dalam prakteknya, cara yang paling umum digunakan untuk menemukan
diskontinuitas pada citra adalah dengan menggunakan mask yang dioperasikan ke seluruh pixel yang ada di dalam citra tersebut. Dengan menggunakan mask berukuran 3 x 3, akan
didapatkan hasil :
Rumus 2 Rumus konvolusi
dimana zi adalah graylevel dari pixel yang bersesuaian dengan koefisien mask wi.
Gambar 14 Contoh mask 3 x 3
Lakukan loop untuk seluruh titik pada gambar (gunakan dua for loop. Loop pertama untuk sumbu X dan loop kedua untuk sumbu Y). a) Rekam titik yang sedang diperiksa dan juga titik sepenulisrnya ke dalam matrix neighbor. b) Isi matrix mask dengan angka. c) Kalikan matrix neighbor dengan matrix mask secara scalar (Output[x,y] = Mask[x.y] * Neighbor[x,y]). Maksudnya adalah kalikan cell matrix mask [0,0] dengan matrix neighbor[0,0] dan simpan hasilnya dalam matriks lain misalnya output [0,0]. Kemudian kalikan cell matrix mask [0,1] dengan matrix neighbor [0,1] demikian seterusnya hingga setiap cell dari matriks telah dikalikan. Jumlahkan seluruh isi cell dari matrix Output. Hasil penjumlahan ini adalah titik baru yang akan penulis letakkan pada layer output. Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
BAB II Landasan Teori
19
2.5.1.1 Deteksi Tepi (Edge Detection)
Deteksi tepi (Edge Detection) pada suatu citra adalah suatu proses yang menghasilkan tepi
tepi dari objek-objek citra, tujuannya adalah :
a) Untuk menandai bagian yang menjadi detail citra.
b) Untuk memperbaiki detail dari citra yang kabur, yang terjadi karena error atau adanya efek dari proses akuisisi citra.
Suatu titik (x,y) dikatakan sebagai tepi (edge) dari suatu citra bila titik tersebut mempunyai
perbedaan yang tinggi dengan tetangganya. Gambar x berikut ini menggambarkan bagaimana
tepi suatu gambar diperoleh.
Gambar 15 Proses deteksi tepi citra
Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
BAB II Landasan Teori
20
Perhatikan hasil deteksi dari beberapa citra menggunakan model differensial di atas :
Gambar 16 Hasil deteksi tepi
Pada Gambar 16. terlihat bahwa hasil deteksi tepi berupa tepi-tepi dari suatu gambar. Bila diperhatikan bahwa tepi suatu gambar terletak pada titik-titik yang memiliki perbedaan tinggi. Berdasarkan prinsip-prinsip filter pada citra maka tepi suatu gambar diperoleh mengguanakn High Pass Filter (HPF), yang mempunyai karakteristik: Rumus 3 High pass filter (HPF)
Diketahui fungsi citra f(x,y) sebagai berikut:
Gambar 17 Contoh fungsi citra
Dengan menggunakan filter : H(x,y) = [-1 1] Maka hasil filter adalah :
Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
BAB II Landasan Teori
21
Gambar 18 Hasil deteksi tepi Gambar 17
Bila digambarkan maka proses filter di atas mempunyai masukan dan keluaran sebagai berikut
Gambar 19 Input dan output deteksi tepi
Banyak metoda untuk mendeteksi tepi. Metoda yang banyak digunakan untuk proses deteksi tepi ini, antara lain : 1. Metoda Robert 2. Metoda Prewitt 3. Metoda Sobel 2.5.1.1.1
Metoda Robert
Metoda Robert adalah nama lain dari teknik differensial yang dikembangkan di atas, yaitu differensial pada arah horizontal dan differensial pada arah vertikal, dengan ditambahkan proses konversi biner setelah dilakukan differensial. Teknik konversi biner yang disarankan adalah konversi biner dengan meratakan distribusi warna hitam dan putih. Metoda Robert ini juga disamakan dengan teknik DPCM (Differential Pulse Code Modulation). Kernel filter yang digunakan dalam metoda Robert ini adalah : Rumus 4 Kernel deteksi tepi robert
2.5.1.1.2
Metoda Prewitt
Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
BAB II Landasan Teori
22
Metoda Prewitt merupakan pengembangan metoda Robert dengan menggunakan filter HPF
yang diberi satu angka nol penyangga. Metoda ini mengambil prinsip dari fungsi laplacian yang dikenal sebagai fungsi untuk membangkitkan HPF.
Kernel filter yang digunakan dalam metoda Prewitt ini adalah :
Rumus 5 Kernel deteksi tepi prewitt
2.5.1.1.3
Metoda Sobel
Metoda Sobel merupakan pengembangan metoda Robert dengan menggunakan filter HPF yang diberi satu angka nol penyangga. Metoda ini mengambil prinsip dari fungsi laplacian dan gaussian yang dikenal sebagai fungsi untuk membangkitkan HPF. Kelebihan dari metoda Sobel ini adalah kemampuan untuk mengurangi noise sebelum melakukan perhitungan deteksi tepi. Kernel filter yang digunakan dalam metoda Sobel ini adalah : Rumus 6 Kernel deteksi tepi sobel
2.5.1.1.4
Hasil Implementasi Deteksi Tepi
Untuk mendeteksi garis yang berbasis edge diperlukan kumpulan point terlebih dahulu. Point ini didapat dari pendeteksian tepi. Seperti yang sudah diketahui terdapat tiga metoda deteksi tepi yang sering digunakan, yaitu Roberts, Prewitt dan Sobel. Nilai baru dari suatu pixel akan ditemukan dengan cara: Rumus 7 Menenntukan nilai gradien
√
Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
BAB II Landasan Teori
Dimana
23
adalah hasil konvolusi filter H dengan citra, dan
adalah hasil konvolusi filter V
dengan citra.
Dalam pendeteksian tepi ini akan dipilih salah satu metoda yang akan digunakan. Berikut
perbandingan dari metoda Roberts, Prewitt dan Sobel.
Jika diketahui terdapat 3 buah citra berikut :
Gambar 20 Tiga buah citra yang akan di deteksi tepiannya
1. Hasil perhitungan menggunakan metoda Sobel dengan ambang konvolusi T=255 * * * * * * * 900 798 400 2 278 * 40 458 464 394 740 * 758 694 160 1164 518 * 20 438 668 726 272 * * * * * *
* * * * 618 330 392 * 198 58 430 * 476 416 192 * 634 454 494 * * * * *
Gambar 21 Hasil deteksi tepi Gambar 20 (a) dengan metoda sobel
Terdeteksi 25 tepi menggunakan metoda Sobel. Berikut hasil deteksi tepi menggunakan software yang sudah ada (ImageJ).
Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
BAB II Landasan Teori
24
Gambar 22 Hasil deteksi tepi Gambar 20 (b) dan (c) dengan metoda sobel
2. Hasil perhitungan menggunakan metoda Prewitt dengan ambang konvolusi T=255
* * * * * * 650 599 400 1 * 40 228 262 394 * 549 527 110 775 * 20 419 307 550 * * * * *
* 278 403 292 103 *
* 342 132 379 474 *
* * * 301 290 * 168 81 * 259 143 * 384 277 * * * *
Gambar 23 Hasil deteksi tepi Gambar 20 (a) dengan metoda prewitt
Terdeteksi 22 tepi menggunakan metoda Prewitt. Berikut hasil deteksi tepi menggunakan software yang sudah ada (ImageJ).
Gambar 24 Hasil deteksi tepi gambar 20 (b) dan (c) dengan metoda prewitt
3. Hasil perhitungan menggunakan metoda Robert dengan ambang konvolusi T=255 60 0 1 1 0 2 137 140 1 350 400 199 1 0 139 33 135 224 380 370 227 3 198 92 106 157 38 49 59 37 211 197 325 0 314 375 Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
* * * *
BAB II Landasan Teori
25
69 *
59 *
180 *
23 *
194 317 * *
87 *
99 *
189 *
* *
Gambar 25 Hasil deteksi tepi gambar 20 (a) dengan metoda robert
Terdeteksi 9 tepi menggunakan metoda Robert Berikut hasil deteksi tepi menggunakan software yang sudah ada (ImageJ).
Gambar 26 Hasil deteksi tepi gambar 20 (b) dan (c) dengan metoda robert
Dari ketiga uji coba tersebut terlihat bahwa dengan metoda Roberts pendeteksian tepi yang dihasilkan lebih sedikit dibanding Prewitt dan Sobel. Operator yang digunakannya pun menggunakan filter 2x2 sedangkan Prewitt dan Sobel 3x3, sehingga dalam pengoprasiannya metoda Roberts lebih cepat dibanding metoda Sobel dan Prewitt. 2.5.1.2 Line Detection Tingkatan selanjutnya dalam deteksi diskontinuitas adalah pendeteksian garis. Untuk mendeteksi adanya suatu garis, bisa digunakan mask berikut :
Gambar 27 Mask-mask pendeteksian garis
Mask yang pertama akan memberikan respon yang kuat pada garis yang memiliki arah horizontal. Sedangkan mask-mask berikutnya dapat digunakan untuk mendeteksi garis yang memiliki arah 45°, vertikal, dan -45°. Tampak bahwa arah garis yang dideteksi sesuai dengan arah koefisien mask yang nilainya lebih besar dari yang lain, yaitu 2. Jika R1, R2, R3, dan R4 Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
BAB II Landasan Teori
26
adalah response dari keempat mask yang ada di gambar di atas, dan keempatnya dijalankan
pada pixel yang sama, maka nilai R yang tertinggi menunjukkan arah yang paling mendekati arah pixel tersebut.
2.6 RANSAC (Random Sample Consensus)
RANSAC adalah singkatan untuk "RANdom SAmple Consensus". Ini adalah algoritma untuk
menemukan kelompok “inliers”, yaitu point yang dapat dipasangkan ke dalam garis. Ini
adalah algoritma non-deterministik dalam pengertian bahwa RANSAC memproduksi hasil
yang memuaskan hanya dengan probabilitas tertentu. RANSAC mendapatkan model garisnya dengan cara mengambil secara random subset dari data-data yang ada. Kemudian data tersebut di hipotesis sebagai inlier yang kemudian di test
dengan parameter-parameter yang ada sehingga menghasilkan model garis yang paling baik (Sunglok, et al., n.d.). Parameter-parameter pada RANSAC diantaranya adalah nilai threshhold t , jumlah minimal data yang dekat dengan model d untuk menegaskan bahwa data tersebut bisa dijadikan model ditentukan berdasarkan kebutuhan dan jumlah data yang ada, nilainya biasanya ditentukan oleh eksperimen yang dilakukan (Sunglok, et al., n.d.). Sedangkan nilai dari maksimal iterasi max_iteration ditentukan berdasarkan hasil perhitungan yang sudah ditentukan. Untuk menentukan jumlah dari iterasi yang dilakukan bisa didapat dari rumus : Rumus 8 Menentukan jumlah iterasi algoritma RANSAC
Dimana p merupakan probabilitas yang ditentukan oleh user sesuai dengan kebutuhan, dan w adalah jumlah inlier pada data dan n adalah jumlah point yang akan dipilih (Sunglok, et al., n.d.). Secara umum langkah-langkah pada RANSAC bisa digambarkan seperti pada flowchart dibawah ini :
Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
BAB II Landasan Teori
27
Mengambil 2 Data secara random
Perkirakan Parameter Garis yang terbentuk dari data yang diambil
Error < Threshold
Ambil data baru dan Hitung Error garis terhadap data yang baru
true false
false
false
Masukan data sebagai kandidat inliers dan tambah jumlah inliers
Semua data sudah dicek
true
Simpan Parameter Garis sebagai Parameter Final
true
Iterasi sudah selesai dilakukan
Jumlah inliers terbesar sampai saat ini
false
true
Return Parameter Final
Gambar 28 Flowchart RANSAC
2.7 Metoda Martin Hirzer Metoda Martin Hirzer merupakan metoda yang akan digunakan dalam pendeteksian marker ini. Berdasarkan tulisannya yang berjudul “Marker Detection for Augmented Reality” akan digunakan.
2.7.1 Deteksi Garis Berbasis Tepi Dalam metodanya hirzer mendeteksi garis dalam dua tahapan algoritma. Tahapan yang pertama algoritma yang digunakan adalah untuk mencari kandidat-kandidat titik yang akan dijadikan garis, kandidat-kandidat titik ini adalah berupa tepian (edge). Untuk menghindari pencarian semua bagian pixel dalam sebuah gambar algoritma ini pertama kali membagi Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
BAB II Landasan Teori
28
gambar menjadi region dengan besar 40px X 40px dan tiap region itu dibagi lagi menjadi
region yang lebih kecil dengan besar 5px X 5px, pembagian ini dilakukan agar tepi yang didapatkan tidak terlalu banyak karena hanya mendapatkan titik tepi setiap 5px bukan setiap
1px, dengan kata lain yang diambil adalah sampling tepi untuk setiap 5px. Setiap titik tepi yang ditemukan dihitung orientasinya dengan persamaan : Rumus 9 Menentukan orientasi titik
(
⁄
)
gy : komponen y pada gradient gx : komponen x pada gradient
Gambar 29 Contoh citra yang akan dicari titik tepinya
Hasil dari orientasi ini adalah 0o – 360o sesuai dengan nilai intensitas gambar. Ini berarti titik yang berada diantara hitam-putih dengan titik tepi yang berada diantara putih-hitam dengan arah yang sama akan mempunyai nilai perbedaan orientasi sebesar 180o.
Gambar 30 Hasil titik tepi dengan orientasinya
Pada tahapan kedua algoritma RANSAC-grouper akan digunakan untuk mencari segmen garis berdasarkan tepian yang sudah ditemukan oleh tahapan pertama. RANSAC-grouper ini Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
BAB II Landasan Teori
29
akan menghipotesis garis menggunakan paling sedikit dua titik tepi, dimana dua titik tepi ini
berada di region 40px X 40px yang sama dan memiliki orientasi yang compatible dengan segmen garis yang akan menghubungkan kedua titik ini.
2.7.2 Menggabungkan segmen-segmen garis
Setelah langkah sebelumnya selesai dilakukan penulis akhirnya hanya mempunyai segmen
garis pendek. Untuk memperoleh garis yang lebih panjang penulis harus menyatukan segmen
garis pendek tersebut. Penulis melakukanya dengan cara melakukan testing semua
kemungkinan penyatuan garis yang bisa dilakukan. Dua segmen garis disatukan jika mampu memenuhi dua kriteria. Yang pertama orientasi dua segmen garis tersebut haruslah
kompatibel. Hal ini harus diperiksa karena penulis ingin mencari garis-garis lurus. Definisikan
maksimal perbedaan orientasi yang dibolehkan dan hanya pasangan segmen garis yang mempunyai perbedaan orientasi lebih kecil dari threshold
tersebut yang diperiksa lebih
lanjut. Akan tetapi jika hanya memeriksa orientasi dari dua segmen garis tentu saja tidak cukup, karena hal itu akan mengantarkan penulis pada situasi segmen garis yang parallel yang tidak bertempat pada garis yang sama tapi tetap saja penulis menyatukanya. Maka dari itu kriteria kedua berhubungan dengan koneksi garis dari dua segmen-segmen garis. Orientasi dari koneksi garis juga harus kompatibel dengan orientasi dari dua segmensegmen garis. Oleh karena koneksi garis sekarang harus mempunyai orientasi yang sama terhadap segmen-segmen garis. Segmen garis parallel yang tidak berada digaris yang sama tidak lagi disatukan. Tapi, masih ada satu masalah lagi yaitu segmen garis mana yang tidak sesuai tapi telah disatukan. Bayangkan, untuk contohnya, ada beberapa marker yang terlihat pada gambar, dan marker ini disejajarkan dalam grid reguler. Dengan test menyatukan garis, definisi sejauh ini ialah memungkinkan saja bahwa segmen-segmen garis marker sebelahnya bergaris sama dengan satu sama lain (koneksi garisnya juga memiliki orientasi yang sama). Hal ini dapat menghasilkan garis panjang yang menyambungkan region dari image lainya, seperti background putih yang dikelilingi oleh marker-marker. Untuk menghindari hal ini penulis harus memeriksa koneksi garis dari poin ke poin. Gradien orientasi dari semua poin koneksi garis harus kompatibel dengan orientasinya. Perhitungan dari gradien orientasinya sama seperti untuk edgels. Pada akhirnya segmen garis yang sudah melewati test terakhir ini penulis satukan.
Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
BAB II Landasan Teori
30
Hingga saat ini tidak ada yang mengatakan tentang jarak antara segmen garis dalam proses
menyatukan. Tentu saja penulis ingin menghubungkan segmen garis yang dekat dengan satu sama lain, karena segmen-segmen garis seharusnya memang berasal dari garis yang sama.
Gambar 31 Sebelum segmen garis digabungkan (kiri) dan setelah digabungkan (kanan)
Hence dalam versi sebelumnya tentang algoritma merging yang penulis pakai threshold value-nya untuk jarak maksimum yang diperbolehkan. Masalahnya ialah disatu sisi jika value terlalu kecil tidak semua segmen garis yang sesuai disatukan, yang menyebabkan hasilnya bisa memiliki jarak. Disisi lainya menggunakan value yang terlalu besar bisa menyebabkan situasi dimana exterior segmen garis dari sebuah garis di satukan terlebih dahulu. Sebagai hasilnya bisa terjadi interior segmen garis tidak disatukan dengan garis lagi, karena jarak terhadap akhir garis terlalu jauh sekarang. Dan segmen garis yang tersisa sekarang bisa menyebabkan permasalahan dilangkah selanjutnya. Untuk mengatasi problem ini penulis menggunakan line segment merging process. Sekarang dimulai dengan dua segmen garis yang kompatibel dengan koneksi garis terdekat, lalu datang dua segmen garis kompatibel dengan koneksi garis kedua terdekat, dan seterusnya. Dengan cara seperti ini penulis bisa menyatukan segmen garis yang terdekat sebelum menyatukan segmen garis yang jarraknya lebih jauh. Untuk mengurangi waktu kerja dari algoritma ini dua langkah menyatukan segmen garis digunakan. Yang dimana penulis gunakan region yang kecil untuk mendapatkan segmen garis.
Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
BAB II Landasan Teori
31
2.7.3 Perpanjangan Garis
Setelah segmen-segmen garis tersebut sudah disatukan (merge), langkah berikutnya ialah memperpanjang garis. Fungsi perpanjangan garis ini untuk memperoleh garis dengan panjang yang maksimum sesuai pada citra yang ada.
Cara yang digunakan Hirzer untuk memperpanjang garis ialah dengan mencari point berikutnya yang sesuai.
Pada gambar dibawah ini terlihat terdapat garis berwarna merah.Setelah diperpanjang point berwarna kuning merupakan point yang sesuai untuk perpanjangan garisnya dan berhenti hingga menemukan daerah putih atau hitam. Point berwarna biru merupakan tes point untuk
estimasi disaat menentukan corner.
Gambar 32 Proses memperpanjang garis
Menurut
penelitian
infi
pada
blognya
memaparkan
bahwa
Algoritmanya
dalam
memperpanjang garis ini ialah (Otter, 2010): 1. Perpanjang garis dari setiap end of line telah teredeteksi dengan menemukan tepinya. Jika setiap pixel adalah tepi lakukan langkah 2. Lakukan hingga pixel bukan merupakan tepi. 2. Lanjutkan ke pixel berikutnya. Jika piksel tersebut berwarna „putih‟, piksel tersebut merupakan corner walaupun ada pada daerah putih.
Gambar 33 Hasil memperpanjang garis
Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
BAB II Landasan Teori
32
2.7.4 Deteksi Titik Sudut
Untuk mendapatkan quadrangle langkah yang dilakukan adalah dengan mendeteksi sudut.Pada metodanya martin hirzer mendapatkan sudut dari hasil perpanjangan garis yang dilakukan.
Gambar 34 Warna merah adalah garis yang dihasilkan dari menggabungkan garis dan garis kuning adalah hasil dari perpanjangan garis (Hirzer, 2008)
Cara mendeteksinya adalah dengan cara mengambil salah satu segment garis yang telah diperpanjang kemudian mencari perpotongannya dengan segment garis lain yang sudah diperpanjang juga. Untuk mencari garis lainnya yang cocok dengan garis pertama yang diambil beberapa langkah dilakukan: 1. Langkah pertama setalah secara random garis pertama diambil, garis kedua yang diambil harus memiliki perpotongan dengan garis yang pertama. 2. Periksa arah dari garis pertama dan kedua, arahnya tidak boleh sama seperti pada Gambar 35 sebelah kiri.
Gambar 35 Sebelah (kiri) arah yang hampir sama dan sebelah (kanan) arah yang berbeda
Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
BAB II Landasan Teori
33
Dengan ketentuan titik akhir dari garis pertama harus bertemu dengan titik awal dari garis
kedua.
3. Kemudian pengecekan terhadap orientasi garis dilakukan, disini yang ingin didapatkan
hanyalah marker sehingga yang hars terdeteksi adalah garis hitam yang dikelilingi oleh latarbelakang berwarna putih. Nilai dari orientasi adalah berupa derajat yang menandakan
orientasinya seperti terlihat pada gambar dibawah ini.
Gambar 36 Nilai orientasi garis antara latar depan dan latar belakang
Dengan begitu yang diperiksa adalah yang memiliki orientasi seperti pada Gambar 37.
Gambar 37 (a) Orientasi garis yang kompatibel Dan (b) orientasi garis yang tidak kompatibel (Hirzer, 2008)
Dari Gambar 37(a) orientasi garis sesuai dengan yang ditentukan kemudian keempat sudut didapatkan (titik berwarna hijau) dan pada gambar b tidak ada sudut yang ditemukan karena tidak sesuai orientasinya.
Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
BAB II Landasan Teori
34
Gambar 38 Hasil akhir deteksi titik sudut
Setelah semua langkah-langkah deteksi sudut dijalanjan sesuai dengan aturan-aturan yang ada tadi maka hasil akhir yang didapatkan ada seperti pada Gambar 38.
2.7.5 Pembentukan Quadrangle Jika ke empat sudut sudah ditemukan maka quadrangle sudah terbentuk dan marker bisa ditemukan dan pendeteksian lokasi marker pun selesai, namun jika yang ditemukan hanya tiga sudut, sudut yang ke empat dapat di perkirakan letaknya dengan cara menarik garis dari dua sudut sehingga akan ditemukan sudut yang ke empat.
Gambar 39 (Kiri) 4 Titik sudut ditemukan Quadranle dapat ditemukan dan (Kanan) 3 Titik sudut terdeteksi titik yang keempat diestimasi
Gambar 40 Dua titik sudut terdeteksi tidak dapat menemukan Quadrangle
Pendeteksian Posisi Marker Pada Teknologi Augmented Reality
BAB II Landasan Teori
35
Jika yang terdeteksi hanya 2 sudut ada kemungkinan quadrangle gagal dideteksi seperti
terlihat pada gambar Gambar 40, namun jika sudut yang terdeteksi hanya 1 sudut saja tidak akan ada quadrangle terdeteksi.
Gambar 41 Quadrangle yang terbentuk
Gambar diatas hasil dari deteksi dengan ditemukanya tiga marker sedangkan ada marker yang id markernya tertutupi sehingga tidak terdeteksi. Terlihat jika satu bagian segmen garis tertutupi benda lain dan salah satu sudut marker tertutupi masih dapat terdeteksi bahwa itu adalah sebuah marker pada akhir proses pendeteksian.
Pendeteksian Posisi Marker Pada Teknologi Augmented Reality