垃圾彩信中海量圖片檢索和聚類關(guān)鍵技術(shù)研究

杜剛，朱艷云，張晨，杜雪濤

（中國移動通信集團(tuán)設(shè)計院有限公司，北京 100080）

垃圾彩信中海量圖片檢索和聚類關(guān)鍵技術(shù)研究

杜剛，朱艷云，張晨，杜雪濤

（中國移動通信集團(tuán)設(shè)計院有限公司，北京 100080）

本文總結(jié)了不良違規(guī)圖片管理經(jīng)驗，詳細(xì)介紹了海量圖片相似檢索和聚類技術(shù)的諸多關(guān)鍵技術(shù)，包含視覺詞和嵌入碼的生成、索引、結(jié)果打分等，并給出了許多工程化的實踐經(jīng)驗。

圖片檢索；模式識別；視覺詞；圖片相似檢索

網(wǎng)絡(luò)中傳播的不良信息通常被傳播者篡改而衍生出許多相似的版本。在治理不良信息時，需要對大量不良圖片信息進(jìn)行相似聚類。常規(guī)的聚類方法已經(jīng)遠(yuǎn)遠(yuǎn)無法滿足生產(chǎn)的需要。借鑒海量圖片索引和檢索技術(shù)，可以大幅提高相似圖片的聚類效率。

在圖像處理和識別領(lǐng)域，SURF特征能夠有效的表示圖像的局部特征。這些特征是具有很好的魯棒性，針對圖片的尺度變換（縮放、旋轉(zhuǎn)）后，特征也不會發(fā)生變化，并且已經(jīng)成功的應(yīng)用于大量的圖像識別任務(wù)，如人臉識別，環(huán)境識別等。具體來說，一個SURF特征是一個64維實數(shù)空間中的一個點，一幅圖可能包含不定數(shù)量的SURF特征。如果將一個SURF特征當(dāng)做文檔中的一個詞，而一幅圖就可以看做包含若干詞的文檔。這是基于視覺詞的圖片檢索技術(shù)的基本思想。

然而，實數(shù)空間是可以無限細(xì)分的。理論上存在無限多個SURF特征。換言之，視覺詞有無限多個，語義粒度可以無限細(xì)致。過細(xì)的語義粒度有利于檢索的準(zhǔn)確率但不利于檢索的查全率。為了在這兩個指標(biāo)之間取得權(quán)衡，需要對SURF特征進(jìn)行粒度合適的聚類。在特定范圍內(nèi)的SURF特征被聚類到同一個視覺詞中。則可將視覺詞匯表限定在有限多個視覺詞之中。將圖片特征映射為視覺詞的方法成功的將文本搜索引擎技術(shù)引入到了圖像領(lǐng)域，使得對圖片的檢索性能和效果都得到了大幅提升。

1 相似圖片檢索框架

圖1為基于視覺詞和倒排索引的相似圖片檢索框架。如圖1所示，其整體分為圖片索引、圖片查詢和圖片排序3個步驟。圖片索引主要將需要進(jìn)行檢索的圖片進(jìn)行視覺詞化后加入到倒排索引。圖片查詢則將圖片視覺詞化后，構(gòu)成查詢語句。圖片排序是將倒排索引檢索的結(jié)果進(jìn)行相似度打分，從而使相似度高的圖片排在結(jié)果的前面。

圖1 基于視覺詞的圖片相似檢索框架

在進(jìn)行圖片索引時，需要先生成視覺詞典。視覺詞典的生成需要大量的圖片，這些圖片不一定是待檢索的圖片，但與待檢索圖片語義上越接近越好，且圖片量越大越好。視覺詞典構(gòu)建完成后，需要將待檢索的圖片映射為視覺地點當(dāng)中的視覺詞，并計算嵌入碼。最后，根據(jù)圖片所包含的視覺詞為圖片建立倒排索引。

在進(jìn)行圖片查詢時，首先需要提取查詢圖片的特征，并映射為視覺詞和嵌入碼。然后去倒排索引中獲取包含視覺詞的圖片。最后根據(jù)圖片包含查詢圖片視覺詞的多少和嵌入碼的一致性對圖片進(jìn)行打分排序。

2 視覺詞生成

為了將無限可能的特征映射到有限個視覺詞，需要對圖片的SURF特征分布空間進(jìn)行聚類劃分，將相近的特征聚類到一起。通常視覺詞的數(shù)量不能過少。過少的視覺詞并不能精確描述圖片的特征，從而導(dǎo)致查準(zhǔn)率下降。建議視覺詞數(shù)量定義在N=100 000以上?？梢娨曈X詞的聚類過程是非常耗時的。為了降低聚類的計算復(fù)雜度?？梢酝ㄟ^降維的方法將算法的復(fù)雜度降低到具體算法如圖2所示。

