一種特征線提取的自適應閾值選擇方法*

邵 煜，王亞偉，胡建華，王昊天，萬子豪

（1.太原科技大學計算機科學與技術學院，太原 030024；2.佛山市科自智能系統技術有限公司，廣東佛山 528010；3.中國科學院自動化研究所，北京 100190）

0 引言

圖像處理領域的特征提取技術越來越受到人們的關注，其結果可廣泛應用于圖像配準、圖像識別、遙感圖像、直線匹配和三維重建等方面，其中三維重建具有很高的研究價值，能幫助對實物進行數字化保護。基于圖像的數字化保護也可成為基于圖像的古建筑三維重建，而特征提取作為古建筑數字化保護過程中的關鍵步驟，其精度和效率直接影響三維重建的結果。現在三維重建中的特征提取主要包括點、線和區域等特征。其中，直線因為豐富的局部描述信息和紋理信息，成為三維重建過程中的常用特征。因此，特征線提取具有非常重要的研究意義。

目前，常用的特征線提取方法有很多，雖然其最終結果都是提取圖像中的直線，但它們的效率和準確度卻不盡相同，有的特征線算法提取效率高，但特征線提取結果并不準確；有的特征線算法提取效率低，但特征線提取結果比較精確。其中Hough 變換就是一種經典的直線提取算法，它主要利用了類似于生活中的投票機制來檢測直線，即累加器，利用累加器在極坐標系中檢測峰值，構成該峰值的每一條曲線即為笛卡爾坐標系中構成直線的每一個點，這些點構成的直線Hough 變換檢測出來的直線。因此，Hough 變換具有抗干擾能力強、對噪聲不敏感的優點，成為當前特征先提取中的研究熱點。

然而，針對結構復雜、紋理重復的對象，基于Hough的直線提取方法受參數影響很大，若參數設置不合適，提取的直線存在斷線多、直線提取不正確的問題。實際上，圖像的邊緣信息對直線提取也有一定的指導意義，所以為了提高直線提取信息，本文結合Canny 邊緣檢測方法，設計了一種自適應直線提取方法，該方法首先運用邊緣檢測使目標邊緣與背景分割開來，使之能夠在保留理想的目標邊緣信息的同時，還能大大減少圖像處理的計算量，最終保證直線提取的準確性；然后針對Hough直線提取方法存在斷線多的問題，分析了Canny 邊緣檢測和Hough變換中的參數對直線提取結果的影響，并給出相應結論。

1 相關工作

1.1 邊緣檢測方法

提取圖像中的邊緣信息在圖像處理技術中是非常重要的一個環節，既能使目標邊緣與圖像背景分割開來，同時還能大大減少圖像處理的計算量。圖像中的邊緣其實就是圖像中相鄰像素點有很明顯的灰度值差距的部分，邊緣檢測就是通過在圖像中查找出所有具有明顯灰度值差值的相鄰像素點區域，從而檢測出圖像邊緣的一個過程。目前應用比較廣泛的算子主要有以下幾種：Robert算子是最早使用的一種邊緣算子，提出于1965年，它是一個2×2 的二維模板，采用對角線方向相鄰兩象素之差近似梯度幅值檢測邊緣，邊緣定位精準度比較高，是一種最簡單的算子，但缺點是對噪聲比較敏感，容易受到噪聲的影響；Prewitt 算子是在Robert 算子提出后，為了對其進行改進，提高邊緣檢測的精準度，人們又提出了Prewitt 算子，它實質是當像素點上下、左右鄰點的灰度值的差在邊緣處達到極值時進行邊緣檢測，優點是去除了部分偽邊緣，對漸變低噪聲也具有平滑作用，但不能很好地處理復雜的噪聲；Sobel 算子是一種經過改進優化得到的算子，在進行邊緣檢測時，可分別利用Sobel 算子中的Sobelx 矩陣和Sobely 矩陣與圖像中的每個像素點做卷積運算，然后可以分別得出每個像素點在x方向上和y方向上的差分，最后可利用這個兩個差分值計算像素點的梯度大小和梯度方向，是一種應用廣泛，簡單有效的算子，但缺點是Sobel 沒有將圖像進行灰度化處理。

1.2 特征線提取方法

