劉大有，董 婥，王生生

吉林大學計算機科學與技術學院，長春130012

基于空間關系的CBIR算法［1］(content-based image retrieval，CBIR)，主要依據(jù)圖像中對象之間的空間關系進行相似性檢索.近十多年來，一些基于空間關系的CBIR算法陸續(xù)被提出.Gudivada等［2］提出的SIMR算法及 El-Kwae等［3］擴展SIMR得到的SIMDTC算法，將對象抽象成幾何中心點，利用兩點之間的角度描述對象間的空間關系，忽略了對象自身大小.WANG［4-5］等提出基于2D BE-string排序的最大公共子序列(longest common subsequence，LCS)算法.基于LCS的算法考慮物體在兩個維度的排列順序，無法精確描述區(qū)域間的空間拓撲關系.Hsieh等［6］提出公共模式方法(common pattern method，CPM)，隨后又提出將圖像中所有對象及對象間方位關系表示為空間關系圖(spatial relationship graph，SRG)，用兩個SRG的公共頂點和公共邊的總數(shù)度量相似性［7］.這兩個方法同樣將對象抽象成幾何中心點，僅利用兩點之間的方位排序進行檢索，不僅導致檢索出了不相關的圖像，且耗時，無法滿足互聯(lián)網(wǎng)上快速響應的需求.Chiang等［8］提出將對象抽象成最小邊界矩形(minimum bounding rectangle，MBR)，將MBR一維上的空間關系映射為ING(interval neighbor group)的一個頂點，對象間距即為兩個維度上ING頂點的最短路徑之和，對象間距離越遠說明相似性越低.Wang等［9］在MBR表示物體的基礎上，考慮對象間z軸方向的距離，得到復合的方位關系并計算方位距離.以上兩種方法需計算所有對象間距，當圖像中對象規(guī)模為n時，需進行n×(n-1)/2次計算.這些方法中.CPM是一個平均比較時間最短，且具兼容性的方法，尤其是在對象較多或符號重復率較高的情況下，仍滿足多項式時間復雜性［6］，是目前較好的相似性算法之一.實驗說明，CPM的檢索速度是基于LCS的團集LCS_clique的30倍，是SIMR、SIMDTC和2D BE-string的8～10倍［6］.隨著對象數(shù)目或符號重復率的增加，LCS_clique、SIMR和SIMDTC的檢索時間將會激增，而CPM仍保持穩(wěn)定的速度，滿足多項式時間的復雜性［6］，CPM的檢索效果比9DLT 的檢索效果更好［10］.

由于CPM采用基于點的空間模型，無法檢索出精確結果.為此，本研究基于CPM，將圖像中的對象抽象為MBR，采用矩形代數(shù)描述對象間的空間關系，得到基于矩形代數(shù)的相似性圖像檢索算法(similarity retrieval by rectangle algebra，SRRA).SRRA關于對象間的相似性度量比CPM更嚴格，在計算最大相似對象集合的過程中，可有效減少不相關對象的計算，不僅得到更準確的檢索結果，且顯著縮短了檢索時間.

1 研究背景

1.1 矩形代數(shù)(rectangle algebra)

1983年，Allen［11］提出基于連續(xù)區(qū)間的時態(tài)推理系統(tǒng)，即區(qū)間代數(shù).區(qū)間代數(shù)中定義了13種基本關系，每個基本區(qū)間關系描述兩個時間段的確定關系.Balbiani等［12］將 Allen時態(tài)區(qū)間代數(shù)擴展到二維空間，得到矩形代數(shù)，所描述的空間對象是四邊平行于二維直角坐標的矩形，如圖1.

圖1 矩形代數(shù)描述的空間對象Fig.1 The objects described by rectangle algebra

矩形代數(shù)關系的定義為［13］

其中，Aint={p，pi，m，mi，e，d，di，s，si，f，fi，o，oi}，如表1.Arec構成一個互不相交且聯(lián)合完備(jointly exhaustive and pair wise disjoint，JEPD)的關系集合，它包含矩形所有關系［14］.盡管 Hoàng等［15］提出新的空間關系制圖法，矩形代數(shù)仍因其易于理解、良好的計算性質(zhì)和推理方法被廣泛采用.

