摘 要：概念格是一種有效的數(shù)據(jù)分析和知識提取的形式化工具，已廣泛應(yīng)用于機(jī)器學(xué)習(xí)、人工智能、軟件工程、知識發(fā)現(xiàn)等領(lǐng)域。提出了一種新的基于概念格的圖像語義檢索方法，將概念格理論應(yīng)用到圖像檢索中，利用形式概念分析發(fā)現(xiàn)圖像中潛在的概念結(jié)構(gòu)和概念間的相互關(guān)系。借助于語言變量描述圖像語義特征并根據(jù)這些模糊語義值構(gòu)建概念格，用基于概念格的方法進(jìn)行圖像語義檢索，這種方法所給的結(jié)果與人類視知覺具有更好的一致性。

關(guān)鍵詞：概念格；基于內(nèi)容的圖像檢索；語言變量；語義檢索

中圖分類號：TN391 文獻(xiàn)標(biāo)識碼：A

文章編號：1004-373X(2008)02-165-04

Research on Semantic Images Retrieval via Concept Lattices

JIANG Jinhui，XIE Fuding

(College of Computer and Information Technology，Liaoning Normal University，Dalian，116029，China)

Abstract： Concept lattice is an effective formal tool in data analysis and extraction of knowledge.It has been widely used in various domains，such as machine learning，artificial intelligence，software engineering，knowledge discovery and so on.This paper presents a new semantic image retrieval method based on the concept lattices.The potential concept structures and mutual relations of the concepts in the image are analyzed by using of formal concept.The linguistic variables are employed to describe semantic feature of image and concept lattice is constructed in terms of these semantic fuzzy value.Then semantic image retrieval based on the concept lattices will work.This approach provides a result that is better consistency with human visual perception.

Keywords：concept lattices;content-based image retrieval;linguistic variable;semantic retrieval

1 引 言

隨著計算機(jī)及網(wǎng)絡(luò)技術(shù)的發(fā)展和普及，可利用的圖像信息日益增多，為解決對圖像數(shù)據(jù)庫的高效管理及查詢問題，研究者提出了基于內(nèi)容的圖像檢索(CBIR)方法，即使用顏色、紋理、形狀和相互關(guān)系等可視特征進(jìn)行圖像檢索。隨著研究深入，人們發(fā)現(xiàn)CBIR系統(tǒng)存在明顯的不足：圖像的低層視覺特征與高層語義特征間存在“語義鴻溝”，于是人們開始進(jìn)行語義圖像檢索研究。

本文將概念格理論應(yīng)用到圖像語義檢索中，利用語言變量來描述圖像語義特征，根據(jù)這些模糊語義值構(gòu)建概念格，利用形式概念分析方法［1］發(fā)現(xiàn)圖像語義潛在的格結(jié)構(gòu)和相互關(guān)系，用基于概念格的方法進(jìn)行圖像語義檢索。這種方法可以得到與人類視知覺具有較好一致性的檢索結(jié)果。

2 概念格的基本概念

概念是由外延和內(nèi)涵組成的?；谶@一哲學(xué)思想， Wille教授在20世紀(jì)80年代初期提出了一種形式化概念分析方法，用于概念的發(fā)現(xiàn)、排序和顯示［1-3］。形式概念分析的核心數(shù)據(jù)結(jié)構(gòu)-概念格是一種有效的數(shù)據(jù)分析和知識提取的形式化工具，已在知識發(fā)現(xiàn)、軟件工程、信息檢索等諸多領(lǐng)域得到應(yīng)用［2-4］。

概念格的基本思想是將每個概念用1個節(jié)點(diǎn)來表示，對概念進(jìn)行形式化的表達(dá)，稱為形式概念。每個形式概念包括：內(nèi)涵是概念外延中所有對象的共同屬性的集合；外延是概念內(nèi)涵可以確定的最大的對象集合，一個概念是一個完備的二元組。特別的，定義2個特殊的概念：全概念即包含所有對象的概念；空概念即外延為空的概念。形式概念分析理論通過數(shù)學(xué)的形式化語言將概念的內(nèi)涵和外延表達(dá)出來。概念格可以通過Hasse圖來體現(xiàn)這些概念之間的泛化和特化關(guān)系，反映數(shù)據(jù)中所蘊(yùn)含的概念之間的相互關(guān)系。

3 語言變量概念

L.A.Zadeh［5］深入研究了自然語言的模糊性質(zhì)，在1975年提出了一種用數(shù)量分析的方法來處理自然語言的模糊性，并詳細(xì)地論述了語言變量的概念以及在近似推理中的應(yīng)用，為用模糊理論進(jìn)行近似推理做了開創(chuàng)性的工作。

