基于改進RANSAC算法的道路直線提取方法

吳劍亮，李 艷，高 揚，黃小賽

（1.南京大學(xué) 國際地球系統(tǒng)科學(xué)研究所， 江蘇 南京 210023；2.江蘇省地理信息技術(shù)重點實驗室，江蘇 南京 210023）

基于改進RANSAC算法的道路直線提取方法

吳劍亮1,2，李 艷1,2，高 揚1，黃小賽1

（1.南京大學(xué) 國際地球系統(tǒng)科學(xué)研究所， 江蘇 南京 210023；2.江蘇省地理信息技術(shù)重點實驗室，江蘇 南京 210023）

直線檢測是計算機視覺領(lǐng)域的一項重要內(nèi)容，也是遙感影像信息提取的基本過程。隨機抽樣一致性算法（RANSAC）常用來進行包括直線在內(nèi)的目標提取，是在計算機視覺領(lǐng)域應(yīng)用較廣泛的估計算法之一，但其計算效率較低。因此提出了一種基于序貫概率的改進型多目標RANSAC算法，在利用邊緣檢測限定隨機抽樣原始樣本集的基礎(chǔ)上，運用該算法提取了高分辨率航空影像數(shù)據(jù)中的道路邊界線，大大提升了計算效率。

RANSAC算法；直線檢測；邊緣檢測

直線檢測是計算機視覺領(lǐng)域的一項重要內(nèi)容，是圖像分割的基礎(chǔ)，在多目標跟蹤、人臉識別和車道線提取等方面有著廣泛的應(yīng)用[1]?，F(xiàn)有的直線檢測算法主要分為兩大類：一類是通過圖像預(yù)處理得到目標邊界點的集合，然后再結(jié)合直線識別的基本方法提取目標邊界上的直線；另一類是通過圖像預(yù)處理直接得到圖像邊界線的集合，然后在該集合中進行直線檢測[2]，本文采用第一類方法。傳統(tǒng)的霍夫（Hough）變換是一 種參數(shù)化的對象檢測方法[3]，是一種根據(jù)投票機制檢測特定形狀的算法。在空間A中具有相同特征的曲線或直線可通過Hough變換映射到空間B中的一點，從而形成峰值，即把檢測形狀問題轉(zhuǎn)換為統(tǒng)計峰值問題。雖然傳統(tǒng)的Hough變換不受直線間斷等缺陷的影響，但其對于在高噪聲環(huán)境下的檢測結(jié)果不佳。RANSAC算法由Fisheler和Bolles提出[4]，作為一種普遍的魯棒性模型參數(shù)估計方法，其對于含有錯誤數(shù)據(jù)50%的樣本集依然具有很強的魯棒性[5]，因此它在計算機視覺領(lǐng)域應(yīng)用廣泛，如圖像匹配、拼接等。本文以高分辨率航空影像數(shù)據(jù)為數(shù)據(jù)源，選取日本東京地區(qū)作為研究區(qū)，在序貫概率和多次迭代算法的基礎(chǔ)上提升了RANSAC算法的效率，并將其運用于提取東京地區(qū)平直道路的邊界線。結(jié)果表明，在高噪聲環(huán)境下，提升效率后的RANSAC算法具有很好的多直線檢測結(jié)果。

1 RANSAC算法

1.1 RANSAC算法的基本思想

傳統(tǒng)的數(shù)據(jù)擬合技術(shù)是先使用盡可能多的數(shù)據(jù)得到初始解，再消除無效的數(shù)據(jù)點；而RANSAC算法與傳統(tǒng)的數(shù)據(jù)擬合技術(shù)不同，是選擇少而有效的初始數(shù)據(jù)集，然后在一定容差范圍內(nèi)盡可能地擴大這一初始數(shù)據(jù)集[6]。

一般而言，假設(shè)一組數(shù)據(jù)集中包含適應(yīng)于觀測數(shù)據(jù)的參數(shù)化模型，在總體樣本中抽樣選擇一組最小子集（直線為2），得到符合該子集的參數(shù)化模型M，預(yù)先設(shè)定誤差閾值t。若在閾值t的范圍內(nèi)，初始數(shù)據(jù)集中存在符合模型M的元素，則把該元素歸入子集；然后統(tǒng)計子集內(nèi)元素的個數(shù)n即局內(nèi)點數(shù)，用它們反演模型參數(shù)M*。經(jīng)K次重復(fù)試驗之后，得到滿足一定條件的參數(shù)化模型M。

當置信概率為P時，假設(shè)估計模型需選定n個局內(nèi)點[7]，θ為這n個數(shù)據(jù)點符合該模型的概率，根據(jù)概率理論，K和n之間關(guān)系滿足：

式中，θ= n/N；N為全部數(shù)據(jù)點數(shù)。

RANSAC算法過程為：

