隨機變點統計的ＭＤＲ邊緣檢測算法

（華南理工大學 數學科學學院， 廣州 510640）

摘 要：統計方法是計算機視覺中邊緣檢測的重要處理方法，但是之前的基于概率統計的算法在效率和效果方面均不能得到令人滿意的結果，所以阻礙了這類算法的推廣應用和進一步發展。為此，提出一種基于隨機變點統計的多尺度(multidirectionsrelationship，MDR)邊緣檢測算法，并深入分析和討論了該算法在實際應用中的處理框架和多個參數控制問題。實驗證明，該算法在保全圖像信息和細節處理上均具有優勢。

關鍵詞：計算機視覺；邊緣檢測；多方向關聯算法

中圖分類號：TP39141 文獻標志碼：A

文章編號：10013695(2009)01038403

MDR edge detection algorithm on random changepoint theory

GUAN Yizhang，HAO Zhifeng

(College of Mathematics， South China University of Technology， Guangzhou 510640， China)

Abstract:Statistical method is an important method on edge detection of computer vision. But the preview algorithms， which based on probability theory， are not practical. So the development of this research direction has been slow.This paper proposed a MDR (multidirectionsrelation) algorithm， and discussed on the setting of the parameters carefully. The experiments show that the algorithm is faithful to desource and is good at dealing the detail of images.

Key words:computer vision；edge detection；MDR algorithm

0 引言

邊緣檢測作為計算機視覺的基礎而又相當關鍵的圖像處理工作一直是一個研究熱點。從概率統計的角度來研究邊緣檢測的算法是其中一個重要方法。J. S. Huang等人[1]從概率統計的角度對邊緣檢測進行了討論，并指出邊緣檢測中最大的問題是噪聲對檢測結果的影響，如閾值的選擇。要想有好的檢測結果就要十分恰當地選擇閾值，但是沒有一般的好方法。R.M. Haralick[2]提出了Slope Facet模型，本質上是三個參數的回歸分析，可是還沒有解決其中的回歸變點問題，而這個問題的解決基礎本質上是一個多決策理論的難題。為了解決這個問題，J. S. Huang等人提出了統計變點理論。將圖像分成很多小塊，每一塊均是一個n×n的正方形，使得這個正方形中最多只有一個邊緣。國內研究者在此基礎上進行精確測量[3]等的應用推廣。在這個統計方法中，首先要確定n的取值。顯然這里的n是由圖像的分辨率決定的，而且還應該是比較小的數值，那么這將是一個全局參數。如果沒有關于邊緣形態的先驗知識，要解決好這個問題在圖像處理方面是比較困難的。為了避開這個局部統計計算中的全局參數計算的難題，本文提出采用分解的方法——首先只采用統計方法判斷變點是否存在，然后根據統計變點相互的關聯性來進行計分，得分較高的變點作為種子，再由所有與之關聯的變點組成邊緣。

變點問題[4，5]最初源于工業中的質量控制問題。近年來，關于統計變點的算法有不錯的進展。本文主要采用了M. Lavielle等人[6，7]提出的基于蒙特卡洛方法的統計變點算法。這類算法一般只是用于一維時間序列的處理。

1 邊緣檢測中的基本統計方法

11 基于經典統計方法的邊緣檢測

J. S. Huang等人[1]提出了邊緣檢測的基本統計方法。他們將圖像分成很多小塊，每一塊均是一個n×n的正方形，而n要足夠小，使得這個正方形中最多只有一個邊緣。顯然這里的n是由圖像的分辨率以及圖像中物體的星外觀性質決定的。考察這些小塊，不難發現它們大體有四種類型， 包括一致區域、階梯形邊緣（由兩塊組成，每一塊至少有三個像素）、線（有一條線通過一致區域）、點（在一致區域上有一個點，至少由三個像素組成）。這四種類型如圖1所示。對于圖1(b)~(d)這些有邊緣的情形，都是在這個小塊中存在灰度值相差較大的兩塊區域。

對于一個n×n的正方形區域，用Xi（i=1，2，…，N，N=n2）來表示每一個像素的灰度值。在這里，由于像素的灰度值會受到噪聲的影響，可認為Xi是隨機變量。假設這里的n足夠小，那么這個區域中最多出現兩組灰度差距大的兩個分類。對應地，將落在第一分類區域中的像素灰度值記為{Xi；i=1，2，…，m}，落在第二塊區域中像素灰度值記為{X′i；i=1，2，…，m′}。其中：m+m′=N。不妨假設Xi~N(μi，σ2)，X′i~N(μ′i，σ2)，就是說在給定分法(P)時存在著下面的這樣一個假設

H0:μ1=μ2=…=μm=μ′1=μ′2=…=μ′m=μ0

對立假設

H1:μ1=μ2=…=μm≠μ′1=μ′2=…=μ′m′

因為n比較小，所以上述兩個假設至少有一個是真的，當然這個命題也可能是假的，可是這樣概率太小，則忽略不計。如果是H0真的，這就是一個一致區域，不存在邊緣；如果H1是真的，那么這種劃分就對應著邊緣。通過統計分析構造了統計量W2=maxP（m×m′×|-′|2）/N×S2P。其中：S2P=[mi=1(Xi-)2+m′i=1(X′i-′)2]/（N-2），P代表一種對這個區域的像素分為兩類的分法。

