基于概念格的圖像語義檢索研究

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

關鍵詞：概念格；基于內容的圖像檢索；語言變量；語義檢索

中圖分類號：TN391 文獻標識碼：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 引 言

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

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

2 概念格的基本概念

概念是由外延和內涵組成的?；谶@一哲學思想， Wille教授在20世紀80年代初期提出了一種形式化概念分析方法，用于概念的發現、排序和顯示［1-3］。形式概念分析的核心數據結構-概念格是一種有效的數據分析和知識提取的形式化工具，已在知識發現、軟件工程、信息檢索等諸多領域得到應用［2-4］。

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

3 語言變量概念

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

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

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

傳統的顏色劃分方法與人們對大自然中顏色的感知有時會有較大的差異，但無論人們的評審標準多么復雜，人們對大自然中顏色的命名和分類一般都會包括紅、黃、藍、綠、青、紫、黑、白幾種主色調。因此將上述8種色調作為顏色的基本類別，將所有的顏色都歸到這幾種類別中。

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

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

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

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

4.1 圖像預處理

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

4.2 圖像的形式背景 

4.5 圖像檢索

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

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

5 結 語

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

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

參 考 文 獻

［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］周長發.精通Visual C++.NET圖像處理編程［M］.北京:電子工業出版社，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］.計算機工程與應用，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.

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