基于四叉樹結(jié)構(gòu)的形狀特征檢索*

陳 慧 黃 堃 林 雯 林旭云

(福建江夏學(xué)院 福建福州 350001)

由于海量化的各種圖像數(shù)據(jù)的迅速擴(kuò)張，如何快速、有效地檢索所需要的圖像是當(dāng)前圖像應(yīng)用領(lǐng)域的一個重要挑戰(zhàn)，基于內(nèi)容的圖像檢索是通過提取圖像內(nèi)容的特征作為索引來實現(xiàn)更高層次的圖像檢索[1]。在圖像的諸多內(nèi)容特征中，形狀特征具備了不受目標(biāo)顏色、紋理及背景變化影響的特點(diǎn)，在查詢與目標(biāo)圖像具有類似形狀為主要目的圖像檢索中，顯示出了顏色和紋理特征所無以倫比的優(yōu)勢?；谛螤钐卣鞯膱D像檢索已經(jīng)被廣泛應(yīng)用于許多專業(yè)領(lǐng)域，比如對醫(yī)學(xué)圖像、商標(biāo)和徽標(biāo)圖像、陶瓷工藝圖像和指紋圖像檢索等。目前這些特征提取大多是基于全局匹配的特征提取，強(qiáng)調(diào)整體圖像的特點(diǎn)，忽略局部特征及局部圖像間的空間關(guān)系，利用空間的局部信息來增強(qiáng)全局的形狀特征的圖像檢索算法，不僅可以實現(xiàn)特征間的優(yōu)勢互補(bǔ)，還可以將多種視覺特征有效地整合到圖像檢索系統(tǒng)中，提高圖像檢索的質(zhì)量和性能。

1形狀特征表示方法

在二維的圖像空間中，形狀被認(rèn)為是一個區(qū)域，由一條封閉的輪廓曲線組成。形狀特征的提取必須滿足獨(dú)特性、完整性、幾何變形后的不變性、靈敏度以及抽象性等特點(diǎn)，以下是幾種典型的形狀特征：

1.1 Hu不變矩

矩是一種數(shù)學(xué)表示，可以包含目標(biāo)區(qū)域而不必先分離目標(biāo)。由于低階對量化誤差和噪聲不敏感，它為描述形狀區(qū)域提供了雖不完全卻有用的整體表示[2]。圖像的矩特征是用一個全局量描述描述了整體對象的特點(diǎn)，具有很好的旋轉(zhuǎn)，尺度縮放，平移不變性，是檢索相似的圖片的特征依據(jù)之一。設(shè)F(x，y)是一幅數(shù)字圖像，其(p+q)階矩定義為：

(1)

f(x ,y)的(p+q)階中心矩定義為：

(2)

用圖像的2階和3階規(guī)格化中心矩導(dǎo)出的由7個不變矩組成的不變矩組，稱為Hu不變矩[2]。Hu不變矩具有的良好不變性，已被廣泛應(yīng)用于圖像的識別和檢索中。

1.2信息熵

在數(shù)字圖像中，不同亮度的象素點(diǎn)在空間占據(jù)不同的區(qū)域，使得圖像表現(xiàn)出不同的形狀，用信息熵來描述圖像形狀。給定F(x,y)=0表示單元圖像中背景空白的像素點(diǎn)，F(xiàn)(x,y)=1表示圖像的實際像素點(diǎn)，圖像子塊的信息熵可定義為：

H(p0,p1)=-p0logp0-p1logp1

(3)

p1=∑∑F(xi,yj)/Size(i,j)；p0=1-p1

(4)

p1和p0是從單元圖像中像素點(diǎn)的幾何分布導(dǎo)出的。

對圖像的每個子塊計算其單元熵后，整幅圖像的信息熵特征就可以用一個P×Q維的一維單元熵矢量來表示。

1.3偏心率

偏心率又稱伸長度。偏心率Ec是指軸向的最大和最小的比率，描述圖像區(qū)域的致密性。計算公式如下：

(5)

1.4圓形度

圓形度是定義邊界點(diǎn)的特征量，測量的振幅反映邊界的復(fù)雜性。該值越大，則形狀越復(fù)雜。圓度特性不受地域的平移，旋轉(zhuǎn)和縮放變化。子塊的圓形度特征用ci=ui/σi來表示，ui表示子塊重心至邊界點(diǎn)的平均距離，σi表示重心至邊界點(diǎn)的距離的均方差。

1.5相對位置

相對位置即分塊重心到整幅圖像重心的距離，表示如下：

(6)

2圖像形狀特征的四叉樹表示方法

上述的圖像檢索方法是基于全局匹配檢索，強(qiáng)調(diào)的是全局圖像的特點(diǎn)，忽略圖像的局部特征及局部圖像間的空間關(guān)系。描述的圖像局部特征與空間關(guān)系有兩種方法：一種是自動分割圖像形成區(qū)域，并根據(jù)這些區(qū)域建立索引，另一種是將圖像均勻劃分成若干規(guī)則塊，然后對每個子塊索引的圖像特征提取法。

