拼图问题数模大学本科毕业论文.doc

拼图问题

摘要
本文研究被规则切割的图片的拼接复原问题。使用MATLAB软件得到图片的RGB值后，我们建立了RGB颜色模型、欧氏距离模型以及贪婪算法模型。以图片上下边缘RGB值作为解决问题的基础，以欧氏距离作为图片拼接的具体判断依据，并根据贪婪算法的思想得出最优的图片拼接结果。
针对问题一，首先将16张被切割的图片上边缘与原始图上边缘的RGB值进行欧氏距离比较，确定第一行的四张图片。然后分别将第一行图片下边缘与其他图片上边缘RGB值进行欧氏距离比较，循环进行，直至得出全部四行四列图片的正确排列。
针对问题二，由于没有原始图，我们将16张图片分别假设位于第一行，根据贪婪算法，找出最可能位于其下方的其他三张图片。至此得出16列可能的图片组合，然后进行人工筛选剔除上下拼接明显不正常的图片组合，最后得出四行四列图片的正确排列。

关键词：Matlab图像处理 RGB颜色模型（图像的数字化处理模型） 欧氏距离 贪婪算法 边缘匹配度

一、 问题重述

拼图是一种解决平面空间填充和排列难题的益智游戏，要求玩家将印有局部图案的扁平零片进行拼组从而展现出完整图案。在图像处理的计算机时代，为了解决这样一个图片拼接复原的问题，其核心是碎图片的图像信息的科学提取和算法处理等。
请讨论以下问题：
1. 对于给定原始图像的碎片，如何对附件1中整齐划割的图像进行拼接复原。复原过程不需要进行人工干预。复原结果以图片形式及表格形式表达。
2. 对于未给定原始图像的碎片，如何对附件2中整齐划割的图像进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。

二、问题分析

考虑到所要拼接复原的图片都是被规则切割的，我们可以使用MATLAB软件得到图片的数字信息。由于以BMP格式储存的图片读入MATLAB后是主要以灰度值矩阵来储存其图片信息，不能准确地反映彩色图像的特征，所以我们首先要将图片格式全部转化为JPG格式，以得到图片的RGB值矩阵。
得到RGB值后，我们并不需要用到全部的值，而只需要用到其上下边缘的RGB值，并以此作为解决问题的基础，另外采用欧氏距离的概念作为图片拼接的具体判断依据，由此确定图片之间的边缘匹配度。
在问题一中，基于题目已给出原始图片，首先将16张被切割的图片上边缘与原始图上边缘的RGB值进行欧氏距离比较，确定第一行的四张图片。
注意在这一步骤中，16张被切割的图片的大小是不一致的（存在137×91、137×92、138×91、138×92四种尺寸情况），所以在进行被切割的图片之间的欧氏距离计算式我们均采用上下边缘的前面137个像素点的RGB值进行计算。在之后的叙述中均为如此，不再进行特别说明。
在进行被切割的图片与原始图片的比较时，首先采用其上边缘的前137个像素点的值进行欧氏距离计算，在得出第一行的第一张图片后，将原始图上边缘的像素点除去第一张图片上边缘全部像素点个数，然后用随后的137个像素点与其他被切割的图片进行计算比较，得出第一行第二张图片。以此类推直至得出第一行全部四张图片。
然后将第一行的第一张图片作为目标图片，选取其下边缘137个像素点的RGB值，与其他15张图片的上边缘137个像素点的RGB值做欧氏距离计算，得出与其距离值最小的图片，即为目标图片正下方的一张图片。再将这张图片作为新的目标图片，重复上述操作，直到找到这一列全部的四张图片
同样对第一行的其他三张图片进行上述的操作，得出正下方的另外三张图片。至此可以得出16张图片的完整拼图。
针对问题二，由于没有原始图，我们运用贪婪算法，将16张图片分别假设位于第一行，与问题一种确定了第一行的图片相似处理，找出最可能位于其下方的其他三张图片。至此得出16列可能的图片组合，然后进行人工筛选剔除上下拼接明显不正常的图片组合，最后得出四行四列图片的正确排列。
注意在问题二中，所给图片的大小都是一致的，因此在进行RGB值的欧氏距离计算式不用考虑问题一中的情况，直接将上下边缘全部像素点的RGB值进行欧氏距离计算。

