吳 迎

(浙江理工大學(xué)信息學(xué)院，浙江 杭州 310018)

0 引 言

21世紀以來，互聯(lián)網(wǎng)的發(fā)展速度飛快。隨著互聯(lián)網(wǎng)的普及，電子商務(wù)也得到了很大的發(fā)展，很多線下的店鋪也開起了網(wǎng)店，由此產(chǎn)生了很多問題。比如天貓水果網(wǎng)店“果小云”抄襲其它店鋪臍橙產(chǎn)品信息，甚至連同其它店鋪的手機號和錯設(shè)的“26元4500斤”都被照抄。由于之前該網(wǎng)店疑似標錯商品售價，被“羊毛黨”數(shù)百萬訂單薅垮，已經(jīng)得到輿論的關(guān)注。而此次的事件出現(xiàn)反轉(zhuǎn)，更是將其推上了風(fēng)口浪尖。這不得不讓人們?nèi)ニ伎茧娚讨写嬖诘陌鏅?quán)[1]保護問題。而通過計算機技術(shù)手段可以有效地解決這個問題。否則，采用人工方式解決，由于數(shù)據(jù)海量，一方面需要大量的人力，另一方面，人的精力有限，長時間進行枯燥乏味的工作，精力跟不上，錯誤率也會不斷攀升，是一個吃力不討好的解決方案?；氐郊夹g(shù)層面，如果采用光學(xué)字符識別[2-3]的方案提取圖像中的文字，一方面，沒有那么完美的光學(xué)字符識別的方法，另一方面，會丟失圖像上原本存在的比文字描述更豐富的信息。因此，此方案理論上錯誤率比較高。圖像相似度算法常見的做法是先進行特征提取或者指紋生成，最后計算圖像的相似度?；谥讣y生成的有感知哈希算法[4-5]，基于特征提取的有基于局部不變性的SIFT算法[6-9]。2011年，百度公司借助于TinEye[10]的技術(shù)發(fā)布了百度識圖。緊接著，谷歌發(fā)布了類似的功能，以圖搜圖搜索引擎。其中，感知哈希算法在搜索引擎中發(fā)揮了重要作用。感知哈希算法里包括很多哈希算法，它的作用是為圖像產(chǎn)生指紋字符串，最后利用指紋字符串的漢明距離計算圖像的具體相似度數(shù)值。SIFT(Scale-invariant Feature Transform)中文名稱為尺度不變特征轉(zhuǎn)換，是一種用來檢測以及描述圖像中的局部性特征的機器視覺算法，這個算法由Lowe[11]在1999年提出，并且在2004年總結(jié)完善。SIFT利用局部的信息提取特征點，經(jīng)過坐標軸變換和歸一化操作之后，使得提取出的特征不受旋轉(zhuǎn)和顏色的變化。此外，對存在噪聲點和一些小的變化的魯棒性也很好，不易受到這些因素的影響。隨著當今計算機硬件快速地發(fā)展，SIFT提取特征的速度有很大的提升，幾乎已經(jīng)接近實時。SIFT還可以與其它算法相結(jié)合[12-14]，能夠更好地提升算法的精度和速度。本文先利用SIFT算法提取SIFT描述子，即SIFT特征，接著使用近似最鄰近算法匹配SIFT特征，最后根據(jù)匹配出的特征點計算出圖像的相似數(shù)值。本文以電鉆的圖像為實驗對象，分別讓其與剪切、翻轉(zhuǎn)、添加字幕、加大對比度、增加濾鏡等操作之后的圖像進行相似度的計算，來驗證各種算法的精度。

1 基于哈希的圖像相似度算法

感知哈希算法里包括很多哈希算法，它的作用是為圖像產(chǎn)生指紋字符串，最后利用指紋字符串的漢明距離計算圖像的具體相似度數(shù)值。感知哈希算法包括均值哈希(aHash)、感知哈希(pHash)和差異值哈希(dHash)[15]。

1.1 aHash

aHash全稱叫做average Hash，是感知哈希算法中最簡單的一種。其具體處理圖像的過程見算法1。

算法1aHash。

輸入：圖像信息。

步驟1縮小圖像。保留圖像的結(jié)構(gòu)，降低圖像的信息量，去掉細節(jié)、大小和橫縱比的差異，將圖片縮小成N×N,N一般取值為8。

步驟2轉(zhuǎn)化為灰度圖。將縮小之后的圖像處理成灰度圖。對于RGB圖像，可以用公式Gray=0.299R+0.587G+0.114B將其轉(zhuǎn)為灰度圖像。

