基于灰度矩阵的中文碎纸片的拼接复原算法_王欣洁

《基于灰度矩阵的中文碎纸片的拼接复原算法_王欣洁》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3卷第6期智能计算机与应用Vol．3No．62013年12月INTELLIGENTCOMPUTEＲANDAPPLICATIONSDec．2013基于灰度矩阵的中文碎纸片的拼接复原算法王欣洁(太原科技大学应用科学学院，太原030024)摘要:主要对碎纸片的拼接复原问题进行分析，分别对仅纵切和横纵切两种切割方式建立了模型进行求解，主要思想是对碎片的灰度值矩阵进行处理，利用文字所处的位置信息、空格的分布情况、碎片的边界信息(文字的链接情况)等信息，对所给的碎纸片进行拼接复原。对2013年“高教社杯”大学生数学建模竞赛B题附件中的中文碎片进行拼接，拼接效率高，算法可行。关键词:灰度值矩阵;差异

2、度量;贪心算法;相容性;边界特征中图分类号:TP312文献标识码:A文章编号:2095－2163(2013)06－0095－04ChineseScrapsofPaperＲeconstructionAlgorithmbasedonGrayMatrixWANGXinjie(collegeofappliedscience，Taiyuanuniversityofscienceandtechnology，Taiyuan030024，China)Abstract:Thispaperanalyzesthereconstructionproblemofthescrapsofpaper，andestabl

3、ishesthemodeltosolvethever-ticalcuttingandaspectcutting．Themainideaistodisposegrayvaluematrixoffragmentforresconstructingthescrapsofpaperusinglocationinformationofthetext，thespacedistributionandtheboundaryinformation(theConnectionoftext)offragmentandsoon．Afterthat，thepaperalsoreconstructstheBprob

4、lemdataof“HigherEducationPressCup”Undergrad-uateMathematicalmodelingCompetitionin2013，theSplicingefficiencyishigh，andthealgorithmisfeasible．Keywords:GrayValueMatrix;DifferenceMeasurement;GreedyAlgorithm;Compatibility;BoundaryCharacteristics0问题提出对于仅纵切的情形，各碎片的边界特征信息(文字的链破碎文件的拼接在司法物证复原、历史文献修复以及军接情况)

5、较为丰富，故可以利用边界特征进行拼接复原。首事情报获取等领域都有着重要的应用。为了提高拼接复原先根据左侧的第一张碎片通常存在着左边的页边距的特点，效率，人们试图利用计算机，实现碎纸片的自动拼接。本文即其灰度值矩阵中左边几列的元素均为255，从而可以找出对2013高教社杯全国大学生数学建模竞赛B题中提出的碎排在左边的第一张碎片。对于仅纵切的规则图形的拼接问纸片拼接复原问题进行研究，主要研究其中中文碎片的拼接题，只需考虑横向连接，由于纵切产生的边界特征信息较多，［1］复原。在此引入相邻的两幅碎片的边界差异度量。ijii1模型假设和符号说明定义1:设A和A均为r×l矩阵，akm为矩阵A中第jj

6、研究前，需要做出如下假设:假设所给碎片均无噪声污k行m列元素，akn为矩阵A中第k行n列元素，称r染;各碎片之间互有关联;并且只考虑打印稿，而不涉及手写ijijdm，n(A，A)=∑

7、akm－akn

8、稿;同时也要假设文件中的文字行间距确定;没有相同的两k=1ij个碎片;以及附件所给碎片的原文件页边距不为零。为矩阵A第m列与A的第n列的差异度量，其中1≤k≤r，iji本文中用到的符号如下:1≤m，n≤l。特殊地，用d(A，A)表示矩阵A最后一列与ijA:第i个碎片图像的灰度值矩阵;A的第1列的差异度量。iakm:第i个碎片图像的灰度值矩阵中第k行m列元素;2．2横纵切问题的分析ijd(A，

9、A):两矩阵的列差异度;对于纵横切的情形，在增加横切之后，两图片边界处共N1:附件1、2碎片个数;同信息量大大减少，故需要更进一步地挖掘可用信息。汉字N2:附件3、4碎片个数;是方块字，每个字所占的位置基本都是一致的，均可以填在F:复原序列;一个“田”字格中。(r)ijd(A，A):两矩阵的行差异度;首先找出排在左侧的11张图片，可以判定两碎片中汉1SＲ:排在左侧的第Ｒ张碎片;字所在位置位于同一行的图片应该拼接在同一行中，将这样GＲ