通信工程畢業(yè)設(shè)計(jì)（論文）- Hough 變換檢測圓

《通信工程畢業(yè)設(shè)計(jì)（論文）- Hough 變換檢測圓》由會員分享，可在線閱讀，更多相關(guān)《通信工程畢業(yè)設(shè)計(jì)（論文）- Hough 變換檢測圓（37頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、 北京科技大學(xué)遠(yuǎn)程與成人教育學(xué)院 畢業(yè)設(shè)計(jì)（論文） 題 目： Hough 變換檢測圓 學(xué)習(xí)中心： 遠(yuǎn)程與成人教育學(xué)院（TY） 專 業(yè)： 通信工程 年 級： 2007級 姓 名： 學(xué) 號： 指導(dǎo)教師：

2、 年 月 日 北京科技大學(xué)遠(yuǎn)程與成人教育學(xué)院 畢業(yè)設(shè)計(jì)（論文）任務(wù)書 遠(yuǎn)程與成人教育學(xué)院（TY）學(xué)習(xí)中心通信工程 專業(yè)2007年級 王 辰 同學(xué)（學(xué)號207998198 ）： 經(jīng)研究決定，你的畢業(yè)設(shè)計(jì)（論文）題目為： Hough 變換檢測圓 指導(dǎo)教師為： 胡師舜

3、 請你于 年 月 日-- 年 月 日期間完成。 指導(dǎo)教師：（簽字） 年 月 日 學(xué) 生：（簽字） 年 月 日 北京科技大學(xué)遠(yuǎn)程與成人教育學(xué)院 畢業(yè)設(shè)計(jì)（論文）指導(dǎo)教師評分 學(xué)習(xí)中心 遠(yuǎn)程與成人教育學(xué)院（TY）專業(yè)通信工程年級2007 學(xué)號207998198 學(xué)生 王 辰 ： 畢業(yè)設(shè)計(jì)(論文)題目 Hough 變換檢測圓 指導(dǎo)教師評分參考標(biāo)準(zhǔn) 序號 項(xiàng)

4、 目 滿分 1 文獻(xiàn)檢索、調(diào)研、開題報(bào)告 10 2 基本理論的掌握及外語、計(jì)算機(jī)應(yīng)用 15 3 數(shù)據(jù)（事實(shí)）真實(shí)可靠，綜合分析、解決問題能力 30 4 設(shè)計(jì)（論文）水平、創(chuàng)新意識 15 5 完成的工作量和工作態(tài)度 15 6 全文規(guī)范、圖紙、圖表、文字表達(dá)能力及書寫質(zhì)量 15 合 計(jì) 100 評分： 評語（特別點(diǎn)評或結(jié)論，同時(shí)請說明是否同意該學(xué)生參加答辯）： 指導(dǎo)教師（簽字）： 年 月 日 北京科技大學(xué)遠(yuǎn)

5、程與成人教育學(xué)院 畢業(yè)設(shè)計(jì)（論文）答辯評分和綜合成績 學(xué)習(xí)中心 遠(yuǎn)程與成人教育學(xué)院（TY）專業(yè) 通信工程年級2007 學(xué)號 207998198 學(xué)生 王 辰 ： 畢業(yè)設(shè)計(jì)(論文)題目 Hough 變換檢測圓 答辯評分參考標(biāo)準(zhǔn) 序號 項(xiàng) 目 滿分 1 論述的條理性、邏輯性 25 2 回答問題的正確性 30 3 設(shè)計(jì)（論文）內(nèi)容的正確性 20 4 設(shè)計(jì)（論文）水平及創(chuàng)新意識 25 　 合 計(jì) 100

6、 評分： 評語： 答辯小組組長（簽字）： 年 月 日 綜合成績 項(xiàng)目 評分 權(quán)重 加權(quán)分 指導(dǎo)教師評分 0.5 答辯評分 0.5 綜合成績 ------------ ----------- 指導(dǎo)教師（簽字）： 答辯委員會主任（簽字）： 摘 要 圖像是人類獲取和交換信息的主要來源。人類認(rèn)知圖像的構(gòu)成主要通過圖形的分類辨別，因此圖形檢測是人類視覺分類的一部分重要內(nèi)容，同時(shí)圖形檢測在

7、圖像配準(zhǔn)、機(jī)器人視覺、工業(yè)檢測中有著重要應(yīng)用。圓是構(gòu)成圖像的一個(gè)基本要素，因此，能夠快速、準(zhǔn)確地檢測基礎(chǔ)圖形-圓，在圖像處理中顯得尤為重要。所以本文針對圖形檢測中的一部分圓檢測進(jìn)行研究，學(xué)習(xí)并改進(jìn)傳統(tǒng)圓檢測算法。 現(xiàn)有最常用的圓檢測算法是Hough變換。該算法于1962年由Paul Hough提出，實(shí)現(xiàn)了一種從圖像空間到參數(shù)空間的映射關(guān)系。其基本思想是將圖像空間的一點(diǎn)變換到參考空間的一條曲線或一個(gè)曲面，而具有同一參量特征的點(diǎn)變換后在參兩空間中相交，通過判斷交點(diǎn)處的累積程度來完成特征曲線的檢測?，F(xiàn)有的利用Hough變換對圓進(jìn)行檢測的方法分為二類，第一類是已經(jīng)知道圓的半徑，另一類是半徑未知。

8、本課題研究的對象是第二類問題，在圖像中檢測出半徑未知的圓。實(shí)際應(yīng)用中，一幅圖像中可能有多個(gè)圓，并且其半徑處于不同的尺度范圍。而圓也可以根據(jù)這種不同的尺度范圍分為小、中、大等不同類型?，F(xiàn)有算法只能檢測到規(guī)定半徑長的圓，或者圖像中的所有圓。然后再根據(jù)半徑判斷圓的類型，即根據(jù)半徑范圍的不同劃分大、中、小等類別。介于Hough變換對于未知半徑的圓計(jì)算量大，所以這類方法的計(jì)算時(shí)間和效率較低。 本文針對上述問題進(jìn)行研究，學(xué)習(xí)已有Hough變換的知識，并研讀相關(guān)論文，實(shí)現(xiàn)了一種基于Hough變換的圓檢測的快速算法。該算法對預(yù)處理之后的邊緣圖像限定一個(gè)圓環(huán)半徑范圍，在Hough變換后，對移動后在圓環(huán)范圍

9、內(nèi)的點(diǎn)的個(gè)數(shù)進(jìn)行累加，累加得到的局部最大值提供了檢測出的圓心坐標(biāo)。這種方法實(shí)現(xiàn)了各類圓形、橢圓等非理想圖形的快速檢測，在一定程度上減少了Hough變換的時(shí)間。本文利用matlab語言編程實(shí)現(xiàn)了該算法。實(shí)驗(yàn)結(jié)果表明，該算法可以提取一定半徑范圍內(nèi)的圓形。關(guān)鍵詞：圖像處理，圓檢測，Hough變換 HOUGH Image is the main source that people gain and exchange information, the application domain of image processing must relate to human life and wor

10、k in all its aspects. The circle is a basic essential factor constituting the image. So it is important that detecting the circle quickly and accurately in image processing especial the industrial image processing. Hough transform is an effective way to detect line、circle、ellipse even any shape . F

11、or many years, researchers all devote to study the algorithm of Hough transform. Now Hough transform has been widely used in military and civil domain, such as image processing, signal detection, radar target track, passive track, track and so on. But most of the algorithms of Hough transform cost m

12、uch time and memory space. And they all suppose that the image can be well described by perfect models in computers. Otherwise, in our real life, real images are distorted because of the influence of noise, digital error and so on. Although the image input is complete, the image in computers is diff

13、icult to be well described by perfect models. Aimed at the problem of huge time consuming, this paper studied a fast algorithm for the detection of circles. The principle is that we first detect a cirque which has a definite inside and outside radius, then move this cirque in the image, add the nu

14、mber of point in the moved cirque. The some largest points are considered to be the detected circle. This way improved huge time consuming when using the traditional Hough transform. We realized the detection of circles of Hough transform through Matlab. The result shows that this way realized the d

