BAB 3 ANALISIS DAN PERANCANGAN
3.1 Gambaran Permasalahan Secara Umum
Poligon bukanlah suatu bentuk yang spesifik seperti segitiga sama kaki, persegi, belah ketupat, ataupun jajargenjang, melainkan suatu bentuk bebas yang memenuhi definisi yang telah diberikan pada subbab 2.7. Sehingga diperlukan serangkaian proses dan feature extraction yang baik agar aplikasi dapat membedakan poligon yang satu dengan poligon yang lainnya. Rangkaian proses dan feature extraction yang digunakan akan dijelaskan pada subbab-subbab selanjutnya. Perhatikan gambar berikut ini.
Gambar 3.1 Contoh Poligon Sejenis 33
34 Pada gambar di atas terdapat 100 buah poligon yang sejenis, yaitu segiempat. Untuk proses pengenalan secara manual dapat dikatakan tidak sulit karena jenis poligonnya adalah sama. Sedangkan untuk proses penghitungan secara manual dapat memerlukan waktu yang cukup lama. Hal ini tergantung kecepatan tiap individu dalam menghitung.
Gambar 3.2 Contoh Poligon Tak Sejenis
Pada gambar di atas terdapat 100 buah poligon yang berbeda, yaitu 20 segitiga, 20 segiempat, 20 segilima, 20 segienam, dan 20 segidelapan. Untuk proses pengenalan dan penghitungan secara manual pasti memerlukan waktu yang cukup lama. Tingkat keakuratan hasil perhitungan secara manual juga belum tentu tinggi. Hal ini tergantung
35 kondisi individu yang melakukan proses perhitungan dimana tingkat kelelahan mata dapat mengurangi ketelitian dalam menghitung. 3.2 Kebutuhan Sistem dan Pemenuhan Kebutuhan Sistem
Sistem harus dapat mengenali dan menghitung jumlah masing-masing pola poligon yang terdapat pada input yang diberikan.
Untuk memenuhi kebutuhan ini
digunakan artificial neural networks sehingga dapat mengantisipasi penambahan pola poligon yang akan dikenali dengan tetap menyimpan pola poligon yang lama. Dalam hal ini artificial neural networks yang digunakan adalah metode backpropagation yang memberikan keakuratan dan kecepatan tinggi dalam proses pengenalan dan penghitungan.
3.3 Alur Program Secara Umum
Aplikasi ini dapat dibagi menjadi tiga bagian utama, yaitu insert pola poligon, proses recognition and counting poligon, dan training pola poligon. Gambaran dari masing-masing proses ini secara umum dapat dilihat pada Gambar 3.3 dan Gambar 3.4 berikut.
36
m ulai
input dengan im age file yang sudah ada tidak gam bar dengan bentuk yang sudah disediakan
ya
pilih file im age
im age processing
polygon extraction
feature extraction
recognition and counting
sim pan pola atau lakukan recognition and counting
sim pan pola
recognition and counting
feature, target output, dan nam a poligon
hasil recognition and counting
feature, target output, dan nam a poligon
selesai
Gambar 3.3 Flowchart Proses Insert Pola Poligon dan Proses Recognition and Counting Poligon
37
mulai
1
setting network (learning rate, jumlah hidden units, jumlah unit ditiap hidden units, gunakan inisialisasi nguyen-widrow)
baca pola pertama
training dengan backpropagation
tidak tidak
file setting sudah ada
belum
baca pola selanjutnya
pola habis ya
setting network
sudah error system <= target error
ya
Baca setting network setting network network
selesai
target error
pola ada
ada
tidak ada selesai
1
Gambar 3.4 Flowchart Proses Training Pola Poligon
38 3.4 Image Processing 3.4.1 Grayscaling
Warna-warni pada image yang akan diproses bukan merupakan informasi vital dari image. Bagi komputer warna yang banyak hanya akan menambah beban komputasi yang tentunya memperlambat proses yang dilakukan terhadap image.
Proses
grayscaling yang menjadikan image berwarna banyak menjadi grayscale image, yaitu image dengan 256 tingkatan warna abu-abu, akan mempercepat proses yang dilakukan
terhadap image. Warna abu-abu sendiri dibentuk dari perpaduan komponen warna yaitu R (Red), G (Green), dan B (Blue) dengan nilai setiap komponen adalah sama (dari 0 sampai 255). Untuk mendapatkan grayscale image dari image berwarna dilakukan dengan menyamakan nilai setiap komponen warna dari masing-masing pixel pada image. Hal ini dapat dilakukan dengan merata-ratakan nilai dari setiap komponen warna. Sebagai contoh, sebuah pixel terdiri dari R = 255, G = 0, dan B = 0 (pixel dengan warna merah murni) diubah menjadi pixel abu-abu dengan merata-ratakan nilai R, G, dan B nya sehingga mempunyai nilai R = G = B = (255 + 0 + 0) div 3 = 85 (div adalah kependekan dari divisor yaitu operasi pembagian dengan hasil berupa bilangan bulat). Cara tersebut mempunyai kelemahan dalam kasus berikut. Ada dua pixel dimana pixel pertama memiliki nilai R = 255, G = 0, dan B = 0 dan pixel kedua memiliki nilai R = 0, G = 0, dan B = 255.
Kedua pixel tersebut jika dilihat dengan mata manusia maka akan
berwarna merah dan biru. Jika kedua pixel tersebut dijadikan pixel abu-abu dengan cara merata-ratakan nilai komponen warnanya maka akan didapatkan nilai yang sama yaitu R= G = B = 85. Hal tersebut dapat diatasi dengan mengubah cara konversinya dengan
39 mengalikan masing-masing komponen warna dengan nilai konstanta yang berlainan, dimana nilai-nilai konstanta yang dipakai untuk masing-masing komponen warna jika dijumlahkan akan bernilai 1 sehingga tetap akan menghasilkan nilai dengan kisaran dari 0 sampai 255. Misal nilai konstanta yang digunakan untuk masing-masing komponen warna 0.3, 0.6, dan 0.1 maka pada kasus di atas nilai R, G, dan B untuk pixel pertama = 0.3 * 255 + 0.6 * 0 + 0.1 * 0 = 76.5 dan nilai R, G, dan B untuk pixel kedua = 0.3 * 0 + 0.6 * 0 + 0.1 * 255 = 25.5, dikarenakan tingkatan warna abu-abu harus bilangan bulat maka harus dilakukan pembulatan terhadap hasil akhir perhitungan tersebut (boleh pembulatan ke bawah atau ke atas). Algoritma dan flowchart untuk melakukan proses grayscaling adalah sebagai berikut. GRAYSCALING FOR baris = 0 TO tinggi image – 1 DO FOR kolom = 0 TO lebar image – 1 DO pixel[kolom,baris].R = ROUND (0.3 * pixel[kolom,baris].R + 0.6 * pixel[kolom,baris].G + 0.1 * pixel[kolom,baris].B) pixel[kolom,baris].G = pixel[kolom,baris].R pixel[kolom,baris].B = pixel[kolom,baris].R END FOR END FOR END GRAYSCALING
40
mulai
baris = 0
baris < tinggi image ya kolom = 0
kolom < lebar image ya pixel[kolom,baris].R = ROUND (0.3 * pixel[baris,kolom].R + 0.6 * pixel[kolom,baris].G + 0.1 * pixel[kolom,baris].B) tidak pixel[kolom,baris].G = pixel[kolom,baris].R tidak pixel[kolom,baris].B = pixel[kolom,baris].R
kolom = kolom + 1
baris = baris + 1
selesai
Gambar 3.5 Flowchart Proses Grayscaling
3.4.2 Corner Detection
Proses corner detection dilakukan dengan menerapkan algoritma SUSAN corner detection. Saat ditemukan sebuah corner pada image maka posisi (posisi x atau posisi
kolom dan posisi y atau posisi baris) dari corner tersebut akan disimpan ke dalam sebuah variabel array dari sebuah struktur data. Struktur data yang digunakan memiliki data-data sebagai berikut:
41
Posisi x dan y bertipe integer. Besar sudut yang dimiliki corner bertipe array double. Hubungan ke corner lain bertipe array integer. Setelah proses ini berakhir maka semua posisi corner yang ada pada image telah tersimpan. Penjelasan tentang proses ini dapat dilihat pada Lampiran 17.
3.4.3 Edge Detection
Proses edge detection dilakukan dengan menerapkan algoritma SUSAN edge detection.
Saat proses ini selesai maka akan dihasilkan sebuah image baru yang
merupakan gambar rangka dari image lama. Dari image yang dihasilkan akan dilakukan pengecekan keterhubungan tiap-tiap corner yang didapat dari proses corner detection dengan menggunakan algoritma midpoint dengan memanfaatkan posisi pixel yang seharusnya merupakan posisi pixel pembentuk garis lurus di antara dua buah corner. Lihat nilai pixel pada posisi ini dari image yang dihasilkan. Jika nilai pixel adalah 255 (R = 255, G = 255, dan B = 255) atau berwarna putih berarti dua buah corner itu adalah tidak saling berhubungan. Setelah didapatkan keterhubungan antar corner maka dapat dicari besar sudut untuk setiap corner dengan menggunakan aturan cosinus yang dibahas pada subbab 3.7.1. Hasilnya disimpan pada variabel array dari sebuah struktur data yang telah dijelaskan pada subbab 3.4.2. Penjelasan proses ini dapat dilihat pada Lampiran 17.
42 3.5 Polygon Extraction
Hasil dari image processing tersebut diperoleh informasi mengenai pixel-pixel pada image yang merupakan titik sudut dari poligon yaitu posisi, hubungannya ke titik sudut lain, dan besar sudut yang dimiliki oleh titik sudut tersebut. Meskipun informasi tersebut dimiliki, tetap belum dapat diketahui kombinasi atau urutan titik-titik yang manakah yang membentuk sebuah poligon. Hal tersebut dapat diselesaikan dengan menerapkan sebuah algoritma pencarian poligon, sebut saja polygon extraction. Dengan didasari oleh beberapa definisi tentang poligon pada subbab 2.7, polygon extraction ini dapat dilakukan dengan cara menelusuri titik-titik sudut yang didapatkan. Penelusuran ini dilakukan dari sebuah titik sudut ke titik sudut lainnya dengan persyaratan sebagai berikut: 1. Minimal titik sudut yang telah ditelusuri sebanyak tiga buah, karena dengan jumlah demikianlah baru dapat dibentuk suatu kurva tertutup yang dibentuk oleh garis-garis lurus. 2. Titik sudut yang akan ditelusuri berikutnya bukan merupakan salah satu titik sudut yang telah ditelusuri sebelumnya, kecuali titik tersebut merupakan titik awal penelusuran dan jumlah titik sudut yang telah ditelusuri lebih besar dari dua. 3. Titik terakhir dari penelusuran harus sama dengan titik awal penelusuran. Setelah proses polygon extraction ini selesai maka akan didapatkan sejumlah kumpulan urutan titik-titik sudut (vertex) yang membentuk poligon pada image, kumpulan vertex beserta informasi lain yang dimilikinya ini disimpan ke dalam sebuah variabel array dari
43 sebuah struktur data agar dapat digunakan oleh proses selanjutnya. Adapun struktur data yang digunakan memiliki data-data sebagai berikut: Vertex bertipe array dari sebuah struktur data (dengan data: posisi x dan y dari vertex bertipe integer, hubungan ke vertex lain bertipe array integer, dan sudut
bertipe sebuah struktur data dengan data: lengan sudut bertipe array integer, besar sudut dalam radian bertipe double, dan besar sudut dalam derajat bertipe double).
Arah
poligon
bertipe
enumerasi
arah
yang
digunakan
yaitu
CW
(clockwise/searah putaran jarum jam) dan CCW (counter clockwise/berlawanan arah putaran jarum jam).
44 Algoritma dan flowchart untuk melakukan proses ini adalah sebagai berikut. POLYGON EXTRACTION SET titik_pembentuk_poligon = titik_sedang_ditelusuri = NIL SET poligon = NIL FOR index = 0 TO COUNT (titik_sudut) – 1 DO IF index PARTOF (titik_pembentuk_poligon) THEN CONTINUE END IF PUSH (index, titik_sedang_ditelusuri) DO WHILE TRUE titik_akhir = titik lain yang berhubungan dengan titik_sudut[TOP (titik_sedang_ditelusuri)] IF titik_akhir PARTOF (titik_sedang_ditelusuri) AND COUNT (titik_sedang_ditelusuri) < 3) THEN BREAK IF COUNT (titik_sedang_ditelusuri) > 2 AND titik_akhir = BOTTOM (titik_sedang_ditelusuri) THEN PUSH (titik_sedang_ditelusuri, titik_pembentuk_poligon) PUSH (titik_sedang_ditelusuri, poligon[TOPINDEX (poligon)+1]) BREAK; END IF PUSH (titik_akhir, titik_sedang_ditelusuri) END DO WHILE POPALL (titik_sedang_ditelusuri) END FOR END POLYGON EXTRACTION
45
mulai titik_pembentuk_poligon = NIL titik_sedang_ditelusuri = NIL poligon = NIL index = 0
index < COUNT(titik_sudut) ya index PART OF(titik_pembentuk_poligon) tidak PUSH(index,titik_sedang_ditelusuri)
titik_akhir = titik lain yang berhubungan dengan titik_sudut[TOP (titik_sedang_ditelusuri)] ya titik_akhir PART OF (titik_sedang_ditelusuri) AND COUNT(titik_sedang_ditelusuri) < 3 tidak tidak
COUNT(titik_sedang_ditelusuri) > 2 AND titik_akhir = BOTTOM(titik_sedang_ditelusuri) ya PUSH(titik_sedang_ditelusuri,titik_pembetuk_poligon) PUSH(titik_sedang_ditelusuri,poligon[TOPINDEX(poligon)+1]) tidak PUSH(titik_akhir, titik_sedang_ditelusuri) ya
POPALL(titik_sedang_ditelusuri) index = index + 1 selesai
Gambar 3.6 Flowchart Proses Polygon Extraction
46 3.6 Menentukan Arah Poligon
Penentuan arah dari poligon dapat dilakukan dengan mencari convex hull dari poligon menggunakan algoritma graham’s scan. Misal bentuk poligon adalah sebagai berikut.
Dengan urutan vertex pembentuk convex hull dapat ditentukan arah dari poligon. Jika urutan vertex pembentuk convex hull sesuai (searah) dengan urutan vertex pembentuk poligon maka dapat dikatakan arah poligon tersebut adalah CCW, sebaliknya maka arah poligon adalah CW. Penerapan algoritma graham’s scan untuk poligon di atas akan menghasilkan convex hull yang terbentuk dari urutan vertex 3, 1, 0, dan 4 dan urutan tersebut
mempunyai arah CCW. Sedangkan urutan vertex pembentuk poligon adalah 0, 1, 2, 3, dan 4. Maka arah dari poligon adalah CW, karena urutan vertex pembentuk convex hull berlawanan arah dengan urutan vertex pembentuk poligon, yang jelasnya ditunjukkan oleh gambar berikut.
47 0 4
0 4
2
2
1
1
3 arah urutan vertex poligon
3 arah urutan vertex convex hull
Dengan gambar di atas perbedaan arah dari urutan vertex pembentuk convex hull dan arah dari urutan vertex pembentuk poligon dapat dilihat dengan jelas. Permasalahannya adalah komputer tidak dapat melihat, oleh karena itu diperlukan logika dan algoritma agar komputer dapat melihat perbedaan arah ini. Logika berikut dapat digunakan: 1. Anggap vertex 0, 1, 2, 3, 4, dan seterusnya mewakili nilai 0, 1, 2, 3, 4, dan seterusnya, maka vertex 3, 1, 0, dan 4 mewakili nilai 3, 1, 0, dan 4. 2. Jika nilai pertama lebih kecil dari nilai kedua maka beri tanda ‘+’, jika lebih besar beri tanda ‘–‘, begitu juga untuk nilai kedua dan nilai ketiga, nilai ketiga dan nilai keempat, dan seterusnya. 3. Anggap vertex pembentuk poligon selalu dimulai dari vertex 0, dan diikuti vertex 1, 2, 3, 4, dan seterusnya, maka akan didapatkan jumlah tanda ‘+’ yang
lebih banyak dari tanda ‘–‘. 4. Bandingkan jumlah tanda ‘+’ dan ‘–‘ yang didapatkan dari vertex pembentuk convex hull, jika jumlah tanda ‘+’ lebih banyak dari ‘–‘ berarti urutan vertex
pembentuk convex hull searah dengan urutan vertex pembentuk poligon maka arah poligon adalah CCW, dan sebaliknya. Sedangkan algoritma pencarian arah poligon adalah sebagai berikut:
48 ARAH POLIGON (poligon) plus = 0 minus = 0 vertexs = GRAHAM’S SCAN (poligon.vertexs) FOR index = 0 TO TOPINDEX(vertexs) – 1 DO IF vertexs[index] < vertexs[index + 1] THEN plus = plus + 1 ELSE minus = minus + 1 END IF END FOR IF plus > minus THEN RETURN CCW ELSE RETURN CW END IF END ARAH POLIGON Setelah didapatkan arah dari poligon-poligon yang didapatkan pada proses polygon extraction maka simpan arah tersebut pada variabel array dari sebuah struktur
data yang dijelaskan pada subbab 3.5. Algoritma graham’s scan dapat dilihat pada subbab 2.9.
3.7 Feature Extraction 3.7.1 Pengambilan Besar Sudut Dalam dari Poligon
Perhatikan poligon berikut.
49
Setelah dilakukan corner detection akan diperoleh posisi dari sejumlah pixel yang merupakan vertex-vertex pembentuk poligon. Dari sejumlah vertex yang didapat akan dihitung terlebih dahulu besar sudut dalam untuk masing-masing vertex. Bagaimana hal itu dapat dilakukan jika yang diketahui hanyalah sejumlah posisi dari vertex-vertex poligon? Ilustrasi dari permasalahan ini ditunjukkan oleh gambar berikut.
Untuk mengatasi hal tersebut dilakukan pengecekan keterhubungan vertex-vertex tersebut dengan menggunakan algoritma midpoint setelah didapatkan rangka dari poligon dengan melakukan edge detection. Asumsikan bahwa vertex-vertex tersebut berada pada koordinat cartesius seperti ditunjukkan gambar berikut.
50
dengan keterhubungan antar vertex sudah diketahui, vertex 0 terhubung dengan vertex 1 dan vertex 5, vertex 1 terhubung dengan vertex 0 dan vertex 2, vertex 2 terhubung dengan vertex 1 dan vertex 3, vertex 3 terhubung dengan vertex 2 dan vertex 4, vertex 4 terhubung dengan vertex 3 dan vertex 5, dan vertex 5 terhubung dengan vertex 0 dan vertex 4. Menggunakan aturan cosinus sebagai berikut:
C b
a
α A
B c
b2 + c2 − a2 2bc α = arccos(cos A) a =| BC | b =| AC | c =| AB | cos A =
dapat diperoleh besar sudut untuk masing-masing vertex. Misal, untuk besar sudut yang dibentuk oleh vertex 5, vertex 0, dan vertex 1 (sudut pada vertex 0)
51
didapat A = vertex 0, B = vertex 1, dan C = vertex 5, a, b, dan c masing-masing dapat dihitung menggunakan rumus jarak 2 titik sebagai berikut.
d
(x1, y1)
(x0, y0)
d = ( x1 − x0) 2 + ( y1 − y 0) 2
Didapatkan: a = (15 − 5) 2 + (25 − 15) 2 = 14.14 b = (5 − 5) 2 + (25 − 5) 2 = 20 c = (15 − 5) 2 + (15 − 5) 2 = 14.14 (20) 2 + (14.14) 2 − (14.14) 2 = 0.707 2(20)(14.14) α = arccos(0.707) = 44.99° cos A =
Perhatikan kasus berikut. Bagaimana dengan besar sudut yang dibentuk vertex 0, vertex 1, dan vertex 2 (sudut pada vertex 1) dan besar sudut yang dibentuk vertex 3, vertex 4, dan vertex 5 (sudut pada vertex 4)?
52
A = vertex 1, B = vertex 0, dan C = vertex 2.
Didapatkan: a = (25 − 5) 2 + (5 − 5) 2 = 20 b = (25 − 15) 2 + (15 − 5) 2 = 14.14 c = (15 − 5) 2 + (15 − 5) 2 = 14.14 (14.14) 2 + (14.14) 2 − (20) 2 = −0.0003 2(14.14)(14.14) α = arccos(−0.0003) = 90.02° cos A =
A = vertex 4, B = vertex 3, dan C = vertex 5.
Didapatkan: a = (25 − 5) 2 + (20 − 25) 2 = 20.62 b = (10 − 5) 2 + (20 − 25) 2 = 7.07 c = (25 − 10) 2 + (20 − 20) 2 = 15 (7.07) 2 + (15) 2 − (20.62) 2 = −0.708 2(7.07)(15) α = arccos(−0.708) = 135.08° cos A =
53 pada dua kasus di atas besar sudut yang didapat untuk vertex 1 dan vertex 4 adalah bukan sudut dalam, dapat dilihat bahwa aturan cosinus hanya bisa digunakan untuk mencari sudut kecil (0°-179°). Lalu bagaimana agar yang nilai sudut yang didapat untuk vertex 1 dan vertex 4 adalah nilai sudut besarnya (181°-359°)? Jawabnya sederhana,
untuk vertex 1 sudut besarnya adalah 360° – 90.02° = 269.98° dan untuk vertex 4 sudut besarnya adalah 360° – 135.08° = 224.92°. Permasalahannya adalah bagaimana cara mengetahui nilai sudut yang didapat dengan aturan cosinus merupakan sudut dalam atau sudut luar dari poligon. Menentukan apakah sudut dalam dari suatu vertex poligon adalah sudut kecil (nilai sudut yang didapat dari perhitungan menggunakan aturan cosinus) atau sudut besar (360° – nilai sudut kecil) dapat dilakukan dengan melihat arah belok yang terjadi pada vertex yang bersangkutan, jika arah belok suatu vertex searah dengan arah dengan arah urutan vertex-vertex pembentuk poligon maka sudut dalam pada vertex tersebut adalah sudut kecil, dan sebaliknya jika arah belok suatu vertex berlawanan arah dengan arah urutan vertex-vertex pembentuk poligon maka sudut dalam pada vertex tersebut adalah sudut besar. Dalam hal ini arah yang dimaksud adalah CW (clockwise/searah perputaran jarum jam) dan CCW (counter clockwise/berlawanan arah putaran jarum jam).
54
Pada gambar di atas dapat dilihat bahwa arah poligon adalah CCW. Lihat arah belok pada vertex 1, dapat dilihat bahwa dari vertex 0 menuju vertex 1 dan dari vertex 1 menuju vertex 2 terjadi belokan dengan arah CW (berlawanan dengan arah poligon) maka sudut dalam pada vertex 1 adalah sudut besar. Begitu juga dari vertex 3 menuju vertex 4 dan dari vertex 4 menuju vertex 5 terjadi belokan dengan arah CW maka sudut
dalam pada vertex 4 adalah sudut besar. Lain halnya dengan arah belok pada vertex 0, vertex 2, vertex 3, dan vertex 5 dapat dilihat bahwa semuanya memiliki arah belok yang
searah dengan arah poligon maka sudut dalam pada vertex-vertex tersebut adalah sudut kecil. Masalah yang dihadapi sekarang adalah bagaimana menentukan arah belok dari vertex pertama menuju vertex kedua dan dari vertex kedua menuju vertex ketiga.
Pemanfaatan perkalian cross vektor dapat digunakan untuk mengatasi permasalahan tersebut. Dengan membedakan tanda (negatif atau positif) dari hasil perkalian cross vektor dapat ditentukan arah belok pada suatu vertex.
55
untuk mengetahui apakah arah belok dari titik pusat sumbu menuju v1 dan dari v1 menuju v2 adalah CW atau CCW dapat ditentukan dengan melihat hasil perkalian vektor v1 dan v2.
x1 x 2 v1 × v 2 = det = x1y 2 − x 2 y1 y1 y 2 Jika hasilnya negatif maka arah belok dari titik pusat menuju v1 dan dari v1 menuju v2 adalah CW dan sebaliknya jika positif maka arah belok dari titik pusat menuju v1 dan dari v1 menuju v2 adalah CCW. Rumus di atas dapat diterapkan asalkan titik awalnya adalah titik pusat sumbu (0, 0). Dengan memasukkan posisi dari vektor ke dalam rumus di atas didapat: 10 25 v1 × v 2 = det = (10)(15) − (25)(20) = −350 adalah negatif maka arah belok dari 20 15 titik pusat menuju v1 dan dari v1 menuju v2 adalah CW. 25 10 v 2 × v1 = det = (25)(20) − (10)(15) = 350 adalah positif maka arah belok dari 15 20 titik pusat menuju v2 dan dari v2 menuju v1 adalah CCW. Permasalahan kembali timbul karena pada poligon titik awal tidaklah selalu titik pusat dari sumbu. Untuk permasalahan ini bisa memanfaatkan rumusan berikut.
56 v'1 = v1 − v0
v'2 = v 2 − v0
x'1 = x1 − x0 dan x'2 = x 2 − x0 y '2 = y 2 − y 0 y '1 = y1 − y 0 x'1 x'2 v'1× v'2 = det = x'1y '2 − x'2 y '1 = ( x1 − x0)( y 2 − y 0) − ( x 2 − x0)( y1 − y 0) y '1 y '2 Uji kebenaran rumusan di atas pada vertex-vertex poligon, misal untuk vertex 3 menuju vertex 4 dan dari vertex 4 menuju vertex 5. v2 v1 v2 – v0 v1 – v0 v0
v’2 v’1
(10 − 25) (5 − 25) v'1 × v'2 = det = (10 − 25)(25 − 20) − (5 − 25)(20 − 20) = −75 (20 − 20) (25 − 20) karena bernilai negatif maka arah belok dari vertex 3 menuju vertex 4 dan dari vertex 4 menuju vertex 5 adalah CW dan berarti berlawanan dengan arah poligon maka sudut dalam pada vertex 4 adalah 360° – sudut kecil = 360° – 135.08° = 224.92°. Setelah semua sudut dalam dari poligon didapatkan maka jadikan urutan sudut dalam mulai dari vertex 0 sampai vertex 5 sebagai salah satu feature dari poligon. Algoritma untuk
pengambilan sudut dalam poligon adalah sebagai berikut. SUDUT DALAM (poligon) FOR vertex = 0 TO COUNT (poligon.vertexs) – 1 DO IF arah belok poligon.vertexs[vertex] = poligon.direction THEN poligon.vertexs[vertex].angle = sudut_kecil ELSE poligon.vertexs[vertex].angle = 360 – sudut_kecil END IF END FOR FOR i = 0 TO COUNT (poligon.vertexs) – 1 DO
57 sudut[i] = poligon.vertexs[i] END FOR RETURN sudut END SUDUT DALAM
Perhatikan gambar poligon berikut ini.
Poligon 1
Poligon 2
Besar sudut dalam perlu diambil sebagai feature, sebab jika sudut kecil (sudut yang diperoleh dari perhitungan menggunakan aturan cosinus) yang diambil maka kedua poligon di atas akan memiliki feature yang sama sehingga tidak dapat dibedakan atau dengan kata lain kedua poligon tersebut dianggap sama.
3.7.2 Pengambilan Perbandingan Sisi Poligon
Selain sudut dalam, perbandingan sisi dari poligon diperlukan sebagai feature poligon agar dapat mewakili keunikan dari setiap poligon. Sebagai contoh jika hanya digunakan sudut dalam sebagai feature, bagaimana bentuk poligon berikut dapat dibedakan?
58 0
3
0
3
1
2
1
2
Poligon 1
Poligon 2
Seperti terlihat kedua poligon mempunyai urutan sudut dalam yang sama yaitu 90°, 90°, 90°, dan 90°.
Dengan menambahkan perbandingan sisi dari poligon maka kedua
poligon tersebut dapat dibedakan. Misal pada poligon 1 panjang masing-masing sisi adalah 10 satuan maka poligon 1 memiliki perbandingan sisi 1:1:1:1 dan pada poligon 2 panjang sisi 0–1 dan sisi 2–3 adalah 10 satuan sedangkan panjang sisi 1–2 dan 0–3 adalah 20 satuan maka poligon 2 memiliki perbandingan sisi 1:2:1:2.
Urutan
perbandingan sisi diambil berdasarkan sisi yang dibentuk oleh vertex pertama poligon dan vertex kedua, diikuti sisi yang dibentuk oleh vertex kedua dan vertex ketiga, kemudian sisi yang dibentuk oleh vertex ketiga dan vertex keempat, dan seterusnya sampai sisi terakhir yang dibentuk oleh vertex terakhir dan vertex pertama. Algoritma proses ini adalah sebagai berikut. PERBANDINGAN SISI (poligon) j=0 FOR vertex = 0 TO COUNT (poligon.vertexs) – 2 DO sisi[j] = DISTANCE (poligon.vertexs[vertex], poligon.vertexs[vertex+1]) j=j+1 END FOR sisi[j] = DISTANCE (poligon.vertexs[0], poligon.vertexs[j]) minimum = MIN (sisi) FOR j = 0 TO COUNT (sisi) – 1 DO perbandingan[j] = sisi[j] / minimum END FOR RETURN perbandingan END PERBANDINGAN SISI
59 3.8 Insert Pola Poligon
Setelah didapatkan feature dari seluruh poligon yang ada pada image, maka feature-feature tersebut disimpan ke dalam data store (berupa tabel) untuk dapat
digunakan saat training maupun saat recognition and counting. Struktur tabel yang digunakan diperlihatkan pada Tabel 3.1 berikut.
Alasan untuk menggunakan tabel
sebagai sarana untuk data store adalah untuk memanfaatkan kecepatan pencarian feature poligon, target output dari sebuah poligon, ataupun nama sebuah poligon
menggunakan sintaks SQL dan memudahkan penambahan pola-pola poligon baru. Nama Field Tipe Data Keterangan Feature1 Text Besar sudut dalam secara berurutan Feature2 Text Perbandingan panjang sisi secara berurutan OutputTarget Text 0 -> mewakili -1 dan 1 -> mewakili +1 TargetName Text Nama Poligon Tabel 3.1 Struktur Tabel yang Digunakan sebagai Data Store
Perlu diperhatikan disini, bahwa jika sebuah poligon terbentuk dari urutan vertex sebagai berikut: 0, 1, 2, 3, dan 4. Dengan feature sudut dalam berturut-turut (dalam derajat) 90, 116, 109, 108, dan 116 serta feature perbandingan sisinya 1.4, 1, 1.3, 1, dan 1.4, maka pola dari poligon tersebut tidak hanya feature dengan urutan seperti yang disebutkan di atas. Melainkan feature yang merupakan kombinasi dari kemungkinan pembentukan poligon dengan urutan vertex selain 0, 1, 2, 3, dan 4 misalnya selain urutan vertex 0, 1, 2, 3, 4 juga dapat dibentuk poligon dengan urutan 1, 2, 3, 4, 0, atau 2, 3, 4, 0, 1, atau 3, 4, 0, 1, 2, atau 4, 0, 1, 2, 3, atau 0, 4, 3, 2, 1, atau 4, 3, 2, 1, 0, atau 3, 2, 1, 0, 4, atau 2, 1, 0, 4, 3, atau 1, 0, 4, 3, 2. Feature sudut dalam dan perbandingan sisi dengan urutan tersebut juga harus dimasukkan sebagai pola suatu poligon, sehingga sebuah poligon dengan n sisi memiliki 2n pola. Hal ini perlu dilakukan mengingat
60 posisi, ukuran, dan orientasi poligon pada image adalah bebas. Perhatikan pada Gambar 3.5 pada field “OutputTarget” 0 mewakili target output minimum (-1) dan 1 mewakili target output maksimum (1) sehingga pada saat training maupun recognition and counting nilai 0 atau 1 pada field “OutputTarget” ini harus dikonversi terlebih dahulu
sesuai dengan target output minimum dan target output maksimum yang digunakan.
3.9 Training Pola Poligon
Pada proses ini error dari sistem untuk satu pola diperoleh dengan cara mengambil nilai absolut dari selisih maksimum output yang dihasilkan oleh network (output pada setiap unit dalam output units) dengan target output yang ditentukan. Sedangkan error sistem untuk satu epoch diperoleh dengan cara mengambil error sistem maksimum yang terjadi pada training masing-masing pola. Error sistem yang diperoleh dengan cara ini akan menjadi error maksimum yang akan didapatkan sewaktu proses recognition and counting atau dengan kata lain nilai absolut dari selisih maksimum output disetiap unit pada output units dengan target output yang telah ditentukan untuk
sebuah pola poligon akan lebih kecil atau sama dengan error sistem. Algoritma dan flowchart untuk proses ini dapat dilihat pada subbab 2.11.5.3 dan pada Gambar 3.4.
3.10 Recognition and Counting Poligon
Proses ini dilakukan setelah network sudah di–training dengan pola-pola yang ada, proses ini hanya melibatkan proses feedforward pada algoritma training backpropagation (lihat subbab 2.11.5.3). Output yang dihasilkan disetiap unit pada
61 output units akan dibandingkan dengan target output untuk masing-masing pola poligon
yang telah di–training jika nilai absolut dari selisih maksimum output yang dihasilkan disetiap unit pada output units tersebut lebih kecil atau sama dengan error sistem yang ditentukan saat training maka poligon pada image akan dikenali sebagai poligon yang memiliki pola bersangkutan, selain itu maka poligon pada image akan dianggap sebagai unknown. Setiap pengenalan dilakukan akan diikuti penambahan counter untuk setiap
bentuk poligon yang ada pada data store ditambah counter untuk bentuk unknown.
62 3.11 Perancangan Interface Aplikasi
Rancangan interface untuk aplikasi yang dibuat adalah sebagai berikut.
Program Edit Image Tools Help Toolbox
Action Image field
Preview
Gambar 3.7 Rancangan Interface Aplikasi
Gambar 3.7 di atas merupakan rancangan layar utama pada aplikasi yang akan dibuat. Layar utama tersebut terbagi menjadi lima bagian utama yang akan dijelaskan berikut ini. 1. Menu Terdiri dari menu: ”Program” dengan submenu “Load Image” untuk membuka image untuk melakukan training atau recognition and counting, “Save Image” untuk menyimpan image buatan melalui toolbox yang disediakan, “Save Image As” berfungsi sama seperti “Save Image” hanya saja meminta nama file baru sebagai
63 nama file, “Close Image” untuk menutup image yang sedang terbuka, dan “Exit” untuk keluar dari aplikasi. ”Edit” dengan submenu “Undo” dan “Redo” untuk kembali ke tahap sebelumnya dan maju ke tahap setelahnya. ”Image” dengan submenu “Grayscale” untuk melakukan proses grayscaling pada image aktif, “Corner Detection” untuk melakukan proses corner detection pada image aktif, dan “Edge Detection” untuk melakukan proses edge detection pada image aktif. ”Tools” dengan submenu “View Angles” untuk melihat titik sudut yang terdetektsi saat proses corner detection, “Insert to Pattern” untuk memasukkan pola poligon yang didapatkan dari image aktif ke data store, “Training” untuk melakukan training pola poligon yang ada pada data store, “Simulate” untuk melakukan recoginition and counting terhadap image aktif, dan “Setting” untuk melihat dan men–set ulang setting dari network. ”Help” dengan submenu “How to Use” dan “About” berisi cara penggunaan aplikasi dan tentang pembuat apikasi. 2. Image Field Merupakan tempat image aktif dan melihat perubahan yang terjadi pada image pada setiap proses yang dilakukan. 3. Toolbox Merupakan alat bantu yang dapat digunakan dalam proses penggambaran poligon pada image field. Berisi tombol-tombol (icon) yang dapat dipilih untuk membentuk poligon dengan warna dan orientasi yang diinginkan.
64 4. Action Berisi kumpulan icon yang menunjukkan proses yang dapat dilakukan. Icon yang tersedia antara lain: icon grayscaling, berfungsi sama seperti submenu “Grayscale”. icon corner detection, berfungsi sama seperti submenu “Corner Detection”. icon edge detection, berfungsi sama seperti submenu “Edge Detection”. icon undo, berfungsi sama seperti submenu “Undo”. icon redo, berfungsi sama seperti submenu “Redo”. 5. Preview Merupakan tempat untuk melihat image secara lebih mendetail karena adanya perbesaran sebesar tiga kali dari ukuran aslinya.
