基于边界像素匹配的碎片拼接问题研究

邵春雨，胡方涛，程明辉，李厚彪

(电子科技大学 a. 光电信息学院； b.数学科学学院，成都 611731)

·学生实验园地·

基于边界像素匹配的碎片拼接问题研究

邵春雨a，胡方涛b，程明辉b，李厚彪b

(电子科技大学 a. 光电信息学院； b.数学科学学院，成都 611731)

文中针对碎纸机破碎纸片的双面文字拼接复原问题，以边界像素数据差值最小为优化目标，建立0-1规划模型，并设计了实现拼接复原的算法。与以往人工拼接不同，所设计算法采用分治思想将拼接过程分为横向和纵向，借助Matlab进行机器拼接，并利用边界像素匹配得到机器拼接规则。实验结果表明，该方法可以高效、准确地完成数量庞大的单/双面碎纸片的拼接。

双面文字; 0-1规划; 边界像素匹配; 分治; Matlab 软件

灰度使用黑色调表示物体,即以黑色为基准色，用不同饱和度的黑色来显示图像。根据黑-灰-白的连续变化，将灰度值量化为256个灰度级，灰度值的范围为0～255，表示亮度从深到浅，对应图像中的颜色为从黑到白[1-2]。像素是指基本原色素及其灰度的基本编码，像素和灰度具有紧密的联系。对于给定的图像，可以用Matlab中imread函数读入图片中的相关数据。

碎纸机碎纸后产生的矩形碎片形状相同，无法根据纸片的形状进行拼接，只能针对纸片图像内容寻找复原办法。目前，大部分采用传统的人工分辨方法，但这种方法很难将大量碎片拼接起来，并且费时较多。所以，需要用编程方法将纸片图像信息转化为像素数据进行机器拼接。

对于给定的来自同一页印刷文字文件的碎纸片，根据文字文件的印刷方式不同，分为单面印刷和双面印刷。双面文字文件被破碎切割后，正反面的不确定性增加了碎纸片的混乱程度，且碎片数据量增大了一倍，计算机发生误差的可能性增大，加大了碎纸片拼接复原的难度。

1 拼接流程

要实现碎片的拼接，需要根据一定的拼接流程来进行，而碎片的具体匹配将使用人工制定的拼接规则，整体的拼接流程如图1所示。

2 碎片拼接的数学模型

为使问题更具体，先考虑来自同一页印刷文件的19条长条碎片[3]，对其进行拼接复原。我们先考虑纸片只被纵切的情况，之后再将模型推广到既横切又纵切。

图1 拼接流程示意图

模型建立的步骤如下：首先，需要将图像信息进行数据化；然后，分析各边界颜色数据条件，数据化相邻关系；最后，构造纸片边界的拼接准则，从而找出符合条件的相邻碎片，完成拼接复原。

2.1 图像信息抽象成网格颜色数据

碎纸片中的图像信息需要转化成能够运用数学方法进行分析的数学数据。用网格均匀划分的方法将图像分成足够多个小块，使每个网格块内颜色单一，再统计出每一小块的颜色信息作为图像数据。

如图2所示，将每一碎纸片的纸面划分成无数个等大的网格，为形象显示划分过程，图中划分出的网格比较大，因此，很多网格中的颜色不唯一，即在一个网格内既有黑色又有白色。当划分的网格数目足够大时，可以使每一网格中只存在一种颜色，即不是黑色就是白色。因此，实际操作时，我们将网格数目取尽可能多。

图2 碎纸片的网格划分示意图

为达到图片拼接的目的，需要找到与其相邻的碎纸片，因此，我们关注的只是图2中边缘部分的网格颜色。观察碎纸条边缘的颜色变化规律，可以发现，通常情况下边界部分的网格颜色具有连续性，即在网格数目足够大的前提下，等高度的边界网格颜色是相同的。接下来，需要量化边界网格颜色，便于进行拼接设计分析。

经上分析，可知网格中的颜色分为黑和白，不妨引入0-1矩阵变量Rik和Ljk，分别用0和1表示黑色和白色信息。其中：

从上面两个公式可看出，Rik和Ljk分别表示左右边界的网格方块的颜色，且1代表黑色，0代表白色，且对于固定的纸片i与j，Rik和Ljk的值是确定的，即纸片内容确定时，边界网格块的颜色也是个确定值。

2.2 相邻关系的数学描述

若网格数目足够大，利用每个网格的颜色数据量化为图像信息的基础上，引入纸片间的相邻关系。利用一个0-1决策变量xij对相邻关系进行刻画[4]，具体来说，就是用xij表示两纸片是否相邻以及相邻时的左右关系。只要确定了xij的值，即得到具体的相邻拼接顺序，遍历每张纸片即可得到拼接复原纸片的编号顺序。

