IMPLEMENTASI CANNY EDGE DETECTION DAN FUNGSI HASH SHA-1 DALAM PHOTO RECOGNITION SEBAGAI OTENTIKASI DIRI

ANDREAS DONY M.S (M0508084)

Program Studi InformatikaUniversitas Sebelas Maret

Jalan Ir. Sutami no. 36A SurakartaEmail : andomaze@gmail.com

ABSTRAK

Keaslian identitas diri seseorang dari kartu identitasnya belum dapat dijamin. Hal ini terbukti dengan

adanya kasus-kasus penyalahgunaan kartu identitas untuk pemalsuan identitas diri untuk tujuan tertentu. Dari

masalah itu pada paper ini akan dibahas lebih lanjut mengenai pembandingan gambar foto dengan

menggunakan metode Hash SHA-1. Untuk mengurangi banyaknya perbedaan yang terjadi antara kedua foto

yang dibandingkan tersebut, digunakan metode canny edge detection. Hasil dari edge detection tersebut akan

didapatkan message digestnya. Pencocokan dilakukan dengan melakukan perbandingan terhadap message

digest gambar foto yang diuji coba dengan message digest foto yang dipercaya kebenarannya. Metode ini

diharapkan dapat memudahkan dalam autentikasi identitas seseorang.

I. PENDAHULUAN

Identitas merupakan hal penting yang melekat pada seseorang dan menunjukkan diri sebenarnya orang

tersebut. Dengan menggunakan berbagai peralatan canggih, kita dapat dengan mudah mencari informasi

mengenai seseorang. Namun sayangnya, tidak semua informasi tersebut valid atau dapat dipercaya. Semakin

majunya teknologi juga berimplikasi kepada semakin canggihnya kelicikan orang. Kini orang dengan mudah

membuat penanda identitas palsu. Kecurangan atau kejahatan yang terjadi dengan memanfaatkan pemalsuan

identitas kini menjadi makin populer.

Oleh karena itu, diperlukan teknologi untuk mengautentikasi identitas yang mudah dan murah untuk

diterapkan. Salah satu caranya adalah dengan menggunakan metode Photo Recognition pada foto suatu

penanda identitas. Dengan cara tersebut, dapat ditentukan identitas aslinya dengan membandingkan foto

pada penanda identitas yang ada dengan foto dengan foto lain yang telah dipercaya. Penangkapan gambar pada

foto dengan menggunakan kamera biasa tentu dapat menghasilkan perbedaan yang cukup besar dalam hal

pembandingan. Maka digunakan canny edge detection pada foto tersebut agar lebih kecil rentang

perbedaannya. Untuk mengefisiensikan dan memudahkan penyimpanan data foto, dapat menggunakan fungsi

hash sebagai pembandingnya. Data foto yang disimpan merupakan sebuah fungsi hash dari gambar edge

detection foto yang telah diatur resolusinya ke ukuran tertentu.

II. DASAR TEORI

A. Canny Edge Detection

Operator deteksi tepi Canny dikembangkan oleh John F. Canny pada tahun 1986 dan menggunakan

algoritma multi-stage untuk mendeteksi berbagai tepi dalam gambar. Yang paling penting, Canny juga

menghasilkan teori komputasi deteksi tepi menjelaskan mengapa teknik ini bekerja.

Tahapan Algoritma Canny

1. Pengubahan menjadi Grayscale

Awal sebelum pengoperasian dilakukan konversi gambar terlebih dahulu menjadi bentuk Grayscale.

2. Pengurangan derau (Noise)

Detektor tepi Canny menggunakan filter berdasarkan turunan pertama dari Gaussian, karena

rentan terhadap derau yang muncul pada gambar awal yang belum diproses, sehingga sebelumnya

dilakukan konvolusi dahlu gambar awal dengan filter Gaussian. Hasilnya adalah gambar yang terlihat

agak kabur dari versi asli yang tidak dipengaruhi oleh pixel noise tunggal untuk setiap tingkat yang

signifikan. Berikut adalah contoh 5x5 Gaussian filter, digunakan untuk membuat gambar ke kanan,

dengan σ = 1,4 :

3. Menemukan Gradien Intensitas Gambar

