BAB 2 TINJAUAN PUSTAKA. Radar merupakan singkatan dari Radio Detecting And Ranging yaitu mencari

BAB 2 TINJAUAN PUSTAKA

2.1.

Pendahuluan Radar merupakan singkatan dari Radio Detecting And Ranging yaitu mencari

posisi target dan menentukan jarak antara sasaran dan sumber dengan menggunakan frekuensi radio. Istilah ini pertama kali digunakan oleh Angkatan Laut Amerika Serikat pada tahun 1940 dan diadopsi secara universal pada tahun 1943 pada awalnya di Inggris bernama Radio Direction Finding (RDF). Dapat dikatakan bahwa untuk radar semuanya diawali dengan penemuan frekuensi radio dan penemuan dari beberapa sub komponen seperti perangkat elektronik menghasilkan penemuan dan pengembangan sistem radar. Sejarah radar mencakup berbagai praktis dan teoritis penemuan pada abad 18, abad 19 dan awal abad ke-20 membuka jalan bagi penggunaan radio sebagai alat komunikasi. Meskipun pembangunan radar sebagai teknologi yang berdiri sendiri memang tidak sampai pada Perang Dunia II, prinsip dasar deteksi radar hampir sama tuanya dengan subjek elektromagnetik itu sendiri terlihat pada Gambar 2.1. Deteksi radar cuaca.

Gambar 2.1. Deteksi radar cuaca [4]

21 Universitas Sumatera Utara

Terdapat beberapa jenis radar dan data citra radar yang dipergunakan merupakan radar jenis Doppler [4], yaitu memiliki sifat: 1. Target yang diambil hanya objek yang bergerak dengan kecepatan minimum relatif terhadap radar atau terhadap latar belakang tetap. 2. Sistem pengolahan hamper (hambatan) seluruhnya menghilangkan klatter (sinyal yang tidak diiginkan dari latar belakang). 3. Tingkat PRF (Pulse Repetition Frequncy) dengan satuan (Sec-1,1000sec1

) yang jauh lebih tinggi dipergunakan untuk menghilangkan atau

mengurangi jumlah kecepatan yang tidak mampu dideteksi (blind speed). 4. Serta klasifikasi radar ini pada pita frekuensi C–band yang bekerja pada gelombang 4-8 cm dan frekuensi 4- 8 GHz. Terlihat pada Gambar 2.2.

Gambar 2.2. Jenis gelombang dan frekuensi [4]


Dari informasi radar diperoleh data berupa sinyal gelombang dan direfleksikan kedalam bentuk image awan sehingga dapat kita lihat bentuknya seperti pada Gambar 2.3.

Gambar 2.3. Hasil data radar (radar image) [4]

Rekrontruksi citra awan yang akan dilakukan perlu digunakan super resolution yang telah banyak dipakai untuk perbaikan (enhancement) kualitas citra yang diaplikasikan berbagai kasus praktis seperti pencitraan pada kedokteran (medical image), pencitraan satelit, aplikasi video dan digital fotografi dan data yang dihasilkan akan kita kawinkan dengan hasil perhitungan alat lightning detektor. Sebagai contoh pencitraan dengan resolusi tinggi pada kedokteran sangat membantu para dokter membuat diagnosa yang benar, mudah mengenali obyek yang sama dengan memakai citra resolusi tinggi dan bentuk pengenalan pola pada computer vision yang dapat ditingkatkan menggunakan citra resolusi tinggi (high resolution image) dan untuk hasil lightning detektor dapat dipergunakan untuk data lokasi pembangunanan tower serta lain sebagainya. Beberapa keuntungan dalam teknik 23 Universitas Sumatera Utara

pengolahan citra (image processing) dengan super resolution adalah transfer data yang lebih cepat, mengurangi biaya dan sistem citra resolusi rendah masih dipakai. Super resolution merupakan sebuah algoritma yang diharapkan mampu memberikan solusi untuk pemecahan berbagai masalah secara luas dalam meningkatkan kualitas citra mulai dari menghilangkan kabur, mempertajam dan menghilangkan noise sampai dengan pengolahan citra resolusi tinggi yang dibentuk dari berbagai citra resolusi rendah (low resolution images) untuk meningkatkan resolusi atau jumlah piksel pada citra saat bersamaan ditambahkan informasi resolusi tinggi yang bersesuaian dengan citra tersebut. Saat ini berbagai penelitian citra super resolution untuk meningkatkan kualitas citra hasil rekonstruksi. Rekonstruksi citra super resolution dapat diklasifikasikan sebagai berikut [5]: 1. Pendekatan Non Uniform Interpolation. 2. Pendekatan Domain Frekuensi. 3. Pendekatan Rekonstruksi Regularized Super Resolution: a. Pendekatan Deterministic. b. Pendekatan Stokastik ( Metode Bayesian, MAP,ML, dan MRF). 4. Pendekatan POCS (Projection onto Convex set). 5. Pendekatan ML (Maximun Likelihood) – POCS Hybrid. 6. Pendekatan Rekonstruksi lainnya: a.

Pendekatan Iterative Back Projection.

b.

Pendekatan Adaptive Filter. 24 Universitas Sumatera Utara

