基于概念格的圖像特征數據降維

摘 要:高維圖像特征數據不利于圖像數據挖掘。為了降低圖像特征數據維數，提出了基于概念格的降維算法，該算法將圖像的HSV顏色特征轉換為圖像形式背景，再對背景的概念格進行屬性約簡。實驗結果表明，該降維方法比較有效，并且較主成分分析具有明顯的優勢。

關鍵詞:圖像挖掘; 維度災難; 形式背景; 概念格; 屬性約簡; 數據降維

中圖分類號:TP18文獻標志碼:A

文章編號:1001-3695(2009)09-3553-03

doi:10.3969/j.issn.1001-3695.2009.09.102

Image feature data dimension reduction based on concept lattices

LUO Weia， WANG Lia， AI Lib， WANG Yue-hanga

(a. School of Computer Science Engineering， b. School of Science， University of Science Technology Liaoning， Anshan Liaoning 114051， China)

Abstract:High-dimensional image feature data is an obstacle for image mining. In order to reduce the image feature data dimension， this paper introduced a dimension reduction algorithm based on concept lattices. In this algorithm， calculated the concept lattices of the image formal， which was transformed from the HSV color feature， and then reduced the attributes of the concept lattice. The experiment results prove that this method is efficient， and it outperforms the principal component analysis (PCA).

Key words:image mining; curse of dimensionality; formal context; concept lattices; attribute reduction; data dimension reduction

隨著數字成像技術和設備的廣泛應用，每天都會產生大量的圖像數據，然而如何對這些圖像進行自動分析以獲取大量有用的知識，這就需要使用圖像挖掘技術。圖像數據本身是一種半結構化或非結構化數據，若要使用數據挖掘領域成熟的數據挖掘方法對圖像數據進行挖掘，必須先將數據結構化，即對圖像進行預處理。圖像預處理階段最重要的是圖像特征的提取、表示與描述。但是在特征提取過程中，會得到有關圖像的很多特征數據，導致圖像特征維度過高，這樣容易引起圖像挖掘精度的下降，還可能導致圖像挖掘算法的復雜度過高，稱為圖像數據維度災難。

雖然使用相關技術能夠提取的圖像特征非常多，達到的維數非常高，但在實際的圖像挖掘中，必需的圖像特征維數并不高。因此對于高維圖像特征，為了降低所提取圖像特征維數之間的相關性，需要消除圖像特征之間的依賴性，該過程被稱為高維圖像特征數據降維。

目前，常用的數據降維算法主要有獨立成分分析(ICA)、主成分分析(PCA)和因子分析(FA)等。另外還有近幾年發展起來的基于流形學習的非線性維數約簡方法，如LLE、Isomap等[1]。

概念格又稱為Galios格，是Wille教授[2]于1982年首先提出來的。概念格是根據數據集中對象與屬性之間的二元關系建立的一種概念層次結構，是一種有效的數據分析工具。概念格描述了對象與屬性之間的泛化和特化關系，因此具有很好的知識表示和描述知識發現問題的能力。作為數據分析的有力工具，概念格理論已經被廣泛地應用于知識發現和數據挖掘領域。

本文將利用概念格屬性約簡理論對圖像顏色特征數據進行數據降維。

1 概念格的基本概念

1.1 形式背景與概念格

定義1 一個形式背景是一個三元組(G， M， I)，其中G和M是集合，二元關系I=G×M，G和M的元素相應地被稱為對象和屬性。通常用gIm表示(g， m)∈I，即對象g有屬性m。

對于AG和BM，定義下面運算:

A′={ m∈M |g∈A，gIm}=B′ { g∈G|m∈B，gIm}

顯然，A′是A中所有對象所共有的屬性集合，B′是B中所有屬性的對象集合，則形式B-(G， M1， I1) 細于B-(G， M2， I2)，記做B-(G， M1， I1)≤B-(G， M2， I2)。如果存在關系B-(G， M1， I1)≤B-(G， M2， I2)，且B-(G， M2， I2)≤B-(G， M1， I1) ，那么稱這兩個概念格同構，記做B-(G， M1， I1)B-(G， M2， I2)。

定義3 對于形式背景(G， M， I)，如果存在屬性集DM，使B- (G， D， ID)B- (G， M， I)，其中，ID=I∩( G×D )，則稱D是(G， M， I)的協調集。若進一步d∈D，B-(G， D -g0gggggg， ID - g0gggggg)B-(G， M， I)，則稱D是(G， M， I)的約簡。

1.2 概念格屬性約簡

定義4 對于一個形式背景(G， M， I)，其中，G={ g1， g2， …， gm }，M={ m1， m2， …， mn }，IG×M，g∈G，m∈M，定義V (g)={ m∈M|gIm}，D (m)={ g∈G|gIm}，分別稱V(g)為對象的屬性空間，D(m)為屬性的對象空間。

對于一個形式背景(G， M， I)，其約簡一定存在。根據各屬性的對象空間之間關系的不同，可以采用下面的屬性約簡定理對屬性進行約簡。

