空間局部重合圖像的快速聚類

汪國安, 郭　昕

(1.河南大學(xué) 計算機(jī)與信息工程學(xué)院,河南 開封 475004; 2.河南大學(xué) 網(wǎng)絡(luò)信息中心,河南 開封 475004)

?

空間局部重合圖像的快速聚類

汪國安1,2, 郭昕1

(1.河南大學(xué) 計算機(jī)與信息工程學(xué)院,河南 開封 475004; 2.河南大學(xué) 網(wǎng)絡(luò)信息中心,河南 開封 475004)

摘要：采用視覺詞袋模型表示圖像，以快速檢測空間上部分重合圖像對的最小哈希算法為基礎(chǔ)，提出一種對局部重合圖像聚類即數(shù)據(jù)挖掘的方法，能夠找到類種子的概率隨著類別中圖像數(shù)目的增長顯著增加.對聚類的結(jié)果進(jìn)行空間上的驗證，并在大小分別為104、105以及5×106的圖像數(shù)據(jù)集上對該算法的效果進(jìn)行測試.算法的速度依賴于數(shù)據(jù)集中圖像的數(shù)目和數(shù)據(jù)集中類別的數(shù)目，類種子生成的時間復(fù)雜度線性相關(guān)于數(shù)據(jù)集大小.

關(guān)鍵詞：最小哈希；視覺詞袋模型；圖像聚類；局部重合圖像；數(shù)據(jù)挖掘

0引言

近年來，圖像數(shù)據(jù)的規(guī)模因商業(yè)用途和個人用途等因素呈爆炸性增長.檢索海量圖像數(shù)據(jù)成為一個具有挑戰(zhàn)性的問題[1].

文獻(xiàn)[2]表明，基于三維采集和空間重合獲取到的圖像特征點很直觀，也很容易滿足用戶的需求.但是，該方法用空間相關(guān)的圖像數(shù)據(jù)集進(jìn)行模型訓(xùn)練時，需要手工標(biāo)注大量數(shù)據(jù).文獻(xiàn)[3-5]表明，在當(dāng)前主流的圖像檢索系統(tǒng)中，檢索一個用戶感興趣的實例對象時，其結(jié)果能夠同時具有相當(dāng)高的準(zhǔn)確率和召回率.如果把其中的方法直接應(yīng)用到海量圖像集的檢索任務(wù)中去，由于它要將實例對象和數(shù)據(jù)庫中每個圖像兩兩進(jìn)行比對，所以時間復(fù)雜度將會是數(shù)據(jù)集大小的平方，因此這種方法不適用于海量圖像數(shù)據(jù)庫的檢索任務(wù).

本文以圖像檢索知識為背景提出一種快速的空間局部重合圖像聚類算法.與文獻(xiàn)[2]相比，該算法不需要人工進(jìn)行大量的數(shù)據(jù)標(biāo)注工作.與文獻(xiàn)[3-5]相比，該算法不是將查詢的實例對象和數(shù)據(jù)庫中的每個圖像兩兩進(jìn)行比對，而是快速檢測空間上部分重合圖像對的最小哈希算法，也就是所謂的類種子.類種子生成的概率隨著該類別中圖像數(shù)目的增長顯著增加，實際的時間復(fù)雜度(生成類種子的時間)與數(shù)據(jù)集大小線性相關(guān).

1空間局部重合圖像聚類中的最小哈希算法

本節(jié)主要對空間局部重合圖像聚類中的最小哈希算法進(jìn)行詳細(xì)描述.

把找到空間相關(guān)圖像的任務(wù)看作是搜尋一個無向圖中的連通分支.無向圖中的頂點代表圖像.如果兩個圖像擁有共同的場景，那么就說它們在空間上是相關(guān)的.從快速聚類算法的角度給出一個更實際的定義：如果兩個圖像能夠被一些魯棒的匹配算法匹配，那么它們描述著同一個場景.

