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

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 拼接是三边耦合。通过三边规则得到的拼接矩阵称为三边耦合矩阵。针对上面已经定义的六种基本规则拼接准确度的强弱对算法实现的先后进行排序，优先级排序为：基线规则<字宽规则<边缘规则<字符规则<双边规则<三边规则。在进行排序时，按照优先级由高到低的顺序进行一步一步筛选。13生成图的流程图4-9 生成图的流程图如图（4-9）所示为得到生成图的流程图。首先选取初始点，对初始点按照各项规则的优先级进行处理。其中英文文件进行字符规则，不进行字宽规则。中文文件进行字宽规

20、则，不进行字符规则。对第一次经历流程图得到图形进行人工筛选出确定集与排除集。在已有基础上再进行整个流程，此次得到的图形即为生成图。14、人工参与方式14.1交互式图4-9 交互式算法流程图图4-9所示的为人工参与方法中交互式的算法流程图。首先选择一个种子，即通过一定的算法找到初始图片。然后就搜索与其拼接最好的图片，搜索的规则为先在确定集里面进行选择拼接，由于第一次运行时，确定集、排除集均为空集，所以直接按耦合度的等级从高到低进行搜索，得到一个结果可以显示出图片和提示信息以供用户进行直观判断，根据实际情况输入指令，更新当前图像，再返回到“获取最优”过程，以此循环，随着运行次数的提高，确定集、排除

21、集逐渐扩大，搜索的效率逐渐提高，直到最后得到复原图。14.2审查式图4-10 审查式算法流程图图4-10所示的是人工参与方式中审查式的算法流程图。首先获取种子，即确定目标，设定最低耦合度，获得在当前约束条件下的最大拼接，此次为第一次显示拼接图像，确定集为空，无法进行匹配，则从当前耦合度开始查找一是查找到最低耦合度，如果找到合理的拼接，就判断该拼接是否在排除集里面，若果在，则重新进行查找，若果不在，则确定该块，更新图。再返回到“获取当前图的最大拼接”这个阶段，如此循环往复，直到找不到合理的拼接，此时程序结束，给用户反馈出一个图，用户根据实际情况选出确定集与排除集。再以此循环上述整个过程，直到得出

22、复原图为止。14.3交互审查式交互审查式拼接法图4-11 交互审查式算法流程图交互审查式拼接是将交互式与审查式相结合。首先任取一碎片，对碎片的信息进行处理后，首先运用审查式的选择方法，将最低耦合规则定为三边规则，则可直接得出两块耦合度较高的已拼接好的碎片。得出初步两块碎片后，设定最低耦合度，获得在当前约束条件下的最大拼接。随后检验审查式算法是否结束。审查式拼接使得交互式与审查式相互弥补，完善整个拼接过程，使得筛选的过程更快，从而拼接的方式得到优化。每一次人工操作时，可选用不同种子进行拼接。这种多种子模式可使得碎片的拼接更加迅速，准确。4.2问题一4.2.1模型建立由于问题一中，附录一和附录二所

23、给出的碎片的像素均为，且其长远长于其宽，故可以直接运用边缘规则进行模型建立求解。根据对图像处理后得到的矩阵，首先人工筛选出左零边的碎纸，再利用边缘规则对剩下的碎纸与其进行右拼接，直至拼接复原。4.2.2模型求解根据边缘模型，计算出碎纸的复原位置如表4-1、4-2所示，从而将原图拼接复原（原图见附录一、附录二）。表4-1 问题一中文拼接顺序8141215310216145913181171706表4-2 问题一英文拼接顺序36271518110519131081214171644.3问题二4.3.1模型建立问题二中是对文件既纵切又横切的情形，相比与第一问而言，碎纸片的大小变小，若单独在某种规则下

24、，得到拼接耦合的组合数增大，增加了得到正确拼接的困难，因此，我们在此问中采用了多种拼接规则对碎纸片进行处理。首先选取一张碎纸片作为种子，设定最低耦合度，按照优先级从高到低的拼接规则对种子进行拼接。对中文文字的碎纸片我们采用的拼接规则的顺序如下：三边规则、双边规则、边缘规则、字宽规则、基线规则。对英文文字的碎纸片我们采用的拼接规则的顺序如下：三边规则、双边规则、字符规则、边缘规则、基线规则。不管是英文还是中文文件，在此文件拼接过程中，对计算机每次产生的结果加入人工参与，参与方式为交互式。对种子进行一次流程的处理，可以给用户反馈出一个拼接图像，在此时进行人工参与，给出确定集与排除集。在此基础之上，

