PatchMatch图像修复实战：Python实现补丁匹配与NNF搜索

简介：这份资源是Python实现的PatchMatch补丁匹配算法代码包，面向计算机视觉方向的学习者与研究者，适合已掌握Python基础、希望深入理解图像对应与纹理合成等底层算法的人群。包内提供PatchMatch.py与PatchMatch_Bidirectional.py两个核心脚本，后者可用于DeepImageAnalogy示例，帮助读者复现论文中的双向匹配流程。资源共33个文件，以20张jpg与7个gif为主，配合2个png、2个py脚本及license、md说明文档，压缩包约15.83MB，图像与动图可用于对照迭代过程与匹配效果。目前已有1045人学习下载。借助完整脚本与多轮迭代可视化素材，读者可快速跑通补丁匹配实验，观察从迭代0到迭代5的收敛变化，理解随机初始化、传播与搜索等关键环节，并在此基础上开展图像类比、风格迁移等扩展实验，是入门与复现PatchMatch的实用参考。

1. 从一张被抹掉的路人照片说起：PatchMatch 到底在补什么

你手里有一张街拍，构图、光线都满意，唯独画面右下角有个路人甲。传统做法是拿仿制图章一点点涂，涂十分钟手一抖就糊。PatchMatch 想解决的就是这件事：给定一张图和一个待填充的洞，让算法自己从图里别的地方找相似的纹理块，一块块贴回来，贴得还看不出接缝。它 2009 年由几个研究者提出，核心不是深度学习，而是随机化 + 传播的近似最近邻搜索，速度快到能在普通笔记本上跑交互式图像编辑。Python 实现的价值在于：你能读懂每一行、改得动参数、把它塞进自己的修图或去水印流程里，而不是调一个黑盒 API。这篇写给想真正搞懂补丁匹配、愿意动手复现的开发者，新手能跟着跑通，熟手能看到搜索半径、迭代次数这些参数背后的取舍。

2. 补丁匹配的直觉：为什么随机撒点反而比暴力搜索快

2.1 最近邻场（NNF）到底在存什么

先把问题形式化。假设源图 A 和目标图 B 尺寸相同，我们要为 B 里每个像素位置 p 找一个偏移量 f(p)，使得 A 中以 p+f(p) 为中心的补丁，和 B 中以 p 为中心的补丁最像。所有 f(p) 组成的集合就是最近邻场（Nearest Neighbor Field，NNF）。暴力做法是对每个 p 遍历 A 里所有可能位置，复杂度是 O(N²)，一张 512×512 的图就是 260 亿次补丁比较，纯 Python 跑到天亮。

PatchMatch 的洞察是：图像是高度冗余的，相邻像素的最近邻大概率也相邻。于是它放弃全局最优，用「随机初始化 + 迭代传播 + 随机扰动」三步，在极少的迭代里逼近一个足够好的解。这不是玄学，是概率上的近似——它不保证找到真最近邻，但找到的补丁在视觉上几乎没差别，而速度快了几个数量级。

2.2 三个动作：初始化、传播、随机搜索

初始化：给每个像素随机分配一个偏移量。听起来很蠢，但这是后面传播的种子。随机的好处是覆盖面广，坏处是初始误差大，靠迭代收敛。

传播：按扫描顺序（比如从左到右、从上到下）处理每个像素，检查它左边和上边邻居的偏移量，如果邻居的偏移量在当前像素上表现更好，就采纳。这一步是 PatchMatch 的灵魂——好的解会像涟漪一样扩散开。反向扫描（从右到左、从下到上）再传播一轮，让信息双向流动。

随机搜索：在当前位置的偏移量周围，以指数衰减的半径随机采样几个候选。半径从图像尺寸开始，每轮减半，这样既能跳出局部最优，又能在后期精细调整。

下面是一个最小可运行的 NNF 搜索核心，用 numpy 做补丁距离计算，避免纯 Python 循环拖慢速度：

