一種投票式并行RANSAC算法及其FPGA實(shí)現(xiàn)

江 潔 凌思睿

?

一種投票式并行RANSAC算法及其FPGA實(shí)現(xiàn)

江 潔 凌思睿*

(北京航空航天大學(xué)精密光機(jī)電一體化技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室 北京 100191)

隨機(jī)抽樣一致(RANdom SAmple Consensus, RANSAC)算法在數(shù)據(jù)量大，局外點(diǎn)比例高，模型復(fù)雜等情況下運(yùn)算速度明顯下降。該文提出一種投票式并行RANSAC算法，在把假設(shè)階段并行化，同時(shí)生成多個(gè)模型的基礎(chǔ)上，提出多個(gè)模型并行對(duì)同一個(gè)數(shù)據(jù)點(diǎn)投票，直接判斷其是否屬于局內(nèi)點(diǎn)的方法，省去了傳統(tǒng)方法中根據(jù)最佳模型重新篩選數(shù)據(jù)點(diǎn)的步驟。在以FPGA為代表的并行平臺(tái)上，該算法可以充分利用其硬件資源和并行處理特性，實(shí)現(xiàn)深度流水線的并行運(yùn)算。實(shí)驗(yàn)結(jié)果表明該算法不僅擁有更好的魯棒性，其性能和數(shù)據(jù)吞吐量還獲得了大幅提升。

FPGA；隨機(jī)抽樣一致(RANSAC)；并行計(jì)算

1 引言

Fischler等人[1]在1981年提出的RANSAC(RANdom SAmple Consensus)算法，由于其原理簡(jiǎn)單，魯棒性強(qiáng)，目前已廣泛應(yīng)用于含錯(cuò)誤數(shù)據(jù)的模型估計(jì)，如目標(biāo)檢測(cè)，立體圖像匹配等。

提高RANSAC性能的另一種方法是并行化。如袁紅星等人[13]和Lee等人[14]等提出利用GPU并行計(jì)算RANSAC中的多個(gè)“假設(shè)-檢驗(yàn)”過程；Fijany等人實(shí)現(xiàn)了在ClearSpeed[15]和Tilera[16]平臺(tái)上的多數(shù)據(jù)流RANSAC算法。這些并行化方法雖然達(dá)到了加速的效果，但某些地方還存在速度瓶頸，依賴于計(jì)算機(jī)平臺(tái)且功耗較大，應(yīng)用場(chǎng)合受到限制。

本文在把RANSAC算法深度并行化的基礎(chǔ)上，提出一種投票式數(shù)據(jù)檢驗(yàn)方法，提高了RANSAC算法的性能和數(shù)據(jù)吞吐量。本文還以圓的提取為例，利用FPGA的并行處理特性和豐富的資源實(shí)現(xiàn)了該算法，能滿足高速實(shí)時(shí)處理的需求。

2 傳統(tǒng)RANSAC算法

兩邊取對(duì)數(shù)得

3 并行RANSAC算法及其FPGA實(shí)現(xiàn)

串行RANSAC算法要求對(duì)“假設(shè)-檢驗(yàn)”過程進(jìn)行次迭代，導(dǎo)致計(jì)算速度難以提高；常見的并行化方案只是簡(jiǎn)單地把原串行方案分成多個(gè)線程同時(shí)執(zhí)行，尋找最佳模型時(shí)依然需要串行操作，影響了整體速度。本文提出了一種投票式并行RANSAC算法，通過把假設(shè)階段并行化以及對(duì)數(shù)據(jù)點(diǎn)并行投票，直接檢驗(yàn)，獲得了可觀的性能提升。

3.1 假設(shè)階段的并行化

3.2 投票式檢驗(yàn)

圖1 現(xiàn)有并行檢驗(yàn)方法流程圖

圖2 本文投票檢驗(yàn)方法流程圖

3.3 并行RANSAC算法的FPGA實(shí)現(xiàn)

以提取圓為例，投票式并行RANSAC算法在FPGA上的實(shí)現(xiàn)方法如下。

圖3 隨機(jī)采樣與并行假設(shè)模塊

圖4 圓模型的假設(shè)模塊內(nèi)部結(jié)構(gòu)(3點(diǎn)定圓)

