UNIVERSITAS BINA NUSANTARA Jurusan Teknik Informatika Skripsi Sarjana Komputer Semester Ganjil tahun 2003/2004
ANALISIS DAN PERANCANGAN APLIKASI PENGENAL DAN PENGHITUNG POLIGON MENGGUNAKAN ARTIFICIAL NEURAL NETWORKS METODE BACKPROPAGATION Dwirani Novianti Ferry Eka Kurniadi
0400486433 0400499745 0400528442
Abstrak Poligon sebagai satuan terkecil ketiga dari bangun ruang setelah titik dan garis. Pengenalan bangun ruang menggunakan komputer merupakan masalah yang kompleks, sama halnya dengan pengenalan objek lainnya seperti pengenalan sidik jari, suara, retina, tulisan tangan, tanda tangan, karakter, dan sebagainya. Untuk itu diperlukan suatu algoritma untuk melakukan pengenalan dan perhitungan jumlah poligon. Proses pengenalan objek secara umum terdiri atas tiga tahap, yaitu image processing, feature extraction, dan recognition. Image processing menggunakan algoritma SUSAN (Smallest Univalue Segment Assimilating Nucleus) Corner Detection, dan SUSAN Edge Detection. Feature extraction dengan mengambil besar sudut dalam poligon menggunakan perhitungan matematis dan algoritma Graham Scan juga perbandingan sisi dari poligon. Recognition menggunakan ANN (Artificial Neural Networks/Jaringan Saraf Tiruan) dengan metode backpropagation (propagasi balik). Aplikasi yang dibuat dapat mengenali bentuk-bentuk poligon dan menghitung jumlah masing-masingnya dengan kecepatan dan keakuratan tinggi. Penggunaan ANN dengan metode backpropagation memberikan kecepatan dan keakuratan tinggi pada proses pengenalan poligon walaupun memerlukan waktu yang relatif lama pada proses training–nya (pembelajarannya). Algoritma SUSAN memberikan keakuratan tinggi pada proses pendeteksian sudut dan pendeteksian sisi dari poligon. Feature extraction dengan mengambil besar sudut dalam dan perbandingan sisi dari poligon sudah mewakili keunikan dari setiap poligon. Kata Kunci pengenalan poligon, penghitung poligon, artificial neural networks, jaringan saraf tiruan, backpropagation, propagasi balik Abstrak
v
PRAKATA Prakata
Puji syukur kepada Tuhan Yang Maha Esa atas berkat dan bimbingan-Nya sehingga penulis dapat menyelesaikan skripsi yang berjudul “ANALISIS DAN PERANCANGAN APLIKASI PENGENAL DAN PENGHITUNG POLIGON MENGGUNAKAN
ARTIFICIAL
NEURAL
NETWORKS
METODE
BACKPROPAGATION” dengan baik. Skripsi ini merupakan salah satu syarat untuk menyelesaikan jenjang pendidikan Strata-1 di Universitas Bina Nusantara, Jakarta dan ditujukan bagi pengembangan Ilmu Pengetahuan dan Teknologi Indonesia. Penulis mengucapkan terima kasih kepada pihak-pihak yang telah berperan dalam penyelesaian skripsi ini: 1. Orang tua dan wali, yang telah memberikan dukungan moril maupun materiil dalam proses perkuliahan sampai tersusunnya skripsi ini. 2. Bapak Januar Wahjudi, S.Kom., M.Sc. selaku dosen pembimbing, yang telah membantu dalam memberikan bimbingan, ide-ide, dan solusi dari masalahmasalah yang ditemukan selama proses penyusunan skripsi ini. 3. Ibu Anny Tandyo, S.Kom., M.Sc., yang telah meluangkan waktunya untuk memberikan penjelasan tentang materi yang diperlukan dalam penyusunan skripsi ini. 4. Rekan-rekan di UPTPL Universitas Bina Nusantara khususnya Fredy Muliono, Chandra Adi Mulya, Joko Sunarya, Andoko, Robert Fransetya Purba, Robert, Samuel Heriyanto, Mulyanto, Ricky, Andreanes Yosef Vanderlee yang telah membantu dalam pemecahan masalah yang dihadapi selama perancangan vi
aplikasi yang dibuat, juga rekan-rekan lain yang memberikan dukungan dan semangat. 5. Ibu Dyah Budiastuti, Ir., MM dan Heriawan yang telah memberikan bantuan sarana dalam penyusunan skripsi ini. 6. Marsella Triwahyuni dan Erwin Susanto yang telah memberikan dukungan dan semangat selama proses penyusunan skripsi. 7. Ibu DR Th. Widia S. selaku rektor Universitas Bina Nusantara. 8. Bapak Ir. Harjanto Prabowo, MM selaku dekan Fakultas Ilmu Komputer. 9. Bapak Ir.
Sablin Yusuf, M.Sc., M.CompSc. selaku kepala jurusan Teknik
Informatika dan koordinator bidang ilmu Intelligent Systems. 10. Dan pihak-pihak lain yang tidak dapat disebutkan satu per satu yang telah memberikan bantuan secara langsung maupun tidak langsung dalam proses penyusunan skripsi ini. Penulis menyadari akan keterbatasan kemampuan dan pengetahuan yang dimiliki. Oleh karena itu, saran dan kritik yang membangun sangat diharapkan untuk penyempurnaan skripsi ini. Akhir kata, semoga skripsi ini dapat memberikan manfaat kepada semua pihak yang memerlukannya, juga memberikan sumbangsih kepada kemajuan Ilmu Pengetahuan dan Teknologi Indonesia.
Jakarta, Juni 2004 Penulis
vii
DAFTAR ISI Daftar Isi
Halaman Judul Luar ........................................................................................................i Halaman Judul Dalam.................................................................................................... ii Halaman Persetujuan Hardcover................................................................................. iii Halaman Pernyataan Dewan Penguji ...........................................................................iv Abstrak..............................................................................................................................v Prakata.............................................................................................................................vi Daftar Isi ....................................................................................................................... viii Daftar Tabel.................................................................................................................. xiii Daftar Gambar ...............................................................................................................xv Daftar Lampiran ........................................................................................................ xviii BAB 1 PENDAHULUAN ................................................................................................1 1.1 Latar Belakang .........................................................................................................1 1.2 Ruang Lingkup.........................................................................................................2 1.3 Tujuan dan Manfaat .................................................................................................3 1.4 Metodologi Penelitian ..............................................................................................3 1.5 Sistematika Penulisan ..............................................................................................4 BAB 2 LANDASAN TEORI ...........................................................................................5 2.1 Teori Pengenalan Objek...........................................................................................5 viii
2.1.1 Teori Pengenalan Objek pada Manusia.............................................................5 2.1.2 Batasan Pengenalan Objek................................................................................6 2.2 Model Warna RGB ..................................................................................................8 2.3 Image........................................................................................................................9 2.3.1 Pengertian Image...............................................................................................9 2.3.2 Pengertian Pixel ................................................................................................9 2.3.3 Image Bitmap ..................................................................................................10 2.3.4 Format Pixel 24-Bit .........................................................................................10 2.4 Image Processing ...................................................................................................11 2.4.1 Grayscaling.....................................................................................................11 2.4.2 Corner Detection.............................................................................................12 2.4.3 Edge Detection ................................................................................................12 2.5 Prinsip SUSAN ......................................................................................................13 2.6 Feature Extraction .................................................................................................15 2.7 Poligon ...................................................................................................................16 2.8 Convex Hull............................................................................................................17 2.9 Graham’s Scan .......................................................................................................17 2.10 Algoritma Midpoint..............................................................................................18 2.11 Artificial Neural Networks ...................................................................................21 2.11.1 Cara Kerja Neural Network...........................................................................24 2.11.2 Arsitektur Neural Network............................................................................24 2.11.3 Training.........................................................................................................26 2.11.4 Activation Function.......................................................................................26 2.11.5 Backpropagation...........................................................................................27 ix
2.11.5.1 Arsitektur Neural Network Metode Backpropagation...........................28 2.11.5.2 Tahapan Training Backpropagation ......................................................29 2.11.5.3 Algoritma Training Backpropagation ...................................................30 2.11.6 Inisialisasi Nguyen–Widrow.........................................................................32 BAB 3 ANALISIS DAN PERANCANGAN.................................................................33 3.1 Gambaran Permasalahan Secara Umum ................................................................33 3.2 Kebutuhan Sistem dan Pemenuhan Kebutuhan Sistem .........................................35 3.3 Alur Program Secara Umum..................................................................................35 3.4 Image Processing ...................................................................................................38 3.4.1 Grayscaling.....................................................................................................38 3.4.2 Corner Detection.............................................................................................40 3.4.3 Edge Detection ................................................................................................41 3.5 Polygon Extraction.................................................................................................42 3.6 Menentukan Arah Poligon .....................................................................................46 3.7 Feature Extraction .................................................................................................48 3.7.1 Pengambilan Besar Sudut Dalam dari Poligon ...............................................48 3.7.2 Pengambilan Perbandingan Sisi Poligon ........................................................57 3.8 Insert Pola Poligon.................................................................................................59 3.9 Training Pola Poligon ............................................................................................60 3.10 Recognition and Counting Poligon ......................................................................60 3.11 Perancangan Interface Aplikasi ...........................................................................62 BAB 4 IMPLEMENTASI DAN EVALUASI ..............................................................65 4.1 Implementasi ..........................................................................................................65 x
4.1.1 Spesifikasi Sistem ...........................................................................................65 4.1.1.1 Spesifikasi Perangkat Keras.....................................................................65 4.1.1.2 Spesifikasi Perangkat Lunak ....................................................................65 4.1.2 Prosedur Operasional ......................................................................................66 4.1.2.1 Cara Menjalankan Aplikasi......................................................................66 4.1.2.2 Cara Insert Pola........................................................................................67 4.1.2.3 Cara Training Pola ...................................................................................72 4.1.2.4 Cara Recognizing and Counting Poligon .................................................74 4.2 Evaluasi ..................................................................................................................75 4.2.1 Evaluasi Kecepatan Training ..........................................................................75 4.2.1.1 Pengaruh Jenis Activation Function.........................................................76 4.2.1.1.1 Penggunaan Binary Sigmoid .............................................................76 4.2.1.1.2 Penggunaan Bipolar Sigmoid............................................................78 4.2.1.2 Pengaruh Inisialisasi Nguyen-Widrow ....................................................81 4.2.1.2.1 Penggunaan Bipolar Sigmoid dengan Target -1 dan 1......................82 4.2.1.2.2 Penggunaan Bipolar Sigmoid dengan Target -0.8 dan 0.8................83 4.2.1.3 Pengaruh Banyaknya Unit pada Suatu Hidden Units ..............................85 4.2.2 Evaluasi Kecepatan Recognition and Counting..............................................88 4.2.2.1 Evaluasi Kecepatan Recognition and Counting dengan Data Training...89 4.2.2.2 Evaluasi Kecepatan Recognition and Counting dengan Data Non Training................................................................................................................90 4.2.3 Evaluasi Keakuratan Recognition and Counting ............................................91 4.2.3.1 Evaluasi Tingkat Keakuratan Recognition and Counting dengan Data Training................................................................................................................92 xi
4.2.3.2 Evaluasi Tingkat Keakuratan Recognition and Counting dengan Data Non Training ........................................................................................................94 4.2.4 Hasil Evaluasi .................................................................................................95 BAB 5 SIMPULAN DAN SARAN................................................................................97 5.1 Simpulan ................................................................................................................97 5.2 Saran.......................................................................................................................98 Daftar Pustaka................................................................................................................99 Riwayat Hidup..............................................................................................................101 Lampiran ....................................................................................................................... L1
xii
DAFTAR TABEL Daftar Tabel
Tabel 3.1 Struktur Tabel yang Digunakan sebagai Data Store........................................59 Tabel 4.1 Parameter Training untuk Percobaan Pengaruh Jenis Activation Function Terhadap Kecepatan Training..................................................................................76 Tabel 4.2 Kecepatan Training Menggunakan Binary Sigmoid........................................78 Tabel 4.3 Kecepatan Training Menggunakan Bipolar Sigmoid.......................................80 Tabel 4.4 Perbandingan Kecepatan Training Antara Bipolar Sigmoid dan Binary Sigmoid.....................................................................................................................81 Tabel 4.5 Parameter Training untuk Percobaan Pengaruh Inisialisasi Nguyen-Widrow Terhadap Kecepatan Training..................................................................................81 Tabel 4.6 Hasil Percobaan Pengaruh Penggunaan Inisialisasi Nguyen-Widrow Terhadap Kecepatan Training dengan Target -1 dan 1............................................................82 Tabel 4.7 Hasil Percobaan Pengaruh Penggunaan Inisialisasi Nguyen-Widrow Terhadap Kecepatan Training dengan Target -0.8 dan 0.8......................................................84 Tabel 4.8 Parameter Training untuk Percobaan Pengaruh Banyaknya Unit pada Suatu Hidden Units Terhadap Kecepatan Training ...........................................................86 Tabel 4.9 Hasil Percobaan Pengaruh Banyaknya Unit pada Suatu Hidden Units Terhadap Kecepatan Training..................................................................................87 Tabel 4.10 Parameter Training untuk Percobaan Tingkat Kecepatan dan Keakuratan Recognition and Counting........................................................................................89 Tabel 4.11 Hasil Percobaan Kecepatan Recognition and Counting untuk Data Training ..................................................................................................................................89 xiii
Tabel 4.12 Hasil Percobaan Kecepatan Recognition and Counting untuk Data Non Training....................................................................................................................90 Tabel 4.13 Hasil Percobaan Tingkat Keakuratan Recognition and Counting untuk Data Training....................................................................................................................92 Tabel 4.14 Hasil Percobaan Tingkat Keakuratan Recognition and Counting untuk Data Non Training ............................................................................................................94
xiv
DAFTAR GAMBAR Daftar Gambar
Gambar 2.1 Rotational Invariance.....................................................................................6 Gambar 2.2 Size Invariance ...............................................................................................7 Gambar 2.3 Translational Invariance................................................................................7 Gambar 2.4 Model Warna RGB.........................................................................................8 Gambar 2.5 Nilai Grayscale pada Adobe Photoshop ......................................................11 Gambar 2.6 Posisi Circular Mask pada Image Sederhana...............................................14 Gambar 2.7 Posisi Pixel Penyusun Circular Mask pada Image.......................................15 Gambar 2.8 Convex Hull..................................................................................................17 Gambar 2.9 Neural Network Sederhana ..........................................................................23 Gambar 2.10 Struktur Sebuah Neuron .............................................................................23 Gambar 2.11 Single Neural Net .......................................................................................25 Gambar 2.12 Multilayer Neural Net ................................................................................25 Gambar 2.13 Arsitektur Neural Network Metode Backpropagation...............................28 Gambar 3.1 Contoh Poligon Sejenis ................................................................................33 Gambar 3.2 Contoh Poligon Tak Sejenis.........................................................................34 Gambar 3.3 Flowchart Proses Insert Pola Poligon dan Proses Recognition and Counting Poligon .....................................................................................................................36 Gambar 3.4 Flowchart Proses Training Pola Poligon .....................................................37 Gambar 3.5 Flowchart Proses Grayscaling .....................................................................40 Gambar 3.6 Flowchart Proses Polygon Extraction..........................................................45 Gambar 3.7 Rancangan Interface Aplikasi ......................................................................62 xv
Gambar 4.1 Tampilan Awal DEF Polygon Recognizer and Counter (70%)...................67 Gambar 4.2 Tampilan Setelah Input Bentuk Poligon (70%) ...........................................68 Gambar 4.3 Tampilan Setelah Grayscaling (70%) ..........................................................69 Gambar 4.4 Tampilan Setelah Edge Detection (70%) .....................................................70 Gambar 4.5 Tampilan Window Insert to Pattern (70%) ..................................................71 Gambar 4.6 Hasil Penyimpanan Pola ..............................................................................72 Gambar 4.7 Tampilan Window Settings...........................................................................73 Gambar 4.8 Tampilan Window Training .........................................................................74 Gambar 4.9 Tampilan Hasil Recognizing and Counting .................................................75 Gambar 4.10 Grafik Hasil Percobaan Kecepatan Training Menggunakan Binary Sigmoid dengan Target Error 0.05.........................................................................................77 Gambar 4.11 Grafik Hasil Percobaan Kecepatan Training Menggunakan Binary Sigmoid dengan Target Error 0.025.......................................................................................77 Gambar 4.12 Grafik Hasil Percobaan Kecepatan Training Menggunakan Binary Sigmoid dengan Target Error 0.01.........................................................................................78 Gambar 4.13 Grafik Hasil Percobaan Kecepatan Training Menggunakan Bipolar Sigmoid dengan Target Error 0.05 ..........................................................................79 Gambar 4.14 Grafik Hasil Percobaan Kecepatan Training Menggunakan Bipolar Sigmoid dengan Target Error 0.025 ........................................................................79 Gambar 4.15 Grafik Hasil Percobaan Kecepatan Training Menggunakan Bipolar Sigmoid dengan Target Error 0.01 ..........................................................................80 Gambar 4.16 Grafik Perbandingan Kecepatan Training Tanpa dan Menggunakan Inisialisasi Nguyen-Widrow dengan Target -1 dan 1 ..............................................83
xvi
Gambar 4.17 Grafik Perbandingan Kecepatan Training Tanpa dan Menggunakan Inisialisasi Nguyen-Widrow dengan Target -0.8 dan 0.8 ........................................85 Gambar 4.18 Grafik Perbandingan Banyaknya Unit pada Suatu Hidden Units Terhadap Kecepatan Training..................................................................................................88
xvii
DAFTAR LAMPIRAN Daftar Lampiran
Lampiran 1 Training Pola 1 (75%) ................................................................................. L1 Lampiran 2 Training Pola 2 (75%) ................................................................................. L1 Lampiran 3 Training Pola 3 (75%) ................................................................................. L2 Lampiran 4 Training Pola 4 (75%) ................................................................................. L2 Lampiran 5 Training Pola 5 (75%) ................................................................................. L3 Lampiran 6 Tes Keakuratan dan Kecepatan 1 (75%) ..................................................... L3 Lampiran 7 Tes Keakuratan dan Kecepatan 2 (75%) ..................................................... L4 Lampiran 8 Tes Keakuratan dan Kecepatan 3 (75%) ..................................................... L4 Lampiran 9 Tes Keakuratan dan Kecepatan 4 (75%) ..................................................... L5 Lampiran 10 Tes Keakuratan dan Kecepatan 5 (75%) ................................................... L5 Lampiran 11 Tes Keakuratan dan Kecepatan 6 (75%) ................................................... L6 Lampiran 12 Tes Keakuratan dan Kecepatan 7 (75%) ................................................... L6 Lampiran 13 Tes Keakuratan dan Kecepatan 8 (75%) ................................................... L7 Lampiran 14 Tes Keakuratan dan Kecepatan 9 (75%) ................................................... L7 Lampiran 15 Tes Keakuratan dan Kecepatan 10 (75%) ................................................. L8 Lampiran 16 Bentuk Flowchart yang Digunakan........................................................... L9 Lampiran 17 Prinsip SUSAN (Edge Detection dan Corner Detection) ....................... L10
xviii
