基于最小生成樹(shù)的規(guī)則圖像碎片復(fù)原算法

趙 林，朱桂斌，文玉強(qiáng)，戚 曹

(1.重慶通信學(xué)院 應(yīng)急通信重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400035;2.重慶通信學(xué)院 信息資源管理應(yīng)用教研室，重慶 400035)

基于最小生成樹(shù)的規(guī)則圖像碎片復(fù)原算法

趙 林1，朱桂斌2，文玉強(qiáng)1，戚 曹1

(1.重慶通信學(xué)院 應(yīng)急通信重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400035;2.重慶通信學(xué)院 信息資源管理應(yīng)用教研室，重慶 400035)

文中針對(duì)大數(shù)量的規(guī)則圖像碎片進(jìn)行了拼接復(fù)原研究，在圖像碎片缺少外形輪廓這一匹配特征和碎片數(shù)量龐大的前提下，提出了一種基于最小生成樹(shù)原理的規(guī)則圖像碎片快速?gòu)?fù)原算法。通過(guò)計(jì)算圖像碎片邊緣像素差異值的方法對(duì)碎片進(jìn)行匹配，再運(yùn)用貪心策略的思想，通過(guò)最小生成樹(shù)原理對(duì)圖像進(jìn)行復(fù)原框架設(shè)計(jì)，完成了對(duì)規(guī)則圖像碎片的快速?gòu)?fù)原。而且相比現(xiàn)有算法，文中算法無(wú)需知道原始圖像的尺寸，更為符合實(shí)際應(yīng)用情況。仿真結(jié)果表明，文中算法完成了對(duì)大數(shù)量圖像碎片的復(fù)原工作，具有快速、準(zhǔn)確的特點(diǎn)。

規(guī)則碎片；匹配；復(fù)原；最小生成樹(shù)

1 概 述

如今，隨著計(jì)算機(jī)等硬件設(shè)備的不斷發(fā)展，通過(guò)數(shù)字圖像輸入設(shè)備來(lái)獲得更加清晰的數(shù)字圖像已不成問(wèn)題。利用掃描儀或者數(shù)碼相機(jī)獲取圖像碎片的數(shù)字圖像，之后利用碎片的顏色、形狀等信息探測(cè)出相鄰的碎片，進(jìn)而讓計(jì)算機(jī)程序自動(dòng)拼接相鄰碎片，最終實(shí)現(xiàn)圖像的復(fù)原。這類問(wèn)題廣泛存在于情報(bào)和密碼破譯、圖像信息修復(fù)及司法物證復(fù)原等方面，特別是當(dāng)碎片數(shù)量巨大，人工拼接難以在短時(shí)間內(nèi)完成任務(wù)時(shí)，我們就可以借助現(xiàn)代計(jì)算機(jī)技術(shù)從成千上萬(wàn)圖像碎片中找到互相鄰接的圖像碎片，通過(guò)相應(yīng)算法計(jì)算并最終拼接成完整的圖像[1]。此應(yīng)用是計(jì)算機(jī)視覺(jué)、模式識(shí)別等領(lǐng)域中的一個(gè)新穎且典型的應(yīng)用，也引起了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注。近年來(lái)，很多學(xué)者紛紛開(kāi)展研究并提出了很多行之有效的方法。至此，圖像碎片的自動(dòng)拼接成為了計(jì)算機(jī)應(yīng)用領(lǐng)域的一個(gè)研究熱點(diǎn)，也是一個(gè)難點(diǎn)。

常規(guī)圖像碎片拼接方法主要研究非規(guī)則碎片的匹配，利用碎片邊緣的尖角、尖點(diǎn)、面積及輪廓等特征，搜索與之匹配的相鄰碎片進(jìn)行拼接，但對(duì)于有些外形無(wú)區(qū)別的矩形圖片碎片來(lái)說(shuō)，例如碎紙機(jī)破碎文檔所形成的矩形碎片，它缺少了每個(gè)碎塊所特有的重要匹配特征——形狀，處理這種類型的碎片具有相對(duì)較大的挑戰(zhàn)，所以利用非規(guī)則碎片的拼接技術(shù)顯然不合理。所以對(duì)于外形相同的規(guī)則圖像碎片的復(fù)原來(lái)說(shuō)，就要關(guān)注其圖像內(nèi)容來(lái)解決匹配方面的問(wèn)題。例如在文獻(xiàn)[2]中，作者采用了估計(jì)碎片匹配對(duì)邊緣值的方法來(lái)進(jìn)行匹配，而這種方案最終恢復(fù)了一幅共有3 300塊碎片的圖像，這也是處理規(guī)則圖像碎片匹配方面的又一創(chuàng)新。

