寶航

摘 要 隨著計算機多媒體技術(shù)的快速發(fā)展，基于圖像內(nèi)容的檢索逐漸成為了熱點的研究問題。圖像的特征描述和特征索引機制的建立是實現(xiàn)基于內(nèi)容圖像檢索的關(guān)鍵。根據(jù)圖像局部特征向量與聚類中心的相對距離，建立非對稱距離計算倒排索引機制。為了進(jìn)一步提高查詢效率，本文將可能落入多條哈希鏈表中的數(shù)據(jù)庫向量進(jìn)行多次編碼，實現(xiàn)了基于分散分配的非對稱距離計算倒排索引機制。通過實驗可以發(fā)現(xiàn)，這種索引機制可以有效的提升查詢效率。

【關(guān)鍵詞】倒排索引 非對稱距離計算 分散分配

1 引言

如今，針對規(guī)模巨大的影像數(shù)據(jù)集，一般的檢索系統(tǒng)分為三個基礎(chǔ)步驟：特征提取、高維索引機制和檢索系統(tǒng)設(shè)計，而高維索引機制是快速、精確檢索的核心，高維索引結(jié)構(gòu)的構(gòu)建也是影像數(shù)據(jù)進(jìn)行建庫和檢索引擎模塊建立的重點。從數(shù)據(jù)庫里提取出來的數(shù)據(jù)特征表現(xiàn)為分散的、無序的向量，通過建立多維索引結(jié)構(gòu)將這些特征向量進(jìn)行有規(guī)律的存儲，其中索引結(jié)構(gòu)的設(shè)計是重點。一般，高維索引結(jié)構(gòu)主要分三類：基于樹的索引（tree-based index），基于哈希的索引（ hashing-based index）和基于視覺詞的倒排索引（ visual words based inverted index）方法。

2 基于視覺詞的倒排索引結(jié)構(gòu)

基于視覺詞的倒排索引源于基于內(nèi)容的圖像檢索，對于給定的圖像，首先提取出局部特征，如SIFT，然后量化為視覺詞，這些視覺詞字典是預(yù)先在訓(xùn)練數(shù)據(jù)集上訓(xùn)練得到的。然后，用BOF描述符的高維向量生成表示圖像。BOF描述符通過倒排索引文件方式進(jìn)行索引，該倒排索引文件中每個條目為每個視覺詞和發(fā)生該視覺詞的所有圖像的列表組成。描述符的構(gòu)建可以基于視覺詞所發(fā)生的頻率計數(shù)或tf-idf方法?；谝曈X詞的倒排索引主要集中在視覺描述符的構(gòu)造、描述符壓縮編碼和倒排索引結(jié)構(gòu)的研究。

在標(biāo)準(zhǔn)的基于視覺詞的倒排索引結(jié)構(gòu)中，每個視覺詞與一個倒排的列表關(guān)聯(lián)，列表中存儲圖像的識別和圖像中發(fā)生的視覺詞的頻率。給定一個查詢圖像，轉(zhuǎn)換為BOF描述符后，與查詢圖像中視覺詞關(guān)聯(lián)的倒排列表將作為檢索后續(xù)結(jié)果集。如果在查詢圖像中有1000個視覺詞發(fā)生，則需要1000個倒排列表進(jìn)行檢索。因此，一些粗量化（包含少量的聚類）的方法被提出來以減少檢索的倒排列表數(shù)量，提供時間性能。

非對稱距離計算倒排索引機制聚合了全局量化、積量化、非對稱距離計算以及倒排索引等關(guān)鍵技術(shù)。其中，全局量化是指在全局基礎(chǔ)上對整個數(shù)據(jù)空間進(jìn)行統(tǒng)一量化。量化是將原始向量經(jīng)某種方法獲取離散值，即用一組少量的、規(guī)定的向量來表示整個原始空間中的所有向量。k-means 方法中的聚類中心就是這樣一組規(guī)定的向量，是經(jīng)過訓(xùn)練集合均值聚類獲取的中心點，目的在于使用少量有代表性的數(shù)據(jù)來表示整個數(shù)據(jù)空間。非對稱距離計算是指非量化的查詢向量與量化后的數(shù)據(jù)庫向量之間的距離計算。使用非對稱距離計算更能體現(xiàn)對象之間的相似度，減小量化帶來的距離誤差。

