基于分散分配的非對稱距離倒排索引機制研究

寶航

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

【關鍵詞】倒排索引 非對稱距離計算 分散分配

1 引言

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

2 基于視覺詞的倒排索引結構

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

在標準的基于視覺詞的倒排索引結構中，每個視覺詞與一個倒排的列表關聯，列表中存儲圖像的識別和圖像中發生的視覺詞的頻率。給定一個查詢圖像，轉換為BOF描述符后，與查詢圖像中視覺詞關聯的倒排列表將作為檢索后續結果集。如果在查詢圖像中有1000個視覺詞發生，則需要1000個倒排列表進行檢索。因此，一些粗量化（包含少量的聚類）的方法被提出來以減少檢索的倒排列表數量，提供時間性能。

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

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

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

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

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

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

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

（2）預先計算所有數據點到支點距離并進行全局量化。

根據之前所選取的支點，計算出數據集中所有數據點到支點的距離，將高維特征向量Oi映射為{d（Oi，p1 ），d（Oi，p2），...，d（Oi， pj）}，pj 為支點，j 為支點個數，這樣得到低維向量，在低維情況下聚類算法將會有很好的效果，使用 k-means 方法對映射的向量進行聚類，在聚類過程中同時獲取兩個與向量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；

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

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

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

（7）對倒排索引鏈表進行哈希，生成哈希表進行索引：

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

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

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

4 結束語

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

參考文獻

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

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

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

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

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

[6]張志遠，徐恒盼.一種基于倒排索引的多維網絡存儲模型[J].計算機技術與發展，2016（04）：1-6.

作者單位

遼寧民族師范高等專科學校 遼寧省阜新市 123000