張媛媛，楊洪娟，朱匯龍

（1. 昆明理工大學(xué)信息工程與自動化學(xué)院計算機(jī)技術(shù)，云南 昆明 650500；2. 昆明理工大學(xué)信息工程與自動化學(xué)院計算機(jī)技術(shù)，云南 昆明 650500）

0 引言

圖像檢索技術(shù)成為近年來多媒體領(lǐng)域的研究熱點，在社會各行業(yè)領(lǐng)域都起到很重要的作用。其實它是將圖像的視覺內(nèi)容描述成高維數(shù)字特征信息，然后把圖像檢索問題轉(zhuǎn)化成能相似查詢的高維數(shù)據(jù)問題。隨著網(wǎng)絡(luò)科技的飛速發(fā)展，許多領(lǐng)域?qū)τ趫D像信息的應(yīng)用頗多。在圖像數(shù)據(jù)庫規(guī)模不斷增多的背景之下,我們要對目標(biāo)信息進(jìn)行查詢與定位，這種問題直接關(guān)系到數(shù)據(jù)庫的利用價值，而此時如何建立一種高效良好的高維索引結(jié)構(gòu)就發(fā)揮它的重要性了。因此我們需要從圖像檢索技術(shù)角度來分析它的發(fā)展趨勢以及主要應(yīng)用方向。本文是研究圖像視覺特征檢索技術(shù)中構(gòu)建索引結(jié)構(gòu)的方法，為了實現(xiàn)這個目的，我們需要從整個技術(shù)涉及到的基礎(chǔ)來入手[1]。

一些國內(nèi)外的許多研究人員開始選擇降維的方向，有些選擇側(cè)重于如何構(gòu)建合適的索引方式。常用的降維方法有K-L變換以及聚類等。但是隨意降維并不是個安全的舉措，因為降維會在一定程度上損失關(guān)鍵圖形信息。很多研究學(xué)家充分利用互聯(lián)網(wǎng)的文本資源來做理解圖像，高維向量的檢索是非常關(guān)鍵的部分，隨著圖像維數(shù)的增多，未來對于圖像檢索的要求也越來越高，因此目前越來越多的研究著重于如何發(fā)現(xiàn)潛在的低維結(jié)構(gòu)，以及如何利用高維數(shù)據(jù)來探索尋找低維空間與高維空間之間的關(guān)系，來建立特定的索引結(jié)構(gòu)幫助人們來處理更大量的數(shù)據(jù)信息[2]。

1 高維索引結(jié)構(gòu)研究相關(guān)知識

1.1 向量空間和度量空間的高維索引結(jié)構(gòu)

高維索引方法分為兩大類別：一類是向量空間索引結(jié)構(gòu)SAM，另一類是度量空間索引結(jié)構(gòu)MAM。下面將簡單闡述這兩類索引結(jié)構(gòu)的區(qū)別，然后在給出這兩類中比較常見的索引結(jié)構(gòu)。

向量空間和度量空間中索引結(jié)構(gòu)的區(qū)別：其實在一定條件下，這兩種結(jié)構(gòu)是可以互相轉(zhuǎn)化的。一方面，如果有一個已經(jīng)定義好的距離函數(shù)時，向量空間就可以利用這個函數(shù)轉(zhuǎn)換成度量空間。另一方面，在做相似查詢計算距離函數(shù)時，兩者的算法執(zhí)行主要代價不同。MAM是占用cpu的代價，而SAM是磁盤讀取時的I/O代價[3]。不僅如此，在MAM中用到的唯一距離函數(shù)方法是三角不等式性質(zhì)；而在SAM中更著重利用坐標(biāo)信息，因此它具有更大的靈活性，例如后面將涉及到的K-D-B-tree算法就是一個很好的例子。

下面介紹向量空間中的高維索引結(jié)構(gòu)R-tree以及度量空間中的M-tree。

（1）R-tree

R-tree屬于動態(tài)索引結(jié)構(gòu)，動態(tài)性表現(xiàn)在做插入和刪除操作時并不影響查詢操作。R樹的每個結(jié)點對應(yīng)一個磁盤頁，根結(jié)點或者不是葉子結(jié)點的每個磁盤頁會包含它的子結(jié)點的區(qū)域范圍，因此這些子結(jié)點的磁盤頁也會在相應(yīng)的區(qū)域范圍之內(nèi)。如圖是個簡單的 R-tree，它反映了 R-tree的結(jié)構(gòu)特點。我們可以很明顯的看到，A空間包含 C，D，E，F(xiàn)的區(qū)域，B空間包含G，H，I，J這四個區(qū)域，所以很容易畫出這種樹的結(jié)構(gòu)。

