BAB 2 LANDASAN TEORI
Landasan teori ini secara umum menyajikan sejumlah teori yang relevan dengan penulisan skripsi ini. Kerangka teori ini disajikan berurutan sejalan dengan permasalahan yang dibahas pada skripsi ini. Diharapkan dengan disajikannya landasan teori ini, pembaca dapat memahami skripsi ini dengan teori-teori yang dikemukan pada bagian ini.
2.1. Biometrik Model Teknik informasi secara biometrik mempunyai lima (5) tahapan proses yang harus dilalui. Tahapan tersebut adalah pengambilan data, proses signal, penyimpanan data, pencocokkan, dan keputusan (ISO, 2006). Gambar 2.1 menunjukan tahapan-tahapan tersebut. Penelitian ini berfokus pada tahapan proses signal sampai tahapan keputusan.
7
Gambar 2.1 Biometrik Model (ISO, 2006) 2.2. Sidik Jari Sidik jari setiap orang mempunyai perbedaan bahkan pada orang kembar sekalipun (Jain, Prabhakar, dan Pankanti, 2002). Hal ini membuat sidik jari tepat digunakan dalam teknologi biometrik. Keunggulan lainnya dari sidik jari adalah kepraktisannya dan ketahanannya. Menurut Ashbaugh (1991), sidik jari (fingerprint) adalah hasil reproduksi tapak jari baik yang sengaja diambil, dicapkan dengan tinta, maupun bekas yang ditinggalkan pada benda karena pernah tersentuh kulit telapak tangan atau kaki. Kulit telapak adalah kulit pada bagian telapak tangan mulai dari pangkal pergelangan sampai kesemua ujung jari, dan kulit bagian dari telapak kaki mulai dari tumit sampai ke ujung jari yang mana pada daerah tersebut terdapat garis halus menonjol yang keluar satu sama lain yang
8
dipisahkan oleh celah atau alur yang membentuk struktur tertentu. Pada gambar 2.2 dapat dilihat contoh sidik jari.
Gambar 2.2 Sidik Jari 2.3. Pengenalan Pola Dalam skripsi ini, akan difokuskan pada pengenalan pola (pattern recognition). Pengenalan pola sesungguhnya telah lama ada dan telah mengalami perkembangan terus menerus dimulai dari pengenalan pola secara manual kemudian menjadi pengenalan pola modern dengan menggunakan komputer. Inti dari pengenalan pola adalah proses mengekstraksi ciri-ciri suatu objek dan proses mengklasifikasikan ciri-ciri tersebut. Kedua proses tersebut dapat dilakukan dengan menggunakan berbagai macam metode. Tentunya metode yang dipilih harus memiliki tingkat akurasi yang tinggi yang berarti secara manual (oleh manusia) tidak dapat dikenali tetapi bila menggunakan salah suatu metode tersebut masih dapat dikenali. Selain itu metode tersebut harus dapat diimplementasikan dengan algoritma komputer. Dalam skripsi ini, untuk proses ekstraksi ciri dipilih transformasi wavelet dan untuk proses klasifikasi ciri dipilih Jaringan Syaraf Tiruan yaitu Backpropagation.
9
Dalam Wijaya dan Kanata (2004) telah diuraikan mengenai pengenalan citra sidik jari berbasis transformasi wavelet dan jaringan syaraf tiruan dengan bantuan perangkat lunak Matlab. Dalam makalah tersebut dibahas mengenai berbagai macam jenis wavelet dan unjuk kerjanya dalam mengekstraksi ciri citra sidik jari. Tetapi makalah ini, belum membahas mengenai bagaimana implementasinya dalam perangkat lunak. Di sisi lain dalam Antowiak dan Chalansinska-Macukow (2003), telah dibuat perangkat keras untuk mengenali citra sidik jari berbasis transformasi wavelet dan jaringan syaraf tiruan. Dalam makalah ini, dibahas implementasi transformasi wavelet secara optis dan implementasi Jaringan Syaraf Tiruan secara elektronis. Selain kurangnya fleksibilitas dalam menggunakan berbagai macam metode, implementasi dalam perangkat keras ini membutuhkan dana yang cukup besar. Yang diajukan dalam skripsi ini adalah implementasi perangkat lunak dalam suatu platform terbuka (open platform) sehingga dapat dikembangkan dalam komunitas terbuka terutama di Indonesia. Hal ini dimaksudkan untuk memicu penelitian dan penerapan biometrik lebih lanjut di Indonesia. Dalam pustaka yang ada juga terdapat isu bagaimana mempersingkat proses pengenalan pola ini. Umumnya dengan menjadikan pengenalan pola menjadi satu tahap saja, seperti dalam Allah (2004). Dalam makalah ini proses ekstraksi ciri dan proses klasifikasi digabungkan menjadi satu dengan memodifikasi Jaringan Syaraf Tiruan menjadi dua kategori yaitu backward dan feed-forward. Sedangkan dalam Thomas (2000), modifikasi Jaringan Syaraf Tiruan dilakukan dengan dua tahap yaitu diaplikasikan secara lokal terlebih dahulu dan baru selanjutnya secara global.
10
2.4. Teori Dasar 2.4.1. Pengolahan Citra (Image Processing) Pengolahan citra (image processing) bertujuan untuk memperbaiki kualitas citra menjadi lebih baik sehingga lebih mudah dipahami atau diinterpretasi, baik oleh manusia ataupun komputer. Agar dapat diolah oleh komputer, maka suatu citra harus direpresentasikan secara numerik dengan nilai-nilai diskrit. Representasi citra dari fungsi malar (kontinu) menjadi nilai–nilai diskrit disebut digitalisasi. Citra yang dihasilkan inilah yang disebut citra digital (digital image). Untuk meningkatkan mutu suatu citra, kita harus mengeliminasi noise yang tidak diinginkan dari citra tersebut. Selain itu kita juga harus menjaga detail yang tetap ingin ditampilkan pada citra. Noise pada suatu citra digital bisa disebabkan oleh beberapa hal, seperti citra analog yang telah memiliki noise. Metode yang digunakan dalam skripsi ini adalah dengan metode thresholding. Thresholding adalah suatu metode untuk membantu menghilangkan noise dengan mengubah citra digital menjadi citra biner. Untuk menentukan thresholding dibutuhkan nilai ambang (threshold value) sebagai penentu apakah suatu piksel diubah menjadi warna putih atau warna hitam. Jika nilai piksel lebih besar dari nilai ambang, piksel tersebut akan diubah menjadi warna putih, sebaliknya akan menjadi warna hitam. Untuk menentukan nilai ambang digunakankan metode adaptive threshold. Metode ini menjumlahkan seluruh nilai piksel yang ada pada citra, dan kemudian membaginya dengan luas dari citra tersebut. Hasil dari perhitungan tersebut digunakan sebagai nilai ambang.
11
2.4.2. Pendekatan Non Minutiae Pada program yang dikembangkan ini menggunakan pendekatan Non Minutiae, dan metode yang digunakan adalah transformasi wavelet. Transformasi wavelet merupakan metode yang biasa digunakan untuk menyajikan data, fungsi atau operator ke dalam komponen-komponen frekuensi yang berlainan, dan kemudian mengkaji setiap komponen dengan suatu resolusi yang sesuai dengan skalanya. Transformasi wavelet mempunyai kemampuan membawa keluar ciri-ciri atau karakteristik khusus dari citra yang diteliti.
2.4.2.1. Transformasi Wavelet Dalam skripsi ini perangkat lunak yang dikembangkan menggunakan algoritma Discrete Haar Wavelet Transformation untuk mengekstraksi ciri-ciri khusus. Wavelet merupakan sebuah basis. Basis wavelet berasal dari sebuah fungsi penskalaan atau dikatakan juga sebuah scaling function. Scaling function memiliki sifat yaitu dapat disusun dari sejumlah salinan dirinya yang telah didilasikan, ditranslasikan dan diskalakan. Fungsi ini diturunkan dari persamaan dilasi (dilation equation), yang dianggap sebagai dasar dari teori wavelet. Persamaan dilasi berbunyi demikian :
φ ( x) = ∑ ck φ (2 x − k ) …………….. (2.1) dari persamaan scaling function ini dapat dibentuk persamaan wavelet yang pertama (atau disebut juga mother wavelet), dengan bentuk sebagai berikut :
12
ϕ 0 ( x) = ∑ (−1) k c1− k φ (2 x − k ) ………………(2.2) k
Dari mother wavelet ini kemudian dapat dibentuk wavelet berikutnya (ψ1, ψ2 dan seterusnya) dengan cara mendilasikan (memampatkan atau meregangkan) dan menggeser mother wavelet. Scaling function yang dapat membentuk wavelet bermacam-macam jenisnya. Berdasarkan scaling function inilah basis wavelet memiliki nama yang berbeda-beda. a. Wavelet Haar memiliki scaling function dengan koefisien c0 = c1 = 1. b. Wavelet Daubechies dengan 4 koefisien (DB4) memiliki scaling function dengan koefisien c0 = (1+√3)/4, c1 = (3+√3)/4, c2 = (3-√3)/4, c3 = (1-√3)/4
Untuk lebih memperjelas teori dari wavelet, mari kita lihat contoh wavelet Haar berikut ini. Wavelet Haar dapat dijelaskan dalam ruang vektor 4 dimensi. Basis paling sederhana yang sudah sering kita gunakan adalah basis orthonormal sebagai berikut : ⎡1 ⎤ ⎡0 ⎤ ⎡0 ⎤ ⎡0 ⎤ ⎢0 ⎥ ⎢1 ⎥ ⎢0 ⎥ ⎢0 ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ v0 = ,v = ,v = ,v = ⎢ ⎥ ⎢0⎥ 1 ⎢0⎥ 2 ⎢1⎥ 3 ⎢0⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣0 ⎦ ⎣0 ⎦ ⎣0 ⎦ ⎣1 ⎦ Wavelet Haar juga merentang ruang vektor 4 dimensi dengan vektor-vektor basis sebagai berikut :
13
⎡0⎤ ⎡1⎤ ⎡1⎤ ⎡1⎤ ⎢1⎥ ⎢1⎥ ⎢− 1⎥ ⎢0⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ h0 = ,h = ,h = ,h = ⎢ ⎥ ⎢1⎥ 1 ⎢− 1⎥ 2 ⎢ 0 ⎥ 3 ⎢ 1 ⎥ ⎢⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣− 1⎦ ⎣0⎦ ⎣− 1⎦ ⎣1⎦ yang bila digambarkan dalam bentuk sinyal akan berbentuk seperti pada gambar 2.3 dan tabel 2.1 :
h0
h1
h2
h3
Gambar 2.3 Wavelet Haar dalam Bentuk Sinyal
Tabel 2.1 Wavelet Haar dalam Bentuk Sinyal dan Vektor
14
Jika kita menggunakan basis orthonormal v0, v1, v2, dan v3, mudah bagi kita untuk merepresentasikan suatu vektor sebagai kombinasi linier dari v0, v1, v2, dan v3. Misalkan kita memiliki vektor ⎡6⎤ ⎢4⎥ x=⎢ ⎥ ⎢− 7 ⎥ ⎢ ⎥ ⎣5⎦ Jika kita ingin merepresentasikan vektor x tersebut dalam bentuk x = a v0 + b v1 + c v2 + d v3 ……………………….. (2.3) maka dengan mudah kita dapat menemukan bahwa a = 6, b = 4, c = -7, d = 5. Sekarang bagaimana caranya merepresentasikan suatu vektor sebagai kombinasi linier dari vektor-vektor dalam wavelet Haar ? Atau dengan kata lain, bagaimana kita menentukan nilai a,b,c dan d dalam persamaan berikut ini :
⎡ x0 ⎤ ⎡1⎤ ⎡1⎤ ⎡1⎤ ⎢x ⎥ ⎢1⎥ ⎢1⎥ ⎢ ⎥ ⎢ 1 ⎥ = a ⎢ ⎥ + b ⎢ ⎥ + c ⎢− 1⎥ + d ⎢ x2 ⎥ ⎢1⎥ ⎢− 1⎥ ⎢0⎥ ⎢ ⎥ ⎢⎥ ⎢ ⎥ ⎢ ⎥ ⎣1⎦ ⎣− 1⎦ ⎣0⎦ ⎣ x3 ⎦
⎡0⎤ ⎢0⎥ ⎢ ⎥ ……………………. (2.4) ⎢1⎥ ⎢ ⎥ ⎣− 1⎦
dengan sedikit pengetahuan matematis, kita dapat menurunkan persamaan-persamaan berikut ini dari persamaan (2.4) di atas : x0 = a + b + c x1 = a + b – c x2 = a – b
+d
x3 = a – b
–d
15
sehingga kemudian kita dapatkan : x2 – x3 = 2d x0 – x1 = 2c (x0 + x1) – (x2 + x3) = 4b (x0 + x1) + (x2 + x3) = 4a Dengan demikian dapat diambil kesimpulan bahwa d = ½ (x2 – x3) c = ½ (x0 – x1) b = ½ ( ½ (x0 + x1) – ½ (x2 + x3)) a = ½ ( ½ (x0 + x1) + ½ (x2 + x3)) Terlihat bahwa sebenarnya koefisien-koefisian a,b,c,d dapat diperoleh dari operasi averaging dan differencing terhadap nilai x0, x1, x2 dan x3 dengan aturan tertentu. Stephane Mallat kemudian memperkenalkan cara mudah menghitung koefisien a, b, c dan d dengan cara yang dikenal dengan algoritma piramida Mallat. Algoritma tersebut dapat ditunjukkan dengan gambar berikut. L L L aj ⎯ ⎯→ a j −1 ⎯ ⎯→ a j − 2 ... ⎯ ⎯→ a0 H
H
H
d j −1
d j −2
d0
dimana aj adalah vektor awal dengan ukuran 2j, dan koefisien a, b, c, d dapat diperoleh dari aproksimasi a0 detail-detail d0, d1 dan seterusnya. Matriks L dan H masing masing adalah matriks lowpass (averaging) dan highpass (differencing) dengan bentuk:
16
L=
⎡ c0 ⎢ 1⎢ . 2⎢ . ⎢ ⎣⎢.c 2
c1
c2
c3
c0
c1
... c2
c3
...
. . c3
c0
c1
c2 c0
.
⎤ ⎥ ⎥ ⎥ c3 ⎥ c1 ⎦ ⎥
H =
⎡c3 ⎢ 1⎢ . 2⎢ . ⎢ ⎣⎢.c1
− c2
c1 c3
− c0 − c2
... c1 .
− c0 .
− c0
... c3
− c2
.
c1 c3
⎤ ⎥ ⎥ ⎥ − c0 ⎥ − c2 ⎦ ⎥
Matriks L dan H untuk basis Haar dimana c0 = c1 = 1 adalah sebagai berikut : ⎡ 12 L=⎢ ⎣0
1
2
0
0 1
2
0⎤ 1 ⎥ 2⎦
⎡ 12 − 12 H =⎢ 0 ⎣0
0 1
2
0 ⎤ − 1 2 ⎥⎦
Proses mencari koefisien a, b, c dan d seperti ini disebut dengan proses dekomposisi. Sebagai contoh, untuk vektor x di atas kita akan dekomposisi menjadi: ⎡6⎤ 1 ⎤ ⎡1 ⎢ 4 ⎥ L = ⎢ 2 2 10 10 ⎥ ⎡ ⎤ 1 ] ⎥ 0 0 ⎢ L =[ 1 ⎢ 5 ⎥ 2 ⎦ ⎣ 2 2 a 2 = ⎢ ⎥ ⎯⎯ ⎯⎯⎯ ⎯2→ a 1 = ⎢ ⎥ ⎯⎯ ⎯ ⎯ → a 0 = [2] ⎢ − 1⎥ ⎢− 7 ⎥ ⎣ ⎦ ⎢ ⎥ ⎣5⎦ ⎡ 12 − 12 0 0 ⎤ − 12] H = H = [1 2 ⎢⎣ 0 0 12 − 12 ⎥⎦ ⎡1⎤ d1 = ⎢ ⎥ ⎣− 6⎦
d 0 = [3]
Nilai a,b, c dan d pada persamaan 2.4 kemudian dapat kita peroleh dengan melihat nilai aproksimasi terakhir a0 dan semua nilai-nilai detail d0,d1 dan d1 dimana a = ½ ( ½ (x0 + x1) + ½ (x2 + x3)) = a0 = 2 b = ½ ( ½ (x0 + x1) – ½ (x2 + x3)) = d0 = 3 c = ½ (x0 – x1) = d1(0) = 1 d = ½ (x2 – x3) = d1(1) = -6.
17
⎡6⎤ ⎡1⎤ ⎡ 1 ⎤ ⎡ 1 ⎤ ⎡0⎤ ⎢4⎥ ⎢1⎥ ⎢ 1 ⎥ ⎢− 1⎥ ⎢ ⎥ ⎢ ⎥ = 2 ⎢ ⎥ + 3⎢ ⎥ + 1⎢ ⎥ + (−6) ⎢ 0 ⎥ ⎢− 7 ⎥ ⎢1⎥ ⎢− 1⎥ ⎢ 0 ⎥ ⎢1⎥ ⎢ ⎥ ⎢⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣5⎦ ⎣1⎦ ⎣− 1⎦ ⎣ 0 ⎦ ⎣− 1⎦ Sistem Haar secara lengkap dituliskan sebagai berikut :
,
2
;
,0
2
Transformasi wavelet Diskrit merupakan hasil tranformasi sinyal diskrit menjadi koefisien-koefisien wavelet yang diperoleh dengan cara menapis sinyal dengan menggunakan dua buah tapis yang berlawanan. Kedua tapis tersebut adalah : a. Tapis perataan atau penyekalan atau disebut juga dengan tapis lolos rendah (low pass filter). b. Tapis detil atau tapis lolos tinggi (high pass filter). Pada tahap pertama, sinyal dilewatkan pada rangkaian filter high-pass dan low-pass, kemudian setengah dari masing-masing keluaran diambil sebagai sampel melalui operasi sub-sampling. Proses ini disebut sebagai proses dekomposisi satu tingkat. Keluaran dari filter low-pass digunakan sebagai masukan di proses dekomposisi tingkat berikutnya. Proses ini diulang sampai tingkat proses dekomposisi yang diinginkan. Gabungan dari keluaran-keluaran filter high-pass dan satu keluaran filter low-pass yang terakhir, disebut sebagai koefisien wavelet, yang berisi informasi sinyal hasil transformasi yang telah terkompresi. Jadi secara umum dapat kita simpulkan bahwa transformasi wavelet diskrit adalah proses dekomposisi citra pada frekuensi sub-
18
band dari citra tersebut, di mana komponen sub-band tersebut dihasilkan dengan cara menurunkan level dekomposisi. Proses ini dapat dilihat pada gambar 2.4.
Gambar 2.4 Dekomposisi Wavelet Diskrit pada Sinyal Satu Dimensi
2.4.2.2. Transformasi Wavelet Dua Dimensi
Data citra merupakan data yang berbentuk array dua dimensi, yang berisi informasi tentang warna dan intensitas pencahayaan dari suatu piksel. Untuk mentransformasikan data dua dimensi dengan menggunakan metode Wavelet, digunakan transformasi wavelet dua dimensi, yang algoritmanya dapat dilihat pada gambar 2.5.
19
Gambar 2.5 Algoritma Transformasi Wavelet Dua Dimensi
Gambar 2.6 Contoh Hasil Algoritma Transformasi Wavelet Dua Dimensi
20
Penjelasan terhadap algoritma transformasi wavelet gambar 2.5 : Lowpass terhadap baris Citra
Lowpass terhadap kolom Highpass terhadap kolom
Highpass terhadap baris
Lowpass terhadap kolom Highpass terhadap kolom
Proses dekomposisi transformasi wavelet untuk citra dua dimensi dapat dijelaskan pada gambar 2.6.
Gambar 2.7 Transformasi Wavelet untuk Citra Dua Dimensi
Penjelasan terhadap transformasi terhadap kolom-kolom pada citra (gambar 2.6) LL
LH
LL: hasil lowpass terhadap baris dan kolom LH: hasil lowpass terhadap baris lalu highpass terhadap kolom
HL HH
HL: hasil highpass terhadap baris lalu lowpass terhadap kolom HH: hasil highpass terhadap baris dan kolom
21
2.4.3. Pendekatan Minutiae
Perangkat lunak verifinger yang akan dibandingkan dengan perangkat lunak wavelet (non minutiae) menggunakan pendekatan Minutiae. Suatu pola sidik jari normal terdiri dari garis–garis dan spasi. Garis–garis ini dinamakan ridge sedangkan spasi di antara dua garis dinamakan valley. Pendekatan minutiae ini menggunakan ciri-ciri khusus tersebut untuk identifikasi sidik jari. Minutiae meliputi ridge ending, bifurcation, dan short ridge. Dalam Bartunek (2005) dan Ravi, Raja, dan Venugopal (2009), digunakan bentuk ridge secara umum untuk mengekstrasi ciri sidik jari pada pendekatan minutiae. Ridge yang digunakan meliputi arch, loop, dan whorl. Metode ini adalah metode yang paling kuno dalam pengenalan pola citra sidik jari dan masih digunakan dalam pengenalan pola secara manual yang dilakukan oleh manusia. Dalam Lin, Chen, dan Gaing (2010) dan Polikarpova (1996), dalam proses mengekstraksi ciri ini digunakan menghitung dimensi fraktal dari citra sidik jari tersebut. Proses ekstraksi ciri dengan dimensi fraktal ini, dapat dipertimbangkan untuk meningkatkan keakuratan pengenalan pola sidik jari. Ridge ending (gambar 2.8) adalah bagian ujung/akhir dari sebuah ridge, sedangkan bifurcation adalah bagian percabangan dari ridge. Dan untuk proses identifikasi dari minutiae yang dilihat secara umum, dapat diklasifikasikan dengan core dan delta (gambar 2.9). Core adalah titik pusat dari sidik jari yang dapat berbentuk whorl atau loop. Dan delta adalah sewaktu pola ridge membentuk segitiga. Seperti disebutkan dalam bagian sebelumnya, dalam minutiae, keunikan sidik jari secara
22
eksklusif ditentukan oleh karakteristik ridge lokal dan hubungan mereka (Kamijo, 1993; Kawagoe & Tojo, 1984). Karakteristik ini ridge lokal tidak merata. Kebanyakan dari mereka sangat tergantung pada kondisi dan kualitas sidik jari dalam sidik jari. Karakteristik yang paling menonjol dalam ridge lokal adalah: Ridge ending dan Ridge bifurcation. Sebuah sidik jari dengan kualitas yang baik biasanya mengandung sekitar 40-100 minutiae.
Gambar 2.8 (a) Bifurcation (b) Ridge Ending (Ratha et al., 1996)
Gambar 2.9 Core dan Delta (Maltoni dan Cappelli, 2008)
Pada gambar 2.10 menggambarkan flowchart keseluruhan algoritma yang biasanya digunakan pada pendekatan minutiae. Secara garis besar, terdiri dari 3
23
komponen, yaitu orientation field estimation, ridge extraction, minutiae extraction and postprocessing.
Gambar 2.10 Flowchart Algoritma Minutiae Extraction
Orientation field dari sebuah citra sidik jari mencakup intrinsik alami dari sidik jari. Orientation field estimation sangat berguna dalam analisa citra (Jain, Hong, Bolle, Pankanti, 1997) . Setiap piksel, jika daerah tersebut dibawah nilai threshold maka piksel tersebut ditandakan sebagai background.
24
Ridge extraction, tahap ini berguna untuk mendeteksi ridge. Piksel dapat diidentifikasi sebagai ridge pixels dengan cara jika nilai gray level pada piksel lebih besar dari threshold, maka piksel ditandakan sebagai ridge. Minutiae detection adalah tahap selanjutnya ketika thinned ridge map telah dilakukan. Tetapi, spikes dan breaks yang tidak diinginkan terkadang muncul sehingga menghasilkan banyak mendeteksi minutiae yang salah. Sebuah sidik jari dikomposisikan dari bentuk ridge dan valleys. Secara global, bentuk-bentuk ini terkadang menghasilkan beberapa bentuk lain yang dinamakan singularities, yang diklasifikasikan menjadi 3 tipe: loop, delta whorl (Alonso dan Fernandez, 2009). Berdasarkan jumlah dan struktur delta, bentuk sidik jari dibagi menjadi beberapa kelas, seperti pada gambar 2.11.
25
Gambar 2.11 Fingerprint Patterns Classes (sumber : Criminal Research Product)
Biasanya preprocessing citra sidik jari dikonversikan menjadi binary image, setelah itu di thinning. Pada tahap thinning mengurangi ketebalan ridge menjadi satu piksel, biasanya setelah itu dilakukan juga postprocessing.
26
Gambar 2.12 Minutiae Extraction Algorithm (Jain, Hong, Pankanti, Bolle, 1997)
Pada gambar 2.12 adalah citra sidik jari dari langkah-langkah minutiae extraction. Pada gambar pertama input image adalah contoh hasil citra sidik jari yang didapatkan dari ink-less scanner. Pada gambar ke 2 adalah hasil orientation field dari citra sidik jari, langkah selanjutnya (3) adalah hasil citra sidik jari dengan menghilangkan background. Pada gambar ke 4 adalah hasil dari ridge yang telah diekstrasi, yang lalu kemudian di thinning. Gambar terakhir (6) adalah hasil ekstrasi minutiae dan orientasi dari citra sidik jari yang dimasukkan.
27
2.4.4. Jaringan Syaraf Tiruan
Menurut Eli (2005) Jaringan syaraf tiruan (JST) atau Artificial Neural Network (ANN) adalah suatu metode komputasi yang meniru sistem jaringan syaraf manusia. Metode ini menggunakan elemen perhitungan non-linier yang disebut neuron yang diorganisasikan sebagai jaringan yang saling berhubungan, sehingga mirip dengan jaringan syaraf manusia. Otak terdiri dari sekitar (10.000.000.000) sel syaraf yang saling berhubungan. Sel syaraf mempunyai cabang struktur input (yaitu dendrites), sebuah inti sel dan percabangan struktur output (yaitu axon). Akson (Axon) dari sebuah sel terhubung dengan dendrite (dendrites) yang lain melalui sebuah synapsis (synapse).
Ketika
sebuah sel syaraf aktif, kemudian menimbulkan suatu signal electrochemical pada axon. Signal ini melewati synapse menuju ke sel syaraf yang lain. Susunan syaraf manusia dapat dilihat pada gambar 2.13.
Gambar 2.13. Jaringan Syaraf Manusia (Sumber : stmikpontianak.ac.id)
28
Menurut Haykin (1999), jaringan syaraf tiruan (Artificial Neural Network) adalah sejumlah besar prosesor yang terdistribusi secara parallel dan terdiri dari unit pemrosesan sederhana, di mana masing-masing unit memiliki kecendrungan untuk menyimpan pengetahuan yang dialami dan dapat digunakan kembali. JST menyerupai otak manusia dalam dua hal, yaitu : 1. Pengetahuan diperoleh dari jaringan melalui proses belajar 2. Kekuatan hubungan antar sel syaraf yang dikenal sebagai bobot-bobot sinaptik digunakan untuk menyimpan pengetahuan. JST ditentukan oleh 3 hal (Siang, 2004) : 1. Pola hubungan antar neuron (disebut dengan arsitektur jaringan). 2. Metode penentuan bobot keterhubungan (disebut dengan pelatihan atau proses belajar jaringan). 3. Fungsi aktifasi yaitu fungsi yang digunakan untuk menentukan output suatu neuron. Pada dasarnya cara kerja JST tersebut dengan cara menjumlahkan hasil kali dari nilai masukan dengan nilai bobotnya. Pada Gambar 2.14 diperlihatkan serangkaian masukan …
…
. Setiap masukan akan dikalikan berturut-turut dengan bobot
dengan demikian hasil kali keluaran akan sama dengan: .
.
…
.
29
Gambar 2.14 Input dan Bobot pada Jaringan Syaraf Tiruan (Sumber : www.petra.ac.id)
2.4.5. Backpropagation
Menurut Kusumadewi (2008), backpropagation adalah sebuah metode sistematik untuk pelatihan perambatan balik galat (generalized delta rule) yang merupakan metode penurunan gradien untuk mengurangi galat kuadrat total pada output yang dihitung dari jaringan. Dalam backpropagation terdapat tiga lapisan, yaitu: a. Lapisan Input, yaitu lapisan yang akan diisi dengan data yang akan ditraining ke dalam jaringan syaraf tiruan. b. Lapisan tersembunyi (hidden layer), layer yang tidak pernah muncul dan berada di antara lapisan input dan lapisan output. c. Layer output, yaitu layer yang akan berisi nilai output dari proses backpropagation.
30
Gambar 2.14 adalah contoh backpropagation dengan menggunakan 1 lapisan tersembunyi (hidden layer)
Gambar 2.15 Backpropagation dengan Satu Lapisan Tersembunyi
Algoritma backpropagation terbagi menjadi dua, yaitu algoritma training dan algoritma untuk aplikasi. Pada algoritma training, ada dua langkah yang harus dilakukan, yaitu langkah maju (feedfoward) dan langkah mundur (backward). Untuk bagian aplikasi, hanya langkah maju yang akan dijalankan. Berikut tahap-tahap dalam algoritma backpropagation : •
Tahap 0 :
Inisialisasi nilai weight.
•
Tahap 1 :
Jika proses terus ingin dilanjutkan, lakukan tahap 2-9.
•
Tahap 2 :
Untuk setiap pasangan data training lakukan tahap 3-8.
31
Langkah maju (Feedforward) sebagai berikut : •
Tahap 3 :
Setiap unit input (Xi, i = 1,...,n) menerima sinyal input Xi dan
meneruskan sinyal tersebut ke semua unit pada lapisan di atasnya (hidden layer). •
Tahap 4 :
Setiap unit tersembunyi (Zj, J=1,...,p) menjumlahkan sinyal-
sinyal input terbobot.
kemudian digunakan fungsi aktivasi untuk menghitung sinyal output-nya. _
dan kirimkan sinyal tersebut ke semua unit di lapisan atasnya (output). •
Tahap 5 :
Setiap unit output (Yk, K=1,...,m) menjumlahkan sinyal-sinyal
input terbobot, _
kemudian digunakan fungsi aktivasi untuk menghitung sinyal output-nya. _
32
Langkah mundur (backward) sebagai berikut : •
Tahap 6 :
Tiap-tiap unit output (Yk, k=1,...,m) menerima pola target yang
berhubungan dengan pola input pembelajaran. Hitung informasi error-nya, ′
_
hitung koreksi bobot (yang nantinya akan digunakan untuk memperbaiki nilai Wjk), ∆
hitung juga koreksi bias (yang nantinya digunakan untuk memperbaiki nilai Wok), ∆
dan kirimkan nilai •
ke unit-unit yang ada dilapisan bawahnya.
Tahap 7 : Tiap-tiap hidden unit (Zj, j=1,...,p) menjumlahkan delta input-nya (dari unit yang berada pada lapisan atasnya), _
kalikan nilai ini dengan turunan dari fungsi aktivasinya untuk menghitung informasi error-nya, _
′
_
33
kemudian hitung koreksi bobot (yang nantinya digunakan untuk memperbaiki nilai Vij), ∆
hitung juga koreksi bias (yang nantinya digunakan untuk memperbaiki nilai Voj), ∆
•
Tahap 8 :
Setiap unit output (Yk, K=1,...,m) memperbaiki bobot dan
biasnya (j=0,...,p), ∆
setiap unit tersembunyi (Zj, j=1,...,p) memperbaiki bobot dan biasnya (i=0,...,n). ∆
•
Tahap 9 :
tes kondisi berhenti.
2.4.6. Performance Measure
Untuk menghindari ambiguitas suatu sistem memungkinkan memiliki beberapa template, dalam skripsi ini didefinisikan algoritma kesalahan pencocokan (matching algorithm errors) untuk perbandingan sampel terhadap template yang dimasukkan.
34
False Match Rate adalah probabilitas yang diharapkan dari suatu sampel
dinyatakan salah mengidentifikasi template yang dipilih secara acak, bukan template dirinya sendiri. False Non Match Rate adalah probabilitas yang diharapkan dari suatu sampel
dinyatakan tidak mengidentifikasi template dari pemilik sampel tersebut. Literatur dalam skala besar pada sistem identifikasi sering mengacu pada "false rejection" yang terjadi ketika sampel yang disampaikan, salah dicocokkan dengan template yang terdaftar oleh user lain. Dalam literatur akses kontrol, "false acceptance" muncul ketika sampel yang dikumpulkan salah disesuaikan dengan template user lain. Definisi yang disajikan di sini dimaksudkan untuk mengatasi masalah tersebut.
2.4.7. Perbandingan Pendekatan Minutiae dan Non-Minutiae
Berbagai penelitian telah dilakukan dalam identifikasi sidik jari. Dua kategori utama untuk identifikasi sidik jari dapat diklasifikasikan sebagai minutiae dan non minutiae. Pendekatan minutiae (Jain, 1997; Ratha, 1996; Cappelli, 2011) adalah algoritma paling populer dan canggih untuk pengenalan sidik jari. Fitur utama minutiae : ridge ending, ridge bifurcation dan sebagainya (Mario , 2003) seperti yang telah dijelaskan pada subbab sebelumnya. Pendekatan ini menggunakan fitur ekstraksi vektor dari sidik jari sebagai titik-titik yang terdiri dari tipe, posisi, orientasi. Tahap matching pada pendekatan minutiae adalah mencari keselarasan terbaik antara template dan citra sidik
35
jari yang dimasukkan yang telah diekstraksi. Namun, karena kualitas gambar yang buruk dan kondisi input
yang kompleks, minutiae tidak mudah ditentukan secara
akurat, sehingga menghasilkan akurasi dalam matching tersebut rendah. Selain itu, pendekatan minutiae membutuhkan komputasi dan kompleksitas yang tinggi (Yang, 2008). Pendekatan non minutiae (Amornraksa & Tachaphetpiboon, 2006; Nanni & Lumini, 2008; Yang & Park, 2008) dapat mengekstrak informasi yang lebih banyak dan meninggalkan proses pengolahan binarization, thinning, postprocessing. Pendekatan non minutiae melakukan proses lebih cepat namun analisis terhadap citra sidik jari yang kurang karena mengambil semua ciri dari citra sidik jari tersebut. Berdasarkan literatur tersebut, penulis mempunyai hipotesa bahwa pendekatan minutiae mempunyai keakuratan yang baik dikarenakan memilah ciri-ciri khusus dari citra sidik jari, namun memakan proses yang cukup lama, sedangkan pada pendekatan non minutiae mengekstraksi informasi lebih banyak tanpa dianalis sehingga menghasilkan keakuratan yang kurang baik, namun proses akan lebih cepat dibandingkan dengan pendekatan minutiae. Tabel 2.2 Perbandingan Pendekatan Berdasarkan Literatur Pendekatan Minutiae
Pendekatan Non-Minutiae
Waktu proses lama
Waktu proses cepat
Fitur lokal / detail
Fitur umum