Dari beberapa klasifikasi rekonstruksi citra super resolution diatas dapat ditinjau dalam dua jenis rekonstruksi yaitu rekonstruksi berbasis interpolasi dan rekonstruksi berbasis training. Pada penelitian ini super resolution pertama kali digunakan pada kamera CCD untuk menangkap citra digital yang langsung meningkatkan resolusi ruang terhadap pengurangan ukuran piksel (peningkatan jumlah piksel perunit area). Pendekatan ini digunakan pula dalam teknik pemrosesan sinyal guna memperoleh citra resolusi tinggi dari berbagai citra resolusi rendah yang diamati.

2.1.1. Rekonstruksi super resolution berbasis interpolasi Super resolution berdasarkan interpolasi non uniform [5], dalam penelitian terdapat permasalahan yang berhubungan dengan rekonstruksi super resolution yaitu interpolasi citra yang digunakan untuk meningkatkan ukuran dari citra tunggal. Proses interpolasi non uniform diperoleh dengan cara: Estimasi dari pergerakan atau relativitas perpindahan (diperlukan registrasi bila informasi pergerakan tersebut tidak diketahui), interpolasi non uniform untuk menghasilkan perbaikan resolusi citra dan proses pengkaburan dari model yang diamati. Penelitian citra super resolution dengan pendekatan interpolasi telah lama dikembangkan melalui mechine learning misalnya pendekatan POCS [6] dengan mengestimasi parameter registrasi untuk permasalahan interpolasi citra super resolution menggunakan himpunan (convex set).


Kombinasi antara ML (atau MAP) dengan POCS juga dikembangkan untuk meminimalkan fungsi maksimum likelihood dalam kesesuaian frame resolusi tinggi dari urutan resolusi rendah. Gabungan stokastik dengan POCS ini diteliti oleh Elad dan Feuer pada tahun 1997 [7]. Selanjutnya Irani dan Peleg pada tahun 1991 [8] menggunakan pendekatan IBR (Iterative Back-Projection) dalam rekonstruksi citra super resolution yang dipakai dalam tomografi, resolusi tinggi diestimasi oleh perbedaan error oleh back projection antara citra resolusi rendah yang disimulasikan melalui citra kabur dan citra resolusi rendah yang diamati. Interpolasi dengan cubic B. spline banyak dipakai pada pengolahan citra seperti pada adobe photoshop [9] dengan menggunakan fungsi interpolator gaussian untuk ketajaman citra dan kehalusan pada area tertentu dan kemudian menggunakan metode Bayesian untuk super resolution [10].

2.2.2. Rekonstruksi super resolution berbasis training Exampled based-Approaches yang dikembangkan oleh WT.Freeman [11,12] mengemukakan bahwa 3 cara meningkatkan resolusi citra yaitu: a. Mempertajam dengan menguatkan bagian–bagian kecil citra Cara ini merubah spektrum amplitude frekuensi ruang pada citra yang berhubungan dengan ketajaman citra. Frekuensi yang tinggi pada citra diperkuat namun bagian noise tidak diperkuat.


b. Mengumpulkan dari frame ganda Mengekstrak frame tunggal resolusi tinggi dari urutan video citra beresolusi rendah dan menambahkan nilai. c. Super resolution untuk frame tunggal Mengestimasi bagian citra resolusi tinggi yang tidak dipresentasikan dalam citra asli.

Pembahasan mengenai super resolution yang mampu memberikan pemecahan masalah perbesaran frame tunggal yang dipakai untuk merekonstruksi citra dipilih karena pada kesempurnaan citra dalam dunia nyata sulit untuk mengambil (capture) citra. Saat ini telah dikembangkan oleh Herzmann et al [13] metode pembelajaran bentuk super resolution dengan kontes analogi antara citra, seiring dengan itu memfokuskan perbesaran citra [14]. Ketajaman merupakan parameter penting dalam pengolahan sinyal, interprestasi citra adalah ditentukan oleh kemungkinan mengekstraksi kandungan informasi. Bila citra menjadi kabur akan sulit untuk diinterprestasikan sebab terbatas oleh nilai resolusi citra. Jika ingin memperbesar citra diluar resolusi ini, dibutuhkan interpolasi yang akan menghasilkan sebuah citra kabur. Kenyataannya bahwa mustahil untuk menciptakan kehilangan informasi dimana kita tidak bisa melihat secara jelas citra aslinya. Bagaimanapun ini memberikan perenungan untuk memperkirakan data informasi yang hilang dengan meningkatkan resolusi citra yang disebut super resolution. Régis Destobbeleire [15] mengembangkan penelitian William T.Freeman 27 Universitas Sumatera Utara

