2479-rully-is-final Sitia 2009 - 004

Studi Kinerja Varian Metode Komputasi Momen Legendre Dalam Rekonstruksi Citra Rully Soelaiman1), Mediana Aryuni2), Karlina K. Nisa3) Jurusan Teknik Informatika, Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember, Surabaya, 60111 1) Email : [email protected] ABSTRAK - Momen Legendre telah banyak digunakan pada aplikasi pengenalan pola, pengindeks-an citra, pengenalan wajah, dll karena kemampuannya sebagai deskriptor citra invariant. Namun komputasinya yang kompleks dengan error aproksimasi yang signifikan sering menjadi masalah dalam penggunaan momen Legendret. Pada makalah ini akan dibandingkan beberapa metode komputasi momen Legendre dalam aplikasi rekonstruksi citra dan merekomendasikan yang terbaik dengan error minimal dan waktu komputasi yang efisien. Proses komputasi dilakukan dengan mensampling citra input dan mengaproksimasi polinomial Legendre. Momen Legendre didapat dari perkalian polinomial Legendre dengan fungsi citra. Kemudian citra direkonstruksi dari polinomial Legendre dan momen Legendre yang terbentuk. Beberapa varian pengembangan dari proses komputasi ini antara lain Exact Legendre Moment (ELM), Speedy Legendre Moment (SLM), Exact Geometric Moment (EGM), Zeroth Order Approximation (ZOA), dan Simpson’s Rule (SR). Dari hasil rekonstruksi citra disimpulkan bahwa ELM merupakan metode terbaik untuk citra berwarna atau keabuan. Sedangkan untuk citra biner, SLM merupakan metode terbaik. Keakuratan hasil rekonstruksi dipengaruhi oleh ukuran block encoding dan orde maksimum polinomial. Semakin kecil ukuran block encoding, semakin akurat haslinya, tetapi waktu komputasinya lama. Orde polinomial yang tinggi juga menyebabkan waktu komputasi yang lama, tetapi hasil yang didapat akan lebih akurat. Kata kunci: momen Legendre, polinomial Legendre, rekonstruksi citra. 1.

Pendahuluan

Momen citra adalah proyeksi fungsi intensitas piksel citra ke dalam ruang polinomial. Diantara berbagai jenis momen citra, momen Legendre sering dipakai sebagai deskriptor citra invariant yang handal. Penggunaan momen Legendre dalam berbagai aplikasi seringkali terhambat oleh komputasinya yang kompleks dan error yang

signifikan. Komputasi momen Legendre merupakan proses yang rumit dengan kompleksitas cukup tinggi. Hal ini karena komputasi ini meliputi 2 proses, pertama adalah menghitung polinomial Legendre dari setiap piksel citra pada suatu orde, kedua yakni menghitung momen Legendre dari keseluruhan orde yang ada. Semua proses tersebut merupakan prosedur yang memakan waktu. Keakuratan hasil komputasi juga perlu diperhitungkan. Mengingat selama ini komputasi melibatkan proses aproksimasi integral yang memungkinkan ketidakakuratan. Pada penelitian ini akan dilakukan perbandingan dari beberapa metode komputasi momen Legendre, dalam suatu aplikasi rekonstruksi citra. Sistem yang dibuat merupakan perangkat lunak rekonstruksi citra yang mengimplementasikan kelima metode (ELM, EGM, ZOA, SR, SLM) dalam komputasi momen Legendre-nya. Permasalahan yang dihadapi dalam pembuatan sistem pengujian kninerja ini adalah : • Bagaimana mengaplikasikan momen Legendre yang merupakan momen kontinyu dalam ruang citra diskrit. • Bagaimana melakukan komputasi momen Legendre yang akurat dengan waktu komputasi yang cepat • Bagaimana menentukan metode terbaik untuk komputasi momen Legendre diantara 5 metode berikut : Exact Legendre Moment (ELM), Exact Geometric Moment (EGM), Zeroth Order Approximation (ZOA), Simpson’s Rule, dan Speedy Legendre Moment (SLM). 2.

Metode Komputasi Momen Legendre

Momen Legendre orde (m+n) didefinisikan oleh :

λmn =

(2m + 1)(2n + 1) 1 1 ∫−1 ∫−1 Pm ( x) Pn ( y) f ( x, y)dxdy 4 (1)

dengan m,n = 0, 1, 2,3...∞ . f(x,y) merupakan fungsi citra kontinyu dan Pm dan Pn merupakan polinomial Legendre dengan bentuk umum :

