吳娟

（濟(jì)南工程職業(yè)技術(shù)學(xué)院信息工程學(xué)院，山東 濟(jì)南 250200）

1 引言

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

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

2 算法與改進(jìn)

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

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

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

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

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

其中Si是圖像塊xi右邊緣顏色梯度的一個(gè)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)為兩個(gè)拼圖塊之間馬氏距離的加權(quán)值。

2.2 采用Kruskal算法還原圖像

每個(gè)拼圖塊是一個(gè)頂點(diǎn)，相鄰拼圖塊之間的MGC為邊的權(quán)重，構(gòu)成矩陣E。

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

（2）將生成的最小生成樹(shù)進(jìn)行剪枝，剪枝時(shí)把最大部分留在矩形內(nèi)。

（3）將矩形中剩余部分進(jìn)行填充。

2.3 坎貝拉距離計(jì)算

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

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

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

2.3.1 Canberra與MGC結(jié)合方式一

當(dāng)有大量相似物時(shí)，單純的MGC算法準(zhǔn)確率不高，因此本文提出將Canberra與MGC結(jié)合的度量方式。新的度量方式能夠增加碎片之間的差別。

公式（8）（9）中a，b值大小不同時(shí)，進(jìn)行正確匹配的拼圖塊的數(shù)量不同，運(yùn)行時(shí)間也會(huì)不同。

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

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

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

圖1 a值不同時(shí)，不同圖片匹配正確的拼圖塊數(shù)量對(duì)比

2.3.2 Canberra與MGC結(jié)合方式二

將Canberra距離與MGC距離結(jié)合測(cè)量?jī)蓚€(gè)拼圖塊之間的相似度公式如下所示：

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

r值大小不同時(shí)，Can2算法進(jìn)行正確匹配的拼圖塊的數(shù)量對(duì)比如圖2所示。

圖2 r值不同時(shí)，不同圖片匹配正確的拼圖塊數(shù)量對(duì)比

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

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

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

2.3.3確定整體拼接策略

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

（1）確定判斷閾值函數(shù)值。

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

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

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

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

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

圖4 成功拼接

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

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

3 實(shí)驗(yàn)結(jié)果及分析

3.1 三種算法對(duì)于無(wú)噪聲圖片效果對(duì)比

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

圖5 三種算法準(zhǔn)確率對(duì)比

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

表1 三種算法準(zhǔn)確率對(duì)比

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

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

3.2 噪聲干擾下兩種算法對(duì)比

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

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

圖6 高斯噪聲影響下兩種算法的準(zhǔn)確率

圖7 椒鹽噪聲影響下的兩種算法的準(zhǔn)確率

3.3 設(shè)置圖片缺損

重建圖像的另外一個(gè)難題是當(dāng)圖片不完整時(shí)，是否還能達(dá)到很高的準(zhǔn)確率。隨機(jī)設(shè)置黑塊制造不完整性，對(duì)第一組所有圖片隨機(jī)進(jìn)行涂黑。

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

圖8 第一組圖片加黑塊后的準(zhǔn)確率

4 結(jié)語(yǔ)

本文提出了一種新穎的拼圖算法，通過(guò)坎貝拉距離計(jì)算相鄰塊邊緣的顏色梯度，根據(jù)坎貝拉算法與MGC算法結(jié)合得到的距離對(duì)相鄰拼圖塊的相似度進(jìn)行評(píng)分，重建圖像時(shí)本文先將結(jié)果值進(jìn)行加權(quán)，然后還原圖像。

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