三、模型假设

1、假设将图片格式由BMP格式转化为JPG格式后不会影响到图片读入MATLAB后所给出的数字信息；
2、假设在问题一的处理中部分舍去上下边缘第138各像素点RGB值的图片在进行之后的欧氏距离的计算时不会受到影响；
3、假设图片在被切割的过程中边缘没有受到严重的损坏；
4、假设扩展的欧氏距离计算公式能够反映图片之间的实际匹配度；
5、假设贪婪算法在多次循环使用中所得出的结果是一致的。

四、符号说明

符号
符号说明
R
三原色中的红色
G
三原色中的绿色
B
三原色中的蓝色
m
像素点在图片中所在的行位置
n
像素点在图片中所在的列位置

第i张图片的上边缘RGB矩阵

第i张图片的下边缘RGB矩阵

矩阵第j行k列的元素，k取1、2、3分别对应R、G、B值

矩阵第j行k列的元素，k取1、2、3分别对应R、G、B值
D
欧氏距离的计算结果

五、模型的建立

5.1 RGB颜色模型
我们也可以说是图像的数字化处理模型。
5.1.1RGB颜色模型简介
RGB色彩模式是工业界的一种颜色标准，是通过对红(R)、绿(G)、蓝(B)三个颜色通道的变化以及它们相互之间的叠加来得到各式各样的颜色的，RGB即是代表红、绿、蓝三个通道的颜色，这个标准几乎包括了人类视力所能感知的所有颜色，是目前运用最广的颜色系统之一。
RGB色彩模式使用RGB模型为图像中每一个像素的RGB分量分配一个0~255范围内的强度值。RGB图像只使用三种颜色，就可以使它们按照不同的比例混合，在屏幕上呈现16777216(256 × 256 × 256)种颜色。
RGB是从颜色发光的原理来设计定的，通俗点说它的颜色混合方式就好像有红、绿、蓝三盏灯，当它们的光相互叠合的时候，色彩相混，而亮度却等于两者亮度之总和，越混合亮度越高，即加法混合。
红、绿、蓝三个颜色通道每种色各分为255阶亮度，在0时“灯”最弱——是关掉的，而在255时“灯”最亮。当三色数值相同时为无色彩的灰度色，而三色都为255时为最亮的白色，都为0时为黑色。
故可以建立以红色R、绿色G、蓝色B为坐标轴的三维坐标体系，其示意图如下：

5.1.2RGB颜色模型的具体实现
在MATLAB中RGB图象也被称为真彩图像，在8位型数据储存形式下，图片的RGB值储存时只需要一个m×n×3阶的三维图像数据矩阵，每一面中元素下标对应于图像像素点的下标（m,n），而元素值对应一个基色（红、绿、蓝），3个面组合构成其真色。其中元素值的范围为（0,255）。
通过图形的RGB值，我们便可以了解到图形的具体特征。尤其针对我们所研究的被纵横切割的图片，都是规则的矩阵形状，使用MATLAB软件便可以得出图片的RGB值矩阵。
另外由于所要处理的问题是图片拼接问题，所以我们主要研究图片的边缘RGB值，即取m为1或是图片最大行数，将n全部取到，将对应的RGB值存入二维矩阵中，这样就便于我们计算。操作过程示意图如下：

我们将上边缘RGB值存入矩阵A中，将下边缘RGB值存入矩阵B中，如下：
A= B=
行数为为上下边缘像素点个数，三列分别代表R、G、B值。
通过边缘之间RGB值比较和匹配来进行图片的拼接。

5.2欧氏距离模型
5.2.1欧氏距离简介
欧几里得度量（euclidean metric）即欧氏距离是一个通常采用的距离定义，指在多维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）。在二维和三维空间中的欧氏距离的就是两点之间的实际距离。
欧氏距离变换在数字图像处理中的应用范围很广泛，距离是描述像素建关系的基本参数，也是目标物几何特征和相似度的重要测度。
5.2.2欧氏距离的具体计算
我们在运用欧氏距离模型时，实际是运用了距离的这一种度量方式，并在
欧氏距离计算公式的基础上进行了进一步扩展。具体计算方式如下：
以切割后图片中的第一张为例，读取其下边缘RGB值矩阵（138×3的二维矩阵），另任取一张图片的上边缘RGB值矩阵（以第三张为例，137×3的二维矩阵）：
= =
则欧氏计算公式可表示为：
D=
注意由于两个矩阵的行数不一我们舍弃了矩阵的最后一行RGB值。
通过将某张图片与多张图片进行欧氏距离的计算，最后以D的值作为判断依据，D越小，说明两组数据的欧氏距离越小，也就是说边缘匹配度越高。由此找出相匹配的图片。

