數(shù)字圖像中的Hough變換應用--直線檢測

1、沈陽理工大學數(shù)字圖像處理課程設計摘 要為能夠有效解決實時直線圖形提取問題，提出了一種基于Hough變換(HT)的直線提取算法。它所實現(xiàn)的是一種從圖像空間到參數(shù)空間的映射關系。由于具有一些明顯優(yōu)點和可貴性質(zhì)，它引起了許多國內(nèi)外學者和工程技術人員的普遍關注。由于其根據(jù)局部度量來計算全面描述參數(shù)，因而對于區(qū)域邊界被噪聲干擾或被其他目標遮蓋而引起邊界發(fā)生某些間斷的情況，具有很好的容錯性和魯棒性。多年來，專家們對Hough變換的理論性質(zhì)和應用方法進行了深入而廣泛的研究，目前應用于生物醫(yī)學、自動化和機器人視覺、空間技術和軍事防御、辦公自動化等各個方面。本次課稱設計首先分析了數(shù)字圖像中直線邊緣的三種結構特征

2、，提出采用基元結構表示目標邊緣點，并在約束條件下計算基元結構的基元傾角。在此基礎上，結合傳統(tǒng)的HT的思想對基元結構進行極角約束HT，以獲得最終的直線參數(shù)。最后，再用MATLAB軟件對該算法進行編程仿真。實驗結果表明，對合成圖像和自然圖像，該算法能夠有效的識別圖像中的直線段。關鍵詞：直線提??；Hough變換；MATLAB 2目 錄1. 課程設計的目的12. MATLAB簡介及應用12.1 MATLAB簡介12.2 MATLAB應用12.3 MATLAB特點23. Hough變換原理23.1 Hough變換的基本原理23.2 Hough變換的不足之處43.3 Hough變換的應用44. Hough

3、變換檢測直線設計54.1 Hough變換檢測直線基本原理54.2 Hough變換的幾種基本算法64.3 Hough變換算法的比較與選擇74.4 Hough變換檢測直線的算法流程圖94.5 Hough變換檢測直線算法的實現(xiàn)95. 仿真結果及分析115.1 仿真結果115.2 結果分析14結論15參考文獻162數(shù)字圖像中的Hough變換應用直線的檢測1. 課程設計的目的本次課程設計的目的在于提高發(fā)現(xiàn)問題、分析問題、解決問題的能力，進一步鞏固數(shù)字圖像處理系統(tǒng)中的基本原理與方法。熟悉掌握一門計算機語言，可以進行數(shù)字圖像的應用處理的開發(fā)設計。綜合運用MATLAB軟件實現(xiàn)圖像高通濾波程序設計最終達到以下目

4、的：1) 通過課程設計把自己在大學中所學的知識應用到實踐當中。2) 深入了解利用Matlab設計FIR數(shù)字濾波器的基本方法。3) 在課程設計的過程中掌握程序編譯及軟件設計的基本方法。4) 提高自己對于新知識的學習能力及進行實際操作的能力。鍛煉自己通過網(wǎng)絡及各種資料解決實際問題的能力。2. MATLAB簡介及應用2.1 MATLAB簡介MATLAB 是美國MathWorks公司出品的商業(yè)數(shù)學軟件，用于算法開發(fā)、數(shù)據(jù)可視化、數(shù)據(jù)分析以及數(shù)值計算的高級技術計算語言和交互式環(huán)境，主要包括MATLAB和Simulink兩大部分。MATLAB是矩陣實驗室（Matrix Laboratory）的簡稱，和Ma

5、thematica、Maple并稱為三大數(shù)學軟件。它在數(shù)學類科技應用軟件中在數(shù)值計算方面首屈一指。MATLAB可以進行矩陣運算、繪制函數(shù)和數(shù)據(jù)、實現(xiàn)算法、創(chuàng)建用戶界面、連接其他編程語言的程序等，主要應用于工程計算、控制設計、信號處理與通訊、圖像處理、信號檢測、金融建模設計與分析等領域。2.2 MATLAB應用MATLAB 產(chǎn)品族可以用來進行以下各種工作：1) 數(shù)值分析2) 數(shù)值和符號計算3) 工程與科學繪圖4) 控制系統(tǒng)的設計與仿真5) 數(shù)字圖像處理 技術6) 數(shù)字信號處理 技術7) 通訊系統(tǒng)設計與仿真8) 財務與金融工程MATLAB 的應用范圍非常廣，包括信號和圖像處理、通訊、控制系統(tǒng)設計、

