数学建模中的碎纸片拼接复原要点研究
开篇：润墨网以专业的文秘视角，为您筛选了一篇数学建模中的碎纸片拼接复原要点研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要：基于模拟退火算法与系统聚类法，文章首先依次介绍了仅纵切、既有横切又有纵切、双面打印三种情形下的碎纸片拼接复原要点，然后对全文进行了总结与展望。
关键词：碎片；拼接；复原；模拟退火算法；系统聚类法
碎纸片拼接复原工作在诸多领域中有着极其重要的应用，如历史文物的考证、司法鉴定以及情报获取等。在计算机技术发展起来之后，传统的人工复原方式导致效率低下的弊端日益凸显，因此，通过数学建模的方法得到碎纸片自动拼接复原模型以提高拼接效率显得尤为重要，已有文献对此做了一些研究[1-3]。文章以2013年全国大学生数学建模竞赛B题为例，基于模拟退火算法与系统聚类分析，依次介绍仅纵切、既有横切又有纵切、双面打印三种情形下的碎纸片拼接复原要点。
1 仅纵切的碎纸片拼接复原要点
步骤6： 降温。选定降温系数θ（一般取为接近1的数）进行降温，即用θT取代T，从而得到新的温度。
步骤7： 算法终止条件。用选定的终止温度Te，判断退火过程是否结束。若T
这样，由于碎纸片较大，图片信息较明显，因此不需要人工干预，复原率可达100%。附件2中的英文图片可类似处理。
对于既有横切又有纵切的碎纸片拼接复原，若利用上一问的方法直接对全部的209张图片进行拼接，一方面必然会导致算法运行效率大大降低；另一方面，由于区分各图片间边界差异的灰度值信息较少，易导致拼接时重码率高而复原率低。因此，我们采用的方法是，首先提取出所有图片的行特征；然后对209张图片建立行聚类模型，对各行聚类依据上一问的方法将其中图片重排；最后对排好序的各行类似的作横向排序即可将碎片拼接复原。具体的步骤如下：
第一步，提取图片的行特征。利用Matlab读入图片，将每张图片转化为一个180*72的灰度值矩阵；再用Matlab可计算出中文字符高为40像素点，行间距为31像素点。
第二步，建立行聚类模型。主要思想是：位于同一横行的图片，其空白行的分布特征是一致的。所^空白行是指该行中灰度值等于255的像素点个数恰好有72个（将这样的行赋值为1，否则赋值为0）；所谓分布特征是指每张图片的180行中，空白行分布的具置或范围。因此，每张图片空白行的分布对应一个180维的向量，不妨称为特征向量，其中的元素为1或0，第i张图片的特征向量记为ηi。为了系统聚类法的顺利运行，此时需要进行人工干预，即对含大片空白行图片的信息根据字符高度和行间距进行补充，得到该图片新的空白行分布范围。最后，我们可以利用系统聚类法中的（类与类间）最短距离法进行聚类，只不过此时图片间距离为d'（i，j）=ηi-ηj1。通过调整最短距离值，将所有的209张图片分成11类（行），每类（行）包含19张图片。然后对各行聚类依据上一问的方法对其中图片进行列间重排。由于信息量较少，边界间区分度不明显，有时需进行人工干预。
第三步，对拼接好的各行类似的作横向排序即可将附件3中碎片复原。
附件4中的英文图片可类似处理。与上述方法的区别仅限于由中英文字符本身的特点不同而导致中英文图片预处理方式不同以及图片特征提取方式不同。
3 双面打印文本的碎纸片拼接复原要点
对于双面打印文本，其解决方法与第二问基本相同。先用系统聚类法将全部的418张图片仍分为11类，每类所含的图片此时有38张，再重排得到同一横行的正反两面。在采用模拟退火算法求解时，同一个初值理论上对应两个终值，因此重排时需要充分利用文本的双面信息，可选择使得正反两面路径之和最小的排列为复原方案。由于边界间区分度不明显，有时亦需进行人工干预。同第二问中的第三步，考量正反两面信息，最后可将附件5中碎片复原。
4 总结与展望
从复原率来看，文章建立的基于模拟退火算法与系统聚类分析的模型是十分有效的。不足之处在于，对切割不均匀以及文字倾斜的碎纸片不再适用。因此，建立更具通用性的模型，是我们下一步的目标。
参考文献
[1]王小睿，吴信才，李军.模拟退火算法的改进策略在模板匹配上的应用[J]. 维普资讯，1997.
[2]罗智中.基于文字特征的文档碎纸片半自动拼接[J].计算机工程预测应用，2012，48（5）：207-210.
[3]姜启源，谢金星，叶俊.数学模型[M].高等教育出版社，2003.