Langsung ke konten utama

Random Sample Consensus (RANSAC) Algorithm

Random Sample Consensus (RANSAC) Algorithm

Algoritma RANSAC (Random Sample And Consensus) pertama kali diperkenalkan oleh Fischler dan Bolles di SRI International pada tahun 1981. Algoritma ini sebagai metode untuk estimasi parameter tertentu yang terkontaminasi oleh outlier (titik deviasi rata rata) dalam jumlah besar.

Dengan asumsi bahwa set ini berisi inliers, yaitu, poin yang kira-kira dapat dipasang ke baris, dan outlier, poin yang tidak dapat dipasang ke baris ini, sebuah metode kuadrat sederhana untuk mencocokkan baris pada umumnya akan menghasilkan garis dengan kecocokan yang buruk bagi inliers.


                                            (a)                                                               (b)
Gambar 1. Outlier

Keterangan:
Kumpulan Data Dengan Outlier Banyak.Yang Belum Dipasang (a), Kumpulan Data Setelah Proses RANSAC Outlier Tidak Berpengaruh Pada Hasil (b).
Pada RANSAC untuk mencapai hasil terbaik dilakukan dengan menentukan berapa banyak iterasi yang dilakukan, memilih subset acak dari data asli. Data-data ini merupakan inliers hipotetis dan hipotesis ini kemudian diuji sebagai berikut:
  1. Sebuah model dipasang ke inliers hipotetis, model dengan semua parameter yang bebas direkonstruksikan dari kumpulan data. 
  2. Semua data lain kemudian diuji terhadap model yang dipasang, dan jika titik cocok untuk model estimasi, tetap dianggap sebagai inlier hipotetis.
  3.  Estimasi model cukup baik jika cukup banyak poin yang diklasifikasi sebagai inliers hipotetis.
  4. Model ini reestimated dari semua inliers hipotetis, karena hanya diperkirakan dari inisial set inliers hipotetis.
  5.  Terakhir, model ini dievaluasi dengan memperkirakan kesalahan dari inliers relatif terhadap model.
Prosedur ini diulang beberapa kali, setiap kali menghasilkan model yang ditolak karena terlalu sedikit poin yang diklasifikasikan sebagai inliers. Dalam kasus terakhir, kita terus memperbaiki model jika kesalahan lebih kecil dibandingkan dengan model yang terakhir disimpan. Di bawah ini merupakan representasi hasil pencocokan titik yang menghasilkan inlier dengan metode RANSAC:



Gambar 2: inlier yang telah diperoleh menggunakan RANSAC

Secara garis besar, algoritma ini memiliki prosedur perhitungan sebagai berikut:
Gambar 2: inlier yang telah diperoleh menggunakan RANSAC

Secara garis besar, algoritma ini memiliki prosedur perhitungan sebagai berikut:
  1. Asumsikan titik data sejumlah n, yakni X = {x1, x2, ……..,xn}, di mana sebuah model relasi linier dari data tersebut dibuat dengan menggunakan setidaknya m titik, dimana m ≤ n. Untuk menghasilkan sebuah garis sempurna, setidaknya dibutuhkan 2 titik. 
  2. Mulai counter iterasi k = 1
  3. Pilih secara acak m buah data dari X, kemudian hitung sebuah model linier
  4. Untuk sebuah nilai toleransi ε dari model yang dihasilkan, tentukan seberapa banyak elemen X yang berada dalam nilai toleransi tersebut. Jika jumlah dari elemen-elemen ini melebihi sebuah nilai ambang batas t, maka hitung kembali model menggunakan titik-titik konsensus, kemudian hentikan algoritma.
  5. Naikan nilai counter menjadi k = k+1. Jika k < K, untuk sebuah nilai K yang ditentukan di awal perhitungan, maka ulangi langkah c. Apabila terjadi selainnya, maka terima hasil perhitungan model linier dengan jumlah titik-titik konsensus terbesar.
Pada algoritma RANSAC rumus umum untuk menghitung jumlah iterasi yang diperlukan, yakni:
Dengan:
K = jumlah iterasi yang diperlukan untuk menemukan model linier terbaik
M = jumlah titik data yang diperlukan untuk menghitung model linier
Q = jumlah inliers atau data yang berada di sekamir model
N = jumlah data keseluruhan
ξ = dibaca xi, yakni ration inliers terhadap seluruh data (Q/N)
ζ = dibaca zeta, yakni peluang RANSAC tidak menemukan solusi yang benar dan bisa diterima.