15、etection of circles and ellipses and can resist the influence of noise. I was very pity that this algorithm did not solve the problem that Hough transform needs big storage space. This will be the direction of the future study. Key Words：image processing, detection of circle, HOUGH transformation,

16、 目　　錄 摘 要 1 目　　錄 1 引 言 1 1圖形檢測的意義和發(fā)展 2 課題背景 2 數(shù)字圖像處理概述 2 圖像檢測技術(shù)發(fā)展歷史及現(xiàn)狀 4 本章小結(jié) 6 2 Hough變化的原理和發(fā)展 7 2.1 Hough直線檢測原理 7 2.2 Hough變換的發(fā)展 9 2.3 Hough變換實(shí)現(xiàn)方法 10 2.4 Hough變換應(yīng)用領(lǐng)域 10 本章小結(jié) 11 3 Hough變換圓檢測 13 3.1 Hough變換圓檢測原理和性能分析 13 經(jīng)典Hough變換圓檢測算法 14 檢測一定半徑范圍內(nèi)的圓的Hough算法 16 本章小結(jié) 19

17、4總結(jié)與展望 20 結(jié)　　論 21 參 考 文 獻(xiàn) 22 附 錄A 23 附 錄B 23 附 錄C 26 致謝 30 引 言 圖像目標(biāo)檢測技術(shù)是人類認(rèn)知的延伸，是圖像分析技術(shù)的一個(gè)重要內(nèi)容，圖像檢測技術(shù)在自動目標(biāo)識別系統(tǒng)中也有很重要的地位。學(xué)術(shù)界和工業(yè)界常見的檢測目標(biāo)是直線、橢圓和圓。圓的檢測在圖像配準(zhǔn)、印章檢測、零件形狀、視頻監(jiān)控等方面有著重要的應(yīng)用。 Hough變換于1962年由Paul Hough提出，實(shí)現(xiàn)了一種從圖像空間到參數(shù)空間的映射關(guān)系。其基本思想是將圖像空間的一點(diǎn)變換到參考空間的一條曲線或一個(gè)曲面，而具有同一參量特征的點(diǎn)變換后在參兩

18、空間中相交，通過判斷交點(diǎn)處的累積程度來完成特征曲線的檢測。 目前圓的檢測主要為Hough變換，多數(shù)方法是采用分布的Hough變換，先找到圓心，然后再對半徑進(jìn)行投票。Duquenoy通過加快對圖像的分析速度和對圖像空間的降采樣來提高基于Hough變換的收斂速度。而Chiu通過提供一個(gè)新的投票方案，讓每一個(gè)像素對應(yīng)一個(gè)候選圓參數(shù)，改善了計(jì)算復(fù)雜度。黎則使用受限隨機(jī)Hough變換的方法，解決了隨機(jī)變換中的無效采樣的問題，提出了高效的多圓檢測算法。Ramirez等人使用遺傳算法來檢測圓，可以在圖形中檢測出殘缺的圓。 本文所實(shí)現(xiàn)的算法是Hough變換的定義算法，并可以調(diào)節(jié)參數(shù)來實(shí)現(xiàn)針對不同半徑的圓的

19、檢測，算法復(fù)雜度較低，易于實(shí)現(xiàn)。 1圖形檢測的意義和發(fā)展 課題背景 人工圖像和衛(wèi)星影像中，比如：光學(xué)干涉圖像和軍事駐地圖像，大多數(shù)物體都是由線或曲線組成的，所以，圖像處理中，對線或曲線的識別和定位就顯得十分重要。同時(shí)，工程上經(jīng)常要進(jìn)行曲線檢測或擬合，對圓形器件或圖標(biāo)進(jìn)行模式識別和定位是一個(gè)常見的問題。在計(jì)算數(shù)學(xué)中圓檢測有多種方法，常用的有:基于圓形邊緣積分特性的環(huán)路積分微分法、對邊界區(qū)域進(jìn)行分區(qū)迭代擬合的檢測算法、基于最小二乘原理進(jìn)行擬合的檢測算法、通過計(jì)算圓形目標(biāo)的灰度重心提取圓心坐標(biāo)的Wong-Trinder圓定位算子和模板匹配法、組合法、魯棒性估計(jì)法、形狀分析法等;此外還有一類通過

20、代價(jià)函數(shù)的全局優(yōu)化來提取幾何基元的方法，如:模擬退火算法、遺傳算法等。這些算法(或其組合)雖然在一些特定的場合已經(jīng)得到應(yīng)用，在定位精度和計(jì)算速度等方面也取得了令人滿意的結(jié)果，但是這些方法的使用范圍往往比較有限，如:需要事先知道較多的目標(biāo)圓的知識(大致的圓心位置和半徑范圍等)，且在標(biāo)準(zhǔn)的規(guī)則圖形和干擾噪聲少的場合才比較有效。 Hough變換是一種用來在邊緣增強(qiáng)處理后的圖像中，提取邊緣特征的簡便而有效的方法，它能夠提取直線、圓、橢圓、二次曲線甚至是任意形狀的邊緣。而且Hough變換在計(jì)算機(jī)視覺、軍事防御、辦公自動化等領(lǐng)域都得到了普遍的關(guān)注和廣泛的應(yīng)用。其基本思想是將原圖像變換到參數(shù)空間，用大多數(shù)

21、邊界點(diǎn)滿足的某種參數(shù)形式來描述圖像中的曲線，通過設(shè)置累加器進(jìn)行累積，求得峰值對應(yīng)的點(diǎn)就是所需要的信息。Hough變換以其對局部缺損的不敏感、對隨機(jī)噪聲的魯棒性以及適于并行處理等優(yōu)良特性,備受圖像處理、模式識別和計(jì)算機(jī)視覺領(lǐng)域?qū)W者的青睞。Hough變換的突出優(yōu)點(diǎn)就是可以將圖像中較為困難的全局檢測問題轉(zhuǎn)換為參數(shù)空間中相對容易解決的局部峰值檢測問題。隨著Hough變換在圓檢測上的應(yīng)用越來越廣泛，對基于Hough變換的圓檢測算法的進(jìn)一步研究具有較好的研究意義和實(shí)用價(jià)值。 數(shù)字圖像處理概述 圖像就是用各種觀測系統(tǒng)以不同形式和手段觀測客觀世界而獲得的，可以直接或間接作用于人眼而產(chǎn)生視知覺的實(shí)體?？茖W(xué)研

22、究和統(tǒng)計(jì)表明，人類從外界獲得的信息約有75%來自于視覺系統(tǒng)，也就是說，人類大部分信息都是從圖像中獲得的。 圖像處理是人類視覺延伸的重要手段，可以使人們看到任意波長上所測得的圖像。例如，借助伽馬相機(jī)、X光，人們可以看到紅外和超聲圖像；借助TC可以看到物體內(nèi)部斷層圖像；借助相應(yīng)工具可看到立體圖像和剖視圖像。1964年，美國在太空探索中拍回了大量月球照片，但是由于種種環(huán)境因素的影響，這些照片是非常不清晰的，為此，美國噴射推進(jìn)實(shí)驗(yàn)室(JPL)使用計(jì)算機(jī)對圖像進(jìn)行處理，使照片中的重要信息得以清晰再現(xiàn)。這是這門技術(shù)發(fā)展的重要里程碑。此后，圖像處理技術(shù)在空間研究方面得到廣泛應(yīng)用。 在研究圖像時(shí)，首先要對

23、獲得的圖像信息進(jìn)行預(yù)處理(前處理)以濾去干擾、噪聲，作幾何、彩色校正等。這樣可提高信噪比；有時(shí)由于信息微弱，無法辨識，還得進(jìn)行增強(qiáng)處理。增強(qiáng)的作用，在于提供一個(gè)滿足一定要求的圖像，或?qū)D像進(jìn)行分割，也就是進(jìn)行定位和分離，以分出不同的物體。為了給觀察者以清晰的圖像，還要對圖像進(jìn)行改善，即進(jìn)行復(fù)原處理，它是把己經(jīng)退化了的圖像加以重建或恢復(fù)的過程，以便改進(jìn)圖像的保真度。在實(shí)際處理中，由于圖像信息量非常大，在存儲及發(fā)送時(shí)，還要對圖像信息進(jìn)行壓縮。上述工作必須用計(jì)算機(jī)進(jìn)行，因而要進(jìn)行編碼等工作。 以上所述都屬圖像處理的范疇。對于一個(gè)圖像處理系統(tǒng)來說，可以將流程分成3個(gè)階段：首先是圖像處理階段，第二是圖

