基于譜聚類的邊緣檢測算法

郭 新， 徐 明， 張 眾

(1.鄭州大學 信息工程學院 河南 鄭州 450001； 2.中原工學院 電子信息學院 河南 鄭州 451191;3.鄭州大學 電氣工程學院 河南 鄭州 450001)

0 引言

圖像邊緣處理是目標識別的基礎步驟，得到邊緣的清晰程度直接影響目標檢測的成功率，因此邊緣檢測問題一直是圖像處理領域的研究熱點之一，帶噪聲圖像的邊緣檢測目前仍面臨巨大的挑戰.

常見的邊緣檢測算子包括Sobel算子[1]、Prewitt算子[2]等.基于微分的邊緣提取算法的基本思想是辨別局部最大值或一階偏導和二階偏導的零交叉點，這些算法雖然運算簡單，但對噪聲較為敏感.另外，閾值的選擇問題對邊緣檢測的結果影響很大，如何選擇最優閾值是這些算法面臨的主要問題之一.隨著數學工具與人工智能算法的發展， 一些新處理工具的引進，如小波變換[3-4]、曲線演化[5]和磁滯技術[6]，在某種程度上提高了邊緣檢測的性能.因為高頻噪聲污染點也是局部最大點或者一階偏導和二階偏導的零交叉點，因此，傳統的邊緣檢測算法在處理高頻污染圖像時往往失效，不能得到清晰的邊緣圖像.

為解決高頻污染圖像的邊緣提取及閾值選擇問題，本文提出一種基于SCC[7]的邊緣檢測新算法.圖像是由光滑點和邊緣點組合而成，因此本文創新性地將圖像邊緣檢測問題轉換為二值分類問題，即變為仿射子空間混合的圖像平滑點和邊緣點的分類問題.由于平滑點和邊緣點的信息無法標記，因此該二分類問題只能通過無監督學習算法完成.常見的無監督學習算法往往依托于各類聚類算法，通過估計每一個平面的相關參數以及與其相關的數據點之間的分布特點，如K-均值聚類算法[8]，C-均值聚類算法[9].然而上述算法在有噪聲點的情形下，聚類性能受到很大影響，而SCC有望解決該情形下的分類問題.特別地，當噪聲點位于平滑點和邊緣點以外的子空間中，SCC能夠有效處理噪聲數據.

1 系統模型

1.1 數據集構建

一個像素的空域特征信息取決于它的鄰域.因此，在一幅灰度圖像中，將一個s×s大小的窗口(可以轉換為s2×1的矢量)視為數據集X中一個樣本點.特別地，位于第一行或第一列的灰度值并沒有較多的鄰域.為解決該問題，將該灰度矩陣(m×n)擴展到(m+s-1,n+s-1)，其前(s-1)/2和后(s-1)/2行和列均填充零，為了更好地說明這一過程，示意圖如圖1所示.

圖1 數據集構造過程Fig.1 The process of data construction

通過將所有的數據點按列的形式進行排列，即可得數據集X=[x1,…,xN].接下來討論中，我們認為數據集中的每一列即為該簇中的一個數據點.

1.2 相似矩陣的構造

相似矩陣可以構造為W=A·A′.由此，可以計算出數據集X中數據點的相似度，位于相同子空間的數據點的相似度大于子空間互異數據點的相似度.因此，兩個數據點的相似度越大，兩個點越有可能位于相同的類中.為對所提聚類算法進行評估，采用文獻[7]中的平均正交最小二乘估計誤差eOLS.

1.3 算法流程

對本文所提算法的主要步驟描述如下：

1) 初始化.對于待檢測圖像，通過1.1中方法構造數據集X，數據點的維度為d(1≤d≤s2)，且樣本子空間的分類平面K=2，采樣列數為c(默認為100).

2) 聚類.使用文獻[7]中SCC算法對數據集X進行處理.

3) 二值化.C1中聚類的樣本數據灰度值根據它的位置設定為1.同樣，C2中的數據點灰度值設為0，定義該二值圖像為A.