import numpy as np def patch_distance(A, B, y, x, ay, ax, patch_size): """计算 A 中以 (ay,ax) 为中心和 B 中以 (y,x) 为中心的补丁距离""" r = patch_size // 2 # 边界裁剪，防止越界 y0, y1 = max(0, y - r), min(B.shape[0], y + r + 1) x0, x1 = max(0, x - r), min(B.shape[1], x + r + 1) ay0, ay1 = max(0, ay - r), min(A.shape[0], ay + r + 1) ax0, ax1 = max(0, ax - r), min(A.shape[1], ax + r + 1) # 取实际重叠区域，尺寸不一致时取最小 h = min(y1 - y0, ay1 - ay0) w = min(x1 - x0, ax1 - ax0) if h <= 0 or w <= 0: return 1e10 patch_b = B[y0:y0+h, x0:x0+w] patch_a = A[ay0:ay0+h, ax0:ax0+w] # 用平方差之和（SSD）作为距离度量 return np.sum((patch_a.astype(np.float32) - patch_b.astype(np.float32)) ** 2) def propagate(NNF, cost, A, B, patch_size, reverse=False): """一轮传播：检查邻居偏移量是否更优""" h, w = NNF.shape[:2] ys = range(h - 1, -1, -1) if reverse else range(h) xs = range(w - 1, -1, -1) if reverse else range(w) for y in ys: for x in xs: best = NNF[y, x].copy() best_cost = cost[y, x] # 检查左邻居（正向）或右邻居（反向） nx = x - 1 if not reverse else x + 1 if 0 <= nx < w: cand = NNF[y, nx] ay, ax = y + cand[0], x + cand[1] if 0 <= ay < h and 0 <= ax < w: d = patch_distance(A, B, y, x, ay, ax, patch_size) if d < best_cost: best, best_cost = cand.copy(), d # 检查上邻居（正向）或下邻居（反向） ny = y - 1 if not reverse else y + 1 if 0 <= ny < h: cand = NNF[ny, x] ay, ax = y + cand[0], x + cand[1] if 0 <= ay < h and 0 <= ax < w: d = patch_distance(A, B, y, x, ay, ax, patch_size) if d < best_cost: best, best_cost = cand.copy(), d NNF[y, x] = best cost[y, x] = best_cost return NNF, cost

这段代码里NNF[y,x]存的是偏移量(dy, dx)，不是绝对坐标，这样传播时直接加到当前坐标上就能得到候选位置。patch_distance用 SSD 度量，propagate只检查两个邻居，这是最简版本。实际工程里会加多尺度金字塔，先在缩略图上传播，再逐级放大，收敛更快。

2.3 随机搜索：指数衰减半径怎么设

传播只能利用邻居信息，容易卡在局部最优。随机搜索负责「跳出去」：

def random_search(NNF, cost, A, B, patch_size, alpha=0.5, max_radius=None): """在当前偏移量周围随机采样，半径指数衰减""" h, w = NNF.shape[:2] if max_radius is None: max_radius = max(h, w) for y in range(h): for x in range(w): best = NNF[y, x].copy() best_cost = cost[y, x] radius = max_radius while radius > 1: # 在当前偏移量周围 [-radius, radius] 内均匀采样 dy = int(np.random.randint(-radius, radius + 1)) dx = int(np.random.randint(-radius, radius + 1)) cand = best + np.array([dy, dx]) ay, ax = y + cand[0], x + cand[1] if 0 <= ay < h and 0 <= ax < w: d = patch_distance(A, B, y, x, ay, ax, patch_size) if d < best_cost: best, best_cost = cand.copy(), d radius = int(radius * alpha) # 半径衰减 NNF[y, x] = best cost[y, x] = best_cost return NNF, cost

alpha控制衰减速度，0.5 是论文推荐值，意味着半径每轮减半。max_radius一般设为图像长边，保证第一轮能覆盖全图。这里有个血泪经验：radius必须至少衰减到 1 再停，否则后期精细调整不够，补丁边缘会有明显错位。

3. 用 Python 把 PatchMatch 跑起来：从 NNF 到图像修复

3.1 完整流程与主循环

把初始化、传播、随机搜索串起来，迭代 4～6 轮就能得到不错的 NNF：

