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

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

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

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

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

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

圖片檢索；模式識(shí)別；視覺詞；圖片相似檢索

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

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

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

1 相似圖片檢索框架

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

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

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

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

2 視覺詞生成

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

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

采用如上降維方法進(jìn)行聚類的一個(gè)弊端是經(jīng)過(guò)前后32維排列組合產(chǎn)生的所有視覺詞并不一定都真實(shí)存在。舉例說(shuō)明：假設(shè)有兩個(gè)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個(gè)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}。但實(shí)際上參與聚類的只有兩個(gè)SURF特征，根本不存在x{1，32}+y{33，64}和y{1，32}+x{33，64}。不過(guò)實(shí)驗(yàn)證明，當(dāng)SURF特征的總體數(shù)量遠(yuǎn)遠(yuǎn)大于需要聚類的數(shù)量時(shí)，這種偽聚類中心出現(xiàn)的概率會(huì)降低。

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

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

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

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

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

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

4 圖片檢索與打分排序

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

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

經(jīng)過(guò)tf-idf初步排序后，需要使用嵌入碼對(duì)排序結(jié)果進(jìn)行進(jìn)一步的優(yōu)化。此處引入嵌入碼吻合率計(jì)算，如式(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中的嵌入碼。

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

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

5 不相似圖片去除方法

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

5.1 引入新的相似性測(cè)度

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

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

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

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

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

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

7 總結(jié)

本文對(duì)當(dāng)前比較流行的相似圖片檢索和聚類技術(shù)進(jìn)行了研究，并詳細(xì)的敘述了圖片檢索技術(shù)所涉及到的若干關(guān)鍵技術(shù)。該技術(shù)已經(jīng)應(yīng)用于中國(guó)移動(dòng)垃圾彩信中的違規(guī)圖片庫(kù)管理。實(shí)踐證明，該技術(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