5.3贪婪算法模型
5.3.1贪婪算法简介
当一个问题的状态空间很大时，穷举法计算量可能会太大，而贪婪算法的思想则是采取目前看来最接近解状态的选择方案，它是一种不追求最优解，只希望得到较为满意解的方法。贪婪算法常以当前情况为基础做最优选择，而不考虑各种可能的整体情况，贪婪算法采用逐步构造最优解的方法，一般贪婪算法将构造可行解的工作分工作阶段来完成，在每个阶段，选择那些在一定的标准下是局部最优的方案，期望各阶段的局部最优的选择带来整体最优。贪婪算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
5.3.2贪婪算法步骤
（1）确定要拼接的图片个数。（贪婪算法主要应用于问题二的解决，这里的图片个数为4，即找出某张图片作为第一张图片的这一列最可能的四张图片的组合。）
（2）读取图片的上下边缘RGB值，将图片数字化。
（3）确定作为基准的图片，将其下边缘RGB值与其他图片上边缘RGB值进行欧式距离计算，得到最可能位于其正下方的图片。
（4）将步骤（3）得出的图片作为基准图片重复步骤（3）直到找出以第一张基准图片为第一张图片的这一列的全部四张图片。
（5）将16张图片依次作为第一张基准图片，进行步骤（3）、（4）的操作，直到得到16列由贪婪算法的图片组合。

六、模型的求解

6.1问题一的求解
6.1.1问题一求解的操作流程图

图一：问题一求解流程图

6.1.2问题一求解的实际操作过程
将问题一中所给图片转化为JPG储存格式后将图片读入MATLAB中，得到图片的RGB值，并提取图片上下边缘的RGB值。
将16张切割后的图片的上边缘的137个像素点的RGB值分别与原始图片上边缘的前137个像素点的RGB值进行欧式距离计算，得出与其距离值最小的图片，即为图片拼接的第一行的第一张图片。如下图所示：

图二：第一张图片确定方法

得出第一张图片后，将16张切割后的图片的上边缘的137个像素点的RGB值与原始图片上边缘减去第一张图片上边缘的像素点数后紧接着的137个像素点的RGB值进行欧式距离计算，同样得出与其距离值最小的图片即为第一行的第二张图片。然后根据同样的方法得出第一行的全部四张图片，如下：

图三：第一列全部四张图片
将第一行的第一张图片作为目标图片，选取其下边缘137个像素点的RGB值，与其他15张图片的上边缘137个像素点的RGB值做欧式距离计算，得出与其距离值最小的图片，即为目标图片正下方的一张图片。然后将这张图片作为新的目标图片，重复上述操作，直到找到这一列全部的四张图片。如下图所示：

图四：第一列图片确定方法
然后，对第一行的其他三张图片进行同样的操作，得出正下方的另外三张图片。至此可以得出16张图片的完整拼图。
上述操作都在MALAB软件中编写程序进行，无须任何人工操作。具体程序代码见附录一。

6.1.3问题一的求解结果
根据题目所给16张切割后的图片的编号1—16，将6.1.2求解得出的结果列入4×4表格中如下：
表一：问题一图片正确拼接顺序
15
9
12
4
5
11
7
8
2
10
6
3
13
14
1
16
具体图片拼接结果如下：

图五：问题一图片拼接结果
6.2问题二的求解
6.2.1问题二求解的操作流程图

图六：问题二求解流程图

6.2.2问题一求解的实际操作及求解
将问题二中所给图片转化为JPG储存格式后将图片读入MATLAB中，得到图片的RGB值，并提取图片上下边缘的RGB值。
以第一张图片作为目标图片，进行贪婪算法，将其下边缘的137个像素点的RGB值与其他15张图片上边缘的137个像素点RGB值进行欧式距离计算得出最可能在其正下方的一张图片。这张图片不一定是实际位于其正下方的图片，因为有些本应位于完整图形中最后一行的图片的正下方并没有图片。我们只是假设每一张图片正下方都存在一张图片，并在此基础上进行贪婪算法，找到最可能的那张图片。
然后将得到的图片作为新的目标图片，同样进行贪婪算法重复操作，直到这一列得出四张图片。具体如下图：

