陳仁愛，凌　強(qiáng)，徐　駿，李　峰

(中國(guó)科學(xué)技術(shù)大學(xué) 信息科學(xué)技術(shù)學(xué)院，安徽 合肥 230026)

?

基于DSP的實(shí)時(shí)圓檢測(cè)算法的設(shè)計(jì)實(shí)現(xiàn)與優(yōu)化

陳仁愛，凌強(qiáng)，徐駿，李峰

(中國(guó)科學(xué)技術(shù)大學(xué) 信息科學(xué)技術(shù)學(xué)院，安徽 合肥 230026)

霍夫圓變換是圖像處理中人眼檢測(cè)的一種常見方法，但是其處理的數(shù)據(jù)量多，處理速度慢，在移植到DSP上后難以滿足實(shí)時(shí)性要求。對(duì)此，提出了一種將兩階段霍夫圓變換算法應(yīng)用到 TMS320C6000系列 DSP上的實(shí)現(xiàn)與優(yōu)化方法。首先，在算法上對(duì)霍夫圓變換使用Marr-Hildreth算子增強(qiáng)等方法進(jìn)行改進(jìn)以保證檢測(cè)的準(zhǔn)確率；之后根據(jù) DSP的特點(diǎn)，利用C代碼優(yōu)化、浮點(diǎn)定點(diǎn)轉(zhuǎn)換和軟件流水等技術(shù)對(duì)算法進(jìn)行深度優(yōu)化。實(shí)驗(yàn)結(jié)果表明，程序的運(yùn)行時(shí)間明顯縮短，為視線檢測(cè)的實(shí)時(shí)性實(shí)現(xiàn)創(chuàng)造了良好的條件。

C6000 DSP；霍夫變換；程序優(yōu)化

引用格式：陳仁愛，凌強(qiáng)，徐駿，等. 基于DSP的實(shí)時(shí)圓檢測(cè)算法的設(shè)計(jì)實(shí)現(xiàn)與優(yōu)化[J].微型機(jī)與應(yīng)用，2016,35(11)：93-96，100.

0　引言

在視頻圖像中快速地檢測(cè)出圓形是目標(biāo)跟蹤、目標(biāo)分類和行為理解等更高層次視頻圖像分析的重要基礎(chǔ)，比如人眼檢測(cè)、視線跟蹤和交通視頻分析等?；舴驁A變換是圖像處理中識(shí)別和定位圓形的常用方法，其準(zhǔn)確率高且與圖中形狀的方向無(wú)關(guān)[1-2]，被廣泛用于運(yùn)動(dòng)目標(biāo)軌跡的檢測(cè)與識(shí)別。在視線檢測(cè)領(lǐng)域，也有眾多關(guān)于它的研究。MATHEWS R 提出了一種利用霍夫圓變換來(lái)設(shè)計(jì)鼠標(biāo)的方法[3]，ZIA M A等人嘗試?yán)醚矍蜃粉檨?lái)為殘疾人設(shè)計(jì)輪椅[4]。

標(biāo)準(zhǔn)霍夫變換雖然具有顯著的優(yōu)勢(shì)，但其不足也不容忽視[5-6]。它需消耗大量的時(shí)空資源，對(duì)于在嵌入式平臺(tái)上進(jìn)行視線檢測(cè)這樣的應(yīng)用背景無(wú)法做到實(shí)時(shí)控制。目前有很多研究都僅針對(duì)算法上的改進(jìn)，而沒(méi)有結(jié)合具體的實(shí)現(xiàn)平臺(tái)的特點(diǎn)來(lái)進(jìn)行優(yōu)化，不能充分利用硬件的性能優(yōu)勢(shì)。本文擬在德州儀器的TMS320C6000系列DSP上使用兩階段霍夫變換算法來(lái)實(shí)現(xiàn)圓形檢測(cè)，并開展基于DSP平臺(tái)的程序優(yōu)化研究。

1　改進(jìn)的兩階段霍夫圓變換算法

