Algoritma MSWPD (Multiscale Wavelet Packet Decomposition) 2

Pengenalan Pola adalah cabang kecerdasan yang menitik-beratkan pada metode pengklasifikasian objek ke dalam klas – klas tertentu untuk menyelesaikan masalah tertentu. Contoh yang dibahas kali ini adalah mengenai penentuan pola wajah baru berdasarkan pola wajah yang sudah ada sebelumnya dengan menggunakan metode MSWPD (Multiscale Wavelet Transform Decomposition).
Algoritma ini merupakan variasi dari Algoritma MSWTD (Multiscale Wavelet Transform Decomposition). Jika pada algoritma sebelumnya, proses dekomposisi hanya dilakukan pada penaksiran koefisien dekomposisi saja, maka pada algoritma ini, selain melakukan proses tersebut, proses dekomposisi juga dilakukan pada setiap detail koefisien dekomposisi, yang nantinya akan menghasilkan pohon sample. Selain itu teknik dasarnya semua sama.

Diasumsikan ada 10 wajah manusia yang sudah diketahui sebelumnya, dengan data sebagai berikut:

Selanjutnya ada pola wajah baru yang ingin diketahui hasilnya
Maka tentukan pola wajah baru ini cocok dengan pola wajah yang mana
Diasumsikan pola wajah yang baru adalah sebagai berikut:

Langkah-langkah penggunaan algoritma ini adalah

* Lakukan inisialisasi variabel yang digunakan dalam perhitungan (poin 1)

1a. Tentukan ukuran dari masing-masing sample gambar yang digunakan
Nantinya setiap gambar akan mengalami segmentasi dimulai dari pointer indeks yang sedang terpilih
Diasumsikan dalam kasus ini, ukuran per sample adalah 92 x 2
Karena contoh kasus ini menggunakan contoh gambar dengan ukuran 92 x 112,
maka setiap sample yang digunakan adalah 2 baris data gambar

ukuranPerSample = 92*2;

1b. Tentukan konstanta penambah indeks pointer dalam setiap pengambilan sample
Diasumsikan dalam kasus ini, penambah indeks pointer adalah 92
Karena contoh kasus ini menggunakan contoh gambar dengan ukuran 92 x 112,
maka pergeseran pointer akan berpindah tepat 1 baris berikutnya

penambahIndeksPointer = 92;

1c. Tentukan variabel J, yaitu jumlah level dekomposisi yang digunakan
Diasumsikan dalam kasus ini, jumlah level dekomposisi adalah 5

J = 5;

* Lakukan pembacaan gambar contoh data yang tersedia (poin 2)

2a. Tentukan path folder dari gambar contoh data dan gambar data baru

pathContohData = 'ContohData';
pathDataBaru = 'DataBaru';

2b. Cari semua gambar contoh wajah dan data baru yang tersedia pada masing-masing folder
Kemudian hitung jumlah gambar untuk masing-masing contoh data dan data baru yang tersedia

bmpContohData=dir(sprintf('%s/*.bmp',pathContohData));    
bmpDataBaru=dir(sprintf('%s/*.bmp',pathDataBaru));
jumlahContohData=size(bmpContohData,1);
jumlahDataBaru=size(bmpDataBaru,1);

2c. Tentukan tinggi (H) dan lebar (W) dari masing-masing gambar
Kemudian buat matriks kosong berukuran H*W sebanyak jumlah gambar contoh data

