Algoritma Template Matching

Algoritma Template Matching adalah salah satu algoritma yang dapat digunakan untuk melakukan pengolahan citra. Contoh yang dibahas kali ini adalah mengenai klasifikasi untuk menemukan bagian gambar dalam gambar utama.

Diketahui data awal adalah sebagai berikut. Dalam kasus ini akan digunakan gambar berwarna bertipe jpg dengan ukuran 128 x 128 pixel

Dan gambar part atau bagian yang digunakan adalah

Langkah-langkah penggunaan algoritma ini adalah

1. Lakukan penyimpanan semua data warna dalam pixel yang terdapat dalam gambar tersebut
warna dalam sebuah pixel dibedakan menjadi 3 bagian, yaitu komponen merah, hijau, dan biru

For i = 0 To gmbUtama.Width - 1
	For j = 0 To gmbUtama.Height - 1
		inputPixel(i)(j)(0) = gmbUtama.GetPixel(i, j).R
		inputPixel(i)(j)(1) = gmbUtama.GetPixel(i, j).G
		inputPixel(i)(j)(2) = gmbUtama.GetPixel(i, j).B
	Next j
Next i

For i = 0 To gmbPart.Width - 1
	For j = 0 To gmbPart.Height - 1
		inputPartPixel(i)(j)(0) = gmbPart.GetPixel(i, j).R
		inputPartPixel(i)(j)(1) = gmbPart.GetPixel(i, j).G
		inputPartPixel(i)(j)(2) = gmbPart.GetPixel(i, j).B
	Next j
Next i

2. Hitung normalisasi dari gambar part, yaitu nilai gambar part setelah dikurangi dengan nilai pixel rata-rata gambar part tersebut
Perhitungan akan dilakukan pada masing-masing komponen warna, yaitu komponen merah, hijau, dan biru
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

hitungNormalisasi(normalisasiPart, gmbPart, 0, 0)

* Gunakan fungsi ini untuk menghitung normalisasi antara nilai input dengan parameter gambar
Pertama, jumlahkan dulu semua nilai pixel pada masing-masing komponen warna
kemudian bagi dengan jumlah pixel untuk mendapatkan nilai rata-rata pixel
Setelah itu, kurangi masing-masing nilai input pixel dengan nilai rata-rata pixel
dan pastikan angkanya tidak minus

Public Sub hitungNormalisasi(ByRef input()()() As Byte, ByVal gmb As Bitmap, ByVal startX As Integer, ByVal startY As Integer)
	Dim lebarGambar As Integer = input.Length
	Dim panjangGambar As Integer = input(0).Length

	Dim rata2NilaiPixelR As Integer = 0
	Dim rata2NilaiPixelG As Integer = 0
	Dim rata2NilaiPixelB As Integer = 0

	For i = startX To startX + lebarGambar - 1
		For j = startY To startY + panjangGambar - 1
			rata2NilaiPixelR += gmb.GetPixel(i, j).R
			rata2NilaiPixelG += gmb.GetPixel(i, j).G
			rata2NilaiPixelB += gmb.GetPixel(i, j).B
		Next j
	Next i

	rata2NilaiPixelR /= (lebarGambar * panjangGambar)
	rata2NilaiPixelG /= (lebarGambar * panjangGambar)
	rata2NilaiPixelB /= (lebarGambar * panjangGambar)

	For i = startX To startX + lebarGambar - 1
		For j = startY To startY + panjangGambar - 1
			If gmb.GetPixel(i, j).R - rata2NilaiPixelR >= 0 Then
				input(i - startX)(j - startY)(0) = gmb.GetPixel(i, j).R - rata2NilaiPixelR
			Else
				input(i - startX)(j - startY)(0) = 0
			End If

			If gmb.GetPixel(i, j).G - rata2NilaiPixelG >= 0 Then
				input(i - startX)(j - startY)(1) = gmb.GetPixel(i, j).G - rata2NilaiPixelG
			Else
				input(i - startX)(j - startY)(1) = 0
			End If

			If gmb.GetPixel(i, j).B - rata2NilaiPixelB >= 0 Then
				input(i - startX)(j - startY)(2) = gmb.GetPixel(i, j).B - rata2NilaiPixelB
			Else
				input(i - startX)(j - startY)(2) = 0
			End If
		Next
	Next
End Sub

3. Lakukan perhitungan pada masing-masing blok pixel pada gambar utama sebesar ukuran gambar part (poin 3a – 3d)

For i As Integer = 0 To gmbUtama.Width - gmbPart.Width - 1
	For j As Integer = 0 To gmbUtama.Height - gmbPart.Height - 1
	. . .

