碎纸片拼接复原的数学模型与实现.doc

碎纸片拼接复原的数学模型与实现摘 要 碎纸拼接,就是利用计算机将碎片复原.如果碎片的数量过大,手工拼接会费时费力.本文利用MATLAB实现碎片自动拼接,解决了如何复原一个纵切印刷文字文件破碎纸片,如何复原一个即纵切又横切的印刷文字文件破碎纸片,如何复原一个即纵切又横切的双面印刷文字文件破碎纸片.关键词 碎纸片;像素;灰度;邻接; MATLAB;复原.中图分类号 0141.41Mathematical model stitching scraps of paper and achieve recovery（School of Mathematics and Statistics，Hexi University，Zhangye，Gansu，734000）Abstract:Shredding splicing, is to use the computer to recover the debris. If the number of fragments is too large, hand-stitching dues when consuming. In this paper, using Matlab automatic mosaic fragments, Addresses how to recover a broken piece of paper slitting printing text documents, How to recover a longitudinal and transverse to that file fragmentation paper printed text, How to recover a longitudinal and cross that double-sided printed paper text file fragmentation.Keywords:Scraps of paper; Pixel; Grayscale; Adjacency; Matlab; Recovery.1 问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用.传统上,拼接复原工作需由人工完成,准确率较高,但效率很低.特别是当碎片数量巨大,人工拼接很难在短时间内完成任务.随着计算机技术的发展,人们试图开发碎纸片的自动拼接技术,以提高拼接复原效率.现给出下列三种情形(1)对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切）,建立碎纸片拼接复原模型和算法,如针对给出的同一页中文文件（图片集1）的碎片数据进行拼接复原. (2)对于碎纸机既纵切又横切的情形,建立碎纸片拼接复原模型和算法,如针对给出的同一页中文文件（图片集2）的碎片数据进行拼接复原.(3)上述所给碎片数据均为单面打印文件,从现实情形出发,还可能有双面打印文件的碎纸片拼接复原问题需要解决.现给出一页英文印刷文字双面打印文件（图片集3）的碎片数据.图片文件说明：(1)每一图片集为同一页纸的碎片数据.(2)图片集1为纵切碎片数据,每页纸被切为19条碎片（随机编号为00-19）.(3)图片集2为纵横切碎片数据,每页纸被切为个碎片（随机编号为000-208）.(4)图片集3为纵横切碎片数据,每页纸被切为个碎片,每个碎片有正反两面.该图片集中每一碎片对应两个文件,共有个文件,例如,第一个碎片的两面分别对应文件,.2 问题的分析2.1 问题的背景在文物修复、司法鉴定等领域普遍存在着碎片拼接问题,但目前碎片拼接几乎是以手工的方式完成的.当碎片数量增大到一定程度时,如果任然依靠手工完成,不但耗费大量的人力、物力,而且还可能对物件造成一定的损坏.很多碎片拼接问题都可以归结为或近似为二维碎片的拼接问题,碎片拼接时其中的典型问题.对二维碎片自动拼接的问题的研究,具有广阔的应用前景.有了碎片拼接的一般数学模型和方法,碎片拼接的数据就可以甩给计算机了.本文主要讨论的问题是如何利用计算机实现图片的拼接问题.教计算机如何拼图,就是要教会计算机拼图的规则,让计算机知道什么样的拼接时好的,什么样的拼接时坏的,而这其中最难办的,就是和计算机沟通.在计算机的眼中,万物皆数.或许当计算机睁开眼睛,眼前全是浮动的0和1.要想让计算机知道什么是颜色,什么是轮廓,什么是纹理特征,不能指望感官,只能通过数学描述颜色,一般需要用数学统计.数学知识丰富的人,跟计算机的沟通会很通畅.我们用轮廓,颜色,纹理特征来描述碎片,自认为已经面面俱到.但是事实往往是另一种情况：还有其他的碎片特征是我们肉眼看不到的,或者是尽管我们看到了却没有意识到.就像在处理信号信息时,经过Fouier变换,我们似乎得到了新的信息,但实际上,这些信息一直都在,只不过是隐藏了起来.在碎片中,也有这类似的变换,它使我们看到了碎片的另一种样子,使我们超越颜色,轮廓,纹理这些概念,重新认识它.人们在碎纸拼接过程中,主要还是依靠感官经验.（这没什么不好,比较实用）仔细回忆一下自己拼图时的情景,是如何判断的,就会发现我们用到了下面的规则(1)如果轮廓相似,那么这两个碎片就是在一起的；(2)如果颜色相似,那么这两个碎片就是在一起的；(3)如果轮廓特征相似,那么这两个碎片就是在一起的；(4)如果所含信息连贯,那么这两个碎片就是在一起的.目前,碎片的拼接技术十有八九是基于上述想法,这就使得有关碎片拼接的论文,看上去大同小异,不同之处只在对于颜色,轮廓和纹理特征用了不同的数学解释,或在操作方面用了不同的规则和技巧.就拿颜色来说：可以用RGB(Red Green Blue)颜色空间去描述颜色,也可以用Hsl(Hue saturation Intensity)颜色空间去描述颜色,还可以用Hsv(Hue saturation Value)颜色空间去描述颜色.选择不同的描述方式,往往会得到不同的结果.一个观点认为：“GRB空间是一种非均匀的彩色空间,并存在着亮度与色度之间不独立的缺陷.相比之下,HIS颜色空间比较接近人对颜色的视觉感知,比较效果更好.最后HSV比HIS更胜一筹,是效果最好的.”总之观察事物的角度不同,结果也会不同.2.2印刷体文字碎片的拼接思路对于情形中给出定的碎片全是用碎纸机破碎的文字碎片,且每片大小相同,所以我们不必考虑碎片的形状.每一碎片的上下左右边缘相对于页面上下左右的边缘时一致的,从而两个碎片只有左右拼接和上下拼接两种方式.另外,考虑到印刷文字文件的版面特征,我们还可以判断出那些其边缘碎片.例如一旦知道左边缘碎片,就可以向右搜索确定其右边连接的碎片.印刷体文字一般只是黑色文字,白色纸面,所以我们就用灰度图来识别碎片特征.这一过程可以在Matlab中实现.Matlab把一副灰度图像存储为一个数据矩阵,该矩阵中的元素分别代表了图像中的像素.所以在它看来所有的图片都是矩阵.读入一个的图像,就会得到一个的矩阵,其中存放着每一个像素的灰度值.有了碎片的灰度矩阵我们就可以比较两碎片两边的灰度值,进而判断两碎片是否相连,大体思路如图1图1读入图片建立图片的灰度识别矩阵比较图片左右或上下的相似情况得出结果人工干预唯一不唯一3 模型假设(1) 假设碎片模型为理想模型,碎片表面光滑平整无磨损且厚度为零；(2) 假设在切割过程中除边界外,其他切割线都切割文字；(3) 假设每张碎纸片的大小一致；(4) 假设碎纸机切的纸片无损坏；(5) 假设碎图片中的文字符字体格式相同,英文字符字体格式相同；(6) 假设页面文件的四边都有一定的也边距,且页边距大于文件中文本的行距.4 模型的建立与碎片复原4.1情形1的模型建立 4.1.1碎片识别假设一页中文文件沿纵向切割成条,这里的.对于其中任意一条碎片,采用纵横分割的办法,分成 块小区域,这样的小区域可以完成和图片的像素点对应起来,即可以用碎片的像素点作为碎片的分割方式,通过查看每幅图的属性,我们知道每幅图都是像素的图片因此不妨假设每一碎片被分割成个小区域.每个小区域的识别特征,则这块的识别特征记为是一个的矩阵,称为这一条的识别矩阵.上述过程可以在Matlab中利用读图命令实现,结果为该条的灰度像素矩阵,亦前述的识别矩阵.它的值处于0到255之间,0表示黑色,255表示白色,位于0到255之间的值为表示该小快的灰度,越接近0颜色越接近黑色,越接近255颜色越接近白色.4.1.2复原模型由假设6,印刷文字的页面特征为上、下、左、右边缘留有一定的空白,因此处于做边缘的碎片.其识别矩阵中的前几列的特征数基本相同或完全相同,处于右边缘的碎片,其识别矩阵中的后几列的特征数基本相同或完全相同.利用这一方法,我们可以从所有碎片中首先挑出待复原页面的最左和最右的两条,分别称为页面左边和页面右边.上述过程有时可以人工实现.事实上我们观察图片集1的所有图片,便会发现只有“008.bmp”这一副图是左边文字处于同一竖线上,且每行文字左边都留有一定的空白,因此可以断定它为页面最左边的一条碎片.也只有“006.bmp”这一副图是右边文字处于同一竖线上,且每行文字右边都留有一定的空白,因此可以断定它为页面最右边的一条碎片.当然,用所建的模型也可以直接识别页面左边和页面右边.仅需考虑19条碎片的19个识别矩阵中从第一列开始统计各列中数值全为255的列的个数,含有255个数最多的列为所对应的碎片即为最左边的一条.因此,把识别矩阵按列分快成的分快矩阵其中为矩阵的第列,它是含有1980个元素的列向量.令 则表示第副中的第列元素中255这个元素的分量个数.将所有的图片左边36列、右边36列所以对应的分别放在一起,做成两个矩阵,即,统计中各行元素中数值为1980的元素个数,得到如下两个向量, 则中最大元素所对应的行号分别为页面左边、页面右边的碎片序号.由于左右相接的两幅图片,左边图片的右边和右边图片的左边具有结合关系,所以当我们确定了左边以后,便可以以左边碎片的识别矩阵中最后一列为比较基础,依次判断它与其余图片右边的邻接程度,若邻接程度最大,则断定它与左边是相接的.若图片不唯一,则采用人工干预.由于文字的比划具有连贯性,因此一个文字如果被切开,其两边的灰度值是相近的.另外,如果图片两端被切开出是空白的,则两边灰度值相同.这样,一个页面文件在切开出两边灰度值差值的绝对值之和应是最小的.下面建立如下判断邻接关系的模型设取出任意两幅图片分别为第幅图和第幅图,则第幅图的右边和第幅图的左边邻接成程度只与第幅图第72列和第幅图的第1列着两个向量有关.其邻接程度记为,可以表示为和的绝对值之和,即为因此,一旦确定了页面左边和页面右边,我们可以建立以下复原模型设页面左边碎片为第幅图片,这时其识别矩阵为的第72列,记为.而其他18幅图片的左边识别特征为其识别矩阵的第一列,依次为 (1) (2)若,说明第幅图的左边和第幅图片的右边是邻接的,说明除了第幅图以外,其余各图的左边和第幅图的右边不具有邻接关系或邻接程度较低.每运行一次上面的模型,则确定一幅图的邻接关系,从而为确定的碎片数减少一,经过有限步以后,就可以将文件页面复原.上述复原模型的算法流程如下图2否读入图片,得到像素灰度值,构建识别矩阵判断页面的左边、右边从左边（右边）开始判断邻接关系完成复原人工干预人工干预从另一边判断未复原标记为识别是图24.2情形2的模型建立4.2.1碎片识别假设一页文件沿纵向切割成条,沿横向切割成条,这样的一页文件被切割成的碎片,根据图片集2中的数据,不妨设,对于其中任意一块碎片,采用纵横分割的办法,分成的小区域,这样的小区域可以完全和图片的像素点对应起来,即可以用碎片的像素点作为碎片的分割方式.通过查看每幅图片的属性,我们获知每幅图片都是像素的图片.假设每一小块的识别特征记为是一个矩阵,称为这一块碎片的识别矩阵.4.2.2复原模型由假设6,印刷文字的页面特征为上、下、左、右边缘留有一定的空白,因此处于左边缘的碎片其识别矩阵中的前几列的特征数基本相同或完全相同,处于右边缘的碎片其识别矩阵中的后几列的特征数基本相同或完全相同. 处于上边缘的碎片其识别矩阵中的前几行的特征数基本相同或完全相同. 处于下边缘的碎片其识别矩阵中的后几行的特征数基本相同或完全相同.利用这一方法,我们可以从所有碎片中首先挑出待复原页面的可能位于四边缘的碎片。以识别页面左边缘为例，建立如下复原方法识别页面左边碎片时，仅需考虑209块碎片的209个识别矩阵中从第一列开始到某列数值全为255的碎片，得到图片集2中图片的左边界.找出与左边界11张图片同行的其余碎纸图片.编程筛选出每行的图片,利用问题一中的方法进行计算机拼接,但由于拼接存在一定的误差,所以部分图片拼接不完整正确,在此情况之下进行人工干预,观察图片内容,根据内容手动移动碎纸图片进行拼接.利用第一问求左边界的图片的思想,运行程序可以找到图片集2中位于第一列中的图片共有11张,分别为049图,061图,168图,038图,071图,014图,094图,125图,029图,007图,089图.恰好符合矩阵的格式要求.即说明这11张图片为整体图片第一列的所有组成部分.用Matlab程序,以已经确定的第一列的11张图片为标准分为11类,分别找出与第一列11个图空白行位置相近似的图片归为一类,例如与007图和038图相近的图为与图007（标号为8）空白位置相近的图片有22个,标号为8115334654576971729094127138139154159167175176197209与图038（标号为39）空白位置相近的图片有22个,标号为3991015252636477275828990104106123131149162168190194每一张碎纸片的识别矩阵进行二值化处理,也就是值小于127的将像素值设为0(黑色),值大于等于127的像素值设为255(白色).该方法的好处是计算量少速度快.缺点是阈值为127只是取了一个中间值,其次完全不考虑图像的像素分布情况与像素值特征.搜索每一张碎纸片转化的二值化矩阵 的每行,若存在黑色即矩阵该行中存在数值1,则将该行全部赋值为1,若这一行不存在黑即此行元素全为0,则将该行全部赋值为0,这样将209张碎纸片做出新的二值化矩阵,之后同情形1的求解过程做边缘匹配,做出矩阵大小边缘匹配度矩阵,元素为处理后的碎纸片边缘二值化矩阵的第二列与处理后的碎纸片边缘二值化矩阵第一列的边缘匹配度,匹配度高则说明碎纸片的文字信息处于同一水平位置.上述复原模型的算法流程如下图3将碎片转化为数字矩阵阵找出左边界中的图片(共11张)找到与每幅边界图片同行的剩余的图片选取所有行中图片数量最少的一行拼接确定拼接行的图片顺序,并在其它行删除拼接不唯一,采用人工干预重复上述过程,直至拼接完成图3当上述拼接方法不唯一时，我们可以换个角度再进行拼接，作为补充.例如由上述可知编号为142号的碎片为右上角一块，因此，我们便从这个碎片出发，先左侧递推，得到和它左边缘相邻的碎片编号为189，再从189出发，也向左递推，但是和189邻接的碎片编号是66和92中的某一块，因此暂时中止.然后从142号向下递推，得到和它相接的碎片编号为19，在从19向下递推，也可以从上述推出的碎片中向左搜索.与某一张碎片拼接不唯一的碎片数量较少时可以采用观察文字特征的方法确定其邻接的碎片.其邻接效果图如下图4人工干预91188141036人工干预74018图4搜索搜索搜索4.3情形3的模型建立4.3.1碎片识别情形3的识别方法同情形2,假设一页文件沿纵向切割成条,沿横向切割成条,这样的一页文件被切割成的碎片,根据图片集3中的数据,设,对于其中任意一块碎片,采用纵横分割的办法,分成的小区域,这样的小区域可以完全和图片的像素点对应起来,即可以用碎片的像素点作为碎片的分割方式.通过查看每幅图片的属性,我们获知每幅图片都是像素的图片.假设每一小块的识别特征记为 ,其中和是图片的两个面的编号,是两个矩阵,称为这一块碎片的识别矩阵.4.3.2复原模型同情形2一样,印刷文字的页面特征为上、下、左、右边缘留有一定的空白,利用这一特征,我们可以从所有碎片中首先挑出待复原页面的可能位于四边缘的碎片.对于有双面打印的碎纸片,根据边缘留白情况,可筛选出22个左边界,并根据字母中点所在行的行高分为11类.并根据行高对其他图片进行筛选分类.引入人工干预,完成效果拼接.对于双面打印的英文印刷碎片(1)将碎纸图片转化为的数字矩阵(2)确定图片集3中所有碎纸图片中的边界图片,依据为纸张的边界留白更多这一准则,计算每个矩阵对应列向量和,形成行向量,可将所得行向量元素一次达到最大值的向量所在矩阵对应的碎纸片确定为左边界.(3)又由于所有碎纸图片分为正反两面,每页纸被切为个碎片,故经过筛选之后共得到边界图片22张.其中有11张边界图片为反面的右边界.则这22张碎纸图片可分为11类.每一类的分类标准为两张碎纸图片中字母所在行灰度吻合度最高.依此标准得到的这11类边界分布.(4)每一类的边界有正反两个边界,依据这两张边界图片中字母所占行灰度,在其他剩余碎纸图片中寻找与之灰度吻合参数最小的作为同一行.由于英文字母本身占格位置的特殊性,误差较汉字来说要大.在进行同行碎纸图片拼接时准确率不高.此时,需引入大量的人工干预来进行拼接工作. 上述复原模型的算法流程如下图5 将碎片转化为数字矩阵找出左边界中图片(共22张),并将图片分类(共11类)由所在行的两张图片筛选出所在行的其他碎片将每行碎片利用程序进行拼接完成拼接引入人工干预,同时考虑正反两面引入人工干预,同时考虑正反两面不唯一图55 模型评价缺点假设条件很多,这就直接导致与实际情况仍有一定的差距,因此导致一系列计算数据误差较大.由于知识面不够广,一些改进思路无法用程序实现,对于情形3的复杂性,只是在前两种情况的程序基础上做了一些改动.优点情形1模型,简单、易操作.适用于单张碎片所含文字信息量大的图片拼接复原.情形2模型,对于碎片上信息量较少,但数量庞大的情况,以减少比对范围来达到理想拼接复原效果,且效率较高. 情形3模型，较好的优化人工干预次数,在一定程度上降低了拼接的不唯一性，减少了人工拼接的图片数量，拼接效率有所提高.参 考 文 献1朱德通,最优化模型与实验M,上海:同济大学出版社,2003.42夏少刚,运筹学经济优化方法与模型的M,北京:清华大学出版社,2005.93阮晓青,周义仓,数学建模引论M,北京:高等教育出版社,2005.74熊启才,数学建模方法及应用M,重庆:重庆大学出版社,2005,35宋兆基,徐流美,MATLAB6.5在科学计算中的应用M,北京:清华大学出版社,2005.16张志勇,杨祖樱,MTLAB教程R2012aM,北京:北京航空航天大学出版社,2010.87韩煌,基于颜色和纹理特征的计算机自动拼接研究D,首都师范大学,20088周振环,基于角点特征的形状识别J,计算机工程,2007,33(6)：22-26附件情形1的程序代码clc;clear;close;mum=19;b=;for i=1:mum; bi=(d:fujian1,mum2str(i-1,.bmp);endMax1=0;1=0for i=1:19if(maxsum(double(bi(:,1)=255)Max1=sum(double(bi(:,1)=255)1=iendendw=1-1for v=1:18for j=1:19L(j)=sum(abs(double(b1(:,72)-double(bj(:,1)150);endmax=0;for z=1:19if(maxL(z)max=L(z)1=zendendw=w,1-1ends=1.+wimshow(cell2mat(b(s)情形2的程序代码clcclearp=cell(1,209);for i=1:10 imageName=strcat(d:fujian200,num2str(i-1),. bmp ); pi = imread(imageName);endfor i=11:100 imageName=strcat(d:fujian 20,num2str(i-1),. bmp ); pi=imread(imageName);endfor i=101:209 imageName=strcat(d:fujian2,num2str(i-1),. bmp ); pi=imread(imageName);endAnswer=1:19;20:38;39:57;58:76;77:95;96:114;115:133;134:152;. 153:171;172:190;191:209 %定义下标变量sump=;for i=1:207sump(i)=199999-(sum(pi(:,1)+sum(pi(:,2)+sum(pi(:,3)+sum(pi(:,4);ends,firstLine=sort(sump);disp(第一列的图片是：)FL=firstLine(1:11); %FL表示第一列元素,共11个及11大类std=255*72; %一个作为空行标准的数