圖5投票檢驗(yàn)?zāi)K

4 性能評(píng)估與實(shí)驗(yàn)

4.1 算法性能評(píng)估

表2 RANSAC算法性能比較

本文算法除上述的性能優(yōu)勢(shì)外，還利用FPGA充足的硬件資源和高度的并行性，實(shí)現(xiàn)了多指令多數(shù)據(jù)流的深度流水線運(yùn)算，避免了尋找最佳模型時(shí)的串行操作，基本消除了RANSAC算法在數(shù)據(jù)吞吐量上的瓶頸。

4.2 仿真實(shí)驗(yàn)

仿真實(shí)驗(yàn)?zāi)康氖潜容^PC上的傳統(tǒng)RANSAC與FPGA上的并行RANSAC的準(zhǔn)確性和運(yùn)算速度。實(shí)驗(yàn)環(huán)境：CPU為Intel Core2 Duo E7400的PC平臺(tái)；XILINX公司Virtex-5 LX330 FPGA。為了測(cè)試不同樣本錯(cuò)誤率和樣本大小下兩種RANSAC算法的特性，設(shè)計(jì)了估計(jì)圓的仿真實(shí)驗(yàn)，真實(shí)圓心為(600,450)，半徑為300。數(shù)據(jù)集大小分別為1000, 10000, 100000, 1000000，局外點(diǎn)呈2維均勻分布，比例分別為10%, 20%, 30%, 40%, 50%。在置信水平99%的條件下求解。

在不同的局外點(diǎn)比例下各進(jìn)行100次試驗(yàn)，統(tǒng)計(jì)其正確結(jié)果和錯(cuò)誤結(jié)果的個(gè)數(shù)，表3和圖7為兩種算法的準(zhǔn)確性比較?？梢钥闯觯瑐鹘y(tǒng)算法找到的正確局內(nèi)點(diǎn)比例穩(wěn)定在98.5%附近，本文算法的漏檢率全面優(yōu)于傳統(tǒng)算法。更重要的是，本文算法給出的錯(cuò)誤結(jié)果明顯少于傳統(tǒng)算法，說明本文算法的魯棒性得到了提高。

圖7 兩種RANSAC算法找到的正確局內(nèi)點(diǎn)比例

表4為兩種RANSAC算法的運(yùn)算速度比較。實(shí)驗(yàn)結(jié)果顯示，當(dāng)樣本數(shù)量和局外點(diǎn)比例較小時(shí)，并行RANSAC的性能優(yōu)勢(shì)不很明顯；而樣本數(shù)據(jù)量大，局外點(diǎn)比例高時(shí)，并行RANSAC時(shí)間復(fù)雜度小的特點(diǎn)得到了很好的體現(xiàn)。如當(dāng)=1000000,=50%時(shí)，即使CPU的運(yùn)行頻率(2.8 GHz)是FPGA(100 MHz)的28倍，并行RANSAC的運(yùn)算速度仍然達(dá)到了傳統(tǒng)算法的56倍。此外，在實(shí)際應(yīng)用中常見數(shù)據(jù)集大小相近而噪聲等干擾數(shù)量隨機(jī)波動(dòng)的情況，而并行RANSAC耗費(fèi)的時(shí)間與局外點(diǎn)比例無關(guān)，很好地保證了算法的實(shí)時(shí)性。

4.3 真實(shí)圖像處理實(shí)驗(yàn)

在天文導(dǎo)航中，需要用圖像處理的方法提取近天體目標(biāo)(如地球、月球)的中心。相機(jī)拍攝到的地球圖像(圖8(a))經(jīng)過邊緣提取獲得含有干擾的圓圖像(圖8(b))后，可以利用RANSAC算法去除干擾，再用最小二乘法擬合圓心(圖8(c))。

表3兩種RANSAC算法在不同局外點(diǎn)比例下的準(zhǔn)確性

局外點(diǎn)比例(%) 1020304050 實(shí)際局內(nèi)點(diǎn)9998960088880000777696006666000055550000 正確結(jié)果傳統(tǒng)9913007788427854758474716567091553908040 本文9998960088872968769644986634127455111747 錯(cuò)誤結(jié)果傳統(tǒng)768862187130333199 本文000115