對于給定的α，文獻[1]中給出了相應的ξα值。如果W2＞ξα則拒絕H0，說明這不是一個一致區域，那么使得W2最大的分組就對應著邊緣；否則就接受H0，認為這是一個一致區域。

這個統計方法在實際應用中有一定的局限性。其中一個問題就是要首先確定n的取值。顯然，這里的n應該是一個比較小的數值，而且還是由圖像的分辨率決定的，是一個影響全局結果的重要參數。如果沒有關于邊緣形態的先驗知識，要解決好這個問題在圖像處理方面是比較困難的。沒有一個好的解決方案，就會降低算法的可靠性和穩定性。為了避開這個局部統計計算中的全局參數計算的難題，本文提出采用方向分解(multidirection)的方法，首先只采用統計方法判斷變點是否存在，然后根據統計變點相互的關聯性(relationship)來進行分析，最后確定邊緣的位置。

12統計變點基本算法

近年來，關于統計變點的算法有不錯的進展。本文主要采用了M. Lavielle等人[6，7]提出的基于蒙特卡洛方法的統計變點算法。

考慮一個隨機變量序列Y1，Y2，…，Yn，它們取值于R。假定在一些未知時刻（位置）τ*1，τ*2，…，τ*K*-1變量序列Y=(Y1，Y2，…，Yn)的期望發生突變。其中K*是未知數據樣本分段的數目，而K*-1是變點的個數。

要求解隨機序列Y=(Y1，Y2，…，Yn)中的多變點的估計問題，可以采用的統計方法有序列統計量方法和局部法，這里采用的是一種全局估計[7]方法。

令K為一整數，記τ=（τ1，τ2，…，τK-1）為一整數序列。其中0＜τ′1＜τ2＜…＜τK-1＜n。對任意1≤k≤K，構造一個用來估計均值參數的懲罰函數U=U(Yτk-1+1，

Yτk-1+2，…，Yτk;θ)，假設對每個k都有關于均值θ的估計值使得懲罰函數取得最小值，則有

U(Yτk-1+1，Yτk-1+2，…，Yτk;(Yτk-1+1，Yτk-1+2，…，Yτk))≤U(Yτk-1+1，Yτk-1+2，…，Yτk;θ)

定義懲罰函數為

J(τ，y)=1/nKk=1U

(Yτk-1+1，Yτk-1+2，…，Yτk;

(Yτk-1+1，Yτk-1+2，…，Yτk))

其中τ0=0，τK=n。懲罰函數的形式可以根據應用背景不同作相應的設定。在這里考慮下面的形式

U(Yτk-1+1，Yτk-1+2，…，Yτk;μ)=τki=τk-1+1(Yi-μ)2

而函數的最小值為

U(Yτk-1+1，Yτk-1+2，…，Yτk;)=τki=τk-1+1(Yi-k)2

其中k是第k段的經驗均值（樣本均值）。

2 MDR邊緣檢測算法框架和參數控制

21 MDR邊緣檢測算法計算框架

為了避開局部統計計算中的全局參數計算的難題，筆者提出采用方向分解的方法。首先只解決統計方法判斷變點是否存在的問題，然后根據統計變點相互的關聯性來進行計分，得分較高的變點作為種子，再由所有與之關聯的變點組成邊緣。具體來說，將二維的統計問題分解為多個方向數據序列的一維統計變點的檢測。在這個檢測過程中，只考慮變點是否存在的問題，而對于邊緣的形態先留在下一步再進行分析和處理。假定G是要處理的灰度圖像，為簡單起見，假設圖像的長度和寬度相同，統計變點算法對一維數據的處理效率比較高，因此這里采用四個方向采樣再進行獨立處理的方法。這四個方向包括水平方向、垂直方向、對角線方向和反對角線方向，如圖2所示。

統計變點算法中有三個參數可以調整，包括Kmax、Lmin和sigma參數。這三個參數的物理意義和設定策略會在下一節進行討論，這里采用默認值，即Kmax=20，Lmin=1，sigma=5e-5。事實上，在檢測過程中發現，在同一組參數下，如果采樣數據長度不同也會影響到檢測效果，這主要是因為Kmax參數對于不同的數據規模會發現不同尺度下的邊緣。為了統一尺度，在圖2(c)和(d)情形的Kmax參數是動態的，按照采樣容量的比例來設置。例如，當采樣容量（m）為256時，動態Kmax=1+fix(20/fix(m/20))，這樣可以保持與第一和第二種情形的尺度相同。

采用方向分解的方法，只考慮統計方法判斷變點是否存在，再根據統計變點相互的關聯性來進行計分，得分較高的變點作為種子，再由所有與之關聯的變點組成邊緣。從圖3（b）~（f）的圖像效果來看，該算法對于采樣方向來說是敏感的。

22 統計變點算法的參數設置

