单面英文碎纸片的拼接复原及算法实现

单面英文碎纸片的拼接复原及算法实现

金明娅，孙丹蕾，赵艳，窦霁虹

(西北大学数学学院，陕西西安710127)

摘要：先对碎片文件的边缘轮廓色彩灰度值及所包含内容的格式等进行特征分析，再通过定义差异度指数、高度差建立双目标0-1规划模型，运用聚类分析、MATLAB搜索算法和人工干预等相结合，实现单面文件既被横切也被纵切碎纸片的拼接复原。

关键词：差异度指数；0-1规划；MATLAB软件；聚类分析；高度差

中图分类号：O242

文献标识码：A

文章编号：1004-602X(2015)01-0014-05

收稿日期：2014-11-14

作者简介：金明娅(1993—)，女，陕西安康人，西北大学数学学院2011级本科生。

Abstract：First,this article analyzed the characteristics about the color grey value on the edge of the fragment file outline and the format of the content contained.Then we defined difference index, height difference and established the double objective 0-1 programming model.At the same time,we used the cluster analysis,MATLAB search algorithm and artificial intervention to achieve single file which transverse and longitudinal cut into a scrap of paper splicing recovery.

1问题分析

破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术[1]，来提高拼接复原效率。

本文以2013年全国大学生数学建模竞赛[2]B题为例，研究单面英文文件既被横切也被纵切的碎纸片的拼接复原问题。

要对建模B题附件4中的碎纸片进行拼接复原，需建立碎纸片拼接复原模型和算法。由于209块英文碎片都有左侧、右侧和上侧、下侧，每块碎片边缘灰度已知，需要同时考虑每块碎片左右侧与其他碎片的差异以及上下侧与其他碎片的差异，通过该差异值可定义两个差异度指数，得到双目标0-1规划模型，进而找到碎片的复原顺序。

但由于决策变量较复杂，这种模型不易求解，因而提出改进模型：先定义高度差Hij，运用聚类分析，给定高度差阈值，按照高度不同将所有碎片分为23类，并建立双目标0-1规划模型。结合MATLAB编程和人工干预，将23类碎片处理为11行碎片，再对碎片纵向复原，得到英文复原序号，利用MATLAB编程画出复原图片。最后人工检验英文复原图片中无明显语法、词语和单词错误，证明复原图片正确。

2单面英文碎纸片拼接复原初步模型

2.1　提取信息：差异度指数

我们用差异度指数来衡量任意块碎片右侧边缘与任意块碎片左侧边缘差异及任意块碎片下侧边缘与任意块碎片上侧边缘的差异。定义差异度指数Lij和Uij：Lij表示第i块碎片右侧和第j块碎片左侧的差异度，为第i块碎片右侧与第j块碎片左侧的对应灰度值之差的绝对值的累和。Uij表示第i块碎片下侧和第j块碎片上侧的差异度，为第i块碎片下侧与第j块碎片上侧的对应灰度值之差的绝对值的累和。

公式如下：

2.2　英文碎纸片拼接复原模型

其中：αij=0时，表示第i张碎片右侧和第j张碎片左侧的不相连；αij=1时，表示第i张碎片右侧和第j张碎片左侧的相连；βij=0时，表示第i张碎片下侧和第j张碎片上侧的不相连；βij=1时，表示第i张碎片下侧和第j张碎片上侧的相连；以此模型可以得到所有碎片的连接方式。

3英文碎片拼接复原改进模型

由于建立的初步模型决策变量较复杂，且两个差异度矩阵较大，用程序实现较困难，因此在此提出改进模型[3]，只使用一种决策变量，具体建模过程如下：

3.1　提取信息：差异度指数和高度差

定义差异度指数Lij，与初步模型定义相同，但改进模型中不再使用差异度指数Uij，定义高度差Hij，表示第i块碎片第一行文字中心到第i碎片上侧边缘的高度Hi与第j块碎片第一行文字中心到第j碎片上侧边缘的高度Hj之间的差值。公式如下：

3.2　英文碎纸片拼接复原模型

其中：αij为决策变量，αij=0时，表示第i张碎片右侧和第j张碎片左侧的不相连；αij=1时，表示第i张碎片右侧和第j张碎片左侧的相连。

为了将双目标转化为单目标问题，可以给定高度差阈值Hij≤1，在给定高度范围对所有碎片进行分类，共23类，可以将此模型简化，目标函数与约束条件如下：

再结合人工干预可得到碎片的连接方式。

4英文碎片拼接复原模型算法

①找到每块碎纸片第一行文字中心到碎纸片上侧边缘的高度。

第一步：将每块碎纸片带入MATLAB软件中可得到由碎纸片上每个像素点灰度值组成的矩阵s1x(x=1，…，209)，将所有矩阵归一化：

第二步：对灰度矩阵S1从上到下进行行搜索，找到每块碎片第一行文字的中心位置；

第三步：通过MATLAB软件编程计算第i块碎纸片第一行文字中心到碎纸片上侧边缘的高度Hi；

②确定高度差阈值，进行聚类分析，将209块碎片按照每块碎片第一行文字中心到碎片上侧边缘的高度分为23类[4]。如表1。

表1　按高度不同对英文碎片的分类