将相邻关系用数学语言描述的具体表达式为：

用这种表示方式的目的是：方便最终确定每条碎纸片的相邻纸片，不仅能将相邻关系描述出来，还能将两纸片的左右位置关系表示出来。

2.3 拼接规则的制定

下面以刻画相邻关系的xij为决策变量，先定义边界网格颜色差值，以此为基础制定最终的拼接规则。

2.3.1 边界网格颜色差值

作为拼接工作，我们关注的只是纸片边缘部分的网格颜色，用图像表示如图3所示。

图3 边界网格颜色对比图

图3所示的网格大小十分夸张，实际拼接网格中，划分极密，网格极小。另外，此拼接方式需要考虑的仅仅是边界上的图片内容，也即边界上网格的颜色，为简化分析，不考虑图3中阴影部分的网格颜色。

为了分析出两张相邻的碎纸片，需要使边界部分同高度网格的颜色尽可能相同，或使差异尽可能小。为此，引入边界网格颜色差值

(1)

式中：Rik和Ljk分别表示纸片的左右边界颜色信息；N表示网格划分的列数目，要求N足够大。为消除正负值的影响，用平方值体现这种颜色的差异性[4]。

2.3.2 基于优化的拼接规则

根据上面对边界网格颜色差异的定义，可以得到以下拼接规则：

(2)

式中：Rik和Ljk分别表示纸片的左右边界颜色信息；xij表示相邻关系；N表示网格划分的列数目且要求数目足够多。

拼接规则式(2)实质上是满足相邻关系的一个优化条件，按照上述条件寻找出相邻的纸片编号，从而得到各纸片间的相邻关系。

3 算法设计

设计的算法流程如下：

Step1：用imread读入所有19幅图片，保存为矩阵形式；

Step2：按列遍历所有矩阵的第一列，找到其值全为255(白)的一列，记为第一个矩阵(第一张纸片)；

Step3：遍历第一个矩阵的最后一列，记为a，与其他矩阵的第一列b，逐行求平方和，再相加,得c，找到最小的c，与之对应的矩阵即为第二个矩阵；

Step4：在剩下的矩阵中继续找第3个，一直到第19个；

Step 5：用imshow 读出完整图片。

计算机拼接结束后，需要进行人工观察，即人工干预，防止出现错位情况。一般这种带文字的错位情况用肉眼很容易判断出来。

4 算法求解结果

对于特定无规律的19张碎纸片，分别用1～19将其编号，将纵切碎片中英文数据读入计算机中，利用上述算法编程得到碎纸片拼接复原结果。程序如下：

A=[];B=[];F=[];A1=[];T=100000;

for i=0:9 %相素数据读入

name=[′00′,num2str(i),′.bmp′];

C=imread(name);

A=[A,double(C(:,1))];B=[B,double(C(:,72))];

end

for i=10:18

name=[′0′,num2str(i),′.bmp′];

C=imread(name);

A=[A,double(C(:,1))];B=[B,double(C(:,72))];

end %读入结束

n1=find(sum(A)==max(sum(A)));%寻找左初始图片

n2=find(sum(B)==max(sum(B)));%寻找右初始图片

for i=1:19 %拼接图片

for j=1:19

if sum(abs(A(:,j)-B(:,i)))

T=sum(abs(A(:,j)-B(:,i)));k=j;

end

end

F=[F,[i;k]];T=100000;

end

F1=F(1,:);F2=F(2,:);G=[n1];