為了避免圖像進(jìn)行準(zhǔn)確地自動分割的困難，同時又要結(jié)合圖像的空間信息，一種折中的方法是將圖像劃分成多個子塊，然后提取每個子塊的各種特征。常用的方法有四叉樹分塊法，將整幅圖像看成一個四叉樹的結(jié)構(gòu)，逐層進(jìn)行圖像分塊，分別對每個子塊圖像采用相應(yīng)適合的特征描述[3]。圖像形狀特征的四叉樹方法體現(xiàn)為以下3部分：

2.1確定形狀主方向

形狀主方向取決于圖像的形狀特征，由圖像的主軸方向與水平方向的夾角(記為β)決定[2]。主軸方向是指圖像目標(biāo)區(qū)域的最佳橢圓的長軸方向[2]，β是最大的特征值的向量方向，根據(jù)夾角β和三階中心矩確定形狀主方向，比較形狀x>0與x<0兩部分的能量，選擇能量小的部分作為圖像的形狀主方向[3]。

2.2提取目標(biāo)區(qū)域

將圖像的主方向旋轉(zhuǎn)到水平向右(即x軸的正方向)，以重心為原點(diǎn)，以形狀方向為坐標(biāo)系的x軸，與之垂直的方向為y軸建立坐標(biāo)系，以坐標(biāo)(xmin,ymin)為左上角，坐標(biāo)(xmin,ymin)為右下角，構(gòu)成一個最小外接矩形，該最小外接矩形為圖像的目標(biāo)區(qū)域。

2.3 四叉樹分解

以圖像的重心為中心，以水平方向和垂直方向為軸，將圖像分解為4個一級子塊B1～B4[3]，接著用4個分塊圖像的特征對圖像的局部形狀進(jìn)行描述[4]。另外，以相同的方式對每個子塊進(jìn)行分解，進(jìn)而得到16個二級子塊B5～B20。經(jīng)過兩次這樣的分解，可以得到總共20個子塊[2]。以此類推，對每個二級子塊進(jìn)行分解，得到64個三級分塊。將原圖視為第0級子塊，把0～3級子塊加起來，圖像共被分為85個子塊[2]。因此，四叉樹分解法使用的是由粗到細(xì)的逐層分解方式，利用空間局部信息增強(qiáng)全局形狀特征描述，從而可以充分描述圖像的空間分布信息。通過選擇子塊分割的層次，可以實現(xiàn)對子塊數(shù)量的控制，以及對子塊的圖像內(nèi)容描述的精確性的控制[3]。

3基于四叉樹結(jié)構(gòu)的形狀特征檢索算法思想及步驟

3.1四叉樹結(jié)構(gòu)的形狀特征檢索算法的基本思想

四叉樹結(jié)構(gòu)的形狀特征檢索算法的基本思想是：對圖像進(jìn)行分塊，在進(jìn)行子塊分解時采用的是四叉樹分解的方法，每個分塊圖像特征能夠反映圖像的局部特征，而多個子塊的圖像特征反映局部特征之間的空間關(guān)系的有序組合，從而反映圖像的整體特性[4]。

3.2 算法設(shè)計[4]

①計算圖像的形狀主方向，根據(jù)其形狀主方向?qū)D像進(jìn)行旋轉(zhuǎn), 去除圖像旋轉(zhuǎn)帶來的變化。②提取圖像目標(biāo)區(qū)域，并對目標(biāo)區(qū)域進(jìn)行分塊操作。四叉樹結(jié)構(gòu)的方法中定義的目標(biāo)區(qū)域為目標(biāo)像素的水平方向上圖像的最小外接矩形，實現(xiàn)相對簡單。③對圖像分塊，圖像分塊時采用由粗到細(xì)的分層次四叉樹結(jié)構(gòu)，實現(xiàn)多層次的描述。④分別提取分塊圖像的相應(yīng)特征，定義原始圖像為第0塊子塊圖像，對第0塊子塊圖像提取信息熵、偏心率、圓形度和Hu不變矩四個形狀特征，接著對除了第0塊子塊圖像外的其他的子塊圖像分別提取相對位置、信息熵、偏心率和圓形度四個形狀特征。⑤根據(jù)提取的圖像特征，采用歐氏距離[5]計算子塊間的相似度，再通過加權(quán)法計算出總的相似度。設(shè)定待檢圖像T(a)和查詢圖像T(q)，計算兩幅圖像之間的相似程度為：

(7)

其中第k個子塊圖像形狀特征的權(quán)值表示為wk，當(dāng)兩幅圖像相同時，它們的相似性為1。因此兩幅圖像之間的特征距離越大，則圖像的相似度越小。

4實驗結(jié)果及分析

