2013数学建模论文

21关于碎纸片拼接复原技术模型的探究摘要图像拼接技术是计算机视觉领域的一个重要分支。它是一种将多幅相关的重叠图像进行无缝拼接从而获得宽视角全景图像的技术。本文针对关于碎纸片拼接复原问题，建立了基于边缘的相位相关图像匹配算法模型以及Hausdorff距离算法模型，在一定程度上对碎纸片进行了拼接复原工作。解决了传统上，拼接复原工作需由人工完成，准确率较高，但效率很低的问题。针对问题一，运用基于边缘的相位相关图像最优匹配模型算法，利用matlab软件中的imread函数读取被切边缘像素索引值，根据图片像素灰度值，通过Hausdorff距离算法进行图像配准，涉及相关算法，解决问题一中规则的碎纸片拼接问题。针对问题二，所给碎纸片相对于在问题一基础上又进行横切处理先运用问题一的数学建模思想，把碎纸片左右两端首先进行拼接复原，完成之后再进行上下边缘的拼接复原工作，所需原理与问题一相同。然后人工干预，把未能拼接的碎纸片用人工拼接复原。针对问题三，所给的碎纸片为A,B正反对应，首先对B进行旋转处理，旋转之后将B的上沿与相应的A的下沿进行黏合，形成新的图像。之后读取新图像的边缘像素索引值，按照上述问题二的方法进行拼接。关键字：规则图像拼接基于边缘相位相关Hausdorff距离灰度值一、问题的重述图像拼接技术是计算机视觉领域的一个重要分支，它是一种将多幅相关的重叠图像进行无缝拼接从而获得宽视角全景图像的技术。在现在社会中破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。本文尝试解决以下问题：（1）对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。（2）对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。（3）上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果。二、模型假设（1）模型中假设本题中每个附件的文字部分完整，字迹清晰，没有阴影重叠或断片情况。（2）假设每个附件的纸张图片无破损。（3）图片位置没有上下颠倒（即文字是正向）（4）如果纸张在油墨覆盖的部位切断，附着在纸上的油墨也会被扯开，模型假设在断裂处排除油墨丢失的情况。（5）模型中假设不考虑碎纸片被切边缘的噪声因素。三、符号说明M：表示每个碎片四周的灰度值特征；H：表示图像左侧的灰度值向量；D：表示右侧灰度值向量；T：表示上侧灰度值向量；B：表示下侧灰度值向量；S：表示灰度值向量差的绝对值。模型建立以及求解4.1问题一的模型建立和求解对于问题一给出的碎纸机破碎文件（纵切）的拼接复原问题，目前应用最广泛的是图像拼接技术，图像的拼接只要处理相邻两幅图像样本之间的重叠部分，图像拼接技术有多种方法，其中最为常用的是基于图像特征的方法，考虑到问题一中碎纸片是由碎纸机破碎的规则文本，被切边缘无论是从文本字体特征上还是纸张特征上来说应该在某些方面具有一定的相似性。为此我们采用基于边缘特征灰度值分析的方法。4.1.1基于边缘的相位相关图像匹配算法：边缘相位相关图像匹配算法在本文中指：分别提取19个碎纸片中保持不变的特征M，它的特征是由这个图片上下左右四个边缘的灰度值来决定的，则M可表示为:M={Hx,Dx,Tm,Bx}(n为第n个碎片)其中H表示碎片左侧灰度值向量；D表示右侧灰度值向量；T表示上侧边缘灰度值向量；B表示下侧灰度值向量。然后用这些特征点集进行匹配对应，生成一组对应特征点集，我们通过距离识别中的一个基本概念，具有几何度量的绝对性和相似度量的相对性。本文中是通过计算图像的灰度值距离来反映碎纸片的匹配程度。我们通过计算像素数组之间的距离差的绝对值，绝对值越小，两个碎纸片的匹配度就越高。现定义两个特征点集之间的Hausdorff距离，为H（A,B）=min[(h(A,B)，h(B,A)]；h(A,B)=max（a∈A）min（b∈B）‖a-b‖；有向部分Hausdorff距离hK(A,B)由A中与B的距离第K远的那个点决定：hK（A,B）=Kthmax（a∈A）min（b∈B）‖a-b‖。图像的传统欧式距离：两幅图像想，x,y间距离为：d(x,y)=,m*n被看作图像一个点，每个坐标值对应一个像素的灰度值4.1.2边缘特殊点的相位寻找算法：由于我们实际要拼接复原的碎纸是由一个个像素点组成的，并且这里是边缘规则拼接，故仅需考虑碎纸左右边缘的像素点，那么我们需要根据像素明暗程度的变化，提取出每个碎片边缘的信息。图像预处理由于本题的特殊性，被切边缘是规则的，所以我们只需对碎片边缘像素值进行匹配处理，（由于整个图像像素的明暗程度差别很大，不考虑边界噪声因素。）首先读取19个纵切碎片的左侧边缘灰度值，生成的矩阵M=｛H1,H2,…,H19｝，再读取19个纵切碎片的右侧边缘灰度值，生成的矩阵N=｛D1,D2,…,D19｝，因此我们可以得到每个碎片左右两列边缘像素值，即从H1到H19这19组左侧像素数组和D1到D19右侧像素数组。将得到的边缘像素值矩阵化,把所有碎纸片左侧像素值H1到H19放入同一矩阵H中，得到如下矩阵：H1...H19H=h把所有碎纸片右侧像素值D1到D19放入同一矩阵D中，得到如下矩阵：D1…D19D=（2）图像配准图像配准是一种确定待拼接图像间的重叠区域以及重叠位置的技术，是整个图像拼接的核心。图像配准本文采用的是基于边缘特征的图像配准方法，即通过像素点对构建图像序列之间的变换矩阵，从而完成全景图像的拼接。为了提高碎片配准的精度，本文采用Hausdorff距离的算法对碎片的变换矩阵进行求解与精炼，此算法是描述两组点集之间相似程度的一种度量。记H1点到D点集中距离的最小距离SD(H1)，即SD(H1)=min‖Hi-Di‖，假设一个图片最左边的像素向量为H1，待匹配的一组图像最右边的像素向量组（从D1到D19）为D，可以用SD(H1)，来度量H1和D的匹配程度。例如S(1,1)=(H1-D1)S(1,2)=(H1-D2)…S(1,19)=(H1-D19)得出第一列数据，然后将H中的其他数组作如上运算，得出其他各组数据如下：H1H2H3H4H5H6H7H8H9D11138931309451161031414481009421119552566110609785949D21234231324191265891256523361610002711242311989593527D3127946114084119516105035104745969281224149025682744D41062531276299594512956411333010691111130510320383887D5110732116398100076115677999832230011879210500657564D6120399113365105551124588114916995831226938746581403D78441010634674468114079867094938097898628100D81116071132051091371369761023621113091076059417184629D997181110965116889124112107114786011118839898359823D1011148411862010928812147111806910447212446410150090152D11131031119975221371235861293041063391200879587385307D12100548108018101008123909109337915301136902182862728D13852421192709907411871197789768001066248050635370D1498457115469109007122480117370903871034099571565199D1597912119254758101289518763980236981248316041196D1612306812793411987824331125039110982143326122008110000D1712919029574131162128869131923108750143744111690113372D182699312589111888513491812656610601313060910081589733D191038141212301036701240971227819070811582610456275636H10H11H12H13H14H15H16H17H18H191111189980511830790941122140105724987431200281060589157811160410472112411596125121618105686102069105624119906135541016731048341021461028981080831158638542214639111999153871128103138311206782415114328100510103449114430104020117821040879978082790942161154977537180758103853123565896392465011049311532994013108758105452906751007201139101049280369797626102450346846475530932592813619022966655112936107423116475911951093321093149326510448833594109021113941015939290198493119446275448412511246811162686740115477124432925581049202613112329195686111057115257120771003581046231074359140710819811322610382711780012030211292945671074129498688324103125990977762693299100795944258271598026737348368493927784751222890319928438428310729811013991993106077115402911687474511159811019221352100259745149238618222956978342971984991899562598667126161122828111462119734117695123377114988109707138933127649117107132184121446130916124453113537120944113823131065118371206761180979881310477710207699300908371279921103081093810720511174227268107564105183998477696410529712436798947图表4.1.1（3）图像融合图像融合是图像拼接的另一个关键技术。图像融合是将两幅已配准图像中有用信息综合到一幅图像中并以可视化方法显示的技术。配准后的图像由于分辨率和视角的不同以及光照等因素的影响,有时甚至是多光谱图像之间进行的拼接,在图像拼接的重叠部分有时会产生模糊、鬼影或噪声点,边界处也可能形成明显的拼缝。为了改善拼接图像的视觉效果和客观质量,需要对拼接后的图像进行融合。人工干预:首先分析S矩阵内的数据，发现出现了s中有一个元素为0，此位置是（D7,H9），它所代表的是第七个原始碎片右侧与第九个原始碎片左侧，而从原始碎片可以看出第七个原始碎片为文章最左侧边缘，第九个原始碎片为文章最右侧边缘，详图如下：图表4.1.2根据表格中数据，在每一列比较选取最小值,该最小值所对应的行和列即为左右边缘像素值很相似的两组像素值，则这两个边缘可运用图像融合技术进行拼接复原，按照上表数据可得出碎纸片标号的拼接复原顺序：附件一的结果：附件一碎纸片从左到右19列正确排列顺序如下图所示:008014012015013010002016001004005009013018011015017000006图表4.1.3附件二的结果：附件二碎纸片从左到右19列正确排列顺序如下图所示：003006002007015018011000005001009013010008012014017016004图表4.1.4运用Matlab软件中imshow方法，通过编写及运行程序能够生成全景碎纸片还原图，其中程序代码如附录所示。生成的碎纸片还原全景图如下图所示:图表4.1.5针对问题一给出的英文纵切碎纸片，其原理与中文碎纸片相同，生成的碎纸片还原全景图见附录2所示：图表4.1.64.2对模型一的分析及改进模型二针对问题二所提出的对于既横切又纵切的碎纸片进行拼接复原，实际上是对于问题一的深化，因此我们的整体思路依然是运用基于边缘的相位相关图像匹配算法和Hausdorff距离算法模型来进行。由于计算机数字分析能力具有一定的缺陷，让计算机对碎片进行完全意义上的自动化拼接也几乎不太可能。为保证拼接的准确性，需要在拼接过程中加入人工干预过程。所谓的人工干预过程在本题中即指：因为碎纸片是经过碎纸机既横切又纵切得到的，总共为11*19=209个碎纸片，要想把这209张碎纸片进行拼接复原，我们可以参照问题一所建立的数学模型，运用Hausdorff距离算法模型先对这209个碎纸片进行左右的拼接复原，得到片段的横向条，然后再通过横向条上下边缘的匹配进行纵向复原，最终完成碎纸片的拼接复原，其间可能会出现一些误差，使部分碎片无法拼接复原，此时我们要进行人工干预。模型二的建立及分析具体流程如下所示：4.2.1经过碎纸机既纵切又横切的文件被破碎成11*19个碎纸片，首先对图片预处理，运用matlab软件中的imread函数读取所有碎片四周的像素索引值，不同于问题一的是，要对每个图片读取四个边缘的像素值，分别把四个边缘的数据放入同一矩阵中有：左边缘矩阵H右边缘矩阵D上边缘矩阵T下边缘矩阵B运用模型一的基于边缘的相位相关图像匹配算法模型和Hausdorff算法模型得到如下矩阵：H=D=d1,1首先，我们先要进行碎纸片左右两侧的拼接复原，同样用到Hausdorff算法模型。现在令模版为H1，待匹配图像为D，可以用h（H1,D）来度量H1和D的匹配程度。S(1,1)=(H1-D1)S(1,2)=(H1-D2)…S(1,19)=(H1-D19)得出第一列数据，然后将H中的其他数组作如上运算，得到各步数据。根据表格中数据，在每一列比较选取最小值,该最小值所对应的行和列即为左右边缘像素值很相似的两组像素值，则这两个边缘可运用图像融合技术进行拼接复原。拼接完成后得到了拼接片段，以下是拼接片段中的两个：图表4.2.1这些片段都没能拼接成完整的文本信息，所以每个拼接片段的一端碎片成为此片段的断点处，共有32处。此断点需人工完成，将剩下的未拼接的碎片进行人工拼接。然后，我们再进行碎纸片上下边缘的拼接复原。现在我们定义T,B分别为碎纸片进行左右拼接融合之后形成的横行上下边缘的像素索引值矩阵，令模版为T1，待匹配图像为B，可以用t（T1,B）来度量T1到B的匹配程度。S(1,1)=(T1-B1)S(1,2)=(T1-B2)…S(1,19)=(T1-B19)得出第一行数据，然后将T中的其他数组作如上运算，得到各步数据。根据表格中数据，在每一列比较选取最小值,该最小值所对应的行和列即为上下边缘像素值很相似的两组像素值，则这两个边缘可运用图像融合技术进行拼接复原。由于此过程不能使全部碎纸片复原，按照上述方法即可得到最终附件三的拼接复原顺序表为：049054065143186002057192178118190095011022129028091188141061019078067069099162096131079063116163072006177020052036168100076062142030041023147191050179120086195026001087018X1148X2X3X4X5081189122103130193088167025008009105074071156083132200017080033202198015133170205085152165027060014128003159082199135012073160203169134039031051107115176094034X6183090047121042124144077112149097136164127058043125013182109197016184110187066106150021173157181204139145029064111201005092180048037075055044206010104098172171059007208138158126068175045174000137053056093153070166032196089146102154114040151207155140185108X7004101113194119123图表4.2.2上表中标注的红色数据为未能拼接完整，需由人工进行拼接还原剩余的7个碎纸片,经人工拼接完成后可以得到完整的碎纸片还原图像：图表4.2.3对于英文的附件4来说，由最终形成的断点数据来说，最终是有29个断点，这些断点需有人工拼接完成，最终拼接完整的还原图见附录。4.3模型三的建立及求解在模型三中，给出的是一页英文印刷文字双面打印文件的碎片，一个切割边缘的灰度值则有A,B两面的两组，将000B选转之后，得到000B’，则它之前的最左侧数组变为最右侧数组，那么000A与000B’按如图连接，得到一个新的用图象00AB，则00AB最右侧的数组即为000说明如下：旋转旋转 000A000B000B’000A000A000B图表4.3.1将附件5中的处于正反两面的（a,b）都进行上述处理，同样每组正反两面的两个碎片可得到一个新的图像，每个新图像最右侧的灰度值即为向量K。然后读取每个新图像的矩阵，之后结合问题一和问题二的模型进行处理如下：用矩阵H储存每个新图像矩阵左边缘数列（即第一列）用矩阵D储存每个新图像矩阵右边缘数列（即最后一列）然后运用Hausdorff距离的算法对碎片的变换矩阵进行求解与精炼/r