24、像分析階段，第三是圖像理解階段。圖像處理階段主要是在像素級上進(jìn)行處理，圖像的幾何校正，圖像的灰度處理，圖像噪聲濾除的平滑處理，目標(biāo)物體邊界的銳化處理等。圖像分析階段主要對圖像里感興趣的目標(biāo)進(jìn)行檢測、分割、特征提取和測量，分析的結(jié)果能為用戶提供描述圖像目標(biāo)特點(diǎn)和性質(zhì)的數(shù)據(jù)，把原來以像素描述的圖像轉(zhuǎn)變成比較簡潔的非圖像方式的描述。圖像理解階段主要通過對圖像里各目標(biāo)的性質(zhì)和它們之間相互關(guān)系的研究，對描述抽象出來角符號進(jìn)行運(yùn)算，了解把握圖像內(nèi)容并解釋原來的客觀場景，提供客觀世界的信息，指導(dǎo)和規(guī)劃行為。 圖像處理就是將圖像轉(zhuǎn)換成一個(gè)數(shù)字矩陣存放在計(jì)算機(jī)中，并采用一定的算法對其進(jìn)行處理。圖像處理的基礎(chǔ)是

25、數(shù)學(xué)，最主要的任務(wù)就是各種算法的設(shè)計(jì)和實(shí)現(xiàn)。目前的圖像處理技術(shù)已經(jīng)在許多不同的應(yīng)用領(lǐng)域中得到重視，并取得重要的分支，其中研究的內(nèi)容概括起來主要包括如下5個(gè)方面： 1)圖像數(shù)字化:通過采樣與量化過程將模擬圖像變換成便于計(jì)算機(jī)處理的數(shù)字形式。圖像在計(jì)算機(jī)內(nèi)通常用一個(gè)數(shù)字矩陣來表示，矩陣中的每一個(gè)元素稱為像素。圖像數(shù)字化的設(shè)備主要是各種掃描儀與數(shù)字化儀。 2)圖像增強(qiáng):主要目的是增強(qiáng)圖像中有用的信息，削弱干擾和噪聲，使圖像清晰或?qū)⑵滢D(zhuǎn)換為更適合人或計(jì)算機(jī)分析的形式。圖像增強(qiáng)并不要求真實(shí)的反映原始圖像。常用方法有直方圖增強(qiáng)和偽彩色增強(qiáng)等。 3)圖像重建(恢復(fù)):使退化了的圖像，去掉退化因素，以最

26、大的保真度，恢復(fù)成原來的圖像?；謴?fù)圖像的質(zhì)量，將不僅根據(jù)人的主觀感覺來判斷，而且也根據(jù)某種客觀的衡量標(biāo)準(zhǔn)。 4)圖像編碼:圖像編碼研究屬于信息論中信源編碼的范疇。它是在滿足一定的保真度要求下，簡化圖像的表小，從而大大壓縮表示圖像的數(shù)據(jù)，以便于存儲和傳輸。 5)圖像分析:對圖像中的不同對象進(jìn)行分割、分類、識別和描述、解釋。 目前數(shù)字圖像處理的應(yīng)用越來越廣泛，已經(jīng)滲透到工業(yè)、醫(yī)療保健、航空航天、軍事等各個(gè)領(lǐng)域，在國民經(jīng)濟(jì)中發(fā)揮越來越大的作用。 其中最典型的應(yīng)用有： (1)遙感技術(shù)中的應(yīng)用 遙感圖像處理的用處已經(jīng)越來越大，并且其效率和分辨率也越來越高。它被廣泛地應(yīng)用于土地測繪、資源調(diào)查、

27、氣象監(jiān)測、環(huán)境污染監(jiān)督、農(nóng)作物估產(chǎn)和軍事偵察等領(lǐng)域。目前遙感技術(shù)已經(jīng)比較成熟，但是還必須解決其數(shù)據(jù)量龐大、處理速度慢的特點(diǎn)。 (2)醫(yī)學(xué)應(yīng)用 圖像處理在醫(yī)學(xué)上有著廣泛的應(yīng)用。其中最突出的臨床應(yīng)用就是超聲、核磁共振、γ相機(jī)和CT等技術(shù)。在醫(yī)學(xué)領(lǐng)域利用圖像處理技術(shù)可以實(shí)現(xiàn)對疾病的直觀診斷和無痛、安全方便的診斷和治療，受到了廣大患者的歡迎。 (3)安全領(lǐng)域 利用圖像處理的模式識別等技術(shù)，可以利用在監(jiān)控、指紋檔案管理等安全領(lǐng)域中。目前有清華大學(xué)工程物理系開發(fā)研制的大型集裝箱檢測系統(tǒng)，就是利用圖像處理技術(shù)來實(shí)現(xiàn)全自動集裝箱檢測，從而加快了海關(guān)的工作效率，為打擊走私立下汗馬功勞。 (4)工業(yè)生產(chǎn)

28、 產(chǎn)品的無損檢測也是圖像處理技術(shù)的一項(xiàng)廣泛應(yīng)用。 總之，圖像處理技術(shù)的應(yīng)用是相當(dāng)廣泛的它在國家安全、經(jīng)濟(jì)發(fā)展、日常生活中充當(dāng)著越來越重要的角色，對國計(jì)民生有著不可忽略的作用[8]。 表1.1 圖像處理的應(yīng)用領(lǐng)域 學(xué)科 應(yīng)用 物理、化學(xué) 結(jié)晶分析、譜分析等 生物、醫(yī)學(xué) 細(xì)胞分析、染色體分類、X射線成像、CT等 環(huán)境保護(hù) 水質(zhì)及大氣污染調(diào)查等 地質(zhì) 資源勘測、地圖繪制、GIS等 農(nóng)業(yè)、林業(yè) 農(nóng)產(chǎn)物估產(chǎn)、植被分布調(diào)查等 漁業(yè) 魚群分布調(diào)查等 氣象 衛(wèi)星云圖分析等 通信 、電視、多媒體通信等 工業(yè) 工業(yè)探傷、機(jī)器人、產(chǎn)品質(zhì)量檢測等 軍事 導(dǎo)彈導(dǎo)航

29、、軍事偵查等 法律 指紋識別等 圖像檢測技術(shù)發(fā)展歷史及現(xiàn)狀 圖像檢測作為圖像分析技術(shù)的一個(gè)研究內(nèi)容，它也是伴隨著數(shù)字圖像處理的發(fā)展而發(fā)展的。數(shù)字圖像處理這門學(xué)科的形成也是和社會生產(chǎn)力發(fā)展的需要分不開的。早期的圖像處理是由于通訊方面的要求而發(fā)展起來的，這就是本世紀(jì)20年代 技術(shù)的發(fā)明和發(fā)展。其后，則是由于宇宙方面的要求，需要處理大量的宇宙探測器上拍攝下來的不清楚的其他天體(如月球、火星等)以及地球本身的照片。然而，圖像處理技術(shù)的發(fā)展，遠(yuǎn)遠(yuǎn)突破了這兩個(gè)領(lǐng)域，到今天，它已經(jīng)廣泛的應(yīng)用到科學(xué)研究、工農(nóng)業(yè)生產(chǎn)、軍事技術(shù)、政府部門、醫(yī)療衛(wèi)生等許多領(lǐng)域，進(jìn)一步推動著社會生產(chǎn)力的發(fā)展。 圖像檢測

