碎纸复原模型与算法-广东财经大学
全国大学生数学建模竞赛组委会 2022-08-08
字号:AAA
2013高教社杯全国大学生数学建模竞赛优秀论文选登 声明:未经全国大学生数学建模竞赛组委会书面许可,不得转载。

 

碎纸复原模型与算法-广东财经大学.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设计

[责任编辑:刘宇宏]
2013高教社杯全国大学生数学建模竞赛优秀论文选登 声明:未经全国大学生数学建模竞赛组委会书面许可,不得转载。