盡管無向圖的頂點都是已知的(圖像數(shù)據(jù)庫)，但無向圖的邊結(jié)構(gòu)并不是作為一個先驗已知的，需要用聚類算法去發(fā)掘.一個圖像檢索系統(tǒng)可以被抽象地理解為：給定無向圖中的一個頂點(一個圖像)，返回與這個頂點(圖像)相關(guān)的所有邊.在大多數(shù)的現(xiàn)代檢索系統(tǒng)中，一次查詢的時間復(fù)雜度是和數(shù)據(jù)庫的大小近似于線性相關(guān)的，要比遍歷數(shù)據(jù)庫并且比對數(shù)據(jù)庫中的每一個圖像，在速度上有著數(shù)量級上的優(yōu)勢.

最小哈希算法是一種快速檢索無向圖中邊的哈希方法，但是快速檢索的代價卻是相對低的召回率：檢索到實例對象相關(guān)的一條邊的概率收斂于Pc.Pc正比于以圖像對共有的視覺單詞度量的相似度.相似度和概率Pc的定義將在1.1節(jié)詳細(xì)描述.對于空間局部重合圖像來說，Pc會有一個比較大的值(接近于1)，這也是最小哈希算法主要的應(yīng)用領(lǐng)域[6-7].

整個處理的步驟如下：

1)哈希.圖像描述子被存儲在哈希表中.實驗使用251個不同的描述子.兩個圖像落入同一個哈希桶的概率(精確描述子匹配)正比于它們的相似度.

2)相似度估計.對于在同一個哈希桶中的圖像對，也即在一個哈希桶中發(fā)生沖突，相似度將被計算.比較兩個弱化的視覺詞袋特征向量并且計算完全一致的元素(都為0或者都為1)，這個過程是快速的.在本文的實驗中，弱化的視覺詞袋特征向量的維度為512.之后，相似度可被閾值化.

3)空間一致性驗證.對于每個通過相似度檢測的圖像，將進(jìn)行空間一致性驗證.通過空間一致性驗證的圖像將成為最終的類種子.

1.1最小哈希算法概述

最小哈希算法是一種局部敏感哈希算法[8].在高相似度圖像中它的概率收斂于1，不相關(guān)的圖像收斂于0，對于一般的相似圖像對(有比較低的相似度，但是本質(zhì)上是相似的圖像，諸如同一個場景的圖像對)卻收斂于一個比較小的概率(圖1)[5,9]，這樣一個低的召回率使最小哈希算法不能直接應(yīng)用于圖像檢索中.筆者認(rèn)為它可以很有效地應(yīng)用在圖像聚類和數(shù)據(jù)挖掘中.

注：(b)的函數(shù)圖像是對(a)中函數(shù)圖像左下部的一個局部放大表示，(b)中函數(shù)的垂直坐標(biāo)是用log作為刻度的

下面將概述最小哈希算法.圖像將用視覺字典集合(詞袋模型)表示.本文中是用視覺字典集合的一種相對較弱的表示，映射到視覺字典的視覺詞袋特征向量的每一維(對應(yīng)于相應(yīng)視覺單詞出現(xiàn)的頻率)將被弱化為二值表示(存在或不存在)，稱為弱化的視覺詞袋特征向量.

一個最小哈希函數(shù)f弱化的視覺詞袋特征向量的每一維賦予一個數(shù)值.該函數(shù)有這樣一個性質(zhì)：兩個弱化的視覺詞袋特征向量經(jīng)過f之后相等的概率和兩個弱化的視覺詞袋特征向量之間的相似度完全相同，

P{f(A1)=f(A2)}=sim(A1,A2).

(1)

用杰卡德距離度量兩個特征向量之間的相似度，其中A1和A2是兩個圖像弱化的視覺詞袋特征向量表示，它們的相似度即為它們的交集比它們的并集，

(2)

為了更高效更準(zhǔn)確地進(jìn)行檢索，最小哈希fi的函數(shù)值被分組在s元組中，稱為草圖.由相似度的定義可知，相似的圖像擁有很多相同的最小哈希函數(shù)值，因此擁有相同的草圖的概率比較大.在另一方面，不相似的圖像擁有同一個草圖的概率是比較小的.

兩個弱化的視覺詞袋特征向量之間至少有一個相同的草圖(在k個草圖中)的概率為

Pc(A1,A2)=1-(1-sim(A1,A2)s)k.

