胶片电影中的快速斑块修复算法研究

刘泉洋，刘云清，史俊，颜飞，张琼

（长春理工大学 电子信息工程学院，长春 130022）

电影视频档案作为一种重要的信息记录方式，记录一个国家的社会历史、政治、经济等各方面的重要事件，目前仅中国电影资料馆就保存了近3万部影像资料。早期的拍摄设备限制，大多数影片档案以胶片的形式进行存储，胶片在恒温恒湿等特定条件下，其影像可以完好的保存百年以上。但现实并不能尽如人意，由于年代久远，保存条件不够理想或者转印、播放次数过多等原因，电影胶片存在着灰尘、污垢、斑块、掉色、图像抖动、划伤、闪烁、噪声、变色、模糊［1］等各种问题。造成斑块损伤的原因有很多，使得斑块出现频率最高，对视觉的影响较大，所以斑块修复十分重要。斑块属于单帧突发性视频失真，其特征主要表现有两点：一是斑块只存在于单帧图像中，无前后帧信息关联；二是斑块的形状不规则，出现的位置具有随机性。针对上述斑块的特征，很多学者提出了解决斑块问题的优秀算法。这些算法的修复质量较好，但视频修复时间较长。由于视频修复需要处理的数据量十分庞大，为了进一步提高胶片电影中斑块修复的速度，本文提出一种快速斑块检测与修复算法，该方法通过优化斑块检测算法中的运动估计模型，简化斑块修复模型，提升斑块检测与修复的整体速度。

1 相关工作

1.1 斑块检测算法

斑块的数学模型可表示为：

其中，向量i表征像素点空间坐标；x(i)表示原图像；z(i)是加入斑块后的图像；d(i)∈{0，1}：0表示该点没有被斑块覆盖，1表示已被斑块覆盖；y(i)表示被斑块覆盖的区域。

常见的斑块检测算法有SDI（Spike Detection Index）检 测 器［2］、ROD（Rank Ordered Difference）检测器［3］、MRF（Markov Random Filed）检测器［3］、AR（Autoregression）检测器［3］等。SDI算法利用了斑块在相邻三帧间的不连续性来进行检测。ROD检测器首对参考帧进行运动补偿，然后在参考帧各选取若干像素进行排序；最后进行多阈值判断，类似于自适应中心加权滤波器中的脉冲噪声检测部分的算法，ROD容易受到噪声干扰。MRF模型由kokaram提出，其核心思想是最大化在前后参考帧图像和当前帧图像观测条件下掩膜函数的概率，MRF模型较为复杂，所以其计算复杂度较高。AR检测器基本原理是根据当前帧的图像可由运动补偿后的前向参考帧和后向参考帧来预测。上述检测算法大多是先对图像序列进行运动补偿，再与参考帧做差值，对差值设置特定的阈值，生成掩模图像。斑块检测算法除了MRF检测器模型过于复杂，其他检测算法耗时最多的部分的运动估计部分，因此，快速斑块检测算法的关键在于对运动估计模型的优化。

图1表示的是斑块检测算法简化模型。首先对图像序列进行运动估计，求出运动矢量后对图像序列进行运动补偿，对运动补偿后的图像与参考帧做差值处理，再对差值图像做阈值分割处理，得出斑块掩模图像。

图1 检测器模型图

上述模型的运动估计部分是整个模型的关键部分，也是耗时较多的部分。由于块匹配算法（Block Matching Algorithm，BMA）在计算处理和硬件实现上较为容易［4］，使其成为运动估计算法中应用最广泛算法，被许多视频压缩编码标准所采用，如 H.261/3/4 和 MPEG-2/4［5］。

块匹配算法采用为二维宏块搜索匹配运动矢量最优值［6］。对于全局运动估计的搜索，完整二维宏块存在大量的信息冗余，会增大搜索匹配过程中的计算量，很难通过优化搜索策略和宏块位置等方法大幅度提升算法运算速度。

1.2 一维块匹配运动估计算法

为了进一步提高算法的速度，降低算法实现的复杂度，本文提出了一维块匹配运动估计算法（One-dimensional block matching algorithm，OB⁃MA）。

（1）一维特征矩阵

通过对运动矢量的特点进行分析，运动矢量精度是单位像素，方向和大小均不确定。因此本文采用先对运动矢量正交分解，分解为两个分矢量。如图2所示，其中运动矢量MV的分量x为水平方向和分量y为垂直方向。

图2 运动矢量分解图

求解运动矢量分量x和运动矢量分量y需要使用一维特征矩阵X和一维特征矩阵Y，一维特征矩阵求解过程如下：

其中，A和B为权重系数矩阵；λ为权重系数矩阵A的权重系数；μ为权重系数矩阵B的权重系数，权重系数为设定值，本文设置的值为灰度级的倒数；P为匹配宏块矩阵，形状为（n，m），特征矩阵X的形状为（1，m）；PT为矩阵P的转置矩阵，形状为（m，n），特征矩阵Y的形状为（1，n）。

