BAB II II.1
DASAR TEORI
Pencocokan Citra Digital Teknologi fotogrametri terus mengalami perkembangan dari sistem fotogrametri analog
hingga sistem fotogrametri dijital yang lebih praktis, murah dan otomatis. Proses otomatisasi pada fotogrametri dijital ditujukan untuk mengurangi proses pengambilan informasi dalam rangkaian kerja fotogrametri. Identifikasi titik sekawan pada fotogrametri dijital dapat dilakukan dengan otomatis menggunakan metode pencocokan citra (image matching). Problem dalam otomatisasi sistem fotogrametri dijital adalah sulit untuk mengidentifikasi titik sekawan secara otomatis pada citra homogen yang bertampalan. Pekerjaan mencocokan titik sekawan dalam fotogrametri analog membutuhkan seorang operator yang memiliki keahlian khusus untuk mengenali karakteristik kesamaan citra kiri dan kanan pada pasangan foto stereo. Otomatisasi pencocokan citra fotogrametri dijital diharapkan menjadi solusi terhadap masalah campur tangan dan kelelahan operator sehingga faktor ketelitian dan kecepatan dapat ditingkatkan. Pencocokkan citra adalah dasar proses otomatisasi pada rangkaian proses fotogrametri. Pencocokan citra dapat diaplikasikan untuk orientasi dalam dengan menentukan tanda tepi secara otomatis antara foto yang memiliki tanda tepi (fiducial marks) dan bagian citra lain yang bertampalan sehingga menghasilkan posisi yang ideal dari tanda tepi tersebut. Pencocokan citra juga dapat digunakan dalam proses orientasi relatif untuk menentukan titik sekawan sebanyak minimal 5 titik pada citra yang bertampalan dengan mencocokkan matriks pada citra kiri dengan titik sekawan pada citra kanan. Titik sekawan tersebut didefinisikan pada dua foto udara yang bertampalan sebagai titik indikator untuk mengetahui kelaikan model 3D hasil orientasi relatif. Pencocokan citra dalam orientasi absolut berperan dalam pengukuran titik kontrol utama dengan menghasilkan bagian citra lainnya (citra kanan) dari titik utama dibandingkan dengan bagian kecil dari foto udara. Pencocokan citra juga digunakan untuk menghasilkan DEM dengan mengotomatisasi serangkaian titik objek pada citra dipilih dalam satu bentuk DEM grid teratur untuk dipasangkan dengan serangkaian titik pada citra sebelahnya. Metode pencocokan citra yang banyak dipakai untuk keperluan proses fotogrametri adalah berbasis area (area-based) dan berbasis unsur (feature-based). Metode berbasis area menggunakan komposisi nilai derajat keabuan (gray level) citra sebagai sampel yang akan diuji 7
dalam penelitian. Metode area based matching digunakan dalam penelitian ini karena merupakan metode yang paling mudah dilakukan dan memberikan hasil pencocokan yang relatif cepat (Ilham, 2007). Metode ini juga memiliki akurasi yang cukup tinggi untuk area yang memiliki tekstur baik dan unik, dan pada beberapa kasus tingkat akurasi dari kecocokan dapat dinyatakan kuantitasnya dalam unit metrik. Area based matching pada dasarnya membandingkan nilai derajat keabu-abuan (gray level) suatu bentuk kecil matriks citra dimana pusat matriksnya merupakan lokasi gray value dari titik yang akan dicocokan. Proses pengidentifikasian titik sekawan dilakukan dengan cara memilih titik di citra kiri pada objek yang mudah dikenal. Titik yang dipilih tersebut dibandingkan dengan titik citra di kanan pada objek yang sama di citra kiri. Pusat sub-citra tersebut merupakan lokasi nilai keabuabuan dari titik yang akan dicocokkan. Sampel titik diambil dari citra pada sistem koordinat lokal dalam bentuk posisi kolom-baris. Pada pencocokan citra berbasis area, setiap titik yang akan dicocokan adalah pusat dari sebuah jendela pixel yang kecil pada citra acuan, dan jendela ini dibandingkan dengan jendela yang lain pada citra pencarian dengan ukuran tertentu. Ukuran kecocokan dilihat dengan kecilnya perbedaan nilai yang dihasilkan. Keunikan objek merupakan penentu keberhasilan pencocokan citra. Salah satu penentu keunikan objek adalah ukuran sub citra acuan (SCA). Semakin besar ukuran sub citra acuan, detail yang merupakan bagian dari objek semakin banyak. Ketika ukuran citra acuan diperbesar dapat dilihat adanya keunikan lain dari area yang dikategorikan mewakili jenis objek. Keunikan tersebut dapat berupa objek yang berbeda dan memiliki nilai kecerahan yang berbeda pula. Berdasarkan hal tersebut, rentang nilai kecerahan citra acuan akan melebar sehingga nampak semakin heterogen (Putra, 2008). Proses pencocokan citra diasumsikan berhasil jika diperoleh nilai korelasi ≥ 0.7 (Wolf, et al., 2000). Dengan memperbesar ukuran sub citra acuan, akan diperoleh karakteristik objek yang makin unik sehingga nilai korelasi akan meningkat dan mendukung tercapainya keberhasilan pencocokan citra. Dengan adanya keunikan tersebut, pencarian area paling berkorelasi dapat lebih mudah dan terhindar dari kesalahan posisi pusat area yang paling berkorelasi. Keunikan yang dimaksud dapat objek tersebut memiliki sebagian area heterogen. Secara umum, makin besar ukuran citra acuan, makin banyak keunikan objek yang terlihat sehingga makin besar pula rentang nilai kecerahan citra acuannya.
8
Teknik mengevaluasi pencocokan citra berbasis area adalah dengan menggunakan teknik korelasi maksimal. Nilai korelasi yang dihasilkan bertujuan untuk mengukur derajat kesamaan antara dua atau lebih citra foto yang bertampalan. Citra pertama adalah sub citra acuan (SCA) pada citra kiri sedangkan sub citra kedua merupakan sub citra pencarian (SCP) yang dibatasi oleh citra pencarian (CP) di dalam citra foto kedua. Proses pencocokan citra berlangsung semi otomatis, posisi titik awal diambil secara manual untuk citra kiri dan citra kanan. Titik tengah SCA dan CP menjadi pusat dari area citra yang akan dicari. Nilai pergeseran maksimum SCA pada CP digunakan persamaan (1), nilai berguna dalam algoritma pencocokan citra tahap selanjutnya. Dm,n = CPm,n-SCAm,n+1
(1)
dengan m =baris dan n = kolom.
Sub-Citra Pencarian Citra Acuan
Citra Pencarian Gambar II-1. Sub Citra Acuan dan Sub Citra Pencarian Pencocokan SCA dengan CP menggunakan sistem koordinat lokal, untuk dapat mentransformasikan kembali menjadi sistem koordinat foto hasil pencocokan citra diperlukan nilai titik tengah yang didapat saat menentukan posisi awal. Titik tengah SCA dan SCP dapat ditentukan dengan persamaan (2), untuk dapat mentransformasikan kembali dari koordinat lokal menjadi koordinat foto maka dilibatkan titik tengah nilai awal seperti persamaan (3). Nilai koordinat foto akan didapatkan dengan menjumlahkan titik lokal dengan pergeseran lokal seperti pada persamaan (4).
f plk =
U SCA − 1 2
(2)
9
⎛ U + 1⎞ f PCR = (bar , kol )awal − ⎜ CP ⎟ ⎝ 2 ⎠
(3)
x' , y ' = x, y + f plk + f pcpr
(4)
dengan usca dan ucp adalah ukuran besar SCA dan CP, x,y adalah nilai koordinal lokal titik tengah pada CP dan x’,y’ adalah nilai koordinat citra pada sistem koordinat foto. Foto
Citra Pencarian Sub Citra Acuan
Gambar II-2. Hubungan Citra Foto, SCA dan CP Sub Citra Pencarian akan bergerak dalam citra pencarian, kemudian dihitung nilai korelasi SCA dan semua SCP pada CAP dan nilai korelasi antar kedua citra mempunyai rentang nilai 0 sampai +1 (0 ≤ ρ ≤ 1). Secara umum nilai pembatas dari nilai koefisien korelasi adalah lebih besar sama dengan 0.7 atau 70 % yang dinyatakan cocok atau derajat kesamaannya tinggi. Sampel citra berupa komposisi nilai keabuan array citra yang akan diuji derajat kecocokannya dihitung melalui suatu persamaan matematis untuk kemudian disimpan sebagai nilai korelasi seperti persamaan (5). Metode korelasi dari pencocokan citra berkerja dengan memilih CA dari citra kiri berdasarkan karakteristik tertentu dan jarak objek/area dari titik utama citra untuk dicocokan, dan pencarian posisi yang sekawan akan dilakukan oleh jendela yang bergerak (SCP) pada CP dari citra kanan.
ρ=
σg g = σ g .σ g 1 2
1
2
_ _ ⎛ ⎞⎛ ⎞ g − g g − g . ⎜ ⎟ ⎜ ∑ ⎝ 1ij 1 ⎠ ⎝ 2ij 2 ⎟⎠ 2
_ _ ⎛ ⎞ ⎛ ⎞ g − g g − g . ⎜ ⎟ ⎜ ∑ ⎝ 1ij 1 ⎠ ∑ ⎝ 2ij 2 ⎟⎠
dengan: 10
2
(5)
ρ
= koefisien korelasi
σg1g2
= kovariansi nilai keabuan CA dan SCP
σg1
= standar deviasi untuk CA
σg2
= standar deviasi untuk CP
g1ij,g2ij = nilai keabuan pada kolom ke-i dan baris ke-j pada CA dan SCP ĝ1,ĝ2
= nilai rata-rata pada CA dan SCP
Metode korelasi nilai rata-rata kanal yang diberi bobot adalah metode hitungan korelasi yang menggunakan tiga kanal warna dengan menggunakan komponen bobot dalam menghitung nilai korelasi. Metode ini merupakan pengembangan dari metoda korelasi nilai rata-rata kanal terpisah dengan melibatkan unsur bobot masing-masing kanal merah, hijau dan biru dalam menentukan nilai korelasi citra sebagai upaya memperhitungkan dominasi warna pada citra dan sensitivitas sensor masing-masing kanal (Ilham, 2007). Pembobotan ini diperlukan karena sensitivitas masing-masing kanal terhadap cahaya yang diterima oleh sensor dianggap sama. Cahaya yang diterima oleh sensor foto memiliki sensitivitas yang berbeda tergantung dominasi unsur warna pada ketiga kanal tersebut. Sehingga dalam teknik korelasi nilai rata-rata kanal yang diberi bobot dilibatkan pembobotan dengan memperhitungkan dominasi warna pada citra tersebut. k
ρ total =
∑w
ch
ch =1
.ρ ch (6)
k
∑w
ch =1
ch
dengan: ρch = koefisien korelasi kanal wch = bobot pada CA dengan menggunakan standar deviasi masing-masing kanal (σch) _ ⎛ ch ch ⎞ ⎟⎟ ⎜ g g − ∑∑ ij ⎜ i j ⎝ ⎠ (m.n) − 1 m
wch =
n
2
(7)
dengan m, n = jumlah kolom, jumlah baris
11
II.2
Transformasi Domain Citra Transformasi wavelet merupakan hasil pengembangan transformasi fourier yang
merupakan metode tradisional untuk menentukan kandungan frekuensi dari sebuah sinyal. Transformasi fourier pada dasarnya membawa sinyal dari domain spasial (spatial-domain) ke domain frekuensi (frequency-domain). Transformasi fourier adalah alat mengubah sinyal menjadi fungsi sinus dan cosinus dengan beragam frekuensi. Transformasi fourier menggunakan basis sinus dan kosinus yang memiliki frekuensi berbeda. Hasil transformasi fourier adalah distribusi densitas spektral yang mencirikan amplitudo dan fase dari beragam frekuensi yang menyusun sinyal. Hal ini merupakan salah satu kegunaan transformasi fourier, yaitu untuk mengetahui kandungan frekuensi sinyal (Munir, 2004). Transformasi fourier umum digunakan dalam pengolahan sinyal untuk merepresentasikan sinyal dalam domain frekuensi murni. Keterbatasan dari transformasi fourier konvensional adalah tidak adanya informasi waktu dari kemunculan suatu frekuensi. Informasi waktu tersembunyi dan tidak terakses dalam domain frekuensi murni, akibatnya transformasi fourier tidak cocok diterapkan pada sinyal yang frekuensinya bervariasi terhadap waktu. Permasalahan tersebut diatasi dengan menggunakan transformasi fourier jangka pendek (STFT, short-time fourier transform). Hasil yang diperoleh adalah suatu deret analisis spektral yang berkorespondensi dengan suatu posisi dalam waktu, namun metode ini memiliki kelemahan sebagai akibat dari penggunaan fungsi jendela dengan lebar yang sama untuk tiap komponen spektral. STFT memberikan resolusi waktu dan frekuensi yang buruk pada komponen frekuensi tinggi (durasi rendah). Komponen berdurasi pendek merupakan hasil rata-rata sesuai lebar jendela. Selain itu, komponen yang durasinya lebih besar dari lebar jendela tidak dianalisis (Misiti, et al., 2004). Transformasi wavelet merupakan pengembangan dari STFT. Pada STFT pengamatan antar komponen spektral dilakukan dengan mengubah jumlah osilasi di dalam fungsi jendela. Sedangkan pada transformasi wavelet pengamatan komponen spektral dilakukan dengan mengubah lebar jendela dengan tetap mempertahankan jumlah osilasi di dalamnya. Hal inilah yang menyebabkan istilah frekuensi tidak lagi dipakai dalam analisis wavelet, namun terdapat istilah “skala” yang berkorespondensi dengan frekuensi. Keunggulan transformasi wavelet, sifat
12
natural sinyal dipertahankan. Pada komponen berdurasi pendek, fungsi jendela yang digunakan memiliki lebar yang sempit. Sedangkan komponen yang berdurasi lebih panjang, fungsi jendela diperlebar.
Waktu
Amplitudo
Skala
Frekuensi
Domain
Frekuensi
Amplitudo
Transformasi
Wavelet
STFT
Fourier
Waktu
Waktu
Gambar II-3. Teknik Penjendelaan Frekuensi Dari Metode Transformasi Domain II.2.1 Sinyal dan Spektrum Sinyal adalah deskripsi bagaimana satu parameter merubah parameter lainnya. Parameter tersebut merupakan sekumpulan informasi yang ditimbulkan oleh suatu fenomena dan bisa diperlakukan sebagai data. Sinyal dipresentasikan dalam bentuk grafik gelombang yang menggambarkan suatu siklus pergerakan. Siklus sinyal terdapat komponen yang membentuk gelombang yaitu amplitudo, sudut fase, periode, waktu dan frekuensi. Amplitudo merupakan besar perpindahan maksimum dari titik kesetimbangan dan bernilai selalu positif. Sudut fase memberitahu pada titik apa dalam siklus, gerak berada pada t=0. Sedangkan frekuensi adalah banyaknya siklus pada satu satuan waktu.
x(n)=A.cos(ωn+θ) A= Amplitudo ω = frekuensi (radian/sampel) f = frekuensi (siklus/sampel) θ = fase (radian)
Gambar II-4. Grafik Gelombang Perioda yaitu komponen gelombang yang merepresentasikan waktu dalam satuan detik pada suatu siklus. Perioda merupakan kebalikan dari frekuensi yang merupakan jumlah siklus pada suatu waktu. Komponen frekuensi yang terkandung pada suatu sinyal dapat dibagi menjadi
13
dua, yaitu komponen frekuensi tinggi dan komponen frekuensi rendah. Frekuensi tinggi memiliki periode yang lebih pendek didandingkan dengan frekuensi rendah. transformasi fourier
Frekuensi hasil transformasi fourier
Sinyal orisinal
Gambar II-5. Frekuensi Hasil Transformasi Fourier II.2.2 Transformasi Wavelet Wavelet adalah fungsi matematika yang menguraikan data atau fungsi menjadi komponen-komponen frekuensi yang berbeda, wavelet memiliki keunggulan dari fourier dalam menganalisis situasi-situasi fisis dimana sebuah sinyal memiliki diskontinuitas dan bentuk yang tajam. Transformasi wavelet merujuk pada aproksimasi sinyal menggunakan suatu gelombang singkat yang mengalami translasi dan dilatasi untuk keperluan analisis frekuensi-temporal sinyal. Analisis temporal menggunakan variasi lokasi gelombang singkat pada waktu tertentu dalam durasi sinyal, sedangkan analisis frekuensi menggunakan variasi dilatasi gelombang singkat yang sama (Misiti, et al., 2004). Formulasi matematika representasi sinyal disebut sebagai transformasi wavelet. Proses transformasi domain citra bertujuan untuk memunculkan unsur atau karakteristik citra tertentu dapat lebih ditonjolkan. Wavelet didefinisikan sebagai gelombang singkat (atau gelombang kejut) dengan energi terkonsentrasi pada domain fisik (spasial atau waktu). Berbeda dengan gelombang pada umumnya (sinusoid) yang memiliki sifat halus, terprediksi, dan durasi tak terbatas, wavelet dapat berbentuk tidak simetris, irregular, dan memiliki durasi terbatas atau berosilasi menuju nol dengan cepat. Induk wavelet induk didefinisikan sebagai fungsi basis yang digunakan sebagai dasar dalam menurunkan fungsi-fungsi lain untuk analisis lokasi dan frekuensi tertentu. Dari suatu induk wavelet, diturunkan fungsi wavelet lain (wavelet turunan) yang merupakan fungsi wavelet induk yang mengalami transalasi dan dilatasi. Hubungan antara induk wavelet dan wavelet turunan satu dimensi diberikan dalam persamaan (8) dan hubungan antara induk wavelet dan wavelet turunan dua dimensi diberikan dalam persamaan (9):
14
1 a
⎛ x −b⎞ ⎟ ⎝ a ⎠
ψ⎜
(8)
⎛ x q − b1 x 2 − b2 Ψ ⎜⎜ ' a2 a1 a 2 ⎝ a1 1
⎞ ⎟' x = ( x1 , x 2 ) ∈ R 2 ⎟ ⎠
(9)
dengan ψˆ adalah fungsi wavelet dalam domain frekuensi, ω adalah indeks frekuensi, a dan b merupakan parameter skala (dilatasi) dan pergeseran (translasi) yang berkorespondensi dengan selektifitas frekuensi dan posisi wavelet turunan dalam domain fisik (x). Semua fungsi wavelet turunan ternormalisasi agar memiliki normal energi ψ a ,b
2
= 1 pada skala (a) dan translasi (b)
berapapun.
Haar (DB-1)
DB-2
DB-3
DB-4
DB5
Gambar II-6. Induk Wavelet Skala dalam tranformasi wavelet adalah melakukan perenggangan dan pemampatan pada sinyal. Efek dari skala yang dinotasikan (a) dapat dilihat pada gambar II-5, semakin kecil faktor skala akan menghasilkan induk wavelet yang semakin mampat.
Gambar II-7. Faktor Skala Wavelet
15
Pergeseran wavelet yang dinotasikan (b) adalah menggeser induk wavelet mendekati sinyal sebenarnya sehingga memiliki posisi yang sama dengan sinyal sebenarnya. Secara umum prosedur transformasi wavelet adalah mengambil induk wavelet yang mendekati bentuk sinyal asli, lalu menghitung nilai konstanta pendekatan (C) yang memperlihatkan seberapa mirip induk wavelet dengan sinyal asli. Induk wavelet dilakukan translasi dan dilatasi sehingga dapat mewakili keseluruhan sinyal. Konstanta pendekatan (C) yang berkorespondensi dengan skala dan pergeseran wavelet turunan diberikan pada persamaan (10).
C ( a, b ) = f ( x ) ,ψ *a ,b ( x ) = ∫
+∞
−∞
f ( x )ψ *a ,b ( x ) dx
(10)
dengan ψ * merupakan dan konjugasi kompleks dari ψ . Transformasi wavelet kontinu sinyal untuk suatu baris skala dapat diintepretasikan sebagai konvolusi antara fungsi f dengan keluarga wavelet turunan ψ a ,b pada skala tersebut.
Sinyal Wavelet
Translasi
Skala
Gambar II-8. Proses Transformasi Wavelet Perenggangan yang lebih lebar pada skala induk wavelet menghasilkan sinyal yang lebih panjang untuk dibandingkan sehingga semakin kasar sinyal yang terukur oleh koefisien wavelet. Hubungan antara skala dan frekuensi menunjukkan untuk mendapatkan frekuensi tinggi digunakan skala kecil sehingga dapat menghasilkan sinyal yang lebih padat dan pergantian detil yang cepat. Sebaliknya untuk mendapatkan frekuensi rendah digunakan skala besar sehingga mendapatkan wavelet yang lebih renggang, detil lambat dan kasar. Sinyal Wavelet Skala Kecil
Skala Besar
Gambar II-9. Hubungan Antara Skala dan Frekuensi 16
Proses transformasi wavelet dua dimensi menguraikan citra awal menjadi sebuah citra rata-rata (frekuensi rendah) dan tiga buah citra detail (frekuensi tinggi). Algoritma priramida digunakan melakukan penguraian pada bagian citra frekuensi rendah untuk tahap-tahap selanjutnya. Frekuensi rendah diasumsikan sebagai sinyal sebenarnya dan frekuensi tinggi diasumsikan sebagai derau, sehingga harus terdapat penguraian frekuensi tinggi dan frekuensi rendah pada transformasi wavelet. Penguraian frekuensi memiliki kelemahan yaitu mengurangi data sampel sehingga dapat mengurangi detil yang ada pada sinyal. Downsampling
Frekuensi Tinggi
Downsampling
Frekuensi Rendah
Gambar II-10. Pemisahan Frekuensi Rendah dan Frekuensi Tinggi Proses dekomposisi dapat dilakukan iterasi sehingga sinyal dapat diturunkan menjadi banyak komponen resolusi rendah, kegiatan ini dinamakan multi level dekomposisi. Penurunan sinyal menjadi beberapa turunan sinyal agar mendapatkan sinyal frekuensi rendah yang terbebas derau dan diasumsikan derau sama dengan frekuensi tinggi. Proses dekomposisi level hanya dapat dilakukan hingga mencapai unit terkecil dari sinyal yang dalam kajian ini adalah pixel pada citra. Sehingga harus direncanakan saat melakukan dekomposisi agar tidak menghilangkan informasi dari sinyal atau citra.
Gambar II-11. Multi Level Dekomposisi Wavelet Satu Dimensi 17
Proses dekom mposisi padda transform masi wavelett dua dimennsi menguraikan citra awal ( reendah) dan tiga buah citra c detail (frekuensi ( tinggi) menjadi sebuah citraa rata-rata (frekuensi dengan arah a horizon ntal, vertikaal dan diagoonal. Setiap melakukan dekomposisi level, ressolusi spasial citra c berkuraang menjadii 25% resoluusi citra aslli karena proses downsaampling meenjadi empat baagian frekueensi. Untuk proses dekkomposisi seelanjutnya yang y diturunnkan adalah citra hasil aproksimasi freekuensi renddah. Pada traansformasi wavelet w dua dimensi, cittra dipisah dalam d urutan-urrutan satu diimensi. Urutan horizonttal dibentuk dengan menngambil barris atas (perttama) hingga baris b terakhir citra. Urutan vertikal dibentuk dengan d menggambil kolom m kiri (perttama) hingga kolom k terakh hir citra. Uruutan ini akann ditransform masi oleh wavelet w dengan menggunnakan koefisienn pendekatan n wavelet (C) (Ratnadew wi, 1999). G Gambar II-12 2 menjelaskkan pembaggian citra haasil dekompposisi wavellet. Citra teerurai menjadi sebuah citraa rata-rata yaitu y frekuennsi rendah vertikal v dan frekuensi rendah r horizzontal (RR) serrta tiga buah h citra detaill yaitu frekuuensi rendahh horizontal dan frekuennsi tinggi vertikal (RT), freekuensi rendaah vertikal dan d frekuenssi tinggi horiizontal (TR) dan frekuennsi tinggi vertikal dan frekuuensi tinggi horizontal (TT). Citra yang dikoreelasikan padda penelitiann ini adalah citra rata-rata (RR) dengaan mengasum msikan bahw wa citra rataa-rata tersebuut sudah terrbebas dari derau d (noise).
Gam mbar II-12. Multi M Level Dekomposiisi Wavelet Dua D Dimenssi
18
