基于DSP的快速Hough變換圓檢測算法的實(shí)現

　　1 引言

　　數字圖像處理技術(shù)廣泛應用于機器視覺(jué)、自動(dòng)化檢測和視頻監控等領(lǐng)域。通用的圖像處理系統采用圖像采集卡將圖像傳送至PC，從而實(shí)現圖像處理的各種算法。近年來(lái)，隨著(zhù)集成電路和嵌入式技術(shù)的發(fā)展，特別是DSP集成度、穩定性、運算速度、數據吞吐量等性能的不斷提高，以DSP為核心的實(shí)時(shí)圖像處理系統得到開(kāi)發(fā)。采用DSP實(shí)現快速數字圖像處理可將算法嵌入到DSP中，充分利用DSP的高速性和并行性，提高系統的運行速度，達到數字圖像處理的實(shí)時(shí)性。相對于基于PC機的通用圖像處理系統，基于DSP的圖像處理系統具有體積小，功耗低等優(yōu)點(diǎn)，適用于嵌入式系統領(lǐng)域。

　　在圖像處理中檢測圓通常需要計算圓形度，半徑，圓心位置等圓參數。Hough變換是目前應用最廣泛的圓檢測方法，該方法可靠性高，在噪聲、變形、甚至部分區域丟失的狀態(tài)下仍然能取得理想效果。但其缺點(diǎn)是計算復雜，內存需求大。算法的實(shí)時(shí)性很差，不能滿(mǎn)足實(shí)時(shí)性的要求。

　　根據某項工程的實(shí)際要求，對標準Hough變換檢測圓算法進(jìn)行改進(jìn)，并在TMS320DM642平臺上實(shí)現，取得較好的檢測效果，并達到實(shí)時(shí)性要求。

　　2 算法運行平臺

　　算法運行平臺采用北京合眾達公司的SEED-DTK-VPM642多媒體實(shí)驗平臺，該平臺采用TI公司的TMS320DM642作為核心處理器。TMS320DM642是專(zhuān)用于數字媒體應用的高性能32位定點(diǎn)DSP，工作主頻最高達720 MHz，處理性能可達5 760 MI／s，強大的圖像處理能力為實(shí)現算法實(shí)時(shí)性和可靠性提供保證。該實(shí)驗平臺的整體功能框圖如圖1所示。前端通過(guò)CCD攝像機獲得視頻圖像，經(jīng)視頻解碼器TVP5150的數字化處理后，形成并行數字碼流以EDMA傳輸方式將數據傳送到TMS320DM642的數據輸入緩沖區，對圖像進(jìn)行實(shí)時(shí)處理后的數據自動(dòng)通過(guò)EDMA傳輸至數據輸出緩沖區，再通過(guò)視頻編碼器SAA7121形成碼流，傳送到顯示器顯示檢測結果。在整個(gè)算法的實(shí)現過(guò)程中，為了滿(mǎn)足實(shí)時(shí)性的要求，都是以EDMA的傳輸方式傳輸數據。

　　3 Hongh變換圓檢測算法的實(shí)現

　　3．1 Hough變換圓檢測算法的改進(jìn)

　　Hough變換的基本思想是將圖像從空間域變換到參數空間，用大多數邊界點(diǎn)滿(mǎn)足的某種參數形式來(lái)描述圖像中的曲線(xiàn)。假設在x-y平面檢測并確定一個(gè)圓的參數，圖像中待檢測圓周點(diǎn)的集合為{(xi，yi)，i=1，2，3，…，n}，(x，y)為該集合中的一點(diǎn)，其在參數坐標系(a，b，r)中解析式為：

　　該解析式對應的曲面為三維錐面。圖像中任意確定的一點(diǎn)均有參數空間的一個(gè)三維錐面與之對應。對于圓周上的任一點(diǎn){(xi,yi)，i=1，2，3，…，n}，這些三維錐面構成圓錐面簇，如圖2所示。

　　若集合中的點(diǎn)均在同一個(gè)圓周上，則這些圓錐面簇相交于參數空間上某一點(diǎn)，該點(diǎn)恰好對應于圖像平面的圓心坐標及圓的半徑。Hough變換在計算上將參數空間進(jìn)一步分割為累加器單元A(i，j，k)，并先使累加器單元置零。根據式(1)對參數作相應循環(huán)，如果一個(gè)a(i)值得到相應的b(j)，r(k)，就令A(i,j,k)=A(i，j,k)+1。最后對每個(gè)累加器進(jìn)行比較，找到最大值累加器，該累加器所對應的參數值(a,b,r)，就是在平面上所要檢測圓的圓心及半徑。