(3)

這個概率依賴于兩個圖像之間的相似度以及草圖的大小s和彼此相互獨(dú)立的草圖數(shù)目k.圖1描述了兩個圖像至少有一個草圖沖突的概率和圖像對相似度之間的函數(shù)關(guān)系，將有著不同相似度的圖像與“視覺相關(guān)度”建立聯(lián)系，其中在每個草圖中k=512，s=3.

有一點值得注意，公式(2)的相似度度量假設(shè)弱化的視覺詞袋特征向量的每一維度都是同等重要的，然而在實際中，某些維度是比其他維度更重要.一個擴(kuò)展的方法允許對于不同的維度賦予不同的權(quán)重[10].令dw≥0作為維度Xw的權(quán)重，則加權(quán)的相似度度量為

(4)

這種加權(quán)的相似度度量和非加權(quán)相似度度量的相比，可以更好地表明圖像對之間的相似度以及減少錯誤的草圖沖突數(shù)目[10].

1.2類種子的生成

本小節(jié)描述一個隨機(jī)的類種子生成的過程.首先觀察圖1中的曲線，這樣一個類似sigmoid函數(shù)的曲線對于空間局部重合圖像聚類任務(wù)來說很有研究價值.圖像對之間擁有較高的相似度，可被檢索出(哈希函數(shù)發(fā)生沖突)的概率接近于1.然而盡管一些圖像對的內(nèi)容只是同一場景的些許視角不同，也可能會被檢索(哈希函數(shù)不發(fā)生沖突)，即認(rèn)為是不相關(guān)的圖像對，函數(shù)曲線迅速下降并接近于0.

為了實現(xiàn)空間局部重合圖像聚類亦即數(shù)據(jù)挖掘，注意一下圖1曲線的左下部分.根據(jù)公式(3)，相似度sim=0.05的圖像對可以被檢索出來的概率為6.2%(其中s=3,k=512).如此低的召回率對于一個檢索系統(tǒng)顯然是不能接受的.然而我們并不是要在這樣一個簡單的步驟中檢索到所有的相關(guān)圖像，而是要快速找到類種子，在每個類中找到至少一個類種子是完全可以實現(xiàn)的，因為每個類的重要性是和這個類在數(shù)據(jù)庫中所占的大小相關(guān)的.

使用最小哈希算法但一個類種子都未能找到的概率由下面兩個因素決定：類內(nèi)圖像的相似度和實際代表著同一場景的圖像的數(shù)目.假設(shè)一個確定的場景有v個不同的視角.因此對于類內(nèi)的圖像對(Ai,Aj)，一個類種子都未能找到的概率可以表示為

(5)

其中，ε代表著一個“平均”的沖突概率.圖2的曲線表明，對于一個比較熱門的場景(諸如攝影師經(jīng)常喜歡取景的地方)，一個類種子都未能找到的概率曲線接近于0.圖中3條曲線代表相似度分別為5%(上方曲線)，6%(中間曲線)，7%(下方曲線).既然相似度的定義是兩個弱化的視覺詞袋特征向量的交集比它們的并集(見式(2))，因此相似度為6%與相似度為5%的差別還是很大的.從6%的相似度到5%的相似度意味著要移除它們相交部分17.5%的元素.

注：(a)與(b)水平軸的刻度是不同的.每個圖的3條曲線描述了不同的“平均”

下面討論最小哈希算法的時間復(fù)雜度，該算法建立在固定數(shù)目為M個哈希桶的哈希方法上.假設(shè)哈希鍵服從均勻分布，C個哈希鍵落入同一個哈希桶的隨機(jī)變量服從泊松分布，沖突發(fā)生的期望為λ=D/M(即文件被分割到哈希表中的數(shù)目)，那么一對哈希鍵落入同一個哈希桶的期望為

(6)

由式(6)可知，時間復(fù)雜度為O(D2).然而，對于有限的數(shù)據(jù)庫來說，當(dāng)數(shù)據(jù)庫的大小D≤M時，該算法復(fù)雜度接近于一個線性時間，因為D2/M+D≤2D.在最小哈希算法中，哈希桶的數(shù)目M由兩個參數(shù)決定：視覺詞典的大小w以及草圖的大小s，并且正比于ws.本文實驗中，令w=217，s=3或s=4，則M=251和M=268，這個數(shù)目已足夠模擬互聯(lián)網(wǎng)上的實際數(shù)據(jù)量.