（2）一维三步搜索法

相比于全搜索法（Full Search，FS）要遍历搜索区域所有像素点，三步搜索法的搜索点数大幅减少［7］。有别于全搜索法逐一遍历所有像素点，三步搜索法每一步搜索是搜索边界上的8个点以及正方形的中心点共9个搜索点进行比较，根据匹配准则得出最佳匹配点，搜索步长等于或者略大于最大搜索范围的一半。上一步比较得到的最佳匹配点作为下一个新的搜索步的搜索中心。当搜索范围大于7时，搜索步数大于3步。三步搜索法的搜索方式如图3所示，其中圆形为第一步搜索点，方形为第二步搜索点，三角形为第三步搜索点。

图3 三步搜索法

本文的特征矩阵X和特征矩阵Y是一维矩阵，因此需要将二维三步搜索法改为一维三步搜索法（One-dimensional Three Step Search，OTSS）。一维三步搜索法的搜索步骤与三步搜索法类似，每步搜索对搜索边界上的2个点以及中心点共3个搜索点进行比较，本文匹配准则使用最小绝对误差和准则（SAD），搜索步长等于或者略大于最大搜索范围的一半。上一步比较后得到的最优匹配点，作为下一步新的搜索中心。一维三步搜索法如图4所示，其中圆形为第一步搜索点，方形为第二步搜索点，三角形为第三步搜索点，横轴表示水平或垂直方向的像素坐标。

图4 一维三步搜索法

一维块匹配算法步骤如下：

（1）首先读取当前帧图像和前一帧图像，提取当前帧图像是匹配宏块区域，使用权重系数矩阵求出匹配宏块的特征矩阵X和特征矩阵Y。

（2）提取前一帧图像匹配宏块的最大可能出现区域，使用权重系数矩阵求出最大可能出现区域的特征矩阵XR和特征矩阵YR，从特征矩阵XR中截取匹配特征矩阵Xi，Xi形状与前帧图像的特征矩阵X相同，i为Xi的偏移量，从特征矩阵YR截取匹配特征矩阵Yj，Yj形状与前帧图像的特征矩阵Y相同，j为Yj的偏移量。

（3）将特征矩阵X和匹配特征矩阵Xi组成一组特征矩阵，用于搜索x方向的运动矢量分量x，将特征矩阵Y和匹配特征矩阵Yi组成一组特征矩阵，用于搜索y方向的运动矢量分量y；搜索策略选择一维三步搜索法，匹配准则选择绝对误差和准则，通过改变偏移量i和j的值，搜索匹配分量x和分量y最优值。

（4）最后将运动矢量分量最优值组合为完整运动矢量MV。

1.3 斑块修复算法

斑块的修复过程实质上寻找合适的像素信息填入斑块区域的插值过程。最简单的方法是直接使用参考帧中相同位置的像素内容去代换当前帧中斑块遮盖的内容，而这种方法显然只能使用在静态图像序列中，动态图像序列修复效果较差［8］。在此基础上是加入运动补偿的帧间预测方法，对运动图像序列修复有较好的效果。

常见的斑块修复算法有MRF插值算法［2］、3D AR插值算法［3］、多级中值滤波器插值算法（Multistage Median Filter，MMF）［4］、空间插值算法［4］、控制粘贴算法［4］。MRF 插值算法的核心思想是在前后帧图像和当前帧图像的观测条件下寻找斑块区域的最大后验估计。空间插值算法是利用视频信号在空间上存在的相关性，使用帧内相邻的原始图像像素来重构搜索区域的图像数据。3D插值算法利用了当前帧与前后帧之间在时间上的相关性，对当前帧的像素进行基于相邻若干帧对应点的线性合并，使之获得最佳预测结果。MMF算法采用中值滤波器理论，当前帧的某个点进行多次中值滤波处理。控制粘贴算法是一种简化的AR模型，对于当前帧的某一需要修复的像素，该算法仅从参考前帧和参考后帧提取相应的点粘贴到当前像素位置，对比前一帧和后一帧的哪个更合适被用来填补，这可以被看作是一步AR插值法。上述修复算法是在检测模型生成掩模图像后，根据前后帧信息修复斑块区域。由于胶片电影拍摄设备的限制，导致其清晰度较低，所以对修复算法的精度要求不高，即使采用直接填补法，也可以达到很好的修复效果，同时提高修复算法的速度。

1.4 基于运动补偿的单参考帧修复算法

根据视频图像序列的特点，当视频画面帧非场景切换帧时，人眼观察到的斑块是本帧画面与前一帧画面像素信息发生突变导致，所以本算法省略了控制粘贴法对后一帧信息的使用，只使用前一帧画面作为参考帧。当视频画面帧是场景切换帧时，只使用后一帧画面作为参考帧。本文使用的斑块修复算法入式：

