基于樣條插值的圖像分割算法研究

程?hào)|旭， 杜婭麗

(中原工學(xué)院, 鄭州 450007)

基于樣條插值的圖像分割算法研究

程?hào)|旭， 杜婭麗

(中原工學(xué)院, 鄭州 450007)

摘要：針對(duì)傳統(tǒng)分割算法中的閾值選擇問(wèn)題，提出了一種改進(jìn)的圖像閾值分割算法。采用樣條插值方法對(duì)圖像的灰度直方圖進(jìn)行曲線擬合，獲得直方圖的曲線表達(dá)。利用函數(shù)極值的特點(diǎn)尋找直方圖曲線的極值點(diǎn)，獲取閾值，對(duì)圖像進(jìn)行閾值分割。實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法獲得的閾值較其他算法有更好的分割效果。

關(guān)鍵詞：閾值分割;直方圖;曲線擬合;樣條插值

圖像分割是圖像處理領(lǐng)域的一個(gè)重要組成部分，分割效果直接影響圖像分析、模式識(shí)別等。圖像分割算法有兩類(lèi)：傳統(tǒng)圖像分割算法和現(xiàn)代圖像分割算法[1]。前者有雙峰法、迭代法、Otsu法等，后者有多種方法，大多數(shù)是將一些特定理論的研究成果運(yùn)用到圖像分割中，如：數(shù)學(xué)形態(tài)學(xué)、遺傳算法理論、模糊理論、小波變換理論等，是針對(duì)特殊的圖像結(jié)合特定的數(shù)學(xué)方法進(jìn)行分割的先進(jìn)圖像分割技術(shù)。

本文在閾值分割算法的基礎(chǔ)上，提出一種基于樣條插值的現(xiàn)代圖像分割算法。首先利用樣條插值擬合圖像的直方圖，獲得直方圖的曲線表達(dá)式；再利用函數(shù)極值的特點(diǎn)尋找直方圖曲線的極值點(diǎn)，獲取閾值，對(duì)圖像進(jìn)行閾值分割。

該方法的特點(diǎn)：①適用于所有具有波峰、波谷的圖像，克服了傳統(tǒng)算法的不足；②根據(jù)閾值多位于直方圖波谷位置的特點(diǎn)，巧妙利用函數(shù)極值的特點(diǎn)尋找直方圖曲線的極值點(diǎn)，獲取閾值；③與傳統(tǒng)的分割方法相比，具有計(jì)算簡(jiǎn)單、運(yùn)算效率高以及速度快等特點(diǎn)，并且所得結(jié)果更加準(zhǔn)確，分割效果更好。

1圖像分割原理與算法

1.1圖像分割基本原理

1.1.1灰度閾值分割方法

灰度閾值分割方法是輸入圖像g到輸出圖像k變換的一種方式，變換表達(dá)式為：

(1)

其中：T為閾值；目標(biāo)物體像素k(i,j)=1；背景像素k(i,j)=0。

上述方法是圖像分割中最常用的算法，具有計(jì)算簡(jiǎn)單、運(yùn)算效率高、速度快等優(yōu)點(diǎn)[2]。其關(guān)鍵是閾值的確定，合適的閾值可準(zhǔn)確地分割圖像。

1.1.2區(qū)域生長(zhǎng)分割方法

區(qū)域生長(zhǎng)算法是集合所有具有相似性質(zhì)的像素構(gòu)成區(qū)域。具體為：找一個(gè)種子像素作為每個(gè)需要分割的區(qū)域生長(zhǎng)的起點(diǎn)；合并種子像素周?chē)c種子像素具有相似或者相同性質(zhì)的像素，形成新的種子像素；繼續(xù)訓(xùn)練這些新像素，直到再也沒(méi)有像素可被合并為止，從而生成一個(gè)區(qū)域[3]。

區(qū)域生長(zhǎng)分割方法的優(yōu)點(diǎn)在于計(jì)算簡(jiǎn)單，對(duì)較均勻的連通目標(biāo)進(jìn)行分割具有較好的效果。它的缺點(diǎn)就是對(duì)噪聲比較敏感，種子點(diǎn)需要人為地加以確定，還有可能會(huì)導(dǎo)致區(qū)域內(nèi)空洞；另外，它是串行算法，當(dāng)需要分割的目標(biāo)比較大時(shí)，分割速度比較慢。

