ข้ามไปที่เนื้อหาหลัก

RANdom SAmple Consensus (RANSAC) algorithm

Introduction

fig. 1 picture from 'Multiview geometry in Computer Vision' book.

If you use orthogonal regression ( minimizes the sum of squared perpendicular distances -- LMS ), there will be a problem if you have an outliers (see fig 1a).

RANSAC algorithm

RANSAC algorithm will cope with this problem by discarding outliers.

Slide from 25th year of RANSAC, Philip Torr slides has very clear picture of the algorithm.






support = number of points that lie within a distance threshold

points within the threshold distance of a line with most support are the inliers.

If a point is an outliers, a line will not have so much support. ( see fig 1b from mvg book above )

Explain the algorithm

- First we randomly pick two red point and estimate m, c for y=mx+c ( this is easy, right )

- for consider if a point is a inlier
for every yellow point (x, y)
If | y - (m*x + c) | < t, number of inlier need to justify model

-- re-estimate m, c again by using all the inlier

sample code ?

a simple python example code for RANSAC is available here.
or more complicate code here. all is the same code as a psudocode from wiki.

or you can use my porting octave code here ( NOTE if you are using matlab, this code should be modified )

# Run RANSAC to see if we can recover the line (y=x) from the data.
function [model_params, model_error, model_inliers] = ransac(data,n,k,t,d)
  % k -- the number of iterations.
  % t -- the threshold for deciding when a data point fits a model (i.e. is an inlier).
  % d -- the number of inliers needed to justify the model.

# k=100,d=20
  model_params = [0.0, 0.0] # slope and intercept
  model_error = 1e6
  model_inliers = []

  for i=1:k # k iterations
      fprintf(1, "new iteraion\n\n")
      inliers = choice(data, n)
   
      # Fit a line (or generally any model) using lstsq.
      a = [inliers(:,1), ones(1, n)']
      b = inliers(:,2)

      # linear least square -- rewrite y = mx+c in y = A*p form
      # A = [x 1]      
      # p = [m, c]
      p = a \ b
    
      compatible = []
      for j=1:size(data, 1)
          fprintf(1, '--')
          pt = data(j,:)
          if abs(pt(2) - dot(p, [pt(1), 1.0])) < t # | y - (m*x + c) | < t
              compatible = [compatible; pt]
          end  
      end  

      if size(compatible, 1) > d
          # The current model is good enough so we should recompute it using all compatible points.
          a = [compatible(:,1), ones(1, size(compatible, 1))']
          b = compatible(:,2)
          p = a \ b
       
          # if residuals < model_error
              model_params = p
              # model_error = residuals
              model_inliers = compatible
          # end
      end
  end

function result=choice(seq, n)
  indx = 1:size(seq)-1
  shuffle(indx)
  result = seq(indx(1:n), :)


adaptively find k (the number of iterations)
k = log(1-p)/log(1-(1-ε)^n)

proof ( ref : wiki ) :

p
= prob(RANSAC algorithm in some iteration selects only inliers )

w = prob( choosing an inlier each time a single point is selected ) = number of inliers / number of all points

A common case is that w is not well known beforehand, but some rough value can be given.

n = Sample Size

wn = prob( n points are inliers )
1 − wn = prob( at least one of the n points is an outlier ) [ bad model will be estimated from this point set ]
( 1 − wk = prob( algorithm never selects a set of n points which all are inliers )
( 1 − wn )k = 1 − p
take log and we will get
k = log(1-p)/log(1-w^n)

It should be noted that this result assumes that the n data points are selected independently, that is, a point which has been selected once is replaced and can be selected again in the same iteration.

Apply to Homography
When adapt this to Homography, estimating line is not a visual line. The error is computing from transfer error d.

This RANSAC for Homography steps are adapt from Alexei (Alyosha) Efros's slide.

RANSAC loop:
1. Select 4 feature pairs (at random)
[ n in the code, or s in the book is fixed to 4 ]
2. Compute homography H (exact)
3. If d(x’, H x) largest set of inliers
[ so the number of inliers needed to justify the model ( d in the code or capital T in the book ) is not used here. ]
5. Re-compute least-squares H estimate on all of the inliers

ความคิดเห็น

โพสต์ยอดนิยมจากบล็อกนี้

เทคนิคคิดเลขเร็วโดยใช้ วิธีคิด แบบ เวทคณิต ( Vedic Mathematics example )

จากที่สงสัยเรื่อง ลูกคิด ของ จินตคณิต ที่ลองไปค้นดู
ปรากฎว่า เจอ เวทคณิต ซึ่งเขาบอกว่า อยู่ในคัมภีร์พระเวท

ลองอ่านดูแล้ว รู้สึกว่าฝึกสมอง ก็ทำให้คิดเลขเร็วดี
เลยสรุปมาให้ ตามนี้

Tutorial 1

การลบเลข
ALL FROM 9 AND THE LAST FROM 10
ทุกตัวลบจาก 9 และตัวสุดท้ายลบจาก 10

เช่น 1000 - 357 = 643
10,000 - 1,049 = 8951

ถ้า 1,000 - 83 ให้มองว่ามี 0 อยู่ข้างหน้า
เป็น
1,000 - 083 = 917

ฝึกบ่อยๆ ก็คล่อง แล้วก็ไม่ต้องใช้เครื่องคิดเลขด้วย
ลองทำดูสิ
1) 1000 - 777 =
2) 1000 - 283 =
3) 1000 - 505 =
4) 10,000 - 2345 =
5) 10,000 - 9876 =
6) 10,000 - 1011 =
7) 100 - 57 =
8) 1000 - 57 =
9) 10,000 - 321 =
10) 10,000 - 38 =