[16] sebelumnya dengan menggunakan sebuah referensi himpunan ketajaman citra (a set of sharp images). Himpunan ini mempelajari hubungan antara frekuensi rendah dan frekuensi tinggi pada band citra dan kemudian memperkirakan band frekuensi tinggi yang hilang pada citra kabur. Ketajaman gambar didefenisikan sebagai sebuah citra yang keliatannya nampak sebagai pemandangan yang alamiah dan asli (real scene). Tetapi penginderaan manusia tidak mudah untuk menghitung dan mengakui bahwa ketajaman citra memiliki semua band frekuensi, berlawanan dengan sebuah citra kabur yang mana menggambarkan hilangnya informasi frekuensi tinggi namun akuisisi citra seperti pengambilan citra oleh fotografi cenderung menghasilkan citra kabur saat menangkap citra dengan kamera digital. Selagi pengambilan citra bergerak, citra akan menjadi kabur saat diperbesar karena membutuhkan interpolasi yang menyebabkan kabur. Oleh karena itu ketajaman citra merupakan elemen penting pada gambar yang dipandang. Ide utama dari super resolution adalah menggunakan beberapa citra sebagai referensi dengan tujuan training, bagaimana membentuk ketajaman dan perbesaran citra yang disebut training set. Ketajaman citra mengandung beberapa data yaitu frekuensi tinggi, menengah, dan rendah. Input citra adalah citra dengan skala yang dinaikkan (dengan faktor 2) yang menginterpolasikan kehilangan piksel. Kemudian diperoleh citra perbesaran namun data frekuensi tinggi hilang. Hal ini memungkinkan pemakaian training data yang sangat besar yang mampu menjangkau semua keanekaragaman dari kesempurnaan citra aslinya juga membutuhkan perhitungan komputer yang panjang sehingga diasumsikan beberapa properti dari citra asli dipakai 28 Universitas Sumatera Utara

guna meningkatkan efisiensi dari sebuah ukuran yang masuk akal pada training data untuk super resolution. Asumsi ini dilakukan dengan tiga band frekuensi (dekomposisi citra piramida). Frekuensi tinggi dikondisikan secara bebas dari band frekuensi yang paling rendah, berdasarkan korelasi ini maka kita bekerja pada dua band dan tidak mempertimbangkan keragaman (diversity) dari l band terendah, selanjutnya hubungan antara band frekuensi tinggi dan rendah adalah bebas pada citra lokal yang kontras. Lalu dengan normalisasi kontras setiap variabel citra akan dikurangi untuk meningkatkan efisiensi training set. Super resolution dapat ditinjau sebagai dua tahap yaitu: training set dan rekonstruksi band frekuensi tinggi yang hilang saat peningkatan ukuran skala citra input.

2.2.

Penelitian yang Dilakukan

Untuk rekonstruksi citra super resolution menggunakan Markov Network

telah

diteliti oleh Régis Destobbeleire dan W.T. Freesmann [15,16] . Pada penelitian yang diusulkan tetap mengaju pada hasil citra super resolution berdasarkan model Markov Network ini namun metode yang digunakan untuk perhitungan komputasi matrik yang menghasilkan 16 patch terbaik (the best matching patches) pada training set adalah menggunakan metode PCA. Proses ini digunakan dalam mengurangi dimensi variabel pada sejumlah training set yang sangat besar menjadi sebuah matrik 16x16 yang akan mempresentasikan komponen utama saja dari patch resolusi rendah yang


berukuran 7x7 piksel. Hasil yang akan diperoleh nantinya adalah sebuah pasangan patches resolusi rendah dan resolusi tinggi berukuran 5x5 piksel sebagai the best matching patches yang digunakan dalam proses identifikasi dan proses matching pada perhitungan frekuensi tinggi saat rekonstruksi citra diperbesar. Analisa yang digunakan adalah dengan mengukur jarak (Ecluidian distance) atau similaritas yang paling dekat dari patch yang cocok (sample matching)

pada setiap patch, juga

menghitung MSE dari setiap output dari patch yang dihasilkan dibandingkan dengan input patch, dan pengukuran PSNR yang dipakai untuk mengetahui kualitas citra hasil rekonstruksi.

2.3.

Rancangan Penelitian Pada penelitian ini super resolution pertama kali digunakan pada kamera CCD

untuk menangkap citra digital yang langsung meningkatkan resolusi ruang terhadap pengurangan ukuran piksel (peningkatan jumlah piksel perunit area). Pendekatan ini digunakan pula dalam teknik pemrosesan sinyal guna memperoleh citra resolusi tinggi dari berbagai citra resolusi rendah yang diamati. Konsep dasar pemikiran untuk meningkatkan resolusi ruang pada super resolution yang merepresentasikan ketersediaan citra resolusi rendah yang diambil dari beberapa obyek atau scene seperti terlihat pada Gambar 2.4. Pada super resolution bentuk citra resolusi rendah nampak dipresentasikan berbeda pada scene yang sama. Ini berarti bahwa citra resolusi rendah adalah sub


sampel yang digeser dengan presisi sub piksel. Bila citra resolusi rendah digeser oleh unit integer maka setiap citra mengandung informasi yang sama dan tidak ada informasi baru yang digunakan untuk rekonstruksi citra resolusi tinggi. Jika citra resolusi rendah memiliki perbedaaan pergeseran sub piksel dari setiap yang lainnya dalam kasus ini beberapa informasi baru yang dikandung oleh setiap citra resolusi rendah dapat dimanfaatkan untuk memperoleh citra resolusi tinggi. Dalam memperoleh perbedaan yang nampak dari scene yang sama, beberapa hubungan pergerakan scene yang dilihat dari frame ke frame melalui berbagai obyek atau video sequences.

Scene

dapat

diperoleh

dari

satu

kamera

dengan

beberapa

pemotretan (capture) atau dari beberapa kamera dengan posisi lokasi yang berbeda [17].

Gambar 2.4. Dasar pemikiran super resolution [5]