非對稱距離計算倒排索引機制首先使用 k-means 方法對所有的特征向量進(jìn)行聚類，將數(shù)據(jù)庫中的特征向量分配給聚類，即進(jìn)行全局量化，然后將計算特征向量與所屬聚類中心之差獲得剩余向量，對所有的剩余向量進(jìn)行積量化，從而獲得積量化后的編碼連同數(shù)據(jù)的索引標(biāo)識組成哈希對，添加到對應(yīng)的聚類所屬的倒排索引鏈表中。使用 IVFADC 組織圖像的聚合向量，每幅圖像可用少至 20 字節(jié)的編碼表示，使得海量數(shù)據(jù)庫在內(nèi)存中的檢索成為可能。

3 基于分散分配的非對稱距離計算倒排索引機制

在多維索引機制中，“維度災(zāi)難”會隨著特征維度的增多而出現(xiàn)。在特征向量維度較高的情況下，傳統(tǒng)的樹型索引結(jié)構(gòu)表現(xiàn)并不理想。維度過高時，大多數(shù)索引方法的查詢性能甚至低于對原始數(shù)據(jù)進(jìn)行順序掃描的性能。高維數(shù)據(jù)檢索（high-dimentional retrieval）是一個有挑戰(zhàn)的任務(wù)。由于時間和空間的限制，將檢索數(shù)據(jù)與數(shù)據(jù)庫中的數(shù)據(jù)進(jìn)行一對一的相似度比較是無法實現(xiàn)的。決定檢索復(fù)雜程度的因素有兩個，一是高維向量的相似度比較，二是海量的數(shù)據(jù)檢索。第一個問題，可以用哈希算法對高維數(shù)據(jù)進(jìn)行降維。第二個問題，可以在檢索初期就排除掉一些數(shù)據(jù)來減小比較的次數(shù)。而位置敏感哈希類算法（LSH）恰好滿足了這一需求。位置敏感哈希類以及建立在 BOF 基礎(chǔ)上的倒排索引類是一種效果比較好的解決“維度災(zāi)難”的索引方法。本文介紹一種基于LSH的索引方法——基于分散分配的非對稱距離計算倒排索引機制（DA-IVFADC）。

該索引機制建立的主要過程如下：

（1）參考支點選擇，利用HF算法選擇支點，用于基于距離的降維。

HF支點選擇算法，首先在數(shù)據(jù)庫中選擇隨機的數(shù)據(jù)點A1，到距離A1最遠(yuǎn)的數(shù)據(jù)點B1，B1記為第一個支點，接下來離B1最遠(yuǎn)的支點B2，B2記為第二個支點，計算B1和B2之間的距離，并記為S。對數(shù)據(jù)庫的每一個數(shù)據(jù)點對象Ai，具有最小F值的對象即為下一個支點，重復(fù)最后一步，直到所有支點被選擇。一般選取的支點個數(shù)比高維特征向量的維度小很多。

（2）預(yù)先計算所有數(shù)據(jù)點到支點距離并進(jìn)行全局量化。

根據(jù)之前所選取的支點，計算出數(shù)據(jù)集中所有數(shù)據(jù)點到支點的距離，將高維特征向量Oi映射為{d（Oi，p1 ），d（Oi，p2），...，d（Oi， pj）}，pj 為支點，j 為支點個數(shù)，這樣得到低維向量，在低維情況下聚類算法將會有很好的效果，使用 k-means 方法對映射的向量進(jìn)行聚類，在聚類過程中同時獲取兩個與向量y最近的聚類中心，最近Ci與次近Cj；

（3）計算向量y與最近的兩個聚類中心的距離d（y，Ci）與d（y，Cj）；

