基于改进的BFS算法的碎纸片拼接复原
终期研究报告书
一、课题研究的主要进展和结果
图象拼接是一个日益流行的领域，已经成为照相绘图学、计算机视觉、图像处理和计算机图形学研究中的热点。图像拼接解决的问题一般式，通过对齐一系列空间重叠的图像，构成一个无缝的、高清晰的图像，它具有比单个图像更高的分辨率和更大的视野。 本文的主要工作：
(1) 总结了前人在图像拼接方面的技术发展历程和研究成果。
(2) 学习和研究了前人的图像配准算法。
(3) 学习和研究了常用的图像融合算法。
(4) 用matlab实现本文中的图像拼接算法
(5) 总结了图像拼接中还存在的问题，对图像拼接的发展方向和应用前景进行展望。
我们的项目预期目标是运用改进的BFS算法逐层深入地解决了仅纵切、既横切又纵切以及双面拼接的碎纸片复原问题，并且将得到碎纸片的拼接复原位置和复原图像。为司法物证复原、历史文献修复以及军事情报获取领域提供新的理论方法，同时，避免了人工来进行图象拼接复原的复杂性。
本文根据题目要求，针对具体问题建立相应的数学模型和设计相应的算法，逐层深入地解决了仅纵切、既横切又纵切以及双面拼接的碎纸片复原问题，最后得到了附件1—5的的碎纸片的拼接复原位置和复原图像。结果见附录中的正文。
二、课题研究问题的叙述
2.1 问题一的分析
问题一要求仅对纵切的中英文碎纸片进行拼接复原，这是典型的图像匹配问题。首先按照附件中的图片顺序，依次编号为1~19，然后我们对碎纸片的文字特征进行分析，用将碎纸片数字化，提取其灰度值，再读取每张碎纸片的左右边界灰度值，计算碎纸片之间左右边界灰度值的差的平方值越小，则相似性度量越高。然后判断边界碎纸片，边界的碎纸片的判定可以根据每张纸片的左右边界灰度值是否为空白，左边界灰度值为空白的碎纸片的顺序即为1，右边界灰度值为空白的顺序即为19.从而建立搜索策略模型，用广度搜索优先算法找到每张碎纸片与相似性度量越高的匹配对象即为最佳匹配对象，如果还有小数碎片不能确定其复原位置，单独列出，最后根据文字特征及常识进行人工拼图。
2.2 问题二的分析
问题二要求对既纵切又横切的中英文碎纸片进行拼接复原，在第一问的基础上，我们增加上下两个方向进行广度搜索。以两张碎纸片的上、下、左、右的边界灰度值差的平方之和即相似性度量为标准，相似度量的值越高，两张碎纸片匹配程度越高，对于某个已经标记的碎纸片的某个方向上出现空白，则停止此方向上的搜索，直到四个方向的搜索完成，此时输出该大碎纸片，然后在重复上述过程，直到将所有大碎片全部输出，输出图像中的单个小碎片即为无法确定复原位置的碎纸片。再将各大碎片按照图像的轮廓进行拼接，拼接完成后将形成一张大轮廓图，在人工干预的方式下逐步将单个小碎片逐步拼入大图像中，直至完成对碎片的拼接过程。
2.3问题三的分析
问题三要求对既横切又纵切且双面的中英文碎片进行拼接复原，由于每张碎纸片都有A.B两面，并且无法确定正反面，这样将导致搜索的复杂度大大增加，定位匹配误差明显将会增大，于是我们将所有的碎片在同一平面上进行匹配，只要能拼出其中的一面，另一面的排列顺序即可确定，同时本文设置相似性度量的阀值，在问题二的基础上不断改进搜索策略，对于超过相似性度量阀值的碎纸片单独列出，拼接完成后将形成一张大轮廓图，在人工干预的方式下逐步将单个小碎片拼入大图中，直至完成对碎纸片一面的拼接过程，另外一面随即也将确定。
三、 模型假设
3.1假设碎纸片的原图存在且唯一；
3.2假设干预方式及干预的时间节点可任意选择；
3.3假设被切割的中文在切点处是光滑连续的；
3.4 假设在计算机无法完全自动拼接时，人工干预一定能完成碎片的拼接；
3.5 假设附件中所给的碎纸片清晰完整，无缺失和图像模糊等异常现象；
四、 符号说明及名词定义
4.1符号说明
4.2 名词解释
1.人工干预时间节点：计算机无法自动拼接，人工干预介入时的时间点；
2.拼接完成度：计算机自动拼接好的碎片数与总碎片数的比值；
3.人工干预次数：人工拼接介入的最少次数；
4.相似性度量：两张图像之间的相似系数函数，相似度越高则相似系数值越接1相似度越低则相似系数值越接近0；
5.定位匹配误差：自动拼接中匹配对象出现错误的次数与出现正确次数之比；
基于改进的BFS算法的碎纸片拼接复原
终期研究报告书
一、课题研究的主要进展和结果
图象拼接是一个日益流行的领域，已经成为照相绘图学、计算机视觉、图像处理和计算机图形学研究中的热点。图像拼接解决的问题一般式，通过对齐一系列空间重叠的图像，构成一个无缝的、高清晰的图像，它具有比单个图像更高的分辨率和更大的视野。 本文的主要工作：
(1) 总结了前人在图像拼接方面的技术发展历程和研究成果。
(2) 学习和研究了前人的图像配准算法。
(3) 学习和研究了常用的图像融合算法。
(4) 用matlab实现本文中的图像拼接算法
(5) 总结了图像拼接中还存在的问题，对图像拼接的发展方向和应用前景进行展望。
我们的项目预期目标是运用改进的BFS算法逐层深入地解决了仅纵切、既横切又纵切以及双面拼接的碎纸片复原问题，并且将得到碎纸片的拼接复原位置和复原图像。为司法物证复原、历史文献修复以及军事情报获取领域提供新的理论方法，同时，避免了人工来进行图象拼接复原的复杂性。
本文根据题目要求，针对具体问题建立相应的数学模型和设计相应的算法，逐层深入地解决了仅纵切、既横切又纵切以及双面拼接的碎纸片复原问题，最后得到了附件1—5的的碎纸片的拼接复原位置和复原图像。结果见附录中的正文。
二、课题研究问题的叙述
2.1 问题一的分析
问题一要求仅对纵切的中英文碎纸片进行拼接复原，这是典型的图像匹配问题。首先按照附件中的图片顺序，依次编号为1~19，然后我们对碎纸片的文字特征进行分析，用将碎纸片数字化，提取其灰度值，再读取每张碎纸片的左右边界灰度值，计算碎纸片之间左右边界灰度值的差的平方值越小，则相似性度量越高。然后判断边界碎纸片，边界的碎纸片的判定可以根据每张纸片的左右边界灰度值是否为空白，左边界灰度值为空白的碎纸片的顺序即为1，右边界灰度值为空白的顺序即为19.从而建立搜索策略模型，用广度搜索优先算法找到每张碎纸片与相似性度量越高的匹配对象即为最佳匹配对象，如果还有小数碎片不能确定其复原位置，单独列出，最后根据文字特征及常识进行人工拼图。
2.2 问题二的分析
问题二要求对既纵切又横切的中英文碎纸片进行拼接复原，在第一问的基础上，我们增加上下两个方向进行广度搜索。以两张碎纸片的上、下、左、右的边界灰度值差的平方之和即相似性度量为标准，相似度量的值越高，两张碎纸片匹配程度越高，对于某个已经标记的碎纸片的某个方向上出现空白，则停止此方向上的搜索，直到四个方向的搜索完成，此时输出该大碎纸片，然后在重复上述过程，直到将所有大碎片全部输出，输出图像中的单个小碎片即为无法确定复原位置的碎纸片。再将各大碎片按照图像的轮廓进行拼接，拼接完成后将形成一张大轮廓图，在人工干预的方式下逐步将单个小碎片逐步拼入大图像中，直至完成对碎片的拼接过程。
2.3问题三的分析
问题三要求对既横切又纵切且双面的中英文碎片进行拼接复原，由于每张碎纸片都有A.B两面，并且无法确定正反面，这样将导致搜索的复杂度大大增加，定位匹配误差明显将会增大，于是我们将所有的碎片在同一平面上进行匹配，只要能拼出其中的一面，另一面的排列顺序即可确定，同时本文设置相似性度量的阀值，在问题二的基础上不断改进搜索策略，对于超过相似性度量阀值的碎纸片单独列出，拼接完成后将形成一张大轮廓图，在人工干预的方式下逐步将单个小碎片拼入大图中，直至完成对碎纸片一面的拼接过程，另外一面随即也将确定。
三、 模型假设
3.1假设碎纸片的原图存在且唯一；
3.2假设干预方式及干预的时间节点可任意选择；
3.3假设被切割的中文在切点处是光滑连续的；
3.4 假设在计算机无法完全自动拼接时，人工干预一定能完成碎片的拼接；
3.5 假设附件中所给的碎纸片清晰完整，无缺失和图像模糊等异常现象；
四、 符号说明及名词定义
4.1符号说明
4.2 名词解释
1.人工干预时间节点：计算机无法自动拼接，人工干预介入时的时间点；
2.拼接完成度：计算机自动拼接好的碎片数与总碎片数的比值；
3.人工干预次数：人工拼接介入的最少次数；
4.相似性度量：两张图像之间的相似系数函数，相似度越高则相似系数值越接1相似度越低则相似系数值越接近0；
5.定位匹配误差：自动拼接中匹配对象出现错误的次数与出现正确次数之比；