Algoritma Warshall dan Algoritma Dijkstra - Matematika Diskrit

• Algoritma Warshall

      Algoritma Warshall memiliki input graf berarah dan berbobot (V,E), yang berupa daftar titik (node/vertex V) dan daftar sisi (edge E). Jumlah bobot sisi-sisi pada sebuah jalur adalah bobot jalur tersebut. Sisi pada E diperbolehkan memiliki bobot negatif, akan tetapi tidak diperbolehkan bagi graf ini untuk memiliki siklus dengan bobot negatif. Algoritma ini menghitung bobot terkecil dari semua jalur yang menghubungkan sebuah pasangan titik, dan melakukannya sekaligus untuk semua pasangan titik. Algoritma Warshall yang menerapkan pemrograman dinamis lebih  menjamin keberhasilanpenemuan solusi optimum untuk kasus penentuanlintasan terpendek (single pair shortest path).

      Contoh :

Dari Titik F Menuju Titik  C ada berapa cara :

(F – A – B – C) —>91Km

(F – A – D – C) —>107Km

(F – A – F – E – D – C) —>114Km

(F – A – F – E – D – C) —>114Km

(F – E – D – C) —>80Km

(F – E – D – C) —>80Km

Nah, dengan algoritma Warshall ini, kita dapat mendapatkan informasi yang sedemikian rupa untuk kita timbang dan menentukan jalur yang paling efisien.

Aplikasi dalam kehidupan sehari-hari :

Seperti kita berkunjung ke suatu tempat, pasti ada banyak pilihan jalan yang harus kita lalui, tergantung kita memilih dan memutuskan kita pilih mana. Tentu, kita akan memilih rute atau jalan yang lebih efesien “Biaya murah, cepat dan tidak terlalu repot”. 

• Algoritma Dijkstra

        Algoritma Dijkstra, dinamai menurut penemunya, Edsger Dijkstra, adalah sebuah algoritma rakus (greedy algorithm) dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot-bobot sisi (edge weights) yang bernilai tak-negatif.

Algoritma Dijkstra :

·      Tentukan u₀ paling kiri. Biasanya u₀ diberi tahu.

·      Lintasan berakhir paling ujung.

·      Lintasan atau busur yang dilalui tidak boleh membentuk cycle.

·      Harus berurutan pemberian labelnya pada tiap simpul.

·      Carilah busur dengan bobot yang paling minimum.

      Contoh 1.

Sekarang kita akan mencari jalur terpendek dari A ke C. Ada banyak sekali kemungkinan jalan yang bisa di tempuh

·    A – E – D – C

·    A – F – G – C

·    A – B – C

·    Dan rute/node2 lainnya.

Tapi sekarang kita akan mencari jalur terpendek, dengan cara membandingkan jarak atau ongkos/biaya yang terkecil.

Contoh 2.

Carilah lintasan terpendek dari u0 ke setiap simpul lainnya, dari graf di bawah ini !

Yaitu : Ketika kita memasak, maka kita perlu menyiapkan segala alat yang diperlu untuk di masak, nah disini kita belajar bagaimana ketika memasak tidak banyak memakan waktu yang lama dan efesien dan cepat dengan cara membandingkan dalam mengerjakan hal yang lebih dulu. Dan masih banyak aplikasinya yang boleh kita diterapkan dalam kehidupan kita sehari-hari.

Aplikasi dalam kehidupan sehari :

Yaitu : Ketika kita memasak, maka kita perlu menyiapkan segala alat yang diperlu untuk di masak, nah disini kita belajar bagaimana ketika memasak tidak banyak memakan waktu yang lama dan efesien dan cepat dengan cara membandingkan dalam mengerjakan hal yang lebih dulu. Dan masih banyak aplikasinya yang boleh kita diterapkan dalam kehidupan kita sehari-hari.

Reference :

Munir, Rinaldi,2005. Matematika Diskrit. Bandung: Informatika Bandung. http://www.scribd.com/doc/27745962/Microsoft-Access-2007,

http://gunadarmakalimalang.com. 

