《新工厂选址优化模型》由会员分享，可在线阅读，更多相关《新工厂选址优化模型（24页珍藏版）》请在金锄头文库上搜索。
1、 碎纸片拼接复原摘要 本文主要是研究关于分割图片处理汉字碎片拼接问题。针对问题一，首先将附件1图片用像素表示并进行二值化量化处理，用迭代法求出最佳阈值，将抽象的图片用具体的0-1矩阵表达；其次根据像素值分布用MATALAB筛选出最左列碎纸片的编号为008；最后用欧氏距离法建立像素匹配模型，通过MATALAB直接得到中文的拼接图片（见附录一）及序列（见文中表一），不需要进行人工干预。并根据像素匹配模型也完成英文图片（见附录一）的自动拼接（见文中表二），说明该模型的适用性较好。针对问题二，首先将灰度图片用像素量化成1119的矩阵，再将繁杂的像素矩阵通过聚类的方法利用MATALAB分为11个集合，最
2、后在集合范围内建立分步像素匹配模型，用MATALAB匹配拼接出中文图片（见附录二）和序列（见文中表三）。特别地，对于英文碎纸片，需要对分步像素匹配模型的基线确定用黑色像素比例突变的原则进行改进，再用MATALAB根据改进后模型匹配出英文图片（见附录二）和序列（见文中表四），在每行利用计算机拼接的过程中采用人工识别剔除错误的匹配，然后利用人机交互方式完成拼接。 针对问题三，在解决问题一和问题二的过程中发现阈值对整个碎片拼接过程起着极大的作用，阈值不同拼接效果千差万别，所以我们可以用阈值做误差分析和敏感度分析。关键词：像素量化 欧氏距离 聚类分析 双目标规划1、 问题重述破碎文件的拼接在司法物证复
3、原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附
4、件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。3.对于你们建立的模型和算法做相应的误差分析和敏感性分析。2、 基本假设1、 假设题目所给的附件中的碎纸片文件图片的切口是完全水平的；2、 假设碎纸片与碎纸片之间不存在错位的情况；3、 假设碎纸片切口是干净的，没有污渍，也没有噪声的污染；4、 假设中文、英文在间距、高度以及宽度上的差异对像素匹配模型没有影响；5、 假设在图片二值化时的灰色像素可以近似按最佳阈值归化为白色或黑色；6、 假设英文的笔画均匀，且可以量化为固定像素值；7、 假设一张英文碎纸片中最多可以容纳
5、4个完整的英文字母。 3、 符号说明：第个像素值量化矩阵的第行列交叉位置上的元素的值；：点的灰度值；：阈值；：第次迭代时区域像素个数；：两像素量化矩阵的欧式距离值；：像素值；：第个像素量化矩阵；：像素矩阵中第行第列碎纸片基线的纵坐标；：像素矩阵中第行黑色像素所占总像素比例；：像素量化矩阵中第行0的个数；：像素量化矩阵中第行像素点总数;4、 模型的分析、建立与求解4.1问题一的模型分析、建立与求解从附件1中我们可以得到19张仅纵切的中文碎纸片图片，首先将每个图片按像素值进行二值化量化，可以得到19个153950的矩阵，再提取每个矩阵的最左与最右的像素值用绝对值距离法建立像素匹配模型，从边界第一张
6、编号为008入手，依次得出中文图片的顺序。由于英文和中文一样可以量化为像素，故同理可得英文拼接方案。4.1.1图像二值化量化二值化是图像处理的基本技术，目的是将图像增强结果转换成黑白二值图像，从而能清晰地得到边缘特征线，更好的为边缘提取、图像分割以及目标识别等后续工作服务。其原理是将所有灰度大于或等于阀值的像素判定为属于特定物体，其灰度值用1表示，否则这些像素点被排除在物体区域以外，用灰度值0表示背景或者例外的物体区域。 用表示第个像素值量化矩阵的第行交叉位置上的元素值，利用二值化处理可得： 接下来用迭代法确定阈值：（1） 选择图像的平均灰度值作为初始阈值，其中为迭代次数，初始值。（2） 用分
7、割图像，将图像分割为2个区域（3） 计算两区域的平均灰度值（4） 再计算新的阈限值，即：（5） 重复（2）（4），直到与的差几乎为0时，停止迭代，显示最佳阈值。由MATALAB循环运行此算法程序，得到最佳阈值。4.1.2建立像素匹配模型 本文首先提取每个矩阵最左边与最右边的像素值作为每个碎纸片图片的特征，利用这15391的矩阵建立像素匹配模型。 （1）由于文字文件边缘是完整且存在一定的边距，即:筛选出编号008在该文本文件的最左边。同理：可得编号006在文本文件的最右边。 （2）由于在碎纸片边缘是连续关联的，则断裂处的像素点理论上应该是完全吻合，故提取的最右边的像素值与最左边的像素值用欧式距离
8、法建立像素匹配模型：其中： ：4.1.3模型的求解根据像素匹配模型，通过MATALAB循环匹配程序可直接得出拼接完善的中文图片，且不需要人工干预，最终拼接的中文序列见表1：（详情见附录中附件一）1645212717181020681193131191514 （表一）由于英文与中文一样是可以用像素量化的图片，故英文碎片可以直接用上述模型进行复原，通过MATALAB编程可以直接得出拼接完善的英文图片，且不需要人工干预，最终拼接的英文序列见表二：（详情见附件中附录一）1514519112021761618813129103417（表二） 通过对英文图片的自动拼接，可以验证像素匹配模型对碎片拼接的适用
9、性较好。4.2问题二的模型分析、建立与求解分析附件3中209张碎纸片，首先将图片用像素量化，由于文本既有纵切又有横切，采用二值化将图片转换为0-1矩阵的误差比较大，故优化模型采用不同灰度色阶来量化，得到相应的数学矩阵；由于本题中的碎纸片较多，若采用模型一则工作量大且精度不高，故本文第一步将碎纸片进行聚类，第二步在聚类的基础上进行分步匹配，在计算机不能智能识别的情况下给予适当的人工干预。4.2.1对灰度图片的像素量化把有黑-灰-白连续变化的灰度值量化为256个灰度级，灰度值的范围为0255，表示亮度从深到浅，对应图像中的颜色为从黑到白，即：当像素点为白色，像素值为255；当像素点为黑色，像素值为
10、0；当像素点为灰色，像素值。4.2.2筛选出边缘碎纸片 由于文字文件边缘是完整且存在一定的边距，用表示第个像素值量化矩阵的第行列交叉位置上的元素值，则矩阵所对应的前列向量值应该全为255（即白色），即：其中。确定值： 用MATALAB筛选出 的矩阵 得到符合条件的个像素矩阵 用MATALAB筛选出 的矩阵 得到符合条件的个像素矩阵 用MATALAB筛选出 的矩阵得到符合条件的9个像素矩阵 结束筛选程序，得值即筛选出符合条件的9张最左列的碎纸片，分别编号为52、151、112、140、40、45、179、163、85、同理可得最右边列的9张碎纸片编号分别为：141、36、18、74、176、43
11、、145、19、196、60、123。4.2.3模型的建立一）聚类模型的建立（1）数据处理将像素量化的矩阵再坐标化，即以每个矩阵左上角为坐标原点，向右为横轴正方向，向下为纵轴正方向，以像素点作为坐标增量，可得每个像素点对应一个坐标。 （2）确定聚类依据 由于同一字体的汉字具有相同的高度和宽度，即同一行文字的最下端都位于同一条基线上即同一高度上，该特征则可以作为聚类的依据。本文设定在像素量化矩阵中从有0（即黑色）行突变为全为255（即白色）行的界限作为汉字向下对齐的基线，并用MATALAB记下该基线纵坐标。 由于文本文件切割为11行，则由（1）筛选出的最左边列作为聚类的11个起始样本，但是印刷文
12、本段落的起始行需要空两字符才开始，若刚好从段前空的两字符出切割，则最左边列的基准线就不能作为该行的等高线来匹配，故此时需要人工干预将最左边列分为两类： I 类段落起始行在空格处切割的碎纸片编号为：014、029、071、089 II 类不存在上述情况的碎纸片编号为：007、038、049、061、094、125、168。针对第I 类，用（1）筛选出的最右列作为聚类的起始样本。针对第II 类，用（1）筛选出的最左列作为聚类的起始样本。 （3）建立模糊聚类模型（4）模型的求解 根据模糊聚类模型，通过MATALAB逐次循环程序可以将920的像素量化矩阵聚类到以起始样本为目标的11个集合中.所有的碎纸
13、片聚类结果为：二）分步像素匹配模型的建立碎纸片边缘是连续关联的，则断裂处的像素点理论上应该是完全吻合，因为本问题横切与纵切同时存在，则需要横向和纵向都分别匹配，首先对聚类的每一样本集用欧氏距离法通过MATALAB来横向匹配，得到11个横向切割的碎纸条，再将碎纸条进行纵向拼接。（1） 分步像素匹配模型的建立其中： 值越小，就代表两碎纸片越匹配。 针对横向匹配，由于文本的行距要大于间距，所以在横向分割时切断白色间隔区域的概率远远大于切断黑色汉字的概率，故此时要将11行碎纸条聚类：类横向切割线位于全是白色空隔区域类横向切割线位于黑色汉字区域首先，运用上述模型匹配类，再根据行与行之间的笔画或句意人工干
14、预拼接类。4.2.5人工干预及最终复原结果1） 时间节点：像素矩阵聚类时 干预方式：由于基线的匹配导致集合不能得到预想的19个元素， 如集合中筛选出了24个类似与编号049同行的元素，此时就人工干预剔除不合理的2个像素矩阵。这里一共有5个矩阵不合理，故需要人工干预5次。2) 时间节点：碎纸条纵向拼接时 干预方式：由于类的边缘像素值都是255（即为白色），计算机无法识别没有笔迹特征的碎纸条，故需要人工来拼接，类有3个元素，故需要3次人工干预。用MATALAB程序循环匹配得出最终汉字排序为见表三（详图见附录二）5274576282127834621915143112112182113614051143914012811193456149155179145913116320
