2013全国数学建模竞赛 - 碎纸片拼接复原

保持能力.

对于bw上的一个边缘点x?i,j?，其边缘相似度定义为：

??max?i?i',j?j'?'',''x?ij??BW,x?x'?minx?x?ex'?BWEdSim?x????x?erroneousdetectionpoints??1 （15）

由上式可见，单点边缘相似度反映的是检测边缘点与对应的原标准边缘点之间的位置偏差:如果完全重合，则为最大相似度1;如果相差k个像素点，则其下降为e?k，如果是一个误检点包括错检点和漏检点，即原来不是边缘点，但检测成了一个边缘点；或

者原来有边缘，但是没检测出来，则为-1.

整幅图像的边缘相似度则定义为所有边缘点相似度的平均公式：

EdSim?1M ?EdSim?x? （16）

x?bw式中M为bw中的边缘点数.

5.1.6、基于计算机MATLAB的模型求解 （1）计算机编程求解得到图片的二值矩阵

该问题所见模型基于计算机仿真的MATLAB求解碎纸片的二值矩阵可以得到一个12?72的0、1矩阵列.

以对附件一的纵切碎纸片拼接为例,罗列出前6张碎纸图片求得的二值矩阵如下：

、

表1: 二值矩阵

000.bmp 001.bmp 002.bmp 0 0 0 1 1 0 0 0 1 1 1 1

0 0 1 1 0 1 0 1 0 0 0 1 0 0 1 1 0 0 1 0 1 1 0 0 8

0 1 1 1 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 1 1 1 0 0 1 1 0 1 0 0 0 0 1

003.bmp 004.bmp 005.bmp 0 1 1 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 1 0 0 0 1 1 0 0 1 1 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1 1 0 1 0 0 0 0 1 1 （2）相似度匹配结果 通过相似度匹配分析可以得到每张碎纸图片右边缘与另一张碎纸图片左边缘的相似度匹配分析。若高于90%则匹配吻合。以附件一为例：先人工干预确定第一张图片“008.bmp”为起始点，它的二值矩阵右边与“014.bmp”相似度匹配结果最高. （3）求得的排序结果

表2：对于附件一基于相似度分析匹配求得的碎纸片自动排序 8 4 14 7 12 3 15 8 3 16 10 19 2 12 16 1 1 6 4 2 5 10 9 14 13 11 18 9 11 13 7 15 17 18 0 17 6 5 表3：对于附件二基于相似度分析匹配求得的碎纸片自动排序 （说明：“8”表示第九张图片“008.bmp”排在第一列；附件1和2碎纸图片的拼接结果详见附件） 5.2 问题二模型建立及求解 算法流程图：

导入图像 Sobel 的算法对个碎片进行四个边的边缘化处理 对边缘化处理后的图像进行聚类分析确定阀值 二元相似性度量算法对图像进行分析 二叉树的搜索排序算法对图片排序

图2

9

在实际图像边缘检测问题中，图像的边缘作为图像的一种基本特征，经常被应用到较高层次的图像应用中去。图像边缘是图像最基本的特征之一，往往携带着一幅图像的大部分信息。而边缘存在于图像的不规则结构和不平稳现象中，也即存在于信号的突变点处，这些点给出了图像轮廓的位置，这些轮廓常常是我们在图像边缘检测时所需要的非常重要的一些特征条件，这就需要我们对一幅图像检测并提取出它的边缘. 5.2.1、Sobel operator

索贝尔算子（Sobel operator）是图像处理中的算子之一，主要用作边缘检测。在技术上，它是一离散性差分算子，用来运算图像亮度函数的梯度之近似值。在图像的任何一点使用此算子，将会产生对应的梯度矢量或是其法矢量.

该算子包含两组3x3的矩阵，分别为横向及纵向，将之与图像作平面卷积，即可分别得出横向及纵向的亮度差分近似值。如果以A代表原始图像，Gx及Gy分别代表经横向及纵向边缘检测的图像，其公式如下:

??1?2?1???10?1?????Gx???20?2??A Gy??000??A