表1 矩形代數(shù)的13種基本關系Table1 The basic relationships of rectangle algebra

1.2 LCS_clique

1989年，Lee等［16］提出 LCS_clique算法利用兩個2D string構建一個type-i公共子圖，通過尋找其最大團，求得兩幅原始圖像的最大公共子圖.

type-i公共子圖的定義為［6］

令S為圖像f1的對象子集，T為圖像f2的對象子集.若存在一個從S到T的雙射函數(shù)滿足:①S中對象Oi的符號等于g(Oi)的符號;② 對于S中任意兩個對象Oi和Oj，f1中的Oi和Oj是type-i相似的，同時f2中的g(Oi)和g(Oj)也是type-i相似的(其中i=0，1，2)，我們說S和T是f1和f2的type-i公共子圖.

1.3 CPM

2008年，Shu-Ming Hsieh等提出用CPM解決圖像檢索問題.CPM將圖像中對象抽象成幾何中心點，采用type-i方法度量對象間的相似性.利用LCS_clique思想，CPM將無向的type-i公共子圖轉(zhuǎn)化為一組有向無環(huán)的CP_DAG圖，將在type-i公共子圖內(nèi)尋找最大團的問題轉(zhuǎn)化為在這一組CP_DAG內(nèi)尋找最長路徑的問題.最長路徑上的頂點構成最大的相似對象集合，集合內(nèi)所有對象的相似值加和是兩圖的相似值.

與 LCS_clique、SIMR、SIMDTC及2D BE-string 相比，CPM是一個平均比較時間最短的算法.一般來說，CPM的檢索速度是LCS_clique的30倍，是SIMR、SIMDTC和2D BE-string的8 ～10倍［6］.同時，隨著對象數(shù)目或符號重復率的增加，LCS_clique、SIMR和SIMDTC的檢索時間將會激增，而CPM仍保持穩(wěn)定的速度，滿足多項式時間的復雜性［6］.

但是，CPM無法精確描繪對象間的空間關系.采用type-i方法判斷兩點的方位關系，忽略了對象自身的大小，基于點的空間模型無法描述區(qū)域間的拓撲關系.例如，兩物體呈現(xiàn)meet和overlap等不同拓撲關系時，CPM易將其表示成相同的方位關系，從而認為物體具有較高的相似性.這既不能很好地區(qū)分圖像，還會因為判斷空間相似性不嚴格，增加冗余計算，使檢索過程費時費力.

2 SRRA算法

本研究基于CPM，將圖像中對象抽象為MBR，用矩形代數(shù)描述對象間的空間關系，從而改進得到SRRA算法.算法步驟為

①建立符號化圖像數(shù)據(jù)庫.把圖像中對象抽象成MBR并標注對象的符號(symbol)，即每個對象表示為(［xinf，xsup］，［yinf，ysup］，symbol)這樣的三元組.每張圖像按照所有對象的xinf坐標從小到大將對象排序.例如，查詢圖像f1可表示為α=a1a2...an1，數(shù)據(jù)庫圖像 f2可表示為 β =b1b2...bn2.這樣，我們不再需要存儲圖像本身，只要存儲一串三元組即可.

②建立頂點數(shù)組M.當ai.symbol=bj.symbol時，生成頂點(i，j)，并將其放入頂點數(shù)組M.為便于計算，用vk表示M中第k個頂點.注意，這里的頂點并不代表一個對象，而是具有相同符號的兩個對象構成，即vk=(i，j).

③構造SRRA中的矩形代數(shù)相似圖(rectangle algebra similaritygraph，RASG)，其函數(shù)記作construct_RASG()，具體構建步驟如圖2.

RASG的頂點來自M的元素，對于RASG()的任意兩點vm和vn，設vm=(i，j)，vn=(o，p)，若滿足i＞o且j＞p，同時，ai和ao存在某種矩形代數(shù)關系r，而 bj和bp存在相同的矩形代數(shù)關系 r，RASG()存在有向邊 ＜vm，vn＞.

