HOUGH變換檢測(cè)線段IP設(shè)計(jì)

吳相濤，桑紅石,3

（1.華中科技大學(xué) 人工智能與自動(dòng)化學(xué)院，湖北 武漢 430074；2.多譜信息處理技術(shù)國(guó)防科技重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430074；3.圖像信息處理與智能控制重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430074）

0 引 言

線段識(shí)別和定位在圖像處理領(lǐng)域如機(jī)場(chǎng)跑道和橋梁檢測(cè)識(shí)別等有著重要應(yīng)用，這些處理任務(wù)往往有圖像信息大、實(shí)時(shí)性要求高且資源消耗大等特點(diǎn)，純軟件的處理方式難以滿足系統(tǒng)實(shí)時(shí)性處理要求，因此硬件加速方案是合理選擇[1,5]。硬件加速是基于專用集成電路（Application Specific Integrated Circuit，ASIC）或現(xiàn)場(chǎng)可編程邏輯門陣列（Field-Programmable Gate Array，F(xiàn)PGA）設(shè)計(jì)的高速計(jì)算電路結(jié)構(gòu)，電路通常采用并行和流水線等特定結(jié)構(gòu)，實(shí)現(xiàn)處理任務(wù)的高計(jì)算速度與高效率運(yùn)行[2]。

HOUGH變換因計(jì)算重復(fù)度高、運(yùn)算量大、模塊相對(duì)獨(dú)立且不包含復(fù)雜控制序列、動(dòng)態(tài)數(shù)組以及動(dòng)態(tài)可變長(zhǎng)度循環(huán)任務(wù)等特點(diǎn)，常用于硬件加速檢測(cè)線段，可充分發(fā)揮硬件并行與流水的優(yōu)勢(shì)，且具備極好的魯棒性與抗干擾性，但當(dāng)檢測(cè)非單一線段時(shí)，HOUGH變換存在峰值檢測(cè)最值搜索困難和臨近線段干擾真實(shí)峰值等問題。根據(jù)HOUGH變換算法特點(diǎn)，提出一種適合硬件加速的HOUGH變換檢測(cè)線段IP實(shí)現(xiàn)方案，可檢測(cè)一幀圖像中不含干擾線段的5條共線點(diǎn)最多的線段。

1 算法介紹與難點(diǎn)分析

1.1 算法介紹

HOUGH變換是利用平面點(diǎn)-線變換思想，將笛卡爾坐標(biāo)系中二值圖像的每個(gè)特征點(diǎn)通過HOUGH變換轉(zhuǎn)化為極坐標(biāo)系中的一條曲線，笛卡爾坐標(biāo)系中共線的點(diǎn)映射到極坐標(biāo)系中是對(duì)應(yīng)曲線的交點(diǎn)，通過交點(diǎn)獲取直線極經(jīng)ρ與極角θ并結(jié)合地址信息完成特殊圖像中的臨近線段合并，最后通過首末并行有限次掃描獲取線段端點(diǎn)。

假設(shè)笛卡爾坐標(biāo)系中直線y=kx+b上有點(diǎn)(x1,y1)，HOUGH變換是將方程參數(shù)和變量交換，即將x、y視為已知參數(shù)，將k、b視為坐標(biāo)變量，則直線函數(shù)為b=-kx1+y1，為保證k在任意時(shí)刻的有效性，將該函數(shù)轉(zhuǎn)化為極坐標(biāo)系下的函數(shù)為：

同理，直線上的點(diǎn)(x2,y2)和(x3,y3)映射到極坐標(biāo)系下為ρ=x2cosθ+y2sinθ和ρ=+x3cosθ+y3sinθ，且 3 條曲線在極坐標(biāo)系下交于點(diǎn)(ρ0,θ0)，具有相同的極經(jīng)和極角。可知，笛卡爾坐標(biāo)系中的點(diǎn)經(jīng)HOUGH變換映射為極坐標(biāo)系中的曲線，笛卡爾坐標(biāo)系中共線的點(diǎn)映射為極坐標(biāo)系中曲線相交的點(diǎn)。HOUGH變換點(diǎn)-線變換示意如圖1所示。

圖1 HOUGH變換點(diǎn)-線變換示意圖

1.2 硬件實(shí)現(xiàn)難點(diǎn)分析

HOUGH算法檢測(cè)線段實(shí)際實(shí)現(xiàn)過程中，除了圖片大小可配置、數(shù)計(jì)算復(fù)雜度高且計(jì)算量大、存儲(chǔ)資源需求高以及時(shí)間開銷大等可通過并行流水線思想解決外，還面臨著峰值檢測(cè)最值搜索困難和臨近線段干擾真實(shí)峰值等需要優(yōu)化檢測(cè)方案或電路結(jié)構(gòu)才能實(shí)現(xiàn)的部分，特別是檢測(cè)任務(wù)非單一線段時(shí)，以上問題更加尖銳。

