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