1.3空間一致性驗證

在空間一致性的驗證過程中，筆者采用了多對多的類RANSAC方法[3].用一個共有的視覺單詞ID號定義嘗試性的對應(yīng).幾何約束是一個仿射變換.這樣的一個選擇是便捷的，因為只是一個橢圓到橢圓的仿射對應(yīng)(加上一個約束在重力向量上)，這對實例化這樣的一個近似模型是足夠的，該模型還可以用局部優(yōu)化算法進(jìn)一步優(yōu)化[11].有著一個松散閾值的仿射變換模型，允許檢測一個在場景里面沒有明顯透視形變的接近平面的結(jié)構(gòu).之后，在這些模型上的全局一致性將通過RANSAC方法去驗證，滿足核面幾何學(xué)或者單應(yīng)性[11-13].最終的檢查速度是非?？斓?，因為對這個階段的嘗試性對應(yīng)是從前一階段統(tǒng)一起來的內(nèi)層對應(yīng)，并且存在一個較高的內(nèi)層對應(yīng)系數(shù).

這里有兩個誤匹配的來源：感興趣點的退化(靠近共線點集合)和重復(fù)結(jié)構(gòu)(許多特征被映射到了同一個視覺單詞上，典型的情況是類網(wǎng)格結(jié)構(gòu)).在本文提到的實驗中，為了正確驗證圖像對，必須有足夠多的匹配不是感興趣點的退化以及重復(fù)結(jié)構(gòu).

2實驗結(jié)果與評估

筆者做了兩個相關(guān)實驗.第一個是為了驗證在1.2節(jié)提到的理論上的種子生成概率在實際數(shù)據(jù)上是否足夠高；第二個實驗是為了驗證在海量數(shù)據(jù)上的效果，實驗數(shù)據(jù)為一個包含10萬張圖像的數(shù)據(jù)集.

2.1種子生成的成功率

為了驗證種子生成階段在真實數(shù)據(jù)上的成功率，筆者使用了一個標(biāo)準(zhǔn)圖像檢索基準(zhǔn)數(shù)據(jù)集(美國肯塔基州大學(xué)數(shù)據(jù)集).該數(shù)據(jù)集包含10 200個圖像；每4個圖像描述同一個場景，也就是說總共有2 550個類別，其中每個類別的大小為4.并且，數(shù)據(jù)集提供了圖像、已經(jīng)檢測的圖像特征以及SIFT描述子.在實驗中使用提供的特征和描述子.在這個數(shù)據(jù)集上的實驗是對每個檢索實例去查詢數(shù)據(jù)集，并從它所在的類別中找出檢索實例對應(yīng)的其他3個圖像.檢索的成功率由前4個結(jié)果中正確檢索圖像的數(shù)目衡量(檢索實例圖像也需要被檢索到)，因此最好的得分就是4.

圖3　在Kentucky數(shù)據(jù)集上種子生成成功率與期望成功率關(guān)系的直方圖分布 Fig.3　Histogram of relationship between success average of generate seeds and expectation on Kentucky dataset

然而我們對另外的一些數(shù)據(jù)感興趣.目標(biāo)是有多少個類別(每類中圖像數(shù)目是4)，我們的方法可以找到至少一個類種子.本實驗使用包含217個單詞的視覺詞典.對于每個圖像，512個獨(dú)立的隨機(jī)最小哈希函數(shù)將被使用，并把這些函數(shù)分組,得到512個大小為3的草圖(獨(dú)立的最小哈希函數(shù)將被多次使用).通過這樣的設(shè)置，將有11 556對圖像有至少一個公共的草圖沖突，對于3 553個通過相似度檢測的圖像，3 210個是正確的.至少有一個圖像在它對應(yīng)類中的4個圖像之一的數(shù)目是1 196(在2 550個所有的類別中).換句話說，在每個類大小為4的2 550個類中，種子生成的成功概率為46.9%，這個值相當(dāng)于解決失敗值的期望.接近50%的種子生成成功率看起來比理論的低，但是一個類只有4個圖像這種情況比一般實際情況每個類別中包含105~107個圖像要少得太多了.

