Template matching adalah sebuah teknik dalam pengolahan citra digital untuk menemukan bagian-bagian kecil dari gambar yang cocok dengan template gambar. Template matching merupakan salah satu ide yang digunakan untuk menjelaskan bagaimana otak kita mengenali kembali bentuk-bentuk atau pola-pola. Template dalam konteks rekognisi pola menunjuk pada konstruk internal yang jika cocok (match ) dengan stimulus penginderaan mengantar pada rekognisi suatu objek. Atau pengenalan pola terjadi jika terjadi kesesuaian antara stimulus indera dengan bentuk mental internal. Gagasan ini mendukung bahwa sejumlah besar template telah tercipta melalui pengalaman hidup kita. Tiap-tiap template berhubungan dengan suatu makna tertentu.
Contoh proses identifikasi bentuk geometri :
Energi cahaya yang terpancar dari suatu bentuk mengena pada retina mata dan diubah menjadi energi neural yang kemudian dikirim ke otak. Selanjutnya terjadi pencarian di antara templatetemplate yang ada. Jika sebuah template ditemukan sesuai (match ) dengan pola tadi, maka subjek dapat mengenal bentuk tersebut. Setelah kecocokan antara objek dan template terjadi, proses lebih lanjut dan interpretasi terhadap objek bisa terjadi.
Keunggulan :
Kelemahan :
Jika perbandingan eksternal objek dgn internal objek 1:1, maka objek yang berbeda sedikit saja dengan template tidak akan dikenali. Oleh karena itu, jutaan template yang spesifik perlu dibuat agar cocok dengan berbagai bentuk geometri yang kita lihat dan kenal. Jika memang penyimpanan memori di otak seperti ini, otak tentu seharusnya sangat kewalahan dan pencarian informasi akan memakan waktu, padahal pada kenyataannya tidak demikian.
Template Matching dapat dibagi antara dua pendekatan, yaitu : pendekatan berbasis fitur dan pendekatan berbasis template. Pendekatan berbasis fitur menggunakan fitur pencarian dan template gambar seperti tepi atau sudut, sebagai pembanding pengukuran matrik untuk menemukan lokasi template matching yang terbagus di sumber gambar.
Pendekatan Berbasis Fitur.
Sebuah pendekatan berbasis fitur dapat dianggap; pendekatan dapat membuktikan lebih berguna, jika template gambar memiliki fitur yang kuat jika pencocokan di pencarian gambar bisa diubah dengan cara tertentu. Karena pendekatan ini tidak mempertimbangkan keseluruhan dari template gambar, komputasi dapat lebih efisien ketika bekerja dengan sumber gambar beresolusi lebih besar, sebagai pendekatan alternatif, berbasis template, mungkin memerlukan pencarian titik – titik yang berpotensi untuk menentukan lokasi pencocokan yang terbaik.
Pendekatan Berbasis Template
Untuk template tanpa fitur yang kuat, atau ketika sebagian besar template gambar merupakan gambar yang cocok, sebuah pendekatan berbasis template mungkin efektif. Seperti disebutkan di atas, karena berbasis template, template matching berpotensi memerlukan sampling dari sejumlah besar poin, untuk mengurangi jumlah sampling poin dengan mengurangi resolusi pencarian dan template gambar oleh faktor yang sama dan melakukan operasi pada perampingan gambar yang dihasilkan (multiresolusi, atau piramida, pengolahan citra), menyediakan pencarian titik data dalam pencarian gambar sehingga template tidak harus mempunyai pencarian titik data, atau kombinasi keduanya.
Implementasi
Dalam implementasi sederhana ini, diasumsikan bahwa metode yang dijelaskan di atas diterapkan pada gambar abu-abu: karena abu-abu digunakan sebagai intensitas piksel.
minSAD = VALUE_MAX;
// loop through the search image
for ( int x = 0; x <= S_rows - T_rows; x++ ) {
for ( int y = 0; y <= S_cols - T_cols; y++ ) {
SAD = 0.0;
// loop through the template image
for ( int i = 0; i < T_rows; i++ )
for ( int j = 0; j < T_cols; j++ ) {
pixel p_SearchIMG = S[x+i][y+j];
pixel p_TemplateIMG = T[i][j];
SAD += abs( p_SearchIMG.Grey - p_TemplateIMG.Grey );
}
}
// save the best found position
if ( minSAD > SAD ) {
minSAD = SAD;
// give me VALUE_MAX
position.bestRow = x;
position.bestCol = y;
position.bestSAD = SAD;
}
}
Study kasus
Contoh Aplikasi
“PENGGUNAAN METODE TEMPLETE MATCHING UNTUK IDENTIFIKASI KECACATAN PADA PCB”
Penerapan metode template matching pada identifikasi kecacatan PCB dapat dilakukan dengan langkah utama sbb:
1. Pengepasan posisi: Dilakukan dengan mencuplik 80% area citra untuk mendapatkan posisi ideal.
2. Hitung nilai korelasi silang : Untuk mengklasifikasikan suatu citra PCB adalah baik dan tanpa cacat sedikitpun, maka nilai korelasi adalah 1 dan cacat total maka nilai korelasinya adalah -1. Rumus yang digunakan adalah :
Dengan :
3. Deteksi akhir : Dari nilai korelasi yang didapat, nilai tersebut kemudian di konversikan dalam rentang 0 sampai 255 pada channel red untuk digambarkan dalam bentuk segiempat pada titik koordinat citra PCB yang mengalami cacat.
Prinsip metode ini adalah membandingkan antara image objek yang akan dikenali dengan image template yang ada. Image objek yang akan dikenali mempunyai tingkat kemiripan sendiri terhadap masing-masing image template.
Pengenalan dilakukan dengan melihat nilai tingkatkemiripan tertinggi dan nilai batas ambang pengenalan dari image objek tersebut. Bila nilai tingkat kemiripan berada di bawah nilai batas ambang maka image objek tersebut dikategorikan sebagai objek tidak dikenal.
Selanjutnya untuk dapat mengimplementasikan metode templete matching maka perlu dilakukan sejumlah operasi pengolahan citra digital, antara lain:
• Penapisan Citra (Filtering) : dilakukan bila citra yang akan dianalisis memiliki derau sehingga perlu dihaluskan dengan tapis citra. Perancangan tapis dengan memanipulasi piksel-piksel tetangga membuat citra lebih halus, bentuk sudut, dan tepi citra tetap terjaga. Pada proses perekaman citra digital dapat terjadi gangguan yang bersifat frekuensi rendah, dimana terjadi proses pemerataan intensitas cahaya pada suatu titik sampel dengan titik-titik tetangganya. Gangguan lain yang sering terjadi pada proses perekaman citra digital adalah terjadinya gangguan berbentuk garis-garis akibat adanya kerusakan pada sebagian detektor sensor. Juga sering dijumpai gangguan lain dalam bentuk bercak hitam yang acak.
• Pengambangan (Tresholding) : digunakan untuk mengubah citra dengan format keabuan yang mempunyai nilai lebih dari dua ke format citra biner yang hanya memiliki dua nilai (0 atau 1). Dalam hal ini titik dengan rentang nilai keabuan tertentu diubah menjadi warna hitam dan sisanya menjadi warna putih atau sebaliknya.
Aplikasi yang akan dibangun adalah sebuah simulasi sederhana untuk proses AOI (Automated Optical Inspection), dalam hal ini diasumsikan PCB master dan PCB input deteksi telah tersedia dalam bentuk file bitmap.
Secara umum implementasi dari identifikasi kecacatan PCB dengan menggunakan metode Templete Matching ini dapat digambarkan sebagaimana pada Gambar 1. Pada Gambar 1 tersebut :
• Grayscale digunakan untuk merubah citra warna menjadi citra keabuan.
• Median Filter : Digunakan untuk melakukan proses penapisan jika citra dianggap masih mengandung derau.
• Batas Ambang : Digunakan untuk mengatur tingkat proses pengambangan pada citra
Gambar 1 Penerapan Templete Matching pada Identifikasi Cacat PCB
Pada penelitian sejenis, umumnya output dari penggunaan templete matching adalah berupa prosentase kemiripan antara image master dengan image input. Untuk permasalahan identifikasi kecacatan pada PCB ini, maka outputnya adalah posisi blok pada PCB input yang tidak sesuaidengan PCB master. Posisi blok itulah yang diidentifikasi terdapat kecacatan.
Pada penelitian ini dilakukan upaya untuk mendeteksi kecacatan pada PCB RAM. Dalam hal ini digunakan dua buah model PCB, yaitu PCB acuan (master) dan PCB RAM yang cacat. Aplikasi akan berusaha untuk mendeteksi kecacatan yang terjadi dalam bentuk output yang menunjukkan letak titik kecacatan pada PCB RAM tersebut. Masing-masing PCB yang digunakan adalah sebuah citra berkarakteristik bitmap.
Sebelum digunakan sebagai acuan pada pada proses templete matching ini,maka PCB master terlebih dahulu dibuatkan model grayscalenya. Pembentukan model grayscale ini dilakukan setelah sebelumnya menerapkan pemrosesan penapisan dan pengambangan citra. Gambar 2 menunjukkan pola grayscale dari PCB master.
Hal yang serupa juga dilakukan pada model PCB yang akan diidentifikasi. Gambar 3 menunjukkan pola PCB masukan yang siap diidentifikasi. Terlihat secara sekilas antara dua pola gambar tersebut tidak nampak perbedaan. Dengan demikian apabila inspeksi kecacatan dilakukan secara manual maka tidak akan mudah terdeteksi.
Setelah dua buah citra tersebut diproses dengan menggunakan aplikasi templete matching, maka terlihat hasil identifikasinya berupa lokasi dimana terdapat ketidak cocokan pola dan diasumsikan bahwa pada lokasi tersebut terdapat kecacatan PCB.Dalam hal ini titik-titik yang dianggap cacat karena tidak sesuai dengan citra pada master akan ditandai dengan blok korelasi berwarna merah dimana ukuran blok korelasi tersebut telah ditentukan sebelumnya oleh user. Gambar 4 menunjukkan output hasil template matching pada PCB input. Pada Gambar 4 tersebut terlihat adanya blok korelasi pada titik yang dianggap cacat karena memiliki kesalahan berupa putusnya jalur sirkuit PCB.
Contoh proses identifikasi bentuk geometri :
Energi cahaya yang terpancar dari suatu bentuk mengena pada retina mata dan diubah menjadi energi neural yang kemudian dikirim ke otak. Selanjutnya terjadi pencarian di antara templatetemplate yang ada. Jika sebuah template ditemukan sesuai (match ) dengan pola tadi, maka subjek dapat mengenal bentuk tersebut. Setelah kecocokan antara objek dan template terjadi, proses lebih lanjut dan interpretasi terhadap objek bisa terjadi.
Keunggulan :
- Jelas bahwa untuk mengenal bentuk, huruf atau bentuk-bentuk visual lainnya diperlukan kontak dengan bentuk-bentuk internal.
- Template matching adalah prosedur pengenalan pola yang sederhana yang didasarkan pada ketepatan konfigurasi informasi penginderaan dengan “konfigurasi” pada otak. (Contohnya : barcode)
Kelemahan :
Jika perbandingan eksternal objek dgn internal objek 1:1, maka objek yang berbeda sedikit saja dengan template tidak akan dikenali. Oleh karena itu, jutaan template yang spesifik perlu dibuat agar cocok dengan berbagai bentuk geometri yang kita lihat dan kenal. Jika memang penyimpanan memori di otak seperti ini, otak tentu seharusnya sangat kewalahan dan pencarian informasi akan memakan waktu, padahal pada kenyataannya tidak demikian.
Template Matching dapat dibagi antara dua pendekatan, yaitu : pendekatan berbasis fitur dan pendekatan berbasis template. Pendekatan berbasis fitur menggunakan fitur pencarian dan template gambar seperti tepi atau sudut, sebagai pembanding pengukuran matrik untuk menemukan lokasi template matching yang terbagus di sumber gambar.
Pendekatan Berbasis Fitur.
Sebuah pendekatan berbasis fitur dapat dianggap; pendekatan dapat membuktikan lebih berguna, jika template gambar memiliki fitur yang kuat jika pencocokan di pencarian gambar bisa diubah dengan cara tertentu. Karena pendekatan ini tidak mempertimbangkan keseluruhan dari template gambar, komputasi dapat lebih efisien ketika bekerja dengan sumber gambar beresolusi lebih besar, sebagai pendekatan alternatif, berbasis template, mungkin memerlukan pencarian titik – titik yang berpotensi untuk menentukan lokasi pencocokan yang terbaik.
Pendekatan Berbasis Template
Untuk template tanpa fitur yang kuat, atau ketika sebagian besar template gambar merupakan gambar yang cocok, sebuah pendekatan berbasis template mungkin efektif. Seperti disebutkan di atas, karena berbasis template, template matching berpotensi memerlukan sampling dari sejumlah besar poin, untuk mengurangi jumlah sampling poin dengan mengurangi resolusi pencarian dan template gambar oleh faktor yang sama dan melakukan operasi pada perampingan gambar yang dihasilkan (multiresolusi, atau piramida, pengolahan citra), menyediakan pencarian titik data dalam pencarian gambar sehingga template tidak harus mempunyai pencarian titik data, atau kombinasi keduanya.
Implementasi
Dalam implementasi sederhana ini, diasumsikan bahwa metode yang dijelaskan di atas diterapkan pada gambar abu-abu: karena abu-abu digunakan sebagai intensitas piksel.
minSAD = VALUE_MAX;
// loop through the search image
for ( int x = 0; x <= S_rows - T_rows; x++ ) {
for ( int y = 0; y <= S_cols - T_cols; y++ ) {
SAD = 0.0;
// loop through the template image
for ( int i = 0; i < T_rows; i++ )
for ( int j = 0; j < T_cols; j++ ) {
pixel p_SearchIMG = S[x+i][y+j];
pixel p_TemplateIMG = T[i][j];
SAD += abs( p_SearchIMG.Grey - p_TemplateIMG.Grey );
}
}
// save the best found position
if ( minSAD > SAD ) {
minSAD = SAD;
// give me VALUE_MAX
position.bestRow = x;
position.bestCol = y;
position.bestSAD = SAD;
}
}
Study kasus
Contoh Aplikasi
“PENGGUNAAN METODE TEMPLETE MATCHING UNTUK IDENTIFIKASI KECACATAN PADA PCB”
Penerapan metode template matching pada identifikasi kecacatan PCB dapat dilakukan dengan langkah utama sbb:
1. Pengepasan posisi: Dilakukan dengan mencuplik 80% area citra untuk mendapatkan posisi ideal.
2. Hitung nilai korelasi silang : Untuk mengklasifikasikan suatu citra PCB adalah baik dan tanpa cacat sedikitpun, maka nilai korelasi adalah 1 dan cacat total maka nilai korelasinya adalah -1. Rumus yang digunakan adalah :
Dengan :
3. Deteksi akhir : Dari nilai korelasi yang didapat, nilai tersebut kemudian di konversikan dalam rentang 0 sampai 255 pada channel red untuk digambarkan dalam bentuk segiempat pada titik koordinat citra PCB yang mengalami cacat.
Prinsip metode ini adalah membandingkan antara image objek yang akan dikenali dengan image template yang ada. Image objek yang akan dikenali mempunyai tingkat kemiripan sendiri terhadap masing-masing image template.
Pengenalan dilakukan dengan melihat nilai tingkatkemiripan tertinggi dan nilai batas ambang pengenalan dari image objek tersebut. Bila nilai tingkat kemiripan berada di bawah nilai batas ambang maka image objek tersebut dikategorikan sebagai objek tidak dikenal.
Selanjutnya untuk dapat mengimplementasikan metode templete matching maka perlu dilakukan sejumlah operasi pengolahan citra digital, antara lain:
• Penapisan Citra (Filtering) : dilakukan bila citra yang akan dianalisis memiliki derau sehingga perlu dihaluskan dengan tapis citra. Perancangan tapis dengan memanipulasi piksel-piksel tetangga membuat citra lebih halus, bentuk sudut, dan tepi citra tetap terjaga. Pada proses perekaman citra digital dapat terjadi gangguan yang bersifat frekuensi rendah, dimana terjadi proses pemerataan intensitas cahaya pada suatu titik sampel dengan titik-titik tetangganya. Gangguan lain yang sering terjadi pada proses perekaman citra digital adalah terjadinya gangguan berbentuk garis-garis akibat adanya kerusakan pada sebagian detektor sensor. Juga sering dijumpai gangguan lain dalam bentuk bercak hitam yang acak.
• Pengambangan (Tresholding) : digunakan untuk mengubah citra dengan format keabuan yang mempunyai nilai lebih dari dua ke format citra biner yang hanya memiliki dua nilai (0 atau 1). Dalam hal ini titik dengan rentang nilai keabuan tertentu diubah menjadi warna hitam dan sisanya menjadi warna putih atau sebaliknya.
Aplikasi yang akan dibangun adalah sebuah simulasi sederhana untuk proses AOI (Automated Optical Inspection), dalam hal ini diasumsikan PCB master dan PCB input deteksi telah tersedia dalam bentuk file bitmap.
Secara umum implementasi dari identifikasi kecacatan PCB dengan menggunakan metode Templete Matching ini dapat digambarkan sebagaimana pada Gambar 1. Pada Gambar 1 tersebut :
• Grayscale digunakan untuk merubah citra warna menjadi citra keabuan.
• Median Filter : Digunakan untuk melakukan proses penapisan jika citra dianggap masih mengandung derau.
• Batas Ambang : Digunakan untuk mengatur tingkat proses pengambangan pada citra
Gambar 1 Penerapan Templete Matching pada Identifikasi Cacat PCB
Pada penelitian sejenis, umumnya output dari penggunaan templete matching adalah berupa prosentase kemiripan antara image master dengan image input. Untuk permasalahan identifikasi kecacatan pada PCB ini, maka outputnya adalah posisi blok pada PCB input yang tidak sesuaidengan PCB master. Posisi blok itulah yang diidentifikasi terdapat kecacatan.
Pada penelitian ini dilakukan upaya untuk mendeteksi kecacatan pada PCB RAM. Dalam hal ini digunakan dua buah model PCB, yaitu PCB acuan (master) dan PCB RAM yang cacat. Aplikasi akan berusaha untuk mendeteksi kecacatan yang terjadi dalam bentuk output yang menunjukkan letak titik kecacatan pada PCB RAM tersebut. Masing-masing PCB yang digunakan adalah sebuah citra berkarakteristik bitmap.
Sebelum digunakan sebagai acuan pada pada proses templete matching ini,maka PCB master terlebih dahulu dibuatkan model grayscalenya. Pembentukan model grayscale ini dilakukan setelah sebelumnya menerapkan pemrosesan penapisan dan pengambangan citra. Gambar 2 menunjukkan pola grayscale dari PCB master.
Hal yang serupa juga dilakukan pada model PCB yang akan diidentifikasi. Gambar 3 menunjukkan pola PCB masukan yang siap diidentifikasi. Terlihat secara sekilas antara dua pola gambar tersebut tidak nampak perbedaan. Dengan demikian apabila inspeksi kecacatan dilakukan secara manual maka tidak akan mudah terdeteksi.
Setelah dua buah citra tersebut diproses dengan menggunakan aplikasi templete matching, maka terlihat hasil identifikasinya berupa lokasi dimana terdapat ketidak cocokan pola dan diasumsikan bahwa pada lokasi tersebut terdapat kecacatan PCB.Dalam hal ini titik-titik yang dianggap cacat karena tidak sesuai dengan citra pada master akan ditandai dengan blok korelasi berwarna merah dimana ukuran blok korelasi tersebut telah ditentukan sebelumnya oleh user. Gambar 4 menunjukkan output hasil template matching pada PCB input. Pada Gambar 4 tersebut terlihat adanya blok korelasi pada titik yang dianggap cacat karena memiliki kesalahan berupa putusnya jalur sirkuit PCB.