語言變量就是以自然語言或人工語言中的詞或詞組作為值的變量。用字或詞組而不是用數(shù)是語言的特性一般沒有數(shù)那么精確，但具有表達(dá)靈活的特點(diǎn)。例如談到身高的時候，說“小李很高”比“小李一米九”的表達(dá)精確性差些，但更為靈活，很高可以作為身高變量的語言值。本文采用語言變量的方法更有利于對圖像語義特征的表達(dá)。3.1 圖像語義特征的表示

3.1.1 圖像顏色語義特征表示

傳統(tǒng)的顏色劃分方法與人們對大自然中顏色的感知有時會有較大的差異，但無論人們的評審標(biāo)準(zhǔn)多么復(fù)雜，人們對大自然中顏色的命名和分類一般都會包括紅、黃、藍(lán)、綠、青、紫、黑、白幾種主色調(diào)。因此將上述8種色調(diào)作為顏色的基本類別，將所有的顏色都?xì)w到這幾種類別中。

3.1.2 圖像紋理語義特征表示

基于人們對紋理視覺感知的心理學(xué)研究， Tamura等提出，人的視覺系統(tǒng)更易于感知紋理模式的特性，如粗糙度(coarseness)、對比度(contrast)、方向度(directionality)、直線度(line likeness)以及規(guī)則度(regularity)等。本文選擇Tamura模型的前3個特征作為圖像的語義特征。根據(jù)語言變量的定義，這3個特征都可以當(dāng)作語言變量來描述圖像的紋理語義。

下面用語言變量=(X，T(X)，U，G，M)來形式化表示紋理的語義特征，以語言變量粗糙度X為例闡述圖像語義的語言變量描述方法。粗糙度測度紋理模式的粒度大小，紋理模式粒度越大表示該紋理圖像越粗糙，相反則越細(xì)膩。一般用“粗糙”、“細(xì)膩”等詞來描述紋理粗糙度。X是這個語言變量的名稱，可以認(rèn)為是描述對象的屬性，這里是“粗糙度”。T(X)是語言變量X取值的語言值集合，由基本詞集和擴(kuò)展詞集組成。 基本詞集是詞集中語義不可再分的語言值集合，由設(shè)計人員制定，如X基本詞集可定義為{粗糙，細(xì)膩，適中}。擴(kuò)展詞集通過句法規(guī)則產(chǎn)生，由基本詞集中的語言值和修飾詞組成的語言值的集合。U是論域，在圖像檢索中，U可以是圖像本身（象素值）或者圖像的一個近似（圖像特征向量）。

4 基于概念格的圖像檢索

4.1 圖像預(yù)處理

一般來講，一幅圖中并不是所有出現(xiàn)的顏色都與這幅圖所描述的目標(biāo)有關(guān)系，有些顏色的出現(xiàn)是偶然的或與查詢目標(biāo)無關(guān)的，但這些點(diǎn)的顏色統(tǒng)計卻會影響到檢索效果。通常，目標(biāo)的象素點(diǎn)和圖像背景的象素點(diǎn)會頻繁地在某些行（列）中同時出現(xiàn)，為了找到圖像中與目標(biāo)相關(guān)的行（列），只要找到那些背景色和前景色頻繁地同時出現(xiàn)的行（列）即可。用頻繁色處理方法［8］對圖像的行（列）分別進(jìn)行一次預(yù)處理。將圖像看成一個事務(wù)集，圖像的每一行（列）看成一個事務(wù)，用Apriori算法［9］進(jìn)行計算后，只取具有最多項(xiàng)的最大模式-頻繁k項(xiàng)集，因?yàn)樽罡唔?xiàng)的頻繁項(xiàng)集［10］更能夠反應(yīng)圖像中目標(biāo)的信息。統(tǒng)計所有頻繁k項(xiàng)集中所有項(xiàng)(顏色)的出現(xiàn)頻率，將在這個區(qū)域中未出現(xiàn)的顏色的頻率設(shè)為0，出現(xiàn)但不包括在頻繁k項(xiàng)集中的顏色的頻率也設(shè)為0，可得到一個頻繁色在目標(biāo)相關(guān)區(qū)域的統(tǒng)計直方圖。采用頻繁色處理方法，更能突出圖像中人們感興趣的目標(biāo)區(qū)域，同時濾除一些干擾因素。

4.2 圖像的形式背景 

4.5 圖像檢索