峰值檢測(cè)即需要在累積參數(shù)表形成后，找出其中最大的5個(gè)有效峰值。由于所需峰值非單一值，峰值問題轉(zhuǎn)化為排序問題，同時(shí)累計(jì)參數(shù)存儲(chǔ)在SRAM中，最快只能單周期處理一個(gè)數(shù)據(jù)，不能實(shí)現(xiàn)多數(shù)據(jù)輸入電路參與排序，即輸入數(shù)據(jù)帶寬低。而且結(jié)果要求同時(shí)輸出多干個(gè)可能峰值，若采用常見排序算法，如冒泡排序、堆排序、樹狀結(jié)構(gòu)排序以及二階段搜索排序等會(huì)多次讀取存儲(chǔ)器，大大提升時(shí)間開銷，因此急需一種不重復(fù)加載數(shù)據(jù)、低輸入帶寬并行輸出結(jié)果的排序電路。本文提出并行比較電路滿足上述要求，排序效率高，結(jié)果準(zhǔn)確。

雖然HOUGH算法在直線檢測(cè)時(shí)具備極好的魯棒性，但對(duì)于一些特殊圖像，如過長(zhǎng)過短線段均為待檢目標(biāo)等存在臨近線段干擾真實(shí)峰值問題，另外由于圖像數(shù)字化不可避免的偏差，也導(dǎo)致出現(xiàn)虛假峰值，對(duì)實(shí)際使用形成一定干擾，因此有必要進(jìn)行類似直線合并。本文通過觀察結(jié)合理論證明虛假峰值圍繞真實(shí)峰值呈一定方向出現(xiàn)，根據(jù)該特點(diǎn)結(jié)合峰值地址判斷虛假峰值位置，進(jìn)而進(jìn)行類似直線合并得到真實(shí)有效5條共線點(diǎn)最多的線段。

2 HOUGH變換硬件實(shí)現(xiàn)

硬件實(shí)現(xiàn)參數(shù)計(jì)算部分采用6路并行12路存儲(chǔ)計(jì)算方案，模塊并行度n=12，每輸入一個(gè)坐標(biāo)，同時(shí)控制三角函數(shù)計(jì)算CORDIC模塊輸出15個(gè)角度的三角函數(shù)值并計(jì)算直線參數(shù)ρ，特征點(diǎn)計(jì)算并存儲(chǔ)完成之后再輸入下一個(gè)特征點(diǎn)坐標(biāo)值，待所有特征點(diǎn)計(jì)算完成后，通過并行比較電路得到累計(jì)參數(shù)表中最大的14個(gè)值，隨后去除臨近干擾值，得到真實(shí)直線對(duì)應(yīng)峰值。根據(jù)其地址獲取直線參數(shù)k、b，最后首末兩端同時(shí)掃描特征點(diǎn)，得到的第一個(gè)滿足式（1）的特征點(diǎn)分別對(duì)應(yīng)線段首點(diǎn)和末點(diǎn)，最終檢測(cè)出一幀圖像中共線點(diǎn)最多的5條線段。

2.1 峰值檢測(cè)模塊

峰值檢測(cè)模塊采用兩級(jí)排序電路，如圖2所示，結(jié)合參數(shù)計(jì)算模塊，需要將12路存儲(chǔ)器整合為6個(gè)獨(dú)立存儲(chǔ)bank，第一級(jí)6路并行排序搜尋單bank中最大的14個(gè)峰值保存在寄存器中，第二級(jí)排序電路用于從84個(gè)寄存器中搜尋最大的5個(gè)峰值為真實(shí)直線參數(shù)，兩級(jí)排序電路都采用并行比較排序電路進(jìn)行搜索。排序單元示意如圖3所示。

圖2 兩級(jí)排序電路

圖3 單元示意圖

下述以數(shù)字1到14的倒序排序介紹本文排序電路結(jié)構(gòu)，倒序排序是時(shí)間復(fù)雜度和空間復(fù)雜度最高的排序，具有一般性。每次運(yùn)算時(shí)數(shù)據(jù)兩兩比較，假設(shè)所需為降序排序，較大的數(shù)據(jù)位置上升，較小的數(shù)據(jù)位置下降，然后奇偶交叉兩兩比較，升降原則同上，每輪比較奇偶交替，依此類推，這樣理論上最多只需要C214次兩兩比較即可排出正確順序。同時(shí)本文設(shè)計(jì)的是同步時(shí)序電路，為避免時(shí)序違例，排序電路3周期完成，詳細(xì)電路如圖4所示，左邊為第一個(gè)時(shí)鐘周期內(nèi)的運(yùn)算邏輯，中間部分為第二個(gè)時(shí)鐘周期運(yùn)算邏輯，右邊為第三個(gè)時(shí)鐘周期內(nèi)的運(yùn)算邏輯。排序完成后輸入端數(shù)據(jù)更新，更新個(gè)數(shù)可配置，本文為2，依此類推排完所有存儲(chǔ)器數(shù)據(jù)。

圖4 并行比較電路簡(jiǎn)圖

