3.1 基于相关字典的图像修复 
3.1.1 引言 
图像修复是利用图像的已知信息来填充缺失或损坏的区域，这些区域可能是损坏图像 
中的个别像素缺失或为人为退化等原因造成的连续区域。近年来，图像修复引起了越来越 
多研究人员的兴趣，因为它具有广泛的应用，例如图像对象去除、图像修复和传输[115-116]。 
形式上，修复问题可以定义如下：给定输入待修复图像 I 以及其目标区域 Ω，使用已 
知区域的信息填充所有丢失像素 Ψ = I . Ω[116]。 
Bertalmio 等首先研究了图像修复，然后提出了一种基于线性偏微分方程的修复方法[3]。 
从那时起，许多研究者提出了很多修复方法来解决这个问题。通常，图像修复方法可以分 
为三种类型，即基于扩散的修复方法、基于块的修复方法和基于稀疏表示的修复方法[115]。 
基于扩散的修复方法是通过扩散目标区域的周边信息来修复损坏的区域[3,6]，但不太适合 
修复纹理信息，尤其是当要修复的目标区域大于其他区域时[115]。基于块的修复方法，这 
种修复方法是受纹理合成技术思想的启发[7]，首先选择损坏区域中的目标块，然后比较未 
破损区域中的块与目标块的相似性，最后复制最佳匹配块中的像素来填充目标块中的未知 
像素[4,7,115,117-120]。基于稀疏表示的修复方法不是使用最相似的块，而是使用字典中原子的 
稀疏线性组合来表示图像待修复块。因此，字典对于修复结果非常重要。文献 [11] 提出了 
一种有效的稀疏表示迭代修复算法，并且非常适合修复图像中不同的结构成分。另外，稀 
疏表示也适用于修复彩色图像[121]，该方法主要是对去噪算法[122] 的扩展，其字典是使用 
K-SVD 算法[123] 进行构建的。这之后，文献 [9] 提出了一种相似的的算法，直接使用从图 
像未破损的区域中裁剪出来的所有块来构建字典，获得了良好的修复效果，并且分析得到 
该方法优于算法[121]。虽然利用未破损区域所有块生成的字典有利于图像的修复，但是由 
于有不相关的原子引入，导致会复原出一些与目标块无关的信息，并且对修复结果产生干 
扰，影响修复效果。 
因此，为了解决这个问题，本节提出了一种新的相似度比较算法，在直接使用未破损 
区域图像块生成字典之前找到与目标块相似的块。然后，使用这些相似的块为目标块生成 
相关字典。最后，在本章中提出了一种基于相关字典的图像修复方法。该方法使每个目标 
块都有对应的相关字典，因此可以保证修复结果。
第 3 章 基于稀疏表示的图像修复 
3.1.2 算法 
本节将详细介绍基于相关字典的图像修复方法，可以分为以下三个部分：寻找目标块、 
生成相关字典和稀疏重建算法。第一部分：通过计算填充顺序找到目标块，并且整个算法 
就是从这个目标块开始的。第二部分：使用直方图的方法比较目标块和候选块之间的相似 
性，然后找到与目标块相似的候选块。最后，利用找到的相似候选块来构成一个相关性字 
典。第三部分，使用来自目标块的已知信息，根据稀疏表示估计它们的未知信息。下面详 
细介绍各个方法的细节。 
1. 填充顺序 
图像块的填充顺序决定了缺失区域边界上的块开始进一步修复的优先级，对于修复结 
果至关重要。在修复方法中，不同的填充顺序会导致不同的结果[119]。我们在提出的方法 
中，最后决定使用 CRIMINISI[118] 提出的填充顺序，因为这种方法可以有效地保留结构信 
息。使用填充顺序计算位于受损区域（目标区域 T）和未受损区域（源区域 S）之间的边 
界 δU 上的以 p 为中心的每个块，找到目标块 ψp 具有最高优先级。由于目标块 ψp 在边界 
上，因此目标块包含已知像素 A 和未知像素 B。在图 3.1 中可以清楚地看到拥有最高优先 
级的目标块。 
图 3.1 利用填充顺序来选择优先级高的目标块 
Criminisi 等在文献 [118] 提出的填充顺序是一种迭代算法直到所有像素都被填满，其 
算法具体可以分为以下 3 个步骤。 
（1）计算优先级。 
在填充顺序算法中，每个未填充的像素都拥有一个颜色值和一个置信度值，它们反映 
了在某个像素值下的置信度。一旦一个像素被填充，其置信度就会被锁定。也就是说，沿 
着填充边沿的目标块在填充顺序算法的过程中被赋予了一个临时的优先级值，这决定了它 
们被填充的顺序。给定一个以点 p 为中心的目标块 Ψp，中心点 p 在待填充区域的边沿上 
P ∈ δΩ，如图 3.2 所示，给定图像块 Ψp, np 是目标区域的轮廓 δ Ω 的法线，▽I⊥p 是点 p 
的照度（方向和面密度），整个图像定义为 I，优先级 P(p) 定义为 
P(p) = C(p)D(p) (3.1) 
19
图像修复和图像融合 
式中，C(p) 和 D(p) 是分别表示置信项和数据项，它们可以通过以下式子来计算。 
C(p) = X q∈Ψp∩
C(q) 
|Ψp| 
(3.2) 
D(p) = |▽I⊥p · np| 
λ 
(3.3) 
式中，|Ψp| 表示 Ψp 的区域，λ 是一个归一化因子（如 λ = 255 表示一个典型的灰度图 
像），np 是在点 p 与边沿 δΩ 正交的单位向量。函数 C(p) 可以设置为 C(p) = 0.p ∈ Ω 和 
C(p) = 1.p ∈ I . Ω。 
图 3.2 符号图 
（2）传播纹理和结构信息。 
一旦计算了以填充边沿上所有点为中心的待修复块的优先级，就会找到具有最高优先 
级的目标块 Ψ.p，然后用源区域 Φ 中的信息通过修复算法填充它。 
（3）更新置信值。 
在目标块 Ψp 被新像素填充后，置信度 C(p) 在由 Ψ.p 分隔的区域中更新为 
C(q) = C(.p), .q ∈ Ψ.p ∩ Ω (3.4) 
这是一个简单的更新规则，它允许我们测量填充边沿上的块的相对置信度，而无需特 
定于图像的参数。 
2. 生成字典 
为了计算图像块的稀疏表示，必须首先确定字典。在传统的生成字典的方法中，有 3 种字 
典的生成形式。第一种是固定字典。例如，过完备可分离版式 DCT 字典是通过对不同频 
率的余弦波进行采样来构建的[92]。但是，这类词典不是通过使用适当的输入图像数据来构 
成的，所以对某些类型数据的适应性不好。第二类是学习型字典。例如，基于 K-SVD 的 
字典学习算法，该词典与输入图像数据相适应，计算效率高[1,105]。第三类是直接用原始区 
域裁剪的整个图像块生成的字典[70]，这类字典的一个问题是一些不相关的块可能会导致一 
些干扰。为了解决这个问题，在上述所提出的方法中对候选的图像块使用直方图的相似性 
比较方法进行预处理，其过程如图 3.3 所示。详细地，使用求和直方图差异来进行相似性 
比较方法如图 3.4 所示。首先，利用 Criminisi 等[118-119] 提出的计算填充顺序的方法来选 
20
第 3 章 基于稀疏表示的图像修复 
择一个目标块 Ψp 并且计算其直方图。假设直方图有 N 个 bins，那么彩色图像的直方图也 
就有 N 个值。对于目标块 Ψp 的 R、G、B 三个通道，每个通道的直方图可以用以下式子 
进行计算。 
hΨpR = [hΨpR1, · · · , hΨpRN]T (3.5) 
hΨpG = [hΨpG1, · · · , hΨpGN]T (3.6) 
hΨpB = [hΨpB1, · · · , hΨpBN]T (3.7) 
图 3.3 直方图比较目标块和候选块之间的相似性 
图 3.4 基于求和直方图的相似性比较方法 
21
图像修复和图像融合 
其次，从图像 I 中切出所有已知的块 fi 并计算它们的直方图。分别定义 fi (i = 
1, 2, · · · ,L)，其中 L 表示已知块的数量，fRi、fGi 和 fBi 表示图像块的三个通道（R、G、 
B），每个通道的直方图可以利用以下式子进行计算。 
hfRi =[hfRi1, · · · , hfRiN ]T (3.8) 
hfGi =[hfGi1, · · · , hfGiN ]T (3.9) 
hfBi =[hfBi1, · · · , hfBiN ]T (3.10) 
因此，两个块 Ψp 和 fi 可以通过比较直方图的相应 bin 来衡量相似度。在 R、G、B 
三个通道中，可以通过比较它们的直方图来定义差异。 
VRi = ||hΨpR . hfRi||1 = 
N Xj=1
(|hΨpRj . hfRij |) (3.11) 
VGi = ||hΨpG . hfGi||1 = 
N Xj=1
(|hΨpGj . hfGij |) (3.12) 
VBi = ||hΨpB . hfBi||1 = 
N Xj=1
(|hΨpBj . hfBij |) (3.13) 
根据求和 VSi 可以定义相似性为 
VSi = VRi + VGi + VBi (3.14) 
考虑已知图像块的个数为 L，基于 sum 的相似度写为 VS = [VS1, · · · , VSL]T。 
最后，对 VS 进行排序，找到前 TN (TN < L) 个已知图像块，用来生成相关字典。 
在图 3.5 所示的示例中，在图中“Sample”字体区域（也就是破损区域用矩形框住的 
部分）表示为目标块，也就是需要修复的块。未破损区域的矩形块表示为选择生成相关字 
典的块。例如，选择前 TN = 50 个相似的块 {Ψqj}50 
j=1，其中 Ψq1 表示与目标块最相似的一 
个，它表示为相关字典的第一列。其余块可以以相同的方式构成字典。 
图 3.5 利用相似块生成相关字典 
22
第 3 章 基于稀疏表示的图像修复 
3. 恢复信号 
找到图像块 Ψp 后，稀疏重构的目的是利用已知信息 A 估计未知信息 B。矩阵 M 具 
有由已知像素的布局决定的特殊结构。因此，已知信息可以计算为 
A =MΨp (3.15) 
在图像修复问题中，其目的在利用已知信息 A 估计未知信息 B。并且 A 可以看作是稀疏 
表示理论中的信号 y，那么稀疏表示可以改写为 
A =MDα (3.16) 
式中，D 是通过直方图的相似性比较方法生成的新相关字典。 
在所提出的方法中，编者将使用非负正交匹配追踪（Non-Negative Orthogonal Matching 
Pursuit，NNOMP）[124] 算法，它是 OMP 的一种改进方法，用于获得稀疏系数 .α 的估计。 
NNOMP 算法可以描述如下步骤。 
（1）初始化残差 r0 = A，初始化所选变量的集合 D(c0) = .，让迭代计数器 i = 1。 
（2）遍历所有原型信号原子并找到 D 中最佳原子函数的索引为 ti = argmax < ri.1, 
dt >，并将变量 Dti 添加到所选变量的集合中，更新 ci = ci.1 ∪ ti。 
（3）使用非负最小二乘（NNLS）估计稀疏表示系数 . αi， . αi = argminαi.0 ∥ A . 
Dciαi ∥2= (DT
ciDci).1DT
ciA。 
（4）更新半径 ri = A.Dci . αi = A.Dci(DT
ciDci).1DT
ciA。令 Pi = Dci(DT
ciDci).1DT
ci 
表示由 Dci 的元素投影到线性空间上，那么残差可以改写为 ri = (I . Pi)A。 
（5）如果达到停止条件，则停止算法。否则，设置 i = i + 1 并返回（2）。 
如果使用 NNOMP 算法得到稀疏系数 .α 的估计，那么未知信息 B 可以近似地估计为 
B = ˉM
D.α (3.17) 
式中， ˉM
= E .M 是一个矩阵，由缺失像素的布局决定，E 也是一个矩阵，并且矩阵中 
的每一项都为 1。具体来说，目标块中的缺失像素可以利用如下公式进行修复。 
. Ψip
=8<:
Ψip
, i ∈ A 
( ˉM
D.α)i, 其他 
(3.18) 
根据以上讨论，我们所提出的修复算法的流程图如图 3.6 所示。 
23
图像修复和图像融合 
图 3.6 修复算法的流程图 
3.1.3 实验结果 
实验结果证明使用直方图生成相关字典可以比原字典更有效地进行图像修复。在本实 
验中，我们采用不同的字典并将它们的修复结果进行比较。 
1. 利用不同的字典进行图像修复 
为了客观地评估不同字典图像修复的性能，实验中使用两种字典进行比较：原始字典 
和相关字典。两幅图像用来进行实验，图 3.7（a）和图 3.7（b）分别显示了自然景观原始图 
像 1 和输入图像，图 3.8（a）和图 3.8（b）分别显示了自然景观原始图像 2 和输入图像。 
图 3.7 对图像 1 利用不同字典的修复结果 
24
第 3 章 基于稀疏表示的图像修复 
图 3.8 对图像 2 利用不同字典的修复结果 
2. 评价指标 
本节中使用从 MSE 获得的 PSNR 来定量地评估实验结果。此外，每个颜色通道（R、 
G、B）的 PSNR 的也在实验中计算。与计算整个图像的均方误差不同，这里只计算缺陷 
区域的均方误差。均方误差可以通过以下式子计算得出。 
MSE = X(i,j) 
∈ T(Iori(i, j) . Iinp(i, j))2 
N(T) 
(3.19) 
式中，Iori(i, j) 是原始图像的亮度值；Iinp(i, j) 是修复图像的亮度值；T 表示目标区域，即 
缺陷区域；N(T) 代表破损区域内的像素个数。 
PSNR 定义为 
PSNR = 10log10 2552 
MSE (3.20) 
整个实验是根据算法流程图 3.6 来进行的，使用原始图像和修复图像之间的 PSNR 作 
为评估量化修复结果的指标。实验结果的量化值在表 3.1 中显示。从表 3.1 可以看出，使 
用相关字典的方法比使用原始字典的方法具有更好的修复效果。为了使实验结果看起来更 
加清晰，图 3.9 和图 3.10 对原始图像、损坏图像和修复结果的修复区域进行裁剪并放大。 
表 3.1 实验结果的量化值 
原始字典 PSNR 相关字典 PSNR 
图像 1 
R 通道 18.45 18.78 
G 通道 20.58 21.01 
B 通道 23.66 24.19 
RGB 20.40 20.80 
图像 2 
R 通道 18.28 18.79 
G 通道 19.26 19.71 
B 通道 20.25 20.91 
RGB 19.19 19.72 
25
图像修复和图像融合 
图 3.9 原始图像 1 修复结果裁剪放大示意图 
图 3.10 原始图像 2 修复结果裁剪放大示意图 
从图 3.7 和图 3.8 可以看出，使用原始字典的修复结果中存在一些伪影，这些伪影可 
以从图 3.9 和图 3.10 很容易地看出来。产生这些伪影是因为原始字典中包含与图像目标块 
无关的原子。与此同时使用相关字典的修复结果图 3.7（d）和图 3.8（d）中获得了良好的 
26
第 3 章 基于稀疏表示的图像修复 
视觉效果，人眼看上去没有奇怪的感觉，并且可以很清晰地显现出来。从主观评价和客观 
评价可以清楚地看出来，使用相关字典修复算法的性能优于使用原始字典的修复算法。 
3.1.4 总结 
在本节中，我们提出了一种基于稀疏表示和相关字典的新的修复方法。该方法总为每 
个目标块定义了与之相关的相关字典，该目标块的相关字典由未损坏区域中与目标块具有 
相似直方图的图像块组成。这是一个重要的步骤，它保证了修复结果更准确，因此，目标块 
可以通过相关字典中图像块的稀疏表示来修复。正如实验结果所示，使用相关字典的方法 
比使用原始字典获得了更好的修复性能。修复结果客观的定量评价与主观视觉效果一致。 
未来，我们将关注如何使用直方图选择与目标块相关的块。选择与目标块越相似的块， 
修复效果越好。此外，我们还想研究其他的图像修复的方法，尤其是针对破损区域较大的 
图像。 
3.2 一种提高的直方图比较方法 
在 3.1 节中已经介绍了利用相关字典进行图像修复，但是利用相关字典进行图像修复 
存在一个问题。如表 3.2 所示，三个样本的直方图总和值都是 10，所以我们利用求和直方 
图排序然后再选择样本作为字典时就会出错。 
表 3.2 相关字典客观评价指标值 
例 子 R 通道 G 通道 B 通道 Sum(R, G, B) 
11 4.2 3.5 2.3 10 
2 0.8 8.1 1.1 10 
3 6.1 1.5 2.4 10 
为了解决这个问题，编者提出了一种改进的直方图比较方法。考虑到彩色图像具有三 
个通道，这里将图像块的相似度视为一个 3-D 向量并找到它的最大值，然后对它们进行排 
序。表 3.2 排序后的示例显示在表 3.3 中。然后我们可以通过此方法找到相似的块来生成 
直方图字典。本节提出的最大直方图的算法框架如图 3.11。从图 3.11可以看出，总和直方 
图与最大直方图最大的差异在于对 R、G、B 三个通道处理方式上。 
表 3.3 相关字典客观评价指标值排序结果 
例 子 R 通道 G 通道 B 通道 Sum(R, G, B) Max(R, G, B) 排 序 
1 4.2 3.5 2.3 10 4.2 1 
2 0.8 8.1 1.1 10 8.1 3 
3 6.1 1.5 2.4 10 6.1 2 
27
图像修复和图像融合 
与方程 3.14 类似，这里将三个通道的最大差异表示为 VMi。 
VMi = max(VRi, VGi, VBi) (3.21) 
图 3.11 最大值直方图比较相似性的流程图 
假设已知图像块的数量为 L，基于最大差异的相似度可以写为 VM = [VM1, · · · , VML]T。 
然后，对 VM 进行排序，找出前 TN1 (TN1 < L) 个已知的图像块用来生成直方图字典。 
3.2.1 直方图字典 
对于每个目标块，令 TN1 = 50，然后用它们构建一个直方图字典。图 3.12（a）和（b） 
显示了两个目标块以及使用改进的直方图比较方法获得的相似块。图 3.12（c）和（d）在 
散点图中显示了图 3.12（a）和（b）选择的相似块。 
另外，为了清楚地显示差异，这里通过一个具体的例子来展示同一个目标块使用直方 
图的两种不同方法进行相似度比较得到的相似块，如图 3.13 所示。也就是说在同一幅图 
片中显示了使用两种方法选择的前 50 个图像块。图中用“Sample”字体区域矩形块显示 
基于最大值直方图方法的结果，未破损区域的矩形块显示基于求和直方图方法的结果。从 
图 3.13（a）可以看出，使用基于最大值直方图的相似性比较方法选择的前 50 个样本块比 
使用基于求和直方图的相似性比较方法选择的样本块包含更多的相关块。从图 3.13（b）可 
以看出，使用基于最大值直方图的相似性比较方法选择的前 50 个样本块通常与使用基于 
求和直方图的相似性比较的方法选择的块一样与目标块具有相关性。 
28
第 3 章 基于稀疏表示的图像修复 
图 3.12 利用最大值直方图选择的前 50 个相似块 
图 3.13 分别利用求和直方图和最大值直方图对同一目标块选择的相似块 
29
图像修复和图像融合 
3.2.2 基于直方图字典的图像修复 
基于直方图字典的图像修复过程与基于相关词典的图像修复算法类似。算法 1 中详细 
描述了基于直方图字典的图像修复算法。 
算法 1 基于直方图字典的图像修复算法 
输入 : the observed image I 
输出 : inpainting image .I 
Initialization: block= n × n, KP, l = 0 
Repeat: 
Clipped the patch fl+1 from the image I in a window (n × n) 
if fL+1 is as a candidate patch compute the histogram of the patch by Eq.3.8 
L ← L + 1 
KPL+1 = 4[KPL fL+1] then fL+1 is in the source region S of image I 
end 
while I has defective pixels do 
initialization:VM=[ ] 
use the filling order to find the target patch ψp 
compute the histogram of it by Eq.(3.5) 
for i = 1 : L do 
compute the difference between target patch and the candidate patches by Eq.3.11 
Use VMi = max(VRi, VGi, VBi) 
Update VM =[VM VMi] 
index ← sort(VM) 
Dh=KP(:,index(1 : L)) 
end 
.α=FNNOMP(ψp, Dh) 
reconstruct the ψp by using Eq.3.18 
end 
3.2.3 实验结果 
这一部分在各种自然图像上测试了所提出方法的性能并且将该方法与 Criminisi 等提 
出的修复算法进行了比较[118-119]，还采用了一些文献[118-119] 中描述的修复填充顺序，使用 
算法 1 来实现所提出的方法。将 L 的个数设置为 400，也就是说这里选择前 400 个相似的 
块来构成直方图字典。为了公平起见，所有方法的窗口大小设置为 9 × 9。 
在定量评估中，将所提方法的性能与不同的图像修复方法进行了比较。本实验中使用 
PSNR 作为评估修复结果的指标。此外，为了更清楚地比较修复结果，实验中还给出了 R、 
G、B 三个通道的 PSNR 值。 
考虑到本章中这两种相似性方法，所提出的方法分别使用相关字典和直方图字典来修 
复图像的缺失区域。图 3.14 展示了本实验中的三幅实验图像及其修复结果。修复结果与原 
始图像之间的 PSNR 总结在表 3.4 中。在图 3.14（c）中，可以很明显地看到由 
30
第 3 章 基于稀疏表示的图像修复 
Criminisi 等提出的算法所得的修复结果具有错误。例如，修复结果中的雪山出现了不需 
要的结构信息。这是因为该方法只选择一个最佳匹配的块来修复缺失区域，会导致修复结 
果出现一些不需要的伪影。利用相关字典所得的修复结果如图 3.14（d）所示，可以看出图 
中山的边缘没有修复得很好，并且右侧图片在实验结果中产生了多余的颜色。对于使用相 
关字典的图像修复方法，在稀疏表示框架下相似的图像块由基于最大值直方图的相似度比 
较方法，因此它可以克服 Criminisi 等提出的修复方法造成的影响。此外，直方图字典是通 
过比较 3-D 向量的差异来生成的，它比相关字典更适合彩色图像。这一事实也被如表 3.4 
所示的量化指标所证实了。因此，图像修复结果的客观定量评价结果与主观视觉效果评价 
一致。 
图 3.14 三幅实验图像及其修复结果 
31
图像修复和图像融合 
表 3.4 修复图像与原始图像的 PSNR 指标值 
图 片 通 道 Criminisi 修复算法 
相似性比较方法 
sum max 
N01 
R 通道 31.2285 36.2735 38.8340 
G 通道 32.9927 37.0261 40.4300 
B 通道 33.8244 37.0565 41.3951 
RGB 32.6819 36.7854 40.2197 
N06 
R 通道 31.2285 36.2735 38.8340 
G 通道 32.9927 37.0261 40.4300 
B 通道 33.8244 37.0565 41.3951 
RGB 32.6819 36.7854 40.2197 
N05 
R 通道 31.2285 36.2735 38.8340 
G 通道 32.9927 37.0261 40.4300 
B 通道 33.8244 37.0565 41.3951 
RGB 32.6819 36.7854 40.2197 
N02 
R 通道 31.2285 36.2735 38.8340 
G 通道 32.9927 37.0261 40.4300 
B 通道 33.8244 37.0565 41.3951 
RGB 32.6819 36.7854 40.2197 
3.2.4 结论 
本章提出了一种新的基于稀疏表示的图像修复方法。为了解决固定字典带来的适应性 
差的问题，提出了基于稀疏表示的方法，该方法直接使用从未破损区域中的所有块构建的 
字典。因为字典由待修复图像未破损区域的所有块组成，这些块将包含大量不相关的原子， 
因此它们可能会影响修复结果。为了解决这个问题，提出了两种相似度度量的方法，即基 
于求和直方图和基于最大直方图的方法，用于比较目标块与所有候选块之间的相似度。然 
后选择相似的块组成相关字典和直方图字典。这样就可以避免不相关的块对稀疏表示造成 
干扰。
实验结果表明，使用直方图字典的图像修复结果优于使用相关词典的图像修复结果。 
此外，还将使用直方图字典提出的修复方法与 Criminisi 等提出的方法进行了比较，实验结 
果表明，前者在 PSNR 定性评价指标和视觉质量方面都表现出更好的性能。 
32