??? 摘 要: 提出了一種快速二維最大相關(guān)準(zhǔn)則閾值分割算法,。該方法利用積分和迭代編程技術(shù),,避免了數(shù)據(jù)的重復(fù)運(yùn)算,從而將計(jì)算的復(fù)雜性從一般二維最大相關(guān)準(zhǔn)則方法的O(L4)減少至O(L2),。實(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)算簡(jiǎ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í)長(zhǎng),難以實(shí)用,。為了解決這一問(wèn)題,,本文利用積分和迭代編程技術(shù),實(shí)現(xiàn)了算法的簡(jiǎn)化,,減少了計(jì)算復(fù)雜度,,增強(qiáng)了算法的實(shí)用性。
1 二維最大相關(guān)準(zhǔn)則閾值分割
??? 若一幅圖像的灰度級(jí)數(shù)為L(zhǎng),,總的像素點(diǎn)數(shù)為N(m×n),,設(shè)fij為圖像中點(diǎn)灰度為i、區(qū)域灰度均值為j的像素點(diǎn)數(shù),,pij為點(diǎn)灰度-區(qū)域灰度均值對(duì)(i,,j)發(fā)生的概率,,即:
???
其中,N(m×n)為圖像的總像素?cái)?shù),,則pij{i,,j=1…L}就是該圖像關(guān)于點(diǎn)灰度-區(qū)域灰度均值的二維直方圖。
??? 圖1為二維直方圖的xoy平面圖,。沿對(duì)角線分布的A區(qū)和B區(qū)分別代表目標(biāo)類(lèi)和背景類(lèi),,遠(yuǎn)離對(duì)角線的C區(qū)和D區(qū)分別代表邊界和噪聲,所以應(yīng)該在A區(qū)和B區(qū)上利用點(diǎn)灰度-區(qū)域灰度均值,,通過(guò)二維最大法確定最佳閾值,,使真正代表目標(biāo)類(lèi)和背景類(lèi)的相關(guān)數(shù)為最大。這兩類(lèi)的分別被定義為:
???
其中:
???
相關(guān)數(shù)的判別函數(shù)定義為:
2 快速二維最大相關(guān)準(zhǔn)則閾值分割算法
??? 在上述二維最大相關(guān)準(zhǔn)則閾值分割算法中,,對(duì)于每個(gè)(s,,t)對(duì),都要從頭開(kāi)始計(jì)算PA(s,,t)和GA(s,,t),運(yùn)算過(guò)程是一個(gè)四重循環(huán),,計(jì)算復(fù)雜性為O(L4),,計(jì)算比較耗時(shí)。實(shí)際應(yīng)用中,,為了提高運(yùn)算速度,,減少重復(fù)運(yùn)算,需進(jìn)一步優(yōu)化算法,。
??? 從式(2),、式(3)和式(7)可以看出,計(jì)算TC(s,,t)需要計(jì)算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ù)以上分析,如果能夠找到一種快速計(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列元素和;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,。
??? 通過(guò)這樣優(yōu)化,該算法可將計(jì)算的復(fù)雜性減少到O(L2),,從而大大減少了計(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,GA(-1,,t)=0,,s∈[0,L],t∈[0,,L]
??? (3)找出最佳閾值向量(S,,T):
??? ①根據(jù)式(9)和式(10)計(jì)算矩陣PA(s,t)和GA(s,,t),,s∈[0,L],,t∈[0,,L]
??? ②按式(2)、(3)計(jì)算CA(s,,t)和CB(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)測(cè)試圖像分割實(shí)驗(yàn)
??? 實(shí)驗(yàn)是用Matlab 6.5語(yǔ)言在P42.4GB,、內(nèi)存512MB的微機(jī)上進(jìn)行。選用經(jīng)過(guò)噪聲污染的Lenna圖像(圖片大小為256×256,,灰度級(jí)256)進(jìn)行分割,,比較一維最大相關(guān)準(zhǔn)則閾值分割法、二維最大相關(guān)準(zhǔn)則閾值法和本文快速算法的差異,,得出實(shí)驗(yàn)分割結(jié)果如圖2所示,,它們的圖像分割閾值與運(yùn)行時(shí)間見(jiàn)表1。
?
?
??? 從圖2可以看出,,一維最大相關(guān)準(zhǔn)則閾值分割法的分割效果明顯不如二維最大相關(guān)閾值法和本文提出的快速二維最大相關(guān)準(zhǔn)則閾值分割法,,有些背景被誤分為目標(biāo),這主要由于一維最大相關(guān)準(zhǔn)則算法不能完整地反映圖像的局部空間信息,。當(dāng)圖像的信噪比減少時(shí),,因門(mén)限值對(duì)噪聲很敏感,所以門(mén)限值不好確定,,造成圖像分割的穩(wěn)定性和可靠性下降,。二維最大相關(guān)準(zhǔn)則法因考慮了圖像的局部空間信息,可以排除一些噪聲的干擾,,分割穩(wěn)定性好,。
??? 從表1可以看出,,一維MCC算法的閾值分割所需時(shí)間較少,主要由于閾值搜索空間相對(duì)較小,,但是分割效果差,。二維最大相關(guān)準(zhǔn)則閾值法是二維尋優(yōu),運(yùn)用窮盡搜索法獲取最優(yōu)閾值,,耗時(shí)太長(zhǎng),,難以實(shí)用。而本文算法和二維MCC算法相比,,分割閾值接近最優(yōu)閾值,,運(yùn)算時(shí)間可以節(jié)約99%左右。
3.2 真實(shí)輪對(duì)光截曲線圖像分割實(shí)驗(yàn)
??? 在某車(chē)輛段的“線結(jié)構(gòu)光動(dòng)態(tài)檢測(cè)列車(chē)輪對(duì)外形尺寸”課題研究中,,以一幅圖像大小為768×576,、灰度級(jí)別為256的真實(shí)輪對(duì)踏面光截曲線圖像為例進(jìn)行分割實(shí)驗(yàn),結(jié)果如圖3所示,,運(yùn)行時(shí)間如表2所示,。
?
?
??? 從圖3(a)可以看出,基于一維最大相關(guān)準(zhǔn)則分割法分割效果差,,圖像中仍然存在一些噪聲顆粒,,光截曲線不能清晰檢測(cè),不利于后續(xù)處理和測(cè)量,;對(duì)比圖3(a),、圖(b)和圖(c)可以看出,基于二維最大相關(guān)準(zhǔn)則法分割和本文算法分割結(jié)果幾乎相同,,分割效果明顯優(yōu)于一維最大相關(guān)準(zhǔn)則閾值分割法,光截曲線檢測(cè)清晰,。
??? 從表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.