（2）M-tree

它是一顆平衡樹，中間結(jié)點的結(jié)構(gòu)比較特殊，是對于VP—tree的改進(jìn)，減少了距離計算次數(shù)，是一種有效的高維索引結(jié)構(gòu)。

1.2 高維索引結(jié)構(gòu)存在的問題

圖像是向人類傳遞信息的重要媒體之一，圖像的優(yōu)點便是直觀簡便，但是向人們傳遞各種信息的能力是毋庸置疑的。有一種現(xiàn)象叫做“維度災(zāi)難”。在大量數(shù)據(jù)的背景下，內(nèi)存資源變成一種停滯不前的狀態(tài)，而有那種基于磁盤的查找又會影響到查詢的效率[4]。那么如何對這樣大量的圖像數(shù)據(jù)建立高維索引來滿足查詢的需求就變得很重要。不僅如此，像這種傳統(tǒng)的高維索引建立方法一般來說都是獨立的，它沒有指出特征本身所具有的數(shù)據(jù)共性，因此這對檢索性能的提高是相當(dāng)有限的。所以難點就暴露出來了，我們需要挖掘視覺特征的潛在信息，然后利用該信息去建立高維索引，這樣才能提高檢索效率，當(dāng)然這不僅是難點也是研究的新熱點。而圖像檢索有兩個研究方向，一個是數(shù)據(jù)管理，另一個是計算機(jī)視覺。區(qū)別就在于數(shù)據(jù)管理是文本描述，而計算機(jī)視覺是視覺描述。對于前者始于上世紀(jì)70年代末期，本文研究的是后者雖然研究學(xué)家研究出了許多索引方法，但仍然沒有完全解決 “維度災(zāi)難”的問題。

2 距離度量公式

2.1 明可夫斯基距離

一個圖像檢索的性能好壞不止取決于所提出的圖像特征，查詢的關(guān)鍵還在于所使用的距離度量函數(shù)。它直接關(guān)系到檢索的結(jié)果和檢索效率[5]。明可夫斯基距離是基于Lp范數(shù)定義的：

如果p=l，L1(A, B)稱為城區(qū)距離(city—block)，也就是絕對值距離；

如果 p=2，L2(A, B)稱為歐式距離（Euclidean distance）：

如果 p→∞，L→(A, B)稱為切比雪夫距離（Chebyshev distance）：

2.2 馬氏距離

馬氏距離可以有效計算兩個未知特征向量的相似度。數(shù)學(xué)表達(dá)式為：

其中C為特征向量的協(xié)方差矩陣。這個距離標(biāo)準(zhǔn)常用來計算SAR（Simultaneous Auto Regressive）特征的相似度。將馬氏距離進(jìn)一步簡化，表示如下：

假如Q為檢索對象，D為一系列數(shù)據(jù)庫中的任意圖像，m和n是方向和尺度，提取的特征向量為m×n維，則兩者之間的相似度量如下：

其中， dmn(Q,D)表示檢索圖像Q和D在相應(yīng)條件下的歐式距離，μmn表示相應(yīng)尺度和方向下各像素的均值，σmn表示相應(yīng)尺度和方向下各像素的方差， ? (?mn)和 ? (σmn)表示各自特征的標(biāo)準(zhǔn)差。表達(dá)式如下：

2.3 曼哈頓距離

曼哈頓距離又名CBD（City Block distance），它表示的是再某一空間的直角坐標(biāo)系上存在兩點構(gòu)成的線段映射在x，y軸的距離之和。對于給定平面上的兩點 A (x1,y1)和 B (x2, y2)之間的CBD距離為：

如果有兩個 n維向量 A = ( x11,x12, … ,x1n)與B = ( x21, x22, … x2n)之間的曼哈頓距離為：

2.4 歐式距離

用來判斷歐式空間中兩點之間的直線距離，本文后面將采用歐式距離公式。平面上兩點 A (x1,y1)和B(x2, y2)之間的歐式距離公式為：

如果有兩個 n維向量 A = ( x11,x12, … ,x1n)與B = ( x21, x22, … x2n)之間的歐式距離為[6]：