對(duì)于規(guī)則圖像碎片的復(fù)原，研究的核心有兩點(diǎn)：

一是如何在碎片間進(jìn)行匹配，采用何種方法來(lái)計(jì)算它們之間的匹配度；

二是采取何種復(fù)原結(jié)構(gòu)來(lái)快速無(wú)誤地復(fù)原出原始圖像。

在碎片匹配方面，Kosiba在文獻(xiàn)[3]中首次利用了碎塊形狀和圖像內(nèi)容信息來(lái)匹配碎片，提出了在碎片的輪廓邊緣上計(jì)算兩側(cè)像素差值的方法，依計(jì)算出的差值來(lái)判決碎片是否相鄰，隨后在文獻(xiàn)[4-5]中也采取了類似的匹配計(jì)算方法，并且在文獻(xiàn)[4]中詳細(xì)證明了此方法具有高效的匹配性和較低的計(jì)算開(kāi)銷，是一種簡(jiǎn)單有效的方法，也是在規(guī)則碎片匹配中廣泛應(yīng)用的方法。

在圖像碎片復(fù)原方面，目前有采取動(dòng)態(tài)規(guī)劃[5]、匈牙利方法[6]和貪婪算法[4]的解決方案，它們都是現(xiàn)今主流的計(jì)算機(jī)處理方法，但它們之中存在的問(wèn)題主要有可處理的碎片數(shù)量較少、復(fù)原度不高和需要過(guò)多的限制條件。

所以，基于現(xiàn)今存在的問(wèn)題，在提高處理數(shù)量的同時(shí)不失準(zhǔn)確度這一原則下，文中提出了基于最小生成樹(shù)的規(guī)則圖像復(fù)原方法。對(duì)來(lái)自同一幅圖像的n個(gè)互不重疊的無(wú)方向變換的正方形圖像碎片，在無(wú)需其他原始圖像先驗(yàn)信息的條件下，運(yùn)用文中提出的復(fù)原方案可以快速完成碎片間的匹配并恢復(fù)出復(fù)原率較高的原始圖像。

在匹配計(jì)算方面，文中采用了基于邊緣色彩差異值的算法，此算法不僅可以有效匹配相鄰碎片，同時(shí)還有較小的計(jì)算代價(jià)。而在復(fù)原構(gòu)架的設(shè)計(jì)上，文中在參考了文獻(xiàn)[2-3，5-7]的基礎(chǔ)上，基于最小生成樹(shù)原理設(shè)計(jì)了復(fù)原結(jié)構(gòu)。相對(duì)于文獻(xiàn)[2-3]所采用的基于貪婪算法的復(fù)原方案，文中方法能更快地復(fù)原出原始圖像，同時(shí)具有簡(jiǎn)便的算法結(jié)構(gòu)和較高的復(fù)原度，而在計(jì)算代價(jià)上相對(duì)現(xiàn)存算法有較小的計(jì)算開(kāi)銷[8]。

通過(guò)仿真實(shí)驗(yàn)結(jié)果顯示，文中算法具有良好的復(fù)原效果。

2 基于邊緣色彩差異值的圖像碎片匹配

在匹配過(guò)程中采用邊緣色彩差異度的匹配算法，這種算法具有更廣的適配性，在文獻(xiàn)[4]中被證明是最為高效的匹配算法。對(duì)于規(guī)則碎片的匹配，只需考慮碎片邊緣的顏色匹配問(wèn)題。若是在原始圖像中兩碎片相鄰，則它們?cè)谙噜忂吘壣蠒?huì)有相似的色彩分布，則在相鄰邊緣上，兩個(gè)碎片間的差異值和最小，以此作為評(píng)判標(biāo)準(zhǔn)來(lái)計(jì)算它們之間的匹配度。

對(duì)于彩色圖片，可取R,G,B色彩空間的矢量進(jìn)行匹配計(jì)算，通過(guò)計(jì)算碎片間的匹配度大小來(lái)判斷它們?cè)谠紙D像中是否鄰接。用D代表碎片對(duì)之間的匹配度，對(duì)于碎片xi和xj，設(shè)定它們之間的空間關(guān)系為R∈{u,r,d,l}，u,r,d,l分別代表碎片xj位于xi的上、右、下、左側(cè)，用D(xi,xj,R)表示碎片xj位于碎片xi相應(yīng)位置的匹配度。編號(hào)為i和j的碎片左右邊緣匹配程度(i左j右)用相同位置(m表示對(duì)應(yīng)的行數(shù))的灰度差的積累結(jié)果衡量，定義邊緣匹配函數(shù)為公式(1)。此值越小，說(shuō)明匹配程度越好，吻合程度越好。