表4兩種RANSAC算法在不同數(shù)據(jù)集大小和局外點(diǎn)比例下的耗時(shí)(ms)

數(shù)據(jù)集大小局外點(diǎn)比例(%) 1020304050 傳統(tǒng)本文傳統(tǒng)本文傳統(tǒng)本文傳統(tǒng)本文傳統(tǒng)本文 1000 0.12960.01126 0.11100.01126 0.1812 0.01126 0.3006 0.01126 0.5742 0.01126 10000 0.63130.10130 1.78670.10130 1.7747 0.10130 3.7239 0.10130 5.5898 0.10130 100000 6.35421.0013011.18241.0013030.8633 1.00130 30.5217 1.00130 62.6235 1.00130 100000063.648010.00100113.123010.00100179.089010.00100308.515010.00100566.284010.00100

圖8 天體目標(biāo)圓心提取示意圖

用FPGA和PC對(duì)含干擾的地球圖像(圖8(a))進(jìn)行圓心提取，結(jié)果如表5所示。

表5 FPGA圓心提取結(jié)果

FPGA提取的圓心與軟件計(jì)算結(jié)果基本一致。在Virtex-5 LX330 FPGA上綜合、布局布線后，并行RANSAC模塊(其中包含30個(gè)假設(shè)模塊和投票模塊)占用60個(gè)硬核DSP模塊，81780個(gè)LUTs和66750個(gè)寄存器。整個(gè)圓心提取系統(tǒng)在100 MHz的時(shí)鐘下，圖像輸入完畢后經(jīng)過2.063 ms可獲得圓心和半徑的擬合結(jié)果(邊緣點(diǎn)約為1400個(gè)，局外點(diǎn)比例10%)，可以獲得最高484.7幀/s的處理速度。

5 結(jié)論

本文提出了一種改進(jìn)的并行RANSAC算法，首先把假設(shè)階段并行化，同時(shí)生成多個(gè)模型，之后采用投票方式對(duì)數(shù)據(jù)點(diǎn)進(jìn)行檢驗(yàn)，直接從數(shù)據(jù)集中獲得局內(nèi)點(diǎn)，與現(xiàn)有并行算法相比節(jié)省了一半時(shí)間。模擬數(shù)據(jù)和真實(shí)圖像處理結(jié)果表明，該并行算法在改善RANSAC魯棒性的同時(shí)有效提高了其性能。在大樣本、高局外點(diǎn)比例的情況下，該算法能充分利用FPGA硬件的并行特性，在準(zhǔn)確度和速度上均有更好的表現(xiàn)。

[1] Fischler M A and Bolles R C. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[J]., 1981, 24(6): 381-395.

[2] 陳付幸, 王潤(rùn)生. 一種新的消失點(diǎn)檢測(cè)算法[J]. 電子與信息學(xué)報(bào), 2008, 28(8): 1458-1462.

Chen Fu-xing and Wang Run-sheng. A new vanishing point detecting algorithm[J].&, 2008, 28(8): 1458-1462.

[3] Priyadarshi Bhattacharya and Marina Gavrilova. Improving RANSAC feature matching with local topological information[C]. 2012 Ninth International Symposium on Voronoi Diagrams in Science and Engineering, Piscataway, 2012: 17-23.

[4] Baker C L and Hoff W. DIRSAC: a directed sampling and consensus approach to quasi-degenerate data fitting [C]. 2013 IEEE Workshop on Applications of Computer Vision, Clearwater Beach, 2013: 154-159.

[5] El-Melegy M T. RANSAC algorithm with sequential probability ratio test for robust training of feed-forward neural networks[C]. Proceedings of International Joint Conference on Neural Networks, San Jose, 2011: 3256-3263.

[6] 周駿, 陳雷霆, 劉啟和, 等. 基于序貫概率及局部?jī)?yōu)化隨機(jī)抽樣一致性算法[J]. 儀器儀表學(xué)報(bào), 2012, 33(9): 2037-2044.

Zhou Jun, Chen Lei-ting, Liu Qi-he,Fast and accurate RANSAC based on optimal sequential probability test and local optimization[J]., 2012, 33(9): 2037-2044.