30、是圖像分析研究內(nèi)容的一部分。目前，在圖像分析領(lǐng)域已經(jīng)有很大的發(fā)展。圖像分析是一種從一幅圖像中通過自動的或半自動的方法提取圖像尺寸、數(shù)據(jù)或信息的方法。圖像分析方法通常因圖像分析系統(tǒng)最后的輸出是數(shù)字而不是畫面，使它與其他類型的圖像處理方法，如編碼、恢復(fù)、放大等不同。圖像分析源于經(jīng)典的模式識別方法，根據(jù)定義，分析系統(tǒng)并不局限于對一個(gè)固定數(shù)量類別的場景區(qū)域的分類，而是更傾向于可設(shè)計(jì)成用于描繪復(fù)雜場景。根據(jù)事先預(yù)測，該場景的種類可能是非常多的和不確定的。目前，圖像分析領(lǐng)域主要包括形態(tài)學(xué)圖像處理、邊緣檢測、圖像特征提取、圖像分割、形狀分析、圖像檢測和配準(zhǔn)等幾個(gè)方面的內(nèi)容： (1)形態(tài)學(xué)圖像處理：它的基本

31、概念可以追朔到Mnikowski對空間集合代數(shù)的研究和Matheron對拓?fù)涞难芯?。形態(tài)學(xué)圖像處理是這樣的一種處理類型，它對圖像中的物體的空間形態(tài)或結(jié)構(gòu)進(jìn)行修改。膨脹、腐蝕和骨架化是三種基本的形態(tài)學(xué)計(jì)算。 (2)邊緣檢測：一幅圖像的振幅屬性(如亮度或三色值)的變化或突變是對圖像進(jìn)行描述的重要特性，因?yàn)樗鼈兂Ｖ甘緢D像中物體的物理特性。從一個(gè)層面到另一個(gè)層面的圖像亮度的局部突變叫亮度邊緣。對于亮度圖像中的邊緣檢測、直線檢測和點(diǎn)檢測有兩類近似方法：微分檢測和模型擬合。 (3)圖像特征提取：圖像的特征是指圖像顯著的基本特征或特性。一些圖像是其本質(zhì)的特性，在一定程度上這樣的特征可以從視覺上分辨出來，

32、另一些則是通過某些變換產(chǎn)生的人為特征。本質(zhì)特征包括像素區(qū)域和灰度紋理區(qū)域的亮度。 (4)圖像分割：圖像分割法使圖像被劃分成或分隔成具有相近特征的區(qū)域。對于圖像分割法，其最基本的特征是:單色照片圖像的亮度振幅和彩色圖像的彩色因素。圖像邊緣和紋理也是對分割法很有用的特征。 (5)形狀分析：目前已經(jīng)提出了幾種定性的和定量的方法來描述圖像中物體的形狀，這些方法對于在模式識別系統(tǒng)中對物體進(jìn)行分類和在圖像理解系統(tǒng)中象征性的描述物體是很有用的。在這些方法中，有一些只能應(yīng)用在二進(jìn)制圖像中，另外的一些則可以被擴(kuò)展到灰度圖像中。 (6)圖像檢測和配準(zhǔn)：圖像檢測主要是確定位于圖像內(nèi)被猜測的物體是存在還是不存在

33、的。而圖像配準(zhǔn)主要是涉及到一對圖像區(qū)域的空間配準(zhǔn)問題。在一個(gè)圖像區(qū)域中，物體檢測的一種最基本方法是通過模板匹配來進(jìn)行。在目前的實(shí)際應(yīng)用中，廣泛的利用Hough變換來進(jìn)行圓形或橢圓性的物體檢測。 本文主要是研究Hough變換在圓形物體檢測中的應(yīng)用。在實(shí)際的圖像檢測和配準(zhǔn)中，利用模板匹配是物體檢測的一種最基本的方法。在匹配過程中，把所關(guān)注的物體的拷貝和圖像區(qū)域中的所有的未知物體進(jìn)行比較，如果模板和未知物體是匹配的，并且模板是足夠精確的，則未知物體被標(biāo)識為模板物體。由于存在圖像噪聲、空間和振幅量化效應(yīng)以及對于要檢測的物體的精確形狀和結(jié)構(gòu)的預(yù)先不確定性，模板匹配很難保證精確性。 分析物體檢測的整個(gè)

34、過程，自然界中的一幅連續(xù)圖像對其數(shù)字化的描述，經(jīng)過圖像的增強(qiáng)、圖像的恢復(fù)后得到的數(shù)字圖像，要實(shí)現(xiàn)對其特定形狀圖形的檢測，還需要對二進(jìn)制的圖像進(jìn)行圖像分析，其中包括:形態(tài)學(xué)的處理，圖像分割、邊緣檢測、必要時(shí)還需要對其進(jìn)行圖像彩色特征提取。經(jīng)過這些處理后才可進(jìn)行圖像的檢測和配準(zhǔn)。而每個(gè)處理過程涉及的算法都有一定的使用范圍和局限性，如何利用和有效組合每個(gè)處理過程中現(xiàn)有的成熟技術(shù)，一直是圖像檢測中的難點(diǎn)。檢測識別問題上的一個(gè)難點(diǎn):假設(shè)現(xiàn)在有一個(gè)識別的問題，一幅圖像，其中包含了一些簡單的幾何形狀:矩形、圓等。任務(wù)就是編寫計(jì)算機(jī)程序，自動的識別這些形狀。還有一些影響識別的因素，是由圖像質(zhì)量以及多義性引起的

35、。比如噪音，在有意義的目標(biāo)附近存在大量的干擾信息，當(dāng)對圖像中的點(diǎn)進(jìn)行梯度運(yùn)算時(shí)，這些干擾信息會造成計(jì)算上的錯(cuò)誤，這些都給識別帶來了很大的困難，同時(shí)這也是多義性產(chǎn)生的原因。即使是人來識別也會遇到這個(gè)問題:重疊覆蓋。檢測圖像多個(gè)目標(biāo)的時(shí)候，一個(gè)目標(biāo)覆蓋了另一個(gè)，使得另一個(gè)目標(biāo)的信息不完整；交叉、目標(biāo)與目標(biāo)之間的交叉點(diǎn)是難于處理的。數(shù)字圖像處理過程中的經(jīng)典問題之一圓形檢測，有著廣泛的應(yīng)用背景，也面臨著上述同樣的問題。研究者們提出了多種圓形檢測的方法，其中非常重要的一種:基于Hough變換的累積方法。圓的Hough變換(CHT)是目前應(yīng)用最為廣泛的圓檢測方法，該方法的最大特點(diǎn)是可靠性高，在噪聲、變形大

36、部分區(qū)域不完整的狀態(tài)下依然能取得理想的結(jié)果，但該方法的缺點(diǎn)是計(jì)算量大，資源需求大。所以如何減少算法的計(jì)算量和存儲量在近年得到了廣泛的重視，已提出了不少改進(jìn)算法，如隨機(jī)Hough變換算法。但大多數(shù)的這些算法都是假設(shè)圖像在計(jì)算機(jī)中能用完美的模型來描繪原始圖像。然而，在現(xiàn)實(shí)生活中，由于噪音、數(shù)字化錯(cuò)誤和圖形變異等因素影響，真實(shí)的圖形經(jīng)常被曲解。盡管輸入圖像是完整的，但圖像在計(jì)算機(jī)中很難用完美的模型來描繪)本文將針對此類問題，利用現(xiàn)有的關(guān)于圓圖形檢測理論和技術(shù)，結(jié)合模糊數(shù)學(xué)中的相關(guān)理論進(jìn)行檢測。 本章首先大概介紹了本次論文的背景，接著著重講解了數(shù)字圖像處理，引入了圖像檢測技術(shù)的發(fā)展現(xiàn)狀，并指出了

37、圖像檢測技術(shù)。 本論文中主要工作如下： (1)通過圖像邊緣提取算子得到測試灰度圖像邊緣的二值圖像； (2)用matlab、c或OpenCV環(huán)境完成一個(gè)Hough變換檢測圓的函數(shù)程序； (3)對步驟(1)得到的二值圖像進(jìn)行Hough變換，將圖像空間變換到參數(shù)空間； (4)在參數(shù)空間搜索超過閾值的聚焦點(diǎn)，即同一圓上的點(diǎn)； (5)改變半徑范圍，檢測符合制定半徑的圓。 2 Hough變化的原理和發(fā)展 Hough變換是圖像處理中從圖像中識別幾何形狀的基本方法之一。Hough變換的基本原理在于利用點(diǎn)與線的對偶性，將原始圖像空間的給定的曲線通過曲線表達(dá)形式變?yōu)閰?shù)空間的一個(gè)點(diǎn)。這樣就把原始圖

