PENERAPAN ANALISA KOMPONEN UTAMA PADA HIMPUNAN PELATIHAN MARKOV NETWORK DALAM PERBAIKAN KUALITAS GAMBAR

SEMINAR NASIONAL ELECTRICAL, INFORMATICS, AND IT’S EDUCATIONS 2009

PENERAPAN ANALISA KOMPONEN UTAMA PADA HIMPUNAN PELATIHAN MARKOV NETWORK DALAM PERBAIKAN KUALITAS GAMBAR Ir. Ni Putu Agustini, MT Jurusan Teknik Elektro Fakultas Teknologi Industri Institut Teknologi Nasional Malang e-mail : [email protected] ABSTRAK Analisa Komponen Utama (PCA) digunakan untuk mereduksi dimensi citra dalam proses perhitungan pada pelatihan Markov Network guna meningkatkan kualitas citra, antara lain menghilangkan kabur dan mempertajam citra. Metode ini mampu mencari patch citra terbaik dari training set yang diperoleh dari database berdasarkan neighboorhood patch searching dengan kalkulasi lebih cepat . Hasil yang diperoleh pada perbesaran citra memiliki kualitas citra pengukuran PSNR (Peak Signal Noise To Ratio) rata-rata 74,9 – 88,5% dan waktu pencarian patch terbaik dan memiliki delay runtime prosese lebih cepat dibandingkan dengan metode training based lainnya. Kata kunci : PCA, training set, PSNR

PENDAHULUAN Pendekatan analisa interpolasi bilinier atau cubic B-spline mampu menghilangkan kabur pada tepi secara rinci . Peningkatan pada frekuensi tinggi kurang sempurna dengan manusia sebagai operator dalam memutuskan tingkat perbaikan, namun beberapa pendekatan statistik memberikan hasil yang baik. Robust dan fast algorithm untuk ketajaman gambar belum ada meskipun banyak yang mencoba untuk membuat dan meneliti seperti yang dilakukan oleh Kersten dan Later, sementara Hulbert dan Paggio menggunakan pendekatan linier tetapi mereka masih memiliki kekurangan pada beberapa kasus, selanjutnya Freesmann menggunakan Bayesian Propagation Algorithm dengan hasil yang lebih efisien, algoritma ini menggunakan data training dalam menentukan parameter propagasi. Pada pengujiannya mencoba menggunakan One Pass Algorithm tanpa menggunakan model Markov Network yang sebelumnya digunakan. Training set yang dibangun dari model Markov Network masih lambat dan kurang efisien, sehingga masih memerlukan penelitian lanjut untuk menyempurnakan proses perbaikan kulaitas gambar berbasis training ini. Salah satu metode yang akan diterapkan untuk peningkatan kualitas gambar dan mendapatkan waktu proses yang lebih cepat adalah metode PCA(Principle Component Analysis).

Ekivalen dengan : P(A,B||C) = P(A||B,C)P(B||C) = P(A||C)P(B||C) (3) Distribusi gabungan melalui 3 variabel oleh graph

Node B adalah “Head to Tail” berkenaan dengan path A-B-C. distribusi gabungan P(A,B,C)=P(A)P(B A)P(C B) - kondisi pada node B

P(A,C B)=P(A B)P(C B) A⊥ ⊥C B

(2)

(5)

Jika B bukan observasi maka: A⊥ ⊥C φ observasi pada B adalah path yang diblok dari A ke C. - 3 Node graph :

TEORI MARKOV NETWORK 1. Defenisi MarkovNetwork Markov Network merupakan sebuah conditional independent misalnya A adalah independent dari B oleh C. P(A||B ,C) = P(A||C) (1) Notasi Phil David : A ⊥ B||C

(4)

-

Distribusi gabungan P(A,B,C)=P(B)P(A B)P(C B) (6)

Node B adalah “Tail to Tail” berkenaan dengan path A-B –C

B1-123


-

B1-124

separation pada graph yang dikatakan secara tidak langsung sebagai sifat umum Markov Dg

Kondisi pada node B

dengan persamaan P(A,C B)=P(A B)P(C B) A⊥ ⊥C B

(7) (8)

Jika B bukan observasi A⊥ ⊥C φ

(9)

Undirected Graph Sebuah himpunan A dan B dari node yang dipisahkan oleh sebuah himpunan ketiga C jika setiap path dari berbagai node pada A terhadap node pada B yang melewati jalur sepanjang node dalam C.

observasi pada B adalah path yang diblok dari A – C Node C adalah “Head to Head” berkenaan dengan path A-C-B