(1)

首先把一幅原始圖像分解為N幅碎片圖像并且進(jìn)行無(wú)方向變化的隨機(jī)置亂，每個(gè)碎片大小為P*P。假設(shè)有待匹配碎片xi和xj，為每個(gè)碎片分配P*P*3大小的矩陣。當(dāng)碎片位于左側(cè)時(shí)，用D來(lái)表示這兩個(gè)碎片之間的匹配度，其值越小，則兩個(gè)碎片之間的匹配度越高，如式(2)所示。

D(xi,xj,l)=

(2)

顯然，兩個(gè)碎片相鄰的可能性越大時(shí)，匹配度D就會(huì)越小。把每塊碎片與剩余的碎片依次做匹配計(jì)算，之后把求得的值放入碎片匹配值矩陣D(xi,xj,r)中，它的大小為N*N*4。因?yàn)槠ヅ渖婕暗乃槠瑳](méi)有進(jìn)行方向變換，所以第一層矩陣放入的是碎片xi第一邊和碎片xj第三邊的匹配值，第二層矩陣放入的是碎片xi第二邊和碎片xj第四邊的匹配值，第三層矩陣放入的是碎片xi第三邊和碎片xj第一邊的匹配值，第四層矩陣放入的是碎片xi第四邊和碎片xj第二邊的匹配值。

3 基于最小生成樹(shù)的圖像碎片復(fù)原

針對(duì)規(guī)則圖像碎片，文中在碎片的復(fù)原過(guò)程中運(yùn)用圖論學(xué)中的最小生成樹(shù)原理[9]。它是一種運(yùn)用了“貪心”策略的最優(yōu)化解決方法[10]，運(yùn)用到碎片復(fù)原中可以看出，復(fù)原圖像初始時(shí)從一個(gè)碎片開(kāi)始逐步加入其余碎片直到全部拼接完畢。而且不需要知道原始圖像的其他先驗(yàn)知識(shí)，如原始圖像的尺寸，也無(wú)需人工干預(yù)。

3.1 最小生成樹(shù)原理

根據(jù)文獻(xiàn)[11-12]所提出的克魯斯卡爾(Kruskal)算法,來(lái)尋找復(fù)原圖像相應(yīng)的最小生成樹(shù)。設(shè)圖用G=(VG,EG)表示，其中VG和EG分別表示圖G的節(jié)點(diǎn)集合和邊集合，也就是把節(jié)點(diǎn)集和邊集作為圖的屬性來(lái)表示。節(jié)點(diǎn)就是每個(gè)圖像碎片，而邊就是碎片之間的連接關(guān)系，其中每一個(gè)節(jié)點(diǎn)u∈VG可以指向滿足條件(u,v)∈EG的節(jié)點(diǎn)v，EG的元素一般用(u,v)表示，其中u,v屬于VG，而邊的權(quán)重為矩陣D(xi,xj,r)中存放的碎片之間的匹配值D。

(3)

因?yàn)門無(wú)回路且連接了所有節(jié)點(diǎn)，所以它必然是一棵樹(shù)，故稱之為最小生成樹(shù)[14]。

3.2 基于最小生成樹(shù)的圖像碎片復(fù)原算法

在此階段，根據(jù)Kruskal算法的思想，從圖中尋找其最小生成樹(shù)來(lái)構(gòu)造復(fù)原圖像。在起始階段，把每一個(gè)節(jié)點(diǎn)(碎片)當(dāng)作一棵樹(shù)，也就是令最小生成樹(shù)的初始狀態(tài)為只有N個(gè)節(jié)點(diǎn)而無(wú)邊的非連通圖T=(VG,{})，根據(jù)邊集合以及它們每條邊所對(duì)應(yīng)的權(quán)重找到最低代價(jià)(最高匹配度)的邊emin并且從邊集合中取出，若是屬于這個(gè)邊emin的節(jié)點(diǎn)(碎片)屬于同一棵樹(shù)，則舍去這條邊，若是不屬于同一棵樹(shù)，則把具有最小權(quán)值的邊emin作為安全邊，并把它添加到正在生長(zhǎng)的樹(shù)中。在添加過(guò)程中，若是分別屬于兩棵樹(shù)中的節(jié)點(diǎn)(碎片)占用了同一個(gè)位置，則舍去這條邊。算法偽代碼如圖1所示。

