一种形状规则碎纸的拼接模型及其仿真

黄永斌

【摘 要】 本文针对形状规则的碎纸的拼接问题，提出了一种基于双三次插值的优化模型，并进行了仿真验证。仿真结果表示，针对形状规则的碎纸拼接问题，本文提出的算法是可行的，可以获得良好的拼接效果，具有一定的实用价值。

【关键词】 碎纸拼接 图像处理 三次插值 优化模型

碎纸拼接问题是计算机视觉和模式识别领域内的一个热点问题，主要是通过计算机处理，获取碎纸片的形状、颜色等内容信息，然后利用这些内容信息对碎纸进行自动拼接，恢复碎纸原始的内容。碎纸拼接在情报资料碎片整理、司法技术鉴定等领域有着很多的应用，但大都是人工完成。因此研究碎纸拼接，尤其形状规则的碎纸有着重大的实际意义[1]。

1 碎纸拼接问题的分析

对于碎纸拼接问题，无法通过纸片轮廓的提取进行拼接，可以利用的信息主要集中在碎纸的边缘部分。实现拼接是以寻找各纸片边缘内容间的差异为突破口，选择合理的方法将纸片中的内容完整有效的提取出来。在纸片中的内容被提取后，可建立优化模型求解拼接方案。

2 数字图像处理

获取纸片信息是将图像转化为可感知数据的过程，需要取样和量化处理。对图像进行取样量化的结果是图像被保存为一个实矩阵的形式[2]。一幅图像各点的像素大小若能用位置的函数表示，离散取样后，产生的数字图像有m行和n列，则可用以下大小为的紧凑矩阵表示数字图像

，

也可用传统矩阵如下表示为A，而且显然有

。

灰度数字图像每个像素只有一个采样颜色，从黑色到白色的灰度有256级灰度。将需要拼接的N张碎纸扫描彩色为数字图像。将所有彩色数字图像转化为灰色数字图像，保存为矩阵的形式，其中每个元素为0-256的整数。

用表示第k块碎纸，碎纸片量化后得到矩阵，考虑下面碎片拼接的实现，定义n个列向量表示第1列至第n列，则量化所得矩阵为

3 碎纸边缘信息的提取

定义域是平面上的一个矩形区域，在x轴和y轴上分别取等分

由此可以定义出上述区域上的分割矩形的大小为，区域被分成个矩形。对其中的任意一个有标记

此区域内的双三次插值函数定义为[3]：

在利用灰度矩阵进行拼接时，若只取边界上一列来提取图像的边缘信息，会因边缘像素中存在大量噪声而不能很好刻画图片的边界信息，因此我们取的灰度矩阵最后5列记为取的前5列，同样取最后五列记为。

若的右边缘和的左边缘应当拼接在一起，则令，

由于图像函数应该具有良好的连续性和光滑性，即选择RL任意连续几列，所得的插值函数在某固定位置上的取值应大小相当，否则的右边缘和的左边缘不应当拼接在一起。从RL第一列开始依次选取连续6列做插值函数，则可得5个插值函数，记为：

利用各个插值函数分别可得在两张碎片拼接处的像素值

实际计算中，取拼接处在坐标系中的横坐标值为。根据图像的连续性假设和光滑性假设，利用上述5个值构造拼接的匹配度为：

4 拼接模型的建立

纸片有四个边缘，可知上下边缘的拼接方法与作用边缘的拼接方法应该相同，因此建立模型时只需要考虑一行碎纸片的拼接即可，将每行拼接好后再将行与行拼接。同时可知，一般纸张的左右边缘留白较大，因此根据留白找出一行的左右边缘再进行后续拼接，具体寻找过程不再详述。

可得模型的目标函数：使一行碎纸拼接后匹配度总和最大。也可得约束条件为：（1）每一行中最后一张碎纸的右边界不能与其他碎纸的左边界拼接；（2）每一行中的第一张碎纸的左边界不能与其他碎纸的右边界拼接；（3）碎纸的右边界只能与另一张碎纸的左边界拼接；（4）除第一张外，任意碎纸的左边界有且仅有一张碎纸的右边界与之拼接；除最后一张外，任意碎纸的右边界有且仅有一张碎纸的左边界与之拼接；（5）碎纸片整体必须构成巡回路线，不能含有子巡回[4]。

令表示碎片的右边缘与碎片左边缘的相似度，且设为0-1变量，表示碎片的右边缘与碎片左边缘拼接，则表示不能拼接，则根据约束目标函数和约束条件可建立碎纸片拼接模型为：

5 算法仿真

算例中有30张图片，分为三行，每行10张碎纸，处于同一行的已知。图1为部分原始图片。

将碎纸片进行编号为1-30，利用Matlab软件进行图像处理，分别找出三行散乱图片的左右边缘，在同一行内计算匹配度矩阵。最后根据拼接模型，利用Lingo[5]软件进行编程求解，得到每行的拼接结果。然后采用同样的方法将三行拼接。拼接的结果按照编号表示如表1，以图片表示则如图2。为显示整体拼接效果，图2将原始图片的黑白部分进行了反转。

最终的拼接结果为如图2所示。

6 结语

仿真实验证明，本文提出的基于双三次插值的优化模型是可行的。本文先拼行、再拼列和先定位边缘碎纸片的方法，可以极大简化问题的难度。利用LINGO软件建立模型求解能保证结果的精确性。本文的模型主要针对形状规则的碎纸片的拼接问题，具有一定的普适性，可以进行适当推广，具有一定的实用价值。

参考文献：

[1]贾海燕.碎纸自动拼接关键技术研究[D].国防科技大学硕士论文，2005

[2][美]冈萨雷斯，[美]伍兹.数字图像处理（第三版），北京：电子工业出版社，2010

[3]王会鹏，周利莉，张杰.一种基于区域的双三次算法[J].计算机工程，2010，36（19）： 216-218

[4]袁新生，邵大宏. LINGO和Excel在数学建模中的应用.北京：科学出版社，2007

[5]谢金星，薛毅.优化建模与Lindo/Lingo软件.北京：清华大学出版社，2005.