PENERAPAN METODE PRIMAL DUAL ACTIVE SET UNTUK NON NEGATIVE CONSTRAINT TOTAL VARIATION PADA MASALAH DEBLURRING Riza Rediyanti Pratiwi1 – Rully Soelaiman2
[email protected],
[email protected]
Mahasiswi Jurusan Teknik Informatika ITS 1 , Dosen Pembimbing I 2 Jurusan Teknik Informatika Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember (ITS), Surabaya, 60111, Indonesia
Abstrak - Restorasi citra bertujuan untuk merekontruksi citra yang terdegradasi menjadi citra yang menyerupai citra aslinya. Minimisasi total variation (TV) digunakan untuk masalah deblurring dengan constraint non negativity. Dengan adanya penambahan constraint non negativity membuat proses penyelesaian menjadi sulit. Hubungan antara metode semi smooth Newton dan metode primal dual active set dimanfaatkan untuk mencapai banyak penyederhanaan dari perhitungan. Sehingga, citra yang terdegradasi dapat diketahui dikembalikan ke dalam bentuk semula dengan memanfaatkan hubungan antara metode semi smooth Newton dan metode primal dual active set. . Kata Kunci : Total variation, Non-Negative Constrained, Primal Dual Active Set.
Ku + n = f
1. PENDAHULUAN
(2.1)
Dimana u merepresentasikan citra asli, K adalah PSF, n adalah Gaussian white noise dan f merepresentasikan citra yang terdegradasi. Data pada suatu citra dipresentasikan ke dalam suatu bentuk matrik m x n, sedangkan K adalah bentuk matrik dari mn x mn.
Citra yang kabur merupakan salah satu permasalahan dalam pengolahan citra yang telah lama ada. Penyebab dari citra yang kabur ada berbagai macam, diantaranya adalah pergerakan alat optik (kamera) pada saat proses pengambilan gambar, penggunaan lensa dengan sudut yang lebar, dan sebagainya.
2.2 TOTAL VARIATION
Dalam pengolahan citra juga dapat dilakukan penambahan noise dan blur, sehingga membuat citra menjadi cacat. Penambahan noise dan blur ada berbagai banyak macam model salah satunya adalah Gaussian yang digunakan dalam pengerjaan tugas akhir ini. Permasalahan pada citra kabur tersebut dapat dimodelkan dengan menggunakan total variation, dan constraint yang digunakan adalah non-negativity.
Total Variation (TV) berdasarkan denoising pertama kali dikemukakan oleh Rudin, Osher dan Fatemi. Total Variation dari gambar adalah meminimalkan subject to constraint yang melibatkan statistik dari noise. Untuk perkiraan sebuah sinyal dalam noise, metode yang sering digunakan adalah berdasarkan kriteria least square. Model untuk non negative constraint masalah total variation deblurring adalah pada persamaan 2.2 2 1 (2.2) min K u − f + β u u ,u ≥ 0 2 TV
Dalam pengerjaan tugas akhir ini untuk mencari kondisi yang optimal pada citra yang telah cacat tersebut dengan menggunakan metode primal dual active set. Algoritma yang digunakan berdasarkan inspirasi dari metode Chan-Golub-Mulet (CGM). Metode CGM tidak menangani constraint nonnegativity, sehingga pengerjaan tugas akhir ini adalah memfokuskan untuk menangani non-negativity tersebut yang nantinya metode ini akan biasa disebut dengan Non-Negativity Chan - Golub - Mulet (NNCGM).
Dimana β merupakan parameter dari regulasi total variation. 2.3 METODE PRIMAL DUAL ACTIVE SET Formula dual diperoleh dengan menggunakan kombinasi antara Lagrangian dan fenchel dual. Formula primal yang akan dirubah ke dalam formula dual adalah pada persamaan 2.3.
2. DASAR TEORI 2.1 PROSES DEGRADASI CITRA Restorasi citra adalah proses dimana memperbaiki atau mengembalikan citra yang terdistorsi atau terdegradasi sehingga menyerupai citra aslinya. Proses dari degradasi citra dapat dimodelkan ke dalam bentuk berikut:
1 min u,u≥0 2
Ku − f
2
+β
u
+ TV
α
u 2
2
(2.3)
Persamaan dari 2.3 dapat pula ditulis seperti pada persamaan 2.4
1
⎧1 min⎨ Ku − f u ⎩2
2
+β
u
+ TV
α
2
u
2
⎫ + I (u ≥ 0)⎬ ⎭
Kuhn-Tucker (KKT). Kondisi optimal yang diberikan adalah sebagai berikut:
(2.4)
Dimana I(u≥0)=0 jika u≥0 untuk semua komponen u, I(u≥0)= ∞ jika semua komponen u adalah u>0. Dengan menggunakan transform Fenchel untuk TV norm, diperoleh persamaan 2.5
u TV = sup u,−divp
p ∇u ε − ∇u = 0
(2.12)
− βdivp − K T f − λ + Au = 0 λ − max {0, λ − cu } = 0
(2.13) (2.14)
dimana A = KTK + I dan c adalah konsta yang dapat berubah.
(2.5)
p , pi , j ≤1
Algoritma dari Primal Dual Active Set (PDAS) 1. Memasukkan beberapa parameter yang dibutuhkan. Parameter yang dibutuhkan antara lain adalah ε, α, ρ, c, FBIP Bandwidth (symmetric), Tol. Untuk outer iter (KKT residual), Max # outer iter, Tol. CG iter. Per outer iter, Max. # CG iter. Per outer iter, Max. line search (p), Initial guess untuk u, Initial guess untuk p, Initial guess untuk λ 2. Melakukan inisialisasi variabel p0, u0, λ 0, dan set k =0 k k 3. Set inactive dengan Ik = {i: λi − cui ≤ 0 }dan
Dimana p adalah dual variabel dan div adalah operator discrete convergance. Bentuk dari operator discrete convergance dapat dilihat pada persamaan 2.6.
(div )i , j
= p ix, j − p ix−1, j + p iy, j − p ix, j −1
(2.6)
Selanjutnya adalah mensubtitusi persamaan (2.4) dan (2.5), yaitu dapat dilihat pada persamaan (2.7). 2 α 2 ⎧1 ⎫ ⎪ 2 Ku − f + 2 u ⎪ min max⎨ ⎬ u p ⎪+ β u,−divp + I (u ≥ 0) − I pi , j ≤ 1 ⎪ ⎩ ⎭
(
untuk active set adalah Ak = {i:
(2.7)
)
4. Hitung nilai untuk δuki
2
2
+
α 2
u
2
+ u ,− β divp − λ
(
)
(2.8)
δp =
(
T
u = B K f + β divp + λ
(
)
L(λ ) = −
{
(2.9)
(2.17)
}
ρ supγ >0 pik, j + γδip, j ≤ 1∀i, j
)
(2.18)
−1
(
)
Untuk memperoleh persamaan persamaan 2.10 ke persamaan 2.8
)
2
2.11,
⎧⎪ 1 1 min min ⎨ B 1 / 2 K T f + βdivp + λ − f p λ 2 ⎪⎩ 2
2 2
8. Update nilai
p k +1 = p k + sδp k u Ik +1 = u Ik + δ u ki
2
1 1/ 2 T 1 B K f + βdivp + λ + f 2 2
(
(2.16)
7. Hitung step size s dengan menggunakan persamaan 2.18
dimana B = K K + αI . Langkah selanjutnya adalah masukkan persamaan 2.9 pada 2.8 yang menghasilkan persamaan 2.10 berikut ini. T
)]
δλA =−βDADIVδp+AAIδuI +DAF2 −AAuA
∇ u L = 0 adalah
T
[ (
1 −H∇ DITδuI −DATδuA −F1 ∇u ε
6. Hitung nilai untuk δλkA dengan persamaan 2.17
∇ u L = K K + αI u − K f − β divp − λ Penyelesaian
(2.15)
5. Hitung nilai untuk δp k dengan persamaan 2.16
Dimana λ adalah pengali Lagrangian multiplier untuk u≥0. Selanjutnya T
dengan persamaan 2.15
T ⎡ ⎤ 1 ⎛⎜ p(∇u) + (∇u) pT ⎞⎟ ∇+ A⎥ × DITδUi = g Di ⎢− βdiv I− ⎜ ⎟ 2∇u ε ∇u ε ⎝ ⎢⎣ ⎥⎦ ⎠
Mempertimbangan inner minimization untuk p tertentu dengan memberikan Lagrangian adalah pada persamaan 2.8 L(u,λ)= 1 Ku − f
λik − cuik > 0 }
⎫⎪ ⎬ ⎪⎭
u Ak + 1 = 0
(2.10)
λ kI + 1 = 0 λ kA+1 = λ kA + δλ kA
masukkan
9. Berhenti apabila kondisi hasil dari KKT sudah mencapai yang diinginkan,apabila belum mencapai kondisi yang diinginkan maka kembali ke langkah 3). Untuk menghitung hasil KKT yaitu dengan menggunakan (||F1||2 + ||F2||2 +||F3||2)1/2 dimana F1,F2,F3 diperoleh dari persamaan (2.12)-(2.14).
(2.11)
Untuk mengetahui kondisi optimal dari persamaan nonlinear (2.14) adalah dengan menggunakan Karush-
2
Berikut ini adalah penjelasan untuk spesifikasi dari beberapa parameter dari algoritma Primal Dual Active Set : 1. c merupakan bentuk dari nilai positif yang digunakan untuk menentukan active dan inactive set pada setiap iterasi. ρ digunakan untuk sedikit mempertahankan 2. perubahan pada size step. Nilai yang digunakan adalah 0.99 untuk semua tes numerik. ε merupakan perturbation konstan yang 3. memiliki nilai yang kecil untuk mencapai tradeoff antara fungsi error dan kecepatan konvergensi. 3. METODOLOGI Perancangan data merupakan hal penting untuk diperhatikan karena diperlukan data yang tepat agar perangkat lunak beroperasi secara benar. Data yang diperlukan dalam pengoperasian perangkat lunak yaitu data masukan (input) yang didapatkan dari pengguna, data proses yang dibutuhkan dan dihasilkan selama proses eksekusi perangkat lunak, dan data keluaran (output) yang memberikan hasil proses pengoperasian perangkat lunak untuk pengguna yang menggunakannya.
Gambar 3.3 Diagram Alir Proses Awal hingga Akhir Gambar 3.3 merupakan diagram alir proses dari awal hingga akhir pada sistem. Dimana terdapat suatu citra yang dikontaminasi noise terlebih dahulu untuk kemudian diproses dengan menggunakan metode primal dual active set untuk dicari hasil yang optimal dan iterasi yang dibutuhkan.
Data masukkan yang paling utama adalah sebuah citra grayscale berukuran 128 x 128 piksel bertipe tiff yang digunakan untuk proses restorasi.
Mulai
Menginisialisasi Parameter
Iterasi k+=max_iter
Set Active dan Inactive Set Hitung u Hitung p Hitung lambda Hitung step size p Update p,u,lambda
Gambar 3.1 Citra Inputan Selain itu SNR yang digunakan untuk membangkitkan noise. Sedangkan PSF merupakan suatu fungsi matematis yang menggambarkan proses blurring pada citra, seperti pengaruh suatu titik pusat cahaya terhadap titik yang lain sehingga menyebabkan efek blur tertentu.
Hitung KKT
N
KKT =
0 Y
Output: Citra yang diperbaiki, waktu, banyaknya iterasi
Selesai
Gambar 3.4 Diagram Alir Metode Primal Dual Active Set Gambar 3.32Citra Terkontaminasi Noise
Algoritma dari primal dual active set dapat dilihat pada gambar 3.4
3
Hasil yang diperoleh berdasarkan nilai PSF yang berbeda pada masing masing citra adalah menunjukan bahwa semakin besar nilai PSF semakin banyak iterasi dan waktu yang dibutuhkan untuk memperoleh hasil yang optimal.
4. HASIL UJI COBA DAN EVALUASI Skenario uji coba yang dilakukan adalah untuk mengetahui jumlah iterasi dan waktu yang dibutuhkan untuk memperoleh hasil citra yang optimal adalah membandingkan pengaruh dari PSF dan SNR pada tiga citra yang berbeda. Ukuran PSF yang digunakan adalah 3 x 3, 9 x 9, dan 15 x 15, sedangkan untuk SNR adalah -10dB, 20dB, dan 50. Citra yang digunakan adalah citra satellite, citra cameraman dan citra license plate.
Berikut adalah hasil uji coba berdasarkan nilai SNR yang berbeda pada citra satellite. Nilai SNR yang digunakan adalah -10dB, 20dB, 50dB. -10
20
50
Hasil uji coba yang dilakukan pada nilai PSF yang berbeda pada citra satellite. -10
20
50
4.2 Hasil Uji Coba Untuk Nilai SNR Citra Tabel 4.1 Hasil Uji Coba Untuk Nilai PSF Citra
Satellite
Camera man
License Plate
PSF
3x3 9x9
Ju mla h Iter asi 18 21
Waktu
L2 error
SN R (dB ) -10
Jumla h Iteras i 32
20
21
50
21
-10
36
20
19
50
21
-10
39
20
20
50
18
Satellite
77.703125 114.765625
15 x 15 3x3
25
201.281250
19
100.640625
9x9
20
139.546875
15 x 15 3x3
21
207.015625
19
103.000000
9x9
20
136.640625
15 x 15
20
193.796875
707.453399 1374.17496 8 2034.60575 7 2234.53730 4 2462.09611 1 2930.02227 4 2758.71404 7 2136.57781 0 2318.49727 1
Cameram an
License Plate
Waktu
L2 error
79.14062 5 114.7656 25 120.0937 50 88.39062 5 139.5468 75 139.6250 00 94.50000 0 136.6406 25 125.1093 75
21595.43809 5 1374.174968 1330.569494 98671.07636 2 2462.096111 2170.361721 123316.9690 18 2136.577810 1310.602393
Berdasarkan Uji coba yang dilakukan dengan menggunakan nilai SNR yang berbeda dapat diketahui
4
bahwa hasil optimal diperoleh pada nilai SNR sebesar 20dB. 5. PENUTUP 5.1 KESIMPULAN Dari hasil pengamatan selama perancangan, implementasi, dan proses uji coba, penulis mengambil kesimpulan sebagai berikut : 1. Masalah deblurring dengan menggunakan model berdasarkan total variation dapat bekerja dengan cepat dan kuat algoritma numerik untuk menyelesaikan masalah constraint non negativity. 2. Dari seluruh uji coba yang dilakukan dapat mencapai kondisi optimal untuk seluruh citra inputan yang digunakan dan hasil yang akurat. 3. Untuk memperoleh hasil yang akurat tidak terlalu banyak iterasi yang terjadi, sehingga waktu yang dibutuhkan tidak terlalu lama untuk memperoleh solusi yang optimal dengan menggunakan nilai PSF sebesar 9 x 9 dan nilai SNR sebesar 20 dB. 5.2 SARAN Melakukan uji coba dengan menggunkan citra berwarna agar dapat mengetahui hasil banyaknya iterasi dan waktu yang dibutuhkan 6. DAFTAR PUSTAKA [1] D., Krishnan, Ping, Lin, M., Yap. 2007 . A Primal-Dual Active Set Method for NonNegativity Constrained Total Variation Deblurring Problems. [2] T., F., Chan, G., H., Golub, P., Mulet. 1999 . A Nonlinear Primal – Dual Method for Total Variation Based Image Restoration. [3] L., I., Rudin, S. Osher and E. Fatemi. 1999. Nonlinear Total Variation Based Noise Removel Algorithm. [4] J., L., Carter. 2002. Dual Methods for Total Variation Based Image Restoration [5] C., R., Vogel, M., E., Oman. 1996. Iterative Methods for Total Variation Denoising
5
