TKE 2403
SISTEM PENGOLAHAN ISYARAT Kuliah 9 – Analisis Wavelet : Alihragam Wavelet Diskret
Indah Susilawati, S.T., M.Eng.
Program Studi Teknik Elektro Fakultas Teknik dan Ilmu Komputer Universitas Mercu Buana Yogyakarta 2009
1
KULIAH 9 SISTEM PENGOLAHAN ISYARAT
Analisis Wavelet : Alihragam Wavelet Diskret Alihragam wavelet kontinyu (CWT) bersifat sangat redundan; terlalu banyak koefisien yang dibangkitkan melebihi yang dibutuhkan untuk secara unik menspesifikasikan suatu sinyal tertentu. Redundansi semacam ini tidak terlalu menjadi masalah dalam aplikasi yang telah dibahas pada pertemuan yang lalu (contoh 1 dan 2), namun akan menjadi sangat mahal jika digunakan untuk merekontruksi kembali sinyal aslinya. Untuk merekontruksi sinyal asli maka semua koefisien yang ada harus digunakan dan dengan demikian akan membutuhkan komputasi yang sangat besar (tak berhingga karena dalam bentuk kontinyu akan ada tak berhingga koefisien). Alihragam wavelet diskret (DWT: Discrete Wavelet Transform) membatasi variasi dalam pergeseran dan skala, biasanya dalam perpangkatan 2, sehingga redundansi menjadi berkurang. Saat skala diubah dalam perpangkatan 2, alihragam wavelet diskret juga disebut dengan istilah Dyadic Wavelet Transform (DWT). DWT seringkali dinyatakan dalam bentuk alihragam sbb.
(13) Dalam hal ini k dihubungkan ke a dengan a = 2k dan b dihubungkan ke b = 2k l, dan d(k,
l
l dengan
) adalah hasil pencuplikan dari W(a,b) pada titik-titik diskret k
dan l . Dalam DWT dipergunakan konsep baru yang disebut fungsi skala (scaling function), yaitu sebuah fungsi yang memungkinkan dilakukannnya komputasi DWT. Untuk menerapkan DWT secara efisien, terlebih dahulu dihitung resolusi terbaiknya. Komputasi yang selanjutnya menggunakan resolusi yang lebih kasar.
2
Komputasi ini tidak dilakukan menggunakan sinyal asli namun menggunakan versi sinyal yang telah diperhalus (smoothed version). Sinyal yang telah diperhalus ini diperoleh dengan bantuan smoothing function. Definisi fungsi skala menggunakan persamaan berikut.
(14) Dengan c(n) adalah deretan skalar yang menentukan fungsi skala. Persamaan ini melibatkan dua skala waktu (t dan 2t) dan dapat menjadi persamaan yang sangat sulit untuk diselesaikan. Dalam DWT, wavelet dapat didefinisikan dari fungsi skala,
(15) Dengan d(n) adalah deretan skalar yang berhubungan dengan sinyal x(t) (persamaan (13)) dan yang menentukan wavelet diskret dalam bentuk fungsi skala.
Meskipun
DWT
dapat
diimplementasikan
dengan
menggunakan
persamaan-persamaan di atas, namun biasanya DWT diimplementasikan menggunakan teknik filter banks.
Filter Banks Untuk sebagian besar aplikasi pemrosesan sinyal dan citra, analisis berbasis DWT paling baik jika dinyatakan sebagai filter banks. Pengggunaan sekelompok filter untuk membagi sinyal menjadi berbagai komponen spektral disebut dengan istilah subband coding. Implementasi paling sederhana dari DWT adalah menggunakan dua filter dalam filter banks seperti diperlihatkan pada Gambar 6. Sinyal yang dianalisis dibagi menjadi menjadi dua komponen ylp(n) dan yhp(n) oleh filter digital H0(ω) dan H1(ω). Karakteristik spektral kedua filter harus dipilih dengan hati-hati yaitu H0(ω) mempunyai karakteristik spektral lowpass dan H1(ω)mempunyai karakteristik spektral highpass. Filter highpass sama dengan penerapan wavelet pada sinyal asli sedangkan filter lowpass sama dengan 3
penerapan fungsi skala atau fungsi smoothing. Jika filter-filter tersebut invertible maka dimungkinkan untuk menemukan suatu filter inversnya (yaitu filter yang mempunyai spektrum invers dari H0(ω) dan H1(ω)), sehingga akan dapat pula ditemukan kembali sinyal asli dari kedua sinyal subband ylp(n) atau yhp(n). Sinyal asli juga seringkali dapat ditemukan kembali meskipun kedua filter tidak invertible, namun dalam hal ini kedua sinyal subband harus digunakan.
Gambar 6. Filter banks sederhana terdiri atas 2 filter yang diaplikasikan pada sinyal yang sama. Filter mempunyai karakteristik spektral lowpass dan highpass. Keluaran filter terdiri atas subband lowpass ylp(n) dan subband highpass yhp(n). Proses recoveri sinyal (menemukan kembali sinyal asli) diperlihatkan pada Gambar 7. Pada gambar tersebut sepasang filter yang kedua yaitu G0(ω) dan G1(ω), bekerja pada sinyal subband highpass dan lowpass dan jumlahannya digunakan untuk merekontruksi kembali sinyal aslinya yaitu x’(t). Filter banks yang mendekomposisi sinyal asli biasanya disebut dengan filter analisis (analysis filters) dan filter banks yang merekontruksi sinyal disebut filter sistesis (syntheses filters).
Filter-filter
FIR
banyak
digunakan
karena
kestbilannya
dan
kemudahannya untuk diimplementasikan. Memfilter sinyal asli x(n) hanya untuk recoveri sinyal asli merupakan operasi yang kurang bermakna (biasanya memfilter sinyal asli merupakan proses awal saja sebelum dilakukan operasi yang lebih penting lagi). Dalam beberapa aplikasi analisis hanya sinyal-sinyal subband saja yang menjadi perhatian dan 4
rekontruksi sinyal tidak diperlukan. Namun dalam beberapa aplikasi wavelet dilakukan operasi pada sinyal-sinyal subband ylp(n) dan yhp(n) sebelum rekontruksi sinyal keluaran (lihat Gambar 7). Pada kasus yang demikian, keluaran tidak akan tepat sama dengan masukan. Jika keluaran tepat sama dengan masukan maka proses disebut tanpa rugi-rugi (lossless) dan jika tidak maka prosesnya disebut dengan rugi-rugi (lossy). Hal yang seperti ini misalnya terjadi pada aplikasi kompresi data.
Gambar 7. Aplikasi wavelet menggunakan filter banks yang terdiri atas dua filter. Sinyal masukan didekomposisi menjadi dua subband menggunakan filter analisis. Suatu proses diterapkan pada sinyal hasil filtering sebelum rekontruksi. Rekontruksi dilakukan oleh filter sintesis. Dengan menggunakan skema seperti yang ditunjukkan pada Gambar 7, maka dapat dipahami bahwa dibutuhkan proses yang dua kali lipat besarnya jika dibandingkan dengan proses langsung pada sinyal asli x(n). Semakin banyak filter yang digunakan dalam filter banks maka masalahnya juga semakin besar. Jelas bahwa terjadi redundansi informasi pada sinyal ylp(n) dan yhp(n), karena keduanya dibutuhkan untuk menyatakan x(n), namun jumlah titik-titiknya menjadi dua kali lipat. Jika filter analisis dapat dengan tepat dipilih maka dimungkinkan untuk mengurangi panjang ylp(n) dan yhp(n) menjadi setengahnya dan juga masih dimungkinkan untuk proses recoveri sinyal asli. Untuk mengurangi sampel sinyal menjadi setengahnya dan tetap mempertahankan periodanya, maka dapat dilakukan dengan cara menghilangkan titik-titik yang bernomor ganjil. Operasi ini
5
dikenal dengan istilah downsampling dan akan disimbolkan dengan ↓2. Sebagai contoh, sinyal y(n) yang telah dikenakan downsampling hanya akan terdiri atas sampel-sampel yang berindeks genap yaitu [y(2), y(4), y(6), ...] dari hasil filtering. Jika digunakan downsampling maka harus ada metode untuk recoveri sampel yang sebelumnya telah dihilangkan sehingga sinyal aslinya dapat diperoleh kembali. Operasi yang disebut upsampling (yang disimbolkan dengan ↑2) menyelesaikan masalah ini dengan cara mengganti titik-titik yang sebelumnya dihilangkan dengan nilai nol. Sinyal hasil recoveri tidak akan mempunyai nilai nol pada titik-titik tersebut karena filter sintesis G0(ω) dan G1(ω) akan mengisi titik-titk tersebut. Gambar 8 memperlihatkan aplikasi wavelet yang menggunakan tiga filter banks dan juga melibatkan operasi downsampling dan upsampling. Amplitude downsampling kadang-kadang diskala dengan √2 (dapat menyederhanakan perhitungan filter jika digunakan metode matriks).
Gambar 8. Aplikasi wavelet menggunakan tiga filter. Sebagaimana pada Gambar 7, beberapa proses dapat dilakukan pada sinyal ylp(n) dan yhp(n) sebelum proses rekontruksi.
6
Perancangan filter dalam filter bank wavelet menjadi cukup menantang karena filter harus memenuhi beberapa kriteria. Yang terpenting adalah bahwa sinyal asli harus dapat diperoleh kembali setelah melalui filter analisis dan filter sintesis.
Recoveri
yang
tepat
juga
diperumit
dengan
adanya
proses
downsampling. Perlu dicatat bahwa proses downsampling sama artinya dengan mencuplik sinyal asli dengan setengah frekuensi pencuplikan (fs/2). Untuk beberapa sinyal hal ini akan menyebabkan aliasing. Jika filter bank terdiri atas dua tipe filter (highpass dan lowpass) maka kriteria yang harus dipenuhi untuk mencegah aliasing adalah (16) Dengan H0(z) adalah fungsi transfer filter lowpass analisis, H1(z) adalah fungsi transfer filter highpass analisis, G0(z) adalah fungsi transfer filter lowpass sintesis, G1(z) adalah fungsi transfer filter highpass sintesis. Syarat lain yang harus dipenuhi agar memungkinkan recoveri sinyal asli adalah (17) Dengan N adalah jumlah koefisien filter (yaitu orde filter) sehingga z
–N
hanyalah
merupakan tunda dari filter. Dalam beberapa analisis diperlukan untuk memperoleh sinyal-sinyal subband yang ortogonal. Beberapa jenis filter dibangun sehingga dapat memenuhi sifat ini. Misalnya filter Daubechies yang merupakan filter wavelet dengan 4 atau lebih koefisien. Koefisien filter lowpass, h0(n), untuk filter Daubechies 4 koefisien diberikan berikut ini.
(18) Supaya keluaran filter highpass menjadi ortogonal terhadap keluaran filter lowpass, karakteristik frekuensi filter highpass dan lowpass harus mempunyai hubungan khusus sebagai berikut. (19)
7
Kriteria
pada
persamaan
(19)
dapat
diimplementasikan
dengan
cara
menerapkan algoritma alternating flip pada koefisien-koefisien h0(n) sebagai berikut. (20) Dengan N adalah jumlah koefisien dalam h0(n). Setelah filter analisis dipilih maka filter sintesis yang akan digunakan untuk rekontruksi dibatasi oleh ketentuan yang dinyatakan pada persamaan (14) dan (15). Persamaan (17) dapat dipenuhi dengan membuat G0(z) = H1(-z) dan G1(-z) = - H0(-z). Dengan demikian maka fungsi transfer filter analisis terhubung dengan fungsi transfer filter sintesis menurut persaman (21) (22) Implementasi
persamaan-persamaan
di
atas
dapat
dilakukan
dengan
menggunakan algoritma order flip sebagai berikut. (23) (24)
Hubungan antara Pernyataan Analitis dan Filter Banks Secara teori dapat dibangun wavelet dan fungsi skala dari koefisien filter dan juga sebaliknya. Kenyataanya adalah bahwa koefisien c(n) dan d(n) pada persamaan (14) dan (15) merupakan versi terskala dari koefisien filter, (25) Dengan substitusi c(n) dalam persamaan (14), persamaan fungsi skala (persamaan dilasi) menjadi
(26)
8
Untuk menemukan φ dapat digunakan representasi dalam domain frekuensi. Dengan mengambil alihragam Fourier pada kedua sisi pada persamaan (26) maka diperoleh,
(27) Catat bahwa skala waktu 2t menjadi ω/2 dalam domain frekuensi. Suku kedua pada persamaan (27) dapat dipecah menjadi H0(ω/4) Φ(ω/4) sehingga dimungkinkan untuk menulis kembali persamaan tersebut sebagai
(28)
(29) Jika N Æ ∞ maka perrsamaan (29) menjadi
(30) Hubungan antara φ(t) dan koefisien filter lowpass dapat diperoleh dengan mengambil invers alihragam Fourier dari persamaan (30). Setelah fungsi skala ditentukan, fungsi wavelet dapat diperoleh langsung dengan persamaan (16) dengan 2h1(n) disubstitusikan untuk d(n),
(31) Persamaan (30) menunjukkan kriteria lain untuk koefisien filter lowpass h0(n) yang belum disebutkan sebelumnya. Supaya hasilkali menjadi konveergen maka H0(ω/2j) harus mendekati 1 saat j Æ ∞. Hal ini menghendaki syarat bahwa H0(0) = 1; dan hal ini merupakan syarat yang mudah dipenuhi oleh sebuah filter lowpass.
9
Contoh 3 Buatlah filter bank untuk analisis yang terdiri atas L dekomposisi, yaitu sebuah filter lowpass dan L filter highpass. Dekomposisilah sebuah sinyal yang terdiri atas 4 sinusoida yang berderau dan bentuklah kembali sinyal aslinya menggunakan filter bank sintesis.
% % % % %
Contoh 3 : Contoh DWT Membentuk sinyal yang terdiri atas 4 sinusoid plus derau Mendekomposisi sinyal dalam 4 level, mem-plot tiap level dan merekontruksi kembali Menggunakan filter Daubechies 6 elemen
clear all; close all; clc; fs = 1000; % Frekuensi sampling N = 1024; % Jumlah titik dalam sinyal t = linspace(0,1,N); % Sumbu waktu t x = 1.2*sin(2*pi*.63*t)+ sin(2*pi*1.1*t)+1.2*sin(2*pi*2.7*t)+.75*sin(2*pi*5.6*t); x1 = x+.25*rand(size(t)); load db6 h0 = db6; an = analyze(x1,h0,4); y = synthezise(an,h0,4); figure plot(t,x,'k',t,x1-4,'m',t,y-8,'c');
----------------------------------------------------------------% Fungsi untuk menghitung filter analisis % an = analyze(x, h0, L) % x = sinyal input dalam bentuk kolom yg panjangnya tidak lebih dari 2^L+L % dan merupakan perpangkatan dari 2 % h0 = koefisien filter (lowpass) % L = level dekomposisi (jumlah filter highpass dalam filter banks) function an = analyze(x, h0, L) lf = length(h0); lx = length(x); an = x;
% Panjang filter % Panjang data % Inisialisasi output
% Menghitung koefisien highpass dari koefisien lowpass for i = 0:(lf-1) h1(i+1)=(-1)^i*h0(lf-i); % Alternating flip end
10
% Menghitung output filter untuk semua level for i = 1:L a_ext = an; lpf = conv(a_ext,h0); % Filter lowpass FIR hpf = conv(a_ext,h1); % Filter highpass FIR lpf = lpf(1:lx); % Remove extra points hpf = hpf(1:lx); % Remove extra points lpfd = lpf(1:2:end); % Downsampling hpfd = hpf(1:2:end); % Downsampling an(1:lx) = [lpfd hpfd]; % Output lowpass pd awal array lx = lx/2; subplot (L+1,2,2*i-1); % Plot kedua output filter plot (an(1:lx)); % Output lowpass if i == 1 title('Output Lowpass') end subplot(L+1,2,2*i); plot(an(lx+1:2*lx)); if i == 1 title('Output Highpass') end end HPF = abs(fft(h1,256)); LPF = abs(fft(h0,256));
% % % %
freq = (1:128)*1000/256; subplot(L+1,2,2*i+1); plot(freq, LPF(1:128)); text(1,1.7,'Filter Lowpass'); xlabel('frekuensi (Hz)')' subplot(L+1,2,2*i+2); plot(freq, HPF(1:128)); text(1,1.7,'Filter Highpass'); xlabel('frekuensi(Hz)')'
Menghitung dan menggambar fungsi transfer dari HPF dan LPF Misal fs = 1000 Hz
% Plot dari 0 hingga fs/2 Hz
----------------------------------------------------------------------% % % % %
Fungsi untuk menghitung filter sintesis an = synthesize(a, h0, L) a = output bank filter analisis (hasil fungsi analyze.m h0 = koefisien filter (lowpass) L = level dekomposisi (jumlah filter highpass dalam filter banks)
function y = synthezise(a, h0, L) lf = length(h0); lx = length(a); lseq = lx/(2^L); y = a; g0 = h0(lf:-1:1);
% Panjang filter % Panjang data % Panjang segment lowpass dan % highpass pertama % Inisialisasi output % Koefisien lowpass dgn order flip
% Menghitung koefisien highpass h1(n) dari koefisien lowpass % menggunakan alternating flip for i = 0:(lf-1)
11
h1(i+1)=(-1)^i*h0(lf-i); end g1 = h1(lf:-1:1);
% Koefisien filter highpass dgn % order flip
% Menghitung output filter untuk semua level for i = 1:L lpx = y(1:lseq); % Ambil segmen lowpass hpx = y(lseq+1:2*lseq); % Ambil segmen highpass up_lpx = zeros(1,2*lseq); % Inisialisasi upsampling up_lpx(1:2:2*lseq) = lpx; % Upsampling lowpass up_hpx = zeros(1,2*lseq); % Inisialisasi upsampling up_hpx(1:2:2*lseq) = hpx; % Upsampling highpass syn = up_lpx + up_hpx; % Filter dan gabungkan y(1:2*lseq) = syn(1:(2*lseq)); % Remove extra points lseq = lseq*2; % Menggandakan panjang segmen % utk yg berikutnya
12