Gbr.1 Undirected graph Dikatakan pemisahan ini bersifat undirected graph bila A dan B dipisahkan oleh C pada graph maka

- Distribusi gabungan P(A,B,C)=P(A)P(B)P(C A,B) - Bila C adalah bukan oesrvasi P(A,B=P(A)P(B) A⊥ ⊥C φ -

(10)

(11)

Undirected Factorization Sebuah himpunan node adalah lengkap bila terdapat sebuah hubungan dari setiap node terhadap setiap node yang lain dalam himpunan sebuah klik atau kelompok terkecil (clique) yang merupakan maximal complete set dari node.Graph dengan cliques {A,B,C} dan {B,C,D}

maka kondisi pada node C

P(A,B C)=P(A C)P(B C) A⊥ ⊥B C

(12)

Yang bukan obeservasi “Head to Head” node C adalah patah yang diblok dari A ke B,tetapi C sekali lagi adalah path yang diobservasi tidak diblok. d- Separation Mempertimbangkan 3 group dari node A,B,C untuk menentukan apakah syarat bebas dari pernyataan adalah benar , pertimbangan semua kemungkina path dari node pada A terhadap node pada B.Beberapa path diblok jika sebuah node Ω dimana merupakan head to head atau tail to tail dengan aturan terhadap path dan Ω ε C. Sebuah contoh node khusus dengan head to head pada satu path khusus dan head to head terhadap sebuah graph yang berlainan.Jika semua kemungkinan path diblok maka . Prosedur ini sebagai filter yang dipakai pada sebuah distribusi probabilitas.Distribusi yang mana seluruh bersifat syarat bebas (conditional independence properties) termasuk oleh d-

Gbr.2.Graph dengan clique Distribusi probabilitas dikatakn faktorisasi berkenaan dengan undirected graph jika dinyatakan sebagai perkalian (product) dari fungsi positif atas cliques pada graph. P(X)=1/Z∏ψc(Xc) $

(13)

ψc(Xc) adalah cliques potensial dan Z adalah konstanta normalisasi. Untuk mempresentasikan lebih jelasnya secara umum adalah hasil dari potensi clique dibagi oleh potensi pemisah (Separator Potensial atau pemisah antara dua clique yang merupakan himpunan dari node yang dimiliki mereka secara umum)

(14) Contoh sebelumnya cliques adalah {A,B,C} dan {B,C,D}, dan himpunan pemisah (separator set) adalah {B,C}


Distribusi dengan faktorisasi berdasarkan graph istimewa berkenaan dengan sifat undirected factorisation F Torema :Untuk beberapa graph dan distribusi F => g juga g =>F untuk distribusi jika dan hanya jika graph triangular.

B1-125

membentuk subsample dari citra yang beresolusi rendah setengah dari jumlah pixel asli dalam setiap dimensi.

Directed Markov Sebagai penyederhanaan formula Dg dengan bantuan dari pemisahan undirected graph. Drop tanda panah lebih simpel dan penggunaan pemisahan undirected graph lebih jelas kesalahannya karena alasan tersendiri.untuk pemecahan ini dengan menambahkan jalur (link) yang menghubungkan semua parent untuk setiap node disebut moralization.Contoh : Gbr.6 Features Image Frekuensi Tinggi dan Frekuensi Rendah

Gbr. 3.Undirected graph Bagaimanapun moralization sendiri akan menekan beberapa conditional independencies misalnya pada graph.

Gbr.4.Moralization Undirected graph Permasalahan yang muncul adalah pada node W saat node ini bukan bagian himpunan yang disyaratkan. Teorema: Jika probabilitas faktorisasai distribusi menurut directed acyclic graph , maka kapanpun A dan B merupakan pemisah oleh C dalam graph terkecil ancestral set terdiri atas AU BUC

Pada himpunan pelatihan ini citra di pecahpecah menjadi patches dan hanya menyimpan patch resolusi tinggi yang menghubungkan setiap kemungkinan patch dengan resolusi rendah bentuk patches 5 x 5 piksel untuk citra resolusi tinggi dan 7 x 7 piksel untuk citra resolusi rendah. Pada tahap ini faktor keputusan adalah menentukan hasil yang ber kualitas dengan membuat hubungan antara band frekuensi tinggi dan menengah yang mempertimbangkan tetangga lokalnya , atau patches dalam setiap band. Untuk setiap patch resolusi rendah dihubungkan terhadap satu r esolusi tinggi di tengah daripada pixel yang sama tetapi tidak perlu dengan ukuran yang sama.Namun patch lokal sendiri tidak berisikan sejumlah data dalam memperkirakan resolusi tinggi secara detil.Untuk satu input patch,dapat diseleksi sejumlah dari patch resolusi rendah terdekat dari himpunan pelatihan.Freeman menunjukkan hubungan antara patch resolusi tinggi yang berbeda dan kemudian memilih tetangga terdekat (nearest neighbour) atau patch resolusi rendah untuk membuat band resolusi tinggi pada input citra untuk memperkirakan band resolusi tinggi yang sebenarnya. Input patch resolusi rendah yang dicuplik dimensi 7 x 7 piksel .Hasil observasi 16 closest patches dari database yang paling mirip (terdekat) untuk citra resolusi rendah adalah :

Gbr 5.Directed Acyclic graph Model Training Set Markov Network. Untuk tahap pelatihan ini Freeman telah menggunakan algoritma Markov Network. Cara membuat himpunan pelatihan ini dimulai dengan mengumpulkan citra dengan resolusi tinggi dan memperbaiki setiap citra yang berhubungan dengan peningkatan kualitas citra yang akan diproses nantinya. misalnya membuat kabur dengan

Gbr.7 Proses pencuplikan patch resolusi tingi, Hasil estimasi 16 patches korespondensi patches resolusi tinggi dengan satu closest patch resolusi rendah yang juga berasal dari database yang paling mirip(terdekat) adalah :


-

Gbr 8. 16 Closest patch gabungan antara patches resolusi rendah dan resolusi tinggi Model Hubungan Ruang Antar Patches Model hubungan ruang antar patches pada proses training set Markov network untuk rekonstruksi citra super resolusi dapat dilihat pada gambar 9. Model ini merupakan aplikasi dari Markov Random Field.

-

-

-

Gbr.9 MRF relasi antar ruang patch Untuk lebih jelasnya model ini dapat dipresentasikan sebagai berikut : - Lingkaran menggambarkan node jaringan dan garis menunjukkan statistik ketergantungan antara node. - Menentukan Patches citra resolusi rendah menjadi observasi pada node y dengan memilih 16 contoh closest untuk setiap input patch sebagai state yang berbeda dari hidden node x yang diestimasi. - Pada jaringan ini probabilitas node sebanding dengan hasil dari semua himpunan yang bersesuaian dengan matrik ψ yang menghubungkan kemungkinan states dar setiap pasangan tetangga hidden nodes dan vector φ menghubungkan setiap observasi pada hidden states yang pokok.

-

-

(15) Z adalah konstanta normalisasi. Hasil pertama adalah semua pasangan node tetangganya, i dan j , yi dan xi adalah patch resolusi rendah yang diobservasi dan patch resolusi tinggi yang diestimasi. Fungsi khusus Markov Network ψij(xi,xj) digunakan sebagai trik.Misalnya input node citras agar supaya patch resolusi tinggi terjadi

B1-126

overlap dengan lainnya oleh satu atau lebih pixel.pada daerah overlap, nilai pixel dari patches tetangganya yang bersesuaian seharusnya disepakati. Dengan mengukur dij(xi,xj) jumlah akar dari perbedaan antara kandidat patch xi dan xj dalam daerah overlap pada node i dan node j. Matriks antara node i dan node j adalah

(15) σ adalah parameter noise. Persamaan diatas juga adalah untuk menghitung dan mengevaluasi kesesuaian antara hidden node tetangganya dan antara pasangan dari hidden/node observasi dimana citra dibagi agar supaya korespondensi patches resolusi tinggi overlap.bila overlapping pixel dari dua node state matching, maka kesesuaian antara statetersebut akan tinggi. Menggunakan persamaan kuadrat yang sama pada akhir perbedaan antara patch citra resolusi rendah yi dan menemukan kandidat patch resolusi rendah dari training set xi, yang bersesuaian secara khusus dengan fungsi markov network φi (xi,yi). Patches resolusi tinggi yang optimal pada setiap node merupakan kumpulan dari probabilitas Markov Network Maksimun. Untuk menemukan solusi yang tepat dalam perhitungan komputasi dan menmperoleh hasil yang baik dan lebih cepat menggunakan fast training dengan metode PCA(principle Component Analisys).

HASIL PENGUJIAN DAN ANLAISA Perhitungan Training Set PCA Metode statistik untuk mereduksi ribuan patches pada training set dan juga dipakai dalam menentukan the best match patch yang mampu mempercepat proses iterasi adalah PCA, dengan hanya menghitung komponen utama dari 16 closets patches dan patches korespondensi resolusi tinggi. Hasil perhitungan algoritma PCA dapat dilihat dalam beberapa tahap diwah ini :

Gbr.10.Komponen Utama dari Patch Terbaik Pembentukan Patches Masing-masing citra training terdiri atas 100 sampel. Satu citra sample memiliki ukuran 200 x 200 piksel dengan toleransi + 50 piksel. Sehingga untuk satu citra terdiri dapat dibentuk sekitar 2500 –


3000 patches resolusi rendah dankombinasi gabungan patch resolusi tinggi dan rendah.perhitungan ini diperoleh dari citra resolusi rendah dengan ukuran patch adalah 7 x 7 piksel sedangkan untuk patch resolusi tinggi dengan ukuran 5 x 5 piksel. Contoh implementasi program pembentukan patches adalah :

B1-127

Proses Pembesaran Citra

Gbr. 12 Hasil pembesaran citra dan perhitungan PNSR

Gbr 11.Proses pembentukan patches Proses Scene Citra Proses scene ini adalah proses rekonstruksi citra untuk perbesaran.input citra pengujian terdiri atas 100 image yang mana dibagi atas 2 jenis citra , yaitu input citra training dan input citra non training. Proses perbesaran citra diasumsikan semua citra tranining telah melalui tahap praproses dan tahap training, serta tahap identifikasi (proses matching).. Akhir proses adalah sebuah citra perbesaran dengan display banyaknya jumlah patches yang direkonstruksi. Proses ini hanya mampu memperbesar image dengan factor perbesaran 2x dan 4x dengan sekali menekan tombol proses scene

Dari hasil diperoleh kualitas citra berdasarkan PNSR dan kecepatan proses yang dilakukan dengan metode Komponen Analisa Utama (PCA) memberikan hasil yang cukup baik dalam delay pemrosesan scene citra. Beberapa pengujian scene citra dan perhitungan kualitas citra telah dilakukan sebagai berikut :

Gbr.13. hasil scene citra factor 2 dan 8 KESIMPULAN Dari hasil pengujian dan training dengan metode Markov Network diperoleh citra perbesaran dengan kualitas citra hasil relatif lebih tajam, tidak kabur untuk perbesaran dengan factor 2x dibandingkan dengan factor 4x. Model Markov Network yang diterapkan pada training set mampu memberikan solusi untuk perbesaran citra super resolusi namun proses training sangat lama karena data training terlalu banyak (ribuan patches). Gbr 12 . Proses scene citra dengan factor 2


Metode fast training seperti PCA(Principle Component Analysis) dalam mereduksi perhitungan patches memberikan delay yang cukup kecil dalam proses pemcarian the best patches dalam proses numerik.

DAFTAR PUSTAKA [1].Sung Cheol Park, Min Kyu park, and Moon Gi kang , Super Resolution Image Reconstruction. IEEE Citra processing SN 1053-5888/2003. [2]. W.T. Freeman and E.C. Pasztor, “Markov Networks for Superresolution,” Proc. 34th Ann. Conf. Information Sciences and system (CISS 2000), Dept. Electrical Eng.,Princeton Univ., 2000. [3].Régis Destobbeleire Super-resolution, L. Velho (IMPA, Brazil) and S. Mallat (École polytechnique, France) May - June 2002 [4]. Dana Sharon, “ Loopy Belief Propagation in Image-Based Rendering” Department of Computer Science University of British Columbia [5]. Cristopher M.Bishop,”Probabilistic Graphical Model”.Graphs and Markov properties, Microsoft research, Cambridge, UK.July 2002 [6]. Tommi Jaakkola Machine learning and neural networks MIT AI Lab - [email protected] [7]. Simon Baker and Takeo Kanade “Limits on Super-Resolution and How to Break Them” The Robotics Institute Carnegie Mellon University Pittsburgh, PA 15213 IEEE Transactions on Pattern Analysis and Machine Intelligence [8].Junzhou Huang, Li Ma, Tieniu Tan, YunhongWang, “Learning Based Resolution Enhancement of Iris Images” National Laboratory of Pattern Recognition, Institute of Automation Chinese Academy of Sciences, P.O. Box 2728, Beijing, 100080, P.R. China [9].A.Herzmann et al.image analogies,Computer graphics (procsiggraph 2001)ACM press new york 2001 pp327-340

B1-128

PENERAPAN ANALISA KOMPONEN UTAMA PADA HIMPUNAN PELATIHAN MARKOV NETWORK DALAM PERBAIKAN KUALITAS GAMBAR

Recommend Documents