[2]提出將霍夫變換一般化的方法，對(duì)于任何曲線，只要給出了它的函數(shù)方程，就可以利用霍夫變換的方法，將圖像空間變換到霍夫參數(shù)空間，利用投票的方法求得曲線參數(shù)。對(duì)于檢測(cè)圓的情形，由于圓的方程有3個(gè)未知量，變換到霍夫空間中需要一個(gè)三維的累加器，對(duì)于高清圖片來(lái)說(shuō)將耗費(fèi)大量的內(nèi)存，而且搜索極值時(shí)時(shí)間代價(jià)很大。這二者對(duì)于DSP平臺(tái)都是致命的，故在移植到DSP時(shí)本文采用了兩階段霍夫圓變換算法，并對(duì)其進(jìn)行性能上的改進(jìn)。本節(jié)闡述了基于兩階段霍夫圓變換算法的圓檢測(cè)方案設(shè)計(jì)。

1.1兩階段霍夫圓變換算法

兩階段霍夫圓變換是一種針對(duì)標(biāo)準(zhǔn)霍夫圓變換的參數(shù)空間分解的方法，主要目的是為了減少原算法的空間復(fù)雜度，其輸入是邊緣圖像[5]。

考慮如下圓的參數(shù)方程：

(1)

其中(x0,y0,r)是一組圓心和坐標(biāo)參數(shù)。兩階段霍夫圓變換的第一步是對(duì)圓心參數(shù)空間累加。根據(jù)圓的一階導(dǎo)數(shù)和二階導(dǎo)數(shù)的特性，過(guò)圓周上任意一點(diǎn)的圓切線的垂線經(jīng)過(guò)圓心，如圖1所示。對(duì)已知邊緣上的任意點(diǎn)做垂線，這些垂線將會(huì)在(a, b)空間匯集，形成一個(gè)熱點(diǎn)，在(a, b)空間搜索極值即得圓心坐標(biāo)。給定r的范圍，在邊緣點(diǎn)上做垂線段，得(a, b)空間。即：

(2)

A(i±a,j±b)←A(i±a,j±b)+E(i,j)

(3)

圖1　圓的方向?qū)?shù)示意

其中，(minr,maxr)是給定的半徑的范圍，也是做出的垂線段的長(zhǎng)度，A是(a,b)空間的累加器，E(i,j)是待檢測(cè)圖像的邊緣圖。在(a,b)空間搜索極值即得圓心坐標(biāo)。

求得圓心坐標(biāo)之后，在此基礎(chǔ)上可以進(jìn)行半徑參數(shù)空間的累加。對(duì)每一個(gè)檢測(cè)的圓，R空間累加方式為：

(4)

其中，E是邊緣圖，r是給定的半徑范圍。在R空間搜索極值即可求得半徑。

圖2　圓檢測(cè)整體流程設(shè)計(jì)

1.2圓形檢測(cè)整體方案設(shè)計(jì)

1.1節(jié)描述了一種節(jié)省空間開銷的霍夫變換方法，基于此，本節(jié)設(shè)計(jì)了一套圓檢測(cè)方案，增加了預(yù)處理和利用Marr-Hildreth算子進(jìn)行圖像增強(qiáng)等步驟，具體如圖2所示。

由于形狀只與灰度值有關(guān)，故首先獲取灰度圖。之后，對(duì)于含噪聲的圖像，對(duì)其進(jìn)行平滑處理，減少邊緣檢測(cè)的工作量和出錯(cuò)率。平滑操作使用高斯平均算子，模板大小為5，方差為1，實(shí)現(xiàn)時(shí)采用空域卷積的方式。為了保存更多的邊緣信息，本文使用一階及二階邊緣檢測(cè)的方式來(lái)求取邊緣圖而不是直接對(duì)灰度圖進(jìn)行二值化。一階邊緣提取使用Sobel算子，包括水平Sobel算子和垂直Sobel算子，最后取二者的幾何平均作為最終的Sobel圖像。在使用圓的方向?qū)?shù)縮減參數(shù)空間時(shí)需要使用邊緣圖像的方向信息，本文使用Sobel處理后的圖像來(lái)直接求得。

對(duì)于每個(gè)被檢測(cè)到的邊緣點(diǎn)(i,j)，計(jì)算其方向角度θ(i,j)：

(5)

對(duì)于邊緣更復(fù)雜的圖像，當(dāng)一階邊緣檢測(cè)過(guò)粗或者錯(cuò)誤時(shí)，使用二階邊緣檢測(cè)能獲得更好的檢測(cè)效果。Marr-Hildreth算子是利用高斯濾波的一種二階濾波方式，它先對(duì)圖像進(jìn)行高斯平滑，之后應(yīng)用拉普拉斯運(yùn)算，即：