25、再进行一次流程的处理，得到更新图，此图为生成图。接着在生成图的基础上继续进行流程的拼接。如此循环往复，直至得到复原图为止。4.3.2模型求解利用MATLAB对碎片进行处理，让上述流程算法实现，从而找出正确的组合方式如表4-3、4-4，最终拼接为复原图（原图见附录三，附录四）。表4-3 问题二中文拼接排序4954651431862571921781181909511221292891188141611978676999162961317963116163726177205236168100766214230412314719150179120861952618718381484616124358

26、118912210313019388167258910574711568313220017803320219815133170205851521652760141283159821991351273160203169134393151107115176943484183904712142124144771121499713616412758431251318210919716184110187661061502117315718120413914529641112015921804837755544206101049817217159720813815812668175451740137535

27、693153701663219689146102154114401512071551401851081174101113194119123表4-4 问题二英文拼接排序1917511154190184210418064106414932204653967147201148170196188941131647810391801012610061728146865110729401581869824117150559589230374612719194931418812112610515511417618215122572027116582159139112963138153533812312017

28、585501601879720331204110811613673362071351576431994517379161179143208217496111933142168621695419213311818916219711270846014681741371958471721569623991229018510913218195691671631661881111442063130341311025271781714266205101577414583134551856351691831524481771282001315212514019387894872121771240102115

29、4.4问题三4.4.1模型建立问题三中附录五所给的碎片为英文字符，且碎纸为两面均有字符，即可看做是在附录四的基础上，提高了难度，将碎纸的数量扩大了一倍，相应的筛选过程中的可供筛选的碎纸数量同样扩大了一倍，所以对问题三的解决方法可采用交互审查式算法。但根据题意，附录五中同一碎片的两面分别用a，b表示，故匹配的范围有了一定的缩小。先任取一碎片作为种子，首先根据优先级的高低从高到低对种子进行拼接，找出其附近的碎片，形成一小片拼接好的碎片。再取不同的种子，用同样的方法，拼出许多的小片后，再将小片进行拼接，如此循环往复，直至得到复原图，程序结束。4.4.2模型求解根据已有的程序，对碎片的信息进行处理，通

30、过运算，找出图片的正确组合方式如表4-5（原图见附录五）。表4-5 问题三拼接排序136a047b020b164a081a189a029b018a108b066b110b174a183a150b155b140b125b111a078a005b152b147b060a059b014b079b144b120a022b124a192b025a044b178b076a036b010a089b143a200a086a187a131a056a138b045b137a061a094a098b121b038b030b042a084a153b186a083b039a097b175b072a093b132a087

31、b198a181a034b156b206a173a194a169a161b011a199a090b203a162a002b139a070a041b170a151a001a166a115a065a191b037a180b149a107b088a013b024b057b142b208b064a102a017a012b028a154a197b158b058b207b116a179a184a114b035b159b073a193a163b130b021a202b053a177a016a019a092a190a050b201b031b171a146b172b122b182a040b127b188b068

32、a008a117a167b075a063a067b046b168b157b128b195b165a105b204a141b135a027b080a000a185b176b126a074a032b069b004b077b148a085a007a003a009a145b082a205b015a101b118a129a062b052b071a033a119b160a095b051a048b133b023a054a16a112b103b055a100a106a091b049a026a113b134b104b006b123b109b096a043b099b五、模型的评价与改进5.1模型的评价5.1.1模

33、型的优点1、模型采用了多耦合准则，使得碎片之间的耦合程度量化，通过对不同耦合准则的等级化，层层的分析使得问题的分析更有调序，从而达到减少程序运行时间的目的；2、将碎片的拼接问题抽象转化为图像的最优数的寻找问题，利用数学理论，描述图像的拼接；3、提出并实现了多指令的人机交互识别过程，有效缓和用户工作量和拼接效率的问题，充分利用人工识别的优势并极大减少人工工作量；4、碎片拼接算法有较大灵活性，能够广泛运用于一维、二维、双面拼接问题上，对于一般拼接问题都适用。5.1.2模型的缺点1、耦合准则只能对英文字符进行识别，无识别汉字、单词、词意、语意等复杂度较高的耦合规则；2、本文的某些规则如基线规则只适用

