HOUGH變換檢測線段IP設計

吳相濤，桑紅石,3

（1.華中科技大學 人工智能與自動化學院，湖北 武漢 430074；2.多譜信息處理技術國防科技重點實驗室，湖北 武漢 430074；3.圖像信息處理與智能控制重點實驗室，湖北 武漢 430074）

0 引 言

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

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

1 算法介紹與難點分析

1.1 算法介紹

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

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

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

圖1 HOUGH變換點-線變換示意圖

1.2 硬件實現難點分析

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

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

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

2 HOUGH變換硬件實現

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

2.1 峰值檢測模塊

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

圖2 兩級排序電路

圖3 單元示意圖

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

圖4 并行比較電路簡圖

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

2.2 臨近線段合并模塊

由于計算誤差或特殊圖像，臨近線段干擾不可避免，但通過觀察發現所有曲線并非任意方向分布，臨近干擾峰值只沿特定角度分布，對θ方向求導所得結果為：

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

根據式（3）可知，在峰值點處θ→θ0，為常數，即在峰值點處隨x的變化呈一次函數形式變換，ρ在峰值點處隨θ的變化是呈二次函數的形式，可知干擾點不會出現在水平方向，因為該方向上ρ不隨θ的改變而改變，所以在峰值點只出現在正負45°方向，并且斜率具有單調性，因此為確保正確無誤的進行干擾峰值的剔除，需要額外多搜尋出兩個點的峰值，最終需要搜尋3×4+1+1=14個峰值點，后續最值地址信息剔除臨近線段，剔除效果如圖5所示。

圖5 剔除效果

3 實驗結果

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

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

查閱相關資料，將其他學者硬件實現HOUGH變換檢測線段IP與本文相比較，由于各個設計面向的應用各有不同，圖像大小和測試平臺等存在一定差異，下面將從資源消耗、時間開銷、數據通過率以及處理性能等角度將本文設計方案與其他學者實現的方案進行對比并做大致評價，結果如表2所示。

表2 IP性能橫向比較

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

4 結 論

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