基于Hough變換的圓檢測算法研究及其實現(xiàn)

江蘇科技大學本科畢業(yè)設計（論文）PAGEPAGE29基于Hough變換的圓檢測算法研究及其實現(xiàn)TheStudyandRealizationofCircleDetectionBasedonHoughTransform摘要圖像是人類獲取和交換信息的主要來源。圓是構成圖像的一個基本要素，因此，能夠快速、準確地對圓進行檢測，在圖像處理中顯得尤為重要。Hough變換是一種提取直線、圓、橢圓、二次曲線甚至是任意形狀邊緣的有效方法，目前已經(jīng)在軍事和民用領域將會得到廣泛的應用，如：圖像處理、信號檢測、雷達目標跟蹤、被動跟蹤、多傳感器多目標跟蹤等。但是，Hough變換大多數(shù)算法的計算量大，需要很大的存儲空間，而且都是假設圖像在計算機中能用完美的模型來描繪。然而，由于噪聲、數(shù)字化誤差等因素影響，真實的圖形在計算機中經(jīng)常會失真。本文針對Hough變換計算量大的情況研究了一種新的基于Hough變換的圓檢測的快速算法，即先檢測出一個內、外半徑已知的圓環(huán)，然后在整個圖像范圍內移動這個圓環(huán)，對移動后在圓環(huán)范圍內的點的個數(shù)進行累加，累加得到的局部最大值提供了檢測出的圓心坐標。這種方法實現(xiàn)了各類圓形、橢圓等非理想圖形的快速檢測，克服了Hough變換耗時巨大的缺陷。最后，本文采用VC++編程實現(xiàn)了這種Hough變換的圓檢測并進行了實驗研究，實驗結果表明，該快速算法能夠對各類圓形、橢圓等非理想圖形進行快速檢測，有一定的抗噪聲性能。該算法沒有很好的改善Hough變換需要很大的存儲空間的問題，這將是今后研究的一個方向。關鍵字：圖像處理，圓檢測，Hough變換,快速算法AbstractImageisthemainsourcethatpeoplegainandexchangeinformation,theapplicationdomainofimageprocessingmustrelatetohumanlifeandworkinallitsaspects.Thecircleisabasicessentialfactorconstitutingtheimage.Soitisimportantthatdetectingthecirclequicklyandaccuratelyinimageprocessingespecialtheindustrialimageprocessing.Houghtransformisaneffectivewaytodetectline、circle、ellipseevenanyshape.Formanyyears,researchersalldevotetostudythealgorithmofHoughtransform.NowHoughtransformhasbeenwidelyusedinmilitaryandcivildomain,suchasimageprocessing,signaldetection,radartargettrack,passivetrack,multitarget-multisensortrackandsoon.ButmostofthealgorithmsofHoughtransformcostmuchtimeandmemoryspace.Andtheyallsupposethattheimagecanbewelldescribedbyperfectmodelsincomputers.Otherwise,inourreallife,realimagesaredistortedbecauseoftheinfluenceofnoise,digitalerrorandsoon.Althoughtheimageinputiscomplete,theimageincomputersisdifficulttobewelldescribedbyperfectmodels.Aimedattheproblemofhugetimeconsuming,thispaperstudiedafastalgorithmforthedetectionofcircles.Theprincipleisthatwefirstdetectacirquewhichhasadefiniteinsideandoutsideradius,thenmovethiscirqueintheimage,addthenumberofpointinthemovedcirque.Thesomelargestpointsareconsideredtobethedetectedcircle.ThiswayimprovedhugetimeconsumingwhenusingthetraditionalHoughtransform.WerealizedthedetectionofcirclesofHoughtransformthroughVC++.Theresultshowsthatthiswayrealizedthedetectionofcirclesandellipsesandcanresisttheinfluenceofnoise.IwasverypitythatthisalgorithmdidnotsolvetheproblemthatHoughtransformneedsbigstoragespace.Thiswillbethedirectionofthefuturestudy.Keywords:imageprocessing,detectionofcircle,HOUGHtransformation,fastalgorithm目錄第一章緒論11.1課題的背景11.2數(shù)字圖像處理概述11.3圖像檢測技術發(fā)展現(xiàn)狀41.3.1圖像檢測技術發(fā)展歷史及現(xiàn)狀41.3.1存在的問題51.4Hough變換簡介61.5課題的研究內容71.6本章小結8第二章Hough變換92.1Hough變換原理92.2Hough變換實現(xiàn)方法102.3Hough變換的研究現(xiàn)狀102.3.1Hough變換的研究現(xiàn)狀102.3.2Hough變換研究存在的問題和解決方法112.4Hough變換應用領域122.4.1Hough變換在圖像處理中的應用132.4.2Hough變換在信號檢測中的應用132.4.3Hough變換在雷達目標跟蹤中的應用132.4.4Hough變換在多目標多傳感器跟蹤中的應用142.5本章小結14第三章Hough變換圓檢測算法163.1Hough變換圓檢測原理和性能分析163.1.1Hough變換圓檢測原理163.1.2Hough變換圓檢測性能分析173.2經(jīng)典Hough變換圓檢測算法183.3一種快速Hough變換圓檢測算法193.3.1快速Hough變換圓檢測算法基本思想193.3.2快速Hough變換圓檢測算法203.3.3快速Hough變換圓檢測計算量分析213.4本章小結22第四章Hough變換圓檢測圖像處理234.1引言234.2實驗結果與分析234.3本章小結26第五章結束語27致謝28參考文獻29第一章緒論1.1課題背景人工圖像和衛(wèi)星影像中，比如：光學干涉圖像和軍事駐地圖像，大多數(shù)物體都是由線或曲線組成的，所以，圖像處理中，對線或曲線的識別和定位就顯得十分重要。同時，工程上經(jīng)常要進行曲線檢測或擬合，對圓形器件或圖標進行模式識別和定位是一個常見的問題。在計算數(shù)學中圓檢測有多種方法，常用的有:基于圓形邊緣積分特性的環(huán)路積分微分法[1]、對邊界區(qū)域進行分區(qū)迭代擬合的檢測算法、基于最小二乘原理進行擬合的檢測算法、通過計算圓形目標的灰度重心提取圓心坐標的Wong-Trinder圓定位算子和模板匹配法、組合法[2]、魯棒性估計法[3]、形狀分析法等;此外還有一類通過代價函數(shù)的全局優(yōu)化來提取幾何基元的方法，如:模擬退火算法、遺傳算法[4]等。這些算法(或其組合)雖然在一些特定的場合已經(jīng)得到應用，在定位精度和計算速度等方面也取得了令人滿意的結果，但是這些方法的使用范圍往往比較有限，如:需要事先知道較多的目標圓的知識(大致的圓心位置和半徑范圍等)，且在標準的規(guī)則圖形和干擾噪聲少的場合才比較有效。Hough變換是一種用來在邊緣增強處理后的圖像中，提取邊緣特征的簡便而有效的方法，它能夠提取直線、圓、橢圓、二次曲線甚至是任意形狀的邊緣。而且Hough變換在計算機視覺、軍事防御、辦公自動化等領域都得到了普遍的關注和廣泛的應用。其基本思想是將原圖像變換到參數(shù)空間，用大多數(shù)邊界點滿足的某種參數(shù)形式來描述圖像中的曲線，通過設置累加器進行累積，求得峰值對應的點就是所需要的信息。Hough變換以其對局部缺損的不敏感、對隨機噪聲的魯棒性以及適于并行處理等優(yōu)良特性,備受圖像處理、模式識別和計算機視覺領域學者的青睞。Hough變換的突出優(yōu)點就是可以將圖像中較為困難的全局檢測問題轉換為參數(shù)空間中相對容易解決的局部峰值檢測問題。隨著Hough變換在圓檢測上的應用越來越廣泛，對基于Hough變換的圓檢測算法的進一步研究具有較好的研究意義和實用價值。1.2數(shù)字圖像處理概述圖像就是用各種觀測系統(tǒng)以不同形式和手段觀測客觀世界而獲得的，可以直接或間接作用于人眼而產(chǎn)生視知覺的實體。科學研究和統(tǒng)計表明，人類從外界獲得的信息約有75%來自于視覺系統(tǒng)，也就是說，人類大部分信息都是從圖像中獲得的。圖像處理是人類視覺延伸的重要手段，可以使人們看到任意波長上所測得的圖像。例如，借助伽馬相機、X光，人們可以看到紅外和超聲圖像；借助TC可以看到物體內部斷層圖像；借助相應工具可看到立體圖像和剖視圖像[5]。1964年，美國在太空探索中拍回了大量月球照片，但是由于種種環(huán)境因素的影響，這些照片是非常不清晰的，為此，美國噴射推進實驗室(JPL)使用計算機對圖像進行處理，使照片中的重要信息得以清晰再現(xiàn)。這是這門技術發(fā)展的重要里程碑。此后，圖像處理技術在空間研究方面得到廣泛應用。在研究圖像時，首先要對獲得的圖像信息進行預處理(前處理)以濾去干擾、噪聲，作幾何、彩色校正等。這樣可提高信噪比；有時由于信息微弱，無法辨識，還得進行增強處理。增強的作用，在于提供一個滿足一定要求的圖像，或對圖像進行分割，也就是進行定位和分離，以分出不同的物體。為了給觀察者以清晰的圖像，還要對圖像進行改善，即進行復原處理，它是把己經(jīng)退化了的圖像加以重建或恢復的過程，以便改進圖像的保真度[6]。在實際處理中，由于圖像信息量非常大，在存儲及發(fā)送時，還要對圖像信息進行壓縮。上述工作必須用計算機進行，因而要進行編碼等工作。以上所述都屬圖像處理的范疇。對于一個圖像處理系統(tǒng)來說，可以將流程分成3個階段：首先是圖像處理階段，第二是圖像分析階段，第三是圖像理解階段。圖像處理階段主要是在像素級上進行處理，圖像的幾何校正，圖像的灰度處理，圖像噪聲濾除的平滑處理，目標物體邊界的銳化處理等。圖像分析階段主要對圖像里感興趣的目標進行檢測、分割、特征提取和測量，分析的結果能為用戶提供描述圖像目標特點和性質的數(shù)據(jù)，把原來以像素描述的圖像轉變成比較簡潔的非圖像方式的描述。圖像理解階段主要通過對圖像里各目標的性質和它們之間相互關系的研究，對描述抽象出來角符號進行運算，了解把握圖像內容并解釋原來的客觀場景，提供客觀世界的信息，指導和規(guī)劃行為。圖像處理就是將圖像轉換成一個數(shù)字矩陣存放在計算機中，并采用一定的算法對其進行處理。圖像處理的基礎是數(shù)學，最主要的任務就是各種算法的設計和實現(xiàn)。目前的圖像處理技術已經(jīng)在許多不同的應用領域中得到重視，并取得重要的分支，其中研究的內容概括起來主要包括如下5個方面[7]：(1)圖像數(shù)字化:通過采樣與量化過程將模擬圖像變換成便于計算機處理的數(shù)字形式。圖像在計算機內通常用一個數(shù)字矩陣來表示，矩陣中的每一個元素稱為像素。圖像數(shù)字化的設備主要是各種掃描儀與數(shù)字化儀。(2)圖像增強:主要目的是增強圖像中有用的信息，削弱干擾和噪聲，使圖像清晰或將其轉換為更適合人或計算機分析的形式。圖像增強并不要求真實的反映原始圖像。常用方法有直方圖增強和偽彩色增強等。(3)圖像重建(恢復):使退化了的圖像，去掉退化因素，以最大的保真度，恢復成原來的圖像?；謴蛨D像的質量，將不僅根據(jù)人的主觀感覺來判斷，而且也根據(jù)某種客觀的衡量標準。(4)圖像編碼:圖像編碼研究屬于信息論中信源編碼的范疇。它是在滿足一定的保真度要求下，簡化圖像的表小，從而大大壓縮表示圖像的數(shù)據(jù)，以便于存儲和傳輸。(5)圖像分析:對圖像中的不同對象進行分割、分類、識別和描述、解釋。目前數(shù)字圖像處理的應用越來越廣泛，已經(jīng)滲透到工業(yè)、醫(yī)療保健、航空航天、軍事等各個領域，在國民經(jīng)濟中發(fā)揮越來越大的作用。其中最典型的應用有：(1)遙感技術中的應用遙感圖像處理的用處已經(jīng)越來越大，并且其效率和分辨率也越來越高。它被廣泛地應用于土地測繪、資源調查、氣象監(jiān)測、環(huán)境污染監(jiān)督、農作物估產(chǎn)和軍事偵察等領域。目前遙感技術已經(jīng)比較成熟，但是還必須解決其數(shù)據(jù)量龐大、處理速度慢的特點。(2)醫(yī)學應用圖像處理在醫(yī)學上有著廣泛的應用。其中最突出的臨床應用就是超聲、核磁共振、γ相機和CT等技術。在醫(yī)學領域利用圖像處理技術可以實現(xiàn)對疾病的直觀診斷和無痛、安全方便的診斷和治療，受到了廣大患者的歡迎。(3)安全領域利用圖像處理的模式識別等技術，可以利用在監(jiān)控、指紋檔案管理等安全領域中。目前有清華大學工程物理系開發(fā)研制的大型集裝箱檢測系統(tǒng)，就是利用圖像處理技術來實現(xiàn)全自動集裝箱檢測，從而加快了海關的工作效率，為打擊走私立下汗馬功勞。(4)工業(yè)生產(chǎn)產(chǎn)品的無損檢測也是圖像處理技術的一項廣泛應用?？傊瑘D像處理技術的應用是相當廣泛的它在國家安全、經(jīng)濟發(fā)展、日常生活中充當著越來越重要的角色，對國計民生有著不可忽略的作用[8]。表1-1圖像處理的應用領域學科應用物理、化學結晶分析、譜分析等生物、醫(yī)學細胞分析、染色體分類、X射線成像、CT等環(huán)境保護水質及大氣污染調查等地質資源勘測、地圖繪制、GIS等農業(yè)、林業(yè)農產(chǎn)物估產(chǎn)、植被分布調查等漁業(yè)魚群分布調查等氣象衛(wèi)星云圖分析等通信傳真、電視、多媒體通信等工業(yè)工業(yè)探傷、機器人、產(chǎn)品質量檢測等軍事導彈導航、軍事偵查等法律指紋識別等1.3圖像檢測技術發(fā)展現(xiàn)狀1.3.1圖像檢測技術發(fā)展歷史及現(xiàn)狀圖像檢測作為圖像分析技術的一個研究內容，它也是伴隨著數(shù)字圖像處理的發(fā)展而發(fā)展的。數(shù)字圖像處理這門學科的形成也是和社會生產(chǎn)力發(fā)展的需要分不開的。早期的圖像處理是由于通訊方面的要求而發(fā)展起來的，這就是本世紀20年代傳真技術的發(fā)明和發(fā)展。其后，則是由于宇宙方面的要求，需要處理大量的宇宙探測器上拍攝下來的不清楚的其他天體(如月球、火星等)以及地球本身的照片。然而，圖像處理技術的發(fā)展，遠遠突破了這兩個領域，到今天，它已經(jīng)廣泛的應用到科學研究、工農業(yè)生產(chǎn)、軍事技術、政府部門、醫(yī)療衛(wèi)生等許多領域，進一步推動著社會生產(chǎn)力的發(fā)展。圖像檢測是圖像分析研究內容的一部分。目前，在圖像分析領域已經(jīng)有很大的發(fā)展。圖像分析是一種從一幅圖像中通過自動的或半自動的方法提取圖像尺寸、數(shù)據(jù)或信息的方法。圖像分析方法通常因圖像分析系統(tǒng)最后的輸出是數(shù)字而不是畫面，使它與其他類型的圖像處理方法，如編碼、恢復、放大等不同。圖像分析源于經(jīng)典的模式識別方法，根據(jù)定義，分析系統(tǒng)并不局限于對一個固定數(shù)量類別的場景區(qū)域的分類，而是更傾向于可設計成用于描繪復雜場景。根據(jù)事先預測，該場景的種類可能是非常多的和不確定的。目前，圖像分析領域主要包括形態(tài)學圖像處理、邊緣檢測、圖像特征提取、圖像分割、形狀分析、圖像檢測和配準等幾個方面的內容：(1)形態(tài)學圖像處理：它的基本概念可以追朔到Mnikowski對空間集合代數(shù)的研究和Matheron對拓撲的研究。形態(tài)學圖像處理是這樣的一種處理類型，它對圖像中的物體的空間形態(tài)或結構進行修改。膨脹、腐蝕和骨架化是三種基本的形態(tài)學計算。(2)邊緣檢測：一幅圖像的振幅屬性(如亮度或三色值)的變化或突變是對圖像進行描述的重要特性，因為它們常指示圖像中物體的物理特性。從一個層面到另一個層面的圖像亮度的局部突變叫亮度邊緣。對于亮度圖像中的邊緣檢測、直線檢測和點檢測有兩類近似方法：微分檢測和模型擬合。(3)圖像特征提?。簣D像的特征是指圖像顯著的基本特征或特性。一些圖像是其本質的特性，在一定程度上這樣的特征可以從視覺上分辨出來，另一些則是通過某些變換產(chǎn)生的人為特征。本質特征包括像素區(qū)域和灰度紋理區(qū)域的亮度。(4)圖像分割：圖像分割法使圖像被劃分成或分隔成具有相近特征的區(qū)域。對于圖像分割法，其最基本的特征是:單色照片圖像的亮度振幅和彩色圖像的彩色因素。圖像邊緣和紋理也是對分割法很有用的特征。(5)形狀分析：目前已經(jīng)提出了幾種定性的和定量的方法來描述圖像中物體的形狀，這些方法對于在模式識別系統(tǒng)中對物體進行分類和在圖像理解系統(tǒng)中象征性的描述物體是很有用的。在這些方法中，有一些只能應用在二進制圖像中，另外的一些則可以被擴展到灰度圖像中。(6)圖像檢測和配準：圖像檢測主要是確定位于圖像內被猜測的物體是存在還是不存在的。而圖像配準主要是涉及到一對圖像區(qū)域的空間配準問題。在一個圖像區(qū)域中，物體檢測的一種最基本方法是通過模板匹配來進行。在目前的實際應用中，廣泛的利用Hough變換來進行圓形或橢圓性的物體檢測。1.3.2存在的問題本文主要是研究Hough變換在圓形物體檢測中的應用。在實際的圖像檢測和配準中，利用模板匹配是物體檢測的一種最基本的方法。在匹配過程中，把所關注的物體的拷貝和圖像區(qū)域中的所有的未知物體進行比較，如果模板和未知物體是匹配的，并且模板是足夠精確的，則未知物體被標識為模板物體。由于存在圖像噪聲、空間和振幅量化效應以及對于要檢測的物體的精確形狀和結構的預先不確定性，模板匹配很難保證精確性。分析物體檢測的整個過程，自然界中的一幅連續(xù)圖像對其數(shù)字化的描述，經(jīng)過圖像的增強、圖像的恢復后得到的數(shù)字圖像，要實現(xiàn)對其特定形狀圖形的檢測，還需要對二進制的圖像進行圖像分析，其中包括:形態(tài)學的處理，圖像分割、邊緣檢測、必要時還需要對其進行圖像彩色特征提取。經(jīng)過這些處理后才可進行圖像的檢測和配準。而每個處理過程涉及的算法都有一定的使用范圍和局限性，如何利用和有效組合每個處理過程中現(xiàn)有的成熟技術，一直是圖像檢測中的難點。檢測識別問題上的一個難點:假設現(xiàn)在有一個識別的問題，一幅圖像，其中包含了一些簡單的幾何形狀:矩形、圓等。任務就是編寫計算機程序，自動的識別這些形狀。還有一些影響識別的因素，是由圖像質量以及多義性引起的。比如噪音，在有意義的目標附近存在大量的干擾信息，當對圖像中的點進行梯度運算時，這些干擾信息會造成計算上的錯誤，這些都給識別帶來了很大的困難，同時這也是多義性產(chǎn)生的原因。即使是人來識別也會遇到這個問題:重疊覆蓋。檢測圖像多個目標的時候，一個目標覆蓋了另一個，使得另一個目標的信息不完整；交叉、目標與目標之間的交叉點是難于處理的。數(shù)字圖像處理過程中的經(jīng)典問題之一圓形檢測，有著廣泛的應用背景，也面臨著上述同樣的問題。研究者們提出了多種圓形檢測的方法，其中非常重要的一種:基于Hough變換的累積方法。圓的Hough變換(CHT)是目前應用最為廣泛的圓檢測方法，該方法的最大特點是可靠性高，在噪聲、變形大部分區(qū)域不完整的狀態(tài)下依然能取得理想的結果，但該方法的缺點是計算量大，資源需求大。所以如何減少算法的計算量和存儲量在近年得到了廣泛的重視，已提出了不少改進算法，如隨機Hough變換算法。但大多數(shù)的這些算法都是假設圖像在計算機中能用完美的模型來描繪原始圖像。然而，在現(xiàn)實生活中，由于噪音、數(shù)字化錯誤和圖形變異等因素影響，真實的圖形經(jīng)常被曲解。盡管輸入圖像是完整的，但圖像在計算機中很難用完美的模型來描繪)本文將針對此類問題，利用現(xiàn)有的關于圓圖形檢測理論和技術，結合模糊數(shù)學中的相關理論進行檢測[9]。1.4Hough變換簡介Hough變換是實現(xiàn)圖像邊緣檢測的一種有效方法，其基本思想是將測量空間的一點變換到參量空間中的一條曲線或一個曲面，而具有同一參量特征的點交換后在參量空間中相交，通過判斷交點處的積累程度來完成特征曲線的檢測，基于參量性質的不同，Hough變換可以檢測直線、圓、橢圓、雙曲線、拋物線等。同時，將概率論、模糊集理論、分層迭代的思想和級聯(lián)的方法應用于Hough變換的過程中，大大地提高了Hough變換的效率，改善了Hough變換的性能。1962年，PaulHough提出了Hough變換法[10]，并申請了專利。該方法將圖像空間中的檢測問題轉換到參數(shù)空間，通過在參數(shù)空間里進行簡單的累加統(tǒng)計完成檢測任務，用大多數(shù)邊界點滿足的某種參數(shù)形式來描述圖像的區(qū)域邊界曲線，因而對于被噪聲干擾或間斷區(qū)域邊界的圖像，Hough變換具有很好的容錯性和魯棒性。Hough變換法最初主要用于檢測圖像空間中的直線，最早的直線Hough變換是在兩個笛卡爾坐標系之間進行變換，這給檢測斜率為無窮大的直線帶來了困難。1972年，Duda將Hough變換法的變形形式進行了改變[11]，將數(shù)據(jù)空間中的點變換為ρ-θ參數(shù)空間的曲線，改善了其探測直線的性能。由于經(jīng)典的Hough變換法只能檢測圖像空間中的直線，為了能檢測到圖像空間中的曲線，在1978年Sklansky將Hough變換進行推廣，提出了推廣Hough變換法[12]來檢測圖像空間中的曲線。基于變換方程的不同，Hough變換法可以檢測出圖像空間中的圓、橢圓、拋物線、雙曲線等可以有解析式表達的曲線。但是經(jīng)典的Hough變換計算量比較大，在實際應用中很難實現(xiàn)。為了解決這個問題，40余年以來，許多學者致力于Hough變換算法的研究，將隨機過程、模糊理論等應用于Hough變換，并將分層迭代、級聯(lián)的思想引入到Hough變換的過程中，大大提高了Hough變換的效率[13]。1.5課題的研究內容在本次設計中，主要是在VC＋＋環(huán)境下對二值圖像中的圓進行檢測。本次課題主要進行算法的研究，用移動坐標的快速算法來進行檢測。在本論文中的主要工作如下：一、了解Hough變換的基本方法和圖像檢測的應用領域。二、掌握邊緣檢測與圖像分析的基本原理及方法，了解邊緣的種類和一般處理方法；采用Hough變換的一種快速算法對目標區(qū)域進行檢測。三、學習和掌握VisualC++編程方法，用VisualC++為開發(fā)工具完成數(shù)字圖像的基于Hough變換的圓檢測算法及可視化界面設計。1.6本章小結本章首先大概介紹了本次論文的背景，接著著重講解了數(shù)字圖像處理，引入了圖像檢測技術的發(fā)展現(xiàn)狀，并指出了圖像檢測技術存在的問題。然后，對Hough變換作了一個簡介，最后，講述了本次論文的研究內容。第二章Hough變換2.1Hough變換原理1962年，PaulHough根據(jù)數(shù)學對偶性原理提出了檢測圖像直線的方法，此后該方法被不斷地研究和發(fā)展[14-15]，主要應用于模式識別領域中對二值圖像進行直線檢測。其原理如圖2.1所示，平面直角坐標系中的直線L表達為:(2-1)其中，a為斜率，c為截距。據(jù)式(2-1)，直線L上不同的點(x,y)在參數(shù)空間中被變換為一族相交于P點的直線。顯然，若能確定參數(shù)空間中的P點（局部最大值），就實現(xiàn)了直線的檢測。平面中任意一條直線也可以用極坐標方程來表示，即可以用和兩個參數(shù)確定下來，對于圖像空間任意點,其函數(shù)關系為：(2-2)其中為原點到直線的距離（即原點到直線的垂直線的長度），確定了直線的方向（即原點到直線的垂直線與x軸方向的夾角）。如果對位于同一直線l上的n個點進行上述變換，則原圖像空間n個點在參數(shù)空間中對應地得到n條正弦曲線，并且這些曲線相交于同一點[16]。XX坐標Y坐標Hough變換截距斜率P圖2-1：直線檢測中的Hough變換由上述Hough變換原理可知，Hough變換具有如下性質：(1)直角坐標系中的一個點映射到參數(shù)空間中為一條直線；(2)參數(shù)空間中的一個點對應直角坐標系中的一條直線；(3)直角坐標系中的共點線映射到參數(shù)空間中為一條直線；(4)直角坐標系中的共線點映射到參數(shù)空間中后為一個交于同一點的直線簇。2.2Hough變換實現(xiàn)方法工程中的實驗數(shù)據(jù)和圖像處理中的二值邊緣圖，通常都是離散數(shù)據(jù)，因此，根據(jù)Hough變換性質，可按下列步驟實現(xiàn)Hough變換[17-18]：(1)將參數(shù)空間量化成(為的等份數(shù)，為的等份數(shù))個單元，并設置累加器矩陣；(2)給參數(shù)空間中的每個單元分配一個累加器,并把累加器的初始值置為零；(3)取出直角坐標系中的點代入式(2-2)，并以量化的值計算出；(4)在參數(shù)空間中，找到和所對應得單元，并將該單元的累加器加1，即；(5)當直角坐標系中的點都經(jīng)過(3)(4)兩步遍歷后，檢驗參數(shù)空間中每個累加器的值，累加器最大的單元所對應的和即為直角坐標系中的直線方程式(2-1)的參數(shù)。當直角坐標系中的點分布在R條直線附近時，可在第5步檢測累加器時，取出累加器中前R個值最大的單元所對應的和，以和為直角坐標系中直線方程式(2-2)的參數(shù)，即可同時實現(xiàn)多條直線的檢測。2.3Hough變換的研究現(xiàn)狀2.3.1Hough變換的研究現(xiàn)狀Hough變換最初只用于從圖像中識別圖形邊界，經(jīng)過幾十年的發(fā)展，Hough變換現(xiàn)在已經(jīng)用于各個方面的圖像處理，包括辦公文檔圖像處理、多普勒-時間圖像處理、航空圖像自動判斷等。隨著科學技術的發(fā)展，Hough變換在軍事和民用領域將會得到廣泛的應用。1994年，Carlson等人將Hough變換法應用到搜索雷達中檢測直線運動或近似直線運動的低可觀測目標。1996年，JiChen等人將Hough變換法應用于航跡起始中。除此之外，在國防科技領域，Hough變換還廣泛用于低可觀測信號檢測、聲納信號處理、雷達目標跟蹤、ESM目標跟蹤、紅外目標跟蹤、多傳感器多目標跟蹤、多傳感器信息融合等方面。圓形檢測是數(shù)字圖像處理過程中的經(jīng)典問題之一，有著廣泛的應用背景，研究者們提出了多種圓形檢測的辦法，基于Hough變換的累積方法是其中非常重要的一種方法。圓的Hough變換（CHT）是目前應用最為廣泛的圓檢測方法，該方法最大特點是可靠性高，目前已經(jīng)提出了多種基于Hough變換的圓的檢測算法，其中的一些算法在繼承Hough變換優(yōu)勢的同時，也對Hough變換過程中存在的計算量大、資源需求大等缺點進行了很好的改進，如隨機Hough變換算法。同時，Hough變換的測量數(shù)據(jù)的預處理、參數(shù)空間的離散化、門限的選擇、平均虛警概率的問題都得到了解決，如集束算法、基于邏輯的檢測方法、數(shù)據(jù)的融合等方法。2.3.2Hough變換研究存在的問題和解決方法（1）解決計算量大的問題為了解決參數(shù)空間維數(shù)過高，計算量大的問題，幾十年來，人們一直在致力于這方面的研究，以期對Hough變換方法進行多種修正和改進。例如可以利用圖像的梯度方向信息；運用隨機Hough變換的思想，用一個圖像空間點集的一個有限子集來代替該點集；利用級聯(lián)或分層迭代的方法等等，進行變換后同樣可以得到很好的結果。在實現(xiàn)過程，還可以將整個Hough變換分為幾步，這樣就可以將每一步的輸出放在一個一維累加器中，根據(jù)需要加入新的判別信息，且每一步都可以選擇待研究曲線最適合的特性。將變換結果和原圖像聯(lián)系起來，選擇Hough變換直方圖中的峰值點。只有這些峰值點才能進行下一步的Hough變換。這樣也能大大減少操作步驟，并加強了峰值點，同時避免了在多維空間中搜尋目標的困難。（2）測量數(shù)據(jù)的預處理為了降低數(shù)據(jù)處理負擔，可以利用固定雜波在數(shù)據(jù)圖像平面上具有的特點剔除固定雜波。在斜距-時間平面上，固定雜波或慢速運動目標呈現(xiàn)為跟斜距坐標平行的直線，而需要關心的具有正常運動速度的目標在該平面上呈現(xiàn)為具有一定斜率的直線。利用上述特點，可以對測量數(shù)據(jù)進行預處理，剔除掉這些特殊雜波。（3）參數(shù)空間離散化在實際應用中，由于測量噪聲的影響，使圖像空間上的一條直線在映射到參數(shù)空間后不能相交于一點，因此，要對平面進行分割，以通過直方圖的方法進行檢測。具體方法是，將平面離散分割成若干個小方格，通過檢測3D直方圖中的峰值判斷公共的交點。當X-Y平面上存在有可連成直線的若干點時，這些點就會聚集在平面相應的方格內。經(jīng)過多次掃描之后，對于直線運動的目標，在摸一個特定單元中的點的數(shù)量會得到積累。（4）門限的選擇Hough變換的信號檢測性能與第一門限和第二門限有關。當?shù)谝婚T限設置比較低時，會有很多的噪聲點通過第一門限，此時第二門限的設置應該比較高，這樣才能有效地剔除由于噪聲點產(chǎn)生的峰值。當?shù)谝婚T限設置比較高時，大多數(shù)噪聲點均能被排除掉，此時第二門限的設置就不能太高，如果太高的話，將很可能檢測不到目標的峰值。第一門限可以通過數(shù)據(jù)平面上每一個方格中的信號強度來得到。在雷達信號檢測中，可以通過斜距-時間平面上每一個方格中的虛警概率得到第一門限。通過第一門限的點可以經(jīng)Hough變換法轉換到參數(shù)空間，在參數(shù)空間中設置第二門限。（5）平均虛警概率在雷達信號檢測性能的分析中，針對單個單元確知目標而言，虛警概率采用了平均虛警概率，即將整個可達Hough空間的虛警概率除以可達Hough單元總數(shù)。但在實際應用中，不知道目標具體在哪一個Hough單元，也不知道目標的數(shù)目，因此實際的虛警概率應該采用整個可達Hough參數(shù)空間的積累虛警概率。而當實際的虛警概率相當高的時候，仿真所需要的次數(shù)太大以至于實現(xiàn)起來很困難。為了降低實際檢測中的虛警概率，可以采用下列方法：集束算法；基于邏輯的監(jiān)測方法；數(shù)據(jù)融合的方法等。2.4Hough變換的應用領域經(jīng)典Hough變換的計算量大，在實際應用中很難實現(xiàn)。40年來，許多學者將隨機過程、模糊集理論、分層迭代的思想和級聯(lián)的方法應用于Hough變換中，就形成了隨機Hough變換、模糊Hough變換、分層迭代Hough變換、級聯(lián)Hough變換和三維Hough變換，這使的Hough變換的應用越來越廣泛，例如將Hough變換應用在圖像處理，信號檢測等方面。2.4.1Hough變換在圖像處理中的應用Hough變換最初是作為圖像處理的方法提出來的。Hough變換的一個突出的有點是抗干擾能力強。如果待檢測的曲線上有小的擾動或斷裂，或者存在背景噪聲，算法都能準確的檢測出曲線。甚至對于直線，經(jīng)Hough變換后，在變換空間中仍然能夠得到明顯的峰值點。所以，Hough變換在圖像處理中應用的非常廣泛。Hough變換在圖像處理中的應用主要是對圖像中特定形狀的識別和檢測。它具體可以用來對圖形進行識別，提取圖像拐點，SAR圖像處理，傾斜文本圖像校正和檢測，多普勒-時間圖像處理以及航空圖像自動判讀等等。采用Hough變換進行形狀特征提取，可對形狀進行有效的識別，可并行實現(xiàn)，而且對噪聲不敏感，所提取的特征不受待識別形狀大小及所在圖像中的位置的影響。但由于Hough變換必須逐點處理圖像平面上的每一點，計算量大，內存開銷較大，特別是對于圖像幅面大，前景復雜的圖形時尤其明顯。對圖像進行濾波和邊緣檢測雖然能夠加快處理速度，但識別精度會受到不同成都的影響。2.4.2Hough變換在信號檢測中的應用基于Hough變換的信號檢測方法既可以用于低可觀測信號的檢測，也能用于強雜波環(huán)境下的多目標跟蹤。通過Hough變換，可以把可能是同一個航跡的回撥能量進行非相干積累。由于非相參積累的作用，低可觀測目標的能量得以積累，增強了低可觀測目標的信噪比，從而可以對低可觀測目標進行檢測。利用Hough變換對信號進行檢測主要有兩種方法：一是基于Hough變換的非相干積累法，二是基于Hough變換的二值積累法。其中，Hough變換的非相參積累方式對低可探測目標的檢測性能有一定的改善，由于它不需要對目標進行回掃即可進行檢測前跟蹤，因此在強雜波環(huán)境下基于Hough變換的檢測是常規(guī)檢測手段的一種有益的補充。2.4.3Hough變換在雷達目標跟蹤中的應用航跡起始是航跡處理中的首要問題，但同航跡處理中的跟蹤維持的研究相比，航跡處理中的航跡起始算法比航跡處理中的航跡維持算法更為復雜。現(xiàn)有的航跡起始算法可分為順序處理技術和批數(shù)據(jù)處理技術兩大類。通常，順序數(shù)據(jù)處理技術適用于相對無雜波環(huán)境中的航跡起始，主要包括啟發(fā)式規(guī)則方法和基于邏輯的方法。批數(shù)據(jù)處理技術適用于雜波環(huán)境，主要包括Hough變換法和修正的Hough變換法等。Hough變換還可以應用到三維空間中的航跡起始。由于Hough變換只適用于起始二維平面中的目標航跡，因此在實際工程中，可以根據(jù)實際的需要選擇投影面，然后在利用基于Hough變換和邏輯的起始算法，并將各個平面起始的航跡進行比較和關聯(lián)起始三維空間中的航跡。而且通過在密集雜波環(huán)境下的航跡起始仿真驗證了該方法特別適用于在密集雜波環(huán)境中快速起始三維空間中的軌跡。2.4.4Hough變換在多傳感器多目標跟蹤中的應用利用多傳感器獲取數(shù)據(jù)來進行多目標跟蹤的技術在許多軍事和民用領域得到了廣泛的應用。從本質上講，多傳感器多目標跟蹤系統(tǒng)成功的關鍵都在于數(shù)據(jù)關聯(lián)算法的有效性。在一般情況下，數(shù)據(jù)關聯(lián)問題可以分解為兩項單獨的任務：用于航跡其實起始的測量-測量關聯(lián)和用于航跡維持的測量-測量關聯(lián)。而Hough變換特征檢測方法是可以用作實現(xiàn)目標航跡起始的一種有效方法，通過將前幾次搜索掃描所感知的數(shù)據(jù)組合成多維數(shù)據(jù)矢量，可以用Hough變換從復合數(shù)據(jù)中檢測出軌跡。文獻[19-20]對Carlson等人的工作進行了拓展，并提出了可用于在雜波環(huán)境中緝拿測兵起始多目標航跡的基于Hough變換的多傳感器數(shù)據(jù)關聯(lián)方法?；贖ough變換的多傳感器，多目標航跡起始方法的最大優(yōu)勢在于其對多傳感器結構的適應能力，因為在所有仿真中，多傳感器結構的性能總是優(yōu)于單傳感器結構的性能。而且雜波不會顯著影響航跡起始性能，但可以看到雜波密度的增加會引起虛假航跡起始率的上升。2.5本章小結本章首先講述了Hough變換的原理和實現(xiàn)方法，并簡單介紹了其研究現(xiàn)狀和存在的問題，接著介紹了Hough變換的應用領域。Hough變換是一種用來在邊緣增強處理后的圖像中，提取邊緣特征的簡便而有效的方法，它能夠提取直線、圓、橢圓、二次曲線甚至是任意形狀的邊緣。Hough變換在計算機視覺、軍事防御、辦公自動化等領域都得到了普遍的關注和廣泛的應用。Hough變換1962年由PaulHough提出，并在美國作為專利。它所實現(xiàn)的是一種從圖像空間到參數(shù)空間的映射關系。Hough變換的實質是將圖像空間內具有一定關系的象元進行聚類，尋找能把這些象元用某一解析形式聯(lián)系起來的參數(shù)空間累積對應點。經(jīng)過幾十年的發(fā)展，Hough變換現(xiàn)在已經(jīng)用于各個方面的圖像處理，包括SAR/ISAR圖像處理、辦公文檔圖像處理、多普勒-時間圖像處理、航空圖像自動判讀等。隨著科學技術的發(fā)展，Hough變換在軍事和民用領域得到了廣泛的應用。比如在國防科技領域，Hough變換被用于低可觀測信號檢測、聲納信號處理、雷達目標跟蹤、ESM目標跟蹤、紅外目標跟蹤、多傳感器多目標跟蹤、多傳感器信息融合等方面。在民用領域，Hough變換在水聲目標形狀分析、人臉圖像識別、地下目標檢測、車輛識別、目標平移和旋轉運動分析等方面發(fā)揮著巨大的作用。總之，Hough變換的作用已被世界各國所認識，顯示出了巨大的應用價值和重要的應用前景。第三章Hough變換圓檢測算法3.1Hough變換圓檢測原理和性能分析3.1.1Hough變換圓檢測原理Hough變換常常被用于直線段、圓和橢圓的檢測。其基本思想是將圖像的空間域變換到參數(shù)空間，用大多數(shù)邊界點滿足的某種參數(shù)形式來描述圖像中的曲線(區(qū)域邊界)。通過設置累加器進行累加，求得峰值對應的點就是所需要的信息。下面我們介紹一下經(jīng)典的圓檢測Hough變換。假設希望在圖像平面(X-Y平面)考察并確定一個圓周。令為圖像中欲確定圓周上的點的集合，而為集合中的一點，它在參數(shù)坐標系中方程為:（3-1）顯然該方程為三維錐面，對于圖像中任意確定的一點均有參數(shù)空間的一個三維的錐面與之對應。對于圓周上的任何點集合，這些三維錐面構成圓錐面簇。圖3-1：圓的Hough變換原理若集合中的點在同一個圓周上，則這些圓錐簇相交于參數(shù)空間上某一點，這點恰好對應于圖像平面的圓心坐標及圓的半徑。對于離散圖像，式(3-1)可寫為:(3-2)其中ξ是考慮到對圖像進行數(shù)字化和量化的補償。Hough變換的基本思想在于證據(jù)積累，一般情況下圓變換的參數(shù)空間為三維的，在三維積累空間上進行證據(jù)累加的時間空間消耗是非常大的，在具體應用中幾乎是不可能的，不現(xiàn)實的。3.1.2Hough變換圓檢測性能分析由以上分析可以看出，影響常規(guī)Hough變換運算速度的主要因素有:邊緣點的數(shù)量，參數(shù)空間維數(shù)，參數(shù)空間的離散化程度，運算的復雜性，以及最后的峰值檢測。對于半徑為，圓心坐標為的圓在參數(shù)空間的表示為:(3-3)顯然，上式表示的是一個三維錐面，它的物理意義是，圖像空間中的圓對應著參數(shù)空間的一個點，而圖像空間中的一個點對應著參數(shù)空間中的一個三維圓錐。對于圖像空間中的一個圓其半徑是固定不變的，圓周上的各個點組成的集合在參數(shù)空間就表現(xiàn)為相等而、不等的各個圓錐的集合。圖像空間中圓上的點映射到參數(shù)空間的一簇圓錐的交點正好對應于圓心坐標和半徑。對于參數(shù)空間適當量化，得到一個三維的累加列陣，用來記錄，當檢測圖像空間中的圓時，計算與邊緣上的每一個像素距離r的所有，同時在對應的列陣中累加，當對全部邊緣點變換完成后，對三維列陣中的所有累加值進行檢驗，其中的峰值就對應圖像空間中的圓心。由于圖像是離散的，對(3-3)式的判別可改寫為:(3-4)對于邊緣上的每一點，給定半徑，那么對、的變化各需要計算次上式，同時排除已經(jīng)計算過的重復點，因而總共需要計算次左右。假設每次耗時，那么對于一個邊緣點需耗時，再假設半徑的變化范圍為，則每個邊緣點耗時為:(3-5)假設有N個邊緣點，則總耗時即為，本系統(tǒng)所涉及到的圖像，N通常在2000以上，那么總耗時中t的系數(shù)就是10的6次方以上，這個計算量是相當大的。顯然，單就這一環(huán)節(jié)，就需要耗費大量的運行時間和存儲空間，因而，對于常規(guī)Hough變換的改進要求是非常之迫切的。雖然常規(guī)Hough變換有明顯的缺憾，但是由于它完全按照Hough變換的定義進行，所以通常用來作為改進算法的參照對象。3.2經(jīng)典Hough變換圓檢測算法Hough變換的基本思想在于證據(jù)積累，一般情況下圓變換的參數(shù)空間為三維的，需要在參數(shù)空間建立一個三維的累加數(shù)組,根據(jù)具體的圖像數(shù)據(jù)點計算出的每一個三元組，對累加，其具體變換過程如下：(1)在、、合適的最大值和最小值之間建立一個零散的參數(shù)空間；(2)建立一個累加器,并置每一個元素為0；(3)對圖像空間中超過門限值的每一點作Hough變換，即算出該點在三維網(wǎng)格上的對應曲線，并在相應的累加器加1：(3-6)(4)找出對應圖像平面共圓周點累加器上的局部最大值，這個值就提供了圖像平面上共圓周點的圓心以及半徑參數(shù)。由于Hough變換的實質是將圖像空間的具有一定關系的像元進行聚類，尋找能把這些像元用某一解析形式聯(lián)系起來的參數(shù)空間累積對應點。在參數(shù)空間不超過二維的情況下，這種變換有著很理想的效果。然而，當參數(shù)空間超過二維時，這種變換的時間消耗和所需存儲空間的急劇增大使得這種變換僅僅在理論分析上可行，而在實際應用中幾乎是不可能實現(xiàn)的。這時往往需要從具體的應用情況中尋找特點，如利用被處理圖像像元的灰度的變化值確定灰度的變化方向來降低參數(shù)空間維數(shù)，或利用一些對于被檢測圖像的先驗知識來設法降低變換過程的時間和空間的開銷。在參數(shù)空間中，將設為遞增變量，每一步迭代都先固定，在垂直于的平面上求對應于圓心為的圓周各點，并將軌跡上的點在與此平面映像的一個三維累加數(shù)組上的相應點上累加。從0開始遞增直到圖像平面所能容納的上限（一般可根據(jù)先驗知識來確定r的可能變換范圍來減少計算量），每次遞增均有一平面映像與之對應。因此，對于圖像上每一確定點,和的變化范圍均為。求出在此范圍內對應的每一和的坐標，即要計算式（3-2）次。設每次這種計算耗時為，則對應的每一步進的得計算耗時為。若設的步進范圍為，則對應于每個像元的計算量為：（3-7）若對圖像平面上的若干個點進行Hough變換，則總耗時將為。而用于累加陣列的存儲空間約為字節(jié)（設,分別為圖像的高度和寬度，累積單元采用單字節(jié)）?？梢姡陨线\算的時空開銷是很大的。當全部點轉換完成后，對累加數(shù)組每個元素的值進行比較，有較大值得數(shù)組元素對應于圓或圓弧，其參數(shù)可作為圓的擬合參數(shù)，而具有較小值得元素則舍棄。如圖3-2所示,從圖像空間中取八個圓的邊緣像素點A、B、C、D、E、F、G、H,以R為半徑將這八個點映射到參數(shù)空間?？梢钥吹?這八個點在參數(shù)空間中的投影均在O點相交,也即O點的累加值在參數(shù)空間中是最大的。同時,O點也是圖像空間中圓的圓心。此時,圖像空間中每一邊緣點映射到參數(shù)空間得到的投影為一個圓。圖3-2：圖像空間及邊緣點在參數(shù)空間的投影3.3一種快速的Hough變換圓檢測算法在一些實時處理系統(tǒng)中,識別速度是關鍵性能的指標之一。在Hough變換原理的啟發(fā)下,本章提出了一種改進的用Hough變換檢測圓的方法,大大減少了計算量,提高了目標識別速度。3.3.1快速Hough變換圓檢測算法基本思想經(jīng)典的Hough變換在圖像中尋找半徑已知的圓的圓心時,對整個圖像進行遍歷,尋找邊緣點需要兩重循環(huán)。遍歷到每個邊緣點時,求其在參數(shù)空間中的投影集合需要兩重循環(huán)。所以經(jīng)典的Hough變換在檢測半徑已知圓時需要四重循環(huán),這在實際計算中是極其耗時的。當遍歷到圖像中的邊緣點時,先求出邊緣點映射到參數(shù)空間得到的坐標點集合,然后對集合中每個坐標點元素對應的累加值進行一次累加,此點在參數(shù)空間中的投影為坐標點集合(設圖像中邊緣點的數(shù)目為N個,則n的取值范圍為[1,N])。將圖像放到坐標系中考慮時,由坐標平移的知識可以知道,當一個圓的圓心由點平移到點時,圓上任意一點的坐標就由變?yōu)椤＿@樣,圖像中每個邊緣點在參數(shù)空間中投影得到的坐標點集合就不需要通過計算得出,只需先求出一個基準點在參數(shù)空間中的投影,投影得到的坐標點集合為,其余的邊緣點在參數(shù)空間中的投影就可以通過將基準點在參數(shù)空間的投影即坐標點集合平移得到。這樣處理有如下優(yōu)點:在參數(shù)空間中減少參與運算的點,并且通過平移在參數(shù)空間得到的坐標點集合與通過計算在參數(shù)空間得到的坐標點集合基本相等。對任意一邊緣點,經(jīng)典Hough變換需要在參數(shù)空間中對以邊緣點為中心,2R為邊長的正方形內所有像素點進行計算,判斷是否是邊緣點映射到參數(shù)空間得到的坐標點集合中的元素,一共需要計算個像素點。改進的算法只需在參數(shù)空間中移動N個點(N為正方形內滿足圓的方程的像素點個數(shù))。由于正方形內的像素點不可能全部是邊緣點映射到參數(shù)空間得到的坐標點集合中的元素,必有。3.3.2快速Hough變換圓檢測算法新的快速算法是通過將基準點在參數(shù)空間中的投影集合平移來得到其他邊緣點在參數(shù)空間的投影集合,所以與經(jīng)典Hough變換算法相比,新的快速算法需要一塊額外的內存區(qū)域用于保存基準點在參數(shù)空間的投影集合。但新的快速算法與經(jīng)典算法相比耗時減少了很多。新的快速算法的基本步驟如下:a)在原始圖像中取一個基準點,以此點為圓心、為外半徑、為內半徑求在參數(shù)空間的投影,得到坐標點集合,將所得到的坐標點集合保存在一塊內存區(qū)域baseunion中。b)對圖像進行遍歷,當遇到第一個邊緣點時,將baseunion中保存的集合中所有元素即所有坐標點的坐標分別加上x、y方向的偏移量、,得到一個新的坐標點集合F1,然后在參數(shù)空間中將集合F1中所有坐標點元素對應的累加值進行累加。c)重復b),計算Fn(N≥n≥2),并將Fn中所有坐標點元素對應的累加值進行累加,直到所有邊緣點均被遍歷到并計算過。d)找出參數(shù)空間中累加值的極大值,累加值極大值在參數(shù)空間中所對應的坐標便是圓在圖像空間中的圓心坐標。3.3.3快速Hough變換圓檢測計算量分析在經(jīng)典Hough變換中:a)確定圖像中參與運算的邊緣點個數(shù)為(M、N、R、α分別為圖像的高度、寬度、圓的半徑、圖像分割后邊緣點個數(shù)占整個圖像中像素點的比例)。b)求某個邊緣點映射到參數(shù)空間得到的坐標點集合時,在參數(shù)空間中需要進行計算的區(qū)域大小為。c)確定參數(shù)空間中需要計算的區(qū)域中的某個像素點是否是邊緣點在參數(shù)空間中投影得到的坐標點集合中的元素,若是集合中的元素,則對坐標點元素對應的累加值累加,此處需要次乘法運算和次加法運算(由于減法運算和加法運算需要的時鐘周期一樣,此處兩次減法運算算做兩次加法運算。β、χ分別為滿足第一個圓環(huán)判定條件的像素點個數(shù)占參數(shù)空間中需要計算的區(qū)域中的像素點個數(shù)的比例,滿足兩個圓環(huán)判定條件的像素點個數(shù)占參數(shù)空間中需要計算的區(qū)域中的像素點個數(shù)的比例)。這樣經(jīng)典Hough變換主要的計算部分需要次乘法運算,需要的加法運算次數(shù)為次。新的快速算法:a)確定圖像中參與運算的邊緣點個數(shù)為；b)在參數(shù)空間中將集合平移得到新的坐標點集合Fn,并對新集合Fn中所有坐標點元素對應的累加值進行累加。計算平移后的坐標需要次加法運算(由于χ為滿足兩個圓環(huán)判定條件的像素點個數(shù)占參數(shù)空間中需要計算的區(qū)域中的像素點個數(shù)的比例,集合中的元素個數(shù)為個),計算累加器所在的位置并進行累加需要次乘法運算和次加法運算。綜上所述，快速算法的主要計算部分為次乘法運算和次加法運算。對圓環(huán)來說,第一判定條件為空間中的點是否在圓環(huán)內或圓環(huán)外,可通過面積來近似考慮,得到,即可近似認為等于。滿足兩個圓環(huán)判定條件的像素點在圓環(huán)內,在實現(xiàn)中,由于設圓環(huán)外圓比內圓大兩個像素,通過面積來近似考慮時,得到,即χ可近似認為。由此，經(jīng)典Hough變換需要次加法運算，而新的快速算法需要次加法運算,則我們得到新的快速算法相對經(jīng)典算法提高了約倍[21]。3.4本章小結本章首先講述了經(jīng)典Hough變換圓檢測的原理及其性能，算法等，接著引出了一種新的快速Hough變換圓檢測算法，并具體分析了新的快速算法的思想和計算量。通過比較，我們可以發(fā)現(xiàn)新的快速Hough變換圓檢測算法明顯比經(jīng)典算法快了很多，提高了約六倍，顯著的提高了Hough變換圓檢測的速度，同時它也保持了經(jīng)典Hough變換的所有優(yōu)點。第四章Hough變換圓檢測圖像處理4.1引言一般的圖像處理中的圖像都是彩色的，而且還有背景。在圖像處理過程中我們必須先將彩色圖像經(jīng)過灰度變換、邊緣檢測和二值化后再進行檢測；同時，在檢測時還有可能會受到噪聲、雜波等外界環(huán)境的影響。常規(guī)做法是先去除背景、雜波和噪聲等外界影響，然后再進行檢測。在本文中我們只是對最簡單的二值圖像進行檢測，這是基于最基本的圖像處理，在實際應用中往往是彩色圖像。在本次實驗中，使用的編程語言為VisualC++6.0，運行環(huán)境為WindowsXP。VisualC++是目前使用最為廣泛的C++工具，VisualC++提供了一個集源程序編輯、代碼編譯與調試于一體的開發(fā)環(huán)境，這個環(huán)境稱為集成開發(fā)環(huán)境，對于集成開發(fā)環(huán)境的熟悉程度直接影響程序設計的效率。利用C++可以完成各種各樣的應用程序的開發(fā)，從底層軟件直到上層直接面向用戶的軟件。而且VisualC++強大的調試功能也為大型復雜軟件的開發(fā)提供了有效的排錯手段。VisualC++是一個很好的可視化編程工具，使用VisualC++環(huán)境來開發(fā)Windows應用程序大大縮短了開發(fā)時間，而且它的界面更友好，便于程序員操作[22]。4.2實驗結果與分析本文在經(jīng)典Hough變換的基礎上研究了一種新的快速Hough變換圓檢測算法，處理的速度明顯比經(jīng)典算法快很多，同時有一定的抗噪聲性能，但是這種算法還是需要很大的存儲空間。圖4-1，圖4-2是對沒有噪聲影響的二值圖像的檢測結果。原圖像檢測到的圓心檢測到的圓檢測到的圓心坐標圖4-1：第一幅圖實驗結果原圖像檢測到的圓心檢測結果圖像檢測到的圓心坐標圖4-2：第二幅圖實驗結果從上面兩幅圖的檢測結果可以看出，這種快速算法能很好的檢測出標準的圓形，對非規(guī)則的圓形也有一定的檢測能力。同時，這種快速算法解決了經(jīng)典Hough變換運算量大的問題。通過比較我們可以發(fā)現(xiàn)，快速算法的運算量相比于經(jīng)典算法提高了約6R/5π倍。為了檢測快速Hough變換算法的抗噪聲性能，我們對上面的第二幅圖加上了方差分別為0.1和0.2的高斯噪聲，比較了兩幅圖像的實驗結果。實驗處理結果如圖4-3和圖4-4所示。加上方差為0.1的高斯噪聲后的圖像檢測到的圓心檢測到的圓檢測到的圓心坐標圖4-3：加上方差為0.1的噪聲的處理結果加上方差為0.2的高斯噪聲后的圖像檢測到的圓心檢測到的圓檢測到的圓心圖4-4：加上方差為0.2的高斯噪聲的處理結果從上述兩幅圖片的處理結果中，我們可以看到這種快速算法有一定的抗噪聲性能，但效果不是很理想。當給圖片加上了方差為0.1的噪聲后，檢測的結果比沒加噪聲的要差一點，檢測結果有點失真；然后給圖片加上方差為0.2的噪聲，其檢測出來的結果沒有前一幅好，有些圓都沒有檢測出來。由此可見，快速Hough變換算法的抗噪聲性能不是很理想，在檢測過程中很容易受外界條件的影響。綜上所述，快速Hough變換算法減少了Hough變換的計算量，有一定的抗噪聲性能，但效果不是很理想，同時還沒能解決存儲空間大的問題。4.3本章小結由于經(jīng)典的Hough變換計算量很大，而且需要很大的存儲空間，使得在實際應用中很難實現(xiàn)。在本文中采用了一種新的快速Hough變換圓檢測算法，這種算法大大提高了檢測速度，取得了較好的效果。但是這種算法并沒有解決經(jīng)典算法需要很大的存儲空間的問題，它的抗噪聲性能也有待于進一步加強。第五章結束語圖像是對客觀存在的一種相似性生動模仿，是用各種觀測系統(tǒng)以不同形式和手段觀測客觀世界而獲得的，可以直接或間接作用于人眼而產(chǎn)生視知覺的實體。圖像處理是人類視覺延伸的重要手段，可以使人們看到任意波長上所測得的圖像。圖像檢測作為圖像分析技術的一個研究內容，它也是伴隨著數(shù)字圖像處理的發(fā)展而發(fā)展的。圖像檢測是圖像分析研究內容的一部分。目前，在圖像分析領域己經(jīng)有很大的發(fā)展。圖像分析是一種從一幅圖像中通過自動的或半自動的方法提取圖像尺寸、數(shù)據(jù)或信息的方法。本文主要是研究Hough變換圓檢測的算法，本文的主要工作是：首先介紹了數(shù)字圖像處理的發(fā)展。應用以及內容，同時也介紹了圖像檢測技術的發(fā)展歷史、現(xiàn)狀和存在的問題；然后概述了本課題研究的意義和研究內容。圖像檢測作為圖像分析技術的一個研究內容，它也是伴隨著數(shù)字圖像處理的發(fā)展而發(fā)展的。圖像檢測是圖像分析研究內容的一部分。目前，在圖像分析領域己經(jīng)有很大的發(fā)展。圖像分析是一種從一幅圖像中通過自動的或半自動的方法提取圖像尺寸、數(shù)據(jù)或信息的方法。目前，圖像分析領域主要包括形態(tài)學圖像處理、邊緣檢測、圖像特征提取、圖像分割、形狀分析、圖像檢測和配準幾個方面理論的內容。其次，介紹了經(jīng)典的Hough變換圓檢測算法和一種新的快速算法，并分析了它們的計算量。新的Hough變換圓檢測的快速算法是用移動的坐標來實現(xiàn)的。首先我們先在原始圖像中取一基準點,以此點為圓心、Rmax為外半徑、Rmin為內半徑求在參數(shù)空間的投影,得到坐標點集合,將所得到的坐標點集合保存在一塊內存區(qū)域中，然后對圖像進行遍歷，包括邊緣點，從而完成對圓得檢測。通過比較，我們發(fā)現(xiàn)新的快速算法減