图七：目标图片正下方三张图片确定方法

将第2至16张图片分别作为目标图片，重复上述贪婪算法步骤，则可得出16列（每列4张图片）图片，具体结果如下图：

图八：基于贪婪算法的16中可能结果

以上基于贪婪算法得出的16列图片的操作过程，均在MALAB软件中编写程序进行，无须任何人工操作。具体程序代码见附录二。
在得出上述16列图片后，由于没有原始图形进行对比，我们需要进行人工筛选。上述16张组合后的图片中蓝色箭头所指的衔接处都是可以看出明显不正常的衔接，因此我们很容易剔除12列图片，得出按正确顺序排列的四列图片，如下：

图九：人工筛选得到的四组正确图片
至此得出最后四列仅需调整左右顺序的图片，进行简单的人工调整便可得出图片拼接结果。
6.2.3问题一的求解结果
首先将16张图片分别假设为位于第一行，进行贪婪算法得出这一列最可能的4张图片，在MATLAB中进行编程操作后得出的排列顺序矩阵如下（仍根据题目所给16张切割后的图片的编号1—16）：
表二、基于贪婪算法得出的16种可能结果的拼接顺序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
6
12
12
3
9
16
4
5
13
14
1
10
3
15
7
3
16
10
10
12
13
3
3
9
3
15
6
14
12
7
4
12
3
14
14
10
3
12
12
13
12
7
16
15
10
4
3
10

在上述16列图片组合中进行人工筛选和拼接后得出四行四列图片的正确排列顺序矩阵如下：
表三：问题一图片正确拼接顺序
8
2
15
11
5
12
7
1
9
10
4
6
13
14
3
16

具体图片拼接结果如下：

图十：问题二图片拼接结果
七、模型的评价

模型通过对每一张被切割的图片相互之间（或者与原始图）的边缘值的数字化定量分析，客观地得到每一行每一列的全部图片的正确顺序。采用图片的RGB指标作为判断基础，能够真实准确地反映图片的实际信息；运用扩展的欧氏距离计算方法能为图片边缘匹配度的确定提供客观地依据；基于贪婪算法的检测方法可以得到十六组最佳的图片匹配组合，便于之后的筛选；使用MATLAB软件进行编程求解能够快速准确地得出结果。
但在图片的循环检测过程中，并没有省去对已确定位置的图片的检测而是每次都对其他16张（或15张）图片进行重复检测，这样明显增大了程序运行的工作量。但考虑到所要处理的图片数目较少以及MATLAB软件功能的强大，上述问题实际上也可以忽略。

八、模型的推广

模型评价中考虑到的缺陷对于所要拼接的图片较多时还是真实存在的，所以当处理数据资料过大时，可以在程序中加入部分剔除功能，对于已经明显不可能存在的情况就不再予以考虑或检测。
在问题二处理中，得出最后上下排列正确的四列图片组合后，也可以将这四列图片作为新的图片目标，进行左右边缘RGB值的对比检测，确定其正确顺序。在问题一中也可以对已确定的结果进行进一步检验。但这种检测或检验同样是针对处理大量图片拼接的问题，针对无法轻易人工判断的情况，针对图片边缘数据不够明确的情况。而在实际生活中上述几种情况也是客观且普遍存在的，面对具体的问题我们应进行具体推广。

九、参考文献

[1] 姜启源、谢金星、叶俊 ，《数学建模》 ，高等教育出版社；
[2] 王沫然，《MATLAB与科学计算》 ，电子工业出版社；
[3] 杨丹、赵海滨、龙哲，《MATLAB图像处理实例详解》 ，清华大学出版社；
[4] 李庆阳、王能超、易大义，《数值分析》 ，清华大学出版社；
[5] 基于分类树和贪心算法的测试数据自动生成方法-计算机工程与设计-2011年 第8期 (32)；
[6] 基于核策略的半监督学习方法-计算机工程-2009年 第15期 (3)。

