應(yīng)用粗糙集理論實現(xiàn)基于對象的圖像檢索

摘要:粗糙集理論已經(jīng)成功應(yīng)用于許多領(lǐng)域，特別是數(shù)據(jù)挖掘、知識發(fā)現(xiàn)、人工智能和信息系統(tǒng)分析。在粗糙集理論背景下，對圖像進(jìn)行建模，用集合的上下近似表示圖像對象。通過定義新的圖像相似度計算“Object Similarity Ratio”，介紹一種精確的基于對象的圖像檢索方法，它可以處理基于例圖的查詢，并且介紹了一種高效的大型圖像庫檢索算法。

關(guān)鍵詞:粗糙集理論;相似度;圖像檢索;圖像建模;Object Similarity Ratio

中圖分類號:TP391文獻(xiàn)標(biāo)識碼:A文章編號:1009-3044(2010)05-1176-03

Achieving Object-based Image Retrieval by Rough Set Theory

JIA Ning， LUO Yang

(Department of Computer Science and Technology， USC， Hengyang 421001， China)

Abstract: The rough set theory has been applied in diverse areas of research， especially in data mining， knowledge discovery， artificial intelligence and information systems analysis. In the context of rough set theory， modeling for images， describing images using upper and lower approximations of set. Introduced an accurate Object-based image retrieval method which can handle image-based queries by defining a novel image similarity measure called Object Similarity Ratio， and presented an efficient retrieval algorithm from large image database.

Key words: rough set theory; similarity; image retrieval; image model; object similarity ratio

隨著圖像獲取技術(shù)的飛速發(fā)展，許多領(lǐng)域都出現(xiàn)了大型的圖像數(shù)據(jù)庫。在大量的實際應(yīng)用中，用戶希望在這些圖像庫中快速有效地檢索圖像，但是又缺少對所有這些圖像的語義標(biāo)簽，從而很難達(dá)到理想的效果。由于缺乏廣泛使用的統(tǒng)一標(biāo)準(zhǔn)，應(yīng)用關(guān)鍵字并不能全面的描述圖像。這樣，基于內(nèi)容的圖像檢索[1]就應(yīng)運而生。當(dāng)用戶希望檢索圖像時，不再需要對圖像庫中的圖像以及查詢圖像進(jìn)行文本描述，只需輸入查詢圖像，便可以依靠檢索系統(tǒng)得到理想的相似圖像。

大多數(shù)基于內(nèi)容的圖像檢索技術(shù)自動提取圖像底層特征，如顏色、紋理、形狀和空間布局等，然后根據(jù)特征向量空間計算兩幅圖像間的相似性，進(jìn)而完成檢索圖像的工作。但是，圖像底層特征和高層語義之間存在著巨大的“語義鴻溝”[2]，導(dǎo)致了檢索效果并不能很好的滿足用戶要求。因此，許多研究者開始關(guān)注縮減“語義鴻溝”的研究， 提出了眾多的解決方法，應(yīng)用粗糙集理論實現(xiàn)基于圖像對象的檢索便是其中的一種。

在粗糙集理論背景下實現(xiàn)基于圖像對象的檢索方法，對圖像庫和查詢圖像有一定的要求限制。該方法應(yīng)用于具有單個中心對象的圖像，期望輸出則是包含跟查詢圖像最相似對象的圖像，這個對象可以不同的大小分布在不同位置的位置，也就是說，對對象的尺寸、偏移和旋轉(zhuǎn)變化具有健壯性。

該方法主要依賴圖像中物理對象的表征檢索圖像，物理對象可以是任何用戶希望查找的對象，比如建筑物，直升機(jī)，大象等，但是須滿足以下條件:1)基本上位于圖像的中心;2)相對于背景，有顯著地顏色或紋理特征;3)尺寸相對較大;4)邊緣像素相對較銳利。

1 粗糙集預(yù)備知識

