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

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

2、和對(duì)比的軟件方便讀者更加深刻的理解Hough算法。</p><p>　　關(guān)鍵詞：直線(xià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 圖像工程與直線(xiàn)檢測(cè)1</p><p>　　1.2 圖像檢測(cè)技術(shù)發(fā)展歷史及現(xiàn)狀1</p

6、><p>　　1.3 課題的難點(diǎn)3</p><p>　　第2章 直線(xiàn)檢測(cè)算法4</p><p>　　2.1 Hough直線(xiàn)檢測(cè)算法4</p><p>　　2.2 Freeman直線(xiàn)檢測(cè)算法5</p><p>　　2.3 尺蠖蠕行算法9</p><p>　　2.3.1 尺蠖蠕行的過(guò)程和環(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 獲取圖片類(lèi)（GetBMP）23</p><p>　　3.3.2 獲得直線(xiàn)類(lèi)（GetLine）28</p><p>　　3.3.3 圖像輸出類(lèi)（OutputBMP）32</p><p>　　3.4 軟件效果展示36</p><

10、p>　　3.4.1 軟件結(jié)果展示36</p><p>　　3.4.2 直線(xiàn)檢測(cè)效果36</p><p>　　3.5 經(jīng)典Hough算法的性能39</p><p>　　第4章 結(jié)束語(yǔ)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 圖像工程與直線(xiàn)檢測(cè)</p><p>　　

12、圖像工程將圖像技術(shù)發(fā)展過(guò)程中出現(xiàn)的各種新理論、新方法、新算法、新手段、新設(shè)備等進(jìn)行綜合研究和集成應(yīng)用的一個(gè)整體框架，可分為3個(gè)層次[1]：</p><p>　　圖像處理（Image Processing）</p><p>　　強(qiáng)調(diào)在圖像之間進(jìn)行的變換，狹義上的圖像處理主要滿(mǎn)足對(duì)圖像進(jìn)行各種加工以改善圖像的視覺(jué)效果并為自動(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ù)的過(guò)程。這里的數(shù)據(jù)可以是對(duì)目標(biāo)特征測(cè)量的結(jié)果，或是基于測(cè)量的符號(hào)表示，其主要是以觀察著為中心研究

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

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

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

17、真技術(shù)的發(fā)明和發(fā)展。其后，則是由于宇宙方面的要求，需要處理大量的宇宙探測(cè)器上拍攝下來(lái)的不清楚的其他天體(如月球、火星等)以及地球本身的照片。然而，圖像處理技術(shù)的發(fā)展，遠(yuǎn)遠(yuǎn)突破了這兩個(gè)領(lǐng)域，到今天，它已經(jīng)廣泛的應(yīng)用到科學(xué)研究、工農(nóng)業(yè)生產(chǎn)、軍事技術(shù)、政府部門(mén)、醫(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、從一幅圖像中通過(guò)自動(dòng)的或半自動(dòng)的方法提取圖像尺寸、數(shù)據(jù)或信息的方法。圖像分析方法通常因圖像分析系統(tǒng)最后的輸出是數(shù)字而不是畫(huà)面，使它與其他類(lèi)型的圖像處理方法，如編碼、恢復(fù)、放大等不同。圖像分析源于經(jīng)典的模式識(shí)別方法，根據(jù)定義，分析系統(tǒng)并不局限于對(duì)一個(gè)固定數(shù)量類(lèi)別的場(chǎng)景區(qū)域的分類(lèi)，而是更傾向于可設(shè)計(jì)成用于描繪復(fù)雜場(chǎng)景。根據(jù)事先預(yù)測(cè)，該場(chǎng)景的種類(lèi)可能是非常多的和不確定的。目前，圖像分析領(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é)圖像處理是這樣的一種處理類(lèi)型，它對(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è)、直線(xiàn)檢測(cè)和點(diǎn)檢測(cè)有兩類(lèi)近似方法：微分檢測(cè)和模型擬合。</p><p>　　(3)圖像特征提?。簣D像的特征是指圖像顯著的基本特征或特性。一些圖像是其本質(zhì)的特性，在一定程度上這樣的特征可以從視覺(jué)上分辨出來(lái)，另一些則是通過(guò)某些變換產(chǎn)生的人為特征。本質(zhì)特征包括像素區(qū)域和灰度紋理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

48、t;p>　　近似化的QDEs必須滿(mǎn)足一下兩個(gè)條件：</p><p>　　1）一條直線(xiàn)所有的QDEs都小于π/4</p><p>　　2）數(shù)字化直線(xiàn)現(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)的直線(xiàn)段連接起來(lái)。同時(shí)，參數(shù)也將會(huì)更新。</p><p>　　Freeman直線(xiàn)檢測(cè)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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ì)過(guò)程是將其作為圖片處理平臺(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>　　打開(kāi)項(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”路徑到庫(kù)目錄。</p><p>　　6）打開(kāi)鏈接器，添加附加依賴(lài)項(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 添加依賴(lài)項(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ù)空間，圖像中的直線(xiàn)可表示為</p><p><

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

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

77、直線(xiàn)。通過(guò)判斷數(shù)據(jù)空間中邊緣點(diǎn)的累加值，可以進(jìn)一步確定此直線(xià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)在直線(xiàn)上，相應(yīng)的S加1，直至所有的點(diǎn)檢測(cè)完畢。若S的值大于給定的峰值閾值Tp，搜索圖像中該直線(xiàn)的斷點(diǎn)數(shù)，如斷點(diǎn)數(shù)小于斷點(diǎn)閾值，則判定該直線(xiàn)存在，并將該直線(xiàn)對(duì)應(yīng)的點(diǎn)從數(shù)據(jù)空間V 中剔除，提高下一條直線(xiàn)的檢測(cè)速度，否則判定這

78、條直線(xiàn)不存在，重復(fù)上述操作，檢測(cè)下一條直線(xiàn)，即可檢測(cè)出圖像中的多條直線(xiàn)參量。</p><p>　　Hough變換閥值的選擇也是一個(gè)很關(guān)鍵的問(wèn)題，過(guò)大的閥值有可能出現(xiàn)非直線(xiàn)的干擾結(jié)果，而過(guò)小的閥值往往又會(huì)使得大場(chǎng)景中的直線(xiàn)因?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變換確定直線(xiàn)的大致位置；然后，利用所得直線(xiàn)參數(shù)，計(jì)算圖像中的點(diǎn)到直線(xiàn)的距離，根據(jù)距離，可以確定每條直線(xiàn)附近的點(diǎn)集，剔除干擾點(diǎn)和噪聲；最后，用LSM對(duì)點(diǎn)集中的各點(diǎn)進(jìn)行擬合，得到精確的直線(xiàn)參量。</p><p>　　設(shè)圖像空間中欲擬合的各像素點(diǎn)的坐標(biāo)用（xi，yi）表示，i=1.2...n，n是擬合點(diǎn)個(gè)數(shù)，擬合函

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

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

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

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

85、律來(lái)模糊約束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>　　的集合稱(chēng)為a（x',y'）的支持集。</p><p>　　2）PCA 的方法獲得支持集的主元方向</p><p>　　通過(guò)對(duì)支持集中的像素點(diǎn)進(jìn)行統(tǒng)計(jì)，得到協(xié)方差矩陣，進(jìn)而得到特征向</p><p>　　量和特征值。協(xié)方差矩陣如下</p><p><b

88、>　　（3-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>　?。?-9）</b>&

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

90、性，所以一般認(rèn)為為0。然</p><p>　　后利用λ1求的主支持元方向θ'</p><p><b>　　（3-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>　　此方法通過(guò)θ的取值范圍的約束從而實(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 變換的原理是把在圖像空間中的直線(xiàn)檢測(cè)問(wèn)題轉(zhuǎn)換到參數(shù)空間中對(duì)點(diǎn)的檢測(cè)問(wèn)題,通過(guò)在參數(shù)空間里進(jìn)行簡(jiǎn)單的累加統(tǒng)計(jì)完成檢測(cè)任務(wù)，同時(shí)直線(xiàn)檢測(cè)都

93、是建立在圖像的邊緣之上的，而往往一般的圖像并不是邊緣圖像。所以要實(shí)現(xiàn)一例Hough算法的實(shí)現(xiàn)需要經(jīng)過(guò)以下步驟：</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>　　由累加器決定是否存在直線(xiàn)</p><p>　　根據(jù)最后結(jié)果繪制直線(xiàn)</p><p>　　通過(guò)以上步驟的實(shí)現(xiàn)我們可以首先得知整個(gè)系統(tǒng)的系統(tǒng)流程圖。系統(tǒng)流程圖如圖3.1所示。在整個(gè)系統(tǒng)中，我們將其劃分成為了獲取圖片、邊緣檢測(cè)、直線(xiàn)檢測(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)在開(kāi)發(fā)過(guò)程中擬采用面向?qū)ο蟮拈_(kāi)發(fā)方式[11]，擁有3個(gè)類(lèi)，分別為獲取圖片類(lèi)（GetBMP），獲得直線(xiàn)類(lèi)（GetLine）以及圖像輸出類(lèi)（OutputBMP）。各類(lèi)之間的成員參數(shù)和相互的聯(lián)系如圖3-6所示。</p><p>　　圖3-6 Class Diagram</p><p>　　通過(guò)上

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

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

98、<p>　　獲取圖片類(lèi)（GetBMP）參數(shù)和成員函數(shù)如圖3-7所示。</p><p>　　圖3-7 GetBMP類(lèi)示意圖</p><p>　　下面我們將對(duì)GetBMP類(lèi)的成員和函數(shù)進(jìn)行詳細(xì)的說(shuō)明。</p><p>　　成員變量中bmfh和bmih兩個(gè)成員其類(lèi)型為兩種結(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; // 位圖文件的類(lèi)型，必

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; // 位圖壓縮類(lèi)型</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; // 位圖顯示過(guò)程中重要的顏色數(shù)</p><p>　　}BITMAPINFOHEADER;</p><p>　　成員變量wi

105、dth和height分別記錄了讀入原圖的高度信息和寬度信息，其數(shù)據(jù)的記錄，可以通過(guò)計(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è)類(lèi)擁有8個(gè)成員函數(shù)，分別是readFileHeader、readInfoHeader、getLineBytes和readPixelData以及4個(gè)數(shù)據(jù)操作函數(shù)。接下來(lái)我們將分析函數(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為打開(kāi)文件失敗，0為打開(kāi)文件成功，并讀取數(shù)據(jù)。函數(shù)調(diào)用了兩個(gè)函數(shù)fopen和fread。fopen函數(shù)打開(kāi)一個(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ù)是需要跳過(guò)的字節(jié)數(shù)，第三個(gè)參數(shù)是跳過(guò)時(shí)使用的模式。函數(shù)完成后返回-1表示無(wú)法打開(kāi)文件，返回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、>　　//文件頭占文件開(kāi)始的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