(2n − 2m)!

M

Pn ( x) = ∑ (−1) m

x n−2m ............

2 m!(n − m)!(n − 2m)! m =0 (2n)! (2n − 2)! = n − x n−2 + −..... 2 (n!) 2 2 n1!(n − 1)!(n − 2)! n

(2) Sampling citra dilakukan dengan menempatkan fungsi citra f(xi,yj) pada ruang diskrit [-1,1] × [-1,1] sehingga 1 1 xi = −1 + (i + ) × Δx, y j = −1 + ( j + ) × Δy, 2 2 2 2 dan Δy j = Δy = ; ∀ j Δx i = Δx = ; ∀ i N M Nilai polinomial Legendre didapat dengan menghitung polinomial Legendre di setiap titik tengah interval. Fungsi kontinyu f(x,y) dapat ditulis sebagai deret tak hingga dari polinomial Legendre pada [-1 ≤ x, y≤ 1] yakni : ∞

∞

f ( x, y ) = ∑∑ λmn Pm ( x) Pn ( y )

(3)

m=0 n =0

Jika diberikan order momen (m+n) ≤ L maka fungsi f(x,y) dapat dihitung dengan pendekatan: L

m

fˆ ( x, y ) = ∑∑ λm − n, n Pm − n ( x) Pn ( y) m=0 n =0

(4)

Jika order momen Legendre dibatasi pada m≤ mmax dan n≤nmax maka aproksimasinya seperti persamaan (5): mmax nmax

fˆ ( x, y ) = ∑ ∑ λ m, n Pm ( x) Pn ( y) m=0 n =0

(5)

Persamaan (4) inilah yang diaplikasikan untuk merekonstruksi citra menggunakan momen Legendre. Beberapa metode komputasi momen Legendre yang mengimplementasikan persamaan (1) antara lain : 2.1

∫ xi −

yj +

dimana

Δxi 2

Δxi 2 Δx xi − i 2

∑ Brm xm−2r +1

[

]

∑ B [y

]

D ( m) r =0

xi +

Δy j

∫ yj −

Pm ( x)dx =

2

Δy j

Pn ( y)dy =

D ( n) s =0

sn

n − 2 s +1

yj + yj −

(6)

Δy j 2 Δy j 2

Bkn = −

(n − k + 1)(n − 2k + 3)(n − 2k + 2) Bk −1 , n (2n − 2k + 2)(2n − 2k + 1)k (9)

dengan

B0,n =

(2n)! 2n − 1 = B0,n−1 , B0,0 = 1 2 n!(n + 1)! n + 1

(10)

n

Untuk menyederhanakan, dibentuk jadi persamaan

Qn ( z j ) =

[ ]

2n + 1 D ( n ) ∑ Bkn Z j ,n−2k +1 , Z jp = z p 2 k =0

zj+ zj−

Δy j 2 Δy j 2

(11) Nilai Qn(zi) tidak tergantung pada fungsi citra, melainkan pada orde dan ukuran citra. Sehingga untuk citra yang berbeda, asal ukuran dan ordenya sama, nlai Qn(zi) cukup dihitung sekali. Momen Legendre kemudian didapat dengan persamaan : M −1 N −1

λ mn = ∑∑ f ( xi , y j )Qm ( xi )Qn ( y j ) i =0 j =0

2.2

(12)

Exact Geometric Moment (EGM)

Momen Legendre juga bisa dihitung melalui momen Geometri. Momen Geometri orde (m+n) didefinisikan oleh : 1 1

(13)

Jika citra didefinisikan hanya pada titik-titik diskrit (xi ,yj) maka persamaan (13) menjadi, M −1 N =0

M mn = ∑∑ f ( xi , y j ) i =0 j =0

xi +

Δy j Δxi yj+ 2 2

∫ ∫x xi −

Δxi Δy j y − 2 j 2

m

y n dxdy

(14)

Integrasi pada persamaan ini dilakukan seperti persamaan (14) Jika dinotasikan dengan Zip seperti pada persamaan (15) menjadi,

M mn = (7)

(8)

D(n)=n/2 atau n-1/2 dipilih yang bulat. Dengan demikian momen Legendre bisa dihitung secara lebih akurat karena diintegrasikan langsung dari polinomialnya, bukan dengan mengaproksimasi per interval. Untuk menghindari faktorial, persamaan (8) dapat diubah menjadi :

−1 −1

Metode ELM ini melakukan perhitungan momen Legendre dengan mengintegrasikan langsung dari polinomialnya secara matematis. Polinomial Legendre pada persamaan (2) diintegrasikan menjadi: Δxi 2