定理1[3] 對于一個形式背景(G， M， I)，若mi∈M，i∈[1，n] 使得D(mi)=G時，則屬性mi為冗余的，即可約簡mi所在列。若mi∈M，i∈[1， n] 使得D(mi)=時，則可約簡mi所在列。

定理2[3] 對于一個形式背景(G， M， I)，

a)若mi，mj，mk ∈M(i，j，k∈[1， n])，使得D(mk)D(mi)，D(mk)D(mj)且D(mi) ∩D(mj)=D(mk) 時，則屬性mk是冗余的，即可約簡mk所在列。

推論 若mi，mj，…，mk，…，mn ∈M，其中i，j，…，k∈[1， n]，使得D(mk)D(mi)，D(mk)D(mj)，…，D(mk)D(mn)且D(mi)∩D(mj)∩…∩D(mn)=D(mk) 時，則可約簡mk所在列。

b)若mi ，mj∈M(i，j∈[1， n])，使得D(mi)=D(mj) 時，則屬性mi或mj是冗余的，即可約簡mi或mj所在列。

2 圖像形式背景

2.1 圖像顏色特征

在圖像的顏色、形狀、紋理等特征中，顏色是圖像的顯著特征，也是人識別圖像的主要感知特征。目前常用的顏色空間主要有RGB、CMY和HSV等。HSV顏色空間直接對應于人眼色彩視覺特征的三要素，即色調(hue)、飽和度(saturation)和亮度(value)。由于HSV空間中各軸在視覺上彼此無關，空間距離又符合人眼視覺特征，并且從RGB到HSV的轉換是一個簡單且快速的非線性變換，這里將使用HSV顏色空間作為圖像的色彩空間。

對于任何一幅彩色圖像來說，通過HSV顏色空間轉換之后均可以得到顏色的H、S和V值。得到顏色值后對其進行適當的非等間隔量化，并計算L=16H+4S+V[6]，即可將H、S和V這三個分量在一維矢量上分布開來。L的取值可以確定為[0， 1， 2， …， 255]。這樣就獲得一個256柄的一維直方圖，任意彩色圖像都可以通過這種方法獲得其256維顏色特征直方圖。

由于顏色分布的局域性，有的顏色出現得比較少，為了簡化直方圖描述，有必要對其進行優選。一種基于閾值顏色集(color set)的思想是針對顏色直方圖中每個顏色項k，引入閾值ξ:

p(ck)=1h(k)≥ξ0others(1)

其中:ξ為閾值，取值[0， 1]。顯然，p(ck)是否為1可以判斷顏色特征k在處理時是否可以忽略。實驗結果表明，其與直方圖的查詢結果基本一致，且在存儲容量、查詢響應上更具有優勢[7]。

2.2 圖像形式背景

定義5 基于圖像的形式背景是一個三元組B=(I， K， R)。其中:I是圖像集合;K是特征集合;R是一個二元關系，表示K是否為圖像I的特征。

提取圖像的顏色特征后，通過實驗選擇合適閾值，由式(1)對顏色直方圖進行轉換，得到一個取值為0或1的顏色直方圖。使用圖像向量空間模型(vector space image model，VSIM)來表示圖像庫中的圖像[8]。設圖像庫中共有n幅圖像，圖像顏色特征數為m，這樣形成一個n×m的向量Bnm，向量的每一行代表一幅圖像，而每一列代表圖像的一個顏色特征。使圖像的個數集合代表I，顏色特征集合代表K，這樣向量Bnm就可以表示圖像的形式背景了。

3 算法描述

對于圖像形式背景B=(I， K， R)，通過對其上的概念格進行屬性約簡，即可達到對圖像顏色特征數據降維的目的。

先由算法1得到圖像背景屬性集合DM={ DM1， DM2， …， DMm }，其中DMi表示屬性i的對象全體集合。得到屬性集合后就可以直接進行圖像特征降維了，圖像特征降維算法如算法2所示。算法2中使用了一個臨時集合T，主要是用來存放DMi的超集。得到超集后，利用屬性約簡定理2及其推論進行判斷，確定是否進行約簡。

算法1中，對于圖像特征屬性集合DM的每一個特征屬性DMi，需要比較n次，時間復雜度為O(n);對于圖像特征集DM中的m個特征，總的時間復雜度為O(nm)。算法2中，圖像特征降維算法的時間復雜度為O(m2)。

算法1 生成圖像背景屬性集合

輸入:圖像形式背景Bnm;

輸出:DM={DM1，DM2，…，DMm}。

初始化j=0，DM=，DM1=DM2 = … = DMm=;

repeat

i=0;