Pada kebanyakan aplikasi citra elektronik, citra dengan resolusi tinggi sangat diinginkan dan kadang-kadang juga sangat dibutuhkan. Citra resolusi tinggi memiliki arti sebagai tingkat kepadatan piksel dalam citra adalah tinggi, dan oleh karena itu citra resolusi tinggi dapat menawarkan tingkat detil yang lebih tinggi juga kadangkadang merupakan suatu hal yang kritis dalam beberapa aplikasi, seperti terlihat pada Gambar 2.5. Sebagai contoh, citra resolusi tinggi pada citra-citra medis akan sangat membantu dokter dalam melakukan diagnosa yang benar. Akan terasa lebih mudah untuk mencirikan sebuah obyek dari citra padanannya dengan menggunakan citra yang memiliki resolusi lebih tinggi dan juga performansi dari sistim pengenalan pola pada computer vision bisa ditingkatkan apabila citra resolusi tinggi tersedia.

Gambar 2.5. Sistem pemrosesan piksel [17]

Rekonstruksi

dan

restorasi

citra,

istilah

super

resolution

awalnya

dipergunakan dalam optik yang diartikan sebagai algoritma yang secara umum


beroperasi pada sebuah citra tunggal untuk menghitung data dari spektrum obyek diluar batas difraksi. Dua konsep super resolution ini (rekonstruksi super resolution dan restorasi super resolution) mempunyai fokus yang sama dalam aspek mengembalikan informasi frekuensi tinggi yang hilang atau tidak sempurna selama akuisisi citra. Bagaimanapun juga penyebab hilangnya informasi frekuensi tinggi berbeda dalam dua konsep tersebut. Super resolution restorasi dalam optik berfungsi untuk mengembalikan informasi diluar frekuensi cutoff difraksi sementara metode rekonstruksi super resolution dalam istilah teknik berupaya untuk mengembalikan komponen frekuensi tinggi yang rusak karena aliasing seperti terlihat pada Gambar 2.6.

Gambar 2.6. Model super resolution [5]


2.4.

Teori Markov Network

2.4.1. Defenisi Markov Network Defenisi bahwa Markov Network merupakan sebuah kondisi dengan syarat bebas (conditional independent) [18], misalnya A adalah bebas terhadap B oleh C maka: …………………….…….(2.1)

P(AB ,C) = P(AC) Notasi Phil David: A  BC

……………………………..(2.2)

Ekivalen dengan: P(A,BC) = P(AB,C)P(BC) = P(AC)P(BC)

…………...………………. ..(2.3)

2.4.1.1.Sifat-sifat Markov Network 1.

Dapat menentukan syarat bebas (conditional independent) dari arah distribusi l graph.

A.

2.

Diawali dengan mempertimbangkan 3 contoh sederhana.

3.

Dapat diberikan pemisah (d- Separation).

Contoh pertama Distribusi gabungan melalui 3 variabel oleh graph


1. Node B adalah “Head to Tail” berkenaan dengan path A-B-C. 2. Distribusi gabungan P(A,B,C) = P(A)P(BA)P(CB)

.......................... (2.4)

3. Kondisi pada node B

P(A,CB)=P(AB)P(CB) ................................... (2.5) A CB

...………………………….……...….….. (2.6)

Jika B bukan observasi maka: AC

………....………………………...….. (2.7)

4. Observasi pada B adalah path yang diblok dari A ke C.

B. Contoh kedua: 1. 3 node graph:

2. Distribusi gabungan P(A,B,C) = P(B)P(AB)P(CB)

…………... (2.8)


3. Node B adalah “Tail to Tail” berkenaan dengan path A-B -C 4. Kondisi pada node B

P(A, CB ) = P(AB)P(CB) ………….........…... (2.9)

A CB Jika B bukan observasi 5.

AC

Observasi pada B adalah path yang diblok dari A – C

C. Contoh Ketiga: 1. Node C adalah “Head to Head” berkenaan dengan path A-C-B

2. Distribusi gabungan P(A,B,C) = P(A)P(B)P(CA,B)

……….…. (2.10)

3. Bila C adalah bukan observasi P(A,B) = P(A)P(B)

.......................................... (2.11)

AC 4. maka kondisi pada node C


P(A,BC)=P(AC)P(BC) …………………………. (2.12) ABC

Yang bukan observasi “Head to Head” node C adalah path yang diblok dari A ke B,tetapi C sekali lagi adalah path yang diobservasi tidak diblok.

2.4.1.2. d- Separation Terdapat 3 kelompok dari node A,B,C untuk menentukan apakah syarat bebas dari pernyataan ABC adalah benar, pertimbangan semua kemungkinan 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 ACB. Prosedur ini sebagai filter yang dipakai pada sebuah distribusi probabilitas. Distribusi yang seluruhnya bersifat syarat bebas (conditional independence properties) termasuk oleh d-separation pada graph yang dikatakan secara tidak langsung sebagai sifat umum Markov Network D g. 37 Universitas Sumatera Utara

Teorema: DF

 DG

…………………………….……. (2.13)

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 path sepanjang node dalam C, seperti terlihat Pada Gambar 2.7.

Gambar.2.7. Undirected graph [17]

Dikatakan pemisahan ini bersifat undirected graph bila A dan B dipisahkan oleh C pada graph maka ABC .

2.4.1.3. Undirected Factorization Pengertian: 1. Sebuah himpunan node adalah lengkap bila terdapat sebuah hubungan dari setiap node terhadap setiap node yang lain dalam himpunan. 2. Sebuah clique kelompok terkecil merupakan maximal complete set dari sebuah node. Contoh: Graph dengan cliques {A,B,C} dan {B,C,D} terdapat pada Gambar 2.8. 38 Universitas Sumatera Utara