如今人們已經設計出了很多種檢測和提取直線的方法，其中比較常用的方法就是采用Hough變換[1-13]來檢測和提取直線，Hough 變換是一種從參數域到特征域的直線提取技術，但傳統的Hough 變換算法有很多不足的地方，比如說它本身就是一種一對多的映射匹配算法，所以傳統的Hough 變換具有很高的時間復雜度和空間復雜度，而且在參數空間里的計算中很容易出現一些計算誤差，這會影響到直線提取的準確性，這對于很多計算機專業人員來說是一種不理想的結果。所以，人們在傳統的Hough 變換算法的基礎上設計出了很多種優化后的Hough 變換算法，盡可能地彌補傳統Hough 變換算法的不足。典型方法包括：1990年，Yamato 設計了一種算法，在Hough 變換中，在變換得來的參數空間中保存所有極值點，對其進行檢測可以得到兩個參數（ρ，θ），通過這兩個參數可以在圖像中找到這條直線，且該直線為最優的直線。同時，1990年，國內學生Xu Lei 等提出了一種隨機Hough 變換算法，這種方法將復雜的映射關系轉化為較簡單的映射關系，最后再從圖像中隨機選取邊緣點進行直線提取。該方法大幅度減少了Hough 變換算法的時間復雜度和空間復雜度，但該方法也存在一定的缺陷，由于是隨機選取邊緣點，那就很容易受噪聲等因素的影響，若圖像在預處理階段處理不當時，那就會嚴重影響到該算法的準確度和穩定性。在隨后的1991年時，Kiryati 發表了一種基于概率的Hough 變換算法，這種算法和傳統的直線提取算法有著相同的映射方法，但不同的是這種概率Hough 變換算法的時間復雜度和空間復雜度都比傳統Hough 變換算法的要小，與隨機Hough變換相比，它是在圖像空間中建立了一個隨機的小窗口數據點，這樣就提高了計算機的計算效率，所以這種方法更多地應用于具有高噪聲、高誤差率的圖像，對于簡單而又不復雜的圖像來說用這種方法會比用傳統Hough變換花更多的時間。1994年，Akhtar 提出了一種時間和空間復雜度比較好的算法，在Hough 變換的過程中設計一個累加器，該方法可通過對累加器進行投票操作，已投票的數量來間接表示出已檢測直線的長度，但該方法卻只能有累加作用，并不能判斷直線的端點在哪里。2011年，Ji 等提出了一種改進的Hough 變換算法，該方法主要是在進行峰值累計的時候利用局部算子來加大圖像中的直線和噪聲的差別，再通過計算全局閾值使直線能更好地提取出來，這樣做既降低了噪聲等因素影響，又提高了直線提取的準確度，表面上看似是一種很好的直線提取算法，但也存在很大的局限性，因為該方法只能檢測和提取一些定長的直線。

然而，不管是邊緣提取方法還是特征線提取方法，不可避免地存在參數選擇困難的問題，本文針對特征線的參數選擇問題進行研究并給出相關結論。

2 方法介紹

本方法主要分成兩部分：Canny邊緣檢測和Hough特征線提取。

2.1 Canny邊緣檢測

（1）圖像濾波——高斯濾波法

二維高斯分布公式是高斯濾波法能夠實現的原理所在，當均值μ=0 時，其二維高斯分布公式可變為如式（1）所示，是由兩個如式（2）所示的一維高斯分布函數相乘，高斯濾波主要利用了概率論中聯合概率密度等于邊緣概率密度之積（隨機變量x，y相互獨立）這一原理得來的。

如果將二維高斯分布公式用函數圖像表示，可表示為圖1所示的樣子。從圖中可以看出，離中心點越近位置，值越大，離中心點越遠的位置，值越小。這一特性奠定了高斯濾波的基礎，高斯濾波法就是利用這一特性設計出了高斯卷積核。圖2所示就是一個大小為3×3 的高斯卷積核的設計過程，設計一個如圖2（a）所示的3×3 大小的模板，以其中心點為坐標值（0，0）的原點，再依次寫出周邊的坐標值，然后假設標準差σ=1.5 就可通過式（1）算出來一個如圖2（b）所示的權重模板，最后將該權重模板每個位置的值除以權重模板所有值的總和，就可得到如圖2（c）所示的最終的高斯卷積核。

圖1 二維高斯分布公式的函數圖像

圖2 設計高斯卷積核的過程

