碎纸复原模型与算法-广东财经大学.pdf

学校：广东财经大学；

成员： 陈佳润，谢天旺，王行志；

指导教师：胡桂武。     

摘要

本文围绕碎纸片拼接问题，建立了碎纸距离模型、复原TSP模型，并设计了一维碎纸复原算法、二维碎纸复原算法、三维碎纸复原算法等算法，利用MATLAB实现对问题的求解。

针对问题一，设计了一维碎纸复原算法（见4.1.7），首先提取出附件1和附件2碎纸图片的像素矩阵，并对其进行二值化处理，然后利用MATLAB提取碎纸图片的文字特征，通过字符大小、行距等文字特征构造识别序列，并且利用识别序列的吻合度建立了碎纸距离模型（见4.1.4），进而将碎纸复原问题转化为复原TSP问题（见4.1.5），并用模拟退火法进行求解，得到了正确的复原图形及序列（详见附录一）。

针对问题二，设计了二维碎纸复原算法（见4.2.5），首先对附件3和附件4的碎纸图片进行标准化，并对标准化有误的图片进行修正，然后提取标准化后图片的层次特征，利用层次特征对图片进行初步分类，对于机器不能分类的图片，通过编制GUI程序提高了人工判别效率，得到相应11类行特征相同的碎纸，进而将问题转化为11个一维碎纸复原问题并进行求解，得到了正确的复原图形及序列（详见附录二）。

针对问题三，设计了三维碎纸复原算法（见4.3.2），首先对附件5的a面与b面的图片进行整合，得到416张三维碎纸图片，同样对图片进行标准化、提取层次特征、分类等操作，将问题维度降为一维并进行求解，得到附件5正反面的正确复原图片及序列（详见附录三）。

考虑到算法的量化评价问题，本文在模型改进处提出最小干预度算法，即通过计算机识别顺序与复原顺序的序列逆序数，实现了最小人工干预次数对算法优劣进行刻画。

关键词：碎纸复原算法、TSP、模拟退火法、分类降维、GUI设计