6、測試和測量、財務建模和分析以及計算生物學等眾多應用領域。附加的工具箱（單獨提供的專用 MATLAB 函數(shù)集）擴展了 MATLAB 環(huán)境，以解決這些應用領域內(nèi)特定類型的問題。2.3 MATLAB特點此高級語言可用于技術計算1) 此開發(fā)環(huán)境可對代碼、文件和數(shù)據(jù)進行管理2) 交互式工具可以按迭代的方式探查、設計及求解問題3) 數(shù)學函數(shù)可用于線性代數(shù)、統(tǒng)計、傅立葉分析、篩選、優(yōu)化以及數(shù)值積分等4) 二維和三維圖形函數(shù)可用于可視化數(shù)據(jù)5) 各種工具可用于構建自定義的圖形用戶界面6) 各種函數(shù)可將基于MATLAB的算法與外部應用程序和語言（如 C、C+、Fortran、Java、COM 以及 Micros

7、oft Excel）集成7) 不支持大寫輸入，內(nèi)核僅僅支持小寫。3. Hough變換原理3.1 Hough變換的基本原理Hough變換是一種使用表決原理的參數(shù)估計技術。其原理是利用圖像空間和Hough參數(shù)空間的點線對偶性，把圖像空間中的檢測問題轉(zhuǎn)換到參數(shù)空間。通過在參數(shù)空間里進行簡單的累加統(tǒng)計，然后在Hough參數(shù)空間尋找累加器峰值的方法檢測直線。Hough變換的實質(zhì)是將圖像空間內(nèi)具有一定關系的像元進行聚類，尋找能把這些像元用某一解析形式聯(lián)系起來的參數(shù)空間累積對應點。在參數(shù)空間不超過二維的情況下，這種變換有著理想的效果。Hough變換的實質(zhì)是將圖像空間內(nèi)具有一定關系的像元進行聚類，尋找能把這些

8、像元用某一解析形式聯(lián)系起來的參數(shù)空間累積對應點。在參數(shù)空間不超過二維的情況下， 這種變換有著理想的效果。但是，一旦參數(shù)空間增大，計算量便會急劇上升，同時耗費巨大的存儲空間，耗時也隨之猛增。就此，多年來國內(nèi)外眾多學者針對具體情況對常規(guī)Hough變換進行了多方面的探索，并提出了許多有價值的改進方法：1） 擴展應用范圍，提出多種參數(shù)化的方法在早期的研究中，Hough變換由只檢測圖像中的直線擴展到檢測圓弧、二次曲線和任意曲線構成的形狀；線條的參數(shù)化方法也由最初的截距型參數(shù)發(fā)展到斜率傾角和截距型參數(shù)、雙Hough空間型參數(shù)、以及檢測圓的圓心坐標、半徑型參數(shù)和檢測物體復雜形狀的基于模板的多維關鍵點參數(shù)等。

9、2） 提高實用性，提出多種減少計算量的算法針對Hough變換計算量大的不足，相繼提出了四分樹結構的Hough變換、以梯度信息為引導的Hough變換、分層Hough變換、自適應Hough變換、快速自適應Hough變換、隨機Hough變換（RHT）等；對于高維Hough變換采用降維處理，數(shù)據(jù)結構多采用動態(tài)量化空間等。3） 增強抗干擾能力，提高檢測精度Hough變換提取精度問題始終受到普遍關注，例如Hough變換的離散化誤差、混疊干擾、抗噪聲干擾性能等。就此類問題的研究例如，Kiryati、Buckstein提出采用最佳Kaider窗函數(shù)對參數(shù)域進行平滑濾波以減少混疊誤差；Hunt、Nolte等人應