步驟3計算平均值。計算出步驟2后所有像素點的平均值。

步驟4比較像素。依次對步驟2得到的像素逐個地進行判斷：如果當前像素比步驟3中得到的平均值大，則相應(yīng)地置為1；如果比平均值小，則置為0。

步驟5構(gòu)造Hash。拼接64個只包含0-1的字符為指紋字符串。

輸出：指紋字符串。

1.2 pHash

感知哈希算法可以得到更精確的結(jié)果，采用的是離散余弦變換(DCT)來降低頻率。其具體處理圖像的過程詳見算法2。

算法2pHash。

輸入：圖像信息。

步驟1縮小圖像。將圖片縮小成N×N,N推薦的取值是32。

步驟2轉(zhuǎn)化為灰度圖。與算法1的步驟2一致。

步驟3計算DCT均值。

步驟4構(gòu)造Hash值。上一步DCT得到的是32×32矩陣，由于大部分圖像信息存在于左上角的8×8系數(shù)子矩陣中，而且為了簡化計算，故最后只保留左上角的8×8系數(shù)子矩陣，拼接64個只包含0-1的字符為指紋字符串。

輸出：指紋字符串。

算法2中一維的離散余弦變換如式(1)和式(2)所示。

(1)

(2)

其中f為最初的信號，F(xiàn)為DCT變換以后的系數(shù)，N為最初的信號的點數(shù)，c為補償系數(shù)，這樣能夠使DCT變換轉(zhuǎn)化為正交陣。

二維離散余弦變換的正交變換如公式(3)所示。

(3)

1.3 dHash

差異值哈希和感知哈希的運算速度相比，前者會快一些，差異值哈希和均值哈希的效果相比，前者會好一些，其具體處理圖像的過程詳見算法3。

算法3dHash。

輸入：圖像信息。

步驟1縮小圖像。收縮為9×8，比aHash多一位是為了做差值。

步驟2轉(zhuǎn)化為灰度圖。與aHash一致。

步驟3計算差異。對相鄰像素做差，每行有9個像素點，產(chǎn)生8個不同的差異，共有8行，故而，最后產(chǎn)生64個差異值。

步驟4比較差異值。如果前面的一個像素比后面一個像素要大，就置為1；如果前面的一個像素比后面一個像素要小，置為0。

步驟5構(gòu)造Hash。拼接64個只包含0-1的字符為指紋字符串。

輸出：指紋字符串。

基于感知哈希算法的圖像相似度計算公式如式(4)所示。

(4)

其中，Similarity為圖像相似度，h為指紋字符串的漢明距離。

感知哈希算法的特點是計算速度快，適用于原圖和縮略圖之間的快速匹配。但該算法體現(xiàn)的是整體特征，忽略了很多細節(jié)，丟失了很多局部特征，這就需要在局部特征的方面增加算法的魯棒性。

2 基于SIFT和近似最鄰近匹配的圖像相似度算法

局部特征檢測算法在相似度計算、圖像檢索、物體識別等領(lǐng)域有非常多的應(yīng)用。相對于圖像哈希的這種做法，局部上的一些特征在描述圖像的特征時信息量更豐富。在提取過程中，SIFT描述子的坐標軸統(tǒng)一對準主方向，保證了圖像局部特征的旋轉(zhuǎn)不變性，即使改變旋轉(zhuǎn)角度，特征依然不會發(fā)生變化。本文先對SIFT提取圖像特征給出理論分析，并與近似最鄰近匹配算法結(jié)合，進行特征點的快速匹配。

2.1 SIFT算法

SIFT算法提取特征分為4步：1)建立尺度空間，即構(gòu)建高斯金字塔，然后利用高斯金字塔得到差分高斯金字塔；2)找出極值點；3)找到關(guān)鍵點；4)生成描述子。

2.1.1 尺度空間的建立

要建立圖像的尺度空間，需要對其進行高斯模糊[16]作用，接著利用高斯卷積核做尺度的變換。尺度空間實質(zhì)上是使用了高斯卷積核函數(shù)在圖像上操作，以獲取多尺度的特征。尺度空間的定義公式詳見式(5)。

L(x,y,σ)=G(x,y,σ)*I(x,y)

(5)

其中，G(x,y,σ)是由σ值所決定的高斯卷積核，“*”的含義是卷積，G(x,y,σ)的計算公式詳見式(6)。

(6)

