??? 摘 要： 提出了一種快速二維最大相關(guān)準(zhǔn)則閾值分割算法。該方法利用積分和迭代編程技術(shù)，避免了數(shù)據(jù)的重復(fù)運(yùn)算，從而將計(jì)算的復(fù)雜性從一般二維最大相關(guān)準(zhǔn)則方法的O(L⁴)減少至O(L²)。實(shí)驗(yàn)結(jié)果表明，該方法分割效果好，計(jì)算效率高，適合實(shí)時(shí)圖像系統(tǒng)的應(yīng)用。
??? 關(guān)鍵詞： 閾值分割；最大相關(guān)準(zhǔn)則；快速算法

?

??? 閾值化是圖像分割中一項(xiàng)重要的技術(shù)^[1]。常用的閾值分割方法有：直方圖雙峰法、最大熵法、矩量保持法、梯度統(tǒng)計(jì)法、一維最大相關(guān)準(zhǔn)則法^[2]，以及這些方法在二維上的推廣化方法。這些方法中，一維最大相關(guān)準(zhǔn)則以其運(yùn)算簡單、分割效果好、適用范圍廣而得到廣泛應(yīng)用。
??? 一維最大相關(guān)準(zhǔn)則法由Yen^[3]等人提出。該方法以圖像的一維直方圖為依據(jù)，以目標(biāo)和背景的相關(guān)總量為最大選擇閾值，在多數(shù)情況下能取得很好的閾值。但在實(shí)際應(yīng)用中，當(dāng)圖像信噪比降低時(shí)，應(yīng)用一維最大相關(guān)法將產(chǎn)生很多分割錯(cuò)誤。為此，2005年陳修橋^[4]等人將一維最大相關(guān)法(MCC)推廣到二維。二維最大相關(guān)法應(yīng)用二維直方圖，不僅反映了灰度分布信息，還反映了鄰域空間相關(guān)信息，使分割效果得到了明顯改善。但其計(jì)算量大、耗時(shí)長，難以實(shí)用。為了解決這一問題，本文利用積分和迭代編程技術(shù)，實(shí)現(xiàn)了算法的簡化，減少了計(jì)算復(fù)雜度，增強(qiáng)了算法的實(shí)用性。
1 二維最大相關(guān)準(zhǔn)則閾值分割
??? 若一幅圖像的灰度級(jí)數(shù)為L，總的像素點(diǎn)數(shù)為N(m×n)，設(shè)f_ij為圖像中點(diǎn)灰度為i、區(qū)域灰度均值為j的像素點(diǎn)數(shù)，p_ij為點(diǎn)灰度-區(qū)域灰度均值對(duì)(i，j)發(fā)生的概率，即：
???
其中，N（m×n）為圖像的總像素?cái)?shù)，則p_ij{i，j=1…L}就是該圖像關(guān)于點(diǎn)灰度－區(qū)域灰度均值的二維直方圖。
??? 圖1為二維直方圖的xoy平面圖。沿對(duì)角線分布的A區(qū)和B區(qū)分別代表目標(biāo)類和背景類，遠(yuǎn)離對(duì)角線的C區(qū)和D區(qū)分別代表邊界和噪聲，所以應(yīng)該在A區(qū)和B區(qū)上利用點(diǎn)灰度－區(qū)域灰度均值，通過二維最大法確定最佳閾值，使真正代表目標(biāo)類和背景類的相關(guān)數(shù)為最大。這兩類的分別被定義為：
???
其中：
???
相關(guān)數(shù)的判別函數(shù)定義為：