38、像中給定曲線的檢測問題轉(zhuǎn)化為尋找參數(shù)空間中的峰值問題。也即把檢測整體特性轉(zhuǎn)化為檢測局部特性。比如直線、橢圓、圓、弧線等. 同時(shí)，將概率論、模糊集理論、分層迭代的思想和級聯(lián)的方法應(yīng)用于Hough變換的過程中，大大地提高了Hough變換的效率，改善了Hough變換的性能。 1962年，Paul Hough提出了Hough變換法，并申請了專利。該方法將圖像空間中的檢測問題轉(zhuǎn)換到參數(shù)空間，通過在參數(shù)空間里進(jìn)行簡單的累加統(tǒng)計(jì)完成檢測任務(wù)，用大多數(shù)邊界點(diǎn)滿足的某種參數(shù)形式來描述圖像的區(qū)域邊界曲線，因而對于被噪聲干擾或間斷區(qū)域邊界的圖像，Hough變換具有很好的容錯(cuò)性和魯棒性。Hough變換法最初主要用于

39、檢測圖像空間中的直線，最早的直線Hough變換是在兩個(gè)笛卡爾坐標(biāo)系之間進(jìn)行變換，這給檢測斜率為無窮大的直線帶來了困難。1972年，Duda將Hough變換法的變形形式進(jìn)行了改變，將數(shù)據(jù)空間中的點(diǎn)變換為ρ-θ參數(shù)空間的曲線，改善了其探測直線的性能。由于經(jīng)典的Hough變換法只能檢測圖像空間中的直線，為了能檢測到圖像空間中的曲線，在1978年Sklansky將Hough變換進(jìn)行推廣，提出了推廣Hough變換法來檢測圖像空間中的曲線。基于變換方程的不同，Hough變換法可以檢測出圖像空間中的圓、橢圓、拋物線、雙曲線等可以有解析式表達(dá)的曲線。但是經(jīng)典的Hough變換計(jì)算量比較大，在實(shí)際應(yīng)用中很難實(shí)現(xiàn)。

40、為了解決這個(gè)問題，40余年以來，許多學(xué)者致力于Hough變換算法的研究，將隨機(jī)過程、模糊理論等應(yīng)用于Hough變換，并將分層迭代、級聯(lián)的思想引入到Hough變換的過程中，大大提高了Hough變換的效率。 2.1 Hough直線檢測原理 1962年，Paul Hough根據(jù)數(shù)學(xué)對偶性原理提出了檢測圖像直線的方法，此后該方法被不斷地研究和發(fā)展，主要應(yīng)用于模式識別領(lǐng)域中對二值圖像進(jìn)行直線檢測。其原理如圖2.1所示，平面直角坐標(biāo)系中的直線L表達(dá)為: (2.1) 其中，a為斜率，c為截距。據(jù)式(2.1)，直線L上不同的點(diǎn)(x,

41、y)在參數(shù)空間中被變換為一族相交于P點(diǎn)的直線。顯然，若能確定參數(shù)空間中的P點(diǎn)（局部最大值），就實(shí)現(xiàn)了直線的檢測。 平面中任意一條直線也可以用極坐標(biāo)方程來表示，即可以用和兩個(gè)參數(shù)確定下來，對于圖像空間任意點(diǎn),其函數(shù)關(guān)系為： (2.2) 其中為原點(diǎn)到直線的距離（即原點(diǎn)到直線的垂直線的長度），確定了直線的方向（即原點(diǎn)到直線的垂直線與x軸方向的夾角）。如果對位于同一直線l上的n個(gè)點(diǎn)進(jìn)行上述變換，則原圖像空間n個(gè)點(diǎn)在參數(shù)空間中對應(yīng)地得到n條正弦曲線，并且這些曲線相交于同一點(diǎn)。 X坐標(biāo) Y坐標(biāo) Hough變換 截距 斜率 P 圖2.

42、1： 直線檢測中的Hough變換 由上述Hough變換原理可知，Hough變換具有如下性質(zhì)： (1)直角坐標(biāo)系中的一個(gè)點(diǎn)映射到參數(shù)空間中為一條線； (2)參數(shù)空間中的一個(gè)點(diǎn)對應(yīng)直角坐標(biāo)系中的一條線； (3)直角坐標(biāo)系中的共點(diǎn)線映射到參數(shù)空間中為一條線； (4)直角坐標(biāo)系中的共線點(diǎn)映射到參數(shù)空間中后為一個(gè)交于同一點(diǎn)的線簇。 圖2.2為matlab模擬結(jié)果，從圖中我們可知，經(jīng)過Hough變換后，在原空域中的一個(gè)點(diǎn)變成了一條曲線，曲線橫坐標(biāo)為，縱坐標(biāo)為。代表經(jīng)過原空間的以點(diǎn)為圓心、斜率在[-∞,+∞]之間的所有直線。 圖2.2 點(diǎn)的Hough變換matlab模擬 圖2.

43、3為直線的Hough變換，可以看到，原空間的一條直線變換到Hough空間就變成了很多條曲線的交疊，通過投票法我們可以的得到點(diǎn)最為集中位置的和，從而確定原始空間直線的信息。 圖2.3 直線的Hough變換 圖2.4和圖2.5分別是以直線為主要構(gòu)成元素的三角形和長方形的Hough變換，與Hough變換獲得直線信息相似，在三角形的Hough空間，我們獲得了三個(gè)局部極大值點(diǎn)，通過這三個(gè)點(diǎn)可以判斷原空間中三角形三條邊的信息，繼而確定了三個(gè)頂點(diǎn)的位置，連接三個(gè)頂點(diǎn)，獲得了三角形信息。長方形的檢測方法同上。因此，通過Hough變換檢測由直線構(gòu)成的圖形和圖像中的直線，采用的都是全局

44、極值投票判定。 圖2.4 三角形的Hough變換 圖2.5 長方形的Hough變換 2.2 Hough變換的發(fā)展 Hough變換最初只用于從圖像中識別圖形邊界，經(jīng)過幾十年的發(fā)展，Hough變換現(xiàn)在已經(jīng)用于各個(gè)方面的圖像處理，包括辦公文檔圖像處理、多普勒-時(shí)間圖像處理、航空圖像自動判斷等。隨著科學(xué)技術(shù)的發(fā)展，Hough變換在軍事和民用領(lǐng)域?qū)玫綇V泛的應(yīng)用。1994年，Carlson等人將Hough變換法應(yīng)用到搜索雷達(dá)中檢測直線運(yùn)動或近似直線運(yùn)動的低可觀測目標(biāo)。1996年，JiChen等人將Hough變換法應(yīng)用于航跡起始中。除此之外，在國防科技領(lǐng)域，Ho

45、ugh變換還廣泛用于低可觀測信號檢測、聲納信號處理、雷達(dá)目標(biāo)跟蹤、ESM目標(biāo)跟蹤、紅外目標(biāo)跟蹤、多傳感器多目標(biāo)跟蹤、多傳感器信息融合等方面。 圓形檢測是數(shù)字圖像處理過程中的經(jīng)典問題之一，有著廣泛的應(yīng)用背景，研究者們提出了多種圓形檢測的辦法，基于Hough變換的累積方法是其中非常重要的一種方法。圓的Hough變換（CHT）是目前應(yīng)用最為廣泛的圓檢測方法，該方法最大特點(diǎn)是可靠性高，目前已經(jīng)提出了多種基于Hough變換的圓的檢測算法，其中的一些算法在繼承Hough變換優(yōu)勢的同時(shí)，也對Hough變換過程中存在的計(jì)算量大、資源需求大等缺點(diǎn)進(jìn)行了很好的改進(jìn)，如隨機(jī)Hough變換算法。同時(shí)，Hough變換

