直線檢測(cè)技術(shù)畢業(yè)設(shè)計(jì)

1、<p><b>　　摘要</b></p><p>　　直線檢測(cè)是計(jì)算機(jī)視覺和模式識(shí)別中最重要的任務(wù)之一。直線是圖像的重要特征，直線特征提取方法的研究對(duì)圖像的理解、模式識(shí)別有重要的意義。文章首先介紹了直線檢測(cè)的研究狀態(tài)，并對(duì)比了當(dāng)前幾種主流的直線檢測(cè)方法。然后針對(duì)具有經(jīng)典意義的基于Hough變換的直線檢測(cè)進(jìn)行了詳細(xì)的說明，并介紹了其幾種改進(jìn)算法。最后，編寫了一款基于Hough直線檢測(cè)

2、和對(duì)比的軟件方便讀者更加深刻的理解Hough算法。</p><p>　　關(guān)鍵詞：直線檢測(cè)，Hough變換</p><p><b>　　Abstract</b></p><p>　　Line detection has become one of the most important tasks in computer vision and pa

3、ttern recognition. The research of the algorithm of extracting straight lines is meaningful to the understanding and recognition of a graph because the line is the major character to a graph. In the paper, it shows the t

4、rend and method in line detection in this situation, and it tell us the details how to design the Hough transform then it achieves and contrasts some line detection which are based on the Hough tr</p><p>　　

5、Keyword: Line detection, Hough transform</p><p><b>　　目錄</b></p><p><b>　　第1章 引言1</b></p><p>　　1.1 圖像工程與直線檢測(cè)1</p><p>　　1.2 圖像檢測(cè)技術(shù)發(fā)展歷史及現(xiàn)狀1</p

6、><p>　　1.3 課題的難點(diǎn)3</p><p>　　第2章 直線檢測(cè)算法4</p><p>　　2.1 Hough直線檢測(cè)算法4</p><p>　　2.2 Freeman直線檢測(cè)算法5</p><p>　　2.3 尺蠖蠕行算法9</p><p>　　2.3.1 尺蠖蠕行的過程和環(huán)境

7、10</p><p>　　2.3.2 基本原理11</p><p>　　第3章 Hough算法的改進(jìn)和實(shí)現(xiàn)13</p><p>　　3.1 編程環(huán)境的搭建13</p><p>　　3.1.1 OpenCV13</p><p>　　3.1.2 Microsoft Visual Studio13</p>

8、;<p>　　3.1.3 環(huán)境搭建14</p><p>　　3.2 Hough算法的改進(jìn)16</p><p>　　3.2.1 Randomized Hough Transform(RHT)16</p><p>　　3.2.2 RHT-LSM17</p><p>　　3.2.3 PCA-HT18</p>&

9、lt;p>　　3.3 經(jīng)典Hough算法的實(shí)現(xiàn)20</p><p>　　3.3.1 獲取圖片類（GetBMP）23</p><p>　　3.3.2 獲得直線類（GetLine）28</p><p>　　3.3.3 圖像輸出類（OutputBMP）32</p><p>　　3.4 軟件效果展示36</p><

10、p>　　3.4.1 軟件結(jié)果展示36</p><p>　　3.4.2 直線檢測(cè)效果36</p><p>　　3.5 經(jīng)典Hough算法的性能39</p><p>　　第4章 結(jié)束語42</p><p><b>　　參考文獻(xiàn)43</b></p><p><b>　　致謝4

11、4</b></p><p><b>　　外文資料原文46</b></p><p><b>　　外文資料譯文49</b></p><p><b>　　第1章 引言</b></p><p>　　1.1 圖像工程與直線檢測(cè)</p><p>　　

12、圖像工程將圖像技術(shù)發(fā)展過程中出現(xiàn)的各種新理論、新方法、新算法、新手段、新設(shè)備等進(jìn)行綜合研究和集成應(yīng)用的一個(gè)整體框架，可分為3個(gè)層次[1]：</p><p>　　圖像處理（Image Processing）</p><p>　　強(qiáng)調(diào)在圖像之間進(jìn)行的變換，狹義上的圖像處理主要滿足對(duì)圖像進(jìn)行各種加工以改善圖像的視覺效果并為自動(dòng)識(shí)別打下基礎(chǔ)，或?qū)D像進(jìn)行壓縮編碼以減少所需存儲(chǔ)空間或存儲(chǔ)時(shí)間、傳輸通

13、路的要求。圖像處理是圖像工程最底層的操作，主要在圖像像素級(jí)上進(jìn)行處理，處理的數(shù)據(jù)量非常大。 </p><p>　　圖像分析（Image Analysis）</p><p>　　圖像分析是對(duì)圖像中感興趣的目標(biāo)進(jìn)行檢測(cè)和測(cè)量，以獲得目標(biāo)的客觀信息從而建立對(duì)圖像的描述。圖像分析是一個(gè)從圖像到數(shù)據(jù)的過程。這里的數(shù)據(jù)可以是對(duì)目標(biāo)特征測(cè)量的結(jié)果，或是基于測(cè)量的符號(hào)表示，其主要是以觀察著為中心研究

14、客觀世界。圖像分析是圖像工程中層的操作，分割和特征值提取把原來以像素描述的圖像轉(zhuǎn)變成比較簡(jiǎn)潔的非圖形式的描述。</p><p>　　圖像理解（Image Understanding）</p><p>　　圖像理解進(jìn)一步研究圖像中各目標(biāo)的性質(zhì)和它們之間的相互聯(lián)系，并得出對(duì)圖像內(nèi)容含義的理解以及對(duì)原來客觀場(chǎng)景的解釋，從而指導(dǎo)和規(guī)劃行動(dòng)。圖像理解在一定程度上是以客觀世界為中心，借助知識(shí)、經(jīng)驗(yàn)等來

15、把握整個(gè)客觀世界(包括沒有直接觀察到的事物)。圖像理解是處于圖像工程最高層的操作，基本上是對(duì)從描述抽象出來的符號(hào)進(jìn)行運(yùn)算，其處理過程和方法與人類的思維推理可以有許多類似之處。 </p><p>　　直線段的檢測(cè)屬于圖像分析階段，對(duì)其研究的意義在于：直線段是圖像的基本組成元素，任何圖形微觀上都是由直線段組成；直線段的檢測(cè)為圖像分析階段中更高層的處理諸如目標(biāo)的表達(dá)提取和識(shí)別提供數(shù)據(jù)支持，它的影響可以達(dá)到圖像理解階段

16、。在實(shí)際應(yīng)用中，道路識(shí)別、建筑物識(shí)別、醫(yī)學(xué)圖像分析、航空和衛(wèi)星圖像分析等領(lǐng)域都需要借重于直線檢測(cè)技術(shù)。</p><p>　　1.2 圖像檢測(cè)技術(shù)發(fā)展歷史及現(xiàn)狀</p><p>　　圖像檢測(cè)作為圖像分析技術(shù)的一個(gè)研究?jī)?nèi)容，它也是伴隨著數(shù)字圖像處理的發(fā)展而發(fā)展的。數(shù)字圖像處理這門學(xué)科的形成也是和社會(huì)生產(chǎn)力發(fā)展的需要分不開的。早期的圖像處理是由于通訊方面的要求而發(fā)展起來的，這就是本世紀(jì)20年代傳

17、真技術(shù)的發(fā)明和發(fā)展。其后，則是由于宇宙方面的要求，需要處理大量的宇宙探測(cè)器上拍攝下來的不清楚的其他天體(如月球、火星等)以及地球本身的照片。然而，圖像處理技術(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)一步推動(dòng)著社會(huì)生產(chǎn)力的發(fā)展。</p><p>　　圖像檢測(cè)是圖像分析研究?jī)?nèi)容的一部分。目前，在圖像分析領(lǐng)域已經(jīng)有很大的發(fā)展。圖像分析是一種

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