圖1 算法偽代碼

接下來(lái)對(duì)一幅圖像碎片進(jìn)行復(fù)原。圖2顯示的是一幅像素?cái)?shù)為800*600的圖像及其任意置亂的碎片，碎片的邊長(zhǎng)像素?cái)?shù)為40，數(shù)量為300塊。

圖2 原始圖像及其置亂圖像

對(duì)圖2中的置亂圖像，采取文中提出的復(fù)原算法對(duì)其進(jìn)行復(fù)原。初始每個(gè)碎片都是一棵含有一個(gè)節(jié)點(diǎn)的樹(shù)，把匹配值D最小(權(quán)重值w最大)的兩個(gè)碎片作為復(fù)原起點(diǎn)，按照算法的約束條件依次加入合法的碎片，直到碎片全部加入并形成一棵樹(shù)，最終按照生成樹(shù)中的位置信息復(fù)原出圖像。復(fù)原過(guò)程如圖3所示。

圖3 碎片圖像復(fù)原過(guò)程

4 仿真結(jié)果及分析

在算法仿真過(guò)程中，采取中文算法和文獻(xiàn)[4]的算法對(duì)碎片圖像進(jìn)行復(fù)原仿真并作出比較。文中使用CPU為2.20GHzIntel(R)Core(TM)T6670的計(jì)算機(jī)在MatlabR2013a的仿真平臺(tái)上進(jìn)行編程實(shí)驗(yàn)。

選定三種尺寸的20幅圖像，把碎片邊長(zhǎng)設(shè)定為50*50，對(duì)其打亂，分別包含有400塊、800塊和1 200塊碎片。對(duì)每幅圖像碎片運(yùn)用文中算法測(cè)試10次，記錄其復(fù)原的最高準(zhǔn)確度、最低準(zhǔn)確度和平均準(zhǔn)確度，如表1所示。

表1 文中算法運(yùn)算性能分析

對(duì)文中算法和文獻(xiàn)[4]中提出的算法進(jìn)行比較，對(duì)上述20圖像進(jìn)行測(cè)試，每幅圖像碎片測(cè)試10次，對(duì)每次運(yùn)行結(jié)果取最高準(zhǔn)確值作比較，如表2所示。

表2 算法性能比較

由表2可知，文中算法相對(duì)文獻(xiàn)[4]算法具有較高的復(fù)原準(zhǔn)確度。

為了能直觀地說(shuō)明文中算法復(fù)原的有效性和優(yōu)越性，選取文獻(xiàn)[4]中所提供的2幅圖像，分別對(duì)其置亂，然后應(yīng)用文獻(xiàn)[4]的算法與文中算法進(jìn)行比較，其結(jié)果如圖4所示。圖中，第一行為置亂圖像，第二行為文獻(xiàn)[4]算法所復(fù)原的圖像，第三行為文中算法所得圖像。

圖4 比較結(jié)果

由圖4可知，采取文中算法處理的碎片圖像，復(fù)原的準(zhǔn)確度得到了大幅提升。由于文中算法采用了貪心策略，在復(fù)原過(guò)程中無(wú)需知道原始圖像尺寸，這也是文中算法的獨(dú)特之處，較以往算法更為貼合實(shí)際應(yīng)用。

5 結(jié)束語(yǔ)

文中提出了一種用于規(guī)則圖像碎片的快速?gòu)?fù)原算法。在算法實(shí)現(xiàn)中，運(yùn)用了文獻(xiàn)[4]提出的基于邊緣色彩差異度的匹配算法，同時(shí)結(jié)合了圖論學(xué)中的最小生成樹(shù)原理用于復(fù)原框架的設(shè)計(jì)。由仿真實(shí)驗(yàn)可知，文中算法對(duì)于大量規(guī)則圖像碎片可以進(jìn)行準(zhǔn)確復(fù)原，同時(shí)相比文獻(xiàn)[4]算法，準(zhǔn)確度有了大幅度提升。在下一步的工作中，會(huì)根據(jù)實(shí)際應(yīng)用的需求，在匹配過(guò)程中，對(duì)存在照度突變或噪聲干擾的情況下如何對(duì)碎片精確匹配進(jìn)行研究。同時(shí)，對(duì)方向錯(cuò)亂的圖像碎片復(fù)原進(jìn)行研究并進(jìn)行算法實(shí)現(xiàn)。