1.2傳統(tǒng)圖像分割算法

1.2.1雙峰法

雙峰法適用于以下圖像中：要分割圖像的灰度直方圖分布比較有規(guī)律；圖像背景和分割目標(biāo)區(qū)域的灰度各自形成一個(gè)波峰，滿足波峰與區(qū)域一一對(duì)應(yīng)。其分離思想為：將對(duì)應(yīng)在雙峰間的波谷處的灰度值作為閾值，即可將圖像背景中有意義的部分分割出來(lái)[4]。

該方法的缺點(diǎn)為：當(dāng)雙峰間出現(xiàn)波谷比較平坦或圖像灰度直方圖波形不明顯等情況時(shí)，使用該方法難以確定閾值，需采用其他方法才能完成閾值選擇。

1.2.2迭代法

迭代法選取閾值的基本思想是利用程序自動(dòng)搜尋最合適的閾值。具體為：初始值T0是圖像灰度的中值，圖像全部的像素被分為前景和背景；將積分后的結(jié)果取平均值作為新的閾值，按此閾值再次將圖像分為前景和背景；反復(fù)迭代下去，直到閾值不再變化為止，將此時(shí)的閾值作為最終的結(jié)果并運(yùn)用于圖像分割[5]。迭代公式如下：

(2)

其中：灰度級(jí)的個(gè)數(shù)為L(zhǎng)；灰度值k的像素點(diǎn)的個(gè)數(shù)為lk。當(dāng)Ti+1=Ti時(shí)，迭代結(jié)束，Ti即為閾值。

1.2.3Otsu法

Otsu法適用于圖像灰度直方圖有雙峰但無(wú)低谷或雙峰與低谷都不明顯的圖像。它將圖像灰度值分成兩類(lèi)，最佳閾值為類(lèi)間方差與類(lèi)內(nèi)方差分離度最大時(shí)的灰度值。

同一區(qū)域具有相似的灰度特性，不同區(qū)域灰度差異明顯，當(dāng)兩個(gè)區(qū)域之間灰度差較大時(shí)，兩個(gè)區(qū)域的平均灰度u1、u2與整個(gè)圖像的平均灰度u之差也較大[6]。

該方法的特點(diǎn)：對(duì)圖像二值化時(shí)準(zhǔn)確而快速，當(dāng)圖像分割目標(biāo)和背景的灰度值差距比較大時(shí)，效果更加明顯。

2基于樣條插值的閾值分割算法

2.1樣條插值

設(shè)在區(qū)間[m,n]內(nèi)插入k-1個(gè)節(jié)點(diǎn)，即:

m=x0

構(gòu)造一個(gè)三次樣條插值函數(shù)g(x)。

已知：

(1)節(jié)點(diǎn)處的函數(shù)值為：

f(xi)=yi(i=0,1,…,k)

(2)三次樣條插值函數(shù)g(x)滿足以下3個(gè)條件：

(a)g(xi)=yi(i=0,1,2,…，k)；

(b)g(x)在每一個(gè)小區(qū)間[xi,xi+1]上是一個(gè)三次多項(xiàng)表達(dá)式；

(c)g(x)∈C2[m,n]。

求解過(guò)程如下：

假設(shè)區(qū)間[m,n]上三次樣條插值函數(shù)g(x)存在，用ji表示g(x)在點(diǎn)xi處的微商，曲線通過(guò)點(diǎn)(xi,yi)(i=0,1,2,…,n)，且在每一個(gè)小區(qū)間[xi,xi+1]上滿足以下條件：

g(xi)=yi, g(xi+1)=yi+1

(3)

g′(xi)=ji, g′(xi+1)=ji+1

(4)

利用Hermite插值公式寫(xiě)出小區(qū)間[xi,xi+1]上的樣條插值函數(shù)g(x)的表達(dá)式：

(5)

但是在節(jié)點(diǎn)xi(i=0,1,2,…,k)上的微商ji未知，如果要用表達(dá)式(5)，必須設(shè)法求出(j0,j1,…,jk)的值。利用函數(shù)g(x)在節(jié)點(diǎn)xi上的二階微商連續(xù)的性質(zhì)，將上述表達(dá)式對(duì)x求微商，同時(shí)令hi=xi+1-x，得到以下表達(dá)式：