for i=1:size(F')-1

G=[G,F2(find(F1==G(i)))];

end

G %显示拼接顺序并显示图像

for i=1:size(G')

if G(i)>10

name=[′0′,num2str(G(i)-1),′.bmp′];

C=imread(name);

else

name=[′00′,num2str(G(i)-1),′.bmp′];

C=imread(name);

end

A1=[A1,C];

end

imshow(A1)

用一张带有文字信息的特定A4纸张进行实验，获得的拼接顺序如表1所示。计算机编程计算后直接给出了正确的结果，不需要人工干预，显示出这种方法的优越性。

表1 纵切碎片复原编号顺序

5 横纵切纸片的模型推广

根据上述模型建立的方法，对于双面拼接问题其解决思路是相同的，但由于此时图片数据量增加一倍且正反面未知，任意两张碎片不一定能进行同面拼接，大大增加了模型建立和求解的难度。

将横向边界颜色差值和纵向边界颜色差值综合考虑，得到复合差值。由于一张纸片存在两面，计算出两面的复合差值并求和得到最终的优化条件，差值越小，相邻的可能性就越大。优化得到最小值对应的纸片作为相邻纸片，按纸片编号顺序依次向下进行排列。

如图4所示，假设A为待拼接纸面的头部纸片的某一面，需要找到其相邻纸片。取第一张纸片的两面000a和000b分别与A的每一面进行匹配，如与000a面进行匹配，同样分为横纵两个边界方向，即让A面的下边界颜色值和000a面的上边界颜色值进行差值计算，让A面的右边界颜色值和000a面的左边界颜色值进行差值计算，将两方向的差值求和就得到了A面纸片和000a面的颜色差值匹配结果。同理，对000b面进行操作，将两面差值结果求和就得到了A面纸片对此张双面碎纸片的最终匹配差值。依次遍历剩余的纸片，找到最小值对应的纸片，即为相邻纸片。

图4 双面拼接规则示意图

将上述拼接规则用数学语言描述为：

6 结束语

本文利用算法编程进行碎纸片的机器拼接，全过程没有手动操作，节约了大量时间，降低了工作量，并使得拼接过程较为高效、准确。拼接过程采用了分治的思想，先横拼再纵拼并辅以人工干预，可确保结果的准确性，减少计算机出错的可能性，同时降低人工干预的工作量。另外，采用双向同时进行(即首尾同时相对拼接)的方式，可提高计算机的容错率，降低人工干预的复杂度。本文介绍的模型思路明了，算法简单实用，具有很强的可行性，在警察办案、重要文件复原等方面有很好的实用价值。

关于碎纸片的拼接复原问题，国内外已进行了大量研究[5-9]。它们各有不同，我们将继续予以关注。

致谢：衷心感谢电子科技大学数学科学学院何国良老师在数学建模竞赛培训中给予的无私帮助和鼓励。

[1]灰度.百度百科[EB/OL].(2013-11-07)[2014-4-15].http://baike.baidu.com/link?url=eDoykgmWxgmzp2xi1nbTyrGx3Hfb5-YgL-MgsvZ9yTH HMCUsi6SBNpurQGCNb0As.

[2]冈萨雷斯.数字图像处理(Matlab版)[M].3版.北京：电子工业出版社, 2005:60-72.

[3]全国大学生数学建模组委会.2013高教社杯全国大学生数学建模竞赛B题——碎纸片的拼接复原[EB/OL].(2013-09-13)[2014-4-15].http://www.mcm.edu.cn/html_cn/block/c61dfec317d7a5bd9b 2b8efed81c8af3.html.

[4]姜启源，谢金星.数学模型[M].4版.北京：高等教育出版社，2010: 275-288.

[5]Edson Justino, Luiz S Oliveira, Cinthia Freitas. Reconstructing shredded documents through feature matching[J]. Forensic Science International，2006，160：140-147.

[6]Leitao H C G , Stolfi J. A multi-scale method for the reassembly of two-dimensional fragmented objects[J]. IEEE Trans. Pattern Anal. Mach. Intel，2002(24):1239-1251.

[7]Yao F H , Shao G F. A shape and image merging technique to solve jigsaw puzzles[J].Pattern Recog.Lett.2003(24)：1819-1835.

[8]潘荣江.计算机辅助文物复原中的若干问题研究[D].济南：山东大学,2005:15-27.

[9]潘荣江,孟祥旭,屠长河.一种基于LCS的物体碎片自动拼接方法[J].计算机学报，2005(3):351-356.

Research on the Problem of Shredded Document Reconstruction Based on Matching of Pixels for Boundary

SHAO Chunyua，HU Fangtaob，CHENG Minghuib，LI Houbiaob

(a.School of Optoelectronic Information; b. School of Mathematics Sciences, University of Electronic Science and Technology of China, Chengdu 610054, China)

Based on minimizing the difference value between boundary pixel data, a 0-1 programming model and corresponding algorithm are established for the doubled-sided shredded document reconstruction problem. The designed algorithm is divided into vertical and horizontal reconstruction. Then utilizing the matching of pixels for boundary rule, we obtained the reconstruction of shredded documents. As it is different from the method of artificial recovery we used before, computer becomes the main labor force with Matlab. It turned out that this method of reconstruction can be accomplished efficiently and precisely.

doubled-sided shredded document; 0-1 programming model; divide and conquer; matching of pixels for boundary; Matlab software

2014-04-22；修改日期: 2014-05-13

国家自然科学基金资助项目(11101071);电子科技大学教学研究基金资助项目(2013XJYSL026)。

邵春雨(1994-),女，本科在读，专业方向：电子科学与技术(光电工程与光通信)专业。

李厚彪(1976-),男，副教授，主要从事科学计算与数值代数的教学和研究工作。

O151.2

A

10.3969/j.issn.1672-4550.2015.02.070