3 構(gòu)建SY-tree算法思想及實現(xiàn)過程

本節(jié)將首先介紹建立 SY-tree之前所要用到的K-means聚類方法，再介紹VP-tree的基本原理以及構(gòu)造方法，然后又這兩個基礎(chǔ)就可以設(shè)計一種新的高維索引結(jié)構(gòu)SY-tree，方便給出下一節(jié)的實驗分析。

3.1 K-means聚類方法基本原理

通常的K-means聚類方法是一種聚類劃分的技術(shù)，K-means算法的工作過程大致如下：我們從多個給定對象中隨意選取 k個對象做為初始聚類中心，剩下來的就根據(jù)它們自己與這些k個操作對象的距離，分別把它們分配給與各自最相似的聚類，然后再計算每個新聚類中的對象的均值，依次重復(fù)上述相同的操作直到標(biāo)準(zhǔn)測度函數(shù)是收斂的，大多數(shù)情況下標(biāo)準(zhǔn)測度函數(shù)是均方差[7]。

3.2 VP-tree基本原理

VP-tree是一種基于距離的屬于MAM的索引結(jié)構(gòu)，是一顆平衡二叉樹，具有平衡二叉樹的特性。它的構(gòu)造和搜索算法并不是特別的難，主要是利用二分查找的方法實現(xiàn)高維空間距離信息的搜索。VP-tree的構(gòu)造和搜索算法如下。假設(shè)一個含有n個對象的數(shù)據(jù)集 S={S1, S2, …Sn}和度量空間距離函數(shù)d(Si, Sj)，現(xiàn)在來構(gòu)造VP-tree，算法如下：

步驟1：如果|S|=0，則為空樹；

步驟 2：如果不為空，則從 S中任取一個對象Sv，作為參考點vantage point，令M為S中所有對象與Sv的距離值，其中對象與Sv的距離小于M的數(shù)據(jù)集構(gòu)成左子樹，對象與Sv的距離大于M的數(shù)據(jù)集構(gòu)成右子樹。集合表達(dá)式為：Sr={Sj|d(Sj,Sv)≦M,Sj∈S,Sj≠Sv}；

步驟3：遞歸構(gòu)造VP-tree。它的搜索方法也是利用遞歸，假設(shè)存在查詢對象Q和距離范圍r：

（1）如果d(Q,Sv)小于等于r，則返回Sr；

（2）如果d(Q,Sv)+r大于等于M，遞歸查找右子樹Sr；

（3）如果d(Q,Sv)-r小于等于M，遞歸查找左子樹Sl[8]。

3.3 SY-tree的算法設(shè)計思想

仿照上述K-means聚類方法以及 VP-tree的基本原理[9]，我給出構(gòu)建SY-tree這個索引結(jié)構(gòu)SY-tree的設(shè)計思想：首先從大量數(shù)據(jù)對象中選取k個對象做初始聚類中心，利用得到k個聚類；再將這些聚類的中心點集中在一個結(jié)點中；然后以中心點為參考點，令 r是所有對象與中心點的距離中值，與中心點的距離小于 r的構(gòu)成左子樹，相應(yīng)的與中心點距離大于 r的構(gòu)成右子樹；依次重復(fù)上述操作，直到它的左子節(jié)點或者右子節(jié)點中的個數(shù)小于r；對于個數(shù)小于 r的左子節(jié)點或者右子節(jié)點，把它們作為葉子結(jié)點，在該結(jié)點中存放實際數(shù)據(jù)對象和相關(guān)信息。如此一來SY-tree的結(jié)點結(jié)構(gòu)也形成了。我所設(shè)計的SY-tree只是在VP-tree的基礎(chǔ)上運用了K-means聚類，并且聚類時計算的距離采用的是歐式距離公式，也就是說SY-tree的中間結(jié)點含有k個小聚類的聚類中心Oi(i=l，…，k)，中間結(jié)點中整體結(jié)構(gòu)形式如下圖所示。Si代表該中間結(jié)點中第i個聚類[10]。

圖2 中間結(jié)點整體結(jié)構(gòu)形式Fig.2 The overall structure of the intermediate node

SY-tree的中間結(jié)點中其他聚類的參考點數(shù)據(jù)結(jié)構(gòu)如下圖所示：

圖3 各聚類的參考點數(shù)據(jù)結(jié)構(gòu)Fig.3 Reference point data structure for each cluster

3.4 SY-tree的實現(xiàn)過程