十、附件

附件一、问题一在MATLAB中的求解程序
clear all,clc;
for i=1:17
picname=sprintf('%d.jpg',i);
a=imread(picname); %读取图片RGB值
b=a(1,:,:);
s=size(a);
c=a(s(1),:,:);
x{i}=b; %将所有图片上边缘的RGB值存入到元胞x中
y{i}=c; %将所有图片下边缘的RGB值存入到元胞y中
end

original=x{17};
original=double(original); %将RGB值转化为数值型
sequence=[0 0 0 0];
for ii=1:4 %首先找出位于第一层的四张图片
rr=10000000000000;
for i=1:16
ss=x{i};
ss=double(ss);
zz=0;
for j=1:137
mm=(ss(1,j,1)-original(1,sequence(ii)+j,1))^2+(ss(1,j,2)-original(1,sequence(1,ii)+j,2))^2+(ss(1,j,3)-original(1,sequence(1,ii)+j,3))^2;
zz=mm+zz; %将原始图片与进行对比的图片的上边缘对应位置的R、G、B值分别做差，然后平方相加，作为判断依据
end
zz=sqrt(zz); %对上述结果开根号进行比较
if zz<rr
rr=zz;
order(1,ii)=i; %通过与原始图的对比确定第一层四张图，将图片编号存入矩阵order的第一行中
end
end
number=size(x{order(ii)});
sequence(1,ii+1)=sequence(1,ii)+number(1,2);
end

for jj=1:3 %将已确定的第一层的四张图作为目标，确定第二层的四张图。然后以下一层已确定的四张图为目标，重复操作。
for ii=1:4
target=y{order(jj,ii)};
target=double(target);
rrr=10000000000000;
for i=1:16
if i==order(jj,ii)
continue;
else
sss=x{i};
sss=double(sss);
zzz=0;
for j=1:137
mmm=(sss(1,j,1)-target(1,j,1))^2+(sss(1,j,2)-target(1,j,2))^2+(sss(1,j,3)-target(1,j,3))^2;
zzz=sqrt(mmm)+zzz; %将目标图片下边缘R、G、B值与进行对比的图片的上边缘的的R、G、B值
%分别做差，然后平方相加，作为检测依据
end
end
zzz=sqrt(zzz); %对上述结果开根号进行比较
if zzz<rrr
rrr=zzz;
result=i;
end %选出上述做差后平方相加的结果中的最小值，即为目标图片正下方的一张图片
end
order(jj+1,ii)=result; %将通过循环对比找到的图片编号存入order矩阵中，得出最终结果。
%（得到一个4*4的矩阵）
end
end

附件二、问题二在MATLAB中的求解程序
clear all,clc;
for i=1:16
picname=sprintf('b%d.jpg',i);
a=imread(picname); %读取图片RGB值
b=a(1,:,:);
s=size(a);
c=a(s(1),:,:);
x{i}=b; %将所有图片上边缘的RGB值存入到元胞x中
y{i}=c; %将所有图片下边缘的RGB值存入到元胞y中
end

next=ones(4);
for ii=1:16 %将16张图片分别作为第一张目标图片进行如下操作
next(1,ii)=ii;
for jj=1:3 %将第一张目标图片与其他15张图片进行对比检测找出其正下方的一张图片作为新的目标图片重复操作，
%直到这一列有4张图片
rrr=10000000000000000;
for i=1:16
target=y{next(jj,ii)};
target=double(target);
if i==next(jj,ii)
zzz=10000000000000000;
continue;
else
sss=x{i};
sss=double(sss);
zzz=0;
for j=1:128
mmm=(sss(1,j,1)-target(1,j,1))^2+(sss(1,j,2)-target(1,j,2))^2+(sss(1,j,3)-target(1,j,3))^2;
zzz=mmm+zzz; %将目标图片下边缘R、G、B值与进行对比的图片的上边缘的的R、G、B值
%分别做差，然后平方相加，作为检测依据
end
end
zzz=sqrt(zzz); %对上述结果开根号进行比较
if zzz<rrr
rrr=zzz;
result=i;
end
next(jj+1,ii)=result; %将每一步确定的图片编号存入矩阵next中，最后得到的是一个4*16的矩阵
end
end
end