BAB 2 LANDASAN TEORI
2.1
Noise Pada saat melakukan pengambilan gambar, setiap gangguan pada gambar dinamakan dengan noise. Noise dipakai untuk proses training corrupt image, gambarnya diberi noise dan pada saat ingin melakukan image denoising.
merupakan suatu set sinyal yang terdapat noise dimana untuk proses image denoising agar menjadi nilai , yang merupakan patch sinyal dan nilai noise sudah berkurang didalamnya terdapat noise Berdasarkan bentuk dan karakteristiknya, noise pada gambar dibedakan menjadi beberapa macam yaitu: 1. GaussianWhite Noise Noise Gaussian merupakan model noise yang mengikuti distribusi normal standar dengan rata-rata nol dan standar deviasi 1. Efek dari Gaussian noise ini, pada gambar muncul titik-titik berwarna yang jumlahnya sama dengan persentase pada noise. 2. Speckle Noise Speckle merupakan model noise yang memberikan warna hitam pada titik yang terkena noise. 3. Salt & Pepper
8
9 Noise Salt & Pepper seperti halnya taburan garam, akan memberikan warna putih pada titik yang terkena noise
2.2
Representasi dan sparsity Sinyal adalah besaran besaran fisik yang berubah – ubah terhadap satu atau beberapa variabel bebas. Representasi adalah bagaimana menyatakan suatu sinyal dalam basis pembentuknya / dictionary. Representasi tidak mengubah banyak data sinyal asli. Representasi dilakukan dengan harapan suatu sinyal dinyatakan dalam basis pembentuk yang tepat sehingga menghasilkan penempatan atau sparsity. Dengan sparsity maka hanya sebagian nilai koefisien yang besar yang memuat sebagian besar informasi dari sinyal. Sedangkan sebagian besar lainnya memiliki nilai koefisien yang kecil yang tidak memuat informasi dari sinyal sehingga dapat dihilangkan. Rumus representasi adalah sebagai berikut : (2.1) Dimana : = sinyal input = dictionary = representasi koefisien Matriks dan
ukurannya berukuran
sedangkan ukuran nilai matriks pada
adalah
. Representasi sparse adalah representasi sebuah
sinyal yang memiliki nilai non-zero yang sedikit. Melakukan representasi sparse maka memudahkan proses pengolahan sinyal. Sinyal y dikatakan k-sparse apabila
10 sejumlah
dari
koefisiennya bernilai tidak nol, sedangkan sisanya (
bernilai nol. Kondisi sparse yang diinginkan adalah ketika
)
.
.
2.3
Sparse approximation Aproksimasi merupakan pendekatan dalam mengambil suatu data. Data yang diambil hanya sebagian sedangkan sisa datanya dijadikan nol. Ketika melakukan aproksimasi maka akan terdapat selisih antara data asli dengan data yang diaproksimasi. Selisih ini yang dikenal dengan sebutan norm error. Aproksimasi dapat dibedakan menjadi dua jenis yaitu aproksimasi linier dan aproksimasi non-linier. Pada aproksimasi linier sebagian data yang diambil adalah data yang terletak di bagian depan sedangkan sisanya dijadikan nol. Sementara pada aproksimasi nonlinier sebagian data yang diambil adalah data yang paling besar setelah data-data tersebut diabsolutkan. Data – data yang tidak diambil dijadikan nol. 2.3.1 Algoritma Greedy Algoritma greedy merupakan metode yang paling populer untuk mencari solusi optimasi / terbaik dengan mencari nilai terbesar atau terkecil. Pada setiap langkah membuat pilihan optimum lokal, dengan
harapan
langkah sisanya ke optimum global. Contohnya adalah dalam metode penukaran uang. Terdapat uang dengan nilai 1, 3, 4, 5. Jika koin yang ditukar berupa 7 maka dengan solusi greedy untuk mencari nilai terbesar, koin yang didapat berupa 5, 1, 1. Sedangkan solusi optimalnya 4, 3. Oleh
11 karena itu pada kenyataanya dalam menggunakan metode greedy tidak selalu mencari nilai terbaik.
2.4 Orthogonal Matching Pursuit Orthogonal Matching Pursuit adalah algoritma yang bersifat greedy dalam menemukan sparse dari suatu sinyal yang diberikan. Algoritma ini mencoba menemukan basis vektor terbaik (atom) secara iteratif, sehingga dalam setiap iterasi eror dalam representasi berkurang. Hal ini dicapai dengan pemilihan bahwa atom dari dictionary memiliki proyeksi terbesar dan mutlak pada vektor eror. Hal ini pada dasarnya menunjukkan bahwa dalam memilih atom yang menambahkan informasi maksimum sehingga secara maksimal mengurangi kesalahan / eror dalam rekonstruksi sinyal vektor
dan dictionary
mendapatkan nilai dari vektor
, algoritma OMP digunakan untuk
dalam tiga langkah, yaitu :
1. Pilih atom yang memiliki proyeksi maksimal pada residunya. 2. Perbarui 3. Perbarui residu
2.5
.
Norm Secara matematis norm adalah ukuran total atau panjang semua vektor dalam ruang vektor atau matriks. Untuk mempermudah, dapat dinyatakan bahwa semakin besar norm-nya maka semakin besar nilai matriks atau vektor. Norm dapat datang dalam berbagai bentuk dan banyak nama.
12 2.5.1 l0-norm optimization l0-norm optimization dirumuskan sebagai : (2.2) Banyak aplikasi termasuk compressive sensing mencoba untuk memperkecil norm-l0 pada vektor yang ssesuai dengan constraint. Persamaan strandar dalam minimization :
Namun hal tersebut tidak dapat dikerjakan, karena kurangnya representasi norm sehingga dianggap sebagai NP-hard (terlalu kompleks dan mustahil dipecahkan), oleh karena itu untuk penyelesaiannya dengan menggunakan norm yang lebih tinggi seperti l1 dan l2.
2.5.2 l2-norm optimization l2-norm digunakan dalam hampir setiap bidang teknik dan ilmu pengetahuan secara keseluruhan. l2-norm didefinisikan sebagai (2.3) l2-norm dikenal juga sebagai Euclidean norm ataupun Frobenius norm, yang digunakan sebagai kuantitas standar untuk mengukur perbedaan vektor. norm Euclidean dihitung untuk perbedaan vektor, diketahui sebagai jarak Euclidean : (2.4) l2-norm optimization dirumuskan sebagai :
13 Asumsikan bahwa matriks kendala D memiliki full rank, masalahnya adalah bagaimana menentukan suatu sistem yang memiliki solusi tidak terbatas untuk mendapatkan persamaannya. Tujuan dalam hal ini adalah untuk mencari solusi yang terbaik, Dengan menggunakan perkalian Lagrange, dapat mendefinisikan:
(2.5) Ambil turunan dari persamaan diatas yang nilainya sama dengan nol untuk menemukan solusi optimal dan mendapatkan : (2.6) Dengan
memasukan
persamaan
tersebut
kedalam
constraint
untuk
mendapatkan
Persamaan akhirnya : (2.7)
Dengan menggunakan persamaan 2.7, dapat langsung menghitung solusi optimal dari masalah l2-optimasi. Persamaan ini dikenal sebagai Moore-Penrose pseudoinverse dan masalah itu sendiri biasanya dikenal sebagai masalah kuadrat terkecil, regresi kuadrat terkecil, atau optimasi Least Square. Namun, meskipun solusi dari metode kuadrat terkecil mudah
14 didapatkan nilainya bukan berarti menjadi solusi terbaik. Karena sifat kelancaran l2-norm itu sendiri, sulit untuk mencari solusi terbaik untuk menyelesaikan masalahnya.
2.6
Dictionary Overcomplete dictionary yang mengarah ke sparse representasi dapat dibuat 2 jenis, yaitu yang fungsinya di tentukan terlebih dahulu (pra-specified), dan fungsi yang mampu beradaptasi berdasarkan contoh sinyal yang diberikan. Dengan memilih tipe yang menentukan fungsinya (pra-specifief) terlebih dahulu maka mengarah ke algoritma sederhana dan cepat untuk evalusi dari sparse representasi. Contohnya adalah overcomplete wavelets, curvelets, dan sebagainya. Preferensi biasanya diberikan untuk frame yang ketat sehingga dengan mudah dilakukan pseudo-inverse[3]. Keberhasilan dictionary dalam aplikasinya tergantung pada seberapa cocok membentuk sinyal yang bersangkutan secara sparse. Dalam penelitian, dictionary yang digunakan mampu melakukan pelatihan / learning berdasarkan contoh sinyal yang diberikan ( ). 2.6.1 Transformasi Cosinus Diskrit (DCT) Transformasi cosinus Diskrit atau disebut dengan discrete cosine transform (DCT) adalah model transformasi fourier yang dikenakan pada fungsi diskrit dengan hnaya mengambil bagian cosinus dari eksponensial kompleks, dan hasilnya juga diskrit. DCT didefinisikan dengan : (2.8) = merupakan variabel frekuensi
15 = merupakan sinyal input = jumlah data / sampling Berbeda dengan DFT (Discrete Fourier Transform) yang hasilnya berupa variabel kompleks dengan bagian riil dan imajiner, maka hasil DCT hanya berupa bilangan riil tanpa ada imajiner, hal ini banyak membantu karena dapat mengurangi perhitungan. Dalam DCT nilai magnitude adalah hasil dari DCT itu sendiri
2.6.2 Algoritma K-SVD Singular Value Decomposition (SVD) merupakan suatu teknik dalam aljabar linear yang memiliki banyak fungsi dalam pengolahan gambar digital, dan bidang pemrosesan sinyal. SVD dikenal sebagai teknik yang sangat kuat, berkenaan dengan penyelesaian masalah persamaan atau matriks, baik singular maupun secara numeric yang mendekati singular. Keunggulan pada SVD adalah kemampuan untuk digunakan pada semua matriks riil berukuran (m,n). , dengan
Jika E adalah matriks riil dengan ukuran
. maka
rumus singular value decomposition pada E adalah (2.9) SVD merupakan perluasan dari data asli dalam sistem koordinat di mana matriks kovarians adalah diagonal. SVD didapat dari menemukan nilai eigen dan vektor eigen dari
dan
membentuk kolom dari V, vektor eigen dari
. Vektor eigen dari membentuk kolom U.
16 Nilai-nilai singular dalam S adalah akar kuadrat dari nilai eigen dari atau
. Nilai-nilai singular adalah entri diagonal dari matriks S dan
disusun dalam urutan. Nilai-nilai singular selalu bilangan riil. Jika matriks E adalah matriks riil, maka U dan V juga riil. Dimana kolom dari U adalah vektor-vektor singular kiri dan nilai U adalah matriks orthogonal
, S (dimensi yang sama dengan E) bernilai
memiliki nilai tunggal dan orthogonal matriks dengan ukuran
diagonal matriks, dan V adalah square maka pada dan
memiliki baris
yang vektor-vektor singular kanan. Karena nilai U dan V berupa orthogonal, maka dapat ditulis :
Dimana nilai transpose pada setiap matriks setara dengan inverse. Elemen yang berada pada di diagonal pada D, diberi simbol
. Dimana
merupakan nilai singular pada E.
Jika matriks E berbentuk kotak
maka kita dapat menggunakan singular value decomposition untuk mencari nilai inverse. Nilai inversenya adalah
Contoh perhitungan SVD : Carilah nilai singular value decomposition pada matriks :
17
Tahap pertama adalah mencari nilai transpose matriks E
Tahap selanjutnya adalah mencari nilai eigenvalues pada W. untuk mencari nilai eigenvalues dapat menggunakan rumus
.
adalah matriks
indentitas. Nilai eigenvaluesnya adalah {0,1,6}, nilai yang diambil hanya yang bernilai positif. Singular value didapat dari akar nilai eigenvalue yang bernilai positif.
S didapat dari nilai singular value yang ditaruh secara diagonal. Terdapat 2 nilai singular value maka ukuran matriks S bernilai
matriks. (2.10)
Selanjutnya cari nilai eigenvector pada W yang berhubungan dengan nilai eigenvalues untuk mendapatkan normalize dari eigenvectornya. Dengan menggunakan Eigenvalue = 6,
Didapat
18 Maka nilai eigenvectornya dapat ditulis
Mencari nilai normalize pada eigenvector
Setelah mendapatkan nilai normalize pada eigenvector dengan nilai eigenvalue = 6 maka selanjutnya cari nilai normalize pada eigenvector dengan nilai eigenvalue = 1.
Maka didapat
Nilai U didapat dari nilai normalized eigenvector, maka didapat
(2.11)
Setelah itu, carilah :
19 Maka didapat nilai eigenvalue {1,6} dan didapat normalized eigenvectornya adalah :
V didapat dari eigenvector diatas :
(2.12)
Pada perhitungan diatas telah didapat nilai singular value decomposition pada matriks E. untuk membuktikan hasilnya dapat memakai persamaan 2.9
2.7
Mean Square Error (MSE) Mean Square Error (MSE) merupakan ukuran kontrol kualitas yang digunakan untuk mengetahui kualitas dari suatu proses. MSE menghitung seberapa besar pergeseran data antara sinyal sumber dan sinyal hasil keluaran, dimana sinyal sumber dan sinyal hasil keluaran memiliki ukuran yang sama. Nilai MSE yang baik adalah mendekati 0 (MSE ≈ 0). Rumus dari perhitungan MSE adalah (2.13)
20 = Mean Square Error = Sinyal input = Sinyal output = panjang sinyal
2.8
Peak Signal to Noise Rasio (PSNR) Parameter ukur yang digunakan untuk mengetahui gambar digital yang dihasilkan dari proses restorasi dalam penelitian ini adalah PSNR. PSNR (Peak Signal to Noise Ratio) merupakan nilai perbandingan antara nilai maksimum dari gambar hasil filtering dengan nilai rata – rata kuadrat eror (MSE), yang dinyatakan dalam satuan desibel (dB). Secara matematis, nilai PSNR dapat dirumuskan sebagai berikut : Rumus nilai PSNR : (2.14) Dimana : = Mean Square Error Max sinyal = nilai maksimum dari gambar
