网站首页  词典首页

请输入您要查询的论文：

　

标题 切割文字全等矩形图片拼接算法设计与实现
范文 黄薇



摘 要：全等矩形破碎文字图片拼接还原技术是一种特殊的图片拼接复原技术，其处理的图片具有明显几何规律。通过数据挖据得到图片中所有文字占据连续像素行的平均行数、图片中两行文字间的间距（行距）占据的连续像素行的平均行数，以及每张图片所包含的文字和行距之间的交替规律即行信息向量，并对图片边沿进行二值化处理。还原技术通过对图片的行信息向量进行聚类分析，采用二值特征的Tanimoto测度，得出每行图片的排列顺序。最终得出所有图片的排列顺序，并将所有图片按照该顺序拼接，即可实现图片的拼接还原。
关键词：破碎图片；图片拼接；数据挖掘；模式识别；Tanimoto测度
DOIDOI：10.11907/rjdk.151506
中图分类号：TP312
文献标识码：A 文章编号文章编号：16727800（2015）009006105
0 引言
破碎文件的拼接还原在复原司法物证、修复历史文献及获取军事情报等领域有着重要应用。人工完成拼接复原，虽然准确率高，但效率很低。尤其当碎片数量庞大时，采用人工拼接复原几乎不可能在短时间内完成。随着计算机技术的发展，可以利用计算机实现破碎文件的自动拼接还原，以提高拼接复原效率。这是图像处理与模式识别领域中的一个新颖且典型的应用，它通过扫描和图像提取技术获取一组全等大小矩形碎纸片的颜色、形状等信息，然后利用计算机进行相关处理，从而实现对这些碎纸片的半自动或全自动拼接还原。
在进行拼接前将所有的小碎片放正（即上下不颠倒）扫描录入，并对每一个录入的图片进行唯一编号，然后导入计算机。处理对象为采用数字阵列表示的位图，通常有BMP、JPG、GIF等格式。
1 数字图像表达
一幅数字图像可以视为一个二维函数f（x，y），在平面中的任意一对坐标（x，y）上的幅值f称为该点图像的灰度、亮度或强度。一个大小为M×N的数字图像是由M行N列的有限元素组成，每个元素都有特定的位置和幅值，代表其所在行列位置上的图像物理信息，如灰度、彩色等。这些元素称为图像元素或像素。每个像素只有黑白两种颜色的图像称为二值图像。在二值图像中，像素只有0和1两种取值，用0表示黑，用1表示白，而介于黑色与白色之间的颜色深度，构成灰度图像，这类图像通常显示为从最暗黑色到最亮白色的灰度，每种灰度称为一个灰度级，通常用L表示。在灰度图像中像素的取值范围为0～L-1且为整数。根据类型的不同，可能有256种或2k种取值，当k=1时，为二值图像。本文使用的像素之间绝对位置的坐标约定，如图1所示。
图1 像素之间绝对位置的坐标约定
将物理图像转化成数字矩阵后，数字图像的矩阵表示如式（1）所示：
f（y，x）=f（0，0）…f（0，N-1）………f（M-1，0）...f（M-1，N-1）（1）
在矩阵f（y，x）中，采用的表示方式是纵坐标y（对应行下标），横坐标x（对应列下标）。通过软件完成对图像的处理实质上是通过计算机修改图像的像素矩阵。通过Matlab图像处理工具箱（Image Processing Toolbox，IPT）调用imread函数，获取图像底层数据即像素矩阵，通过imwrite函数将底层数据写入对应格式的图片中。破碎图片的拼接还原，即通过对底层数据进行数据挖掘，再通过一系列算法进行处理，最终确定每张图片的对应位置，最后定义一个更大的像素矩阵，将所有图片的底层数据写入到矩阵的对应位置，从而完成图片的拼接复原。
2 图片预处理
将待处理图片全部导入Matlab后，对所有图片进行编号，得到n张图片。原始图片如图2所示。
图2 原始图片导入编号
首先，获取每张图片的像素矩阵Ai（M×N）（i表示编号为i的图片，M×N表示数字图像由M行N列的有限元素组成）。图3展示了待处理小图片“001”号的部分像素矩阵（“上”字的局部）。每张图片的像素矩阵都是一个180×72的矩阵。
图3 小图片001号及其像素矩阵部分
根据每张图片的像素矩阵，得到每张图片像素矩阵中哪些行和列为全白，哪些行和列表示有字迹存在。根据这些信息可以直接筛选出那些可能为最顶端位置的图片和最左边、最底端及最右边的图片。
为得到图片的空白行信息，需构造一个M行的列向量a=（r0，...，rM-1）T，ri=0或1，i=0，...，M-1。当矩阵A第i行的所有元素全表示最亮白色的灰度时，ri=1，否则ri=0。在算法中，对矩阵的每一行进行遍历，每一行中只要有一列（一个元素）的值不是灰度信息最大（2k-1）值（示例图像灰度最大值为255（28-1）），则将向量a的相应行的值记为0，表示该行不为空白行或该行中有文字信息体现。如果矩阵该行的所有元素值都是灰度信息最大值，则将向量a相应行的值记为1，表示该行是一个空白行。向量a的意义为：它能如实反映出图片在哪些行是全白的，哪些行有文字信息体现。在此将列向量a命名为图片的行信息向量。同理，构造一个N列的行向量b=（c0，...，cN-1），ci=0或1，i=0，...，N-1，当矩阵A第i列的所有元素全表示最亮白色的灰度时，ci=1，否则ci=0。将行向量b称为图片的列信息向量。“001”号图片的行信息向量分段，如图4所示。由此可以得到每张图片的行信息向量ai和bi（i表示编号为i的图片）。
图4 001号的行信息向量分段截图
通过文字图片行信息向量可以得到与之类似的信息。即通过行信息向量得出图片中一个字的高度平均占多少个连续像素行，行距或两行字之间的平均间距占多少个连续像素行；通过列信息向量可以得到每一行中两个字之间的平均间距占多少个连续列。为得到上述信息，对每张图片的行信息向量建立一张图像的像素行信息表。这张表包含两个属性，当行信息向量在第i行和i+1行的元素值发生改变（由0变为1或由1变为0）时，第一个属性记录第i行的行号，第二个属性记录发生改变后的值。
伪代码如下：
updataB（a）
输入：
a：图片的行信息向量。
输出：
B：图片的像素行信息表。
算法：
r=a.length；
count=1；
define B；//定义一个空表
for（i=1；iif a[ i ]==0 && a[ i+1 ]==1
B[ count ][ 1 ]=i；
B[ count ][ 2 ]=1；
count++；
else if a[ i ]==1 && a[ i+1 ]==0
B[ count ][ 1 ]=i；
B[ count ][ 2 ]=1；
count++；
return B；
如果图片像素行信息表不为空，则表示该图片有文字存在，否则该图片为没有字迹的纯白图片。因为通过示例图片得知，一张图片中可以存在两行字迹，而且行距明显，即任意一张图片的像素矩阵，至少有一行的值全为255。而由每张图片的列信息向量，可以建立该图像的像素列信息表。当列信息向量在第i列和第i+1列的元素值发生改变（由0变为1或由1变为0）时，第一个属性记录第i列的列号，第二个属性记录发生改变后的值。值得注意的是，图片的像素列信息表为空时，并不能和像素行信息表一样体现出图片是否有字或纯白。因为文字一般是从左往右连续写的，虽然每一行字与字之间有间距，但是并不是每一行这些间距都对齐（导致各行字间距不能对齐的根本原因是因为有标点符号存在）。如果字间距没有对齐，上一行的字间距表示的空白位置有可能被下一行文字信息覆盖，因而得到的列信息向量的所有元素都为0，这样得到的像素列信息表为空，但图片却有文字信息体现。
用字高（WH）表示图片中每个字占用连续像素行的行数，每张图片都可以通过算法求出该图片的平均字高EWHi。
获取每张图片中平均字高的算法如下：
Step1：开始，输入图片的像素行信息表，进入Step2。
Step2：判断图片的像素行信息表是否为空，如果为空，则返回该图片的平均字高为0，进入Step6；如果不为空，统计出表的行数记为r。令i=0，count=0，sum=0，进入Step3。
Step3：判断i+1≤r，如果为真，进入Step4，然后i=i+1，返回Step3；如果为假，进入Step5。
Step4：判断表的第i行第2列等于0，且第i+1行第2列等于1，如果为真，则count=count+1，sum则赋值为sum加上表的第i+1行第1列的值，减去第i行第1列的值。
Step5：如果count>0为真，则sum=sum/count，返回平均字高为sum，进入Step6；如果为假，则返回平均字高为sum，进入Step6。
Step6：结束。
选出所有不为0的EWHi，将其求平均值，则得到每个字所占连续像素行行数的均值EWH，即：
EWH=∑ni=1EWHi∑ni=1SWi，SWi =1（EWHi ≠0）0（EWHi =0）（2）
用行距（HJ）表示图片中两行字之间的空白行占用连续像素行的行数，则求每张图片中行距的算法，只需将获取每张图片中平均字高算法的Step4改为：判断表的第i行第2列等于1，且第i+1行第2列等于0。如果为真，则count=count+1；sum则赋值为sum加上表的第i+1行第1列的值，减去第i行第1列的值；其它不变。于是可求得平均行距为：
EHJ=∑ni=1EHJi∑ni=1SHi，SHi = 1（EWJi ≠0）0（EWJi =0）（3）
用字距（WJ）表示字与字之间的空白，则求字距的算法只需将求行距算法的Step1改为：输入图片的像素列信息表进入Step2，其它不变。于是可得平均列距为：
ELJ=∑ni=1ELJi∑ni=1SLi，SLi =1（ELJi ≠0）0（ELJi =0）（4）
由于所求均值都涉及到像素信息，像素点不存在小数，以字高为例，只需作如下处理，伪代码如下：
if（EWH-|EWH|≠0）EWH=|EWH+1|； //加1再向下取整
将示例图片按上述方法，得到图片的EWH=41（行），EHJ=34（行），ELJ=4（行）。灰度图像中像素的取值范围为[0～L-1]（L=2k）。对于示例图片而言，像素的取值范围则是0～255。在一张灰度图片中灰度像素是一个渐变过程，而不是一个突变过程。在最亮白色灰度和最暗黑色灰度像素点之间肯定存在一个或多个像素点，这些点的像素值都介于最亮和最暗之间，起到一个过渡作用。每张图片像素矩阵边沿的信息熵较大，为降低信息熵，使图片边沿更容易识别，对每张图片的左侧和右侧进行边沿处理。
图像左侧边沿处理算法如下：
Step1：开始，输入图片的像素矩阵A，新建一个M行两列的图像左边沿信息表LB。
Step2：判断矩阵A每一行第1列元素的值是否为最亮白灰度或最暗黑灰度，如果为真，则LB的相应行第1列记录下该像素值，第2列记为1；如果为假，则从该行的第2列元素开始往右搜索，直到遇到最亮或最暗灰度为止才终止向右搜索。并且最后终止时遇到的是最暗灰度，则LB的该行第1列则记为最亮灰度，如果终止时遇到的是最亮灰度，则第1列记为最暗灰度。LB的该行第2列记为2。
Step3：输出表LB，结束。
其伪代码如下（假设最暗灰度为0，最亮为255）：
4 结语
利用计算机完成破碎文件的拼接复原，相对于人工拼接有着强大的时间优势，但是该算法也有一定局限性，其只能处理纯文字图片，并通过数据挖掘计算平均行距，因而对字高等信息有着极大依赖。该算法也能解决一些实际问题，可以比较完整且高效地复原碎片文字图片，但部分功能还有待进一步改进。
参考文献参考文献：
[ 1 ] THOMAS H CORMEN，CHARLES E LEISERSON，RONALD L RIVEST，et al.算法导论[ M ].第3版.北京：机械工业出版社，2013.
[ 2 ] JIAWEI HAN，MICHELINE KAMBER，JIAN PEI.数据挖掘概念与技术[ M ].北京：机械工业出版社，2013.
[ 3 ] 张铮，王艳平.数字图像处理与机器视觉——Visual C++与Matlab实现[ M ].北京：人民邮电出版社，2013.
[ 4 ] 姜启源，谢金星，叶俊.数学模型[ M ].北京：高等教育出版社，2011.
责任编辑（责任编辑：黄 健）
随便看

　

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。

　

Copyright © 2004-2023 puapp.net All Rights Reserved
更新时间：2025/3/15 9:01:58