《基于灰度像素理论的碎纸片拼接方法数学建模论文1.doc》由会员分享，可在线阅读，更多相关《基于灰度像素理论的碎纸片拼接方法数学建模论文1.doc（32页珍藏版）》请在三一办公上搜索。
1、基于灰度像素理论的碎纸片拼接方法摘要 常规的二维碎片拼接技术一直受到科研领域重视，它在司法鉴定、文物修复、图像处理等领域有着广泛的应用。本文研究的是二维碎片拼接技术中最典型的文档类碎纸片拼接问题。基于文档纸片色彩明确、方向一致、无重叠等特点，利用灰度理论对问题作出解决。通过图形扫描得到图像，然后通过二值化， 梯度算进行预处理，并运用皮尔逊相关性度量及方差分析算法进行匹配，以实现对纸片进行还原。本文通过MATLAB程序模型，以及图片像素灰度理论实现文档碎片的重新拼接。对于问题1，应用图像处理技术中的灰度理论建立了灰度模型I。在对得到灰度模型进行梯度边缘化预处理的方法进行模型改进，建立了边缘灰度模
2、型II。然后借助于皮尔逊相关系数算法和MATLAB软件，对附件中所提供的碎片进行排列拼接。对于问题2，采用化归思想，将二维问题渐变为一维问题。首先归纳碎片特征运用MATLAB软件对碎片进行同行分类，得到11行19列的元素；采用方差分析算法和人工干预对各行中元素进行排列，得到11条横切的图形；采用方差分析算法和人工干预对其进行排列，得以还原。本文的亮点在于对各行中元素采用方差分析算法进行左侧到右侧匹配后，同时增加了右侧到左侧的匹配检验，大大减少了人工干预的工作。关键字： 灰度理论；皮尔逊相关系数算法；梯度边缘化；方差分析算法；人工干预一、问题的重述问题一、对于给定的来自同一页印刷文字文件的碎纸机
3、破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。问题二、对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。问题三、上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模
4、型与算法，并就附件5的碎片数据给出拼接复原结果。二、模型的假设1.所修复的文章必须是一张完整的文章，碎片一定可以拼接成功，并且文章纸张完整；2.碎纸片的几何尺寸完全相同，边缘清晰，且碎片中字体一致无残缺；3.在检测是否匹配时，不存在实际中不相接的碎片但匹配度相对较高的情况。4.附件中数据真实可靠。三、符号说明四 问题分析问题一的分析：4.1通过对附件1、附件2进行分析，碎片在外观形状上并无差异，所以若对碎片进行重新匹配，可以简化为对碎片边缘进行匹配。考虑先运用MATLAB中的函数将数据以像素灰度模型（gray-scale model）的形式进行读取。通过对结果和附件的观察不难发现，每片碎片列边
5、缘像素特征较为明显，因此，可以通过比较样本碎片左边与其他待测碎片的右边相关性(Correlation coefficient)大小，得到最近拟合碎片，对右边也进行类似处理。这里采用皮尔逊相关系数理论作为相关性检测的基准。选取相关性度量最高值，可以得到正确的排序序列。最后运用MATLAB中的函数将拼接后的图像进行输出。问题二的分析：4.2.1.与一维的区别和联系I.区别：1）需要匹配边数由二到四；2）一边上可用于检测匹配程度的像素点大幅减少；3）段落的首尾会影响检测时的判别。II.联系：1）都可以应用灰度理论转化为数值矩阵后进行分析；2）可以转化为一维问题，可先化成若干横条，然后11个横条进行匹
6、配或先化成若干纵条，然后19个纵条进行匹配。4.2.2.二维碎片的图像分析由图4.2.1可以发现，行间形成的空白区域可视作一条直线，列间形成的空白区域可视作为曲折的直线。并且行间距大于列间距，因此碎片的左右两侧更不容易在碎片中出现白边，白边属于分析匹配程度时的一种特殊情况，会提高分析难度，应尽量避免。另外，由于碎片上下两侧的像素点少于左右两侧，故在单边进行匹配时上下比较更容易出现错误。先成一列的难度较大，先成行较简单，并且成行后横向像素点将增加很多，易于提高成功率，有效减少人工干预。图4.2.14.2.3.归纳可能为一行的所有特征，进行编程监测以得到11行数据。采用方差分析算法对这些数据内部的
7、每列进行排序，得到11条横切的图形。然后采用方差分析算法和人工干预对其进行排列。问题三的分析：采用类似于问题二的方法对正反面分别排序，将不完整的正反面图进行覆盖，得到较完整图，然后进行人工干预，填入少量未识别碎片，得到拼接结果。五、模型的建立与求解问题一 本题考虑到文本图片有别于一般图像，具有色彩稳定，无光照因素扰乱，同时不存在碎片旋转、变形以及遮挡的因素，所以运用基于图像灰度的图像配准方法就能完美得解决文本图片的自动化拼接问题。5.1.基于灰度理论求解模型对碎片进行拼接5.2对图像建立灰度模型灰度（Gray scale）数字图像是每个像素只有一个采样颜色的图像。这类图像通常显示为从最暗黑色到
8、最亮的白色的灰度，尽管理论上这个采样可以任何颜色的不同深浅，甚至可以是不同亮度上的不同颜色。灰度图像与黑白图像不同，在计算机图像领域中黑白图像只有黑白两种颜色，灰度图像在黑色与白色之间还有许多级的颜色深度。但是，在数字图像领域之外，“黑白图像”也表示“灰度图像”，例如灰度的照片通常叫做“黑白照片”。在一些关于数字图像的文章中单色图像等同于灰度图像，在另外一些文章中又等同于黑白图像。其实际颜色越接近白色，灰度值越接近255；越接近黑色，灰度值越接近0。对附件1中19图片进行编号，分别为基于灰度理论得到附件1中19张碎片的0-255像素灰度图矩阵。运用算子提取各碎片样本的左列与右列边缘数列，标记为
9、矩阵。算子的表示：梯度幅值：用卷积模板来实现：1.2相关性度量选取碎片左右列后，需要对碎片进行重新排序，此处，进行各碎片边缘相关性度量。采用皮尔逊相关系数对相关性进行分析。两个变量之间的皮尔逊相关系数定义为两个变量之间的协方差和标准差的商：以上方程定义了总体相关系数, 一般表示成希腊字母。基于样本对协方差和标准差进行估计，可以得到样本相关系数, 一般表示成： 一种等价表达式的是表示成标准分的均值。基于的样本点，样本皮尔逊系数是：其中 简单的二维皮尔逊相关系数是两项间的差是每个变量值差的平方和再平方根，目的是计算其间的整体距离即不相似性，其中为样本量，分别为两个变量的观测值和均值。描述的是两个变
10、量间线性相关强弱的程度。的取值在-1与+1之间，若表明两个变量是正相关，即一个变量的值越大，另一个变量的值也会越大；若表明两个变量是负相关，即一个变量的值越大另一个变量的值反而会越小。的绝对值越大表明相关性越强。对每一组数据进行相关系数比较可以清楚的得出最有拟合组。例如：通过MATLAB可视化显示与拟合度最高的是即图片与相邻。图5.1.1 由上图可见，相关系数越大，说明指标性质越接近。由于碎片均是正向放置，所以令分别于进行相关性度量分析，对做同样处理，即可得到新序列。附件一结果 08141215031002160104050913181107170006 根据序列排序讲碎片进行重新匹配。考虑到
11、自动化批量处理，下面，通过程序来实现。程序流程图如下：图5.1.2 程序流程图注释：Ci，j代表第i个向量与第j个向量的相似度的值。运用MATLAB软件实现程序。重新匹配后的的图片见附录。图片贴合度满意，基本达到要求。再对附件2中碎片运用此算法进行重新排序并进行拼接。重新匹配后的的图片见附录。由此可见，本算法具有一定的可行性，符合题设要求。程序见附录。拼接结果：附件一结果 08141215031002160104050913181107170006附件二结果 03060207151811000501091310081214171604问题二本题是在问题一的基础上的延伸及复杂化，对一中的纵切结果
12、加以横切。同样，应用灰度理论模型，对各个方块碎片进行重新匹配。1. 碎片灰度化处理，提取边缘数列一、 得到特定行1.流程图2.说明此时，每一行内的各列尚为乱序，运行该程序后通过查找可知这些行内部的碎片序号。如下表所示。07324553566870931261371381531581661741751962081182326304150627686871001201421471681791911952112228495457659195118129141143178186188190192312143139517382107115128134135159160169176199203440891
13、011021081131141171191231401461511541551851942075102937444855596475929810411117117218020120661920365261636769727879969911613116216317789242535384674818810310512213014816116718919313162166106109110125139145150157173181182184187197204151727336071808385132133152156165170198200202205344243475877849094971
14、121211241271361441491641833.程序见附录二、行内排序1.流程图2.说明此时，每一行内各列得到排序，但由于白边和逗号出现，使得单向检测存在很大偏差。故当出现以上两种情况时，记录出现情况的位置，再倒序检测匹配到那个位置，情况会得到好转。3.人工干预得到各行内正确的列序1）部分不需要更改，如第四行图看着上图，进行人工干预。记下应如何修改，再找到变量后进行调序，存储即可。4.方差匹配方差分析（ANOVA）即F检验,是通过分析研究中不同来源的变异对总变异的贡献大小，从而确定可控因素对研究结果影响力的大小。总变量(TSS)：为组别为观测值个数(j=1,2,3,.,J)， 为第i组
15、第j个观测值， 为所有观测值的平均数。组间变异量(BSS)：为i组内观测值总数，为第i组的平均数组内变异量(WSS)：当WSS=0时，代表各组内的所有观测值与各组的期望值没有差异存在，因此只有WSS与BSS都为0情况下，才能断定所有观测值达到完美的一致，然而当WSS0, BSS=0的情况，则是各组期望值达到一致，但组内却存在变异，WSS=0, BSS0，则是组内没有变异存在，但各组间却存在差异，然后真实状况不可能如此极端，因此必须比较WSS与BSS的差异来判断方差分析的结果，也就是各组期望值是否有差异存在。而这个部份在比较变异量的过程中，必须考量均方值来比较组内变异与组间变异量。组间均方BMS
16、S： = 组内均方WMSS： = 其中k为组别数量，N为观测值总数。两个均方值的比较为:此比较值也就是目前惯称的F检定值，F越大，则组间均方大于组内均方，也就是组间变易量大于组内变异量，各组间的差异远超出总期望值离差，代表各组的平均数存在明显的差异，相反的，F越小甚至于逼近于0，则是组间变异量小于组内变异量，代表各组间的差异很小，各组平均数则不存在明显的差异。5得到行内正确排序附件三序列720813815812668175451740137535693153701663219616810076621423041231471915017912086195261871849546514318625
17、719217811819095112212928911881411412831598219913512731602031691343931511071151768914610215411440151410111319411920715514018510811712329641112015921804837755544206101049817217159611978676999162961317963116163726177205236381484616124358118912210313019388167258910574125131821096618411018719716106150211
18、731571812041391457115683132200178033202198151331702058515216527609434841839047121421241447711214997136164127584312345678910111213141516171819三、 对行进行排序1. 流程图2. 将上表输入后，得图。经检验，此算法对附件四同样可行，以下为附件四的拼接序列附件四结果191751115419018421041806410641493220465396714720114817019619894113164781039180101261006172814686511
19、072940158186982411715055958923037461271919493141881211261051551141761821512257202711658215913911296313815353381231201758550160187972033120411081161367336207135157643199451737916117914320821749611193314216862169541921331181891621971127084601468174137195847172156962399122901851091321819569167163166188
20、1111442063130341311025271781714266205101577414583134551856351691831524481771282001315212514019387894872121771240102115问题三此问是建立在问题二的基础上进行的。由于纸张为双页面，可以考虑每次排序仅考虑一页进行，匹配过程中，某一碎片被确定，则其另一面碎片数据自动从待求碎片库中移除。由此对问题二中程序进行改造，可以得到正面大部分碎片序列，将它们拼接起来，得到正面局部图。对反面进行相同的算法，实现程序，得到反面局部图，然后将两图进行覆盖，相互填补，得到较为完整的正反面图，但是仍有少数空
21、缺电脑难以确定。此时根据语法结构，进行人工干预，得到结果图及序列。附件五正面序列 136a047b020b164a081a189a029b018a108b066b110b174a183a150b155b140b125b111a078a005b152b147b060a059b044b079b144b120a022b124a192b025a044b178b076a036b010a089b143a200a086a187a131a056a138b145b137a061a094a098b121b038b030b042a084a153b186a083b039a094b175b081a093b132a087
22、b198a181a034b156b206a173a194a169a161b011a199a090b203a162a002b139a070a041b170a151a001a166a115a065a191b037a180b149a107b008a013b024b057b142b208b064a102a017a012b028a154a197b158b058b207b116a179a184a114b035b159b071a193a163b130b021a202b051a177a016a019a092a190a050b201b031b171a146b172b122b182a040b127b188b068
23、a008a117a167b075a063a067b046b168b157b128b195b165a105b204a141b135a027b080a000a185b176b126a074a032b036b004b077b148a085a007a003a009a045b082a205b015a101b118a129b062b052b071a033a119b160a095b051a048b133b023a054a196a112b103b055a100a106a091b049a026a113b134b104b006b123b109b096a043b099b附件五反面序列 078b111b125a140
24、a155a150a183b174b110a066a108a018b029a189b081b164b020a047a136b089a010b036a076b178a044a025b192a124b022a120b144a079a044a059a060b147a152a005a186b153a084b042b030a038a121a098a094b061b137b145a138a056b131b187b086b200b143b199b011b161a169b194b173b206b156a034a181b198b087a132b093a081b175a094a039b083a008b107a149
25、b180a037b191a065b115b166b001b151b170b041a070b139b002a162b203b090a114a184b179b116b207a058a158a197a154b028b012a017b102b064b208a142a057a024a013a146a171b031a201a050a190b092b019b016b177b051b202a021b130a163a193b071b159a035a165b195a128a157a168a046a067a063b075b167a117b008b068b188a127a040a182b122a172a003b007
26、b085b148b077a004a036a032a074b126b176a185a000b080b027a135b141a204b105a023b133a048a051b095a160b119a033b071b052a062a129a118b101a015b205a082b045a009b099a043a096b109a123a006a104a134a113a026b049b091a106b100b055b103a112a196b054b六、 模型的评价推广本文模型通过检验基本解决题设问题，但是在图形处理方面灰度理论仍然存在较大的缺陷，如对非线性光照图片比较敏感，对旋转、覆盖情况敏感，计算量高
27、等。在算法上，关联度定义的改进，基于文字的特征尽可能设计出反映正确匹配的有效指标，提高指标精度。但是本模型就碎纸机纸片拼接，复原准确率高，自动化程度高，通用性较高，可以较完美的解决该类问题。碎纸片拼接技术看似像儿时我们做过的游戏，但是却有及其重要的理论价值，它在司法鉴定，文物修复，图像处理中都有这个极大应用价值，同时，根据碎纸片拼接灰度理论原理，可以应用与人类基因组计划中对DNA遗传序列的匹配与连接。所以，该技术的理论意义远大于本文所涉及内容，推广价值极高。七、参考文献1 姜启源，数学模型（第二版），北京：高等教育出版社，19922 刘振航，数学建模，北京：中国人民大学出版社，20043 罗智
28、中，基于文字特征的文档碎纸片半自动拼接，2012,48（5）：207-2104 刘金根，吴志鹏.一种基于特征区域分割的图像拼接算法J.西安电子科技大学学报，2002，29（6）：768-7715 韩煜.基于颜色和纹理特征的计算机自动拼图研究D.首都师范大学.20086吉奥丹诺(等著)，叶其孝(等译)，数学建模，北京：机械工业出版社，2009.7 李志刚，纪玉波，薛全；边界重叠图像的一种快速拼接算法J;计算机工程；2000年05期8 汪华琴.基于特征点匹配的图像拼接方法研究D.华中师范大学.20079 余洪山，王耀南；一种改进型Canny边缘检测算法J;计算机工程与应用；2004年20期9De
29、Smet P.Semi-automatic Forensic reconstruction of ripped-updocumentsC/10th International Conference on Document Analysisand Recognition，2009：703-707.八、 附录附件一附件二附件三附件四附件五程序：得到每特征行元素：picclassclcclear%读取附件2中数据bm=cell(1,209);s3=.bmp;for i=0:9 s1=00; s2=num2str(i); s=s1 s2 s3; bm1,i+1=imread(s); end for i
30、=10:99 s1=0; s2=num2str(i); s=s1 s2 s3; bm1,i+1=imread(s);end for i=100:208 s1=num2str(i); s=s1 s3; bm1,i+1=imread(s);end %LAST ROWpicnumber=zeros(1,19); picturenumber=zeros(11,19);everyrow=cell(1,19);picture=cell(11,19); A=0,7,32,45,53,56,68,70,93,126,137,138,153,158,166,174,175,196,208; 1,18,23,26
31、,30,41,50,62,76,86,87,100,120,142,147,168,179,191,195; 2,11,22,28,49,54,57,65,91,95,118,129,141,143,178,186,188,190,192; 3,12,14,31,39,51,73,82,107,115,128,134,135,159,160,169,176,199,203; 4,40,89,101,108,113,114,117,119,123,140,146,151,154,155,185,194,207,102; 5,10,29,37,44,48,55,59,64,75,92,98,104
32、,111,171,172,180,201,206; 6,19,20,36,52,61,63,67,69,72,78,79,96,99,116,131,162,163,177; 8,9,24,25,35,38,46,74,81,88,103,105,122,130,148,161,167,189,193; 13,16,21,66,106,110,125,139,145,150,157,173,181,182,184,187,197,204,109; 15,17,27,33,60,71,80,83,85,132,133,152,156,165,170,198,200,202,205; 34,42,
33、43,47,58,77,84,90,94,97,112,121,124,127,136,144,149,164,183; for ii=2:2; for j=1:19 everyrow1,j=bm1,A(ii,j)+1; %将组合的单元转化为矩阵 picnumber(1,j)=A(ii,j); end %m,n=size(everyrow1,1);%判断矩阵大小bbone=ones(m,1);bb=255*ones(m,10);for k=1:19 %找到第一碎条并交换到第一行 tt=everyrow1,k(:,1:10); if tt=bb %把图片交换到第一行 t=everyrow1,1;
34、 everyrow1,1=everyrow1,k; everyrow1,k=t; %交换图片编号 l=picnumber(1,1); picnumber(1,1)=picnumber(1,k); picnumber(1,k)=l; endendfor k=2:19 %找到最后一个碎条并交换到最后一行 tt=everyrow1,k(:,n-9:n); mmm=everyrow1,k(:,n-20:n-11); if tt=bb if mmm=bb else %把图片交换到最后一行 t=everyrow1,19; everyrow1,19=everyrow1,k; everyrow1,k=t; %
35、交换图片编号 l=picnumber(1,19); picnumber(1,19)=picnumber(1,k); picnumber(1,k)=l; end endend% for k=1:18 %对中间过程进行排序,由前往后排 tt=everyrow1,k(:,72); xintt=round(double(tt)./255); mmin=sum(xintt-round(double(everyrow1,k+1(:,1)./255).2); for l=k+2:18 mm=round(double(everyrow1,l(:,1)./255); ss=sum(xintt-mm).2); i
36、f ssmmin mmin=ss; t=everyrow1,k+1; everyrow1,k+1=everyrow1,l; everyrow1,l=t; %交换图片编号 ll=picnumber(1,k+1); picnumber(1,k+1)=picnumber(1,l); picnumber(1,l)=ll; end endend % for k=1:18 %对中间过程进行排序 tt=double(everyrow1,k(:,72); mmin=sum( (tt-double(everyrow1,k+1(:,1) ).2 ); for l=k+2:18 mm=double(everyrow1,l(:,1); ss=sum(double(tt-mm).2); if ssmmin mmin=ss; t=everyrow1,k+1; everyrow1,k+1=everyrow1,l; everyrow1,l=t; end endend %找出差别较大的排列row1=zeros(1,18);for k=1:18 piclastcol=round(double(everyrow1,k(:,72)./255); picfirstcol=round(double(everyrow1,k+1(:,1)./255);
