作者：王先榮

    大約在兩年前翻譯了《隨機(jī)抽樣一致性算法RANSAC》，在文章的最后承諾寫該算法的C#示例程序。可惜光陰似箭，轉(zhuǎn)眼許久才寫出來，實(shí)在抱歉。本文將使用隨機(jī)抽樣一致性算法來來檢測直線和圓，并提供源代碼下載。

一、RANSAC檢測流程

    在這里復(fù)述下RANSAC的檢測流程，詳細(xì)的過程見上一篇翻譯文章：

    RANSAC算法的輸入是一組觀測數(shù)據(jù)，一個(gè)可以解釋或者適應(yīng)于觀測數(shù)據(jù)的參數(shù)化模型，一些可信的參數(shù)。

    RANSAC通過反復(fù)選擇數(shù)據(jù)中的一組隨機(jī)子集來達(dá)成目標(biāo)。被選取的子集被假設(shè)為局內(nèi)點(diǎn)，并用下述方法進(jìn)行驗(yàn)證：
    1.有一個(gè)模型適應(yīng)于假設(shè)的局內(nèi)點(diǎn)，即所有的未知參數(shù)都能從假設(shè)的局內(nèi)點(diǎn)計(jì)算得出。
    2.用1中得到的模型去測試所有的其它數(shù)據(jù)，如果某個(gè)點(diǎn)適用于估計(jì)的模型，認(rèn)為它也是局內(nèi)點(diǎn)。
    3.如果有足夠多的點(diǎn)被歸類為假設(shè)的局內(nèi)點(diǎn)，那么估計(jì)的模型就足夠合理。
    4.然后，用所有假設(shè)的局內(nèi)點(diǎn)去重新估計(jì)模型，因?yàn)樗鼉H僅被初始的假設(shè)局內(nèi)點(diǎn)估計(jì)過。
    5.最后，通過估計(jì)局內(nèi)點(diǎn)與模型的錯(cuò)誤率來評(píng)估模型。
    這個(gè)過程被重復(fù)執(zhí)行固定的次數(shù)，每次產(chǎn)生的模型要么因?yàn)榫謨?nèi)點(diǎn)太少而被舍棄，要么因?yàn)楸痊F(xiàn)有的模型更好而被選用。

二、得到觀測數(shù)據(jù)

    我們沒有實(shí)驗(yàn)（測試）數(shù)據(jù)，這里用手工輸入的數(shù)據(jù)來替代——記錄您在PictureBox中的點(diǎn)擊坐標(biāo)，作為觀測數(shù)據(jù)。

得到樣本點(diǎn)

三、檢測直線

    3.1 直線的相關(guān)知識(shí)

    （1）平面上的任意兩點(diǎn)可以確定一條直線；

    （2）直線的通用數(shù)學(xué)表達(dá)形式為：ax+by+c=0。這種表達(dá)形式有三個(gè)未知數(shù)，需要提供三個(gè)點(diǎn)才能解出a,b,c三個(gè)參數(shù)。由于隨機(jī)選擇的三個(gè)點(diǎn)不一定在一條直線上，所以程序中放棄這種方式。

    （3）直線可以用y=ax+b及x=c這兩個(gè)式子來表示。這兩種形式只有一個(gè)或者兩個(gè)未知數(shù)，只需兩個(gè)點(diǎn)就能解出a,b,c三個(gè)參數(shù)。隨機(jī)選擇的兩個(gè)點(diǎn)即可得到直線，我們采用這種形式。

    3.2 直線類

    直線類(Line)封裝了跟直線相關(guān)的一些屬性及方法，列表如下：

    （1）屬性

    A——y=ax+b中的a

    B——y=ax+b中的b

    C——x=c中的c

    （2）構(gòu)造函數(shù)

    public Line(PointF p1, PointF p2)

    提供兩個(gè)點(diǎn)p1及p2，計(jì)算出直線的屬性A,B,C。

    （3）方法

    GetDistance——獲取點(diǎn)到直線之間的距離；

    GetY——根據(jù)x坐標(biāo)，獲取直線上點(diǎn)的y坐標(biāo)；

    ToString——獲取直線的方程式。

Line類

    3.3 檢測直線的過程

    （1）隨機(jī)從觀測點(diǎn)中選擇兩個(gè)點(diǎn)，得到通過該點(diǎn)的直線；

    （2）用（1）中的直線去測試其他觀測點(diǎn)，由點(diǎn)到直線的距離確定觀測點(diǎn)是否為局內(nèi)點(diǎn)或者局外點(diǎn)；

    （3）如果局內(nèi)點(diǎn)足夠多，并且局內(nèi)點(diǎn)多于原有“最佳”直線的局內(nèi)點(diǎn)，那么將這次迭代的直線設(shè)為“最佳”直線；

    （4）重復(fù)（1）~（3）步直到找到最佳直線。

    細(xì)心的您估計(jì)已經(jīng)發(fā)現(xiàn)我省略了標(biāo)準(zhǔn)RANSAC檢測過程中重新估計(jì)模型的步驟，我是故意的，我覺得麻煩且沒什么用處，所以咔嚓了，O(∩_∩)O~。

獲取直線

四、檢測圓

    4.1 圓的相關(guān)知識(shí)

    （1）平面內(nèi)不在同一直線上的三個(gè)點(diǎn)可以確定一個(gè)圓；

    （2）圓的數(shù)學(xué)表達(dá)形式為：(x-a)²+(y-b)²=r²

    其中，(a,b)為圓心，r為半徑。

    4.2 圓類

    圓類(Circle)封裝了跟圓有關(guān)的屬性及方法，列表如下：

    （1）屬性

    A——圓心的x坐標(biāo)

    B——圓心的y坐標(biāo)

     R——圓的半徑

    （2）構(gòu)造函數(shù)

    public Circle(PointF p1, PointF p2, PointF p3)

    提供三個(gè)點(diǎn)p1，p2和p3，計(jì)算出圓的屬性A,B,R。

    （3）方法

    GetDistance——獲取點(diǎn)到圓（周）之間的距離，表示點(diǎn)接近或者遠(yuǎn)離圓；

    ToString——獲取圓的方程式。

Circle類

    3.3 檢測圓的過程

    （1）隨機(jī)從觀測點(diǎn)中選擇三個(gè)點(diǎn)，嘗試得到通過這三個(gè)點(diǎn)的圓；

    （2）用（1）中的圓去測試其他觀測點(diǎn)，由點(diǎn)到圓的距離確定觀測點(diǎn)是否為局內(nèi)點(diǎn)或者局外點(diǎn)；

    （3）如果局內(nèi)點(diǎn)足夠多，并且局內(nèi)點(diǎn)多于原有“最佳”圓的局內(nèi)點(diǎn)，那么將這次迭代的圓設(shè)為“最佳”圓；

    （4）重復(fù)（1）~（3）步直到找到最佳圓。

獲取圓

五、本文源代碼

    點(diǎn)擊這里下載本文源代碼。

    感謝您閱讀本文，希望對(duì)您有所幫助。