Gambar 3 sampai dengan Gambar 5 menunjukkan salah satu implementasi RANSAC untuk panoramic stitching (menggabungkan dua citra panorama yang diproduksi dengan mengambil gambar dari dua sudut pandang yang berbeda). Pada Gambar 4, dua buah citra gedung diambil dari sudut pandang yang berbeda. Dua citra ini nantinya akan menjadi masukan untuk algoritma panoramic stitching. Gambar 4 menunjukkan hasil deteksi fitur pada dua citra. Seleksi dengan RANSAC dilakukan untuk memisahkan inliers dari outliers (Gambar 5). Panoramic stitching dilakukan dengan menggunakan fitur yang dikategorikan sebagai good matching (Gambar 6).





Gambar 3: dua citra masukan sebelum di proses





Gambar 4: deteksi fitur pada dua buah citra





Gambar 5: Seleksi inliers dan outliers dengan RANSAC.


Garis hijau menunjukkan fitur diklasifikasi sebagi inliers (good matching), sedangkan garis merah menunjukkan fitur yang diklasifikasi sebagai outliers (bad matching).





Gambar 6: Hasil panoramic stitching


Komentar

Postingan populer dari blog ini

Cara Menambahkan Plugin TextFX di notepad++

TextFX adalah plugin pada notepad++ yang digunakan untuk menyortir kata atau kalimat yang sama atau istilah kerenya duplikat data. Berikut saya share cara untuk menambahkan plugin TextFX, perhatikan langkah-langkah berikut! 1. install notepad++ dulu dengan mengunduh filenya disini 2. setelah diunduh kemudian install, setelah di install lalu buka menu Plugins>Plugin Manager>Show Plugin Manager  3. pada Plugin Manager, klik tab Available kemudia geser kebawah dan cari TextFx. klik centang lalu Install. 4. Berhasil, setelah itu restart program notepad++ sekian share dari saya semoga bermanfaat, silahkan bertanya dikolom komentar jika kurang paham. terimakasih

32 Dosa Suami terhadap Istri

KELUARGA diibaratkan seperti batu bata pertama dalam sebuah bangunan masyarakat. Apabila keluarga baik, maka masyarakat pun akan ikut menjadi baik dan sebaliknya jika keluarga rusak, maka masyarakat akan menjadi rusak pula. Oleh karena itu, Islam memberikan perhatian kepada urusan keluarga dengan perhatian yang sangat besar, sebagaimana Islam juga mengatur hal-hal yang dapat menjamin keselamatan dan kebahagiaan keluarga tersebut. Sangat fundamental dalam keluarga adalah perlakuan seorang suami terhadap istrinya. Bisa jadi juga berbuah dosa. Coba cek poin-poin di bawah ini. 1. Lalai Berbakti kepada orang tua setelah menikah 2. Kurang serius dalam mengharmonisasikan antara istri dan orang tua 3. Ragu dan buruk sangka kepada istri 4. Kurang memiliki sikap cemburu terhadap istri 5. Meremehkan kedudukan istri 6. Melepaskan kendali kepemimpinan dan menyerahkannya kepada istri 7. Memakan Harta istri secara batil 8. Kurang semangat dalam mengajari istri ajaran-ajaran agamanya 9. Bersikap pelit

Tenggorokan Kering dan Sakit? Hati-hati! Bisa Jadi Itu Adalah Gejala Kanker Stadium Awal

Kamu harus perhatikan dengan baik! Kanker tenggorokan adalah salah satu kanker yang sering dijumpai pada kebanyakan orang, dan tentu saja hasil pengobatan kanker ini tergantung pada seberapa cepat kita menyadari tingkat keparahan kanker tersebut. Seorang ahli bedah mengatakan bahwa kanker yang didiagnosa pada 5 tahun pertama itu mempunyai tingkat kesembuhan sebesar 90%, tetapi sebaliknya, kanker yang baru diketahui setelah 5 tahun, hanya mempunyai tingkat kesembuhan sekitar 20-30% saja.  Kanker tenggorokan ini tumbuh dari sel Mesothelial yang berkembang pada selaput kerongkongan, dan karena faktor inilah yang akhirnya tumbuh menjadi kanker secara bertahap. Waktu yang diperlukan kanker ini untuk berkembang pada tenggorokan mencapai beberapa tahun lamanya, bahkan dari stadium awal hingga stadium menengah membutuhkan waktu sekitar satu tahun.  Gejala-gejala kanker tenggorokan stadium awal ini adalah sebagai berikut: 1. Merasa kesulitan ketika menelan; biasanya disebabkan oleh masuknya ma