[1] 先 毅.圖像碎片復(fù)原方法的研究[D].北京：華北電力大學(xué),2010.

[2]PomeranzD,ShemeshM,Ben-ShaharO.Afullyautomatedgreedysquarejigsawpuzzlesolver[C]//Proceedingsof

CVPR.Piscataway,NJ:IEEE,2011:9-16.

[3] Kosiba D A,Devaux P M,Balasubramanian S,et al.An automatic jigsaw puzzle solver[C]//Proceedings of the 12th International conference on image processing.Piscataway,NJ:IEEE,1994:616-618.

[4] Cho T S,Avidan S,Freeman W T.A probabilistic image jigsaw puzzle solver[C]//Proceedings of CVPR.Piscataway,NJ:IEEE,2010:183-190.

[5] Yang X,Adluru N,Latecki L J.Particle filter with state permutations for solving image jigsaw puzzles[C]//Proceedings of CVPR.Piscataway,NJ:IEEE,2011:2873-2880.

[6] Alajlan N.Solving square jigsaw puzzles using dynamic programming and the hungarian procedure[J].American Journal of Applied Sciences,2009,5(11):1941-1947.

[7] Sholomon D,David O,Netanyahu N S.A genetic algorithm-based solver for very large jigsaw puzzles[C]//Proceedings of CVPR.Piscataway,NJ:IEEE,2013:1767-1774.

[8] Toyama F,Fujiki Y,Shoji K,et al.Assembly of puzzles using a genetic algorithm[C]//Proceedings of CVPR.Piscataway,NJ:IEEE,2002.

[9] Held M,Karp R M.The traveling-salesman problem and minimum spanning trees:Part II[J].Mathematical Programming,1971,1(1):6-25.

[10] 朱 青.計(jì)算機(jī)算法與程序設(shè)計(jì)[M].北京：清華大學(xué)出版社,2009:122-126.

[11] Kruskal J B.On the shortest spanning subtree of a graph and the travelling salesman problem[J].Proceedings of the American Mathematical Society,1956,7:48-50.

[12] Cormen T H,Leiserson C E,Rivest R L,et al.Introduction to algorithms[M].2nd ed.[s.l.]:McGraw-Hill,2001:1297-1305.

[13] 朱清新，楊 凡，鐘黔川.計(jì)算機(jī)算法設(shè)計(jì)與分析導(dǎo)論[M].北京:人民郵電出版社,2008.

[14] Matsui T. The minimum spanning tree problem on a planar graph[J].Discrete Applied Mathematics,1995,58(1):91-94.

A Restoration Algorithm for Square Image Pieces Based on MST

ZHAO Lin1，ZHU Gui-bin2，WEN Yu-qiang1，QI Cao1

(1.Chongqing Key Laboratory of Emergency Communication,Chongqing Communication Institute,Chongqing 400035,China;2.Teaching and Research Section of Information Resources Management and Application,ChongqingCommunication Institute,Chongqing 400035,China)

The matching and restoration for large number of square image pieces are studied in this paper.On the premise of lacking outline and large quantity of pieces,a fast restoration algorithm for square image pieces based on Minimum Spanning Tree (MST) is put forward.It calculates the difference of pixel value on the edge to match two pieces,then with the idea of the greedy strategy,the structure for restoration of square image pieces is designed,completing the quick restoration of square image pieces finally.Compared with the existing algorithms,this algorithm does not need to know the size of the original image,more accorded with the actual application situation.Simulation indicates that it can complete the restoration for tens of thousands pieces rapidly and accurately.

square pieces;matching;restoration;minimum spanning tree

2015-08-31

2015-12-09

時(shí)間：2016-06-00

國(guó)家自然科學(xué)基金資助項(xiàng)目(61272043)；重慶市基礎(chǔ)與前沿研究重點(diǎn)項(xiàng)目(cstc2013jjB40009)；重慶科技研發(fā)基地能力提升項(xiàng)目(cstc2014pt-sy40003)

趙 林(1990-)，男，碩士研究生，研究方向?yàn)閳D像與視頻分析；朱桂斌，教授，博士，研究方向?yàn)樾畔踩D像處理。

TP391

A

1673-629X(2016)06-0069-05

10.3969/j.issn.1673-629X.2016.06.015