一個SURF特征有64維，將其平均分為兩部分，前32維特征和后32維特征。則所有的SURF特征的前32維向量和后32維向量分別進(jìn)行kmeans聚類。若要聚類100 000個聚類，前后32維聚類只需要分別聚類出個聚類。將前后32維的聚類結(jié)果分別進(jìn)行從0開始的編號，并保存起來，就形成了我們需要的視覺詞典。此時，前32維當(dāng)中的任何一個聚類中心都可以與后32維進(jìn)行排列組合形成317個64維的聚類中心。則實際上詞典的詞匯量為100 000。

采用如上降維方法進(jìn)行聚類的一個弊端是經(jīng)過前后32維排列組合產(chǎn)生的所有視覺詞并不一定都真實存在。舉例說明：假設(shè)有兩個SURF特征x，y。x{1，32}代表x的前32維，x{33，64}代表x的后32維。假定將前32維和后32維分別進(jìn)行kmeans聚類，聚類數(shù)量取2，則得到前32維向量聚類中心為x{1，32}和y{1，32}，后32維向量聚類中心為x{33，64}和y{33，64}。則可以得到4個SURF特征聚類中心：x{1，32}+x{33，64}、x{1，32}+y{33，64}、y{1，32}+x{33，64}和y{1，32}+y{33，64}。但實際上參與聚類的只有兩個SURF特征，根本不存在x{1，32}+y{33，64}和y{1，32}+x{33，64}。不過實驗證明，當(dāng)SURF特征的總體數(shù)量遠(yuǎn)遠(yuǎn)大于需要聚類的數(shù)量時，這種偽聚類中心出現(xiàn)的概率會降低。

圖2 視覺詞典生成算法流程、視覺詞映射和嵌入碼計算方法

視覺詞典生成后，需要將圖片中的SURF特征映射為視覺詞，也即映射到上一步得到的聚類中心的其中一個。首先，提取圖片的所有SURF特征，其次，將提取的SURF特征以同樣方式分為前32維和后32維。前后32維分別與視覺詞典中的前后32維聚類中心進(jìn)行最近鄰匹配，則可以得到前32維最近鄰聚類中心編號i和后32維最近鄰聚類中心編號j。則圖片包含的視覺詞編號為i×n+j，其中n為kmeans的聚類數(shù)量。經(jīng)過如上步驟，圖片每一個SURF特征都會映射為一個視覺詞的編號。則一幅圖像被映射為一個視覺詞編號的序列。

為了進(jìn)一步提高檢索效率，可以保存在映射視覺詞過程中，特征點與聚類中心之間的拓?fù)潢P(guān)系，形成嵌入碼。以便更細(xì)粒度的比較圖片的相似性。以二維空間為例，則二維空間中的點可表示為(x，y)。假設(shè)聚類中心為(x{1}，y{1})，特征點為(x{2}，y{2})。可用兩個二進(jìn)制位來表示特征點與聚類中心的拓?fù)潢P(guān)系，稱為嵌入碼。其中當(dāng)x{1}＞x{2}則嵌入碼第一個二進(jìn)制位為1，否則為0。其中當(dāng)y{1}＞y{2}則嵌入碼第二個二進(jìn)制位為1， 否則為0。則嵌入碼00、01、10和11分別代表特征點位于聚類中心4個象限?？梢詫⑦@個思路擴(kuò)展到64位，則可以形成一個64位的嵌入碼。在比較視覺詞時，可以進(jìn)一步比特征與聚類中心的拓?fù)潢P(guān)系?？梢砸郧度氪a之間的海明距離來計算嵌入碼的相似性。海明距離越少，則嵌入碼表示的拓?fù)潢P(guān)系越接近。

3 構(gòu)建視覺詞索引

在構(gòu)建視覺詞索引時，需要維護(hù)兩個序列。視覺詞編號序列以及相應(yīng)的嵌入碼序列。由于海明距離完全可以用位運(yùn)算很快完成（1 s內(nèi)可完成千萬次計算），可不對嵌入碼進(jìn)行索引。若將視覺詞編號序列看做文檔中的詞序列，則可參照文本檢索方法，形成視覺詞與圖片的倒排索引。假設(shè)圖片1包含視覺詞1、2，圖片2包含視覺詞2、3，則倒排索引結(jié)構(gòu)如圖3所示。

圖3 基于視覺詞的倒排索引示例

4 圖片檢索與打分排序