1）在指定置信概率P（一般設(shè)置為0.99）的情況下，根據(jù)局內(nèi)點數(shù)的比例θ，由式（1）確定試驗次數(shù)K。

2）隨機抽樣計算模型參數(shù)，用全部數(shù)據(jù)點檢驗?zāi)Ｐ蛥?shù)，得到該模型的局內(nèi)點數(shù)n'。

3）以局內(nèi)點數(shù)最多或點數(shù)相同時局內(nèi)點對模型的誤差方差最小為原則選擇最優(yōu)模型。

4）用最優(yōu)模型對應(yīng)的n'個局內(nèi)點重新估算最終模型參數(shù)。

在足夠多的試驗次數(shù)條件下，該算法一定能找到最優(yōu)模型。如圖1所示，黑色圓點表示含有噪聲的一 組二維點集，在該點集中，噪聲點達到40%以上；藍色圓點表示兩個隨機抽樣點；藍色直線表示由它們確定的直線模型；紅色圓點表示局內(nèi)點。通過擬合技術(shù)得到最終的直線模型如圖2中紅色直線所示。

圖1 RANSAC算法第一次抽樣圖

1.2 RANSAC算法優(yōu)化

確定RANSAC算法時間復(fù)雜度的公式為：

式中， TM為每次隨機抽樣的時間；為抽樣樣本中每個數(shù)據(jù)點驗證該模型的平均時間；N為抽樣樣本中數(shù)據(jù)點個數(shù)；K為迭代次數(shù)。通常TM和對一個特定問題而言可認為是不變的，所以RANSAC算法的時間復(fù)雜度由K和N決定。

由式（2）可知，樣本模型越復(fù)雜，θ隨之越小，在保證置信概率P的前提下，就必須提高迭代次數(shù)K，算法的時間復(fù)雜度也隨之升高。

通過上述分析，對RANSAC算法進行了3個方面的優(yōu)化，使其能夠更加快速和準確地提取多直線：

1）在選取數(shù)據(jù)子集時，可給予一定的條件約束，而非完全隨機抽樣。例如，對于圖像而言，可利用邊緣檢測并結(jié)合直方圖信息，縮小子集的選取范圍。本文提取對象為平直道路的邊界線，與周圍背景具有一定灰度差異，可利用Canny算子進行邊緣檢測的預(yù)處理。

2）在數(shù)據(jù)集隨機采樣子集并估計子集的模型后，采用序貫概率檢測技術(shù)[8-9]進行預(yù)檢驗優(yōu)化，隨機選取數(shù)據(jù)集中部分而非全部點來檢驗?zāi)Ｐ偷恼_性。若模型在早期被拒絕，則進行重新估計和檢驗；若模型被最終接受，則把剩余的點代入模型進行全部檢驗。由于大部分模型受錯誤點影響，所以可較快速地過濾掉大多數(shù)錯誤模型，提高算法速率。

3）為了檢測多直線，在一次檢測后標記出符合此次檢測最佳模型的數(shù)據(jù)，然后把這些數(shù)據(jù)從總體樣本中去除，再進行下次檢驗，如此循環(huán)直到總體數(shù)據(jù)中沒有滿足最佳模型條件的數(shù)據(jù)子集。

1.3 改進RANSAC算法步驟

根據(jù)算法分析和優(yōu)化方案，結(jié)合RANSAC算法的基本步驟，對高分辨率航空影像數(shù)據(jù)中的平直道路邊界線進行了多直線提取，主要步驟為：

1）預(yù)設(shè)參數(shù)：序貫檢測局內(nèi)點數(shù)閾值為N1，最少提取點數(shù)閾值為N2（直線提取停止條件之一），誤差閾值為D，試驗次數(shù)閾值為T，當前步數(shù)s=0。

2）利用Canny算子對原始圖像邊緣進行提取。3）數(shù)據(jù)隨機抽樣并計算模型參數(shù)及局內(nèi)點數(shù)n'i。4）s=s+1；進行序貫檢測，若n'i＞N1，則模型通過預(yù)檢驗，進入下一步，否則返回步驟3）進行重抽樣。

5）把剩余點逐個代入模型進行誤差檢驗，并由此更新局內(nèi)點數(shù)n'i。

6）若n'i＞N2，比較n'i與上一次迭代的局內(nèi)點數(shù)n'i-1：選擇局內(nèi)點數(shù)較多的模型為較優(yōu)模型，n'i=max{n'i, n'i-1}；若n'i=n'i-1，則選擇方差較小的模型為較優(yōu)模型，n'i=maxvar{n'k|Vark,k=i,i-1}，i=i+1，進入下一步；否則返回步驟3）。

7）若當前步數(shù)s＞T，則停止；否則輸出一個模型，返回步驟3）。

8）利用最優(yōu)模型對應(yīng)的n'個局內(nèi)點重新估算最終模型參數(shù)。

2 直線檢測結(jié)果及分析