基于概念格檢索的優(yōu)點(diǎn)是：用戶可以沿著一個節(jié)點(diǎn)的一條路徑向下檢索，若沒有發(fā)現(xiàn)相關(guān)的圖像，則返回到該節(jié)點(diǎn)的另一條路徑上而不用再重頭開始檢索。子節(jié)點(diǎn)和父節(jié)點(diǎn)之間是超文本鏈接，可以通過點(diǎn)擊一個父或子節(jié)點(diǎn)導(dǎo)航這些鏈接。這一點(diǎn)上明顯優(yōu)于傳統(tǒng)的層次樹結(jié)構(gòu)。對于層次樹結(jié)構(gòu)，用戶在每個決策點(diǎn)都已經(jīng)做了最好的推測，當(dāng)用戶對每一層向下檢索時，都盡力挑選最好的孩子節(jié)點(diǎn)，如果沒有發(fā)現(xiàn)合適的圖像，就停滯不前。而基于概念格檢索，就能夠經(jīng)由另一條路徑返回到該節(jié)點(diǎn)開始新的決策。

如圖1所示，概念格的節(jié)點(diǎn)是由概念(A，B)組成，其中，A是概念的外延，B是概念的內(nèi)涵。每個概念的內(nèi)涵用作瀏覽格結(jié)構(gòu)的索引詞。其中數(shù)字代表圖像，字母代表關(guān)鍵詞，節(jié)點(diǎn)代表概念(A，B)。假定用戶的查詢是“黃色的圖像”，那么系統(tǒng)會在結(jié)果空間中列出概念“黃色”的圖像集(2，4，5)，并且會在導(dǎo)航空間中給出概念“黃色且對比度底”、“黃色和綠色”和“黃色且粗糙度適中且方向度好”的圖像集作為比較特殊的節(jié)點(diǎn)，只有節(jié)點(diǎn)的直接鄰居節(jié)點(diǎn)被列出。如果用戶選擇了概念“含有黃色和綠色”的圖像集(2，4)，則系統(tǒng)將會給出他的父節(jié)點(diǎn)“黃色”的圖像集(2，4，5)和他的孩子節(jié)點(diǎn)的 “含有黃綠青且粗糙度細(xì)膩且對比度低且方向度壞” 圖像集(4)和 “含有黃綠藍(lán)紫且粗糙度適中且對比度高且方向度好”的圖像集(2)。在這個階段，用戶可以再向上或向下導(dǎo)航，也可以移到格的根部。

5 結(jié) 語

本文給出一種新的利用FCA進(jìn)行圖像語義檢索的方法。該方法的主要特點(diǎn)在于改善了系統(tǒng)的性能。由于系統(tǒng)給出查詢結(jié)果的鄰居節(jié)點(diǎn)，提供給用戶更好的啟發(fā)式搜索體驗(yàn)。同時，可以對每個概念計算其支持度，通過設(shè)置閾值的方法，返回給用戶更加準(zhǔn)確的結(jié)果。

文中用頻繁色的方法對圖像進(jìn)行預(yù)處理，此方法對目標(biāo)區(qū)域比較明顯的圖像有較好的處理結(jié)果，同時引入語言變量的方法來描述圖像語義，提供了靈活的模糊匹配策略，使結(jié)果與人類視知覺具有更好的一致性。

參 考 文 獻(xiàn)

［1］Ganter B，Wille R.Formal Concept Analysis:Mathematical Foundations［M］.Springer-Verlag，Berlin-Heidelberg，1999.

［2］Baltasar Fernandez-Manjon，Alfredo Fernandez-Valmayor.Building Educational Tools Based on Formal Concept Analysis［J］.Education and Information Technologies，1998:187-201.

［3］Krohn U，Davies N J，Weeks R.Concept Lattices for Knowledge Management ［J］ .BT Technol，1999，17 (4):108 - 113.

［4］Kuznetsov S O.Machine Learning on the Basis of Formal Concept Analysis［J］.Automation and Remote Control，2001，62(10):1543 - 1564.

［5］Zadeh L A.The Concept of Linguistic Variable and Its Application to Approximate Reasoning[J].Information Sciences，1975，8:199-249.

［6］周長發(fā).精通Visual C++.NET圖像處理編程［M］.北京:電子工業(yè)出版社，2003.

［7］Wan Hualin.The Research on High Semantic Feature Extraction and Low Visual Feature Extraction ［D］.Institute of Computing Technology，Chinese Academy of Sciences，Beijing，2002.

［8］馮玉才，程珺，聶晶，等.一種新的基于顏色的圖像檢索算法［J］.計算機(jī)工程與應(yīng)用，2006，42（22）：52-55，99..

［9］Agrawal R，Srikant R.Fast Algorithms for Mining Association in Large Databases［R］.In Research Report RJ 9839，IBMAlmaden Research Center，San Jose，CA，1994.

［10］Jiawei Han，Micheline Kamher.Data Mining Concepts and Techniques［M］.China Machine Press，2001.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。