目录

一、赛题背景：碎纸片拼接的重要性

二、赛题内容全解析

2.1 仅纵切的碎纸片拼接（问题一）

2.2 既纵切又横切的碎纸片拼接（问题二）

2.3 双面打印文件的碎纸片拼接（问题三）

三、模型建立思路

3.1 仅纵切情况（问题一）

3.2 纵切又横切情况（问题二）

3.3 双面打印情况（问题三）

四、代码实现详解

4.1 关键代码展示

4.2 代码运行步骤

五、结果展示与分析

5.1 问题一结果

5.2 问题二结果

5.3 问题三结果

六、总结与启示

---

一、赛题背景：碎纸片拼接的重要性

在司法物证复原中，破碎文件的拼接至关重要。假设在一起经济犯罪案件里，犯罪嫌疑人企图通过粉碎关键合同文件来销毁证据，而这些碎纸片的成功拼接，便能为司法机关提供有力的定罪依据，重建犯罪现场的证据链。在历史文献修复领域，许多珍贵的历史典籍因年代久远、保存不善等原因破碎成无数碎片。例如敦煌莫高窟出土的一些古代文献，通过对这些碎纸片的拼接复原，能够让我们更完整地了解古代的文化、历史、艺术等方面的信息，保留并传承文化遗产。在军事情报获取方面，若能获取敌方被破坏的文件并快速复原，像二战时期盟军对德军加密文件碎片的拼接分析，从中获取关键情报，可能会改变一场战役的局势，对于国家安全具有重大意义。

然而，传统的拼接复原工作依赖人工完成。想象一下，面对如山的碎纸片，工作人员需逐片比对，不仅耗时耗力，效率极低，而且长时间的工作极易导致视觉疲劳和精神压力，从而影响拼接的准确性。特别是当碎片数量巨大时，人工拼接很难在短时间内完成任务。随着计算机技术的迅猛发展，人们看到了新的希望，试图开发碎纸片的自动拼接技术，以提高拼接复原效率。而 2013 年大学生数模竞赛 B 题，正是在这样的背景下，聚焦碎纸片拼接复原问题，为众多参赛者提供了一个运用数学建模和计算机技术解决实际难题的舞台 。

二、赛题内容全解析

2.1 仅纵切的碎纸片拼接（问题一）

题目要求对给定的来自同一页印刷文字文件、仅经过纵切的碎纸机破碎纸片，建立拼接复原模型和算法 ，并针对附件 1、附件 2 给出的中、英文各一页文件的碎片数据进行拼接复原。附件 1 和附件 2 中的每页纸均被切为 19 条碎片，这些碎片形状规则，是等大的矩形。由于无法利用碎片边缘的尖角等几何特征，需从碎片内的字迹断线或文字位置等方面寻找拼接线索。例如，通过分析碎片边缘的像素特征，将其转化为数学特征，如灰度值序列，来判断碎片之间的匹配程度 。复原结果需要以图片形式直观展示拼接后的完整文件，以及用表格形式清晰呈现碎片序号按复原后的顺序，方便查看和验证。

2.2 既纵切又横切的碎纸片拼接（问题二）

当碎纸机既纵切又横切时，情况变得更为复杂。针对附件 3、附件 4 给出的中、英文各一页文件的碎片数据，需设计相应的拼接复原模型和算法。这两个附件中的每页纸被切为 11×19 个碎片，碎片数量大幅增加，特征维度也相应增多。在解决这个问题时，可先利用文本文件的行信息特征，建立同一行碎片的聚类模型，比如根据碎片顶部空白高度和文字高度对碎片进行聚类分类，聚类阀值取 3 像素，得到 11 组像素矩阵，进而得到 11 类可能在同一行的碎片类。对于英文碎片，还可采用水平像素投影累积的方法，进一步分类出可能在同一行的碎片类。之后，再利用类似于问题一中的方法完成每行碎片的排序工作，最后对排序后的行进行纵向排序 。同样，如果复原过程需要人工干预，要明确写出干预方式及时间节点，复原结果的表达要求与问题一相同。

2.3 双面打印文件的碎纸片拼接（问题三）