Gambar.2.8. Graph dengan clique [17]

Faktorisasi distribusi probabilitas dengan undirected graph jika dinyatakan sebagai perkalian dari fungsi positif atas clique pada graph. P(X)=1/Zc(Xc) c

…………………. (2.14)

c(Xc) adalah potensial clique 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).

P(X) = 1cc(Xc) Z ss(Xs)

………….………. (2.15)

Contoh sebelumnya clique adalah {A,B,C} dan {B,C,D}, dan himpunan pemisah (separator set) adalah {B,C}. Distribusi dengan faktorisasi berdasarkan graph istimewa dengan sifat undirected factorisation {F }.


Teorema: Untuk beberapa graph dan distribusi F => g juga g =>F untuk distribusi jika dan hanya jika graph triangular.

2.4.1.4. Directed Markov Network Sebagai penyederhanaan formula Dg dengan bantuan dari pemisahan undirected graph. Pemberian tanda panah arah kebawah akan nampak lebih sederhana dan penggunaan pemisahan undirected graph lebih jelas kesalahannya karena alasan tersendiri. Untuk pemecahan ini dengan menambahkan jalur yang menghubungkan semua parent untuk setiap node yang disebut moralization. Contoh seperti pada Gambar 2.9.

Gambar. 2.9. Moralization Markov [17]

Bagaimanapun moralization sendiri akan menekan beberapa syarat bebas misalnya ABC pada graph. Permasalahan yang muncul adalah pada node W saat node ini bukan bagian himpunan yang disyaratkan. Terlihat seperti pada Gambar 2.10


Gambar.2.10. Moralization dengan syarat bebas [17] Teorema: Jika probabilitas faktorisasai distribusi menurut directed acyclic graph, maka ABC dimana A dan B yang dipisahkan oleh C dalam graph terkecil ancestral set yang terdiri atas AU B U C, seperti pada Gambar 2.11.

Gambar 2.11. Ancestral set [13]

Contoh aplikasi pada Markov Random Field untuk citra super resolution seperti pada Gambar 2.12.

Gambar 2.12. Aplikasi teorema Markov Network [13] 41 Universitas Sumatera Utara

2.4.2. Menggunakan Markov Random Field Markov Random Field adalah sebuah model graph komplemen yang dapat menangkap ketergantungan interaksi secara simetri dan dapat dilihat pada Gambar 2.13. misalnya, sebuah spin lattice dimana tergantung dari nearest neighbor [19].

Gambar 2.13. Bentuk Spin Lattice MRF [19]

dimana sebelumnya harus mempertimbangkan graph semantic dan probabilitas distribusi yang berkorelasi. Untuk graph semantic dapat dijelaskan sebagai berikut:

x dan y adalah graph dengan syarat bebas yang diberikan oleh z jika semua path antara x dan y melintasi sepanjang z. Contoh persamaan simple independent:


………….………………..(2.16)

Untuk Markov Network:

................................(2.17)

Teorema faktorisasi Hammersley-Clifford: Distribusi konsisten oleh faktor undirected graph seharusnya mengikuti clique dalam graph. P(X)= 1/Z c(Xc) ………………………………. cclique

(2.18)

Z adalah konstanta normalisasi dan xc adalah variabel himpunan (node) yang dihubungkan dengan clique.Faktor non negatif c(xc) tergantung hanya pada variabel dalam setiap clique disebut sebagai potensial function, dapat dilihat pada Gambar 2.14.


Gambar 2.14. clique digambarkan oleh lingkaran dengan garis putus-putus clique adalah subset yang dihubungkan secara maksimal pada node dalam graph [20]

2.4.3. Pendekatan Nearest Neigborhood dalam MRF Untuk setiap piksel dalam citra adalah merupakan satu node dalam MRF [20], dan dapat dilihat Pada Gambar 2.15.

Gambar.2.15. Struktur Node MRF untuk Model Markov Network [16]

Piksel adalah node-node yang saling berpasangan pada Markov Random Field. Lingkaran putih xi adalah hidden node yang mempresentasikan sebuah piksel dan lingkaran hitam yi adalah node nyata yang muncul sebagai citra piksel. Pada Belief Propagation Algorithm akan ditentukan kompabilitas atau fungsi potensial antara neigbhboring hidden nodes , dan antara hidden node dan korespondensi node observasi . Secara umum neighboring pixel memiliki warna yang sama dengan 44 Universitas Sumatera Utara

asumsi bahwa dikodekan kedalam fungsi kompabilitasnya. Sebagai contoh, himpunan sebuah kompabilitas tinggi antara neighboring pixel yang berwarna sama dan kompabilitas rendah antara neighboring pixel dengan warna yang berbeda. Potensi ini dipakai sebagai pesan bahwa propagasi antara piksel terhadap indikasi warna apa pada setiap scene piksel seharusnya dimiliki. Persamaan (2.19) untuk menentukan probailitas distribusi bersama untuk semua node adalah:

………….. (2.19)

Untuk memaksimalkan P({x}) dengan menemukan state yang paling mirip untuk semua hidden node xi yang diberikan oleh semua node nyata yi. Pada belief propagation menggunakan belief untuk aproksimasi probabilitas ini. Belief bi (xi) dari sebuah node adalah: ………….……... (2.20)