其中，zmc为z加入运动补偿后的图像；f是场景切换标识位，0表示非场景切换帧，1表示场景切换帧。

2 算法流程

本算法将视频帧序列分为场景切换帧和非场景切换帧，场景切换帧的修复使用的参考帧为当前帧的后一帧图像，非场景切换帧修复使用的参考帧为当前帧的前一帧图像。整体算法可分为三步：首先根据参考帧求出当前帧的运动矢量；然后对当前帧图像进行运动补偿，与参考帧做差值图像，设定阈值求出斑块掩模图像；最后根据掩模图像利用参考帧信息修复当前帧图像。快速斑块检测与修复算法流程图如图5所示。

图5 算法流程图

3 实验结果

为了验证本文提出的快速斑块检测与修复算法的性能，分别从主观和客观两方面分析本文提出的算法与改进前算法。改进前算法中的运动估计模块为传统的二维块匹配算法；修复模块为控制粘贴算法，控制粘贴算法中的前后帧判别依据选择峰值信噪比。本文提出的快速斑块检测与修复算法的运动估计模块选择一维块匹配算法；修复模块为基于运动补偿的参考帧修复算法。

3.1 实验平台

本文进行实验的计算机配置为AMD Ryzen5 2600 CPU（3.40 GHz），内存为16 GB；操作系统为Window10；编程环境为python3.6。

3.2 算法性能主观评价

为了直观对比本文提出的一维块匹配算法与二维块匹配算法的实际效果，选取测试视频图像序列中两个不同场景，将未加入运动补偿的前后帧差值图像与加入运动补偿后的前后帧差值图像进行对比。考虑到差值图像对比度较低，为了提高差值图像的对比度，对样本的结果做直方图均衡化处理，最后得到对比度增强后的差值图像，如图 6、图 7所示。图 6（a）、图 7（a）是未加入运动补偿后，与前一帧参考帧的差值图像；图6（b）、图 7（b）为加入运动补偿后，与前一帧参考帧的差值图像，运动估计算法为二维块匹配算法；图 6（c）、图 7（c）为加入运动补偿后，与前一帧参考帧的差值图像。

通过图6、图7中2个不同场景下运动补偿后的差值图像对比分析，本文提出的运动估计算法的实际补偿效果与传统块匹配法基本一致。

图6 场景一前后帧差值图像

图7 场景二前后帧差值图像

图8、图9和图10为两种算法在不同场景下的带斑块图像修复效果，其中图 8（a）、图 9（a）和图 10（a）为未修复的原始图像，图 8（b）、图 9（b）和图10（b）为改进前修复算法的修复效果，图8（c）、图9（c）和图10（c）为改进算法的修复效果。

从主观角度对比图8、图9、图10中不同场景下斑块修复算法的修复效果，改进后的算法修复效果与改进前算法修复效果基本一致。

图8 场景一斑块修复效果

图9 场景二斑块修复效果

图10 场景三斑块修复效果

3.3 算法性能客观指标

测试样本选择连续50帧视频图像序列，客观指标参数选择算法的运行时间。如图11所示，其中图11（a）为运动估计模块运行时间，图11（b）为修复模块运行时间，图 11（c）为完整修复算法运行时间。

根据图11（a）和表1中的运动估计平均时间可以看出，一维匹配运动估计算法运行时间少于二维块匹配算法；根据图11（b）和表1的修复模块平均运行时间可以看出，本文提出单参考帧的修复算法运行时间少于传统双参考帧修复算法；根据图11（c）和表1的完整算法平均运行时间可以看出，本文提出快速斑块修复算法运行时间少于传统斑块修复算法。

图11 运行时间

表1 改进前算法与改进后算法在连续50帧视频序列平均运行时间/ms

通过以上数据分析，本文提出快速斑块修复算法的运动估计模块、修复模块和算法整体的运行时间均少于传统斑块修复算法。由于胶片电影数字化后庞大的数据量，以及胶片电影中斑块问题的普遍性，传统修复算法面对庞大的数据量势必会花费大量的时间，使用本文提出快速斑块修复算法可以有效地解决此问题。

4 结论

传统的斑块修复算法依然停留在直接使用二维信息计算运动估计，使用前后帧作为参考帧修复斑块。本文通过对胶片视频与斑块特点的研究，发现二维宏块经过权重系数矩阵降维后的一维特征矩阵具备二维矩阵的部分特征，使用一维特征矩阵代替二维矩阵进行运动估计，可以有效地提高运动估计模块的效率；使用单参考帧修复斑块，可以满足胶片电影对清晰度的要求下，提高修复速度。本文提出的斑块修复算法将一维块匹配运动算法代替二维块匹配运动算法，将单参考帧的斑块修复算法代替双参考帧的斑块修复算法。实验结果表明：本文提出的快速斑块修复算法的速度比改进前的传统算法快。下一步的研究方向是分析胶片电影中的划痕问题，提高划痕的修复效果和修复速度。