2023年全国数学建模竞赛碎纸片拼接复原

2023高教社杯全国大学生数学建模竞赛重庆工商大学姜木北小组作品编号专用页赛区评阅编号(由赛区组委会评阅前进行编号):赛区评阅记录（可供赛区评阅时使用):评阅人评分备注全国统一编号（由赛区组委会送交全国前编号):全国评阅编号(由全国组委会评阅前进行编号）碎纸片的拼接复原摘要目前，“碎片拼接复原”技术在司法物证复原、历史文物修复及社会生活各项领域扮演着重要角色，对于碎片数量特别巨大而人工又难以在短时间内完毕碎片拼接时，要找到一种高效快捷的自动拼接方法已变得尤为重要。本文针对只有中英文的碎片拼接问题，综合分析了从单一的纵切到纵横切以及纵横切双面碎片这三个不同的情况，提出了碎片拼接复原的解决方案.在问题一中,对于仅有“纵切”且数量相对较少的碎纸片，我们基于边沿去噪和采用构建碎纸图片的左右边沿二值矩阵提取相似度分析的方法,再通过两张图片左右相似度匹配排序,得到附件1和附件2中的碎纸排序(见表2和表3)，并运用Ｍatlａb的图像解决工具箱,按排列顺序导入碎纸片得到相应拼接结果(见附录附件一)．在问题二中，由于碎纸片数量相对较多，同时存在横切和纵切的情况,在问题一的基础上增长了碎纸片的上下边沿相似度匹配。在进行人工干预，找到第一张起始碎纸片作为匹配起点后,我们基于索贝尔算子的原理,对碎纸片灰度值进行边沿相似度的旋转检测和比较匹配,最后进行二叉树搜索排序（见表4和表５)。对附件3和４的碎纸图片拼接出的结果详见附录中的附件二．在问题三中，由于碎纸片是两面的并且碎纸片数量更多，若采用第二问的求解方案则加大了求解难度同时也存在较大误差。因此,我们基于蚁群算法(ACA）的ＳIFT特性点匹配原理来求解。先提取碎纸图片特性点，然后基于蚁群算法的最优化快速比对匹配，最后基于ACA的搜索排序对碎纸片拼接。Matｌab编程所求得的排序结果详见表6和表７,附件5中的碎纸片拼接复原结果见附录中的附件三.在问题的解决中，我们得出结论：碎纸图片导入量越小，图片匹配出的效果越佳,在相似度的匹配上，出现的误差减小,最后拼出的图像效果好,人工干预量也相对小。本建模考虑到了图片噪声对图片拼接时的影响,选择了去噪效果较好的邻域平均法对图片进行解决。但是,为了解题方便，我们忽略了碎纸机切纸时碎纸片也许产生的边界遗失破损。在这里我们的改善是,对于边界遗失图像碎片的修复，根据复原后的整体形状,可以根据线连续性来拟合此类线段,从而得到较为完整的图像.关键词:碎纸拼接、腐蚀算法、蚁群算法、图像特性匹配、邻域平均法一、问题的重述破碎文献的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完毕,准确率较高,但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完毕任务。随着计算机技术的发展,人们试图开发碎纸片的自动拼接技术,以提高拼接复原效率。现解决如下问题:1．对于给定的来自同一页印刷文字文献的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法,并针对附件１、附件2给出的中、英文各一页文献的碎片数据进行拼接复原。假如复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达.２．对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件３、附件4给出的中、英文各一页文献的碎片数据进行拼接复原。假如复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达规定同上.3．上述所给碎片数据均为单面打印文献,从现实情形出发，还也许有双面打印文献的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文献的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法,并就附件５的碎片数据给出拼接复原结果,结果表达规定同上.二、问题的分析本题是一个关于碎纸片拼接复原的问题,针对题目的规定,我们对于“碎纸片拼接复原”等一系列问题的解决特点和解决方案,就每个问题做除了以下的具体分析：2．1针对问题1的分析结合给出的碎纸机碎片情况,分别是一页中文和英文文献的碎片数据，也就是说,在每张碎片中都会出现相称多的完整或不完整的汉字（英文）或者结构,要解决把纵切的碎纸片拼接复原的问题：一方面，运用ＭAＴLＡB编程建立图片的二值矩阵。鉴于纸片的大小相同，并且只有黑白两色，通过观测附件一的碎片，每张碎片最左端或者最右端不是全空，这些碎片就可以所有转化为二值图,０代表白色，1代表黑色。另一方面，采用邻域平均法对图像进行边沿去噪，进一步运用分割最佳阈值的迭带算法来达成消除或减少噪声影响的效果。最后，比较图像左右边沿的相似情况,从而得出两个边沿图像的相似度，以此来度量两个图像能否匹配。复原过程中需要人工干预，将依顺序显示的未拼接碎片,采用半自动拼接，即人工选择碎片并拼接到计算机屏幕上。将序号排列好后；再通过基于MATLAB编程将１9张图片分别排好序通过调用imshow（）函数合成图片，这样就能得到最终求解结果.2．２针对问题2的分析求解规定中我们可以知道该问题在第一问的基础上增长了“横切”碎片,出现的纸张既有横切又有纵切。解决方案与第一问有所不同；增长了“横切”过后,在第一问的左右相似度比较之上增长了上下边沿的相似度比较和匹配。但考虑到求解精度我们采用灰度值(0~255)求解的图片解决方法；同样基于MATＬＡＢ编程对附件３和附件4中的碎片分别进行灰度解决得到图片矩阵的灰度值；并采用基于Sｏbｅl的算法对个碎片进行四个边的边沿化解决，提取边沿特性，并对其进行边沿相似度的计算。同时对边沿化解决后的灰度值进行聚类分析拟定一个阀值，也就是拟定一个误差值。只考虑切缝处并对其相似度一致的缝合。又由于该问中需要拼接的图片数量众多，我们采用基于二叉树的搜索排序算法对相似度矩阵排序并得到该相似度矩阵所相应的图片序列号数组，该排列的序列号数组即为碎片的组合方式；最后采用MATLAB循环调用序列号数组相应的碎片名拼接出所求结果达成解决该问题的目的.2.3针对问题3的分析对于问题3其实是在问题二的基础上在增长了正反面的拼接。此外通过度析题目中告诉了的类容可以发现附件中同一个序号表达是一张碎纸图片，a和b表达同一张碎片的了两面,但并不拟定a和ｂ的正反。这样同第二问中的解决思绪相似，但由于问题三中相应的附件5的碎图片数据量过大如若采用第二问的求解方式也并不抱负所以我们采用基于蚁群算法（ACA）的SIＦT特性点图像碎片拼接方法。针对附件五中的图片基于MATLAＢ采用所设计的算法提取其特性点并建立特性点匹配矩阵。再运用这些特性点匹配矩阵根据理论建模设计基于MATLＡB的算法求解出顺序排列的部分序列号和误差节点。将其中求得的序列号相应的碎纸图片导入MＡTＬAB中求解出拼接图像，最后通过人工干预的方式补全各个残缺节点的碎片得到完整的纸片图像已达成拼接出碎纸片的正反两面的目的.三、模型假设1、假设未碎纸张的文字行方向沿水平方向，字与字之间有间隔且字宽度与高度比值1/3；假设碎片模型为抱负模型，碎片表面光滑平整无磨损且厚度为零；假设在切割过程中除边界外，其他切割线都切割文字;假设每张碎纸片的大小一致;假设碎纸机切的纸片无损坏;假设碎图片中的文字符字体格式相同，英文字符字体格式相同.四、符号的定义图像平面上的一系列平均噪声点,第个二值矩阵图像的分割阀值，即灰度值阀值,灰度均值，待测边沿图像边沿点经横(纵向）边沿检测的图像梯度方向第i像素和它的Ｋ连通像素边沿相似度不同中心像素点的协议变量，为启发式因子的相对重要限度为信息素的相对重要限度为信息素蒸发系数表达信息素的持久性系数为窗口信息素含量五、模型的建立及求解５．1问题一模型的建立及求解算法的流程图:载入图像建立图片的二值矩阵载入图像建立图片的二值矩阵采用邻域平均法进行边沿去噪比较图像左右边沿的相似情况运用腐蚀算法轮廓提取方法来消除图像的左右边界的作用图15.1.１、把图像转化为二值矩阵二值图像是指每个像素不是黑就是白,其灰度值没有中间过渡的图像。二值图像一般用来描述文字或者图形,其优点是占用空间少,人们经常用黑白、B＆W、单色图像表达二值图像，但是也可以用来表达每个像素只有一个采样值的任何图像,例如灰度图像等.因此针对问题一,我们先将相应的碎纸图片用Matlａb调用ｉm2ｂｗ函数对导入的碎纸图片求解其二值矩阵.5．１.２、图像边沿去噪——邻域平均法邻域平均法是一种运用Box模板对图像进行模板操作（卷积操作）的图像平滑方法最简朴的平滑滤波是将原图中一个像素的灰度值和它周边邻近像素的灰度值相加,然后将求得的平均值作为新图中该像素的灰度值。它采用模板计算的思想，模板操作实现了一种邻域运算,即某个像素点的结果不仅与本像素灰度有关,并且与其邻域点的像素值有关.将附件１或2中已经进行二值化的碎纸片矩阵惊醒边沿去噪解决,消弱噪声点起到平滑作用，减小相似度误差，增大匹配准确度.设为给定的具有噪声的图像,通过邻域平均解决后的图像为，则邻域平均法也可以用数学公式表达：(1)式中:，;是认为中心的邻域的集合，Ｍ是S内的点数.邻域平均法的思想是通过一点和邻域内的像素点求平均来去除突变的像素点,从而滤掉一定的噪声，其重要在实际应用中,也可以根据不同的需要选择使用不同的模板尺寸,如3×３、5×5、7×7、9×9等。邻域平均解决方法是以图像模糊为代价来减小噪声的,且模板尺寸越大，噪声减小的效果越显著。假如是噪声点,其邻近像素灰度与之相差很大,采用邻域平均法就是用邻近像素的平均值来代替它，这样能明显消弱噪声点，使邻域中灰度接近均匀，起到平滑灰度的作用.从理论上看：a、要改变均值滤波的滤波能力，就要改变模板的大小,模板越大去噪能力越强，反之越弱;b、由于是在整幅图上以取局部灰度平均的方法来淡化噪声,所以不可避免的会使原有图像的清楚度、对比度下降,会损失原有图像的细节，模板越大损失的越多;c、对整幅图像用同一个模板,不能适应局部具体情况，会出现有滤波不均匀的情况.5.1.３、分割阀值的迭代分析法阀值分割方法是把图像的灰度提成不同的等级,然后用设立灰度门限的方法拟定欲分割物体的边界。当用阀值来分割口标与背景时,假如某一灰度值g是某图像的分割阀值，即小于ｇ的灰度点将构成口标（不妨如此假设），而大于g的灰度点就构成背景一般而言,假如灰度值g可以作为图像的一个阀值,那么它应当使按这个阀值划分口标和背景的错误分割的图像像素点数为最小.假如前景物体的内部具有均匀一致的灰度值,并分布在另一个灰度值的均匀背景上，那么图像的灰度直方图应具有明显的双峰。可是在许多情况下,噪声的干扰使峰谷的位置难以鉴定或者结果不稳定本文采用迭代算法，有效地消除或减少噪声对灰度门限值g的影响.设有一幅混入噪声的图像g(x)，力是由原始图像f（x，y)和e(ｘ，ｙ)叠加而成的。即:(2）这里假设各点的噪声是互不相关的,且具有零均值，标准差为。通过阀值分割将图像分割为两部分，由于噪声是随机作用于图像的像素点上，则可以认为在分割出口标和背景图像上噪声干扰仍为，即：(3)（４)在迭代算法中，需要对分割出的图像分别求其灰度均值，则：(5)(６）上式说明，随着迭代次数的增长，平均灰度值将趋向于真值。因此,用迭代算法求得的最佳阀值不受噪声干扰的影响根据上述分析,针对该问题的迭代算法描述如下.(1)一方面选择一个近似阀值作为估训一值的初始值，然后进行分割,产生子图像，并根据子图像的特性来选择新的阀值,再用新的阀值分割图像，通过几次循环,使错误分割的图像像素点降到最少。这样做的效果好于用初始阀值直接分割图像的效果，阀值的改善策略是迭代算法的关键。算法环节如下:选择一个初始阀值的估算值(７）式中,，分别表达图像中的最小和最大灰度值.(２）运用阀值把图像分割成两组,和,其中:(８）(9）(3)计算区域和的灰度值均值，,其中：(10)（11）式中，f（x,y)是图像上(i，j)点的灰度值，N(i,j)是（i,j)点的权重系数，一般Ｎ（i,ｊ)=1.0。（4）选择新的阈值(12)（５）假如,则结束，否则,转环节(2)。通过图像分割解决后,有效减少了噪声对图像的干扰范围,并使图像的边沿邻域像素点离噪声干扰的敏感区,从而提高了图像边沿检测抗干扰能力．5.1．4、腐蚀算法轮廓提取方法通过上述三求解阶段过后，图像轮廓提取算法就变得非常简朴。基于二值图像轮廓提取的算法就是掏空内部点,假如原图中有一点为黑,且它的８个相领点都是黑色时,鉴定该点是原图像的内部点,则将该点删除。最后,通过这样的算法处缘检测[４,5]。在数学形态学运算中,腐蚀具有消除物体边界点的作用。结构元素取3×3的黑点块,腐蚀将使物体的边界沿周边减少一个像素。那么边沿检测事实上相称于用3×3块的９个点结构元素对原图进行腐蚀，再用原图像减去腐蚀的图像。令X为图像，B为结构元素,BZ表达结构元素B平移Z后的结果，代表结构元素关于原点的对称集合。其数学表达如下:（13）则腐蚀的运算定义:(14)式中,的结构元素；ED(X）：代表图像Ｘ的边界.该方法检测到的物体边沿宽度仅为一个像素,因此具有较高的定位精度。同时,二值化解决后的图像具有完整的轮廓,所以轮廓提取检测到的边沿具有连续性.5.1.5、边沿相似度边沿相似度的基本思想是用标准的无噪图像产生出标准的边沿图像，设为,将含噪图像用噪声克制算法滤波解决后产生待测边沿图像,设为,比较两个边沿图像上各个边沿点的相似情况,从而得出两个边沿图像的相似度,以此来度量滤波算法的边沿保持能力.对于上的一个边沿点，其边沿相似度定义为:(１５)由上式可见，单点边沿相似度反映的是检测边沿点与相应的原标准边沿点之间的位置偏差:假如完全重合,则为最大相似度１;假如相差ｋ个像素点,则其下降为,假如是一个误检点涉及错检点和漏检点，即本来不是边沿点，但检测成了一个边沿点；或者本来有边沿，但是没检测出来，则为-1.整幅图像的边沿相似度则定义为所有边沿点相似度的平均公式：(16）式中M为中的边沿点数．5.1．６、基于计算机MATＬAB的模型求解（1）计算机编程求解得到图片的二值矩阵该问题所见模型基于计算机仿真的ＭＡＴLAB求解碎纸片的二值矩阵可以得到一个的０、1矩阵列.以对附件一的纵切碎纸片拼接为例,罗列出前６张碎纸图片求得的二值矩阵如下：、表1:二值矩阵000．bｍp０01．bmp0０2.bｍp0０0011000１１0０111００11110１1001010100００0０10１1０1010010１00０1010０01０００10110111００3.ｂmp０04．bｍp００５.bｍp01001０11010011110１01100１0０0100１０101１01010０101０0０101０0０00101001111１010１01(２）相似度匹配结果通过相似度匹配分析可以得到每张碎纸图片右边沿与另一张碎纸图片左边沿的相似度匹配分析。若高于90%则匹配吻合。以附件一为例：先人工干预拟定第一张图片“００8.bmｐ”为起始点,它的二值矩阵右边与“0１4．bmp”相似度匹配结果最高.（３）求得的排序结果表2:对于附件一基于相似度分析匹配求得的碎纸片自动排序81４121５３10２161459１3181１71706表3：对于附件二基于相似度分析匹配求得的碎纸片自动排序47381619１2162101411913１51８175(说明:“８”表达第九张图片“008.ｂｍp”排在第一列;附件1和2碎纸图片的拼接结果详见附件)5.2问题二模型建立及求解算法流程图：SobelSobel的算法对个碎片进行四个边的边沿化解决对边沿化解决后的图像进行聚类分析拟定阀值二叉树的搜索排序算法对图片排序二元相似性度量算法对图像进行分析导入图像图2在实际图像边沿检测问题中,图像的边沿作为图像的一种基本特性，经常被应用到较高层次的图像应用中去。图像边沿是图像最基本的特性之一，往往携带着一幅图像的大部分信息。而边沿存在于图像的不规则结构和不平稳现象中,也即存在于信号的突变点处，这些点给出了图像轮廓的位置,这些轮廓经常是我们在图像边沿检测时所需要的非常重要的一些特性条件,这就需要我们对一幅图像检测并提取出它的边沿.5.2.1、Sｏbeｌoｐeｒator索贝尔算子（Sｏｂelopｅrator）是图像解决中的算子之一，重要用作边沿检测。在技术上，它是一离散性差分算子，用来运算图像亮度函数的梯度之近似值。在图像的任何一点使用此算子,将会产生相应的梯度矢量或是其法矢量.该算子包含两组3x3的矩阵，分别为横向及纵向,将之与图像作平面卷积，即可分别得出横向及纵向的亮度差分近似值。假如以A代表原始图像,Gx及Gy分别代表经横向及纵向边沿检测的图像,其公式如下:图像的每一个像素的横向及纵向梯度近似值可用以下的公式结合，来计算梯度的大小。(1７)然后可用以下公式计算梯度方向(１８)在以上例子中,假如以上的角度Θ等于零,即代表图像该处拥有纵向边沿,左方较右方暗。在边沿检测中,常用的一种模板是Soｂel算子。Sobel算子有两个，一个是检测水平边沿的;另一个是检测垂直平边沿的。Sｏbel算子对于象素的位置的影响做了加权，因此效果更好。Sobｅl算子另一种形式是各向同性Sobel(IsotropｉcSｏｂel)算子，也有两个,一个是检测水平边沿的,另一个是检测垂直平边沿的。各向同性Sｏbel算子和普通Sｏbｅl算子相比,它的位置加权系数更为准确,在检测不同方向的边沿时梯度的幅度一致.5.2.２、调整簇阀值的加速聚类方法调整簇阀值的加速聚类方法的基本思想是:设立簇调整阀值,在每次迭代完毕后,只有簇调整量大于阀值的簇才参与下一次迭代调整。簇调整阀值可以设立为簇中心迁移的调整阀值和簇中样本数目调整阀值二种情况：（１)记某一簇在第1次迭代后聚类中心与初始的簇中心之间的距离为,在第次迭代后新的簇中心与原簇中心之间的距离,假如,则认为代表的簇不再参与下轮迭代调整,否则,继续参与迭代调整.(2)对于任一个簇,假设样本数目,在每次迭代完毕后,该簇中样本调整个数为（增长或减少的数目绝对值),假如满足,那么,该簇将不再参与下一轮迭代调整。针对航运信息数据,通过多次Monte-Ｃaｒlｏ仿真实验测试,在该算法中,通常设立阀值在0~0.1之间,阀值在０～0.０5之间。阀值可以只设立任意一个，也可以两个都设立。但是,值得注意的是，假如阀值设立过大，会严重影响聚类精度,因此,要合理地设立阀值的大小。这样，有了调整阀值条件后,参与迭代的样本数目大大减少，从而可以节约大量的运算时间.算法的基本流程如下：输入：聚类个数k,数据集X,阀值和输出：k个簇集V和簇中心C:初始化簇中心;可以使用传统的k－ｍeａnｓ随机初始化法,也可以采用k－meａnｓ初始化法。：设最终簇集和中心都为空集V=和C＝,迭代次数t＝1。计算每个对象与中心的距离，按最小距离原则将数据划分到相应的簇,形成k个簇,并记录各簇中样本个数,设立初始的调整标号.:重新计算每个簇中心和各个簇中心移动的初始位移,其中,表达簇中样本的个数.:计算标号的簇中每个样本对象与参与调整簇的中心的距离,按最小距离原则将数据划分到相应的簇,形成k个新簇,并记录各簇中样本个数,求得调整的样本个数.:重新计算参与调整簇中心和簇中心移动的位移．：假如簇的中心满足或者,那么，将簇中的调整标号设立为０,即＝０,并将和添加到最终簇及簇中心集合中,即和.:假如形成了包含k个簇的集合，即V=k,那么,终止迭代，算法结束,否则,迭代次数t=t+1,跳转到环节4.聚类结果的评价重要两个方面:聚类精度和算法时间复杂度．算法性能分析实验如下:（1）聚类精度分析传统的k－ｍeans算法,所求的解往往是局部最优解,使用k-meanｓ算法在一定限度上减少了局部最优也许性,但从聚类过程看，求的解也往往是局部最优解,本文提出的调整簇阀值的加速算法，由于采用了近似的ｋ-ｍeanｓ算法，导致该算法只能找到局部近似解。适本地设立阀值，也能得到和ｋ-means算法相称的聚类精度.（2)时间复杂度分析传统k－meaｎs算法的时间复杂度为，其中,ｎ为样本个数,ｋ为簇数目,d为数据维数,t为迭代次数.5．2.3、相似度计算二元相似性度量算法分析传统的度量是采用基于两幅图像相应像素位置的位与位匹配的方法。但是在被动篡改检测中,是没有可以用来比对的原始图像的。所以,在基于二元相似性度量的图像被动篡改检测中,我们考虑比较图像位平面的二元纹理记录特性.一方面,我们用表达第i像素和它的K连通像素(或Ｋ邻居像素，K＝4或K＝８）的顺序关系。在本文中，我们选择K=4,表达选择N,W,Ｓ，E(上!下!左！右)四个连通像素,i表达图像所有像素点,假定图像的大小是M和Ｎ。我们定义模板函数如式(6）所示:（1９)这样,对于一个中间像素点ｉ，它与其四连通像素的关系可以表达为式:(2０)对于中心像素，我们定义它的协议变量(agreemｅnt）为下式：（21）其中，是克罗内克函数(Krｏnｅckerdeltａｆuｎｃtioｎ),其定义如式：（22）因此对于,有:(２3)很显然，函数表达中心像素点和其连通像素点之间的转换关系。对于中心像素点,它与其四连通像素的关系可以重新表达为式：累积一协议量(acｃumulatｅdagｒeemeｎｔs)的定义如下所示：，,这四个变量是一幅二进制图像的一阶随着变量.5．2.4、二叉树搜索排列二叉树搜索排序定义:二叉树的定义:空或有一个根，根有左子树、右子树;而左右子树自身又是二叉树。如图所示：B图3:BLCLCDFEDFE1、二叉树的性质：性质１：在二叉树的第i层上至多有2i-1个结点;性质２：高度为k的二叉树至多有2k－1个结点;性质３:二叉树的叶子结点数ｎ0等于度为2的结点数n2+1；性质4:具有n个结点的完全二叉树高度为ｌoｇ2n＋1;性质5:对一棵有ｎ个结点的完全二叉树按照从第一层(根所在的层次〕到最后一层，并且每一层都按照从左到右的顺序进行编号。根结点的编号为１,最后一个结点的编号为n．1：对任何一个编号为ｉ的结点而言,它的左儿子的编号为2ｉ(若２i＜=n),而右儿子的编号为2i+１(若2i+1<=ｎ).2:对任何一个编号为ｊ的结点而言,它的父亲结点的的编号为j／2。根结点无父结点.２、二叉树的遍历:设N代表根节点,Ｌ代表左子树,R代表右子树。a．前序（或先序):假如二叉树为空,则操作为空:否则访问根结点；前序遍历左子树;前序遍历右子树。记为：NLRｂ.中序:假如二叉树为空，则操作为空：否则中序遍历左子树；访问根结点;中序遍历右子树。记为:LNＲ.c．后序：假如二叉树为空，则操作为空：否则后序遍历左子树;后序遍历右子树;访问根结点。记为：LRN.B图４:BCLCLDFBEDFBEXW3、二叉树的作用:XW1查找当前第K大元素;２查询某元素在当前所有元素中的排名.(２４)其中，是克罗内克函数（Kroneckerdeltafｕnｃtion)，其定义如式:(25）因此对于,有:很显然,函数表达中心像素点和其连通像素点之间的转换关系.对于中心像素点,它与其四连通像素的关系可以重新表达为式:累积一协议量(acｃuｍuｌａtｅｄagreements）的定义如式所示,,这四个变量是一幅二进制图像的一阶随着变量.5.2.5、构建模型的计算机仿真求解通过基于MATＬAB编程的算法求解分析我们得到了如下表格的碎纸图片序号排列矩阵:表４:附件三的碎纸片排列矩阵0123456104905４0６514318６0０220６10１9078067069099３１68100０760６214２０3０4０3８1480４６1610２40３5507１１5608３13220001７60141280031590821９97094０3４08４183090０4７８12501３1８210919701６９0２9064１１1２0100５0９２10007２0813８1581２6０68110８９14６1６２15411４0４07891０１１1２0５7192１7811８１9００95162０9613１０７９0631１6041０2３１４７19１05０17９08118９122103１3019308003３022１98015133１3５012０7３16０2031６912１0４2124１4４０7７1121841１0１８7０６６106150１8004８037０7５０55０4417５04５14７０00137053１5１２０7155140１８５1０8131415161７1819０1１0221２90２8０９118８141１630７2006１7702０0５２0361200861950２６001087０１80８８１6７02500800910507417020508５15２1６5027060１34０39０310５1017115１76１49097１361６412７０５8043０2117015718120４1３９145206０１0104０9817２１710590560931５3０7016６032１９6117004１0111３１９411９１23表5:对于附件四的碎纸片排列矩阵01234５611910７5０１１15４19018４220114８1701961980９430860５1107０2９０4015８４019194０93１4１08812151５9139001129０6３23860２0041108１1613607３7208０2１00７0490６111980７０08４06001406817４９1321８10９５069１67１6３1017１0420６6205０１０１571108１077１28200１3１05278910111２13002104180０6４1０60041４９１1３1６407810３０9108010118６０９8０２411７150005０59１２61０51５5114１７618２１51１５305303８1231２0175０8５0３6207１35０15０7６0４31９9033142１６806２16905４1921３719５0０8０47１72156０9６16６1８81１11442０600３１３0074１45０８３13４０5５01805612５１４019308７08９０48０７2１41516１７18１90322０４0６5０39０67147０26１000０601702814６0580920３0０3704612702２０57２０２07１1６5０8205016０18709７203031０４51７3０79161１7914３13311818916２197112０2３0９91２20９0185１0903４0１３１100２50２７１780３501600918３15２0440121771２４0001021１5(附件3和４的碎纸片拼接结果详见附件）５.3、问题三模型的建立及求解5．３.1、蚁群算法实现图像最优化比对搜索蚁群算法(ACA)是受到蚂蚁群体寻找食物行为的启发而提出的一种基于蚁群的模拟进化算法。一般来讲群体随机搜索算法常用于解决特定的组合优化问题。自然界中蚂蚁搜索食物过程是一个不断聚类的过程，食物就是聚类中心，其重要思想是：将每个数据看作一个蚂蚁，蚂蚁分别聚集到个聚类中心，到的距离为,采用欧式距离计算:(26）其中：m表达每个数据特性的维数；Ｐ加权因子，根据像素分量对信息测度影响限度设定。假设算法中的蚂蚁具有一定的记忆能力,能根据２幅待拼接图像上互信息浓度选择转移方向，从而引导蚂蚁向互信息测度最大值的方向移动．蚁群算法解决的问题一般具有如下特点:①搜索空间是离散的;②有一组有限的约束条件；③有一个代价函数,为搜索算法生成的解计算相应的代价,解的每一部分都会对解的代价产生影响;④有一个有限的节点集合，用于构建解；⑤有一个有限的节点间的也许转移的集合；⑥有一个节点序列的有限集合,用于表达所有的有效组合，来定义完整的搜索空间，组合的有效性、可行性由约束条件决定．可以将图像拼接过程中图像A中的窗口在Ｂ搜索迭代的过程当作是“只蚂蚁的城市模型”,从而使得蚂蚁可以在这个模型图上进行爬行,并且保证了蚂蚁爬行所获得的每个哈密顿路都相应一个互信量最大的组合.蚁群算法的参数进行如下设立：为信息素的相对重要限度;为启发式因子的相对重要限度；为信息素蒸发系数，表达信息素的持久性系数,且（2７）其中：为窗口信息素含量;为启发函数；N为循环遍历次数．5.３.２、基于ＡCA搜索的碎纸片图像SIFT特性点匹配基于图像特性的方法,一方面要对待配准的两幅图像进行解决，提取满足特定应用规定的特性集,然后将这两组特性集进行匹配相应,生成一组相应特性对集，最后运用这组特性对之间的相应关系估计出全局变换参数。基于图像特性的方法，在特性提取后得到的特性点的数量将会大大减少,因此可以提高配准的速度，但其配准的效果很大限度上还取决于特性点的提取精度以及特性点匹配的准确度。基于图像特性的配准方法重要困难在于如何提取和选择鲁棒的特性，以及如何对特性进行匹配,其中要克服,由于图像噪声和场景中出现遮挡现象所引起的误匹配的问题。常用的图像匹配特性有点、直线、曲线等.目前大多数文献都是采用点特性进行图像之间的配准，从而实现图像的拼接。基于图像特性配准的方法的重要优点是它提取了图像的显著特性，大大压缩了图像的信息量，计算量小,速度较快,并且它对图像灰度的变化具有鲁棒性。但另一方面，正是由于只有一小部分的图像灰度信息被使用了,所以这种方法对特性提取和特性匹配的错误更敏感，需要可靠的特性提取和特性一致性.图5:基于特性点的图像拼接流程图该问题总结的算法的搜索过程可以理解为：在2幅或多幅图上运用蚁群作为搜索窗口,通过互信息测度的方式代替搜索出的2幅图像之间在目的、背景、边界和噪声等内容中的特性向量的过程。依据互信息量最大作为搜索并且不断改变的方向,最终朝着使互信息量最大的方向搜索，从而拟定出2幅图像之间存在的匹配区域.碎片全局拼接假如有两个碎片证明是匹配的，那么把匹配之后的碎片组成一个新的人工碎片,反复以上的环节,直到所有的碎片拼接完毕。用这种方式，拼接的过程形成了岛屿状。计算每个碎片的轮廓长度。假如M是旋转链的轮廓像素的总数，N是固定链的轮廓像素的总数。那么旋转链每次从＃(M-j），ｊ=1,2,...,M-1绕着固定链＃（N－Ｌ)，L=1,２,....N－1进行比较，直到完毕匹配．5．3.3、模型三的MATLAB求解表6:对于附件五的碎纸片排列矩阵第一面01２3４5６1０78ｂ11１b１２５a140a155a1５0a20８９a0１0ｂ036ａ0７6b１78ａ0４4ａ３186ｂ15３ａ０84b042ｂ030a038a4199ｂ011b１61ｂ169b1９４b173b5088b1０7a14９ｂ180a037b１91a6１１4ａ184ｂ１７９b116ｂ20７a058a７146a17１b031a２０1a05０a190ｂ8165b１95a118a15７ａ1６8ａ04６a900３ｂ0０7b085b14８b０77a０04a10023ｂ133a048a０5１b０95a160b11099a0４3a０96b109ａ123a00６ａ７8910１112１318３ｂ174b11０a066a１08ａ018b029a02５ｂ192a12４b02２a120b1４4a0７9a１21a098a094b061a１３７b０４5ａ１３8ａ２06ｂ156a0３４a18１b198b087a1３２ｂ065b115b1６6b001b151b1７０b041ａ158a197a1５4b0２8ｂ0１2a01７ｂ120b092b０1９b016b１７7ｂ０53b202ａ0２1b０67ａ0６3b075b167a1１7b0０8b068b０６9a032ａ074ｂ１2６b17６a15８a000b１19a0３3b071b05２a0６2a１２9ｂ１18b104ａ1３4a113a026b04９b091b106b１415161７18１9１98b０81b164b02０a0４7a１36b０14a０5９a06０ｂ1４7a152ａ005a05６b131b１87ｂ０8６b2０0ｂ1４3b０93ａ072ｂ17５ａ09７a0３9ｂ083a070b13９b002a162b２03b090ａ0６4b2０８a142ａ0５7a024a０１3a1３0a163a１93b0７３b159ａ035a188a12７a０40a１82ｂ1２2ａ17２a18０b027a１3５b14１ａ204ｂ105a101ａ015b20５a０82b145a009ｂ100ｂ０５5b1０3a112a1９6b054b表７：对于附件五的碎纸片排列矩阵第二面0１2３456１136a０47ｂ0２0ｂ164ａ081a198a2０05b１５2b147b０6０a059b０14b3143a20０ａ0８６a1８7a131a056a40８３ｂ0３9a09７ｂ１７5ｂ072ａ093ｂ５090b2０3a162a0０2b１3９a０70ａ60１3b０24b0５7b１4２b208ｂ064ａ7035b１5９ｂ073a19３ａ１６３b1３0ｂ８１7２b12２b182ａ０40b127ｂ18８ｂ9１0５b２0４a141b135a027b1８０a100０9ａ145ｂ0８2a205ｂ01５ａ１01b1１０54a１96a112ｂ103b05５a１００a７8910111213０29b018a１08b０６6ｂ１1０b174a1８3a０79b14４b１20ａ０22ｂ124ａ1９2b02５ａ13８ｂ0４5ｂ１37a061b0９4a09８b121b132ａ087b１98a18１ａ034b1５6b20６a0４1ｂ17０a１5１ａ０01a1６6a1１５a065ａ12０a０１７a0１2b0２８a154a19７b15８b02１a２０2b0５3a177a０16a019ａ092a068a00８ａ１１7a167ｂ075ａ063a067b000a1５8b176b12６ａ07４a０３２b０69b118ａ129ａ062b05２ｂ０71ａ0３3a1１9b１０６a091ａ0４9a０26a1１3b１3４b１04b14151617１８1９１50ｂ1５5b14０ｂ１25b1１１a０７8ａ０４4b１78b0７6a０36b010ａ０89b038b030b0４2ａ084a１53ｂ１86a1７3a1９４a169ａ16１ａ011a199ａ191b０37ａ１８0b14９a1０7b08８a0５8b2０7ｂ116a179ａ1８4a11４b19０a０50b２01b0３1b17１a1４６b046b16８b1５７b11８b19５ｂ16５a0０4b０7７b148a0８５ａ007ａ0０3a160a095b05１a０48b1３3ｂ0２３a00６b123b109b０9６a043b０99b六、模型求解结果分析针对问题一的结果进行分析。题目所给出图片量小,图片匹配出的效果好，在相似度的分析中,出现的误差减小。最后拼接出的图像清楚,人工干预量小.针对问题二的结果进行分析。题目给出的图片量较大,相似度分析中出现的误差较大。在聚类分析中设定的参数也相应较大,导致最后的误差较大。量的增长同时也使得人工干预增多，最后拼出图片的效果也相应较低.针对问题三的结果进行分析。在本论文中,基于ＡCA的SIＦT图像特性点分析算法对图片进行匹配，相较于简朴的二值矩阵相似度匹配方法和相关灰度的算法，运营的速度变快,精度增大，匹配的效果较好。但是由于题目给出的图片量较为庞大,导致人工干预增长,使得最后产生的误差增大．七、模型的优缺陷分析7.１模型优点：本文建立的模型比较多,模型计算过程清楚简朴,并且可以通过MＡTLＡＢ快速求解,有比较强的理论性及实用性，通过对模型的分析,验证了其的可靠性,为司法物证复原、历史文献修复以及军事情报获取等提供了方便，相对于人工拼接，节约了时间成本。因此,具有重要的实际意义和较高的应用价值.1、迭代算法使最佳分割阈值不受噪声影响,因此边沿点完全由自身的灰度值拟定,避免了噪声影响范围的扩大。图像阈值分割可以提取完整的图像轮廓,使检测所得边沿具有连续性。数学形态学的腐蚀算法保证了检测得到的边沿仅有一个像素的宽度,边沿定位精确。同时避免了边沿宽度增长而引起邻近边沿的重叠。即使边沿比较模糊,也能通过阈值分割得到增强,运用腐蚀算法能可靠地提取边沿.2、蚁群算法与其他启发式算法相比，在求解性能上，具有很强的鲁棒性(对基本蚁算法模型稍加修改,便可以应用于其他问题）和搜索较好解的能力。蚁群算法是一种基于种群的进化算法,具有本质并行性，易于并行实现。蚁群算法很容易与多种启发式算法结合，以改善算法性能.7.２.模型缺陷:1、邻域平均解决方法是以图像模糊为代价来减小噪声的，且模板尺寸越大，噪声减小的效果越显著.2、Ｓｏｂeｌ算子没有基于图像灰度进行解决，由于Sobeｌ算子没有严格地模拟人的视觉生理特性，所以提取的图像轮廓有时并不能令人满意.八、模型的推广与改善８.1、模型改善相似度计算方法改善本论文第二个问题是采用的二元相似性度量算法分析,上述模型中,我们只讨论了连通像数K=4的情况，现在我们简朴说明连通像数Ｋ＝8的状况．此时,对于一个中间像素点i,它与其八连通像素的关系可以表达为式:可以看到，在K=8时，相似度会更加的精确,考虑时间和效率问题，还是尽量不要采用连通像数K=8的算法.８.2模型推广对于本论文的图片拼接问题,我们将图片进行了图片去噪滤波、膨胀腐蚀、相似度匹配等。这些技术,在生活中具有广泛的应用。类似的研究重要集中在文物碎片的自动修复、虚拟考古、故障分析及计算机辅助设计、医学分析等领域.九、参考文献［１]董汉莉．Marr－Hildreth算子边沿精拟定位的研究[J］.郑州工业大学学报,199９,４.[２]孙慧,等.图像解决中边沿检测技术的研究［J］.电脑开发与应用,2023,15(1０):7－9[3]王郑耀.数字图像边沿检测[D］.西安：西安交通大学理学院，2023.[４]侯舒维.图像拼接技术研究[D]．西安:西安电子科技大学,2０23.[５］万丰.一种全自动稳健的图像拼接融合算法［J］.中国图形图像学报，004．9(4):4１7-422.[６]王磊,莫玉龙,戚飞虎．基理论的边沿提取改善方法[J].中国图象图形学报,1９96．［７］刘金根，吴志鹏.一种基于特性区域分割的图像拼接算法[Ｊ］.西安电子科技大学学报，２023.[8]韩晓军．数字图像解决技术与应用.北京:电子工业出版社,2023[9]MAＬLAＴS.AＴourGuｉdeｏfＳignalＰroｃesｓiｎｇ[M].Ｂeｉjｉｎg：ＭachｉｎeInduｓtrｙPrｅsｓ,2０23.9５-150．附录附件一用Mａtｌab对问题一进行二值化和相似度匹配排序cｌｃｃlｅａr;I=dｉr（'C：\Ｕsｅrs＼hp\Ｄesｋtｏp\ｗc\*.bmp')；imreａd_num=ｌeｎｇth(I);p=strucｔ（＇ｚhａngsｈu','ｉｍreaｄ'，'ｚuｏ'，'you');fｏｒi＝1:iｍreａd_ｎump(ｉ）.zhａｎｇshu=i；ｐ(ｉ).imrｅad＝imread（I(i).ｎame,'bmp＇);aaa=ｐ(i)．ｉmreaｄ；［mｎ]=sizｅ(aaａ);p(i).zuo=ａaａ(：,１)；ｐ(ｉ).you=aaa(：,n)；enｄfori=1:imｒead_numｃcc＝ｐ(i).zｕo；bbb(1,ｉ)＝ｓｕm(ccｃ)；enｄ[ｚｈizｈizhiｔtｔ]=maｘ（ｂbb);qqq＝ttt-1;disｐ(＇最左边那张是?＇);qqq；foｒｊ=１:ｉmread＿nuｍjjj＝ｔtt;youｙou＝ｐ（jjj)．yｏu;zuozuo=p(j）.zｕｏ;sss（１,j)=（1／ｍ)*sｕm((zuoｚｕｏ-youｙou)．＾２);end[zｈizｈｉｔtt]＝min(sss);ttｔ-1；用Matlａb对附件一和附件二中的碎纸片排序拼接代码附件一碎纸图片拼接代码Ｉ１=imread('008．ｂｍp');I2=imread（'014.bmp＇）；I３=ｉmrｅａd('012.bｍp');I4=ｉmread（'015．bmp');Ｉ５＝iｍread('003．bmp＇);I6=imrｅad('01０.bmｐ'）;Ｉ7=iｍreａd(＇00２.bmｐ');Ｉ8=imｒead(＇０1６.ｂmp');I９=ｉmｒead(＇001.bmｐ'）;Ｉ10=imｒｅad('０04.bmp');I１1=imreａd('0０5.ｂｍｐ');I12=iｍread(＇0０9．bmp＇);I13=imrｅａd('013.ｂmｐ');I1４=imread('0１8.ｂmp'）;I1５=imｒeａｄ('011．ｂmｐ');Ｉ16＝iｍreａd('0０7.bmp＇)；I17=imread（'０17.bmｐ'）;I18＝iｍread('000．ｂmp');I１9=imread（'006.ｂmp')；I=[Ｉ1,I2,I3,I4,I5，Ｉ6,I７,I8，I9,Ｉ１0,Ｉ１1,I12,I１3,I１4，Ｉ1５,I16，I１7,Ｉ18,Ｉ1９];ｉmshow(Ｉ)（附件2的拼接代码同上，将排序号改换即可)附录图一：附件一碎纸片拼接结果附录图二：附件二碎纸片拼接结果附件二Mａｔlab进行碎纸片边沿化解决和相似度矩阵求解cｌccleａrallｆori=０:208d｛i＋1｝＝imreａｄ(sｔrcat('C:maｔhmｏdel\AS\',num2ｓtr（i，＇%03ｄ＇),＇.bmp'));d｛i+1}=ｉｍ２bw（d{ｉ+1})ｅndＴmａtrix＝zerｏs（1１,19);TCol＝zｅrｏs(１1,19);lｅｆtEdge=12;TopEdge＝37;Tｍａxtrix(1，１)=50；colｓｐａn=6;rowspaｎ＝28;TUｓeｄ=zｅｒoｓ(1,209);TUseｄ（50）＝1;cｏunｔ＝１;TCol(1,1）=５0;foｒｊ=1:lｅｎgtｈ(TＵsｅd)if（TUsed（j)~=1)ｔemｐTotal=suｍ(sum（d｛j}（1:１8０，1:lefｔEdgｅ)）);if(ｔｅmpTotａl==１８０*leｆtEｄgｅ)ＴＵsed(j）=1;cｏunt=ｃｏunt+1;TＣoｌ(couｎt,１)=j;endｅndeｎdfoｒi=１：１1foｒl=1:18mａｘcount＝０;forj=1:209iｆ(ＴUsed（j）~=1)coｕnt=0;samｅspaｎ＝0；ｋ=UｐBracｋet(d{ｊ});if(i＝=1)ｉｆ（UpBraｃｋet（ｄ{j})＞=TopEdge)rｅt=ＲiｇhｔBｒａｃket(ｄ{TＣol(i,l)}）;if(reｔ～=0)if（ＲigｈｔBrackeｔ（d｛TCol（i，ｌ)})＋LｅfｔBrackｅｔ(d{j}＝=ｃｏlspａn))ｓamｅspａn=samｅspan+1;TCol(ｉ,l+1)=j;ｉｆ(sａmｅsｐan>1)ｐauseendbreａk;endelｓecount=simstat(ｄ{ＴCol（i,l)},d{j});ｉf(count>ｍaxcounｔ)TCol(ｉ,ｌ+1)=jmａxcounｔ=count;ｅｎdendendelset1＝TＣol(ｉ,l);ｉf(UpBrａckeｔ(d{ｔ1}）=＝UpBracｋet(d{j}))ｉｆ(RigｈtBｒacket(ｄ{TCol(i,l)｝)~=０)m＝TCol（i,ｌ）；n＝ＲiｇhｔBrａckeｔ(d{m})+LefｔBracket(d{ｊ｝)ｉｆ(n==colsｐan)TCｏl(i,l+1)=j;ｅndｅｌseｃoｕnt=simstat(d{TＣol(i，l）｝,d{ｊ｝)if(ｃouｎt>maｘcounｔ)TＣoｌ(i,l＋1)=j;maxcount=coｕnt;ｅndeｎdｅndendendenｄteｍp=TCol(ｉ,l+1)；ＴUsｅd(tｅmp）＝１；endｅndMａtlａb进行搜索排序拼接碎纸图片的代码I=dｉr('．＼*．bmp');im＿ｎｕm=lengtｈ(Ｉ）;im_ｔｅｍp=iｍreaｄ(I(１).nａｍe,'bmp');[hｅｉght,widｔh]=size（im＿ｔemp);ＤB(:,：,a)=zeｒos(heiｇht,wｉdｔh,im_ｎum,'uint8');fora=1:length(I）DB(:,:,a)=imreaｄ（I(a)．ｎame,'ｂmp');enｄif（isgｒay(I)==0)disp（'请输入灰度图'）;eｌseｉf(size(I)~=[1２８，1２8])disｐ