生成RASG(i，j)的步驟為

i)RASG(i，j)的第一個頂點為(i，j);

ii)對所有 RASG(k，h)，k ＜ i，h ＜ j，求得其中和頂點(i，j)具有相同的空間關系的頂點以及相應的有向邊.考察頂點(i，j)和(k，h)是否具有相同的空間關系，需分別在x軸和y軸上判斷對象的投影范圍屬于哪種矩形代數(shù)基本關系(表1)，相應算法為 Algorithm RA((i，j)，(k，h)). 當 求 得RASG(k，h)中和頂點(i，j)具有相同的空間關系的頂點以及相應的有向邊之后，需要將其全部加入RASG(i，j).這是RASG(i，j)的擴展過程，表示按順序掃描到(i，j)為止，包含(i，j)的最大相似對象集合;

iii)擴展RASG(i，j)的具體情況可分為:一，若RASG(k，h)中僅(k，h)和(i，j)具有相同矩形代數(shù)關系，則直接在RASG(i，j)中增加頂點(k，h)，增加一條從(i，j)到(k，h)的有向邊，并給這條有向邊賦值一個新的pID;二，通常稱RASG(k，h)中和(i，j)具有相同的矩形代數(shù)關系的頂點組成的集合為SV，相應的有向邊集合為SE，且＞1.對于任意路徑p'∈SE，將該路徑上的所有頂點和邊依次加入RASG(i，j)，同時增加從(i，j)到(k，h)的有向邊，設路徑號為p'，則該有向邊成為路徑 p'的一部分.生成算法見Algorithm Construct_RASG((i，j)).

圖2 Algorithm SRRA()構建步驟Fig.2 Construct Algorithm SRRA()

④針對M中的每個元素(i，j)生成RASG(i，j)，并依此得到當前圖中的最長路徑pi.最后，在集合{pi}中尋找最長路徑pmax.pmax上的所有頂點即最大相似對象集合.

下面將給出最長路徑上的頂點即構成最大相似對象集合的正確性說明.

傳統(tǒng)方法利用最大團解決圖像檢索問題需構建一個無向圖，其每個頂點和RASG頂點定義一致;無向圖中的邊表示連接的兩個頂點所代表的對象之間具有相同矩形代數(shù)關系.設無向圖的頂點數(shù)為N，則在構建無向圖的過程中，需考察每個頂點和其余N-1個頂點的關系.在求解最大團的過程中，還需不斷考察任意頂點和其他頂點是否相鄰.

由SRRA算法可知，構建RASG(i，j)需不斷擴展，將RASG(k，h)中和(i，j)具有相同的矩形代數(shù)關系的頂點及相應的有向邊合并入RASG(i，j)，其中k＜i，h＜j，且只需考慮符合這種關系的頂點.考慮兩種擴展RASG(i，j)的情況:

第一種情況，當RASG(k，h)中和(i，j)具有相同矩形代數(shù)關系的頂點集合內(nèi)只有一個頂點(k，h)，不存在相應的有向邊時，將(k，h)加入RASG(i，j)，并增加一條從(i，j)到(k，h)的有向邊，同時分配該邊新的ID路徑編號.此時該路徑長度為1，路徑上兩個頂點具有相同矩形代數(shù)關系.

第二種情況，設RASG(k，h)中和(i，j)具有相同矩形代數(shù)關系的頂點集合為SV，相應的有向邊集合為SE，＞1.考慮任意路徑pID∈SE，設其長度為n.