有了以上SY-tree的設(shè)計思想和結(jié)點結(jié)構(gòu)，開始對它用c語言進(jìn)行構(gòu)造：首先我們從含有N個對象的集合中選取k個對象做為初始聚類中心，其余對象根據(jù)它們與這些聚類中心的距離分別把各自分配給與其最相似的聚類；然后根據(jù)每個聚類的均值，計算聚類中每個對象與其相應(yīng)中心對象的距離，并根據(jù)最小距離重新劃分，再計算每個新聚類的均值[11]；重復(fù)上述操作直到不再有變化。此時，返回每個聚類Si的中心對象，并返回每個聚類的覆蓋半徑R(On)。然后把這些聚類中心Ol，…，Ok，作為每個聚類的參考對象，令M為所有對象與中心Qi的距離中值。同樣的，把與Qi的距離小于M的集合構(gòu)成左子樹，距離大于 M 的集合構(gòu)成右子樹。如果左子樹/右子樹中對象個數(shù)小于等于m，則以左子樹/右子樹中的對象做為實際數(shù)據(jù)建立其相應(yīng)的葉子結(jié)點；同樣的，如果左子樹/右子樹中對象個數(shù)大于m，遞歸調(diào)用之前的步驟。這樣就創(chuàng)建完成SY-tree。

4 實驗結(jié)果與分析

4.1 測試方案

為了測試建立的索引結(jié)構(gòu) SY-tree是否有提高檢索在距離計算次數(shù)、檢索效率以及精準(zhǔn)度方面的性能，我們做出以下3個方案：

（1）首先我們選擇4100副64×64像素的圖像，采集其中 16維，64維的數(shù)據(jù)特征向量組成集合，對這些數(shù)據(jù)集分別采用VP-tree和SY-tree索引結(jié)構(gòu)，最后根據(jù)這兩種結(jié)構(gòu)進(jìn)行相關(guān)查詢。其中，選擇SY-tree中2個對象作為初始聚類中心，葉子結(jié)點中對象個數(shù)m取6，利用matlab編程環(huán)境求得距離計算次數(shù)，分析它的性能[8]。

（2）采集16維的數(shù)據(jù)特征向量組成集合，分別利用VP-tree和SY-tree的索引結(jié)構(gòu)來查詢，根據(jù)不同數(shù)據(jù)量來得到相應(yīng)的查詢時間，從而分析他們各自的檢索效率。

（3）采集16維的數(shù)據(jù)特征向量組成集合，分別選擇10，20，30，40，50個數(shù)據(jù)對象進(jìn)行查詢，也就是進(jìn)行10~50次等分查詢，根據(jù)經(jīng)查詢后的對象是否在聚類中來檢測兩個不同索引結(jié)構(gòu)的平均精準(zhǔn)度。

4.2 實驗環(huán)境

MATLAB軟件是1984年由美國Math Work公司推出的一款商業(yè)數(shù)學(xué)軟件，在進(jìn)行數(shù)據(jù)挖掘、算法開發(fā)、數(shù)據(jù)分析處理、圖形圖像處理、仿真等都有著廣泛的用處。MATLAB軟件以其簡便強(qiáng)大的功能迅速占領(lǐng)市場，被眾多鄰域青睞。MATLAB軟件包含龐大的數(shù)學(xué)算法資源，包含我們上面提到的距離度量函數(shù)，可以方便的實現(xiàn)用戶所需要的各種計算需求。本章將通過實驗對 VP-tree和已經(jīng)創(chuàng)建的SY-tree進(jìn)行比較，并給出對比結(jié)果并進(jìn)行定量分析。

測試使用的軟件環(huán)境如下：

（1）操作系統(tǒng)平臺：Microsoft Windows 8。

（2）編程環(huán)境：Matlab R2011a。

4.3 測試結(jié)果與分析

（1）如圖4所示采集16維的數(shù)據(jù)集一次性搜索可得性能評價，隨著查詢范圍的增大兩個索引結(jié)構(gòu)的距離計算次數(shù)也在相應(yīng)的增加，但是兩者增加幅度相差甚遠(yuǎn)，SY-tree的距離計算次數(shù)明顯小于VP-tree。

（2）如圖5所示采集64維的數(shù)據(jù)集一次性搜索可得性能評價，隨著查詢范圍的增大兩個索引結(jié)構(gòu)的距離計算次數(shù)也在相應(yīng)的增加，并且這種高維的增加也會導(dǎo)致距離次數(shù)增加，但是兩者增加幅度依然相差甚遠(yuǎn)，也就是SY-tree的距離計算次數(shù)明顯小于VP-tree。

