结合自适应梯度分块和等距变换的改进Criminisi图像修复方法

摘要

本发明提供一种结合自适应梯度分块和等距变换的改进Criminisi图像修复方法，在该发明中，首先对待修复图像的已知和修复区域进行标记，对落入已知区域的所有像素点计算梯度直方图，从而将已知区域像素点划分为平滑、纹理和边缘三种类型；其次结合块分类的改进优先权函数增强对边缘纹理部分的辨别能力，以克服传统方法所导致的纹理延伸问题；再次通过判断待修复块中的已知梯度信息判断待修复块所属的块类型，并通过建立自适应块大小函数来保证不同类型采用不同大小的块进行修复，并且只在对应的类型中进行匹配来提高匹配效率；最后通过引入等距变换来提高匹配精度。同现有方法相比，本发明较好地克服了纹理延伸，时间复杂度高等问题，提高了修复质量。

说明书

技术领域

本发明属于图像信号处理领域，涉及一种数字图像修复方法，特别涉及一种结合 自适应梯度分块和等距变换的改进Criminisi图像修复方法。

背景技术

图像修复是对图像缺失信息区域进行信息填充，其目的是使填充后的图像接近或 达到一定的视觉质量。图像修复技术是目前计算图形学和视觉计算中的研究热点，在文物 保护，破损图像修补和复原，目标障碍物剔除以及高分辨率图像再现上有着重大的应用和 研究价值。