(6)

(7)

(9)

令

(10)

在每個(gè)內(nèi)點(diǎn)建立方程，則得到下列方程組:

(1-αi)ji-1+2ji+αiji+1=βi(i=1,2,…,k-1)

(11)

這是關(guān)于未知數(shù)(j0,ji,…,jk)的k-1個(gè)線性方程組。這個(gè)方程組會(huì)有無(wú)窮多個(gè)解，但是實(shí)際問(wèn)題是只能選取一個(gè)特定的解。因此根據(jù)具體情況，補(bǔ)充兩個(gè)附加條件，假設(shè)曲線在兩個(gè)端點(diǎn)處的二階微商已知,

令y″0=y″n=0,或g″(x0)=g″(xk)=0，可得：

(12)

將式(12)與式(11)聯(lián)立，可以解出唯一的未知數(shù)(j0,j1,…,jk)。

將求得的ji代入公式(5)中，求出區(qū)間[xi,xi+1]上的樣條插值函數(shù)g(xi) (i=0,1,2,…,k-1)。

采用樣條插值得出插值函數(shù)，當(dāng)插值節(jié)點(diǎn)加密時(shí)，插值函數(shù)收斂于它本身，其微商收斂于函數(shù)的微商，其結(jié)果比多項(xiàng)式插值得到的結(jié)果更優(yōu)越。從圖1、圖2可以看出，采用該方法得出的擬合曲線與原圖像的直方圖非常接近。

2.2基于三次樣條插值的閾值選取算法

首先，在得到圖像的灰度直方圖的基礎(chǔ)上，為了使圖像灰度值更加具有連續(xù)性，采用三次樣條插值方法擬合圖像灰度曲線，根據(jù)所得到的圖像灰度曲線，找到閾值所在的灰度區(qū)間。這一步主要是為了更加準(zhǔn)確地尋找閾值分割點(diǎn)，縮小閾值所在的區(qū)間范圍。

其次，截取閾值所在區(qū)間，采用三次樣條插值方法有針對(duì)性地再次進(jìn)行曲線擬合。

最后，尋找曲線的極值點(diǎn)。本文主要采用逐步差分的方法來(lái)計(jì)算擬合曲線的極小值點(diǎn)。當(dāng)該點(diǎn)左邊的差值為正，右邊差值為負(fù)的時(shí)候，該點(diǎn)為極小值點(diǎn)，即圖像像素明顯變化的點(diǎn)。用該點(diǎn)作為閾值，將大于該點(diǎn)的像素點(diǎn)設(shè)為1，小于該點(diǎn)的像素點(diǎn)設(shè)為0，從而將圖像分割出來(lái)。

2.3基于三次樣條插值的閾值圖像分割

采用三次樣條插值方法擬合圖像灰度直方圖曲線，找到圖像像素明顯變化的區(qū)域，提取該區(qū)間，再次進(jìn)行三次樣條插值，進(jìn)一步擬合圖像灰度曲線。采用差分的方法找到該區(qū)域的極小值點(diǎn)，確定該極小值點(diǎn)為閾值點(diǎn)。

具體步驟如下：

(1)讀取將要分割的圖像，如果是彩色圖像，先將彩色圖像轉(zhuǎn)化為灰度圖像；

(2)對(duì)圖像進(jìn)行中值濾波，減少噪聲對(duì)圖像分割的影響；

(3)計(jì)算該圖像的灰度值，畫(huà)出圖像的灰度直方圖，如圖1所示。

圖1　圖像灰度直方圖

(4)利用Matlab編程進(jìn)行三次樣條插值擬合，擬合出圖像的灰度曲線，查看圖像灰度曲線的波動(dòng)情況，確定閾值所在的區(qū)間。截取這一區(qū)間，采用三次樣條插值方法有針對(duì)性地再次進(jìn)行曲線擬合。三次樣條插值擬合圖像灰度曲線如圖2所示。

圖2　樣條插值擬合曲線

