BAB 2
LANDASAN TEORI
Pada bab ini diuraikan beberapa landasan teori dan konsep-konsep yang mencakup biometrik, Pengenalan pola, verifikasi tanda tangan,
Image Processing,
Preprocessing, Hidden Markov Model, False Rejection Rate, False Acceptance Rate, dan Delphi.
2.1 Biometrik Biometrik adalah sebuah kata Yunani tua untuk sebuah konsep yang baru. “Bio” berarti kehidupan, dan “Metric” berarti nilai, jadi kata biometrik berarti nilai kehidupan. Biometrik adalah teknologi untuk mengidentifikasikan seseorang secara otomatis, dengan menggunakan karakteristik fisik atau kebiasaan seseorang. Tipe-tipe biometrik dapat berdasarkan karakterisitik manusia yang unik, misalnya sidik jari, suara, iris, retina, tanda tangan, dan geometri tangan. Biometrik memberikan solusi yang lebih baik pada kebutuhan keamanan yang semakin meningkat pada informasi-informasi di masyarakat dari pada metode identifikasi yang sekarang ini ada, misalnya seperti penggunaan pasword, nomor PIN, atau kartu magnetik dengan PIN. Pengidentifikasian dengan menggunakan teknik biometrik ini membuat orang tidak perlu lagi untuk mengingat password (atau menuliskannya pada catatan kecil), PIN ataupun membawa suatu tanda pengenal lainnya. Sistem biometrik dapat digunakan untuk mengidentifikasikan pengguna / user
7
8 dari sebuah komputer, ATM, telepon genggam dan penggunaan katu kredit, dengan tujuan untuk mengurangi penipuan ataupun pengaksesan secara tidak sah.
2.2 Pengenalan Pola Pola adalah entitas yang terdefinisi dan dapat diberi suatu identifikasi atau nama (Murni dan Setiawan, 1992). Pola adalah bentuk atau model yang bisa dipakai untuk membuat atau untuk menghasilkan suatu atau bagian dari sesuatu, khususnya jika sesuatu yang ditimbulkan cukup untuk mempunyai suatu yang sejenis untuk pola dasar yang dapat ditunjukkan atau terlihat, yang mana sesuatu itu dikatakan memamerkan pola (http://id.wikipedia.org/wiki/Pola). Deteksi pola dasar disebut pengenalan pola. Pengenalan pola digunakan untuk mengenali objek kompleks dari bentuk sifat dari objek yang akan dikenali ciri-ciri dari objeknya. Pengenalan pola secara formal dapat dideskripsikan sebagai sebuah proses yang menerima pola (pattern) atau sinyal berdasarkan hasil pengukuran yang kemudian diklasifikasikan ke dalam satu atau lebih kategori / kelas tertentu (Haykin, 1999, p67). Suatu sistem pengenalan pola pada dasarnya terdiri atas tiga tahap, yaitu penerimaan data, pengolahan data, dan pengenalan objek atau pembuat keputusan. Adapun pengekatan utama dalam pengenalan pola adalah pendekatan geometrik dan pendekatan struktural. Pendekatan struktural delakukan dengan penentuan dasar yang mendeskripsikan objek yang akan dikenali (pendekatan pola melalui deskripsi dan kesimpulan) sedangkan pendekatan geometrik dilakukan berdasarkan ciri objek dan pola yang terjadi (pendekatan pola melalui klasifikasi dan perkiraan atau hitungan)
9 Secara teori, pendekatan struktural lebih mudah diterapkan karena dalam pengenalan pola, sistem pengenalan yan digunakan seperti manusia (Murni dan Setiawan (1992). Sedangkan untuk pendekatan geometrik dapat lebih diterima karena berdasarkan fakta-fakta yang ada.
2.3 Verifikasi tanda tangan . Dua hal utama yang harus ditentukan untuk mengenali identitas seseorang apakah berupa verifikasi atau identifikasi. Dalam verifikasi, yang ditentukan adalah megkonfirmasikan ataupun menolak seseorang yang mengklaim identitas tertentu. Pada verifikasi di sistem biometrik, sistem akan membuktikan apakah sampel dari biometrik seseorang sesuai dengan data yang ada. Identifikasi menyatakan identitas dari seseorang. Pada identifikasi, sebuah sampel biometrik akan dibandingkan dengan database, di mana sistem akan langsung memberikan identitas dari orang tersebut. Pada umumnya, verifikasi tanda tangan dilakukan secara manual, yaitu dimana seseorang bertugas untuk membandingkan bentuk tanda tangan yang akan diverifikasikan, dengan tanda tangan yang disimpan sebelumnya. Verifikasi adalah proses membandingkan sebuah sampel biometrik terhadap sebuah referensi dari seorang pengguna untuk memastikan identitas seseorang yang berhubungan dengan akses ke sistem, pada sistem keamanan dengan biometrik. (http://isp.webopedia.com/TERM/V/verification.html) Verifikasi tanda tangan adalah verifikasi berdasarkan pada tanda tangan seseorang, dimana tanda tangan yang diberikan dicocokkan dengan sampel tanda tangan yang telah disimpan pada data sebelumnya, apakah sesuai atau tidak. Berdasarkan
10 karakteristik tanda tangan yang diambil, verifikasi tanda tangan secara umum dapat dibagi menjadi 2 yaitu : a. Verifikasi tanda tangan secara offline Sistem verifikasi offline membandingkan tanda tangan berdasarkan bentuk tanda tangan. Dalam verifikasi secara offline, input berupa citra tanda tangan yang ditangkap oleh sebuah scanner pada sebuah kertas. b. Verifikasi tanda tangan secara online Sistem verifikasi online membandingkan tanda tangan berdasarkan bentuk (karakteristik spatial) dan rentang waktu pemasukan data (karakteristik temporal). Dalam verifikasi tanda tangan secara online, input yang diambil berupa tanda tangan yang dilakukan secara langsung misalnya pada sebuah digitizer, maupun alat untuk menangkap tanda tangan secara langsung lainnya.
2.4 Image Processing 2.4.1 Pengertian Image Processing Image Processing adalah suatu proses yang menganalisis dan memanipulasi gambar dengan menggunakan komputer. Image processing umumnya melibatkan 3 langkah dalam prosesnya yaitu : (http://pami.uwaterloo.ca/tizhoosh) •
Mengimport suatu gambar dengan optical scanner atau langsung melalui digital photography. Hasilnya berupa digital image
•
Memanipulasi atau menganalisis suatu gambar dengan teknik tertentu. Memanipulasi
gambar
berarti
termasuk
image
enchanment
dan
data
11 compression, sedangkan menganalisis suatu gambar berarti mencari pola tertentu yang tidak tampak oleh mata manusia •
Mengeluarkan hasilnya. Mengeluarkan hasilnya bisa suatu gambar yang telah diubah dengan cara tertentu atau berupa laporan hasil analisis gambar tersebut
2.4.2 Citra Digital Untuk mengolah citra dengan komputer pertama-tama citra harus diubah menjadi bentuk yang dapat dimengerti oleh komputer. Komputer hanya menerima data digital, oleh karena itu citra yang akan diproses dengan komputer harus diubah dahulu menjadi citra digital (http://pami.uwaterloo.ca/tizhoosh). Pada umumnya citra dapat digambarkan seperti terlihat pada gambar dibawah ini, di mana x dan y menyatakan posisi dan f(x,y) adalah intensitas cahaya yang pada potret atau film merupakan densitas. Besaran x, y, f(x,y) bila diubah menjadi besaran digital akan diperoleh citra digital.
Gambar 2.1 Citra Digital
12 Untuk melaksanakan hal ini pada bidang gambar citra dibuat kisi-kisi dan pada setiap kotak/sel nilai densitasnya hanya punya nilai diskrit. Proses ini dinamakan kuantisasi dan nilai yang diperoleh dinamakan tingkat kuantisasi (nilai keabuan). Citra yang diperoleh dengan cara ini dapat dinyatakan dengan titik koordinat (i, j) yang bernilai diskrit dan dinamakan titik sampling atau piksel serta nilai tingkat kuantisasi dari piksel itu.
Gambar 2.2 Citra yang mengalami kuantisasi menjadi citra digital
Citra digital dibagi menjadi 3 menurut jumlah tingkat kuantisasi dan warnanya (http://pami.uwaterloo.ca/tizhoosh) a. Citra biner (binary image) yaitu citra di mana setiap piksel hanya punya 2 nilai biasanya 0 dan 1 atau hitam dan putih. Terkadang ada yang menyebutnya 0 dan 255 (sebagai pengganti 1). b. Citra keabuan (gray image) yaitu citra yang mempunyai jumlah tingkat kuantisasi lebih dari 2. c. Citra warna (Color image) yaitu citra di mana setiap pixel selain punya nilai tingkat kuantisasi mempunyai warna. Citra warna mempunyai
13 komponen RGB. Berdasarkan jumlah tingkat kuantisasi untuk setiap jumlah warna yang dapat ditampilkan ditentukan. Misalkan RGB masingmasing komponen terdiri dari 1 bit, akan memberikan 8 warna, sedangkan kalau masing-masing terdiri dari 8 bit akan memberikan kurang lebih 16.000.000 warna.
Jenis-jenis format grafik diantaranya yaitu : a. JPEG (Joint Photographic Expert Group) merupakan pilihan format file yang baik untuk digunakan dalam Web untuk photography (http://www3.umassd.edu/public/BBwebcraft/ defjpeg.html). JPEG adalah format file terkompresi lossy untuk menampung foto dari gambar yang kontinu. b. GIF (Graphic Interchange Format) merupakan file terkompresi lossless dimana warna maksimum adalah 256 yang mendukung transparansi dan animasi. GIF termasuk format file yang banyak digunakan pada Web dan Graphical Browser dimana file GIF baik untuk simple line art, logo dan icon (http://www3.umassd.edu/ public/BBwebcraft/defgif.html) c. BMP merupakan format file standar untuk Windows (http://www. webopedia.com/TERM/B/BMP.html). format file ini mendukung RGB, grayscale, bitmap, maupun indexed color tetapi tidak mendukung alpha channel. BMP terdiri atas dot-dot atau bit-bit yang tersusun yang akan terbentuk dalam suatu gambar.
14 d. TIFF (Tagged Image File Format) merupakan format file yang biasa digunakan pada desktop publishing dan juga percetakan. e. PICT merupakan format file untuk Mac yang mana dapat menampung object vector dan bitmap. f. EPS (Encapsulated PostScript) merupakan format file untuk mentransfer grafik (vector atau bitmap) dalam bahasa PostScript antar aplikasi. g. PSD merupakan format standar Photoshop yang mana mendukung semua mode citra dan tidak terkompresi. h. PNG (Portable Network Graphics) merupakan format file yang mendukung pemakaian dalam Web dengan 24 bit dan background transparency. i. Dan sebagainya.
2.5 Pre-processing Preprocessing adalah proses pendahuluan pada data dengan tujuan untuk menpersiapkan data tersebut untuk proses utama ataupun proses selanjutnya. Pada image processing, preprocessing dilakukan sebelum tahap feature extraction dengan tujuan untuk menjadikan gambar atau citra yang akan diolah ke dalam bentuk standar. Preprocessing diantaranya terdiri atas cropping, dan scalling.
2.5.1 Cropping Cropping adalah memotong satu bagian dari citra sehingga diperoleh citra yang berukuran lebih kecil (Achmad, 2005, p172). Operasi ini pada dasarnya adalah operasi
15 translasi, yaitu menggeser koordinat titik citra. Rumus yang digunakan untuk operasi ini adalah : x’=x-xL
untuk x=xL sampai xR
y’=y-yT
untuk y=yT sampai yB
(xT,yT) dan (xB,yB) masing-masing adalah koordinat titik pojok kiri atas dan pojok kanan bawah bagian citra yang hendak di-crop
Gambar 2.3 Koordinat titik pojok bagian citra yang akan di-crop
Ukuran citra berubah menjadi : h’=yB-yT
dan transformasi baliknya adalah : x=x’+xL
untuk x’=0 sampai w’-1
y=y’+yT
untuk y’=0 sampai h’-1
2.5.2 Scalling Operasi Scalling dimaksudkan untuk memperbesar (zoom-in) atau memperkecil (zoom-out) citra. Hal ini dapat dilakukan dengan mengintroduksi parameter skala, baik
16 ke arah horisontal (Sh) maupun vertikal (Sv). Skala yang bernilai lebih dari 1 akan memperbesar citra asli, sedangkan jika bernilai kurang dari 1 akan memperkecil citra. Apabila aspect ratio (perbandingan antara tinggi dan lebar citra) hendak dipertahankan, maka dipilih Sh=Sv. Transformasi spasial yang dipakai adalah: x'=Sbx y’=Svy Dari persamaan-persamaan tersebut, untuk setiap titik pada citra hasil, dengan koordinat x’ dan y’ diketahui, dapat dicari koordinat titik asalnya yaitu x dan y. Ukuran citra juga berubah sesuai hubungan berikut w’=Shw h’=Svh
2.6 Hidden Markov Model Hidden Markov Model (HMM) merupakan himpunan terbatas yang terdiri dari state-state, yang masing-masing berhubungan dengan probabilitas distribusi. Transisi di antara state ditentukan oleh himpunan probabilitas yang dikenal dengan probabilitas transisi. Untuk mendapatkan HMM secara lengkap, maka dibutuhkan elemen-elemen sebagai berikut : •
Banyak state dari model tersebut, N
•
Banyak simbol pengamatan dalam alphabet, M. Jika pengamatannya kontinu maka nilai M terbatas
•
Himpunan probabilitas transisi state, Λ = {aij }
17 aij = p{q t +1 = j qt = i }, 1 ≤ i, j ≤ N
di mana qt merupakan state pada saat t Probabilitas transisi harus berada dalam batas normal stokastik,
aij ≥ 0, 1 ≤ i, j ≤ N dan •
N
∑a j =1
ij
= 1, 1 ≤ i ≤ N
Probabilitas distribusi pada setiap state, B = {b j (k )} b j (k ) = p{ot = v k q t = j}, 1 ≤ j ≤ N , 1 ≤ k ≤ M
di mana v k menunjukkan simbol pengamatan ke-k dalam alphabet, dan ot merupakan parameter vektor saat itu. Batasan stokastik di bawah ini harus dipenuhi
b j (k ) ≥ 0, 1 ≤ j ≤ N , 1 ≤ k ≤ M dan •
M
∑ b (k ) = 1, k =1
j
1≤ j ≤ N
Distribusi state awal, π = {π i } di mana, π i = p{q1 = i} 1 ≤ i ≤ N
Elemen-elemen tersebut dijadikan satu dan ditulis menjadi : λ = (Λ, B, π )
Gambar 2.4 Bentuk Hidden Markov Model
18
Dalam Hidden Markov Model, terdapat tiga masalah dasar, yaitu a. Masalah Evaluasi (Evaluation Problem) Masalah Evaluasi adalah masalah di mana probabilitas (P(O/ λ )) dari serangkaian pengamatan (O=o1,o2 ,....,oT) yang dibangun oleh model HMM ( λ ) belum diketahui. Probabilitas tersebut dapat dihitung dengan menggunakan algoritma forward (forward algorithm) b. Masalah Pengkodean (Decoding Problem) Masalah pengkodean adalah masalah di mana bagian dari rangkaian state dalam model HMM ( λ ) yang menghasilkan pengamatan (O=o1,o2 ,....,oT) belum diketahui. c. Masalah pembelajaran (Learning Problem) Masalah pembelajaran adalah masalah di mana parameter model harus disesuaikan berdasarkan model HMM
λ
dan serangkaian pengamatan
O=o1,o2,...oT agar nilai probabilitas P (O λ ) maksimal. Untuk mendapatkan model HMM tersebut, digunakan algoritma k-means (k-means algorithm).
2.6.1 Algoritma Forward
Untuk menghitung probabilitas dari serangkaian pengamatan (O=o1,o2 ,....,oT) yang dibangun oleh model HMM λ = (Λ, B, π ) , diperlukan algoritma forward. Berikut ini adalah langkah-langkah dalam algoritma forward. 1. Inisialisasi
α1 (i ) = π 1bi (o1 ), dimana :
1≤ i ≤ N
19
α
adalah variabel forward
π1
adalah distribusi state awal
bi
adalah probabilitas state ke-i
o1
adalah pengamatan ke-1
N
adalah jumlah state
2. Induksi ⎡
N
⎤
α t +1 (i ) = ⎢∑ α t (i )aij ⎥b j (ot +1 ), ⎣ i =1
1 ≤ t ≤ T − 1, 1 ≤ j ≤ N
⎦
dimana : t
adalah waktu
T
adalah jumlah pengamatan
aij
adalah probabilitas transisi i ke j
3. Terminasi P (O λ ) = ∑ α T (i ) N
i =1
dimana : P (O λ ) adalah probabilitas dari pengamatan O yang dibangun oleh model
HMM λ
2.6.2 Algoritma k-means
Algoritma k-means berguna untuk mendapatkan model HMM λ = (Λ, B, π ) agar mendapatkan nilai probabilitas P (O λ ) yang maksimal. Dalam menjalani proses learning pada algoritma k-means ini, dibutuhkan serangkaian data dan sejumlah pengamatan. Berikut ini adalah algoritma k-means yang terdiri dari 6 langkah. a. Pilihlah means inisial secara acak dari data yang akan diolah means (k ) = data (rand (i ), rand ( j ))
1 ≤ i ≤ w, 1 ≤ j ≤ T , 1 ≤ k ≤ N
20 dimana : data(i,j)
adalah data pada matriks i, j
rand( )
adalah fungsi acak
w
adalah jumlah baris data
T
adalah jumlah kolom data
N
adalah jumlah state
b. Berikan nilai klasifikasi pada setiap unit dari data berdasarkan euclidean distance terkecil dari means. EuclideanDis tan ce =
(x
ij
− means(k )) , 2
1 ≤ i ≤ w, 1 ≤ j ≤ T , 1 ≤ k ≤ T
c. Hitung means baru berdasarkan klasifikasi baru.
MeansBaru(k ) =
jumlah nilai data (k ) , jumlah data (k )
1≤ k ≤ N
d. Hitung error antara means dengan means baru N
Error =
∑ (MeansBaru(k ) − Means(k ))
2
k =1
N
e. Jika error lebih besar dari batas yang ditentukan, ulangi langkah b sampai e f. Hitung nilai-nilai pada model HMM λ = (Λ, B, π ) ,
dengan menggunakan
klasifikasi akhir.
πk =
aij =
Jumlah dari (klasifikasi ( j ,1) = k ) , w
1 ≤ k ≤ N, 1 ≤ j ≤ w
jumlah (klasifikasi( x, y ) = i dan klasifikasi ( x, y + 1) = j ) , 1 ≤ i ≤ N ,1 ≤ j ≤ N ,1 ≤ x ≤ w,1 ≤ y ≤ T jumlah(klasifikasi ( x, y ) = i )
21
bik =
jumlah(klasifikasi ( j , t ) = i dan v(k ) = data ( j , t )) , 1 ≤ i ≤ N ,1 ≤ k ≤ M ,1 ≤ j ≤ w,1 ≤ t ≤ T jumlah(klasifikasi ( j , t ) = i )
dimana :
πi
adalah distribusi state awal
aij
adalah probabilitas distribusi state
bij
adalah probabilitas state
N
adalah jumlah state
W
adalah jumlah baris data
T
adalah jumlah kolom data
M
adalah jumlah simbol pengamatan
2.7 False Acceptance Rate
False Acceptance Rate (FAR) adalah persentase jumlah diterimanya tanda tangan palsu dengan jumlah keseluruhan dari tanda tangan palsu yang diuji cobakan ke dalam sistem. Evaluasi performa FAR tergantung pada dua tipe pengujian, yaitu zeroeffort signature dan skilled forgery signature. zero-effort signature (McCabe, 1997, p11), atau yang disebut juga random forgery adalah pemalsuan tanda tangan, dimana digunakan nama dari yang akan dipalsukan atau hanya diminta untuk membuat sembarangan tanda tangan tanpa mengetahui bentuk tanda tangan aslinya sama sekali. Skilled forgery signature (McCabe, 1997, p11), adalah apabila tanda tangan yang dihasilkan berasal dari pemalsu tanda tangan, dimana orang tersebut memiliki referensi bentuk tanda tangan aslinya untuk dipalsukan
22 2.8 False Rejection Rate
False Rejection Rate (FRR) adalah persentase ditolaknya tanda tangan asli dengan jumlah keseluruhan tanda tangan asli yang diuji cobakan ke dalam sistem. Original signature / Reference Signature (McCabe, 1997, p10) berisi persentase penolakan tanda tangan yang berasal dari data referensi tanda tangan itu sendiri yang sebelumnya digunakan untuk diambil feature-nya yang nilainya telah disimpan knowledge storage. Pada uji evaluasi ini seharusnya original signature ini selalu menghasilkan nilai nol persen, yaitu tidak ada penolakan sama sekali. Test signature menurut McCabe (1997, p10) berisi persentase penolakan tanda tangan yang dilakukan oleh pemilik tanda tangan yang otentik, tetapi data tanda tangan ini tidak terdapat di dalam knowledge storage sehingga nilainya tidak ada di dalam referensi tanda tangan Nilai FRR yang tinggi sebenarnya tidak mengejutkan, mengingat test signature environment (lingkungan pada saat implementasi di lapangan) tidak senyaman kondisi signing environment (lingkungan pada saat proses pengambilan referensi tanda tangan)
2.9 Delphi
Delphi merupakan bahasa pemrograman pascal yang mendukung pengolahan citra. Delphi termasuk bagian dari borland. Delphi yang akan digunakan dalam perancangan sistem adalah Borland Delphi versi 7. Dalam perancangan verifikasi tanda tangan ini, komponen-komponen yang dipakai antara lain adalah •
Edit Box
23 Digunakan sebagai input dari keyboard dan dapat juga sebagai output berupa teks •
Label Sebagai tampilan teks untuk memberikan informasi dalam penggunaan program
•
Picture Untuk menampilkan citra maupun gambar
•
Button Tombol yang apabila ditekan akan melakukan prosedur tertentu
•
Open Picture Dialog Fungsi untuk membuka dan mengambil file berupa gambar atau citra
•
Combo Box Untuk menampilkan beberapa teks. Menyerupai Edit Box tetapi pada combo box terdiri dari beberapa teks yang menggulung.