mki adalah pesan (message) dimana node i diterima dari neighbor tersebut. Pesan di update menggunakan aturan sebagai berikut: …...…. (2.21)

pada Persamaan (2.21) perkalian pesan informasi (message) tidak termasuk satu dari node j, node-node ini melewati message. Kedua message mij(xj) dan lokal potensial i(xi) merupakan vektor-vektor yang memiliki panjang korespondensi terhadap 45 Universitas Sumatera Utara

jumlah state pada node xi yang dipakai. Neighbouring potential ij(xi,xj) adalah matrik N x M dimana N jumlah state dimana xj dapat diperoleh, dan M adalah jumlah state untuk node xi .

2.4.4. Identifikasi dengan struktur induk Nearest Neighbor Pada pembahasan mengenai pengenalan sebagai penentuan struktur induk nearest neighbor dengan mengira sebuah training set resolusi tinggi(Tj) sebagai bentuk piramida F0(Tj)…….FN(Tj). Juga mengira bahwa yang diberikan adalah input citra resolusi rendah (L0i) yang diperoleh., selanjutnya mengira bahwa citra ini merupakan sebuah resolusi dimana M=2k kali lebih kecil daripada sampel training. Citra diinterpolasikan dengan rasio faktor 2, citra interpolasi merupakan down-sample untuk menciptakan piramida tersebut pada level yang paling rendah dari bentukbentuk piramida yang dibuat oleh interpolasi. Untuk menghitung bentuk piramida bagi input citra dari level k dan kenaikan Fk(Loi)…….FN(Loi) [21].

Gambar 2.16. Identifikasi dan pengenalan citra pada proses training [21]


Pada Gambar 2.16 mengilustrasikan identifikasi dan pengenalan citra dengan level k=2. Perhitungan bentuk piramida F0(Tj)…….FN(Tj) untuk citra Tj dan bentuk piramida Fk(Loi)…….FN(Loi) bagi input citra resolusi rendah Loi. Untuk setiap piksel dalam citra resolusi rendah akan ditemukan the closest matching parent structure pada data resolusi tinggi. Mencatat dan menghasilkan output the best matching image BIi dan lokasi piksel pada the best matching parent structure BPi. Struktur data ini keduanya bebas untuk setia piksel (m,n) pada citra Loi dan membandingkannya dengan parent structure vector PSk(Loi)(m,n) terhadap semua vektor struktur induk training pada level k yang sama. Misalnya membandingkan PSk(Tj)(p,q) bagi semua j dan semua (p,q). The best matching image BIi(m,n) = j dan the best matching pixel BPi(m,n) = (p,q) keduanya disimpan sebagai output keputusan dari pengenalan, dengan bebas untuk setiap piksel (m,n) pada Loi. Pengenalan dengan vektor struktur induk ini untuk menemukan the closest matching pixel pada training set dengan struktur induk untuk dua piksel adalah hampir sama. Pencarian ini secara umum berlaku pada semua bentuk piksel pada semua citra dalam training set .

2.5.

Metode Statistik PCA PCA (Principle Component Analysis) merupakan metode yang digunakan

untuk menjalankan struktrur keragaman yaitu melalui suatu kombinasi linier dari variabel-variabel. Metode ini dapat juga digunakan untuk mengurangi dimensi dari


sebuah ruang. Dengan adanya pengurangan dimensi maka akan dihasilkan dimensi basis baru yang lebih baik dalam menggambarkan berbagai kumpulan model. Model disini adalah sekumpulan citra resolusi tinggi dan citra resolusi rendah dalam tahap training kemudian oleh kombinasi linier maka basis baru tersebut dilakukan konstruksi. Sering sumbu pertama dari sebuah dataset menjelaskan variasi dari sumber ukuran rata-rata untuk data allometric. Sebuah indikasi yang baik adalah sumbu utama (principle axis) sebesar % varian yang digambarkan. Hal ini bertujuan meningkatkan jumlah variabel sama dengan jumlah sumbu dalam peningkatan dataspace, terlihat pada Gambar 2.17.

Gambar 2.17. Diagram dataspace . [21]

Untuk setengah data yang layak dengan 10-20 variabel diharapkan 30% dari variasi pada sumbu utama pertama. Dalam memperoleh satu sumbu utama yang


cocok, dapat menggunakan sumbu kedua dengan varian yang lebih sedikit daripada sumbu pertama. Sumbu kedua mengcitrakan kemungkinan variasi maksimum yakni: A. Orthogonal (sudut 90 o) pada sumbu utama pertama. B. Dapat dihitung melalui rata-rata dari dataset (mean of dataset).

2.5.1. Konsep dasar PCA Teori PCA pertama kali di kembangkan oleh para ahli statistika. Metode PCA ini merupakan suatu teknik multivariate untuk menentukan korelasi antara sejumlah variabel kuatitatif. Teknik ini pertama kali dikembang pada tahun 1901 oleh K.Pearsong kemudian pada tahun 1933 dikembangkan oleh Hotteling aplikasi analisa PCA adalah menggunakan teknik pencarian kombinasi linier baku dari variabel data asli yang memiliki variasi yang maksimum. Secara umum teknik ini bertujuan untuk mencari kombinasi linier yang digunakan untuk meminimalkan data tanpa kehilangan informasi. Komponen utama pertama merupakan proyeksi kombinasi dari titik–titik pengamatan yang memiliki variansi terbesar diantara semua linier yang mungkin dan komponen utama kedua memiliki variansi terbesar kedua yang orthogonal dengan komponen utama pertama dan seterusnya. Setiap komponen utama merupakan kombinasi linier dari variabel–variabel aslinya dengan koefisien yang sama dangan vektor–vektor karakteristik (eigenvector) dari matrik korelasi atau matrik kovariansi. Variabel–variabel aslinya mempunyai nilai rata–rata 0 dan variasinya 1 sehingga dapat menghindari kemungkinan suatu variabel memiliki kemungkinan yang tidak menguntungkan pada komponen utama. Komponen utama dipisahkan oleh nilai–nilai 49 Universitas Sumatera Utara

