碎纸片的拼接复原分析(最终)

1、基于多耦合规则的人机交互拼接模型摘要随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。本题就是求解破碎文件自动拼接问题，实际上就是通过数字处理技术将碎纸信息转化成计算机可以识别的数字图像信息，然后利用计算机进行相应的处理从而实现对这些碎纸片的全自动或半自动拼接还原。题目共分为三个问题，第一个问题是对同一页单面印刷文字文件仅纵切的碎纸片进行拼接复原。第二个问题是对同一页单面印刷文字文件既纵切又横切的碎纸片进行拼接复原。第三个问题是对同一页双面打印文件既纵切又横切的碎纸片拼接复原问题。前两个问题的文件又分为中英文两种情况。三个问题由简到难，层层深入。 在求解问题过程中，首

2、先利用图论概念与定义描述了图片的拼接问题，将问题转化为最优树寻找问题。根据对中、英字符的分析，总结出中、英字符在书写上的异同，分别建立基线耦合、字宽耦合、边缘耦合、字符耦合、双边耦合、三边耦合等六种耦合拼接准则，尽量使得每一块碎片都有多种可用的耦合拼接方式。将耦合准则根据关联程度进行优先级排序，每一块碎片的信息依次按照耦合准则优先级进行量化，从而多方式量化每一块碎片之间拼接的耦合程度，进而实现了碎片的自动最优拼接。 本题所建立的耦合准则拼接算法只需要随机选取一块碎片作为种子，经过不同耦合方式的筛选，可找到与之某一边具有较高耦合度的另一块碎片，拼接成为一块具有较大可信度的图像，再通过人工识别，判

3、断所得的图片是否正确，并建立确定拼接集和排除拼接集，实现拼接图像的进化，再与用户交互。对于碎片拼接过程的提出了交互审查式、人机交互式和混合式三种模式，并建立了包括拼接模式、拼接识别、拼接控制、信息显示等多种用户指令在内的指令库，即可通过简单的人工指令对程序进行控制，进而利用计算机对碎片进行正确的复原。 利用耦合准则拼接算法及人机交互过程实现了碎片复原过程的简化。且本题所建立的模型可广泛应用与解决一维、二维、双面等问题。该计算过程具有灵活度高、交互性强、时间复杂度低等特点。关键词：图像复原；最优数；最优树；多耦合准则；人机交互。一、 问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报

4、获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：1. 对于给定的来自同一页印刷文字文件的碎纸机以纵切方式破碎纸片，建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件

5、的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果以图片形式及表格形式表达。二、 问题分析被切碎的原纸张为打印文档，故纸张上的字符写法、文字大小、行间距等相同，且排列规则，被碎纸机切碎的碎片的大小、形状、像素相同。从而使得根据字符模式进行识别这一方案可行。根据题目要求，将碎纸机切碎的碎纸进

6、行拼接复原。在本题中，利用MATLAB的imread函数可对题目所给出的图片进行初步处理，将图片的像素参数转化为矩阵排列。由此可找到图像中具体某一点所对应的坐标，由此可以延伸到对具体一条线或局部图像的位置的判定以及某两边缘匹配度高低的计算。对碎片的大致分布位置有一定判定后，再根据中英文字符的宽度、高度等区别，分别用不同的耦合规则进行进一步的拼接。针对问题一，根据题目已给出的附录一和附录二，其中的19张碎片的图片像素为，由此可先根据像素点的变化趋势，进行人工操作，找出最左与最右的碎片，再利用MATLAB对由图片得到的矩阵信息进行进一步处理，得出每一张图片的左、右边缘的像素点的矩阵，根据不同的耦合

7、规则进行拼接，得出耦合矩阵，由此将碎片拼接完成。针对问题二，附录三和附录四均有209张大小、形状相同，像素均为的碎片。先任意取一碎纸片，利用MATLAB对图像进行处理后，根据不同的耦合规则，从剩余的208张碎片中进行筛选，寻找出分别与该纸片四个方向匹配度最高的四张纸片。重复上述操作，将209张纸片进行一一匹配，最终可得出关于四个方向的拼接耦合矩阵，由此可将纸片复原。三、 基本假设和符号说明3.1基本假设1、原纸张无缺损等被破坏现象；2、原纸张内字符大小、字体相同；3、由碎纸机切碎的纸片上都有字符，无空白纸片；4、由碎纸机切碎的纸片的大小形状完全相同；5、被切碎的纸片无缺漏，数量总和满足理论碎纸

8、机碎纸数量。3.2符号说明符号符号说明符号符号说明左零边基线耦合矩阵右零边字宽耦合矩阵任意一张碎纸片：块边缘耦合矩阵拼接的方向字符耦合矩阵的基线位置双边耦合矩阵汉字字宽三边耦合矩阵汉字字高左边缘字符的宽度像素参数转换矩阵右边缘字符的宽度拼接耦合矩阵上边缘字符的宽度判断矩阵下边缘字符的 宽度图生成树类型名称说明模式指令set module设置模式拼接识别指令enter输入到确定集try不确定是否满足deny输入到排除集deny针对审查法，一次性输入多个到确定集拼接控制指令set(i,j,p)在拼图（i,j）位置放入图片pcancel(i,j)将拼图（i,j）位置图片取消show(i,j)显示拼图

