碎纸片拼接复原算法：灰度边缘距离与人工修正的工程实践

简介面向数学建模学习者与图像处理实践者的碎纸片拼接复原项目资料借助MATLAB工具实现碎片信息的自动重组。压缩包内共八百九十二个文件大小约十四点零七兆字节其中八百七十四张位图文件作为碎纸片样本九个脚本源文件为MATLAB代码另有少量结果图片、数据文件及一份原版论文。目前已有一千八百四十五人学习或下载。资料围绕图像预处理中的灰度化、二值化、去噪边缘检测中的坎尼与索贝尔算子片段分割的连通组件分析配对旋转的轮廓匹配与几何变换以及拼接复原的图像融合等关键步骤展开代码与论文相互对应可帮助读者理解这些算法在真实碎片问题中的具体运用。附录还提供了实验数据与操作说明便于按步骤复现完整流程既可用于数学建模竞赛备赛也适合作为图像处理课程设计或算法研究的参考。1. 碎纸片拼接复原拿到赛题数据后先别急着拼眼睛做数学建模或档案数字化时最容易卡住的就是碎纸片拼接复原这类题一张文档被横向切成 19 条、11 条甚至先纵切再横切成几百个小块。用肉眼拼一两条还行数据一多人眼找相邻碎片的效率极低而且很容易被相似的文字区域带偏。碎纸片拼接复原的标准解决思路是用边缘列之间的灰度距离代替人工比对由程序按距离分数贪心排出一条顺序最后再用人工修正收尾。这套流程在 MATLAB、Python 里都能落地资源包里通常也包含完整的赛题图片、脚本和说明。这篇笔记就把两个关键环节拆开讲灰度边缘距离怎么算才稳混合切割碎片怎么聚类加人工修正并记录几个容易翻车的参数坑。2. 灰度边缘距离匹配核心算法与一个容易被忽略的参数2.1 边缘距离为什么能拼出文档顺序横切碎片的拼接本质是在找相邻关系。每条碎片左右两侧各有一条由裁纸刀切出来的边切开的边缘会把原本连续的印刷内容从中间截断比如汉字“拼”的左半边在碎片 A 的右边缘右半边在碎片 B 的左边缘。整行文字沿横向分布所以真正决定相邻关系的是这两条切口边缘上的像素灰度分布是否衔接得上。如果直接拿整列像素做差会受到文段内部空白区域的干扰如果只比较最外面一列又会被扫描噪声、轻微倾斜影响。常见做法是各取边缘处若干列构成窄带逐像素比较灰度后取平均。因为打印字体边缘有笔画、衬线等高频信息这个平均距离在真正相邻的碎片对之间会明显小于无关碎片对。这也是为什么大部分数学建模赛题解法都用灰度边缘距离而不是 SIFT 或 ORB 特征文档图像场景简单、纹理单一特征点往往集中在少量汉字上反而没有像素级距离稳定。function d edge_gap(A, B, band) % 计算两个碎片在左右边缘的灰度距离 % A 为左侧碎片B 为右侧碎片band 为边缘比较宽度单位像素列 if nargin 3 band 5; end seg_a double(A(:, end-band1:end)); seg_b double(B(:, 1:band)); d sqrt(mean(mean((seg_a - seg_b).^2))); end这段代码做了三件事把两侧 band 列取出来逐像素求差后平方再取整体均值。使用 L2 距离是因为它对笔画边缘的响应更敏感文字区域灰度跳变剧烈平方项能把真正错位的像素差值放大让正确匹配和错误匹配之间的分数差距更明显。如果改用 L1 绝对差分数整体会被文字内部的细小灰度波动拖平导致分数区分度下降。但 L2 也有一个副作用它会被扫描产生的阴影或光照不均放大所以后面避坑章会再讨论均值灰度对齐。band 参数的取值直接影响匹配质量band1 时只比较切口最外一列虽然计算量最小但这一列往往刚好落在字符的间隙或空白处信息量不足容易出现多对碎片分数相近的情况band 太大比如 band15就会把不是切口边缘的正文内容也卷进来距离分数反映的是整块文字区域的相似性而不是边缘衔接性。我一般取 band5对 200 dpi 左右的扫描文档这个宽度既能覆盖笔画断裂区域又不会超过半个字符宽度。如果图像分辨率更高按字符宽度估算band 取字符宽度的三分之一比较稳妥。2.2 找起点、贪心链以及“先左后右”的推进顺序有了两两距离后拼接顺序基本就是一条贪心链先从所有碎片里找到最左侧的那张然后反复跟当前碎片右边缘距离最小的碎片往后接。问题在于最左侧碎片怎么确定。文档被完整切开后最左侧碎片的最左边一列应当是纸张原始边缘也就是接近纯白的空白区域。这个白色特征在灰度图上非常稳定只要扫描时没有大片阴影白纸部分灰度值都在 245 以上。function left find_leftmost(strips) % strips 是元胞数组每个元素是一张灰度图像矩阵 % 返回最左侧碎片的索引 for i 1:numel(strips) first_col strips{i}(:, 1); if mean(first_col 245) 0.95 left i; return; end end error(没有找到符合条件的白边请检查图像是否旋转或阈值是否合理); end这里用“均值大于 0.95”而不是“全部大于 245”是为了容忍扫描时个别像素上的噪点或轻微灰尘。只要 95% 以上的像素落在白色区域就判定为纸边。拼链代码同样用一个距离矩阵来加速function order greedy_chain(strips, band) n numel(strips); % 预先计算两两之间的边缘距离 D zeros(n); for i 1:n for j 1:n D(i, j) edge_gap(strips{i}, strips{j}, band); end end order zeros(1, n); used false(1, n); order(1) find_leftmost(strips); used(order(1)) true; for k 2:n cand find(~used); [~, idx] min(D(order(k-1), cand)); order(k) cand(idx); used(order(k)) true; end end这个实现把两两分数先算好后面每次只查一行最小值。n19 时总共 361 次边缘距离计算哪怕每张图 2000×200 像素MATLAB 里也只要几秒钟。n209 时是四万多对属于中等规模同样能接受。要注意 MATLAB 的 min 函数返回的第一个最小值索引当分数完全相同时会选索引小者这本身不是问题但一旦出现“分数并列”说明当前碎片与多个候选的匹配度都接近这在第五章避坑里会提到如何使用距离阈值来提前发现这种风险。2.3 灰度预处理降噪与归一化不能省边缘距离对灰度绝对值比较敏感。同一个扫描仪在两次扫描之间亮度可能发生轻微波动导致碎片整体偏亮或偏暗。比较两个碎片时如果一个整体偏亮另一个整体偏暗即便内容是连上的平方距离也会被拉高。常见的处理是先把每个碎片转成 double 类型然后减去自身均值让比较对象从“绝对灰度”变成“相对灰度”。这样处理后文字区域和空白区域的差值关系不变但不同碎片之间的亮度差异被抵消了。function strips preprocess(raw_cell) strips cell(size(raw_cell)); for i 1:numel(raw_cell) img double(raw_cell{i}); if size(img, 3) 3 img rgb2gray(uint8(img)); end strips{i} img - mean(img(:)); % 中心化消除整体亮度差 end end中心化之后再跑 edge_gap就会发现原本因为亮度差导致的高分现在明显降下来了。这个预处理在后续行聚类里同样适用因为它保证的是碎片之间的相对关系。3. 把赛题数据跑通完整流程与脚本走查3.1 资源包里的脚本结构与主入口拿到一份“碎纸片拼接复原”资源包里面通常会有赛题提供的图片文件夹、一个主脚本 main_stitch.m、若干辅助函数 edge_gap.m、find_leftmost.m以及一份说明文档。主脚本完成的事情是固定的读图、灰度化、预处理、算距离、贪心拼接、输出结果。我一般会先把主脚本从头到尾读一遍确认它的输入路径是相对路径还是绝对路径因为赛题图片经常被放在子文件夹里路径对不上是第一个翻车点。资源包里的主脚本大致长这样clear; clc; data_path ./data; files dir(fullfile(data_path, *.jpg)); n length(files); strips cell(1, n); for i 1:n strips{i} imread(fullfile(data_path, files(i).name)); end strips preprocess(strips); order greedy_chain(strips, 5); for i 1:n fprintf(第 %d 张: %s\n, i, files(order(i)).name); end out cat(2, strips{order}); imwrite(uint8(out), restored.png);这段脚本的流程很清晰先把文件夹里所有 jpg 读进来做预处理然后调用 greedy_chain 得到顺序最后用 cat(2,...) 横向拼接并保存。要注意 dir 返回的文件名是按字母序排列的而赛题图片命名通常是 001、002、003 这类数字所以顺序不一定等于拼图顺序必须用算法输出的 order 去索引。3.2 中文数据 19 条从图片到顺序以经典的 19 条中文文档为例实际运行时我会把 band 从 5 改到 3 或者 7 各跑一遍比对两次输出的拼接结果。为什么这样做因为 band 偏大时匹配距离会受字符整体结构影响band 偏小时噪声影响变大。如果两次 band 输出顺序完全一致说明拼接结果稳定如果中间有几个位置不同这些位置往往就是人眼也容易看错的区域需要重点检查。% 两个 band 的结果对比找出不一致位置 order5 greedy_chain(strips, 5); order7 greedy_chain(strips, 7); diff_idx find(order5 ~ order7); disp(diff_idx);这一步很值得做。跑题跑一次不难难的是知道哪一步不可信。两个不同 band 下输出不一致的索引通常就是匹配分数接近、算法最不确定的地方。把这几个位置对应的碎片单独显示出来用肉眼确认比直接信任一次拼接结果可靠得多。3.3 用 Python 重写一边省掉 MATLAB 授权问题并不是每个读者都有 MATLAB许多赛题资源包默认给的是 MATLAB 脚本但 Python 重写并不复杂。核心逻辑完全一样只是用 NumPy 替代矩阵操作。下面给出一个等价实现import numpy as np from PIL import Image def load_strip(path): img Image.open(path).convert(L) return np.array(img, dtypenp.float64) def edge_gap(a, b, band5): seg_a a[:, -band:] seg_b b[:, :band] return np.sqrt(np.mean((seg_a - seg_b) ** 2)) def find_leftmost(strips): for i, s in enumerate(strips): if np.mean(s[:, 0] 245) 0.95: return i raise RuntimeError(没有找到白边) def greedy_chain(strips, band5): n len(strips) d np.zeros((n, n)) for i in range(n): for j in range(n): d[i, j] edge_gap(strips[i], strips[j], band) order [find_leftmost(strips)] used set(order) while len(order) n: cur order[-1] cand [i for i in range(n) if i not in used] nxt min(cand, keylambda i: d[cur][i]) order.append(nxt) used.add(nxt) return order这段 Python 的 edge_gap 与 MATLAB 版完全等价用 numpy 的切片特性一次性取出边缘矩阵。运行时如果发现某个碎片匹配分数特别低而其它候选分数都高出不少就说明这一步是可确定的反过来如果最佳候选和第二候选只差 0.5%说明这里存在歧义需要直接看原图。3.4 输出拼接热力图找出可疑位置如果只输出最终顺序看拼接结果是黑匣子。我习惯再把每对相邻碎片的边缘距离打出来做成一条趋势线哪个位置的分数明显高于前后哪里就是可疑接缝。edges zeros(1, n - 1); for k 1:n - 1 edges(k) edge_gap(strips{order(k)}, strips{order(k 1)}, 5); end bar(edges);正常情况下边缘距离曲线应该在 0 到 30 之间波动。如果某一对相邻碎片的距离突然冲到 80 以上几乎可以肯定那里接错了。当然这个分数没有绝对标准必须结合前后位置一起看这也是为什么我一直强调“先把可疑点定位再人工确认”。4. 纵切横切混合碎片的行聚类与人工修正4.1 为什么要先聚类再拼接双面切割问题里文档先被纵向切成若干竖直长条再横向切成小块得到的碎片既有文字内容又没有一条贯穿整张纸的长边。此时直接对所有小碎片两两算边缘距离匹配难度会上升很多因为每个碎片有四个方向任意两个碎片都可能存在上下或左右邻接搜索空间比横切情形大得多而且大量碎片整体是空白的容易相互误配。正确做法是先做行聚类把属于原始文档同一水平位置的小碎片归到同一组。因为横向切割的裁切线是完整的直线同一行内碎片的上边缘和下边缘跟各自上下相邻行的切割位置一致所以上下边缘的灰度模式可以作为聚类线索。观察一下就能发现同一水平带上的碎片它们上下边缘的空白分布和文字高度基本相同不同带之间的边缘文字分布差异则很大。基于这个事实可以先用上下边缘距离做相似度矩阵再按相似度把碎片聚成若干行。4.2 上下边缘相似度与行分组具体实现时需要定义一个新的比较函数只比较两个碎片上边缘和下边缘各自的灰度分布而不是整块图像。这里不比较左右只比较上下因为纵向切碎后的每一小块的上下边缘是横向裁切线留下的相邻行碎片之间的上下边缘是互补的。资源包里常出现的做法是把每个碎片向下缩成一行灰度值向量再对这个向量做两两距离。实际操作中我会取每个碎片的上边缘若干行以及下边缘若干行各算出一条平均灰度线然后比较任意两个碎片的上、下线相似度。function sim row_similarity(frag_i, frag_j, band_rows) ai double(frag_i(1:band_rows, :)); aj double(frag_j(end-band_rows1:end, :)); sim mean(mean((ai - aj).^2)); end这个函数的意义是frag_i 的上边缘和 frag_j 的下边缘理论上应该布满同一道横向切线。如果两个碎片原本属于相邻两行frag_i 的上边缘邻接 frag_j 的下边缘它们的边缘灰度带应当高度重合。对所有碎片两两计算这个分数然后做一次层次聚类就能把同一行的碎片分到一起。需要注意一个细节比较上下边缘时碎片宽度不一定一致因为纵向裁切位置可能错开。严格实现时要把两个边缘向量做中点对齐之后再按重叠区域比较否则宽度不同的碎片之间分数会偏高。常见简化方式是先对每个碎片插值到固定宽度比如统一改成 256 列再做边缘比较。插值不影响边缘带内的灰度分布趋势但能让所有碎片在后续聚类时处于同一坐标系。聚好行之后每一行内部的碎片再使用第二章的 edge_gap 拼成完整行然后行与行之间再用上下边缘距离拼成完整页面。这个过程跟横切 19 条完全一样只是比较方向从左右变为上下。4.3 人工修正的半自动交互聚类和自动拼接完成之后通常还会残留少量错误这些错误几乎全部集中在文字稀疏或全空白区域。到这一步代码能做的是把候选拼接对挑出来给人看而不是让算法背锅。我习惯写一个小交互脚本程序自动拼接出候选顺序同时把每步的最佳、次佳匹配分数打印出来如果最佳分数与次佳分数差距小于 5%脚本就暂停并显示这两个候选的碎片边缘。function [order, warn_list] greedy_with_warning(strips, band, thresh) % thresh 为次佳分数与最佳分数的相对差距阈值例如 0.05 % 返回顺序和需要人工确认的位置索引 n numel(strips); D zeros(n); for i 1:n for j 1:n D(i, j) edge_gap(strips{i}, strips{j}, band); end end order zeros(1, n); used false(1, n); order(1) find_leftmost(strips); used(order(1)) true; warn_list []; for k 2:n cand find(~used); scores D(order(k-1), cand); sorted_scores sort(scores); if numel(sorted_scores) 1 sorted_scores(2) - sorted_scores(1) thresh * sorted_scores(1) warn_list(end1) k; % 记录该位置后面人工看 end [~, idx] min(scores); order(k) cand(idx); used(order(k)) true; end end这段代码在第 2 章贪心链基础上加了一个警告机制。thresh 设为 0.05 时表示当第二名比第一名差不到 5% 就把位置记录下来提示人工介入。人工介入的操作也很简单把这一对相邻碎片的边缘图裁剪出来左右拼在一起看如果字迹衔接自然就保留否则试第二名。这类交互不会太频繁通常一份 200 块左右的混合碎片需要人工修正的位置在 5 到 15 处之间。5. 碎纸片拼接避坑五条血泪记录5.1 高分假匹配两片空白边缘互为最优现象拼接结果里出现连续几行都是空白后面接的碎片完全不搭但算法认为分数足够低。原因相邻碎片边缘都是空白区域时灰度距离天然就是 0算法把一张空白边缘和另一张空白边缘当成了最优匹配。这在纯文本文档里很常见段落换行处会连续多行空白。解决判段匹配时加入对空白区域的惩罚项。如果在比较边缘带时检测到某一侧完全是空白就把这个候选对的距离加上一个固定惩罚值比如在 edge_gap 返回值上增加 20。也可以直接统计每个碎片的“边缘空白比例”两个空白边缘比例都超过 80% 时不参与匹配优先让有实际文字内容的碎片先拼最后再把空白行插入到对应位置。5.2 起点检测失败扫描件整体偏暗现象find_leftmost 报错找不到任何碎片最左列大于 245。原因扫描仪的亮度设置偏暗或者文档纸质偏黄、偏灰灰度图里白纸区域只有 200 左右而不是 245 以上。解决动态阈值用整张图的亮度分布来确定“白”的定义。常见做法是先统计所有碎片灰度值的中位数如果中位数低于 210说明整体偏暗把白边判断阈值下调到 200。或者不依赖绝对阈值而是比较每张碎片最左列均值和整张碎片均值之差差值大于某个绝对量就认为是纸边。function left find_leftmost_adaptive(strips) % 用全局亮度中位数估计白色阈值 all_pixels []; for i 1:numel(strips) all_pixels [all_pixels; strips{i}(:)]; end white_level max(210, median(all_pixels) 40); for i 1:numel(strips) if mean(strips{i}(:, 1) white_level) 0.9 left i; return; end end end这里的白阈值取“中位数加 40”是因为通常文档图像里白色背景占据一半以上中位数代表的是背景亮度背景亮再加上 40 就能把文字和噪声排除在外。5.3 灰度不均匀导致同一张纸左右明暗不同现象正确匹配的两个碎片边缘距离分数偏高反而一些无关碎片分数更低。原因扫描时光源在文档边缘的衰减比较明显同一张纸左边偏亮、右边偏暗导致切出来的碎片之间整体亮度差值比内容差异还大。解决在做 distance 之前先把每个碎片做均值中心化这正是第 2 章 preprocess 做的那步。如果中心化还不够可以再对边缘带内部做局部归一化让边缘带的均值和方差拉到同一范围。seg_a double(A(:, end-band1:end)); seg_b double(B(:, 1:band)); seg_a (seg_a - mean(seg_a(:))) / (std(seg_a(:)) 1e-5); seg_b (seg_b - mean(seg_b(:))) / (std(seg_b(:)) 1e-5);局部归一化后再算 L2 距离就可以消除边缘亮度差的影响。这里加 1e-5 是为了避免空白区域标准差为 0 时除零。要注意的是归一化会把纯白区域变成 0同时也把纸张上的淡色底纹变成伪信息所以只应在确认光照不均时使用。5.4 贪心链的连续错误一步拼错后面全乱现象顺序前 8 张都对第 9 张开始突然接错后面全部跟着错。原因贪心链每次只取当前最优一旦某个错误匹配被选中后面每一步都是在错误基础上继续找局部最优错误会像多米诺骨牌一样传递。解决在拼链过程中增加中断条件。当这一步的最佳分数与次佳分数差距低于阈值时直接停止自动拼接转而用人工交互模式把这一步确定后再继续。更彻底的做法是 “双向拼接”分别从左端和右端开始拼接中间相遇时检查是否吻合如果两边拼出的序列在中间区域冲突就说明至少一边有问题。5.5 图片尺寸不一致导致比较错位现象同一次扫描的碎片宽度、高度都有几像素偏差edge_gap 分数整体偏高且差别不大。原因扫描或预处理时对图像做了缩放或者原始文件本身来自不同批次拍摄导致两张相邻碎片在边缘处差了几个像素。直接整列比较时笔画位置对不上分数被无谓拉高。解决在 edge_gap 里加入“按行偏移对齐”步骤枚举 1 到 2 个像素的行偏移量取最小距离作为最终分数。这样做相当于允许两个碎片之间有一两行的错位能有效吸收扫描倾角带来的微小偏差。function d edge_gap_shift(A, B, band, max_shift) if nargin 4, max_shift 2; end d inf; for s -max_shift:max_shift if s 0 aa A(1:ends, :); bb B(1-s:end, :); else aa A(1s:end, :); bb B(1:end-s, :); end d min(d, edge_gap(aa, bb, band)); end end这段代码枚举了上下最多两行的偏移每次偏移后重新计算边缘距离取最小值。代价是计算量增加 5 倍但换来的是对微小倾斜的容忍在真实扫描文档里值得。6. 用自切碎的回测验证拼接结果拿到资源包并跑通主流程后最需要做的一件事不是直接交结果而是先验证这套代码的可靠性。我的习惯是自建一个回测脚本找一页清晰的中文 A4 文档用代码把它按同样的规矩切成 19 条记录真实顺序再乱序交给拼接算法。这样做的价值在于回测里的真实顺序是已知的可以对照算法输出检查每一步是否拼接正确。import numpy as np from PIL import Image # 生成一页和赛题风格相近的“假文档”白底黑字 page np.full((800, 600), 255, dtypenp.uint8) # 用文字块模拟内容实际使用时替换成真实文档图片 for y0 in range(100, 700, 60): page[y0:y020, 80:520] np.random.randint(0, 80, (20, 440)) strips_true [] for i in range(19): strips_true.append(page[:, i*32:(i1)*32]) order_true list(range(19)) np.random.shuffle(order_true) strips_shuffled [strips_true[i] for i in order_true] recovered greedy_chain(strips_shuffled, 5) print(真实顺序:, order_true) print(恢复顺序:, recovered)这段代码的好处是可控可以任意调整文本密度、是否加空白行、是否加噪声、是否加亮度不均来测试算法在不同条件下的鲁棒性。我实际跑下来发现纯文本密排情况下正确率接近 100%一旦加入大段空白区域就会在空白衔接处出现第 5.1 节说的假匹配。所以我会故意在回测集里留出几个段落间距较大的行看看算法是否会在这里翻车。有一个小技巧值得养成习惯每次跑完拼接保存结果前先看一次“相邻碎片边缘距离曲线”的可视化图把曲线上明显凸起的点位对应位置标出来。如果凸起点分布均匀且数值偏低说明结果可信如果某个位置突然飞高即使最后顺序肉眼看起来没什么问题也值得多盯一眼。曾经有一次回测里编辑器输出的顺序与真实顺序完全一致但边缘距离曲线在第 7 和第 8 个碎片之间出现了 60 的尖峰后来发现是扫描时两条碎片之间有 2 个像素的旋转错位加了按行偏移对齐后尖峰消失。从那以后我每次做完拼接都会强制生成这条曲线不通过曲线检查就不算跑完。希望这条经验对你也一样有效。本文还有配套的精品资源点击获取