karakteristik (eigenvalues) yang urutannya menurun dan sama untuk variansinya dari semua komponen tersebut. Sehingga dari nilai komponen utama pertama, kedua, ketiga dan seterusnya nilainya akan menurun dan jumlahnya adalah 100%. Komponen utama juga merupakan teknik representasi data. Representasi data yang diperoleh memenuhi suatu kriteria optimal. Dengan menggunakan komponen utama akan diperoleh kolom dan representasi baris pada ruang berdimensi satu (garis), dua (bidang), atau tiga (ruang). Metode PCA diaplikasikan untuk menentukan aspekaspek dari obyek yang mana merupakan tahap penting untuk proses identifikasi. Vektor–vektor karakteristik (eigenvector) dihitung dari sekumpulan data obyek. Setelah karakteristik didapatkan dan diwakili oleh sejumlah bobot maka bobot–bobot tersebut dapat digunakan sebagai identifikasi [22].

2.5.2. Parameter dan variabel PCA

PCA merupakan upaya untuk mengelompokkan variabel–variabel yang berkorelasi linier sejalan menjadi komponen utama. Sehingga dari “p” variabel akan didapat “q” komponen utama yang dapat mewakili seluruh persoalan. Atau dapat dikatakan bahwa PCA adalah suatu metode untuk menyederhanakan atau mereduksi variabel–variabel yang diamati dengan cara mengurangi dimensinya agar mempermudah analisis selanjutnya. Jadi di sini terjadi transformasi variabel asal menjadi variabel baru yang lebih sederhana. Transformasi yang dimaksud adalah


bersifat menghilangkan korelasi antar varaibel sehingga variabel baru yang di hasilkan akan saling bebas [23]. Meskipun pada PCA terjadi pengurangan dimensi tetapi informasi yang diberikan mengenai permasalahannya tidak akan berbeda atau sama. Dalam penerapannya, PCA tidak mutlak sebagai ukuran kepentingan suatu komponen karena mungkin diperoleh suatu komponen utama yang memberikan keragaman yang tidak terlalu besar tetapi penaksirannya mudah, jelas dan bermanfaat. Metode ini pula dapat digunakan untuk mereduksi sejumlah patch total variasi dalam training set yang dimasukkan, kemudian akan berusaha menjelaskan variasi tersebut kedalam suatu nilai karakteristik. Walaupun dari sejumlah X variabel yang diamati maka dapat diturunkan menjadi beberapa buah Y komponen utama tetapi tidak semua nilai dari Y digunakan untuk menjelaskan keragaman seluruh sistem, cukup beberapa Y saja. Ini sudah dapat menjelaskan secara memuaskan. Metode PCA dapat juga digunakan sebagai tahap awal dari sistem pemrosesan data yang besar misalnya digunakan untuk membangun masukan data membentuk analisa regresi demikian juga dalam analisa clustering dimana PCA digunakan sebagai input untuk menjelaskan pengelompokan. Jika dilakukan penelitian terhadap N individu, dan setiap individu diselidiki p buah variabel karakteristik maka organisasi data pengamatan dapat ditulis dalam notasi vektor sebagai berikut: X’ = ( X1 , X2……….., Xp) ............................. (2.22)

2.5.3. Matriks karakteristik (eigen) 51 Universitas Sumatera Utara

Sistem karakteristik (eigen sistem) adalah inti dari metode PCA yang berusaha merepresentasikan kemungkinan sebuah solusi yang dapat digunakan dalam sistem pengenalan (sample matching) pada sistem eigen akan dihitung nilai karakteristik (eigenvalue) yang bersesuaian dengan vektor karakteristik (eigenvector).

2.5.4. Nilai karakteristik dan vektor karakteristik Teorema: Misalkan A adalah sebuah matrik nxn, sebuah matrik bukan nol (P) yang berukuran nx1 sedemikian rupa sehingga AP = P dinamakan vektor karakteristik bagi A, sedangkan skalar  dinamakan nilai karakteristik bagi A yang bersesuaian dengan Persamaan (2.23) pendefinisian yaitu: AP = P ekivalen dengan IP = AP atau (I – A)P = 0 ..... (2.23) Persamaan (2.24) terakhir akan mempunyai solusi bukan nol jika dan hanya jika det (I - A) = 0

.......................................... (2.24)

Hal ini memberi petunjuk tentang bagaimana cara memperoleh nilai karakteristik dan vektor karakteristik.

2.5.5 Penentuan nilai karakteristik dan vektor karakteristik Untuk mendapatkan nilai karakteristik dan vektor karakteristik sekaligus digunakan metode reduksi Householder. Metode ini hanya bisa dikerjakan untuk matrik simetris. Untuk memudahkan pencarian vektor karaktritik P yang bersesuaian