(−1) k (2n − 2k )! 2n k!(n − k )!(n − 2k + 1)!

M mn = ∫ ∫ x m y n f ( x, y )dxdy

Exact Legendre Moment (ELM)

xi +

Bkn =

M −1 N =0 1 ∑∑ f ( xi , y j )Zi,m+1Z j ,n+1 (m + 1)(n + 1) i=0 j =0

(15)

2

Karena ada proses pengintegrasian secara matematis dari persamaan (13) menjadi persamaan (15), dengan kata lain tak ada aproksimasi integral,

maka metode ini dinamakan Exact Geometric Moment (EGM).

yang sama nilai pikselnya, dikenal sebagai Image Block Representation (IBR) Encoding.

Adapun hubungan antara momen Legendre dan momen Geometri adalah pada persamaan (16):

Algoritma dari IBR Encoding adalah sebagai berikut : 1. Plot citra biner pada diagram cartesius. Pada setiap garis y perhatikan interval antara blok (berpiksel 1) dan latarnya (berpiksel 0) 2. Bandingkan dengan interval pada garis y-1. 3. Jika interval tidak cocok dengan blok berpiksel, maka ini adalah awal dari blok baru 4. Jika interval cocok dengan blok berpiksel, maka akhir dari blok ini pada garis y

λmn =

(2m + 1)(2n + 1) D ( m)D( n ) ∑ ∑ B'rm B'sn M m−2r ,n−2s 4 r =0 s =0 (16)

dimana B’rm=(m-2r+1) Brm dan B’sn=(n-2s+1) Bsn, Dengan demikian Exact Legendre Moment (ELM) bisa dihitung secara tidak langsung lewat Exact Geometric Moment (EGM) 2.3

Zeroth Order Approximation (ZOA)

Dalam ruang citra diskrit berukuran M × N, f(x,y) disampling pada ruang [-1,1] × [-1,1] dinotasikan dengan (xi , yj) ( xi , y j ) ∈ [-1,1] × [-1,1], dimana i = 0,1,2,3.....M-1 dan j = 0,1,2,3.....N-1. Pada metode Zeroth Order Approximation (ZOA), integrasi polinomial Legendre pada persamaan (1) diaproksimasi sebagai nilai konstan sepanjang Δx Δx interval ⎡ xi − i , xi + i ⎤ , ⎡ y − Δy j , y + Δy j ⎤ . j ⎥ ⎢ 2 2 ⎥⎦ ⎢⎣ j 2 2 ⎦ ⎣ sehingga menjadi : (2m + 1)(2n + 1) M −1 N −1 λ mn = f ( xi , y j ) Pm ( xi ) Pn ( y j ) ∑∑ MN i =0 j =0

(17) dimana Δxi = xi +1 − xi

dan Δy j = y j +1 − y j .

Gambar 1 Citra Biner dengan IBR Encoding Hasil dari algoritma ini adalah representasi citra menjadi k blok segiempat berpiksel 1.

f ( x, y) = {bi : i = 0,1,......, k − 1}

(19) Masing-masing blok b memiliki koordinat kiri atas dan kanan bawah. Blok-blok ini jika disubtitusikan ke persamaan ELM menjadi : k −1 x2 ,bi y2 ,bi

k −1

λmn = ∑ λbmn = ∑∑∑ Qm ( x)Qn ( y) i

i =0

(20)

i =0 x1,bi y1,bi

x1,bi , x2,bi dan

di mana

y1,bi , y2,bi

merupakan

dengan m,n = 0, 1, 2,3...∞ , Pm dan Pn merupakan polinomial Legendre dan f(x,y) merupakan fungsi citra kontinyu.

koordinat dari blok bi . Implementasi SLM adalah dengan menyederhanakan persamaan untuk mencari Momen Legendre pada suatu blok, yakni:

2.4

λbmn =

Simpson’s Rule (SR)

Tiap interval sampling xi sampai xi+1 dibagi menjadi 4 titik integrasi, yakni k0 , k1 , k2 , k3. Integrasi dari xi sampai xi+1 dengan Simpson 3/8 rule didefinisikan : x 3h ∫x Pn(x)dx ≈ 8 [Pn(k0 ) + 3Pn(k1 ) + 3Pn(k2 ) + Pn(k3 )] (18) Nilai h merupakan interval integrasi, yakni interval sampling citra dibagi 3, h = xi +1 − xi . Setelah nilai

2.5

