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

北京科技大學(xué)遠程與成人教育學(xué)院畢業(yè)設(shè)計（論文）題 目： Hough 變換檢測圓 學(xué)習(xí)中心： 遠程與成人教育學(xué)院（TY） 專 業(yè)： 通信工程 年 級： 2007級 姓 名： 學(xué) 號： 指導(dǎo)教師： 年 月 日 北京科技大學(xué)遠程與成人教育學(xué)院畢業(yè)設(shè)計（論文）任務(wù)書遠程與成人教育學(xué)院（TY）學(xué)習(xí)中心通信工程 專業(yè)2007年級 王 辰 同學(xué)（學(xué)號207998198 ）： 經(jīng)研究決定，你的畢業(yè)設(shè)計（論文）題目為： Hough 變換檢測圓 指導(dǎo)教師為： 胡師舜 請你于 年 月 日- 年 月 日期間完成。指導(dǎo)教師：（簽字） 年 月 日學(xué) 生：（簽字） 年 月 日北京科技大學(xué)遠程與成人教育學(xué)院畢業(yè)設(shè)計（論文）指導(dǎo)教師評分學(xué)習(xí)中心 遠程與成人教育學(xué)院（TY）專業(yè)通信工程年級2007 學(xué)號207998198 學(xué)生 王 辰 ：畢業(yè)設(shè)計(論文)題目 Hough 變換檢測圓 指導(dǎo)教師評分參考標準序號項 目滿分1文獻檢索、調(diào)研、開題報告102基本理論的掌握及外語、計算機應(yīng)用153數(shù)據(jù)（事實）真實可靠，綜合分析、解決問題能力304設(shè)計（論文）水平、創(chuàng)新意識155完成的工作量和工作態(tài)度156全文規(guī)范、圖紙、圖表、文字表達能力及書寫質(zhì)量15合 計100評分：評語（特別點評或結(jié)論，同時請說明是否同意該學(xué)生參加答辯）： 指導(dǎo)教師（簽字）： 年 月 日北京科技大學(xué)遠程與成人教育學(xué)院畢業(yè)設(shè)計（論文）答辯評分和綜合成績學(xué)習(xí)中心 遠程與成人教育學(xué)院（TY）專業(yè) 通信工程年級2007 學(xué)號 207998198 學(xué)生 王 辰 ：畢業(yè)設(shè)計(論文)題目 Hough 變換檢測圓 答辯評分參考標準序號項 目滿分1論述的條理性、邏輯性252回答問題的正確性303設(shè)計（論文）內(nèi)容的正確性204設(shè)計（論文）水平及創(chuàng)新意識25合 計100評分： 評語： 答辯小組組長（簽字）： 年 月 日綜合成績項目評分權(quán)重加權(quán)分指導(dǎo)教師評分0.5答辯評分0.5綜合成績-指導(dǎo)教師（簽字）： 答辯委員會主任（簽字）： 摘 要 圖像是人類獲取和交換信息的主要來源。人類認知圖像的構(gòu)成主要通過圖形的分類辨別，因此圖形檢測是人類視覺分類的一部分重要內(nèi)容，同時圖形檢測在圖像配準、機器人視覺、工業(yè)檢測中有著重要應(yīng)用。圓是構(gòu)成圖像的一個基本要素，因此，能夠快速、準確地檢測基礎(chǔ)圖形-圓，在圖像處理中顯得尤為重要。所以本文針對圖形檢測中的一部分圓檢測進行研究，學(xué)習(xí)并改進傳統(tǒng)圓檢測算法。 現(xiàn)有最常用的圓檢測算法是Hough變換。該算法于1962年由Paul Hough提出，實現(xiàn)了一種從圖像空間到參數(shù)空間的映射關(guān)系。其基本思想是將圖像空間的一點變換到參考空間的一條曲線或一個曲面，而具有同一參量特征的點變換后在參兩空間中相交，通過判斷交點處的累積程度來完成特征曲線的檢測?，F(xiàn)有的利用Hough變換對圓進行檢測的方法分為二類，第一類是已經(jīng)知道圓的半徑，另一類是半徑未知。本課題研究的對象是第二類問題，在圖像中檢測出半徑未知的圓。實際應(yīng)用中，一幅圖像中可能有多個圓，并且其半徑處于不同的尺度范圍。而圓也可以根據(jù)這種不同的尺度范圍分為小、中、大等不同類型。現(xiàn)有算法只能檢測到規(guī)定半徑長的圓，或者圖像中的所有圓。然后再根據(jù)半徑判斷圓的類型，即根據(jù)半徑范圍的不同劃分大、中、小等類別。介于Hough變換對于未知半徑的圓計算量大，所以這類方法的計算時間和效率較低。 本文針對上述問題進行研究，學(xué)習(xí)已有Hough變換的知識，并研讀相關(guān)論文，實現(xiàn)了一種基于Hough變換的圓檢測的快速算法。該算法對預(yù)處理之后的邊緣圖像限定一個圓環(huán)半徑范圍，在Hough變換后，對移動后在圓環(huán)范圍內(nèi)的點的個數(shù)進行累加，累加得到的局部最大值提供了檢測出的圓心坐標。這種方法實現(xiàn)了各類圓形、橢圓等非理想圖形的快速檢測，在一定程度上減少了Hough變換的時間。本文利用matlab語言編程實現(xiàn)了該算法。實驗結(jié)果表明，該算法可以提取一定半徑范圍內(nèi)的圓形。關(guān)鍵詞：圖像處理，圓檢測，Hough變換HOUGHImage is the main source that people gain and exchange information, the application domain of image processing must relate to human life and work 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 . For 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 much 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 difficult 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 number 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 detection 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, 目錄摘 要1目錄1引 言11圖形檢測的意義和發(fā)展2課題背景2數(shù)字圖像處理概述2圖像檢測技術(shù)發(fā)展歷史及現(xiàn)狀4本章小結(jié)62 Hough變化的原理和發(fā)展72.1 Hough直線檢測原理72.2 Hough變換的發(fā)展92.3 Hough變換實現(xiàn)方法102.4 Hough變換應(yīng)用領(lǐng)域10本章小結(jié)113 Hough變換圓檢測133.1 Hough變換圓檢測原理和性能分析13經(jīng)典Hough變換圓檢測算法14檢測一定半徑范圍內(nèi)的圓的Hough算法16本章小結(jié)194總結(jié)與展望20結(jié)論21參 考 文 獻22附 錄A23附 錄B23附 錄C26致謝30引 言 圖像目標檢測技術(shù)是人類認知的延伸，是圖像分析技術(shù)的一個重要內(nèi)容，圖像檢測技術(shù)在自動目標識別系統(tǒng)中也有很重要的地位。學(xué)術(shù)界和工業(yè)界常見的檢測目標是直線、橢圓和圓。圓的檢測在圖像配準、印章檢測、零件形狀、視頻監(jiān)控等方面有著重要的應(yīng)用。Hough變換于1962年由Paul Hough提出，實現(xiàn)了一種從圖像空間到參數(shù)空間的映射關(guān)系。其基本思想是將圖像空間的一點變換到參考空間的一條曲線或一個曲面，而具有同一參量特征的點變換后在參兩空間中相交，通過判斷交點處的累積程度來完成特征曲線的檢測。目前圓的檢測主要為Hough變換，多數(shù)方法是采用分布的Hough變換，先找到圓心，然后再對半徑進行投票。Duquenoy通過加快對圖像的分析速度和對圖像空間的降采樣來提高基于Hough變換的收斂速度。而Chiu通過提供一個新的投票方案，讓每一個像素對應(yīng)一個候選圓參數(shù)，改善了計算復(fù)雜度。黎則使用受限隨機Hough變換的方法，解決了隨機變換中的無效采樣的問題，提出了高效的多圓檢測算法。Ramirez等人使用遺傳算法來檢測圓，可以在圖形中檢測出殘缺的圓。本文所實現(xiàn)的算法是Hough變換的定義算法，并可以調(diào)節(jié)參數(shù)來實現(xiàn)針對不同半徑的圓的檢測，算法復(fù)雜度較低，易于實現(xiàn)。1圖形檢測的意義和發(fā)展課題背景人工圖像和衛(wèi)星影像中，比如：光學(xué)干涉圖像和軍事駐地圖像，大多數(shù)物體都是由線或曲線組成的，所以，圖像處理中，對線或曲線的識別和定位就顯得十分重要。同時，工程上經(jīng)常要進行曲線檢測或擬合，對圓形器件或圖標進行模式識別和定位是一個常見的問題。在計算數(shù)學(xué)中圓檢測有多種方法，常用的有:基于圓形邊緣積分特性的環(huán)路積分微分法、對邊界區(qū)域進行分區(qū)迭代擬合的檢測算法、基于最小二乘原理進行擬合的檢測算法、通過計算圓形目標的灰度重心提取圓心坐標的Wong-Trinder圓定位算子和模板匹配法、組合法、魯棒性估計法、形狀分析法等;此外還有一類通過代價函數(shù)的全局優(yōu)化來提取幾何基元的方法，如:模擬退火算法、遺傳算法等。這些算法(或其組合)雖然在一些特定的場合已經(jīng)得到應(yīng)用，在定位精度和計算速度等方面也取得了令人滿意的結(jié)果，但是這些方法的使用范圍往往比較有限，如:需要事先知道較多的目標圓的知識(大致的圓心位置和半徑范圍等)，且在標準的規(guī)則圖形和干擾噪聲少的場合才比較有效。Hough變換是一種用來在邊緣增強處理后的圖像中，提取邊緣特征的簡便而有效的方法，它能夠提取直線、圓、橢圓、二次曲線甚至是任意形狀的邊緣。而且Hough變換在計算機視覺、軍事防御、辦公自動化等領(lǐng)域都得到了普遍的關(guān)注和廣泛的應(yīng)用。其基本思想是將原圖像變換到參數(shù)空間，用大多數(shù)邊界點滿足的某種參數(shù)形式來描述圖像中的曲線，通過設(shè)置累加器進行累積，求得峰值對應(yīng)的點就是所需要的信息。Hough變換以其對局部缺損的不敏感、對隨機噪聲的魯棒性以及適于并行處理等優(yōu)良特性,備受圖像處理、模式識別和計算機視覺領(lǐng)域?qū)W者的青睞。Hough變換的突出優(yōu)點就是可以將圖像中較為困難的全局檢測問題轉(zhuǎn)換為參數(shù)空間中相對容易解決的局部峰值檢測問題。隨著Hough變換在圓檢測上的應(yīng)用越來越廣泛，對基于Hough變換的圓檢測算法的進一步研究具有較好的研究意義和實用價值。數(shù)字圖像處理概述圖像就是用各種觀測系統(tǒng)以不同形式和手段觀測客觀世界而獲得的，可以直接或間接作用于人眼而產(chǎn)生視知覺的實體。科學(xué)研究和統(tǒng)計表明，人類從外界獲得的信息約有75%來自于視覺系統(tǒng)，也就是說，人類大部分信息都是從圖像中獲得的。圖像處理是人類視覺延伸的重要手段，可以使人們看到任意波長上所測得的圖像。例如，借助伽馬相機、X光，人們可以看到紅外和超聲圖像；借助TC可以看到物體內(nèi)部斷層圖像；借助相應(yīng)工具可看到立體圖像和剖視圖像。1964年，美國在太空探索中拍回了大量月球照片，但是由于種種環(huán)境因素的影響，這些照片是非常不清晰的，為此，美國噴射推進實驗室(JPL)使用計算機對圖像進行處理，使照片中的重要信息得以清晰再現(xiàn)。這是這門技術(shù)發(fā)展的重要里程碑。此后，圖像處理技術(shù)在空間研究方面得到廣泛應(yīng)用。在研究圖像時，首先要對獲得的圖像信息進行預(yù)處理(前處理)以濾去干擾、噪聲，作幾何、彩色校正等。這樣可提高信噪比；有時由于信息微弱，無法辨識，還得進行增強處理。增強的作用，在于提供一個滿足一定要求的圖像，或?qū)D像進行分割，也就是進行定位和分離，以分出不同的物體。為了給觀察者以清晰的圖像，還要對圖像進行改善，即進行復(fù)原處理，它是把己經(jīng)退化了的圖像加以重建或恢復(fù)的過程，以便改進圖像的保真度。在實際處理中，由于圖像信息量非常大，在存儲及發(fā)送時，還要對圖像信息進行壓縮。上述工作必須用計算機進行，因而要進行編碼等工作。以上所述都屬圖像處理的范疇。對于一個圖像處理系統(tǒng)來說，可以將流程分成3個階段：首先是圖像處理階段，第二是圖像分析階段，第三是圖像理解階段。圖像處理階段主要是在像素級上進行處理，圖像的幾何校正，圖像的灰度處理，圖像噪聲濾除的平滑處理，目標物體邊界的銳化處理等。圖像分析階段主要對圖像里感興趣的目標進行檢測、分割、特征提取和測量，分析的結(jié)果能為用戶提供描述圖像目標特點和性質(zhì)的數(shù)據(jù)，把原來以像素描述的圖像轉(zhuǎn)變成比較簡潔的非圖像方式的描述。圖像理解階段主要通過對圖像里各目標的性質(zhì)和它們之間相互關(guān)系的研究，對描述抽象出來角符號進行運算，了解把握圖像內(nèi)容并解釋原來的客觀場景，提供客觀世界的信息，指導(dǎo)和規(guī)劃行為。圖像處理就是將圖像轉(zhuǎn)換成一個數(shù)字矩陣存放在計算機中，并采用一定的算法對其進行處理。圖像處理的基礎(chǔ)是數(shù)學(xué)，最主要的任務(wù)就是各種算法的設(shè)計和實現(xiàn)。目前的圖像處理技術(shù)已經(jīng)在許多不同的應(yīng)用領(lǐng)域中得到重視，并取得重要的分支，其中研究的內(nèi)容概括起來主要包括如下5個方面：1)圖像數(shù)字化:通過采樣與量化過程將模擬圖像變換成便于計算機處理的數(shù)字形式。圖像在計算機內(nèi)通常用一個數(shù)字矩陣來表示，矩陣中的每一個元素稱為像素。圖像數(shù)字化的設(shè)備主要是各種掃描儀與數(shù)字化儀。2)圖像增強:主要目的是增強圖像中有用的信息，削弱干擾和噪聲，使圖像清晰或?qū)⑵滢D(zhuǎn)換為更適合人或計算機分析的形式。圖像增強并不要求真實的反映原始圖像。常用方法有直方圖增強和偽彩色增強等。3)圖像重建(恢復(fù)):使退化了的圖像，去掉退化因素，以最大的保真度，恢復(fù)成原來的圖像?；謴?fù)圖像的質(zhì)量，將不僅根據(jù)人的主觀感覺來判斷，而且也根據(jù)某種客觀的衡量標準。4)圖像編碼:圖像編碼研究屬于信息論中信源編碼的范疇。它是在滿足一定的保真度要求下，簡化圖像的表小，從而大大壓縮表示圖像的數(shù)據(jù)，以便于存儲和傳輸。5)圖像分析:對圖像中的不同對象進行分割、分類、識別和描述、解釋。目前數(shù)字圖像處理的應(yīng)用越來越廣泛，已經(jīng)滲透到工業(yè)、醫(yī)療保健、航空航天、軍事等各個領(lǐng)域，在國民經(jīng)濟中發(fā)揮越來越大的作用。其中最典型的應(yīng)用有：(1)遙感技術(shù)中的應(yīng)用遙感圖像處理的用處已經(jīng)越來越大，并且其效率和分辨率也越來越高。它被廣泛地應(yīng)用于土地測繪、資源調(diào)查、氣象監(jiān)測、環(huán)境污染監(jiān)督、農(nóng)作物估產(chǎn)和軍事偵察等領(lǐng)域。目前遙感技術(shù)已經(jīng)比較成熟，但是還必須解決其數(shù)據(jù)量龐大、處理速度慢的特點。(2)醫(yī)學(xué)應(yīng)用圖像處理在醫(yī)學(xué)上有著廣泛的應(yīng)用。其中最突出的臨床應(yīng)用就是超聲、核磁共振、相機和CT等技術(shù)。在醫(yī)學(xué)領(lǐng)域利用圖像處理技術(shù)可以實現(xiàn)對疾病的直觀診斷和無痛、安全方便的診斷和治療，受到了廣大患者的歡迎。(3)安全領(lǐng)域利用圖像處理的模式識別等技術(shù)，可以利用在監(jiān)控、指紋檔案管理等安全領(lǐng)域中。目前有清華大學(xué)工程物理系開發(fā)研制的大型集裝箱檢測系統(tǒng)，就是利用圖像處理技術(shù)來實現(xiàn)全自動集裝箱檢測，從而加快了海關(guān)的工作效率，為打擊走私立下汗馬功勞。(4)工業(yè)生產(chǎn)產(chǎn)品的無損檢測也是圖像處理技術(shù)的一項廣泛應(yīng)用?？傊?，圖像處理技術(shù)的應(yīng)用是相當廣泛的它在國家安全、經(jīng)濟發(fā)展、日常生活中充當著越來越重要的角色，對國計民生有著不可忽略的作用8。表1.1 圖像處理的應(yīng)用領(lǐng)域?qū)W科應(yīng)用物理、化學(xué)結(jié)晶分析、譜分析等生物、醫(yī)學(xué)細胞分析、染色體分類、X射線成像、CT等環(huán)境保護水質(zhì)及大氣污染調(diào)查等地質(zhì)資源勘測、地圖繪制、GIS等農(nóng)業(yè)、林業(yè)農(nóng)產(chǎn)物估產(chǎn)、植被分布調(diào)查等漁業(yè)魚群分布調(diào)查等氣象衛(wèi)星云圖分析等通信 、電視、多媒體通信等工業(yè)工業(yè)探傷、機器人、產(chǎn)品質(zhì)量檢測等軍事導(dǎo)彈導(dǎo)航、軍事偵查等法律指紋識別等圖像檢測技術(shù)發(fā)展歷史及現(xiàn)狀圖像檢測作為圖像分析技術(shù)的一個研究內(nèi)容，它也是伴隨著數(shù)字圖像處理的發(fā)展而發(fā)展的。數(shù)字圖像處理這門學(xué)科的形成也是和社會生產(chǎn)力發(fā)展的需要分不開的。早期的圖像處理是由于通訊方面的要求而發(fā)展起來的，這就是本世紀20年代 技術(shù)的發(fā)明和發(fā)展。其后，則是由于宇宙方面的要求，需要處理大量的宇宙探測器上拍攝下來的不清楚的其他天體(如月球、火星等)以及地球本身的照片。然而，圖像處理技術(shù)的發(fā)展，遠遠突破了這兩個領(lǐng)域，到今天，它已經(jīng)廣泛的應(yīng)用到科學(xué)研究、工農(nóng)業(yè)生產(chǎn)、軍事技術(shù)、政府部門、醫(yī)療衛(wèi)生等許多領(lǐng)域，進一步推動著社會生產(chǎn)力的發(fā)展。圖像檢測是圖像分析研究內(nèi)容的一部分。目前，在圖像分析領(lǐng)域已經(jīng)有很大的發(fā)展。圖像分析是一種從一幅圖像中通過自動的或半自動的方法提取圖像尺寸、數(shù)據(jù)或信息的方法。圖像分析方法通常因圖像分析系統(tǒng)最后的輸出是數(shù)字而不是畫面，使它與其他類型的圖像處理方法，如編碼、恢復(fù)、放大等不同。圖像分析源于經(jīng)典的模式識別方法，根據(jù)定義，分析系統(tǒng)并不局限于對一個固定數(shù)量類別的場景區(qū)域的分類，而是更傾向于可設(shè)計成用于描繪復(fù)雜場景。根據(jù)事先預(yù)測，該場景的種類可能是非常多的和不確定的。目前，圖像分析領(lǐng)域主要包括形態(tài)學(xué)圖像處理、邊緣檢測、圖像特征提取、圖像分割、形狀分析、圖像檢測和配準等幾個方面的內(nèi)容：(1)形態(tài)學(xué)圖像處理：它的基本概念可以追朔到Mnikowski對空間集合代數(shù)的研究和Matheron對拓撲的研究。形態(tài)學(xué)圖像處理是這樣的一種處理類型，它對圖像中的物體的空間形態(tài)或結(jié)構(gòu)進行修改。膨脹、腐蝕和骨架化是三種基本的形態(tài)學(xué)計算。(2)邊緣檢測：一幅圖像的振幅屬性(如亮度或三色值)的變化或突變是對圖像進行描述的重要特性，因為它們常指示圖像中物體的物理特性。從一個層面到另一個層面的圖像亮度的局部突變叫亮度邊緣。對于亮度圖像中的邊緣檢測、直線檢測和點檢測有兩類近似方法：微分檢測和模型擬合。(3)圖像特征提?。簣D像的特征是指圖像顯著的基本特征或特性。一些圖像是其本質(zhì)的特性，在一定程度上這樣的特征可以從視覺上分辨出來，另一些則是通過某些變換產(chǎn)生的人為特征。本質(zhì)特征包括像素區(qū)域和灰度紋理區(qū)域的亮度。(4)圖像分割：圖像分割法使圖像被劃分成或分隔成具有相近特征的區(qū)域。對于圖像分割法，其最基本的特征是:單色照片圖像的亮度振幅和彩色圖像的彩色因素。圖像邊緣和紋理也是對分割法很有用的特征。(5)形狀分析：目前已經(jīng)提出了幾種定性的和定量的方法來描述圖像中物體的形狀，這些方法對于在模式識別系統(tǒng)中對物體進行分類和在圖像理解系統(tǒng)中象征性的描述物體是很有用的。在這些方法中，有一些只能應(yīng)用在二進制圖像中，另外的一些則可以被擴展到灰度圖像中。(6)圖像檢測和配準：圖像檢測主要是確定位于圖像內(nèi)被猜測的物體是存在還是不存在的。而圖像配準主要是涉及到一對圖像區(qū)域的空間配準問題。在一個圖像區(qū)域中，物體檢測的一種最基本方法是通過模板匹配來進行。在目前的實際應(yīng)用中，廣泛的利用Hough變換來進行圓形或橢圓性的物體檢測。本文主要是研究Hough變換在圓形物體檢測中的應(yīng)用。在實際的圖像檢測和配準中，利用模板匹配是物體檢測的一種最基本的方法。在匹配過程中，把所關(guān)注的物體的拷貝和圖像區(qū)域中的所有的未知物體進行比較，如果模板和未知物體是匹配的，并且模板是足夠精確的，則未知物體被標識為模板物體。由于存在圖像噪聲、空間和振幅量化效應(yīng)以及對于要檢測的物體的精確形狀和結(jié)構(gòu)的預(yù)先不確定性，模板匹配很難保證精確性。分析物體檢測的整個過程，自然界中的一幅連續(xù)圖像對其數(shù)字化的描述，經(jīng)過圖像的增強、圖像的恢復(fù)后得到的數(shù)字圖像，要實現(xiàn)對其特定形狀圖形的檢測，還需要對二進制的圖像進行圖像分析，其中包括:形態(tài)學(xué)的處理，圖像分割、邊緣檢測、必要時還需要對其進行圖像彩色特征提取。經(jīng)過這些處理后才可進行圖像的檢測和配準。而每個處理過程涉及的算法都有一定的使用范圍和局限性，如何利用和有效組合每個處理過程中現(xiàn)有的成熟技術(shù)，一直是圖像檢測中的難點。檢測識別問題上的一個難點:假設(shè)現(xiàn)在有一個識別的問題，一幅圖像，其中包含了一些簡單的幾何形狀:矩形、圓等。任務(wù)就是編寫計算機程序，自動的識別這些形狀。還有一些影響識別的因素，是由圖像質(zhì)量以及多義性引起的。比如噪音，在有意義的目標附近存在大量的干擾信息，當對圖像中的點進行梯度運算時，這些干擾信息會造成計算上的錯誤，這些都給識別帶來了很大的困難，同時這也是多義性產(chǎn)生的原因。即使是人來識別也會遇到這個問題:重疊覆蓋。檢測圖像多個目標的時候，一個目標覆蓋了另一個，使得另一個目標的信息不完整；交叉、目標與目標之間的交叉點是難于處理的。數(shù)字圖像處理過程中的經(jīng)典問題之一圓形檢測，有著廣泛的應(yīng)用背景，也面臨著上述同樣的問題。研究者們提出了多種圓形檢測的方法，其中非常重要的一種:基于Hough變換的累積方法。圓的Hough變換(CHT)是目前應(yīng)用最為廣泛的圓檢測方法，該方法的最大特點是可靠性高，在噪聲、變形大部分區(qū)域不完整的狀態(tài)下依然能取得理想的結(jié)果，但該方法的缺點是計算量大，資源需求大。所以如何減少算法的計算量和存儲量在近年得到了廣泛的重視，已提出了不少改進算法，如隨機Hough變換算法。但大多數(shù)的這些算法都是假設(shè)圖像在計算機中能用完美的模型來描繪原始圖像。然而，在現(xiàn)實生活中，由于噪音、數(shù)字化錯誤和圖形變異等因素影響，真實的圖形經(jīng)常被曲解。盡管輸入圖像是完整的，但圖像在計算機中很難用完美的模型來描繪)本文將針對此類問題，利用現(xiàn)有的關(guān)于圓圖形檢測理論和技術(shù)，結(jié)合模糊數(shù)學(xué)中的相關(guān)理論進行檢測。本章首先大概介紹了本次論文的背景，接著著重講解了數(shù)字圖像處理，引入了圖像檢測技術(shù)的發(fā)展現(xiàn)狀，并指出了圖像檢測技術(shù)。本論文中主要工作如下：(1)通過圖像邊緣提取算子得到測試灰度圖像邊緣的二值圖像；(2)用matlab、c或OpenCV環(huán)境完成一個Hough變換檢測圓的函數(shù)程序；(3)對步驟(1)得到的二值圖像進行Hough變換，將圖像空間變換到參數(shù)空間；(4)在參數(shù)空間搜索超過閾值的聚焦點，即同一圓上的點；(5)改變半徑范圍，檢測符合制定半徑的圓。2 Hough變化的原理和發(fā)展Hough變換是圖像處理中從圖像中識別幾何形狀的基本方法之一。Hough變換的基本原理在于利用點與線的對偶性，將原始圖像空間的給定的曲線通過曲線表達形式變?yōu)閰?shù)空間的一個點。這樣就把原始圖像中給定曲線的檢測問題轉(zhuǎn)化為尋找參數(shù)空間中的峰值問題。也即把檢測整體特性轉(zhuǎn)化為檢測局部特性。比如直線、橢圓、圓、弧線等. 同時，將概率論、模糊集理論、分層迭代的思想和級聯(lián)的方法應(yīng)用于Hough變換的過程中，大大地提高了Hough變換的效率，改善了Hough變換的性能。1962年，Paul Hough提出了Hough變換法，并申請了專利。該方法將圖像空間中的檢測問題轉(zhuǎn)換到參數(shù)空間，通過在參數(shù)空間里進行簡單的累加統(tǒng)計完成檢測任務(wù)，用大多數(shù)邊界點滿足的某種參數(shù)形式來描述圖像的區(qū)域邊界曲線，因而對于被噪聲干擾或間斷區(qū)域邊界的圖像，Hough變換具有很好的容錯性和魯棒性。Hough變換法最初主要用于檢測圖像空間中的直線，最早的直線Hough變換是在兩個笛卡爾坐標系之間進行變換，這給檢測斜率為無窮大的直線帶來了困難。1972年，Duda將Hough變換法的變形形式進行了改變，將數(shù)據(jù)空間中的點變換為-參數(shù)空間的曲線，改善了其探測直線的性能。由于經(jīng)典的Hough變換法只能檢測圖像空間中的直線，為了能檢測到圖像空間中的曲線，在1978年Sklansky將Hough變換進行推廣，提出了推廣Hough變換法來檢測圖像空間中的曲線?；谧儞Q方程的不同，Hough變換法可以檢測出圖像空間中的圓、橢圓、拋物線、雙曲線等可以有解析式表達的曲線。但是經(jīng)典的Hough變換計算量比較大，在實際應(yīng)用中很難實現(xiàn)。為了解決這個問題，40余年以來，許多學(xué)者致力于Hough變換算法的研究，將隨機過程、模糊理論等應(yīng)用于Hough變換，并將分層迭代、級聯(lián)的思想引入到Hough變換的過程中，大大提高了Hough變換的效率。2.1 Hough直線檢測原理1962年，Paul Hough根據(jù)數(shù)學(xué)對偶性原理提出了檢測圖像直線的方法，此后該方法被不斷地研究和發(fā)展，主要應(yīng)用于模式識別領(lǐng)域中對二值圖像進行直線檢測。其原理如圖2.1所示，平面直角坐標系中的直線L表達為: (2.1)其中，a為斜率，c為截距。據(jù)式(2.1)，直線L上不同的點(x,y)在參數(shù)空間中被變換為一族相交于P點的直線。顯然，若能確定參數(shù)空間中的P點（局部最大值），就實現(xiàn)了直線的檢測。平面中任意一條直線也可以用極坐標方程來表示，即可以用和兩個參數(shù)確定下來，對于圖像空間任意點,其函數(shù)關(guān)系為： (2.2)其中為原點到直線的距離（即原點到直線的垂直線的長度），確定了直線的方向（即原點到直線的垂直線與x軸方向的夾角）。如果對位于同一直線l上的n個點進行上述變換，則原圖像空間n個點在參數(shù)空間中對應(yīng)地得到n條正弦曲線，并且這些曲線相交于同一點。X坐標Y坐標Hough變換截距斜率P圖2.1： 直線檢測中的Hough變換由上述Hough變換原理可知，Hough變換具有如下性質(zhì)：(1)直角坐標系中的一個點映射到參數(shù)空間中為一條線；(2)參數(shù)空間中的一個點對應(yīng)直角坐標系中的一條線；(3)直角坐標系中的共點線映射到參數(shù)空間中為一條線；(4)直角坐標系中的共線點映射到參數(shù)空間中后為一個交于同一點的線簇。圖2.2為matlab模擬結(jié)果，從圖中我們可知，經(jīng)過Hough變換后，在原空域中的一個點變成了一條曲線，曲線橫坐標為，縱坐標為。代表經(jīng)過原空間的以點為圓心、斜率在-,+之間的所有直線。 圖2.2 點的Hough變換matlab模擬 圖2.3為直線的Hough變換，可以看到，原空間的一條直線變換到Hough空間就變成了很多條曲線的交疊，通過投票法我們可以的得到點最為集中位置的和，從而確定原始空間直線的信息。 圖2.3 直線的Hough變換圖2.4和圖2.5分別是以直線為主要構(gòu)成元素的三角形和長方形的Hough變換，與Hough變換獲得直線信息相似，在三角形的Hough空間，我們獲得了三個局部極大值點，通過這三個點可以判斷原空間中三角形三條邊的信息，繼而確定了三個頂點的位置，連接三個頂點，獲得了三角形信息。長方形的檢測方法同上。因此，通過Hough變換檢測由直線構(gòu)成的圖形和圖像中的直線，采用的都是全局極值投票判定。 圖2.4 三角形的Hough變換 圖2.5 長方形的Hough變換2.2 Hough變換的發(fā)展Hough變換最初只用于從圖像中識別圖形邊界，經(jīng)過幾十年的發(fā)展，Hough變換現(xiàn)在已經(jīng)用于各個方面的圖像處理，包括辦公文檔圖像處理、多普勒-時間圖像處理、航空圖像自動判斷等。隨著科學(xué)技術(shù)的發(fā)展，Hough變換在軍事和民用領(lǐng)域?qū)玫綇V泛的應(yīng)用。1994年，Carlson等人將Hough變換法應(yīng)用到搜索雷達中檢測直線運動或近似直線運動的低可觀測目標。1996年，JiChen等人將Hough變換法應(yīng)用于航跡起始中。除此之外，在國防科技領(lǐng)域，Hough變換還廣泛用于低可觀測信號檢測、聲納信號處理、雷達目標跟蹤、ESM目標跟蹤、紅外目標跟蹤、多傳感器多目標跟蹤、多傳感器信息融合等方面。圓形檢測是數(shù)字圖像處理過程中的經(jīng)典問題之一，有著廣泛的應(yīng)用背景，研究者們提出了多種圓形檢測的辦法，基于Hough變換的累積方法是其中非常重要的一種方法。圓的Hough變換（CHT）是目前應(yīng)用最為廣泛的圓檢測方法，該方法最大特點是可靠性高，目前已經(jīng)提出了多種基于Hough變換的圓的檢測算法，其中的一些算法在繼承Hough變換優(yōu)勢的同時，也對Hough變換過程中存在的計算量大、資源需求大等缺點進行了很好的改進，如隨機Hough變換算法。同時，Hough變換的測量數(shù)據(jù)的預(yù)處理、參數(shù)空間的離散化、門限的選擇、平均虛警概率的問題都得到了解決，如集束算法、基于邏輯的檢測方法、數(shù)據(jù)的融合等方法。2.3 Hough變換實現(xiàn)方法工程中的實驗數(shù)據(jù)和圖像處理中的二值邊緣圖，通常都是離散數(shù)據(jù)，因此，根據(jù)Hough變換性質(zhì)，可按下列步驟實現(xiàn)Hough變換17-18：(1)將參數(shù)空間量化成(為的等份數(shù)，為的等份數(shù))個單元，并設(shè)置累加器矩陣；(2)給參數(shù)空間中的每個單元分配一個累加器,并把累加器的初始值置為零；(3)取出直角坐標系中的點代入式(2-2)，并以量化的值計算出；(4)在參數(shù)空間中，找到和所對應(yīng)得單元，并將該單元的累加器加1，即；(5)當直角坐標系中的點都經(jīng)過(3)(4)兩步遍歷后，檢驗參數(shù)空間中每個累加器的值，累加器最大的單元所對應(yīng)的和即為直角坐標系中的直線方程式(2-1)的參數(shù)。當直角坐標系中的點分布在R條直線附近時，可在第5步檢測累加器時，取出累加器中前R個值最大的單元所對應(yīng)的和，以和為直角坐標系中直線方程式(2-2)的參數(shù)，即可同時實現(xiàn)多條直線的檢測。2.4 Hough變換應(yīng)用領(lǐng)域經(jīng)典Hough變換的計算量大，在實際應(yīng)用中很難實現(xiàn)。40年來，許多學(xué)者將隨機過程、模糊集理論、分層迭代的思想和級聯(lián)的方法應(yīng)用于Hough變換中，就形成了隨機Hough變換、模糊Hough變換、分層迭代Hough變換、級聯(lián)Hough變換和三維Hough變換，這使的Hough變換的應(yīng)用越來越廣泛，例如將Hough變換應(yīng)用在圖像處理，信號檢測等方面。(1)Hough變換最初是作為圖像處理的方法提出來的。Hough變換的一個突出的有點是抗干擾能力強。如果待檢測的曲線上有小的擾動或斷裂，或者存在背景噪聲，算法都能準確的檢測出曲線。甚至對于直線，經(jīng)Hough變換后，在變換空間中仍然能夠得到明顯的峰值點。所以，Hough變換在圖像處理中應(yīng)用的非常廣泛。Hough變換在圖像處理中的應(yīng)用主要是對圖像中特定形狀的識別和檢測。它具體可以用來對圖形進行識別，提取圖像拐點，SAR圖像處理，傾斜文本圖像校正和檢測，多普勒-時間圖像處理以及航空圖像自動判讀等等。采用Hough變換進行形狀特征提取，可對形狀進行有效的識別，可并行實現(xiàn)，而且對噪聲不敏感，所提取的特征不受待識別形狀大小及所在圖像中的位置的影響。但由于Hough變換必須逐點處理圖像平面上的每一點，計算量大，內(nèi)存開銷較大，特別是對于圖像幅面大，前景復(fù)雜的圖形時尤其明顯。對圖像進行濾波和邊緣檢測雖然能夠加快處理速度，但識別精度會受到不同成都的影響。(2)基于Hough變換的信號檢測方法既可以用于低可觀測信號的檢測，也能用于強雜波環(huán)境下的多目標跟蹤。通過Hough變換，可以把可能是同一個航跡的回撥能量進行非相干積累。由于非相參積累的作用，低可觀測目標的能量得以積累，增強了低可觀測目標的信噪比，從而可以對低可觀測目標進行檢測。利用Hough變換對信號進行檢測主要有兩種方法：一是基于Hough變換的非相干積累法，二是基于Hough變換的二值積累法。其中，Hough變換的非相參積累方式對低可探測目標的檢測性能有一定的改善，由于它不需要對目標進行回掃即可進行檢測前跟蹤，因此在強雜波環(huán)境下基于Hough變換的檢測是常規(guī)檢測手段的一種有益的補充。(3)航跡起始是航跡處理中的首要問題，但同航跡處理中的跟蹤維持的研究相比，航跡處理中的航跡起始算法比航跡處理中的航跡維持算法更為復(fù)雜?，F(xiàn)有的航跡起始算法可分為順序處理技術(shù)和批數(shù)據(jù)處理技術(shù)兩大類。通常，順序數(shù)據(jù)處理技術(shù)適用于相對無雜波環(huán)境中的航跡起始，主要包括啟發(fā)式規(guī)則方法和基于邏輯的方法。批數(shù)據(jù)處理技術(shù)適用于雜波環(huán)境，主要包括Hough變換法和修正的Hough變換法等。Hough變換還可以應(yīng)用到三維空間中的航跡起始。由于Hough變換只適用于起始二維平面中的目標航跡，因此在實際工程中，可以根據(jù)實際的需要選擇投影面，然后在利用基于Hough變換和邏輯的起始算法，并將各個平面起始的航跡進行比較和關(guān)聯(lián)起始三維空間中的航跡。而且通過在密集雜波環(huán)境下的航跡起始仿真驗證了該方法特別適用于在密集雜波環(huán)境中快速起始三維空間中的軌跡。(4)Hough變換在多傳感器多目標跟蹤中的應(yīng)用利用多傳感器獲取數(shù)據(jù)來進行多目標跟蹤的技術(shù)在許多軍事和民用領(lǐng)域得到了廣泛的應(yīng)用。從本質(zhì)上講，多傳感器多目標跟蹤系統(tǒng)成功的關(guān)鍵都在于數(shù)據(jù)關(guān)聯(lián)算法的有效性。在一般情況下，數(shù)據(jù)關(guān)聯(lián)問題可以分解為兩項單獨的任務(wù)：用于航跡其實起始的測量-測量關(guān)聯(lián)和用于航跡維持的測量-測量關(guān)聯(lián)。而Hough變換特征檢測方法是可以用作實現(xiàn)目標航跡起始的一種有效方法，通過將前幾次搜索掃描所感知的數(shù)據(jù)組合成多維數(shù)據(jù)矢量，可以用Hough變換從復(fù)合數(shù)據(jù)中檢測出軌跡。文獻19-20對Carlson等人的工作進行了拓展，并提出了可用于在雜波環(huán)境中緝拿測兵起始多目標航跡的基于Hough變換的多傳感器數(shù)據(jù)關(guān)聯(lián)方法?；贖ough變換的多傳感器，多目標航跡起始方法的最大優(yōu)勢在于其對多傳感器結(jié)構(gòu)的適應(yīng)能力，因為在所有仿真中，多傳感器結(jié)構(gòu)的性能總是優(yōu)于單傳感器結(jié)構(gòu)的性能。而且雜波不會顯著影響航跡起始性能，但可以看到雜波密度的增加會引起虛假航跡起始率的上升。本章小結(jié)本章首先講述了Hough變換的原理和實現(xiàn)方法，并簡單介紹了其研究現(xiàn)狀和存在的問題，接著介紹了Hough變換的應(yīng)用領(lǐng)域。Hough變換是一種用來在邊緣增強處理后的圖像中，提取邊緣特征的簡便而有效的方法，它能夠提取直線、圓、橢圓、二次曲線甚至是任意形狀的邊緣。Hough變換在計算機視覺、軍事防御、辦公自動化等領(lǐng)域都得到了普遍的關(guān)注和廣泛的應(yīng)用。Hough變換1962年由Paul Hough提出，并在美國作為專利。它所實現(xiàn)的是一種從圖像空間到參數(shù)空間的映射關(guān)系。Hough變換的實質(zhì)是將圖像空間內(nèi)具有一定關(guān)系的象元進行聚類，尋找能把這些象元用某一解析形式聯(lián)系起來的參數(shù)空間累積對應(yīng)點。經(jīng)過幾十年的發(fā)展，Hough變換現(xiàn)在已經(jīng)用于各個方面的圖像處理，包括SAR/ISAR圖像處理、辦公文檔圖像處理、多普勒-時間圖像處理、航空圖像自動判讀等。隨著科學(xué)技術(shù)的發(fā)展，Hough變換在軍事和民用領(lǐng)域得到了廣泛的應(yīng)用。比如在國防科技領(lǐng)域，Hough變換被用于低可觀測信號檢測、聲納信號處理、雷達目標跟蹤、ESM目標跟蹤、紅外目標跟蹤、多傳感器多目標跟蹤、多傳感器信息融合等方面。在民用領(lǐng)域，Hough變換在水聲目標形狀分析、人臉圖像識別、地下目標檢測、車輛識別、目標平移和旋轉(zhuǎn)運動分析等方面發(fā)揮著巨大的作用。總之，Hough變換的作用已被世界各國所認識，顯示出了巨大的應(yīng)用價值和重要的應(yīng)用前景。3 Hough變換圓檢測 Hough變換圓檢測原理和性能分析(1) Hough變換圓檢測原理 Hough變換常常被用于直線段、圓和橢圓的檢測。其基本思想是將圖像的空間域變換到參數(shù)空間，用大多數(shù)邊界點滿足的某種參數(shù)形式來描述圖像中的曲線(區(qū)域邊界)。通過設(shè)置累加器進行累加，求得峰值對應(yīng)的點就是所需要的信息。經(jīng)典的Hough圓檢測假設(shè)希望在圖像平面(X-Y平面)考察并確定一個圓周。令為圖像中欲確定圓周上的點的集合，而為集合中的一點，它在參數(shù)坐標系中方程為: （3.1）顯然對于來說，圓上的一點其橫坐標x=a+rcos()，縱坐標y=b+rsin()。若已經(jīng)知道待檢測圓的半徑，那么檢測工作就相對容易一些，如圖3.1所示，由于圓點到圓上的點的距離相同，所以以圓上的點為圓心，相同的半徑r畫圓，最后就可以通過投票法得到圓心位置，最后在原坐標中確定圓。圖3.1 已知半徑圓的檢測若圓的半徑未知，即r是一個變量，那么方程3-1為三維錐面，對于圖像中任意確定的一點均有參數(shù)空間的一個三維的錐面與之對應(yīng)。對于圓周上的任何點集合，這些三維錐面構(gòu)成圓錐面簇。圖3.2 未知半徑的圓檢測的Hough變換原理若集合中的點在同一個圓周上，則這些圓錐簇相交于參數(shù)空間上某一點，這點恰好對應(yīng)于圖像平面的圓心坐標及圓的半徑。對于離散圖像，式(3-1)可寫為: (3.2)其中是考慮到對圖像進行數(shù)字化和量化的補償。Hough變換的基本思想在于證據(jù)積累，一般情況下圓變換的參數(shù)空間為三維的，在三維積累空間上進行證據(jù)累加的時間空間消耗是非常大的，在具體應(yīng)用中幾乎是不可能的，不現(xiàn)實的。(2) Hough變換圓檢測性能分析由以上分析可以看出，影響常規(guī)Hough變換運算速度的主要因素有:邊緣點的數(shù)量，參數(shù)空間維數(shù)，參數(shù)空間的離散化程度，運算的復(fù)雜性，以及最后的峰值檢測。對于半徑為，圓心坐標為的圓在參數(shù)空間的表示為: (3.3)顯然，上式表示的是一個三維錐面，它的物理意義是，圖像空間中的圓對應(yīng)著參數(shù)空間的一個點，而圖像空間中的一個點對應(yīng)著參數(shù)空間中的一個三維圓錐。對于圖像空間中的一個圓其半徑是固定不變的，圓周上的各個點組成的集合在參數(shù)空間就表現(xiàn)為相等而、不等的各個圓錐的集合。圖像空間中圓上的點映射到參數(shù)空間的一簇圓錐的交點正好對應(yīng)于圓心坐標和半徑。對于參數(shù)空間適當量化，得到一個三維的累加列陣，用來記錄，當檢測圖像空間中的圓時，計算與邊緣上的每一個像素距離r的所有，同時在對應(yīng)的列陣中累加，當對全部邊緣點變換完成后，對三維列陣中的所有累加值進行檢驗，其中的峰值就對應(yīng)圖像空間中的圓心。由于圖像是離散的，對(3-3)式的判別可改寫為: (3.4)對于邊緣上的每一點，給定半徑，那么對、的變化各需要計算次上式，同時排除已經(jīng)計算過的重復(fù)點，因而總共需要計算次左右。假設(shè)每次耗時，那么對于一個邊緣點需耗時，再假設(shè)半徑的變化范圍為，則每個邊緣點耗時為: (3.5)假設(shè)有N個邊緣點，則總耗時即為，本系統(tǒng)所涉及到的圖像，N通常在2000以上，那么總耗時中t的系數(shù)就是10的6次方以上，這個計算量是相當大的。顯然，單就這一環(huán)節(jié)，就需要耗費大量的運行時間和存儲空間，因而，對于常規(guī)Hough變換的改進要求是非常之迫切的。雖然常規(guī)Hough變換有明顯的缺憾，但是由于它完全按照Hough變換的定義進行，所以通常用來作為改進算法的參照對象。Hough變換的基本思想在于證據(jù)積累，一般情況下圓變換的參數(shù)空間為三維的，需要在參數(shù)空間建立一個三維的累加數(shù)組,根據(jù)具體的圖像數(shù)據(jù)點計算出的每一個三元組，對累加，其具體變換過程如下：(1)在、合適的最大值和最小值之間建立一個零散的參數(shù)空間；(2)建立一個累加器,并置每一個元素為0；(3)對圖像空間中超過門限值的每一點作Hough變換，即算出該點在三維網(wǎng)格上的對應(yīng)曲線，并在相應(yīng)的累加器加1： (3.6)(4)找出對應(yīng)圖像平面共圓周點累加器上的局部最大值，這個值就提供了圖像平面上共圓周點的圓心以及半徑參數(shù)。由于Hough變換的實質(zhì)是將圖像空間的具有一定關(guān)系的像元進行聚類，尋找能把這些像元用某一解析形式聯(lián)系起來的參數(shù)空間累積對應(yīng)點。在參數(shù)空間不超過二維的情況下，這種變換有著很理想的效果。然而，當參數(shù)空間超過二維時，這種變換的時間消耗和所需存儲空間的急劇增大使得這種變換僅僅在理論分析上可行，而在實際應(yīng)用中幾乎是不可能實現(xiàn)的。這時往往需要從具體的應(yīng)用情況中尋找特點，如利用被處理圖像像元的灰度的變化值確定灰度的變化方向來降低參數(shù)空間維數(shù)，或利用一些對于被檢測圖像的先驗知識來設(shè)法降低變換過程的時間和空間的開銷。在參數(shù)空間中，將設(shè)為遞增變量，每一步迭代都先固定，在垂直于的平面上求對應(yīng)于圓心為的圓周各點，并將軌跡上的點在與此平面映像的一個三維累加數(shù)組上的相應(yīng)點上累加。從0開始遞增直到圖像平面所能容納的上限（一般可根據(jù)先驗知識來確定r的可能變換范圍來減少計算量），每次遞增均有一平面映像與之對應(yīng)。因此，對于圖像上每一確定點,和的變化范圍均為。求出在此范圍內(nèi)對應(yīng)的每一和的坐標，即要計算式（3.2）次。設(shè)每次這種計算耗時為，則對應(yīng)的每一步進的得計算耗時為。若設(shè)的步進范圍為，則對應(yīng)于每個像元的計算量為：若對圖像平面上的若干個點進行Hough變換，則總耗時將為 。而用于累加陣列的存儲空間約為字節(jié)（設(shè),分別為圖像的高度和寬度，累積單元采用單字節(jié)）。可見，以上運算的時空開銷是很大的。當全部點轉(zhuǎn)換完成后，對累加數(shù)組每個元素的值進行比較，有較大值得數(shù)組元素對應(yīng)于圓或圓弧，其參數(shù)可作為圓的擬合參數(shù)，而具有較小值得元素則舍棄。如圖3-3所示,從圖像空間中取八個圓的邊緣像素點A、B、C、D、E、F、G、H,以R為半徑將這八個點映射到參數(shù)空間?？梢钥吹?這八個點在參數(shù)空間中的投影均在O點相交,也即O點的累加值在參數(shù)空間中是最大的。同時, O點也是圖像空間中圓的圓心。此時, 圖像空間中每一邊緣點映射到參數(shù)空間得到的投影為一個圓。圖3.3 圖像空間及邊緣點在參數(shù)空間的投影檢測一定半徑范圍內(nèi)的圓的Hough算法通過上述描述我們可以知道，Hough變換檢測圓最常見的問題分為已知半徑和完全未知半徑圓的檢測。第一類問題比較容易實現(xiàn)，因為尋找歐氏距離相同的點不困難。而第二類問題由于半徑未知，并且每個點得到的范圍是個圓錐，所以計算量較大。而能夠?qū)崿F(xiàn)實時檢測，對于其應(yīng)用的推廣是極為重要的。在實際應(yīng)用中，能夠檢測到一定半徑范圍內(nèi)的圓是重要的應(yīng)用，因為即使是檢測規(guī)定半徑的圓，其實際檢測中也會存在一定的像素偏差，所以應(yīng)用中的檢測范圍是一個半徑圓環(huán)。本節(jié)針對的問題是，如何利用Hough變換檢測到一定半徑范圍內(nèi)的圓，并且效率要盡量高。(1) 經(jīng)典基于Hough變換的圓檢測算法經(jīng)典的Hough變換在圖像中尋找半徑已知的圓的圓心時,對整個圖像進行遍歷,尋找邊緣點需要兩重循環(huán)。遍歷到每個邊緣點時,求其在參數(shù)空間中的投影集合需要兩重循環(huán)。所以經(jīng)典的Hough變換在檢測半徑已知圓時需要四重循環(huán),這在實際計算中是極其耗時的。當遍歷到圖像中的邊緣點時,先求出邊緣點映射到參數(shù)空間得到的坐標點集合,然后對集合中每個坐標點元素對應(yīng)的累加值進行一次累加,此點在參數(shù)空間中的投影為坐標點集合(設(shè)圖像中邊緣點的數(shù)目為N 個,則n的取值范圍為 1, N ) 。將圖像放到坐標系中考慮時,由坐標平移的知識可以知道,當一個圓的圓心由點平移到點時,圓上任意一點的坐標就由變?yōu)?。這樣,圖像中每個邊緣點在參數(shù)空間中投影得到的坐標點集合就不需要通過計算得出,只需先求出一個基準點在參數(shù)空間中的投影,投影得到的坐標點集合為,其余的邊緣點在參數(shù)空間中的投影就可以通過將基準點在參數(shù)空間的投影即坐標點集合平移得到。這樣處理有如下優(yōu)點:在參數(shù)空間中減少參與運算的點,并且通過平移在參數(shù)空間得到的坐標點集合與通過計算在參數(shù)空間得到的坐標點集合基本相等。對任意一邊緣點,經(jīng)典Hough變換需要在參數(shù)空間中對以邊緣點為中心, 2R 為邊長的正方形內(nèi)所有像素點進行計算,判斷是否是邊緣點映射到參數(shù)空間得到的坐標點集合中的元素, 一共需要計算個像素點。改進的算法只需在參數(shù)空間中移動N 個點(N 為正方形內(nèi)滿足圓的方程的像素點個數(shù)) 。由于正方形內(nèi)的像素點不可能全部是邊緣點映射到參數(shù)空間得到的坐標點集合中的元素,必有。(2)基于Hough變換的規(guī)定半徑范圍的圓檢測算法由于算法效率主要取決于邊界點的個數(shù)，以及