10、用信號檢測理論對Hough變換的抗干擾性能和基于最大后驗概率的最佳算法進行了抗干擾性能比較，并指出了影響Hough變換抗干擾性能的原因。4） 多種峰值檢測方法Hough變換中參數(shù)空間的峰值檢測是一個聚類檢測問題，閾值的選取是成功與否的關鍵所在。其中，一種方法是對圖像空間進行加權，以改變參數(shù)空間的峰值分布；一種方法是直接對參數(shù)空間進行極大值的搜索。3.2 Hough變換的不足之處本課題的研究內(nèi)容，如上所述，常規(guī)Hough變換雖然具有顯著的優(yōu)勢，但其不足也不容忽視，如不加改進，有時將會令人無所適從，例如檢測速度太慢，無法做到實時控制；精度不夠高，期望的信息檢測不到反而做出錯誤判斷，進而產(chǎn)生大量的冗

11、余數(shù)據(jù)。就圓檢測而言，常規(guī)Hough變換的不足主要有以下幾點：（1）參數(shù)由直線的兩個參數(shù)，即截距和斜率，上升到三個，即圓心坐標和半徑，每個點映射成參數(shù)空間的一個曲面，是一到多映射，因而計算量急劇增大；（2）需要占用大量內(nèi)存空間，耗時久、實時性差；（3）現(xiàn)實中的圖像一般都受到外界噪聲的干擾，信噪比較低，此時常規(guī)Hough變換的性能將急劇下降，進行參數(shù)空間極大值的搜索時由于合適的閾值難以確定，往往出現(xiàn)“虛峰”和“漏檢”的問題。3.3 Hough變換的應用理論與實踐向來是形影不離，相輔相成，Hough變換之所以有如此長足的發(fā)展，主要原因還是在于實踐應用上的廣泛需求；而在實踐中所暴露出的不足又進而促進

12、了它的發(fā)展，循環(huán)往復，就如同生命的演化?，F(xiàn)枚舉其主要應用領域如下：1） 生物醫(yī)學： Hough變換已被成功應用于基于人工智能的專家診斷系統(tǒng)；X射線人體照片和CT圖像的處理和判讀；光學顯微鏡和電子顯微鏡中的細胞核自動分析系統(tǒng)；從超聲波診斷中提取三維動脈特征，等等。2） 自動化和機器人視覺: Hough變換已被用于產(chǎn)品部件的自動監(jiān)視、缺陷診斷、生產(chǎn)過程的自動監(jiān)控、計算機輔助制造（CAM）等。例如基于Hough變換的機械零件檢測和定位系統(tǒng)；基于Hough變換采用直線、圓弧等作為基本特征的工業(yè)產(chǎn)品檢查系統(tǒng);3） 空間技術和軍事防御: Hough變換已被用于運動目標軌跡的檢測與識別，高空偵察機、間諜衛(wèi)星

13、和軍事雷達等目標自動識別系統(tǒng)的特征提取。例如應用Hough變換對戰(zhàn)斗機的外形特征進行提取和自動識別；應用Hough變換輔以信號檢測理論解決并行多運動目標的跟蹤問題。4） 辦公自動化: Hough變換在許多應用系統(tǒng)中得到了很好的應用。例如采用Hough變換進行英文字符特征提取并自動識別，其對印刷體字符識別率為99.6%，對手寫體字符的平均識別率也達到了86.9%，并已成功應用于郵政信件的自動分揀、文件處理等。由以上分析可見，Hough變換有著廣泛的關注程度以及良好的應用前景。在計算機視覺和自動目標識別系統(tǒng)中，Hough變換是一個用于邊緣線條特征提取的強有力工具。4. Hough變換檢測直線設計4