2 快速二維最大相關(guān)準(zhǔn)則閾值分割算法
??? 在上述二維最大相關(guān)準(zhǔn)則閾值分割算法中，對(duì)于每個(gè)(s，t)對(duì)，都要從頭開始計(jì)算P_A(s，t)和G_A(s，t)，運(yùn)算過程是一個(gè)四重循環(huán)，計(jì)算復(fù)雜性為O(L⁴)，計(jì)算比較耗時(shí)。實(shí)際應(yīng)用中，為了提高運(yùn)算速度，減少重復(fù)運(yùn)算，需進(jìn)一步優(yōu)化算法。
??? 從式（2）、式（3）和式（7）可以看出，計(jì)算TC(s，t)需要計(jì)算P_A(s，t)、G_A(s，t)和G_L。而G_L恒定，P_A(s，t)是二維直方圖P中坐標(biāo)(s，t)左上方的元素和，G_A(s，t)是p²_ij形成的矩陣G中坐標(biāo)(s，t)左上方的元素和。
??? 根據(jù)以上分析，如果能夠找到一種快速計(jì)算二維矩陣中坐標(biāo)(s，t)左上方元素和的方法，則必然能夠避免二維相關(guān)準(zhǔn)則算法中點(diǎn)的重復(fù)計(jì)算。本文針對(duì)二維直方圖P和矩陣G分別進(jìn)行一次積分迭代操作：
???
其中，l(s，t)表示二維直方圖P中縱坐標(biāo)t列元素和；P_A(s，t)是二維直方圖P中坐標(biāo)(s，t)左上方的元素和，且l(s，1)=0，P_A(-1，t)=0；ls(s，t)表示矩陣G中縱坐標(biāo)小于等于t的列元素和，G_A(s，t)表示矩陣G中坐標(biāo)小于等于(s，t)左上方的元素和，且ls(s，1)=0，G_A(-1，t)=0。
??? 通過這樣優(yōu)化，該算法可將計(jì)算的復(fù)雜性減少到O(L²)，從而大大減少了計(jì)算的復(fù)雜性，提高了計(jì)算速度。具體實(shí)現(xiàn)算法如下：
??? (1)由原始圖像計(jì)算各像素點(diǎn)的領(lǐng)域平均灰度值，從而形成二維灰度直方圖。
??? (2)賦初值：
??? max=0，l(s，-1)=0，PA(-1，t)=0，ls(s，-1)=0，G_A(-1，t)=0，s∈[0，L]，t∈[0，L]
??? (3)找出最佳閾值向量(S，T)：
??? ①根據(jù)式（9）和式（10）計(jì)算矩陣P_A(s，t)和G_A(s，t)，s∈[0，L]，t∈[0，L]
??? ②按式（2）、（3）計(jì)算C_A(s，t)和C_B(s，t)
??? ③按式（7）計(jì)算TC(s，t)
??? if (TC(s，t))>max
?? ?{ max=TC(s，t)；S=s；T=t}
?? ?(4)利用閾值向量(S，T)分割圖像原始圖像，可得分割結(jié)果。
3 實(shí)驗(yàn)結(jié)果與分析
3.1 基準(zhǔn)測試圖像分割實(shí)驗(yàn)
??? 實(shí)驗(yàn)是用Matlab 6.5語言在P42.4GB、內(nèi)存512MB的微機(jī)上進(jìn)行。選用經(jīng)過噪聲污染的Lenna圖像（圖片大小為256×256，灰度級(jí)256）進(jìn)行分割，比較一維最大相關(guān)準(zhǔn)則閾值分割法、二維最大相關(guān)準(zhǔn)則閾值法和本文快速算法的差異，得出實(shí)驗(yàn)分割結(jié)果如圖2所示，它們的圖像分割閾值與運(yùn)行時(shí)間見表1。

?

?

??? 從圖3(a)可以看出，基于一維最大相關(guān)準(zhǔn)則分割法分割效果差，圖像中仍然存在一些噪聲顆粒，光截曲線不能清晰檢測，不利于后續(xù)處理和測量；對(duì)比圖3(a)、圖（b）和圖(c)可以看出，基于二維最大相關(guān)準(zhǔn)則法分割和本文算法分割結(jié)果幾乎相同，分割效果明顯優(yōu)于一維最大相關(guān)準(zhǔn)則閾值分割法，光截曲線檢測清晰。
??? 從表2可以看出，本文算法分割閾值接近二維最大相關(guān)準(zhǔn)則閾值分割算法，運(yùn)行時(shí)間比二維最大相關(guān)準(zhǔn)則算法也節(jié)約99%左右。
??? 二維最大相關(guān)準(zhǔn)則閾值分割法和本文算法不僅考慮了孤立像素點(diǎn)的灰度信息，而且還充分利用了像素的空間鄰域信息，抑制噪聲能力大大加強(qiáng)，分割錯(cuò)誤明顯減少。利用一種積分和迭代編程技術(shù)快速計(jì)算二維最大相關(guān)準(zhǔn)則函數(shù)，大大減少了算法的復(fù)雜度，提高了算法的實(shí)用性。實(shí)驗(yàn)結(jié)果表明，本文算法是一種效率高、分割效果好的閾值分割算法，具有較好的應(yīng)用前景。
參考文獻(xiàn)
[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)則圖像閾值分割遞推算法.計(jì)算機(jī)工程與應(yīng)用[J]，2005，32：91-93.