19、割、形狀分析、圖像檢測(cè)和配準(zhǔn)等幾個(gè)方面的內(nèi)容[2]：</p><p>　　(1)形態(tài)學(xué)圖像處理：它的基本概念可以追朔到Mnikowski對(duì)空間集合代數(shù)的研究和Matheron對(duì)拓?fù)涞难芯?。形態(tài)學(xué)圖像處理是這樣的一種處理類型，它對(duì)圖像中的物體的空間形態(tài)或結(jié)構(gòu)進(jìn)行修改。膨脹、腐蝕和骨架化是三種基本的形態(tài)學(xué)計(jì)算。</p><p>　　(2)邊緣檢測(cè)：一幅圖像的振幅屬性(如亮度或三色值)的變化或突

20、變是對(duì)圖像進(jìn)行描述的重要特性，因?yàn)樗鼈兂Ｖ甘緢D像中物體的物理特性。從一個(gè)層面到另一個(gè)層面的圖像亮度的局部突變叫亮度邊緣。對(duì)于亮度圖像中的邊緣檢測(cè)、直線檢測(cè)和點(diǎn)檢測(cè)有兩類近似方法：微分檢測(cè)和模型擬合。</p><p>　　(3)圖像特征提?。簣D像的特征是指圖像顯著的基本特征或特性。一些圖像是其本質(zhì)的特性，在一定程度上這樣的特征可以從視覺上分辨出來，另一些則是通過某些變換產(chǎn)生的人為特征。本質(zhì)特征包括像素區(qū)域和灰度紋理

21、區(qū)域的亮度。</p><p>　　(4)圖像分割：圖像分割法使圖像被劃分成或分隔成具有相近特征的區(qū)域。對(duì)于圖像分割法，其最基本的特征是:單色照片圖像的亮度振幅和彩色圖像的彩色因素。圖像邊緣和紋理也是對(duì)分割法很有用的特征。</p><p>　　(5)形狀分析：目前已經(jīng)提出了幾種定性的和定量的方法來描述圖像中物體的形狀，這些方法對(duì)于在模式識(shí)別系統(tǒng)中對(duì)物體進(jìn)行分類和在圖像理解系統(tǒng)中象征性的描述物

22、體是很有用的。在這些方法中，有一些只能應(yīng)用在二進(jìn)制圖像中，另外的一些則可以被擴(kuò)展到灰度圖像中。</p><p>　　(6)圖像檢測(cè)和配準(zhǔn)：圖像檢測(cè)主要是確定位于圖像內(nèi)被猜測(cè)的物體是存在還是不存在的。而圖像配準(zhǔn)主要是涉及到一對(duì)圖像區(qū)域的空間配準(zhǔn)問題。在一個(gè)圖像區(qū)域中，物體檢測(cè)的一種最基本方法是通過模板匹配來進(jìn)行。在目前的實(shí)際應(yīng)用中，廣泛的利用Hough變換來進(jìn)行圓形或橢圓性的物體檢測(cè)。</p><

23、;p><b>　　1.3 課題的難點(diǎn)</b></p><p>　　傳統(tǒng)的Hough 變換法首先是運(yùn)算量大,由于對(duì)所有源像素點(diǎn)都要進(jìn)行無差別的Hough 轉(zhuǎn)換運(yùn)算,對(duì)像素較大的圖像進(jìn)行轉(zhuǎn)換時(shí)相應(yīng)的計(jì)算時(shí)間也太長(zhǎng)。傳統(tǒng)的Hough 變換法最主要的缺陷在于它會(huì)將中斷的直線無差別地連接起來,在某些場(chǎng)合有助于修補(bǔ)圖像,但是對(duì)源數(shù)據(jù)處理階段會(huì)產(chǎn)生錯(cuò)誤的數(shù)據(jù),導(dǎo)致了與源圖像的偏差。</p>

24、;<p>　　第2章 直線檢測(cè)算法</p><p>　　直線檢測(cè)現(xiàn)在已經(jīng)成為計(jì)算機(jī)視覺中的一個(gè)研究重點(diǎn)，近年來許多學(xué)者就這一領(lǐng)域展開了廣泛研究并提出了許多直線檢測(cè)算法。目前直線檢測(cè)算法主要可以分為以下幾類：</p><p><b>　　Hough變換法</b></p><p><b>　　相位編組法</b>&

25、lt;/p><p><b>　　鏈碼檢測(cè)法</b></p><p>　　以下將就直線檢測(cè)中的一些經(jīng)典和高效算法進(jìn)行原理的介紹。</p><p>　　2.1 Hough直線檢測(cè)算法</p><p>　　Hough算法及其改進(jìn)算法是利用坐標(biāo)域變換的代表[3]。此類算法的優(yōu)點(diǎn)是抗干擾能力強(qiáng)，對(duì)圖像中的噪聲不敏感。但是由于其算法特點(diǎn)

26、使得其時(shí)間復(fù)雜度和空間復(fù)雜度都很高，并且在變換過程中丟失了線段的長(zhǎng)度信息。</p><p>　　Hough 變換的基本思想是點(diǎn)線的對(duì)偶性。一方面,圖像空間中共線的點(diǎn)對(duì)應(yīng)在參數(shù)空間里相交的線;另一方面,在參數(shù)空間中相交于同一個(gè)點(diǎn)的所有直線在圖像空間里都有共線的點(diǎn)與之對(duì)應(yīng)。因此Hough 變換把在圖像空間中的直線檢測(cè)問題轉(zhuǎn)換到參數(shù)空間中對(duì)點(diǎn)的檢測(cè)問題,通過在參數(shù)空間里進(jìn)行簡(jiǎn)單的累加統(tǒng)計(jì)完成檢測(cè)任務(wù)。如果參數(shù)空間中使用

27、直線方程,當(dāng)圖像空間直線斜率為無窮大時(shí),會(huì)使累加器尺寸和變很大,從而使計(jì)算復(fù)雜度過大。為解決這一問題,采用直線極坐標(biāo)方程,變換方程下所示。</p><p>　　ρ = xcosθ+ ysinθ （2-1）</p><p>　　根據(jù)這個(gè)方程,原圖像空間中的點(diǎn)對(duì)應(yīng)新參數(shù)空間中的一條正弦曲線,即點(diǎn)- 正弦曲線對(duì)偶。檢測(cè)直線的具體過程就是讓?duì)热”榭赡艿闹?然后

28、計(jì)算ρ的值,再根據(jù)θ和ρ的值對(duì)累加數(shù)組累加,從而得到共線點(diǎn)的個(gè)數(shù)。下面介紹θ和ρ取值范圍的確定。設(shè)被檢測(cè)的直線在第一象限, 右上角坐標(biāo)為( m , n) , 則第一象限中直線的位置情況如圖2-1所示。</p><p>　　圖2-1 　檢測(cè)位置圖</p><p>　　由圖可見,當(dāng)直線從與x 軸重合處逆時(shí)針旋轉(zhuǎn)時(shí),θ的值開始由0°增大,直到180°,所以θ的取值范圍為0&#

29、176;～ 180°。由直線極坐標(biāo)方程可知：</p><p><b>　　（2-2）</b></p><p>　　由θ、ρ的取值范圍和它們的分辨率就可以確定累加器的大小, 從而檢測(cè)直線。</p><p>　　2.2 Freeman直線檢測(cè)算法</p><p>　　Hough由于其應(yīng)用廣泛和簡(jiǎn)潔獲得了很大程度上的

