2013B 碎纸复原拼接（一）：边缘相似度模型与拼接路径搜索

一、问题重述

2013 年国赛 B 题要求处理"碎纸片的拼接复原"：给定一张被切碎的文档，需由碎片的边缘信息推断其原始排列顺序，从而复原成完整文档。原题多为纵切（沿纵向把纸切成若干竖条），复原的核心是判断"哪一条碎片的右边，应当紧挨着哪一条碎片的左边"。

本文将问题抽象为：给定 $N$ 个纵切碎纸竖条，每个竖条带有左边缘特征向量 $L_i$ 与右边缘特征向量 $R_i$ ，建立碎片之间的边缘相似度模型，并据此进行排序/路径搜索，使复原出的排列尽可能还原真实位置序列。这一抽象抓住了"匹配—排序"这一赛题最本质的环节，又绕开了真实图像预处理的不确定性，使方法论可在本站合成数据上独立验证——真实参赛时只需把图像边缘提取环节接入本文的特征向量即可直接复用后续拼接框架。

二、数据与预处理

本文使用本站生成的合成练习数据集 data/cumcm2013b.csv。该数据集共 $N=19$ 条纵切碎纸竖条（与国赛原题"纵切 19 条"的规模一致），每条竖条被离散化为 $K=10$ 维的边缘特征：左边缘特征 $L_i\in\mathbb R^{10}$ 与右边缘特征 $R_i\in\mathbb R^{10}$ ，分别刻画该竖条左、右两条边界处的灰度剖面。数据集还给出每条碎片的"真实位置"标签（1 到 19，表示其在原始文档中的左右次序），用于评估复原准确率。

数据由固定随机种子确定性生成，保证可复现：原始文档剖面沿竖条序号作平滑演化（相邻竖条强相关、非相邻弱相关），从而"碎片 $i$ 的右边缘"与"碎片 $j$ 的左边缘"的相似度，在 $j$ 恰好是 $i$ 的真实后继（即 $j=i+1$ ）时达到峰值。碎片随后被随机打乱真实位置，模拟"切碎混入"的现实情形。

由于左右边缘特征同属灰度剖面，量纲一致、量级相近，本文不额外做 z-score 标准化（标准化不会改变余弦相似度的排序），仅在含噪实验中对特征叠加高斯扰动。

三、边缘相似度模型

拼接的本质是比较"上一条碎片的右边缘"与"下一条碎片的左边缘"是否吻合。设两特征向量 $a,b$ ，本文采用余弦相似度：

$\mathrm{sim}(a,b)=\frac{a^\top b}{\|a\|\|b\|}\in[-1,1]$

选用余弦而非欧氏距离，原因在于：文档剖面的绝对灰度会随内容整体平移（例如某段更亮），而相邻竖条的"相对结构"才是匹配依据。余弦相似度对向量的整体缩放不敏感，只捕捉方向一致性，更贴合"边缘是否连续"这一语义。记碎片 $i$ 与碎片 $j$ 之间的相似度为 $S_{ij}=\mathrm{sim}(R_i,L_j)$ ，并令 $S_{ii}=-1$ 排除自匹配。于是可得一张 $19\times19$ 的相似度矩阵 $S$ 。

图 2 给出该矩阵的热力图（行对应碎片右边缘、列对应碎片左边缘）。理想情况下，正确相邻对 $(i,j=i+1)$ 应位于近乎次对角线的位置并呈现高亮（相似度接近 1），而其余位置颜色偏暗。从图 2 可见：虽然碎片已被随机打乱，但真实后继对应的相似度峰值清晰可辨，说明"边缘吻合"这一信号在合成数据中被成功编码。

图 3 进一步给出某一条碎片（真实位置 6）的右边缘 $R$ 与其正确后继（真实位置 7）左边缘 $L$ 的逐维吻合曲线：两条折线在 10 个维度上几乎重合，直观印证了相邻竖条边缘灰度剖面的连续性——这正是相似度模型能够成立的数据基础。

四、拼接路径搜索：起点识别 + 贪心生长

复原即寻找一个排列 $\pi=(\pi_1,\dots,\pi_N)$ ，使目标函数

$F(\pi)=\sum_{k=1}^{N-1} S_{\pi_k,\pi_{k+1}}$

最大。本文首先给出一种轻量且高效的贪心链式拼接策略，它由两步构成：