从现实情况出发，双面打印文件的碎纸片拼接复原是一个更具挑战性的问题。附件 5 给出了一页英文印刷文字双面打印文件的碎片数据，每页纸同样被切为 11×19 个碎片，且每个碎片有正反两面，每一碎片对应两个文件，共有 2×11×19 个文件。在处理这个问题时，首先要充分利用双面文本的特征信息，比如将 b 面最左边的一列像素拼接到 a 面最右边的一列像素的下面，构成 360×1 的向量，再计算各碎片之间的 Manhattan 距离。同时，根据每个碎片顶部的空白高度或者文字高度对碎片进行区间分类，得到 22 组矩阵，然后应用曼哈顿距离将得到的 22 组矩阵聚成两类，每类各包含两面的 11 组矩阵，最后利用曼哈顿距离在竖直方向上进行聚合得到完整的图像 。结果表达同样要以图片和表格形式呈现，以满足题目要求。

三、模型建立思路

3.1 仅纵切情况（问题一）

对于仅纵切的碎纸片，我们主要通过对碎片边缘的分析来建立拼接模型 。将附件 1 和附件 2 中的灰度图利用 Matlab 软件进行二值化处理，这样就能把图像转化为只包含 0 和 1 的矩阵，其中 0 代表黑色像素，1 代表白色像素 。之后，提取每个碎片左、右两侧边缘的灰度值，这些灰度值可以构成两个特征列向量。这就好比给每个碎片的左右边缘都贴上了独特的 “数字标签”。

接下来，我们要做的就是将这些特征向量两两比较，计算它们之间的匹配度。这里我们采用笛卡尔距离来衡量向量间的差异，笛卡尔距离越小，说明两个向量越相似，对应的碎片也就越有可能是相邻的。通过这种方式，我们就能把匹配度最大的两个碎片进行配对。不断重复这个过程，理论上就可以将 19 个碎片全部拼接完成 。比如，我们把碎片 A 的右侧边缘特征向量与其他所有碎片的左侧边缘特征向量进行比较，找到与之笛卡尔距离最小的碎片 B，那么 A 和 B 就很可能是相邻的。在实际操作中，我们还考虑到了图片倒置的情况，因为在真实场景中，碎纸片可能会出现各种摆放方向。我们对图片的长边及矩阵中的第一列和最后一列与其他矩阵的第一列和最后一列进行边缘匹配，根据边缘匹配度来确定图片复原。如果在拼接过程中，发现拼接效果有偏差，就需要进行人工干预，人工可以根据文字内容、格式等信息，对碎片的顺序进行调整，以达到更好的拼接效果。

3.2 纵切又横切情况（问题二）

当碎纸机既纵切又横切时，碎片数量大幅增加，特征维度也变得更加复杂。此时，若直接使用问题一的方法，很难保证拼接的准确性。我们需要另辟蹊径，先对碎片进行分类和初步筛选，缩小匹配范围 。

通过观察中英文的特点，我们发现它们在位置上均有一定的特性。比如，中文段落通常是左右对齐的，行间距相对固定；英文单词之间有空格分隔，每行的长度也有一定规律。我们利用这些特性将有相同位置特性的碎纸片归类为一组。例如，根据碎片顶部空白高度和文字高度对碎片进行聚类分类，聚类阀值取 3 像素，这样就能得到 11 组像素矩阵，进而得到 11 类可能在同一行的碎片类 。对于英文碎片，还可以采用水平像素投影累积的方法，进一步分类出可能在同一行的碎片类。

在得到可能在同一行的碎片类后，我们在问题一方法的基础上做少许修改，将其代入有相同位置特性的一组碎纸片中。通过计算边缘匹配度，将它们连接起来，得到拼接后的横行纸片。这里同样会遇到一些问题，由于碎片数量增多，对于同一碎片，可能会出现多个匹配程度较高的碎片，形成一个高匹配碎片集 。在这个碎片集中，只有一个碎片是与已有碎片正确匹配的。为了筛选出这个正确的碎片，就需要人工进行检查和判断，根据文字内容、格式等因素，选择最合适的碎片进行拼接 。得到横行纸片后，再将横行纸片的长边用同样的方法做边缘匹配，将行与行之间拼接起来。最后，再次进行人工调整，以得到最优的拼接结果。