30、認(rèn)可，但同時(shí)有學(xué)者對(duì)Hough算法的低效率和高空間占用并不滿意，而且在Hough變換時(shí)直線將喪失其長(zhǎng)度和具體位置的問題也令一些學(xué)者不滿意。于是，他們提出了改進(jìn)的方案。與Hough算法通過坐標(biāo)轉(zhuǎn)換的方式不同，改進(jìn)的方案更傾向與從直線的直接特征中尋找突破點(diǎn)。</p><p>　　Yuan 等提出了一種在鏈碼中檢測(cè)直線的算法。該算法從起始鏈碼開始,對(duì)每一鏈碼確定一個(gè)直線穿行區(qū)域以及兩條用于確定下一鏈碼是否屬于同一直線的

31、上下邊界線。如果下一鏈碼位于上下邊界線之內(nèi),則該鏈碼與上一鏈碼屬于同一直線;否則該鏈碼屬于另一直線。由于該算法僅對(duì)目標(biāo)的邊界鏈碼進(jìn)行處理, 因此其算法的復(fù)雜度較小, 為O ( n) ,其中n 為邊界鏈碼的個(gè)數(shù)。但該算法在跟蹤得到每一鏈碼時(shí)需確定下一直線鏈碼的存在范圍,這是一比較耗時(shí)的過程,利用數(shù)字直線的特征可以簡(jiǎn)化該過程。計(jì)算機(jī)處理的圖像是經(jīng)過采樣、量化等數(shù)字過程后形成的離散圖像,離散空間中的直線呈現(xiàn)出連續(xù)空間的直線所不具備的一些特征。

32、Freeman 總結(jié)了這些特征并提出了數(shù)字直線的鏈碼應(yīng)遵循的三條準(zhǔn)則(簡(jiǎn)稱Freeman 準(zhǔn)則)[4]: </p><p>　　一條數(shù)字直線的8鄰域鏈碼中最多包括兩個(gè)方向,其中一個(gè)為主方向,它是決定直線方向的主要因素; </p><p>　　這兩個(gè)方向的鏈碼值相差為1 (mod 8) ; </p><p>　　主方向上鏈碼值相同的連續(xù)像素組成一個(gè)線段子元,除去第一個(gè)

33、和最后一個(gè)線段子元,其余各線段子元的長(zhǎng)度至多相差一個(gè)像素。</p><p>　　Freeman算法直接從直線的特征找到突破點(diǎn)，通過比對(duì)直線的特征從而就可以</p><p>　　找出隱藏在圖像中的直線。這為從多的學(xué)者從迷茫中指明了方向，一些比較經(jīng)典的基于Freeman準(zhǔn)則的想法被相繼提出。</p><p>　　其中最有里程意義的應(yīng)該是Chan 等提出一個(gè)基于Freem

34、an準(zhǔn)則直線檢測(cè)算法。該算法完整而全面的理解了Freeman準(zhǔn)則，并且在現(xiàn)實(shí)上并不困難。該算法的具體思想如下：首先跟蹤線段子元,然后根據(jù)兩相鄰線段子元間的偏轉(zhuǎn)角度確定這兩線段子元是否相似,最后若兩子元相似則連接兩線段子元。該算法的計(jì)算復(fù)雜度為O( n) , n 為目標(biāo)邊界像素的數(shù)目。雖然該算法與Yuan 等算法的計(jì)算復(fù)雜度相同,但該算法在跟蹤得到一個(gè)線段子元后才進(jìn)行偏轉(zhuǎn)角度的計(jì)算,因此,該算法比Yuan 等算法更高效[5]。</p

35、><p>　　首先我們需要定義一個(gè)新概念：量化方向子集（Quantized Directional Subsets，下文簡(jiǎn)稱QDSs），在對(duì)一個(gè)圖像進(jìn)行數(shù)字化之后，一條連續(xù)的直線段將成為一系列短直線段的集合，而這些短直線段被定為在八個(gè)等同的量化方向上，如圖2-2所示。</p><p>　　圖2-2 像素的量化定位</p><p>　　這些具有相同的方向而長(zhǎng)度不同的短直線

36、段被成為量化方向子集（QDSs）。對(duì)于一個(gè)數(shù)字化直線任意的QDSs，可能存在不同長(zhǎng)度的短直線和相同長(zhǎng)度的短直線，我們稱為量化方向元素（Quantized Directional Elements，下文簡(jiǎn)稱QDEs）。</p><p>　　現(xiàn)在我們來考慮下一條數(shù)字化直線段的參數(shù)方程式為l1：y=a*x+b并且其終點(diǎn)為P1（x1，y1）和PN（xN，yN）。我們已經(jīng)定義了QDEs，而且可以認(rèn)為一條數(shù)字化直線就是那些處

37、在不同x，y坐標(biāo)占一個(gè)像素點(diǎn)QDE的QDEs。最初的擁有QDEs聯(lián)系的數(shù)字化已經(jīng)劃分完全了。</p><p>　　為了不失廣泛性，現(xiàn)在考慮tan-1α≦π/8（注意：主要QDS在方向0上）和主要點(diǎn)序列q（在主要QDE上像素的數(shù)目）</p><p><b>　　QDEs的結(jié)束點(diǎn)：</b></p><p><b>　　…</b>

38、;</p><p>　　… （2-3）</p><p><b>　　…</b></p><p>　　同樣的具有以下等式：</p><p><b>　　,</b></p><p><b>　　,</b>&l

39、t;/p><p><b>　　…</b></p><p>　　… （2-4）</p><p><b>　　…</b></p><p><b>　　.</b></p><p>　　εi是第i個(gè)點(diǎn)和（xq

40、n，yqn）=（xn,yn)的公差。</p><p>　　QDEs混合的情況如下：</p><p><b>　　,</b></p><p><b>　　,</b></p><p><b>　　…</b></p><p>　　…

41、 （2-5）</p><p><b>　　…</b></p><p>　　因此，第n個(gè)直線段和第n-1個(gè)直線段之間推導(dǎo)的夾角方程式是：</p><p><b>　　（2-6）</b></p><p>　　δθi被定義為數(shù)字化直線的定位的推導(dǎo)結(jié)果。相同的結(jié)果可以推論到其他

42、的方位。明顯的，δθ取值n將從0直到無窮。</p><p>　　我們現(xiàn)在可以得到一個(gè)推論：一條數(shù)字化直線角度的變化趨勢(shì)將會(huì)趨于穩(wěn)定（注意：更多的相同數(shù)字化直線的QDEs被連接）。這個(gè)收斂的特性對(duì)決定QDEs的連接是非常有用的（注意：如果和之前一個(gè)QDE的推導(dǎo)結(jié)果小于臨界值，QDE將會(huì)被連接）。</p><p>　　通過以上的補(bǔ)充定義我們可以方便的提出chan關(guān)于Freeman準(zhǔn)則的算法實(shí)現(xiàn)

43、。整個(gè)算法分為3步：</p><p><b>　　QDE（s）的存儲(chǔ)</b></p><p>　　在遍歷所有的QDEs之后，檢查每一個(gè)直線段能否和上一個(gè)直線段連</p><p>　　接。如果不能連接，我們將認(rèn)為這個(gè)QDE是一個(gè)新的直線段。QDE的數(shù)據(jù)</p><p>　　結(jié)構(gòu)將會(huì)存儲(chǔ)在一個(gè)LSL（Line Segment