起点识别（左端碎片）：原始文档的最左端碎片没有"前驱"，其左边缘 $L$ 不会与任何碎片的右边缘 $R$ 高度匹配。因此本文以"作为后继被需要程度" $\max_i S_{ij}$ 最小者作为起点——即最不像任何人后继的碎片，正是左端。
贪心生长：从起点出发，每一步在未用碎片中选取与"当前碎片右边缘"相似度最高的碎片作为下一个，直至取完所有碎片。

该算法时间复杂度仅 $O(N^2)$ ，适合大规模碎片。图 4 将贪心复原出的序列（按排列位置给出其真实位置）与真实序列对照：两条折线完全吻合，说明在本文无噪合成数据上，贪心策略已 100% 复原文档。

为说明贪心并非"碰巧"，图 7 给出全部碎片对的相似度分布：正确相邻对（红色区域）高度集中在相似度接近 1 的右端，错误对（蓝色区域）则集中在低相似度区，两类分布明显分离。这意味着"选最相似者"这一贪心规则有坚实的统计依据，而非随机成功。

五、多策略对照与规模的稳健性

除了贪心，本文还实现了两种更"全局"的拼接策略用于对照（其完整算法见范文二）：2-opt 局部搜索（在贪心解上反复反转子段以增目标值）与模拟退火（随机扰动排列并按 Metropolis 准则接受）。在无噪数据上，三者均达到理论最优目标值 $F^*=18.000$ ，相邻正确率同为 100%（图 5），说明在理想数据下三种策略等价地完美复原——图 5 的价值在于验证了"方法上界"，真正区分它们的是含噪与规模放大后的表现。

图 6 给出在固定噪声 $\sigma=0.10$ （边缘特征叠加高斯扰动）下，不同碎片规模 $N\in\{5,9,13,17,19\}$ 的贪心相邻正确率：小规模（5、9、13 条）仍保持 100%，当规模增至 17、19 条时正确率降至约 0.96、0.98。规模越大，错误信息在链式生长中累积的机会越多，正确率略有回落，但整体仍维持在很高水平，说明贪心拼接对规模具有较好的可扩展性。

六、噪声鲁棒性

真实碎纸的边缘往往受光照、污损、扫描噪声影响。图 8 给出在边缘特征上叠加不同强度高斯噪声（标准差 $\sigma$ 从 0 增至 0.30）后，贪心拼接的相邻正确率变化：

噪声 $\sigma$	0.00	0.05	0.10	0.15	0.20	0.25	0.30
相邻正确率	1.000	1.000	1.000	0.965	0.917	0.875	0.847

可见当 $\sigma\le0.10$ 时复原完全不受影响，直到 $\sigma=0.30$ 仍有 84.7% 的相邻正确率。这是因为相似度模型基于方向一致性（余弦），少量加性噪声对方向的影响有限，且贪心每一步只依赖"局部最相似"，对均匀噪声具备天然鲁棒性。这一结论为范文三的系统鲁棒性分析提供了基线。

七、与真实图像复原的工程衔接

本文使用合成数据完成方法验证，但真实赛题的输入是扫描图像。要把本文框架落地，需在前端补一个"图像→边缘特征"的提取链路：首先对碎纸扫描图做二值化与去噪，沿纵切方向把文档切成 $N$ 条竖条；对每条竖条取其左、右两条边界列的灰度值，按行投影得到 $L_i$ 、 $R_i$ 向量（即本文的 10 维特征）；若原图是彩色，可先转灰度或对各通道分别投影再拼接。提取出的 $L/R$ 向量即可直接接入本文的余弦相似度与贪心/2-opt 拼接流程，无需改动核心算法。

需要强调的是，真实情形比合成数据更复杂：文档可能为彩色、含文字与图片混排，边缘可能因污损、折痕而缺损，且实际切碎常是"横纵混合"（二维网格而非单纯纵切）。针对这些差异，可做三点改进：一是双向相似度，不仅比较右缘—左缘，也校验左缘—右缘以互相印证；二是分段复原，当出现多片缺失导致链式断裂时，先复原若干连续子段再对段首段尾做粗匹配；三是人工校验闭环，对相似度处于阈值附近的配对交人工确认，避免自动错误传播。这些改进与本文方法同源，可在不推翻框架的前提下逐步叠加。

还需注意：前端提取误差会向后端拼接传递。例如某竖条右边界因阴影导致灰度整体偏移，会使余弦相似度下降、甚至错配。因此真实部署时，边缘特征宜先做局部标准化（减去该边界均值），这恰好呼应范文三"异源数据优先用皮尔逊"的结论——标准化后的余弦即等价于皮尔逊，对均值漂移更稳健。综上，本文的"相似度建模 + 路径搜索"是一条可直接工程化的主线，真实参赛时只需补足前端特征提取与少量鲁棒性加固即可。

