趙 林，朱桂斌，文玉強，戚 曹

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

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

趙 林1，朱桂斌2，文玉強1，戚 曹1

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

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

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

1 概 述

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

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

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

一是如何在碎片間進行匹配，采用何種方法來計算它們之間的匹配度；

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

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

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

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

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

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

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

在匹配過程中采用邊緣色彩差異度的匹配算法，這種算法具有更廣的適配性，在文獻[4]中被證明是最為高效的匹配算法。對于規(guī)則碎片的匹配，只需考慮碎片邊緣的顏色匹配問題。若是在原始圖像中兩碎片相鄰，則它們在相鄰邊緣上會有相似的色彩分布，則在相鄰邊緣上，兩個碎片間的差異值和最小，以此作為評判標準來計算它們之間的匹配度。

對于彩色圖片，可取R,G,B色彩空間的矢量進行匹配計算，通過計算碎片間的匹配度大小來判斷它們在原始圖像中是否鄰接。用D代表碎片對之間的匹配度，對于碎片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)位置的匹配度。編號為i和j的碎片左右邊緣匹配程度(i左j右)用相同位置(m表示對應(yīng)的行數(shù))的灰度差的積累結(jié)果衡量，定義邊緣匹配函數(shù)為公式(1)。此值越小，說明匹配程度越好，吻合程度越好。

(1)

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

D(xi,xj,l)=

(2)

顯然，兩個碎片相鄰的可能性越大時，匹配度D就會越小。把每塊碎片與剩余的碎片依次做匹配計算，之后把求得的值放入碎片匹配值矩陣D(xi,xj,r)中，它的大小為N*N*4。因為匹配涉及的碎片沒有進行方向變換，所以第一層矩陣放入的是碎片xi第一邊和碎片xj第三邊的匹配值，第二層矩陣放入的是碎片xi第二邊和碎片xj第四邊的匹配值，第三層矩陣放入的是碎片xi第三邊和碎片xj第一邊的匹配值，第四層矩陣放入的是碎片xi第四邊和碎片xj第二邊的匹配值。

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

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

3.1 最小生成樹原理

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

(3)

因為T無回路且連接了所有節(jié)點，所以它必然是一棵樹，故稱之為最小生成樹[14]。

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

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

圖1 算法偽代碼

接下來對一幅圖像碎片進行復(fù)原。圖2顯示的是一幅像素數(shù)為800*600的圖像及其任意置亂的碎片，碎片的邊長像素數(shù)為40，數(shù)量為300塊。

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

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

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

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

在算法仿真過程中，采取中文算法和文獻[4]的算法對碎片圖像進行復(fù)原仿真并作出比較。文中使用CPU為2.20GHzIntel(R)Core(TM)T6670的計算機在MatlabR2013a的仿真平臺上進行編程實驗。

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

表1 文中算法運算性能分析

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

表2 算法性能比較

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

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

圖4 比較結(jié)果

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

5 結(jié)束語

文中提出了一種用于規(guī)則圖像碎片的快速復(fù)原算法。在算法實現(xiàn)中，運用了文獻[4]提出的基于邊緣色彩差異度的匹配算法，同時結(jié)合了圖論學(xué)中的最小生成樹原理用于復(fù)原框架的設(shè)計。由仿真實驗可知，文中算法對于大量規(guī)則圖像碎片可以進行準確復(fù)原，同時相比文獻[4]算法，準確度有了大幅度提升。在下一步的工作中，會根據(jù)實際應(yīng)用的需求，在匹配過程中，對存在照度突變或噪聲干擾的情況下如何對碎片精確匹配進行研究。同時，對方向錯亂的圖像碎片復(fù)原進行研究并進行算法實現(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] 朱 青.計算機算法與程序設(shè)計[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] 朱清新，楊 凡，鐘黔川.計算機算法設(shè)計與分析導(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

時間：2016-06-00

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

趙 林(1990-)，男，碩士研究生，研究方向為圖像與視頻分析；朱桂斌，教授，博士，研究方向為信息安全、圖像處理。

TP391

A

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

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