基于模糊聚类分析的碎纸片拼接模型

叶德华 朱溦

摘 要：规则边界碎纸片拼接在司法实践中有应用意义，研究采用模糊聚类分析对碎纸片进行行的分类。行分类后，利用带有字宽评估的0-1规划模型对行内碎纸片进行排序拼接。行排序完成后，以每行为碎片单位，采用带有字高评估的0-1规划模型。

关键词：模糊聚类分析;0-1规划模型;碎纸片拼接

中图分类号：O159 文献标识码：A

1 问题概述

随着司法实践对文档物证修复的需要，碎纸机的普遍使用，碎纸片文档的自动或半自动拼接复原技术的研究具有重要意义。一般文档碎片拼接复原问题，可分为手撕非规则碎片拼接和机器类切割规则碎片拼接两类。而机器类切割、边界规则碎片又可以分为纵切和纵横切，单面文档和双面文档，中文字体、英文字体、混合字体和图文并茂等特征文档。

碎片拼接的拼接过程往往可以划分为4个环节：碎片图象采集、碎片图象预处理、匹配程度度量和拼接算法（可以含人工交互）。其中，匹配程度度量和拼接算法实现是关键。在匹配度度量上，有带有罚函数的欧氏距离[1];利用Hamming距离或Jaccard距离[2];利用余弦距离[3];利用碎片边缘像素的总变差度量距离[4]。拼接算法，主要有利用聚类分析找到同行的碎片，然后轉化为旅行商问题[1-2]。在定义了邻接距离或度量距离后，转化为0-1整数规划问题[3-4]。

文章针对单面纵横切中文字体的文档，从人工拼接思考的过程出发，在手动拼接时，总把最有可能归为一行的碎片先归纳为同一行。在这样的行中进行行内排序，在排序过程中，根据行内整体匹配度高低，进行碎片的剔除。行排序完成后，以整行为单位再进行行之间的排序。因此，研究采用模糊聚类分析，在聚类阈值的选择上，采用类间碎纸片的数量尽可能均衡和碎片数估计的方法。而行类中碎纸片的排序，以及以行为单位的行之间的排序，则分别采用带有字宽评估的0-1规划模型和带有字高评估的0-1规划模型。

2 图象采集与预处理

为保证图象有共同的几何大小，对碎片文档进行扫描，保存为“.jpg”格式的图片。然后利用Matlab中的imread（‘filename.jpg’）命令读入图象，再利用im2bw（A，thresh）命令进行二值化，参数thresh针对具体的应用场景确定。实验中使用的是CUMCM2013B题中的附件3.确定thresh=0.5.经过二值化后得到m×n（例子中180×72）的矩阵集{Ai|i=1，2，…}。Ai中元素值为0表示字迹，1表示背景色。

3 碎纸片特征提取

针对中文碎纸片的特点，定义碎纸片特征结构体Hi={r，hor，ver，h，w}。

对每块碎片的矩阵Ai，采用从左上角顺时针历遍的方式对边缘像素值前后值求差，计算像素值从1突变到0的频数fi。得到碎片一周边缘像素丰富程度。

特殊情况，当碎片四周都是没有笔画像素的或都有笔画像素的，越接近于0;相反，像素恰好是1-0交替出现的，越接近于1。显然，值越大，越有利于正确地拼接。

用水平像素累积直方图的方法确定字符行的开始和结束位置。从碎片上方开始记录直方图中全1（像素累积是 ）的位置，记为（第片的右侧文字行开始或结束位置向量）。同时可以得到汉字高度特征向量（第片的汉字高度向量），计算出平均字高H。

用相邻列求差法，计算每个碎纸片上边缘和下边缘的字符开始和结束位置，分别记为（第片上侧文字开始或结束位置向量）和（第片下侧文字开始或结束位置向量）。同时，可以得到汉字宽度向量 （第片上侧文字宽度）和（第片下侧文字宽度），计算出平均字宽 W。

相邻列求差算法。

4 模糊聚类分析

利用碎片边缘像素丰富程度（1），设置合理的阈值，可以直接筛选出边缘没有文字的碎片集M，模糊聚类对所有碎纸片中去除了M集中的碎片进行。聚类分析的过程是数据标准化，建立模糊相似矩阵，动态聚类。

用相关系数法建立模糊相似矩阵得到R，用二次方法计算R的传递闭包t（R），在传递闭包t（R）中，根据相似度的值，由大到小进行聚类。

聚类中最佳阈值的确定。策略（1）根据实际问题信息A4纸的宽度和每个碎纸片的宽度，估计出每行中碎纸片的数量，记为。策略（2）设分类中第类的碎纸片数量为，选择使最小且最接近值的。

5 行内和行间排序

聚类分析后得到每行的碎片类，在行内排列中，采用带有字宽评估的0-1规划模型。分别取出碎片Ai的左侧和右侧边缘像素值：

行内排序完成后，可以根据文件切碎的大小、是否有中英文混排、是否有图片等的复杂程度，进行人工干扰。确保行排序完整无误后，进行行间的碎片排序。以整行碎片的上下边缘像素值和汉字高度向量为特征，类似与行内排序，建立带有字高评估的0-1规划模型进行拼接，最终完成文档的拼接。

6 实验与评价

实验以2013年高教杯全国大学生数学建模竞赛B题中的碎片为数据，以MATLAB R2014a为平台进行验证。拼接结果准确完整。研究提出利用模糊聚类分析进行碎片行分组，采用行内碎纸片的数量尽可能均衡和碎片数估计的方法，选择合理的聚类阈值。然后，利用带有字宽评估的0-1规划模型对行内碎片进行排序，采用带有字高评估的0-1规划模型对行的碎片进行排序。存在不足，在行内碎片排序中，因切割的多样性，还是会需要人工干预;算法的速度和准确性对比方面还需要进一步的研究。

参考文献

[1] 付光辉，华云，陈军华，等.基于聚类和蚁群算法的横纵切碎纸片复原算法[J].数学的实践与认识，2019，49（15）：199-209.

[2] 薛毅.碎纸片拼接复原的数学方法[J].数学建模及其应用，2013，2（Z2）：9-13.

[3] 蔡志杰.碎纸片拼接复原的数学模型与方法[J].高等数学研究，2016，19（04）：107-110.

[4] 余锦华，杨维权.多元统计分析与应用[M].广州：中山大学出版社，2005：162-183.