44、 List）的直線段緩沖區(qū)（lp）中，</p><p><b>　　儲(chǔ)存方式如下：</b></p><p><b>　　;</b></p><p><b>　　;</b></p><p>　　; （2-7）</p><p>&l

45、t;b>　　;</b></p><p><b>　　;</b></p><p><b>　　;</b></p><p>　　點(diǎn)（x1，y1）和（xn，yn）代表了每個(gè)檢測(cè)QDE的起始點(diǎn)和結(jié)束點(diǎn)。</p><p>　　每個(gè)像素的QDE將被標(biāo)記為（line_number）放進(jìn)緩沖區(qū)中。

46、</p><p><b>　　相鄰直線段的搜索</b></p><p>　　一旦一個(gè)QDE被檢測(cè)，它的相鄰點(diǎn)將會(huì)被以a->b->c->d->e的順序檢測(cè)</p><p>　　是否存在一條直線段（如圖2-3）。在圖2-3中，被標(biāo)記為“1”的是存儲(chǔ)在</p><p>　　直線緩沖區(qū)中的已知的直線段。被

47、標(biāo)記為“N”的是現(xiàn)在正在追蹤的QDE。</p><p>　　如果一條直線處于檢測(cè)狀態(tài)，我們將按QDEs的近似化準(zhǔn)則來判定是否連</p><p><b>　　接。</b></p><p>　　圖2-3 搜索相鄰像素的準(zhǔn)則</p><p><b>　　QDEs的近似化</b></p>&l

48、t;p>　　近似化的QDEs必須滿足一下兩個(gè)條件：</p><p>　　1）一條直線所有的QDEs都小于π/4</p><p>　　2）數(shù)字化直線現(xiàn)在方位推導(dǎo)結(jié)果必須小于臨界值μ，</p><p>　　, （2-8）</p><p>　　α是一個(gè)正實(shí)數(shù)，εx代表當(dāng)前QDE的公差，其定義為：</p&g

49、t;<p>　　, （2-9）</p><p>　　mi是在第i個(gè)時(shí)期像素點(diǎn)的個(gè)數(shù)，q被定義為兩個(gè)QDEs之間所擁有的最小像素的數(shù)目。理論上，εx等于1或者0。</p><p>　　如果QDE（s）相似，他們將會(huì)同以前已經(jīng)發(fā)現(xiàn)的直線段連接起來。同時(shí)，參數(shù)也將會(huì)更新。</p><p>　　Freeman直線檢測(cè)

50、算法的優(yōu)點(diǎn)在于其具有較低的計(jì)算復(fù)雜度，實(shí)時(shí)性強(qiáng)。此外，由于在直線檢測(cè)之前首先進(jìn)行了邊界跟蹤，因此能比較方便地得到線段的長(zhǎng)度、方向等信息。但Freeman直線檢測(cè)算法的缺點(diǎn)在于，F(xiàn)reeman準(zhǔn)則來源于理想數(shù)字直線。因此當(dāng)邊界噪聲較大時(shí)，外觀上呈現(xiàn)出直線特征的線段也不能很好的滿足Freeman準(zhǔn)則。</p><p>　　2.3 尺蠖蠕行算法</p><p>　　利用大自然中生物的生活習(xí)性，可

51、以巧妙的解決人類社會(huì)的許多難題，尺蠖蠕行算法就是一種利用尺蠖蠕行的規(guī)律的算法。該算法首先是將圖像中的直線檢測(cè)問題分解成為若干個(gè)平行或近似于平行的直線族的檢測(cè),然后采用蠕行算法分別檢測(cè)各組的平行直線[6]。</p><p>　　2.3.1 尺蠖蠕行的過程和環(huán)境</p><p>　　尺蠖是一種蛾類的幼蟲,善于沿著樹枝爬行吃食,其蠕動(dòng)行進(jìn)的過程如下:</p><p>　　

52、(1) 選擇初始目標(biāo)。尺蠖在尋找食物源時(shí),根據(jù)自己的觸覺和對(duì)重力的感知作用搜索第一個(gè)攀援點(diǎn),然后在向上的鄰域內(nèi)繼續(xù)尋找下一個(gè)攀援點(diǎn),逐步挪動(dòng)身體向上攀援。</p><p>　　(2) 選擇行進(jìn)方向。尺蠖的整個(gè)身體在爬行到一條樹枝上之后,根據(jù)身體在當(dāng)前的位置所確定的直線方向向前爬行。若身體正前方?jīng)]有落腳點(diǎn),它將在以身體為軸線的小扇形區(qū)域內(nèi)擺動(dòng)前足尋找下一個(gè)落腳點(diǎn),如圖2-4(a) 所示。因此,它對(duì)行進(jìn)方向具有一定的

53、選擇性和容錯(cuò)性,從而使其行進(jìn)軌跡在一定距離內(nèi)近似為一條直線。</p><p>　　圖2-4 尺蠖的蠕行行為</p><p>　　(3) 蠕行。尺蠖利用身體的屈伸運(yùn)動(dòng)依次帶動(dòng)身體后端和前端的足,從而完成向前的蠕行(圖2-4(b) ～圖2-4(c) ) 。它的身體中間沒有足的分布,其身體中部的軸線在爬行平面上的投影始終為一直線段。由于它的身體自身的柔性特性,其前后足間的距離可在一定范圍內(nèi)伸縮,

54、從而在爬行時(shí)可跨越一定的距離間隔和障礙,降低了它對(duì)爬行路徑連續(xù)性的要求。當(dāng)爬行路徑上的間隔或障礙超過其身體長(zhǎng)度而無法跨越時(shí),尺蠖認(rèn)為它已經(jīng)走到了樹枝的盡頭,從而完成一個(gè)搜索過程。</p><p>　　尺蠖蠕行的環(huán)境可以是一棵枝椏遍布、縱橫交錯(cuò)的樹,也可以是一棵棵互相平行的植株(圖2-5) 。當(dāng)它在如圖2-5(a) 的樹上爬行時(shí),由于樹枝的交叉,在某處的行進(jìn)方向可能有多種選擇,其爬行的軌跡將可能偏離原有的直線方向;

55、 在平行的植株(圖2-5(b) ) 上爬行時(shí),其行進(jìn)方向是唯一確定的,從而保持了爬行軌跡的直線方向。</p><p>　　圖2-5 尺蠖的蠕行環(huán)境</p><p>　　2.3.2 基本原理</p><p>　　對(duì)應(yīng)于尺蠖的仿生學(xué)特點(diǎn),CCA 在邊緣像素子集內(nèi)檢測(cè)直線的原理如下:</p><p>　　(1) 選擇直線的初始搜索點(diǎn)。在選擇直線的初

56、始搜索點(diǎn)時(shí),尺蠖是在地面爬行碰到樹干時(shí)才向上探行。因此CCA 檢測(cè)直線時(shí)也首先從圖像的左下角(本文將圖像的左下角定義為圖像的坐標(biāo)原點(diǎn)) 開始逐行掃描,搜索圖像中的邊緣點(diǎn)。當(dāng)掃描到第一個(gè)邊緣點(diǎn)時(shí), 將其作為直線的初始搜索點(diǎn)( XS0 ,YS0) ,該點(diǎn)對(duì)應(yīng)于尺蠖在樹干上的第一個(gè)攀援點(diǎn)。</p><p>　　(2) 直線搜索的方向選擇。尺蠖在向前行進(jìn)時(shí),將根據(jù)自身當(dāng)前的狀態(tài)來判斷行進(jìn)的方向,將下一個(gè)落足點(diǎn)限制在以身體