(5)采用差分的方法尋找曲線的極值點(diǎn)。編寫(xiě)循環(huán)語(yǔ)句，當(dāng)找到滿足條件的點(diǎn)時(shí)，終止程序運(yùn)行，輸出該點(diǎn)的灰度值作為閾值，將圖像的灰度轉(zhuǎn)化到[0,1]之間，從而完成圖像的分割。

2.4實(shí)驗(yàn)結(jié)果

采用經(jīng)典傳統(tǒng)方法中的雙峰法、迭代法、Otsu法分別進(jìn)行圖像分割，與本文采用三次樣條插值方法選取閾值進(jìn)行圖像分割的結(jié)果進(jìn)行對(duì)比(如圖3所示),結(jié)果發(fā)現(xiàn)采用三次樣條插值選取閾值的方法具有很大的優(yōu)越性。

(a)雙峰法　　　　　　　　(b)迭代法

(c)Otsu法　　　　　　　(d)三次樣條插值法圖3　圖像分割結(jié)果對(duì)比

3結(jié)語(yǔ)

經(jīng)過(guò)與經(jīng)典傳統(tǒng)分割方法對(duì)比發(fā)現(xiàn)，三次樣條插

值函數(shù)收斂于函數(shù)本身，而且其微商也收斂于函數(shù)的微商。采用三次樣條插值方法選取閾值更加準(zhǔn)確，分割效果更好，并且計(jì)算簡(jiǎn)單、運(yùn)算效率高、速度快。

綜合本次圖像分割的實(shí)現(xiàn)方法以及分割效果，該分割方法還存在一些不足，如一些參數(shù)設(shè)置不夠優(yōu)化，導(dǎo)致分割效果不是特別理想。隨后的研究可以將算法進(jìn)行優(yōu)化，并結(jié)合其他圖片進(jìn)行分析，將三次樣條插值選取閾值方法做得更加完善。

參考文獻(xiàn):

[1]徐瑞.圖像分割方法及性能評(píng)價(jià)綜述[J].寧波工程學(xué)院學(xué)報(bào),2011,23(3):76-79.

[2]何俊,葛紅,王玉峰.圖像分割算法研究綜述[J].計(jì)算機(jī)工程與科學(xué)，2009,31(12)：58-61.

[3]魏津瑜,施鶴南,蘇思沁.基于改進(jìn)算法的自動(dòng)種子區(qū)域生長(zhǎng)圖像分割[J].中南大學(xué)學(xué)報(bào)(自然科學(xué)版)，2013(s2):311-315.

[4]余松煜，周源華，張瑞.數(shù)字圖像處理[M].上海：上海交通大學(xué)出版社，2007.

[5]陳寧寧.幾種圖像閾值分割算法的實(shí)現(xiàn)與比較[J].人工智能及識(shí)別技術(shù), 2011, 7(13): 3109-3111.

[6]郭永芳,于明,黃凱.基于細(xì)菌趨藥性的Otsu雙閾值圖像分割算法[J].計(jì)算機(jī)工程,2011, 37(22):8-11.

(責(zé)任編輯：席艷君)

Image Segmentation Algorithm Study Based on Spline Interpolation

CHENG Dong-xu, DU Ya-li

(Zhongyuan University of Technology, Zhengzhou 450007, China)

Abstract:In order to solve the threshold selection problem of the traditional segmentation algorithms, an improved spline interpolation algorithm for image segmentation is presented. Firstly, the spline interpolation is used to obtain the image histogram fitting curve. Secondly, the extreme points of the histogram curve is found based on the characteristic of the function extreme and the threshold is obtained. Then, the image is segmented with the threshold. Numerical experiments show that the threshold segmentation obtained by the improved algorithm is better than other algorithms.

Key words:threshold segmentation; histogram; curve fitting;spline interpolation

文章編號(hào)：1671-6906(2015)01-0013-04

作者簡(jiǎn)介：楊艷(1982-)，女，河南濟(jì)源人，碩士，講師。

基金項(xiàng)目：國(guó)家自然科學(xué)基金數(shù)學(xué)天元基金(11326167)；河南省高等學(xué)校重點(diǎn)科研項(xiàng)目(15A110045)

收稿日期：2014-03-21

中圖分類(lèi)號(hào)：TG142.1

文獻(xiàn)標(biāo)志碼：ADOI:10.3969/j.issn.1671-6906.2015.01.003