1.问题
破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：
1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达（见【结果表达格式说明】）。
2.对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。
3.上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。
2.思路
碎纸片的自动拼接技术在司法物证复原、历史文献修复以及军事情报获取等领域具有极为重要的意义，基于此，本文主要对碎纸片自动拼接进行研究分析。建立旅行商模型，求出碎纸片间的Jaccard距离，使用贪心算法取最邻近距离，可求出纵向切割时的最优路线，即为仅单向切割时的复原结果。当进行横纵向切割时，先通过层次聚类中ward聚类进行聚类分析，加以必要的人工干预均分每一类，然后对每一类通过旅行商模型求出最优路线，再对各类之间通过旅行商模型求出最优路线，即为横纵向切割时的复原结果。对碎纸片实现自动拼接技术，可以节约大量的人力物力资源，具有较高的研究意义和现实意义。
3.问题分析
3.1 问题背景
破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用，对碎纸片拼接的研究具有重要意义。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。如果碎片数量巨大，人工拼接很难在短时间内完成任务。基于此，通过计算机技术自动完成碎纸片拼接具有较高的研究意义与现实意义。
3.2 问题重述
- 问题1：对仅纵切的来自同一页印刷文字文件的破碎纸片建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。
- 问题2：对既纵切又横切的碎纸片建立拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。
- 问题3：对既纵切又横切的双面碎纸片建立拼接复原模型和算法，并针对附件5给出的英文文件的碎片数据进行拼接复原。
3.3 问题分析
- 问题1：建立
旅行商模型，求解最优路线，即为复原后碎纸片排序结果。获取二值图，首先根据最左侧求出左边界，然后求解图片边界间的Jaccard距离，利用贪心算法，取最邻近距离，得到该图片左侧的图片，然后继续利用贪心算法求解子问题，得到最优路线。 - 问题2：通过
层次聚类中的ward聚类将209张图片进行聚类分析，分为11类，通过人工干预将图片均分为11类，每一类作为1行，对每一类通过问题1中的旅行商模型求解纵向切割最优路线，然后对11类通过问题1中的旅行商模型求解横向切割最优路线，最终得到最优路线，即复原后排序结果。 - 问题3：计算图片间的
相关系数，求出图片的正反两面，将分类后的209张图片通过问题2的方法求解最优路线。
4. 模型假设
① 假设碎纸片均为大小相等的矩形；
② 假设不存在字迹缺失问题；
③ 假设人工干预时的每次判断均是正确的，不存在手误问题。
5. 符号说明
表1-符号说明与解释
| 符号定义 | 符号释义 |
|---|---|
| $F(i)$ | 第i张图片的灰度矩阵 |
| $B(i)$ | 第i张图片的二值图 |
| $D$ | 切片方向，1表示纵切，2表示横切 |
| $ I(i, j) $ | 排序后第(i,j)处的原序号 |
| $ W $ | 单张图片的宽度 |
| $ H $ | 单张图片的高度 |
| $ R $ | 复原后图片的灰度矩阵 |
| $ C(i) $ | 聚类后的第i行图片 |
| $ J(i, j) $ | 图片i与图片j间的Jaccard距离 |
| $ m1 $ | 图片边界配对数量 |
| $ m2 $ | 图片边界不配对数量 |
| $ up $ | 图片文字距上边界像素数 |
6. 模型建立
6.1 旅行商模型
6.1.1 模型介绍
旅行商问题（Traveling Salesman Problem，TSP），是最基本的路线问题，单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点，需要求出最短距离。可以从距离矩阵中产生一个近似最佳解的途径，有节省法、插入法、途程改善法、合成启发法等求解途径。
6.1.2 建立模型
使用Jaccard距离建立距离矩阵J，利用贪心算法确定最邻近距离，取最邻近距离的图片作为邻接图片，利用贪心算法继续求解子问题的最优路线。得到排序结果I，按照I转化为灰度矩阵R，即为复原结果。
6.2 Jaccard距离
图片F{i}的左边界与F{j}的右边界的配对数量为$m1$，不配对数量为$m2$，则第i张图片与第j张图片的Jaccard距离记为：$J(i,j)=m1/(m1+m2)$
6.3 贪心算法（最邻近算法）
贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。在旅行商模型中，使用贪心算法取最邻近距离，即max(J)，得到的即为邻接图片。通过贪心算法的最优子结构性质求得对子问题求解，得到最优路线。
6.4 Ward聚类
聚类分析以相似性为基础，在一个聚类中的模式之间比不在同一聚类中的模式之间具有更多的相似性。对碎纸片进行拼接复原，每一行具有较高的相似性，通过层次聚类中的ward方法可求出C，通过人工干预将碎纸片均分。
Ward聚类过程：
① 计算每个cluster的ESS：
② 计算合并每两个cluster后总的ESS。
③ 取合并后ESS最小的两个cluster进行合并，重复上述步骤直到合并完所有cluster。
7. 问题求解
7.1 问题1求解
7.1.1 图片预处理
如图1所示图片，在计算机内存储为数字矩阵形式。
计算机将图片存储为灰度矩阵：
将其转化为二值图形式：
7.1.2 建立旅行商模型
在仅纵切碎纸片还原过程中，所有图片作为结点，两图片间Jaccard距离作为权值，可获得一有向图，建立旅行商模型，求解该有向图中权值最大的哈密尔顿路径，选择最邻近算法求解。首先通过图片左侧是否为全白选择出左边界图片，即为哈密尔顿路径的起点，以此为起点获得最优解。
7.1.3 求解Jaccard距离
使用矩阵J记录第i张图片到第j张图片间的Jaccard距离，从左边界开始，所以求图片i的最后一列与图片j的第一列间的匹配数$m_1$，不匹配数$m_2$，从而得到矩阵J。
7.1.4 贪心算法求解
从哈密尔顿路径起点开始，求解该图片到其他图片间Jaccard距离的最大值，即为右侧相邻图片。根据贪心算法的最优子结构性质，依次对剩余图片求Jaccard距离的最大值，直到得出最优哈密尔顿路径。
在仅纵切碎纸片复原中，由于纵向像素较多，误差较小，自动复原准确率高。为了获得最精确的复原效果，在自动复原结束后添加人工干预，人工判断是否需要进行交换操作。
7.2 问题2求解
7.2.1 求每张图片文字距上边界像素数up
部分图片自上向下第一个文字只有一半，导致第一行有黑色像素位置，需要跳过，仅记录完整文字的第一行距上边界的像素数。
对于英文碎纸片，由于字母占用三线格格数不同，对up影响较大，暂时忽略，通过人工干预进行筛选。
7.2.2 对up进行ward层次聚类并人工干预均分每一类
使用层次聚类求解，获得11类，由于up的误差以及分类不精确，需要通过人工干预进行均分，并判断每一类是否为同一行。
通过终端交互式方式进行判断，如果某一图片不属于该行，则输入序号将其去掉。
7.2.3 对每一类求解单行最优路径
求出每一行后需要对每一行进行排序，求解旅行商模型的最优哈密尔顿路径。由于聚类过程中聚类效果可能存在问题，该步骤需要与6.2.2同时进行，以提高精确度。
先通过6.2.2求出聚类结果的某一行，然后利用问题1的旅行商模型对该行求解最优哈密尔顿路径，再次通过6.2.2人工干预方式对聚类效果进行交互式判断，直到获得该行的最优哈密尔顿路径。
7.2.4 求解横向切割最优路径
获得每一行的最优哈密尔顿路径后，通过问题1旅行商模型求解横向切割的最优哈密尔顿路径。由于横向切割时单行得文字数量较少且空白区域较大，需要使用必要的人工干预。
8. 模型的检验与分析
8.1 可行性分析
通过旅行商模型求解最优哈密尔顿路径可以获得最优路线，对于某些误差可以通过人工干预完成，可以较好的完成碎纸片自动拼接操作。使用ward聚类求出图片的每一行，虽然不能均分得到较好的分类效果，但是加以必要的人工干预可以较好的完成分类操作，实际运用完成附件3、附件4的拼接工作足以证明可行性。
8.2 准确度分析
通过旅行商模型以及最邻近算法求解仅纵向切割时的效果较好，对附件1、附件2自动复原的结果完全准确。对附件3、附件4进行聚类时有部分错误，可以通过人工干预完成，对横向切割图片进行求解时有部分误差，可以通过人工干预完成，以实现较高的准确度。
本文主要针对准确度进行研究，在人工干预完全正确的前提下可以实现较高的准确度，但是人工成本增加；在人工干预阶段输入0可以拒绝当前步骤人工干预，但是准确度会下降。
8.3 误差分析
8.3.1 Jacaard距离误差
求解Jaccard距离时通过匹配数进行求解，对下图所示情况不能较好的判断，导致两张图片间Jaccard距离较小，从而对哈密尔顿路径求解产生较大误差。可以通过人工干预避免误差。
8.3.2 图片大小误差
当单张图片较小时，图片中文字数量较少，文字大小与所占位置各不相同，容易产生误差。图片大小不能人为确定，只能通过人工干预判断图片位置。在某些情况下，人工干预也不能正确判断图片所在位置，需要图片多方面特征避免误差。
8.3.3 空白区域误差
图片中某个边界位置处可能为空白区域，对边界图片的判断有影响，也会对最优哈密尔顿路径求解产生影响。对于空白区域误差，可以通过人工干预完成，人工判断边界图片以及人工交换图片所在位置。
8.3.4 聚类误差
聚类过程仅根据up的值进行聚类，由于up的求解过程忽略了文字本身大小以及文字所占格数，up的值并不是完全准确的，导致聚类过程产生误差。对于聚类误差，可以通过人工干预完成，排除聚类误差的影响。
8.4 模型改进
8.4.1 模型准确度改进
在本文仅通过相邻图片匹配求解问题，有较大误差，比如图2所示，对于这种情况，只能通过多次人工干预完成，匹配数无法解决该问题。可以通过OCR技术进行判断，以提高准确度。
由于英文印刷体为三线格形式，在同一行中有些字母占中间一格，有些字母占某两个格或三个格，导致仅通过距上下边界距离进行聚类产生的误差较大，可通过每个字母底部的短横进行聚类，以减小误差，提高准确度。
8.4.2 人工干预方式改进
本文实现的算法是通过终端输入的方式进行交互式人工干预，效果不佳，需要多次输入序号才能完成，容易产生疲劳感，可以实现可视化界面，计算机自动复原和再次基础上的GUI界面人工拼接相结合可以实现更好的效果。
9. 结论
在问题1中，通过旅行商模型求解最优路线，可以通过自动复原得到较好的效果， 对附件1、附件2的还原很好，不需要人工干预。在问题2中通过ward层次聚类的结果不能完美分割为19行，需要通过人工干预得到均分后的各行。在对各行求解最优路线时，由于图片较小，仅通过自动复原误差较大，所以需要进行必要的人工干预，以保证还原的准确性。对求出最优路线的各行排序求整体最优路线时，由于文字是按行方向印刷的，有部分分界处为空白，产生误差，所以仍需要人工干预。
通过计算机技术自动复原和人工干预相结合，可以较好的完成碎纸片复原，既节省了人力物力资源，又获得了较好的复原效果，对相关领域的研究也有着重要意义。
参考文献
[1]王栋.人工智能OCR技术的应用研究[J].电子技术与软件工程,2022(01):122-125.
[2]郭昕刚,王佳,程超.层次聚类算法和基于图的分割算法相融合的图像分割算法[J].国防科技大学学报,2022,44(03):194-200.
[3]张硕航,郭改枝.多旅行商模型及其应用研究综述[J/OL].计算机科学与探索:1-20[2022-07-15]
附录
附录1——碎纸片复原结果以及排序
附录2——排序
排序结果见附件excel表格
附录3——-代码
代码见附件中matlab代码文件
