基于坎貝拉度量改進的智能拼圖算法

吳娟

（濟南工程職業(yè)技術學院信息工程學院，山東 濟南 250200）

1 引言

數據挖掘技術的進步使得大規(guī)模的圖像問題得以被解決，例如用計算機解決拼圖問題能夠實現(xiàn)碎片的還原和圖像對象的定位等。好的拼圖技術能夠在上百以及上千個拼圖塊中找到最好的匹配。最近有研究[1,2]實現(xiàn)基于圖模型解決拼圖問題，它用一個節(jié)點代表相鄰兩塊的相似度分數。其中，Gallagher[1]提出了一種新的兼容性測量MGC(馬氏相似度度量)。Paikin和Tal[2]提出了對于缺失拼圖塊的解決方案。Kosiba等人[3]根據拼圖塊的顏色相似性進行匹配。Yao等人[4]根據拼圖分類策略來組裝拼圖。Nielson等人[5]采用分而治之的策略，通過對可能相互連接的碎片進行分組組裝。還有一些研究[6-10]不考慮碎片的形狀信息，主要考慮碎片的內容來解決方形拼圖問題。這些方法一般都是首先計算相鄰塊的相似度，然后利用貪婪算法組裝拼圖。

目前大多數拼圖算法側重于計算拼圖塊之間的邊緣相似度，即測量拼圖塊邊緣的像素之間的兼容性，但不是檢查所有邊緣像素。雖然機器學習能夠利用像素級分析邊緣相似度，但是不容易實現(xiàn)。通過考慮拼圖塊之間的邊緣相似度，本文提出一種改進的拼圖算法來解決未知方向、未知位置的拼圖。將計算邊緣相似度的坎貝拉距離算法與MGC算法結合，使得還原圖像更準確。

2 算法與改進

MGC（馬氏相似度度量）是一種能夠較好還原圖片的相似度測量算法。早期的SSD算法僅僅比較RGB值的差異，而MGC通過比較顏色梯度，實現(xiàn)了較高的準確率。還原算法有貪婪算法、遺傳算法等，其中基于最小生成樹的還原過程能夠還原出較準確的圖片。

2.1 MGC度量（馬氏相似度度量）

MGC通過考慮邊緣相似度，使度量更準確，不但計算相鄰塊之間顏色梯度的協(xié)方差，而且將馬氏距離應用其中。

拼圖塊xj在xi的右側，計算相似度評分ELR(xi,xj)時，首先表示出拼圖塊xi右邊緣顏色梯度變化的向量，定義一個P*3的矩陣。其中，GiL表示拼圖塊xi右側邊界梯度變化。

uiL為拼圖塊xi右邊緣的平均分布。t為行數，c為顏色通道。

其中Si是圖像塊xi右邊緣顏色梯度的一個3*3的協(xié)方差矩陣。ELR(xi,xj)為xi到xj的相似度度量。

GijLR(t)為拼圖塊xi右邊緣到拼圖塊xj左邊緣的梯度變化。

公式(5)為修正公式。ELR(xi,xj)是拼圖塊xi到拼圖塊xj的馬氏距離，ERL(xj,xi)是拼圖塊xj到拼圖塊xi的馬氏距離。MGC(xi,xj)為兩個拼圖塊之間馬氏距離的加權值。

2.2 采用Kruskal算法還原圖像

每個拼圖塊是一個頂點，相鄰拼圖塊之間的MGC為邊的權重，構成矩陣E。

（1）找出E中代價最小的邊emin并將其從MGC矩陣中移除。如果emin的頂點位于同一個森林，則為了避免環(huán)路的形成，將emin舍棄。如果在合并森林時，兩塊拼圖占據相同的位置，即發(fā)生了沖突，則舍棄emin。如果emin符合要求通過檢測，則將其加入森林；否則繼續(xù)在剩余邊里選取權重最小的，重復以上步驟。

（2）將生成的最小生成樹進行剪枝，剪枝時把最大部分留在矩形內。

（3）將矩形中剩余部分進行填充。

2.3 坎貝拉距離計算

