基于卷積特征提取和DTW的圖像相似度評估算法

宋珣，劉一廷

（西安交通大學(xué)自動化系，西安 710049）

0 引言

圖像相似度評估是計算機視覺和圖像分析中最基本的任務(wù)之一。在低級的任務(wù)中可用于寬基線匹配，建立全景圖等。在高級的任務(wù)中可用于目標識別與檢測、圖像恢復(fù)等。

現(xiàn)有的方法中，有些方法需要進行人工特征提取，例如通過提取圖像的SIFT特征來描述需要進行比較的兩幅圖像，再進行特征的匹配。不過這種方法不適用于解析圖片中的更高級別的特征，例如桌子、水杯等特征。還有的方法不需要進行人工特征特征提取，而是借助于卷積層。例如siamese方法，該方法將兩張圖片分別通過一個由若干卷積層堆疊而成的網(wǎng)絡(luò)結(jié)構(gòu)得到兩個輸出，再將兩個輸出拼接起來，送入一個由若干全連接層組成的網(wǎng)絡(luò)結(jié)構(gòu)，得到相似度輸出。這種方法對特征的解析和提取更加全面，但其訓(xùn)練所需的數(shù)據(jù)集中，相似度標簽是一個偏向于主觀的量，不同的人定義相似的標準是不同的，這就削弱了該種方法的說服力。

本文采用的相似度的評估標準是用圖像特征矩陣之間的距離表征的。距離通過二維動態(tài)時間規(guī)整求得，具有很強的客觀性，特征則是選用目標檢測網(wǎng)絡(luò)的卷積層進行提取的，一定程度繼承了siamese算法的優(yōu)越性。本項目已在GitHub開源：https://github.com/SongXuningithub/Similarity-Evaluation.git。

1 模型實現(xiàn)

1.1 特征提取

特征提取依靠若干卷積層進行，我們選用YOLO v1的前面卷積部分進行特征提取。首先對YOLO v1進行了結(jié)構(gòu)的調(diào)整，本文所用的YOLO由ResNet-18（已在Image-Net數(shù)據(jù)集上預(yù)訓(xùn)練）和若干卷積層、批量歸一化層、LeakyReLu層的堆疊，最后加兩個全連接層組成。YOLO在VOC2007數(shù)據(jù)集上訓(xùn)練（凍結(jié)ResNet-18部分的參數(shù)）后，去掉最后的一層卷積層以及其后的所有全連接層，得到的網(wǎng)絡(luò)結(jié)構(gòu)即為用于特征提取的網(wǎng)絡(luò)結(jié)構(gòu)。網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示，所需的輸出特征由Conv48層直接輸出，其后的所有層只用于模型訓(xùn)練。

這里選用YOLO的卷積層進行特征提取而不是用GoogleNet、ResNet這種僅僅用于目標分類的網(wǎng)絡(luò)的卷積層，是因為我們認為后者提取出的特征表征的是整個圖片的特征，而對于圖片中目標的移位沒有足夠的敏感度；相反，YOLO不僅僅關(guān)注圖像中的目標是什么，還關(guān)注目標的位置。因此同一場景中目標的移位也會更好地反映在卷積層提取的特征中。這有利于模型區(qū)分出場景或目標移位大小不同的圖片。

不直接用YOLO的最后一層輸出作為特征，是因為最后一層輸出的特征向量中，每一個值都代表對應(yīng)種類的物品出現(xiàn)在該負責(zé)區(qū)域的置信度。當負責(zé)區(qū)域中沒有該種類物體時，會被抑制為一個很小的值，所以當場景中沒有特別典型的物體時，輸出特征整體會趨于零，這是不利于后續(xù)處理的。所以使用過高級的特征在這里是不合適的。但我們可以借鑒skip-gram模型，使用網(wǎng)絡(luò)的中間輸出作為輸入的特征的間接表達，于是就選用中間的卷積層輸出作為其特征。

通過YOLO提取出的特征矩陣Feature Matrix的維度是[H，W，C]，H代表特征圖的高度，W代表特征圖的寬度，C代表每一個特征向量的維度，本文中C為48，即每個特征是一個48維的向量。

圖1 提取特征所用網(wǎng)絡(luò)結(jié)構(gòu)