圖5 一次性搜索64維數(shù)據(jù)集的性能Fig.5 Perform a one-time search on the performance of a 64-dimensional dataset

（3）如圖6所示，當(dāng)選取16維的數(shù)據(jù)集進(jìn)行不同條數(shù)的數(shù)據(jù)量查詢，我們可以很明顯的看到，當(dāng)數(shù)據(jù)量在500條的時候，VP-tree與SY-tree的查詢時間相同，隨著數(shù)據(jù)量的增加VP-tree的查詢時間明顯比 SY-tree的查詢時間要大，故由此可看到SY-tree比VP-tree的查詢效率高。

圖6 對不同數(shù)據(jù)量的查詢時間Fig.6 Query time for different data volumes

（4）如圖7所示，當(dāng)選取16維的數(shù)據(jù)集分別選擇 10~50個數(shù)據(jù)對象搜索時，分別采用 VP-tree和 SY-tree檢索時的平均精準(zhǔn)度，可以很清楚的發(fā)現(xiàn)，無論進(jìn)行多少次查詢，SY-tree查詢的準(zhǔn)確率都要高于VP-tree，并且隨著數(shù)據(jù)對象的增多，精準(zhǔn)度都會有所下降，故有此可見，查詢數(shù)據(jù)時 SY-tree的精準(zhǔn)度比VP-tree的精準(zhǔn)度要高。

圖7 對不同數(shù)據(jù)個數(shù)的查詢精準(zhǔn)度Fig.7 The number of different data query accuracy

綜上所述，我們可以明顯看到設(shè)計的 SY-tree是一種靜態(tài)非平衡樹，在每次構(gòu)建樹的過程中都使用了K-means聚合，與 VP-tree索引方法相比減少了距離計算次數(shù)，大大提高了檢索效率。

5 結(jié)論

在本文中，我們描述了一種面向圖像視覺特征檢索的高維索引結(jié)構(gòu)。運用到了圖像視覺特征檢索原理和高維索引領(lǐng)域研究基礎(chǔ)知識，并且分析了數(shù)據(jù)間距離公式，選擇合適的距離公式來設(shè)計一種新的高維索引結(jié)構(gòu) SY-tree。并將其與之前的 VP-tree進(jìn)行對比，證實了該索引結(jié)構(gòu)的高效性及精準(zhǔn)性。

[1] 王崇錦. 面向圖像檢索的視覺特征提取及語義[D]. 吉林:長春工業(yè)大學(xué)圖書館, 2016.

[2] 黃元元, 等. 一種基于顏色特征的圖像檢索方法[J]. 中國圖像圖形學(xué)報, 2006, 16(4): 265-322.

[3] 嚴(yán)蔚敏, 等. 數(shù)據(jù)結(jié)構(gòu)(c語言版)[M]. 北京: 清華大學(xué)出版社, 2011.

[4] 吳企淵, 等. 計算機(jī)操作系統(tǒng)(第2版)(教育部人才培養(yǎng)模式改革和開放教育試點教材)[M]. 北京: 清華大學(xué)出版社,2003.

[5] TonyF.Chan,等. 圖像處理與分析[J]. 北京: 科學(xué)出版社,2009.

[6] 陳永春, 等. MATLAB M語言高級編程[M]. 北京: 清華大學(xué)出版社, 2004.

[7] 張志涌, 等. 精通MATLAB R2011a[M]. 北京: 北京航空航天大學(xué)出版社, 2011.

[8] 于靜洋, 等. 海量數(shù)據(jù)的高維索引結(jié)構(gòu)研究[D]. 河南: 河南大學(xué)圖書館, 2010.

[9] 梁俊杰, 等. 大規(guī)模高維數(shù)據(jù)庫索引結(jié)構(gòu)[J]. 計算機(jī)研究與發(fā)展, 2006, 43(2): 546-551.

[10] Hutflesz A, Siz H-'Winmayer Pf Twin grid files: Space optimizing access schemes[C]. In: Proc.Of the ACM SIGMOD Int.Conf.on Management of Data, 1988, 183-190.

[11] Bentley J L, Friedman J H. Data structures for range searching[J]. ACM Compute. 1979, 11(4): 3997-4009.