【摘要】 傳統(tǒng)的二維Otsu閾值分割算法采用窮舉搜索法搜尋閾值向量。與此不同，本文提出了一種二維類間方差閾值分割的快速迭代算法，用迭代的思想解決原始二維Otsu方法計(jì)算復(fù)雜、實(shí)時(shí)性差的問題。文中導(dǎo)出了迭代算法的公式，給出了算法流程。實(shí)驗(yàn)結(jié)果表明，與二維Otsu原始算法及其他兩種快速算法相比較，本文提出的二維Otsu快速迭代算法分割結(jié)果準(zhǔn)確，實(shí)現(xiàn)簡(jiǎn)單，其運(yùn)行時(shí)間僅為原始算法的0.4%左右，大大減少了計(jì)算量和存儲(chǔ)空間，是一種快速有效且實(shí)時(shí)性好的圖像閾值分割算法。
【關(guān)鍵詞】 圖像分割； 二維類間方差； Otsu閾值； 快速迭*試大http:/
A fast iterative algorithm for image segmentation based on 2D
maximum betweencluster varianceWU Yiquan, WU Wenyi, PAN Zhe
（College of Information Science and Technology, Nanjing University of Aeronautics and Astronautics,Jiangsu Nanjing 210016, China）
Abstract: The traditional twodimensional (2D) Otsu threshold algorithms for image segmentation always use exhaustive searching method for the best thresholds. In this paper, a fast iterative algorithm based on 2D maximum betweencluster variance is proposed in order to improve the performance and efficiency of the original 2D Otsu threshold algorithms. The iterative formula is deduced and the algorithm flow chart is given in the paper. Experimental results show that the proposed algorithm has a good segmentation result compared to the original 2D Otsu algorithm and the other two fast methods. It can well reduce the storage space and the running time which is only 0.4% of that of the original method. Therefore, it is a fast and effective image segmentation algorithm with a good realtime quality.
Key words: image segmentation; 2D maximum betweencluster variance; Otsu threshold; fast iterative
引言來源：考試大
圖像分割是圖像處理和前期視覺中的基本技術(shù)，也是大多數(shù)圖像分析及視覺系統(tǒng)的重要組成部分，分割質(zhì)量直接影響著后續(xù)處理的結(jié)果。閾值分割是普遍使用的最為有效的圖像分割方法，它實(shí)質(zhì)上歸結(jié)為閾值的選取。針對(duì)這一問題國(guó)內(nèi)外學(xué)者進(jìn)行了大量的研究，提出了多種閾值選取方法［1,2］。在諸多閾值選取方法中，由Otsu（即大津展之）于1978年提出的一維類間方差法，以其分割效果較好、適用范圍較廣、簡(jiǎn)單有效而引起人們普遍關(guān)注，且應(yīng)用最為廣泛。該方法基于類別可分離性，根據(jù)圖像的一維灰度直方圖，用窮舉搜索法選取一個(gè)閾值使得類間方差。1984年Reddi等［3］針對(duì)Otsu的方法，不采用原始的窮舉搜索法，通過假定一維灰度直方圖為連續(xù)的概率密度函數(shù)，提出了一種快速搜尋迭代法——最陡上升法。這種算法速度非?？欤阅芎?，一般只需6～20次迭代即可收斂到閾值。一維Otsu算法雖然處理速度快，在圖像質(zhì)量較好和背景穩(wěn)定變化的情況下，可以取得令人滿意的效果，但是，由于圖像的一維灰度直方圖僅反映了圖像的灰度分布，并不能反映圖像像素之間的空間相關(guān)信息，當(dāng)圖像的信噪比較低或受到光照不均勻等因素影響時(shí)，該方法的分割效果就不太令人滿意，甚至產(chǎn)生分割錯(cuò)誤。
為此，1993年劉建莊［4］借助Abutaleb等［5］的二維直方圖的思想，利用像素的灰度級(jí)分布和鄰域的平均灰度級(jí)分布所構(gòu)成的直方圖來進(jìn)行閾值分割。由于二維灰度直方圖同時(shí)考慮了圖像的灰度級(jí)信息和空間鄰域信息，因此二維類間方差閾值分割方法的分割效果比相應(yīng)的一維方法有明顯改善。但同時(shí)由于將一維搜索空間擴(kuò)大到二維，加上變成二維算法后本身的復(fù)雜性，導(dǎo)致運(yùn)算量按指數(shù)增加，運(yùn)行時(shí)間長(zhǎng)，所需存儲(chǔ)空間大，實(shí)時(shí)性較差，從而限制了二維類間方差閾值分割方法的適用范圍。
為了降低計(jì)算量，1998年龔堅(jiān)等［6］從減少重復(fù)計(jì)算的觀點(diǎn)出發(fā)，提出二維Otsu的一種快速遞推算法［7］。2005年郝穎明等［8］在改變二維直方圖區(qū)域劃分的基礎(chǔ)上，提出通過將二維閾值轉(zhuǎn)換成一維閾值的快速算法。這兩種快速算法都能不同程度地節(jié)省計(jì)算時(shí)間，提高運(yùn)行速度，但搜尋閾值實(shí)質(zhì)上仍然采用的是窮舉搜索法。與此不同，本文將Reddi的一維類間方差閾值分割的快速迭代法推廣到二維，提出了一種二維類間方差閾值選取的快速迭代算法，用迭代的思想解決了原始二維方法計(jì)算復(fù)雜、實(shí)時(shí)性差的問題。文中導(dǎo)出了二維類間方差閾值分割迭代算法的公式，給出了分割結(jié)果和運(yùn)行時(shí)間，并與二維Otsu原始算法及其他兩種快速算法的運(yùn)行時(shí)間進(jìn)行了比較。
1 二維直方圖
設(shè)圖像的尺寸為M×N，圖像灰度級(jí)取為0,1,…,L－1。如果用集合Z表示這L個(gè)灰度級(jí)，則Z={z0|z0∈(0,L－1)}。顯然，圖像中坐標(biāo)(m,n)的像素點(diǎn)的灰度級(jí)f(m,n)為集合中的某一值，即f(m,n)∈Z。定義坐標(biāo)(m,n)的像素點(diǎn)的鄰域平均灰度級(jí)g(m,n)如下g(m,n)
=1W×W(W－1)/2i=－(W－1)/2(W－1)/2j=－(W－1)/2f(m+i,n+j)，
(1)這里W為像素點(diǎn)f(m,n)的正方形鄰域窗口的寬度，一般取奇數(shù)。對(duì)于g(m,n)，顯然有0≤g(m,n)≤L－1。因此鄰域平均灰度級(jí)g(m,n)與圖像f(m,n)具有同樣的灰度變化范圍。
對(duì)于一幅M×N的圖像f(m,n)，當(dāng)采用［f(m,n),g(m,n)］的向量表示方式時(shí)，我們定義并計(jì)算其二維直方圖。該二維直方圖定義在一個(gè)L×L大小的正方形區(qū)域，其橫坐標(biāo)表示圖像像素的灰度級(jí)，縱坐標(biāo)表示像素的鄰域平均灰度級(jí)。直方圖任意一點(diǎn)的值定義為pij，它表示向量(i,j)發(fā)生的頻率，這里向量(i,j)表示［f(m,n),g(m,n)］，且0≤i,j≤L－1。若用cij表示向量(i,j)發(fā)生的頻數(shù)，那么向量(i,j)發(fā)生的頻率pij由下式確定pij=cijM×N，(2)其中0≤i,j≤L－1，并且L－1i=0 L－1j=0pij=1。
若以二維向量(t,s)作為閾值來分割圖像，t為像素灰度級(jí)閾值，s代表鄰域平均灰度級(jí)閾值，則圖像的二維直方圖的定義域可被分為四個(gè)區(qū)域，如圖1所示。假設(shè)圖像的背景灰度級(jí)高于目標(biāo)灰度級(jí)，則區(qū)域0和區(qū)域1中像素的灰度級(jí)與鄰域平均灰度級(jí)基本接近，其分別對(duì)應(yīng)于目標(biāo)內(nèi)部和背景內(nèi)部，而區(qū)域2和區(qū)域3處像素的灰度級(jí)與鄰域平均灰度級(jí)相差較大，對(duì)應(yīng)目標(biāo)和背景之間的邊界像素和圖像的噪聲點(diǎn)分布。多數(shù)情況下，區(qū)域邊界附近的像素?cái)?shù)與整幅圖像的像素?cái)?shù)比較，數(shù)量很少，因此按照慣例可以假設(shè)區(qū)域2和區(qū)域3上的pij≈0。一般情況下pij≠0的統(tǒng)計(jì)值為：0.98～0.95。
【關(guān)鍵詞】 圖像分割； 二維類間方差； Otsu閾值； 快速迭*試大http:/
A fast iterative algorithm for image segmentation based on 2D
maximum betweencluster varianceWU Yiquan, WU Wenyi, PAN Zhe
（College of Information Science and Technology, Nanjing University of Aeronautics and Astronautics,Jiangsu Nanjing 210016, China）
Abstract: The traditional twodimensional (2D) Otsu threshold algorithms for image segmentation always use exhaustive searching method for the best thresholds. In this paper, a fast iterative algorithm based on 2D maximum betweencluster variance is proposed in order to improve the performance and efficiency of the original 2D Otsu threshold algorithms. The iterative formula is deduced and the algorithm flow chart is given in the paper. Experimental results show that the proposed algorithm has a good segmentation result compared to the original 2D Otsu algorithm and the other two fast methods. It can well reduce the storage space and the running time which is only 0.4% of that of the original method. Therefore, it is a fast and effective image segmentation algorithm with a good realtime quality.
Key words: image segmentation; 2D maximum betweencluster variance; Otsu threshold; fast iterative
引言來源：考試大
圖像分割是圖像處理和前期視覺中的基本技術(shù)，也是大多數(shù)圖像分析及視覺系統(tǒng)的重要組成部分，分割質(zhì)量直接影響著后續(xù)處理的結(jié)果。閾值分割是普遍使用的最為有效的圖像分割方法，它實(shí)質(zhì)上歸結(jié)為閾值的選取。針對(duì)這一問題國(guó)內(nèi)外學(xué)者進(jìn)行了大量的研究，提出了多種閾值選取方法［1,2］。在諸多閾值選取方法中，由Otsu（即大津展之）于1978年提出的一維類間方差法，以其分割效果較好、適用范圍較廣、簡(jiǎn)單有效而引起人們普遍關(guān)注，且應(yīng)用最為廣泛。該方法基于類別可分離性，根據(jù)圖像的一維灰度直方圖，用窮舉搜索法選取一個(gè)閾值使得類間方差。1984年Reddi等［3］針對(duì)Otsu的方法，不采用原始的窮舉搜索法，通過假定一維灰度直方圖為連續(xù)的概率密度函數(shù)，提出了一種快速搜尋迭代法——最陡上升法。這種算法速度非?？欤阅芎?，一般只需6～20次迭代即可收斂到閾值。一維Otsu算法雖然處理速度快，在圖像質(zhì)量較好和背景穩(wěn)定變化的情況下，可以取得令人滿意的效果，但是，由于圖像的一維灰度直方圖僅反映了圖像的灰度分布，并不能反映圖像像素之間的空間相關(guān)信息，當(dāng)圖像的信噪比較低或受到光照不均勻等因素影響時(shí)，該方法的分割效果就不太令人滿意，甚至產(chǎn)生分割錯(cuò)誤。
為此，1993年劉建莊［4］借助Abutaleb等［5］的二維直方圖的思想，利用像素的灰度級(jí)分布和鄰域的平均灰度級(jí)分布所構(gòu)成的直方圖來進(jìn)行閾值分割。由于二維灰度直方圖同時(shí)考慮了圖像的灰度級(jí)信息和空間鄰域信息，因此二維類間方差閾值分割方法的分割效果比相應(yīng)的一維方法有明顯改善。但同時(shí)由于將一維搜索空間擴(kuò)大到二維，加上變成二維算法后本身的復(fù)雜性，導(dǎo)致運(yùn)算量按指數(shù)增加，運(yùn)行時(shí)間長(zhǎng)，所需存儲(chǔ)空間大，實(shí)時(shí)性較差，從而限制了二維類間方差閾值分割方法的適用范圍。
為了降低計(jì)算量，1998年龔堅(jiān)等［6］從減少重復(fù)計(jì)算的觀點(diǎn)出發(fā)，提出二維Otsu的一種快速遞推算法［7］。2005年郝穎明等［8］在改變二維直方圖區(qū)域劃分的基礎(chǔ)上，提出通過將二維閾值轉(zhuǎn)換成一維閾值的快速算法。這兩種快速算法都能不同程度地節(jié)省計(jì)算時(shí)間，提高運(yùn)行速度，但搜尋閾值實(shí)質(zhì)上仍然采用的是窮舉搜索法。與此不同，本文將Reddi的一維類間方差閾值分割的快速迭代法推廣到二維，提出了一種二維類間方差閾值選取的快速迭代算法，用迭代的思想解決了原始二維方法計(jì)算復(fù)雜、實(shí)時(shí)性差的問題。文中導(dǎo)出了二維類間方差閾值分割迭代算法的公式，給出了分割結(jié)果和運(yùn)行時(shí)間，并與二維Otsu原始算法及其他兩種快速算法的運(yùn)行時(shí)間進(jìn)行了比較。
1 二維直方圖
設(shè)圖像的尺寸為M×N，圖像灰度級(jí)取為0,1,…,L－1。如果用集合Z表示這L個(gè)灰度級(jí)，則Z={z0|z0∈(0,L－1)}。顯然，圖像中坐標(biāo)(m,n)的像素點(diǎn)的灰度級(jí)f(m,n)為集合中的某一值，即f(m,n)∈Z。定義坐標(biāo)(m,n)的像素點(diǎn)的鄰域平均灰度級(jí)g(m,n)如下g(m,n)
=1W×W(W－1)/2i=－(W－1)/2(W－1)/2j=－(W－1)/2f(m+i,n+j)，
(1)這里W為像素點(diǎn)f(m,n)的正方形鄰域窗口的寬度，一般取奇數(shù)。對(duì)于g(m,n)，顯然有0≤g(m,n)≤L－1。因此鄰域平均灰度級(jí)g(m,n)與圖像f(m,n)具有同樣的灰度變化范圍。
對(duì)于一幅M×N的圖像f(m,n)，當(dāng)采用［f(m,n),g(m,n)］的向量表示方式時(shí)，我們定義并計(jì)算其二維直方圖。該二維直方圖定義在一個(gè)L×L大小的正方形區(qū)域，其橫坐標(biāo)表示圖像像素的灰度級(jí)，縱坐標(biāo)表示像素的鄰域平均灰度級(jí)。直方圖任意一點(diǎn)的值定義為pij，它表示向量(i,j)發(fā)生的頻率，這里向量(i,j)表示［f(m,n),g(m,n)］，且0≤i,j≤L－1。若用cij表示向量(i,j)發(fā)生的頻數(shù)，那么向量(i,j)發(fā)生的頻率pij由下式確定pij=cijM×N，(2)其中0≤i,j≤L－1，并且L－1i=0 L－1j=0pij=1。
若以二維向量(t,s)作為閾值來分割圖像，t為像素灰度級(jí)閾值，s代表鄰域平均灰度級(jí)閾值，則圖像的二維直方圖的定義域可被分為四個(gè)區(qū)域，如圖1所示。假設(shè)圖像的背景灰度級(jí)高于目標(biāo)灰度級(jí)，則區(qū)域0和區(qū)域1中像素的灰度級(jí)與鄰域平均灰度級(jí)基本接近，其分別對(duì)應(yīng)于目標(biāo)內(nèi)部和背景內(nèi)部，而區(qū)域2和區(qū)域3處像素的灰度級(jí)與鄰域平均灰度級(jí)相差較大，對(duì)應(yīng)目標(biāo)和背景之間的邊界像素和圖像的噪聲點(diǎn)分布。多數(shù)情況下，區(qū)域邊界附近的像素?cái)?shù)與整幅圖像的像素?cái)?shù)比較，數(shù)量很少，因此按照慣例可以假設(shè)區(qū)域2和區(qū)域3上的pij≈0。一般情況下pij≠0的統(tǒng)計(jì)值為：0.98～0.95。