坎貝拉距離(Canberra距離)算法最早是由Lance和Williams提出的。它是相似度分析中一種度量距離的常用方法。好的度量方法對于碎片之間的微小差異是很敏感的，當圖片中出現(xiàn)大量相似物時，利用MGC方法進行組裝拼圖的準確率會降低。因此本文將坎貝拉距離算法應用于拼圖中。

提取相鄰塊邊緣某一行（列）的RGB特征。將相鄰拼圖塊標記為pi、pj，若pi是塊i的上邊緣，則pj是塊j的下邊緣，則pi(h,Q,c)為拼圖塊pi在第h位置第c通道最左側邊界的顏色梯度，則pj(h,l,c)為拼圖塊pj在第h位置第c通道最左側邊界的顏色梯度。然后通過計算相鄰塊邊緣對應向量之間的坎貝拉距離，從而得到相鄰塊之間的相似度度量：

其中d(pi,pj)為相鄰兩塊拼圖塊的坎貝拉距離。式中d(pi,pj)越小，說明pi，pj接近程度越大，否則說明pi，pj接近程度越小。

2.3.1 Canberra與MGC結合方式一

當有大量相似物時，單純的MGC算法準確率不高，因此本文提出將Canberra與MGC結合的度量方式。新的度量方式能夠增加碎片之間的差別。

公式（8）（9）中a，b值大小不同時，進行正確匹配的拼圖塊的數量不同，運行時間也會不同。

在對a∈{0.4,0.5,0.6,0.7}時進行對比分析，發(fā)現(xiàn)當a=0.7時正確匹配的拼圖塊的數量最多，效果最好。將此方法標記為Can1。

Can1算法在不同a取值時，正確匹配的拼圖塊的數量對比如圖1所示。

從圖1中可以看出，當a=0.7，b=0.3時正確匹配的拼圖塊的數量最多。因此后續(xù)的實驗中取a=0.7，b=0.3。

圖1 a值不同時，不同圖片匹配正確的拼圖塊數量對比

2.3.2 Canberra與MGC結合方式二

將Canberra距離與MGC距離結合測量兩個拼圖塊之間的相似度公式如下所示：

公式（10）中r是一個可以設置的自由參數，對r∈{1/2,1/4,1/8,1/16}進行對比分析，發(fā)現(xiàn)當r=1/4時效果最好。將次方法標記為Can2。

r值大小不同時，Can2算法進行正確匹配的拼圖塊的數量對比如圖2所示。

圖2 r值不同時，不同圖片匹配正確的拼圖塊數量對比

從圖2中可以看出當r=1/8開始正確匹配的拼圖塊數量明顯下降，r=1/4，即r=0.25時正確匹配的拼圖塊數量最多。因此后續(xù)的實驗中取r=1/4。

類似于Gallagher[4]，我們假定N為相似度矩陣，則N(pi,pj)是拼圖塊pi和pj的相似度評分，設P為所有拼圖塊的集合，則歸一化矩陣N"定義如下：

由于不需要將拼圖塊與自身相比較，因此對角線上的項不需要考慮。這一規(guī)范化提高了拼圖的準確率。

2.3.3確定整體拼接策略

貪婪算法即一步一步地構建問題的最優(yōu)解決方案。其中每一步只需考慮眼前的最佳選擇，即我們希望通過局部最優(yōu)到達全局最優(yōu)。

（1）確定判斷閾值函數值。

其中mean(Can1)、mean(Can2)是Can1和Can2的均值，var(Can1)、var(Can2)是Can1和Can2的方差。

（2）將計算的所有塊與塊、每種塊與塊之間的16種組合的g(Can1)、g(Can2)的值，選擇值最小的值作為正確的拼接。

（3）將上一次結果與剩余塊拼接，防止出現(xiàn)重疊。

圖3中拼接發(fā)生沖突，因此合并這兩個森林后的結果將被丟棄。圖4中拼接未發(fā)生重疊，因此為正確拼接。

圖3 拼接發(fā)生沖突

圖4 成功拼接

（4）如果拼接之后的結果圖片的維度超過原圖像維度，需要剪枝。

（5）剪枝之后，將剩余空缺較小的部分重新填充完畢。

3 實驗結果及分析

3.1 三種算法對于無噪聲圖片效果對比

