bab ii kajian pustaka - library.binus.ac.idlibrary.binus.ac.id/ecolls/ethesisdoc/bab2/tsa-2013-0027...
TRANSCRIPT
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
Dimensi Lingkaran 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 Test for accuracy, specification and build standard test only
Phase II Test under competition conditions and approved for some
ISSF supervised Competitions / Championships
Phase III
Test under Major Competition Compatibility with ISSF
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 256-
gray-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 warna-
warna 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 pola-
pola. 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
………… (2.1)
dimana merupakan nilai mean dari template dan merupakan nilai mean
dari f(x, y) dalam area suatu template.
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.