(6)

其中P是待處理的圖像，g(x,y)是高斯平滑濾波器。此外，Marr-Hildreth算子還被用于圖像增強(qiáng)。

在獲得邊緣圖像和邊緣方向信息之后使用1.1節(jié)中的方法就能求得圓心和半徑。

1.3圓形檢測(cè)中的實(shí)現(xiàn)細(xì)節(jié)

由于邊緣檢測(cè)的不精確性和待檢測(cè)圓的不確定性，兩階段霍夫圓變換方法在實(shí)現(xiàn)的過(guò)程中存在一些問(wèn)題，本節(jié)將討論這些問(wèn)題的解決方式。

(7)

實(shí)驗(yàn)中發(fā)現(xiàn)大的圓由于邊緣方向估計(jì)誤差更大，在圓心區(qū)域的偏差會(huì)更大，這會(huì)使它的聚集程度下降，從而與由半徑大帶來(lái)的優(yōu)勢(shì)相抵消，此時(shí)k可設(shè)為1。

對(duì)于同心圓，在R空間累加后選擇合適的閾值以保留多個(gè)峰值，能獲得不同的半徑值。

圖3是一組檢測(cè)結(jié)果示意圖。其中圖(c) 是將θ映射到(0,255) 得來(lái)。在采取合適的參數(shù)后能獲得較好的檢測(cè)結(jié)果。

圖3　檢測(cè)結(jié)果圖示

2　基于C6000 DSP的移植與優(yōu)化

2.1移植到DSP

本文使用的硬件平臺(tái)是TI的TMS320C64x+TM定點(diǎn)型DSP核，使用的開發(fā)環(huán)境為CCSv4。使用C64x+ simulator進(jìn)行軟件仿真，通過(guò)CCS的時(shí)鐘工具測(cè)得試運(yùn)行時(shí)鐘周期，通過(guò)profile工具分析工程耗時(shí)分布[7]。

2.2具體的優(yōu)化步驟

本文的優(yōu)化基于所用DSP的結(jié)構(gòu)特性，盡量充分利用DSP的計(jì)算資源來(lái)縮短檢測(cè)時(shí)間[8-9]。本節(jié)將介紹本文使用的優(yōu)化方法。

2.2.1基于編譯器的優(yōu)化方法

CCS的編譯器中設(shè)置了眾多參數(shù)，選擇合適的參數(shù)能減少檢測(cè)耗時(shí)。

選擇優(yōu)化級(jí)別。由于本文不考慮代碼體積，故使用-o3文件級(jí)優(yōu)化。

使用-mt。假設(shè)不存在多個(gè)指針對(duì)同一個(gè)內(nèi)存(塊)進(jìn)行讀寫操作。

使用 -mh。 允許編譯器取超過(guò)數(shù)組邊界num字節(jié)的值。該操作使編譯器在編排軟件流水時(shí)有額外的彈性，可提高流水性能。在CMD文件中定義大于num的緩存空間，避免 EDMA或其他cache沖突。

不使用 -g、-ss等參數(shù)。這些參數(shù)對(duì)調(diào)試很有效，但是會(huì)造成性能下降，在最終發(fā)布產(chǎn)品時(shí)不應(yīng)使用。

CCS編譯器選項(xiàng)中有部分能減少手工整定時(shí)間但是對(duì)代碼性能沒(méi)有影響的參數(shù)，使用這些參數(shù)有助于程序優(yōu)化。使用-s[-k|-al]-o[2|3]能生成優(yōu)化后的類似于C的代碼，且優(yōu)化器描述被嵌套在匯編代碼中，使用-mw或者-mw-al輸出額外的關(guān)于軟件流水的信息，包括單次循環(huán)的調(diào)度方式；使用-on2-o3生成*.nfo文件，以給出高級(jí)別的優(yōu)化總結(jié)和可用的優(yōu)化建議。

2.2.2手工整定方法

僅使用基于編譯器的優(yōu)化所減少的程序耗時(shí)是有限的，本文對(duì)算法的實(shí)時(shí)性要求較高，需要在2.2.1節(jié)的基礎(chǔ)上進(jìn)行手工整定。手工整定的方式很多，本文使用的幾種方法有基于編譯器和優(yōu)化器描述、浮點(diǎn)定點(diǎn)轉(zhuǎn)換、不用除法等。

