PROGRAM MAGISTER BIDANG KEAHLIAN JARINGAN CERDAS MULTIMEDIA JURUSAN TEKNIK ELEKTRO FAKULTAS TEKNOLOGI INDUSTRI INSTITUT TEKNOLOGI SEPULUH NOPEMBER SURABAYA 25 Januari 2010
Taufiqurrahman NRP. 2208 205 716
Seminar Thesis
REKONSTRUKSI PERMUKAAN TIGA DIMENSI AREA POINT CLOUDS DENGAN ALGORITMA TRIANGULASI DELAUNAY
OUTLINE IDEA
1. Pendahuluan a. Latar Belakang b. Perumusan Masalah c. Tujuan dan Manfaat Penelitian
2. Kajian Pustaka dan Dasar Teori 3. Metode Penelitian 4. Hasil dan Pembahasan 5. Kesimpulan 25 Jan 2010
GameTech'08
2
PENDAHULUAN 1. Latar Belakang 2. Perumusan Masalah 3. Tujuan dan Manfaat Penelitian
Latar Belakang • Data tiga dimensi (3D) bisa disajikan dimana dalam mempresentasikan suatu model. Informasi objek 3D merupakan hal yang sangat diperlukan dalam suatu proses kerja seperti navigasi, target recognition dan identifikasi. Pada faktanya, sekumpulan titik atau vertex - point clouds merupakan salah satu bentuk sederhana – primitive yang menjadikan fundamental bentuk representasi objek 3D . • (Sorkine, 2006), (Sorkine, et al., 2007) dan (Sapiro, et al., 2008). 25 Jan 2010
GameTech'08
4
Latar Belakang (cont’d - 1) • Mengusulkan suatu gabungan sistem rekonstruksi permukaan 3D: – Pembentukan model berdasarkan informasi Verteks atau Point Clouds – Tehnik sistem triangulasi – Pembentukan Mesh yang terakuisisi • Legalitas triangulasi • Kualitas Mesh
25 Jan 2010
GameTech'08
5
Perumusan Masalah • Masalah yang dihadapi pada sistem rekonstruksi permukaan 3D adalah sbb : 1. Proses menjalin suatu tautan antar titik pada bidang tiga dimensi, dalam hal ini proses tersebut menggunakan metode Delaunay Triangulasi dan voronoi. 2. Bagaimana menerapkan algoritma sistem triangulasi agar bisa melakukan rekontruksi permukaan tiga dimensi suatu model objek ? 3. Legalisasi dalam kriteria triangulasi dalam hal ini pada delaunay triangulasi. 25 Jan 2010
GameTech'08
6
Penelitian Camera Calibration Motion Capture Pose Estimation
Surface Reconstruction Deformation 25 Jan 2010
GameTech'08
7
Tujuan dan Manfaat Penelitian • Tujuan 1. Mendapatkan metode sistem algoritma triagulasi 2. Menganalisa metode triangulasi yang didapat dengan metode lain. 3. Dihasilkannya sebuah analisis unjuk kerja sistem triangulasi yang ditawarkan yaitu dalaunay triangulasi.
• Manfaat – Munculnya suatu optimasi dalam reka bentuk permukaan tiga dimensi dari sekumpulan point sets yang ada. 25 Jan 2010
GameTech'08
8
Kajian Pustaka dan Dasar Teori
Kajian Pustaka dan Dasar Teori Triangulasi Delaunay (Detri) banyak digunakan untuk keperluan rekonstruksi obyek, baik D2 maupun D3. Sedemikian populernya, sehingga banyak metode Detri yang dihasilkan oleh para peneliti Su dan Drysdale, Mei, 2005. Metode-metode tersebut menjadi tiga kelompok yaitu : 1. Konstruksi bertambah (incremental construction) 2. Penyisipan bertambah (incremental insertion atau on-line) 3. Pembagi bertahap (divide-and-conquer) 25 Jan 2010
GameTech'08
10
Kajian Pustaka dan Dasar Teori • Triangulasi – Triangulasi adalah suatu metode pembangkitan jalinan segitiga dan pola reka bentuk mesh. Dimana jalinan tersebut terdapat sekumpulan titik-titik yang membentuk pola. Untuk menggunakan mesh yang menerapkan triangulasi langkah pertama yang dilakukan adalah mengikuti aturan dan struktur vertek. – Triangulation T dari dua dimensi ataupun dengan ordo lebih Rn dimana n adalah dimensi ordo menurut Henrik Zimmer, 2005. • Setiap bagian dari triangulasi saling terkait oleh salah satu bagian triangulasi yang lain atau tidak sama sekali • Setiap batas di sekumpulan pada Rn saling berpotongan hanya terbatas pada bagian triangulasi di T 25 Jan 2010
GameTech'08
11
Kajian Pustaka dan Dasar Teori • Model Permukaan Tiga Dimensi – Permukaan 3 dimensi dibentuk oleh beberapa titik dengan beberapa metode. – Tiga titik dihubungkan dengan tiga garis (edge) yang berturut – turut sehingga membentuk sebuah segitiga (triangle). – Beberapa model dibentuk dengan beberapa cara seperti Delaunay Triangulation versi Constrained Delaunay Triangulation untuk proses lebih lanjut dari optimasi terhadap waktu keputusan dalam tautan (de Gambar 1 Aguiar, et al., 2008). Dataset Stanford Bunny yang berupa point clouds (kiri) dan Hasil dari rekonstruksi permukaan 3D (kanan). Foto sumber (de Aguiar, et al., 2008) 25 Jan 2010
GameTech'08
12
Kajian Pustaka dan Dasar Teori • Model Tiga Dimensi – Wireframe – Rekonstruksi permukaan yang berasal dari point clouds – grafik berdasarkan point sets, dan reverse aplikasi engineering dimana persebaran point clouds dari suatu permukaan memerlukan perubahan yang sesuai (Alliez, et al., 2007). Gambar 2 Transformasi dari Point Clouds ke bentuk preSurface Reconstruction (wireframe)
Surface Reconstruction Algorithm
25 Jan 2010
GameTech'08
13
Kajian Pustaka dan Dasar Teori Aproksimasi Diagram Voronoi Sekumpulan set point P = {p1, p2, ... ,pn} pada bidang Rn
pada kasus ini adalah 2D. Maka diagram voronoi V atau (P) adalah bagian dari Rn ke dalam n daerah polyhedral. Setiap daerah diketahui sebagai sel voronoi yang didenotasikan vo(p) saling melingkupi dan berhubungan satu dengan lainnya pada tiap n point. Masing-masing point yang berdekatan tersebut ditarik garis tegak lurus. (Aurenhanmer,1991) Gambar 3 Voronoi dua dimensi dengan 5 vertek
25 Jan 2010
GameTech'08
14
Kajian Pustaka dan Dasar Teori Aproksimasi Diagram Voronoi (lanjutan)
– Lebih tepatnya dengan vo(p) menjadi sel voronoi setiap point P dan set S dari setiap point sebagai berikut : – Dimana dist adalah fungsi euclidian distance
25 Jan 2010
GameTech'08
15
Kajian Pustaka dan Dasar Teori • Triangulasi Delaunay – Triangulasi Delaunay Del(P) pada sekumpulan vertek P = {p1, p2, ... ,pn} dikenalkan oleh Delaunay pada tahun 1934 yang sangat berguna ketika ada pekerjaan yang berkaitan dengan mesh. – Keuntungan utama dari triangulasi delaunay ini adalah memaksimalkan dengan membuat sudut minimum diantara semua triangulasi yang terbentuk oleh sekumpulan vertek. Gambar 4 Triangulasi vertek
25 Jan 2010
GameTech'08
Delaunay
16
dari
5
Kajian Pustaka dan Dasar Teori • Triangulasi Delaunay (lanjutan-1) Dengan Adanya keuntungan dari Delaunay maka memunculkan suatu kriteria dalam triangulasi: 1. Tidak diijinkan ada vertek di dalam lingkran tersebut. 2. Minimal terbentuk triangulasi dalam satu lingkaran. 3. Meskipun terbentuk triangulasi tetapi ada vertek independen di dalam lingkaran maka masih belum dikategorikan delaunay. 25 Jan 2010
GameTech'08
17
Kajian Pustaka dan Dasar Teori • Triangulasi Delaunay (lanjutan-2) – Kriteria dari Triangulasi Delaunay di deskripsikan sbb:
Gambar 5 Triangulasi Delaunay menurut kriteria delaunay pada gambar abjad D 25 Jan 2010
GameTech'08
18
Kajian Pustaka dan Dasar Teori • Triangulasi Delaunay (lanjutan-3) – Sehingga setiap triangulasi yang dihasilkan akan mendapatkan proses legalisasi untuk kriteria tersebut.
Gambar 6 Triangulasi Delaunay pada suatu bidang yang dinampakkan sekumpulan lingkaran yang menyatakan kriteria delaunay 25 Jan 2010
GameTech'08
19
Kajian Pustaka dan Dasar Teori • Dualitas Voronoi dan Delaunay - Henrik Zimmer’05 – Berdasarkan kajian pustaka voronoi dan delaunay sebelumnya, terdapat hubungan keduanya, yaitu: • pusat lingkaran triangulasi terpusat di vertek voronoi pada vertek v. • vertek sesungguhnya p,q,r saling berpotongan pada lingkaran yang terbentuk secara triangulasi.
Gambar 7 Dualitas voronoi dan Delaunay
25 Jan 2010
GameTech'08
20
Metode penelitian
Metode Penelitian • Studi Literatur – Proses pengumpulan landasan teori dan kajian pustaka. Pustaka yang dikumpulkan berupa paper, artikel jurnal, buku, tutorial, maupun internet.
• Rekayasa pembuatan dataset titik-titik model pada bidang D2 dan selanjutnya pada bidang D3 • Merancang dan membangun suatu algoritma yang dapat membentuk jaring-jaring dari diagram voronoi • Merancang dan membangun dari algoritma delaunay triangulasi • Evaluasi algoritma triangulasi untuk rekonstruksi permukaan D3 25 Jan 2010
GameTech'08
22
Diagram Penelitian Literatur
Studi Literatur
Representasi Objek 3D
REKONSTRUKSI PERMUKAAN TIGA DIMENSI
Model 3D Titik-titik Awan
Start Tidak
Optional
Ya
Test
Metode Traingulasi
Node ? Threshold ? Radius ?
Clustering
QHull
Delaunay dan Voronoi
Kriteria Detri ?
Tidak
Keluaran
Ya
25 Jan 2010
Model 3D FINAL GameTech'08
Finish
23
Metode Penelitian • Pembuatan Model Tiga Dimensi – Generator menghasilkan model 2D dan 3D secara random
25 Jan 2010
GameTech'08
24
Metode Penelitian • Penerapan algoritma untuk voronoi 3D – Definisikan sumbu Z=0, shg mendapati model menjadi 2D pada kondisi X,Y saja. – Setelah proses voronoi selesai kembali nilai Z masing-masing point clouds.
25 Jan 2010
GameTech'08
25
Metode Penelitian • Penerapan algoritma untuk triangulasi delaunay 3D – Triangulasi Delaunay 2D dapat di intepretasikan ke dalam 3D pada bidang tertentu misalnya paraboloid dimana, • f(x,y) = (x, y, x2 + y2)
– Dan menggunakan kalkulasi convex hull
25 Jan 2010
GameTech'08
26
Metode Penelitian • Penerapan algoritma untuk triangulasi delaunay 3D (lanjutan-1) – Kalkulasi convex hull pada bidang paraboloid
25 Jan 2010
GameTech'08
27
Metode Penelitian • Evaluasi Algoritma Triangulasi – Berdasarkan Teorema Thale legalitas Delaunay perlu divalidasikan – Misalkan L adalah lingkaran, l adalah garis yang memotong L pada a dan b, dan p,q,r, dan s adalah titik-titik yang terletak pada sisi yang sama dari l, dalam hal ini semua titik berada di sebelah atas l. Misalkan p dan q berada pada L, r di dalam L, dan s diluar L, maka: • sudut arb > sudut apb = sudut aqb > sudut asb
25 Jan 2010
GameTech'08
28
Metode Penelitian • Evaluasi Algoritma Delaunay (lanjutan-1) – Jika xi, xj, xk, xl adalah titik-titik yang membentuk segiempat dan ada salah satu titik yang terletak di dalam lingkaran, sementara tiga titik lainnya berada pada lingkaran yang sama, maka pasti ada salah satu sisi pembentuk segitiga xixj atau xkxl yang ilegal.
25 Jan 2010
GameTech'08
29
1. 2. 3. 4.
Uji Model Uji Simplifikasi Uji Triangulasi Delaunay Bidang Planar (2D) Uji Triangulasi Delaunay Bidang Paraboloid (3D) a. b.
Uji Kinerja Convex Hull Uji Model 3D i. Data Acak Uniform terkondisi ii. Data Model 3D yang sudah ada
5. Analisa Hasil Uji
Hasil dan pembahasan
Uji Model • Algoritma pada penelitian ini diujicobakan pada Notebook Personal Computer Intel Core 2 Duo 2GHz dengan memori 2GB. Sistem operasi yang dipakaikan untuk pengujian adalah Windows XP Service Pack 2. Algoritma dibangun dengan Matlab dan visualisasi dua dimensi dan tiga dimensi pun juga dibangun dengan menggunakan Matlab. 25 Jan 2010
GameTech'08
31
Uji Model • Pembangkitan model secara acak membentuk ruang tertentu.
• Menggunakan model tiga dimensi yang sudah ada baik terbuka maupun tertutup.
25 Jan 2010
GameTech'08
32
Uji Simplifikasi • Bertujuan untuk menyederhanakan vertek dari Point Clouds • Dengan menggunakan euclidian distance dan pembacaan index vertex model dari OFF file • Didapatkan empat konfirgurasi proses simplifikasi
25 Jan 2010
GameTech'08
33
Uji Simplifikasi
25 Jan 2010
GameTech'08
34
Uji Simplifikasi 12
Waktu (detik)
10 8 Simplifikasi 1
6
Simplifikasi 2
4
Simplifikasi 3
2
Simplifikasi 4
0 100
1000
10000
100000
CARA
Banyaknya Data
0.07 0.06 Waktu (detik)
LAMA (detik)
0.05
DATA 100
0.05769
0.47483
10.56825
2
0.00089
0.00161
0.00630
0.06514
3
0.00041
0.00180
0.00235
0.03223
4
0.00050
0.00060
0.00143
0.00929
Simplifikasi 3 Simplifikasi 4
0.01 0 100
1000
10000
100000
Banyaknya Data
25 Jan 2010
100000
0.01127
Simplifikasi 2
0.02
10000
1
0.04 0.03
1000
GameTech'08
35
Uji Triangulasi Delaunay2D
Item (a) (b)
25 Jan 2010
Penjelasan -Delaunay 2D dengan 40 vertek selama : 0.00239 detik -Print Edge Delaunay 2D dengan 67 edge selama : 0.01733 detik -Delaunay 2D dengan 40 vertek selama : 0.00253 detik -Voronoi 2D dengan 107 vertek selama : 0.00086 detik
GameTech'08
36
Uji Triangulasi Delaunay2D
Metode Delaunay Voronoi 25 Jan 2010
Uji Delaunay 2D dengan 40 vertek Edge Delaunay 2D dengan 69 edge Voronoi 2D dengan 108 vertek
Total waktu traingulasi Delaunay 2D
GameTech'08
Waktu (detik) 0.00247 0.0179 0.00074
0.02111 37
Uji Kinerja Convex Hull Filter vertel dalam
Vertek Hilang sementara
Step 1
Vertek muncul kembali
Hasil Convex Hull
25 Jan 2010
GameTech'08
38
Uji Kinerja Convex Hull VERTEK 100000 177828 316228 562342 1000000
25 Jan 2010
LAMA (detik) CONVHULL CONHULL2D 0.01 0.11 0.02 0.2 0.03 0.38 0.06 0.69 0.1 1.27
GameTech'08
39
Uji Tringulasi Bidang Paraboloid 3D • Coba01.off Koordinat
1
x y z
25 Jan 2010
2 0 0 0
3 1 0 0
1 0 1
Vertek 4 5 6 0 0 1 0 1 1 1 0 1
7 0 1 1
8 0.9 0.1 0.1
9 0.5 0.5 0.5
-jumlah vertek yg dibaca oleh OFF 9 vertek selama : 0.00097 s -Delaunay 2D dengan 9 vertek selama : 0.00109 s -Delaunay 3D dengan 9 vertek selama : 0.00109 s
GameTech'08
40
Uji Tringulasi Bidang Paraboloid 3D • Coba02.off Koordinat x y z
Vertek 1 2 3 4 5 6 7 8 9 10 0 1 0 1 0.5 0.1 0.5 0.9 0.25 0.75 0 0 1 1 0.5 0.1 1 0.1 1 1 0 0 0 0 0 0.1 1 0.1 0.25 0.25
25 Jan 2010
11 0.5 1.5 0.5
-jumlah vertek yg dibaca oleh OFF 11 vertek selama : 0.00107 s -Delaunay 2D dengan 11 vertek selama : 0.00106 s -Delaunay 3D dengan 11 vertek selama : 0.00107 s
GameTech'08
41
Uji Tringulasi Bidang Paraboloid 3D • nefertiti.off
(a) Facet Asli
(b) Delaunay2D
(c) Delaunay3D
- Delaunay 2D input = 299 vertek, output = 568 facet selama : 0.00917 s - Delaunay 3D input = 299 vertek, output = 1629 facet selama : 0.02881 s 25 Jan 2010
GameTech'08
42
Uji Tringulasi Bidang Paraboloid 3D • nefertiti.off Pada gambar (a) merupakan hasil facet sebagai acuan. Ternyata output Detri ada perbedaan di sisi hidung di gambar (b). Dari referensi facet yang dipunyai dari Nefertiti asli sebanyak 562 facet.
(a) Facet Asli 25 Jan 2010
(b) Facet Delaunay2D GameTech'08
43
Uji Tringulasi Bidang Paraboloid 3D • nefertiti-entire.off -Facet Asli = 1252 facet -Delaunay 2D input = 654 vertek, output = 1283 facet selama : 0.02037 s -Delaunay 3D input = 654 vertek, output = 4056 facet selama : 0.07576 s
25 Jan 2010
(a) Facet Asli
(b) Delaunay2D
(c) Delaunay3D 44
GameTech'08
Uji Tringulasi Bidang Paraboloid 3D • beetle.off -Facet Asli = 1763 facet -Delaunay 2D input = 988 vertek, output = 1934 facet selama : 0.03143 s -Delaunay 3D input = 988 vertek, output = 5218 facet selama : 0.10588 s
(a) Facet Asli
25 Jan 2010
(b) Delaunay2D
(c) Delaunay3D
GameTech'08
45
Analisa Model 3D Open Surface TRIANGULASI DELAUNAY MODEL
PENJELASAN KETERANGAN KETERANGAN 2D 3D
2D
3D
NEFERTITI
TRUE
FALSE
Perubahan pada hidung
gagal rekonstruksi
NEFERTITI-ENTIRE
FALSE
FALSE
berubah, kecuali pada dahi dalam
gagal rekonstruksi
BEETLE
FALSE
FALSE
gagal
gagal rekonstruksi
MODEL
MODEL ASLI JUMLAH JUMLAH VERTEK FACET
HASIL DELAUNAY
WAKTU
JUMLAH FACET (2D)
JUMLAH FACET (3D)
2D
3D
NEFERTITI
299
562
568
1629
0.00917
0.02881
NEFERTITIENTIRE
654
1252
1283
4056
0.02037
0.07576
BEETLE
988
1763
1934
5218
0.03143
0.10588
25 Jan 2010
GameTech'08
46
Kesimpulan
Kesimpulan • Fungsi triangulasi dengan menggunakan metode delaunay ini dibuat dua fungsi pada penelitian ini yaitu Delaunay 2D dan Delaunay 3D. • Tahapan-tahapan rekonstruksi permukaan di buat dua tahap yaitu : – Rekonstruksi permukaan pada model 2D – Dan, rekonstruksi permukaan pada model 3D
• Simplifikasi efektif terhadap model yaitu cara 4 namun tidak terhadap waktu. • Uji triangulasi 2D dan 3D berjalan 100% tanpa memperhatikan sudut minimal pada segitiga. • Model lebih efektif menggunakan open surface pada uji model. Namun menyebabkan pertambahan facet, yaitu – Delaunay2D = 91.15% hingga 98.94% valid (penilaian secara visual facet) – Delaunay 3D = 33.78% hingga 34.49% valid (penilaian secara visual facet) 25 Jan 2010
GameTech'08
48