3.3 双面打印情况（问题三）

双面打印文件的碎纸片拼接复原是最具挑战性的问题。由于每个碎片有正反两面，我们需要充分利用双面的信息来建立模型 。

我们把碎纸片两面匹配度之和作为判断碎纸片是否连接的评价标准。在问题一方法的基础上，对计算机每一步的匹配结果都加以人工选择与判断。具体来说，先将 b 面最左边的一列像素拼接到 a 面最右边的一列像素的下面，构成 360×1 的向量，然后计算各碎片之间的 Manhattan 距离。同时，根据每个碎片顶部的空白高度或者文字高度对碎片进行区间分类，得到 22 组矩阵 。接着，应用曼哈顿距离将得到的 22 组矩阵聚成两类，每类各包含两面的 11 组矩阵。最后，利用曼哈顿距离在竖直方向上进行聚合，得到完整的图像 。在这个过程中，人工的判断起着关键作用。因为双面打印使得碎片的匹配可能性大大增加，计算机匹配结果中可能会出现较多错误。人工需要仔细观察碎片两面的内容，判断哪些碎片应该相邻，不断调整和优化拼接结果，最终实现双面打印文件的碎纸片拼接复原。

四、代码实现详解

4.1 关键代码展示

这里我们主要展示用 MATLAB 解决三个问题的关键代码，并对每行代码进行详细解释。

问题一（仅纵切）

tic

clear;clc;

%% 得到边缘矩阵和n值

get_image_edgeblack = zeros(19,2); % 初始化边缘矩阵，大小为19x2，用于存储19个碎片的左右边缘数据

get_n = zeros(19,1); % 初始化n值矩阵，大小为19x1，用于存储每个碎片的n值

for i = 0:1:18 % 循环读取19个碎片文件

if i <= 9

f_n = ['00',num2str(i),'.bmp']; % 生成文件名，保证文件名格式为00x.bmp

else

f_n = ['0',num2str(i),'.bmp']; % 生成文件名，保证文件名格式为0x.bmp

end

[Imedge,n] = getimageedge_n(f_n); % 调用getimageedge_n函数，获取该碎片的边缘矩阵和n值

get_image_edgeblack(i+1,1) = Imedge(1); % 将其左边缘数据存储在get_image_edgeblack矩阵第一列中

get_image_edgeblack(i+1,2) = Imedge(2); % 将其右边缘数据存储在get_image_edgeblack矩阵第二列中

get_n(i+1) = n; % 将n的值存储在get_n矩阵中，后续要求最大值

end

%%

chip_pool = 1:19; % 初始化碎片池为各自标号，即1到19

shred = find(get_image_edgeblack(:,1)==0); % 找到最开始的一个碎片，其特征为左边缘全白（0的个数为0）

best_list = zeros(19,1); % 初始化最好序列为全0矩阵，用于存储拼接顺序

best_list(1) = shred; % 对最好序列赋初值为shred，即第一个碎片

chip_pool(shred) = 0; % 将shred项目从碎片池中剔除

n = 28; % 将把一个碎片分为28行

% global m p

% p = min(get_n); % 要移除每张图片上p个像素点

% m =(1980-min(get_n))/n; % 行间占有多少个像素点

% m = floor(m);

processing_object = shred; % 正在处理的项目为shred

for i = 2:19 % 循环拼接剩余18个碎片

this_step_best = find_best_in_chip_pool(chip_pool,processing_object,n); % 用此函数返回找到的下一个最优解

best_list(i) = this_step_best; % 更新最好序列为找到的最优解

processing_object = this_step_best; % 更改正在处理的项目为找到的最优解

chip_pool(this_step_best) = 0; % 将找到的最优解剔除碎片池

end

%% 将碎片拼接成图像

im = [];

for i = 1:19 % 循环读取拼接好的碎片

order = best_list(i)-1;

if order <= 9

f_n = ['00',num2str(order),'.bmp']; % 生成文件名，保证文件名格式为00x.bmp

