《一种单张文件碎纸片拼接的方法.doc》由会员分享，可在线阅读，更多相关《一种单张文件碎纸片拼接的方法.doc（29页珍藏版）》请在三一办公上搜索。
1、2013高教社杯全国大学生数学建模竞赛 承 诺 书 我们仔细阅读了全国大学生数学建模竞赛章程和全国大学生数学建模竞赛参赛规则（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和
2、参赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： （论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。） 日期： 年 月 日 赛区评阅编号（由赛
3、区组委会评阅前进行编号）：2013高教社杯全国大学生数学建模竞赛 编 号 专 用 页 赛区评阅编号（由赛区组委会评阅前进行编号）： 赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注 全国统一编号（由赛区组委会送交全国前编号）： 全国评阅编号（由全国组委会评阅前进行编号）： 一种单张文件的碎纸片拼接的方法摘要在司法物证复原、历史文献修复、医学生物组织或细胞切片观察以及军事情报获取等领域，破碎文件的拼接技术起到了很重要的作用。随着计算机技术的发展，使得破碎文件的拼接的方法有了突破性进展，计算机软件的开发为破碎文件的拼接复原节省了很多人力。针对单张文件的碎纸片拼接复原问题，基于图像像素统计的方法，
4、提出了纵向最优匹配模型、横向最优匹配模型、单面快速分类模型、双面快速分类模型，有效地对将一页纸文件被碎纸机切割成若干条碎片，进行拼接复原；对于单张文件被碎纸机经过水平和竖直方向切割成若干个碎片的拼接复原问题，首先采用快速分类模型，进行分类，并对每一类碎片按照纵向像素吻合度进行横向拼接，对于部分拼接异常的碎片，进行人工调整，然后，对每一横条碎片，按照横向像素吻合度进行纵向拼接，最后，对于纵向拼接异常的碎片再进行人工干预，得到了完整的复原图像，特别是双面印刷的单张文件也能快速拼接复原。结果表明，对于单面或者双面印刷的单张文件的拼接复原问题，采用计算机编程统计、分类、拼接、复原，加上人工干预，能快速
5、地得到复原的图像。基于像素统计的方法可以推广到规则碎片的拼接复原之中。关键字：最优匹配；快速分类；像素吻合度；拼接；C#语言 1. 问题重述 1.1 问题背景分析生活中人们偶尔会遇到粘合撕碎重要票据或纸币的情况，此时数量较小，可以根据其上的文字、形状、纹理、色彩等可以很快将他们拼接成功。但是当他们数量达到成千上百时，如果仍然依靠手工完成不但耗费大量的人力物力，还可能对碎片造成一定的损坏，而且这种繁琐的劳动力在短时间内是很难完成的。破碎文件的拼接技术能够帮助采集许多非常重要的信息，考古学家遇到的古代留下来的破碎珍贵文物，公安机关破案遇到的破碎照片，司法技术鉴定工作遇到的大量破碎纸质证物，保密机构
6、获得的破碎的重要文献和图片，珍贵破碎艺术品等等，靠全人工拼接是相当困难的。碎片匹配仍然是学术研究的前沿问题，这个问题研究成功会开辟诸多新的应用领域，促进模式识别等多种学科的发展，所以随着计算机技术的进步，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。1.2 问题的提出 问题1 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。问题2 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和
7、算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。问题3 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。2. 问题分析 分析问题：针对问题一：对于同一页印刷文字文件等分纵切成19条，一种文字是中文，一种文字是英文，利用计算机辅助方法，将19条碎片进行拼接复原。分析其特点：（1）这19条碎片
8、来自于同一页面，没有多余的信息和缺损的信息；（2）这19条碎片组成的页面，具有确定的左边距、右边距、上边距和下边距，字号全文统一，行间距相同，字符的颜色都是黑色。（3）这19条碎片仅是字符，不含有图。针对问题二：对于同一页印刷文字文件等分纵切成19条，每条等分横切成11块，形成了1119 209块碎片。一种文字是中文，一种文字是英文，利用计算机辅助方法，将209块碎片进行拼接复原。分析其特点：（1）这209块碎片来自于同一完整页面，没有多余的信息和缺损的信息；（2）这209块碎片组成的页面，具有确定的左边距、右边距、上边距和下边距，字号全文统一，行间距相同，字符的颜色都是黑色。（3）这209块
9、碎片仅是字符，不含有图。针对问题三：对于同一张正反面印刷文字的文件等分纵切成19条，每条等分横切成11块，形成了1119 209块碎片。文字是英文，利用计算机辅助方法，将209块碎片进行拼接复原。分析其特点：（1）这209块碎片来自于同一张完整的纸张，没有多余的信息和缺损的信息；（2）这209块碎片正反面组成了两个完整的页面，每个页面具有确定的左边距、右边距、上边距和下边距，字号全文统一，行间距相同，字符的颜色都是黑色。（3）每张碎片具有正反面两幅图像的信息，相当于518张图，两两相贴构成了209块碎片。（4）这209块碎片仅是字符，不含有图。 3. 模型假设1（1）假设经过碎纸机切过的每张碎
10、纸片外围轮廓不存在弯曲或锯齿状,是标准矩形，切缝平行于纸张边界，且与字符的行平行或者垂直；（2）假设所给碎片属于同一张完整纸张，碎片没有多余部分或者不完整部分；（3）假设所给碎片属于正常黑白打印文件的一部分，且具有左边距、右边距、上边距和下边距；（4）假设所给碎纸片上只是文字、字符，没有图像；（5）假设同一纸张所印刷的字符，其字号、字体相同，且行间距相同；（6）假设所给碎片无字符区域计算机读出像素值为255，有字符区域读出像素值小于255。4. 符号说明 ：第i张碎片图像的像素矩阵；(j)：表示第i张碎片图像，从左向右按列读取出现“0”前的像素列数j；Bj(i)：表示第j张碎片图像，从上向下按
11、行读取出现“0”前的像素行数i；ai：表示第i张碎片图像第一列中像素值为“0”的个数；bi：表示第i张碎片图像最后一列中像素值为“0”的个数；Iij=|bi - aj|：表示“像素吻合度”，即两边缘对应像素值为0个数的差值的绝对值；ci：表示类型“1”中第i张碎片图像首次出现字符信息前的全为1的像素行数；di：表示类型“0”中第i张碎片图像首次整行出现全为1前的像素行数；ei: 表示类型“d1”中第i幅图像按行从下向上首次出现字符信息前的全为1的像素行数；fj：表示类型“d0”中第i幅图像按行从下向上首次整行出现全为1前的像素行数； 5. 模型建立5.0 纸片信息预处理对扫描所得的纸片图像的处
12、理过程是：二值化处理。利用C语言编制程序2-6，读取图像中每个像素的像素值，将像素值为255的像素用“1”表示，其余用“0”表示。即灰度图像变成了黑白图像。5.1 问题一模型的建立及求解对于给定的来自于同一页的印刷文字文件，经碎纸机破碎后，纸片在仅进行纵切，形成了19条碎片，要求建立碎纸片拼接复原模型和算法7-8。对于附件1中提供的19条内容为中文的纵切碎片，要求拼接成完整的页面。针对这一问题，首先对图片进行二值化预处理，得到了19幅黑白图像。其次，建立纵向最优匹配模型，第一、利用C语言编制程序，从左向右按列读取每幅图像信息，判断每幅图像首次出现字符信息前的全白像素列数，最大的为左边界。第二、
13、将左边界图像的最后一列的信息与剩余的所有图像的第一列信息进行比较，最匹配的优先，然后将这两幅图像组合成新的左边界，依次类推，最后组合成整幅图像。纵向最优匹配模型步骤一：利用C语言编制程序，从左到右按列读取每个碎片图像的左边首次出现“0”前的列数(j)，比较(j)的大小，值最大的为左边界图像。步骤二：将左边界图像的最后一列的信息与剩余的所有图像的第一列信息进行比较，按照像素个数吻合度，最匹配的优先，具体地说，相同的优先，相差1的其次，依次类推，然后将这两幅图像组合成新的左边界。步骤三：将新的左边界图像，与剩余的所有图像的第一列信息进行比较，最匹配的优先，依次类推，直至组合成整幅图像。附件1拼接结
14、果如表5.1-1所示。表5.1-1 附件1拼接结果编号表008014012015003010002016001004005009013018011007017000006对于附件2，内容为英文的碎纸片，对于这一拼接问题，其模型及算法步骤同内容为中文的附件1相似。附件2拼接结果如表5.1-2所示。表5.1-2 附件2拼接结果编号表0030060020070150180110000050010090130100080120140170160045.2 问题二模型的建立及求解对于给定的来自于同一页的印刷文字文件，经碎纸机破碎后，纸片经过纵切和横切，形成了1119209块碎片，要求建立碎纸片拼接复原模
15、型和算法。对于附件3中提供的209块碎片，其内容为中文，要求拼接成完整的页面。针对这一问题，首先对图片进行二值化预处理，得到了209幅黑白图像。其次，建立单面快速分类模型，利用C语言编制程序，从上到下按行读取每幅图像的信息，先将第一行所有像素为1的设定为类型“1”，其他为类型“0”，进行粗略分类；对于类型“1”统计出每幅图像首次出现字符信息前的全白像素行数，对于类型“0”统计每幅图像首次整行出现全为1前的字符像素的行数，将209块碎片分成11个类。接着，对于第i类，利用纵向最优匹配模型，进行横向拼接。最后，对于已经拼接好的11条横向碎片，按横向最优匹配模型进行纵向拼接，完成整幅图的拼接。单面快
16、速分类模型步骤一：利用C语言编制程序，从上到下按行读取每幅图像的信息，先将第一行所有像素为1的设定为类型“1”，其他为类型“0”；步骤二：对类型“1”中的图像，统计每幅图像首次出现字符信息前的全白像素行数ci，对类型“0”中的图像，统计每幅图像首次整行出现全为1前的字符像素的行数dj。步骤三：将类型“0”和类型“1”中所有图像按ci和dj的大小区间分成11个类。横向最优匹配模型步骤一：利用C语言编制程序（见附录XX），从上到下按行读取每条碎片图像的上边首次出现“0”前的行数Bj(i)，比较Bj(i)的大小，值最大的为上边界图像。步骤二：将上边界图像的最后一行的信息与剩余的所有图像的第一行信息进
17、行比较，按照像素个数吻合度，最匹配的优先，具体地说，相同的优先，相差1的其次，依次类推，然后将这两幅图像组合成新的上边界。步骤三：将新的上边界图像，与剩余的所有图像的第一行信息再进行比较，最匹配的优先，依次类推，直至组合成整幅图像。在附件3中的209块碎片，按照单面快速分类模型分类结果如表5.2-1所示。表5.2-1 附件3的单面快速类结果类型0000001111111距离范围3-415-1722-2627-3134-3540-426-812-1618-2114-2737-418393个数191919191914192317181911存在着特殊情况，需要人工干预，例如编号为029的图像与编号
18、为064、编号为111、编号为201等图像，本属于同一类，但是按单面快速分类模型，编号为029的图像粗分为类型“1”，而其他粗分为类型“0”，需要最后手工拼接。如图5.2-1所示。除此以外，由于汉字的特殊性，像“一”、“三”等，出现字高较低，例如编号为030的图像与编号为041等图像，相差4个像素行数；编号为095的图像与编号为190等图像，相差4个像素行数。一般相差03个像素行。因此对于个别图像需要人工分类。图5.2-1 分类异常情况下拼接的结果图附件3拼接结果如表5.2-2所示。表5.2-2 附件3拼接结果编号表049054065143186002057192178118190095011
19、022129028091188141061019078067069099162096131079063116163072006177020052036168100076062142030041023147191050179120086195026001087018038148046161024035081189122103130193088167025008009105074071156083132200017080033202198015133170205085152165027060014128003159082199135012073160203169134039031051107115
20、176094034084183090047121042124144077112149097136164127058043125013182109197016184110187066106150021173157181204139145029064111201005092180048037075055044206010104098172171059007208138158126068175045174000137053056093153070166032196089146102154114040151207155140185108117004101113194119123附件4中提供的209块碎
21、片，其内容为英文，其模型及算法步骤同内容为中文的附件3相似。在附件4中的209块碎片，存在着特殊情况，需要人工干预。例如编号为053编号为187、编号为203与编号为031、编号为139等图像不同，本属于同一类，但是由于英文字母中“y”、“j”的“下尾巴”较长，按快速分类模型，粗分为不同的类型，需要最后手工拼接。附件4拼接结果如表5.2-3所示。表5.2-3 附件4拼接结果编号表1910750111541901840021041800641060041490322040650390671472011481701961980941131640781030910801010261000060170
22、281460860511070290401581860980241171500050590580920300370461270191940931410881211261051551141761821510220572020711650821591390011290631381530530381231201750850501601870972030310200411081161360730362071350150760431990451730791611791432080210070490611190331421680621690541921331181891621971120700840600
23、140681741371950080471721560960230991220901851091321810950691671631661881111442060031300340131100250271781710420662050101570741450831340550180560350160091831520440810771282001310521251401930870890480720121771240001021155.3 问题三模型的建立及求解对于给定的来自于同一张双面印刷文字的文件，经碎纸机破碎后，纸片经过纵切和横切，形成了1119209块碎片，每块碎片包含正反面两面的信息
24、，构成了21119418幅图像，要求建立碎纸片拼接复原模型和算法。对于附件5中提供的209块碎片418幅图像，其内容为英文，针对这一问题，首先对图片进行二值化预处理，得到了418幅黑白图像。其次，建立双面快速分类模型，利用C语言编制程序，对418幅黑白图像从上向下按行读取每幅图像的信息，先将第一行所有像素为1的设定为类型“1”，其他为类型“0”，再根据同一块碎片的a, b两面的类型，粗略地分为“00”、“01”和“11”三类，再对类型“1”中的图像，统计每幅图像首次出现字符信息前的全白像素行数ci，对类型“0”中的图像，统计每幅图像首次整行出现全为1前的字符像素的行数dj。然后对“01”粗类，
25、按ci和dj分成若干类，再对“00”型和“11”型相对分为若干类。接着，对于第i类，利用纵向最优匹配模型，进行横向拼接。最后，对于已经拼接好的11条横向碎片，按横向最优匹配模型进行纵向拼接，完成整幅图的拼接。双面快速分类模型步骤一：利用C语言编制程序，对418幅黑白图像从上向下按行读取每幅图像的信息，将第一行所有像素为1的设定为类型“u1”，其他为类型“u0”；步骤二：对于类型“u1”中的图像，统计每幅图像中首次出现字符信息前的全为1的像素行数ci，对于类型“u0”中的图像，统计每幅图像首次整行出现全为1前的像素行数dj；步骤三：根据同一块碎片的a, b两面的类型，粗略分为“u00”、“u01
26、”和“u11”三类，因为a, b面可以互换；步骤四：先对“u01”粗类，按ci和dj分成若干类，再对“u00”粗类和“u11”粗类相对分为若干类；步骤五：对于没有办法确定类的碎纸片，利用C语言编制程序，对其图像从下向上按行读取每幅图像的信息，将最后一行所有像素为1的设定为类型“d1”，其他为类型“d0”； 步骤六：对于类型“d1”中的图像，统计每幅图像中首次出现字符信息前的全为1的像素行数ei，对于类型“d0”中的图像，统计每幅图像首次整行出现全为1前的像素行数fj；步骤七：根据同一块碎片的a, b两面的类型，粗略分为“d00”、“d01”和“d11”三类，因为a, b面可以互换；步骤八：先对
27、“d01”粗类，按ei和fj分成若干类，再对“d00”粗类和“d11”粗类相对分为若干类。附件5拼接结果如表5.3-1和表对于类型“d1”中的图像，统计每幅图像中首次出现字符信息前的全为1的像素行数ei，对于类型“d0”中的图像，统计每幅图像首次整行出现全为1前的像素行数fj；5.3-2所示。表5.3-1 附件5“He”开头的拼接结果编号表136a047b020b164a081a189a029b018a108b066b110b174a183a150b155b140b125b111a078a005b152b147b060a059b014b079b144b120a022b124a192b025a0
28、44b178b076a036b010a089b143a200a086a187a131a056a138b045b137a061a094a098b121b038b030b042a084a153b186a083b039a097b175b072a093b132a087b198a181a034b156b206a173a194a169a161b011a199a090b203a162a002b139a070a041b170a151a001a166a115a065a191b037a180b149a107b088a013b024b057b142b208b064a102a017a012b028a154a197b1
29、58b058b207b116a179a184a114b035b159b073a193a163b130b021a202b053a177a016a019a092a190a050b201b031b171a146b172b122b182a040b127b188b068a008a117a167b075a063a067b046b168b157b128b195b165a105b204a141b135a027b080a000a185b176b126a074a032b069b004b077b148a085a007a003a009a145b082a205b015a101b118a129a062b052b071a0
30、33a119b160a095b051a048b133b023a054a196a112b103b055a100a106a091b049a026a113b134b104b006b123b109b096a043b099b表5.3-2 附件5“what”开头的拼接结果编号表078b111b125a140a155a150a183b174b110a066a108a018b029a189b081b164b020a047a136b089a010b036a076b178a044a025b192a124b022a120b144a079a014a059a060b147a152a005a186b153a084b042
31、b030a038a121a098a094b061b137b045a138a056b131b187b086b200b143b199b011b161a169b194b173b206b156a034a181b198b087a132b093a072b175a097a039b083a088b107a149b180a037b191a065b115b166b001b151b170b041a070b139b002a162b203b090a114a184b179b116b207a058a158a197a154b028b012a017b102b064b208a142a057a024a013a146a171b031
32、a201a050a190b092b019b016b177b053b202a021b130a163a193b073b159a035a165b195a128a157a168a046a067a063b075b167a117b008b068b188a127a040a182b122a172a003b007b085b148b077a004a069a032a074b126b176a185a000b080b027a135b141a204b105a023b133a048a051b095a160b119a033b071b052a062a129b118b101a015b205a082b145a009b099a043
33、a096b109a123a006a104a134a113a026b049b091a106b100b055b103a112a196b054b6. 模型评价6.1 模型的优缺点对于一张纸片水平与竖直分割成若干块碎片，都是需要先进行横向快速分类，将同一行的碎片分在同一类，然后在同一类中的若干块碎片进行拼接；拼接的原则是先判断左边界的图像，然后以左边界图像的最后一列出现字符信息的像素点个数与其他同类中的每幅图像中的第一列出现字符信息的像素点个数，相比较，相同的和相差个数最少的为优先，然后将左边界的图像与优先的图像进行拼接，成为新的左边界图像，再与剩余的同组图像进行比较、拼接，将每一类的碎片图像拼接完成
34、，出现不正常的情况，采用人工干预。最后将完成的同一行碎条，进行纵向快速分类，先统计出上边界图像，再按上边界图像的最后一行，出现字符信息的像素点个数与其他每幅图像中的第一行出现字符信息的像素点个数，相比较，相同的和相差个数最少的为优先，然后将上边界的图像与优先的图像进行拼接，成为新的上边界图像，再与剩余的图像进行比较、拼接，出现不正常的情况，采用人工干预。因此，该模型能广泛地应用于各种字符类、同行距，具有确定的上下左右边距，字体相同的正常印刷的纸面文件碎面的拼接工作。其优点是快速、准确。6.2 模型的改进与推广（1）模型分析了五个问题，这些碎片要么是中文、要么是英文，对于中英文混排也可以采用计算
35、机辅助统计信息的人工干预法，来完成复杂图像碎片的拼接工作。（2）对于图文排的文件，需要改进用C语言编制的程序，同样可以采用计算机辅助统计信息的人工干预法，来完成复杂图像碎片的拼接工作。（3）对于字号大小不统一，需要改进用C语言编制的程序，同样可以采用计算机辅助统计信息的人工干预法，来完成复杂图像碎片的拼接工作。（4）对于斜切的碎片和大小不一碎片，甚至形状不同的碎片拼接问题，需要具体问题具体分析。 参考文献 1 司守奎, 数学建模算法与应用M, 北京: 国防工业出版社, 20112 罗智中, 基于文字特征的文档碎纸片半自动拼接J, 计算机工程与应用, 48(5): 207-210, 20123
36、丁迎, 洪继光, 图像拼接中伪匹配的判别和消解J, 中国图像图形学报, 1999, 4(10): 886-8904 唐证, C#项目开发全程实录, 北京: 清华大学出版社, 20085 姚领田, 精通MFC程序设计M. 北京: 人民邮电大学出版社, 20066 罗斌, C#.NET精彩编程实例集锦M, 北京: 中国水利水电出版社, 20057 陶波, 于志伟, 图像的自动拼接J, 中国生物医学工程学报, 1997, 16(4): 29-138 贾海燕, 碎纸自动拼接关键技术研究D, 长沙: 国防科技大学, 2005【附录一】纵向最优匹配模型程序using System;using System
37、.Collections.Generic;using System.ComponentModel;using System.Data;using System.Drawing;using System.Linq;using System.Text;using System.Threading.Tasks;using System.Windows.Forms;namespace B_图片拼贴 public partial class Form1 : Form private static int Height = 1980; private static int Width = 72; priv
38、ate static int TotalWidth = 72 * 19; private string openFile = ; private string saveFile = result.bmp; private Bitmap ResultBitmap = new Bitmap(TotalWidth, Height); private int isFileValid = new int19; public Form1() InitializeComponent(); for (int i = 0; i 19; i+) isFileValidi = 1; private void but
39、ton1_Click(object sender, EventArgs e) int current; /当前的块数编号 char current_right = new charHeight; /当前完成块的右侧数组情况 int finish = 0; /已经完成的块数 Bitmap bitmap; Color pixel; for (int i = 0; i 19; i+) int count = 0; string open = E:StudySourcesC语言类我的CSharp工程数学建模B_图片拼贴B_图片拼贴sources0 + (i 10 ? 0 : ) + i.ToString() + .bmp; bitmap = (Bitmap)Bitmap.FromFile(op
