搜索
1.1对于纵切等长纸片拼接问题的分析在之前的问题中，我们已经将纵向撕裂的纸片拼接成纵向等长的长条状纸片，现在要解决纵切纸片的拼接问题。首先要对整个的纵向纸片进行数字化的处理，将颜色的差异性用数值矩阵表示出来，然后进行二值化处理，得到的是只含有（0,1）的二值矩阵，每一幅图片都对应着一个独立的二值矩阵，两幅图如果能够拼接在一起，那么拼接处的两幅图的对应点的像素值会很接近，因此我们引入匹配度的概念，通过匹配度来衡量两张图片边缘处的相似程度，由于我们所研究的仅仅是图片的边缘部分，因此我们只需要研究二值矩阵的边缘匹配度即可，只需要构建一个仅仅含有边缘部分的矩阵C来进行研究即可，1(1)2kikiCC或者2(1)1kikiCC的时候，称为一个像素点的匹配，对所有的像素点进行求和即可得到相同的点的个数。通过C矩阵从而计算纸片与纸片之间的匹配度，目的是为了得到图片与图片之间按照某一种顺序拼接而成之后得到的匹配度为最大即可，这是典型哈密顿回路问题，将节点看做是纸片，匹配度与费用成反比的关系，要得到匹配度最大此时的对应费用即为最小。最后我们可以建立模型来求解问题，通过前边部分我们已经可以确定边缘部分的的图片，以此为基准，依次按照匹配度与其进行匹配，得到匹配度最大的作为拼接图片，然后进行下一次拼接，此时上一次拼接的图片应该要剔除出去，最后可以依次得到最后的完整图像。1.问题1——基于匹配度的ＲＳＳＴＤ问题研究１．１图像的数字化处理（１）二值化的处理由于碎纸片的长度特征（碎纸片文件的宽度彼此之间都相等），其边缘所含有的信息量是最为丰富的，也是我们进行匹配所需要的。因此我们对其进行灰度处理，进而进行二值化的处理，每一条碎片应该为408×48，其像素点的值分别为｛０,１｝，分别表示颜色的黑与白。（２）Ｃ矩阵的建立Ｃ矩阵为408×２的矩阵，用以存储碎纸片的左右边缘的匹配度，现在可以将问题进行化简，已知起始的碎纸片，然后选择其他的碎纸片的排列顺序，令其总的匹配度达到最大。碎纸片的顺序匹配可以简化为Ｃ矩阵之间的边缘匹配。（３）Ｄ矩阵的建立对于每一个Ｃ矩阵都存在着一个Ｄ矩阵与其相对应，该矩阵用以存储每一条边缘取值为０的像素点的个数，Ｄ（ｉ，ｊ），ｉ表示碎纸片的编号，ｊ＝０表示左侧像素点的信息，ｊ＝１表示右侧的像素点的信息。例如Ｄ（２,１）＝１００，表示的意思是２号碎纸片的右侧边缘有１００个黑色的像素点。（４）图片边缘的选取（５）碎纸片特征的选取１．２匹配度的定义为了：为了衡量两个碎片之间的匹配程度，通过行匹配度计算碎片之间的匹配程度，更加充分的挖掘了碎片边缘的信息，更为精确。单纯的使用像素点的个数是极为不准确的，因此我们使用匹配度Mij来作为我们的评价标准：Mij=元素相同的数量4082基于TSP问题的模型建立与求解由匹配度的定义我们可以知道10个碎片之间的边缘匹配度，现在可以将问题化简：已知起始时的碎片与其他碎片之间的匹配度，寻找一个序列使起始碎片与其他的碎片之间的总的匹配度达到最大值。模型建立的步骤如下：（1）找到起始的碎片，得到起始碎片与其他碎片的匹配程度（2）用节点来表示碎片，以有向线段的长度表示费用，费用的具体数值wij=1-Mij（wij与匹配度的Mij成反比关系）箭头表示前一条碎片的右侧边缘到后一条碎片的左侧边缘。（3）现在要求找到一条路径遍历所有的节点使得费用最小，即为哈密顿回路如图一所示。图一2.1决策变量的分析：我们给出的所有路径之中只存在有一条哈密顿回路，因此我们引入决策变量ijX，ijX=1表示(,)ij进入了哈密顿回路，反之则表示没有进入到哈密顿回路中。2.2对于目标函数的分析：两纸片之所以能够拼接在一起是因为两纸片的相邻处的边缘匹配度最大，即对应着在该路径的费用最小，(,)minijijijEwX其中的(,)ij表示的是一条路径，即为两纸片之间的对应的方式，ijw为在该路径上的费用。2.3对于约束条件的分析：由于该图形之中只存在有位移的一条哈密顿路径，所以必然要保证给定的(,)ij只存在一条哈密顿回路，因此需要满足(,)(,)11ijijEjiijEXX，由此可以保证(,)ij,(,)ji仅仅只有一次能够进入到哈密顿回路中去。经过以上的分析我们可以得到以下的TSP模型（1）假设存在哈密顿回路，回路之中存在着n个节点，得到线性规划的模型如下所示：(,)minijijijEwX(,)(,)110,1,(,)ijijEjiijEijXXXijE模型的求解：算法如图所示（1）将碎片放入到一起进行混合后（2）选择起始的纸片并且将其从混合纸片中剔除，记为Xi（3）依次计算右侧边缘与其他的碎片Xj左侧边缘的匹配度Mij（4）选择匹配度最大的碎片，Xt作为碎片Xi的右侧的碎片，并且将其记为Xi，从混合的纸片之中将其剔除掉后（5）重复（3）~（4）之间的步骤，一直到所有的碎片为空。排序后的碎片顺序（竖直方向的排列）第一排3579101617212627第二排82561323121241514第三排0019220221128418应用上边所得到的TSP模型，以及算法可以求根据TSP模型左右拼接后的图形第一排1710321167275269第二排12382412614251513第三排1120028221918042通过求解我们发现，利用TSP模型以及线性规划的知识可以求解出最优解，原因在于匹配度的定义比较好。由于竖直方向的图片拼接的比较好，所以使得纵向切条的边缘二值矩阵所包含的信息量比较丰富，能够很大的提高匹配度的准确性。从而使得结果也变得更为准确。拼接后的视图如图所示：开始将所有的碎片进行混合选择起始碎片，记该碎片为Xi，并将其从混合碎片中剔除依次计算Xi的右侧边缘与混合碎片中的其他碎片的左侧边缘的匹配度Mij选取选择匹配度最大的碎片，Xt作为碎片的右侧的碎片，并且将其记为Xi，从混合的纸片之中将其剔除掉判断碎纸片是否还有剩余NY得到正确的拼接顺序结束对于拼接结果的分析：在上述的碎纸片拼接的过程之中，我们并没有用到人工干预，因为在连接处我们并没有遇到过连接处全是同一种颜色的情况，根据像素的匹配程度大小，我们完全可以完成拼接，如果在拼接的过程之中出现了接缝处的边缘全部相等的情况时，我们再根据情况进行人工干预。