碎纸片的拼接与复原 全国二等奖

B题:碎纸片的拼接复原-------云南大学滇池学院参赛队员：赵刚 陈一凡 刘明华 指导老师：杨金华

碎纸片的拼接与复原 全国二等奖

主要内容问题的理解与分析 模型的建立与求解 模型的评价与改进

碎纸片的拼接与复原 全国二等奖

主要思想： 图像的边缘拼接问题MATLAB图形处理模型

方法：边缘像素点相似度比较算法贪婪算法

碎纸片的拼接与复原 全国二等奖

一、问题的理解与分析针对问题一：

提取边缘像素点灰度值比较碎片边缘相似度

利用边缘像素点相似度函数 (corr2())对其边缘进行比较，得到 相关系数利用相关系数对碎片进行拼接

碎纸片的拼接与复原 全国二等奖

对于边缘像素点相似度函数 (corr2())所产生的相关系数：

0:两边缘之间毫无相关 -1和1:两边缘之间完全相关越靠近-1或1表示相关系数越强

碎纸片的拼接与复原 全国二等奖

针对问题二： 选出可以作为最左边的碎片在MATLAB中利用corr2()函数比较边 缘相似度，拼接出行，组成大碎片，然后 对大碎片进行整体拼接，最终拼接原图 必要时人工干预

碎纸片的拼接与复原 全国二等奖

针对问题三： 选出可以作为正反两面最左边的碎片

采用贪婪法，将众多小碎片转换为 大碎片 采用边缘像素点比较，选取相关系 数大的，多次循环最终得到拼接复 原结果

碎纸片的拼接与复原 全国二等奖

二、模型的建立与求解图形转换合成部分碎片

对剩余碎片进行处理对不能处理的碎片 进行人工干预 将能合并的碎片转化 为像素点，进行处理

合成总图形

碎纸片的拼接与复原 全国二等奖

问题一程序流程图：图 转 形 换人工干预出 一个碎片 提取边缘灰 度值 边缘相似 度比较 Matlab程序

像素点灰度 值表示

得到待拼接图 形的顺序

得到最终 拼接结果

碎纸片的拼接与复原 全国二等奖

问题一：模型求解提取左边(36列及以上)像素点的灰度值 均为255的碎片 人工干预提取每一个碎片的像素点灰度值的第一列和 最后一列组成变量集合 根据公式corr2()函数计算出每个碎片最后一 列和其余碎片的第一列像素点的相似度008

碎纸片的拼接与复原 全国二等奖

r

( Am n m n

mn

A)( Bmn B )2 2

( ( Amn A) )( ( Bmn B ) )m n

其中

r

:

相关系数 的矩阵对应的矩阵元素值

Amn Bmn :第m行第n列

A B

: Amn

Bmn

的平均矩阵值

碎纸片的拼接与复原 全国二等奖

用MATLAB中的imread()命令读 取19张碎片，每一张碎片构成了 1920x72的矩阵，得到相应的灰度值， 使用相关系数比较法得出边缘像素点 的相似度

碎纸片的拼接与复原 全国二等奖

例如：序号 0 1 2 3 4 5 6 0.1806 7 0.0776 相似度 0.2433 0.2393 -0.0076 0.1782 0.1651 0.2218

序号

8

9

10

110.129

12

13

140.7996 0.7996

150.0034

相似度 NaN 序号 16

0.0849 0.1749 17 18

-0.012 0.0316

相似度 0.0812 0.1386 0.2323

拼接顺序为008-014

碎纸片的拼接与复原 全国二等奖

逐一类推

最终拼接结果：008 014 012 015 003 010 002 016 001 004 005 009 013 018 011 007 017 000 006

碎纸片的拼接与复原 全国二等奖

中文图形：

碎纸片的拼接与复原 全国二等奖

同理得到 英文图形：

碎纸片的拼接与复原 全国二等奖

问题二程序流程图图形转化

matlab挑选出最左边碎片

人工干预

合成大碎片

对剩余碎片进行

处理

人 工 干 预

对断点进行干预

能合成

不能合成的

合成总图形

碎纸片的拼接与复原 全国二等奖

问题二：模型求解

将附件中的碎片导入MATLAB 提取出能作为第一列的碎片利用MATLAB程序进行相关系数比较，先拼 接出每一行，再拼出原文件

碎纸片的拼接与复原 全国二等奖

提取出能作为最左一列的碎片 程序运行结果如下：

7

14 29 38 49 61 62 67 71 80 89 94 125 135 143 168

碎纸片的拼接与复原 全国二等奖

观察图形：

143

49

碎纸片的拼接与复原 全国二等奖

最左边碎片序号如下：7 14 29 38 49 61 71 89 94 125 168