3,000 - 467 ก็ทำเหมือนกัน โดยลบตัวแรกสุดของ 3,000 ไป 1
จากนั้นก็ทำเหมือนเดิม จะได้ว่า 3,000 - 467 = 2,533

Tutorial 2
VERTICALLY AND CROSSWISE สำหรับตัวเลขที่น้อยกว่าฐานนิดหน่อย

ลอง 88x98

88 น้อยกว่า 100 อยู่ 12
98 น้อยกว่า 100 อยู่ 2
12x2 = 24
88-2 หรือ 98-12 ได้ 86
ดังนั้นตอบ 8,624

ดูอีกตัวอย่าง
หรือ

ลองทำนี่ดู
1) 87 x 98 =
2) 88 x 97 =
3) 77 x 98 =
4) 93 x 96 =
5) 94 x 9…

วิธีใช้ ย่อๆ เกี่ยวกับ Matrix กับ Vector ( มาจาก CASIO-991MS manual )

Matrix

เปลี่ยน mode เป็น Matrix
กด mode ไปเรื่อยๆ จนเจอ MAT

วิธีใส่ Matrix เข้าไป
จิ้ม MAT ( ตรงเลข 4 )
DIM -- สร้าง Matrix ใหม่ - เราจะสร้าง Matrix เก็บไว้ในตัวแปรได้สามตัว คือ A, B, C ( Trick : ตอนใส่ค่า a11, a12, .. ถ้าอยากข้ามไปให้กดลูกศร ขึ้น ลง ซ้าย ขวา ได้เลย )
รุ่นนี้ มันใส่ได้มากสุด 3x3 นะ ถ้าใส่ 4 ไป มันจะ dimension error
EDIT -- แก้ไข Matrix ที่สร้างไว้แล้ว
MAT -- เอา Matrix ออกมาใช้งาน

Add : MatA + MatB
Subtract : MatA - MatB
Multiply with scalar : MatA x 3 หรือ 3 x MatA
Multiply : MatA x MatB
Det : Det MatA
Transpost : Trn MatA
Inverse :MatA -1
Absolute Value of Each Element : Abs MatA

ผลลัพธ์มันจะได้เป็น
MatAns11
ซึ่งเราสามารถกด ซ้าย ขวา ขึ้นลงได้เหมือนเลื่อนดู Element จาก Matrix เลย

Vector
เปลี่ยน mode เป็น Vector
กด mode ไปเรื่อยๆ จนเจอ VCT

วิธีใส่ Vector เข้าไป
จิ้ม VCT ( ตรงเลข 5 )
DIM -- สร้าง Vector ใหม่ - เราจะสร้าง Vector เก็บไว้ในตัวแปรได้สามตัว คือ A, B, C ( Trick : ตอนใส่ค่า a1, a2, .. ถ้าอยากข้ามไปให้กดลูกศร ซ้าย ขวา ได้เลย )
EDIT -- แก้ไข Vector ที่สร้างไว้แล้ว
VCT -- เอา Vector ออกม…

อยู่เหงาๆ เราไปเที่ยว - วัดอรุณราชวราราม ( วัดแจ้ง ) + วัดสระเกศ ( ภูเขาทอง )

เอนทรีนี้เป็นส่วนหนึ่งของ serie ท่องเที่ยว ดูบทความท่องเที่ยว อื่นๆ ของผม ได้ที่ ลิงก์นี้ นะครับ

คำเตือน เอ็นทรีนี้รูปเยอะมากกกก ควรปิดบิตก่อนดู

ผ่างๆๆ ท่านสามารถรับชมเอนทรีนี้ผ่าน url http://tinyurl.com/goldenMount ได้ด้วย

วันนี้ตั้งใจไปวัดอรุณฯ

เดินทางทางน้ำเหมือนเดิม

แต่คราวนี้นั่งเรือ ธงสีฟ้า ( คราวก่อน นั่งเรือ ธงสีส้ม )

พอถึงท่าสาทร เขาบอกว่า ให้ลงลำที่จอดอยู่ได้เลย เก็บตังในเรือ

ก็ งงๆ เดินลงไป

เหมือนเดิมครับ

ชูชีพอยู่ใต้ที่นั่งของท่าน
พอเรือออกสักพัก มีไกด์ มาบรรยาย

อ้าว กรำ

ขึ้นผิดเรือรึเปล่า

นี่มันเรือท่องเที่ยว 150 บาท ไม่ใช่เร๊อะ

กะลังอึ้งๆอยู่

แต่พอไกด์พูดไปสักพัก ก็เลยรู้ว่า 150 บาท มันราคาเหมาวัน

แล้วก็ได้ความรู้ของท่าเรือ แล้วก็สองข้างทาง




เรือธงฟ้านี่มันไปสุดที่ท่าพระอาทิตย์เท่านั้นเองนะ แล้วก็กลับ

ตอนไปมีสาวคนนึง ถามว่า จะไปวัดสระเกศ ไปทางไหน

ถ้าฟังไม่ผิด คนเก็บตังบนเรือ บอกว่า ท่ามหาราช

จากนั้นก็คุยอะไรกันไม่รู้ ไม่ได้ยินแล้วล่ะ




เรือธงฟ้า มันใหญ่กว่า น่าหวาดเสียวน้อยกว่า น้ำกระเด็นน้อยกว่า แพงกว่า เรือธงสีส้ม

คราวนี้รู้และ นั่งริมฝั่งธน ได้มาหลายรูปเหมือนกัน แต่วันนี…