def patchmatch(A, B, patch_size=7, iters=5): """A 源图，B 目标图，返回 NNF 和对应 cost""" h, w = B.shape[:2] # 随机初始化偏移量，范围限制在图像内 NNF = np.random.randint(-h, h, size=(h, w, 2)).astype(np.int32) cost = np.full((h, w), 1e10, dtype=np.float32) # 初始化时计算一次真实 cost for y in range(h): for x in range(w): ay, ax = y + NNF[y, x, 0], x + NNF[y, x, 1] if 0 <= ay < h and 0 <= ax < w: cost[y, x] = patch_distance(A, B, y, x, ay, ax, patch_size) for it in range(iters): # 正向传播 + 随机搜索 NNF, cost = propagate(NNF, cost, A, B, patch_size, reverse=False) NNF, cost = random_search(NNF, cost, A, B, patch_size) # 反向传播 + 随机搜索 NNF, cost = propagate(NNF, cost, A, B, patch_size, reverse=True) NNF, cost = random_search(NNF, cost, A, B, patch_size) print(f"iter {it}, mean cost {cost.mean():.2f}") return NNF, cost

主循环里正向和反向各做一轮传播加随机搜索，这是标准配置。iters=5对多数图够用，再多收益递减。patch_size=7是经验值，纹理细的图可以降到 5，平滑区域可以升到 9。打印 mean cost 是为了观察收敛，如果几轮后还在大幅下降，说明迭代不够或参数不对。

3.2 图像修复：把 NNF 变成填洞操作

拿到 NNF 后，修复就是按偏移量把源补丁搬过来。但直接搬会有接缝，需要加权融合：

def inpaint(A, B, mask, NNF, patch_size=7): """A 源图，B 待修复图，mask 为 1 表示待修复区域""" h, w = B.shape[:2] result = B.copy().astype(np.float32) weight = np.zeros((h, w), dtype=np.float32) r = patch_size // 2 for y in range(h): for x in range(w): if mask[y, x] == 0: continue # 只处理待修复像素 ay, ax = y + NNF[y, x, 0], x + NNF[y, x, 1] if not (0 <= ay < h and 0 <= ax < w): continue # 把源补丁中心像素搬过来，这里简化处理 result[y, x] = A[ay, ax] weight[y, x] = 1.0 # 对修复区域做简单均值滤波，减少块状感 from scipy.ndimage import uniform_filter for c in range(3): smoothed = uniform_filter(result[:, :, c], size=3) result[:, :, c] = np.where(mask == 1, smoothed, result[:, :, c]) return np.clip(result, 0, 255).astype(np.uint8)

这段是简化版，真实修复会用多尺度 + 补丁投票，每个像素被多个重叠补丁覆盖，取加权平均。uniform_filter是后悔药，能压掉块状伪影，但会轻微模糊，纹理锐利的图慎用。mask 的生成可以用 OpenCV 的交互式工具，或者手动涂一个二值图。

3.3 参数怎么调：patch_size、iters、alpha 的取舍

patch_size 是最敏感的。我一般会先用 7 跑一遍看效果，如果修复区域出现明显重复纹理，说明补丁太小，匹配到了错误位置，升到 9；如果边缘糊，说明补丁太大，降回 5。iters 不是越多越好，超过 6 轮后 NNF 基本不变，纯浪费算力。

4. 避坑与排查：那些让 PatchMatch 翻车的细节

4.1 现象：修复区域出现整块错位，像贴了张歪膏药

原因通常是传播顺序和边界处理不一致。正向传播时左邻居和上邻居的偏移量可能指向图像外，代码里如果没做边界检查，就会取到越界内存或错误像素。解决：在propagate和random_search里对每个候选坐标都做0 <= ay < h判断，越界直接跳过，不要用 clamp 强行拉回边界，那会引入错误匹配。

4.2 现象：跑得特别慢，512×512 要几分钟

纯 Python 双重循环是性能杀手。patch_distance里每次调用都做切片和 numpy 运算，循环次数是 h×w×iters×候选数，很容易上千万次。解决：用 numpy 向量化补丁距离，或者把内层循环用 numba 的@jit加速。另一个常见误用是 patch_size 设得过大，7 和 15 的耗时差 4 倍以上，而视觉提升有限。