9、（i,j）位置图片流程控制指令backward将操作向后退一步forward将操作向前进一步finish结束操作loop循环操作四、模型的建立与求解4.1模型定义1、块：每一碎纸片称为块，记为。2、基线：在英文中为英语字母书写四线三格的第三条线，在汉语中为字符的最底边3、零边：文件的页面最左边为左零边，文件的页面最右边为右零边4、拼接：对于给定的来自同一页印刷文字文件的碎纸机破碎纸片张，任取一张碎纸片，与它相异的碎纸片为。若与拼接，根据碎纸片的二维形状，在四个方向上进行拼接，作如下定义:与左拼接 :与右拼接:与上拼接 :与下拼接图4-1 碎片拼接方式若拼接与，有，则与为同种拼接。5、块与拼接的

10、关系：若存在拼接，则称与包含于，记为。6、块与图的拼接：一个最优拼接块即一个图，块与图的拼接存在于块与最优拼接块之间，则块与最优拼接块所形成图的外边缘进行拼接。7、拼接中的图论：将块拼接成图像最关键的是确定块与块之间的相对位置。利用图论将块的拼接问题转化为图的连通性问题，一个图是一个序偶，记为,其中：（1），为顶点，称为顶点集，每一个拼接视为顶点。（2）为边集，若两个拼接能够构成邻接，则它们之间存在一条边。若存在两个拼接组合与均是拼接耦合，分别记为点，且与邻接，则可以构成一条边，记为，则整个邻接组合记为 。这样就可以将块的拼接耦合转化为图的连通性。块的连续拼接将得到的连通子图，即的每一个连通子

11、图对应块的连续拼接集。无环的连通子图可以确定唯一的拼接图像，且该图像是连续的。每一种块的拼接方式都对应得到一个唯一的顶点子集。对于来自同一印刷文件的碎纸片产生的所有拼接的可能组成拼接全集。拼接全集则可转化为，顶点集。顶点两两组合则可以构成边，所有边构成边集。块的相对位置的拼接集是拼接全集的子集，块的相对位置的拼接集是的子集。碎纸片拼接复原的过程类似于得到的一颗生成树。碎纸片拼接复原过程是先选取一块作为根结点，从它出发引出树枝，的每个树枝赋予权值，每次选取该方向上权值最大的树枝，即在拼接过程中对于该块各个方向上会去寻找与它耦合度最高的块进行拼接，如此进行下去，直到得到权重最大的生成树为止，同样如

12、此循环往复地拼接下去，则将会得到理想中的复原图。但在实际中若按此方法进行操作，得到的复原图像并不是那么理想。在算法实现中是想通过计算机一次性得到结果，但是存在多种误差导致产生的结果不是标准的复原图。所以，在后续复原过程中加入了人工参与，使得复原图更加准确。8、拼接耦合:如果采用某种拼接规则对两张碎纸片进行拼接，若在该规则下使得拼接合理，则称该拼接是耦合的。9、拼接耦合矩阵：任意的两张碎纸片在方向上的进行拼接得到的矩阵， 10、邻接：设两个拼接耦合的拼接组合，如果且或者，则称与邻接。11、判断集合（确定集、排除集）：在利用某种拼接规则对信息进行处理后，得到一个拼接图形，用户进行人工识别，正确的拼

13、接组合放入确定集，表示该组合拼接耦合，不正确的拼接组合放入排除集，表示该组合不合理。放入排除集的组合将在后续的图像拼接中不会出现。用一个四维数组表示，其中表示第1张图片，表示第2张图片，表示相对于的拼接方向，表示状态，可取1，-1两个值，当取1时，表示为确定集，当取-1，表示为排除集。12、耦合规则：12.1基线规则 基线规则是其它所有耦合规则的基础。 借助MATLAB可轻易得出每一块碎片的所有基线。将所有的图片利用MATLAB进行处理后，从中任取一块碎片设为，并得到其所有的基线，将其基线所在位置设为，如下图所示： 图4-2 中文基线 而在对英文碎片选取时，由于j、p、q、y等英文字母与其他英

14、文字母相比，下方会有一段突出，因此对于英文碎片的选取法则略异与中文选取法则。如下图所示：图4-3 英文基线 先将英文碎片沿竖直方向均分为两块或三块（图4-3以两块为例）。将分得的每一块进行比较，不难看出第一块有三条基线，第二块由四条基线，而第二块的编号为1、2、3的基线恰好与第一块编号为1、2、3的基线的位置相重合，故第二块中编号为4的基线略去。由此我们可以得出，该图片的基线只有三条。找出每一块碎片的每一条基线后，根据MATLAB转换图片信息所得到的的矩阵信息确定该图中每一条基线的大致位置。从所有的碎片中任意选取两块进行拼接，拼接好后对他们的基线位置进行判定，看两碎片的基线之间是否存在一定的关