3a. Dapatkan blok data pixel dari gambar utama yang akan dihitung
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

getBlokData(blokGmbUtama, gmbUtama, i, j)

* Gunakan fungsi ini untuk mendapatkan blok pixel dari gambar input dimulai dari indeks (startX, startY)

Public Sub getBlokData(ByRef input()()() As Byte, ByVal gmbInput As Bitmap, ByVal startX As Integer, ByVal startY As Integer)
	Dim lebarGambar As Integer = input.Length
	Dim panjangGambar As Integer = input(0).Length

	For i = startX To startX + lebarGambar - 1
		For j = startY To startY + panjangGambar - 1
			input(i - startX)(j - startY)(0) = gmbInput.GetPixel(i, j).R
			input(i - startX)(j - startY)(1) = gmbInput.GetPixel(i, j).G
			input(i - startX)(j - startY)(2) = gmbInput.GetPixel(i, j).B
		Next
	Next
End Sub

3b. Hitung normalisasi blok pixel dari gambar utama dengan cara yang sama seperti sebelumnya

hitungNormalisasi(blokGmbUtama, gmbUtama, i, j)

3c. Hitung nilai korelasi antara blok pixel gambar utama dan gambar part yang telah dinormalisasi
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

Dim korelasi As Double = hitungKorelasi(blokGmbUtama, normalisasiPart)

* Gunakan fungsi ini untuk menghitung korelasi antara input dengan normalisasi part
Pertama, dapatkan nilai korelasi dengan menjumlahkan semua perkalian dari nilai input pixel dan nilai normalisasi part
Kemudian dapatkan total kuadrat input dengan menjumlahkan semua kuadrat dari nilai input
nilai korelasi adalah jumlah dari korelasi setelah dibagi dengan akar total kuadrat input

Public Function hitungKorelasi(ByVal input()()() As Byte, ByVal nilaiNormalisasi()()() As Byte) As Double
	Dim lebarGambar As Integer = input.Length
	Dim panjangGambar As Integer = input(0).Length

	Dim korelasi(2) As Double
	For i = 0 To lebarGambar - 1
		For j = 0 To panjangGambar - 1
			For k As Integer = 0 To 2
				korelasi(k) += CUInt(input(i)(j)(k)) * CUInt(nilaiNormalisasi(i)(j)(k))
			Next
		Next j
	Next i

	Dim totalInput2(2) As Double
	For i = 0 To lebarGambar - 1
		For j = 0 To panjangGambar - 1
			For k As Integer = 0 To 2
				totalInput2(k) += CUInt(input(i)(j)(k)) * CUInt(input(i)(j)(k))
			Next
		Next j
	Next i

	Dim totalKorelasi As Double = 0
	For k As Integer = 0 To 2
		totalKorelasi += korelasi(k) / Math.Sqrt(totalInput2(k))
	Next

	Return totalKorelasi
End Function

3d. Jika nilai korelasi lebih baik dari nilai korelasi terbaik
maka simpan posisi indeks perhitungan sebagai indeks terbaik

If korelasi > maksKorelasi Then
	maksKorelasi = korelasi
	xTerbaik = i
	yTerbaik = j
End If

4. Lakukan pemberian tanda dimana indeks terbaik ditemukan
Penandaan akan dilakukan mulai indeks terbaik tersebut sampai pada ukuran dari gambar part

For i = 0 To gmbUtama.Width - 1
	For j = 0 To gmbUtama.Height - 1
		pb.Value += 1

		outputPixel(i)(j)(0) = gmbUtama.GetPixel(i, j).R
		outputPixel(i)(j)(1) = gmbUtama.GetPixel(i, j).G
		outputPixel(i)(j)(2) = gmbUtama.GetPixel(i, j).B

		If ((i = xTerbaik Or i = xTerbaik + gmbPart.Width) AndAlso (j >= yTerbaik And j <= yTerbaik + gmbPart.Height)) Or _
			((j = yTerbaik Or j = yTerbaik + gmbPart.Height) AndAlso (i >= xTerbaik And i <= xTerbaik + gmbPart.Width)) Then
			outputPixel(i)(j)(0) = 255
			outputPixel(i)(j)(1) = 255
			outputPixel(i)(j)(2) = 255
		End If
	Next
Next

* Tampilkan pada layar

Dim bitMap As Bitmap = BuatBitmap(outputPixel, 2)
picHasil.Image = bitMap.Clone
bitMap.Dispose()

Hasil akhir adalah: (klik untuk perbesar gambar)

Contoh source code lengkap dalam bahasa VB (Visual Basic) dapat didownload disini:

Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.