八、结论与建模建议

碎纸纵切复原可抽象为"边缘相似度 + 排列路径搜索"两个问题；余弦相似度能有效刻画相邻竖条边缘的连续性，且对加性噪声具备天然鲁棒性。
轻量贪心策略（起点识别 + 链式生长）在本合成数据上即达 100% 复原（Kendall $\tau=1.000$ 、位置全对），时间复杂度 $O(N^2)$ ，适合大规模碎片快速复原。
无噪下贪心、2-opt、模拟退火三者等价完美，差异主要体现在含噪与规模放大后——这提醒我们：评价拼接算法不能只看理想数据，应在噪声与规模维度上做系统测试（见范文二、三）。
相似度分布中"正确对 vs 错误对"明显分离，说明本合成数据的边缘信号编码良好；真实参赛时只要边缘提取质量足够，可直接套用本文拼接框架。

关键词：碎纸复原；纵切；余弦相似度；贪心拼接；路径搜索；Kendall 秩相关；噪声鲁棒性

附录：2013B 拼接复原可运行代码

import csv, math, random

# ---------- 数据 ----------
def load(path="../data/cumcm2013b.csv"):
    rows = list(csv.reader(open(path, encoding="utf-8-sig")))
    K = 10
    data = [[float(x) for x in r] for r in rows[1:] if len(r) >= 2 + 2 * K]
    frags = []
    for r in data:
        fid = int(r[0]); pos = int(r[1])
        L = [r[2 + k] for k in range(K)]; R = [r[2 + K + k] for k in range(K)]
        frags.append((fid, pos, L, R))
    return frags

def cos(a, b):
    na = math.sqrt(sum(x * x for x in a)); nb = math.sqrt(sum(x * x for x in b))
    if na == 0 or nb == 0: return 0.0
    return sum(a[k] * b[k] for k in range(len(a))) / (na * nb)

def sim_matrix(frags):
    n = len(frags); S = [[0.0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            S[i][j] = -1.0 if i == j else cos(frags[i][3], frags[j][2])
    return S

# ---------- 贪心拼接 ----------
def greedy(S, n):
    used = [False] * n
    succ = [max(S[i][j] for i in range(n)) for j in range(n)]
    start = min(range(n), key=lambda j: succ[j])   # 最不像任何人后继者=左端
    order = [start]; used[start] = True; cur = start
    for _ in range(n - 1):
        bj, bs = -1, -2.0
        for j in range(n):
            if used[j]: continue
            if S[cur][j] > bs: bs, bj = S[cur][j], j
        order.append(bj); used[bj] = True; cur = bj
    return order

def evaluate(order, frags):
    n = len(order); seq = [frags[idx][1] for idx in order]
    adj = sum(1 for k in range(n - 1) if seq[k] + 1 == seq[k + 1])
    conc = disc = 0
    for a in range(n):
        for b in range(a + 1, n):
            if (seq[a] < seq[b]) == (a < b): conc += 1
            else: disc += 1
    tau = (conc - disc) / (conc + disc) if conc + disc else 0
    cor = sum(1 for k in range(n) if seq[k] == k + 1)
    return adj, tau, cor

# ---------- 噪声鲁棒性 ----------
def noisy_rate(sig, reps=8, seed=2013):
    rng = random.Random(seed); tot = 0.0
    for _ in range(reps):
        fn = [(fid, pos, [v + rng.gauss(0, sig) for v in L],
              [v + rng.gauss(0, sig) for v in R]) for (fid, pos, L, R) in frags]
        Sn = sim_matrix(fn); gn = greedy(Sn, n); a, _, _ = evaluate(gn, fn)
        tot += a / (n - 1)
    return tot / reps

# ---------- 主流程 ----------
frags = load(); n = len(frags); S = sim_matrix(frags)
g = greedy(S, n); adj, tau, cor = evaluate(g, frags)
print("贪心拼接：相邻正确 %d/%d, Kendall tau=%.3f, 位置正确 %d/%d" % (adj, n - 1, tau, cor, n))
for sig in [0.0, 0.1, 0.2, 0.3]:
    print("噪声 σ=%.2f 相邻正确率=%.3f" % (sig, noisy_rate(sig)))