str=strcat(pathContohData,'\',bmpContohData(1).name);    
im=imread(str);
H=size(im,1);
W=size(im,2);
daftarGambar=zeros(H,W,jumlahContohData);

* Lakukan proses pengambilan fitur gambar contoh wajah dengan metode MSWPD (Multiscale Wavelet Packet Decomposition) (poin 3)

3. Lakukan perhitungan pada masing-masing gambar contoh wajah (poin 3a – 3c)

for i=1:jumlahContohData
. . .

3a. Simpan data gambar wajah yang ada

str=strcat(pathContohData,'\',bmpContohData(i).name);    
daftarGambar(:,:,i)=imread(str);

3b. Lakukan proses perhitungan dengan metode MSWPD (Multiscale Wavelet Packet Decomposition)
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 3b1 – 3b10)

matriksFeatureContohData(:,:,i) = MSWPD(daftarGambar(:,:,i));

Memasuki perhitungan pada fungsi MSWPD

3b1. Hitung jumlah data,
Kemudian hitung jumlah sample yang akan didapatkan pada perhitungan berikutnya
dan lakukan inisialisasi daftar sample yang digunakan

jumlahData = size(data,1);
jumlahSample = floor((jumlahData - ukuranPerSample)/penambahIndeksPointer)+1;
daftarSample = zeros(ukuranPerSample,jumlahSample);

3b2. Hitung jumlah output yang diperoleh dari masing-masing channel / dimensi level
Nantinya dalam setiap level, masing-masing node akan terbelah menjadi 2
sehingga nilai output dari masing-masing channel adalah 2^n-1
Kemudian lakukan inisialisasi nilai output yang dihasilkan

jumlahOutputPerChannel = (2^(J+1)-1);
output = zeros(jumlahSample,jumlahOutputPerChannel*size(data,2));

* Lakukan perhitungan pada masing-masing jumlah kolom data yang ada (poin 3b3 – 3b9)

for k = 1:size(data,2)
. . .

3b3. Lakukan proses segmentasi data sebanyak jumlah sample
jika terdapat 6 buah data seperti berikut:
[ 1 ]
[ 2 ]
[ 3 ]
[ 4 ]
[ 5 ]
[ 6 ]
dengan ukuran per sample = 3 dan penambah indeks pointer = 2
maka jumlah sample adalah floor((6 – 3) / 2) + 1 = 2
dan sample yang didapatkan adalah [ 1 2 3 ] dan [ 3 4 5 ]

pointerIndeksAwal = 1;
pointerIndeksAkhir = ukuranPerSample;    
for i = 1:jumlahSample
	daftarSample(1:ukuranPerSample,i) = data(pointerIndeksAwal:pointerIndeksAkhir,k);
	
	pointerIndeksAwal = pointerIndeksAwal + penambahIndeksPointer;
	pointerIndeksAkhir = pointerIndeksAkhir + penambahIndeksPointer;
end

3b4. Tentukan variabel J, yaitu jumlah level dekomposisi yang digunakan
Ada beberapa cara untuk menghitung nilai ini
pertama, dapat didefinisikan secara langsung
J=10;
kedua, menggunakan nilai maksimum level dekomposisi wavelet, dengan rumus:
J=wmaxlev(ukuranPerSample,’Sym5′);
ketiga, menggunakan logaritma frekuensi sample, dengan rumus:
J=floor((log(frekuensiSample/2)/log(2))-1);
Dalam kasus ini akan digunakan cara pertama untuk menentukan nilai J, yaitu sesuai dengan parameter jumlah level dekomposisi

3b5. Lakukan proses perhitungan utama fungsi ini menggunakan metode MSWPD (Multiscale Wavelet Packet Decomposition)
Jika terdapat jumlah level dekomposisi sebanyak 4 level,
maka fungsi ini akan menghasilkan pohon 4 level dengan jumlah node adalah 1+2+4+8 = 15 node
dan masing-masing node akan memiliki jumlah baris sample yang akan semakin kecil seiring dengan level node tersebut
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 3b5a – 3b5c)

Dec = HitungMSWPD('col',daftarSample,'db4',J);

Memasuki perhitungan pada fungsi HitungMSWPD

3b5a. Hitung jumlah sample yang digunakan
Jumlah level dekomposisi tidak boleh lebih dari jumlah sample
agar memastikan akan terdapat node dalam masing-masing level

jumlahSample = size(daftarSample,1);
if J > floor(log2(jumlahSample))
    error('Jumlah level dekomposisi terlalu banyak.');
end

3b5b. Masukkan sample ini sebagai node pertama pada level dekomposisi pertama

Dec{1,1} = daftarSample;

3b5c. Lakukan perhitungan pada level berikutnya setelah level pertama (poin 3b5c1)

for j = 1:J
. . .

3b5c1. Lakukan perhitungan pada masing-masing pasangan node pada level dekomposisi terpilih (poin 3b5c1a – 3b5c1b)

for k = 1:2^(j-1)
. . .

3b5c1a. Lakukan proses perhitungan Multisignal 1-D Wavelet Decomposition pada node terpilih

nodeTerpilih = Dec{j,k};
dec = mdwtdec(DIRDEC,nodeTerpilih,1,filterWavelet);

