Algoritma LWT (Lifting Wavelet Transform) dengan filter Spline 5/3

Algoritma LWT (Lifting Wavelet Transform) adalah salah satu algoritma yang dapat digunakan untuk melakukan kompresi sinyal ataupun gambar. Contoh yang dibahas kali ini adalah mengenai pengolahan file gambar.
Sama seperti algoritma transformasi wavelet sebelumnya, algoritma ini akan melakukan konversi data dari bentuk spasial menjadi bentuk frekuensi, kemudian melakukan pengolahan data frekuensi, dan dikonversi menjadi bentuk spasial menggunakan inversi metode yang bersangkutan.
Dalam kasus ini filter wavelet yang digunakan adalah filter Spline 5/3. Filter ini merupakan salah satu alternatif yang dapat digunakan dalam proses Lifting.

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

Langkah-langkah penggunaan algoritma ini adalah

1. Lakukan konversi ke dalam bentuk grayscale

if size(img,3) == 3
    warning('Data gambar ini akan dikonversi menjadi bentuk grayscale!')
    img = rgb2gray(img);
end

2. Lakukan proses perhitungan dengan menggunakan metode LWT (Lifting Wavelet Transform)
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 2a – 2d)

y=LWT(img, 2');

Memasuki perhitungan pada fungsi LWT

2a. Tentukan struktur variabel L yang digunakan dalam perhitungan
Filter yang digunakan adalah filter Spline 5/3 dengan mode kompresi Lossless
Nilai yang digunakan disini adalah nilai yang direkomendasikan dalam jurnal

lamdaz = struct('coeff',  {[-.5, -.5], [.25 .25]}, ...
               'zorder', {[ 0,   1 ], [ 0, -1 ]});
L = struct('lamdaz', lamdaz, 'K', [1, 1/2]);
mode='lossless';

2b. Beri nilai awal output (y) dengan data awal (x)

y = x;

2c. Jika jumlah level lebih dari 0, maka lakukan proses dekomposisi (poin 2c1)

if jumlahLevel > 0
. . .

2c1. Lakukan proses dekomposisi sebanyak jumlah level (poin 2c1a – 2c1e)

for i = 1:jumlahLevel
. . .

2c1a. Lakukan proses lifting pada data gambar awal
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan poin nomor 3 setelah pembahasan fungsi ini selesai

[temp0, temp1] = LWTPerLevel(x, L, 'd', mode);

2c1b. Hasil perhitungan sebelumnya akan menghasilkan urutan data genap dan ganjil
Lakukan proses lifting sekali lagi pada urutan data tersebut

[temp0, temp1] = LWTPerLevel([temp0; temp1]', L, 'd', mode);
temp = [temp0', temp1'];

2c1c. Update koefisien matriks y sesuai hasil lifting sebelumnya

y(1:ukuranX(1), 1:ukuranX(2)) = temp;

2c1d. Update data gambar yang baru menggunakan 1/4 blok data kiri atas dari hasil lifting sebelumnya
Data gambar ini nantinya digunakan dalam perhitungan level berikutnya

x = temp(1:ceil(ukuranX(1)/2), 1:ceil(ukuranX(2)/2));

2c1e. Jika data gambar sudah tidak dapat didekomposisi lagi, maka tampilkan pesan peringatan

if size(x,1)<=1 && size(x,2)<=1 && i~=jumlahLevel
	warning('WAVELIFT:InArgDegrade', ['Hanya melakukan dekomposisi sampai ' ...
		num2str(i) 'level saja daripada ' num2str(nlevel) ...
		', \nkarena perkiraan koefisien pada level ' num2str(i) ...
		'hanya memiliki baris / kolom sebanyak 1.']);
	break
end

2d. Jika jumlah level kurang dari 0, maka lakukan proses rekonstruksi / inversi (poin 2d1 - 2d2)

2d1. Hitung jumlah level rekonstruksi yaitu nilai positif dari parameter jumlah level
Jika jumlah level rekonstruksi lebih dari jumlah level dekomposisi, maka tampilkan pesan peringatan

jumlahLevelR = -jumlahLevel;

ukuranX = size(x);
while ukuranX(1)/2^jumlahLevelR<=1/2 && ukuranX(2)/2^jumlahLevelR<=1/2,  
	jumlahLevelR = jumlahLevelR-1;  
end

if jumlahLevelR ~= -jumlahLevel 
	warning('WAVELIFT:InArgDegrade', ['Hanya melakukan rekonstruksi sampai ' ...
		num2str(jumlahLevelR) 'level saja daripada ' num2str(-jumlahLevel) ...
		', \nkarena perkiraan koefisien pada level ' num2str(jumlahLevelR) ...
		'hanya memiliki baris / kolom sebanyak 1.']);
end

2d2. Lakukan proses rekonstruksi sebanyak jumlah level (poin 2d2a - 2d2d)

for i = 1 : jumlahLevelR
. . .

2d2a. Tentukan target blok yang dihitung pada level ini

sTarget = ceil(ukuranX/2^(jumlahLevelR-i));
target = y(1:sTarget(1), 1:sTarget(2));

2d2b. Lakukan proses inversi lifting pada blok tersebut

sLL = ceil(sTarget/2);
temp0 = target(:, 1: sLL(2));
temp1 = target(:, sLL(2)+1:end);
temp = LWTPerLevel(temp0', temp1', L, 'r', mode);
temp = temp';

2d2c. Setelah menemukan setengah data pertama yang berisi urutan genap
dan setengah data berikutnya berisi urutan ganjil
Maka lakukan proses inversi lifting pada urutan data tersebut

temp0 = temp(1: sLL(1), :);
temp1 = temp(sLL(1)+1 :end, :);
temp = LWTPerLevel(temp0, temp1, L, 'r', mode);

2d2d. Update nilai y pada blok terpilih sesuai dengan hasil inversi lifting tersebut

y(1:sTarget(1), 1:sTarget(2)) = temp;

proses pada fungsi LWTPerLevel adalah sebagai berikut

3a. Beri nilai awal output (y) dengan data awal (x),
y0 dengan urutan data ganjil dari x
dan y1 dengan urutan data genap dari x

if nargin == 4
    y0 = x(1:2:end, :);
    y1 = x(2:2:end, :);
    y = x;
else
    y0 = x;
    y1 = optx;
    y = zeros(size([y0; y1]));
    y(1:2:end, :) = y0;
    y(2:2:end, :) = y1;
end

3b. Jika data awal masih berjumlah lebih dari 1, maka lakukan perhitungan berikut (poin 3b1 - 3b7)

if size(y, 1) > 1
. . .

3b1. Simpan ukuran awal y0 dan y1,
karena y0 dan y1 akan mengalami perubahan pada saat proses ekstensi dan lifting

ukuranY0 = size(y0, 1);
ukuranY1 = size(y1, 1);

3b2. Tentukan nilai tanda untuk digunakan dalam proses lifting
Nilai awal tanda adalah tanda positif

eval('plusminus = 1;');

* Memasuki proses ekstensi data (poin 3b3)
Kesulitan proses ini terdapat pada penanganan batas data
Demi kemudahan dalam lifting variabel L, maka akan diterapkan cara yang lebih umum tapi lebih kompleks

3b3a. Hitung nilai shift / pergeseran yang diperlukan oleh x0 dan x1

temp = [L.lamdaz.zorder];
rshift = - sum( temp(find(temp<0)) ) * 2;
lshift = sum(temp) * 2 + rshift;
if ukuranY1 ~= ukuranY0
	rshift = rshift + 1;
end

3b3b. Lakukan proses ekstensi, yaitu pergeseran sesuai variabel pergeseran sebelumnya

for i = 1: max(lshift, rshift)
	y = [y(2*i, :); y; y(ukuranY(1)-1, :)];
end
if rshift > lshift
	y = y(rshift-lshift+1:end, :);
elseif rshift < lshift
	y = y(1:end+rshift-lshift, :);
end

3b3c. Catat urutan genap dan ganjil setelah mengalami proses pergeseran

y0 = y(1:2:end, :);
y1 = y(2:2:end, :);
clear y;    

* Jika proses yang dilakukan adalah proses rekonstruksi,
maka harus dilakukan proses tambahan berikut sebelum memasuki proses lifting
Lakukan modifikasi input inversi lifting dengan menambahkan proses inversi (poin 3b4)

3b4. Lakukan perhitungan berikut apabila proses yang dijalankan adalah proses rekonstruksi (poin 3b4a - 3b4d)

if strcmp(arah, 'r')
. . .

3b4a. Pindahkan nilai lifting gains ke urutan depan

y0 = y0 / L.K(1);  L.K(1) = 1;
y1 = y1 / L.K(2);  L.K(2) = 1;

3b4b. Jika panjang lamdaz berjumlah genap, maka x0 dan x1 harus ditukar posisinya
kemudian setelah proses lifting, hasil output y0 dan y1 harus ditukar juga

if rem(panjangLamdaz,2) == 0
	temp = y0;
	y0 = y1;
	y1 = temp;
end

3b4c. Lakukan pembalikan urutan posisi lamdaz

for i = 1: floor(panjangLamdaz/2)
	temp = L.lamdaz(i).coeff;
	L.lamdaz(i).coeff = L.lamdaz(panjangLamdaz-i+1).coeff;
	L.lamdaz(panjangLamdaz-i+1).coeff = temp;            
	temp = L.lamdaz(i).zorder;
	L.lamdaz(i).zorder =  L.lamdaz(panjangLamdaz-i+1).zorder;
	L.lamdaz(panjangLamdaz-i+1).zorder = temp;
end

3b4d. Beri nilai tanda dalam proses lifting dengan tanda negatif

eval('plusminus = -1;');

* Memasuki proses lifting (poin 3b5)

3b5. Lakukan perhitungan sebanyak panjang lamdaz yang ada (poin 3b5a - 3b5b)

for i = 1: panjangLamdaz
. . .

3b5a. Lakukan proses convolution menggunakan fungsi circshift
Fungsi circshift digunakan untuk menerapkan perhitungan yang sederhana
dan sisa kelebihan contoh data dapat dibuang

eval('yconv = zeros(size(y0));');

for j = 1: length(L.lamdaz(i).zorder)
	eval(['yconv = yconv +  circshift(y' num2str(rem(i-1,2)) ...
			', -L.lamdaz(i).zorder(j)) * L.lamdaz(i).coeff(j);']); 
end

3b5b. Untuk mode lossy, hitung nilai output dengan rumus:
y_(rem(i,2)) = y_(rem(i,2))+ lamdaz(i) ** y_(rem(i,2))
Untuk mode lossless, hitung nilai output dengan rumus:
y_(rem(i,2)) = y_(rem(i,2)) + floor(0.5+lamdaz(i)**y_(rem(i,2)))
Jangan lupa menambahkan tanda negatif untuk proses rekonstruksi

if strcmp(mode, 'lossy')
	eval(['y' num2str(rem(i,2)) ' = y' num2str(rem(i,2)) ...
		' + yconv * plusminus;']);
else % 'lossless'
	eval(['y' num2str(rem(i,2)) '= y' num2str(rem(i,2)) ...
		' + floor(yconv + .5) * plusminus;']);
end

3b6. Jika proses yang dilakukan adalah proses rekonstruksi,
sesuai penjelasan sebelumnya, maka y0 dan y1 harus ditukar,
karena sebelumnya x0 dan x1 sudah ditukar

if strcmp(arah, 'r') && rem(panjangLamdaz,2) == 0
	temp = y0;
	y0 = y1;
	y1 = temp;
end

* Memasuki proses pembuangan ekstensi data
Proses ini adalah kebalikan dari proses ekstensi yang sudah dilakukan sebelumnya (poin 3b7)

3b7a. Hapus bagian ekstensi dan lakukan perkalian dengan nilai gain

y0 = y0(1+lshift/2 : end-floor(rshift/2), :) * L.K(1);
y1 = y1(1+lshift/2 : end-floor(rshift/2), :) * L.K(2);

3b7b. Hapus kolom yang sebelumnya ditambahkan pada input

if ukuranY1 < ukuranY0
	y1 = y1(1:end-1, :);
elseif ukuranY1 > ukuranY0
	y0 = y0(1:end-1, :);
end

3c. Masukkan nilai y0 dan y1 sebagai nilai jawaban dari fungsi ini

if nargout == 1
    y = zeros(ukuranY);
    y(1:2:end, :) = y0;
    if ukuranY(1) > 1
        y(2:2:end, :) = y1;
    end
elseif nargout == 2
    y = y0;
    opty = y1;
end

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.