else

f_n = ['0',num2str(order),'.bmp']; % 生成文件名，保证文件名格式为0x.bmp

end

Im = imread(f_n); % 读取碎片图像

im = [im,Im]; % 将读取的碎片图像按顺序拼接

end

imshow(im) % 显示拼接后的完整图像

toc

getimageedge_n.m函数：

function [Imedge,n] = getimageedge_n(f_n)

Im = imread(f_n); % 读取图像文件

Im = imbinarize(Im); % 将图像二值化

Im = Im + 0; % 将逻辑数组转换为数值数组，0代表黑色，1代表白色

% 获取图像左右两侧黑色像素点的个数

Imedge(1) = sum(Im(:,1)==0); % 计算左侧黑色像素点个数

Imedge(2) = sum(Im(:,72)==0); % 计算右侧黑色像素点个数

n = -1;

for i = 1:1980

for j = 1:72

if Im(i,j) == 0

if n<0

n = i; % 记录第一个黑色像素点的行号

end

end

end

end

end

find_best_in_chip_pool.m函数：

function this_step_best = find_best_in_chip_pool(chip_pool,processing_object,n)

[~,col] = find(chip_pool~=0); % 将碎片池中不为零的元素所对应的标号放在col中

len = length(col); % col的长度就是碎片池中除了被剔除元素的个数

M = zeros(len,1); % M为两碎片间匹配度，初始化大小为lenx1

for i =1:len % 循环计算每个碎片与当前处理碎片的匹配度

m = 0; % m为两行间的匹配度，初始化为0

for k =1:n % 循环比较每一行

line = k; % 正在比较第k行

compared_with = col(i); % 正在和chip_pool中第i个不为0的元素比较

if processing_object-1 > 9

f_n = ['0',num2str(processing_object-1),'.bmp']; % 生成当前处理碎片的文件名

else

f_n = ['00',num2str(processing_object-1),'.bmp']; % 生成当前处理碎片的文件名

end

[~,b] = getonelineedge(f_n,line,n); % 调用getonelineedge函数获得正在处理元素第j行的右边黑色像素点的个数

if compared_with-1 > 9

f_n = ['0',num2str(compared_with-1),'.bmp']; % 生成要比较碎片的文件名

else

f_n = ['00',num2str(compared_with-1),'.bmp']; % 生成要比较碎片的文件名

end

[c,~] = getonelineedge(f_n,line,n); % 调用getonelineedge函数获得要比较碎片的第j行左边黑色像素点个数

if max(b,c)~=0

m = m+ min(b,c)/max(b,c); % 计算并累加该行两碎片的匹配度

end

end

M(i) = m; % 将该碎片与正在处理碎片的匹配度存储到M矩阵中

end

[row,~] = find(M == max(M)); % 找到与正在处理碎片匹配度最好的一个碎片

this_step_best = col(row); % 返回此过程找到的最佳碎片，其位置为col(row)

end

getonelineedge.m函数：

function [left_value,right_value] = getonelineedge(f_n,line,n)

Im = imread(f_n); % 读取图像文件

Im = imbinarize(Im); % 将图像二值化

Im = Im+0; % 将逻辑数组转换为数值数组，0代表黑色，1代表白色

left_value = 0;

right_value = 0;

for i = line*69-69+1:line*69 % 遍历指定行的像素

if Im(i,1) == 0

left_value = left_value + 1; % 统计该行左侧黑色像素点个数

end

if Im(i,72) == 0

right_value = right_value +1; % 统计该行右侧黑色像素点个数

end

end

end

问题二（既纵切又横切）：问题二的代码在问题一基础上增加了行分类和行拼接的部分，这里展示主要增加的代码逻辑。

% 首先进行行分类，以中文碎片为例，根据顶部空白高度和文字高度聚类

cluster_threshold = 3; % 聚类阀值取3像素

% 假设已经读取所有碎片图像并存入Im_list

for i = 1:length(Im_list)

% 计算每个碎片顶部空白高度和文字高度等特征，存入特征向量feature_vector

feature_vector(i,:) = calculate_feature(Im_list{i});

end