??1?2?1???10?1?????图像的每一个像素的横向及纵向梯度近似值可用以下的公式结合，来计算梯度的大

小。

22 G?Gx (17) ?Gy然后可用以下公式计算梯度方向

y ??arctan(Gx) (18)

G在以上例子中，如果以上的角度Θ等于零，即代表图像该处拥有纵向边缘，左方较右方暗。在边沿检测中，常用的一种模板是Sobel 算子。Sobel 算子有两个，一个是检测水平边沿的；另一个是检测垂直平边沿的。Sobel算子对于象素的位置的影响做了加权，因此效果更好。Sobel算子另一种形式是各向同性Sobel(Isotropic Sobel)算子，也有两个，一个是检测水平边沿的，另一个是检测垂直平边沿的。各向同性Sobel算子和普通Sobel算子相比，它的位置加权系数更为准确，在检测不同方向的边沿时梯度的幅度一致.

5.2.2、调整簇阀值的加速聚类方法

调整簇阀值的加速聚类方法的基本思想是:设置簇调整阀值,在每次迭代完成后,只有簇调整量大于阀值的簇才参与下一次迭代调整。簇调整阀值可以设置为簇中心迁移的调整阀值?和簇中样本数目调整阀值?二种情况:

(1)记某一簇在第1次迭代后聚类中心c1与初始的簇中心c0之间的距离为d(c1,c0),在第i次迭代后新的簇中心c，与原簇中心c之间的距离d?c,c'?,如果

?c,c'?d?c1,c0?d??,则

以c，为代表的簇不再参与下轮迭代调整,否则,继续参与迭代调整. (2)对于任一个簇Vi,假设样本数目Ni?n,在每次迭代完成后,该簇中样本调整个数k10

为?Ni(增加或减少的数目绝对值),如果?Ni满足

?Ni??,那么,该簇将不再参与下一轮Ni迭代调整。针对航运信息数据,通过多次Monte-Carlo仿真实验测试,在该算法中,通常设置阀值?在0～0.1之间,阀值?在0～0.05之间。阀值可以只设置任意一个,也可以两个都设置。但是,值得注意的是,如果阀值设置过大,会严重影响聚类精度,因此,要合理地设置阀值的大小。这样,有了调整阀值条件后,参与迭代的样本数目大大减少,从而可以节约大量的运算时间. 算法的基本流程如下:

输入:聚类个数k,数据集X,阀值?和? 输出:k个簇集V和簇中心C

S1：初始化簇中心?coi?i?1;可以使用传统的k-means随机初始化法,也可以采用

kk-means初始化法。

S2：设最终簇集和中心都为空集V=?和C=?,迭代次数t=1。计算每个对象与中心

的距离,按最小距离原则将数据划分到相应的簇,形成k个簇?Voi?i?1,并记录各簇中

k样本个数?Noi?i?1,设置初始的调整标号?f0i?ik?1??1?1.

kkS3：重新计算每个簇中心c1i?1Vi?Xx?Vi和各个簇中心移动的初始位移d?c1i,c0i?,

其中,Vi表示簇Vi中样本的个数.

S4:计算标号ftj?1的簇中每个样本对象与参与调整簇的中心的距离,按最小距离原

则将数据划分到相应的簇,形成k个新簇?Vtj?,并记录各簇中样本个数?Ntj?,求得调整的样本个数?Ntj.

S5：重新计算参与调整簇中心ctj?1Vtjx?Vtj?x和簇中心移动的位移d?c,c?.

tjtjS6：如果簇Vtj的中心ctj满足

d?c1j,c2j?d?ctj,c1j???或者

?NtjNtj??,那么,将簇Vtj中的调整标

号设置为0,即ftj=0,并将Vtj和ctj添加到最终簇及簇中心集合中,即V?V??Vtj?和

c?c??ctj?.

S7：如果形成了包含k个簇的集合,即V=k,那么,终止迭代,算法结束,否则,迭代次

数t=t+1,跳转到步骤4.

11