其中：m、n是高斯模板矩陣的大小，由(6σ+1)×(6σ+1)確定；x、y是圖像當中像素點的位置；σ是尺度空間的因子，其取值比較小的時候，代表的含義是圖像沒有怎么被平滑，即得到的尺度相應(yīng)地變得越小。尺度相對較大時，會表現(xiàn)圖像中的表面特性；尺度相對較小時，會表現(xiàn)圖像中較細的特性。

尺度空間是利用高斯金字塔實現(xiàn)的，通過對圖像做高斯模糊，遍歷高斯金字塔不同的尺度空間，接著對圖片進行隔點采樣。高斯金字塔如圖1所示。

圖1 高斯金字塔

圖像的高斯金字塔模型是指把最初的原始圖像不斷降階地進行采樣，得到很多組長度和寬度逐漸遞減的圖像，這樣，從大到小，自下而上的過程便構(gòu)成了金字塔的形狀。其中，最原始的圖像為金字塔模型中的第1層，然后隨著采樣，圖像大小逐漸遞減，形成了金字塔模型中的上一層。金字塔的層數(shù)l是根據(jù)初始的圖像以及最后采樣的圖像計算得出的，其計算公式如式(7)所示。

(7)

其中，w和h是初始圖像的寬、高。例如，原始圖像的大小是128×128，那么圖像的層數(shù)和最底層圖像大小的關(guān)系如表1所示。

表1 最底層圖像大小與圖像層數(shù)的關(guān)系

從表1可以看出，當最頂層的圖像大小為16×16時，此時高斯金字塔的層數(shù)為4。

高斯金字塔除了進行了采樣，還使用了高斯濾波，這樣做的原因是為了讓尺度空間的連續(xù)性更好。其具體做法是將每一層的圖像分別利用不同值的σ尺度因子進行高斯濾波，這樣每一層會得到多幅濾波后的圖像，將這些圖像稱為一組圖像，而且每層有且僅有一組圖像，也稱為octave。創(chuàng)建高斯金字塔完畢以后，差分的高斯金字塔利用它相減就可以得到，即使用高斯金字塔相鄰上下層相減得到高斯差分金字塔，也稱為DOG。至此，尺度空間建立完畢。

2.1.2 極值點檢測

接下來要找出高斯差分金字塔構(gòu)成的尺度空間中的極值點，目的是初步地進行關(guān)鍵點的搜索。由于高斯拉普拉斯算子能夠提取出比較好的圖像特征，而其在計算效率方面，沒有高斯差分算子[17]效率那么高，又由于高斯拉普拉斯算子和高斯差分算子極值點位置比較接近，故而最后用高斯差分算子來替代高斯拉普拉斯算子。DOG尺度空間中局部的極值點構(gòu)成了關(guān)鍵點。初步地進行關(guān)鍵點的搜索是利用相鄰2層直接的同一個octave的圖像確定的。對于某個像素點，如果它是極值點，它需要滿足同一個尺度內(nèi)圖像的8個點，以及相鄰尺度，即上下2幅圖像的9×2個點，共26個點都比其大或者小。由于比較的過程中涉及相鄰的2個尺度，假設(shè)DOG有5層，那么只有中間3層才能夠進行極值點的檢測，首末層由于其不同時存在2個相鄰的層而無法進行極值點的檢測。基于這種情況，為了最終能夠檢測出X個尺度所包含的極值點，則初始的DOG需要X+2層，這樣，高斯金字塔就需要X+3層。但是基于這種方式得到的極值點并不一定都是特征點，只是特征點的候選點，這是由于DOG算子具有比較強烈的邊緣效應(yīng)所導(dǎo)致的。

2.1.3 特征點定位

由于前述步驟所得到的極值點是基于離散空間下，故而需要采取措施得到連續(xù)空間下比較精確的特征點，消除因為DOG算子邊緣效應(yīng)所導(dǎo)致的比較差的特征點，達到增強算法魯棒性的目的。為了得到連續(xù)空間下比較精確的特征點，下面采用3維二次函數(shù)插值來預(yù)測特征點的位置和尺度。

離散空間下得到的極值點并不一定就是真正的極值點。如圖2所示，實心的點是離散空間中的點，空心的點是通過實心點擬合出來的函數(shù)插值所得。很顯然離散空間中的極值點是2和4，但通過擬合函數(shù)插值而得到的3和5才是比較精確的極值點。

圖2 離散空間插值擬合