根據(jù)優(yōu)化器描述給所有安全的指針添加restrict關(guān)鍵字，消除循環(huán)間的依賴，使生成的匯編文件中循環(huán)依賴項(xiàng)值為零；根據(jù)匯編嵌入信息添加pragma 指令MUST_ITERATE和UNROLL，告訴編譯器循環(huán)的最大值、最小值、公約數(shù)和展開次數(shù)，并根據(jù)軟件流水信息中各資源的使用情況在循環(huán)前使用 _nassert() 告訴編譯器數(shù)據(jù)是64位對(duì)齊的，一次讀取多個(gè)對(duì)齊數(shù)據(jù)以減少D單元和T通道的使用數(shù)，以能較好地平衡資源。這些措施極大地提高了軟件流水的效率。

由于算法涉及眾多的浮點(diǎn)運(yùn)算，在定點(diǎn)型甚至浮點(diǎn)型DSP中效率都很低，故在精度允許的情況下，使用定點(diǎn)運(yùn)算代替浮點(diǎn)型運(yùn)算。浮點(diǎn)轉(zhuǎn)換為定點(diǎn)除了手動(dòng)使用Qn定標(biāo)外，對(duì)于C64x+ DSP還可以使用TI的C64x+ IQmath庫(kù)。IQmath集合了很多高精度且高度優(yōu)化的數(shù)學(xué)函數(shù)，適合于將浮點(diǎn)的算法轉(zhuǎn)換成定點(diǎn)[10]。除了提供_iq數(shù)據(jù)類型及各類型互相轉(zhuǎn)換之外，IQmath還提供了各種高度優(yōu)化的數(shù)學(xué)函數(shù)比如_IQcos(余弦函數(shù))，并且支持可調(diào)節(jié)精度，在不同地方可以選擇不同的定標(biāo)Q值，即GLOBAL_Q可以在需要的地方指定0～31中的任意值。比如融合兩個(gè)Sobel算子時(shí)求兩個(gè)數(shù)的幾何平均：

(*imageTot)[i][j]= pow( (*imageH)[i][j]*(*imageH)[i][j] +(*imageV)[i][j]*(*imageV)[i][j], 0.5f);

可以修改為：

tmp=_IQpow(*imageH[i][j],2) +_IQpow(*imageV[i][j],2);

//sqrt(H^2+V^2)

*imageTot[i][j] = _IQsqrt(tmp);

//pow(tmp,0.5f)

先將數(shù)據(jù)轉(zhuǎn)換成_iq類型，然后使用IQmath中的_IQpow和_IQsqrt來(lái)求冪和根號(hào)，之后再轉(zhuǎn)換回需要的float型。

對(duì)于除法運(yùn)算，DSP是利用函數(shù)調(diào)用來(lái)完成，耗費(fèi)的時(shí)鐘周期比乘法高出2個(gè)數(shù)量級(jí)以上。為了消除除法，可以使用移位或者查找表(look-up table)來(lái)代替。比如:

(int)(_abs(im[i][j] + shift) /maxval*255);

其中maxval值在0～255之間，可以提前將255/maxval計(jì)算出來(lái)，計(jì)算時(shí)查表代替；或者使用?8替代*255。另外，使用 _IQdiv( _iq A, _iq B) 函數(shù)可完成_iq類型的除法。

對(duì)于DSP的優(yōu)化方法還有很多，如使用內(nèi)聯(lián)函數(shù)和線性匯編等，在進(jìn)一步優(yōu)化過(guò)程中可使用。

2.3優(yōu)化結(jié)果與分析

在綜合了各種優(yōu)化方式之后，重新使用profile測(cè)試各部分的時(shí)鐘周期，保持其他條件不變。程序優(yōu)化前后所用的時(shí)間見表1?？梢娊?jīng)過(guò)優(yōu)化，耗時(shí)明顯減少。

表1　優(yōu)化前后部分函數(shù)耗時(shí)對(duì)比(時(shí)鐘周期數(shù))

3　結(jié)論

本文先在PC上實(shí)現(xiàn)了基于霍夫變換的圓形檢測(cè)算法，然后將它移植到了DSP上并進(jìn)行了基于時(shí)間的優(yōu)化分析，使得實(shí)時(shí)性有很大的提高。