15、系：1、若是两碎片的基线位置相同，则可判断出两碎片的位置为同行，即为左右拼接（如图4-4）；2、若是两碎片的上下两基线之间的差值为行高的整数倍，则可判断出两碎片的位置为同列，即为上下拼接（如图4-5）。 图4-4 任意两碎片左右拼接 图4-5 任意两碎片上下拼接如图（4-4）所示，若碎纸片进行左拼接（右拼接类似），拼接耦合有如下关系式：；如图（4-5）所示，若碎纸片进行下拼接（上拼接类似），拼接耦合有如下关系式：。根据基线规则可对每一块碎片的基线的参数与其他碎片的基线参数相匹配，可得出基线耦合矩阵，从而可对对碎纸片的位置进行大致划分。12.2字宽规则我们可以针对汉字形状较为规则这一特点建立字宽

16、规则，即算出每一个字的宽度和，为后续模型做准备。 其算法流程图如图4-6所示：图4-6 字宽规则流程图 通过字宽规则，可以对汉字的左右与上下进行拼接。（详细字宽规则见附录六）。12.3边缘规则利用MATLAB的imread函数，可将图片的像素参数转换为矩阵，n为碎纸片数。根据汉字与英文字母的笔画书写规律可大致判断出，相邻碎片的边缘的像素大致相同。因此可以将得出的矩阵进行简化，即只选取该矩阵的四个边，分别得到四个子矩阵，设为，d代表了碎纸片可拼接的四种方式，对于每种拼接方式，如果任取一张碎纸片，一一与其余的碎纸片进行拼接，可以得到四个的边缘耦合矩阵。根据边缘耦合矩阵，可以选出与碎纸片四个边拼接的

17、最佳拼接组合。12.4字符规则对于英文字母，不同的字母有不同的宽度与高度，因此需要对英文字母的拼接建立一个字符规则。首先对52个字母的宽度与高度进行一一统计。其次将图片中的被切碎的字母按照基线规则进行筛选，再将筛选出来的碎片的左右边框两两拼接，拼接出来得到的字母与之前统计的52个字符进行一一比对，看是否有相匹配的字符，若有相匹配的，则证明两碎片为左右拼接；若没有相匹配的字符，则说明两碎片不是相邻的碎片。重复利用此方法，最终将碎片拼接完整（详细字符规则见附录七）。12.5双边规则通过边缘规则若得到某些拼接组合是拼接耦合，可以确定这些组合是耦合的，但是由于有些文字的渐变性，则会将某些拼接是耦合的组

18、合归为拼接不耦合的一类。双边规则是在边缘规则的基础上进行的进一步改进，使得对碎纸片拼接组合是否耦合的判定更加准确。如图4-7所示：图4-7 双边规则已知碎片A与碎片C上下边缘耦合，碎片B与碎片D上下边缘耦合，碎片C与碎片D左右边缘耦合，由此可得出碎片A与碎片B双边耦合。根据双边规则，对任意两张碎纸片在四个方向上进行拼接，得到双边耦合矩阵。12.6三边规则三边规则是在双边规则的基础上对拼接组合是否耦合的判定条件的进一步加强，使得得到的拼接组合更加准确。如图4-8所示：图4-8 三边规则在上图中，若A与C边缘耦合，B与D边缘耦合，C与D边缘耦合，由双边规则可以得到A与B双边耦合，若还存在A与E边缘

19、耦合，B与F边缘耦合，E与F边缘耦合，由双边规则可以得到A与B双边耦合，A与B拼接中存在两种双边耦合，则称A与B 拼接是三边耦合。通过三边规则得到的拼接矩阵称为三边耦合矩阵。针对上面已经定义的六种基本规则拼接准确度的强弱对算法实现的先后进行排序，优先级排序为：基线规则字宽规则边缘规则字符规则双边规则=1); for i=1:length(ccbset) %if(sum(PrepareSet)=ccbset(i)|isempty(PrepareSet) if(HavedSelect(ccbset(i)=0) fn=ccbset(i); return end %end end fn=;endfun

20、ction cm=CalBaseLineCoupling(ym)m,n=size(ym);BlockHeiht=180;cm=zeros(m,m,4);%0-不耦合，1-耦合 %2:1-水平方向，2-垂直方向for i=1:m for j=(i+1):m vi=ym(i,:); vj=ym(j,:); if(vi(1)=-1 | vj(1)=-1)%未识别，判别为耦合 cm(i,j,2)=1; cm(j,i,2)=1; cm(i,j,4)=1; cm(j,i,4)=1; cm(i,j,1)=1; cm(j,i,1)=1; cm(i,j,3)=1; cm(j,i,3)=1; end if(testNear(vi(1)-vj(1)+BlockHeiht,0) cm(i,j,2)=1; cm(j,i,4)=1; end if(testNear(-vi(1)+vj(1)+BlockHeiht,0) cm(i,j,