[7] Golban C, Szakats I, and Nedevschi S. Stereo based visual odometry in difficult traffic scenes[C]. 2012 Intelligent Vehicles Symposium, Alcalá de Henares, 2012: 736-741.

[8] 張文聰, 李斌, 鄧宏平, 等. 視線跟蹤過程中變形瞳孔的定位[J]. 電子與信息學(xué)報(bào), 2010, 32(2): 416-421.

Zhang Wen-cong, Li Bin, Deng Hong-ping,Distorted pupil localization in eye tracking[J].&, 2010, 32(2): 416-421.

[9] Xu M and Lu J. Distributed RANSAC for the robust estimation of three-dimensional reconstruction[J]., 2012, 6(4): 324-333.

[10] Martelli S, Marzotto R, Colombari A,FPGA-based robust ellipse estimation for circular road sign detection[C]. 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), San Francisco, 2010: 53-60.

[11] Marzotto R, Zoratti P, Bagni D,A real-time versatile roadway path extraction and tracking on an FPGA platform[J]., 2010, 114(11): 1164-1179.

[12] Dohi K, Hatanaka Y, Negi K,Deep-pipelined FPGA implementation of ellipse estimation for eye tracking[C]. 2012 22nd International Conference on Field Programmable Logic and Applications (FPL), Oslo, 2012: 458-463.

[13] 袁紅星, 吳少群, 朱仁祥, 等. 平面單應(yīng)性矩陣求解的CUDA 并行實(shí)現(xiàn)[J]. 微型機(jī)與應(yīng)用, 2012, 31(23): 38-41.

Yuan Hong-xing, Wu Shao-qun, Zhu Ren-xiang,CUDA-based parallel implementation of homography estimation[J].&, 2012, 31(23): 38-41.

[14] Lee Dong-hwa, Kim Hyong-jin, and Myung Hyun. GPU- based real-time RGB-D 3D SLAM[C]. 2012 9th International Conference on Ubiquitous Robots and Ambient Intelligence (URAI), Daejeon, 2012: 46-48.

[15] Fijany A and Hosseini F. Image processing applications on a low power highly parallel SIMD architecture[C]. IEEE Aerospace Conference, Big Sky, 2011.

[16] Fijany A and Diotalevi F. A cooperative search algorithm for highly parallel implementation of RANSAC for model estimation on Tilera MIMD architecture[C]. IEEE Aerospace Conference, Big Sky, 2012.

[17] 孫紅偉. 二項(xiàng)分布兩種近似計(jì)算的討論[J]. 河南教育學(xué)院學(xué)報(bào)(自然科學(xué)版), 2007, 16(1): 28-29.

Sun Hong-wei. Discussion about two approximate calculations of binomial distribution[J].(), 2007, 16(1): 28-29.

江 潔： 女，1973年生，教授，博士生導(dǎo)師，研究方向?yàn)閷?shí)時(shí)圖像處理和天體敏感器技術(shù).

凌思睿： 男，1988年生，碩士生，研究方向?yàn)閷?shí)時(shí)圖像處理和天體敏感器技術(shù).

Parallel Voting RANSAC and Its Implementation on FPGA

Jiang Jie Ling Si-rui

(-,,,100191,)

RANdom SAmple Consensus (RANSAC) performs poor with the mass of data, high outliers ratio and complicated models.In this paper, a highly parallel voting version of RANSAC is presented. On the basis of parallelizing the hypothetical stage and generating multiple models simultaneously, a novel strategy of voting to determine whether a point belongs to inliers is proposed. Conventional search for the inliers relative to the best model is saved. On parallel platforms represented by FPGA, this algorithm can take advantage of the parallel architecture and characteristics to achieve deep-pipelined parallel computing. Experiments demonstrate the good robustness of the proposed algorithm and its considerable improvement of both speed and throughput.

FPGA; RANdom SAmple Consensus (RANSAC); Parallel computing

TP391

A

1009-5896(2014)05-1145-06

10.3724/SP.J.1146.2013.00962

凌思睿 lingsirui@126.com

2013-07-04收到，2013-11-08改回

國(guó)家自然科學(xué)基金(61222304)和高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金(20121102110032)資助課題