46、的測量數(shù)據(jù)的預(yù)處理、參數(shù)空間的離散化、門限的選擇、平均虛警概率的問題都得到了解決，如集束算法、基于邏輯的檢測方法、數(shù)據(jù)的融合等方法。 2.3 Hough變換實(shí)現(xiàn)方法 工程中的實(shí)驗(yàn)數(shù)據(jù)和圖像處理中的二值邊緣圖，通常都是離散數(shù)據(jù)，因此，根據(jù)Hough變換性質(zhì)，可按下列步驟實(shí)現(xiàn)Hough變換[17-18]： (1)將參數(shù)空間量化成(為的等份數(shù)，為的等份數(shù))個(gè)單元，并設(shè)置累加器矩陣； (2)給參數(shù)空間中的每個(gè)單元分配一個(gè)累加器,并把累加器的初始值置為零； (3)取出直角坐標(biāo)系中的點(diǎn)代入式(2-2)，并以量化的值計(jì)算出； (4)在參數(shù)空間中，找到和所對應(yīng)得單元，并將該單元的累加器加1，即；

47、 (5)當(dāng)直角坐標(biāo)系中的點(diǎn)都經(jīng)過(3)(4)兩步遍歷后，檢驗(yàn)參數(shù)空間中每個(gè)累加器的值，累加器最大的單元所對應(yīng)的和即為直角坐標(biāo)系中的直線方程式(2-1)的參數(shù)。 當(dāng)直角坐標(biāo)系中的點(diǎn)分布在R條直線附近時(shí)，可在第5步檢測累加器時(shí)，取出累加器中前R個(gè)值最大的單元所對應(yīng)的和，以和為直角坐標(biāo)系中直線方程式(2-2)的參數(shù)，即可同時(shí)實(shí)現(xiàn)多條直線的檢測。 2.4 Hough變換應(yīng)用領(lǐng)域 經(jīng)典Hough變換的計(jì)算量大，在實(shí)際應(yīng)用中很難實(shí)現(xiàn)。40年來，許多學(xué)者將隨機(jī)過程、模糊集理論、分層迭代的思想和級聯(lián)的方法應(yīng)用于Hough變換中，就形成了隨機(jī)Hough變換、模糊Hough變換、分層迭代Hough變換、級聯(lián)

48、Hough變換和三維Hough變換，這使的Hough變換的應(yīng)用越來越廣泛，例如將Hough變換應(yīng)用在圖像處理，信號檢測等方面。 (1)Hough變換最初是作為圖像處理的方法提出來的。Hough變換的一個(gè)突出的有點(diǎn)是抗干擾能力強(qiáng)。如果待檢測的曲線上有小的擾動或斷裂，或者存在背景噪聲，算法都能準(zhǔn)確的檢測出曲線。甚至對于直線，經(jīng)Hough變換后，在變換空間中仍然能夠得到明顯的峰值點(diǎn)。所以，Hough變換在圖像處理中應(yīng)用的非常廣泛。 Hough變換在圖像處理中的應(yīng)用主要是對圖像中特定形狀的識別和檢測。它具體可以用來對圖形進(jìn)行識別，提取圖像拐點(diǎn)，SAR圖像處理，傾斜文本圖像校正和檢測，多普勒-時(shí)間圖

49、像處理以及航空圖像自動判讀等等。 采用Hough變換進(jìn)行形狀特征提取，可對形狀進(jìn)行有效的識別，可并行實(shí)現(xiàn)，而且對噪聲不敏感，所提取的特征不受待識別形狀大小及所在圖像中的位置的影響。但由于Hough變換必須逐點(diǎn)處理圖像平面上的每一點(diǎn)，計(jì)算量大，內(nèi)存開銷較大，特別是對于圖像幅面大，前景復(fù)雜的圖形時(shí)尤其明顯。對圖像進(jìn)行濾波和邊緣檢測雖然能夠加快處理速度，但識別精度會受到不同成都的影響。 (2)基于Hough變換的信號檢測方法既可以用于低可觀測信號的檢測，也能用于強(qiáng)雜波環(huán)境下的多目標(biāo)跟蹤。通過Hough變換，可以把可能是同一個(gè)航跡的回?fù)苣芰窟M(jìn)行非相干積累。由于非相參積累的作用，低可觀測目標(biāo)的能量得

50、以積累，增強(qiáng)了低可觀測目標(biāo)的信噪比，從而可以對低可觀測目標(biāo)進(jìn)行檢測。利用Hough變換對信號進(jìn)行檢測主要有兩種方法：一是基于Hough變換的非相干積累法，二是基于Hough變換的二值積累法。其中，Hough變換的非相參積累方式對低可探測目標(biāo)的檢測性能有一定的改善，由于它不需要對目標(biāo)進(jìn)行回掃即可進(jìn)行檢測前跟蹤，因此在強(qiáng)雜波環(huán)境下基于Hough變換的檢測是常規(guī)檢測手段的一種有益的補(bǔ)充。 (3)航跡起始是航跡處理中的首要問題，但同航跡處理中的跟蹤維持的研究相比，航跡處理中的航跡起始算法比航跡處理中的航跡維持算法更為復(fù)雜?，F(xiàn)有的航跡起始算法可分為順序處理技術(shù)和批數(shù)據(jù)處理技術(shù)兩大類。通常，順序數(shù)據(jù)處理

51、技術(shù)適用于相對無雜波環(huán)境中的航跡起始，主要包括啟發(fā)式規(guī)則方法和基于邏輯的方法。批數(shù)據(jù)處理技術(shù)適用于雜波環(huán)境，主要包括Hough變換法和修正的Hough變換法等。 Hough變換還可以應(yīng)用到三維空間中的航跡起始。由于Hough變換只適用于起始二維平面中的目標(biāo)航跡，因此在實(shí)際工程中，可以根據(jù)實(shí)際的需要選擇投影面，然后在利用基于Hough變換和邏輯的起始算法，并將各個(gè)平面起始的航跡進(jìn)行比較和關(guān)聯(lián)起始三維空間中的航跡。而且通過在密集雜波環(huán)境下的航跡起始仿真驗(yàn)證了該方法特別適用于在密集雜波環(huán)境中快速起始三維空間中的軌跡。 (4)Hough變換在多傳感器多目標(biāo)跟蹤中的應(yīng)用 利用多傳感器獲取數(shù)據(jù)來進(jìn)行

52、多目標(biāo)跟蹤的技術(shù)在許多軍事和民用領(lǐng)域得到了廣泛的應(yīng)用。從本質(zhì)上講，多傳感器多目標(biāo)跟蹤系統(tǒng)成功的關(guān)鍵都在于數(shù)據(jù)關(guān)聯(lián)算法的有效性。在一般情況下，數(shù)據(jù)關(guān)聯(lián)問題可以分解為兩項(xiàng)單獨(dú)的任務(wù)：用于航跡其實(shí)起始的測量-測量關(guān)聯(lián)和用于航跡維持的測量-測量關(guān)聯(lián)。而Hough變換特征檢測方法是可以用作實(shí)現(xiàn)目標(biāo)航跡起始的一種有效方法，通過將前幾次搜索掃描所感知的數(shù)據(jù)組合成多維數(shù)據(jù)矢量，可以用Hough變換從復(fù)合數(shù)據(jù)中檢測出軌跡。文獻(xiàn)[19-20]對Carlson等人的工作進(jìn)行了拓展，并提出了可用于在雜波環(huán)境中緝拿測兵起始多目標(biāo)航跡的基于Hough變換的多傳感器數(shù)據(jù)關(guān)聯(lián)方法。 基于Hough變換的多傳感器，多目標(biāo)航跡