粗糙集作為一種處理不精確、不確定與不完全數(shù)據(jù)的數(shù)學(xué)理論，最初是由波蘭數(shù)學(xué)家Z Paw lak[3]在1982年提出的，它是建立在分類機(jī)制基礎(chǔ)上，將分類理解為在特征空間上的等價關(guān)系，而等價關(guān)系構(gòu)成了對該空的劃分。粗糙集中的知識表達(dá)方式一般采用信息表或稱為信息系統(tǒng)的形式。一個信息系統(tǒng)S=(U，A)，U是一個非空有限的對象集合，稱為全集，A為一個非空有限的屬性集合。令B?哿A，X?哿U，通過建立集合X的上下近似，僅用包含在B中的信息來表示集合X。

如果X?哿U，集合{x∈U:[x]B }，{ x∈U: [x]B∩X≠Ф}，分別稱為X在U中B-下近似和B-上近似，分別用BX和BX表示，[x]B是對象x∈U的等價關(guān)系IB的等價類。在BX中的對象可以確定地分類為在B中的x成員，在BX中的對象只能分類為B的可能成員。

集合X對于B的粗糙性測度定義為:

Rα=1-|BX| / |BX||

0≤Rα≤1，等于0時，X對于B可定義的;Rα>0時，X是粗糙的。集合的粗糙表示方法可以用圖1來描述，其中曲線包含的區(qū)域表示集合X，深灰色區(qū)域表示下近似，所有的灰色區(qū)域表示上近似。

2 圖像建模

令論域U為包含像素點集合的圖像。然后，如果將U分成大小為m×n不重疊的子窗體集合，每個子窗體可被看成是一個粒點G，每個粒點都是像素的簇。

考慮灰度級為L(0，1，...，T，T+1，...，L-1)的圖像(m×n)中背景和對象的分離問題。設(shè)B和O分別代表兩種屬性:背景區(qū)域，對象區(qū)域。對象和背景可以看成是兩個關(guān)于T的粗糙集[4]:

對象的下近似

對象的上近似

背景的下近似

背景的上近似。因此，圖像的粗糙集表示(對象OT和背景BT)取決于灰度級T的值。

集合的不精確性是因為邊界的存在，而邊界又由上近似和下近似的區(qū)別引起的，所以對象OT的粗糙性測度可表示為:

其中|OT|和|OT|是OT和OT的基數(shù)。

相似地，背景BT的粗糙性測度可表示為:

其中|BT|和|BT|是BT和BT的基數(shù)。

現(xiàn)在，為一幅圖像定義一個稱為“平均粗糙性測度計算”RMT，當(dāng)取某個特定的T值時，ROT和RBT的平均值，

(3)

由(1)和(2)可知，由于0≤ROT≤1，0≤RBT≤1，所以RMT∈[0，1]。當(dāng)ROT=RBT=1時，RMT有最大值。ROT=RBT=0時，RMT有最小值。

對不同的大小的粒點，通過最小化RMT原則，得到以分割為基礎(chǔ)的對象提取方法。RMT的最小化就是最小化由對象邊界區(qū)域的模糊性引起的不確定性。因此，對一個既定的粒點，對象—背景分離的閾值可以通過最小化RMT獲得。計算相對于圖像每個灰度級T的RMT值，(0，…，T)代表背景，(T+1，…，L-1)代表對象區(qū)域。選擇使RMT最小的T，即選擇T*=arg inRMT作為閾值，由T*提供對象—背景的分離。

3 相似度計算和檢索算法

3.1 相似度計算

為了檢索跟查詢圖像相似的圖像，需要計算圖像的相似度。首先由用戶輸入查詢圖像，為提取出它的對象，根據(jù)最佳閾值T*計算對象的下近似數(shù)組。為了匹配兩幅圖像中的對象，需要比較兩幅圖像的對象下近似數(shù)組。

計算在兩個數(shù)組中具有相似灰度值的像素數(shù)量N，然后按公式(4)求出對象相似度Object Similarity Ratio:

