## Studi dan Implementasi Pengenalan Wajah dengan Menggunakan Pencocokan String Boyer Moore

## Suharto Siregar
Prodi Teknik Informatika, Universitas Budi Darma, Medan, Indonesia Email: soehartosiregar1@gmail.com
Abstrak− Pengolahan  citra  merupakan  suatu  sistem  dimana  proses  dilakukan  dengan  input  berupa  citra  dan  hasilnya juga  berupa  citra.  Pada  awalnya  pengolahan  citra  ini  dilakukan  untuk  memperbaiki  kualitas  citra,  namun  dengan berkembangnya dunia teknologi yang ditandai dengan semakin meningkatnya kapasitas dan kecepatan proses komputer, serta munculnya ilmu-ilmu komputasi yang memungkinkan manusia dapat mengambil informasi dari suatu citra, maka pengolahan citra tidak dapat dilepaskan dengan bidang computer.Pada peneletian ini pengolahan citra diterapkan untuk pengenalan    wajah  menggunakan  pencocokan  string  boyer  moore.  Boyer  Moore  adalah  salah  satu  teknik  dalam pengolahan  citra    yang  berfungsi  untuk  mencocokan  string.  Permasahan  pada  pengenalan  wajah    adalah  bagaimana melakukan pencarian string pada wajah  berdasarkan  string Boyer Moore  dengan melakukan pencocokan string . Oleh karena itu, sangat penting penelitian yang bertujuan agar komputer dapat memiliki fungsi mendeteksi  wajah . Apabila komputer  dapat  didesain  agar  memiliki  kecerdasan  mendekati  kecerdasan  yang  dimiliki  manusia,  tentu  hal  tersebut dapat memudahkan kerja manusia.
Kata Kunci: Implementasi, Pengenalan Wajah, Pencocokan String
Abstract− Image processing is a system where the process is carried out with the input in the form of an image and the result is also an image. Initially, image processing was carried out to improve image quality, but with the development of the world of technology, which was marked by the increasing capacity and speed of computer processing, as well as the emergence of computational science that allowed humans to retrieve information from an image, image processing could not be separated from it. In this research, image processing is applied to face recognition using moore boyer string matching.  Boyer  Moore  is  a  technique  in  image  processing  that  functions  to  match  strings.  The  problem  of  facial recognition is how to search for strings on faces based on Boyer Moore's strings by matching the strings. Therefore, it is very  important  research  that  aims  so  that  computers  can  have  the  function  of  detecting  faces.  If  computers  can  be designed to have intelligence closer to that of humans, of course this can facilitate human work.
Keywords : Implementation, Face Recognition, String Matching

## 1. PENDAHULUAN
Sistem identifikasi merupakan hal yang penting. Salah satu sistem identifikasi yang banyak dikembangkan saat ini yaitu sistem  identifikasi  menggunakan  informasi  biologis  yaitu  sidik  jari,  wajah,  retina,  suara  dan  lain-lain.  Salah  satu informasi  biologis  yang  sekarang  banyak  dikembangkan  dan  memiliki  tingkat  keakuratan  tinggi  yaitu  wajah.  Wajah seseorang  memiliki  ciri  unik  masing-masing  yang  dapat  diidentifikasi.  Identifikasi  tersebut  dapat  digunakan  untuk sistem  pencarian  seseorang  di  dalam  sebuah  gambar  yang  berisi  wajah. Eigenface merupakan  salah  satu  metode pengenalan  wajah  berdasarkan Principal  Component  Analysis (PCA)  yang  mudah  diimplementasikan  [1].  Lyon  dan Vincent melakukan sebuah penelitian untuk membuat sebuah prototype ―Interactive Embedded Face Recognition [2]. Sistem  ini  menghadirkan  pendekatan  warna  kulit  menggunakan  warna  YCbCr  untuk  pendeteksian  wajah  yang  lebih akurat. Pemrosesan gambar wajah ini menggunakan kombinasi operator morfologi dan elliptical shape dari wajah untuk proses  segmentasi  wajah.  Secara  umum,  proses  pendeteksian  wajah  ini  dimulai  dengan  pengambilan  gambar, pendeteksian kulit, pendeteksian wajah untuk selanjutnya dilakukan face recognition.
Pengenalan  wajah  adalah  suatu  metode  pengenalan  yang  berorientasi  pada  wajah.  Pengenalan  ini dapat  dibagi menjadi dua bagian yaitu : Dikenali atau tidak dikenali, setelah dilakukan perbandingan dengan pola yang sebelumnya disimpan di dalam database.
Latar  belakang  masalah  ini  diawali  dengan  adanya  kebutuhan  teknik  pengenalan  wajah  yang  memiliki  akurasi diatas rata-rata dan mampu mengatasi kondisi variasi pencahayaan yang ekstrim untuk diimplementasikan pada kondisi real-time.
Salah satu jenis pengenalan pola yang banyak dikembangkan yaitu String Boyer Moore. Algoritma Boyer-Moore adalah salah satu algoritma pencarian string, yang diterbitkan oleh Robert S. Boyer, dan J. Strother Moore pada tahun 1977. Algoritma ini dianggap sebagai  algoritma aplikasi  umum yang paling efisien. Tidak seperti algoritma pencarian string  yang  ditemukan  sebelumnya,  algoritma  Boyer-Moore  mulai  mencocokkan  karakter  dari  sisi  kanan  pola.  Ide dibalik Algoritma ini adalah bahwa dengan memulai karakter yang cocok dari kanan, dan bukan dari kiri, lebih banyak informasi  akan  didapat.  Algoritma  Boyer  Moore  mencakup  algoritma  pencocokan  stringyang  paling  efisien dibandingkan  algoritma  pencocokan  string  lainnya.  Karena  sifatnya  yang  efisien,banyak  algoritma  pencocokan  string telah  dikembangkan  berdasarkan  konsep  algoritma  Boyer  Moore.  Algoritma  Boyer  Moore  menggunakan  metode pencocokan string dari kanan ke kiri yaitu memindai pola karakter dari kanan ke kiri mulai dari karakter paling kanan.
Algoritma  Boyer  Moore  menggunakan  dua  fungsi  shift:  pergeseran  akhiran  yang  baik  dan  pergeseran  karakter  buruk untuk mengambil langkah berikutnya setelah ketidakcocokan antara pola karakter dan karakter teks yang sesuai

