APLIKASI METODE SURFACE FLATTENING PADA PEMETAAN TEKSTUR Rully Soelaiman1, Hathfi Bahrial Hakim1 dan I Made Agus Setiawan1 1 Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember (ITS), Surabaya, 60111, Indonesia E-mail :
[email protected]
Abstrak - Dewasa ini perkembangan ilmu grafika semakin banyak digunakan dalam berbagai bidang terutama dalam desain teknik, periklanan, perfilman, kedokteran sampai sekedar untuk permainan atau game komputer. Semuanya berkaitan dengan kebutuhan visualisasi objek sehingga mencapai kesan realistis. Dalam usaha untuk menampilkan objek-objek serealistis mungkin, pemetaan tekstur (texture mapping) merupakan proses yang erat berkaitan. Agar objek yang divisualisasikan tampak memiliki warna-warni yang bervariasi dan berkesan alami, perlu ditambahkan efek tekstur pada permukaan objek tersebut. Pada penelitian ini akan dibahas dan diimplementasikan sebuah metode pemetaan tekstur pada permukaan objek tiga dimensi dengan melakukan pendekatan pendataran permukaan. Melalui versi datar dari permukaan, sebuah tekstur dua dimensi dapat dipetakan dengan mudah sehingga kemudian dapat diaplikasikan kedalam permukaan tiga dimensi. Pendataran permukaan dilakukan dengan cara melakukan pendekatan jarak geodesic pada permukaan 3D dengan jarak euclidean pada bidang datar melalui teknik Multi-Dimensional Scaling. Metode pemetaan ini menampilkan struktur lokal dan global dari tekstur dengan distorsi minimal dan tingkat komputasi yang efisien. Kata Kunci : Pemetaan Tekstur, Pendataran Permukaan, Jarak Geodesic, Multi-Dimensional Scaling.
ditunjukkan oleh Gauss (1828) bahwasanya pemetaan isometri antara dua permukaan dengan lekukan yang berbeda adalah hal yang tidak mungkin. Dengan kata lain, tidaklah mungkin memetakan permukaan dengan lekukan-lekukan yang kompleks kedalam bidang planar tanpa terjadinya distorsi. Hingga saat ini hanya solusi pendekatan yang dimungkinkan untuk dilakukan. Oleh karena itu algoritme pendataran pemukaan (surface flattening) hanya bertujuan pada peminimalan distorsi geometri, tetapi tidak bisa mencegah terjadinya distorsi itu sendiri. Dalam penelitian ini akan dibahas mengenai salah satu metode yang diperkenalkan dalam teknik pendataran permukaan. Dalam metode ini diperlukan dua tahap proses metode numerik. Tahap pertama yaitu proses pencarian jarak geodesic dibahas pada bagian 2. Hasil proses ini dijadikan inputan proses tahap selanjutnya yaitu Multi-Dimensional Scaling (MDS) dibahas pada bagian 3. Bagian 4 secara singkat menjelaskan bagaimana menggunakan hasil MDS untuk pemetaan tekstur. Bagian 5 menampilkan hasil dari beberapa ujicoba yang dilakukan dan kesimpulan dijabarkan pada bagian 7. 2. PENCARIAN JARAK GEODESIC Sebagai langkah awal dalam melakukan pendataran permukaan tiga dimensi pada penelitian ini adalah mencari jarak geodesic antara tiap pasang titik di dalam permukaan.
1. PENDAHULUAN Permasalahan pemetaan tekstur (texture mapping) sangat erat kaitannya dengan masalah pendataran permukaan tiga dimensi ke dalam bidang planar, karena pada umumnya tekstur yang ada berupa gambar 2D. Sehingga untuk memetakan tekstur tersebut dibutuhkan suatu metode untuk mendatarkan permukaan 3D menjadi bidang planar sehingga tekstur dapat dengan mudah dipetakan. Pada konteks pemetaan permukaan bumi, hal ini dikenal sebagai “map maker problem”, yaitu bagaimana cara menggambarkan permukaan bola dunia ke dalam suatu lembaran peta. Telah
Gambar 1 Jarak geodesic pada permukaan bola
Jarak geodesic antara dua titik dalam sebuah permukaan adalah jarak terdekat yang melalui permukaan yang menghubungkan kedua titik tersebut. Sebagai contoh pada sebuah permukaan bola (gambar 1), jarak geodesic antara 2 titik dalam permukaan tersebut merupakan jarak busur
antara 2 titik tersebut pada sebuah lingkaran yang berpusat pada pusat bola dan melalui kedua titik tersebut. Karena didalam Penelitian ini permukaan tiga dimensi yang akan diberi tekstur direpresentasikan dalam bentuk triangular mesh maka pencarian jarak geodesic dikhususkan pada permukaan dengan bentuk tersebut. Metode pencarian jarak geodesic pada triangular mesh yang digunakan dalam Penelitian ini dinamakan “Fast Marching Method on Triangulated Domain (FMM on TD)” yang dikembangkan oleh James A. Sethian dan Ron Kimmel [Kim-1998]. Inti dari FMM ini adalah melakukan propagasi menyebar / maju (front propagation) dari sebuah titik sebagai starting vertex ke segala arah yang mungkin. Setiap bergerak maju algoritme ini selalu mensghitung dan menyimpan nilai jarak suatu titik terhadap titik awal (starting vertex), nilai jarak tadi disimpan sebagai properti dari titik tersebut. Tiap titik diproses, semakin jauh titik tersebut nilai jaraknya menjadi semakin besar. Seperti terlihat pada gambar 2, proses propagasi maju dari FMM ini dapat dianalogikan sebagai kobaran api yang membakar padang rumput, kobaran api ini berjalan maju dengan kecepatan konstan ke segala arah membakar rumput yang belum terbakar (Unprocessed vertex set). Proses “pembakaran” ini dimulai pada titik awal dan bergerak maju “membakar” titik-titik lain di sebelahnya (Close vertex set). Titik yang telah “terbakar” (Fixed vertex set) berarti titik tersebut telah diproses atau telah dihitung nilai jaraknya dari titik awal. Proses ini berhenti sampai semua titik telah “terbakar” atau telah dihitung nilai jaraknya.
u v w
Fixed Vertex Set
Close Vertex Set
Unprocessed Vertex Set
u v x w
Algoritme FMM ini mirip dengan algoritme Dijkstra yang digunakan untuk memecahkan masalah single-source shortest paths pada sebuah graf berbobot dan tak berarah (weighted and nondirected graphs). Idenya adalah mendeskripsikan permukaan triangular mesh sebagai sebuah graf, dimana sisi dari segitiga adalah sebagai garis penghubung berbobot dan tak berarah (nondirected weighted edge) yang menghubungkan 2 vertex. Vertex pada graf dinyatakan oleh titik pada ruang 3 dimensi. Nilai bobot (weight) dari suatu edge sama dengan jarak Euclidean antara 2 titik dihubungkan oleh edge tersebut : w ( e v ,v ) = d ( v i , v j ) . i
j
Algoritme Dijkstra terdiri dari langkahlangkah berikut : Inisialisasi : Ambil v0 menjadi source vertex, nilai T(v0) = 0 dan tetapkan pada semua vertex lainnya T(v) = ∞. Langkah 1 : Update semua vertex vi yang terhubung dengan v0 oleh sebuah edge melalui cara :
(
T (vi ) = min T (vi ), T (vi ) + w(evi ,v j )
)
Langkah 2 : Masukkan vertex yang baru diupdate tersebut ke dalam struktur data min-heap. Jika vertex tersebut telah ada di dalam min-heap, maka hanya update lokasi vertex tersebut di dalam min-heap. Langkah 3 : Jika min-heap telah kosong, keluar dari proses, jika tidak pindahkan vertex pada puncak dari struktur minheap dan sebut vertex tadi sebagai v0. Langkah 4 : Kembali ke langkah 1. Perbedaan antara algoritme FMMdengan algoritme Dijkstra adalah pada langkah update (langkah 1). Pada algoritme FMM, untuk mengupdate nilai dari suatu titik digunakan suatu metode khusus yang bertujuan untuk menghitung nilai T dari suatu titik berdasarkan nilai T dari dua titik lainnya yang berada pada satu segitiga yang sama. Solusi dari metode khusus langkah update tersebut dijelaskan selengkapnya pada [Kim-1998] dan [Soe-2006]. Seperti pada gambar 2 nilai T titik v dihitung dari nilai T titik u dan titik w yang nilai T-nya sudah pasti, karena kedua titik tersebut sudah termasuk dalam Fixed vertex set. Semisal nilai T titik v adalah nilai T yang terkecil pada Close vertex set maka titik v dimasukkan dalam Fixed vertex set. Dan titik tetangga v yaitu titik x dimasukkan dalam Close vertex set dan seterusnya hingga semua titik terproses. 3. MULTIDIMENSIONAL SCALING
Gambar 2 Ilustrasi proses propagasi maju FMM
Multi-Dimensional Scaling (MDS) adalah sebuah teknik matematis yang digunakan untuk
mengungkap struktur geometri dari sebuah set data. Sebagai contoh, diketahui n objek data dengan nilai dissimilaritas {δ} antar tiap pasang objek tersebut (dissimilaritas dapat diartikan sebagai jarak atau nilai lain yang merepresentasikan hubungan antar tiap objek data), MDS dapat digunakan untuk membuat sebuah peta konfigurasi n titik yang merepresentasikan n objek tersebut dalam sebuah ruang m dimensi. Sedemikian rupa sehingga jarak {d} tiap pasang titik pada ruang tersebut (tidak harus berupa jarak euclidean) mendekati nilai dissimilaritas {δ} antar tiap pasang objek. Pada umumnya dimensi m yang diharapkan adalah dimensi yang rendah, misal dimensi 2 sehingga n objek data tersebut lebih mudah untuk dianalisa. Dalam Penelitian ini, MDS digunakan dengan cara serupa. Sebagai nilai dissimilaritas, digunakan jarak geodesic yang diukur diantara tiap pasang titik pada permukaan 3D dengan menggunakan metode yang telah dibahas pada bagian 2. Peta yang dihasilkan merepresentasikan pendataran dari permukaan 3D. Salah satu pendekatan yang langsung dan mudah dari MDS adalah Classical Scaling. Secara garis besar Classical Scaling meliputi 2 tahap proses yaitu membangun matriks Bnxn yaitu matriks perkalian skalar antar tiap pasang titik tanpa mengetahui matriks koordinat Xnxm tetapi mengetahui matriks Mnxn yaitu matriks dissimilaritas antar tiap pasang titik, proses ini dinamakan “Double Centering” dan tahap selanjutnya adalah melakukan dekomposisi terhadap matriks Bnxn tersebut sehingga didapatkan matriks koordinat Xnxm, tahap ini disebut sebagai “Eigen Decomposition”. Untuk lebih jelasnya sebagai berikut : Double Centering Misalkan matriks Xnxm adalah matriks koordinat dari n titik pada ruang euclidean m dimensi. Maka kuadrat jarak euclidean antara titik i dan titik j didefinisikan sebagai : m
d ij2 = ∑ ( xia − x ja ) 2
3.1
a =1
Matriks Enxn adalah matriks kuadrat jarak euclidean antara tiap pasang titik pada Xnxm, sehingga Eij = d2ij. Maka matriks Enxn dapat dituliskan sebagai :
E = c1'+1c'−2 XX '
3.2
Dimana 1nx1 adalah vektor yang berisi satu dengan panjang n. sedangkan cnx1 adalah vektor dengan panjang n dimana ci = ∑m xia2 dan tanda petik satu a =1
(‘) menandakan operasi transpose. Matriks Bnxn, yaitu matriks perkalian skalar antar tiap pasang titik pada Xnxm dapat didefinisikan sebagai : 3.3 B = XX '
Tujuan “double centering” adalah membentuk matriks Bnxn diatas dari matriks Enxn kuadrat jarak euclidean antar tiap pasang titik. Secara logika dengan hanya memiliki informasi jarak antar tiap pasang titik maka akan terdapat banyak solusi konfigurasi koordinat titiktitik yang memenuhi jarak antar tiap pasang titik tersebut, karena solusi tersebut apabila dirotasi, ditranslasi, maupun dicerminkan akan tetap menghasilkan solusi yang memenuhi jarak antar tiap pasang titik tersebut dan bisa dianggap benar. Untuk mengatasi hal tersebut maka pusat massa dari konfigurasi titik tersebut ditempatkan pada titik pusat koordinat (centering). Hal tersebut dapat dilakukan dengan cara sebagai berikut, tentukan :
s = (1' X ) / n
3.4
Dimana n adalah jumlah titik dan 1nx1 adalah vektor yang berisi satu dengan panjang n. Maka matriks koordinat Xnxm yang ditengahkan (centered) :
X * = X − 1s = X − (11' X ) / n
3.5 Dengan menggunakan Xnxm versi centered maka matriks perkalian skalar Bnxn yang ditengahkan (centered) :
1 B* = − JEJ 2
dengan
1 J = I − 11' n
Matriks Enxn kuadrat jarak euclidean diatas merupakan matriks dissimilaritas Mnxn dan matriks Jnxn disebut sebagai matriks “centering”. Sehingga secara umum “Double Centering ” dapat dirumuskan :
B=−
1 JMJ 2
3.6
Eigen Decomposition Setelah didapatkan matriks Bnxn, maka langkah selanjutnya adalah melakukan dekomposi matriks Bnxn. Langkah ini erat kaitannya dengan metode Singular Value Decomposition (SVD). Karena matriks Bnxn adalah matriks simetri dan positif semi definit (semua nilai eigennya lebih besar dari nol) maka matriks Bnxn dapat didekomposisi menjadi :
B = QΛQ '
3.7
Dimana Λnxn adalah matriks diagonal nilai eigen dari matriks Bnxn dan tiap kolom Qnxn adalah vektor eigen yang bersesuaian. Karena matriks Λnxn adalah matriks diagonal sehingga (Λ½)’ = (Λ½) , maka Bnxn dapat dituliskan sebagai :
B = (Q Λ½ )( Λ½ Q ' )
3.8
Karena Bnxn = XX’ maka bisa didapatkan kembali matriks koordinat Xnxn dengan mendefinisikan :
X = (QΛ½ )
3.9
versi datar dari permukaan tersebut sebuah tekstur 2D dapat dipetakan dengan mudah ke dalam permukaan. Secara umum langkah-langkahnya sebagai berikut : 1.
Algoritme Pendataran Permukaan Pada masalah pendataran permukaan, yang dilakukan adalah mencoba memetakan titik pada permukaan 3D pada bidang datar sedemikian rupa sehingga didapatkan error pendekatan sekecil mungkin antara jarak geodesic pada permukaan 3D dan jarak euclidean pada bidang datar yang bersesuaian.
2. 3.
Tentukan posisi relatif permukaan datar terhadap bidang tekstur dengan cara melakukan transformasi geometri 2D (rotasi, translasi, penskalaan, flip). Tentukan koordinat tekstur tiap titik pada permukaan datar berdasarkan posisi relatif terhadap bidang tekstur. Aplikasikan tekstur pada permukaan 3D berdasarkan koordinat tekstur dari tiap koresponden titik pada permukaan datar.
5. HASIL UJI COBA Berikut adalah beberapa hasil uji coba yang telah dilakukan. Uji Coba Visualisasi Gambar 3 Pendekatan jarak geodesic pada 3D dengan jarak euclidean pada 2D
Berikut akan dijelaskan secara singkat langkah-langkah algoritme pendekatan pendataran permukaan : 1. 2.
3.
4.
5.
Hitung kuadrat jarak geodesic antar tiap pasang titik pada permukaan 3D sebagai matriks dissimilaritas Mnxn. Lakukan Double Centering pada matriks Mnxn untuk mendapatkan matriks perkalian skalar : Bnxn = -½ JMJ dimana Jnxn = I–(11’)/n adalah matriks centering dan 1nx1 adalah vektor yang berisi satu dengan panjang n. Dekomposisi matriks Bnxn sehingga Bnxn = QΛQ’ dimana Λnxn adalah matriks diagonal nilai eigen dari matriks Bnxn dan Qnxn adalah matriks vektor eigen yang bersesuaian. Tentukan Λ+ adalah 2x2 matriks diagonal 2 nilai eigen positif terbesar pada Λnxn dan Q+ adalah nx2 matriks vektor eigen yang bersesuaian. Matriks koordinat hasil pendataran permukaan adalah :
Uji coba visualisasi dilakukan pada model manekin_face.ply yang berupa permukaan wajah manusia dan tekstur yang digunakan adalah tekstur wajah seperti yang terlihat pada gambar 4(b). Hasil akhir pemetaan tekstur diperlihatkan pada gambar 4(d) dibawah, secara umum hasil pemetaan tekstur cukup memuaskan. Sebuah visualisasi wajah 3D dapat terlihat cukup realistis pada gambar tersebut.
(a)
(b)
(c)
(d)
½
Xnx2 = Q+Λ+
4. MDS UNTUK PEMETAAN TEKSTUR Setelah Classical Multi-Dimensional Scaling dengan menggunakan masukan jarak geodesic antar tiap titik pada permukaan dilakukan, maka hasilnya didapatkan sebuah versi datar dari permukaan. Tiap titik pada permukaan 3D memiliki korespondensi dengan titik pada permukaan versi datar. Dengan menggunakan
Gambar 4 (a) Tekstur wajah. (b) Pemetaan tekstur wajah pada model 3D manekin_face.ply. (c) Pemetaan tekstur wajah pada model 2D manekin_face.ply. (d) Hasil akhir Pemetaan tekstur wajah pada model 2D manekin_face.ply.
(a)
(b)
Gambar 5 (a) Hasil pemetaan tekstur papan catur pada model swissroll.ply. (b) tekstur papan catur
Gambar 5(a) merupakan hasil pemetaan tekstur papan catur pada model swissroll.ply. model ini menyerupai sebuah gulungan kertas. Tampak pada gambar pola kotak-kotak papan catur terlihat jelas pada model ini. Pada bagian akhir paper ini ditampilkan hasil pemetaan tekstur papan catur pada model-model yang lain. Uji Coba Pendekatan Pendataran Uji coba ini dilakukan dengan cara melakukan perbandingan antara jarak geodesic antar tiap pasang titik pada permukaan 3 dimensi dengan jarak euclidean antar tiap pasang titik pada permukaan dua dimensi hasil proses pendataran. Gambar 6(b) adalah grafik error pendekatan pendataran permukaan model pada gambar 4(d). Sedangkan Gambar 6(d) adalah grafik error pendekatan pendataran permukaan model pada gambar 5(a). Seperti yang terlihat, terdapat kecenderungan untuk membentuk sebuah garis diagonal. Grafik akan menunjukkan garis diagonal hanya jika terjadi pendataran permukaan yang sempurna (jarak geodesic = jarak euclidean). Model pada gambar 4(d) berupa sebuah wajah sehingga relatif lebih sulit untuk didatarkan (terlihat error lebih besar) ketimbang model pada gambar 5(a) yang berupa gulungan lembaran kertas. Gambar disebelah kiri masing-masing grafik adalah hasil pendataran permukaan.
(c)
(d)
Gambar 6 (a) Hasil pendataran permukaan model manekin_face.ply. (b) Grafik error pendataran permukaan model manekin_face.ply. (c) Hasil pendataran permukaan model swissroll.ply. (d) Grafik error pendataran permukaan model swissroll.ply
Uji Coba Pada Model dengan Hole Uji coba dilakukan pada model bethoven_mask.ply, model ini berupa topeng wajah manusia dengan lubang pada daerah mata dan alis. Distorsi juga terlihat jelas pada daerah disekitar lubang pada model ini, seperti terlihat pada gambar 7(a). Pada Gambar 7(b) menunjukkan hasil pendataran permukaan model, lubang alis terlihat lebih besar jika dibandingkan dengan lubang alis pada permukaan 3D. Efek yang ditimbulkan pada model dengan lubang (hole) ini terjadi karena pada proses pendataran permukaan dilakukan pendekatan jarak geodesic pada permukaan 3D dengan jarak euclidean pada bidang 2D. Oleh karena jarak geodesic antara 2 titik yang dihalangi oleh lubang harus memutari lubang (relatif lebih jauh jika lubang tidak ada), maka hasil pendataran permukaan menjadi seperti yang ditunjukkan pada gambar.
(a)
(b)
Gambar 7 (a) Hasil pemetaan tekstur papan catur pada model dengan hole (b) Hasil pendataran permukaan model dengan hole
(a)
(b)
6. SIMPULAN Dari hasil ujicoba yang telah dilakukan dapat diambil kesimpulan bahwa metode surface flattening dapat diterapkan sebagai metode untuk melakukan pemetaan tekstur permukaan objek 3D yang terbuka. Tingkat distorsi yang terjadi pada teknik pemetaan tekstur dengan metode surface flattening ini bergantung pada karakteristik lekukan pada permukaan, semakin sulit permukaan tersebut didatarkan maka semakin besar distorsi yang terjadi. Teknik pemetaan tekstur dengan metode surface flattening ini sebaiknya tidak diterapkan pada model permukaan yang memiliki lubang (hole), karena relatif terjadi distorsi yang lebih besar pada daerah sekitar lubang. 7. DAFTAR PUSTAKA [Cox-1994] Cox, Trevor F dan Cox, Michael AA. “Multidimensional Scaling”. Chapman & Hall. 1994.
Based Approach”. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 24, no. 4, April 2002. [Kim-1998] Kimmel R dan Sethian J. A. “Computing Geodesic Paths on Manifolds”. Proc. Natl. Acad. Sci., vol. 95, no. 15, pp. 8431-8435, 1998. [Soe-2006] Soelaiman Rully dan Tjandra, Eddy, “Analisis Kinerja Algoritme Perhitungan Geodesic Distance Pada Permukaan Objek Triangular Mesh”. Jurnal Informatika, Jurusan Teknik Informatika, UK Petra, Mei, 2006. [Zig-2002] Zigelman G, Kimmel R, dan Kiryati N. “Texture Mapping Using Surface Flattening via Multidimensional Scaling”. IEEE Transactions on Visualization and Computer Graphics, vol. 8, no. 2, April-June 2002.
[Gro-2002] Grossman. R, Kiryati N, Kimmel R. “Computational Surface Flattening: A Voxel-
Gambar 8 Hasil pemetaan tekstur papan catur pada berbagai model
