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