Tepi dalam sebuah gambar dapat diinterpretasikan dalam berbagai arah, sehingga algoritma

Canny menggunakan empat filter untuk mendeteksi tepi horisontal, vertikal dan diagonal dalam gambar

kabur. Deteksi tepi operator (misalnya Roberts, Prewitt, & Sobel) mengembalikan nilai untuk turunan

pertama dalam arah horisontal (Gy) dan arah vertikal (Gx). Dari gradien tepi dan arah dapat ditentukan :

Sudut arah tepi adalah dibulatkan ke satu dari empat sudut mewakili vertikal, horisontal dan

kedua diagonal ( misalnya derajat 0, 45, 90 dan 135).

4. Menemukan Gradien Intensitas Gambar

Mengingat perkiraan gradien gambar, pencarian kemudian dilakukan untuk menentukan apakah

besarnya gradien mengasumsikan maksimum lokal di arah gradien. Jadi, misalnya,

Bila pembulatan sudut gradien adalah nol derajat (yaitu tepi berada dalam arah utara - selatan) titik

akan dianggap sebagai “tepi” jika intensitasnya lebih besar dari intensitas di arah barat dan timur,

Bila pembulatan sudut gradien adalah 90 derajat (yaitu tepi berada dalam arah timur - barat) titik

akan dianggap sebagai “tepi” jika intensitasnya lebih besar dari intensitas di arah utara dan selatan,

Bila pembulatan sudut gradien 135 derajat (yaitu tepi berada dalam arah timur laut – barat daya) titik

akan dianggap sebagai “tepi” jika intensitasnya lebih besar dari intensitas di arah barat laut dan

tenggara,

Bila pembulatan sudut gradien adalah 45 derajat (yaitu tepi berada dalam arah barat laut - tenggara)

titik akan dianggap “tepi” jika intensitasnya lebih besar dari intensitas di arah timur laut dan barat

daya.

Dari tahap ini disebut sebagai penekanan non-maksimum, satu set poin tepi, dalam bentuk gambar

biner, yang diperoleh. Hal tersebut kadang-kadang disebut sebagai "thin edges".

5. Menelusuri tepi melalui gambar dan hysteresis thresholding

Thresholding dengan histerisis membutuhkan dua ambang pintu - tinggi dan rendah. Membuat asumsi

bahwa tepi yang penting harus terus menerus berada di sepanjang kurva dalam gambar yang

memungkinkan kita untuk mengikuti bagian samar garis yang diberikan dan untuk membuang beberapa

piksel noise yang tidak merupakan sebuah baris, tetapi telah menghasilkan gradien besar. Oleh karena

itu kita mulai dengan menerapkan ambang batas tinggi. Ini menandai keluar tepi kita dapat cukup yakin

yang asli. Mulai dari ini, dengan menggunakan informasi arah diturunkan sebelumnya, tepi dapat

ditelusuri melalui gambar. Sementara penelusuran tepi, kita menerapkan ambang yang lebih rendah,

memungkinkan kita untuk menelusuri bagian samar dari ujung selama kita menemukan titik awal.

Gambar 1. Contoh Canny Edge Detection

B. Fungsi Hash SHA-1

Fungsi hash SHA merupakan sekumpulan fungsi hash didesain oleh National Security Agency dan

dipublikasikan oleh NIST sebagai U.S Federal Information Processing Standard (FIPS). SHA merupakan

singkatan dari Secure Hash Algorithm. SHS (Secure Hash Standard) merupakan standar yang

mendefinisikan SHA. Ada banyak versi SHA. SHA-0, SHA-1, SHA-2. Sedangkan untuk SHA-2 terbagi

lagi menjadi SHA-224, SHA-256, SHA-384, and SHA-512. Di sini hanya akan dibahas mengenai SHA-1.

SHA-1 menghasilkan 160 bit message diggest dari pesan yang panjangnya kurang dari 264 bit. SHA-1

hampir mirip dengan MD4 tetapi dengan beberapa perubahan. Langkah-langkah dalam menghitung nilai

hash adalah sebagai berikut :

Gambar 2. Alur SHA-1

Message Padding

SHA-1 digunakan untuk menghitung message diggest dari pesan atau file data yang disediakan

sebagai input. Pesan atau file dianggap sebagai kumpulan bit-bit. Panjang dari pesan adalah banyaknya