為了測試提出的四叉樹分塊圖像檢索方法的有效性，基于Window平臺上的VisualC++開發(fā)實現(xiàn)該算法。圖像庫的建立分3個步驟完成，首先圖像庫由從網(wǎng)絡(luò)搜索的各種圖像共600幅組成。其次，為了提高圖像檢索效率，需要對圖像進(jìn)行一些預(yù)處理，如轉(zhuǎn)換格式，噪聲過濾等。轉(zhuǎn)換格式的軟件可以將圖像庫中的圖像轉(zhuǎn)換成統(tǒng)一的格式，如bmp位圖格式的圖像源，而噪聲濾波則采用一些有效的濾波算法。最后，確定圖像數(shù)據(jù)庫的存儲位置，所有圖像統(tǒng)一置于操作系統(tǒng)一個共同的文件夾內(nèi)。實驗分為3部分，即幾何變形實驗，尺度和旋轉(zhuǎn)不變性實驗，以及視覺一致性實驗。實驗系統(tǒng)實現(xiàn)本文提出的基于四叉樹分塊的圖像特征檢索算法，并在實驗中采用了多種性能評價方法以驗證實驗的有效性，如體現(xiàn)檢索精度P和檢索回召率R的PVR指數(shù)、用戶參與評價等。

4.1幾何變形實驗

為了研究基于分塊圖像特征的檢索方法對于幾何變形圖像的檢索能力，對原始圖像做多種變形，隨機(jī)從圖像數(shù)據(jù)庫中選擇10個目標(biāo)圖像作為查詢圖像進(jìn)行檢索[5]，圖像編號1～10，分別為設(shè)置圖像旋轉(zhuǎn)100%、圖像旋轉(zhuǎn)-100% ，波紋效果20%、波紋效果-20%、圖像縮放30%、圖像縮放-30%、圖像球形化效果40%、圖像球形化效果-40%、圖像縮放50%、圖像縮放-50% 。檢索結(jié)果的PVR指數(shù)如表1所示。

表1 幾何變形實驗的圖像檢索PVR指數(shù)(%)

顯然，對于變形圖像的檢索能力，四叉樹分塊圖像特征的方法相對于Hu不變矩較令人滿意，平均PVR指數(shù)達(dá)到91.46%，高于Hu不變矩的平均PVR指數(shù)83.30% 。

4.2尺度和旋轉(zhuǎn)不變性實驗

隨機(jī)從圖像數(shù)據(jù)庫中選擇10個目標(biāo)圖像，并對每幅目標(biāo)圖像進(jìn)行多比例圖像縮放和多角度旋轉(zhuǎn)。分別采用基于Hu不變矩的圖像檢索法和基于四叉樹分塊的圖像特征檢索法，在每次檢索時，將目標(biāo)圖像及其相應(yīng)的縮放和旋轉(zhuǎn)圖像都添加到圖像數(shù)據(jù)庫，共同參與圖像檢索[4]。檢索結(jié)果顯示基于Hu不變矩檢索法的平均PVR指數(shù)為98.03%，低于基于四叉樹檢索法的平均PVR指數(shù)99.62%。

4.3視覺一致性實驗

圖像的視覺一致性實驗，是用來驗證圖像的檢索結(jié)果是否符合人的視覺感知，采用用戶參與評價法，即人眼所看到的檢索結(jié)果圖像與要查詢的圖像是否相似。每次從建立的圖像庫中任意選擇一幅圖像作為樣本，檢索結(jié)果將返回前14 幅與樣本圖像相似度最大的圖像，返回的第一幅圖像就是樣本圖像。

圖1給出了五角形圖像的檢索結(jié)果。圖1(a)為基于Hu不變矩的檢索結(jié)果，其中第1, 13和14幅與目標(biāo)圖像相似，圖1(b)為基于四叉

樹分塊的檢索結(jié)果，其中僅第12，13，14幅圖像與目標(biāo)圖像差距明顯，而其它圖像都與目標(biāo)圖像有著不同程度的相似。

4.4結(jié)論

實驗結(jié)果表明，基于四叉樹的分塊檢索方法在以上3個方面的表現(xiàn)都優(yōu)于HU不變矩，可以全面準(zhǔn)確而且多層次的描述圖像的形狀信息和空間分布的信息，可以同時體現(xiàn)圖像的整體形狀和局部形狀，檢索結(jié)果更符合人類視覺感知[4]。

基于四叉樹分塊圖像特征的圖像檢索方法通過利用全局和局部特征，可以更好地描述圖像的內(nèi)容[4]。另外，子塊由粗到細(xì)的分層結(jié)構(gòu)，可用于描述若干層次的圖像的特征的形狀，以提高圖像檢索的性能[2]。因此，該方法對于形狀較明顯的圖像比較適用，對于形狀特征不明顯的圖像，則檢索精度不高。

參考文獻(xiàn)：

[1]黃賽平.基于文本和內(nèi)容的商標(biāo)圖像檢索[D].南京：南京理工大學(xué)，2008.11.

[2]楊青燕.基于內(nèi)容的商標(biāo)圖像檢索研究與實現(xiàn)[D].濟(jì)南：山東科技大學(xué)，2009.13.

[3]張玲.商標(biāo)圖像檢索研究與系統(tǒng)實現(xiàn)[D].長沙：湖南大學(xué)，2006.6.

[4]郭麗.基于內(nèi)容的商標(biāo)圖像檢索研究南京：南京理工大學(xué)，2003.2.

[5]褚菁菁.基于內(nèi)容的二值商標(biāo)圖像檢索技術(shù)研究[D].鄭州：河南大學(xué)，2011.5.