基于譜聚類的邊緣檢測(cè)算法

郭 新， 徐 明， 張 眾

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

0 引言

圖像邊緣處理是目標(biāo)識(shí)別的基礎(chǔ)步驟，得到邊緣的清晰程度直接影響目標(biāo)檢測(cè)的成功率，因此邊緣檢測(cè)問題一直是圖像處理領(lǐng)域的研究熱點(diǎn)之一，帶噪聲圖像的邊緣檢測(cè)目前仍面臨巨大的挑戰(zhàn).

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

為解決高頻污染圖像的邊緣提取及閾值選擇問題，本文提出一種基于SCC[7]的邊緣檢測(cè)新算法.圖像是由光滑點(diǎn)和邊緣點(diǎn)組合而成，因此本文創(chuàng)新性地將圖像邊緣檢測(cè)問題轉(zhuǎn)換為二值分類問題，即變?yōu)榉律渥涌臻g混合的圖像平滑點(diǎn)和邊緣點(diǎn)的分類問題.由于平滑點(diǎn)和邊緣點(diǎn)的信息無法標(biāo)記，因此該二分類問題只能通過無監(jiān)督學(xué)習(xí)算法完成.常見的無監(jiān)督學(xué)習(xí)算法往往依托于各類聚類算法，通過估計(jì)每一個(gè)平面的相關(guān)參數(shù)以及與其相關(guān)的數(shù)據(jù)點(diǎn)之間的分布特點(diǎn)，如K-均值聚類算法[8]，C-均值聚類算法[9].然而上述算法在有噪聲點(diǎn)的情形下，聚類性能受到很大影響，而SCC有望解決該情形下的分類問題.特別地，當(dāng)噪聲點(diǎn)位于平滑點(diǎn)和邊緣點(diǎn)以外的子空間中，SCC能夠有效處理噪聲數(shù)據(jù).

1 系統(tǒng)模型

1.1 數(shù)據(jù)集構(gòu)建

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

圖1 數(shù)據(jù)集構(gòu)造過程Fig.1 The process of data construction

通過將所有的數(shù)據(jù)點(diǎn)按列的形式進(jìn)行排列，即可得數(shù)據(jù)集X=[x1,…,xN].接下來討論中，我們認(rèn)為數(shù)據(jù)集中的每一列即為該簇中的一個(gè)數(shù)據(jù)點(diǎn).

1.2 相似矩陣的構(gòu)造

相似矩陣可以構(gòu)造為W=A·A′.由此，可以計(jì)算出數(shù)據(jù)集X中數(shù)據(jù)點(diǎn)的相似度，位于相同子空間的數(shù)據(jù)點(diǎn)的相似度大于子空間互異數(shù)據(jù)點(diǎn)的相似度.因此，兩個(gè)數(shù)據(jù)點(diǎn)的相似度越大，兩個(gè)點(diǎn)越有可能位于相同的類中.為對(duì)所提聚類算法進(jìn)行評(píng)估，采用文獻(xiàn)[7]中的平均正交最小二乘估計(jì)誤差eOLS.

1.3 算法流程

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

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

2) 聚類.使用文獻(xiàn)[7]中SCC算法對(duì)數(shù)據(jù)集X進(jìn)行處理.

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

4) 稱β(A)為A的邊緣數(shù)據(jù)集，且β(A)=A-(AΘB)，其中B為正確的邊緣點(diǎn)集合，(AΘB)表示B對(duì)A的腐蝕.

1.4 復(fù)雜度分析

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

2 仿真結(jié)果

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

圖2 參數(shù)s對(duì)去噪效果的影響Fig.2 The influence of parameter s on denoising

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

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

圖3 不同邊緣檢測(cè)算法效果對(duì)比圖Fig.3 Comparison of performance for different algorithms

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

由于在聚類過程中移除了大量的噪聲點(diǎn)，所提算法的的錯(cuò)誤檢測(cè)概率明顯低于其他算法，換言之，準(zhǔn)確概率顯著提高.

3 結(jié)論

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