3HUEDQGLQJDQ2SHUDVL'LUHFW&RUUHODWLRQGDQ)DVW)RXULHU7UDQVIRUPSDGD 5HJLVWUDVL&LWUDXQWXN3HQJRODKDQ$ZDO2UWKRUHNWLILNDVL'DWD 6\QWKHWLF $SHUWXUH5DGDU 6$5 .DWPRNR$UL6DPERGR0XV\DURIDK %LGDQJ7HNQRORJL$NXVLVLGDQ6WDVLXQ%XPL3HQJLQGHUDDQ-DXK/HPEDJD3HQHUEDQJDQGDQ$QWDULNVD 1DVLRQDO-O/$3$11R3HND\RQ3DVDU5HER-DNDUWD7LPXU,QGRQHVLD7HOS)D[ (PDLO NDWPRNRBDUL#\DKRRFRPRIDB#\DKRRFRP
Abstrak. Telah dikaji dan dianalisis operasi direct correlation dan Fast Fourier Transform (FFT) pada registrasi citra untuk pengolahan awal orthorektifikasi data Synthetic Aperture Radar (SAR). Pengolahan awal orthorektifikasi data SAR meliputi pembacaan data input, pembentukan citra simulasi SAR dari data Digital Elevation Model (DEM) berdasarkan model pencitraan radar (imaging radar model), registrasi citra (image to image registration) antara citra SAR original dengan citra simulasi yang telah disamakan dengan koordinat citra SAR original dan rekostruksi citra dari masingmasing citra SAR original ke posisi yang baru dalam sistem proyeksi peta yang telah ditentukan. Tahapan registrasi citra meliputi pencarian nilai pergeseran (offset) kedua citra secara global, pencarian beberapa titik ikat (tie point) dan pemilihan titik-titik ikat yang memenuhi syarat (berkualitas baik) dan penyusunan persamaan polynomial berdasarkan titik-titik ikat yang telah dipilih. Pencarian nilai pergeseran bisa dilakukan dengan operasi direct correlation dan FFT. Penulisan paper ini dimaksudkan untuk mengkaji dan menganalisis operasi direct correlation dan FFT pada registrasi citra dengan cara membandingkan kedua operasi tersebut. Perbandingan dilakukan secara eksperimental yang dilakukan melalui ujicoba pada software pengolahan data yang dilengkapi dengan script-script tambahan. Data yang digunakan adalah data SAR (ALOS-PALSAR) dan data DEM (SRTM). Berdasarkan analisis yang dilakukan dapat dikatakan bahwa operasi FFT lebih berpotensi dan mampu memberikan hasil efisiensi komputasi yang lebih tinggi untuk ukuran citra yang lebih besar. Katakunci: direct correlation, FFT, registrasi citra, SAR, ALOS-PALSAR 3(1'$+8/8$1
Data penginderaan jauh SAR telah banyak digunakan untuk observasi bumi dalam berbagai aplikasi pemanfaatan seperti pemantauan vegetasi, pemantauan tanah, pemantauan geologi dan geomorfologi, pemantauan danau dan lautan, pengelolaan perairan, pemetaan dan lain-lain. Kelebihan utama sensor SAR antara lain dapat menembus awan, dapat mengakuisisi data pada berbagai kondisi cuaca, dapat menghasilkan tampilan sinoptik (synoptic view) pada wilayah yang luas, cakupannya dapat diperoleh dengan cepat pada waktu tertentu, dan memungkinkan look angle yang sangat dangkal (shallow) sehingga menghasilkan perspektif yang berbeda dibandingkan fotografi vertikal pada umumnya (Leberl 1990). Meskipun sistem akuisisi data penginderaan jauh dengan sensor SAR memiliki banyak kelebihan, namun secara operasional, pemanfaatan data SAR masih menemui banyak kendala dibandingkan dengan data penginderaan jauh sistem optik, terutama dalam permasalahan geometri. Permasalahan geometri yang timbul pada citra SAR disebabkan oleh sistem pengakuisisian sensor SAR yang bersifat menyamping, seperti terlihat pada Gambar 1. Akibatnya, pada citra SAR terjadi distorsi geometrik citra seperti foreshortening, layover dan shadow pada objek dengan ketinggian atau tingkat
3DSHU&ROOHFWLRQ̽*HR6$51DV
kecuraman yang tajam (Leberl 1990; Woodhouse 2006; Curlander and McDonough 1991). Flight direction
th eng
n RA
L na ten
SA
Real Radar Antenna
q
g Look Angle
Depression Angle
Backscattered energy Transmitted energy
Incidence Angle
an
n
Alo
tion
Near Range
e
c
a g tr
irec
g an tR
)d
uth
zim k (a
Sl
f Nadir
Beamwidth Far Range
Swath
Ground Range Directio n
Gambar 1. Geometri Pencitraan Penginderaan Jauh Sistem SAR(Woodhouse 2006).
Untuk memperoleh citra SAR dengan ketelitian geometrik yang tinggi, diperlukan upaya untuk meminimalkan/mengeliminasi distorsi tersebut. Proses minimalisasi distorsi geometrik pada data SAR disebut sebagai pemrosesan awal (preprocessing) data SAR, yang sering juga disebut dengan proses ortho-rektifikasi. Dengan proses tersebut, diharapkan ketelitian geometrik data SAR dapat meningkat, sehingga lebih berkualitas dan dapat memenuhi standar untuk digunakan dalam berbagai aplikasi pemanfaatan selanjutnya. Secara umum terdapat dua metode utama untuk melakukan proses ortho-rektifikasi data SAR (Woodhouse 2006; Curlander and McDonough 1991), yaitu metode rektifikasi dengan menggunakan ground control point (GCP) yang dilanjutkan dengan polynomial warping (proses penyusunan ulang citra berdasarkan persamaan polinomial) dan metode “Dead Reckoning”, yang intinya merupakan metode rektifikasi citra SAR Slant Range Image (SLR) dengan cara menghilangkan distorsi geometrik yang telah diprediksi sebelumnya berdasarkan parameter-parameter radar, termasuk parameter yang terkait dengan jalur penerbangan wahana yang membawa sensor tersebut dan data Digital Elevation Model (DEM). Dibandingkan dengan metode pertama, metode kedua lebih dapat diterapkan pada data SAR dengan variasi topografik yang tinggi, termasuk distorsi terlokalisasi pada area yang sempit. Secara garis besar proses rektifikasi metode Dead Reckoning meliputi: 1) pembacaan data input SAR dan data DEM; 2) pembentukan citra simulasi SAR dari data DEM dan transformasi ke koordinat SAR; 3) registrasi citra SAR dan citra simulasi SAR; 4) rekonstruksi citra dari masing-masing piksel dalam citra SAR original ke posisinya yang baru dalam sistem proyeksi peta yang telah ditentukan (Woodhouse 2006; Curlander and McDonough 1991). Tahapan registrasi citra meliputi pencarian nilai pergeseran (offset) kedua citra secara global, pencarian beberapa titik ikat (tie point) dan pemilihan titik-titik ikat yang memenuhi syarat (berkualitas baik) dan penyusunan persamaan polynomial berdasarkan titik-titik ikat yang telah dipilih. Pencarian nilai pergeseran (offset) kedua citra dilakukan dengan cara mencari nilai korelasi yang maksimum.
3DSHU&ROOHFWLRQ̽*HR6$51DV
Perhitungan nilai korelasi antara dua citra dapat dilakukan dengan operasi korelasi langsung (direct correlation) ataupun Fast Fourier Transform (FFT). 7,1-$8$13867$.$
Korelasi didefinisikan dengan persamaan di bawah ini.
dimana h menyatakan conjugate kompleks dari variabel kompleks h. Korelasi juga mempunyai interpretasi geometrik pada sliding inner product. Biasanya, pada korelasi, dua sinyal pada sisi tangan kanan (right-hand side) dibandingkan, dan t merupakan variabel delay waktu. Tidak seperti konvolusi, korelasi tidak komutatif, tetapi Direct Correlation Operasi korelasi langsung (direct correlation operation) dilakukan untuk mencari persamaan/hubungan yang sama pada piksel-piksel antara dua citra secara langsung, nilai koefisien korelasi dihitung satu per satu pada tiap piksel. Dua citra dinyatakan terkorelasi jika nilai koefisien korelasinya sama dengan satu. Koefisien korelasi, r, merupakan nilai skalar pada interval (-1,0 hingga 1,0) dan didefinisikan sebagai perbandingan kovarians populasi sampel terhadap hasil deviasi standarnya. Berikut rumus untuk perhitungan nilai koefisien korelasi (r):
Koefisien korelasi merupakan pengukuran secara langsung seberapa bagus variasi gabungan dua populasi sampel. Nilai r = +1 atau r = -1 mengindikasikan kesesuaian yang sempurna terhadap model linier positif atau negatif. Nilai r yang mendekati +1 atau -1 menunjukkan tingkat korelasi yang tinggi dan kesesuaian yang baik terhadap model linier. Nilai r yang mendekati 0 menunjukkan kesesuaian yang tidak baik terhadap model linier. Fast Fourier Transform Fast Fourier Transform (FFT) adalah transformasi Fourier diskret yang dikomputasikan secara efisien. Transformasi Fourier diskret (DFT), F(u), dari fungsi satu dimensi f(x) dengan elemen sejumlah N, didefinisikan sebagai:
Dan transformasi kebalikannya ny (invers), (i s), didefinisikan sebagai: ag
3DSHU&ROOHFWLRQ̽*HR6$51DV
Teknik perhitungan korelasi dengan FFT dilakukan dengan memanfaatkan representasi suatu citra dalam domain frekuensi. Cross-power spectrum dari kedua citra dihitung dan selanjutnya dicari lokasi dimana invers-nya mencapai maksimum (Canty 2006; Barbara and Flusser 2003). *
Á(s )Á(o )
*
Á(s )Á(o ) dimana,
= e 2pi ( mx0 +ny0 )
Á(s ) dan Á(o ) masing-masing menyatakan transform Fourier untuk citra *
simulasi dan citra SAR original. Á(o ) menyatakan konjugasi kompleks dari
Á(o ) . Nilai
x0 dan y0 merupakan nilai offset yang dicari. 2
Metode korelasi langsung melakukan operasi kira-kira sebanyak n operasi, dimana n adalah jumlah titik pada transformasi, sedangkan FFT (yang mengkorelasikan hal yang sama dengan metode korelasi langsung) melakukan operasi kira-kira sejumlah nlogn operasi (Sambodo et al. 2011). 78-8$1
Penulisan paper ini dimaksudkan untuk mengkaji dan menganalisis operasi korelasi langsung (direct correlation) dan FFT pada registrasi citra dengan cara membandingkan kedua operasi tersebut. 0(72'2/2*,
Analisis dalam paper ini dilakukan dengan cara membandingkan hasil operasi direct correlation dan FFT pada proses registrasi citra. Parameter yang dibandingkan adalah waktu komputasi terhadap jumlah titik/piksel pada citra yang diregistrasi. Registrasi citra (image to image registration) antara citra Slant Range Image (SLR) SAR dengan citra simulasi yang telah disamakan koordinatnya dengan citra SAR, dilakukan dengan sub-tahapan sebagai berikut: Pertama-tama dilakukan pencarian nilai pergesaran (offset) kedua citra tersebut secara global, yakni dengan cara mencari nilai korelasi yang maksimum. Nilai korelasi dicari dengan menggunakan teknik penghitungan korelasi langsung (direct correlation) dan teknik perhitungan korelasi berdasarkan transformasi Fourier (FFT: Fast Fourier Transform). Pencarian beberapa titik-titik ikat (tie-point) dilakukan dalam blok-blok berukuran tertentu yang lebih kecil dari ukuran total citranya dan menyebar di seluruh wilayah citranya. Nilai pergeseran dari masing-masing blok tersebut dihitung menggunakan kedua teknik tersebut. Dari hasil perhitungan dengan kedua teknik tersebut, dianalisis perbandingannya dan disimpulkan teknik mana yang lebih efisien komputasinya. Perhitungan nilai korelasi dilakukan dengan ujicoba eksperimental menggunakan fungsi pada program Interactive Data Language (IDL) yang dilengkapi dengan script tambahan. Data yang digunakan adalah data SAR (ALOS-PALSAR) dan data DEM (SRTM). +$6,/'$13(0%$+$6$1
Proses registrasi citra antara citra SLR SAR dengan citra simulasi merupakan proses penyelarasan kedua citra (image matching). Secara intuitif, registrasi citra menyelaraskan sebagian atau keseluruhan citra antara dua citra atu lebih yang mempunyai scene yang sama. Dua citra yang sesuai (match) digunakan untuk
3DSHU&ROOHFWLRQ̽*HR6$51DV
mengekstrak perubahan temporal pada scene, untuk mencari perbedaan kenampakan scene pada kondisi pencitraan yang berbeda, untuk mendeteksi paralaks, untuk menggabungkan (mosaic) citra atau untuk membuat set data multidimensi untuk analisis otomatis. Banyaknya peran yang bergantung pada registrasi yang presisi membuat registrasi citra menjadi masalah yang sangat signifikan pada pengolahan citra dan analisis multi citra SLR. Metode image matching yang paling umum adalah korelasi area (area correlation), dimana window citra yang ditemukan menyerupai satu sama lain pada dua citra diselaraskan (di-match-kan). Metode korelasi area dapat dilakukan dengan menggunakan teknik korelasi langsung dan teknik korelasi berdasarkan FFT. Metode matching mengacu pada penggunaan koefisien korelasi sebagai ukuran kesamaan untuk area yang diuji antara pasangan citra. Pada gambar 2 ditampilkan konsep korelasi citra untuk identifikasi titik-titik yang sesuai (match).
Gambar 2. Konsep Korelasi Citra untuk Identifikasi Titik-Titik yang Sesuai (Match)(Leberl 1990).
Pada gambar 2, anggap W mewakili subcitra dari citra 1, dan S mewakili subcitra dari citra 2, sehingga bagian scene yang dicitrakan pada W keseluruhannya terkandung pada S. Ukuran dan lokasi area yang dicari dipilih berdasarkan informasi geometri pencitraan sebelumnya. Untuk mencari nilai koefisien korelasi antara S dan W, window W digeser dengan ukuran pergeseran tertentu sehingga seluruh window S tercakup oleh pergeseran window W. Satu per satu titik/piksel pada window W dan S dicari nilai koefisien korelasinya. Berdasarkan uji eksperimental yang dilakukan, diperoleh grafik perbandingan waktu (t) terhadap jumlah titik/piksel (n) yang dicari nilai koefisien korelasinya. Ujicoba eksperimental dilakukan dengan menggunakan fungsi pada program IDL dan melengkapinya dengan script tambahan yang diperlukan. Pada gambar 3, ditampilkan grafik perbandingan waktu terhadap jumlah piksel pada perhitungan nilai koefisien korelasi dengan teknik korelasi langsung.
3DSHU&ROOHFWLRQ̽*HR6$51DV
Gambar 3. Grafik Perbandingan Waktu (t) terhadap Jumlah Piksel (n) pada Perhitungan Nilai Koefisien Korelasi dengan Teknik Korelasi Langsung
Pada ujicoba eksperimental, ukuran pergeseran maksimum pada citra yang dicoba diubah-ubah untuk mencari nilai pergeseran maksimum yang paling efektif. Nilai pergeserannya berkisar dari 2 hingga 1024. Jumlah titik/piksel pada citra yang dicari n nilai koefisien korelasinya harus dalam orde 2 . Pada grafik di gambar 3, t menyatakan waktu yang diperlukan untuk komputasi (sekon) dan n menyatakan pangkat dari jumlah n titik yang dikorelasikan (2 ). Dari grafik pada gambar 3, terlihat bahwa semakin besar jumlah titik/piksel yang dicari nilai koefisien korelasinya, waktu komputasinya meningkat. Dengan demikian, semakin banyak jumlah piksel yang diujicoba, waktu yang diperlukan untuk komputasi perhitungan nilai koefisien korelasi menjadi semakin lama. Dari grafik pada gambar 3 juga terlihat, bahwa semakin besar nilai pergeseran maksimum, kemiringan grafiknya semakin tajam. Hal ini menunjukkan bahwa semakin besar pergeseran, waktu yang dibutuhkan juga semakin lama. Untuk jumlah piksel yang semakin banyak dengan pergeseran maksimum yang besar, perhitungan nilai koefisien korelasi tidak dapat dilakukan karena keterbatasan software dan komputer yang mengakibatkan error pada saat ujicoba eksperimental. Dengan demikian, perhitungan nilai koefisien korelasi dengan menggunakan teknik korelasi langsung (direct correlation) kurang efektif karena untuk jumlah piksel yang semakin banyak dan pergeseran yang semakin besar, teknik korelasi ini membutuhkan waktu yang lebih lama dan ada beberapa ujicoba yang gagal. Teknik perhitungan nilai koefisien korelasi yang berbasis FFT menggunakan teorema pergeseran Fourier (Champeney 1973). Selanjutnya, teknik yang menggunakan teorema ini disebut dengan korelasi fase (phase correlation). Penggunaan fase Fourier ini mengacu pada pemikiran bahwa citra mengandung lebih banyak informasi yang akurat dibandingkan frekuensi rendah yang mendominasi metric korelasi, yang menjadi basis untuk korelasi fase (Kuglin et al 1975; Kuglin et al. 1979; Pearson et al. 1977; DeCastro et al. 1987). Karena efek sampling dan ukuran citra yang terbatas, sidelobe terjadi pada puncak utama (main peak) permukaan korelasi. Sehingga, dalam prakteknya, teknik ini mengurangi korelasi dalam domain fase Fourier. Pada ujicoba eksperimental untuk perhitungan nilai koefisien korelasi, selain menggunakan teknik direct correlation, teknik berbasis FFT juga digunakan. Dari ujicoba yang dilakukan, diperoleh grafik yang sama, yaitu perbandingan waktu terhadap jumlah piksel. Pada gambar 4 ditampilkan, perbandingan grafik waktu (t) terhadap jumlah piksel/titik (n) pada perhitungan nilai koefisien korelasi dengan teknik korelasi langsung dan teknik berbasis FFT. 3DSHU&ROOHFWLRQ̽*HR6$51DV
Gambar 4. Perbandingan Grafik Waktu (t) terhadap Jumlah Piksel (n) pada Perhitungan Nilai Koefisien Korelasi dengan Teknik Korelasi Langsung dan Teknik Berbasis FFT.
Pada perhitungan nilai koefisien korelasi dengan teknik berbasis FFT, pergeseran maksimum tidak ditentukan karena secara otomatis teknik ini sudah melakukan pergeseran. Sehingga, teknik ini lebih praktis dalam operasi perhitungan nilai koefisien korelasinya. Jumlah piksel/titik yang dihitung nilai koefisien korelasinya juga harus n dalam orde 2 . Pada grafik di gambar 4, t juga menyatakan waktu yang diperlukan untuk komputasi (sekon) dan n menyatakan pangkat jumlah piksel/titik yang dicari nilai n koefisien korelasinya (2 ). Dari grafik pada gambar 4, terlihat bahwa pada teknik berbasis FFT grafiknya terlihat datar dan nilai t-nya terlihat konstan. Dengan demikian dapat dikatakan bahwa waktu yang dibutuhkan untuk perhitungan nilai koefisien korelasi dengan teknik berbasis FFT tidak bergantung pada jumlah piksel/titik yang diujicoba. Berapapun jumlah titik/piksel yang diujicoba, waktu yang dibutuhkan konstan. Dari grafik pada gambar 4, juga terlihat bahwa waktu yang dibutuhkan untuk perhitungan nilai koefisien korelasi dengan teknik berbasis FFT jauh lebih kecil jika dibandingkan dengan teknik korelasi langsung. Semakin besar jumlah piksel, pada teknik korelasi langsung membutuhkan waktu komputasi yang lebih lama. Sedangkan pada teknik berbasis FFT tidak berlaku seperti itu. Dengan demikian, dapat dikatakan bahwa teknik berbasis FFT lebih efisien dan praktis karena waktu yang dibutuhkan lebih sedikit dan proses perhitungan nilai koefisien korelasinya berlangsung lebih cepat. Pada ujicoba yang dilakukan, tidak terjadi error pada teknik berbasis FFT, sehingga tidak ada yang gagal pada ujicoba eksperimental tersebut. 2
Metode korelasi langsung melakukan operasi kira-kira sebanyak n operasi, dimana n adalah jumlah titik pada transformasi, sedangkan FFT (yang mengkorelasikan hal yang sama dengan metode korelasi langsung) melakukan operasi kira-kira sejumlah nlogn operasi. Dengan demikian, proses dengan teknik berbasis FFT lebih cepat dan waktu yang dibutuhkan lebih sedikit. .(6,038/$1
Pada perhitungan nilai koefisien korelasi dengan menggunakan teknik korelasi langsung (direct correlation), waktu komputasi yang dibutuhkan lebih banyak sehingga prosesnya berlangsung lebih lama. Semakin besar jumlah piksel/titik yang dicari nilai koefisien korelasinya, semakin besar waktu komputasi yang diperlukan. Teknik ini kurang efektif karena untuk jumlah piksel yang semakin banyak dan pergeseran yang 3DSHU&ROOHFWLRQ̽*HR6$51DV
semakin besar, teknik korelasi ini membutuhkan waktu yang lebih lama dan ada beberapa ujicoba yang gagal. Pada perhitungan nilai koefisien korelasi dengan menggunakan teknik berbasis FFT, waktu komputasi yang diperlukan lebih sedikit sehingga prosesnya berlangsung lebih cepat. Berapapun jumlah titik/piksel yang diujicoba, waktu yang dibutuhkan konstan. Teknik ini lebih efisien dan praktis karena waktu yang dibutuhkan lebih sedikit dan proses perhitungan nilai koefisien korelasinya berlangsung lebih cepat. '$)7$53867$.$ Leberl FW. 1990. Radargrammetic Image Processing. Artech House, Inc. Woodhouse IH. 2006. Introduction to Microwave Remote Sensing. Boca Raton: CRC Press Taylor & Francis. Curlander JC, McDonough RN. 1991. Synthetic Aperture Radar Systems and Signal Processing. John Wiley & Sons, Inc. Canty MJ. 2006. Image Analysis, Classification and Change Detection in Remote Sensing. Boca Raton: CRC Press Taylor & Francis. Barbara Z, Flusser J. 2003. Image Registration Methods: a Survey. Image Vision Computing 21(11), 977 – 1000. Sambodo KA, dkk. 2011. Laporan Kemajuan: Pengembangan Sistem Pengolahan Awal Data Satelit LAPAN A3 (Fokus Kegiatan: Pengembangan Sistem Pengolahan Awal Data Satelit SAR (Synthetic Aperture Radar)). Pusat Teknologi dan Data Penginderaan Jauh – LAPAN. Champeney DC. 1973. Fourier Transform and Their Physical Applications. Academic Press. Kuglin CD, et al. 1975. The Phase Correlation Image Alignment Method. Proceeding. IEEE Conference Cybernetics and Society. Kuglin CD, et al. 1979. Map Matching Techniques for Terminal Guidance Using Fourier Phase Information. Proceeding. SPIE, Digital Processing of Aerial Images, Vol. 186. Pearson JJ, et al. 1977. Video Rate Image Correlation Processor. Proceeding. SPIE, Applications of Digital Image Processing, Vol. 119. Decastro E., et al. 1987. Compensation of Random Eye Motion in Television Ophthalmoscopy: Preliminary Results. IEEE Transacrions on Medical Imaging 6(1).
3DSHU&ROOHFWLRQ̽*HR6$51DV