4) 稱β(A)為A的邊緣數據集，且β(A)=A-(AΘB)，其中B為正確的邊緣點集合，(AΘB)表示B對A的腐蝕.

1.4 復雜度分析

所提算法的復雜度主要來源于SCC算法.假設ns表示每個樣本點的迭代次數，那么SCC總的運行時間數量級為O(ns·(d+1)2·m·n·c).

2 仿真結果

為驗證所提算法的有效性，分別在圖像‘cameraman’和BSDS500數據集[11]上進行了實驗.因為s為所提算法的關鍵參數，我們分別研究了當s=3,5,7,9和d≤9時，所提算法在‘cameraman’圖2(a)和受到椒鹽噪聲污染‘cameraman’圖2(b)上的效果，結果分別對應于圖2中的(c)，(d)，(e)，(f).

圖2 參數s對去噪效果的影響Fig.2 The influence of parameter s on denoising

通過圖2可以得出如下結論：首先，噪聲得到了很好的抑制和消除.原因是如果數據集中的一個向量無論在邊緣組還是在平滑組中都明顯增加了eOLS，那么就判斷該點為噪聲點，并在接下來的采樣過程中忽略它.正因為噪聲點位于不同于邊緣點和光滑點的子空間中，所以大部分的噪聲點可以被成功消除.因此，不難理解參數s為什么能夠影響一個具體的邊緣信息.從視覺效果看，雖然s=5,7,9時，算法性能差別不大，但均比s=3時效果要好.然而，就幾何邊緣形狀提取效果而言，s=3,5,7,9的效果差別并不是很顯著.因此，在接下來的實驗中，本文設定s=3，但不難理解所提算法性能將隨著s的增加而增加.最后，維度d的選擇也不必過大，一方面，我們發現采用d≤9和采用更大的d時對于提高算法性能的影響很小.另一方面，較小的d有助于降低算法的運算復雜度.

第二組實驗包括4幅圖，編號分別為37 073,81 066,100 007,368 037，它們中的一個表示為圖片形式，其他結果用表格的形式對檢測比和錯誤比[12]進行歸納，其分別定義為：Pd=Nright/Nedge，Pf=Nwrong/Nedge，其中：Nedge為參考圖像的邊緣點個數；Nright代表正確檢測的邊緣點個數；Nwrong代表被錯誤檢測為邊緣點的非邊緣點個數.圖3顯示了編號為37 073的實驗結果.從視覺效果來看，所提算法明顯優于canny算子.為闡述數值結果，表1呈現了與多個算法的對比分析結果.在這些對比試驗中，假設所有的圖像都是經過椒鹽噪聲的污染.

圖3 不同邊緣檢測算法效果對比圖Fig.3 Comparison of performance for different algorithms

對比項log算法sobel算法prewitt算法canny算法本文算法37 073檢測概率0.849 60.925 20.924 50.807 70.931 237 073錯誤概率0.126 40.048 60.049 90.170 30.043 381 066檢測概率0.854 00.932 80.932 60.798 70.954 481 066錯誤概率0.131 80.051 70.051 90.187 70.028 6100 007檢測概率0.848 50.912 40.911 80.831 90.943 4100 007錯誤概率0.142 20.079 10.079 10.159 60.056 4368 037檢測概率0.880 50.929 40.929 20.832 70.953 6368 037錯誤概率0.107 70.071 20.071 30.165 60.032 7

由于在聚類過程中移除了大量的噪聲點，所提算法的的錯誤檢測概率明顯低于其他算法，換言之，準確概率顯著提高.

3 結論

本文提出一種新的算法，通過分類能夠有效提取數值圖像的邊緣特征信息.相比于傳統算法，特別針對噪聲圖像，仿真結果表明檢測概率能夠達到0.95左右，而且通過設計合適的s和d值可以進一步提高檢測概率.但是，如何從理論上確定合適參數d是下一步考慮的主要工作.