在高斯濾波的過程中，每次將目標像素點放在卷積核的中心位置，依次在原圖像中將卷積核包含在內的各像素點的值作為權重與卷積核對應位置的值相乘，將卷積核內每個位置所得的乘積的值進行相加，其最后的結果就為這一輪高斯卷積后所得像素點的值，重復以上步驟，直到原圖像的所有像素點都進行了高斯卷積，最后每一個高斯卷積后的像素點組成的圖像就為高斯平滑去噪后的圖像。

高斯濾波法能夠得到廣大工程人員的喜愛，這都歸功于高斯函數的幾個重要性質，比如二維高斯函數旋轉不變性，人們根據這個性質設計出了高斯卷積核，然后就是高斯函數的寬度參數σ，σ能較好地決定平滑程度，σ越大，其最后的平滑程度越好。

（2）計算梯度幅值

在Canny 邊緣檢測中，使用Sobel 一階偏導算子來計算像素點的梯度幅值和方向，Sobel也有兩個算子，一個是如式（3）所示的水平算子，一個是如式（4）所示的垂直算子。

分別用這兩個算子對圖像中的每個像素點做卷積運算，所得出的值即為每個像素點在x軸上和在y軸上的變化率，分別為dx與dy，可分別用式（5）和式（6）表示。

再通過式（3）和式（4）可以進一步得到用Sobel算子計算的梯度幅值和梯度方向公式，分別如式（7）和式（8）所示。

（3）非極大值抑制

當計算出所有像素點的梯度幅值時，會存在一些粗邊緣，此時需要利用梯度方向和邊緣的關系原理來對粗邊緣進行細化，在圖像中邊緣與梯度總是成垂直關系，如圖3所示，對于同一梯度方向上像素點，可以比較它們的梯度值，保留其中的最大值，其他像素點的灰度值都置為0（黑色）。

圖3 圖像中存在的各種邊緣

（4）利用雙閾值剔除圖像全部邊緣中的偽邊緣部分

由于受到各種噪聲的影響，圖像中存在著許多噪聲帶來的或亮或暗的點，即使已經進行過了濾波處理，但也只能是最大程度地減少這些點的產生，并不能完全消除，然后圖像中的這些一個個的點就組成了如圖3所示的偽邊緣，這導致在進行邊緣檢測時，計算機很難區分偽邊緣和真實的目標邊緣，此時可以通過設置一個閾值來去掉圖像中的部分邊緣信息，幅值大于該閾值的像素點被保留，幅值低于該閾值的像素點被去掉，但會發現一個問題，那就是很難確定閾值的大小，若閾值設置較大，則會損失很多邊緣信息，弱閾值設置得較小，則會有過多的邊緣信息，這不利于后續的邊緣處理，所以本文所設計的系統采用雙閾值法來保留目標邊緣，去除偽邊緣。

2.2 Hough變換

得到圖像所有邊緣信息后，需要計算邊緣圖像的所有邊緣像素點獲得投票信息，這個過程計算量比較大，所需的內存也比較大，所以需要在標準Hough變換的基礎上進行改進，以提高算法的執行效率。改進后的思想為：當使用幾個點通過標準Hough變換找出一條直線時，那么該直線上的所有點在后續就不需要再被處理，然后再隨機從剩下邊緣點中隨機選取一個點進行處理，直到邊緣圖像中沒有需要被處理的邊緣像素點時，則就完成了直線提取的過程，這樣既可以節省內存的占用，也能提高程序執行效率。

這種改進的Hough變換方法的主要的執行步驟如下：

（1）隨機抽取圖像中的幾個邊緣像素點，在累加器中進行峰值統計，進行標準Hough 變換，當峰值大于閾值時，則檢測出一條直線并將其存儲起來，并隨著該直線的方向找到該直線線段的兩個端點，若不存在大于閾值的峰值時，進行步驟（2）；

（2）從剩余的邊緣像素點中隨機抽取幾個邊緣像素點，重復步驟（1）；

（3）計算出提取出的所有線段的長度，再通過與某一閾值比較，長度若大于該閾值，則被認為是好的直線，并將這些好的直線在圖像上輸出顯示出來。

3 參數分析及結果

3.1 Canny參數分析

在Canny 邊緣檢測中，需要設置一個閾值來去除圖像中偽邊緣，盡可能地保留理想中的目標邊緣，但此時如果閾值設置得過大，那就會丟失包括目標邊緣在內的很多圖像中的邊緣信息，如果閾值設置得過小，那就會在圖像中保留很多不屬于真正目標邊緣的像素點，以致于后續不能準確地進行直線提取。所以需要同時設置兩個閾值，一個高閾值，一個低閾值，這兩個閾值結合起來進行邊緣檢測。與單閾值一樣，雙閾值也是要確定其值的大小，如何選取合適的高閾值與低閾值，需要進行對比分析，分析過程如下。