53、起始方法的最大優(yōu)勢在于其對多傳感器結(jié)構(gòu)的適應(yīng)能力，因?yàn)樵谒蟹抡嬷?，多傳感器結(jié)構(gòu)的性能總是優(yōu)于單傳感器結(jié)構(gòu)的性能。而且雜波不會顯著影響航跡起始性能，但可以看到雜波密度的增加會引起虛假航跡起始率的上升。 本章小結(jié) 本章首先講述了Hough變換的原理和實(shí)現(xiàn)方法，并簡單介紹了其研究現(xiàn)狀和存在的問題，接著介紹了Hough變換的應(yīng)用領(lǐng)域。 Hough變換是一種用來在邊緣增強(qiáng)處理后的圖像中，提取邊緣特征的簡便而有效的方法，它能夠提取直線、圓、橢圓、二次曲線甚至是任意形狀的邊緣。Hough變換在計(jì)算機(jī)視覺、軍事防御、辦公自動化等領(lǐng)域都得到了普遍的關(guān)注和廣泛的應(yīng)用。Hough變換1962年由Paul H

54、ough提出，并在美國作為專利。它所實(shí)現(xiàn)的是一種從圖像空間到參數(shù)空間的映射關(guān)系。Hough變換的實(shí)質(zhì)是將圖像空間內(nèi)具有一定關(guān)系的象元進(jìn)行聚類，尋找能把這些象元用某一解析形式聯(lián)系起來的參數(shù)空間累積對應(yīng)點(diǎn)。 經(jīng)過幾十年的發(fā)展，Hough變換現(xiàn)在已經(jīng)用于各個(gè)方面的圖像處理，包括SAR/ISAR圖像處理、辦公文檔圖像處理、多普勒-時(shí)間圖像處理、航空圖像自動判讀等。隨著科學(xué)技術(shù)的發(fā)展，Hough變換在軍事和民用領(lǐng)域得到了廣泛的應(yīng)用。比如在國防科技領(lǐng)域，Hough變換被用于低可觀測信號檢測、聲納信號處理、雷達(dá)目標(biāo)跟蹤、ESM目標(biāo)跟蹤、紅外目標(biāo)跟蹤、多傳感器多目標(biāo)跟蹤、多傳感器信息融合等方面。在民用領(lǐng)域，

55、Hough變換在水聲目標(biāo)形狀分析、人臉圖像識別、地下目標(biāo)檢測、車輛識別、目標(biāo)平移和旋轉(zhuǎn)運(yùn)動分析等方面發(fā)揮著巨大的作用?？傊琀ough變換的作用已被世界各國所認(rèn)識，顯示出了巨大的應(yīng)用價(jià)值和重要的應(yīng)用前景。 3 Hough變換圓檢測 Hough變換圓檢測原理和性能分析 (1) Hough變換圓檢測原理 Hough變換常常被用于直線段、圓和橢圓的檢測。其基本思想是將圖像的空間域變換到參數(shù)空間，用大多數(shù)邊界點(diǎn)滿足的某種參數(shù)形式來描述圖像中的曲線(區(qū)域邊界)。通過設(shè)置累加器進(jìn)行累加，求得峰值對應(yīng)的點(diǎn)就是所需要的信息。 經(jīng)典的Hough圓檢測假設(shè)希望在圖像平面(X-Y平面)考察并確定

56、一個(gè)圓周。令為圖像中欲確定圓周上的點(diǎn)的集合，而為集合中的一點(diǎn)，它在參數(shù)坐標(biāo)系中方程為: （3.1） 顯然對于來說，圓上的一點(diǎn)其橫坐標(biāo)x=a+rcos()，縱坐標(biāo)y=b+rsin()。若已經(jīng)知道待檢測圓的半徑，那么檢測工作就相對容易一些，如圖3.1所示，由于圓點(diǎn)到圓上的點(diǎn)的距離相同，所以以圓上的點(diǎn)為圓心，相同的半徑r畫圓，最后就可以通過投票法得到圓心位置，最后在原坐標(biāo)中確定圓。 圖3.1 已知半徑圓的檢測 若圓的半徑未知，即r是一個(gè)變量，那么方程3-1為三維錐面，對于圖像中任意確定的一點(diǎn)均有參數(shù)空間的一個(gè)三維的錐面與之對應(yīng)。對于圓周上的任

57、何點(diǎn)集合，這些三維錐面構(gòu)成圓錐面簇。 圖3.2 未知半徑的圓檢測的Hough變換原理 若集合中的點(diǎn)在同一個(gè)圓周上，則這些圓錐簇相交于參數(shù)空間上某一點(diǎn)，這點(diǎn)恰好對應(yīng)于圖像平面的圓心坐標(biāo)及圓的半徑。對于離散圖像，式(3-1)可寫為: (3.2) 其中ξ是考慮到對圖像進(jìn)行數(shù)字化和量化的補(bǔ)償。Hough變換的基本思想在于證據(jù)積累，一般情況下圓變換的參數(shù)空間為三維的，在三維積累空間上進(jìn)行證據(jù)累加的時(shí)間空間消耗是非常大的，在具體應(yīng)用中幾乎是不可能的，不現(xiàn)實(shí)的。 (2) Hough變換圓檢測性能分析 由以上分析可以看出，影響常規(guī)Hough變換

58、運(yùn)算速度的主要因素有:邊緣點(diǎn)的數(shù)量，參數(shù)空間維數(shù)，參數(shù)空間的離散化程度，運(yùn)算的復(fù)雜性，以及最后的峰值檢測。 對于半徑為，圓心坐標(biāo)為的圓在參數(shù)空間的表示為: (3.3) 顯然，上式表示的是一個(gè)三維錐面，它的物理意義是，圖像空間中的圓對應(yīng)著參數(shù)空間的一個(gè)點(diǎn)，而圖像空間中的一個(gè)點(diǎn)對應(yīng)著參數(shù)空間中的一個(gè)三維圓錐。對于圖像空間中的一個(gè)圓其半徑是固定不變的，圓周上的各個(gè)點(diǎn)組成的集合在參數(shù)空間就表現(xiàn)為相等而、不等的各個(gè)圓錐的集合。圖像空間中圓上的點(diǎn)映射到參數(shù)空間的一簇圓錐的交點(diǎn)正好對應(yīng)于圓心坐標(biāo)和半徑。對于參數(shù)空間適當(dāng)量化，得到一個(gè)三維的累加列陣，用來

59、記錄，當(dāng)檢測圖像空間中的圓時(shí)，計(jì)算與邊緣上的每一個(gè)像素距離r的所有，同時(shí)在對應(yīng)的列陣中累加，當(dāng)對全部邊緣點(diǎn)變換完成后，對三維列陣中的所有累加值進(jìn)行檢驗(yàn)，其中的峰值就對應(yīng)圖像空間中的圓心。 由于圖像是離散的，對(3-3)式的判別可改寫為: (3.4) 對于邊緣上的每一點(diǎn)，給定半徑，那么對、的變化各需要計(jì)算次上式，同時(shí)排除已經(jīng)計(jì)算過的重復(fù)點(diǎn)，因而總共需要計(jì)算次左右。假設(shè)每次耗時(shí)，那么對于一個(gè)邊緣點(diǎn)需耗時(shí)，再假設(shè)半徑的變化范圍為，則每個(gè)邊緣點(diǎn)耗時(shí)為: (3.5) 假設(shè)有N個(gè)邊緣點(diǎn)，則總耗時(shí)即為，本系統(tǒng)所

60、涉及到的圖像，N通常在2000以上，那么總耗時(shí)中t的系數(shù)就是10的6次方以上，這個(gè)計(jì)算量是相當(dāng)大的。顯然，單就這一環(huán)節(jié)，就需要耗費(fèi)大量的運(yùn)行時(shí)間和存儲空間，因而，對于常規(guī)Hough變換的改進(jìn)要求是非常之迫切的。雖然常規(guī)Hough變換有明顯的缺憾，但是由于它完全按照Hough變換的定義進(jìn)行，所以通常用來作為改進(jìn)算法的參照對象。 Hough變換的基本思想在于證據(jù)積累，一般情況下圓變換的參數(shù)空間為三維的，需要在參數(shù)空間建立一個(gè)三維的累加數(shù)組,根據(jù)具體的圖像數(shù)據(jù)點(diǎn)計(jì)算出的每一個(gè)三元組，對累加，其具體變換過程如下： (1)在、、合適的最大值和最小值之間建立一個(gè)零散的參數(shù)空間； (2)建立一個(gè)累