在統計變點算法中可以調整的參數有三個，包括sigma、Lmin和Kmax。Sigma參數的主要作用是在規定最大變點數（Kmax）的情況下，算法篩選變點的指標。Lmin參數的作用是規定變點的間隔距離；Kmax參數指定最大變點數。下面以圖3為例子，討論和分析這三個參數對圖像邊緣檢測的作用和影響。

221 參數

Sigma參數是統計變點算法中可以調整的參數之一，它的主要作用是在規定最大變點數（Kmax）的情況下自動篩選變點的臨界值指標。這個參數的使用效果相當于是統計學中的置信水平的臨界值。算法會在規定的最大變點數下展開計算。首先根據懲罰函數的計算結果挑出Kmax個最有可能的像素作為待選變點（邊緣點），然后根據遞減的變點數量計算各組的p(K)值，即分別就其中的K=Kmax，Kmax-1，…，2個變點的組合來計算組合的p(K)值，最后根據預先設定的sigma臨界值來判定哪一組是最有可能的變點組合，也就是說，算法將在不同變點個數（Kmax，Kmax-1，…，2）的組合中搜尋小于sigma的最大組（具有最多變點的組合）。參數sigma對圖像邊緣檢測的影響是非常顯著的。圖4中列出了在a）Kmax=15，Lmin=1；b)Kmax=20，Lmin=1；c）Kmax=25，Lmin=1三種情況分別就經sigma=5e-5篩選前后的邊緣檢測效果來進行比較。

從邊緣檢測的效果來看，sigma參數可以大大減少噪聲的影響，但是也造成了計算資源的很大浪費。從總體來說是得不償失，所以邊緣檢測算法中應盡量減少主要依賴sigma參數去噪所帶來的資源消耗問題。從實驗結果來看，要解決這個問題，主要是要平衡好sigma和Kmax的取值問題。從大量實驗來看，一般可先設定sigma的默認值為5e-5。在這個條件下，如果篩選的比例低于0.3則認為算法是低效率的，就應該調低Kmax的取值。在確定Kmax的取值后，sigma參數作為環境參數就可以功成身退，由Kmax進行微調。

222 參數Lmin

參數Lmin指的是相鄰的變點之間的最短距離。這里指的就是邊緣點之間的像素數目。在實際處理中，算法會從要處理的數據中每隔Lmin-1個像素來進行采樣。這樣做很可能會損失一些信息。如果沒有圖像的先驗知識，那么就可以認為邊緣之間的距離有可能很近，所以默認值為Lmin=1。圖5中列出了Kmax=15時，Lmin=1，3的結果。

223 參數Kmax 

仍然采用256×256的灰度圖像，觀察參數Kmax單獨控制變點的圖像效果。圖5各圖分別依次選取Kmax=15，20，30等的運行結果。這里，相當于令sigma趨于無窮小，每一次檢測變點的個數是固定的，就是Kmax的值。顯然，這樣做的結果是在增加發現不同尺度的范圍的同時也增大了引入噪聲的風險。

3 結束語

統計變點算法中可以調整的參數包括最大變點數Kmax、變點間的最小距離Lmin，以及置信水平sigma參數值，需要補充說明的是，Kmax和Lmin兩個參數的效果是相對于采樣的數據規模而言的。例如，一張圖片在參數設置為Kmax=20和Lmin=3時獲得最佳的檢測邊緣，那么，將同一張圖片按照一定算法放大一倍，算法就會在參數設置Kmax=20和Lmin=6時獲得最優檢測結果。而如果采樣數據是采用原來數據的半數來處理時，假定邊緣分布相對均勻，那么采用Kmax=10和Lmin=3就很有可能獲得最優邊緣。

本文所用編程平臺是MATLAB7，將程序運行結果和MATLAB所帶的edge算法進行比較，發現該算法在保全圖像信息和細節處理上均具有優勢。另外，相對于其他邊緣檢測算法中的參數，Kmax參數顯然具有更加直觀的物理意義，具體應用起來顯得簡單易行。

參考文獻：

［1］

HUANG J S，TSENG D H.Statistical theory of edge detection[J].Computer Vision，Graphics， and Image Processing，1988，43（3）:337346.

[2]HARALICK R M.Digital step edges from zero crossing of second directional derivatives[J].IEEE Trans on Pattern Analysis and Machine Intelligence，1984，6(1):5868.

[3]吳曉波.圖像邊緣特征分析[J].光學精密工程，1999，7(1):5963.

[4]BASSEVILLE M，NIKIFOROV I V.Detection of abrupt changes:theory and applications [M].Englewood Cliffs: PrenticeHall，1993.

[5]GUAN Yizhang，HAO Zhifeng.Using SVMs method to detect abrupt change[C]//Proc of International Conference on Machine Learning and Cybernetics.Hong Kong:IEEE Press，2007.

[6]LAVIELLE M，LEBARBIER E.An application of MCMC methods to the multiple changepoints problem[J].Signal Processing，2001，81(1):3953.

[7]LAVIELLE M.Using penalized contrasts for the changepoint problem[J].Signal Processing，2005，85(8):15011510.