本文實(shí)測(cè)32 760個(gè)數(shù)據(jù)僅需5 564個(gè)周期即可完成排序，排序效率，相較二階段搜索算法提升約60%，相較樹狀比較電路及冒泡排序、堆排序等在參數(shù)累積表中數(shù)據(jù)不重復(fù)加載的前提下，成功實(shí)現(xiàn)多值并行排序輸出[1]。

2.2 臨近線段合并模塊

由于計(jì)算誤差或特殊圖像，臨近線段干擾不可避免，但通過觀察發(fā)現(xiàn)所有曲線并非任意方向分布，臨近干擾峰值只沿特定角度分布，對(duì)θ方向求導(dǎo)所得結(jié)果為：

由式（2）可知，ρ的斜率取值范圍在之間，所以干擾點(diǎn)一定不會(huì)出現(xiàn)在豎直方向，該方向上ρ對(duì)θ的斜率為無窮大，同時(shí)極坐標(biāo)系下的交點(diǎn)有θ→θ0，即所有共線點(diǎn)有相同的θ，也就是說在峰值處不會(huì)隨著θ的變換而變化，而是根據(jù)x的改變而改變，對(duì)式（2）沿x方向求偏導(dǎo)得：

根據(jù)式（3）可知，在峰值點(diǎn)處θ→θ0，為常數(shù)，即在峰值點(diǎn)處隨x的變化呈一次函數(shù)形式變換，ρ在峰值點(diǎn)處隨θ的變化是呈二次函數(shù)的形式，可知干擾點(diǎn)不會(huì)出現(xiàn)在水平方向，因?yàn)樵摲较蛏夕巡浑Sθ的改變而改變，所以在峰值點(diǎn)只出現(xiàn)在正負(fù)45°方向，并且斜率具有單調(diào)性，因此為確保正確無誤的進(jìn)行干擾峰值的剔除，需要額外多搜尋出兩個(gè)點(diǎn)的峰值，最終需要搜尋3×4+1+1=14個(gè)峰值點(diǎn)，后續(xù)最值地址信息剔除臨近線段，剔除效果如圖5所示。

圖5 剔除效果

3 實(shí)驗(yàn)結(jié)果

功能驗(yàn)證及上板測(cè)試后，實(shí)測(cè)IP處理一幀64×64像素大小的圖像消耗9 901個(gè)時(shí)鐘周期，IP實(shí)際運(yùn)行時(shí)鐘以150 MHz為例，處理一張64×64像素（特征點(diǎn)占比約為5.4%）大小的圖像需要0.066 ms，每秒可以處理約15張64×64像素大小的圖片，數(shù)據(jù)通過率達(dá)1.8×107pixel/s，滿足系統(tǒng)實(shí)時(shí)性處理要求，IP處理不同大小圖像性能見表1。

表1 IP處理不同大小圖像性能

查閱相關(guān)資料，將其他學(xué)者硬件實(shí)現(xiàn)HOUGH變換檢測(cè)線段IP與本文相比較，由于各個(gè)設(shè)計(jì)面向的應(yīng)用各有不同，圖像大小和測(cè)試平臺(tái)等存在一定差異，下面將從資源消耗、時(shí)間開銷、數(shù)據(jù)通過率以及處理性能等角度將本文設(shè)計(jì)方案與其他學(xué)者實(shí)現(xiàn)的方案進(jìn)行對(duì)比并做大致評(píng)價(jià)，結(jié)果如表2所示。

表2 IP性能橫向比較

依據(jù)表1和表2可知，得益于在峰值檢測(cè)和端點(diǎn)搜尋等方面的改進(jìn)，本文設(shè)計(jì)的HOUGH變換檢測(cè)線段IP數(shù)據(jù)通過率最高可達(dá)9.58×107 pixel/s，處理性能較其他實(shí)現(xiàn)方案有較大提升，在實(shí)際項(xiàng)目中可以滿足系統(tǒng)實(shí)時(shí)性處理要求。除此之外，本文在參數(shù)計(jì)算及存儲(chǔ)，模塊用6路并行外加少量寄存器達(dá)到12路并行的效果，相比其他方案資源消耗有減少約21%。同時(shí)本文對(duì)臨近線段進(jìn)行合并，剔除真實(shí)待求線段附近的誤差線段，檢測(cè)結(jié)果更加準(zhǔn)確，滿足實(shí)際使用過程中目標(biāo)識(shí)別的應(yīng)用要求。

4 結(jié) 論

本文硬件加速方案較好的實(shí)現(xiàn)二值圖像快速線段檢測(cè)，所設(shè)計(jì)的峰值檢測(cè)電路效率大幅提升，針對(duì)臨近線段干擾作了一定的探索。在機(jī)場(chǎng)跑道和橋梁檢測(cè)中取得較好效果，得到初步應(yīng)用。筆者后續(xù)將繼續(xù)深究HOUGH變換算法硬件實(shí)現(xiàn)，嘗試通過在特征點(diǎn)提取階段指定合理規(guī)則減少特征點(diǎn)數(shù)量，以獲得加速效果。