57、為軸線的小扇形區(qū)域內(nèi),從而使運(yùn)動(dòng)軌跡在身體附近的小區(qū)域內(nèi)近似為一條直線。</p><p>　　在直線像素的搜索過程中,為了減少掃描區(qū)域,增加搜索的準(zhǔn)確性,同樣可以將直線的搜索方向角限定在一定范圍內(nèi)。如前所述,本文根據(jù)邊緣像素的梯度方向?qū)⑵鋭澐殖蔀? 個(gè)子集,每個(gè)子集在梯度方向上的參數(shù)空間占據(jù)兩個(gè)關(guān)于原點(diǎn)對(duì)稱的45°扇形區(qū)域(圖4) 。由于邊緣走向與梯度方向的垂直關(guān)系,當(dāng)在邊緣像素子集中檢測(cè)直線時(shí),搜索的

58、方向也可以相應(yīng)的限定在兩個(gè)45°的扇形區(qū)域內(nèi)(其中心線分別與梯度方向參數(shù)空間的兩個(gè)扇區(qū)中心線互相垂直) 。由于本文給出的直線初始點(diǎn)的搜索均從圖像的左下角開始,直線特征的搜索可限制在直角坐標(biāo)系的上半個(gè)平面,因此直線搜索的方向可進(jìn)一步限定在一個(gè)夾角為45°的扇形區(qū)域內(nèi)。圖5 (a) 給出了圖1 (b) 中矩形框所在直線的搜索方向范圍(0～ 45°) 。</p><p>　　(3) 直線特

59、征搜索。尺蠖利用身體的屈伸運(yùn)動(dòng)依次帶動(dòng)身體后端和前端的足,從而完成向前的爬行。它的身體中間沒有足分布,其身體中部的軸線在爬行平面上的投影始終為一直線段。由于它身體自身的柔性特性,其前后足間的距離δ可在一定范圍內(nèi)伸縮(0 <δ< 身體前后足間的直線長(zhǎng)度) 。</p><p>　　基于尺蠖前進(jìn)時(shí)的這些特點(diǎn),設(shè)計(jì)了CCA算法的直線特征搜索策略。其基本原理是將一條直線看作由若干條具有相似方向和一定長(zhǎng)度范圍的直

60、線段首尾相接而成,在圖像中依次檢測(cè)這些直線段便可完成一條直線的搜索。在理想情況下,直線邊緣上不存在間斷,這些直線段也是連續(xù)的。但在實(shí)際應(yīng)用中,由于光照等條件的影響,Canny 算子提取的圖像邊緣可能在個(gè)別地方不連續(xù)或凸起。這些凸起在邊緣像素子集的劃分過程中可能被劃分成為其它子集,從而造成直線段的間斷。因此在直線特征搜索過程中,應(yīng)允許擴(kuò)大搜索范圍并檢測(cè)具有一定間斷的線段,以提高算法的抗干擾能力。 </p><p>

61、　　第3章 Hough算法的改進(jìn)和實(shí)現(xiàn)</p><p>　　3.1 編程環(huán)境的搭建</p><p>　　3.1.1 OpenCV</p><p>　　OpenCV的全稱是：Open Source Computer Vision Library。 </p><p>　　OpenCV于1999年又Intel建立，現(xiàn)在由Willow

62、Garage提供支持。其是一個(gè)基于BSD許可授權(quán)發(fā)行的計(jì)算機(jī)視覺庫，由一系列C函數(shù)和少量C++類構(gòu)成，同時(shí)提供Python、Ruby、MATLAB等語言的接口，實(shí)現(xiàn)了圖像處理和計(jì)算機(jī)視覺方面很多的通用算法。其具有以下特點(diǎn)：</p><p><b>　　開放C源碼</b></p><p>　　基于Intel處理器指令集開發(fā)的優(yōu)化代碼</p><p&g

63、t;　　統(tǒng)一的結(jié)構(gòu)和功能定義</p><p>　　強(qiáng)大的圖像和矩陣運(yùn)算能力</p><p><b>　　方便靈活的用戶接口</b></p><p>　　支持MS-Windows和Linux平臺(tái)</p><p>　　作為一個(gè)基本的計(jì)算機(jī)視覺、圖像處理和模式識(shí)別的開源項(xiàng)目，OpenCV可以直接應(yīng)用于很多領(lǐng)域，作為二次開發(fā)的理

64、想工具[7]。</p><p>　　3.1.2 Microsoft Visual Studio</p><p>　　Visual Studio 是微軟公司推出的開發(fā)環(huán)境，Visual Studio 可以用來創(chuàng)建 Windows 平臺(tái)下的 Windows 應(yīng)用程序和網(wǎng)絡(luò)應(yīng)用程序，也可以用來創(chuàng)建網(wǎng)絡(luò)服務(wù)、智能設(shè)備應(yīng)用程序和 Office 插件。</p><p>　　Vi

65、sual Studio的出現(xiàn)大大降低了開發(fā)人員在設(shè)計(jì)代碼時(shí)所遇到的困難，其可以將主要的精力投入到實(shí)現(xiàn)軟件所需要的算法和思想，而不是像以前一樣將精力放在怎樣使用一種平臺(tái)。</p><p>　　自其誕生以來，Microsoft投入了大量的人力和物力來改進(jìn)其性能和擴(kuò)展其功能。Visual Studio 97是最早的Visual Studio版本?！　?lt;/p><p>　　1998年，Micros

66、oft發(fā)布了 Visual Studio 6.0。所有開發(fā)語言的開發(fā)環(huán)境版本均升至 6.0。這也是Visual Basic最后一次發(fā)布，從下一個(gè)版本 (7.0) 開始，Microsoft Basic進(jìn)化成了一種新的面向?qū)ο蟮恼Z言：Microsoft Basic NET?！　?　　</p><p>　　2005年，Microsoft發(fā)布了 Visual Studio 2005。.NET 字眼從各種語言的名字中被抹去

67、，但是這個(gè)版本的Visual Studio仍然還是面向 .NET 框架的（版本2.0）。 這個(gè)版本的 Visual Studio 包含有眾多版本，分別面向不同的開發(fā)角色。同時(shí)還永久提供免費(fèi)的Visual Studio Express 版本。</p><p>　　2007年，Microsoft發(fā)布了Visual Studio 2008。在這個(gè)版本中，最大的改動(dòng)就是Microsoft宣布不再支持Java。所以，無論是

68、Java，還是J#都從這個(gè)版本中消失了。</p><p>　　本軟件將在設(shè)計(jì)中使用最新的版本Visual Studio 2010，該版本支持最新的C++標(biāo)準(zhǔn)，并且增強(qiáng)了IDE，提高了編程的效率。同時(shí)其具有對(duì)Windows 7極強(qiáng)的兼容性，可以適應(yīng)當(dāng)前操作系統(tǒng)的發(fā)展趨勢(shì)。正是由于其這些特點(diǎn)，軟件在設(shè)計(jì)過程是將其作為圖片處理平臺(tái)。</p><p>　　3.1.3 環(huán)境搭建</p>

69、<p>　　下載并安裝OpenCV-2.2.0-win32-vs2010.exe</p><p>　　在VS2010創(chuàng)建自己的工程（如圖3-1）</p><p>　　圖3-1 創(chuàng)建VS2010項(xiàng)目</p><p>　　打開項(xiàng)目屬性，在彈出窗口中定位到VC++目錄（如圖3-2）</p><p>　　圖3-2 VC++目錄</p