dengan nilai karakteristik  pada matriks berukuran besar, maka diperlukan pemahaman mengenai metode reduksi Householder, dan perlu mengetahui defenisi– definisi matematika dasar dan aljabar linier. Sebab tanpa dasar ini maka kita akan kesulitan untuk mendapatkan pengertian vektor karakteristik yang bersesuaian dengan nilai karakteristik dalam metode reduksi Householder.

2.5.6. Transformasi kemiripan Transformasi

kemiripan

(Similarity

Transform)

adalah

untuk

mentransformasikan matrik A ke matrik B yang similar dengan matrik A yang telah dinormalisasi, dimana B adalah matrik diagonal yang dikomposisikan dari nilai karakteristik 1 , 2 , 3 ….  n. Tujuannya adalah untuk menunjukkan bahwa nilai karakteristik dari matrik diagonal B adalah nilai karakteristik dari A, dimana A dan B adalah dua matriks n x n dikatakan similar bila B = P-1AP. Dalam implementasi program untuk mendapatkan nilai karakteristik dan vektor karakteristik dengan menggunakan matriks P invers, P-1 akan mendapatkan kesulitan sebab nilai karakteristik di sini harus tidak boleh nol sehingga harus diusahakan agar p adalah matrik orthogonal. Agar P orthogonal maka A harus simetris. Oleh karena A matrik nxn adalah matrik simetris maka matriks AT = A. Dari uraian diatas maka terbukti bahwa P adalah matrik yang dapat didiagonalkan secara orthogonal. Oleh karena P adalah matrik orthogonal, maka matriks P-1 = PT. Akibatnya, matrik diagonal B pada uraian sebelumnya yang semula ditulis B = P-1AP ekivalen dengan B = PTAP


persamaan yang ditulis terakhir ini adalah persamaan untuk mendapatkan kemudahan dalam menentukan nilai karakteristik dan vektor karakteristik dengan menggunakan reduksi matrik householder [24].

2.5.7. Standarisasi hasil PCA a.

Memperoleh matrik dari semua koefisien korelasi–korelasi matrik. Dimulai dengan n kolom data kemudian mengambil [n x n] matrik yang menginformasikan mengenai hubungan antara setiap pasangan dari kolom. Mendapatkan eigenvector dan eigenvalue dari matrik yang diperoleh

b.

dengan teknik multivariabel mencakup analisa eigenvector.

Contoh: Analisa eigenvector serta dapat juga terlihat pada Gambar 2.18.[21] a.

Menghubungkan dengan baik perkalian matrik.

b.

Ambil [n x n] matrik m dan digunakan untuk mengalikan sebuah vektor [1 x n] pada baris 1.

c.

Vektor [1 x n] baru yang dihasilkan dari angka berbeda disebut V1.

d.

Kalikan V1 dengan m untuk mendapatkan V2.

e.

Kalikan V2 dengan m untuk mendapatka V3 dan seterusnya.

f.

Setelah pengulangan dari elemen V dengan pola menurun yang tetap maka diperoleh dominan eigenvector dari matrik m yaitu 1.


g.

Setiap waktu 1 dikalikan dengan m (a constant multiple) untuk memperoleh harga eigenvalue pertama dari m.e1.

*

1

V1

1 1

*

V1

V2

*

V2

V3

After a while, each successive multiplication preserves the shape (the eigenvector) while increasing values bySkema a constant amount (theeigenvector eigenvalue dan Gambar.2.18. mendapatkan

Eigenvalue [21] Secara umum standart deviasi, matrik kovarian dan matrik karakeristik dapat dijelaskan sebagai berikut: 1.

Persamaan linier (2.25) secara umum dapat dituliskan sebagai berikut: Y = Ax Y1 = a11x1 + a21x2 +……ap1xp Y2 = a12x1 + a22x2 +……ap2xp .. .

2.

.

………………(2.25)

.

Standar deviasi (variance) n

(X X) 

2

s2 i1

i

……………..…… (2.26)

(n1)


3.

Matrik kovarian (covariance)

Untuk menentukan matrik-matrik antara 2 variabel maka: n

( X  X )( Y  Y ) 

i  1 cov( X , Y ) 

i

i

( n  1 )

............................. (2.27)

Dimana: cov(X,Y)>0: Dimensi naik bersama cov(X,Y)<0: Satu Naik,Satu turun cov(X,Y)=0: Dimensi bebas Harga covariance antara semua kemungkinan dimensi: nxn .........…... (2.28) C  ( c | c  cov( Dim , Dim )) ij ij i j

4.

Matrik karakteristik Perhitungan

nilai

karakteristik

(eigenvalues)

dilakukan

pada

matrik

karakteristik yang bersesuaian dengan vektor karakteristik (eigenvector): Vektor x dituliskan sebagai A x disebut eigenvectors dari A (A = n x n matrik). Persamaan Ax = x, adalah eigenvalue dari A. Ax = x  (A-I) x = 0 Bagaimana menghitung x dan : 1. Hitung det (A- Ibidang polynomial (derajat n). 2. Determinan rata-rata det (A- Iakar adalah eigenvalues  3. (A- Isetiap  terdiri dari eigenvector x. 56 Universitas Sumatera Utara

BAB 2 TINJAUAN PUSTAKA. Radar merupakan singkatan dari Radio Detecting And Ranging yaitu mencari

Recommend Documents