為了進行擬合，對DOG函數(shù)進行泰勒展開，如式(8)所示。

(8)

其中，A=(x,y,σ)T,對其求導(dǎo)，接著讓導(dǎo)數(shù)等于0，可以求出解，詳見式(9)。

(9)

將式(9)代入式(8)可得式(10)。

(10)

由于DOG算子在水平邊緣部分的極值點的主曲率很可能比較大，豎直方向的主曲率很可能比較小，所以DOG算子會產(chǎn)生不穩(wěn)定的邊緣特征點，故而需要設(shè)法將其刪除。先利用Hessian矩陣求出主曲率，Hessian矩陣如式(11)所示。

(11)

假設(shè)α和β是矩陣H的2個特征值，分別表示x和y方向的梯度。它們的跡和行列式的值如式(12)和式(13)所示。

(12)

(13)

假設(shè)α>β,且α=rβ，則Hessian矩陣跡的平方與行列式的比值即主曲率如式(14)所示。

(14)

由于主曲率和Hessian矩陣的特征值成正相關(guān)，隨著r的增大，主曲率會變得更大。也就是說，一個方向上梯度值變大的同時，另一個方向的梯度值會減小。這正好就是邊緣的特征。所以可以使用這個結(jié)論，直接把邊緣上的點刪除。因此只需要讓滿足式(15)的點保留，不滿足則刪除。

(15)

計算好特征點的位置后，還需要確定方向，這樣做的目的是為了讓特征點可以不受旋轉(zhuǎn)的影響。對于上一步得到的特征點，可利用其周邊3σ范圍內(nèi)像素點的梯度，以及方向的信息。對于每一個像素點的L(x,y)，其梯度的幅值以及方向分別用m(x,y)和θ(x,y)表示，如式(16)和式(17)所示。

