2013高教社杯全国大学生数学建模竞赛-B题论文资料.doc

碎纸片的拼接复原摘 要本文利用Manhattan距离，聚类分析，图像处理等方法解决了碎纸片的拼接复原问题。由于碎纸机产生的碎纸片是边缘规则且等大的矩形，此时碎纸片拼接方法就不能利用碎片边缘的尖角特征等基于边界几何特征的拼接方法，而要利用碎片内的字迹断线或碎片内的文字位置搜索与之匹配的相邻碎纸片。拼接碎片前利用数学软件MATLAB软件对碎片图像进行数据化处理，得到对应的像素矩阵，后设置阈值对像素矩阵进行二值化处理，得到相应的0-1矩阵。下面分别对三个问题的解决方法和算法实现做简单的阐述：问题一，分别对附件1和附件2的碎片数据进行处理得到相应的0-1矩阵，依次计算某个0-1矩阵最右边一列组成向量与其他所有0-1矩阵的最左边向量的Manhattan距离，可以得到某个最小距离值、说明最小距离值对应的碎片是可与基准碎片拼接的，最终得到碎片拼接完整的图像。问题二，同样对于附件3和附件4中的碎片数据进行处理得到相应的数值矩阵，并计算得到每个碎片顶部空白高度和文字高度，即指每行像素点都为255的行数、一行中存在像素点为非255的行数，根据空白高度和文字高度对碎片进行聚类分类，聚类阀值取3像素，得到11组像素矩阵，进而得到11类可能在同一行的碎片类。其中对附件4中的英文的处理中，我们还采用水平像素投影累积的方法，进一步分类出可能在同一行的碎片类。用问题一的方法，计算Manhattan距离可以对每一类碎片按次序排列好，得到11行已经排列好的碎片，再应用曼哈顿距离在竖直方向上进行聚合得到完整的图像。问题三，首先，对于附件5中的碎片数据我们采用正反相接，本文将b面最左边的一列像素拼接到a面最右边的一列像素的下面，构成3601的向量，再把其他的碎片采用相同的办法得到3601的向量，再用问题一的方法，计算出各碎片之间的Manhattan距离。其次，根据每个碎片顶部的空白高度或者文字高度对碎片进行区间分类，得到22组矩阵，然后应用曼哈顿距离将得到的22组矩阵聚成两类，每类各包含两面的11组矩阵，最后利用Manhattan距离在竖直方向上进行聚合得到完整的图像。本文最后，我们根据算法的效率实现进行了改进和优化，实现算法的移植性、灵活性、运行效率等得以提升。关键词：曼哈顿距离，聚类分析，二值化处理一、问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。二、问题分析我们从附件中的碎片数据可知由于碎纸机产生的碎纸片边缘是规则的，此时碎纸片计算机拼接方法就不能利用碎片边缘的尖点特征、尖角特征、面积特征等基于边界几何特征的拼接方法，而要利用碎片内的字迹断线或碎片内的文字内容是否匹配搜索与之匹配的相邻碎纸片并进行拼接。首先，我们对碎片内图像进行数据化处理，得到对应的像素值矩阵；然后，我们设置阈值对像素值矩阵进行二值化处理得到相应的数值矩阵；最后，由于曼哈顿距离公式计算快、数值小，数值矩阵与数值矩阵之间应用最小曼哈顿距离对碎纸片进行拼接复原。 问题一中碎纸机破碎纸片只有纵切，每页纸被切为19条碎片，经过处理可以得到19个数值矩阵。对于每个数值矩阵，我们依次取出最左边一列从上至下各格的值组成一个向量，同样我们依次取出最右边一列从上至下各格的值组成一个向量。计算出每一数值矩阵的左边向量与所有非同源数值矩阵的右边向量的曼哈顿距离，再将得到的距离值进行排序，当某个距离值最小时、说明相应的左边向量与右边向量的匹配率最大，则该距离对应的左、右边认为是可拼接的。若得到的最小距离值不止一个，则此时需要进行人工干预。问题二是对碎纸机既纵切又横切的情形进行讨论，比问题一多了横切条件，此时每页纸被切为209个碎片。首先，我们利用文件最左边碎片与最上面碎片的特殊性对这209个碎片进行聚类，得到两类特殊的碎片，分别是文件最左边一列碎片和最上面一行碎片，然后类似于问题一的处理方法，应用最小曼哈顿距离对每一类碎片按正确顺序拼接，此后对其余碎片再应用最小曼哈顿距离逐一进行拼接，直至剩余所有的碎片都拼接上。问题三中，题目要求考虑双面打印文件的碎纸拼接复原问题的解决方案，此时每页纸虽然也是被切为209个碎片，但每个碎片却有正反两面，因此经过处理得到418个数值矩阵，此时我们分别对每一面各自进行类似问题一的处理，然后综合每一面的聚类情况再应用最小曼哈顿距离对双面碎纸片进行拼接复原。三、模型假设1. 假设碎纸机破碎纸片（纵切或横切）得到的碎纸片是规则且边缘是整齐的等大的矩形； 2.假设我们对文档碎纸片拼接复原不考虑碎片边缘的尖点特征、尖角特征、面积特征等基于边界几何特征； 3.假设附件中给出的所有中、英文文件中的文字排版是按标准格式排版的。4.假设附件中给出的所有中、英文字符都是统一格式，且内容为普通文章。四、符号说明序号符号符号说明1数值矩阵2数值矩阵的最左边列向量3数值矩阵的最右边列向量4曼哈顿距离5隶属函数中的阀值五、模型建立与求解5.1 问题一（曼哈顿距离） 模型一的建立题目要求对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切）建立碎纸片拼接复原模型和算法，并且要对中、英文各一页文件的碎片数据分别进行拼接复原。首先，我们利用数学软件MATLAB软件将19条碎片数据化，得到19个像素值矩阵，像素值的变化范围是从0变化到255，此时我们设置为阈值对像素值矩阵进行二值化处理，当矩阵某位置像素值小于等于时，则将对应位置的数值设为0；当矩阵某位置像素值大于时，则将对应位置的数值设为127。这样我们就得到19个二值化了的数值矩阵，对于每个数值矩阵，我们依次取出最左边一列从上至下各格的值组成一个向量，记为，同样的我们依次取出最右边一列从上至下各格的值组成一个向量，记为。计算出每一数值矩阵的左边向量与所有非同源数值矩阵的右边向量的曼哈顿距离。 模型一的求解对于得到的向量和向量，两向量的曼哈顿距离为。可求出附件1碎片与碎片之间的曼哈顿距离，如下表所示。 表1 附件1碎片与碎片间的曼哈顿距离编号0123456789101112131415161718编号6416105981714132715181231011距离10211748128811130159112120828434777897124102105从而可得到附件1碎片序号按复原后顺序如下表所示。表2 附件1碎片序号复原后顺序8141215310216145913181171706附件1碎片复原图片如附录中图8.1所示。同法可求出附件2碎片与碎片之间的曼哈顿距离，如下表所示。表3 附件2碎片与碎片间的曼哈顿距离编号0123456789101112131415161718编号5976312151213801410171841611距离966582102071671208712882547513310754935290从而可得到附件2碎片序号按复原后顺序如下表所示。表4 附件2碎片序号复原后顺序3627151811051913108121417164附件2碎片复原图片如附录中图8.2所示。问题一人工干预情况如下表所示。 表5 问题一人工干预情况 人工干预图像干预时间干预方式干预次数附件1图像无无0附件2图像无无05.2 问题二（Manhattan距离） 模型二的建立在中文文件中，两个连续的汉字中间的空白间隔所占像素宽度与其左边或者右边的汉字所占像素宽度的比值最大的约为，则对于每一行文字，碎纸机纵切未切到文字的概率为，对于每两行文字碎纸机纵切未切到文字的概率为，而对于每三行文字碎纸机纵切未切到文字的概率更小，可以忽略不计，所以对于总共209个碎片，每个碎片上面的文字至少有两行（碎片上不完整的一行也算一行），所以出现某个碎片上面的文字完全没被碎纸机切割到（即文字完整无缺）的概率至多为，我们把这样的碎片称之为干扰碎片。我们知道，整篇文件的最上面一行字的上边缘是空白的，我们可以利用此特殊性对209个碎纸片进行聚类，可以得到一个特殊的类，即碎纸片上边缘为空白的类，此类碎纸片个数大于等于11；出现个数大于11的情形即为混入上面提到的干扰碎片，此概率最大不超过，可知此类碎纸片应该拼接在文件最上面一行，应用最小曼哈顿距离对此类碎片按正确顺序拼接。同理可聚类出另一个特殊的类，即碎纸片左边缘为空白、拼接在文件最左边一列的类，并且也应用最小曼哈顿距离对此类碎片按正确顺序拼接。然后以此拼接好的第一行和第一列碎片为基准，再应用最小曼哈顿距离拼接其余剩下的碎片，最后拼接复原出原中文文件。在英文文件中，一个英文单词中两个连续的英文字母中间的空白间隔所占像素宽度与其左边或者右边的英文字母所占像素宽度的比值最大的约为，则对于每一行英文单词，碎纸机纵切未切到英文单词的概率为，对于每两行英文单词碎纸机纵切未切到英文单词的概率为，而对于每三行英文单词碎纸机纵切未切到英文单词的概率为， 然后同上述中文文件的分析过程可知，此时对拼接在文件最左边一列归类时混入上面提到的干扰碎片的概率最大不超过，最后拼接复原出原英文文件。 模型二的求解我们利用SPSS软件根据每个碎片顶部空白高度或者文字高度的不同，应用聚类分析方法将碎片聚成11类，结果如下图所示。图1 根据碎片顶部文字高度聚类图2 根据碎片顶部空白高度聚类结合上面的聚类图，可得出附件3的乱序矩阵，如下表所示。表6 附件3的乱序矩阵4922129178118143188192571419119028186254119565617911678722069521631773699961967631621316168179130231421918714762768619518261201004150381677446103148883598241931611051892513012281712052720060851533156170198132172021528316513380141151591281991210717682160733151203169313539134945890149774234112144136124841649747127121183431251318717313966150197182161061811451092111018415720429101041725548171598372065992201644418011175709332561751531661961374520817468158138537012689151114140102207155101146194119411740123108154185113同样的方法可得出附件4的乱序矩阵，如下表所示。表7 附件4的乱序矩阵1911471167204106104218419015465391801497546432201809110119810094626196103113172814878146164170865951117242992581861074615812740983753015019121114578817682194151221551821261411059320271165159203187531120160153853197138129501391236338175201367613536431434117379199179161457320711610815208189168491121181693314211954197616271332119216270236810919560849917490137896156471721412218513216318111025188206279516669178311113034167131441711674134152358355915720542145446656181831081177527248128910214087128125011519377200131124然后我们先求出附件3碎片与碎片之间的曼哈顿距离，从而得到附件3碎片序号按复原后顺序如下表所示。表8 附件3碎片序号复原后顺序4954651431862571921781181909511221292891188141611978676999162961317963116163726177205236168100766214230412314719150179120861952618718381484616124358118912210313019388167258910574711568313220017803320219815133170205851521652760141283159821991351273160203169134393151107115176943484183904712142124144771121499713616412758431251318210919716184110187661061502117315718120413914529641112015921804837755544206101049817217159720813815812668175451740137535693153701663219689146102154114401512071551401851081174101113194119123附件3碎片复原图片如附录中图8.3所示。同法我们再求出附件4碎片与碎片之间的曼哈顿距离，从而得到附件4碎片序号按复原后顺序如下表所示。 表9 附件4碎片序号复原后顺序1917511154190184210418064106414932204653967147201148170196198941131647810391801012610061728146865110729401581869824117150559589230374612719194931418812112610515511417618215122572027116582159139112963138153533812312017585501601879720331204110811613673362071351576431994517379161179143208217496111933142168621695419213311818916219711270846014681741371958471721569623991229018510913218195691671631661881111442063130341311025271781714266205101577414583134551856351691831524481771282001315212514019387894872121771240102115附件4碎片复原图片如附录中图8.4所示。问题二人工干预情况如下表所示。表10 问题二人工干预情况 人工干预图像干预时间干预方式干预次数附件3图像初始化最左边一列纸片需要人工排序图像的最左边一列排序出错的地方进行调整1初次拼接结束后一小部分位置在水平方向出错在程序运行初始化中强制将出错的一个图像安排在水平方向的正确位置2附件4图像初始化最左边一列纸片需要人工排序图像的最左边一列排序出错的地方进行调整1初次拼接结束后小部分位置在水平方向出错在程序运行初始化中强制将出错的一个图像安排在水平方向正确位置45.3 问题三（曼哈顿距离） 模型三的建立问题三在问题二的基础上继续加大碎片拼接复原难度，此时我们对双面碎纸片进行类似问题一的处理，得到418个数值矩阵，我们根据每个碎片顶部的空白高度或者文字高度对碎片进行区间分类，得到22组矩阵，再根据曼哈顿距离将得到的22组矩阵聚成两类，每类各包含某一面的11组矩阵，然后综合每一面的聚类情况再应用最小曼哈顿距离对双面碎纸片进行拼接复原。然后再利用曼哈顿距离对碎纸片在竖直方向上进行聚合得到最终图像。 模型三的求解 问题三的解决方法与问题二的类似，不过我们分两步进行聚类分析。第一步，我们根据每个碎片顶部空白高度的不同进行聚类，第二步，我们根据每个碎片底部空白高度的不同进行聚类。然后我们选取第一、二步聚类产生的公共类，若得到的公共类数量小于22类，则再从单独由第一步聚类产生的类中选取，直到数量达到22类。对于这22类碎纸片，我们再利用问题二的方法聚成两组，每组数量都为11类。后面类似模型二的处理过程，结果顺序如下表所示。表11 附件5某一面碎纸的初次拼接位置078b153a036a157a030a058a025b179a166b061b165b043a096b051b194b160b069a115b071b077b186b184b161a042b050a150a065b174b074b026b199b195a048a169b095a173b158a033b034a066a088b010b085b140a155a006a121a098a113a001b114a007b149b148b037b191a067a134a094b028b146a107a179b180a123a038a104a192a124b181b089a011b031a076b077a046a206b063b075b022a033b171b084b109a178a044a183b156a110a052a023b111b128a116b207a004a119a019b016b167a099a133a125a201a168a190b092b032a154b126b 053b091a102b189b131b142a162b122a172a108a017b029a056b055b175a182b159a005a198b087a079a080b139b002a097a024a090a137b185a021b070b059a164b057a145a013a062a144a132b093a208a205a086b200b143b176a018b068b101a081b193b141a152a136b120b129b000b188a027a103a112a203b105a049b008b041a130a127a060b020a196b009b151b202a118b064b015b135b147a039b083a117b045a138a014a163a187b082b047a054b012a170b106b100b072b040a073b204b035a表12 问题三最终拼接结果078b111b125a140a155a150a183b174b110a066a089a010b036a076b178a044a025b192a124b022a186b153a084b042b030a038a121a098a094b061b199b011b161a169b194b173b206b156a034a181b088b107a149b180a037b191a065b115b166b001b114a184b179b116b207a058a158a197a154b028b146a171b031a201a050a190b092b019b016b177b 165b195a128a157a168a046a067a063b075b167a003b007b085b148b077a004a069a032a074b126b023b133a048a051b095a160b119a033b071b052a099a043a096b109a123a006a104a134a113a026b108a018b029a189b081b164b020a047a136b120b144a079a014a059a060b147a152a005a137b045a138a056b131b187b086b200b143b198b087a132b093a072b175a097a039b083a151b170b041a070b139b002a162b203b090a012a017b102b064b208a142a057a024a013a053b202a021b130a163a193b073b159a035a117b008b068b188a127a040a182b122a172a176a185a000b080b027a135b141a204b105a062a129b118b101a015b205a082b145a009b049b091a106b100b055b103a112a196b054b同理，剩余的图像矩阵可以组成另一面的文章。问题三人工干预情况如下表所示。 表13 问题三人工干预情况 人工干预图像干预时间干预方式干预次数附件5图像初始化最左边一列纸片需要人工排序图像的最左边一列排序出错的地方进行调整9初次拼接中间，一小部分位置在竖直方式方向出错在程序初始化时强制将出错的一个图像安排在竖直方向正确位置4初次拼接结束后小部分位置在水平方向出错在程序初始化时强制将出错的一个图像安排在水平方向正确位置3六、模型的评价与推广1.模型的评价对于问题一，由于题目中给的样本较为简单，所以模型一能很好的解决附件1、附件2给出的中、英文文件碎纸片拼接复原问题。对于问题二，模型二也能较好的解决问题，但模型二也有不足之处。比如模型二只考虑根据每个碎片顶部的空白高度和文字高度对碎片进行区间分类，分为11组矩阵。而没有综合考虑每个碎片顶部与底部的空白高度和文字高度对碎片进行区间分类，因此分类准确率降低。对于问题三，由于每个碎片都有正反两面，而且模型三对碎片聚类时只对每一面单独进行分析，所以模型三解决问题时错误匹配的数量明显多于前面两题。因此，我们除了挖掘算法潜力，还能对模型三做出进一步的改进，比如对碎片聚类时综合对两面进行分析以及对某面分析时综合考虑已经排好顺序的第一行与第一列碎片等都能进一步优化模型，减少错误匹配的数量，提高效率，增加模型的适应性。2.模型的推广我们建立的模型在处理碎纸片较大且碎纸片数量不是很多的时候，模型可以较好的解决问题，但在实际应用中，通常会涉及碎纸片被切割得很细很小，并且要对大量碎纸片数据进行管理和处理工作。所以我们要进一步优化算法和程序结构，改善模型，真正建立起快速有效的计算机辅助碎纸片自动拼接复原模型，从而才能将此模型广泛地应用到我们的实际生活中。七、参考文献1. 张翠. 基于点线的文档图片数字水印与碎片拼接D. 青岛:中国海洋大学, 2011. 26-34。2. 张艳. 图像拼接技术在文档图像扭曲识别中的应用与研究D. 北京:北方工业大学, 2011. 23-29。3. 贾海燕, 朱良家, 周宗潭, 胡德文. 一种碎纸自动拼接中的形状匹配方法J. 计算机仿真, 2006, 23(11): 180-183。4. 汪晓银, 邹庭荣. 数学软件与数学实验M. 北京: 科学出版社,2008. 1-27。5. 张铮,杨文平,石博强,李海鹏.Matlab程序设计与实例应用M.北京:中国铁道出版社,2003.276-306。6. 姚文敏. 数字图像处理M. 北京:机械工业出版社, 2006. 24-45。八、附录图像拼接结果图8.1 附件1碎片复原图片 图8.2 附件2碎片复原图片图8.3 附件3碎片初次拼接结果图图8.4 附件3碎片复原图片图8.5 附件4碎片初次拼接结果图图8.6 附件4碎片复原图片图8.7 附件5碎片复原图片一面图8.8 附件5碎片复原图片另一面程序源代码问题一function Q1() %处理问题1的相关程序clear all;close all；clc; %清理显示屏幕var=0;N=18; m=0;n=0;pi=0;pj=0;% %导入图像部分 for i=0:N if(i<10) filename=sprintf(00%d.bmp,i); %构造需要导入的文件名字 else %而相应的文件存放在工作目录中 filename=sprintf(0%d.bmp,i); %构造需要导入的文件 end I=imread(filename); %导入图片文件 Imi+1=I; %将变量Im用cell格式存放数据，后续调用这个变量 end m n=size(I); %提取矩阵的行与列 for i=0:N IMi+1=im2bw(Imi+1); %Im变量中所有的图像数据进行二值化 i=i+1; end%for i=0:N subplot(1,N+1,i+1) imshow(Imi+1); %显示没有经过处理时候的情况end%for i=0:N var=-1; for j=0:N if(i=j) if(var=-1) var=sum(abs(IMi+1(:,72)-IMj+1(:,1); pi=i; pj=j; else if(sum(abs(double(IMi+1(:,72)-doubl