简介这是一份面向数学建模学习者的碎纸片拼接复原完整资源包以MATLAB实现自动识别、定位、配对与复原的完整流程适用于图像处理、模式识别相关赛题或课设研究。包内共892个文件核心包括874张bmp碎片图像用于实验与测试、9个m源文件实现预处理、边缘检测、连通域分割、轮廓匹配与拼接复原等关键算法、2个mat数据文件及1份原版论文pdf另有少量jpg示例图整体压缩包约14.07MB。资源附带原版论文与附录详细说明了碎片重叠、光照变化、背景干扰等难点及对应的数学模型和优化方法附录中还包含实验数据与代码注释有助于理解算法设计思路并复现实验过程。目前已有1845人学习下载适合数学建模竞赛参赛者、图像处理初学者作为从理论到实践的参考资料。1. 碎纸片拼接复原数学建模竞赛里最容易被低估的送分题碎纸片拼接复原这道题表面上看是在处理图片实际上考的是你把一个实际问题抽象成数学模型的能力。很多同学第一眼觉得“用PS拼一下就完事”结果连第一问的规则切片都拼不到100%正确率。评委和面试官最爱拿这道题去筛人它既考像素级细节又考全局优化还考你能不能把结果讲清楚。本文直接把考点分布、高频算法、答题模板和易错点拆给你照着练拿国奖不好说省奖以上是够用的。2. 考点分布一道碎纸片题到底在考哪些建模能力2.1 图像数字化与预处理灰度、二值化、边缘提取的得分点碎纸片题的第一步不是拼而是把图片读成数据。评委手里拿的是像素矩阵你的算法也得从像素矩阵出发。正式建模前必须说清楚图像是什么格式、彩色还是灰度、每张碎片多大、碎片边缘是否带扫描阴影。把这些写在论文里比你上来就甩一个匹配公式要加分得多。先把彩色图转灰度标准公式是Gray 0.299 * R 0.587 * G 0.114 * B。有些同学直接按 RGB 三通道分别匹配不是不行但会放大颜色噪声尤其是扫描文档边缘有阴影时三通道误差会叠加。稳妥做法是转灰度后做一次中值滤波或高斯滤波去掉扫描噪点。注意别过度平滑——碎片边缘的锯齿是拼接的关键信息滤波核太大等于把特征磨平了。然后是二值化。文档碎片通常是白底黑字二值化能让背景变成 0、文字变成 1最后一行和第一行的匹配只看黑色像素分布计算量小很多。但二值化阈值很玄学固定阈值 128 经常翻车建议用大津算法自动选阈值代码就几行import cv2 th, img_bin cv2.threshold(img_gray, 0, 255, cv2.THRESH_BINARY cv2.THRESH_OTSU)注意这里的th是自动求出的阈值不需要你自己拍脑袋。二值化后不要急着匹配先做边缘提取。这里有一个高频坑很多人直接用整张二值图匹配忽略了碎片边界那一圈白边。扫描碎片时边缘通常有 1 到 2 像素的空白像素不处理的话所有碎片之间的差异都会很小等于没区分度。正确做法是只取左右边缘各 5 列像素或者先用边缘检测把边界定位出来。边缘提取不是必须的但能显著提速。几百张碎片边缘匹配要循环上万次每次算 1000 行像素差如果全图计算时间会翻好几倍。用边缘特征向量代替全图矩阵评委会觉得你有“建模意识”。这里再补一句如果碎片是不规则的还要先做旋转校正把每张碎片的主方向旋转到水平否则后续所有匹配都会乱套。旋转可以用图像矩求主轴角度这是另一个独立考点但每年都有题目不说明碎片方向所以值得提前准备。2.2 匹配模型从像素差到特征向量评委想看的三种建模思路匹配模型是整道题的核心得分点。碎片拼接的本质是找相邻关系怎么定义“相邻”决定了你的模型层次。评委看到三种递进思路通常会按层次给分。第一种思路是直接算像素差也就是欧氏距离。把左右边缘像素分别拉成向量计算对应位置灰度差绝对值之和距离最小的就是候选邻居。这个思路简单但评委只会给基础分因为它忽略了文字行结构遇到空白区域多的碎片会乱配。我见过一份论文全篇只用了这个模型最终错误率 30%分数很低。第二种思路是加权的像素差。文字行的边缘特征比空白行重要所以对边缘像素按梯度幅度加权。比如用 Sobel 算子的水平梯度值作为权重笔画越明显的位置权重越高。这个思路能从大量碎片中稳定找出正确匹配尤其是中英文混排的碎片。你需要写清楚为什么文字行权重大因为文字行包含可验证的连续性信息而空白行在所有碎片中都一样没有区分度。第三种思路是中文文档特有的“行特征”。中文碎片的文字是连续方块左右边缘的笔画分布很有规律。把每行边缘像素中黑色像素个数统计成直方图再比较直方图相似度。这种特征向量维度低、抗噪强特别适合规则横切碎片。三种模型的区别可以整理成一张对比表建模思路特征来源抗噪能力计算量适用场景像素绝对差原始灰度值弱中无阴影的清晰切片梯度加权像素差Sobel 梯度幅值中中扫描抖动、有阴影的文档行纹理直方图每行黑色像素计数强低中文规则横切碎片这里送你一个答题模板先描述问题再给出相似度公式然后做一个小实验说明不同阈值下的匹配效果。评委最讨厌只有公式没有验证的论文。哪怕只是给一个 3 张碎片的匹配实验也比光讲道理强。模板句式是“我们定义碎片 i 与碎片 j 的匹配代价为 C(i,j)其计算方式如下……为验证该代价的合理性我们随机选取 3 组真实相邻碎片与非相邻碎片进行对比结果为……”这样一段话直接把你从“会调包”提高到“会建模”。2.3 全局优化为什么单看边缘一定会拼错TSP 与聚类怎么用只看两两匹配正确率通常卡在 70% 左右上不去。原因很简单局部最优不等于全局最优。碎片 A 和 B 的边缘最像但 A 真正的位置可能在 C 的左边。这类题最经典的坑就是贪心拼接先找最像的一对拼起来然后继续找下一个最像的结果到后半段全乱。正确的建模套路是把问题抽象成全局优化。把每张碎片看成节点把两两之间的匹配代价看成边权那么拼接顺序就是一条遍历所有节点的路径而且必须满足拼完之后整体最连续。这就是一个哈密顿路径问题可以直接套 TSP 模型或者用最小生成树近似求解。对规则碎片比如只按行切可以降成排序问题同一行的碎片按横坐标排序用动态规划求最优排列。对不规则碎片常见的做法是先用聚类把碎片按“行”分组再组内排序、组间拼接。聚类特征可以用图像投影的纹理分布曲线也就是每一行黑色像素的数量构成一个向量。这样能避开全局 TSP 的 NP 难度拿到稳定解。评委想看的不是你有没有跑出结果而是你怎么处理“匹配代价不够可靠”这件事。这时你得引入置信度如果最小代价和次小代价很接近说明这个匹配不可靠宁可跳过也不能硬拼。这道题里“不自信的算法”比“自信的错误”拿分更高。你可以在论文里写当C_min / C_second 0.7时才接受该匹配否则标记为待定由全局优化决定。这个阈值也是一个可调参数画一条曲线展示错误率随阈值变化评委立刻觉得你做过系统实验。3. 高频考点三类必考匹配算法与代码模板3.1 左右边缘像素差匹配最朴素的 baseline 与得分下限先写一个能跑通完整流程的 baseline。假设你已经把碎片读成灰度图列表每张图高 H、宽 W。对碎片 i 和碎片 j计算 i 的右边缘与 j 的左边缘的匹配代价。最简单的公式是只取一列cost sum( abs( img_i[:, W-1] - img_j[:, 0] ) )但实际扫描碎片边缘会有倾斜和噪声取一列太脆弱。推荐取边缘宽度 d5 列做平均绝对差import numpy as np def edge_distance(img_left, img_right, d5): # 取左侧碎片右侧 d 列、右侧碎片左侧 d 列求平均绝对差 h img_left.shape[0] diff 0.0 for offset in range(d): diff np.abs( img_left[:, img_left.shape[1] - 1 - offset].astype(float) - img_right[:, offset].astype(float) ).sum() return diff / (h * d)注意这里必须用astype(float)否则两张 uint8 灰度图相减负值会直接溢出成 0 附近的大正数匹配结果全是乱的。这个坑每年都有人踩而且不容易自查因为只跑一两对看不出问题跑完整组才崩溃。写论文时把这个数据类型问题也写进去证明你考虑过数值稳定性。算完两两代价后用贪心法对每一行碎片排序从最左端开始每次选代价最小的右邻接碎片直到所有碎片用完。然后检查整条链的左右边缘总代价如果总代价太大说明可能方向标反了把整行翻转后重新匹配。这个 baseline 是得分下限能拿到 60% 左右正确率但想冲 90% 以上必须加改进。它最大的问题在于两个非相邻碎片如果恰好都有大片空白边缘代价也会很小导致错误连接。所以 baseline 只适合作为对比参照不适合当最终模型。3.2 基于特征点的匹配改进Sobel、Harris 还是均值哈希改进方向是特征工程。文档碎片匹配的核心特征是笔画形状比灰度值稳定。用 Sobel 算子提取水平梯度Gx然后对边缘区域做梯度向量余弦相似度sim sum( grad_i[k] * grad_j[k] ) / ( ||grad_i|| * ||grad_j|| )这个相似度只看边缘走势不受整体亮度影响。代码片段import cv2 def grad_similarity(img_a, img_b, margin10): # 提取水平梯度 gx_a cv2.Sobel(img_a, cv2.CV_32F, 1, 0, ksize3) gx_b cv2.Sobel(img_b, cv2.CV_32F, 1, 0, ksize3) # 取右侧边缘和左侧边缘的梯度列 vec_a gx_a[:, -margin:].ravel() vec_b gx_b[:, :margin].ravel() dot np.dot(vec_a, vec_b) norm np.linalg.norm(vec_a) * np.linalg.norm(vec_b) return dot / (norm 1e-9)注意margin不能太大否则会把相邻碎片的笔画混进来也不能太小否则噪声权重过高。这个参数就是“调参玄学”建议把 margin 从 3 到 15 做个网格搜索画出正确率曲线论文里放这张曲线图。如果你发现 margin10 时正确率最高就在论文里解释因为扫描仪的分辨率决定了边缘笔画的对齐范围大约相当于 10 个像素的实际长度。Harris 角点特征适合不规则碎片因为角点能定义碎片的几何形状。但文档碎片大多是直线切边角点很少用 Harris 反而没优势。均值哈希适合做粗筛速度快但精度不够。结论文档碎片首选 Sobel 加余弦相似度几何碎片首选角点加边缘距离。把这句话写在论文的“方法选择”一节评委会觉得你有针对性分析而不是把所有算法都堆上去。改进后的匹配代价不再是“距离”而是“相似度”。所以全局优化时要把相似度取反或者用1 - sim作为代价。注意相似度范围是 -1 到 1如果两段边缘完全反向相似度为负说明这两个碎片不仅不像而且一正一反也可以作为方向判断的依据。3.3 全局拼接的图论模型最小生成树还是 TSP匹配代价有了接下来是优化。把碎片视为节点边权为1 - sim求一条经过所有节点的最短路径。但精确 TSP 在碎片数超过 50 时基本跑不动需要近似解法。最小生成树是常用近似。对每一组碎片用 Kruskal 算法求 MST再对树做深度优先遍历得到一条路径。MST 与真实拼接顺序不会完全一致但能保证全局边权和最小错误率通常低于贪心法。关键改进是不要直接对整幅图做 MST先用聚类把碎片按行分组组内排序后再对组间做 MST。这样可以避免跨行误拼因为不同行的碎片边缘纹理可能相似跨行连接的代价虽小但全局模型一定是分行的。如果你要拿高分建议直接用动态规划做单行排序。把“已经拼过的碎片集合”和“最后一片碎片编号”作为状态状态转移方程如下dp[mask][last] min( dp[mask without last][k] cost[k][last] )代码骨架from functools import lru_cache lru_cache(None) def dp(mask, last): if mask (1 n) - 1: return 0, [last] best_cost float(inf) best_path [] for nxt in range(n): if not mask (1 nxt): cost, path dp(mask | (1 nxt), nxt) cost cost_matrix[last][nxt] if cost best_cost: best_cost cost best_path [last] path return best_cost, best_path这个 DP 只能处理十几张碎片但比赛中单行碎片数量通常不超过 20正好能跑。论文里写清楚状态定义、转移方程和边界条件比跑一个黑匣子遗传算法更容易让评委复现。如果你嫌递归太慢可以改成迭代式 DP顺序是从全 1 的掩码倒推或者用二进制枚举。实际实现时注意掩码要从 0 到(1n)-1枚举并且倒序遍历否则会出现状态依赖问题。还有一个细节多行拼接时行与行之间的对齐不止是上下边缘匹配。因为每行碎片是独立排序的拼出来的行长度可能不一致需要设定统一的纵向坐标。在这种情况下可以用“上下边缘代价之和最小”作为一个全局优化目标用动态规划同时决定行顺序和列顺序。这才是这道题真正拉开分数的地方。4. 真题演练一道典型的规则/不规则碎片拼接题怎么答4.1 题目重述与建模假设以某年竞赛真题为例给出一张被切分成若干规则长方形的碎片要求复原原图。碎片以 BMP 格式给出每个碎片大小一致但方向未知可能出现上下左右旋转。这道题的陷阱是没有告诉你碎片是否旋转你必须自己判断。这类题必须先写假设假设碎片都是正放的或者假设方向已知。如果题目没有说明方向那你必须在论文里显式处理方向问题。处理方式很简单对每对匹配计算正向匹配代价和反向匹配代价取较小值并记录方向。这个预处理能让你少走一半弯路。第二步是数据清洗。找出碎片中的空白碎片、全黑碎片这类碎片没有边缘特征要单独剔除否则匹配矩阵里会出现大量假相似。用行标准差做过滤如果某张碎片的标准差低于阈值认为它是空白页或装饰线。实现如下std_threshold 15 blank [i for i in range(N) if np.std(fragments[i]) std_threshold]阈值怎么选可以先打印所有碎片的标准差分布取分布中明显凹陷处的值。这个操作证明你处理过数据而不是盲目设定。4.2 算法设计分而治之的拼接流程推荐一个能拿奖的完整流程先聚类分行再组内排序最后组间拼接。这个流程把 NP 问题拆成多个小规模子问题每一步都可用数学描述。读取所有碎片转灰度、二值化提取边缘特征向量。对每一对碎片计算双向匹配代价得到代价矩阵。用 KMeans 或层次聚类按纹理特征分组每组对应原图一行。对组内碎片用动态规划求最优排列得到行内顺序。对行与行用上下边缘匹配纵向拼接得到完整图像。KMeans 分组时聚类数 k 是一个超参数。如果你不知道原图有几行可以用肘部法则画出 SSE 随 k 变化的曲线找到拐点。例如 k 从 1 到 10SSE 在 k4 之后下降变缓那就取 k4。这个实验步骤写进论文比直接说“我们分成 4 组”可信得多。组内排序用上一节的 DP。组间纵向拼接时需要注意每行碎片数量可能不一致。如果规则切片每行碎片数相同直接按顺序堆叠如果碎片数量不同说明可能存在缺失或空白碎片这时需要把空白碎片也纳入聚类否则行长度对不上。处理方式是先把空白碎片单独保留待所有非空白碎片拼完后再用空白碎片填充到对应位置。4.3 结果呈现错误率、可视化与误差分析竞赛论文最怕光有算法没有结果。题目通常会提供原图因此你可以计算拼接结果的错误率。错误的定义有两种一种是碎片级别的错位一种是像素级别的误匹配。碎片级别错误率 放错位置的碎片数 / 总碎片数。注意错位包括左右颠倒和上下颠倒。你必须给出一个拼接前后的对照图。如果算法在某个位置拼错了用红框标出来并在论文里解释原因“因为该碎片右边缘文字较密集且左右两侧均有相似笔画算法难以区分”。这种解释比“算法效果很好”可信得多。评委宁可看到你承认错误并分析也不想看到一份完美但空洞的汇报。误差分析表格至少要有两行规则碎片结果和不规则碎片结果。列设计为总碎片数、正确匹配数、错误率、运行时间。用这个表对比 baseline 和优化算法算法正确匹配数错误率运行时间像素差 贪心176 / 20915.8%42 秒像素差 DP189 / 2099.6%88 秒Sobel DP 方向处理203 / 2092.9%131 秒这个表格一放你的改进幅度一目了然。评委评审时第一件事就是找表格和图片你要把最有说服力的结果放在最显眼的位置。5. 易错点碎片拼接最容易翻车的位置、灰度和方向5.1 方向假设没写清楚结论全部崩盘错在哪有些同学默认所有碎片都是正放的没有检查方向结果匹配出大量反向拼合。为什么错扫描碎片时碎片的方向完全是随机的。你有 50% 的概率把右边缘当成左边缘匹配代价会突变。不处理方向前 30% 的匹配必然错误。怎么答对在数据预处理阶段对每张碎片生成正向和翻转两个版本对每对碎片计算四种组合的代价正向-正向、正向-翻转、翻转-正向、翻转-翻转取最小值同时记录方向。算完再拼最后统一把翻转的碎片转回来。代码里就多一个np.flip操作但这一步能让正确率提升 10 到 15 个百分点。5.2 只匹配左右边缘忽略上下边缘导致行错位错在哪拿到题目先想到左右拼接忽略了上下边缘。很多碎片在纵向切分后上下边缘也有连续的文字纹理。只拼左右最后行与行之间对不齐原图整体错位。为什么错左右匹配计算量小先做容易的上下匹配涉及行间距特征不明显容易偷懒。但完整建模必须考虑上下相邻关系否则每行拼对了行与行之间差几个像素整张图看起来还是乱的。怎么答对把匹配代价拆成横向和纵向两个矩阵行拼接用横向矩阵列拼接用纵向矩阵最后用二维网格优化整体位置。如果碎片不是规则网格用前面说的先聚类再排序的流程每行碎片先拼成一条长带子再用长带子之间上下边缘匹配。5.3 灰度图直接匹配被阴影和噪点带偏错在哪没有预处理直接用原始扫描图匹配。扫描件边缘有一圈黑边或阴影匹配时阴影区域灰度差异小导致所有碎片之间的代价都很接近区分度消失。为什么错阴影区域面积大在绝对差求和时占比高真实笔画差异被淹没了。尤其是纸张边缘的卷曲会造成 2 到 3 像素的偏移。怎么答对匹配前先做中值滤波再裁掉边缘 1 到 2 像素的阴影带。或者用梯度特征代替原始灰度。梯度特征不受整体亮度影响阴影区域因为灰度平缓梯度值低自动降低权重。梯度特征还有一个好处扫描时的光照不均会被降噪归一化后更稳定。5.4 匹配代价归一化做得太粗糙空白碎片干扰全局错在哪没有归一化不同碎片边缘的黑色像素数量不同导致代价数值不在同一量纲上。为什么错有的碎片边缘几乎没有文字匹配时代价天然小会被误判为最相似。大量空白碎片会吸引所有匹配把正确顺序打乱。怎么答对用相对差异而不是绝对差异。比如归一化到 0 到 1 的余弦相似度或者用diff / sqrt(黑色像素数 1)。对空白碎片直接剔除不参与匹配。如果绝对差代价可以先统计所有碎片两两匹配代价的最大最小值再做归一化但要防止离群值干扰建议用中位数和四分位数做归一化。5.5 结果评估只用正确率一个数字不给错误样例错在哪论文里只写正确率达到 95%没有展示错在哪里。评委一验证发现错误正好出现在关键位置直接怀疑你虚报。为什么错正确率是整体指标掩盖了局部失败模式。比如中间某两片完全空白算法可能随机拼接正确率掉 5%但你不知道是哪一步导致的。怎么答对给一个局部错例分析。挑一张拼错的碎片展示它左右两侧的边缘像素说明相似度接近的原因。这种分析能证明你理解了失败原因而不只是把测试集跑了一遍。具体操作在论文中插入两张相近边缘的灰度对比图然后用一两句话解释“这两个区域均为横线隔断边缘梯度分布几乎一致导致代价函数失效”。这比任何指标都有说服力。6. 答题技巧让评委一眼认定你模型可复现的三个细节6.1 把数据格式和标定写清楚很多论文一上来就贴公式却不说明输入图片是什么格式、像素值范围是多少。评委复现时第一步就是读数据读不出来模型再好也白搭。建议在论文开头用一段话描述数据格式图像尺寸、颜色通道、文件命名规则、是否包含空白碎片。再配合一张数据预览图把前 5 张碎片的缩略图贴在附录里。这些信息让评委觉得你真正处理过数据而不是只会调包。6.2 用表格对比 baseline 与优化算法不要只放一张最终拼接效果图。评委想看到你的改进有据可查。用一张三列的表格算法名称、错误率、运行时间。第一行是像素差加贪心第二行是像素差加 DP第三行是 Sobel 加 DP 加方向处理。这样一个对比表放在结果章节中间改进幅度一目了然。注意表格里要写实际运行时间哪怕你的电脑跑得很慢也如实写。评委要的是可复现性和真实性不是性能竞赛。6.3 给一个局部放大图证明拼接有效最后呈现结果时不要只给整张拼好的大图。整图在论文里缩小后看不出细节。选一处文字密集的边缘比如某个汉字横跨碎片交界处把交界处放大到 200%标出笔画连续对齐。这个证据比任何指标都有说服力。如果找不到完全对齐的字也选一个笔画断点最少的位置说明“误差小于 1 像素”。这三条细节做下来论文的工程完整度会上一个台阶。我自己当年做这道题时第一次交上去的结果正确率 82%但评委反馈说看不懂我的匹配矩阵。后来我把边缘差异的热力图画出来把方向修正和深度搜索分开写再交上去分数立刻上去了。从那以后我每次做仿真或建模题都会强制自己把“数据长什么样、算法怎么跑、结果如何证明”这三段走一遍。希望这份笔记能帮你少走一次弯路在纸面上多拿几分。本文还有配套的精品资源点击获取