通過設置Canny 函數中的高閾值和低閾值，可以得到不同的高低閾值比，本系統設置了3 個不同的高低閾值比，分別為1.5∕1、3∕1、4.5∕1，再設置4 個不同區間的高閾值數值區間，分別為（0，50）、（50，100）、（100，150）、（150，250）。

以圖4所示的圖為原圖，原圖中有總共有800×533=426 400個像素點。對比時每次從一個區間內隨機取一個數作為高閾值，在同一閾值比下可以取不同的高閾值進行定量分析，比較不同閾值比對圖像檢測的影響，從而取得的一個合適的高低閾值比。對比結果如表1所示。由表可知，隨著閾值的提高，對邊緣的提取越精簡，從而越能排除各種干擾因素（樹、草、云），讓后期的特征線提取更精確。在相同的閾值下，閾值比越大，可以讓提取的邊緣信息更多，但閾值也不是越大越好，如果閾值很大，那就損失過多邊緣信息的。同時通過以上圖片對比可看出，當高低閾值比為4∕1、高閾值取210 時圖像中保留的邊緣信息是比較理想的。所以通過本次對比試驗可得出，高閾值應取大于150且小于250的值，且高低閾值比設置在3∕1～4∕1之間是最好的。

圖4 原圖

表1 不同閾值大小和閾值比下邊緣像素點個數

3.2 Hough參數分析

由于Hough 變換是利用閾值來判斷直線的，閾值設置的大小會直接影響直線的提取，所以需要做一個分析對比實驗來為系統選擇一個合適的閾值。

與Canny 邊緣檢測閾值的選取實驗一樣，分別從不同的數值范圍內選取一個值作為閾值來進行對比，選擇4 個不同的閾值區間分別為（0，50）、（50，100）、（100，150）與（150，250）。對比結果如表2所示。

表2 不同閾值大小下直線提取的數量和程序執行時間

由此可知，對于同一幅圖像，隨著閾值的增大，Hough 變換提取出的直線數量越少，相應的程序執行時間也隨之減少，并且雖然閾值的變大會給程序的執行帶來時間上的效益，但在同時圖像的特征點會丟失得越多，以至于達不到理想中的直線提取效果。當在（0，50）的范圍內取閾值時，提取出的特征線是最多的，但其中也包括了很多錯誤的特征線，當在（50，100）的范圍內取閾值大小為75時，提取很多不需要的特征線，同時執行時間也降低了。所以可得以下結論：（1）對于特征信息較少的簡單圖像，可以適當放棄程序執行時間上的效益，降低閾值大小，提取更多的直線，閾值在（0，50）范圍內比較合適；（2）對于特征信息較多的復雜圖像，必須要在提取足夠多的直線特征信息的同時降低程序執行的時間，閾值在（50，100）范圍內比較合適。

4 結束語

由于特征線具有更豐富的幾何信息，因此，特征線的提取成為研究熱點之一，并已廣泛應用于圖像匹配、三維重建、衛星遙感圖等領域。Hough 變換作為一種常用的直線提取方法，具有抗干擾能力強、對噪聲不敏感、對非直線結構不敏感等優點。然而針對結構復雜、紋理重復的對象，現有的Hough變換方法存在受參數影響大、時間復雜度高、丟失特征線長度信息等問題，針對上述問題，本文提出了一種可變閾值的特征線提取方法。該方法首先運用Canny 邊緣檢測使目標邊緣與背景分割開來，使之能夠在保留理想的目標邊緣信息的同時，還能大大減少圖像處理的計算量，最終保證直線提取的準確性；然后對Canny 邊緣檢測算法和Hough 變換算法中的關鍵參數進行分析；最后給出在Canny 邊緣提取方法中，當高低閾值比為4∕1、高閾值取210 時合理的結論。Hough 變換中當在（0，50）的范圍內取閾值時，提取出的特征線是最多的。當在（50，100）的范圍內取閾值大小為75時，將提取很多不需要的特征線，同時執行時間也降低的結論。上述結論對Canny邊緣提取方法和Hough算法的參數合理設置具有重要指導意義。