while( i

if(Bij=1)then

DMj=DMj+{gi};

i=i+1;

end while;//得到DMj

j=j+1;

until(j=m-1);

將DMj加入集合DM，得到集合DM={DM1， DM2， …， DMm}

算法2 維數約簡算法

輸入:DM={DM1，DM2，…，DMm};

輸出:維數約簡集合F-reduct。

初始化維數約簡集合F-reduct =F= {F1， F2， …， Fm}，i=1;

repeat

if(DMi=‖ DMi=G) then

F-reduct=F-reduct -{Fi}

else

repeat

j=i+1，T=;

if(DMiDMj) then

T=T+{DMj};

 j=j+1;

until(j=m);

//得到DMi的超集T， 則計算

DT=T0，k=0;

while (k

// 對T中的集合求交集

DT=DT∩Tk;

k=k+1;

end while;

if( DMi=DT ) then

F-reduct=F-reduct -{Fi};

i=i+1;

until(i=m);

4 實驗

從網上搜索并隨機選取80幅圖像，首先對圖像庫中的圖像進行人工分類，然后抽取圖像HSV顏色特征并計算顏色直方圖。適當調節閾值ξ，通過式(1)進行相應的顏色特征轉換，然后建立圖像特征空間向量即圖像形式背景B80×256，再利用算法對其進行降維。通過多次實驗，選擇閾值ξ=0.004 213 93，利用上述算法對圖像特征數據進行降維后，將256維的顏色特征向量降為47維。

為了驗證降維后的數據仍能準確描述原始數據的特征，對原始圖像基于降維前和降維后的特征進行相似圖像檢索[9]。采用精確度(precision)和檢索率(recall)[10]作為檢索效果的評價標準。其中，精確度定義為檢索結果隊列中檢索的目標圖像與隊列中的圖像數之比，即

precision=R/a(2)

檢索率定義為檢索結果隊列中檢索的目標圖像與數據庫中全部的目標圖像之比，即

recall=R/b(3)

其中:a代表檢索結果隊列中的圖像總數;R代表查詢結果中與例子圖像相關的目標圖像數;b代表圖像庫中與例子圖像相關的目標圖像總數。

對原始圖像分別進行基于降維前和概念格降維、PCA降維后的特征圖像相似性檢索。圖1為降維前后圖像檢索的查準率和查全率曲線。從圖1中可以看出，降維后檢索準確率和降維前的檢索準確率相比變化不大。降維后的特征向量仍然保持高維空間的拓撲結構，大大降低了由于降維引起的檢索精度損失，并且通過與PCA降維方法的比較發現，概念格降維方法具有一定的優勢。

在算法的實際應用過程中，閾值ξ的選取會對數據降低的維數產生影響。閾值過大或過小都會造成圖像檢索精度下降，即降維后的數據不能保持原高維數據中的信息，所以在確定閾值時要進行多次實驗并對閾值進行適當的調整。實驗中發現，閾值在[ 0.00228279， 0.00954621 ]區間時，降維的效果比較理想。此時，數據的維數在區間 [34， 213]，對應的圖像檢索結果如圖2所示。

從圖2可以看出，這時的檢索結果還是比較好的。圖中圖像特征數據維數與圖像查準率對應，而實際上相應的閾值又與圖像特征數據維數對應起來。這樣，通過檢索結果的比較，就可以反過來確定閾值的大小。這也正是本次實驗閾值選取的一個依據。

5 結束語

本文在概念格屬性約簡理論的基礎上，提出了基于概念格屬性約簡的非線性降維方法，并針對圖像256維HSV顏色特征數據進行了降維實驗。從實驗結果來看，這種方法保留了原始高維數據的整體和局部信息，具有較好的性能。

參考文獻:

[1]黃啟宏， 劉釗. 流形學習中非線性維數約簡方法概述[J]. 計算機應用研究， 2007，24(11): 19-25.

[2]WILLE R. Restructuring lattice theory: an approach based on hierarchies of concept [M]//RIVAL I. Ordered sets. Dordeche: Reidel Publishing Company， 1982: 445-470.

[3]楊麗， 徐揚. 基于形式背景的概念格約簡及其修復[J]. 計算機工程， 2008，34(9): 22-24.

[4]王霞，張文修. 概念格的屬性約簡與屬性特征[J]. 計算機工程與應用， 2008，44(12): 1-4.

[5]甘特爾 B， 威爾 R. 形式概念分析[M]. 馬垣，張學東，遲呈英，等譯. 北京: 科學出版社， 2007: 15-46.

[6]FINLAVSON G， SCHETTINE R. Special issue on color for image indexing and retrieval [J]. Computer Version and Image Understanding， 2004，94(1): 1-268.

[7]CASTLEMAN K R. Digital image processing [M]. New York: Prentice-Hall， 1996.

[8]KULKARNI S， SRINIVASAN B， RAMAKRISHNA M V. Vector space image model (VSIM) for content based image retrieval[C]// Proc of the 10th International Workshop on Database and Expert Systems Applications. 1999: 899-903.

[9]LEE S M， XIN J H， WESTLAND S. Evaluation of image similarity by histogram intersection [J]. Color Research and Application， 2005，30(4): 256-274.

[10]LEE H Y， LEE H K， HA Y H. Spatial color descriptor for image retrieval and video segmentation [J]. IEEE Trans on Multimedia， 2003，5(3): 358-367.