( x)Qn ( y) y2 b

y = y1b

y = y1b

y2 b

+ ... + Qm ( x2b ) ∑ Qn ( y ) y = y1b

⎞ ⎞⎛ ⎛ = ⎜⎜ ∑ Qm ( x) ⎟⎟⎜⎜ ∑ Qn ( y) ⎟⎟ ⎠ ⎠⎝ y = y1b ⎝ x = x1b x2 b

y2 b

(21)

Sehingga, nilai keseluruhan Momen Legendre untuk k blok adalah k −1

⎛

i =0

⎝ x= x1b

x2 b

⎞⎛

y2 b

⎞

λmn = ∑ ⎜⎜ ∑ Qm ( x) ⎟⎟⎜⎜ ∑ Qn ( y) ⎟⎟

Speedy Legendre Moment (SLM)

Speedy Legendre Moment (SLM) menyederhanakan komputasi dari ELM pada citra biner. SLM merepresentasikan citra biner menjadi blok-blok

m

y2 b

i +1

polinomial Legendre tiap interval diaproksimasi, selanjutnya momen Legendre dihitung dengan persamaan (17).

∑ ∑Q

x = x1b y = y1b

= Qm ( x1b ) ∑ Qn ( y) + Qm ( x1b + 1) ∑ Qn ( y)

i

3

x = x2 b y = y2 b

3.

⎠⎝ y= y1b

⎠

(22)

Desain dan Implementasi

Aplikasi pada penelitian ini dirancang untuk melaku-kan rekonstruksi citra dengan mengimple-

mentasikan kelima metode komputasi momen Legendre di atas. Kemudian dibandingkan waktu komputasinya dan error rekonstruksinya. Gambar 2 berikut menjelaskan garis besar aplikasi : Citra Input

Sampling Citra

Hitung Error Rekonstruksi dan Waktu Komputasi

Block Decoding

Block Encoding

sudah

Pada Gambar 3, terlihat bahwa error ZOA mekonjak naik seiring bertambahnya orde. Sedangkan pada Simpson’s Rule, error rekonstruksi pada orde-orde awal bergerak turun untuk kemudian melonjak naik pada titik baliknya. Error rekonstruksi ELM dan EGM pada range orde (3,3) sampai (21,21) menunjukkan nilai yang sama.

Semua blok sudah diproses?

belum Komputasi Momen Legendre

Citra Output

Rekonstruksi Citra

Gambar 2 Garis Besar Aplikasi Parameter pembanding kelima metode adalah waktu komputasi dan akurasinya, yakni besanya error rekonstruksi yang didefinisikan sebagai :

ε=

[

]

2 1 M −1 N −1 ˆ f (i, j; L) − f (i, j ) ∑∑ MN i=0 j =0

(23)

4.

Pengujian Sistem Pengujian dilakukan dengan merekonstruksi ctra true color, grayscale, dan binary dengan berbagai orde dan ukuran block encoding kemudian membandingkan waktu komputasi dan error rekonstruksinya. Khusus untuk metode SLM hanya bisa diujikan pada citra biner. 4.1

Citra True Color

Rekonstruksi dilakukan dengan citra input sailonboat.jpg true color 102×102 piksel dan block encoding 25×25 piksel dengan orde diiterasi dari (3,3) sampai (21,21) dan interval interasi sejumlah 3.

Gambar 4 Grafik Waktu Komputasi Grafik waktu komputasi diperlihatkan pada Gambar 4. Untuk semua metode, ELM, EGM, SR, dan ZOA, waktu komputasi akan meningkat seiring pertambahan orde. Terlihat bahwa EGM memiliki waktu komputasi lebih lama dibanding yang lain, disusul Simpson’s Rule, ELM, dan ZOA. 4.2

Citra Grayscale

Citra input boat.jpg grayscale 102×102 piksel direkonstruksi dengan ukuran block encoding 20×20 piksel. Rekonstruksi dilakukan dengan keempat metode sekaligus (ELM, EGM, ZOA, SR) dengan orde diiterasi dari (3,3) sampai (21,21) dan interval iterasi sejumlah 3. Grafik error rekonstruksi pada Gambar 5 memperlihatkan bahwa error terkecil dicapai oleh ELM dan EGM, disusul Simpson’s Rule kemudian ZOA. Pada Gambar 6 terlihat bahwa EGM menghasilkan waktu komputasi yang paling lama disbanding yang lain, kemudian disusul Simpson’s Rule, ELM, dan ZOA.