根據(jù)第一種情況可知，每條邊上的兩點所代表的對象具有相同的矩形代數(shù)關系，且在加入的過程中，當前加入的頂點和路徑的起始點也具有相同的空間關系，那么路徑上的n+1個頂點所代表的對象中，任意兩個對象間均具有相同的矩形代數(shù)關系，且由于pID∈SE，路徑上的n+1個頂點也都屬于集合SV，所以這n+1個頂點也都和(i，j)具有相同的矩形代數(shù)關系.當把pID路徑上的邊和頂點依次加入RASG(i，j)時，需要增加一條從(i，j)到(k，h)有向邊并為其賦值pID.此時，路徑的長度變成n+1，并且這n+2個頂點中任意兩個頂點的矩形代數(shù)關系也保持一致.因此，這條路徑表示的意義同無向圖中最大團的意義是一樣的.至此，我們把求無向圖的最大團問題轉(zhuǎn)化為求有向圖中最長路徑的問題.

同時，從算法中可見，構建RASG(i，j)時只考慮RASG(k，h)，其中，k＜i，h＜j;同時，若RASG(k，h)中第一個頂點(k，h)和(i，j)不滿足相同的空間關系，則RASG(k，h)其余頂點均不必再考察，這個候選圖RASG(k，h)直接被刪減掉.這樣，求解最長路徑問題比求解最大團問題顯著減少了時間.

3 結果分析

3.1 實驗數(shù)據(jù)

