2013高教社杯全国大学生数学建模大赛获奖论文

碎纸片的拼接复原

摘要

碎片拼接是指将一组碎片依据其轮廓拼接出物品原来的形状的技术，碎片拼接技术应用于各个领域应用。为了更快更完整的进行碎片拼接，我们通过建立相关的数学模型和算法对碎片拼接问题进行了研究，并对附录所给的碎片进行了自动拼接，得到碎纸片序号排列和复原图。

针对问题一，首先，把19列碎纸片的全部文字信息转化为灰度值信息，为了找出复原图中第一列碎纸片，进行人工干预，即，通过观察找出复原图中的第一列碎纸片。为了得到相邻碎纸片不相等像素点个数，建立了灰度相关匹配模型，当所有碎纸片能够完全拼接在一起时，记下此时相邻碎纸片间不相等像素点个数，此时为匹配的临界值。当达到临界值时，拼接效果最好，由此得出中文复原图对应的原始碎纸片序号为

008014012015003010002016001004005009013018011007017000006；

英文复原图对应的原始碎纸片序号为

003006002007015018011000005001009013010008012014017016004。

针对问题二，首先对附件3与4中209块碎纸片进行二值化处理，其中1表示白点，0表示黑点。根据附件3与4碎纸片的特征，建立了二值化的灰度相关模型，并给出了算法流程，这里我们根据每张碎纸片中每两行文字字间的高度相等作为约束条件，对二值碎纸片进行匹配。先对209块碎片进行分类，分成了11行，由灰度差的不同对第一列进行了拼接，然后对剩下的198块碎片依次进行匹配，把已匹配过的碎纸片进行依次剔除，剩下的继续匹配，完成拼接。

针对问题三，把附件5中英文碎纸片上的文字信息转化成像素信息，然后对碎纸片信息提取角点，建立角点检测模型，并对正反两面依次进行检测。定义了角点检测算子先利用碎纸片沿不同方向做小的平移时的E u,v w x,y I x u,y v I x,y ，

x,y

2

局部灰度变化进行正面检测，当角点检测算子编号较小时，灰度变化不明显，匹配效果

较好，完成一个碎纸片的拼接，按照此方法，完成所有碎纸片的正面拼接。然后进行反面拼接检测，当反面不匹配时即对不符合碎纸片剔除，并对反面不匹配碎纸片再次进行正面匹配，直到所有的碎纸片正反两面均匹配为止，最终得到复原图。

关键词：灰度相关二值化匹配角点检测像素