## 2. METODOLOGI PENELITIAN

## 2.2 Pengolahan Citra
Pengolahan citra digital (Digital Image Processing) adalah sebuah disiplin ilmu yang mempelajari tentang teknik-teknik mengolah  citra.  Citra  yang  dimaksud  disini  adalah  gambar  diam  (foto)  maupun  gambar  bergerak  (yang  berasal  dari webcam).  Sedangkan  digital  disini  mempunyai  maksud  bahwa  pengolahan  citra/gambar  dilakukan  secara  digital menggunakan komputer. Secara matematis, citra merupakan fungsi kontinyu (continue) dengan intensitas cahaya pada bidang dua dimensi. Agar dapat diolah dengan komputer digital, maka suatu citra harus dipresentasikan secara numerik dengan nilai-nilai diskrit. Repersentasi dari fungsi kontinyu menjadi nilai-nilai diskrit disebut digitalisasi citra. Sebuah citra  digital  dapat  diwakili  oleh  sebuah  matriks  dua  dimensi  f(x,y)  yang  terdiri  dari  M  kolom  dan  N  baris,  dimana perpotongan antara kolom dan baris disebut piksel (pixel = picture element) atau elemen terkecil dari sebuah citra.

## 2.3 Citra
Istilah citra digital menyatakan pemrosesan gambar berdimensi  dua melalui komputer digital. Pengolahan citra adalah istilah umum untuk berbagai teknik yang keberadaannya untuk memanipulasi dan memodifikasi citra dengan berbagai cara, foto merupakan gambar berdimensi dua yang dapat diolah  dengan mudah, setiap foto dalam bentuk citra digital (misalnya  berasal  dari  kamera  digital)  dapat  diolah  melalui  perangkat  lunak  tertentu.  Secara  umum  pengolahan  citra digital  menunjuk  pada  pemrosesan  gambar  2  dimensi  menggunakan  komputer.  Dalam  konteks  yang  lebih  luas, pengolahan  citra  digital  mengacu  pada  pemrosesan  setiap  data  2  dimensi.  Citra  digital  merupakansebuah  larik  (array) yang berisi nilai-nilai real maupun komlek yang direprentasikan dengan deretan bit tertentu.

## 2.4 Wajah
Wajah merupakan bagian dari tubuh manusia yang menjadi fokus perhatian di dalam interaksi sosial, wajah memainkan peranan  vital  dengan  menunjukan  identitas  dan  emosi.  Kemampuan  manusia  untuk  mengetahui  seseorang  dari wajahnya sangat  luar biasa. Kita dapat  mengenali ribuan wajah karena frekuensi  interaksi  yang sangat  sering  ataupun hanya  sekilas  bahkan  dalam  rentang  waktu  yang  sangat  lama.  Bahkan  kita  mampu  mengenali  seseorang  walaupun terjadi perubahan pada orang tersebut karena bertambahnya usia atau pemakaian kacamata atau perubahan gaya rambut. Oleh karena itu wajah digunakan sebagai organ dari tubuh manusia yang dijadikan indikasi pengenalan seseorang atau face recognition -abuan.