14、.1 Hough變換檢測直線基本原理Hough變換檢測直線就是選取圖像空間中一條直線L的某些特征，作為參數(shù)空間的一個點M，并且該直線L上所有點，通過某種算法，都能夠?qū)@些特征 ，從而在圖像空間和參數(shù)空間之間建立起“線點”的對偶性。Hough變換就是根據(jù)這種對偶性，將圖像空間中直線的檢測問題，轉(zhuǎn)化為參數(shù)空間中點的檢 測問題,而后者的處理比前者要簡單得多，進行累加統(tǒng)計即可。下圖4.1給出了數(shù)字圖像中三類直線的結構分布情況，圖中一個小方格代表一個像素，黑方格代表邊緣像素點，白方格代表背景像素點?？梢钥闯?，近水平直線段由相距很近的行基元集合組成；近垂直直線段由相距很近的列基元集合組成；近45

15、76;直線依據(jù)其斜率分別由45°或135°掃描線上的斜基元集合組成。綜上可知，任何直線段都可以表示為總體走向趨勢基本一致且縫隙很小、相距很近的相應基元的集合。以此結構特點為基礎建立本文的直線提取方法。圖4.1數(shù)字圖像中直線的分布4.2 Hough變換的幾種基本算法常用的Hough變換檢測直線的方法，是運用下式在圖像空間和參數(shù)空間之間，建立對偶變換。 = x cos + y sin （4.1） （a）直角坐標系 （b）參數(shù)空間圖4.2 Hough變換示意圖在式（4.1）中，為極徑；為極角，取 0 180 °；x為像素點相對圖像原點的行坐標；y 為像素點相對圖像原點的

16、列坐標。對偶變換示意圖如圖4.2所示。為了檢測出直角坐標系中，由非零點所構成的直線，需要根據(jù)檢測分辨率的要求，將離散化為N個參數(shù)區(qū)間，將離散化為N個參數(shù)區(qū)間，也就是說將極坐標系量化成許多小格，建立參數(shù)空間。這種方法被稱為標準 Hough變換方法 ( standard hough transform，SHT)。 其優(yōu)點是：無論直線怎樣變化,參數(shù)空間中和的取值范圍是有限的。所以，目前的直線檢測大多數(shù)都是基于這種方法。 但是，這種方法在N值較大的情況下，存在以下兩個缺陷：( 1 ) 計算量大 N越大，的步長越小，計算量就越大。在要求檢測精度很高的場合，N的值往往非常大，這樣會使計算量大增。 ( 2

17、) 需要大的存儲空間 如果和都占 4 個字節(jié)，參數(shù)空間所需要的存儲空間的字節(jié)數(shù)S 可由下式求出 : S = 4 NN （4.2）圖4.3 Hough變換從圖像空間到參數(shù)空間的轉(zhuǎn)換在式（4.2）中，N為在 0，) 間取的離散值的個數(shù)；N為的采樣個數(shù)。對較大的圖像，S將大于數(shù)兆字節(jié) ( G B )，單靠物理內(nèi)存，難以滿足這樣的要求。為了減少這種 Hough 變換的計算量，減小所需要的存儲空間，在此基礎上出現(xiàn)了很多改進的Hough 變換算法，例如分塊檢測法、兩次檢測法、全整數(shù) Hough變換等，為討論方便，將其統(tǒng)稱為正弦 Hough 變換方法。但這些方法由于受的步長限制，有時候檢測結果不盡人意，難以

18、實現(xiàn)對任意斜率直線 的快速、精確檢測，尤其是對超大型圖像（例如像素在2048×2048 以上）。如果能夠建立一個不受步長限制的參數(shù)空間，就有可能實現(xiàn)對任意斜率直線的快速、精 確檢測。其中，Hough變換從圖像空間到參數(shù)空間的轉(zhuǎn)換如圖4.3所示。4.3 Hough變換算法的比較與選擇圖像空間中，直線 L0 : y=k0x+b0 上每一個點，在參數(shù)空間中都代表一條直線，這些直線都相當于一點 M ( k0，b0)。與用極坐標建立參數(shù)空間的方法相比，這種方法不受的步長限制，檢測了所有的可能出現(xiàn)的直線，不會有任何遺漏，在像素允許的情況下，能精確地檢測出圖像中的任意直線。這種 優(yōu)點決定了它非常適

