TEMPLATE MATCHING

Pengertian

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.
Teori Template matching memiliki keunggulan dan kelemahan, yaitu :
Keunggulan :
(1) Jelas bahwa untuk mengenal bentuk, huruf atau bentuk-bentuk visual lainnya diperlukan kontak dengan bentuk-bentuk internal.
(2) 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.

Motion dan Oklusi

    Dalam kasus di mana template tidak dapat memberikan pencocokan langsung, mungkin lebih cocok untuk menerapkan penggunaan eigenspaces – template objek yang lebih detail yang sesuai dengan sejumlah kondisi yang berbeda, seperti berbagai perspektif, iluminasi, warna kontras, atau objek yang cocok diterima "pose". Misalnya, jika pengguna mencari seraut wajah, eigenspaces dapat terdiri dari gambar (template) wajah dalam posisi yang berbeda ke kamera, dalam kondisi pencahayaan yang berbeda, atau dengan ekspresi yang berbeda.
Hal ini juga memungkinkan gambar yang cocok untuk menjadi dikaburkan, atau oklusi oleh obyek, dalam kasus ini, memungkinkan untuk menyediakan banyak template untuk menutupi kemungkinan setiap oklusi. Dalam kasus di mana objek lunak atau poseable, motion juga menjadi masalah, dan masalah yang melibatkan motion dan oklusi menjadi ambigu. Dalam kasus ini, salah satu solusi yang mungkin adalah membagi template gambar ke dalam beberapa sub-foto dan melakukan pencocokan pada setiap subdivisi.

Pencocokan berbasis Template dan konvolusi

    Sebuah metode dasar template matching menggunakan konvolusi bayangan (template), disesuaikan dengan fitur tertentu dari template matching, yang ingin kita deteksi. Teknik ini dapat dengan mudah dilakukan pada gambar abu-abu atau tepi gambar. Hasil konvolusi akan di tempat tertinggi di mana struktur gambar sesuai dengan struktur bayangan, di mana nilai-nilai gambar besar dapat dikalikan dengan nilai-nilai bayangan besar.
Metode ini biasanya diimplementasi dengan terlebih dahulu memilih sebuah bagian dari pencarian gambar untuk digunakan sebagai template: Kita akan memanggil pencarian gambar S (x, y), dimana (x, y) mewakili koordinat setiap pixel dalam pencarian gambar. Kita akan memanggil template T (x t, y t,), dimana (x t, t y) merupakan koordinat dari setiap pixel dalam template. Kemudian kita hanya memindahkan pusat (atau asal) dari template T (x t, x t,) atas setiap titik (x, y) dalam pencarian gambar dan menghitung jumlah produk antara koefisien dalam S (x, y) dan T (x t, y t,) atas seluruh wilayah dari template. Karena semua kemungkinan posisi dari template yang berkenaan dengan pencarian gambar dianggap posisi terbaik. Metode ini kadang-kadang disebut sebagai 'Linear Spasial Filtering' dan template disebut masker penyaring.

Mempercepat Proses

Di masa lalu, tipe spasial filtering biasanya hanya digunakan dalam solusi hardware khusus karena kompleksitas komputasi operasi, namun kita dapat mengurangi kompleksitas ini dengan penyaringan dalam domain frekuensi dari gambar itu, disebut sebagai ' frekuensi domain filtering', hal ini dilakukan melalui penggunaan teorema konvolusi.
Cara lain untuk mempercepat proses pencocokan adalah melalui penggunaan dari suatu gambar piramida. Ini adalah serangkaian gambar, pada skala yang berbeda, yang terbentuk dengan berulang kali menyaring dan subsampling gambar asli agar menghasilkan gambar resolusi berkurang berurutan. Gambar resolusi lebih rendah dapat dicari untuk template (dengan mengurangi resolusi yang sama), untuk menghasilkan posisi semula yang memungkinkan untuk mencari pada skala yang lebih besar. Foto yang lebih besar kemudian dapat dicari dalam jendela kecil di sekitar posisi mulai menemukan lokasi template terbaik. Metode lain yang dapat menangani masalah seperti ini antara lain terjemahan, skala dan rotasi gambar.

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;
    }
}

Salah satu cara untuk melakukan template matching pada gambar warna adalah dengan menguraikan piksel ke dalam komponen warna mereka dan mengukur kualitas pertandingan antara warna template dan pencarian gambar dengan menggunakan jumlah SAD dihitung secara terpisah untuk setiap warna.

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.


Gambar 2 Pola Grayscale PCB Master

Gambar 3 Pola PCB Yang siap diidentifikasi

Gambar 4 Hasil Identifikasi Kecacatan Pada PCB

Dalam penelitian ini PCB master dan PCB input diasumsikan telah tersedia dalam bentuk file bitmap. Proses penting untuk mendapatkan kedua jenis file tersebut adalah tahap pemindaian / scanning. Bila proses ini tidak dilakukan dengan teliti akan berakibat pada proses deteksi kecacatan yang tidak akurat.