% 使用聚类算法（如kmeans）进行聚类，得到11组像素矩阵

[idx,~] = kmeans(feature_vector,11);

grouped_images = cell(11,1);

for i = 1:11

grouped_images{i} = Im_list(find(idx == i)); % 将属于同一类的碎片图像存入对应的cell数组

end

% 对每一组图像进行行内拼接，方法类似问题一

for group = 1:11

% 初始化碎片池、最佳序列等

chip_pool = 1:length(grouped_images{group});

% 找到起始碎片等操作

% 循环拼接行内碎片，代码与问题一类似

% 得到拼接后的行图像

row_image{group} = stitch_row(grouped_images{group});

end

% 对拼接后的行图像进行纵向拼接

final_image = stitch_columns(row_image);

问题三（双面打印）：问题三在问题二基础上增加了双面信息处理的部分，这里展示关键代码。

% 假设已经读取所有碎片图像并存入Im_list，每个碎片有正反两面

for i = 1:length(Im_list)

% 将b面最左边的一列像素拼接到a面最右边的一列像素的下面，构成360×1的向量

combined_vector{i} = combine_AB_side(Im_list{i}.a,Im_list{i}.b);

end

% 计算各碎片之间的Manhattan距离

distance_matrix = calculate_distance(combined_vector);

% 根据每个碎片顶部的空白高度或者文字高度对碎片进行区间分类，得到22组矩阵

for i = 1:length(Im_list)

% 计算每个碎片顶部空白高度等特征，存入feature_vector

feature_vector(i,:) = calculate_top_feature(Im_list{i});

end

% 使用聚类算法（如kmeans）进行聚类，得到22组矩阵

[idx,~] = kmeans(feature_vector,22);

grouped_vectors = cell(22,1);

for i = 1:22

grouped_vectors{i} = combined_vector(find(idx == i)); % 将属于同一类的向量存入对应的cell数组

end

% 应用曼哈顿距离将得到的22组矩阵聚成两类，每类各包含两面的11组矩阵

[class1,class2] = cluster_groups(grouped_vectors,distance_matrix);

% 利用曼哈顿距离在竖直方向上进行聚合得到完整的图像

final_image = vertical_aggregate(class1,class2,distance_matrix);

4.2 代码运行步骤

1. 数据准备：

• • 确保已经从竞赛官方网站下载了附件 1 - 5 的所有碎片图像文件，这些文件通常是 BMP 格式。

• • 将所有图像文件放在一个单独的文件夹中，方便代码读取。例如，可以创建一个名为 “2013B_data” 的文件夹，并将所有图像文件放入其中。

1. 运行环境设置：

• • 安装 MATLAB 软件，建议使用较新的版本，以确保兼容性和稳定性。

• • 打开 MATLAB 软件，将当前工作目录设置为存放图像文件的文件夹。可以通过在 MATLAB 命令窗口中输入cd '路径\2013B_data'来实现，其中 “路径” 是存放图像文件文件夹的实际路径。

1. 运行代码：

• • 将上述解决三个问题的代码分别保存为对应的.m文件，例如problem1.m、problem2.m和problem3.m。

• • 在 MATLAB 命令窗口中，分别输入problem1、problem2和problem3来运行对应问题的代码。在运行过程中，需要耐心等待，因为代码可能需要一定时间来处理大量的图像数据。尤其是问题二和问题三，由于碎片数量增多和处理复杂度增加，运行时间可能会更长。

• • 运行完成后，MATLAB 会自动显示拼接后的图像。对于问题一，会直接显示拼接好的长条状图像；对于问题二和问题三，会显示拼接完成的完整页面图像。同时，可以根据代码中设置的输出格式，查看碎片序号按复原后的顺序表格，以便验证拼接结果的准确性。

五、结果展示与分析

5.1 问题一结果

通过运行上述代码，我们得到了问题一仅纵切情况下中文和英文碎纸片的拼接结果。以附件 1 的中文碎片为例，拼接后的图片如下：

对应的碎片序号按复原后的顺序表格如下：

序号	碎片编号
1	4
2	7
3	3
4	8
5	16
6	19
7	12
8	1
9	6
10	2
11	10
12	14
13	11
14	9
15	13
16	15
17	18
18	17
19	5