19、合用來對直線進行精確檢測。為便于討論，將其稱為kb Hough變換方法。雖然這種方法在原理上非常明確，但在具體實現(xiàn)過程中，如 果簡單地用浮點數(shù)進行斜率和截距的計算，還有以下 3個問題需要解決：( 1 ) 如果同時計算斜率和截距，參數(shù)空間結構數(shù)組可能異常龐大，而且計算量非常大。一幅像素為m×n的圖像，假設圖像中可能出現(xiàn)的不重復的斜率有 u種( u大于圖像的像素總數(shù) )。若這些數(shù)據(jù)都占4個字節(jié)，那么要求的計算機內(nèi)存為： W=8umn （4.3）對較大的圖像，要求的計算機內(nèi)存超過上千兆字節(jié)(GB)，這顯然是不現(xiàn)實的。如何解決這個問題？很多時候，如果將一個2維問題分解為兩個1維問題來解決，往

20、往非常方便。參數(shù)空間數(shù)組之所以異常龐大，是因為同時包含了待測的斜率和截距，而斜率和截距的組合，決定了其數(shù)組的元素個數(shù)必然非常多。如果將斜率 k和截距b分步進行檢測，先檢測斜率，找出出現(xiàn)次數(shù)最多的斜率 k0，然后再檢測截距，找出斜率為k0的，出現(xiàn)次數(shù)最多的直線的截b0，也就是說，將一個2維問題分解為兩個1維問題。 由于斜率為k0的二點對的數(shù)量往往非常有限，這樣就能有效地減小參數(shù)空間。但是，即使將斜率k和截距b分步進行檢測，如果用浮點數(shù)進行計算斜率，并采用普通的Hough變換的投票方式，即先計算完由非零點組成的所有的二點對的斜率，再對斜率進行統(tǒng)計，也可能需要很大的參數(shù)空間。1幅800×6

21、00的圖像，如果非零點非常多，需要的參數(shù)空間仍然可能超過數(shù)千兆字節(jié)( GB )。所以，用浮點數(shù)計算斜率，要減小參數(shù)空間，只能一邊計算斜率，一邊統(tǒng)計斜率相同的情況( 與前面的斜率進行比較 )。 即邊投票，邊計票。但是，這樣計算量非常大。( 2 ) 程序的復雜程度高 根據(jù)定量度量程序的復雜程度的McCabe方法，流圖 (也稱為程序圖) 的環(huán)形復雜度可由下式求出 : V(G) = R + 1 （4.4）在式（4.4）中，V ( G)為環(huán)形復雜度；R為流圖中的判定節(jié)點數(shù)目。通常V ( G)10 為宜。根據(jù)McCabe方法求出該方法的流圖的判定節(jié)點數(shù)R為10， 由式( 3 )可知，其環(huán)形復雜度為11，顯