34、于方形块的拼接，无法识别不规则碎片的基线。5.2模型的改进1、可通过进一步建立对汉字、单词、词意、语意等复杂度较高的耦合规则， 以提高耦合可信度；2、丰富人工交互指令库，采用图形交互模式降低用户适用本算法的复杂度；3、增加对不规则图片的耦合准则和不规则本文的识别方法，拓宽应用范围。六、参考文献1 周品、赵新芬，MATLAB数学建模与仿真，北京：国防工业出版社，2009.4。2 王兵团，数学建模基础，北京：清华大学出版社，2004.11。3 冯杰、黄力伟、王勤、尹成义，数学建模原理与案例，北京：科学出版社，2007。4 傅彦、顾小丰、王庆先、刘启和，离散数学及其应用，北京：高等教育出版社，200

35、7.7。5 罗智中，基于文字特征的文档碎纸片半自动拼接，计算机工程与应用，48（5）：207-210，2012。6 张欣，物证复原系统中的碎纸轮廓提取技术研究，计算机仿真，23（11）：184-188，2006.11。7 何鹏飞，基于蚁群优化算法的碎纸拼接，计算机工程与科学，33（7）：67-73，2011。七、附录附录一附件1的复原图附录二附件2的复原图附录三附件3的复原图附录四附件4的复原图附录五附件5的正面附件5的反面附录六字宽规则的建立：根据汉字形状比较规则的特点，我们建立了对汉字进行耦合的字宽规则。可以通过该规则算出宽度和，为后续模型做准备。其算法流程图如下图所示。首先，需要对图片进

36、行一定的筛选，因为对于取定一个字的宽度，只有图片中的字在同一高度才有意义。在设计算法的过程中，我们采用了人工进行选取的办法，如果用计算机进行选取的话，通过基线规则也可以实现。选取完成以后通过matlab中的imread函数对图片进行数字化，将图片中的信息转化为以每个像素点的灰度值的矩阵。同时，因为所给图片显示效果只有黑色和白色，那么只需要两个数字就能表示出图片字形效果。我们就取定当每个矩阵点的灰度值大于灰度最大值的一半时，我们就认为此点是白色，用“0”表示，反之认为是黑色，用“1”表示。对字宽进行统计的时候，我们需要的是对一个字一个字的进行拼接。对于一张图片来说，可能有几行字。这时，必须对图片

37、进行分块，每一块是一行字。针对这种情况，我们先对每行矩阵进行求和，并对所求的和进行判断形成判断数组。当所求和等于“0”时取“0”;当所求和不等于“0”时取“1”。从第一行到最后一行逐行查看，如果前一行到后一行的值突然由“1”变为“0”，那么该行必然是一条基线。此时的行高用一个数组表示。应满足的数学表达式为： ；通过matlab编和就能求得基线所对应的值。然后通过基线进行分块。以下图所例：、分别表示所选的第一块，第二块。 分析一张图片中边缘字的宽度时应分为左边缘右边缘。左、右求解的方法基本一致。左边缘对于给定的分块，就从最左边一直向右逐列进行求和，也对所求的和进行判断形成判断数组。当所求和等于“

38、0”时取“0”;当所求和不等于“0”时取“1”。因为我们讨论的是有字的情形，所以当所得判断数组第一次有“0”出现的时候就认为此时为字的边缘。记当前处于的列数为，宽度为（表示第个分块）。右边缘对于给定的分块相对于左边缘唯一的区别在于是从最右边向左逐列进行求和，其他的完全一致。记当前的列数为，宽度为（表示第个分块）。在运用上述算法进行调试时，大多数都适用，但是也有特殊情况。因为汉字的组成具有结构性，比如汉字的“左右结构”，“上下结构”等。当遇到左右结构的字时，有可能左边的和右边的分得比较开，在进行识别的时候只取得了局部数据。因此需要对算法进行调整。我们注意到，对于一个左右结构的字，即使分得很开，导

39、致计算机识别错误，但是左边的与右边的间距总是小于字与字之间的间距的。针对这样的特点，我们假设左右结构中两边的间隔是小于3。就可以在上述的算法中再加一个判断条件，以左边缘为例，当我们得到宽度时，我们继续向右，直到判断行和为1，记下此时的值，如果，我们则认为字宽；如果，此时我们就认为字宽，为了求得真实的字宽，我们又在的基础上继续向右，一直到判断行和为0，此时。同理，在右边缘的情况下就是一直向左，。判断出左右边缘的字宽，我们就可以对两张给定的图片进行拼接。根据第一张图的右边缘宽度，第二张图的左边缘。得到总的宽度，所得为一个数组，表示就某行宽度之和。附录七字符模型建立：对于英文字母，不像汉字那样规则有

