METODE INTERPOLASI DAN IMPLEMENTASINYA DALAM CITRA DIGITAL Setiawan Hadi 1 Jurusan Matematika UNPAD, Email:
[email protected] 1
ABSTRACT Interpolasi citra dijital memegang peranan penting dalam manipulasi geometris dari sebuah citra digital. Interpolasi berkaitan erat dengan proses pemetaan piksel-piksel baik secara forward maupun reverse. Studi literatur menunjukkan bahwa terdapat empat metode interpolasi yang umum dan dapat dimanfaatkan untuk pengolahan citra dijital yaitu metode nearest-neighbour, metode bilinier, metode bicubic dan metode fractal. Pada makalah ini akan dijelaskan dasar-dasar interpolasi dan beberapa algoritma interpolasi disertai dengan contoh pada pengolahan citra dijital. Kata Kunci: Interpolasi, Pemetaan, Piksel, Citra Dijital 1
PENDAHULUAN
Interpolasi matematika, atau disebuh juka resampling, banyak digunakan dalam proses geometris citra dijital. Dalam proses geometris citra, piksel-piksel citra dipetakan dari satu citra ke citra lainnya mellaui teknik pemetaan forward maupun teknik pemetaan reverse. Algoritma-algoritma pengolahan citra yang menerapkan proses interpolasi antara lain adalah algoritma penskalaan (pembesaran atau digital zoom), rotasi citra serta proses-proses geometris dan kreatif lainnya. Gambar 1.1 menunjukkan ilustrasi proses interpolasi berupa perubahan ukuran dan pendistorsian.
Gambar 1.1: Ilustrasi Interpolasi Hasil interpolasi bisa sangat bervariasi bergantung pada algoritma interpolasi yang digunakan. Pada dasarnya interpolasi adalah proses pendekatan sehingga memungkinkan terjadi perubahan khususnya degradasi kualitas citra pada saat algoritma interpolasi diterapkan. Karena hal ini tak dapat dihindarkan, maka efek negatif proses interpolasi diusahakan seminimal mungkin dengan menerapakan algoritma interpolasi yang tepat dan sesuai dengan kebutuhan. 2
KONSEP INTERPOLASI
Interpolasi menfaatkan informasi yang dikandung oleh data yang sudah diketahui sebelumnya untuk memperkirakan dan menghasilkan data lain yang berkaitan dan tidak diketahui sebelumnya. Secara matematika definisi interpolasi dapat dituliskan sebagai berikut.
1
Jika diketahui sebuah barisan yang terdiri dari n bilangan xk yang disebut node, dan untuk setiap xk sebuah bilangan lain yk akan dicari sebuah fungsi sedemikian rupa sehingga memenuhi persamaan :s f (xk ) = yk
k = 1, . . . , n
(1)
Pasangan xk , yk disebut titik data (data point ) dan f disebut fungsi interpolan untuk titik data tersebut. Apabila banyak yk diketahui maka fungsi interpolan dapat dituliskan sebagai fk . Sebagai contoh, pada gambar 2.2 ditunjukkan sebuah tabel dan visualisainya yang dihasilkan dari sebuah fungsi f (x) yang tidak diketahui. Dari
Gambar 2.2: Contoh Tabel Data Interpolasi gambar 2.2 dapat dibuat sebuah tertanyaan berpa nilai fungsi jika nilai x adalah 2.5? Hal ini dapat dijawab melalui proses interpolasi. 3
JENIS INTERPOLASI
Interpolasi secara umum dapat dikelompokkan menjadi tiga kelompok yaitu interpolasi linier, interpolasi polinomial, dan interpolasi spline. Jenis interpolasi yang paling sederhana adalah interpolasi linier. Pada contoh di atas, untuk menentukan nilai f (2.5) dilakukan dengan cara menghitung titik tengah antara 2 dan 3 (karena 2.5 ada diantara 2 dan 3). Karena nilai f (2) adalah 0.9093 dan nilai f (3) adalah 0.1411, maka nilai f (2.5) adalah 0.5252. Pada umumnya interpolasi linier akan mengambil dua titik, (xa , ya ) dan (xb , yb ) dan interpolannya adalah sebagai berikut: (x − xa )(yb − ya ) (2) y = ya + (xb − xa ) Interpolasi linier memiliki karakteristik cepat dan mudah tetapi tidak terlalu akurat. Kelemahan lainnya adalah fungsi interpolan tidak dapat didiferesialkan (not differentiable) pada titik x(k). Dengan bahasa sederhana, faktor kesalahannya (error ) proporsional pada kuadrat jarak antara titik-titik data. Interpolasi polinomial merupakan bentuk umum dari interpolasi linier. Perbedaanya terletak kepada fungsi interpolan yang digunakan. Pada interpolasi linier, fungsi yang digunakan adalah fungsi linier, sedangkan pada interpolasi polinomial, fungsi yang digunakana adalah sebuah polinomial dengan derajat yang lebih tinggi. Di bawah ini ditunjukkan polinomial derajat enam yang melalui tujuh buah titik-titik data pada contoh sebelumnya. f (x) = −0.0001521x6 − 0.003130x5 + 0.07321x4 − 0.3577x3 + 0.2255x2 + 0.9038x Dengan memasukkan x = 2.5 pada persamaan di atas, maka nilai f (x) adalah 0.5965. Pada umumnya, jika kita memiliki n titik data, maka fungsi polinomial yang melalui semua titik data akan berderajat n − 1. Kesalahan pada interpolasi polinomial adalah proporsional terhadap jarak berpangkat n diantara titik-titik data. Karena interpolan adalah polinomial maka bersifat dapat didiferensiabel tak berhingga (infinitely differentiable). Kelemahan dari interpolasi polinomial adalah proses komputasinya yang kompleks (computationally 2
expensive). Selain itu hasil akhir interpolasi polinomial tidak terlalu akurat khususnya pada titik-titik ujuang (phenomena Runge). Kelemahan ini diatasi dengan interpolasi spline. Interpolasi linier menggunakan sebuah fungsi linier untuk setiap interval [xk , xk + 1]. Interpolasi spline menggunakan polinomial berderajat rendah untuk setiap interval dan memilih bagian atau potongan interval sedemikian rupa yang memenuhi (fit ) dengan tepat (smooth). Fungsi yang dihasilkan disebut fungsi spline. Di bawah ini ditunjukkan fungsi natural cubic spline yang bersifat differensiabel kontinu. Turunan pertama bernilai nol pada titik-titik ujung. ⎧ −0.1522x3 + 0.9937x if x ∈ [0, 1], ⎪ ⎪ ⎪ 3 2 ⎪ − 0.4189x + 1.4126x − 0.1396, if x ∈ [1, 2], −0.01258x ⎪ ⎪ ⎨ 0.1403x3 − 1.3359x2 + 3.2467x − 1.3623, if x ∈ [2, 3], f (x) = 0.1579x3 − 1.4945x2 + 3.7225x − 1.8381, if x ∈ [3, 4], ⎪ ⎪ ⎪ 3 2 ⎪ − 0.2450x − 1.2756x + 4.8259, if x ∈ [4, 5], 0.0538x ⎪ ⎪ ⎩ −0.1871x3 + 3.3673x2 − 19.3370x + 34.9282, if x ∈ [5, 6]. Sebagaimana halnya interpolasi polinomial, interpolasi spline menghasilkan kesalahan yang lebih kecil dibandingkan dengan interpolasi linier dan hasil interpolaso lebih halus. Walaupun demikian, interpolannya lebih mudah dievaluasi daripada polinomial derajat tinggi yang digunakan pada interpolasi polinomial. Pada gambar 3.3 ditunjukkan ilustrasi visual ketiga kelompok interpolasi yang dijelaskan di atas. Studi literatur menunjukkan masih terdapat berbagai kelompok interpolasi yang menarik untuk diteliti yaitu interpolasi rasional, interpolasi trigonometri, interpolasi Nyquist-Shannon, interpolasi bilinier dan bicubic, interpolasi trilinier dan interpolasi Hermite.
Gambar 3.3: Ilustrasi Hasil Proses Interpolasi Linier, Polinomial dan Spline
4
INTERPOLASI CITRA DIJITAL
Interpolasi citra dijital bekerja secara dua arah. Proses ini berusaha untuk mendapatkan hasil perkiraan nilai piksel warna dan intensitas yang terbaik berdasarkan nilai pada piksel-piksel di sekitarnya (pixel surrounding/pixer neighborhood ). Gambar 4.4 menunjukkan ilustrasi proses ini. Citra asli adalah citra gray-level 8-bit yang akan diperbesar 183%. Sebelum interpolasi dilakukan, proses pembesaran akan menghasilkan hole (ditandai dengan ?). Setelah dilakukan interpolasi maka hole akan diisi dengan nilai warna dan intensitas sesuai dengan algoritma interpolasi yang digunanakan. Sebagai pembanding, gambar di paling kanan adalah hasil citra jika tidak dilakukan interpolasi, tetapi hanya dilakukan perbesaran dengan menggunakan teknik replikasi piksel. Ilustrasi di bawah ini menunjukkan penurunan kualitas citra (degradasi) akibat proses geometris rotasi. Sebagian informasi rinci/detil tentang citra akan hilang sebagai akibat dari proses rotasi pada sudut tertentu. Beberapa sudut rotasi yang menghasilkan hasil yang lossless adalah sudut rotasi istimewa yaitu 90 ◦ , 180 ◦ dan 270 ◦ . Algoritma-algoritma yang umum digunakan dalam melakukan interpolasi citra dijital adalah algoritma interpolasi nearest neighbour, algoritma interpolasi bilinier, algoritma bicubic dan algoritma fractal. Penjelasan algoritma 3
Gambar 4.4: Ilustrasi Interpolasi Citra Digital
Gambar 4.5: Degradasi Citra Setelah Proses Rotasi ini dapat dilihat pada bagian selanjutnya, sedangkan ilustrasi proses pembesaran objek sebesar 450% dengan menggunakan ke-empat algoritma ini dapat dilihat pada gambar 4.6. 4.1
Algoritma Interpolasi Nearest Neighbour
Interpolasi citra nearest neighbour merupakan algoritma interpolasi citra yang paling sederhana. Warna dari sebuah piksel pada citra baru adalah warna dari piksel-piksel disekitarnya. Jika kita memperbesar 200% maka sebuah piksel akan diperbesar menjadi area 2x2 dari 4 piksel dengan warna piksel yang sama dengan piksel aslinya. Algoritma ini baik digunakan apabila warna piksel diinginkan tidak berubah. Namun algoritma ini menghasilkan hasil yang kurang baik jika digunakan untuk memperbesar gambar foto. Algoritmanya sangat sederhana karena memanfaatkan teknik replikasi piksel. 4.2
Algoritma Interpolasi Bilinier
Interpolasi bilinier menentukan nilai sebuah piksel yang baru berdasarkan pada rata-rata bobot dari empat piksel pada 2x2 tingkat ketetanggaan pada citra asli. Proses yang mirip dengan perataan (averaging) ini memiliki
Gambar 4.6: Ilustrasi Hasil Interpolasi Citra
4
karakteristik efek anti-alias sehingga akan menghasilkan sisi yang lebih halus dan sedkit jaggies. Algoritma adalah sebagai berikut: 1. Perbesar lebar dan tinggi citra 2x 2. Lakukan interpolasi linier secara vertikal dengan memasukkan nilai y dari piksel yang dicari melalui per1 samaan p = py22 −p −y1 (y − y1 ) + p1 3. Lakukan interpolasi linier secara vertikal dengan memasukkan nilai x dari piksel yang dicari melalui per1 samaan p = xp22 −p −x1 (x − x1 ) + p1 4. lakukan pembulatan pada tiap piksel 4.3
Algoritma Interpolasi Bicubic
Interpolasi Bicubic adalah interpolasi yang canggih dan menghasilkan tepi-tepi yang halus dibandingkan dengan interpolasi sebelumnya. Sebuah piksel merupakan fungsi bicubic menggunakan 16 piksel pada 4x4 ketetanggaan dari citra asli. Algoritmanya adalah sebagai berikut: 1. Perbesar lebar dan tinggi sebanyak 2x 2. Lakukan interpolasi polinomial kubik secara vertikal dengan cara sebagai berikut: (a) susun matriks augmented y (b) lakukan metode eliminasi Gauss Jordan hingga diperoleh p = a0 + a1 y + a2 y 2 + a3 y 3 (c) masukkan nilai y dari piksel yang akan dicari ke persamaan di atas 3. Lakukan interpolasi polinomial kubik secara horizontal dengan cara sebagai berikut: (a) susun matriks augmented x (b) lakukan metode eliminasi Gauss Jordan hingga diperoleh p = a0 + a1 x + a2 x2 + a3 x3 (c) masukkan nilai x dari piksel yang akan dicari ke persamaan di atas 4. lakukan pembulatan pada tiap piksel Adapun matriks augmented y dan x adalah 1 1 1 1 4.4
y1 y2 y3 y4
y12 y22 y32 y42
y13 y23 y33 y43
= = = =
p1 p2 p3 p4
1 1 1 1
x1 x2 x3 x4
x21 x22 x23 x24
x31 x32 x33 x34
= = = =
p1 p2 p3 p4
Algoritma Interpolasi Fractal
Interpolasi fraktal sangat berguna terutama untuk proses pembesaran yang ekstrim. Dengan algoritma interpolasi fraktal akan dihasilkan citra hasil pembesaran yang sangat mendekati sempurna. Pada umumnya algoritma fraktal akan sangat efisien jika objek yang diolah adalah objek yang memiliki bentuk dan kontur yang walaupun rumit tetapi memiliki karakteristik khusus misalnya objek-objek natural yaitu awan, gunung, lautan dan pepohonan. 5
Penutup
Dari paparan ditunjukkan bahwa interpolasi matematika sangat bermanfaat dalam pengolahan citra dijital. Namun pemilihan algoritma mana yang akan digunakan sangat bergantung kepada permasalahan dan kondisi yang ada. Penelitian lanjutan perlu dilakukan untuk menentukan karakteristik lebih rinci tentang masing-masing algoritma interpolasi. Pembahasan algoritma selain ke-empat algoritma sangat memungkinkan untuk memperoleh pengetahuan baru dan tidak mustahil dapat mengembangkan algoritma baru yang spesifik dan lebih baik.
5
Daftar Pustaka [1] Kendell A. Atkinson (1988). An Introduction to Numerical Analysis (2nd ed.), Chapter 3. John Wiley and Sons. ISBN 0-471-50023-2 [2] L. Brutman (1997), Lebesgue functions for polynomial interpolation a survey, Ann. Numer. Math. 4, 111127. [3] M.J.D. Powell (1981). Approximation Theory and Method, Chapter 4. Cambridge University Press. ISBN 0-521-29514-9. [4] Michelle Schatzman (2002). Numerical Analysis: A Mathematical Introduction, Chapter 4. Clarendon Press, Oxford. ISBN 0-19-850279-6. [5] Endre Sli and David Mayers (2003). An Introduction to Numerical Analysis, Chapter 6. Cambridge University Press. ISBN 0-521-00794-1. [6] David Kidner, Mark Dorey and Derek Smith (1999). What’s the point? Interpolation and extrapolation with a regular grid DEM. IV International Conference on GeoComputation, Fredericksburg, VA, USA. [7] David Kincaid and Ward Cheney (2002). Numerical Analysis (3rd ed.), Chapter 6. Brooks/Cole. ISBN 0-53438905-8. [8] Steve Tanimoto (1996) Mathematics Experiences Through Image Processing, http://www.cs.washington.edu, Last accessed 21 April 2006
6
