1.1对于纵切等长纸片拼接问题的分析

1、1.1对于纵切等长纸片拼接问题的分析在之前的问题中，我们已经将纵向撕裂的纸片拼接成纵向等长的长条状纸片，现在要解决纵切纸片的拼接问题。首先要对整个的纵向纸片进行数字化的处理，将颜色的差异性用数值矩阵表示出来，然后进行二值化处理，得到的是只含有(0,1)的二值矩阵，每一幅图片都对应着一个独立的二值矩阵，两幅图如果能够拼接在一起，那么拼接处的两幅图的对应点的像素值会很接近，因此我们引入匹配度的概念, 度，由于我们所研究的仅仅是图片的边缘部分， 通过匹配度来衡量两张图片边缘处的相似程 因此我们只需要研究二值矩阵的边缘匹配度即可，只需要构建一个仅仅含有边缘部分的矩阵C来进行研究即可，Ckii C(ki

2、)2i或者Ck2i C(k 1)1i的时候，称为一个像素点的匹配，对所有的像素点进行求和即可得到相同的点的个数。通过C矩阵从而计算纸片与纸片之间的匹配度，目的是为了得到图片与图片之间按照某一种顺序拼接而成之后得到的匹配度为最大即可，这是典型哈密顿回路问题，将节点看做是纸片，匹配度与费用成反比的关系，要得到匹配度最大此时的对应费用即为最小。最后我们可以建立模型来求解问题，通过前边部分我们已经可以确定边缘部分的的图片，以此为基准，依次按照匹配度与其进行匹配，得到匹配度最大的作为拼接图片，然后进行下一次拼接，此时上一次拼接的图片应该要剔除出去，最后可以依次得到最后的完整图像。1.问题1基于匹配度的R

3、SSTD问题研究1.1图像的数字化处理(1) 二值化的处理由于碎纸片的长度特征(碎纸片文件的宽度 彼此之间都相等)，其边缘所含有 的信息量是最为丰富的，也是我们进行匹配所需要的。因此我们对其进行灰度处理，进而进行二值化的处理，每一条碎片应该为408 x48,其像素点的值分别为0 , 1，分别表示颜色的黑与白(2)c矩阵的建立 c矩阵为408 X 2的矩阵，用以存储碎纸片的左右边缘的匹配度，现在可以将问题进行化简，已知起始的碎纸片，然后选择其他的碎纸片的排列顺序， 令其总 的匹配度达到最大。碎纸片的顺序匹配可以简化为c矩阵之间的边缘匹配。(3) D矩阵的建立对于每一个C矩阵都存在着一个D矩阵与其

4、相对应， 该矩阵用以存储每一条边缘 取值为0的像素点的个数，D(i,j),1表示碎纸片的编号，j=0表示左侧像素点的信息，j=1表示右侧的像素点的信息。例如D(2,1)=100,表示的意思是2号碎纸片的右侧边缘有10 0个黑色的像素点。(4) 图片边缘的选取(5) 碎纸片特征的选取1.2 匹配度的定义为了：为了衡量两个碎片之间的匹配程度， 通过行匹配度计算碎片之间的匹配程度，更加充分的挖掘了碎片边缘的信息，更为精确。单纯的使用像素点的个数是极为不准确的，因此我们使用匹配度来作为我们的评价标准：叫）=疋索相同的数皐4082基于TSP问题的模型建立与求解由匹配度的定义我们可以知道10个碎片之间的边

5、缘匹配度，现在可以将问题化 简：已知起始时的碎片与其他碎片之间的匹配度，寻找一个序列使起始碎片与其 他的碎片之间的总的匹配度达到最大值。模型建立的步骤如下：（1）找到起始的碎片，得到起始碎片与其他碎片的匹配程度（2）用节点来表示碎片，以有向线段的长度表示费用，费用的具体数值忤=1-% （叫与匹配度的则成反比关系）箭头表示前一条碎片的右侧 边缘到后一条碎片的左侧边缘。（3）现在要求找到一条路径遍历所有的节点使得费用最小，即为哈密顿 回路如图一所示。图一2.1决策变量的分析：我们给出的所有路径之中只存在有一条哈密顿回路，因此 我们引入决策变量Xj，Xij =1表示（i,j）进入了哈密顿回路，反之则

6、表示没有进入到哈 密顿回路中。2.2对于目标函数的分析：两纸片之所以能够拼接在一起是因为两纸片的相邻处 的边缘匹配度最大，即对应着在该路径的费用最小，minWj X j（i, j） E其中的（i, j）表示的是一条路径，即为两纸片之间的对应的方式，w j为在该路径上的费用。2.3对于约束条件的分析：由于该图形之中只存在有位移的一条哈密顿路径，所以必然要保证给定的（i,j）只存在一条哈密顿回路，因此需要满足Xij 1(i，j) E，由此可以保证(i, j),Xji 1(i,j) E（j,i）仅仅只有一次能够进入到哈密顿回路中去。经过以上的分析我们可以得到以下的 TSP模型（1）假设存在哈密顿回路

7、，回路之中存在着n个节点，得到线性规划的模型如 下所示：minWjXij(i,j) EX ij1(i ,j ) EX ji1(i ,j) EXij0,1,(i, j)E模型的求解：算法如图所示（1）将碎片放入到一起进行混合后（2）选择起始的纸片并且将其从混合纸片中剔除，记为 曲（3）依次计算右侧边缘与其他的碎片 K左侧边缘的匹配度'勺（4） 选择匹配度最大的碎片，作为碎片 的右侧的碎片，并且将 其记为焉，从混合的纸片之中将其剔除掉后（5）重复（3）（4）之间的步骤，一直到所有的碎片为空。排序后的碎片顺序（竖直方向的排列）第一排35791第二排825614第三排28418N得到正确的拼接顺序结束应用上边所得到的 TSP模型，以及算法可以求 根据TSP模型左右拼接后的图形第一排17169第二排12382412614251513第三排11242通过求解我们发现，利用TSP模型以及线性规划的知识可以求解出最优解，原因在于匹配度的定义比较好。由于竖直方向的图片拼接的比较好，所以使得纵向切条的边缘二值矩阵所包含的信息量比较丰富，能够很大的提高匹配度的准确性。从而使得结果也变得更为准确。拼接后的视图如图所示：对于拼接结果的分析