Gambar 3 Grafik Error Rekonstruksi Gambar 5 Grafik Error Rekonstruksi

Gambar 7 memperlihatkan bahwa SLM merupakan metode dengan akurasi paling baik diantara yang lain. Disusul kemudian ELM dan EGM yang memiliki tingkat error sama. Terlihat pada Simpson’s Rule, orde bergerak turun kemudian naik pada titik baliknya. Akurasi paling buruk adalah pada metode ZOA. Terlihat dari Gambar 8, waktu komputasi SLM bersaing dengan ZOA, tetapi secara umum SLM lebih baik karena akurasinya paling bagus dibanding yang lain. Waktu komputasi ELM menyusul pada peringkat ke-tiga diikuti Simpson’s Rule dan EGM. 5. Gambar 6 Grafik Waktu Komputasi 4.3

Citra Biner

Uji coba rekonstruksi dilakukan dengan citra input cameraman.jpg 102×102 piksel. Karena merupakan citra biner, maka kelima metode (ELM, EGM, ZOA, SR, SLM) bisa diimplementasikan). Rekonstruksi dilakukan dengan ukuran block encoding 16×16 piksel dan orde diiterasi dari (3,3) sampai (21,21) dengan interval iterasi sejumlah 3.

Gambar 7 Grafik Error Rekonstruksi

Kesimpulan

Kesimpulan yang dapat diambil dari hasil studi kinerja yang telah dilakukan adalah sebagai berikut: • Keakuratan hasil rekonstruksi citra dipengaruhi oleh besar kecilnya ukuran block encoding dan orde maksimum polinomial. Semakin kecil ukuran block encoding, semakin akurat hasil yang didapat, namun berakibat pada semakin lamanya waktu komputasi. Orde maksimum polinomial yang tinggi berakibat pula pada waktu komputasi yang lama, tetapi hasil yang didapat akan lebih akurat. • Masing-masing metode memiliki batas orde tertentu yang menjadi titik balik dimana error rekonstruksi akan semakin meningkat setelah melalui orde ini. Hal ini disebabkan oleh Local Truncation Error(LTE) karena keterbatasan aplikasi dalam melakukan komputasi. Error ini biasa ditemukan dalam setiap komputasi. Pada metode ELM, titik balik terjadi pada orde yang lebih tinggi dari yang lain (pada kisaran orde (40,40) ke atas), sehingga error rekonstruksi bisa mencapai hasil yang minimum yakni bisa mendekati 1.0e-007, tergantung pada ukuran block encoding dan orde nya. Pada metode SLM, error rekonstruksi bisa mencapai 0 meskipun belum berada pada titik balik. • Exact Legendre Moment (ELM) merupakan metode komputasi momen Legendre paling akurat dan efisien untuk citra true color atau grayscale. Sedangkan untuk citra biner, Speedy Legendre Moment (SLM) memberikan akurasi yang melebihi metode lainnya dengan waktu komputasi yang cukup minim. Kedua metode ini, SLM dan ELM, merupakan metode yang handal untuk digunakan pada orde tinggi. DAFTAR PUSTAKA

Gambar 8 Grafik Waktu Komputasi

[1] Pew-Thian Yap dan Raveendran Paramesran, “An Efficient Method for The Computation of Legendre Moments,” IEEE Trans. On Pattern Analysis and Machine Intelligence, vol.27, no.12, December 2005.

[2] G.A. Papakostas, E.G. Karakasis dan D.E. Koulouriotis, “Exact and Speedy Computation of Legendre Moments on Binary Image,” Democritus University of Thrace, Xanthi, Hellas 2007. [3] S.P. Prismall, M.S. Nixon dan J.N. Carter. Stork, “Accurate Object Reconstruction by Statistical Moments”, University of Southampton, United Kingdom, 2003 [4] Iraklis M. Spiliotis dan Basil G. Mertzios, ” Real-Time Computation of Two-Dimensional Moments onBinary Images Using Image Block Representation”, IEEE Transactions on Image Processing, vol. 7, no. 11, November 1998. [5] Simon X.Liao dan Miroslaw Pawlak, "On Image Analysis by Moments," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.18, no. 3, March 1996 [6] Cho Huak Teh Roland T. Chin, "On Image Analysis by the Methods of Moments,"IEEE Transactions of Pattern Analysis and Machine Intelligence. vol. 10, no. 4 July 1988 [7] Jun Shen dan Danfei Shen, "Image Charecterization by Fast Calculation of Low Order Legendre Moments," Image Laboratory Institute of Geodynamics, France