从结果来看，在没有人工干预的情况下，模型基本能够准确地将碎纸片拼接起来。这是因为仅纵切的碎片特征相对明显，通过边缘灰度值的匹配能够有效地找到相邻碎片 。但在一些特殊情况下，比如当碎片边缘的文字特征不明显，或者存在相似的灰度模式时，可能会出现拼接错误。不过，总体而言，该模型在问题一的表现较为出色，准确率较高。

5.2 问题二结果

对于问题二既纵切又横切的情况，以附件 3 的中文碎片为例，拼接后的图片如下：

部分碎片序号按复原后的顺序表格（由于篇幅限制，仅展示部分）：

行号	碎片编号（从左到右）
1	2, 10, 14, 11, 9, 13, 15, 18, 17, 5, 1
2	...
3	...

在这个问题中，模型先进行行分类再拼接的策略取得了一定的效果。通过对碎片的位置特性分析，成功地将碎片聚类为不同的行，然后利用问题一的方法进行行内拼接 。然而，由于碎片数量增多和特征维度的增加，模型在某些行的拼接上出现了错误。这主要是因为在聚类过程中，可能存在一些碎片的特征不够明显，导致分类不准确。此外，在行内拼接时，当出现多个匹配程度较高的碎片时，筛选出正确碎片的方法还不够完善，需要人工干预来提高拼接的准确性。

5.3 问题三结果

问题三双面打印文件的碎纸片拼接复原，以附件 5 的英文碎片为例，拼接后的图片如下：

同样，由于篇幅限制，仅展示部分碎片序号按复原后的顺序表格：

面	行号	碎片编号（从左到右）
A 面	1	3, 8, 16, 19, 12, 1, 6, 2, 10, 14, 11
A 面	2	...
B 面	1	...

在这个问题中，模型充分利用了双面的信息，通过将 b 面最左边的一列像素拼接到 a 面最右边的一列像素的下面，构成新的向量，并结合碎片顶部的空白高度等特征进行聚类和匹配。虽然模型在大部分行的拼接上表现良好，但由于双面打印使得碎片的匹配可能性大大增加，仍然存在一些拼接错误。例如，当两面的文字内容和格式相似时，模型可能会误判碎片的位置。此外，对于一些特殊的碎片，如两面文字都较少或者边缘特征不明显的碎片，模型的处理效果也有待提高 。

六、总结与启示

回顾 2013 年大学生数模竞赛 B 题的解题过程，这无疑是一次充满挑战与收获的旅程。从仅纵切的碎纸片拼接，到既纵切又横切，再到双面打印文件的碎纸片拼接，每一个问题都在不断考验我们的思维能力和技术水平 。

在这个过程中，我们深刻体会到数学建模和编程能力的紧密结合是解决复杂问题的关键。数学建模为我们提供了分析问题的思路和方法，通过建立合理的模型，将实际问题转化为数学问题，从而找到解决问题的方向。而编程能力则是实现模型的工具，借助计算机强大的计算能力和高效的数据处理能力，我们能够快速地对模型进行求解和验证 。例如，在处理大量碎纸片的拼接问题时，通过编写代码实现自动匹配和拼接，大大提高了效率和准确性。

这次竞赛也让我们认识到团队协作的重要性。在解决问题的过程中，团队成员需要分工明确、密切配合，充分发挥各自的优势。有的成员擅长数学建模，能够提出创新性的思路和方法；有的成员编程能力强，能够将模型转化为可运行的代码；还有的成员则在数据处理和结果分析方面发挥着重要作用。只有团队成员齐心协力，才能在有限的时间内完成复杂的任务 。

对于广大数学建模爱好者和学生来说，参与数模竞赛是提升自身能力的绝佳途径。通过参与竞赛，不仅可以锻炼自己的数学思维、编程能力和团队协作能力，还能够拓宽知识面，了解到不同领域的实际问题和解决方法。希望更多的人能够积极参与到数模竞赛中来，在这个充满挑战和机遇的舞台上，不断提升自己，创造更多的可能 。