bit didalam pesan (Pesan kosong memiliki panjang 0). Jika banyaknya bit di dalam pesan merupakan

kelipatan 8, untuk memudahkan pembacaan dapat ditampilkan dalam format hexadecimal.

Tujuan dari message padding adalah membuat panjang total dari isi pesan menjadi kelipatan 512

bit. SHA-1 secara sekuensial memproses blok 512 bit ketika menghitung message diggest.

Pada message padding, tambahkan satu buah “1” , diikuti oleh m buah “0” diikuti oleh 64 bit

integer pada akhir pesan untuk menghasilkan pesan dengan panjang 512 * n. 64 bit integer tersebut

adalah panjang dari pesan asli sebelum message padding. Misalkan pesan dengan panjang L < 26.

Sebelum pesan menjadi input SHA-1, dilakukan message padding sebagai berikut :

Misal pesan aslinya (L = 40) adalah :

01100001 01100010 01100011 01100100 01100101 (biner)

61 62 63 64 65 (hex)

Tambahkan “1” pada akhir pesan :

01100001 01100010 01100011 01100100 01100101 1

Karena L = 40, maka hasilnya menjadi = 41, sehingga diperlukan “0” sebanyak

448 – 41 = 407 buah.

01100001 01100010 01100011 01100100 01100101 10000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

00000000 00000000

Dalam hexadecimal hasilnya adalah

61626364 65800000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000 00000000

Tambahkan 64 bit representasi dari panjang pesan asli. Untuk L = 40, maka representasi dari 64 bit

panjang pesan adalah

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00101000 (biner)

00000000 00000028 (hexa)

Maka, setelah ditambahkan hasilnya :

(dalam biner)

01100001 01100010 01100011 01100100 01100101 10000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

00101000

 (dalam hexa)

61626364 65800000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000 00000000 00000000 00000028

Hasil dari message padding adalah n 512-bit block (n * 16 word) , untuk suatu n > 0. Padded message

disimbolkan dengan M(1), M(2), …, M(n)

Fungsi dan Konstanta yang Digunakan

Serentetan fungsi logic f(0), f(1), f(2), .. ,f(79) digunakan dalam SHA-1. Setiap f(t) , 0 ≤ t ≤ 79

beroperasi pada 32bit word B, C, D dan menghasilkan 32bit word sebagai output.

f( t; B,C,D) didefinisikan sebagai berikut. Untuk word B,C,D :

f(t;B,C,D) = (B AND C) OR ((NOT B) AND D) ( 0 <= t <= 19)

f(t;B,C,D) = B XOR C XOR D (20 <= t <= 39)

f(t;B,C,D) = (B AND C) OR (B AND D) OR (C AND D) (40 <= t <= 59)

f(t;B,C,D) = B XOR C XOR D (60 <= t <= 79)

Serentetan konstanta K(0), K(1), K(2), … , K(79) digunakan dalam SHA-1. Dalam hexadecimal

konstanta tersebut adalah :

K(t) = 5A827999 ( 0 <= t <= 19)

K(t) = 6ED9EBA1 (20 <= t <= 39)

K(t) = 8F1BBCDC (40 <= t <= 59)

K(t) = CA62C1D6 (60 <= t <= 79)

Selain itu juga digunakan fungsi Circular Left Shift. Circular left shift S^n(X) , dimana X adalah 32

bit word dan n adalah bilangan integer dengan 0 ≤ n < 32.

S^n(X) = (X << n) OR (X >> 32-n)

Contoh : Misalkan X = 11010000 01010000 11100000 00001010 , dan n = 5.  Maka :

X << 5 = 00001010 00011100 00000001 01000000

X >> 27 = 00000000 00000000 00000000 00011010

———————————————————————- (OR)

S^5(X) = 00001010 00011100 00000001 01011010

Menghitung Message Diggest

Message diggest dihitung menggunakan hasil message padding. Komputasi menggunakan dua jenis

buffer, setiap jenis buffer tediri dari 5 buah 32-bit word. 5 buah 32-bit word buffer pertama dilabeli

dengan A, B, C, D, E. Sedangkan buffer kedua dilabeli H0, H1, H2, H3, H4. Terdapat sebuah sekuen 80