22、然復雜程度太高。 ( 3 ) 如果直接采用浮點數(shù)計算斜率，無法處理斜率為無窮大的垂直直線斜率為無窮大，給計算帶來不便，這正是極少有人采用這種方法的原因。 綜上所述，除了需要分步檢測斜率和截距外，還不能簡單地采用浮點數(shù)計算斜率。 因此采用了斜率分式查表方法來解決這些問題。4.4 Hough變換檢測直線的算法流程圖原始輸入的彩色圖像 變換得到灰度圖像提取灰度圖像邊緣Hough變換得到變換矩陣圖像計算檢測圖像中的直線計算標注出最長直線圖4.4算法流程圖4.5 Hough變換檢測直線算法的實現(xiàn)clearI = imread('abc.jpg');%輸入原圖像I = rgb2gray(I

23、);%將輸入的彩色圖像轉(zhuǎn)換成灰度圖像輸出%I = imrotate(I,33,'crop');% figure% imshow(rotI);figureimshow(I);BW = edge(I,'canny');%提取圖像邊緣figureimshow(BW);H,T,R = hough(BW);% 計算二值圖像的標準霍夫變換，H為霍夫變換矩陣，theta,rho為計算霍夫變換的角度和半徑值 figureimshow(H,'XData',T,'YData',R, 'InitialMagnification',

24、9;fit');xlabel('theta'), ylabel('rho');axis onaxis normalhold onP = houghpeaks(H,5,'threshold',ceil(0.3*max(H(:);%在Hough矩陣圖像中尋找前5個大于最大值0.3倍的峰值x = T(P(:,2); y = R(P(:,1);plot(x,y,'s','color','white');% Find lines and plot themlines = houghlines(BW,T

25、,R,P,'FillGap',5,'MinLength',7); %找出圖中的直線figure,imshow(rotI),hold on  figure, imshow(I),hold onmax_len = 0;for k = 1:length(lines) xy = lines(k).point1; lines(k).point2; plot(xy(:,1),xy(:,2),'LineWidth',2,'Color','green'); % % 繪制線的起點（黃色）、終點（紅色） plot(

26、xy(1,1),xy(1,2),'x','LineWidth',2,'Color','yellow'); plot(xy(2,1),xy(2,2),'x','LineWidth',2,'Color','red'); % 計算線的長度，找最長線段 len = norm(lines(k).point1 - lines(k).point2); if ( len > max_len) max_len = len; xy_long = xy; endendplot(xy_

27、long(:,1),xy_long(:,2),'LineWidth',2,'Color','blue'); 5. 仿真結果及分析在MATLAB7.1環(huán)境運行程序源代碼，對輸入彩色圖像通過變換得到灰度圖像，并進行邊界提取、Hough變換和直線檢測，得到如下結果。5.1 仿真結果如圖5.1，輸入圖像為一幅后綴為jpg格式的彩色圖像，在matlab程序代碼中首先使用imread（）函數(shù)將圖像讀入，以便于后續(xù)的處理和操作。 圖5.1原圖像由圖5.2可知，輸入圖像為一幅彩色圖像時，可以使用rgb2gray（）函數(shù)，先將彩色圖像轉(zhuǎn)換為灰度圖像（RGB不發(fā)生變

28、化），使圖像適合于邊界提取，為下一步做準備。 圖5.2灰度圖像由圖5.3可知，采用edge（）函數(shù)，對灰度圖像進一步進行處理，將圖像的邊緣地方的像素值設為1，其余地方的像素設為0，可以得到圖像的邊界，且提取出的圖像邊界清晰完整。 圖5.3邊界圖像由圖5.4可知，可以采用hough（）函數(shù)對邊界圖像進行Hough變換，并繪制出Hough變換得到的變換矩陣坐標圖，其中在峰值為520時，標注出的5個點為前5個大于最大值0.3倍峰值的點。 圖5.4 Hough變換圖像由圖5.5可知，在Hough變換后的矩陣中選出前5個大于最大值0.3倍峰值的點，并將這些點用“x”標出后，便可簡單地繪制線的起點（用黃色

29、表示）、終點（用紅色表示）并檢測出直線；最后通過計算，使用藍色線段標注出最長的線. 圖5.5直線檢測圖像5.2 結果分析本次課程設計原始的輸入圖像為一幅彩色圖像，并采用了如下算法：首先，在matlab代碼中可用imread（）函數(shù)將其讀入；然后，為了便于處理，需要采用rgb2gray（）函數(shù)，將其從彩色圖像變換為灰度圖像，使其適合于邊界的提取；得到灰度圖像后，采用Canny邊緣檢測算子進行邊界提取，在代碼中輸入BW = edge(I,'canny')；即可實現(xiàn)，其中I為變換得到的灰度圖像；對于提取邊緣后的圖像，應對其進行Hough變換，得到Hough變換矩陣，直接采用hough（）函數(shù)即可實現(xiàn)；最后，計算檢測圖像中的直線，將圖像中的直線以及直線的起始點一一標出，對于最長的直線可用不同于其他顏色的直線標出，這里普通直線采用綠色直線標注，最長的直線采用藍色直線標注。通過對圖