1.2 動態(tài)時間規(guī)整

（1）背景：一維動態(tài)時間規(guī)整

一維動態(tài)時間規(guī)整用于求取兩個數(shù)字序列之間的距離。對于兩個等長序列seq1={ }a1,a2,…an和seq2={b1,b2,…bn}，我們可以直接用歐式距離來表示他們之間的距離：

但是，當兩個序列的長度不相等時，就不能用這種方式了。所以引入了動態(tài)時間規(guī)整。對于不等長的兩個序列和首先計算出它們的距離矩陣Distance Matrix（m行×n列，簡寫為DM）。矩陣元素DM(p,q)可以通過歐氏距離來計算，即它代表seq1的p點和seq2的q點的相似程度，距離越小則相似程度越高。所以DM包含了seq1的每個點和seq2的每個點之間的相似程度。之后利用動態(tài)規(guī)劃的思想找到一條從DM(1,1)到DM(m,n)的路徑。

具體實現(xiàn)時，我們只關(guān)心兩個序列之間的距離，所以可以不用記錄具體路徑，只用多維護一個表示累積距離的矩陣 Cumulative Distance Matrix（m行×n列，簡寫為CDM）即可。CDM的元素CDM(p,q)代表DM(1,1)到DM(p,q)的最短路徑長度，即兩個子序列和之間的距離。那么CDM(m,n)即為seq1和seq2之間的距離。

算法的思想是動態(tài)規(guī)劃，其遞推公式為：

具體的偽代碼形式將在后面二維動態(tài)時間規(guī)整中給出。

（2）特征矩陣距離測算：二維動態(tài)時間規(guī)整

實際要計算的是兩個三維特征矩陣之間的距離，涉及到一些向量操作，所以先將所用到的符號整理至表1。

表1 符號含義

雖然特征矩陣是三維的。但其實可將矩陣中的特征向量先簡化為一個點，那么可將特征矩陣簡化為二維平面，其尺寸為[H，W]。若直接將一維動態(tài)時間規(guī)整推廣到二維，則由于一維情況實際是在seq1和seq2計算出的m×n的二維空間中尋找最短路徑，二維情況也應(yīng)該是在FM1和FM2構(gòu)造的四維距離矩陣中尋找最短路徑。前者的時間復(fù)雜度為O(m×n)。若FM1尺寸為h1×w1，F(xiàn)M2尺寸為h2×w2，則由一維動態(tài)時間規(guī)劃直接推廣得到的二維動態(tài)時間規(guī)劃地時間復(fù)雜度為O(h1×w1×h2×w2)。顯然，復(fù)雜度提升了很多，這會導(dǎo)致算法難以應(yīng)用于流數(shù)據(jù)的實時檢測中。所以，本算法采用的是基于列對齊的二維動態(tài)時間規(guī)劃算法，以下簡稱為COL-DTW。

在COL-DTW中，最終還是在二維的距離矩陣DM中求解最短路徑，算法示意圖如圖2所示。要構(gòu)造這個二維距離矩陣，前提是FM1和FM2的列向量長度相等，即行數(shù)相等，有h1=h2。而DM中的每個元素則由對應(yīng)于FM1和FM2中的列之間的距離求得。即。 用 于 計算列向量之間距離的函數(shù)Distance_of_cols偽代碼如下：

該函數(shù)相當于計算兩個特征列向量的每一個對應(yīng)特征向量之間的歐氏距離，再將其做和、求平均。

計算兩個向量歐氏距離的偽代碼如下：

圖2 COL-DTW結(jié)構(gòu)

最終得到了二維的DM，該DM的尺寸為w1×w2，它的最短路徑距離也就是兩個三維特征矩陣之間的最短距離。如之前所述，實際的DTM計算過程不用關(guān)心具體路徑，只需維護一個累積距離矩陣CDM，算法具體流程如下：

則DTM（DM）輸出的距離即為兩張圖片的相似度：距離越大則相似度越小，距離越小則相似度越大。

2 算法性能分析

2.1 多圖片相似度比較