## 2.5 Metode Boyer Moore
Algoritma  boyer  moore  termasuk  alogritma string  matching yang  paling  efisien  dibandingkan  algotitma string matcthing lainya.karena  sifatnya  yang  efisien,  banya  k  dikembangkan  algoritma  string  matching  yang  bertumpu  pada konsep  algoritma  boyer  moore.  Algoritma  boyer  moore  menggunakan  metode  pencocokan  string  dari  kanan  ke  kiri yaitu  men scan karakter pattern dari  kanan  ke  kiri  dimulai  dari  karakter  paling  kanan.  Algoritma  boyer  moore menggunakan  dua  fungsi shift yaitu, good  suffix  shift dan bad  character  shift untuk  mengambil  langkah  berikutnya setelah ketidak cocokan anar karakter pattern dan karakter teks yang dicocokkan.(Sulistyo,Adie Pradipto dan Adi Setia Perwira.(2006).

## 3. HASIL DAN PEMBAHASAN
Pengambilan  gambar  wajah  yang  dilakukan  secara  konvensional  kemudian  wajah  tersebut  diklasifikasikan  secara manual  sesuai  dengan  pola  dan  juga  jumlah  ridge  yang  terlihat.  Proses  pencarian  dilakukan  secara  manual  dengan mencocokkan  berdasarkan  pola  dan  jumlah  ridge  yang  mendekat.  Untuk  mengubah  sistem  manual  tersebut  ke  dalam sistem yang terkomputerisasi maka data wajah tersebut akan dipindai dan dimasukkan ke dalam basis data sistem. Pada gambar  wajah  yang  akan  dipindai  memungkinkan  adanya  kesalahan-kesalahan  yang  menyebabkan  beberapa  gambar terhapus dikarenakan beberapa hal  seperti, kotoran diwajah, kulit yang terlipat dan lain sebagainya. Setiap data wajah tersebut kemudian diubah menjadi array dua dimensi untuk merpresentasikan setiap koordinat pixel dari gambar. Array tersebut  akan berisi string biner 1 atau 0, dimana 1 menunjukkan warna hitam dan 0 menunjukan warna putih, sesuai dengan data pixel yang diambil. Berikut adalah hasil  dari pengambilan gambar:
Gambar 1. Hasil pengambilan gambar

## 3.2 Penerapan Algoritma Boyer-Moore
Kali  ini  penulis  akan  menjelaskan  cara  kerja  dari  sebuah  algoritma  pencarian  karakter  dalam  gambar  wajah  yaitu algoritma  boyer  moore.  Boyer  moore  secara  rata-rata  meruakan  algoritma  pencarian string yang  paling  baik  jika dibandingkan  dengan  algoritma  pencarian string lainnya  seperti Brute-Force ataupun Knuth-morris  pratt .  Jika  kita menggunakan  fasilitas find atau  search  pada  berbagai  aplikasi  pengilah  teks,  web Browser ,  dabn  aplikasi  lainnya mungkin  saja  kita  telah  memamfaatkan  algoritma  boyer  moore  dalam  pencarian  tersebut,  karena  algoritma  ini  paling banyak di implementasikan dalam berbagai aplikasi untuk fasilitas pencarian teksnya.
Berikut ini adalah langkah-langkah dari algoritma Boyer Moore yakni sebagai berikut:
1. Algoritma Boyer Moore mulai dengan membentuk sebuah array geser yang berisi daftar yang akan dicari.
2. Dilakukan pencocokan kembali terhadap karakter yang sejajar dengan kata yang dicari.
3. Lakukan pengecekan panjang karakter pada seluruh hasil encocokan yang diperoleh.
Untuk  mengetahui  tingkat  keakuratan  pengenalan  wajah  dilakukan  pengujian  dengan  beberapa  contoh  gambar wajah. Basis data sudah berisi data sejumlah gambar wajah. Contoh sebuah gambar wajah di dalam basis data beserta representasi sebagian stringnya diperlihatkan pada gambar.
..à(((XXXXåãîîà±±PR&...
þîîæ !íåæââåá¡/?/(?¾¼þûû÷û(_ °ßàâæ¢v( ̄/(,,ïã§#ç ̄/??ÿ àâîþ££çç¾^° ̄àââíëûûç ̄?_
°° ̄àâáåíííû#(çáï§ççç ̄ûû þøç÷ûþååææ--¬°_ ̄ÿïç÷ûíâ à ̄ ̄=!¡±¬®,°°_/ãîæßßßß_#
Pada  gambar  memperlihatkan  tiga  buah  pattern  yang  dicocokkan  dan  string  yang  diambil.  Pattern  pertama normal, yang kedua bagian wajah sebelah kiri , dan ketiga bagian wajah sebelah kanan.
ýàíû£((W°°âæþþíí÷ ̄? ?_°°ââææíûç
ààæîýç/??_ààßíãç(//® , ?°°° íC#/((_à-P Èæâàâîîîp^? ̄âþà`(ßß°
Gambar 3. Contoh pattern dan string yang diambil
Dari pengujian diperoleh hasil bahwa untuk pattern wajah  yang normal  berhasil dikenali (cocok dengan data di dalam basis data). Tetapi, untuk gambar wajah yang terpotong  masih belum bisa dikenali dengan baik oleh perangkat lunak ini. Hal ini disebabkan pengambilan data dari hasil pembagian  gambar tidak tepat sama dengan data wajah yang terdapat di basis data.
Untuk  pengambilan  gambar  wajah  yang  ingin  dicocokan  juga  dilakukan  proses  yang  hampir  sama.  Kemudian, data  tersebut  diambil  bagian  yang  akan  dicocokan  dan  selanjutnya  diubah  menjadi  data  biner.  Data  biner  tersebut diubah  menjadi string yang  akan  dikenali  dengan  mencocokkannya  ke  basis  data.  Setelah  nilai eigen didapat  maka tahap  selanjutnya  yakni  mengambil  citra  wajah  yang  akan  diujikan  ke  sistem  pengenalan  wajah,  citra  uji  ini  terlebih dahulu dihitung juga nilai eigen -nya.
Berikut nilai ASCII dari gambar wajah diterakan seperti gambar dibawah ini:
Gambar 4 . Hasil Konversi nilai citra gambar
Pencarian string setelah diubah kedalam bentuk biner: 46 = 00101110 = . 50 = 00110010 = 2 0   = 00000000 = 0   = 00000000 = 25 = 00011001 = EM 35 = 00100011 = # 0   = 00000000 = 0   = 00000000 = 0   = 00000000 = 0   = 00000000 = 48 = 00110000 = 0 51 = 00110011 = 3 26 = 00011010 =  ? 28 = 00011100 = FS 60 = 00111100 =  < 72 = 010011000 = H 153= 10011001 = ™ 161= 10010001 = i 152= 10011000 = 160 = 10100000 = 2 33 = 00100001 = y
72 = 01001000 = H 121= 01111001= Y 140= 10001100 =  і 139= 10001011 =  ‹
Langkah-langkah Algoritma Boyer Moore: Teks : . EM 2 # 0 ? < ™   3 FS H I 2 y H Y I ‹ Pattern : H Y i
. EM 2 # 0 ? < ™ 3 FS H i 2 i y H Y     i ‹
H Y i

## Langkah 1
Pada pergeseran pattern langkah 1 dapat dilihat bahwa karakter “2” tidak cocok dengan karakter “i” pada pattern, maka dilakukan  pergeseran  dari  posisi  kanan  karakter  yang  sejajar  pada  teks   “ . EM  2  #  0  ?  <  ™    3  FS  H I  2  y  H  Y  I  ‹ “karakter yang sejajar pada teks  “ . EM 2 # 0 ? < ™   3 FS H I 2 y H Y I ‹ “
. EM 2 # 0 ? < ™ 3 FS H i 2 i  y H Y     i  ‹
H Y i

## Langkah 2
Pada pergeseran pattern langkah 2 dapat dilihat bahwa karakter “<” tidak cocok dengan karakter “i” pada pattern, maka dilakukan pergeseran dari posisi kanan karakter yang sejajar pada teks  “ . EM 2 # 0 ? < ™   3 FS H I 2 y H Y I ‹ “
. EM 2 # 0 ? < ™ 3 FS H i 2 i  y H Y     i  ‹
H Y i
Pada  pergeseran  pattern  lankgah  3  dapat  dilihat  bahwa  karakter  “FS”  tidak  cocok  dengan  karakter  “i”  pada  pattern, maka dilakukan pergeseran dari posisi kanan karakter yang sejajar pada teks  “ . EM 2 # 0 ? < ™   3 FS H I 2 y H Y I ‹ “ Langkah 4
. EM 2 # 0 ? < ™ 3 FS H i 2 i y H Y     i  ‹ H Y i
Pada pergeseran pattern langkah 4 dapat dilihat bahwa karakter “y” tidak cocok dengan karakter “i” pada pattern, maka dilakukan pergeseran dari posisi kanan karakter yang sejajar pada teks  “ . EM 2 # 0 ? < ™   3 FS H I 2 y H Y I ‹ “
. EM 2 # 0 ? < ™ 3 FS H i 2 i y H Y     i  ‹ H Y i

## Langkah 5
Pada  pergeseran  pattern  langkah  5  dapat  dilihat  bahwa  karakter  “H”  tidak  cocok  dengan  karakter  “H”  pada  pattern, maka pencarian dapat dikatakan selesai.
Pada langkah ke-5 ditemukan kecocokan antara pattern dengan teks, sehingga pencarian dapat dikatakan selesai, karna karakter pada pattern sudah cocok terhadap karakter pada teks secara menyeluruh, dimana keberadaan pattern pada teks ditemukan hanya satu kali.
Maka dalam pencarian string dengan algoritma boyer moore untuk setiap krakter pada pattern akan dicocokkan satu  per  satu  dengan  karakter  yang  ada  pada  teks.  Dari  analisa  proses  pencarian  Algoritma  boyer moore  sebelumnya, dapat disimpulkan bahwa, apabila pattern “HYi” diketikkan, maka teks akan muncul pada pencarian.

## 4. KESIMPULAN
Berdasarkan hasil penelitian yang telah dilakukan dapat diambil kesimpulan sebagai berikut:
1. Algoritma Boyer Moore dapat diterapkan untuk deteksi Pengenalan Wajah.
2. Implementasi sistem menggunakan Aplikasi Matlab 6.1 dalam  pengenalan wajah yang memberikan hasil yang baik yang disimpan sebelumnya dengan nilai pencocokan baik.
3. Pengenalan Wajah dapat dilakukan dengan memamfaatkan algoritma Boyer Moore
4. Wajah yang merupakan string biner diubah menjadi ASCII untuk melakukan pencarian 8 baris sekaligus agar daerah pencocokan tidak hanya satu baris saja

## REFERENCES
[1] R. D. Kusumanto and A. N. Tompunu, “Pengolahan Citra Digital Untuk Mendeteksi Obyek Menggunakan Pengolahan Warna Model Normalisasi RGB,” Semin. Nas. Teknol. Inf. Komun. Terap. 2011 , vol. 2011, no. Semantik, pp. 1–7, 2011.
[2] Rinaldi Munir, Pengolahan Citra Digital dengan Pendekatan Algoritmik . Bandung, 2004.
[3] Candra Noor Santi, “Mengubah Citra Berwarna Menjadi Gray­Scale dan Citra biner,” Teknol. Inf. Din. , vol. 16, no. 1, pp. 14– 19, 2011.
[4] Saminan, “Efek Penyimpangan Refraksi Cahaya Dalam Mata Terhadap Rabun Dekat atau Jauh,” Idea Nurs. J. , vol. IV, no. 2, pp. 26–29, 2013.
[5] Y.  Rijal  and  R.  D.  Ariefianto,  “Deteksi  Wajah  Berbasis  Segmentasi  Model  Warna  Menggunakan  Template  Matching  pada Objek Bergerak,” Semin. Nas. Apl. Teknol. Inf. 2008 , vol. 2008, no. Snati, pp. 35–42, 2008.
[6] A. W. Wardhana and Y. Prayudi, “Penggunaan Metode Templete Matching untuk Identifikasi Kecacatan pada PCB,” Semin. Nas. Apl. Teknol. Inf. , vol. 2008, no. Snati, pp. 45–50, 2008.
[7] Adi Nugroho, Rekayasa Perangkat Lunak menggunakan UML dan Java . Yogyakarta, 2010.
[8] Zaini, “Model Penyelesaian Determinan Matriks dengan Metode Eliminasi Gauss Melalui Matrix Laboratory ( MATLAB ),” J. Sains Terap. , vol. 3, no. 1, pp. 15–21, 2017.
[9] Primananda Arif Aditya, Dasar-dasar Pemrograman Database Desktop dengan Microsoft Visual Basic.Net 2008 . 2008.
[10]  K. Umam and B. S. Negara, “Deteksi Obyek Manusia Pada Basis Data Video Menggunakan Metode Background Subtraction Dan Operasi Morfologi,” J. CoreIT , vol. 2, no. 2, pp. 31–40, 2016.
[11]  Abdul kadir & Adhi susanto, Teori dan Aplikasi Pengolahan Citra . Yogyakarta: Andi, 2013.