BAB 2 LANDAS AN TEORI
2.1
Representasi dan Sparsity Representasi sinyal adalah suatu koefisien yang menyatakan suatu sinyal dalam bentuk sinyal basis. Representasi sinyal diperoleh dari hubungan kombinas i linear antara atom-atom (tiap kolom dalam matriks sebuah dictionary), dengan sinyal input. Secara matematis dinyatakan sebagai berikut: N
y = ∑ d i xi
(2.1)
i =1
Dimana: y : sinyal input d : dictionary atau basis x : koefisien representasi Persamaan (2.1) diatas biasa ditulis dalam bentuk matriks menjadi y = Dx ( D adalah matrix N × N sedangkan y dan x adalah vektor N × 1 ). Dictionar y merupakan sekumpulan konstanta sinyal basis dari frekuensi rendah ke frekuens i tinggi. Bentuk sinyal basis mempengaruhi hasil koefisien representasi dari suatu sinyal, karena itu tidak ada basis yang mampu merepresentasikan semua bentuk sinyal dengan baik. Representasi sparse adalah representasi sebuah sinyal yang memiliki nilai non-zero yang sedikit. Representasi sparse dapat memudahkan proses pengolahan sinyal, hal ini disebabkan karena dengan sparse representation suatu sinyal akan direpresentasikan menjadi bentuk yang lebih “padat” informasi. Sehingga memudahkan pengambilan data untuk proses lebih lanjut seperti 6
7 kompresi atau ektraksi ciri. Hasil representasi menggambarkan penyebaran sinyal basis dengan berbagai frekuensi yang berada pada gambar tersebut, sehingga dapat diamati tingkat frekuensi apa saja yang dimiliki gambar tersebut. Kebanyakan sinyal atau citra memiliki representasi yang sparse bila dinyatakan dengan basis yang tepat [3]. Sinyal y dikatakan K-sparse apabila sejumlah K dari N koefisiennya bernilai tidak nol, sedangkan sisanya ( N − K ) bernilai nol. Kondisi sparsity yang diinginkan adalah ketika K << N . Pada kenyataannya tidak ada sinyal yang sparse, yang ada adalah sinyal yang compressible, yaitu apabila sinyal y memiliki koefisien representasi x yang memiliki sebagian kecil koefisien bernilai besar dan sebagian besar sisanya bernilai kecil [8]. Dari sinyal yang compressible, sparsity bisa didapatkan dengan mengambil sebagian koefisien besar saja dan mengabaikan sisanya menjadi nol. Teknik tersebut disebut transform-coding yang merupakan teknik umum yang digunakan pada kompresi citra [9].
Gambar 2.1 [3] (a) Citra asli berukuran 1 Megapiksel. (b) Koefisien-koefisien wavelet. (c) Rekontruksi citra yang didapatkan dengan hanya menggunakan 25.000 koefisien wavelet terbesar.
8 2.2
Dictionary Yang dimaksud dengan dictionary atau kamus dalam image processing adalah sekumpulan sinyal elementer dalam bentuk konstanta, disebut atom, yang dapat merepresentasikan sinyal sebagai kombinasi linear dari atom-atom tersebut [10]. Bila kamus tersebut orthogonal, maka koefisien representasinya adalah inner product dari atom-atom dengan sinyal input sedangkan untuk kasus nonorthogonal koefisien representasi didapat dari inner product antara sinyal dengan inverse dari kamus, biasa disebut juga sebagai bi-orthogonal. Yang dimaksud dengan kamus orthogonal adalah kamus yang tiap atomnya unik, tidak dapat dibentuk dari komponen atom lain atau atau inner product antar atomnya nol. Kamus dapat disebut sebagai kamus lengkap apabila jumlah atomnya sama dengan panjang jumlah elemen sinyal input. Selama bertahun-tahun, kamus lengkap orthogonal dan bi-orthogonal dipakai secara luas karena secara matematis sederhana [10]. Kamus lengkap yang umum digunakan antara lain adalah kamus basis DCT yang digunakan pada kompresi JPG / JPEG dan kamus basis wavelet yang digunakan pada kompresi JPEG2000. Namun kamus lengkap memiliki beberapa kekurangan, misalnya keefektifan satu jenis kamus yang bagus hanya untuk tipe gambar tertentu, dan kekurangan tersebut mendorong pengembangan kamus lewat-lengkap atau overcomplete dictionary. Kamus lewat-lengkap adalah kamus yang memiliki jumlah atom lebih banyak dari panjang jumlah elemen sinyal input. Kamus lewat-lengkap dapat dihasilkan dengan berbagai metode, salah satunya yang paling sederhana adalah dengan menggabungkan beberapa kamus lengkap yang disebut dengan union basis. Secara matematis kamus lewatlengkap union basis didefinisikan sebagai:
9 D = [ B1 , B2 ,..., B L ]
(2.2)
Dimana: D : kamus lewat-lengkap B : kamus basis orthonormal L : jumlah kamus basis orthonormal yang digunakan. Karena kamus lewat-lengkap memiliki pilihan atom yang lebih banyak dari yang dibutuhkan oleh suatu sinyal, maka kamus lewat-lengkap diyakini dapat menghasilkan representasi yang lebih baik untuk berbagai macam sinyal.
2.2.1 Discrete Cosine Transform (DCT) M erupakan
salah
satu
kamus
lengkap
yang
umum
digunakan.
Kepanjangannya adalah Discrete Cosine Transform. Konstanta pengalinya merupakan sinyal kosinus yang sifatnya diskrit. Secara matematis, DCT dirumuskan sebagai berikut: N −1 ⎡ π ( 2x + 1)u ⎤ C (u ) = α (u)∑ f ( x ) cos ⎢ ⎥⎦ 2N ⎣ x =0
Dimana: u
: 0, 1, 2,…, N-1, merupakan variabel frekuensi
f (x )
: sinyal input
N
: jumlah data / sampling
(2.3)
10 Sedangkan inverse DCT adalah sebagai berikut: N −1 ⎡ π ( 2x + 1)u ⎤ f ( x ) = ∑α (u )C(u ) cos ⎢ ⎥⎦ 2N ⎣ u =0
(2.4)
Dimana: x : 0, 1, 2,…, N-1, merupakan variabel waktu
Dalam persamaan (2.3) dan (2.4), α (u) didefinisikan sebagai:
⎧ 1 ,u = 0 ⎪ ⎪ N α (u )⎨ ⎪ 2 ,u ≠ 0 ⎪⎩ N
(2.5)
Dari persamaan (2.3) didapat bahwa untuk u = 0 persamaan (2.3) menjadi: C (0) =
1 N −1 f ( x) N∑ x =0
Dengan kata lain untuk nilai u = 0 koefisien yang didapat merupakan koefisien DC sedangkan untuk nilai u yang lain koefisien yang didapat merupakan koefisien AC. Beberapa sifat dari DCT antara lain energy compaction, yaitu pemadatan informasi dari sinyal kedalam koefisien sesedikit mungkin, separability, yaitu pemisahan operasi DCT multi-dimensional menjadi beberapa operasi DCT 1 dimensi, dan orthonormal, yaitu inner product antara atom-atomnya bernilai 0 dan panjang tiap-tiap atom adalah 1. Sifat orthogonal memberikan keuntungan karena inverse dari matriks transformasi DCT sama dengan matriks trasnpose-nya. Sama seperti transformasi Fourier, DCT memproyeksikan sinyal input kedalam sekumpulan atom berupa sinyal kosinus yang kontinu sehingga DCT bagus dalam
11 menerjemahkan sinyal yang cenderung konstan atau smooth. Namun karena sinyal kosinus bersifat kontinu, DCT kurang bagus dalam menerjemahkan informas i sinyal yang bersifat lokal [10].
2.2.2 Transformasi Wavelet Istilah Wavelet pertama kali diperkenalkan oleh J. M orlet dan A. Grossmann [12]. Awalnya Wavelet berasal dari bahasa Perancis Ondelettes yang berarti gelombang kecil. Pada saat itu Wavelet masih berupa sebuah konsep matematika untuk menangani masalah analisis transien, ketidakstasioneran, serta time-variant. Penerapan dari Wavelet dalam pemrosesan sinyal baru ada setelah penelitian oleh Daubechies dan M allat [13] [14] [15]. Pada dasarnya transformasi Wavelet bekerja dengan mengkonvolusikan gelombang Wavelet dengan sinyal input. Kelebihan dari transformasi Wavelet adalah
sifat
multi-resolusinya.
Secara
matematis
transformasi
Wavelet
didefinisikan sebagai berikut: X WT (τ , s) =
1 s
⎛ t −τ ⎞ ⎟ dt s ⎠
∫ x (t ).ψ * ⎜⎝
(2.6)
Dimana: x (t )
: sinyal input
ψ (t )
: mother wavelet atau fungsi basis
Sedangkan inverse dari transformasi Wavelet didefinisikan sebagai berikut: ⎛ t −τ ⎞ x (t ) = ∫ ∫ X WT (τ , s )ψ ⎜ ⎟dτds ⎝ s ⎠
(2.7)
12 Dari fungsi basis tersebut didapatkan semua fungsi Wavelet yang dibutuhkan dalam transformasi melalui proses shifting dengan variabel τ sebagai informas i waktu / spasial serta proses scaling dengan variabel s sebagai informasi frekuensi. Dari persamaan (2.6) tersebut dapat kami lihat bahwa kelebihan dari transformasi Wavelet adalah hasil representasi koefisien dalam domain waktu / spasial dan frekuensi secara bersamaan serta sifat multi-resolusinya, untuk frekuensi rendah, gelombang Wavelet akan diperlebar dan berfungsi untuk menangkap informasi global dari sinyal, sedangkan untuk frekuensi tinggi gelombang Wavelet akan dipersempit dan berfungsi untuk menangkap informasi detil dari sinyal. Definisi diatas merupakan Continuous Wavelet Transform atau CWT. Dalam praktiknya transformasi Wavelet diproses menggunakan komputer sehingga dibuatlah teknik Discrete Wavelet Transform atau DWT. Proses DWT berbeda dengan CWT karena penghitungan koefisien dengan cara pencuplikan CWT membutuhkan proses komputasi yang berat. Untuk itu proses DWT menggunakan filter digital yang ekuivalen dengan mother wavelet pada proses CWT. Sebuah sinyal input akan dilewatkan pada sebuah low-pass filter dan high-pass filter sehingga menghasilkan 2 set koefisien. Untuk itu masing-masing set akan didownsampling menjadi setengahnya saja untuk menghasilkan jumlah koefisien yang sama dengan jumlah sinyal input. Hasil downsampling ini biasa disebut dengan koefisien a dan koefisien d . Koefisien a merupakan koefisien hasil dari LPF, berisikan informasi aproksimasi dari citra secara keseluruhan sedangkan koefisien d merupakan koefisien hasil dari HPF, berisikan informasi detil dari citra. Proses ini disebut proses dekomposisi satu level. Selanjutnya koefisien a
13 dapat digunakan sebagai input untuk proses dekomposisi level berikutnya. Proses ini dapat dilakukan beberapa kali hingga level dekomposisi yang diinginkan tercapai. Gabungan dari beberapa koefisien d dan satu koefis ien a dari LPF pada level terakhir disebut dengan koefisien Wavelet yang bersifat sparse. Gambar berikut menunjukkan DWT tiga level.
Gambar 2.2 Proses DWT tiga level
Pada setiap level dekomposisi, rentang frekuensi dari sinyal berkuran g setengah sehingga resolusi frekuensi dari koefisien meningkat dua kali pada setiap level. Hal inilah yang disebut sebagai sifat multi-resolusi dari transformasi Wavelet. Level dekomposisi maksimum yang dapat dicapai tergantung dari panjang sinyal, tentunya semakin panjang sinyal semakin dalam level yang bis a dicapai. Hasil koefisien dari DWT bisa didapatkan dengan menggabungkan semua koefisien a[n ] dan d [n ] dimulai dari level dekomposisi terakhir. Demikian juga untuk proses rekonstruksi, kedua set koefisien akan diupsampling menjadi 2 kali dan akan dilewatkan pada LPF dan HPF lalu dijumlahkan
untuk
mendapatkan
menunjukkan inverse DWT tiga level.
sinyal
rekonstruksi.
Gambar
berikut
14
Gambar 2.3 Proses inverse DWT tiga level
Pasangan filter HPF dan LPF yang digunakan dalam DWT harus merupakan quadrature mirror filter atau QMF. Pasangan HPF dan LPF merupakan QMF bila memenuhi persamaan berikut:
h[ L − 1 − n] = ( −1) n g [n]
(2.8)
Dimana: h[n]
: HPF
g [n]
: LPF
L
: Panjang filter
Jenis-jenis fungsi basis yang dapat digunakan sebagai mother wavelet dalam transformasi Wavelet ada banyak dan masing-masing memiliki karakteristiknya sendiri. Karena itu penggunaannya perlu disesuaikan dengan tujuan aplikasi untuk mendapatkan hasil yang efektif. Secara garis besar fungsi basis Wavelet dapat dibagi menjadi dua, yaitu orthogonal wavelet dan biorthogonal Wavelet. Beberapa Wavelet yang orthogonal adalah Haar, Daubechies, Coiflet, dan Symlet. Sedangkan yang bersifat biorthogonal adalah Meyer, Morlet, dan Mexican Hat.
15
Gambar 2.4 Berbagai macam jenis mother wavelet (a) Haar (b) Daubechies4 (c) Coiflet1 (d) Symlet2 (e) Meyer (f) Morlet (g) Mexican Hat.
2.3
Sparse Coding Sparse coding adalah proses pencarian koefisien y dari sinyal x dengan dictionary D yang disebut juga dengan proses dekomposisi atom. Proses ini melibatkan penyelesaian: (P0 ) (P0 ,∈ )
min x x
0
min x
Dimana .
x
0
subject to y = Dx
0
subject to y − Dx
(2.9)
2
≤∈
(2.10)
adalah l 0 norm (dibaca zero norm), yaitu jumlah koefisien non-
zero. Untuk mencari penyelesaian dari persamaan (2.9) dan (2.10), membutuhkan kompleksitas komputasi NP, karena bersifat kombinatorial [18]. Untuk itu biasanya digunakan algoritma pursuit dimana algoritma tersebut hanya mencari
16 penyelesaian aproksimasi saja. Algoritma pursuit memiliki banyak macam, salah satunya adalah Orthogonal Matching Pursuit atau disingkat OMP. OMP menggunakan algoritma greedy yang memilih atom dictionary secara sekuensial untuk mencari inner product terbesar antara sinyal dengan atom tersebut.
2.3.1 Orthogonal Matching Pursuit (OMP) Untuk mengaplikasikan OMP, dictionary yang digunakan harus bersifat orthonormal. Dalam setiap langkah, sebuah atom dari dictionary yang memiliki inner product terbesar dengan sinyal residu akan dipilih dan dimasukkan sebagai koefisien. Selanjutnya sinyal residual akan dihitung sebagai selisih dari sinyal input dengan sinyal rekonstruksi untuk kemudian mencari koefisien kembali. Untuk setiap sinyal y ∈ R n dan dictionary D dengan K atom {d k }Kk=1 , OMP akan dimulai dengan sinyal residu awal r0 = y , k = 1 dan dalam mencari koefisien x akan melakukan proses berikut: 1. M emilih indeks dictionary i k = arg max w rk −1 , d w 2. M eng-update koefisien x ik = rk −1 , dik 3. M eng-update sinyal rekonstruksi y k = Dx 4. M eng-update nilai residu rk = y − y k Proses pengulangan ini dapat dihentikan dengan menentukan jumlah perulangan k yang diinginkan, dengan menentukan besar norm dari residu r yang diinginkan, atau dengan menentukan besar inner product maksimal pada tahapan proses selanjutnya. OMP dapat diterapkan dengan mudah dan dapat diprogram
17 untuk menghasilkan koefisien dengan jumlah non-zero yang telah ditentukan sebelumnya. Variasi lain dari OMP adalah dengan tidak menggunakan inner product terbesar langsung sebagai nilai dari koefisien, melainkan menggunakan pseudoinverse dari sub-matriks kamus lewat-lengkap. Γ n adalah sebuah vektor beris i indeks dari elemen non-zero. Vektor ini digunakan untuk mengacu kepada submatriks dari suatu matriks dictionary D atau sub-vektor dari suatu vektor koefisien x . Untuk setiap sinyal y ∈ R n dan dictionary D dengan K atom {d k }Kk=1 inisialisasi r0 = y , s0 = 0 , Γ n = Ø , dan prosesnya adalah sebagai berikut: 1. M encari inner product atom dengan residu α i = d iT r n −1 untuk i ∉ Γ n−1 2. Semua indeks atom dengan inner product terbesar digabung dalam satu vektor Γ n = Γ n −1 U arg max α i 3. M enghitung koefisien menggunakan atom-atom yang terpilih x Γn n = DΓ' n y 4. M eng-update sinyal residu r n = y − Dx n
2.4
Peak Signal to Noise Ratio (PSNR) PSNR atau Peak Signal to Noise Ratio adalah perbandingan antara nilai power maksimum suatu sinyal dengan nilai power error atau noise. PSNR bias a dinyatakan dalam desibel, yaitu satuan logaritmik basis 10. Satuan desibel digunakan karena sinyal biasanya memiliki rentang yang sangat luas sehingga dengan desibel presentasi dari suatu nilai PSNR dapat disederhanakan karena
18 rentangnya menjadi jauh lebih kecil. Idealnya nilai PSNR adalah tak hingga yaitu ketika tidak terdapat noise sama sekali. Berikut adalah rumus dari PSNR: PSNR = 10× log10
Max Signal2 MSE
(2.11)
Dimana: PSNR
: Peak Signal to Noise Ratio (dB)
Max Signal
: Nilai maksimum sinyal
MSE
: Mean Square Error
MSE sendiri dirumuskan sebagai: MSE =
1 n (S 0 − S ) 2 ∑ n i =1
Dimana: S 0 : Sinyal input S : Sinyal output n : Panjang sinyal
(2.12)