（4）如果d（y，Cj） - d（y，Ci） ≥σ，則計算剩余向量r（y）= y - Ci，接步驟 5；

如果d（y，Cj） - d（y，Ci） < σ，則計算r1（y）= y - Ci、r2（y）= y - Cj，接步驟 6；

σ值可以將那些與多個聚類中心的距離相近的對象，同時分配到這些聚類中，以得到更佳的查詢結(jié)果。

（5）積量化r（y）得到p（ r（y） ），將得到的編碼以及PID 添加到所屬的聚類對應(yīng)的倒排索引鏈表i中；

（6）積量化r1（y）得到p（ r1（y） ），積量化r2（y）得到p（ r2（y） ），將得到的編碼以及PID 分別添加到所屬的聚類對應(yīng)的倒排索引鏈表i、鏈表j中。

（7）對倒排索引鏈表進(jìn)行哈希，生成哈希表進(jìn)行索引：

經(jīng)過積量化得到的編碼G（v）={ h1（v）， h2（v）， .. .hm（v）}，m為積量化參數(shù)（即向量等分子部分的數(shù)量），直接存入哈希表，即占用內(nèi)存又不便于查找，因此定義另外兩個哈希函數(shù)h1的值作為哈希表索引，h2的值作為鏈表中的關(guān)鍵值。ri 和ri'是隨機整數(shù)，C是一個大素數(shù)的取值為232-5，tableSize為哈希表的大小，則每個哈希表的結(jié)構(gòu)如圖1所示。

測試數(shù)據(jù)集是由機器隨機生成104個維度為64的浮點數(shù)向量，訓(xùn)練集合大小為25×103個向量，數(shù)據(jù)庫集合大小為104個向量，查詢集合100個向量。目的在于測試算法對于無規(guī)律、各個維度都完全獨立的非結(jié)構(gòu)化數(shù)據(jù)的查詢性能，如表1所示。

測試結(jié)果表明，本文的DA-IVFADC索引機制相對于傳統(tǒng)的IVFADC索引機制的查詢性能得到了一定的提升。

4 結(jié)束語

本文對基于分散分配的非對稱距離計算的倒排索引機制進(jìn)行了研究，研究表明該索引機制相對于傳統(tǒng)的索引機制的查詢性能得到了提升。但由于該索引機制的建立基礎(chǔ)是訓(xùn)練集合的編碼本，頻繁的插入刪除操作會使中心點產(chǎn)生偏移現(xiàn)象，進(jìn)而影響檢索的準(zhǔn)確性，而重新訓(xùn)練編碼本是不現(xiàn)實的。如何使該索引機制適應(yīng)頻繁的增刪操作，是下一步要研究的主要問題。

參考文獻(xiàn)

[1]何云峰，周玲，于俊清，徐濤，管濤. 基于局部特征聚合的圖像檢索方法[J].計算機學(xué)報，2011（11）：2224-2233.

[2]艾列富，于俊清，管濤，何云峰.大規(guī)模圖像特征檢索中查詢結(jié)果的自適應(yīng)過濾[J].計算機學(xué)報，2015（01）：122-132.

[3]汪昀，朱明，馮偉國.一種支持海量人臉圖片快速檢索的索引結(jié)構(gòu)[J].計算機工程，2015（03）：186-190.

[4]林俊鴻，姜琨，楊岳湘.倒排索引查詢處理技術(shù)[J]. 計算機工程與設(shè)計，2015（03）：572-575+580.

[5]王晶，王昊.融合局部特征和全局特征的視頻拷貝檢測[J].清華大學(xué)學(xué)報（自然科學(xué)版），2016（03）：269-272.

[6]張志遠(yuǎn)，徐恒盼.一種基于倒排索引的多維網(wǎng)絡(luò)存儲模型[J].計算機技術(shù)與發(fā)展，2016（04）：1-6.

作者單位

遼寧民族師范高等?？茖W(xué)校 遼寧省阜新市 123000