　　標準Hough變換的計算非常復雜，在圓形檢測應用中隨著(zhù)取值范圍的不斷擴大，在參數域的三維數組尺寸成正比例增加，需要占用大量計算機內存，計算效率低下。因此，盡可能縮小參與Hough變換的參數域范圍是提高其效率的關(guān)鍵。對其改進(jìn)的步驟如下：

　　第一步：對圖像作canny邊緣檢測處理，得出圖像中待檢測圓的單像素寬的邊緣；

　　第二步：求出圖像中待檢測圓邊緣在上，下，左，右4個(gè)方向上的極點(diǎn)，然后根據圓的幾何對稱(chēng)性，采用“最小外接矩形法”估算待檢測圓的圓心及半徑，生成相應的子圖，并濾除圖像中的噪聲?！白钚⊥饨泳匦畏ā惫浪銏A參數方法如圖3所示，其中圓心O為

　　第三步：考慮到圖像可能存在缺陷和噪聲，對估算所得到的圓心及半徑進(jìn)行適量縮放，從而縮小參與Hough變換的參數域范圍。

　　第四步：在確定的圓心及半徑范圍內，根據圓的參數方程進(jìn)行。Hough變換，從而檢測圓的參數。

　　3．2 基于DSP／BIOS和RF5架構的算法實(shí)現

　　算法的實(shí)現是基于CCS和DSP／BIOS及TI倡導的DSP軟件架構RF5。該算法分為輸入任務(wù)、處理任務(wù)、輸出任務(wù)3個(gè)任務(wù)，軟件框架如圖4所示。

　　在初始化完成后，系統進(jìn)入DSP／BIOS任務(wù)調度管理，3個(gè)任務(wù)通過(guò)RF5的SCOM模塊互相發(fā)送消息。

　　這3個(gè)任務(wù)完成的工作是：

　　(1)輸入任務(wù) 從輸入設備驅動(dòng)程序獲得視頻圖像。它使用驅動(dòng)程序提供的FVID_exchange調用從輸入設備獲得一幀新視頻圖像。輸入任務(wù)接著(zhù)發(fā)送消息到處理任務(wù)，消息中包含圖像數據指針，接著(zhù)等待輸出任務(wù)發(fā)送來(lái)的消息以繼續運行。

　　(2)處理任務(wù) 一直等到接收輸入任務(wù)，包含圖像數據指針消息，才開(kāi)始激活運行。對接收到圖像數據進(jìn)行預處理，得出圖像中待檢測圓的細邊緣，然后調用改進(jìn)的Hough變換檢測圓的參數，接著(zhù)發(fā)送消息到輸出任務(wù)，消息中包含經(jīng)Hough變換檢測后生成的圖像數據指針，然后等待輸入任務(wù)發(fā)送來(lái)的消息以繼續運行。

　　(3)輸出任務(wù) 將圖像顯示在顯示設備上，使用驅動(dòng)程序提供的FVID_exchange調用實(shí)現圖像的顯示，接著(zhù)發(fā)送消息到輸入任務(wù)，然后等待處理任務(wù)發(fā)送來(lái)的消息以繼續運行。

　　4 實(shí)驗結果

　　采用某光纖插針內孔參數檢測項目中所獲取的內孔圓(如圖5a所示，實(shí)際圖像大小1 392×1 040像素，限于篇幅，縮小為原圖的10％)來(lái)檢驗算法效果。原圖的實(shí)際圓心坐標為(678，503)，半徑為462。圖5b為使用Canny算子檢測得到的邊緣圖像；圖5c為采用本文算法得到的檢測結果。表1、表2分別列出了基于PC平臺和TMS320DM642平臺采用本文算法與采用標準Hough算法分別對圖5a進(jìn)行圓參數檢測所得結果、占有內存大小及耗時(shí)的對比。

　　從實(shí)驗結果看出，經(jīng)改進(jìn)后的Hough變換圓檢測算法，無(wú)論是基于PC平臺還是TMS320DM642平臺，與傳統的Hough變換算法相比，算法的運算量、內存需求、耗時(shí)都有了大幅度的削減，因而有效地提高了圓的檢測效率，滿(mǎn)足實(shí)時(shí)性要求。

　　5 結論

　　在以TMS320TMS320DM642為核心的實(shí)時(shí)圖像處理平臺上，通過(guò)對傳統的Hough變換檢測圓算法進(jìn)行改進(jìn)并運行驗證，證明了對于時(shí)間復雜度較大的圖像處理算法，在基于高端DSP的實(shí)時(shí)圖像處理系統上運行，圖像處理效果良好，能夠滿(mǎn)足實(shí)時(shí)性要求。