給定一張圖片，并獲取其中的視覺詞和嵌入碼后，可使用倒排索引快速的獲取包含與查詢圖片包含相同視覺詞的所有圖片。但獲取到的圖片包含查詢視覺詞的數(shù)量各有差異，需要設(shè)計一個打分規(guī)則將包含更多查詢視覺詞的圖片排在前面?？梢越梃b文本領(lǐng)域的基于tf-idf的打分方法對圖片排序進(jìn)行初步的打分，如式(1)所示。

其中式(2)中freq(t，d)為查詢詞t在文檔d中出現(xiàn)的次數(shù)，式(3)中maxDoc為文檔總量，docFreq(t)為包含查詢詞t的文檔量。

經(jīng)過tf-idf初步排序后，需要使用嵌入碼對排序結(jié)果進(jìn)行進(jìn)一步的優(yōu)化。此處引入嵌入碼吻合率計算，如式(4)所示。

fit(e{t，q}，e{t，d})=1-[hammingDist(e{t，q}，e{t，d})]/64(4)

式(4)中e{t，q}代表視覺詞t在查詢q中的嵌入碼，e{t，d}代表視覺詞t在圖片d中的嵌入碼。

則上述評分函數(shù)可以進(jìn)一步變化為式(5)：

score(q，d)∝∑t∈qtf(t，d)×idf(t)×fit(e{t，q}，e{t，d}) (5)

5 不相似圖片去除方法

值得注意的是，通過圖片檢索所獲得的圖片并不一定是與查詢圖片相似的圖片，其又可以返回的是一些相關(guān)而不相似的圖片。為了利用圖片檢索技術(shù)進(jìn)行圖片的相似性聚類，需要將返回結(jié)果中與圖片不相關(guān)的圖片去除掉。有兩種方法可以達(dá)到去除不相似圖片的目的。

5.1 引入新的相似性測度

可以引入新的相似性測度，如cosine余弦或歐式距離，并將查詢圖片與檢索到的圖片進(jìn)行逐個相似度計算。達(dá)到一定閾值的才保留下來。由于一幅圖的surf特征可以很多，這種計算方式會消耗很多時間。但所得到的相似圖片結(jié)果是比較可靠的。

5.2 基于最大熵的打分序列分割的方法

基于打分的方法可以快速的去除不相似的圖片，但其所得到的相似圖片結(jié)果可能存在誤差。在實踐中，采用這種方法去除不相似圖片的錯誤率還是很低的。

該算法的思路為，在得到一個檢索結(jié)果序列以及其對應(yīng)的打分后，可以嘗試將這個序列進(jìn)行一次分割，使得分?jǐn)?shù)高于分割線的圖片判定為相似圖片，分?jǐn)?shù)低于分割線的，判定為非相似圖片。在此，我們假設(shè)與查詢圖片相似的圖片分?jǐn)?shù)基本會穩(wěn)定于特定的數(shù)值，而不相似的圖片會遠(yuǎn)小于這個特定的數(shù)值。則可以初步嘗試對序列的各種分割，找到一個能夠使相似圖片的分?jǐn)?shù)分布的熵與不相似圖片的分?jǐn)?shù)分布的熵達(dá)到最大值的分割結(jié)果作為最終的分割方案。

6 基于檢索到的圖片進(jìn)行相似聚類

經(jīng)過上面的一系列步驟，我們可以快速的計算出圖片集合中與任意一張圖片相似的所有圖片。對每一張圖片進(jìn)行如上的查詢，就可以獲得每一張圖片與庫中圖片的相似關(guān)系。從而可以應(yīng)用各種聚類算法（kmeans、affinity propagation等）進(jìn)行圖片聚類。

7 總結(jié)

本文對當(dāng)前比較流行的相似圖片檢索和聚類技術(shù)進(jìn)行了研究，并詳細(xì)的敘述了圖片檢索技術(shù)所涉及到的若干關(guān)鍵技術(shù)。該技術(shù)已經(jīng)應(yīng)用于中國移動垃圾彩信中的違規(guī)圖片庫管理。實踐證明，該技術(shù)能夠大大提高圖片相似檢索效率，提高不良圖片管理的整體生產(chǎn)力。

Visual word based similar image retrieval and clustering

DU Gang, ZHU Yan-yun, ZHANG Chen, DU Xue-tao
(China Mobile Group Design Institute Co., Ltd., Beijing 100080, China)

In combination with years of experience on controlling the junk MMS, the paper presents a comprehensive study on visual word based similar image retrieval and clustering. Several key points, such as visual word generating, embedding code computing, indexing and scoring are discussed in detail with many excellent engineering practices.

image retrieval; pattern recognition; visual word; similar image retrieval

TN918

A

1008-5599（2016）12-0012-04

2016-11-24