實驗比較了預(yù)測的成功率/失敗率和理論上的失敗率(圖3)，精確計算了“平均”沖突概率ε，即每個類中枚舉類中的所有圖像.對每個類來說，能夠觀察到一個類種子能否成功生成.圖3的曲線描述出不同預(yù)測成功率下類種子生成的成功率，直方圖非常接近于灰色的實線.

這里需要注意的是，本實驗只是對類種子生成的偽陰性感興趣，而不是假陽性概率.潛在的種子并不在每類4個正確圖像之中，即并不是需要的假陽性問題，因為許多場景都在同一個背景中呈現(xiàn).對數(shù)據(jù)集的正確分類圖像來說，這些圖像被分到了不同的組.比如，一些不在同一個組中并且生成空間不相關(guān)的數(shù)據(jù)集，它們實質(zhì)上在背景中存在明顯的局部重合情況.因此，在這種情況下空間一致性驗證將不能發(fā)揮作用，因為筆者僅僅使用提供的數(shù)據(jù)集，這些數(shù)據(jù)集并不包括用于幾何驗證的必要信息.

用上文提到的標(biāo)準(zhǔn)的檢索分?jǐn)?shù)去度量最小哈希算法，得分為1.63.這個效果比目前的檢索系統(tǒng)報告的3.3分到3.6分要低.因此，考慮最小哈希的收尾工作很重要，也就是加上檢索實例本身，這樣會有一個平均的2.27分.這個效果和一個足夠的召回率(46.9%在類別大小為4的數(shù)據(jù)集上的類種子生成成功率)，使得最小哈希方法適合于隨機(jī)數(shù)據(jù)挖掘工作中的類種子生成.

2.2在10萬張牛津標(biāo)志性建筑數(shù)據(jù)集上的聚類實驗

本實驗使用從Flickr個人主頁下載的大數(shù)據(jù)圖像集[2]，這個數(shù)據(jù)集包含5 062個從牛津標(biāo)志性建筑數(shù)據(jù)集[14]上獲得的圖像和99 792張從Flickr1數(shù)據(jù)集(文獻(xiàn)[3]使用的數(shù)據(jù)集)中取得的圖像數(shù)據(jù).兩個數(shù)據(jù)集都由高分辨率的圖像(1 024 pixel×768 pixel)組成.這個數(shù)據(jù)集同樣也包含已經(jīng)提取出來的SIFT特征描述子——這些標(biāo)準(zhǔn)的特征以及描述子將被直接用在本實驗中.這里共有104 844張圖像附帶294 105 803個SIFT特征描述子(平均每張圖像2 805個特征).SIFT描述子特征占用35GB空間，在這個數(shù)據(jù)集中，11個標(biāo)志性建筑場景是手工標(biāo)注的.

和上一個實驗一樣，筆者使用一個包含217個單詞的詞典，并用最小哈希方法去生成類種子.牛津標(biāo)志性建筑數(shù)據(jù)集中每個類別包含102到103個圖像.為了表明這個方法的可擴(kuò)展性，使用512個最小哈希函數(shù)并分組到512個大小為3的草圖中.與前一個實驗類似，這些設(shè)置允許我們發(fā)現(xiàn)很小的類別.平均來看，最小哈希對每個圖像產(chǎn)生了38.4個草圖沖突.這個減少到了平均每個圖像經(jīng)閾值校驗之后產(chǎn)生可能的1.23個類種子——和129 341個類種子對應(yīng).此外，3 103個圖像被發(fā)現(xiàn)有著明確的部分重合在數(shù)據(jù)集中.所有的剛被發(fā)現(xiàn)的部分重合圖像被去除，其他剩下的類種子去進(jìn)行空間一致性驗證，最后剩下441個經(jīng)過驗證后的類種子，這是類數(shù)目的一個上界.