本文將網絡圖像庫以及實驗拍攝的一些圖片分為14組，分別利用Can1算法、Can2算法和MGC算法進行測試，將每張圖片劃分為432塊，每塊28×28像素，實驗環(huán)境選擇Win10 64位操作系統(tǒng)，MatlabR2021a編程實現(xiàn)。實驗結果如表1所示。本文在圖5中展示6張圖片采用兩種算法來重建圖像的匹配圖。

圖5 三種算法準確率對比

從表1中可以發(fā)現(xiàn)，在所測試的14組圖片中，使用本文兩種算法，拼圖塊進行匹配的準確率都有所提高。Can2相對于大多數圖片，都能得到較高的準確率。超過64%的圖片有高達90%以上的準確率。對于背景單一圖片Can2算法仍能達到80%左右的準確率，而此時MGC只能達到60%左右的準確率。Can1相對于某些圖片雖然也起到了微調的作用，準確率也有所提高，但相比于Can2效果要差。

表1 三種算法準確率對比

圖5中將三種算法完成圖作對比，左為利用MGC還原后的圖像，中間為利用Can1還原后的圖像，右為利用Can2還原后的圖像。從圖5中可以看出，對于相似度小的圖像，三種方法均能得到比較完整的還原圖像。而對于背景單一相似物多的圖片，利用坎貝拉距離還原后的圖像能夠減少圖片亂碼的出現(xiàn)。

本文算法相比于MGC算法準確率有所提高，是因為對于背景圖片單一、有大量相似物時，相似塊之間，利用坎貝拉距離算法計算出的矩陣減少了相等值的出現(xiàn)，而利用MGC算法計算出的馬氏距離會有比較多的相同情況，因此還原后的圖像會有差異。對于背景復雜的圖像，Can2算法和MGC算法都能區(qū)分出拼圖塊之間的差異，因此還原此種圖像效果較好。

3.2 噪聲干擾下兩種算法對比

拼圖問題為廣泛的實際應用提供了可能的解決方案，如考古遺物的重組，被破壞文件的復原。在這些應用中，現(xiàn)實圖像總存在大量噪聲。過去的文獻中，解決拼圖問題往往假定圖像是完美的，受到噪聲影響后，其準確率會有明顯變化，比如MGC算法。本文對于受到噪聲干擾的圖像進行實驗預估。首先對14組圖片添加噪聲，然后對兩種算法的準確率進行對比。每張圖片均加入密度為0.05的椒鹽噪聲及均值為0、方差為0.01的高斯噪聲，觀察其準確率。

圖6，圖7中結果可以看出，對于14組測試圖片中，MGC算法對于個別背景單一的圖片，加入噪聲后其準確率會有所提高，而對于背景復雜的圖片其準確率會有所下降。而Can2準確率始終比MGC準確率高，表現(xiàn)出很好的魯棒性，優(yōu)于MGC還原圖像的算法。

圖6 高斯噪聲影響下兩種算法的準確率

圖7 椒鹽噪聲影響下的兩種算法的準確率

3.3 設置圖片缺損

重建圖像的另外一個難題是當圖片不完整時，是否還能達到很高的準確率。隨機設置黑塊制造不完整性，對第一組所有圖片隨機進行涂黑。

將Can1算法與MGC算法作對比，從圖8中可以看出，MGC的準確率低于Can1的準確率，MGC的準確率只有0.6。

圖8 第一組圖片加黑塊后的準確率

4 結語

本文提出了一種新穎的拼圖算法，通過坎貝拉距離計算相鄰塊邊緣的顏色梯度，根據坎貝拉算法與MGC算法結合得到的距離對相鄰拼圖塊的相似度進行評分，重建圖像時本文先將結果值進行加權，然后還原圖像。

坎貝拉測量算法實驗結果表明，本文中的算法對于所測試圖片有較高的準確率，當有噪聲干擾時，Can2算法相比于MGC算法有較高的準確率，當圖片設置缺損時，雖然兩種算法相對于之前完整的圖像準確率有所降低，但是Can1算法的準確率高于MGC的準確率。后續(xù)的工作中，將進一步優(yōu)化算法，提高算法的魯棒性和準確率。