70、><p>　　4）加入“D:\OpenCV2.2\include”、“D:\OpenCV2.2\include\opencv”這兩個(gè)路徑到包含目錄里。</p><p>　　5）加入“D:\OpenCV2.2\lib”路徑到庫目錄。</p><p>　　6）打開鏈接器，添加附加依賴項(xiàng)(如圖3-3）</p><p>　　opencv_core220d

71、.lib</p><p>　　opencv_highgui220d.lib</p><p>　　opencv_video220d.lib</p><p>　　opencv_ml220d.lib</p><p>　　opencv_legacy220d.lib</p><p>　　opencv_imgproc220d.li

72、b</p><p>　　圖3-3 添加依賴項(xiàng)</p><p>　　7）測(cè)試環(huán)境編譯是否成功（結(jié)果如圖3-4）</p><p>　　圖3-4 測(cè)試環(huán)境配置</p><p>　　3.2 Hough算法的改進(jìn)</p><p>　　3.2.1 Randomized Hough Transform(RHT)</p>

73、<p>　　Hough算法由于其明顯的優(yōu)越性，使其在提出后不斷的得到研究和發(fā)展?，F(xiàn)在的Hough改進(jìn)算法在復(fù)雜度和精確性上比最初的Hough算法有了很大程度的提高。</p><p>　　Pekka Kultanen等人針對(duì)Hough算法的缺點(diǎn)提出了一種改進(jìn)型的Hough算法——Randomized Hough Transform(RHT)[8]。</p><p>　　RHT 的

74、基本思想是隨機(jī)選取兩個(gè)邊緣點(diǎn)，由這兩點(diǎn)唯一確定參數(shù)空間的一個(gè)點(diǎn)，這是多到一的映射，避免了傳統(tǒng)Hough 變換一到多映射的龐大計(jì)算量。在實(shí)現(xiàn)累積時(shí)，采用動(dòng)態(tài)鏈表結(jié)構(gòu)，只對(duì)多到一映射所得到的參數(shù)分配單元進(jìn)行累積，從而降低了內(nèi)存需求，提高運(yùn)算速度。RHT的原理如下：</p><p>　　設(shè)(x，y)為圖像中的邊緣點(diǎn)，V 表示圖像邊緣點(diǎn)構(gòu)成的數(shù)據(jù)空間，圖像中的直線可表示為</p><p><

75、b>　?。?-1）</b></p><p>　　從V 中隨機(jī)選取3 個(gè)不同點(diǎn)Vk=(xk，yk)，k=m，n，t。由得到唯一直線lmn：</p><p><b>　　（3-2）</b></p><p>　　由上式可得到直線參量：</p><p><b>　?。?-3）</b><

76、;/p><p>　　此時(shí)，vt到直線lmn的距離dt-mn為：</p><p><b>　　（3-4）</b></p><p>　　如果vt在直線lmn上，dt-mn為0，由于數(shù)字圖像由一系列離散的點(diǎn)陣組成，所以3個(gè)點(diǎn)不一定確切地在某一條直線上，故dt-mn→0 時(shí)，即可認(rèn)為vt 在直線lmn 上。若三點(diǎn)在同一條直線上，對(duì)應(yīng)的直線可能是圖像中存在的

77、直線。通過判斷數(shù)據(jù)空間中邊緣點(diǎn)的累加值，可以進(jìn)一步確定此直線是否在圖像中確實(shí)存在。描述如下：初始化累加器S為0，對(duì)于數(shù)字空間V中的每個(gè)邊緣點(diǎn)vi，i=1，2，…n，n是邊緣點(diǎn)個(gè)數(shù)，若di-mn小于誤差閾值Tδ，即認(rèn)為此點(diǎn)在直線上，相應(yīng)的S加1，直至所有的點(diǎn)檢測(cè)完畢。若S的值大于給定的峰值閾值Tp，搜索圖像中該直線的斷點(diǎn)數(shù)，如斷點(diǎn)數(shù)小于斷點(diǎn)閾值，則判定該直線存在，并將該直線對(duì)應(yīng)的點(diǎn)從數(shù)據(jù)空間V 中剔除，提高下一條直線的檢測(cè)速度，否則判定這

78、條直線不存在，重復(fù)上述操作，檢測(cè)下一條直線，即可檢測(cè)出圖像中的多條直線參量。</p><p>　　Hough變換閥值的選擇也是一個(gè)很關(guān)鍵的問題，過大的閥值有可能出現(xiàn)非直線的干擾結(jié)果，而過小的閥值往往又會(huì)使得大場(chǎng)景中的直線因?yàn)槲镧R的像差被剔除。</p><p>　　3.2.2 RHT-LSM</p><p>　　眾所周知，LSM是一種數(shù)學(xué)優(yōu)化技術(shù)，它使用平方逼近的數(shù)學(xué)

79、思想，找到一組數(shù)據(jù)的最佳函數(shù)匹配。算法結(jié)合RTH抗噪聲能力強(qiáng)與LSM擬合精度高的特性，首先用隨機(jī)Hough變換確定直線的大致位置；然后，利用所得直線參數(shù)，計(jì)算圖像中的點(diǎn)到直線的距離，根據(jù)距離，可以確定每條直線附近的點(diǎn)集，剔除干擾點(diǎn)和噪聲；最后，用LSM對(duì)點(diǎn)集中的各點(diǎn)進(jìn)行擬合，得到精確的直線參量。</p><p>　　設(shè)圖像空間中欲擬合的各像素點(diǎn)的坐標(biāo)用（xi，yi）表示，i=1.2...n，n是擬合點(diǎn)個(gè)數(shù)，擬合函

80、數(shù)為</p><p><b>　?。?-5）</b></p><p>　　依據(jù)最小二乘法的性質(zhì)，得</p><p><b>　?。?-6）</b></p><p>　　設(shè)V是圖像中欲擬合的點(diǎn)集，遍歷點(diǎn)集中所有點(diǎn)vi（xi，yi），i=1.2...n，n是點(diǎn)集中元素的每個(gè)點(diǎn)的xi，yi，xi*yi，x

81、i2分別累加，最后把累加式帶入，即可得直線參量（a*，b*）[9]。</p><p>　　方法具體的實(shí)現(xiàn)如下步驟：</p><p>　　使用RHT確定所求G條直線的大致位置，得到G條模糊直線</p><p>　　分別找出各模糊直線附近的點(diǎn)集</p><p>　　擬合各點(diǎn)集Vk*中的數(shù)據(jù)，得到G條擬合直線</p><p>

82、;　　模式類聚分析提取直線</p><p>　　基于這種改進(jìn)的Hough算法比原算法具有更強(qiáng)的噪聲處理能力，同時(shí)在直線</p><p>　　存在彎曲的情況下也可以很好的檢測(cè)直線，由于LSM檢測(cè)直線的準(zhǔn)確性，同時(shí)也避免了檢測(cè)錯(cuò)誤直線的情況。</p><p>　　3.2.3 PCA-HT</p><p>　　針對(duì)傳統(tǒng)Hough算法計(jì)算時(shí)間長(zhǎng)、存儲(chǔ)

83、空間大的缺點(diǎn)，近來有學(xué)者提出了基于局部PCA方向統(tǒng)計(jì)分析的Hough直線檢測(cè)算法[10]。</p><p>　　主成分分析（ Principal Component Analysis，PCA）是一種掌握事物主要矛盾的統(tǒng)計(jì)分析方法，它可以從多元事物中解析出主要影響因素，揭示事物的本質(zhì)，簡(jiǎn)化復(fù)雜的問題。計(jì)算主成分的目的是將高維數(shù)據(jù)投影到較低維空間。給定 n個(gè)變量的m個(gè)觀察值，形成一個(gè)n′m的數(shù)據(jù)矩陣，n通常比較大。如