Kamayudi, Apri. 2006. Studi dan Implementasi Algoritma Djikstra, Bellman-Ford dan Floyd-Warshall dalam menangani masalah lintasan terpendek dalam Graf. Program Studi Teknik Informatika, Institut Teknologi Bandung. 

Luh Joni Erawati. 2008. “Pencarian Rute Terpendek Tempat Wisata di Bali dengan Menggunakan Algoritma Dijkstra”

http://www.ittelkom.ac.id/library/index.php?view=article&catid=20%3Ainformatika&id=161%3Aalgoritmadijkstr&option=com_content&Itemid=15 

http://www-b2.is.tokushimau.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml

https://wawanlaksito.files.wordpress.com/2012/01/graf2.pptx

Pengembangan Aplikasi Computer Vision untuk Pengamanan Kantin Kejujuran

• Penelitian

          Sistem ini yang dibuat dan dirakit berupa software Computer Vision dan hardware yang terdiri dari tempat dan pencacah koin, kamera webcam beserta penyangga yang dapat diatur jarak dan sudutnya, serta papan tempat meletakkan obyek makanan/ minuman.

    Software CV yang dikembangkan akan mendeteksi keberadaan orang/pembeli, menghitung perubahan jumlah obyek makanan/minuman, serta perubahan jumlah koin setiap kali mendeteksi keberadaan orang/pembeli pada Kantin Kejujuran serta merekam pembeli yang berlaku curang. Gambar 2 menunjukkan kerangka kerja dari software yang akan dikembangkan.

Akuisisi citra dilakukan dengan peralatan webcam yang dipasang tepat mengawasi area tempat menjual aneka makanan. Hasil akuisisi berupa rangkaian matriks 3 dimensi sebagai representasi frame-frame citra. 

Perbaikan citra dilakukan dengan operasi background subtraction sehingga diperoleh citra obyek yang terpisah dengan citra latar. Deteksi binary large object (BLOB) dilakukan dengan memeriksa citra BLOB untuk mencari setiap obyek (makanan/minuman, dan nilai angka pada pencacah koin).

Object counting dan tracking dilakukan untuk menghitung jumlah makanan atau minuman yang terambil serta nilai uang yang terbayar oleh seorang pembeli. Pada Kantin Kejujuran, posisi obyek makanan umumnya dalam formasi berjejer, saling berhimpit ganda, triple, kuartet, hingga berhimpit 20. Untuk itu digunakan pendekatan Artificial Neural Network (ANN) untuk pengenalan aneka formasi BLOB dari obyek makanan yang akan dihitung. Pada tahap pelatihan ANN, Input adalah fitur-fitur yang diperoleh dari BLOB beserta kondisi saat akuisisi citra yakni tingkat intensitas cahaya dan posisi (jarak dan sudut) obyek terhadap kamera. Sedangkan target dari ANN adalah jumlah item dalam BLOB. Untuk setiap jenis obyek makanan yang akan dihitung, disiapkan masing-masing seperangkat ANN yang dilatihkan supaya dapat mengenali aneka formasi BLOB. Penghitungan jumlah uang dilakukan dengan alat pencacah koin yang dapat membedakan jenis koin Rp 1000 dan Rp 500 (kuningan maupun almunium).

Perekaman pembeli yang (diduga kuat) berlaku curang dilakukan setelah menghitung nilai uang yang baru saja bertambah dibandingkan dengan jumlah obyek makanan yang berkurang. Jika nilai uang kurang dari yang seharusnya, maka beberapa frame daricitra yang diperoleh dari webcam lain (dipasang dalam posisi menghadap wajah pembeli) akan direkam.

• Hasil Dan Pembahasan

1.   Akuisisi Citra

        Untuk meningkatkan banyaknya jenis obyek yang dapat dikenali, dihitung, dan diawasi maka telah dibuat fasilitas yang memungkinkan area masing-masing obyek dapat dipartisi secara dinamis, dengn cara cropping untuk masing-masing obyek. Tampilan form untuk partisi dinamis ini

dinyatakan seperti gambar 3 berikut:

2. Perbaikan Citra dan Deteksi BLOB

          Terdapat 2 proses yang dilakukan dalam perbaikan citra, yakni: 1) Konversi dari citra RGB menjadi citra biner kemudian 2) Operasi morfologi. Konversi menjadi citra biner dilakukan untuk membedakan antara obyek dan latar. Operasi morfologi dilakukan untuk menghilangkan bingkai serta noise berupa obyek berukuran kecil.

Pada ini di atas terlihat adanya bingkai di kanan atas dari citra biner, serta bintik-bintik kecil disekitar obyek. Untuk itu dilakukan operasi morfologi penghilangan bingkai serta penghapusan obyek berukuran luas kurang dari 81 pixel.

          Tampilan form untuk perbaikan citra dan deteksi BLOB dinyatakan seperti pada gambar 5 berikut:

3. Data Dan Object Counting

         

          Untuk mengenali dan menghitung obyek berupa makanan/minuman yang dijual pada Kantin Kejujuran maka telah dikumpulkan data yang dideskripsikan dalam tabel 1 berikut:

v  Data Objek 1

Obyek 1 adalah jenis makanan berupa jajanan wafer merk “Ob1” yang terlihat pada gambar 6 berikut: 

Citra pada gambar di atas diambil pada jarak horizontal kamera-meja (Dx) 135 cm, jarak vertikal kamera-meja (Dy) 115 cm, sudut arah kamera terhadap garis vertikal (Sudut) 650, Intensitas cahaya 400 Lux. Terdapat 8 BLOB pada citra sebelah kanan dari gambar 6. BLOB di lajur kiri berisi jumlah item berturut-turut 1, 2, 3, dan 4. Sebagian data yang diperoleh dari formasi obyek pada gambar 6 di atas dinyatakan dalam tabel 2 berikut:

Agar sistem dapat mengenali dan menghitung jumlah obyek wafer merk “Ob1” maka diperlukan data-data pelatihan berbagai formasi BLOB dan jumlahnya.

4. Object Counting Dengan ANN

            Pendekatan ANN dipilih untuk pengenalan dan penghitungan jumlah obyek karena bersifat adaptive serta tidak mensyaratkan asumsi-asumsi yang ketat (dibanding pendekatan regresi). Arsitektur ANN yang digunakan adalah jaringan feedforward dengan jumlah neuron pada hidden layer sebanyak 41 sebagaimana disajikan dalam gambar 10 berikut:

Pada gambar diatas, bagian input adalah semua variabel (ada 17 variabel) selain item. ANN dilatih agar bagian output sama dengan item (sebagai target). Pada tahap pelatihan, digunakan berturut-turut 784 dan 297 data dari aneka formasi obyek 1 dan obyek 2. Kesesuain output ANN terhadap target setelah pelatihan untuk obyek 1 disajikan dalam gambar 11 berikut:

Nilai korelasi pada gambar 11 adalah 0,9999 atau R2 = 0,9998. Artinya setelah dilatih, ANN dapat menjelaskan/mengenali aneka formasi BLOB dari citra Obyek 1 (yang representasikan oleh input 17 variabel) sebesar 99,98 %.

Sedangkan hubungan antara target dan output untuk obyek 2, disajikan dalam gambar 12 berikut:

Nilai korelasi pada gambar 12 adalah 0,99957 atau R2 = 0,9991. Artinya setelah dilatih, ANN dapat menjelaskan/mengenali aneka formasi BLOB dari citra Obyek 2 (yang representasikan oleh input 17 variabel) sebesar 99,91 %. Pendekatan ANN yang digunakan dalam object counting terhadap obyek-obyek lainnya adalah sama dengan yang telah dijabarkan seperti halnya pada obyek1 dan obyek 2 tadi.

Referensi 

http://www.academia.edu/26223022/Pengembangan_Aplikasi_Computer_Vision_untuk_Pengamanan_Kantin_Kejujuran.

http://febripuguhpermana.blogspot.com/2011/03/konversi-color-space-rgb-hsv-dan-hsv.html.