word 32-bit, yang dilabeli W(0), W(1), W(2), …, W(79) dan juga sebuah word buffer yang dilabeli

dengan TEMP. Untuk men-generate message diggest, block-block 16 word M(1) M(2) M(3) … M(n)

hasil message diggest diproses secara berurutan. Setiap pemrosesan M(i) membutuhkan 80 langkah.

Sebelum memproses apapun, untuk pertama kali, H diinisialisasi sebagai berikut :

H0 = 67452301 H1 = EFCDAB89 H2 = 98BADCFE

H3 = 10325476 H4 = C3D2E1F0

Selanjutnya lakukan komputasi dari M(1), M(2), … , M(n). Untuk setiap M(i), lakukan langkah

langkah sebagai berikut ini :

Step 1 :

Divide M(i) into 16 words W(0), W(1), … , W(15), where W(0) is the left-most word.

Step 2 :

For t = 16 to 79 do

W(t) = S^1( W(t-3) XOR W(t-8) XOR W(t-14) XOR W(t-16) )

Step 3 :

Let A = H0, B = H1, C = H2, D = H3, E = H4

Step 4 :

For t = 0 to 79 do

TEMP = S^5(A) + f(t;B,C,D) + E + W(t) + K(t);

E = D;

D = C;

C = S^30(B);

B = A;

A = TEMP;

 Step 5 :

H0 = H0 + A;

H1 = H1 + B;

H2 = H2 + C;

H3 = H3 + D;

H4 = H4 + E;

Setelah memproses M(n), message diggest adalah 160-bit string yang direpresentasikan oleh 5 word

III. IMPLEMENTASI

A. Konsep Penerapan Edge Detection dan Fungsi SHA-1 dalam Photo Recognition dan Otentikasi

Ide utama dari penerapan Photo Recognition dari hasil Edge Detection ini adalah untuk menghasilkan

sebuah gambar yang memilki tingkat kesamaan yang tinggi. Sehingga meskipun gambar dicetak dan

diambil kembali gambar digital dari hasil cetakan tersebut, dapat dihasilkan gambar yang hamper sama

setelah diekstraksi tepinya. Penggunaan fungsi hash adalah untuk membandingkan kedua gambar tersebut.

Jika transfer data dilakukan dengan mengirim gambar untuk dibandingkan dengan gambar yang ada

di server penyimpan, maka diperlukan akses koneksi yang aman dan cepat. Tentunya biaya yang

diperlukan untuk pengadaan layanan tersebut tidak murah. Kapasistasnya pun harus besar untuk dapat

menampung data seluruh gambar.

Dengan menggunakan edge detection pada foto pengenal identitas, device yang digunakan sebagai

sarana autentikasi menjadi lebih murah. Device yang diperlukan secara umum dapat dimiliki oleh banyak

orang, yang bila dibandingkan dengan device untuk mengidentifikasi sidik jari yang lebih mahal dan sulit

untuk diperoleh. Proses request data dari server juga lebih cepat karena bentuk pertukaran data yang terjadi

hanya berupa teks message digest SHA-1 dari gambar yang diekstraksi tepinya dengan data dari server.

B. Uji Akurasi Photo Recognition

Pada bagian ini, akan dilakukan pengujian akurasi fungsi hash terhadap beberapa gambar yang telah

diekstraksi fungsi hashnya. Algoritma Edge Detection yang digunakan berdasarkan metode Canny, dan

algoritma ini disebut sebagai algoritma canny edge detection. Algoritma fungsi hash yang digunakan

adalah SHA-1.

Berikut ini merupakan hasil uji terhadap gambar foto :

Gambar 3. Foto Asli (bag. kiri) & Foto Uji dengan brigthness tinggi (bag. kanan)

Gambar 4. Foto Asli (bag. kiri) & Foto Uji dengan brigthness rendah (bag. kanan)

Gambar 5. Foto Asli (bag. kiri) & Foto Uji yang identik dengan Foto Asli (bag. kanan)

Hasil ekstraksi tepi dari kedua gambar dan message digestnya adalah sebagai berikut :

Gambar 6. Edge Detection Foto Asli (bag. kiri) & Edge Detection Foto Uji dengan brigthness tinggi (bag. kanan)