在進行相似度的計算之前，首先要確定一個基準量Vbase，這是由于進行比較的兩張圖片本就不可能是完全相同的兩張圖片，所謂相似最多是對同一場景的條件相近的兩次拍攝，所以基準量Vbase可以不是0。這里的Vbase定義為待匹配圖像（本例為A1）的左邊90%部分和右邊90%部分經(jīng)過運動模糊之后進行匹配的結(jié)果，即假設(shè)對該場景的兩次拍攝的差別只是相機移動了一個微小的角度。加入運動模糊則是為模擬真實拍攝過程中可能出現(xiàn)的抖動，實踐證明加不加此操作影響不大。Vbase計算如圖3所示。

圖3 Vbase的計算方法

要評估兩張圖片的相似度，就要整合上一節(jié)的兩個步驟：特征提取和2D-DTW（本文采用COL-DTW作為2D-DTW的具體實現(xiàn)）距離計算。整合算法偽代碼如下，其輸入為兩張圖片，輸出為模型評估的相似度。

本節(jié)使用材料有：一張基準圖片A1，與A1拍攝場景相同但拍攝角度和焦距不同的另一張圖片A2、若干與A1拍攝場景截然不同的7張圖片（B，C…H）。將A1分別與A2，B，C..H做比較，用2D-DTW距離表示它們兩兩之間的相似程度，距離大則認為相似程度低，反之則認為相似程度大。所用的與A1進行比較的圖片及其對應(yīng)名稱如表2所示。

表2 與A1比較的圖片

原圖A1及其與A2的關(guān)系如圖4所示。

圖4 A1與A2

通過計算，得出A1與其余8張圖片的距離如表3所示。

表3 與A1的2D-DTW距離

分析結(jié)果，A2作為與A1拍攝場景相同的圖片，與A1的2D-DTW距離最小，只有其他圖片的10%不到，而距離小代表相似度高，所以這個結(jié)果是符合預(yù)期的。

2.2 保真度評估

在圖像恢復(fù)、圖像壓縮等領(lǐng)域，常常會損失原圖像的質(zhì)量。所以在圖像被恢復(fù)之后，需要一個方法確定圖像相對于原圖像之間的保真度。保真度越高，則說明損失越小。例如圖5、圖6、圖7三張圖。

圖5 原圖

圖6 有損圖像1

圖7 有損圖像2

圖5是原始的無損圖像，圖6和圖7是圖5不同程度受損后的圖片?？梢钥吹?，雖然圖6中出現(xiàn)了一些無規(guī)律的鋸齒，使得原有的一些邊緣變得模糊，但卻較好地保留了有效信息。反觀圖7，雖然沒有鋸齒，但很多線條都已經(jīng)消失不見了，對原圖的信息出現(xiàn)了較大程度的損失。所以在實際評估中，我們應(yīng)該給圖6打出更高的分數(shù)。以下是兩種算法對上述兩張圖的評估。

（1）均方根誤差（RMS）算法

假設(shè)原始圖為f，受損圖像為?，則均方根誤差計算方式為：

其計算結(jié)果如表4所示。

表4 RMS計算結(jié)果

結(jié)果表示有損圖像2的RMS比有損圖像1的小，也就是說用RMS做評估的話有損圖像2的質(zhì)量高于有損圖像1。結(jié)合上面的分析，這顯然是不合理的。

（2）特征提取+2D-DTW算法

換用本文所提的（特征提取+2D-DTW）算法，結(jié)果如表5所示。

表5 特征提取+DTW計算結(jié)果

結(jié)果表示，特征提取之后，有損圖像2與原圖的2D-DTW距離相較于有損圖像1更大，也就是說用本文所提方法做評估的話有損圖像1的質(zhì)量高于有損圖像2，這是符合上述分析的。

3 結(jié)語

本文給出了基于卷積特征提取和二維動態(tài)時間規(guī)整的圖像相似度評估算法。該方法不需要特殊的數(shù)據(jù)集進行訓(xùn)練，在擁有已經(jīng)訓(xùn)練好的YOLO網(wǎng)絡(luò)的情況下，甚至可以免去訓(xùn)練的步驟。通過DTW進行最后的距離測算提升了算法的客觀性與靈活性。在已經(jīng)進行的圖像相似度評估實驗中表現(xiàn)出良好的性能，并且在圖像保真度評估中體現(xiàn)出比傳統(tǒng)的模板匹配算法更強的科學(xué)性，具有一定的實際意義。