表1總結(jié)了在真實信息上的實驗結(jié)果.對每一個標(biāo)志性建筑場景，我們發(fā)現(xiàn)所聚的類包含了更多的正確的標(biāo)志性建筑場景圖像，并且在類中計算出很多正確的真實圖像信息.同時，通過觀察這些類別，一個絕對數(shù)量的不相關(guān)圖像也被展示出來.另外的一些建筑出現(xiàn)在相同的一個類別中，如果它們彼此之間在空間上是相鄰的(有連接部分)，并不認(rèn)為是不相關(guān)的圖像.舉個例子，All Souls和Radcliffe Camera是在同一個類中，因為彼此在空間上相鄰，并且同時出現(xiàn)在若干個圖像中.

表1　在牛津地標(biāo)數(shù)據(jù)集上的標(biāo)注圖像結(jié)果

數(shù)據(jù)集大小對運(yùn)行時間的影響反映在圖4上，圖4(c)是聚類完成的時間作為數(shù)據(jù)集大小的一個函數(shù)表示.類種子生成的時間和數(shù)據(jù)集大小約近線性相關(guān)(和類種子生成的數(shù)目與數(shù)據(jù)集大小的關(guān)系十分相近)，并且能夠被檢索的部分隨著數(shù)據(jù)集大小以及種子生成數(shù)目的增大而增大.全局的復(fù)雜度近似平方相關(guān).注意到種子的數(shù)量是數(shù)量級低于數(shù)據(jù)庫的大小——相較于文獻(xiàn)[3-5]中與數(shù)據(jù)庫的大小平方相關(guān)的時間復(fù)雜度，隨機(jī)聚類在速度上明顯快于單獨(dú)去查詢每個圖像.

圖4　標(biāo)注結(jié)果在10萬張牛津地標(biāo)數(shù)據(jù)集上進(jìn)行10次實驗的平均表示

2.3對500萬張圖像的大規(guī)模聚類

我們將在數(shù)據(jù)集大小為500萬的Flickr圖像集上進(jìn)行聚類實驗，在這個實驗中，使用海森仿射特征，視覺詞典是由1M的視覺單詞構(gòu)成，草圖參數(shù)：s=4，k=512.聚類過程在PC機(jī)(CPU 3.0 GHz 單核,內(nèi)存 64 GB)上運(yùn)行了大約28 h，平均0.020 s處理一張圖片.在大約500萬個圖像中，474 434張被指定到16 957個類中.

3結(jié)論

提出了一種海量數(shù)據(jù)集中空間局部重合圖像的快速聚類算法，該算法的基本步驟為：(1)將圖像描述子存儲在哈希表中，即最小哈希的過程；(2)進(jìn)行相似度估計；(3)空間一致性驗證，其中最關(guān)鍵的技術(shù)為利用圖像檢索的原理進(jìn)行空間局部重合圖像的聚類工作.不是將查詢的實例對象和數(shù)據(jù)庫中的每個圖像兩兩進(jìn)行比對，而是快速檢測空間上部分重合圖像對的最小哈希算法.

本文提出的算法收斂速度依賴于數(shù)據(jù)集的大小，在實際中非?？?，并且與數(shù)據(jù)集的大小線性相關(guān)(大約234≈1010張圖像).聚類成功的概率依賴于每個類別的大小，以及每個類中圖像之間的平均相似度，這個概率是和數(shù)據(jù)集的大小無關(guān)的.該算法的效果已在大小分別為104、105以及5×106的圖像數(shù)據(jù)集上進(jìn)行測試.

參考文獻(xiàn)

[1]李向陽,莊越挺,潘云鶴.基于內(nèi)容的圖像檢索技術(shù)與系統(tǒng)[J]. 計算機(jī)研究與發(fā)展,2001,38(3):344-353.

[2]SNAVELY N, SEITZ S M, SZELISKI R. Photo tourism: Exploring photo collections in 3D[J]. ACM Transactions on Graphics (TOG).ACM，2006, 25(3): 835-846.

[3]PHILBIN J, CHUM O, ISARD M, et al. Object retrieval with large vocabularies and fast spatial matching[C]//IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2007: 1-8.