Message Digest Foto asli :

2757AB106E00BEA8E9F1A7CFEED965627426FBD5

Message Digest Foto Uji :

9292A57C2A84D214B6DF042E16DF9A4227E89884

Gambar 7. Edge Detection Foto Asli (bag. kiri) & Edge Detection Foto Uji dengan brigthness rendah (bag. kanan)

Message Digest Foto asli :

2757AB106E00BEA8E9F1A7CFEED965627426FBD5

Message Digest Foto Uji :

7BD3EDDF7FD4AEDE3DCFCD15D80464F06F564A35

Gambar 8. Edge Detection Foto Asli (bag. kiri) & Edge Detection Foto Uji yang identik dengan Foto Asli (bag. kanan)

Message Digest Foto asli :

2757AB106E00BEA8E9F1A7CFEED965627426FBD5

Message Digest Foto Uji :

2757AB106E00BEA8E9F1A7CFEED965627426FBD5

Dari hasil diatas didapati bahwa meski gambar hasil ekstraksi tepi terlihat sama, setelah di cek

SHA-nya foto tersebut masih menghasilkan message digest yang berbeda. Hal ini dikarenakan masih

banyaknya noise yang muncul dari foto hasil ekstraksi tepi. Metode ini akan menjadi lebih akurat bila pada

tahap canny edge detection dilakukan thresholding yang berulang, sehingga didapat edge detection yang

murni hanya tepi saja tanpa adanya noise.

IV. KESIMPULAN DAN SARAN

A. Kesimpulan

Berikut ini kesimpulan yang dapat ditarik dari implementasi di atas :

Kelebihan :

Besar ruang penyimpanan yang dibutuhkan jauh lebih kecil. Sebagai perbandingan, penyimpanan

dalam bentuk gambar menghabiskan ruang 2 kilo byte sedangkan dengan message digest membuthkan

ruang 40 karakter. Jika satu karakter menghabiskan 1 byte, maka ruang yang dibutuhkan hanya sekitar

40 byte.

Kekurangan :

Hasil message digest dari gambar yang telah diekstraksi tepinya masih berbeda. Hasil ekstraksi tepi

dari setiap gambar belum mereduksi noise hingga tingkat dimana gambar yang didapat hanya tepi yang

menjadi primary key gambar.

Permasalahan :

Permasalahan muncul ketika terdapat satu titik perbedaan pada gambar kartu identitas penduduk yang

tidak dapat direduksi, sehingga hasil message digestnya tidak akan pernah menemui kesamaan dengan

data server. Untuk mengatasi permasalahan ini, kualitas hasil pencetakan gambar foto pada kartu

identitas harus baik, dan pereduksian noise dari gambar hasil ekstraksi adalah pook bahasan yang harus

diselesaikan untuk mendapatkan hasil message digest yang tepat.

B. Saran

Berikut ini saran sebagai masukan penelitian selanjutnya terkait dengan masalah ini :

Penyempurnaan Algoritma Canny :

Perlu adanya evaluasi, percobaan dan pelatihan kembali algoritma Canny yang telah dibangun agar

hasil deteksi tepi yang diharapkan hanya mengindikasikan edge dari objek foto saja dan meminimalisir

adanya edge-edge semu yang dihasilkan karena adanya noise / derau atau karena pengembangan

algoritma yang kurang maksimal.

V. REFERENSI

Afif, Irfan. (2010). Fungsi Hash Biometrik Sebagai Sistem Keamanan Kartu Tanda Penduduk. Diakses pada 18

Juni (2011) dari :

http://www.informatika.org/~rinaldi/Kriptografi/2009-010/Makalah2/Makalah2_IF3058_2010_065.pdf

Anonim. (2011). Canny edge detector. Diakses pada 18 Juni (2011) dari :

http://en.wikipedia.org/wiki/Canny_edge_detector

Anonim. (2011). SHA-1. Diakses pada 18 Juni (2011) dari : http://en.wikipedia.org/wiki/SHA-1

Munir, Rinaldi. (2007). Fungsi Hash. Diakses pada 18 Juni (2011) dari :

http://www.informatika.org/~rinaldi/Kriptografi/2010-2011/Fungsi%20Hash.ppt