84、果事物的主要方面剛好體現(xiàn)在幾個(gè)主要變量上，我們只需要將這幾個(gè)變量分離出來，進(jìn)行詳細(xì)分析。但是，在一般情況下，并不能直接找出這樣的關(guān)鍵變量。這時(shí)我們可以用原有變量的線性組合來表示事物的主要方面。</p><p>　　利用PCA的特點(diǎn)，可以有效的與Hough變換進(jìn)行結(jié)合。首先通過邊緣檢測(cè)獲得圖像邊緣，對(duì)邊緣像素進(jìn)行分塊處理，利用PCA所得到所有掩膜范圍內(nèi)的主元方向，將獲得的局部方向信息映射到參數(shù)空間，側(cè)重利用其統(tǒng)計(jì)規(guī)

85、律來模糊約束Hough變換極角范圍，達(dá)到減少運(yùn)算量和存儲(chǔ)累計(jì)矩陣的目的。</p><p><b>　　方法分為以下三步：</b></p><p><b>　　掩膜的選取</b></p><p>　　搜索到邊緣圖像中所有的像素點(diǎn),其中任一像素點(diǎn)為a（x',y'）。令a</p><p>

86、　?。▁',y'）為中心,選取合適的正方形掩膜,大小為k×k,通常情況下取奇數(shù)，</p><p>　　掩膜的尺寸直接影響PCA 中求得主元方向的具體性與準(zhǔn)確度。尺寸太大，</p><p>　　所求得的局部主元方向不夠具體；太小，所有局部主元方向?qū)?huì)變得繁雜而</p><p>　　分散，不利于分析其統(tǒng)計(jì)規(guī)律。以a（x',y'）

87、為中心的掩膜內(nèi)所有像素構(gòu)成</p><p>　　的集合稱為a（x',y'）的支持集。</p><p>　　2）PCA 的方法獲得支持集的主元方向</p><p>　　通過對(duì)支持集中的像素點(diǎn)進(jìn)行統(tǒng)計(jì)，得到協(xié)方差矩陣，進(jìn)而得到特征向</p><p>　　量和特征值。協(xié)方差矩陣如下</p><p><b

88、>　?。?-7）</b></p><p>　　如果令支持集內(nèi)像素點(diǎn)的個(gè)數(shù)為，任一像素的坐標(biāo)為（xi，yi），則</p><p><b>　?。?-8）</b></p><p>　　根據(jù)協(xié)方差矩陣的描述，其第一特征根和第二特征根表述為</p><p><b>　　（3-9）</b>&

89、lt;/p><p>　　特征向量代表支持集內(nèi)點(diǎn)的主要分布方向，特征根表示這種分布的長(zhǎng)</p><p>　　度。通常情況下，λ1>λ2。若支持集內(nèi)為理想直線，那么λ2=0。根據(jù)Freeman</p><p>　　準(zhǔn)則，數(shù)字圖像中的直線并非真正的直線，而是成階梯狀。因此，λ2并不</p><p>　　一定等于0。但是，λ2的取值具有極大的不確定

90、性，所以一般認(rèn)為為0。然</p><p>　　后利用λ1求的主支持元方向θ'</p><p><b>　?。?-10）</b></p><p>　　依上述計(jì)算就可求得所有局部方向信息，將其映射到參數(shù)空間，進(jìn)而建</p><p>　　立參數(shù)空間中參數(shù)對(duì)應(yīng)的直方分布圖。</p><p>　　H

91、ough 變換參數(shù)局部范圍選擇</p><p>　　標(biāo)準(zhǔn)Hough 變換在計(jì)算的時(shí)候把(ρ，θ)的參數(shù)空間細(xì)分，并將它們</p><p>　　映射到累加器單元中。θ的取值范圍為0-180度。由于有了PCA的統(tǒng)計(jì)數(shù)據(jù)結(jié)</p><p>　　果，可以對(duì)θ的取值范圍進(jìn)行約束，其范圍為：</p><p><b>　?。?-11）</b

92、></p><p>　　此方法通過θ的取值范圍的約束從而實(shí)現(xiàn)了計(jì)算時(shí)間的降低和存儲(chǔ)空間的減少。</p><p>　　3.3 經(jīng)典Hough算法的實(shí)現(xiàn)</p><p>　　現(xiàn)在，我們將實(shí)現(xiàn)一種簡(jiǎn)單的Hough算法。由于Hough 變換的原理是把在圖像空間中的直線檢測(cè)問題轉(zhuǎn)換到參數(shù)空間中對(duì)點(diǎn)的檢測(cè)問題,通過在參數(shù)空間里進(jìn)行簡(jiǎn)單的累加統(tǒng)計(jì)完成檢測(cè)任務(wù)，同時(shí)直線檢測(cè)都

93、是建立在圖像的邊緣之上的，而往往一般的圖像并不是邊緣圖像。所以要實(shí)現(xiàn)一例Hough算法的實(shí)現(xiàn)需要經(jīng)過以下步驟：</p><p><b>　　獲取目標(biāo)圖像</b></p><p><b>　　對(duì)圖像進(jìn)行邊緣檢測(cè)</b></p><p>　　由圖像具體情況設(shè)置累加器大小</p><p>　　對(duì)圖像進(jìn)行H

94、ough變換并存儲(chǔ)結(jié)果</p><p>　　由累加器決定是否存在直線</p><p>　　根據(jù)最后結(jié)果繪制直線</p><p>　　通過以上步驟的實(shí)現(xiàn)我們可以首先得知整個(gè)系統(tǒng)的系統(tǒng)流程圖。系統(tǒng)流程圖如圖3.1所示。在整個(gè)系統(tǒng)中，我們將其劃分成為了獲取圖片、邊緣檢測(cè)、直線檢測(cè)、讀入?yún)?shù)和輸出結(jié)果5個(gè)步驟。系統(tǒng)流程圖的劃分為下一步的系統(tǒng)設(shè)計(jì)提供了有效支持。</p&

95、gt;<p>　　圖3-5 系統(tǒng)流程圖</p><p>　　系統(tǒng)在開發(fā)過程中擬采用面向?qū)ο蟮拈_發(fā)方式[11]，擁有3個(gè)類，分別為獲取圖片類（GetBMP），獲得直線類（GetLine）以及圖像輸出類（OutputBMP）。各類之間的成員參數(shù)和相互的聯(lián)系如圖3-6所示。</p><p>　　圖3-6 Class Diagram</p><p>　　通過上

96、圖我們可以直觀的知道各個(gè)類中的關(guān)系的方法，下面我們將詳細(xì)的介紹各個(gè)類的參數(shù)和方法。</p><p>　　3.3.1 獲取圖片類（GetBMP）</p><p>　　要對(duì)一張圖像進(jìn)行處理，我們首先需要獲得一張圖像。本項(xiàng)目擬讀入的圖像文件類型為BMP格式的文件。</p><p>　　BMP格式文件分為文件頭和信息頭以及內(nèi)容三個(gè)部分文件頭占14字節(jié)，其中包括文件類型，文件

97、大小，兩個(gè)為零的保留位以及文件數(shù)據(jù)的起始位5項(xiàng)重要的數(shù)據(jù)，其確定了BMP圖像的一些基本內(nèi)容。文件信息頭開始于第15字節(jié)，其擁有BMP圖像的基本設(shè)置和參數(shù)[12]。</p><p>　　要讀取一個(gè)BMP格式的文件首先需要建立兩個(gè)結(jié)構(gòu)，文件頭和信息頭。以便于接下來我們?cè)趫D像指定的位置獲得了參數(shù)后將其存入兩個(gè)結(jié)構(gòu)中。完成了結(jié)構(gòu)的建立之后，接下來需要做的就是進(jìn)行參數(shù)的讀取并將其存入相應(yīng)的結(jié)構(gòu)當(dāng)中。</p>

