3
TINJAUAN PUSTAKA Dalam bab ini akan dibahas teori-teori yang mendasari penelitian ini. Dimulai dari teori dan konsep citra digital, deteksi pola lingkaran dengan Circle Hough Transform (CHT), ekstrasi ciri pola lingkaran menggunakan Two Dimension Principle Component Analysis (2DPCA) serta proses pengenalan roda kendaraan dengan Jaringan Syaraf Tiruan Propagasi Balik.
Citra Digital Citra digital merupakan sebuah larik (array) berisi nilai-nilai riil maupun kompleks yang dapat direpresentasikan dengan deretan bit tertentu, yang didefinisikan sebagai fungsi dua dimensi f(x,y) berukuran matriks M kali N, dimana M adalah baris dan N adalah kolom serta x dan y adalah pasangan koordinat spasial (Gonzales, et al 2004). Nilai f pada titik koordinat (x,y) disebut sebagai skala keabuan (gray level) atau intensitas dari citra digital pada koordinat koordinat tersebut. Apabila nilai x, y dan f secara keseluruhan berhingga dan bernilai diskrit maka citra tersebut merupakan citra digital. Citra digital direpresentasikan dalam bentuk matriks persegi yang mewakili ukuran dari citra tersebut. Misalkan terdapat sebuah citra digital dengan ukuran MxN, maka citra dapat direpresentasikan dalam sebuah matriks berukuran MxN sebagai berikut:
,
1,1
1,2
1,
,1
,2
,
..........................................(1)
Persamaan matriks diatas memperlihatkan irisan antara baris dan kolom (pada posisi x dan y) dikenal dengan nama picture elemen (pixel). Pixel memiliki intesitas yang dapat dinyatakan dengan bilangan dengan rentang tertentu, dari nilai minimum sampai maksimum. Jangkauan yang digunakan berbeda-beda tergantung dari jenis warnanya. Namun secara umum jangkauannya adalah 0 – 255.
4
Citra RGB dan Derajat Keabuan (Gray Scale) Citra RGB dan derajat keabuan merupakan format warna pada citra digital. Citra warna RGB memiliki kombinasi warna Red(R), Blue(B), dan Green(G) disetiap pikselnya. Setiap komponen RGB memiliki intensitas dengan nilai minimal 0 dan maksimal 255 (8 bit). Setiap piksel pada citra RGB membutuhkan 3 Byte untuk media penyimpanan, sehingga kemungkinan jumlah kombinasi citra RGB adalah lebih dari 16 juta warna. Citra keabuan merupakan citra digital yang hanya memiliki sebuah kanal pada setiap pixel, dengan kata lain bagian warna Red(R) sama dengan bagian Green(G) sama dengan bagian Blue(B) (Gonzales et al, 2004). Derajat keabuan merupakan warna abu dengan berbagai tingkatan dari warna hitam (minimum) ke putih (maksimum). Jumlah maksimum warna terdiri atas 4 bit dan 8 bit. Citra dengan derajat keabuan 4 bit memiliki 16 kemungkinan warna, yaitu 0 sampai 15. Setiap pixel citra dengan nilai intensitas keabuan 8 bit sehingga terdapat 256 kombinasi nilai dimulai dari 0 sampai dengan 255. Persamaan berikut memperlihatkan konversi citra RGB ke dalam citra keabuan (Qur’ania 2012) : ,
,
,
,
,
Persamaan (2) akan memetakan fungsi RGB menjadi fungsi keluaran
,
.......................................(2) yang merupakan nilai piksel citra
sebagai citra keabuan. Gambar 1
memperlihatkan perubahan nilai piksel RGB ke derajat keabuan. ,
R= 50 G= 60 B= 40 R= 55
R= 55 G= 70 B= 55 R= 55
R= 35 G= 50 B= 50 R= 45
R= 70 G= 80 B= 60 R= 60
G= 70
G= 65
G= 60
G= 30
B= 55
B= 45
B= 60
B= 45
R= 50
R= 50
R= 70
R= 70
G= 50
G= 60
G= 70
G= 45
B= 50
B= 40
B= 70
B= 50
Citra RGB
50
60
45
70
60
55
55
45
50
50
70
55
Citra keabuan
Gambar 1 Transformasi nilai piksel RGB ke citra keabuan.
5
Smoothing Smoothing citra masukan dilakukan dengan maksud untuk mengurangi respons sistem terhadap noise atau menyiapkan citra untuk proses segmentasi. Banyak jenis algoritma smoothing dengan menggunakan linear filter ataupun nonlinear filter. Smoothing dengan menggunakan linear filter mengacu pada Low Pass Filter (LPF). Penapis rata-rata (average filter) merupakan salahsatu LPF yang digunakan untuk mengurangi detil yang ‘irrelevant’ dalam suatu citra. Secara umum average filter dapat diberi bobot tertentu dengan maksud untuk mengurangi noise dalam proses smoothing. untuk menapis citra berukuran dengan filter mask (selubung penapis) terbobot ukuran
diberikan dalam
persamaan berikut: (Gonzales, et al 2002) ∑
, dengan
dan
0, 1, 2, … . , mask 3
∑ ∑
1 dan
5 dan matriks 3
,
,
∑
,
.....................................(3)
. persamaan diatas digunakan untuk 0, 1, 2, … . ,
1. Gambar 2 memperlihatkan filter
5 dengan nilai piksel yang sesuai dengan filter mask
tersebut (Gambar 3). W(-1,-2)
W(-1,-1)
W(-1,0)
W(-1,1)
W(-1,2)
W(0,-2)
W(0,-1)
W(0,0)
W(0,1)
W(0,2)
W(1,-2)
W(1,-1)
W(1,0)
W(1,1)
W(1,2)
Gambar 2 Filter mask 3 f(x-1,y-2)
f(x-1,y-1)
f(x-1,y)
f(x-1,y+1)
f(x-1,y+2)
f(x,y-2)
f(x,y-1)
f(x,y)
f(x,y+1)
f(x,y+2)
f(x+1,y-2)
f(x+1,y-1)
f(x+1,y)
Gambar 3 Matriks 3
f(x+1,y+1) f(x+1,y+2)
5 dengan filter mask yang sesuai.
5.
6
First Derivative Operator (Operator Derivatif Pertama) Dalam deteksi tepi, proses smoothing saja terkadang tidak cukup, untuk itu diperlukan kombinasi antara teknik smoothing dengan algoritma derivatif, hal ini dilakukan untuk meningkatkan akurasi serta mengurangi respons ganda terhadap suatu tepi. Derivatif pertama dalam pemrosesan citra menerapkan magnitudo gradien. Untuk fungsi
,
gradien dari f pada koordinat (x,y) didefinisikan sebagai
vektor kolom dua dimensi sebagai berikut: ...........................................................(4) Sedangkan untuk magnitudo dari vektor tersebut diberikan dalam persamaan berikut: / ⁄
..............................................(5)
Thresholding Walaupun citra awal telah mengalami smoothing dan filtering pada tahap awal, masih saja memungkinkan bagi keluaran tahapan sebelumnya mengalami kesalahan disebabkan oleh noise. Untuk mengatasi hal tersebut, maka dilakukan thresholding. Melalui penetapan nilai threshold (nilai ambang), maka nilai yang berada dibawah nilai ambang akan diabaikan.
Hough Transform Hough Transform (HT) merupakan suatu teknik ekstrasi fitur yang dipergunakan untuk menentukan lokasi suatu bentuk dalam citra. HT diperkenalkan oleh Paul Hough pada 1962. Rosenfeld (1969) menggunakannya sebagai salah satu algoritma pemrosesan citra, kemudian tahun 1972 Duda, et al menerapkan HT untuk mendeteksi garis dalam citra. HT telah dikembangkan untuk mendeteksi bentuk-bentuk umum dalam citra seperti lingkaran (circle), elips, dan parabola. Konsep dasar HT adalah
7
terdapat garis dan kurva potensial yang tak terhitung jumlahnya pada suatu citra yang melalui titik mana saja pada berbagai ukuran dan orientasi. Tujuan transformasi adalah untuk menemukan garis dan kurva yang melewati banyak titik-titik (features) dalam citra, yaitu garis dan kurva terdekat yang paling sesuai dengan data dalam citra. Kelebihan HT adalah tahan terhadap gangguan (noise robust) dan kemampuannya untuk mengekstrasi garis maupun kurva bahkan dalam suatu area dengan ketidakhadiran piksel (pixel gaps) (Argialas & Mavrantza 2004).
Circle Hough Transform (CHT) HT dapat didefinisikan menggunakan persamaan lingkaran. Persamaan lingkaran tersebut dapat dilihat pada persamaan 6. Persamaan ini mendefinisikan lingkaran sebagai semua titik ,
,
yang berada pada radius r terhadap titik pusat
. Persamaan lingkaran yang umum adalah: .......................................(6) Pada metode hough circle, setiap titik tepi mendefinisikan lingkaran dalam
ruang akumulator (accumulator space) dengan tiga buah parameter lingkaran ,
yaitu,
, dan r. Setiap titik tepi
,
dapat dihitung menggunakan persamaan
berikut: cos ...........................................................(7) sin
.....................................................(8)
Lingkaran ini diperoleh dari nilai kemungkinan radius dan lingkaran dipusatkan pada koordinat dari setiap titik tepi seperti diperlihatkan pada Gambar 4 berikut:
Gambar 4 Lingkaran dan titik-titik tepi lingkaran.
8
Algoritma Titik Tengah Tahapan-tahapan pencarian titik tengah dalam pencarian lingkaran dengan CHT adalah sebagai berikut : 1. Pencarian lingkaran dimulai dengan suatu titik pada gambar yang bukan background. 2. Diasumsikan titik tersebut terdapat pada tepi dari suatu lingkaran 3. Kemudian dilakukan proses pencarian titik tengah dari lingkaran tersebut, yaitu dengan langkah-langkah (Gambar 5) sebagai berikut:
Gambar 5 Pencarian titik tengah lingkaran. a. Telusuri gambar kebawah sampai menemukan tepi lingkaran sambil menghitung jarak ketepi lingkaran tersebut. Jika ada, maka diperoleh informasi mengenai titik tengah dari tinggi lingkaran, yaitu dari titik awal pergerakan ditambah dengan jarak/2. Jika tidak maka objek bukan lingkaran. b. Titik tengah yang diperoleh pada langkah sebelumnya belum tentu merupakan titik tengah dari lingkaran, tetapi hanya titik tengah dari tinggi lingkaran. Jadi selanjutnya akan dicari titik tengah dari lebar lingkaran. c. Dari titik tengah yang diperoleh pada (b), telusuri gambar ke kanan sampai menemukan tepi sambil menghitung jarak ke tepi lingkaran tersebut. Jika ada, maka diperoleh informasi mengenai titik tengah dari lebar lingkaran, yaitu dari titik awal pergerakan ditambah dengan jarak/2. Jika tidak, maka objek bukan lingkaran.
9
d. Diperoleh informasi titik tengah dan radius dari objek tersebut. 4. Jika radius lebih besar dari threshold, maka dilakukan identifikasi objek. 5. Identifikasi objek dilakukan sebagai berikut (Gambar 6) :
Gambar 6 Identifikasi objek. a. Lakukan rotasi 3600 berlawanan arah jarum jam, yaitu dengan menggunakan loop. b. Untuk setiap iterasi, hitung titik
,
, yaitu titik yang berjarak radius
r dari titik pusat dan memiliki sudut yang bersesuaian dengan ietarsi yang dilakukan. c. Pada titik tersebut dan pada n-tetangga disekitarnya (n adalah toleransi ketetanggaan), dilakukan pemeriksaan. Nilai n ini bergantung pada radius objek yaitu, semakin besar radius objek, maka semakin besar nilai n, dan sebaliknya. Jika salah satu dari titik tersebut merupakan titik tepi, maka iterasi dilanjutkan. Jika tidak satupun dari titik-titik tersebut yang merupakan titik tepi, maka objek bukan lingkaran, d. Jika iterasi berakhir dengan sukses, maka objek adalah lingkaran.
Two Dimension Principal Component Analysis (2DPCA) Principal Component Analysis (PCA) merupakan salah satu metode analisis peubah ganda yang mereduksi dimensi data tanpa harus kehilangan informasi yang berarti (Buono & Irmansyah 2009). Peubah hasil transformasi merupakan kombinasi linear dari peubah asli dan tidak terkorelasi antar sesamanya, serta tersusun berdasar informasi yang dimilikinya. PCA merupakan
10
ekstrasi fitur yang digunakan secara luas dalam pengolahan sinyal dan pengenalan pola.
Sirovich
dan
Kirby
pertama
kali
menggunakan
PCA
dalam
merepresentasikan citra wajah orang (Yang, et al 2004). Menurut Yang, et al teknik 2DPCA memiliki kelebihan dibandingkan dengan teknik PCA (eigenfaces), diantaranya yaitu 2DPCA didasarkan pada matriks citra sehingga lebih sederhana dan straighforward untuk digunakan pada ekstrasi fitur citra. Selain itu, 2DPCA lebih baik dari PCA dalam hal keakuratan pengenalan pada semua eksperimen dan secara komputasional lebih efisien daripada PCA dan dapat meningkatkan kecepatan ekstrasi fitur citra secara signifikan. Dalam teknik proyeksi citra dengan 2D-PCA, sebuah citra berdimensi akan dibaca sebagai matriks A berdimensi
dan tidak diubah
menjadi bentuk vektor. matriks A ini ditransformasi menggunakan matriks menjadi Y sebagai berikut, (Yang, et al 2004): dengan
................................(9)
Permasalahannya adalah bagaimana menemukan matriks transformasi Q yang memaksimalkan persebaran Y. Persebaran Y dapat dikarakterisasi oleh teras matriks koragam, S yang dirumuskan sebagai: ...................................(10)
Dan teras matriks S adalah: ....................(11) Dicari nilai: .................................(12) G dihitung dari sampel citra pelatihan. Anggap terdapat M citra pelatihan, ∑
..................................(13)
Oleh karena itu matrik Q yang dipilih adalah : ,
dengan
,
,
… .,
merupakan vektor ciri yang bersesuaian dengan akar ciri terbesar ke i
dari matriks G.
11
Jaringan Syaraf Tiruan (JST) Menurut Alexander dan Morton dalam (Haykin S 1994), Jaringan Syaraf Tiruan (JST) adalah prosesor tersebar paralel (paralel distributed processor) yang sangat besar dan memiliki kecenderungan untuk menyimpan pengetahuan yang bersifat pengalaman dan membuatnya siap untuk digunakan. JST menyerupai otak manusia, khususnya dalam hal pengetahuan yang diperoleh serta kekuatan hubungan antar sel syaraf (neuron) yang disebut bobotbobot sinapsis. Sel neuron merupakan dasar dari JST. Model neuron terdiri atas 3 elemen penting seperti dalam Haykin 1994, sebagai berikut : 1. Sekumpulan sinapsis atau jalur hubungan antar sel. Setiap sinapsis memiliki bobot tertentu (wk1, wk2, ..., wkp). 2. Adder untuk menjumlahkan sinyal-sinyal input yang telah diberi bobot sinapsis. Operasi penjumlahan mengikuti aturan linier combiner. 3. Fungsi aktivasi untuk membatasi amplitudo keluaran dari setiap neuron.
Gambar 7 Model matematis nonlinier dari neuron dengan bias.
Gambar 7 memperlihatkan model dari suatu neuron (Haykin 1994). Sinyal masukan dinyatakan sebagai x1, x2, ..., x3; wk adalah bias untuk memperbesar nilai masukan; vk merupakan keluaran dari linier combiner. aktivasi dan yk adalah keluaran dari neuron.
(v) merupakan fungsi
12
Jaringan Syaraf Tiruan Propagasi balik Salah satu arsitektur yang banyak digunakan adalah multilayer feedforward network. Secara umum terdiri dari beberapa unit neuron yaitu lapisan masukan, satu atau lebih lapisan tersembunyi (hidden layer) dan sebuah lapisan keluaran. Sinyal masukan dipropagasikan ke arah depan (ke lapisan keluaran). Jenis jaringan ini adalah hasil generalisasi dari arsitektur perceptron satu lapis, dikenal sebagai multilayer perceptrons (MLPs). Jaringan multilayer disebut sebagai jaringan propagasi balik (backpropagation), jika pada tahapan pelatihan menggunakan metode propagasi balik. Jaringan Propagasi Balik ditemukan pertama kali oleh Rumelhart, et al, pada Tahun 1988 melalui beberapa penelitian indenpenden (Fauset 1994). Propagasi balik merupakan algoritma pembelajaran yang terawasi (supervised learning). Algoritma ini menggunakan error output untuk mengubah nilai bobotbobotnya dalam arah mundur (backward). Propagasi balik (ke lapisan masukan) terjadi setelah jaringan menghasilkan keluaran yang mengandung error. Pada fase ini seluruh bobot sinapsis (yang tidak memiliki aktivasi nol) dalam jaringan akan disesuaikan untuk mengkoreksi error yang terjadi (error correction rule). Untuk pelatihan jaringan, pasangan fase propagasi ke depan dan balik dilakukan secara berulang untuk satu set data latihan, kemudian diulangi untuk sejumlah epoch sampai didapatkan error terkecil atau nol.
v11
X!
W11
Z1
v12
v21
Y1
W12
v13
W13
X2 . . . . .
W21
v22
Z3
v23
Y2 W23
v31
W31 v32
X3 wn Input
v33
W32
Z5 Hidden Layer
W33
Y3 Output
Gambar 8 Arsitektur Jaringan Syaraf Tiruan Propagasi Balik.
13
Gambar 8 memperlihatkan arsitektur propagasi balik dengan sebuah lapisan tersembunyi (Fauset 1994). Bias pada lapisan keluaran dinyatakan sebagai wok dan bias pada lapisan tersembunyi dinyatakan sebagai voj. Bias-bias ini berfungsi seperti bobot, yang selalu bernilai +1. Pada lapisan keluaran, nilai bobot dinyatakan sebagai wjk sedangkan nilai bobot lapisan masukan dinyatakan sebagai vij.
Fungsi Aktivasi Menurut Fauset, fungsi aktivasi yang digunakan sebaiknya memiliki nilai kontinu, differentiable, dan tidak turun secara monotik (monotically nondecreasing). Fungsi aktivasi yang digunakan dalam JST dan dilatih dengan propagasi balik berupa fungsi Sigmoid biner ataupun Sigmoid Bipolar. Pada fungsi sigmoid biner memiliki cakupan nilai 0 sampai dengan 1. Oleh karena itu, fungsi ini digunakan untuk jaringan syaraf yang membutuhkan nilai keluaran yang terletak pada interval 0 sampai dengan 1. Namun dapat juga digunakan untuk keluaran yang bernilai 0 atau 1. Persamaan 14 dan persamaan 15 merupakan persamaan untuk fungsi sigmoid biner, (Fauset 1994) : 1 1
...............................................................(14) 1
1
1
........................................(15)
Gambar 9 memperlihatkan fungsi aktivasi sigmoid biner dengan range [0,1]
Gambar 9 Fungsi aktivasi sigmoid biner dengan range (0,1).
Algoritma Pelatihan Dalam algoritma propagasi balik menggunakan dua tahapan yaitu: tahapan perhitungan maju (feedforward) untuk menghitung error antara keluaran aktual dengan keluaran yang menjadi target; dan tahapan perhitungan mundur
14
(backward) yang mempropagasikan balik error tersebut dan memperbaiki bobotbobot sinapsis pada semua neuron yang ada. Berikut adalah algoritma propagasi balik, (Fauset 1994): Langkah 0.
Inisialisasi bobot (bangkitkan nilai random yang cukup kecil).
Langkah 1.
Kerjakan langkah 2 – 9, selama kondisi berhenti bernilai FALSE.
Langkah 2.
Kerjakan langkah 3 – 8, Untuk setiap pasangan elemen pelatihan.
Perhitungan maju: Langkah 3.
Setiap unit masukan (Xi, i = 1,2,3,.., n) menerima sinyal masukan xi dan menyebarkan sinyal tersebut ke seluruh unit pada lapisan tersembunyi.
Langkah 4.
-
Setiap unit tersembunyi (Zj, j = 1,2,..., p) menjumlahkan setiap sinyal yang memiliki bobot berikut: ∑
_ -
........................................ (16)
Gunakan fungsi aktivasi untuk menghitung sinyal keluaran: ,............................................................(17) dan mengirimkan sinyal ini ke seluruh unit pada lapisan keluaran.
Langkah 5.
-
Setiap unit keluaran (Yk, k = 1,....., m) menjumlahkan sinyal-sinyal masukan terbobot, sebagai berikut: ∑
,
......................................(18)
dan fungsi aktivasi digunakan untuk menghitung sinyal keluaran: _
...........................................................(19)
Penghitungan error (propagasi balik) Langkah 6.
-
Setiap unit keluaran (Yk, k = 1,....., m) menerima pola target yang berhubungan dengan pola pelatihan pada masukan, hitung informasi error sebagai berikut: .............................................(20)
15
Dengan δk merupakan informasi error untuk bobot wjk pada unit keluaran Yk . Sementara tk adalah vektor target keluaran, -
Kemudian
hitung
koreksi
bobot
(yang
nantinya
digunakan untuk memperbaiki wjk): ∆
...........................................................(21) Dengan α merupakan laju pembelajaran,
-
Kemudian hitung koreksi bias (yang nantinya digunakan untuk memperbaiki w0k):
∆
..............................................................(22) dan mengirimkan δk ke neuron dilapisan bawahnya (lapisan tersembunyi).
Langkah 7.
-
Setiap neuron pada lapisan tersembunyi (Zj, j = 1 ,..., p) menjumlahkan masukan deltanya (dari neuron-neuron yang berada pada lapisan diatasnya, lapisan keluaran): ∑
......................................................(23)
Kalikan nilai ini dengan fungsi aktivasinya untuk menghitung informasi error: _
......................................................(24)
δj adalah koreksi error untuk vij -
Hitung koreksi bobot (digunakan untuk memperbaiki vij)
∆ -
............................................................(25) Hitung koreksi bias (digunakan untuk memperbaiki v0j)
∆
................................................................(26)
Perbaiki semua bobot dan bias: Langkah 8
-
Setiap unit keluaran (Yk, k = 1, ..., m) memperbaiki bias dan bobotnya (j = 0,1,2,3, ..., p): ∆
-
..............................(27)
Setiap unit tersembunyi (Zj, j = 1 ,..., p) memperbaiki bias dan bobotnya (i = 0,1,..., n): ∆
.................................(38)
16
Langkah 9
Uji kondisi berhenti
Satu epoch adalah satu putaran (cycle) untuk keseluruhan langkah pada tahapan pelatihan. Pada dasarnya dibutuhkan banyak epoch untuk pelatihan jaringan propagasi balik. Pelatihan dilakukan secara berulang-ulang hingga jumlah siklus tertentu atau telah mencapai MSE (Mean Square Error) yang diinginkan.
Kejadian Biner (Binary Events) Pengukuran kinerja (performance measures) merupakan subset dari pengukuran verifikasi yang fokus pada hubungan antara prediksi dan pengamatan. Kejadian biner memiliki empat kemungkinan keluaran seperti diperlihatkan dalam Tabel 1 (Mason 2003). Tabel 1 Empat kemungkinan keluaran pada kejadian biner Prediksi
Pengamatan Ya
Tidak
Ya
Hit (a)
False Alarm (b)
Tidak
Miss (c)
Correct Rejection (d)
Tabel 1 menyajikan hubungan pengamatan dan prediksi dengan empat kemungkinan keluaran. Hit merupakan nilai yang diperoleh dari hasil pengamatan terhadap suatu objek benar dan prediksi yang ditentukan bernilai benar. False Alarm diperoleh jika objek yang diamati bernilai salah namun prediksi bernilai benar. Miss berkebalikan dengan false alarm, yaitu pengamatan bernilai benar namun prediksi bernilai salah. Terakhir, correct rejection hasil pengamatan bernilai salah dan nilai prediksinya juga salah, artinya objek yang salah diprediksi salah (mengandung nilai kebenaran dan biasanya kebenaran ini tidak digunakan). Penghitungan kejadian biner yang mempengaruhi prediksi adalah sebagai (Mason 2003) : Hit rate (Nilai kebenaran prediksi) = Miss =
...........................................(39)
...........................................................................................(40)
17
False Alarm Rate =
......................................................................(41)
Correct Rejection =
.......................................................................(42)