基于变分PDE的图像修补技术和基于纹理合成的图像修复技术是两种主要的图像 修复策略。其中，变分PDE(PartialDifferentialEquation,PDE)的图像修补方法主体思 想是利用物理学中的热扩散方程，将待修补区域周围的有效信息扩散到待修补区域。其中， 比较典型的方法包括基于3阶PDE模拟平滑的BSCB(BertalmioSpairoCasellesand Bellester)方法(BertalmioM.,SapiroG.,CasellesV.,etal.Imageinpainting[C]// Proceedingsofthe27thannualconferenceonComputergraphicsand interactivetechniques.ACMPress/Addison-WesleyPublishingCo.,2000:417-424.) 模型、整体变分(TV,TotalVariation)模型(ChanT.F,ShenJ.MathematicalModelsfor LocalNontextureInpaintings.[J].SiamJournalonAppliedMathematics,2002,62 (3):1019-1043.)和结合三阶PDE的CDD(CurvatureDrivenDiffusions)方法(Chan T.Non-textureinpaintingbycurvaturedrivendiffusion[J].J.visualComm.image Rep,2001,12:436-449.)。这些方法能很好地保留图像线性结构，在修复小尺度破损图像有 较好的修复效果，然而上述方法是在有界变差空间上对图像建模，采用分段平滑函数将破 损区域周围信息扩散到破损区域，导致对大范围破损或富纹理缺失区域的修复质量则整体 欠佳。

针对变分PDE图像修补方法存在的不足，一些学者提出了基于纹理合成的图像修 复方法。比较典型的方法是Criminisi图像修复方法(CriminisiA.,PérezP.,Toyama K.Regionfillingandobjectremovalbyexemplar-basedimageinpainting[J] .IEEETransactionsonImageProcessing,2004,13(9):1200-1212.)，该方法主要由修 复区域优先权计算、修复块全局匹配搜索和匹配块填充3步组成，其主体思想是从待修补区 域边界上选取修复优先权最高的像素点，以该点为中心建立待修复块，利用待修复块中的 已知信息在已知信息区域内寻找与该块纹理最相近的块来填充待修补区域。尽管 Criminisi方法能够对大范围缺失信息图像进行较高质量的图像修复，但仍然存在很多不 足：

①Criminisi方法的优先权模型被设计为置信项和数据项的乘积，随着修补填充 的不断进行，置信项在迭代多次后急剧下降且趋于零值，但是数据项保持平稳变化，这就导 致数据项受制于趋于零值的置信项，使得优先权计算变得不可靠，因此导致错误的填充顺 序，从而影响图像修复质量；

②Criminisi方法在修复时并未对待修复块信息进行具体分析，导致优先权可能 计算不可靠，易将纹理部分误认为边缘部分，造成本来属于纹理部分的图像块先修复，从而 出现纹理延伸影响最终图像修复质量；

③Criminisi方法在整个图像已知信息的所有区域寻找合适的匹配块，而忽视自 然图像自身的局部自相似性，这将带来高昂的匹配计算代价；

④Criminisi方法仅采用块与块之间的Euclidean距离直接匹配存在欠缺，会导致 相似性度量不准确，造成直接匹配的目标块不是最佳目标块，从而影响图像修复质量。

针对问题①，文献(ChengW.H.,HsiehC.W.,LinS.K,etal.Robustalgorithm forexemplar-basedimageinpainting[C]//TheInternationalConferenceon ComputerGraphics,ImagingandVision(CGIV2005).2005:64-69.)将标准Criminisi方 法中优先权计算模型的置信项与数据项乘积改为两项之和，并对数据项与置信项赋予简单 的权重，以保证图像结构和纹理填充的正确顺序。文献(ZhouY.,LiL.,XiaK..Research onweightedpriorityofexemplar-basedimageinpainting[J].Journalof Electronics,2012,29(1):166-170.)则在此基础上，对优先权公式进一步设置，通过增加 数据项的权重来提高结构信息对于优先权的贡献度，使得所提策略在修复结构边缘图像时 有着良好性能，但与此同时对非结构边缘图像修复时则会降低视觉质量，同时该方法需根 据不同图像，手动选择不同的优先权模型，适用范围十分有限。文献(林云莉,赵俊红,朱学 峰,等.改进的纹理合成图像修复算法[J].计算机应用与软件,2010,27(10):11-12.)则在 优先权计算模型中引入补偿因子和加权系数，根据图像纹理结构信息来动态调节补偿因子 和加权系数，使得不同图像对应着不同的优先权计算方法，但是并没有解决优先权的自动 计算问题。文献(刘业妃，王福龙，奚祥艳.改进的Criminisi图像修复算法[J].小型微型计 算机系统,2014,35(12):2754-2758.)在修改优先权模型时通过将置信项改为指数函数的 形式，使得置信项的变化趋势相比原始方法更为平滑合理，但根据不同图像结构纹理信息 丰富程度人为的选取权重因子来控制置信项与数据项的比例，同样存在优先权的自动计算 问题。

针对问题②，文献(任澍,唐向宏,康佳伦.利用纹理和边缘特征的Criminisi改进 算法[J].中国图象图形学报,2012,17(9):1085-1091.)通过对待修复块已知像素点求其均 值和方差，利用其法线方向对待修复块进行分割，采用均值差差值和方差差值两个因素来 对图像待修复块进行纹理边缘区分，进而引入差别因子改进优先权模型，克服了修复过程 中的纹理延伸，但仍然不能解决由于不存在合适的匹配块所造成的修复失真，以及对待修 复块边缘纹理分类不合理问题；为解决存在不合适匹配块导致的修复失真问题，文献(任 澍,唐向宏,康佳伦.纹理和边缘特征相结合的图像修复算法[J].计算机辅助设计与图形学 学报,2013,25(11):1682-1693.)对修复过程中的不良匹配区域进行定位，采用基于图像分 解的图像修复方法进行修复；但是这两篇文章在对待修复图像块的边缘纹理信息判断时采 用均值差和方差差值两个因素来对图像待修复块进行纹理边缘区分，并没有对图像已知区 域内的所有信息进行划分，在匹配待修复块的最佳目标块时并没有针对待修复块的信息进 行分类搜索，从而依然无法有效地降低匹配计算代价。

针对问题③，为了降低计算代价，文献(任澍,唐向宏,康佳伦.利用纹理和边缘特 征的Criminisi改进算法[J].中国图象图形学报,2012,17(9):1085-1091.)调整方法在修 复过程中匹配块的搜索方式，在采用全局搜索的基础上，附加一个判断待修复块与目标匹 配块两个图像块中心距离的搜索条件，如果该距离过大，则停止修复，将修复目标转为次优 先级的修复块，若仍旧发生相同情况，则继续转移修复目标，且转移次数最多为3次，3次之 后忽略该条件按照原来的搜索方式进行匹配搜索，在效率上有所提高，但是依旧采用的是 全局搜索，时间复杂度高；为将全局搜索改为局部搜索，文献(代仕梅,张红英,曾超.一种基 于样例的快速图像修复算法[J].微型机与应用,2010(22):34-36.)通过减少和限定匹配块 的搜索空间来提高方法效率，尽管缓解了计算代价，但简单的搜索空间会导致丢失合理的 匹配块，从而降低图像的视觉修复质量。

针对④，文献(VantigodiS.,BabuR.V.,Entropyconstrainedexemplar-based imageinpainting[C]//SignalProcessingandCommunications(SPCOM), 2014InternationalConferenceon.IEEE,2014.)引入待修复像素值熵的信息，改进判断 相似度的方法，利用结构相似性指标SSIM的相似度判断方法来搜索与待修复块差异最小的 目标块；文献(王新年，王哲，王演.基于几何距离的Criminisi图像修复算法[J].计算机工 程与设计,2015,36.)引入距离修正因子，将待修复块与目标块的几何距离引入到判断相似 性度量函数中，在搜索目标块时首先通过欧式距离相似性函数找出3个目标块，然后根据几 何距离修正因子来找到最佳匹配块。但是，上述修复方法在搜索最佳匹配块时，并没有考虑 到可能存在经过等距变换后的目标块与样本块的相似度更高的问题。

发明内容

本发明的目的在于克服现有技术缺陷，给出一种结合自适应梯度分块和等距变换 的改进Criminisi图像修复方法，用于大样本缺失图像修复，相对于传统方法具有更高的方 法效率和更好的视觉质量。

为实现上述目的，本发明采用以下技术方案：

结合自适应梯度分块和等距变换的改进Criminisi图像修复方法，包括以下步骤：

第1步：记G＝(g_i,j＝-1)_m×n为待修复图像A＝(a_i,j)_m×n的梯度图，记Ω为待修复区 域，由标记矩阵B＝(b_i,j)_m×n中b_i,j＝0的元素进行标记，Φ为已知区域；由标记矩阵B＝ (b_i,j)_m×n中最开始b_i,j＝1的元素进行标记，Φ′为已修复区域；初始化Φ′＝Φ，为 待修复区域边界，对即b_i,j＝1中的元素，计算图像像素a_i,j对应的梯度值g_i,j， 即g_i,j＝Grad(a_i,j,(i,j))；

第2步：对G中每个g_i,j≠-1的元素按其对应的梯度值进行统计形成梯度直方图H_G＝(h_k)_L，其中h_k表示梯度值为k的G中元素发生次数，_L为梯度直方图中梯度阶数；

第3步：对梯度直方图中的每个梯度阶k＝0,1,…,L-1，统计每个梯度值的发生概 率P_k,k＝0,1,…,L-1；

第4步：将落入已修复区域Φ′中的每个像素划分成平滑、纹理和边缘区域像素；

第5步：对计算p点对应的优先权P_p；

第6步：确定优先权P_p最大的点自适应地确定当前待修复像素块的边长

第7步：判断梯度项的块类型，在图像已知区域Φ中寻找和相匹配的 的最优目标块的位置及其所对应的等距变换类型

第8步：利用最优目标块和最优目标块所对应的等距变换类型将变换 为并将当前待修复像素块中被b_i,j＝0标记的像素由中的对应位置像素进行填 充，然后将所有当前待修复像素块被填充像素的标记值由b_i,j＝0调整为b_i,j＝1；

第9步：反复执行第5步至第8步，直到图像中待修复区域Ω中所有像素点修复完 毕，即B＝(b_i,j)_m×n中所有元素都调整成b_i,j＝1，修复结束。

进一步，第1步中计算图像像素a_i,j对应的梯度值g_i,j,即g_i,j＝Grad(a_i,j,(i,j))的 具体方法为使用式(1)：

式(1)中，g_x和g_y是像素a_i,j的x方向和y方向梯度，分别按式(2)和式(3)进行计算：

g_x＝a_i,j+1-a_i,j-1(2)

g_y＝a_i+1,j-a_i-1,j(3)

式(2)和式(3)中，若且a_x,y∈Ω，即b_x,y＝0则用a_i,j替代a_x,y，从而保证每个落入已修补区域的元素a_i,j∈Φ′在G中都有对应的梯度值。

进一步，第3步中统计每个梯度值的发生概率P_k,k＝0,1,…,L-1的具体方法为式 (4)：

P_k＝h_k/N_count(4)

式(4)中，N_count是梯度直方图中所有梯度值的总数，按式(5)进行计算；

$N_{count}=\underset{k=0}{\overset{L-1}{\Sigma }}{h}_k---\left(5\right)$

第4步中将落入Φ′中的每个像素划分成平滑、纹理和边缘区域像素的具体方法为 式(6)：

式(6)中λ₁是平滑和非平滑区域分割阈值，λ₂是将非平滑区域细分为纹理和边缘区 域的分割阈值且满足0≤λ₁≤λ₂≤L-1。

进一步，第4步式(6)分割阈值λ₁和λ₂的具体确定方法为式(7)：

$\begin{array}{c}\hat{\lambda }=\underset{\lambda \in [{\lambda }_{begin},{\lambda }_{end}]}{\arg \max \left(\delta \right)}\\ \delta =\underset{i={\lambda }_{begin}}{\overset{\lambda }{\Sigma }}{P}_i{(u_{part1}-u_{total})}^2+\underset{j=\lambda +1}{\overset{{\lambda }_{end}}{\Sigma }}{P}_j{(u_{part2}-u_{total})}^2\end{array}---\left(7\right)$

即对区间范围内的λ∈[λ_begin,λ_end]，求解使目标式δ最大化的λ，即λ，式(7)中 u_part1,u_part2,u_total可分别按式(8)、式(9)和式(10)进行计算：

$u_{part1}=\underset{i={\lambda }_{begin}}{\overset{\lambda }{\Sigma }}{\mathrm{iP}}_i/\left(\underset{i={\lambda }_{begin}}{\overset{\lambda }{\Sigma }}{P}_i\right)---\left(8\right)$

$u_{part2}=\underset{i=\lambda +1}{\overset{{\lambda }_{end}}{\Sigma }}{\mathrm{iP}}_i/\left(\underset{i=\lambda +1}{\overset{{\lambda }_{end}}{\Sigma }}{P}_i\right)---\left(9\right)$

$u_{total}=\underset{i={\lambda }_{begin}}{\overset{{\lambda }_{end}}{\Sigma }}{\mathrm{iP}}_i---\left(10\right)$

将λ_begin＝0,λ_end＝L-1代入式(7)，可确定分割阈值λ₁，将λ_begin＝λ₁+1,λ_end＝L-1代 入式(7)，可确定分割阈值λ₂。

进一步，第5步对计算p点对应的优先权P_p的具体方法为式(11)：

P_p＝C_p·l+G_p·(1-l)(11)

式(11)中，C_p为置信项，G_p为梯度项，权重l∈[0,1]的取值按式(12)确定，即按p点 所属的边缘、平滑和纹理区域进行自适应地调整；

$l=\left(\begin{array}{cc}\beta & G_p>{\lambda }_2\\ \frac{\beta -\alpha }{{\lambda }_2-{\lambda }_1}(G_p-{\lambda }_1)+\alpha & {\lambda }_1<G_p\le {\lambda }_2\\ \alpha & G_p\le {\lambda }_1\end{array}\right)---\left(12\right)$

式(12)中，参数α∈[0,1]范围内的随机数且满足α+β＝1。

进一步，第5步式(11)中，置信项C_p，梯度项G_p的具体计算方法如式(13)和式(14)所 示：

$C_p=c_{{\psi }_p\cap {\Phi }^{\prime }}/c_{{\psi }_p}---\left(13\right)$

式(13)中，ψ_p为以p为中心的矩阵小块，是ψ_p中的元素数量，为ψ_p落入已 修补区域中的元素数量；

$G_p=\underset{q\in {\psi }_p\cap {\Phi }^{\prime }}{\Sigma }Grad(a_q,q)/c_{{\psi }_p\cap {\Phi }^{\prime }}---\left(14\right)$

式(14)中，q为ψ_p落入已修补区域Φ′的坐标，a_q为A中对应的像素。

进一步，第6步中确定优先权P_p最大的点的具体方法为式(15)：

$\hat{p}=\underset{p\in \partial \Omega }{\mathrm{argmax}}{P}_p---\left(15\right)$

第6步中自适应地确定当前待修复像素块的边长的具体方法为式(16)：

进一步，第7步中判断的块类型的具体方法为式(6)：

第7步中在图像已知区域Φ中寻找和相匹配的的最优目标块的 位置及其所对应的等距变换类型的具体方法为对且按 式(17)在图像已知区域Φ中寻找和相匹配的的最优目标块的位置及其所对 应的等距变换类型

$(\hat{q},\hat{t})=\arg \underset{\forall q\in \Phi ,\forall t\in \{0,1,...,7\}}{min}d({\Psi }_{\hat{p}},T({\Theta }_q,t\left)\right)---\left(17\right)$

式(17)中d()为欧氏距离表示样本块中已知像素和目标块T(Θ_q,t)中对应位 置像素差的平方和，T()等距变换函数，记Θ_q所对应的原子块子块旋转90度、180度、270度 对应子块以及这些子块的水平翻转子块分别为则T()执行的功能为式 (18)：

${\Theta }_q^t=T({\Theta }_q,t),t\in \{0,1,...,7\}---\left(18\right)$

式(18)中，即Θ_q与它的原子块等价。

同现有技术不同，本发明的优点主要体现在：

①在同一幅图像中存在着平滑、边缘和纹理区域，不同区域所包含的图像信息量 不同，传统Criminisi图像修复方法未对图像进行分类，导致在所有区域进行匹配搜索时代 价较大，而本发明将图像已知区域划分为平滑区域、纹理区域和边缘区域，只在特定的区域 进行搜索匹配，从而降低了匹配搜索代价，同时也减少了对纹理和边缘区域的误判，从而提 高了修复精度。在修复过程中，本发明根据梯度项预估待修复像素点属于哪一类图像区域， 自适应选择不同大小图像块。

②Criminisi修复方法的优先权模型被设计为置信项和数据项的乘积，随着修补 填充的不断进行，待修补块中已知信息的可靠性迅速下降导致代表纹理信息的置信项值迅 速下降，置信项在迭代多次后急剧下降且趋于零值，但是数据项保持平稳变化，这就导致数 据项受制于趋于零值的置信项，使得优先权计算变得不可靠，因此导致错误的填充顺序，从 而影响图像修复质量，针对此，本发明将优先权模型设计为加权的置信项与梯度项之和并 采用优先权系数加权自适应策略，在计算完待修复区域边界像素点的优先权顺序后，根据 梯度项的值结合图像分类的阈值来自适应改变加权系数，达到在修复过程中自适应根据像 素点的信息来进行修复。

③Criminisi修复方法在整个图像已知信息的所有区域寻找合适的匹配块，而忽 视自然图像自身的局部自相似性，这将带来高昂的计算代价，但是简单的减少搜索空间有 可能导致合理匹配块的丢失。本发明结合分类策略，在匹配样本块与目标块时，根据样本块 的已知信息判断其属于平滑、边缘和纹理的类型在对应的图像区域类型进行搜索，在减少 搜索时间的同时又能避免合理匹配块的丢失。

④Criminisi修复方法在搜索匹配块时，仅从已知区域中搜索，但是有可能样本块 与目标块等距变换后的像素块更为相近，同时传统Criminisi方法采用边修复边更新已知 区域，会带来误差扩展。针对此，本发明将搜索字典块改为已知区域的目标块及其八种等距 变换的像素块，提高样本块与目标块的相似性，进一步改善图像的视觉修复质量。同时本发 明在修复过程中不更新最初已知区域空间大小，搜索匹配区域一直保持在最初图像的已知 区域空间。

附图说明

图1是图像修复流程图；

图2是分辨率为206×308的24位灰度图像bungee；

图3是实施例：存在待修复区域的待修复图像bungee；

图4是实施例：图3修复完成图像；

图5是分辨率为512×512的24位灰度图像Tank；

图6是实施例：存在待修复区域的待修复图像Tank；

图7是实施例：图6修复完成图像；

图8是分辨率为213×284的8位灰度图像bw；

图9是实施例：存在待修复区域的待修复图像bw；

图10是实施例：图9修复完成图像；

图11是分辨率为512×512的8位灰度图像的baboon；

图12是实施例：存在待修复区域的待修复图像baboon；

图13是实施例：baboon修复完成图像。

具体实施方式

以JAVAjdk1.8.0_20作为案例实施环境，结合附图对本发明实施方式进行详细说 明，但不局限于本实施案例，其中图1是图像修复流程图。

第1步：记G＝(g_i,j＝-1)_m×n为待修复图像A＝(a_i,j)_m×n梯度图，记Ω为待修复区域， 由标记矩阵B＝(b_i,j)_m×n中b_i,j＝0的元素进行标记，Φ为已知区域，由标记矩阵B＝(b_i,j)_m×n中最开始b_i,j＝1的元素进行标记，Φ′为已修复区域，初始化Φ′＝Φ，为待修复区 域边界，对即b_i,j＝1中的元素，按式(1)计算图像像素a_i,j对应的梯度值g_i,j，即 g_i,j＝Grad(a_i,j,(i,j))：

式(1)中，g_x和g_y是像素a_i,j的x方向和y方向梯度，分别按式(2)和式(3)进行计算：

g_x＝a_i,j+1-a_i,j-1(2)

g_y＝a_i+1,j-a_i-1,j(3)

式(2)和式(3)中，若且a_x,y∈Ω，即b_x,y＝0则用a_i,j替代a_x,y，从而保证每个落入已修补区域的元素a_i,j∈Φ′在G中都有对应的梯度值；

假设选取的待修复图像A＝(a_i,j)_m×n为

$A=\left(\begin{array}{ccccc}{a}_{0,0}& a_{0,1}& a_{0,2}& a_{0,3}& a_{0,4}\\ a_{1,0}& a_{1,1}& a_{1,2}& a_{1,3}& a_{1,4}\\ a_{2,0}& a_{2,1}& a_{2,2}& a_{2,3}& a_{2,4}\\ a_{3,0}& a_{3,1}& a_{3,2}& a_{3,3}& a_{3,4}\\ a_{4,0}& a_{4,1}& a_{4,2}& a_{4,3}& a_{4,4}\end{array}\right)=\left(\begin{array}{ccccc}10& 20& 30& 40& 50\\ 20& 10& 20& 30& 40\\ 30& 40& 50& 255& 30\\ 40& 70& 80& 255& 20\\ 50& 40& 255& 20& 10\end{array}\right),$

其中A中元素255所对应的区域为待修复区域Ω，则A所对应的标记矩阵B＝ (b_i,j)_m×n为：

$B=\left(\begin{array}{ccccc}{b}_{0,0}& b_{0,1}& b_{0,2}& b_{0,3}& b_{0,4}\\ b_{1,0}& b_{1,1}& b_{1,2}& b_{1,3}& b_{1,4}\\ b_{2,0}& b_{2,1}& b_{2,2}& b_{2,3}& b_{2,4}\\ b_{3,0}& b_{3,1}& b_{3,2}& b_{3,3}& b_{3,4}\\ b_{4,0}& b_{4,1}& b_{4,2}& b_{4,3}& b_{4,4}\end{array}\right)=\left(\begin{array}{ccccc}1& 1& 1& 1& 1\\ 1& 1& 1& 1& 1\\ 1& 1& 1& 0& 1\\ 1& 1& 1& 0& 1\\ 1& 1& 0& 1& 1\end{array}\right)$

则已知区域Φ对应为标记矩阵B＝(b_i,j)_m×n中元素为1的区域，已修复区域Φ′被初 始化为Φ，待修复区域边界对应为标记矩阵中元素b_1,3,b_2,2,b_3,2,b_4,1,b_4,3,b_3,4,b_2,4所在 位置；

对可计算其梯度：例如由于b_1,2＝1，故a_1,2＝20所对应的梯度值g_1,2可由 式(2)：g_x＝a_1,3-a_0,1＝20和式(3)：g_y＝a_2,2-a_0,2＝20则按式(1)可计算得到 例如由于b_2,2＝1，故a_2,2＝50所对应的梯度值g_2,2需要用到a_2,3, a_2,1,a_1,2,a_3,2，但a_2,3属于待修复区域Ω，此时用a_2,2替代a_2,3，然后由式(2)计算可得到g_x＝ 10，然后由式(3)计算得到g_y＝60，故g_2,2＝60；通过对图像中已知区域的所有像素点进行梯 度值计算可得图像A所对应的梯度图G。

$G=\left(\begin{array}{ccccc}{g}_{0,0}& g_{0,1}& g_{0,2}& g_{0,3}& g_{0,4}\\ g_{1,0}& g_{1,1}& g_{1,2}& g_{1,3}& g_{1,4}\\ g_{2,0}& g_{2,1}& g_{2,2}& g_{2,3}& g_{2,4}\\ g_{3,0}& g_{3,1}& g_{3,2}& g_{3,3}& g_{3,4}\\ g_{4,0}& g_{4,1}& g_{4,2}& g_{4,3}& g_{4,4}\end{array}\right)=\left(\begin{array}{ccccc}14& 22& 22& 22& 14\\ 22& 20& 28& 22& 22\\ 22& 63& 60& -1& 20\\ 36& 40& 31& -1& 20\\ 14& 31& -1& 10& 14\end{array}\right)$

第2步：对G中每个g_i,j≠-1的元素按其对应的梯度值进行统计形成梯度直方图H_G＝(h_k)_L；

仍以$G=\left(\begin{array}{ccccc}14& 22& 22& 22& 14\\ 22& 20& 28& 22& 22\\ 22& 63& 60& -1& 20\\ 36& 40& 31& -1& 20\\ 14& 31& -1& 10& 14\end{array}\right)$为例，除去G中g_i,j≠-1的元素，可得：

h₁₀＝1,h₁₄＝4,h₂₀＝3,h₂₂＝7,h₂₈＝1,h₃₁＝2,h₃₆＝1,h₄₀＝1,h₆₀＝1,h₆₃＝1。

第3步：对梯度直方图中的每个梯度阶k＝0,1,…,L-1，按式(4)统计每个梯度值的 发生概率P_k,k＝0,1,…,L-1

P_k＝h_k/N_count(4)

式(4)中，N_count是梯度直方图中所有梯度值的总数，按式(5)进行计算；

$N_{count}=\underset{k=0}{\overset{L-1}{\Sigma }}{h}_k---\left(5\right)$

例如：由h₁₀＝1,h₁₄＝4,h₂₀＝3,h₂₂＝7,h₂₈＝1,h₃₁＝2,h₃₆＝1,h₄₀＝1,h₆₀＝1,h₆₃＝1 按式(5)得N_count＝h₁₀+h₁₄+h₂₀+h₂₂+h₂₈+h₃₁+h₃₆+h₄₀+h₆₀+h₆₃＝22，代入式(4)，可得P₁₀＝0.05， P₁₄＝0.18，P₂₀＝0.14，P₂₂＝0.22，P₂₈＝0.05，P₃₁＝0.09，P₃₆＝0.05，P₄₀＝0.05，P₆₀＝0.05，P₆₃＝0.05；

第4步：按式(6)将落入Φ′中的每个像素划分成平滑、纹理和边缘区域像素：

式(6)中λ₁是平滑和非平滑区域分割阈值，λ₂是将非平滑区域细分为纹理和边缘区 域的分割阈值且满足0≤λ₁≤λ₂≤L-1分割，阈值λ₁和λ₂可按式(7)确定：

$\begin{array}{c}\hat{\lambda }=\underset{\lambda \in [{\lambda }_{begin},{\lambda }_{end}]}{\arg \max \left(\delta \right)}\\ \delta =\underset{i={\lambda }_{begin}}{\overset{\lambda }{\Sigma }}{P}_i{(u_{part1}-u_{total})}^2+\underset{j=\lambda +1}{\overset{{\lambda }_{end}}{\Sigma }}{P}_j{(u_{part2}-u_{total})}^2\end{array}---\left(7\right)$

即对区间范围内的λ∈[λ_begin,λ_end]，求解使目标式δ最大化的λ，即式(7)中u_part1, u_part2,u_total分别按式(8)、式(9)和式(10)进行计算：

$u_{part1}=\underset{i={\lambda }_{begin}}{\overset{\lambda }{\Sigma }}{\mathrm{iP}}_i/\left(\underset{i={\lambda }_{begin}}{\overset{\lambda }{\Sigma }}{P}_i\right)---\left(8\right)$

$u_{part2}=\underset{i=\lambda +1}{\overset{{\lambda }_{end}}{\Sigma }}{\mathrm{iP}}_i/\left(\underset{i=\lambda +1}{\overset{{\lambda }_{end}}{\Sigma }}{P}_i\right)---\left(9\right)$

$u_{total}=\underset{i={\lambda }_{begin}}{\overset{{\lambda }_{end}}{\Sigma }}{\mathrm{iP}}_i---\left(10\right)$

将λ_begin＝0,λ_end＝L-1代入式(7)，可确定分割阈值λ₁，将λ_begin＝λ₁+1,λ_end＝L-1,可 确定分割阈值λ₂；

例如：根据标记矩阵B，将梯度图中相对应位置b_i,j＝1的所有梯度值进行分类，得 到两个分割点λ₁,λ₂；假设P₁₀＝0.05，P₁₄＝0.18，P₂₀＝0.14，P₂₂＝0.22，P₂₈＝0.05，P₃₁＝0.09， P₃₆＝0.05，P₄₀＝0.05，P₆₀＝0.05，P₆₃＝0.05，且有λ_begin＝0,λ_end＝63，将其分别代入式(8)、 式(9)和式(10)可分别得到：u_part1＝0.06，u_part2＝0.03，u_total＝25.86，然后将P₁₀＝0.05，P₁₄＝0.18，P₂₀＝0.14，P₂₂＝0.22，P₂₈＝0.05，P₃₁＝0.09，P₃₆＝0.05，P₄₀＝0.05，P₆₀＝0.05，P₆₃＝ 0.05和u_part1＝0.06，u_part2＝0.03，u_total＝25.86代入式(7)可得到：δ₁₀＝27.02，δ₁₄＝69.29， δ₂₀＝48.04，δ₂₂＝0.04，δ₂₈＝0.91，δ₃₁＝8.99，δ₃₆＝14.37，δ₄₀＝17.81，δ₆₀＝17.59，δ₆₃＝ 7.42，可得到最大类间方差i＝14，从而可得到分割点λ₁＝14，同理可得分割点λ₂＝20；

第5步：记p为上边界点，即按式(11)和式(12)分别计算的 置信项C_p和梯度项G_p

$C_p=c_{{\psi }_p\cap {\Phi }^{\prime }}/c_{{\psi }_p}---\left(11\right)$

式(11)中，ψ_p为以p为中心的矩阵小块，是ψ_p中的元素数量，为ψ_p落入已 修补区域中的元素数量。

$G_p=\underset{q\in {\psi }_p\cap {\Phi }^{\prime }}{\Sigma }Grad(a_q,q)/c_{{\psi }_p\cap {\Phi }^{\prime }}---\left(12\right)$

式(12)中，q为ψ_p落入已修补区域Φ′的坐标，a_q为A中对应的像素。

例如：假设p点为边界上的点，以p为中心的矩阵小块中的元素数量为49，该矩阵小 块在已知区域中的元素数量为35，代入式(11)得C_p＝0.71，且该矩阵小块在已知区域中所 有像素点的梯度值和为455，代入式(12)得，则G_p＝13。

第6步：对按式(13)计算p点对应的优先权P_p：

P_p＝C_p·l+G_p·(1-l)(13)

式(13)中，权重l∈[0,1]的取值按式(14)确定，即按p点所属的边缘、平滑和纹理 区域进行自适应地调整

$l=\left(\begin{array}{cc}\beta & G_p>{\lambda }_2\\ \frac{\beta -\alpha }{{\lambda }_2-{\lambda }_1}(G_p-{\lambda }_1)+\alpha & {\lambda }_1<G_p\le {\lambda }_2\\ \alpha & G_p\le {\lambda }_1\end{array}\right)---\left(14\right)$

式(14)中，参数α∈[0,1]范围内的随机数且满足α+β＝1，参数α可按优化方法结合 无参考图像评价方法优化得到；

例如：假设p点为优先权最大的点，将G_p＝13代入式(6)可知，p点的块类型type(G_p) ＝平滑，假设α＝0.2,λ₁＝14，代入式(14)可知l＝0.2，将C_p＝0.71，G_p＝13，l＝0.2，代入式 (13)可知：P_p＝10.54；

第7步：按式(15)确定优先权P_p最大的点按式(16)自适应地确定当前待修复像 素块的边长

$\hat{p}=\underset{p\in \partial \Omega }{\mathrm{argmax}}{P}_p---\left(15\right)$

例如：假设优先权最大的点所对应的将代入式(16)可知

第8步：按式(6)判断的块类型，对且按式(17) 在图像已知区域Φ中寻找和相匹配的的最优目标块的位置及其所对应的 等距变换类型

$(\hat{q},\hat{t})=\arg \underset{\forall q\in \Phi ,\forall t\in \{0,1,...,7\}}{min}d({\Psi }_{\hat{p}},T({\Theta }_q,t\left)\right)---\left(17\right)$

式(17)中d()为欧氏距离，表示样本块中已知像素和目标块T(Θ_q,t)中对应位 置像素差的平方和，T()等距变换函数，记Θ_q所对应的原子块子块旋转90度、180度、270度 对应子块以及这些子块的水平翻转子块分别为则T()执行的功能为式 (18)：

${\Theta }_q^t=T({\Theta }_q,t),t\in \{0,1,...,7\}---\left(18\right)$

式(18)中，即Θ_q与它的原子块等价；

例如：假设p点的样本块Ψ_p块类型在已知区域Φ中匹配的最佳目标块为T(Θ_q,1)， 则将q和1返回作为和

第9步：将和代入式(18)，从而将变换为并将中被b_i,j＝0标记的像 素由中的对应位置像素进行填充，然后将所有被填充像素的标记值由b_i,j＝0调整为 b_i,j＝1；

例如：假设${\Theta }_{\hat{q}}=\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 6& 7& 8& 9& 10\\ 11& 12& 13& 14& 15\\ 16& 17& 18& 19& 20\\ 21& 22& 23& 24& 25\end{array}\right),\hat{t}=1,$则：$T({\Theta }_{\hat{q}},\hat{t})=\left(\begin{array}{ccccc}21& 16& 11& 6& 1\\ 22& 17& 12& 7& 2\\ 23& 18& 13& 8& 3\\ 24& 19& 14& 9& 4\\ 25& 20& 15& 10& 5\end{array}\right),$

若${\Psi }_p=\left(\begin{array}{ccccc}3& 2& 3& 255& 255\\ 6& 7& 8& 255& 255\\ 11& 12& 255& 14& 255\\ 19& 17& 18& 19& 20\\ 21& 255& 23& 255& 25\end{array}\right),$对应的标记矩阵为$\left(\begin{array}{ccccc}1& 1& 1& 0& 0\\ 1& 1& 1& 0& 0\\ 1& 1& 0& 1& 0\\ 1& 1& 1& 1& 1\\ 1& 0& 1& 0& 1\end{array}\right)$

则将最佳目标块T(Θ_q,1)填充到样本块后Ψ_p，Ψ_p中的像素值对应为：

${\Psi }_p=\left(\begin{array}{ccccc}3& 2& 3& 6& 1\\ 6& 7& 8& 7& 2\\ 11& 12& 13& 14& 3\\ 19& 17& 18& 19& 20\\ 21& 20& 23& 10& 25\end{array}\right)$

此时可将$\left(\begin{array}{ccccc}1& 1& 1& 0& 0\\ 1& 1& 1& 0& 0\\ 1& 1& 0& 1& 0\\ 1& 1& 1& 1& 1\\ 1& 0& 1& 0& 1\end{array}\right)$调整为$\left(\begin{array}{ccccc}1& 1& 1& 1& 1\\ 1& 1& 1& 1& 1\\ 1& 1& 1& 1& 1\\ 1& 1& 1& 1& 1\\ 1& 1& 1& 1& 1\end{array}\right).$

第10步：重复执行第5步至第9步，直到图像中待修复区域Ω中所有像素点修复完 毕，即B＝(b_i,j)_m×n中所有元素都调整成b_i,j＝1，修复结束。

图2、图5、图8和图11分别为修复测试图像bungee、Tank、bw和baboon，图3、图6、图9 和图12是与之对应的存在缺失信息的待修复图像，图4、图7、图10和图13是按本发明给出的 图像修复方法对其修复的结果，从修复结果看，本方法较好的视觉修复效果。