98、<p>　　獲取圖片類（GetBMP）參數(shù)和成員函數(shù)如圖3-7所示。</p><p>　　圖3-7 GetBMP類示意圖</p><p>　　下面我們將對(duì)GetBMP類的成員和函數(shù)進(jìn)行詳細(xì)的說明。</p><p>　　成員變量中bmfh和bmih兩個(gè)成員其類型為兩種結(jié)構(gòu)，就是上文所提到的BMP文件頭和BMP信息頭。要對(duì)BMP格式的文件進(jìn)行處理，就必須獲得文

99、件的一些基本信息。兩種結(jié)構(gòu)的定義如下：</p><p><b>　　BMP文件頭</b></p><p>　　typedef struct tagBITMAPFILEHEADER</p><p><b>　　{</b></p><p>　　WORD bfType; // 位圖文件的類型，必

100、須為“BM”</p><p>　　DWORD bfSize; // 位圖文件的大小，以字節(jié)為單位</p><p>　　WORD bfReserved1; // 位圖文件保留字，必須為0</p><p>　　WORD bfReserved2; // 位圖文件保留字，必須為0</p><p>　　DWORD bfOffBits; //

101、位圖數(shù)據(jù)的起始位置</p><p>　　}BITMAPFILEHEADER;</p><p><b>　　BMP信息頭</b></p><p>　　typedef struct tagBITMAPINFOHEADER{</p><p>　　DWORD biSize; // 本結(jié)構(gòu)所占用字節(jié)數(shù)</p&

102、gt;<p>　　LONG biWidth; // 位圖的寬度，以像素為單位</p><p>　　LONG biHeight; // 位圖的高度，以像素為單位</p><p>　　WORD biPlanes; // 目標(biāo)設(shè)備的平面數(shù)必須為1</p><p>　　WORD biBitCount; //

103、 每個(gè)像素所需的位數(shù)</p><p>　　DWORD biCompression; // 位圖壓縮類型</p><p>　　DWORD biSizeImage; // 位圖的大小，以字節(jié)為單位</p><p>　　LONG biXPelsPerMeter; // 位圖水平分辨率，每米像素?cái)?shù)</p><p>　　LONG biYPels

104、PerMeter; // 位圖垂直分辨率，每米像素?cái)?shù)</p><p>　　DWORD biClrUsed; // 位圖實(shí)際使用的顏色表中的顏色數(shù)</p><p>　　DWORD biClrImportant; // 位圖顯示過程中重要的顏色數(shù)</p><p>　　}BITMAPINFOHEADER;</p><p>　　成員變量wi

105、dth和height分別記錄了讀入原圖的高度信息和寬度信息，其數(shù)據(jù)的記錄，可以通過計(jì)算獲得圖像數(shù)據(jù)區(qū)的總長(zhǎng)度，方便我們獲得需要的數(shù)據(jù)。同時(shí)也可以為以后的操作界定了操作的邊界，減少計(jì)算量。</p><p>　　imgInfo[][]成員存儲(chǔ)了由BMP文件中讀入的數(shù)據(jù)，數(shù)列的二維坐標(biāo)直接對(duì)應(yīng)像素在直角坐標(biāo)系中對(duì)應(yīng)的位置，數(shù)據(jù)其有效值從0到255，含義是灰度圖中灰度值?；叶戎?為黑?；叶戎?55為白。</p>

106、;<p>　　整個(gè)類擁有8個(gè)成員函數(shù)，分別是readFileHeader、readInfoHeader、getLineBytes和readPixelData以及4個(gè)數(shù)據(jù)操作函數(shù)。接下來我們將分析函數(shù)的具體作用。</p><p>　　getFilePath函數(shù)負(fù)責(zé)讀取一個(gè)字符串，其指向字符串的起始位置。此字符串包含了文件的絕對(duì)路徑，為以后對(duì)文件的操作提供支持。</p><p>

107、　　readFileHeader函數(shù)需要讀入?yún)?shù)*filename和*bmfh。*filename是一個(gè)指向文件路徑的指針，使得函數(shù)能夠從目標(biāo)路徑讀取文件。*bmfh是一個(gè)指向圖像文件頭的指針，使得函數(shù)能夠把從文件中讀取的信息準(zhǔn)確的存入文件頭中。函數(shù)返回一個(gè)整數(shù)-1為打開文件失敗，0為打開文件成功，并讀取數(shù)據(jù)。函數(shù)調(diào)用了兩個(gè)函數(shù)fopen和fread。fopen函數(shù)打開一個(gè)文件夾，第一個(gè)參數(shù)是目標(biāo)文件夾，第二個(gè)參數(shù)是賦予權(quán)限。Fread

108、函數(shù)從文件的指定位置讀入數(shù)據(jù)，第一個(gè)參數(shù)是讀出數(shù)據(jù)存放位置，第二個(gè)參數(shù)是讀入數(shù)據(jù)大小，第三個(gè)參數(shù)是讀入數(shù)據(jù)個(gè)數(shù)，第四個(gè)參數(shù)是讀取文件夾。</p><p>　　int readFileHeader(char *filename,BITMAPFILEHEADER *bmfh)</p><p><b>　　{</b></p><p><b>

109、;　　FILE *fp;</b></p><p>　　fp = fopen(filename,"rb");</p><p><b>　　if(!fp)</b></p><p><b>　　{</b></p><p>　　printf("Can't o

110、pen the file\n");</p><p>　　return -1;</p><p><b>　　}</b></p><p>　　fread(&bmfh->bfType,sizeof(WORD),1,fp);</p><p>　　fread(&bmfh->bfSize,siz

111、eof(DWORD),1,fp);</p><p>　　fread(&bmfh->bfReserved1,sizeof(WORD),1,fp);</p><p>　　fread(&bmfh->bfReserved2,sizeof(WORD),1,fp);</p><p>　　fread(&bmfh->bfOffBits,si

112、zeof(DWORD),1,fp);</p><p>　　fclose(fp);</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　readInfoHeader函數(shù)需要讀入?yún)?shù)*filename和*bmih。*filename是一個(gè)指

113、向文件路徑的指針，使得函數(shù)能夠從目標(biāo)路徑讀取文件。*bmih是一個(gè)指向圖像信息頭的指針，使得函數(shù)能夠把從文件中讀取的信息準(zhǔn)確的存入信息頭中。函數(shù)調(diào)用了fseek函數(shù)，函數(shù)目的是使文件的指針跳到一個(gè)指定的位置。第一個(gè)參數(shù)是目標(biāo)文件，第二個(gè)參數(shù)是需要跳過的字節(jié)數(shù)，第三個(gè)參數(shù)是跳過時(shí)使用的模式。函數(shù)完成后返回-1表示無法打開文件，返回0表示操作成功。</p><p>　　int readInfoHeader(char

114、*filename,BITMAPINFOHEADER *bmih)</p><p><b>　　{</b></p><p><b>　　FILE *fp;</b></p><p>　　fp = fopen(filename,"rb");</p><p><b>　　if

115、(!fp)</b></p><p><b>　　{</b></p><p>　　printf("Can't open the file\n");</p><p>　　return -1;</p><p><b>　　}</b></p><p

116、>　　//文件頭占文件開始的14字節(jié)</p><p>　　fseek(fp,14,SEEK_SET);</p><p>　　fread(&bmih->biSize,sizeof(DWORD),1,fp);</p><p>　　fread(&bmih->biWidth,sizeof(LONG),1,fp);</p>&l