13年全国数学建模竞赛-2013试卷

页赛区评阅（由赛区评阅前进行赛区评阅记录（可供赛区评阅时使用（由赛区送交前评阅（ 评阅前进 基本准则。研究了图像边缘特征的表示与提取、相似性度量方法。用碎片足之处，采用Spearman秩相关检验方法度量任意两个边缘的相似度。Spearman需要解决的问拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行二、，256位的灰度图，共有256级，变成黑白图像后，只有2级，这个需要定义一个值，和图像碎片预处理两个过程,而这两个过采用的方法将直接影响到碎片匹配过程的准确性。在的像素已经固定的情况下，碎片数字化精度一定的时候，二维图将碎片复原成原来的样子，如果复原的结果不能让看到复原对象的真正，那的复原就没有意义。Ⅰ、特征的提一个整体成的两个碎片，那么两个碎片裂口对应的部分的颜色（对灰度图像而本模型需要拼接的碎纸片均为规则矩形，朝向全部一致。所以不需要考虑其外形与图形的旋转问题。对于给定待拼接，因其像素固定，所能提取的最大数据已经01，也就是将整（0.5Ⅱ、相似性度量方每个矩形的宽度是一致的，那么每条边的信息矩阵为

计算尽量简单，对于图像边缘的信息矩阵的距离度量函数D应该尽量计算简单，xiRi来代替xi做统计推断。在实际运用中有三种被经常使用，这就是Pearson相关系数r、SpearsonrsKendallX和Y的线性关系，H0X和YX和Y是（或正或负）相关的(即双边检验)；②X和Y是正相关的；③X和Y是负相关的。的秩进行比较，记d2(RS)2，把它看成对某种距离的度量。若d2 (RiR)(SiS d 1 (RR)(S(RR)(SS 根据rs的算法，若以碎片的边缘信息矩阵Xi{x1;x2;xn}的每一元素均相等，则rs0，这一情况将导致计算结果溢出，信息矩阵元素全部相等对应了边缘是1（2）的每一条边的边缘信息矩阵有1980个数据，其统计量足够大。开碎片数开碎片数字碎片图像二值化处提取碎片图像边信寻找当前碎右边匹配碎判断右边是否复原图右边拼合两个碎为当前碎边信息相匹寻找复原图最左边碎拼图结利用的边缘信息矩阵的相关性来确定相互的位置关系，这里先寻找复用Spearman秩相关检验方法判据求出其与各的秩相关系数，特别的取相关系数最大的那些值所对应的作为与之拼接的，依次类推。编程（程序见附录）对附件1的求其每张每侧边缘与其它所有边缘的秩相关系数，得到1919矩阵，如表1所示（矩阵中对角线数据是没有意义的，其数值表示一张的左侧边缘与右侧边缘的秩相关系数。表1：附件一19张两侧秩相关系数（对角线数据无意义0123456789012345678910111213右---左左左左左左左左左右1234-5678-9-10111213-14---15161718- 便可知附件1内拼接顺序为：同理，编程（程序同上）对附件2的求其每张每侧边缘与其它所有图片边缘的秩相关系数，得到1919矩阵，如表2所示（矩阵中对角线数据是没有意义的，其数值表示一张的左侧边缘与右侧边缘的秩相关系数219张两侧秩相关系数（对角线数据无意义0 1 2 3 4 5 6 7 8 90 0.1450.162 0.2530.8190.1550.1620.2551 0.1280.204 0.1690.1210.1070.1450.2802 0.1380.142 0.2140.1850.1590.7370.2513 0.0940.206 0.1250.2060.7400.1030.139 0.1990.778 0.1440.1990.1580.1770.124 0.1560.070 0.3040.2700.3430.1970.206 0.1650.163 0.1550.2360.3090.1830.232 0.0980.161 0.1250.2820.0890.1450.107 0.0990.139 0.1250.1740.1160.0260.141右-0.0160.142 0.1740.2260.1210.2020.793右0.7610.107 0.1680.1290.1300.1600.029右0.0620.176 0.2660.3320.0510.2610.266右0.2200.157 0.2420.1930.1290.1920.195右0.1910.204 0.3370.2600.1720.2370.136右0.1450.221 0.2150.2160.2240.3060.135右0.1440.101 0.7500.3220.2070.2210.127右0.1670.066 0.1440.1450.0510.2260.118右0.0350.111 0.1530.1670.2130.2100.253左左左左左左左左左右123456789101112131415161718便可知附件二内拼接顺序为按照拼接顺序编程（程序见附录）将连接起来，得到附件1、附件2复原图，其正确率100%，无需人工干预。横纵切匹（简单从左往右匹配，编程（程序见附录）对附件3的求其每张左右因此，对于1119的碎片，考虑分两阶段来完成1111个横切片。横向拼接样本统计量较小，存在匹配误差，采取分块拼接方法，引入人工干预。附件1方法可一次直接成图，其正确率100%，无须人工干预。A、入手点即思利用的边缘信息矩阵的秩相关性来确定 相互的位置关系，这里不妨先 、、、、、、、、、125、168。特别的取秩相关系数最大的那些值所对应的作为与之拼接的，依次类推，直到右边为边界（这里会出现伪边行长度不是19必然出现差错拼接。在设定的允许差值范围内有第二大秩相关系数、第三大秩相关系数，认为该，通过对表3的分析，大致将拼接按分成以下几类情形：Ⅰ.（一行）首张碎片只能得到2张碎片连续拼接：[007208]、[014128]、[089146]、[049054065]、[061019078]、[168100[080033202198015133170205085152165027[135012073160203169134039031051107115[062142030041023147191050179120086195026001087[029064111201005092180048037075055044206010104098172171[094034084183090047121042124144077112149097136164127058（一行）相同首张碎片使用不同路径的碎片连续拼接(称之为含有歧项)B、歧项的出现及原因由于边界上左右侧边色度值相关性可能会出现有两组或是多组相关度大小极最大值项了，分类综合考虑，这就导致了AⅥ.中所说的歧项的问题。038148046095038148046095C、元素的配对组合与合理性检边界的碎片单元，所以这就要求须对所得到的这些组的碎片组合进行筛选：（ⅰ）列数064111201005092180048075044206010104098172034084183090047121042144112149097136164127（ⅱ）列数和综合A中Ⅳ.Ⅱ.的情形，将他们逐一配对组新的1×19的碎片组合，并将边界信息中检验其吻合度，最终可以轻松筛选得到以下两组列数为19061078067069099162096131079063116163072006177020168076062142030041023147191050179120086195026001们将在歧项的检验和筛选中将连续的碎片组用{}分隔。046｛095｛01022｛139046｛095｛129（a）.｛143186002057192178118190095｛129028091188141；（b）.｛143186002057192178118190095011012139145178｛138045｛000153070166032196（d）.｛143186002057192178｛138158126068175045174000137053056093070166032196（e）.｛143186002057192178｛138158126068175045174｛070166032196D、矩阵的再组和聚Ⅰ、满足1×19的碎片组合4个：[138158126068175045170000137053056093153070166032196]（17块碎片[080033202198015133170205085152165027060]（13块碎片[135012073160203169134039031051107115176]（13块碎片[143186002057192178118190095011022]（11块碎片Ⅲ、中横向碎片（4≤列数[004101113194123]（6块碎片 [083132200017]（4块碎片Ⅳ、短横向碎片（列数[007208]、[024128]、[089146]、[125013]、[071156]；[049054065]、[038148046]。E、元素的再组合与二次配对与短横向碎片或中横向碎片中的边缘信息矩阵做组合并再配对，将组合后的情况用秩相关检验后人工干预判断组合是否合理。由此又得到两个1×19的完整横1×14007208138158126068175045174000137053056093153070166032071156083132200017080033202198015133170205085152165027[049054065043186002057192178118190095011022]203169134039031051107115176]135128之间的相关度太小，所以其中的碎片176置于末端。4：F、逆向分析锁定余项（正难则反由统计显然可以知道对于拼接的复原图，不管是从左往右进行拼接还是从首先同A中的思路和方法，通过很容易就可以找到复原图右边缘中尚161024035081189122193188167182109197016184110187150021173G、综合剩余碎片锁定结 、99、207不妨取碎片003，对其先从右向左查209209拼接的碎片，于是得到：[003159082199]；再逆向查秩相关系数矩阵，发现与完全吻合没有交叉不匹配的现象。同理对于剩余的11项又得到下列匹配：[102154114040151207155140185108117]。的验证表明，这组数据匹配度表5：附件3乱序横切片片进行简单从上往下匹配，得出复原图碎片拼接序号（3复原后顺序。利用画出复原图，校验无误。Ⅰ、首先选定复原图任意一个边界作为初始推导点，利用筛选出边界处的用 表中，结合简单从左往右匹配模型的程序和算法再将行的顺序排出即能较完美地得到原图。表6：附件4乱序横切片序。利用画出复原图，校验无误。双面碎片的人工判断和纠正，同问题一、二中的方法，还是可以利用边界匹配的相关度，通过将这些双面碎纸片分成多个不同列数的行矩阵单元。通过对这些矩阵边界交文件）附表sheettwo中所示，其中被涂颜色部分是完全与实际吻合的纸片组合。1（筛选组合结果样例2（筛选组合结果样例3（筛选组合结果样例举例说明，在附表sheettwo中取一利用 自动筛选出的数据：[5027208a及000b到208b的所有的的顺序为连续自然数1，2，……，418。从而从而上述矩阵中各值对应的为049a026a、113b、134b、104b、006b、123b、数不一的横切片按其边界信息矩阵的大小和分布一次排进一个11×19的表格，有正内容中的文字几乎可以相互接合的情形，所以筛选过程仅依赖计算机根本无法但是最终发现即便如此，文本最终的整体匹配程度依然不高，所以目前阶段仍 模型的优

模型的缺没有探讨阈值划分原理而是直接指定阈值0.5，带来一定误差；五、模型的改模型改进方向为了提高判断精度，有2种方法：方法2-1，在某一个纸样上，先判断0的，然后在缺失部分0的，并方法2-2，在2-1的基础上，可以先统计真实的汉字笔画的，用概率来缺失部分的，用方法的思想生成缺失部分的数字，再对整个配对过程做大量的重复性测试，最后，正确的配对结果一定是中出现频率最多的。针对控制max的算法，写出了配对过程的程序（C++见附录。蒙特卡罗待开发。模型改进方向将每张抽象为由黑点和白点构成的M*N二维数组，则逐行对左边图像的最右Czuo[x][N-1]与右边图像的最左列元素Cyou[x][0]进行比较，只可能有下列两种1）Czuo[x][N-2）Czuo[x][N-1]！=Cyou[x][0]Czuo[x][N-1]与右边图像的最左列元素当为情况1）Czuo[x][N-1]==Cyou[x][0]时，则此行的不拟合度计为0当为情况2）Czuo[x][N-1]！=Cyou[x][0]时，取此白点坐标，并以此行为基准，上下各取3 行，每行沿两交线为中心，向左向右同时依次向前查找到第一组两个相邻但颜色不同（既比较数值不同）的点，取其中的白点（即数值大的点）坐标。根据此7由于时间限制，附录中只给出了不拟合度计算的程序（C++见附录。韩煜，基于颜色和纹理特征的计算机自动拼图研究[D]，首都师范大学，2008 .cn/s/blog_4a0824490100ync4.html，2013.09.14234附件5复原后顺序（其一附件5复原后顺序（其二7.10.0Visual1（2）C=[c1c2c3c4c5c6c7c8c9c10c11c12c13c14c15c16c17c18c19];forj=1:72:1297;%头数据dt(m,i)=corr(C(:,k),C(:,j),'type''Spearman');附件3（附件4）求秩相关系数程序太大，且其原理与附件1（附件2）求秩相关系事项产生的也在上交 1原程序类似，这里就不罗列，具体请查询上交资料。模型改进方法1 //void [],int//int[]为目标矩#include<iostream>#include<string>#include<fstream>usingnamespacestd;int{voidgetArraies(int[],intintselect(int[],inttest[],constint//"constintsize"mightbewrong,pleasekeepaneyeonconstintsize=200;int[size];inttest[size];//setarraiestoZERO{}int {}}void [],int{//youwrite//youwrite//youwrite}int [],inttest[],constint{int//setarraytoZERO{}int//findoutwheretheboneisfor(inti=0;i<size;i++){ {}}parewithothersinttag=0;for(int{intlocation;//Iassume:a255-blankwillNEVERbelocatedbya0-totalblack{}}{return}elsereturn}模型改进方法2的代码#include<stdio.h>#include<conio.h>#include<stdlib.h>#include<math.h>#definep(k)(p+(k)*m)#definepkx(k)intm,n;doubleNeiJi(double*F,double*G,double you[1980][72],intth);voidGetPk(intk);voidGetXiShu(intk);doubleWucha(intk);intzhengjiaowenhe(intzuo[1980][72],