4.3 现象：mean cost 震荡不收敛

随机搜索的max_radius设得太小，或者alpha太大导致半径衰减过快，搜索空间不够。解决：确认max_radius不小于图像长边的一半，alpha保持 0.5。如果还震荡，检查初始化偏移量范围是不是限制得太窄，随机撒点要覆盖全图才有足够多样性。

4.4 现象：修复结果有网格状接缝

这是补丁直接搬运的典型问题，每个像素独立取最近邻，相邻像素的偏移量可能突变。解决：在 NNF 上做一次中值滤波，让偏移量场平滑；或者用多尺度金字塔，粗尺度先定大结构，细尺度再修边缘。简单做法是对修复结果做导向滤波，以原图为引导，能保住边缘又压掉接缝。

5. 进阶技巧：多尺度金字塔与 NNF 平滑

单尺度 PatchMatch 在纹理复杂或洞比较大的时候容易力不从心。我一般会加一个图像金字塔：先把源图和目标图各降采样到 1/4、1/2、原尺寸三层，从最粗的一层开始跑 PatchMatch，把得到的 NNF 上采样作为下一层的初始值。这样粗尺度负责找大结构，细尺度负责修纹理，收敛快且不容易卡局部最优。

import cv2 def build_pyramid(img, levels=3): """构建高斯金字塔，返回从粗到细的列表""" pyramid = [img] for _ in range(levels - 1): img = cv2.pyrDown(img) pyramid.append(img) return pyramid[::-1] # 反转，粗的在前面 def multiscale_patchmatch(A, B, mask, levels=3, patch_size=7): """多尺度 PatchMatch 修复""" A_pyr = build_pyramid(A, levels) B_pyr = build_pyramid(B, levels) mask_pyr = build_pyramid(mask.astype(np.float32), levels) NNF = None for i, (a, b, m) in enumerate(zip(A_pyr, B_pyr, mask_pyr)): if NNF is not None: # 上采样 NNF 到当前尺度 h, w = b.shape[:2] NNF = cv2.resize(NNF.astype(np.float32), (w, h), interpolation=cv2.INTER_LINEAR) NNF = NNF.astype(np.int32) else: h, w = b.shape[:2] NNF = np.random.randint(-h, h, size=(h, w, 2)).astype(np.int32) # 在当前尺度跑几轮迭代 NNF, cost = patchmatch_with_init(a, b, NNF, patch_size, iters=3) return NNF

build_pyramid用cv2.pyrDown做降采样，每层尺寸减半。multiscale_patchmatch从最粗层开始，NNF 上采样用双线性插值，偏移量是整数场，插值后取整会有小误差，但下一轮迭代会修正。patchmatch_with_init是接受初始 NNF 的版本，把随机初始化换成传入值即可。

另一个技巧是 NNF 平滑。传播和随机搜索之后，对 NNF 做一次 3×3 中值滤波，能去掉孤立的错误偏移量：

def smooth_nnf(NNF, kernel=3): """对 NNF 的每个通道做中值滤波""" from scipy.ndimage import median_filter smoothed = np.zeros_like(NNF) for c in range(2): smoothed[:, :, c] = median_filter(NNF[:, :, c], size=kernel) return smoothed

中值滤波的代价是可能抹掉一些正确的突变边界，所以只在迭代后期用，别每轮都做。我习惯在最后一轮传播后做一次，然后直接输出修复结果。

验证修复质量有个土办法：把源图里已知区域挖掉一块，跑修复，再和原图算 PSNR。PSNR 高于 28dB 基本看不出问题，低于 25dB 说明参数或金字塔层数要调。这个自检比肉眼靠谱，尤其是批量处理时。

最后说个习惯：每次改参数只动一个，跑完记录 mean cost 和 PSNR，别一次调三个然后不知道哪个起了作用。PatchMatch 的参数耦合不强，但随机搜索有随机性，同一组参数跑两次结果可能略有差异，看趋势别看单次。希望帮到你。

本文还有配套的精品资源，点击获取