m(x,y)=((L(x+1,y)-L(x-1,y))2+

(16)

(17)

對于每個特征點，其周邊區(qū)域方向信息、尺度大小、具體方位可以構(gòu)成一個特征區(qū)域。在完成上一步驟之后，利用直方圖去統(tǒng)計周邊區(qū)域內(nèi)的每個像素的梯度值以及方向，其中，直方圖分為36個柱，每一個柱的區(qū)間長度是10°，直方圖中最大的那個柱子代表的方向為特征點的主方向。至此，檢測出了含有方向信息、尺度大小、具體方位的特征點。

2.1.4 描述子的生成

通過上述步驟，檢測出了含有方向信息、尺度大小、具體方位的特征點。下一步用具體的數(shù)值形式量化，用向量表示是一種比較好的形式。首先，要明確描述子的計算需要哪些圖像區(qū)域，由于描述子又和特征點的尺度相關(guān)，因此，對梯度的計算需要依賴高斯圖像。將特征點的周邊分為4×4的16個部分，每一個部分作為一個統(tǒng)計點，使用統(tǒng)計點的8個方向。接下來將坐標旋轉(zhuǎn)到和特征點主方向相平行的方向，這樣的操作可以保持旋轉(zhuǎn)不變性。共存在16個區(qū)域，每個區(qū)域8個方向，因此，使用128維向量描述一個特征點。在得到特征向量之后，為了去除光照變化的影響，可以利用歸一化的方法。如式(18)所示。

(18)

其中，Q=(q1,q2,…,q128)為特征向量,P=(p1,p2,…,p128)為歸一化后的特征向量。

至此，生成了SIFT特征。

2.2 快速最鄰近搜索算法

在上一節(jié)得到了特征點的128維向量描述，計算2幅圖像的相似度轉(zhuǎn)化為計算2幅圖像特征點的相似度。假設(shè)圖像A提取出了m個特征點，圖像B提取出了n個特征點。對于圖像A的每個特征點都需要從圖像B這n個特征點中找出與其最相似的特征點，相似程度可以用歐氏距離來度量。所以，在這些過程中，要解決的最關(guān)鍵的問題是要利用一種高效的算法，得到與圖像A距離最近的圖像B的特征點。最直觀的解決方案是采用暴力枚舉的做法，但是很顯然，對于圖像A的每一個特征點，圖像B的n個特征點都要被遍歷一遍，這樣的做法效率是很低的。本文采用KD樹[18-22]近似最鄰近搜索算法[23-25]來高效求解這個問題。

KD樹是K-Dimension Tree的簡稱，它可以把多維的數(shù)據(jù)構(gòu)造成一棵二叉樹，它的應(yīng)用范圍也很廣，例如計算幾何以及機器學(xué)習(xí)等領(lǐng)域。KD樹會按照某個維度將數(shù)據(jù)二分，二分出來的部分形成新的子樹，被分割的高維空間稱之為超平面。KD樹的目的是要盡可能地用某個維度的中間值來分割超平面，這樣可以使二叉樹更平衡，也就可以提高查詢時的效率。其詳細過程見算法4。

算法4KD樹。

步驟1若數(shù)據(jù)集為空，返回空的KD樹；若不為空，則轉(zhuǎn)步驟2。

步驟2獲取具體維度值作為二分二叉樹的依據(jù)。對特征向量，計算出其每個維度上的方差，然后計算出最大方差對應(yīng)的維數(shù)，作為二分二叉樹的維度。因為方差可以體現(xiàn)出數(shù)據(jù)的分散程度，數(shù)據(jù)越分散的維度，依據(jù)它劃分子樹效果會更好。轉(zhuǎn)步驟3。

步驟3假設(shè)步驟2得到的是第i維。下面以第i個維度為坐標軸，計算出所有向量里第i個維度的組成數(shù)據(jù)的中位數(shù)，然后把每個向量的第i維度和這個中位數(shù)比較。如果比它大，將這個向量放入子集A，否則放入子集B。將第1個等于這個中位數(shù)的特征向量作為根節(jié)點，子集A、B的特征向量作為其子樹。轉(zhuǎn)步驟4。

步驟4如果子集A和B還有元素，轉(zhuǎn)到步驟2和步驟3繼續(xù)執(zhí)行，如果A和B都沒有元素了，轉(zhuǎn)到步驟5。

步驟5算法結(jié)束。

輸出：KD樹。

3 實驗結(jié)果與分析

實驗部分使用的是一些電鉆商品的圖片。如圖3所示，original.jpg是原圖，cut.jpg是經(jīng)過裁剪并使圖像大小一致的圖像，watermark.jpg是添加了水印以后的圖像，filter.jpg是增加了濾鏡后的圖像，contrast.jpg是增加了對比度之后的圖像，rotate.jpg是往順時針方向旋轉(zhuǎn)90°以后的圖像。

圖3 實驗的圖像

3.1 基于哈希的圖像相似度算法實驗

圖像哈希算法的實驗結(jié)果如表2～表4所示，從中可以得出結(jié)論：該算法對于旋轉(zhuǎn)的情況，算法失效；對于剪裁的情況，算法效果不理想；對于水印、增加對比度、增加濾鏡的情況，算法可以達到精確識別的程度。對于旋轉(zhuǎn)的情況，需要用SIFT算法來彌補其短處。

表2 均值哈希算法aHash實驗結(jié)果

表3 感知哈希算法pHash實驗結(jié)果

表4 差異哈希算法dHash實驗結(jié)果

3.2 基于SIFT的圖像相似度算法實驗

基于SIFT描述子和近似最鄰近匹配算法的實驗結(jié)果如圖4～圖8所示，從中可以得出結(jié)論：該算法對于旋轉(zhuǎn)的情況，可以精確地匹配出很多特征點，進一步驗證SIFT描述子具有很好的旋轉(zhuǎn)不變性；對于剪裁的情況，依然可以匹配80%以上的特征點；對于有水印的情況，也能很好地剔除水印的影響；對于增加濾鏡的情況，算法可以達到比較高的精度；但是對于增加對比度的情況，算法的精確度不是很高，需要進一步地優(yōu)化。與圖像哈希算法相比較，SIFT沒有太明顯的短處，而且精度相對來說很高。

圖4 原始圖像和剪切后圖像的匹配

圖5 原始圖像和添加水印圖像的匹配

圖6 原始圖像和添加濾鏡圖像的匹配

圖7 原始圖像和增加對比度圖像的匹配

圖8 原始圖像和旋轉(zhuǎn)后圖像的匹配

4 結(jié)束語

本文提出了一種SIFT描述子結(jié)合近似鄰近快速搜索的算法，先是介紹了提取SIFT算子的具體過程，然后介紹了基于KD樹的近似鄰近快速搜索算法，最后設(shè)計實驗驗證了該算法具有旋轉(zhuǎn)不變性，對顏色變化不敏感等優(yōu)點。但是對比增加對比度的這個情況效果略微差一些，還有改進的空間。實驗中涉及了抄襲者常用的抄襲手段，最后驗證了所提算法能夠以比較好的精度識別出抄襲的圖像信息。