如圖3所示，本文以東京地區(qū)為研究區(qū)，運用Canny算子對該區(qū)域進行邊緣檢測，最終通過二值化等預(yù)處理操作，生成一系列數(shù)據(jù)點，即圖4中的白色像素點。

圖3 東京高分辨率航空遙感影像數(shù)據(jù)

通過Canny邊緣檢測圖可以看到有很多噪聲數(shù)據(jù)干擾，同時在公路邊界和高架鐵軌兩側(cè)具有明顯的直線特征。設(shè)局內(nèi)點的最少個數(shù)為800，誤差閾值為3，迭代次數(shù)為150，運用改進RANSAC算法進行多直線提取。該算法基于Python3.1環(huán)境和Opencv圖像處理庫實現(xiàn)，得到滿足條件的多條直線模型的局內(nèi)點分布，如圖4所示。把局內(nèi)點分別疊加到原始圖像，得到最終的多直線檢測效果圖。由圖5可知，改進RANSAC算法從大量數(shù)據(jù)點中準確有效地提取了多直線，且無論直線是否間斷都具有很好的效果。

圖4 局內(nèi)點分布圖

圖5 多直線檢測結(jié)果圖

因此，改進RANSAC算法需要確定的參數(shù)有：局內(nèi)點的最少個數(shù)和誤差閾值。下面介紹多直線檢測參數(shù)的設(shè)定方法。

由表1可知，若最少局內(nèi)點數(shù)N2設(shè)置過大，則最終檢測直線的條數(shù)并不會增加，如實驗1～4；若設(shè)置過小，則會檢測出過多的直線，如實驗7～9。因此，在樣本數(shù)據(jù)較大的情況下，最少局內(nèi)點數(shù)應(yīng)設(shè)置為總體樣本點數(shù)的2%～3%。誤差閾值決定了數(shù)據(jù)是否適用于模型，本文利用點到直線的歐氏距離衡量點適用于直線模型的尺度，將誤差閾值設(shè)置為2個像素單位。通過表2可知，改進RANSAC算法的平均計算效率比原始方法有所提高，運行時間相應(yīng)縮短。

表1 區(qū)域參數(shù)和檢測直線條數(shù)的關(guān)系

表2 時間效率比較表

3 結(jié) 語

本文提出了一種改進RANSAC算法，通過對數(shù)據(jù)的預(yù)處理縮小樣本集合，再進行多目標提取。通過對高分辨率航空影像數(shù)據(jù)中的平直道路邊界線多直線提取的實驗表明，通過序貫檢驗縮短了約1/4的驗證模型計算時間，對連續(xù)多直線的提取具有較好的實驗效果。本文探討了參數(shù)對算法最終結(jié)果的影響，其中若干參數(shù)的設(shè)置原則是試驗性的，在今后的研究中將根據(jù)參數(shù)與數(shù)據(jù)的關(guān)系，在理論上給出合理的設(shè)置原則。

[1] 曲天偉,安波,陳桂蘭.改進的RANSAC算法在圖像配準中的應(yīng)用[J].計算機應(yīng)用,2010,30(7)：1 849-1 851

[2] 孫涵,任明武,楊靜宇.一種快速實用的直線檢測算法[J].計算機應(yīng)用研究,2006,23(2)：256-257[3] CHUNG KL，CHANG T C，HUANG Y H，Comment on：“Extended Hough Transform for Linear Feature Detection”[J]. Pattern Recognition,2009,42(7)：1 612-1 614

[4] Chum O,Matan J,Kitfler J.Locally Optimized RANSAC[A]// In：Michaelis B,Krell G.Eds：Proceedings of the 25th DAGM Symposium[C].Berlin,Germany：Springer-Verlag,2003：236-243

[5] 高洪智,盧啟鵬,丁海泉,等.基于隨機抽樣一致性算法的近紅外光譜穩(wěn)健模型研究[J].光學(xué)學(xué)報,2013,33(B12)：220-224

[6] 袁清珂,張振亞,畢慶.改進RANSAC算法在直線擬合中的應(yīng)用[J].組合機床與自動化加工技術(shù),2015(1)：123-125

[7] 陳付幸,王潤生.基于預(yù)檢驗的快速隨機抽樣一致性算法[J].軟件學(xué)報,2005,16(8)：1 431-1 437

[8] 周駿,陳雷霆, 劉啟和,等.基于序貫概率及局部優(yōu)化隨機抽樣一致性算法[J].儀器儀表學(xué)報,2012,33(9)：2 037-2 044 [9] 張紅民,曾禎.一種改進的相鄰概率隨機抽樣一致性算法[J].激光雜志,2013(5)：29-30

P237

B

1672-4623（2017）05-0042-03

10.3969/j.issn.1672-4623.2017.0051.3

吳劍亮，碩士研究生，研究方向為遙感圖像處理與信息提取。

2016-06-13。

項目來源：國家自然科學(xué)基金資助項目（41371331）。