6
BAB II KAJIAN PUSTAKA
2.1. Tinjauan Penelitian Sejenis Dari beberapa penelitian yang dilakukan oleh peneliti terdahulu, hasil penelitian yang dikemukakan menunjukkan bahwa sistem PSO dengan menggunakan pengolahan citra (image processing) memberikan hasil akurasi dalam penilaian skor menembak yang semakin baik. Penelitian yang dilakukan oleh Cuiliu Ye dan Hong Mi (Cuiliu & Hong, 2011) menggunakan target berbentuk siluet dada sebagai objek untuk setiap metode pengolahan citra yang digunakan dalam sistem PSO. Alur kerja sistem terdiri dari beberapa tahap, yaitu : Perbaikan gambar target (median filter, image binary, image edge extraction, geometry rectification), Ekstraksi lubang peluru (erosion, dilation, ring radius, invert color, image subtraction, morphological filter), Pengenalan lubang peluru (moment invariants matching dan euclidean distance), Pemberian skor (membandingkan dan menghitung jarak titik tengah jejak peluru, titik tengah background template dengan bulls eye). Hasil penelitian menunjukkan tingkat akurasi 90% dan dapat mendeteksi lubang peluru yang tumpang tindih. Penelitian yang dilakukan oleh Xinnan Fan dkk (Fan, Cheng, Ding, & Zhang, 2009), menggunakan algoritma Template Matching untuk menemukan jejak peluru. Penambahan pencahayaan pada bagian belakang target tembak dilakukan untuk lebih memudahkan analisa dan ektraksi lubang peluru. Sistem
7
dibagi menjadi dua bagian, yaitu : Pengolahan citra target tembak dengan menggunakan metode Laplace transform, median filter, adaptive threshold segmentation, erosion, dilation dan pembuatan, penebalan, ekstrak kontur lingkaran, Pengolahan citra jejak peluru dengan menggunakan metode image subtraction, fixed threshold segmentation, erosion, dilation, invert color, feature extraction, dan cluster analysis. Pengenalan dan segmentasi nilai lingkaran dan titik pusat target disesuaikan dan dikontrol menggunakan database standar target tembak. Hasil penelitian menunjukkan tingkat akurasi hingga 2 desimal dibelakang koma, dibandingkan dengan yang artificial dengan akurasi 1 desimal, sehingga lebih presisi, mampu menghitung nilai untuk lubang peluru yang tumpang tindih/overlap, pada kondisi gambar tidak normal sistem masih mampu mendeteksi dengan tingkat error 0.1 terhadap nilai seharusnya Penelitian yang dilakukan oleh Faizan Ali dan Atif Bin Mansoor (Ali & Bin Mansoor, 2008), menggunakan pengolahan citra untuk menghitung skor dari dalam dan dari luar bull eyes untuk menambah tingkat akurasi dan untuk mendeteksi tumpang tindih jejak peluru dengan alur kerja sistem sebagai berikut : Konversi gambar target tembak ke gray image scale, Target tembak disegmentasi dengan hysteresis thresholding, Pusat dari bull eyes ditentukan dengan distance transform, Batas dari gambar lubang peluru dipertebal dengan morphological erosion, Setiap jejak peluru diberi label dan dinilai dengan menggunakan konektivitas 8 pixel, Jejak peluru yang tumpang tindih diberi label dan skor tersendiri mulai dari jejak peluru kedua dan seterusnya. Hasil dari penelitian ini menunjukkan tingkat akurasi akurasi 98.3% dan dapat mendeteksi tumpang tindih hasil tembak.
8
Penelitian yang dilakukan oleh Ya-bei Yang dkk (Yang, Li, & Zhao, 2007), menggunakan algoritma Template Matching. Algoritma ini memiliki kemampuan efek filter dua dimensi (2D) untuk menghilangkan noise pada gambar tanpa harus melakukan median filtering dan image smoothing terlebih dahulu sehingga dapat mempercepat proses. Pencocokan dilakukan dengan pencarian target dan posisinya, selanjutnya dibandingkan dengan template gambar yang sebelumnya sudah disimpan. Sistem PSO diimplementasi pada Field-Programmable Gate Array (FPGA). Hasil penelitian menunjukkan perbedaan 0.1 dari pada hasil manual. Penelitian yang dilakukan oleh Jua-wei Liang dan Bin Kong (Hua-wei & Bin, 2006) menggunakan komponen perangkat keras yang terdiri dari pistol, perangkat laser pointer, target tembak, kamera, antarmuka kartu gambar, komputer dan komponen perangkat lunak untuk pemrosesan gambar dan menyimpan hasil skornya. Proses kalibrasi menggunakan image binary untuk mendapatkan titik tengah target dan membuat segmentasi skor berdasarkan suatu look up table sedangkan untuk pengenalan jejak laser dan peluru menggunakan color segmentation. Hasil penelitian menunjukkan tingkat akurasi 0.1. Penelitian yang dilakukan oleh D.J. Hou dkk (Hou, Song, & Soh, 2000), menggunakan pengenalan pola pada kertas target tembak dan jejak peluru dengan alur kerja sebagai berikut : Pemisahan setiap gambar jejak peluru dengan metode regional growth, Feature extraction dari gambar jejak peluru, Dengan menggunakan hasil ekstraksi dan normalisasi dari fitur gambar jejak peluru dilakukan pengklasifikasian pola dengan menggunakan RBF neural network yang
9
dikombinasikan dengan Fuzzy C-Means (FCM) clustering. Hasil penelitian menunjukkan kinerja sistem yang memuaskan dan dapat digunakan dalam sistem. Penelitian yang dilakukan oleh Bijan G. Mobasseri (Mobasseri, 1995), membandingkan metode penghitungan machine vision dengan metode acoustic dan manual. Sistem PSO dibagi menjadi tiga bagian, yaitu : Proses kalibrasi yang terdiri dari penyelarasan kamera / target, menjalankan algoritma chord bisection untuk mendapatkan titik tengah target, Deteksi jejak peluru dengan metode image subtraction, erosion dan pixel extraction, Penghitungan skor dengan mengukur perbedaan jarak menggunakan data citra yang didapat dari proses kalibrasi dan pendeteksian jejak peluru. Dari hasil pengujian, PSO dengan machine vision layak untuk digunakan dan dari sisi biaya yang dikeluarkan, dibandingkan dengan metode acoustic, metode machine vision lebih murah karena tidak memerlukan target tembak yang khusus. Dari beberapa kegiatan penelitian dengan topik sejenis di atas, penelitian yang menggunakan algoritma Template Matching adalah penelitian yang dilakukan oleh Xinnan Fan dkk. dan Ya-bei Yang dkk. Perbedaan yang akan dilakukan dengan penelitian-penelitian sebelumnya adalah penggunaan algoritma GrabCut, yang akan digunakan pada tahap background segmentation. Penggunaan algoritma GrabCut pada sistem PSO ini ditujukan untuk mengurangi dampak bayangan pada citra jejak peluru, sehingga diharapkan dapat meningkatkan akurasi pencarian jejak peluru ketika tahap Template Matching dilakukan. Adapun persamaannya dengan penelitian terdahulu secara garis besar terletak pada metode pre-processing yang akan digunakan pada tahap pengenalan dan penilaian skor menembak.
10
2.2. Olahraga Menembak Olahraga
menembak
merupakan
olahraga
yang
kompleks,
selain
membutuhkan kondisi fisik yang baik, diperlukan pula kemahiran teknik dan keadaan mental yang baik, sehingga seorang atlet menembak dapat membidik secara sempurna. International Olympic Committee (IOC) menunjuk International Shooting Sport Federation (ISSF) sebagai badan yang bertanggung jawab dalam mempromosikan, membuat aturan dan regulasi pada olahraga menembak. Untuk di Indonesia, olahraga menembak berada dalam tanggung jawab Pengurus Besar Persatuan Menembak dan Berburu Indonesia (PB Perbakin).
2.2.1. Kompetisi Olahraga Menembak Dalam Olimpiade ada 15 kelas yang dipertandingkan (KOI, 2008), terdiri dari : 1. Sembilan kelas Putra : − 10m air pistol (60 tembakan). − 10m air rifle (60 tembakan). − 25m rapid fire pistol (60 tembakan). − 50m pistol (60 tembakan). − 50m rifle 3 positions (3x40 tembakan). − 50m rifle prone (60 tembakan). − Double trap (150 target). − Skeet (125 target). − Trap (125 target).
11
2. Enam kelas Putri : − 10m air pistol (40 tembakan). − 10m air rifle (40 tembakan). − 25m pistol (30+30 tembakan). − 50m rifle 3 positions (3x20 tembakan). − Skeet (75 target). − Trap (75 target). Pertandingan menembak dibagi menjadi tiga grup yang berbeda : kelas rifle, pistol, dan shotgun. Pertandingan kelas pistol dan rifle dilaksanakan dengan jarak tembakan antara penembak dengan sasarannya sejauh 10 meter, 25 meter, dan 50 meter. Pada pertandingan kelas shotgun, peserta mengincar sasaran yang terbuat dari tanah liat yang diputar ke berbagai arah yang berbeda.
2.2.2. Perlengkapan Olahraga Menembak Perlengkapan olahraga menembak yang akan digunakan dalam penelitian ini, sebagaimana yang tercantum dalam buku Official Statutes Rules and Regulations (ISSF, 2009) adalah : 1. Senjata Laras Panjang (Air Long Rifle) sering juga disebut dengan senapan angin
adalah
senapan
yang
menggunakan
prinsip
pneumatic
yang
menembakkan proyektil dengan menggunakan tenaga udara atau sejenis gas tertentu yang dimampatkan. Senapan angin biasanya digunakan pada pertandingan olahraga menembak kelas 10m air rifle, 50m rifle dan hanya boleh diisi dengan satu peluru untuk setiap pembidikan.
12
Gambar 2.1. Tipikal Senjata Laras Panjang untuk Air Rifle Sumber : http://en.wikipedia.org/wiki/Air_rifle 2. Peluru (Pellet) adalah proyektil yang didorong oleh senapan atau pistol angin biasanya tidak mengandung bahan peledak, namun mampu membuat kerusakan dan penetrasi terhadap target yang dimaksud. Peluru senapan angin kaliber 4.5 mm (0.177 in) yang digunakan pada pertandingan 10m air rifle memiliki bagian depan hampir datar sehingga dapat meninggalkan jejak lubang yang bagus pada kertas target (tidak robek).
Gambar 2.2. Tipikal Peluru (Pellet) 4.5 mm (0.177 in) Sumber : http://en.wikipedia.org/wiki/Pellet_(air_gun) 3. Kertas Target (Target Paper) terdiri dari sebuah tanda hitam dan lingkaran yang bertujuan untuk mencetak skor. Skor dievaluasi setelah tembakan mengenai kertas target. Tergantung peraturan yang berlaku, pada pertandingan kelas 10m dan 50m air rifle, kertas target diganti untuk setiap tembakan. Kertas target dibagi menjadi beberapa jenis sesuai kelas yang dipertandingkan. Adapun kertas target yang akan digunakan dalam penelitian ini adalah kertas target untuk kelas 10m air rifle, memiliki ukuran panjang 170 mm x lebar 170 mm dan ditempatkan di atas dengan jarak 1.4 meter dari lantai.
13
Tabel 2.1. Ukuran Kertas Target 10m Air Rifle
Lingkaran
Dimensi Diameter
Warna
10
0.5 mm (±0.1 mm)
Hitam
9
5.5 mm (±0.1 mm)
Hitam
8
10.5 mm (±0.1 mm)
Hitam
7
15.5 mm (±0.1 mm)
Hitam
6
20.5 mm (±0.1 mm)
Hitam
5
25.5 mm (±0.1 mm)
Hitam
4
30.5 mm (±0.1 mm)
Hitam
3
35.5 mm (±0.1 mm)
Putih
2
40.5 mm (±0.1 mm)
Putih
1
45.5 mm (±0.1 mm)
Putih
Ketebalan garis lingkaran 0.1mm hingga 0.2mm
Gambar 2.3. Kertas Target 10m Air Rifle Sumber : http://en.wikipedia.org/wiki/File:10_m_Air_Rifle_target.svg
2.2.3. Fasilitas Olahraga Menembak Venue menembak yang merupakan fasilitas olahraga menembak didesain sedemikian rupa seperti minimal 5 station, panjang meja penembak 1 meter, jarak
14
penembak ke penonton minimal 5 meter. Ketinggian meja penembak 0.70-0.80 meter, meja juri atau operator berukuran panjang 3 meter x lebar 1.5 meter.
Gambar 2.4. Trap Range Sumber : Buku Official Statutes Rules and Regulations (ISSF) Untuk pencahayaan lampu di dalam ruangan venue menembak, memiliki persyaratan minimal 1500 lux pada sasaran dan 300-800 lux di atas penembak.
Gambar 2.5. Pengukuran Pencahayaan Venue Menembak Sumber : Buku Official Statutes Rules and Regulations (ISSF)
15
2.2.4. Sertifikasi Electronic Target System Agar sistem PSO dapat digunakan dalam kompetisi menembak yang resmi, maka sistem PSO harus mendapat sertifikasi dari badan ISSF (ISSF, 2009). Adapun tahapan untuk mendapatkan sertifikasinya dapat dilihat pada tabel 2.2 berikut. Tabel 2.2 Tahapan Untuk Mendapatkan Sertifikasi Sistem PSO Phase I
Phase II
Test for accuracy, specification and build standard test only Test under competition conditions and approved for some ISSF supervised Competitions / Championships Test under Major Competition Compatibility with ISSF
Phase III Result Service and approved for all ISSF supervised Competitions / Championships
2.2.5. Penilaian Skor Menembak Secara Manual Pada kompetisi menembak 10m Air rifle, untuk menilai skor menembak secara manual digunakan alat INWARD dan OUTWARD Gauge Scoring.
Gambar 2.6 Outward Gauge Scoring Sumber : buku Official Statutes Rules and Regulations (ISSF, 2009)
16
Inward untuk menilai skor 1 – 9 dari jejak peluru sedangkan outward untuk menilai skor 0.10 – 0.9 dari jejak peluru. Pada gambar 2.6, ilustrasi A, menggambarkan situasi jejak peluru dimana alat ukur berada di dalam ring 7, namun karena sisi lain dari alat (flange) berada pada ring 9, maka skor menembak adalah 9. Ilustrasi B menggambarkan situasi jejak peluru dimana alat ukut berada dalam ring 7 dan 6, namun karena sisi lain dari alat (flange) berada pada ring 9, maka skor menembak adalah 9.
Gambar 2.7 Eagle Eye Sumber : http://www.odcmp.org/0108/images/SGImg/EagleEye.jpg Gambar 2.7 menunjukkan alat bantu lain dalam memberikan peniliaian skor menembak secara manual / visual yang terdiri dari inward (nilai integer) dan outward (nilai decimal) dengan nilai 1 digit dibelakang koma. Alat ini sekaligus sebagai kaca pembesar untuk menilai seberapa jauh posisi jejak peluru dalam suatu ring target tembak.
17
2.3. Pengolahan Citra Digital Pengolahan citra adalah suatu metode yang digunakan untuk memproses atau memanipulasi gambar dalam bentuk 2 dimensi (Prasetyo, 2011). Pengolahan citra dapat juga dikatakan segala operasi untuk memperbaiki, menganalisa, atau mengubah suatu gambar. Konsep dasar pemrosesan suatu objek pada gambar menggunakan pengolahan citra diambil dari kemampuan indera penglihatan manusia yang selanjutnya dihubungkan dengan kemampuan otak manusia.
2.3.1. Gray-scaling Citra digital dapat diwakili oleh format warna RGB (Red-Green-Blue) untuk setiap titiknya, dimana setiap komponen warna memiliki batasan sebesar 1 byte. Jadi untuk masing-masing komponen R, G, dan B mempunyai variasi dari 0 sampai 255. Total variasi yang dapat dihasilkan untuk sistem dengan format warna RGB adalah 256 x 256 x 256 atau 16.777.216 jenis warna. Karena setiap komponen warna memiliki batasan sebesar 1 byte atau 8 bit, maka total untuk mempresentasikan warna RGB adalah 8+8+8 = 24 bit. Gray-level adalah tingkat warna abu-abu dari sebuah pixel, dapat juga dikatakan tingkat cahaya dari sebuah pixel (Prasetyo, 2011). Maksudnya nilai yang terkandung dalam pixel menunjukan tingkat terangnya pixel tersebut dari hitam ke putih. Biasanya ditetapkan nilainya antara 0 hingga 255 (untuk 256gray-level), dengan 0 adalah hitam dan 255 adalah putih. Karena hanya terbatas 1 byte saja maka untuk mempresentasikan nilai pixel cukup 8 bit saja. Gray-scale adalah gambar yang memiliki gray-level sebagai nilai dari tiap pixel-nya.
18
Gray-scaling adalah proses perubahan nilai pixel dari warna (RGB) menjadi gray-level (Prasetyo, 2011). Pada dasarnya proses ini dilakukan dengan meratakan nilai pixel dari 3 nilai RGB menjadi 1 nilai. Untuk memperoleh hasil yang lebih baik, nilai pixel tidak langsung dibagi menjadi 3 melainkan terdapat persentasi dari masing-masing nilai. Salah satu persentasi yang sering digunakan adalah 29,9% dari warna merah (Red), 58,7% dari warna hijau (Green), dan 11,4% dari warna biru (Blue). Nilai pixel didapat dari jumlah persentasi 3 nilai tersebut.
2.3.2. Model Warna HSV Model warna HSV mendefinisikan warna dalam terminologi Hue, Saturation dan Value. Keuntungan menggunakan HSV adalah terdapat warnawarna yang sama dengan yang ditangkap oleh indra manusia. Dimana karakteristik pokok dari warna tersebut adalah : 1. Hue : menyatakan warna sebenarnya, seperti merah, violet, dan kuning dan digunakan menentukan kemerahan (redness), kehijauan (greeness), dan sebagainya. 2. Saturation : kadang disebut chroma, adalah kemurnian atau kekuatan warna. 3. Value : kecerahan dari warna. Nilainya berkisar antara 0-100 %. Apabila nilainya 0 maka warnanya akan menjadi hitam, semakin besar nilai maka semakin cerah dan muncul variasi-variasi baru dari warna tersebut.
2.3.3. Dilasi dan Erosi Ada dua operasi dasar morphologi yaitu dilasi dan erosi. Kedua operasi dasar tersebut menjadi basis untuk membuat berbagai operasi morphologi yang
19
sangat berguna untuk pengolahan citra digital seperti opening, closing, hit and miss transform, thinning dan thickening. Operasi dilasi dilakukan untuk memperbesar ukuran segmen obyek dengan menambah lapisan disekeliling obyek. Terdapat 2 cara untuk melakukan operasi ini, yaitu dengan cara mengubah semua titik latar yang bertetangga dengan titik batas menjadi titik obyek, atau lebih mudahnya set setiap titik yang tetangganya adalah titik obyek menjadi titik obyek. Cara kedua yaitu dengan mengubah semua titik di sekeliling titik batas menjadi titik obyek, atau lebih mudahnya set semua titik tetangga sebuah titik obyek menjadi titik obyek. Operasi erosi adalah kebalikan dari operasi dilasi. Pada operasi ini, ukuran obyek diperkecil dengan mengikis sekeliling obyek. Cara yang dapat dilakukan juga ada 2. Cara pertama yaitu dengan mengubah semua titik batas menjadi titik latar dan cara kedua dengan menset semua titik disekeliling titik latar menjadi titik latar.
2.3.4. Rectification (Geometric Correction) Rectification (Geometric Correction) bertujuan merubah geometri sebuah citra berdasarkan proyeksi dari sebuah citra standar. Koreksi ini diperlukan karena citra yang dihasilkan oleh lensa optik selalu mempunyai masalah dengan distorsi geometri yang disebabkan oleh posisi relatif 3 dimensi antara kamera dengan obyek, distorsi lensa atau faktor lainnya (Cuiliu & Hong, 2011). Proses kalibrasi kamera dapat menggunakan citra papan catur maupun citra jala-jala lingkaran (grid circle). Pada penelitian ini tahap kalibrasi kamera akan menggunakan citra papan catur yang diperkenalkan oleh Janne Heikkila dan Olli
20
Silven (Heikkila & Silven, 1997). Dimana proses awal dari kalibrasi akan mendeteksi posisi dari sudut-sudut kotak papan catur, kemudian posisi sudut tadi diproyeksi ke posisi lain, sehingga distorsi geometri yang ada hilang. Hasil dari kalibrasi ini berupa matrik yang berisi nilai parameter intrinsik dan ekstrinsik dari kamera yang akan digunakan pada proses selanjutnya.
2.3.5. Image Subtraction Image subtraction adalah pengolahan citra berbasis operasi aritmatika, tujuan dari image subtraction adalah untuk mendapatkan citra hasil dengan cara mengurangi nilai pixel input pertama dengan nilai pixel input kedua.
Gambar 2.8 Operasi Image Subtraction Sumber : Buku Pengolahan Citra Digital dan Aplikasinya Menggunakan Matlab (Prasetyo, 2011)
2.3.6. Template Matching Template Matching (Brunelli, 2009) adalah sebuah teknik dalam pengolahan citra digital untuk menemukan bagian-bagian kecil dari gambar yang cocok dengan template gambar merupakan salah satu ide yang digunakan untuk menjelaskan bagaimana otak kita mengenali kembali bentuk-bentuk atau polapola. Template Matching dapat dibagi antara dua pendekatan, yaitu :
21
1. Pendekatan berbasis fitur Pendekatan berbasis fitur menggunakan fitur pencarian dan template gambar seperti tepi atau sudut, sebagai pembanding pengukuran matrik untuk menemukan lokasi Template Matching yang terbaik pada sumber gambar. Sebuah pendekatan berbasis fitur dapat dianggap sebagai pendekatan yang lebih efektif, jika template gambar memiliki fitur yang kuat jika pencocokan di pencarian gambar bisa diubah dengan cara tertentu. Karena pendekatan ini tidak mempertimbangkan keseluruhan dari template gambar, komputasi dapat lebih efisien ketika bekerja dengan sumber gambar beresolusi lebih besar, sebagai pendekatan alternatif, berbasis template, mungkin memerlukan pencarian titik-titik yang berpotensi untuk menentukan lokasi pencocokan yang terbaik. 2. Pendekatan berbasis template. Untuk template tanpa fitur yang kuat, atau ketika sebagian besar template gambar merupakan gambar yang cocok, sebuah pendekatan berbasis template mungkin efektif. Seperti disebutkan di atas, karena berbasis template, Template Matching berpotensi memerlukan sampling dari sejumlah besar titik, untuk mengurangi jumlah titik sampling dengan mengurangi resolusi pencarian dan template gambar oleh faktor yang sama dan melakukan operasi pada perampingan
gambar
yang
dihasilkan
(multiresolusi,
atau
piramida,
pengolahan citra), menyediakan pencarian titik data dalam pencarian gambar sehingga template tidak harus mempunyai pencarian titik data, atau kombinasi keduanya.
22
Pada penelitian ini Template Matching akan menggunakan algoritma Normalized Correlation Coefficient (NCC - Fast Normalized Cross-Correlation) yang dikembangkan oleh JP. Lewis (Lewis, 1995). Korelasi adalah alat penting dalam pengolahan citra, pengenalan pola, dan bidang lainnya. Korelasi antara dua sinyal (cross correlation) adalah pendekatan standar untuk mendeteksi fitur dalam suatu citra. Teknik Template Matching mencoba untuk menjawab beberapa variasi pertanyaan berikut : Apakah gambar berisi view tertentu dari beberapa fitur ?, jika demikian, di mana ?. Penggunaan Cross-Correlation untuk pencocokan template termotivasi oleh ukuran jarak (Euclidean distance).
(penjumlahan atas x, y dengan posisi fitur ada pada u, v) atau jika d2 diperluas menjadi
selalu bernilai konstan. Jika
mendekati nilai
konstan, maka tersisa Cross-Correlation
yang merupakan ukuran tingkat kemiripan antara fitur dengan citra.
2.3.6.1. Normalized Cross Correlation Jika energi citra yang dinyatakan dengan
ternyata tidak bernilai
konstan, pencocokan fitur dengan Cross-Correlation akan gagal. Sebagai contoh,
23
korelasi antara template dan area pencocokan yang sama persis dalam sebuah citra mungkin lebih sedikit jika dibandingkan dengan korelasi antara template dengan sebuah spot yang terang. Kelemahan lain dari Cross-Correlation adalah bahwa jangkauan c(u, v) tergantung pada ukuran template dan amplitudo template berikut citranya. Variasi dalam energi citra template dapat dikurangi dengan filter high-pass sebelum Cross-Correlation. Pada implementasi sebuah transformasi domain proses filter dapat dengan mudah ditambahkan ke proses frekuensi domain, meskipun pemilihan dalam memotong frekuensi jadi masalah tersendiri, pemotongan frekuensi yang terlalu rendah dapat membuat signifikan variasi energi dari citra, sebaliknya jika pemotongan frekuensi terlalu tinggi dapat menghapus informasi yang berguna pada saat proses pencocokan. Normalized Cross-Correlation mengatasi masalah ini dengan menormalisasi vektor citra dan template menjadi satuan panjang, dan menghasilkan koefisien korelasi seperti cosinus
…………
dimana
merupakan nilai mean dari template dan
dari f(x, y) dalam area suatu template.
(2.1)
merupakan nilai mean
24
2.3.6.2. Proses Komputasi Dengan mempertimbangkan pembilang pada persamaan (2.1) dan dengan asumsi
bahwa
kita
mempunyai
citra
dan
dimana nilai mean telah dihapus :
………………………
(2.2)
Untuk jendela pencarian ukuran M2 dan template dari N2 ukuran (2.2) membutuhkan sekitar N2(M - N + 1)2 untuk penambahan dan N2(M - N + 1)2 untuk perkalian. Persamaan (2.2) adalah konvolusi dari citra dengan template terbalik t' (-x,-y) dan dapat dihitung dengan ………………………. (2.3) dimana
adalah transformasi Fourier. Konjugasi kompleks menyelesaikan
pembalikan template melalui properti transformasi Fourier
.
Implementasi dari algoritma Fast Fourier Transform (FFT) umumnya memerlukan f ' dan t' yang dapat mempunyai nilai dari nol hingga perpangkatan dua. Kompleksitas dari perhitungan transform (2.3) dari 12M2log2M perkalian bilangan real dan penambahan bilangan real 12M2log2M. Ketika M jauh lebih besar daripada N, kompleksitas dari 'spatial' langsung pada perhitungan (2.3) adalah sekitar perkalian / penambahan N2M2, dan metode langsung lebih cepat daripada metode transformasi. Metode transformasi menjadi relatif lebih efisien ketika nilai N mendekati M dan dengan nilai M, N yang besar.
25
2.3.7. GrabCut Pada penelitian ini, tahap background segmentation akan menggunakan GrabCut yang dikembangkan oleh Rother dkk. (Rother, Kolmogorov, & Blake, 2004). GrabCut merupakan algoritma yang banyak digunakan dalam prosses segmentasi citra pada Computer Vision. GrabCut adalah algoritma iteratif yang menggabungkan statistik dan Graph Cut untuk membuat segmentasi 2D secara rinci dengan jumlah input yang sangat terbatas. Langkah-langkah dasar dalam algoritma GrabCut adalah sebagai berikut : 1. Tiga input yang digunakan, yaitu : bagian known (foreground dan background), bagian lain dari gambar sebagai unknown yang dapat berupa bagian dari foreground atau background. Pemilihan input biasanya dilakukan dengan memilih di sekitar obyek dan menandainya dengan kotak persegi panjang sebagai bagian unknown. Piksel luar persegi panjang ini adalah bagian known dan ditandai sebagai background. 2. Kemudian dibuat segmentasi citra awal, di mana piksel bagian unknown ditempatkan di foreground class dan semua piksel background bagian known diklasifikasikan sebagai background class. 3. Bagian foreground dan background dimodelkan sebagai Gaussian Mixture Models (GMMs) menggunakan algoritma clustering Orchard-Bouman. 4. Setiap foreground piksel menjadi komponen Gaussian dalam foreground GMMs. Piksel di bagian background diproses dengan proses ID yang sama dengan komponen background GMMs.
26
5. Setiap GMMs baru diambil dari kumpulan piksel yang dihasilkan pada langkah sebelumnya. 6. Sebuah graph dibangun dan graph cut digunakan untuk membuat klasifikasi piksel foreground dan background baru. 7. Ulangi langkah 4-6 sampai semua klasifikasi piksel menyatu.
2.3.7.1. Pemodelan Foreground dan Background Input awal dari foreground dan background yang diberikan oleh pengguna adalah sebuah kotak dalam obyek gambar. Piksel di luar kotak ini dinyatakan sebagai known background dan piksel di dalam kotak dinyatakan sebagai unknown. Dari data ini kita akan membuat sebuah model yang dapat kita pakai untuk menentukan apakah suatu piksel adalah foreground atau background. Dalam algoritma GrabCut kedua bagian tadi dinyatakan dengan komponen K dari multivariat Gaussian Mixture Models (GMM) sebanyak 2K komponen. Komponen K untuk known background dan komponen K untuk bagian yang seharusnya menjadi foreground. Komponen GMM mempunyai dimensi yang sama sebagai ruang warna (color space) dan berasal dari statistik warna dari setiap cluster. Untuk mendapatkan hasil segmentasi yang baik, sebaiknya dicari komponen dengan variasi yang tidak banyak, karena hal ini membuat proses cluster untuk memisahkan setiap komponen satu dengan yang lainnya menjadi lebih mudah. Proses clustering ini menggunakan algoritma clustering Orchard-Bouman. Pada awal proses clustering warna, parameter dari algoritma clustering adalah sejumlah cluster, K dan C1 sebagai cluster pertama.
27
1. Inisialisasi cluster pertama, C1 = Unknown ∪ Foreground. 2. Menghitung nilai mean, μ1, dan kovarian matrik
dari cluster C1.
3. For i = 2 to K do 4. Temukan cluster, Cn, yang mempunyai nilai eigen terbesar dan berasosiasi dengan vektor eigen en. 5. Pisahkan Cn menjadi dua set nilai mean proyeksi terhadap vektor eigen, dan update cluster awal dengan setengah bagian . 6. Hitung
dan
.
2.3.7.2. Graph Cut Graph cut dapat digunakan untuk memecahkan banyak masalah dasar dalam computer vision secara efisien, seperti image smoothing dan beberapa masalah yang dapat diformulasikan kedalam terminologi dari minimalisasi energi. Masalah minimalisasi energi dapat diformulasikan sebagai masalah maksimum aliran dalam suatu graph.
28
Gambar 2.9 Contoh Segmentasi Graph (Pemisahan Foreground dan Background)
Graph terdiri dari beberapa node ni dan semua node saling terhubung dan mempunyai tiap hubungan (link) mempunyai bobot, wij. Bobot menjelaskan seberapa kuat hubungan antara dua node. Min-cut antara dua node adalah cara untuk memisahkan graph menjadi dua bagian yang berbeda dengan usaha minimal dengan meminimalkan
dimana I adalah kumpulan dari link antar node
yang dipotong. Pada contoh di gambar 2.9, n1 akan diklasifikasikan sebagai foreground dan node-node lain sebagai background. `
2.3.7.3. Penggunaan GrabCut Graph terdiri dari dua bagian. Bagian pertama menjelaskan seberapa banyak setiap piksel, m dan n, saling terhubung dengan piksel di sekitarnya, N-links. Seberapa baik sebuah piksel terhubung dengan piksel di sekitarnya dihitung
29
dengan menggunakan formula (2.4) di bawah. Bagaimana setiap piksel terhubung satu sama lainnya tidak berubah selama iterasi berlangsung dan hal ini hanya diperlukan sekali saja pada saat proses dimulai. …………………………… (2.4) Bagian kedua dari graph terdiri dari hubungan (link) ke node foreground dan background, sumber dan posisi untuk memotong. Bobot dari setiap hubungan akan diberi label "labeling cost", L(m) untuk lable sebuah piksel m sebagai foreground atau background. Skema untu membuat bobot dari bagian graph dapat dilihat pada tabel berikut : Tabel 2.3 Skema Bobot Graph
Jika “labeling cost” melampaui maksimum jumlah bobot yang dapat dimiliki oleh suatu piksel dalam lingkungannya maka piksel tersebut akan diberi label sebagai kelas yang telah dipilih sebelumya. Spesifitas dari bobot untuk suatu piksel m dipilih dengan cara berikut.
Kita dapat memaksa suatu piksel untuk menjadi bagian dari foreground atau background. Dalam algoritma ini digunakan 8-neighborhood, sehingga dapat menggunakan
30
Nilai dari Dfore dan Dback adalah suatu fungsi yang dapat menyatakan bahwa piksel tersebut apakah merupakan bagian dari foreground atau background GMMs. Nilai dapat dihitung dengan formula berikut : ……….… (2.5) Dimana Dfore untuk komponen foreground Gaussian dan Dback untuk komponen background Gaussian.