[4]JEGOU H, HARZALLAH H, SCHMID C. A contextual dissimilarity measure for accurate and efficient image search[C]//IEEE Conference on Computer Vision and Pattern Recognition.IEEE, 2007: 1-8.

[5]CHUM O, PHILBIN J, SIVIC J, et al. Total recall: Automatic query expansion with a generative feature model for object retrieval[C]//IEEE 11th International Conference on Computer Vision. IEEE, 2007: 1-8.

[6]SCHINDLER G, BROWN M, SZELISKI R. City-scale location recognition[C]//IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2007: 1-7.

[7]BRODER A Z. On the resemblance and containment of documents[C]//Proceedings of Compression and Complexity of Sequences. IEEE, 1997: 21-29.

[8]INDYK P, MOTWANI R. Approximate nearest neighbors: towards removing the curse of dimensionality[C]//Proceedings of the thirtieth annual ACM symposium on Theory of computing. ACM, 1998: 604-613.

[9]CHUM O, PHILBIN J, ISARD M, et al. Scalable near identical image and shot detection[C]//Proceedings of the 6th ACM international conference on Image and video retrieval. ACM, 2007: 549-556.

[10]CHUM O, PHILBIN J, ZISSERMAN A. Near Duplicate Image Detection: Min-Hash and tf-idf Weighting[C]//BMVC. 2008: 812-815.

[11]CHUM O, MATAS J, OBDRZALEK S. Enhancing RANSAC by generalized model optimization[C]//Proc of the ACCV. 2004: 812-817.

[12]CHUM O, WERNER T, MATAS J. Two-view geometry estimation unaffected by a dominant plane[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition. IEEE, 2005: 772-779.

[13]FRAHM J M, POLLEFEYS M. RANSAC for (quasi-) degenerate data (QDEGSAC)[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition. IEEE, 2006: 453-460.

[14]PERD’OCH M, CHUM O, MATAS J. Efficient representation of local geometry for large scale object retrieval[C]//IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2009: 9-16.

聲明

為擴(kuò)大本刊及作者知識信息交流渠道，加強(qiáng)知識信息推廣力度，本刊已許可CNKI(中國知網(wǎng))及其系列數(shù)據(jù)庫、萬方數(shù)據(jù)資源系統(tǒng)數(shù)據(jù)化期刊群、維普中文科技期刊數(shù)據(jù)庫等，以數(shù)字化方式復(fù)制、匯編、發(fā)行、信息網(wǎng)絡(luò)傳播本刊全文.該著作權(quán)使用費(fèi)及相關(guān)稿酬，本刊均用于為作者文章發(fā)表、出版、推廣交流(含信息網(wǎng)絡(luò))以及贈送樣刊等用途，不再另行向作者支付.凡作者向本刊提交文章發(fā)表之行為即視為同意我刊上述聲明.

河南教育學(xué)院學(xué)報編輯部

Fast Cluster of Partial Duplicate Images

WANG Guo-an1,2, GUO Xin1

(1.CollegeofComputerandInformationEngineering,HenanUniversity,Kaifeng475004,China；

2.NetworkInformationCenterOffice,HenanUniversity,Kaifeng475004,China)

Abstract:A method came up which finds clusters of partial duplicate images. The main idea relies on the Min-Hash algorithm for fast detection of pairs of images with spatial partial overlap. The probability of finding a seed for an image cluster rapidly increases with the size of the cluster. After that a RANSAC spatial consistency test will be passed. The properties and performance of the algorithm are demonstrated on data sets with 104,105, and 5×106images. The speed of the method depends on the size of the database and the number of clusters.

Key words:min-hash; bag of visual word; image clustering; partial duplicate images; data mining

中圖分類號：TP391.4

文獻(xiàn)標(biāo)識碼：A

文章編號：1007-0834(2015)02-0023-07

doi：10.3969/j.issn.1007-0834.2015.02.007

作者簡介：汪國安(1957—)，男，河南新蔡人，河南大學(xué)計算機(jī)與信息工程學(xué)院、網(wǎng)絡(luò)信息中心教授，主要研究方向：計算機(jī)視覺與模式識別.

收稿日期：2015-03-01