2、算法先导---思维能力与工具

题目

碎纸片的拼接复原(2013B)

内容

破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题:
1．对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切)，建立碎纸片拼接复原模型和算法，并针对附1、附件⒉给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。
2．对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。
3.上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。

思路

1、从哪入手解决问题？

1.1 第一问

将问题数字化、二值化（0/1矩阵问题）
拿到的是碎纸条
问：要想拼接，靠什么？
答：靠碎纸条上的字
问：碎纸条上的字本质是什么？
答：图像
问：图像是什么？
答：一幅(帧)图像，可以视为由许多按照一定规律排列的像素组成。数字图像中的每一个位置，对应一个像素，每一个像素一个位置坐标和幅值。一般情况下像素数目越多，图像越清晰。
问：图像怎么数字化表达？
答：连续的图像可以用数字的矩阵来表示，灰度图像[0,255];0为黑色，255为白色，彩色图像RGB
问：表达后怎么读取？
答：MATLAB—行公式读入图片，转化为矩阵

1.2 第二问

运用以上思想还是转化为矩阵
版式矩阵

2、选用什么方法？

2.1第一问

纸张左右两边都是空白，为1，可以采用人工干预，中间的数值要误差最小的对应—图论：最短路径

图论最短路：Dijkstra算法、Floyd算法

旅行商问题(TSP - traveling salesman problem)：一名推销员准备前往若干城市推销产品。如何为他(她)设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地)?又叫图论哈密顿圈(Hamilton)【闭环问题】

TSP问题属于NP-Hard问题，使用启发式算法求解例如遗传算法(GA)或蚁群算法求最优解

2.2 第二问

然后用聚类算法：Kmeans聚类或层次聚类
再用哈密顿圈(Hamilton): TSP问题使用启发式算法求最优解
聚类有错时，用人工干预

能力

1、实际问题转化为数学问题
2、聚类算法和图论模型
3、计算机编程求解

工具

MTLAB（会编程语言）

论文

有成果也要有产出

写篇论文吧：

摘要(重中之重)：问题重述，问题分析，条件假设，符号说明
模型的建立与求解
结果的分析和讨论(灵敏性和稳定性分析)
模型的评价与改进，模型优缺点分析，参考文献

文献查找的途径：

中文:
知网
万方
维普

英文：
Web of science
Google scholar
Scopus