若要將此算法應(yīng)用到人眼檢測(cè)，可以在前述的基礎(chǔ)上繼續(xù)改進(jìn)，比如縮減霍夫變換中r的范圍，在R空間尋找峰值時(shí)指定目標(biāo)是2個(gè)等。本文所完成的只是視線跟蹤中人眼檢測(cè)的一部分，離實(shí)際應(yīng)用還很遠(yuǎn)。本文設(shè)計(jì)還有很多不足，希望在未來(lái)的工作中繼續(xù)改進(jìn)。

參考文獻(xiàn)

[1] BALLARD D H. Generalizing the Hough transform to detect arbitraryshapes[J]. Pattern Recognition, 1981, 13(2): 111-122.

[2] YUEN H K, PRINCEN J, ILLINGWORTH J. Comparative study of Hough transform methods for circle finding[J]. Image and Vision Computing, 1990, 8(1): 71-77.

[3] MATHEWS R, CHANDRA N. Computer mouse using eyetracking system based on houghman circle detection algorithm with grid analysis[J]. International Journal of Computer Applications, 2012, 40(13): 12-16.

[4] ZIA M A, ANSARI U, JAMIL M, et al.Face and eye detection in images using skin color segmentation and circular Hough transform[C].Robotics and Emerging Allied Technologies in Engineering (iCREATE), 2014 International Conference on. IEEE, 2014: 211-213.

[5] NIXON M S,AGUADO A S. 特征提取與圖像處理 (第二版)[M].李實(shí)英，楊高波，譯.北京：電子工業(yè)出版社, 2010.

[6] ILLINGWORTH J, KITTLER J. A survey of the Hough transform[J]. Graphical Models Graphical Models and Image Processing Computer Vision, Graphics, and Image Processing, 1988, 44(1): 87-116.

[7] 美國(guó)德州儀器公司. TMS320C6000系列DSP編程工具與指南[M].田黎育、何佩琨, 朱夢(mèng)宇，譯. 北京：清華大學(xué)出版社, 2006.

[8] TEXAS INSTRUMENTS. Introduction to TMS320C6000 DSP Optimization[EB/OL]. (2011-11-xx)[2016-01-10].http://www.ti.com/lit/an/sprabf2/sprabf2.pdf.

[9] GRANSTON E. Hand-tuning loops and control code on the TMS320C6000[EB/OL]. (2006-08-xx)[2016-01-10].http://www.ti.com/lit/an/spra666/spra666.pdf.

[10] Texas Instruments. TMS320C64x+ IQmath library user’s guide[EB/OL]. (2008-12-xx)[2016-01-10].http://www.ti.com.cn/cn/lit/ug/sprugg9/sprugg9.pdf.

Implementation and optimization of DSPs based real-time circle detection

Chen Renai，Ling Qiang，Xu Jun，Li Feng

(School of Information Science and Technology, University of Science and Technology of China, Hefei 230026, China)

Circular Hough transform is a common method for eye detection in image processing. However, it requires large amount of data processing, leading a long processing period, so that it cannot satisfy the real-time requirements when transplanted to DSPs. In this regard, this paper puts forward a method for circle detection using two-stage circular Hough transform which can be applied to TMS320C6000 DSPs as well as some optimization approaches. Firstly, it uses Marr-Hildreth operator to improve circular detection algorithm to ensure accuracy. Then C code optimization, floating-point to fixed-point conversion and software pipeline technology are utilized to optimize the algorithm in depth according to the characteristics of DSPs. Experimental results show that the execution time of the program is significantly reduced, which creates a good condition for the realization of real-time eye sight detection.

C6000 DSP; Hough transform; code optimization

TP368

A

10.19358/j.issn.1674- 7720.2016.11.028

2016-01-14)

陳仁愛(1992-)，男，碩士研究生，主要研究方向：嵌入式系統(tǒng)、圖像處理。

凌強(qiáng)(1975-)，通信作者，男，博士，副教授，博士生導(dǎo)師，主要研究方向：網(wǎng)絡(luò)化控制、嵌入式系統(tǒng)。E-mail:qling@ustc.edu.cn。

徐駿(1977-)，男，講師，主要研究方向：嵌入式系統(tǒng)。