Object Similarity Ratio(R) = N/T(4)

其中，N是圖像的中上下近似數(shù)組中具有相同值的像素數(shù)量，T是對象下近似數(shù)組的大小。可以發(fā)現(xiàn)，Object Similarity Ratio的取值在0

3.2 檢索算法

檢索算法:

輸入:擁有單個中心對象的灰度圖像

輸出:最優(yōu)的相似圖像

方法:

—創(chuàng)建圖像數(shù)據(jù)庫;

—在數(shù)據(jù)庫中存儲圖像;

—根據(jù)最優(yōu)閾值T*存儲數(shù)據(jù)庫中每幅圖像的對象下近似數(shù)組;

—根據(jù)T*計算用戶選擇的查詢圖像的對象下近似值;

—比較查詢圖像和目標(biāo)圖像的對象下近似值數(shù)組;

—根據(jù)(4)得出每幅圖像的Object Similarity Ratio;

—檢索擁有最大Object Similarity Ratio值的圖像，數(shù)量由用戶指定。

4 實驗結(jié)果及評價

在Matlab7.0中進(jìn)行了仿真實驗。收集了51張大小為128 × 128的灰度圖像作為實驗的數(shù)據(jù)集，其中每一幅圖像都具有一個唯一的中心對象。圖像數(shù)據(jù)集收集自http://www.cs.cmu.edu/~cil/v-images.html，一個專業(yè)的Web圖像網(wǎng)站。當(dāng)輸入查詢圖像，檢索出對象相似度Object Similarity Ratio的值接近于1的圖像，并跟具對象相似度值對圖像集中的圖像按照降序排序，根據(jù)用戶選擇的數(shù)量返回檢索圖像，實驗中返回的檢索圖像為4。選取了2幅圖像分別作為輸入，得到的檢索結(jié)果如圖2所示。

圖2 兩次檢索的查詢圖像和檢索圖像。中間一行為查詢圖像1的檢索結(jié)果，第三行為查詢圖像2的檢索結(jié)果。

通常用查準(zhǔn)率(Pr)和查全率(Re)[5]評價檢索算法的效率。設(shè)Nr為檢索出的相關(guān)圖像，K為檢索出的總的圖像數(shù)量，Nt為圖像數(shù)據(jù)集中所有相關(guān)圖像。則Rr=Nr/K，Re=Nr/Nt。表1顯示了兩次查詢的查準(zhǔn)率和查全率以及它們的平均值。

表1 兩次檢索的結(jié)果

5 總結(jié)

傳統(tǒng)的圖像檢索主要依賴于顏色、紋理和形狀特征，由于這些可視特征僅是圖像信息的一部分，不能很好的表達(dá)人們對圖像語義層次的理解，因此檢索結(jié)果并不是十分的完美。

應(yīng)用粗糙集理論雖然實現(xiàn)了基于圖像對象的檢索，但是它僅局限于具有單個中心對象的灰度圖像，應(yīng)用范圍有限。因此，今后的研究可以擴(kuò)展到具有多個對象的彩色圖像的檢索，使其具有更加廣闊的應(yīng)用空間。

參考文獻(xiàn):

[1] Eakins J， Graham M， Content-based image retrieval， Technical Report， University of Northumbria at Newcastle， 1999.

[2] Ying Liu， Zhang Deng-sheng. A survey of content-based image retrieval with high-level semantics. Pattern Recognition Society，2006.

[3] Paw lak Z Rough sets[J].International Journal of Computer and Information Sciences，1982(11):341-356.

[4] Pal S K， Uma S B， Mitra P. Granular computing， rough entropy and object extraction[J].Pattern Recognition Letters，2005(26):2509-2517.

[5] Koskela M， Laaksonen J， Laakso S， et al. Evaluating the performance of content-based image retrieval systems[C]//In: International conference on Visual Information Systems(Visual 2000)，2000:2-4.