BAB 3 PERANCANGAN
3.1 Desain Verifikasi Tanda Tangan Desain verifikasi tanda tangan secara umum terdiri dari lima tahap utama, yaitu Input Data, Pre-processing, Feature Extraction, Training, dan Verification. Pada tahap input data, sistem akan meminta input data yang terdiri dari nama, tanggal lahir, foto dan tiga buah sampel tanda tangan yang telah digitalisasi melalui scanner dan disimpan sebagai citra dengan format file bitmap. Pada tahap Pre-processing, ketiga input citra tanda tangan akan diseragamkan sehingga invarian terhadap letak dan ukuran. Setelah melalui tahap Pre-processing, citra tanda tangan akan diolah menjadi informasi yang mewakili karakteristik dari masing-masing tanda tangan pada tahap Feature Extraction. Setelah didapat data yang mewakili karakteristik dari tanda tangan, Hidden Markov Model akan memproses data tersebut dan mengolahnya menjadi knowledge pada tahap training. Data dari hasil training tersebut akan disimpan ke dalam memori. Setelah dilakukan training, maka dapat dilakukan verifikasi tanda tangan pada tahap verification, yaitu dengan membandingkan citra tanda tangan yang dimasukkan dengan data hasil training yang disimpan, akan dikerjakan oleh modul Verification. Berikut ini adalah gambar desain verifikasi tanda tangan (Gambar 3.1)
24
25
Gambar 3.1 Desain Verifikasi Tanda Tangan
3.2 Citra Tanda Tangan Dalam program verifikasi tanda tangan ini yang dibutuhkan adalah citra tanda tangan, di mana citra tersebut sebagai input maupun juga sebagai tanda tangan yang akan diverifikasikan. Citra
tanda
tangan
ditangkap
dengan
menggunakan
scanner
dengan
menggunakan resolusi 150 dpi. Tanda tangan tersebut discan dengan latar belakang berwarna putih (tanpa latar belakang), dibatasi kotak dengan ukuran tertentu, sehingga hasil citra tanda tangan yang ditangkap berukuran 256 x 128 piksel. Citra tanda tangan yang ditangkap adalah citra dengan format black and white (biner) dengan format file bitmap (.bmp). Gambar 3.2 merupakan contoh citra tanda tangan yang ditangkap oleh scanner dan menjadi input dari program.
26
Gambar 3.2 Citra Tanda Tangan
3.3 Perancangan Program Aplikasi Verifikasi Tanda Tangan Secara umum bagian dari program terdiri dari 2 bagian, yaitu input data dan verifikasi tanda tangan. Input data digunakan untuk memasukkan data dari user ke dalam memori dari program sebagai referensi data pembanding yang akan dilakukan verifikasi. Verifikasi tanda tangan akan mengolah citra tanda tangan dan memberikan hasil apakah verifikasi tanda tangan berhasil dilakukan atau tidak. Diagram alir yang dibuat dari program ini secara umum adalah sebagai berikut :
3.3 Diagram Alir Program Verifikasi Tanda Tangan
27 3.4 Perancangan Input Data Sebelum melakukan verifikasi tanda tangan, maka diperlukan penyimpanan data, yang nantinya disimpan sebagai referensi pada saat pembandingan data. Input data yang dibutuhkan dalam program adalah data-data dari user, dimana data-data tersebut akan menjadi referensi dalam verifikasi. Data-data yang dibutuhkan antara lain adalah kode, nama, tanggal lahir, foto diri, dan citra tanda tangan sebanyak tiga buah, yang sebelumnya telah di scan dan disimpan dalam file tertentu. Setelah data-data tersebut diisi, maka dilanjutkan dengan proses Pre-processing, Feature Extraction, dan Training. Berikut ini adalah diagram alir dari input data (Gambar 3.4)
Gambar 3.4 Diagram Alir Input Data
28 Proses Pre-processing terdiri dari 2 tahap utama, yaitu cropping dan scalling. Tahap pre-processing ini diperlukan karena setiap citra tanda tangan tidak ada yang sama persis baik dalam letak maupun ukuran. Tujuan Preprocessing ini adalah untuk menyeragamkan data citra tanda tangan dari perbedaan letak dan ukuran, sehinggga hasil dari Pre-processing ini dapat digunakan sebagai input pada tahap feature extraction. Berikut ini adalah diagram alir Pre-processing (Gambar 3.5).
Gambar 3.5 Diagram Alir Pre-processing
Tahap cropping bertujuan untuk mengambil citra tanda tangan sesuai berdasarkan batas piksel hitam terkiri (xmin), terkanan (xmax), teratas (ymin), dan terbawah (ymax) dari citra tanda tangan tersebut. Berikut ini adalah Diagram alir proses cropping (Gambar 3.6) beserta contoh hasil citra tanda tangan yang melalui tahap cropping (Gambar 3.7).
29
Gambar 3.6 Diagram Alir Cropping
Gambar 3.7 Citra tanda tangan yang melalui proses cropping Tahap Scalling bertujuan untuk mengembalikan citra tanda tangan yang telah melalui proses cropping ke dalam ukuran 256 x 128 piksel, sehingga ukuran dari setiap citra tanda tangan menjadi seragam. Berikut ini adalah diagram alir tahap scalling (Gambar 3.8) dan contoh sebuah citra tanda tangan yang melalui tahap scalling (Gambar 3.9)
30
Gambar 3.8 Diagram Alir Scalling
Gambar 3.9 Citra tanda tangan yang telah melalui tahap scalling
Preprocessing Cropping (SignatureImage); Scalling(SignatureImage);
Cropping for i:=0 to SignatureImage.Width-1 do for j:=0 to SignatureImage.Height-1 do if SignatureImage.Canvas.Pixels[i,j]=clBlack then begin if i
31 if i>kanan then kanan:=i; if j>bawah then bawah:=j; if j
Scalling lebar:=kanan-kiri+1; tinggi:=bawah-atas+1; Sh := 256/lebar; Sv := 128/tinggi; w := SignatureImage2.Picture.Width; h := SignatureImage2.Picture.Height; w1 := Round(Sh*w); h1 := Round(Sv*h); SignatureImage.Picture.Bitmap.Width := w1; SignatureImage.Picture.Bitmap.Height := h1; for x1 := 0 to w1-1 do for y1 := 0 to h1-1 do begin xAsal := x1/Sh; yAsal := y1/Sv; if ((Floor(xAsal)<0) or (Ceil(xAsal)>w-1) or (Floor(yAsal)<0) or (Ceil(yAsal)>h-1)) then SignatureImage.Canvas.Pixels[x1,y1]:=clWhite; else begin x := Round(xAsal); y := Round(yAsal); SignatureImage.Canvas.Pixels[x1,y1]:= SignatureImage 2.Canvas.Pixels[x,y] end; end;
Pada proses feature extraction, sistem akan mencari ciri-ciri khusus dari tanda tangan, dengan membuat membagi citra tanda tangan yang telah melalui tahap preprocessing ke dalam kotak-kotak kecil, yang masing-masing yang berukuran 16 x 16 piksel yang memiliki nilai keabuan. Nilai keabuan yang menyusun citra tanda tangan ini yang nantinya mencirikan sebuah tanda tangan. Nilai keabuan masing-masing kotak merupakan perbandingan jumlah piksel putih terhadap jumlah seluruh piksel dalam
32 kotak tersebut. Berikut ini adalah gambar diagram Alir untuk proses feature extraction (Gambar 3.10) serta gambar citra tanda tangan yang telah melalui tahap feature extraction (Gambar 3.11).
inode ( i , j ) =
greyval =
i j + ). 16 16 16
piksel putih jumlah piksel
Gambar 3.10 Diagram Alir Feature Extraction
Gambar 3.11 Citra tanda tangan setelah melalui Feature Extraction
33 Feature Extraction for i:=0 to 255 do for j:=0 to 127 do begin inode[i,j]:=int(i/16)+(int(j/16)*16); if SignatureImage.Canvas.Pixels[i,j]<>clblack then pikspth[round(inode[i,j])]:=pikspth[round(inode[i,j])]+1; jmlhpiks[round(inode[i,j])]:=jmlhpiks[round(inode[i,j])]+1; end; for i:=0 to 127 do greyval[i]:=pikspth[i]/jmlhpiks[i];
Pada tahap Training ini, metode yang digunakan adalah hidden markov model. Tujuan dari tahap training ini adalah dimana informasi karakteristik yang berupa matriks 16 x 8 yang didapat dari proses feature extraction, diolah sehingga didapatkan suatu nilai yang mewakili karakteristik dari tanda tangan setiap orang. Tahap training ini terdiri dari 2 proses, yaitu proses learning, dan proses evaluation. Tahap learning bertujuan untuk membentuk model HMM λ = (Λ, B, π ) agar probabilitas Pt (O λ ) maksimal. Hasil dari tahap feature extraction yang berupa matriks berdimensi 16 x 8 yang merupakan nilai keabuan dari masing-masing kotak akan dimasukkan sebagai input pada proses learning ini dengan menggunakan algoritma kmeans. Setelah didapatkan model HMM λ = (Λ, B, π ) , maka model HMM tersebut akan diteruskan sebagai input pada proses evaluation yang menggunakan algoritma forward untuk mendapatkan nilai probabilitas Pt (O λ ) yang akan disimpan sebagai referensi dari tanda tangan masing-masing orang. Berikut ini adalah diagram alir tahap Training (Gambar 3.12), proses Learning (Gambar 3.13), dan proses Evaluation (Gambar 3.14)
34
Gambar 3.12 Diagram Alir Training pada Input Data
Training Learning (TrainingData); Evaluation(hmm);
35 Start Learning I
Inisialisasi Variabel (data, means, new means, a, b, π, I, j, k, N)
Pola = 1 ; N = 3 means(k) = data(rand(i), rand(j))
Hitung euclidean distance data(i,j)
klasifikasi data(i,j)
means = new means pola = 1
Hitung new-means
Cek Pola = 3 ?
Error =
tidak
tidak
pola = pola +1
(new means − means) 2 N *3
Error sesuai dengan batas error yang telah ditetapkan ?
ya
Hitung a, b, π,
End Learning I
Gambar 3.13 Diagram Alir Learning pada Input Data
36
Gambar 3.14 Diagram Alir Evaluation pada Input Data
Learning for i:=0 to n do means[i]:=TrainingData[random(16),random(8)]; repeat begin for jmlhpola:=0 to 2 do begin for i:=0 to w do begin for j:=0 to t do
37 begin curr:=TrainingData[jmlhpola,i,j]; min_dist:=abs(curr-means[0]); klas:=0; for k:=1 to n do begin dist:=abs(curr-means[k]); if dist<min_dist then begin min_dist:=dist; klas:=k; end; end; classification[i,j]:=klas; end; for i:=0 to w do for j:=0 to t do begin new_means[classification[i,j]]:= new_means[classification[i,j]]+TrainingData[jmlhpola,i,j]; count[classification[i,j]]:=count[classification[i,j]]+1; end; for i:=0 to n do new_means[i]:=new_means[i]/count[i]; for i:=0 to n do selisih:=selisih+sqr(new_means[i]-means[i]); end; error:=sqrt(selisih/(n*3)); if error=errorsblm then done:=true else begin for i:=0 to n do means[i]:=new_means[i]; errorsblm:=error; for i:=0 to w do for j:=0 to t do classification[i,j]:=0; end; end; until (done=true); for i:=0 to hmm.n do begin hitung:=0; for j:=0 to w do if classification[j,0]=i then hitung:=hitung+1; hmm.pi[i]:=hitung/(w+1); end; for i:=0 to hmm.n do for j:=0 to hmm.n do begin hitung:=0; totalhitung:=0; for x:=0 to w do begin for y:=0 to t-1 do begin if classification[x,y]=i then if classification[x,y+1]=j then hitung:=hitung+1;
38 if classification[x,y]=i then totalhitung:=totalhitung+1; end; if classification[x,t]=i then totalhitung:=totalhitung+1; end; hmm.a[i,j]:=hitung/totalhitung; end; for i:=0 to hmm.n do begin for a:=0 to hmm.n do count[a]:=0; totalcount:=0; for j:=0 to w begin for t:=0 to T do if classification[j,t]:=i then begin O:=TrainingData[j,t]; for s:=0 to hmm.m do begin if found=false then if hmm.v[s]=O then begin k:=j; found:=true; end; end; if found=true then count[k]:=count[k]+1; totalcount:=totalcount+1; end; end; for k:=0 to m do hmm.b[i,k]:=count[k]/totalcount; end;
Hasil proses Evaluation yang berupa P (O λ ) akan disimpan, dengan batasan toleransi α , sehingga yang disimpan nilainya ke dalam memori adalah nilai probabilitas 1 dan probabilitas 2, dimana nilainya adalah sebagai berikut
probabilitas 1 =
log(P(O / λ )) ⎛ log(P(O / λ )) ⎞ *α ⎟ −⎜ N N ⎝ ⎠
probabilitas 2 =
log(P(O / λ )) ⎛ log(P(O / λ )) ⎞ *α ⎟ +⎜ N N ⎝ ⎠
39 Setelah semua proses di atas dilakukan, maka proses selanjutnya semua data tersebut akan disimpan dalam memori program, dan kemudian kembali ke menu utama program, untuk melakukan proses berikutnya.
Evaluation for i:=0 to hmm.n do alpha[0,i]:=hmm.pi[i]*hmm.b[i,o[0]]; for k:=1 to T do for j:=0 to hmm.n do begin jumlah:=0; for i:=0 to hmm.n do jumlah:=jumlah+alpha[i,k-1]*hmm.a[i,j]; alpha[k,j]:=jumlah*hmm.b[j,o[t]]; end; prob:=0; for i:=0 to hmm.n do prob:=prob+alpha[i,T]; prob:=log10(prob)/3;
3.5 Perancangan Verifikasi
Dalam perancangan verifikasi ini dibutuhkan input berupa kode yang diklaim sebagai identitas pengguna dan citra tanda tangan yang akan diverifikasi. Tahapan dalam perancangan ini adalah input data, Pre-processing, Feature Extraction, Training dan verifikasi tanda tangan itu sendiri. Berikut ini adalah diagram alir Verifikasi
40
Gambar 3.15 Diagram Alir Verifikasi Proses pre-processing pada verifikasi ini tidak berbeda dengan tahap preprocessing pada input data. Dimana tahap pre-processing ini bertujuan untuk menghasilkan data yang invarian terhadap letak dan ukuran.
41 Proses Feature Extraction pada verifikasi ini juga sama dengan tahap Feature Extraction pada input data dimana tahap feature extraction ini bertujuan untuk mendapatkan fitur yang mewakili karakteristik citra tanda tangan tersebut, yang berupa matriks nilai keabuan. Proses training pada verifikasi ini terdiri dari 2 proses, yaitu learning dan evaluation. Proses learning ini bertujuan untuk mendapatkan model HMM
λ = (Λ, B, π ) . Proses learning pada verifikasi ini tidak jauh berbeda dengan learning pada input data. Proses learning pada input data memproses 3 buah citra tanda tangan untuk dimasukkan ke dalam memori, sedangkan proses learning pada verifikasi ini hanya memproses 1 citra tanda tangan yang akan diverifikasikan. Setelah melalui proses learning, maka model HMM
λ = (Λ, B, π ) tersebut akan dipakai sebagi input pada
proses evaluation, untuk mendapatkan probabilitas Pv (O λ ) , sebagai nilai yang akan dibandingkan dengan data yang telah disimpan sebelumnya. Berikut ini adalah gambar diagram alir training (Gambar 3.16), gambar diagram alir learning (Gambar 3.17), dan gambar diagram alir evaluation (Gambar 3.18)
Gambar 3.16 Diagram Alir Training pada verifikasi
42
Error =
( new means − means ) 2 N
Gambar 3.17 Diagram Alir Learning pada verifikasi
43
⎡N
⎤
⎣i =1
⎦
α t +1 (i ) = ⎢ Σ α t (i ) Aij ⎥.b j (Ot +1 )
N
P (O \ λ ) = Σ α t (i ) i =1
pv =
log P(O \ λ ) N
Gambar 3.18 Diagram Alir Evaluation pada verifikasi Tahap selanjutnya adalah proses verifikasi tanda tangan, yaitu dimana hasil dari Evaluation akan dihitung dan dibandingkan dengan probabilitas 1 dan probabilitas 2 yang telah dihitung pada waktu input data.
44 Bila hasil probabilitas pv pada tahap verifikasi berada di antara probabilitas 1 dan probabilitas 2, maka tanda tersebut akan diterima, sedangkan bila hasil probabilitas pv tersebut tidak berada di antara probabilitas 1 dan probabilitas 2, maka tanda tangan yang diinput akan ditolak. Bila tanda tangan tersebut diterima, maka data-data lain yang telah disimpan sebelumnya, yang berupa nama, tanggal lahir, dan foto diri akan ditampilkan, dengan tujuan untuk menguatkan bukti otentikasi dari orang yang mengklaim identitas tersebut. Dibawah ini merupakan rumus dari pv .
pv =
log(Pv (O / λ )) N