3b5c1b. Masukkan hasil perhitungan ke dalam pasangan node yang levelnya berada dibawah level node terpilih

Dec{j+1,idxNode} = dec.ca; idxNode = idxNode+1;
Dec{j+1,idxNode} = dec.cd{1}; idxNode = idxNode+1;

3b6. Lakukan inisialisasi variabel output sementara,
yaitu sebanyak jumlah node x jumlah kolom sample node

tesNode = Dec{1,1};
jumlahSampleNodePertama = size(tesNode,2); clear nodePertama
tmpOutput = zeros(jumlahSampleNodePertama,2^(J+1)-1);

3b7. Lakukan perulangan pada masing-masing node
Lakukan proses perhitungan nilai output dengan cara logaritma akar rata-rata kuadrat dari masing-masing elemen node

idxTmpOutput = 1;
for i=1:size(Dec,1)
	for j=1:size(Dec,2)
		if ~isempty(Dec{i,j})
			tmpOutput(1:jumlahSampleNodePertama,idxTmpOutput) = log(sqrt(mean(Dec{i,j}.*Dec{i,j})'));
			idxTmpOutput = idxTmpOutput +1;
		end
	end
end

3b8. Hilangkan semua nilai output yang mengandung nilai 0

idxOutputBukanNol = sum(tmpOutput,1);
idxOutputBukanNol = (idxOutputBukanNol~=0);
tmpOutput = tmpOutput(:,idxOutputBukanNol);

3b9. Catat hasil akhir output sesuai dengan jumlah output yang dihasilkan dalam masing-masing channel

jumlahOutputPerChannel = size(tmpOutput,2);    
output(:,((k-1)*(jumlahOutputPerChannel)+1):k*jumlahOutputPerChannel) = tmpOutput;

3b10. Setelah mendapatkan semua jawaban kolom data,
Lakukan perhitungan sekali lagi untuk menghilangkan semua nilai output yang mengandung nilai 0

jumlahOutputPerChannel = size(tmpOutput,2);    
idxOutputBukanNol = sum(output);
idxOutputBukanNol = (idxOutputBukanNol~=0);
output = output(:,idxOutputBukanNol);

3c. Tampilkan gambar contoh wajah tersebut pada layar

subplot(5,jumlahContohData,i)
imshow(str)
if i==1
	title('Contoh gambar wajah: ','Position',[105,0])
end

* Lakukan proses pengambilan fitur gambar wajah baru dengan metode MSWPD (Multiscale Wavelet Packet Decomposition) (poin 4)

4. Lakukan perhitungan pada masing-masing data baru (poin 4a – 4e)

for i=1:jumlahDataBaru
. . .

4a. Simpan data gambar wajah baru yang ada

str=strcat(pathDataBaru,'\',bmpDataBaru(i).name);   
im=imread(str);
daftarGambarBaru(:,i)=reshape(im',[H*W, 1]);

4b. Lakukan proses perhitungan dengan metode MSWPD (Multiscale Wavelet Packet Decomposition)
Penjelasan tentang fungsi ini sudah dijelaskan pada perhitungan sebelumnya

matriksFeatureDataBaru(:,:) = MSWPD(daftarGambarBaru(:,i),ukuranPerSample,penambahIndeksPointer,frekuensiSample);

4c. Hitung jarak Euclidean antara vektor feature data baru dengan vektor feature dari semua contoh data

jarakEuclidean = [];
for j=1:jumlahContohData
	tmp = (norm(matriksFeatureDataBaru(:,:) - matriksFeatureContohData(:,:,j)));
	jarakEuclidean = [jarakEuclidean tmp];
end

4d. Ambil jarak paling minimal sebagai jawaban gambar contoh data yang paling sesuai dengan gambar data baru

[~, idxMinimal] = min(jarakEuclidean);

4e. Tampilkan hasil akhir pada layar

subplot(5,jumlahContohData,sp(i))
imshow(str)
title(strcat('Data ',int2str(i)),'Position',[25,0])

subplot(5,jumlahContohData,sp(i)+1)
imshow(uint8(daftarGambar(:,:,idxMinimal)))
title('Dikenali sebagai','Position',[75,0])

Hasil akhir adalah: (klik untuk perbesar gambar)

Contoh modul / source code menggunakan Matlab 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.