??? 摘 要： 提出了一種快速二維最大相關(guān)準(zhǔn)則閾值分割算法。該方法利用積分和迭代編程技術(shù)，避免了數(shù)據(jù)的重復(fù)運算，從而將計算的復(fù)雜性從一般二維最大相關(guān)準(zhǔn)則方法的O(L4)減少至O(L2)。實驗結(jié)果表明，該方法分割效果好，計算效率高，適合實時圖像系統(tǒng)的應(yīng)用。
??? 關(guān)鍵詞： 閾值分割；最大相關(guān)準(zhǔn)則；快速算法
?
??? 閾值化是圖像分割中一項重要的技術(shù)[1]。常用的閾值分割方法有：直方圖雙峰法、最大熵法、矩量保持法、梯度統(tǒng)計法、一維最大相關(guān)準(zhǔn)則法[2]，以及這些方法在二維上的推廣化方法。這些方法中，一維最大相關(guān)準(zhǔn)則以其運算簡單、分割效果好、適用范圍廣而得到廣泛應(yīng)用。
??? 一維最大相關(guān)準(zhǔn)則法由Yen[3]等人提出。該方法以圖像的一維直方圖為依據(jù)，以目標(biāo)和背景的相關(guān)總量為最大選擇閾值，在多數(shù)情況下能取得很好的閾值。但在實際應(yīng)用中，當(dāng)圖像信噪比降低時，應(yīng)用一維最大相關(guān)法將產(chǎn)生很多分割錯誤。為此，2005年陳修橋[4]等人將一維最大相關(guān)法(MCC)推廣到二維。二維最大相關(guān)法應(yīng)用二維直方圖，不僅反映了灰度分布信息，還反映了鄰域空間相關(guān)信息，使分割效果得到了明顯改善。但其計算量大、耗時長，難以實用。為了解決這一問題，本文利用積分和迭代編程技術(shù)，實現(xiàn)了算法的簡化，減少了計算復(fù)雜度，增強了算法的實用性。
1 二維最大相關(guān)準(zhǔn)則閾值分割
??? 若一幅圖像的灰度級數(shù)為L，總的像素點數(shù)為N(m×n)，設(shè)fij為圖像中點灰度為i、區(qū)域灰度均值為j的像素點數(shù)，pij為點灰度-區(qū)域灰度均值對(i，j)發(fā)生的概率，即：
??? 
其中，N（m×n）為圖像的總像素數(shù)，則pij{i，j=1…L}就是該圖像關(guān)于點灰度－區(qū)域灰度均值的二維直方圖。
??? 圖1為二維直方圖的xoy平面圖。沿對角線分布的A區(qū)和B區(qū)分別代表目標(biāo)類和背景類，遠(yuǎn)離對角線的C區(qū)和D區(qū)分別代表邊界和噪聲，所以應(yīng)該在A區(qū)和B區(qū)上利用點灰度－區(qū)域灰度均值，通過二維最大法確定最佳閾值，使真正代表目標(biāo)類和背景類的相關(guān)數(shù)為最大。這兩類的分別被定義為：
??? 
其中：
??? 
相關(guān)數(shù)的判別函數(shù)定義為：
2 快速二維最大相關(guān)準(zhǔn)則閾值分割算法
??? 在上述二維最大相關(guān)準(zhǔn)則閾值分割算法中，對于每個(s，t)對，都要從頭開始計算PA(s，t)和GA(s，t)，運算過程是一個四重循環(huán)，計算復(fù)雜性為O(L4)，計算比較耗時。實際應(yīng)用中，為了提高運算速度，減少重復(fù)運算，需進一步優(yōu)化算法。
??? 從式（2）、式（3）和式（7）可以看出，計算TC(s，t)需要計算PA(s，t)、GA(s，t)和GL。而GL恒定，PA(s，t)是二維直方圖P中坐標(biāo)(s，t)左上方的元素和，GA(s，t)是p2ij形成的矩陣G中坐標(biāo)(s，t)左上方的元素和。
??? 根據(jù)以上分析，如果能夠找到一種快速計算二維矩陣中坐標(biāo)(s，t)左上方元素和的方法，則必然能夠避免二維相關(guān)準(zhǔn)則算法中點的重復(fù)計算。本文針對二維直方圖P和矩陣G分別進行一次積分迭代操作：
??? 
其中，l(s，t)表示二維直方圖P中縱坐標(biāo)t列元素和；PA(s，t)是二維直方圖P中坐標(biāo)(s，t)左上方的元素和，且l(s，1)=0，PA(-1，t)=0；ls(s，t)表示矩陣G中縱坐標(biāo)小于等于t的列元素和，GA(s，t)表示矩陣G中坐標(biāo)小于等于(s，t)左上方的元素和，且ls(s，1)=0，GA(-1，t)=0。
??? 通過這樣優(yōu)化，該算法可將計算的復(fù)雜性減少到O(L2)，從而大大減少了計算的復(fù)雜性，提高了計算速度。具體實現(xiàn)算法如下：
??? (1)由原始圖像計算各像素點的領(lǐng)域平均灰度值，從而形成二維灰度直方圖。
??? (2)賦初值：
??? max=0，l(s，-1)=0，PA(-1，t)=0，ls(s，-1)=0，GA(-1，t)=0，s∈[0，L]，t∈[0，L]
??? (3)找出最佳閾值向量(S，T)：
??? ①根據(jù)式（9）和式（10）計算矩陣PA(s，t)和GA(s，t)，s∈[0，L]，t∈[0，L]
??? ②按式（2）、（3）計算CA(s，t)和CB(s，t)
??? ③按式（7）計算TC(s，t)
??? if (TC(s，t))>max
?? ?{ max=TC(s，t)；S=s；T=t}
?? ?(4)利用閾值向量(S，T)分割圖像原始圖像，可得分割結(jié)果。
3 實驗結(jié)果與分析
3.1 基準(zhǔn)測試圖像分割實驗
??? 實驗是用Matlab 6.5語言在P42.4GB、內(nèi)存512MB的微機上進行。選用經(jīng)過噪聲污染的Lenna圖像（圖片大小為256×256，灰度級256）進行分割，比較一維最大相關(guān)準(zhǔn)則閾值分割法、二維最大相關(guān)準(zhǔn)則閾值法和本文快速算法的差異，得出實驗分割結(jié)果如圖2所示，它們的圖像分割閾值與運行時間見表1。
?
?
??? 從圖2可以看出，一維最大相關(guān)準(zhǔn)則閾值分割法的分割效果明顯不如二維最大相關(guān)閾值法和本文提出的快速二維最大相關(guān)準(zhǔn)則閾值分割法，有些背景被誤分為目標(biāo)，這主要由于一維最大相關(guān)準(zhǔn)則算法不能完整地反映圖像的局部空間信息。當(dāng)圖像的信噪比減少時，因門限值對噪聲很敏感，所以門限值不好確定，造成圖像分割的穩(wěn)定性和可靠性下降。二維最大相關(guān)準(zhǔn)則法因考慮了圖像的局部空間信息，可以排除一些噪聲的干擾，分割穩(wěn)定性好。
??? 從表1可以看出，一維MCC算法的閾值分割所需時間較少，主要由于閾值搜索空間相對較小，但是分割效果差。二維最大相關(guān)準(zhǔn)則閾值法是二維尋優(yōu)，運用窮盡搜索法獲取最優(yōu)閾值，耗時太長，難以實用。而本文算法和二維MCC算法相比，分割閾值接近最優(yōu)閾值，運算時間可以節(jié)約99%左右。
3.2 真實輪對光截曲線圖像分割實驗
??? 在某車輛段的“線結(jié)構(gòu)光動態(tài)檢測列車輪對外形尺寸”課題研究中，以一幅圖像大小為768×576、灰度級別為256的真實輪對踏面光截曲線圖像為例進行分割實驗，結(jié)果如圖3所示，運行時間如表2所示。
?
?
??? 從圖3(a)可以看出，基于一維最大相關(guān)準(zhǔn)則分割法分割效果差，圖像中仍然存在一些噪聲顆粒，光截曲線不能清晰檢測，不利于后續(xù)處理和測量；對比圖3(a)、圖（b）和圖(c)可以看出，基于二維最大相關(guān)準(zhǔn)則法分割和本文算法分割結(jié)果幾乎相同，分割效果明顯優(yōu)于一維最大相關(guān)準(zhǔn)則閾值分割法，光截曲線檢測清晰。
??? 從表2可以看出，本文算法分割閾值接近二維最大相關(guān)準(zhǔn)則閾值分割算法，運行時間比二維最大相關(guān)準(zhǔn)則算法也節(jié)約99%左右。
??? 二維最大相關(guān)準(zhǔn)則閾值分割法和本文算法不僅考慮了孤立像素點的灰度信息，而且還充分利用了像素的空間鄰域信息，抑制噪聲能力大大加強，分割錯誤明顯減少。利用一種積分和迭代編程技術(shù)快速計算二維最大相關(guān)準(zhǔn)則函數(shù)，大大減少了算法的復(fù)雜度，提高了算法的實用性。實驗結(jié)果表明，本文算法是一種效率高、分割效果好的閾值分割算法，具有較好的應(yīng)用前景。
參考文獻
[1] SEZGIN M.Survey over image thresholding techniques and?quantitative performance evaluation.Journal of Electronic?Image[J].2004，13(1)：146-165.
[2] 韓思奇，王蕾.圖像分割的閾值法綜述.系統(tǒng)工程與電子技術(shù)[J]，2002，24(6)：91-94.
[3] YEN J C，CHANG F J.A new criterion for automatic?multilevel thresholding[J].IEEE Trans on Image rocessing，1995，4(3)：370-378.
[4] 陳修橋，胡以華.二維最大相關(guān)準(zhǔn)則圖像閾值分割遞推算法.計算機工程與應(yīng)用[J]，2005，32：91-93.