本實驗數(shù)據(jù)分為人工構造數(shù)據(jù)集和Simplicity system數(shù)據(jù)庫.人工構造數(shù)據(jù)集用來比較SRRA和CPM的檢索時間，Simplicity system數(shù)據(jù)庫用來比較SRRA和CPM的檢索效果.為與CPM使用的對象信息一致，本研究在構造每個對象的MBR時隨機生成對象符號、(xinf，yinf)坐標和最小外界矩形的長l、寬w，則xsup=xinf+l，ysup=yinf+w，對象的幾何中心點表示為(xcen，ycen)，其中xcen=(xinf，xsup)/2，ycen= (yinf，ysup)/2;Simplicity system 數(shù) 據(jù) 庫(http://wang.ist.psu.edu/docs/related/)需要人工對圖像進行符號標注處理，這個過程對應算法SRRA建立符號化圖像數(shù)據(jù)庫的過程.

3.2 實驗結果

本實驗測試環(huán)境為:處理器Intel(R)Core(TM)2 Duo CPU E7500 2.93 GHz，內(nèi)存 2G，硬盤160 G，操作系統(tǒng)為Windows XP，編程環(huán)境為Visual Studio 2008.

首先復原CPM，然后基于CPM改進得到SRRA.圖3是SRRA與CPM隨著圖像中對象數(shù)目不同，每圖所需檢索時間對比結果.

圖3 SRRA與CPM平均一次的檢索時間對比Fig.3 The average cost of SRRA and CPM

測試集1～3中每組包括1 000張圖像，每張圖包含的對象數(shù)分別是5、10和15;測試集4～6中每組2 000張圖像，每張圖包含的對象數(shù)分別是5、10和15.由圖3可見，SRRA算法在各組測試集上的檢索時間均遠小于基于CPM的算法.這是因為CPM算法用type-i方法判斷對象的相似性，會將很多原本不同的拓撲關系表示為相同的方位關系，所以在構建CP_DAG的過程中，不相關的頂點和空間關系都被加入CP_DAG，構建時間顯著增加.SRRA算法采用的矩形代數(shù)比type-i需要更復雜的判斷，使時間略增，但檢索過程中空間關系判斷的耗時極少，大部分時間都用來構建RASG，而矩形代數(shù)能嚴格衡量空間關系相似，所以構建RASG過程中可擴展的頂點和邊都很少，構建時間顯著縮短.在檢索大對象數(shù)目時，SRRA算法優(yōu)勢明顯，如圖3中第3組和第6組對比結果.圖4對比了SRRA算法和CPM算法模擬檢索耗時.測試集7～8每組包括1×105張圖片，每張圖片包含的對象數(shù)目分別是5張和10張.用這組模擬數(shù)據(jù)考察圖像數(shù)目多，每張圖像內(nèi)包含對象數(shù)目小的特點.由圖4可知，在海量數(shù)據(jù)中檢索圖像時，SRRA較CPM可縮短一半的檢索耗時.

圖4 對比SRRA與CPM在1×105張圖片中檢索1張的耗時Fig.4 The total cost of SRRA and CPM running on massive image database

關于CPM和SRRA的說明:

①在對象投影到x軸和y軸上的線段均是彼此分離的情況下，基于CPM的算法和SRRA算法的相似性度量結果一致，基于CPM的算法效率更高，這種情況在現(xiàn)實中很少發(fā)生;

②當兩幅圖中僅有一組符號相同的對象時，只能得到其位置信息，無法得到對象間的空間關系，此時CPM和SRRA都不適用，這種情況在實際檢索中也較罕見.

圖5是SRRA和CPM在Simplicity system數(shù)據(jù)庫以5(a)為查詢圖像推薦結果，圖5(b)是SRRA推薦的7幅圖像，圖5(b)和(c)是CPM推薦的13幅圖像.相似性圖像檢索只需兩圖像中對象集合有交集即可，所以圖5(b)和(c)中可出現(xiàn)多個對象.設圖5(a)棕色馬為A，白馬為B.CPM僅比較對象的幾何中心點的方位關系，圖5所有圖像中A的中心點均位于B的中心點的NS方向，故CPM推薦(b)、(c)兩組圖像;(a)中A和B投影在x軸的關系是precede，在y軸的關系是start，而(c)中A和B在x軸的關系是overlap，SRRA認為圖5(c)中A和B的拓撲關系與圖5(a)中A和B的拓撲關系不一致，故SRRA不推薦圖5(c)的圖像.在本實驗中，若把最大相似對象數(shù)目為2的圖像推薦為檢索結果，則CPM推薦的結果大約比SRRA推薦的結果多50%，而這50%的結果多為不能嚴格滿足拓撲關系的圖像，這在后續(xù)的相關反饋步驟里也會給用戶帶來復雜的選擇.

圖5SRRA和CPM的推薦結果Fig.5 The recommended result of CPM and SRRA

結 語

本研究在CPM的基礎上，采用矩形代數(shù)描述對象間的拓撲關系，提出基于矩形代數(shù)的相似性圖像檢索算法SRRA.在8組人工構造測試數(shù)據(jù)集和Simplicity system數(shù)據(jù)庫上對兩種算法進行了實驗對比，結果表明，SRRA不僅在時間上優(yōu)于CPM，且檢索結果更符合用戶需求.下一步，我們將在SRRA算法的基礎上引入相關反饋算法［17-18］.由于傳統(tǒng)的相關反饋算法大都針對數(shù)值化特征向量進行修正，在基于空間關系相似性的CBIR中無法使用［19］，因此，在未來研究中，我們將致力于把所有圖像符號化后求得的字符串看做一個有序數(shù)據(jù)庫，針對有序數(shù)據(jù)庫進行序列模式挖掘，以此找到用戶選擇的正例集合中有效的空間信息;根據(jù)空間關系具有復合的性質(zhì)，我們打算采用矩形代數(shù)基本關系復合、路徑一致原理［20］相結合的方法，完成空間關系的復合計算，達到查詢圖像重定義的目的.

/References:

［1］Datta R，Joshi D，LI Jia，et al.Image retrieval:ideas，influences，and trends of the new age ［J］.ACM Computing Surveys，2008，40(2):1-60.

［2］Gudivada V N，Raghavan V V.Design and evaluation of algorithms for image retrieval by spatial similarity ［J］.ACM Transactions on Information Systems，1995，13(2):115-144.

［3］El-Kwae E A，Kabuka M R.A robust framework for content-based retrieval by spatial similarity in image databases［J］.ACM Transactions on Information Systems，1999，17(2):174-198.

［4］WANG Ying-hong.Image indexing and similarity retrieval based on spatial relationship model［J］.Information Sciences，2003，154(1/2):39-58.

［5］YIN Peng-yeng，LIU Chin-wen.A new relevance feedback technique for iconic image retrieval based on spatial relationships ［J］.The Journal of Systems and Software，2009，82(4):685-696.

［6］Hsieh Shu-Ming，Hsu Chiun-Chieh.Retrieval of images by spatial and object similarities［J］.Information Processing and Management，2008，44(3):1214-1233.

［7］Hsieh Shu-Ming，Hsu Chiun-Chieh.Graph-based representation for similarity retrieval of symbolic images ［J］.Data and Knowledge Engineering，2008，65(3):401-418.

［8］Chiang J Y，Cheng Shuenn-ren，Huang Shuenn-Reng，et al.Multiple-instance image database retrieval by spatial similarity based on interval neighbor group［C］//Proceedings of the ACM International Conference on Image and Video Retrieval CIVR'10.Xi'an(China):ACM Press，2010:135-142.

［9］Wang Hui-hui，Mohamad Dzulkifli，Lsmail N A.Semantic gap in CBIR:automatic objects spatial relationships semantic extraction and representation［J］.International Journal of Image Processing，2010，4(3):192-204.

［10］Rezaei-Kalantari Kimia，Eftekhari-Moghadam A M.Symbolic image indexing and retrieval by spatial similarity:a new approach based on multi-dimensional B+tree［C］//The 4th International Conference on New Trends in Information Science and Service Science(NISS).Gyeongju(Korea):［s.n.］，2010:145-152.

［11］Allen J F.Maintaining knowledge about temporal intervals［J］.Communications of the ACM，1983，26(11):832-843.

［12］Balbiani P，Condotta J F，L Del Cerro L F.A new tractable subclass of the rectangle algebra［C］//Proceedings of the 16th International Joint Conference on Artificial Intelligence.San Francisco(USA):Morgan Kaufmann Publishers，1999:442-447.

［13］CHEN Juan.Research on Spatial Directional Relation Models and Integrative Reasoning of Multi-aspect Spatial Relations［D］.Changchun:Jilin University，2011.(in Chinese)陳 娟.空間方位關系模型及多方面空間關系結合推理的研究 ［D］.長春:吉林大學，2011.

［14］DONG Yi-qun.Research on Some Problems of Qualitative Spatial Direction Relations Modeling［D］.Changchun:Jilin University，2011.(in Chinese)董軼群.定性空間方向關系建模中若干問題研究［D］.長春:吉林大學，2011.

［15］Hoàng Nguyen Vu，Gouet-Brunet Valérie，Rukoz Marta.A cartography of spatial relationships in a symbolic image database［J］.Proceedings of the 14th International Conference on Computer Analysis of Images and Patterns:Part I.Berlin:Springer-Verlag，2011，6854:377-385.

［16］Lee Suh-yin，Shan Man-kwan，YANG Wei-pang.Similarity retrieval of iconic image database［J］.Pattern Recognition，1989，22(6):675-682.

［17］LIU Lin，LI Ren-fa，LI Zhong-sheng，et al.Research on relevance feedback in contrent-based image retrieval［J］.Application Research of Computers，2009，26(7):2427-2431.(in Chinese)劉 琳，李仁發(fā)，李仲生，等.基于內(nèi)容圖像檢索中的相關反饋技術研究 ［J］.計算機應用研究，2009，26(7):2427-2431.

［18］XU Xiang-li，ZHANG Li-biao，LIU Xiang-dong，et al.Image retrieval relevance feedback algorithm based on particle swarm optimization ［J］.ACTA Electronica Sinica，2010，38(8):1935-1940.(in Chinese)許相莉，張利彪，劉向東，等.基于粒子群的圖像檢索相關反饋算法 ［J］.電子學報，2010，38(8):1935-1940.

［19］YIN Peng-yeng，LIU Chin-wen.A new relevance feedback technique for iconic image retrieval based on spatial relationships ［J］.The Journal of Systems and Software，2009，82(4):685-696.

［20］XING Shi-mei.Research on Consistency Techniques in Constraint Satisfaction Problems［D］.Changchun:Jilin University，2011.(in Chinese)邢士美.約束滿足問題中相容技術的研究 ［D］.長春:吉林大學，2011.