40、一个近似固定的宽度。比如“l”和“w”这两个字母之间显示不宽度大不一样。所以对英文的拼接不能用己建立的字宽规则。我们为此建立了针对英文字符的字符规则。首先，我们需要获得52个字母的特征。我们就在所给附件中进行取样，将52个完整的字母单独截下来。然后利用Matlab对每个字母先进行数字化处理，然后分析其特征。分析的方法为：将Matlab进行数字化后的矩阵行、列分别进行5等分，就可以得到25个小的矩阵，再对矩阵进行判断，依次生成判断矩阵（1对应字母a52对应字母Z）。当矩阵中所有元素相加等于0时，判断矩阵中元素所对应的值为0，当不等于0时，所对应的值为1。得到的就反映出了字母的特征。然后我们再找到

41、两块图拼接附近一个具有代表性的区域，用同样的方法得到判断矩阵。再将与每个元素依次对比，如果结果几乎完全相同（误差在2个之内），那么我们认为这算是一个字母。选择代表性区域采用如下方法：首先，两张图所对应的位置应该要在一行不能错位，所以必须满足基线准则。然后我们只需要取出图片中完整的一行即可，同样的和字宽规则一样，生成判断数组。表示该行的上面，表示该行的下面，对数组进行依次向下搜索，选取完整一行应满足下列条件：；取定的区域，假设左边图片所生成的矩阵为，右边图片所生成的矩阵为，利用字宽基本规则选取宽度的方法，获得左宽度，右宽度。已知一个图片矩阵的列宽为72。那么就可得代表性区域的矩阵为：。附录八程序

42、代码：主函数：%clearclc%基线识别代码stn=0;fnshn=208;global RealSpliceSet;global ProbLanguage;% 1-chn,2-engglobal RowHeight;global RunMethod;% 1-JH or 2-SC or 3-JHSCglobal CouplingDegree;% 7-三边，6-双边，5-单边，4-基线global figureloc;global ss;global AA;ss=6;figureloc=zeros(420,420);RunMethod=8;CouplingDegree=1;ProbLangua

43、ge=1;AA=LoadAllImageData(stn,fnshn);baseY=GetBaseLine(AA,stn,fnshn);%获取基线zerosEdge=CalZeroEdge(AA);%计算零边bc=CalBaseLineCoupling(baseY);%测试基线耦合RealSpliceSet=zeros(size(bc);ec=EdgeCoupling(AA,bc);%计算边耦合cc=CalCircleCoupling(ec,bc,zerosEdge);%计算圈耦合save secendProb.matload secendProb.matfor ssD=1:100 ss=ss

44、-1 figureloc=zeros(420,420);FLoc=BuildFigure(AA,bc,ec,cc,zerosEdge);end%ShowFigure(AA,FLoc,3);function figureloc=BuildFigure1D(AA,bc,ec,cc,zerosEdge) BlockNum=19; figureloc=zeros(1,2*BlockNum+4); LFigure=find(zerosEdge(:,3)=1);%左边块 %RFigure=zerosEdge(:,1)=1;%右边块 RealSpliceSet=zeros(size(bc); HavedSe

45、lect=zeros(1,BlockNum); figureloc(1,BlockNum)=LFigure(1);%初始块 HavedSelect(LFigure(1)=1; figureloc=LoopInteration(figureloc,1,BlockNum,LFigure,bc,ec,cc,HavedSelect,RealSpliceSet); endfunction figureloc,HavedSelect=LoopInteration(figureloc,i,j,PrepareSet,bc,ec,cc,HavedSelect,RealSpliceSet) currP=figur

46、eloc(i,j) for d=1:2:3 fn=FindNextBlock(currP,d,PrepareSet,bc,ec,cc,HavedSelect,RealSpliceSet); if(isempty(fn) continue end if(d=1|d=3) hmove=2-d;vmove=0; else hmove=0;vmove=d-3; end if(figureloc(i+vmove,j+hmove)=0) continue end figureloc(i+vmove,j+hmove)=fn; HavedSelect(fn)=1; if(sum(HavedSelect)=19

47、) %return end figureloc,HavedSelect=LoopInteration(figureloc,i+vmove,j+hmove,PrepareSet,bc,ec,cc,HavedSelect,RealSpliceSet); endendfunction fn=FindNextBlock(currP,d,PrepareSet,bc,ec,cc,HavedSelect,RealSpliceSet)%备选集,figureloc:已选集 fn=FindInOneCoupling(currP,d,PrepareSet,ec,HavedSelect); if(isempty(fn

48、) return end fn=;endfunction fn=FindInOneCoupling(currP,d,PrepareSet,OneCM,HavedSelect) ccbset=find(OneCM(currP,:,d)>=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=;endfunction 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; c