基于分散分配的非對(duì)稱距離倒排索引機(jī)制研究

寶航

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

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

1 引言

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

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

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

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

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

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

3 基于分散分配的非對(duì)稱距離計(jì)算倒排索引機(jī)制

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

該索引機(jī)制建立的主要過(guò)程如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

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

作者單位

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