61、加器,并置每一個(gè)元素為0； (3)對圖像空間中超過門限值的每一點(diǎn)作Hough變換，即算出該點(diǎn)在三維網(wǎng)格上的對應(yīng)曲線，并在相應(yīng)的累加器加1： (3.6) (4)找出對應(yīng)圖像平面共圓周點(diǎn)累加器上的局部最大值，這個(gè)值就提供了圖像平面上共圓周點(diǎn)的圓心以及半徑參數(shù)。 由于Hough變換的實(shí)質(zhì)是將圖像空間的具有一定關(guān)系的像元進(jìn)行聚類，尋找能把這些像元用某一解析形式聯(lián)系起來的參數(shù)空間累積對應(yīng)點(diǎn)。在參數(shù)空間不超過二維的情況下，這種變換有著很理想的效果。然而，當(dāng)參數(shù)空間超過二維時(shí)，這種變換的時(shí)間消耗和所需存儲空間的急劇增大使得這種變換僅僅在理論分析上可行，而在

62、實(shí)際應(yīng)用中幾乎是不可能實(shí)現(xiàn)的。這時(shí)往往需要從具體的應(yīng)用情況中尋找特點(diǎn)，如利用被處理圖像像元的灰度的變化值確定灰度的變化方向來降低參數(shù)空間維數(shù)，或利用一些對于被檢測圖像的先驗(yàn)知識來設(shè)法降低變換過程的時(shí)間和空間的開銷。 在參數(shù)空間中，將設(shè)為遞增變量，每一步迭代都先固定，在垂直于的平面上求對應(yīng)于圓心為的圓周各點(diǎn)，并將軌跡上的點(diǎn)在與此平面映像的一個(gè)三維累加數(shù)組上的相應(yīng)點(diǎn)上累加。從0開始遞增直到圖像平面所能容納的上限（一般可根據(jù)先驗(yàn)知識來確定r的可能變換范圍來減少計(jì)算量），每次遞增均有一平面映像與之對應(yīng)。因此，對于圖像上每一確定點(diǎn),和的變化范圍均為。求出在此范圍內(nèi)對應(yīng)的每一和的坐標(biāo)，即要計(jì)算式（3.2

63、）次。設(shè)每次這種計(jì)算耗時(shí)為，則對應(yīng)的每一步進(jìn)的得計(jì)算耗時(shí)為。若設(shè)的步進(jìn)范圍為，則對應(yīng)于每個(gè)像元的計(jì)算量為： 若對圖像平面上的若干個(gè)點(diǎn)進(jìn)行Hough變換，則總耗時(shí)將為 。而用于累加陣列的存儲空間約為字節(jié)（設(shè),分別為圖像的高度和寬度，累積單元采用單字節(jié)）?？梢?，以上運(yùn)算的時(shí)空開銷是很大的。 當(dāng)全部點(diǎn)轉(zhuǎn)換完成后，對累加數(shù)組每個(gè)元素的值進(jìn)行比較，有較大值得數(shù)組元素對應(yīng)于圓或圓弧，其參數(shù)可作為圓的擬合參數(shù)，而具有較小值得元素則舍棄。 如圖3-3所示,從圖像空間中取八個(gè)圓的邊緣像素點(diǎn)A、B、C、D、E、F、G、H,以R為半徑將這八個(gè)點(diǎn)映射到參數(shù)空間?？梢钥吹?這八個(gè)點(diǎn)在參數(shù)空間中的投影均在O點(diǎn)相交,

64、也即O點(diǎn)的累加值在參數(shù)空間中是最大的。同時(shí), O點(diǎn)也是圖像空間中圓的圓心。此時(shí), 圖像空間中每一邊緣點(diǎn)映射到參數(shù)空間得到的投影為一個(gè)圓。 圖3.3 圖像空間及邊緣點(diǎn)在參數(shù)空間的投影 檢測一定半徑范圍內(nèi)的圓的Hough算法 通過上述描述我們可以知道，Hough變換檢測圓最常見的問題分為已知半徑和完全未知半徑圓的檢測。第一類問題比較容易實(shí)現(xiàn)，因?yàn)閷ふ覛W氏距離相同的點(diǎn)不困難。而第二類問題由于半徑未知，并且每個(gè)點(diǎn)得到的范圍是個(gè)圓錐，所以計(jì)算量較大。而能夠?qū)崿F(xiàn)實(shí)時(shí)檢測，對于其應(yīng)用的推廣是極為重要的。在實(shí)際應(yīng)用中，能夠檢測到一定半徑范圍內(nèi)的圓是重要的應(yīng)用，因?yàn)榧词故菣z測規(guī)定半徑的圓，其實(shí)際檢

65、測中也會存在一定的像素偏差，所以應(yīng)用中的檢測范圍是一個(gè)半徑圓環(huán)。本節(jié)針對的問題是，如何利用Hough變換檢測到一定半徑范圍內(nèi)的圓，并且效率要盡量高。 (1) 經(jīng)典基于Hough變換的圓檢測算法 經(jīng)典的Hough變換在圖像中尋找半徑已知的圓的圓心時(shí),對整個(gè)圖像進(jìn)行遍歷,尋找邊緣點(diǎn)需要兩重循環(huán)。遍歷到每個(gè)邊緣點(diǎn)時(shí),求其在參數(shù)空間中的投影集合需要兩重循環(huán)。所以經(jīng)典的Hough變換在檢測半徑已知圓時(shí)需要四重循環(huán),這在實(shí)際計(jì)算中是極其耗時(shí)的。 當(dāng)遍歷到圖像中的邊緣點(diǎn)時(shí),先求出邊緣點(diǎn)映射到參數(shù)空間得到的坐標(biāo)點(diǎn)集合,然后對集合中每個(gè)坐標(biāo)點(diǎn)元素對應(yīng)的累加值進(jìn)行一次累加,此點(diǎn)在參數(shù)空間中的投影為坐標(biāo)點(diǎn)集合

66、(設(shè)圖像中邊緣點(diǎn)的數(shù)目為N 個(gè),則n的取值范圍為[ 1, N ] ) 。將圖像放到坐標(biāo)系中考慮時(shí),由坐標(biāo)平移的知識可以知道,當(dāng)一個(gè)圓的圓心由點(diǎn)平移到點(diǎn)時(shí),圓上任意一點(diǎn)的坐標(biāo)就由變?yōu)椤＿@樣,圖像中每個(gè)邊緣點(diǎn)在參數(shù)空間中投影得到的坐標(biāo)點(diǎn)集合就不需要通過計(jì)算得出,只需先求出一個(gè)基準(zhǔn)點(diǎn)在參數(shù)空間中的投影,投影得到的坐標(biāo)點(diǎn)集合為,其余的邊緣點(diǎn)在參數(shù)空間中的投影就可以通過將基準(zhǔn)點(diǎn)在參數(shù)空間的投影即坐標(biāo)點(diǎn)集合平移得到。這樣處理有如下優(yōu)點(diǎn):在參數(shù)空間中減少參與運(yùn)算的點(diǎn),并且通過平移在參數(shù)空間得到的坐標(biāo)點(diǎn)集合與通過計(jì)算在參數(shù)空間得到的坐標(biāo)點(diǎn)集合基本相等。對任意一邊緣點(diǎn),經(jīng)典Hough變換需要在參數(shù)空間中對以邊緣點(diǎn)為中心, 2R 為邊長的正方形內(nèi)所有像素點(diǎn)進(jìn)行計(jì)算,判斷是否是邊緣點(diǎn)映射到參數(shù)空間得到的坐標(biāo)點(diǎn)集合中的元素, 一共需要計(jì)算個(gè)像素點(diǎn)。改進(jìn)的算法只需在參數(shù)空間中移動N 個(gè)點(diǎn)(N 為正方形內(nèi)滿足圓的方程的像素點(diǎn)個(gè)數(shù)) 。由于正方形內(nèi)的像素點(diǎn)不可能全部是邊緣點(diǎn)映射到參數(shù)空間得到的坐標(biāo)點(diǎn)集合中的元素,必有。 (2)基于Hough變換的規(guī)定半徑范圍的圓檢測算法 由于算法效率主要取決于邊界點(diǎn)的個(gè)數(shù)，以及