高度(像素)=39.9±0.5的碎片1,23,39,51,53,64,73,84,86,88,90,98,125,126,129,139,140,194,201高度(像素)=44.3±0.5的碎片3,13,19,32,75,116,154,178高度(像素)=48.7±0.5的碎片2,121,130,161高度(像素)=52.2±0.5的碎片103,141高度(像素)=57.6±0.5的碎片48,76,107,181,192高度(像素)=62.0±0.5的碎片155高度(像素)=66.4±0.5的碎片12,65,185,191高度(像素)=70.9±0.5的碎片105高度(像素)=75.3±0.5的碎片24,91,100,123,209高度(像素)=79.8±0.5的碎片97,110,157,173,186高度(像素)=84.2±0.5的碎片87高度(像素)=106.4±0.5的碎片160高度(像素)=110.8±0.5的碎片33,40,66,205高度(像素)=124.1±0.5的碎片68,148,15高度(像素)=128.5±0.5的碎片5

③对每一类碎片，运用MATLAB软件画图，可以画出23行文字，对每行文字出现的奇异碎片进行剔除。通过人工干预，可以得到11行文字。

④对这11行文字，进行纵向拼接复原，在此基础上通过人工干预将11行文字进行调试和拼接，可以得到英文的复原序号和复原图片。

算法伪代码[5]如下：

PROC

{

//读入数据，根据文件类型进行导入操作

//FileType是导入文件的类型，指文件是否为分离成了两面的文件

//FileType={Single|Double}；

//DATA内包含了文件的索引号及文件的Bitmap数据

DATA=Load_File_Data(‘FileName’，FileType)；

//根据得到的数据对数据进行分类

//SortType决定分类检索方向

DATA_SORTED=Calc_Feature(DATA，SortType)；

//计算数据差异度，得到DATA内部边缘差异度矩阵

[DIF_ROWDIF_COL]=Calc_Dif(DATA)；

//对所得数据进行最小化差异操作，并返回最小化链接关系

[FIG_DATAFIG_CON]=

SORT(DIF_ROW，DIF_COL，DATA_SORTED)；

//在次校订所得数据关系(此处可加入人工校验过程)

CONN_DATA=RESHAPE(FIG_DATA，FIG_CON，DATA_SORTED)；

//由整合的数据进行分析整合成最终图像，返回图像句柄

handle=DRAW_MAP(CONN_DATA)；

}

5模型结果

对23类中任意一类碎片运用MATLAB编程可以画出任意一行英文，举例如图1。

可以画出23行英文，对每行英文出现的奇异碎片进行剔除。通过人工干预和基于碎片左右侧差异度指数的纵向排列方法，可以得到11行有顺序的英文，举例如图2。

图1　某一类英文文字行排列

图2　某一行有顺序的英文排列

干预的时间节点及干预方式如下：

干预时间节点：MATLAB编程排出23行后，对第209块碎片、第8块、第62块、第180块、第5块进行人工干预；将高度(像素)=75.3±0.5的碎片与高度(像素)=79.8±0.5人工干预。

干预方式：将这五个块碎片分别带入剩下的12行英文中，将每个碎片左侧和右侧边缘灰度值这12行英文碎片的边缘灰度值进行比较，找到差异度最小的连接方式，发现要把编号209的碎片归入高度(像素)=8.9±0.5，将高度(像素)=17.7±0.5的碎片与高度(像素)=79.5±0.5人工干预成一行。

得到竞赛原题附件四英文碎片拼接复原复序号表2及复原图片3：

表2　附件四英文碎片复原序号

bath day No news is good news.

Procrastination is the thief of time.Genius is an infinitecapaaty for taking pains.Nothing succeeds like success.Ifyou can't beat em, join em.After a storm comes a calm.Agood beginning makes a good ending.

One hand washes the other.Talk of the Devil, and he isbound to appear.Tuesday's child is full of grace.You can'tjudge a book by its cover.Now drips the saliva, will becometomorrow the tear.All that glitters is not gold.Discretionis the better part of valour.Little things please little minds.Time flies.Practice what you preach.Cheats never prosper.

The early bird catches the worm.It's the early bird thatcatches the worm.Don't count your chickens before they arehatched.One swallow does not make a summer.Every pic-ture tells a story.Softly, softly, catchee monkey.Thought is already is late, exactly is the earliest time.Less is more.

A picture paints a thousand words.There's a time anda place for everything.History repeats itself.The more themerrier.Fair exchange is no robbery.A woman's work is never done.Time is money.

Nobody can casually succeed,it comes from the thorough self-control and the will.Not matter of the today will drag tomorrow.They that sow the wind, shall reap the whirlwind.Rob Peter to pay Paul.Every little helps.In for a penny, in for a pound.Never put off until tomorrow what you can do today.There's many a slip twixt cup and lip.The law is anass.If you can't stand the heat get out of the kitchen.The boy is father to the man.A nod's as good as a wink to a blindhorse.Practice makes perfect.Hard work never did anyoneany harm.Only has compared to the others early, diligently

图3英文碎片复原图片

参考文献：

[1]罗智中.基于文字特征的文档碎纸片半自动化拼接[J].计算机工程与应用，2012:207-211.

[2]全国大学生数学建模竞赛组委会，2013年全国大学生数学建模竞赛B题，http：//www.mcm.edu.cn/problem/2013/2013.html，2013.

[3]韩忠庚.数学建模方法及其应用[M].北京：高等教育出版社，2005.

[4]龚纯.精通MATLAB最优化计算[M].北京：电子工业出版社，2009.

[5]李刚.MATLAB函数速查手册[M].北京：清华大学出版社，2013.

[责任编辑毕伟]

Computer-aided Single English File Fragments Reassembly

JIN Ming-ya,SUN Dan-lei,ZHAO YAN,DOU Ji-hong

(Department of Mathematics,Northwest University,Xi'an 710127,China)

Key words：difference degree index; 0-1 programming; MATLAB software; clustering analysis; height difference