基于5×5邻域像素点相关性的划痕修复算法

徐 敏, 丁友东, 于 冰, 李 畅, 吴 彪, 张婉莹

(1.上海大学上海电影学院,上海200072;2.上海大学上海电影特效工程技术研究中心,上海200072)

划痕是旧电影、旧照片中比较常见的一种画面损伤.由于年代久远、存放的技术条件有限、多次转印播放以及胶片本身老化等原因,会造成影片在前后帧几乎相同的位置持续出现不同长度和宽度的划痕.如果不及时对其进行修复整理,破损区域还会继续扩散,甚至祸及画面中的其他地方.手工修复对修图师自身的技术水平要求很高,消耗时间也长,因此寻求高效的数字图像修复算法很有现实意义.已有的划痕修复算法大致分为空间插值[1]、小波域修复[2]、改进的图像修补算法[3-4]3种,且都趋向于帧内修复.在修复较长较宽的划痕时,这些算法容易产生模糊、假边缘和阶梯效应,且难于理解和实现[5].一般来说,划痕两端的距离较远、相关性较弱,并且划痕两侧存在余弦衰减区域,待修复区域邻域一层像素点会存在噪声和游离的衰减区域点或跳变点[6].如果仅仅通过传统的4邻域或8邻域中的相关像素点来修复,肯定会产生错误积累,出现划痕修复不彻底和模糊现象.本工作改进了传统图像修补算法,并将其应用到旧的影视资料的划痕修复中.本工作的主要思想是利用待修复区域与周围24个邻近像素点的相关性,通过定义划痕边界待修复像素点的优先度来确定填充顺序;并结合图像本身的结构特征,依次修复每一个像素点并及时更新此像素点及其附近边界像素点的优先度,重复操作直至待修复区域像素点的个数为0.

1 划痕修复问题的数学描述

划痕修复是一个病态问题,即不可能将一幅图像完全修复到出现划痕损坏之前的状态.在实际应用中,只能利用图像中未被损坏的信息,按照一定原则去修复划痕所在区域.划痕修复实际上是不可逆的,但可以通过一些技术手段使修复后的划痕所在区域与原图近似相等.对于带有划痕的图像I,其像素点可以分为两类:一类是完整正常的区域ID;另一类是划痕所在区域IS.旧电影胶片上出现的划痕大多为水平划痕和垂直划痕两种,宽度为3∼10个像素,倾斜角小于5◦,划痕处的灰度值与相邻行或列的灰度值的差值绝对值在5∼30之间,且经常出现在亮或暗的地方[7].记描述划痕的掩膜图像为M,是一个二值图像,标记待修复区域为0,已知区域为1,则对应的像素点S的公式可表示为

一般情况下,待修复像素点与邻域已知像素点的分布情况以及纹理结构信息高度相关[8].首先,邻域已知像素点的分布可以从两个维度去描述:已知像素点的个数、已知像素点离待修复像素点的距离.从信息论角度考虑,待修复像素点的信息能够由邻域内已知像素点提供,越靠近待修复像素点的邻域像素点能提供的信息量越大.如果两个待修复像素点邻域内已知像素点的个数相同,则邻域内已知像素点距离权重和越大的越优先被修复.在本工作中,待修复像素点与其24邻域内像素点的距离可采用曼哈顿距离法衡量.距离越小,权值越大,相关性越强;距离越大,权值越小,相关性越弱.其次,纹理结构信息可以用图像梯度来描述.图像梯度体现了当前像素点颜色值变化的快慢和方向[9].事实上,每一幅图像都有其整体和局部上的纹理结构信息,并反映在其邻域像素点相关性上.对于具体的图像,如果其垂直方向上的邻域相关性大于其他方向,则这幅图像的内容呈垂直条纹效果[10].

本工作采用5×5的局部区域规模算子H,窗口步长为1,构造以H区域内像素点颜色值为元素的向量[hi,j],0

2 基于24邻域的划痕修复算法及实现

基于24邻域的划痕修复算法的思路是先输入待修复图像,再通过边界跟踪算法锁定待修复区域,然后按照一定的优先准则确定边界上最先修复的像素点p,之后更新修复边界,不断迭代,直至边界像素点个数为0.由于待修复区域的邻域内已知像素点个数最多的像素点一定在边界上,所以边界跟踪等价于寻找邻域已知像素点个数最多的待修复像素点.定义优先准则是为了找到应该最先被修复的像素点p.研究发现,p点的修复顺序主要与3个因素有关:邻域已知像素点的个数Nqi、邻域已知像素点的分布Fqi、邻域已知像素点的梯度Gqi.

2.1 优先度计算

定义优先度法则是根据像素点的初始状态确定最先被修复的像素点p.图1所示是一个宽度为5个像素的垂直划痕灰度小样.经研究发现,优先度主要依赖于如下3个因素.

图1 划痕小样Fig.1 Scratch samples

(1)24邻域内已知像素点个数越多的像素点越优先被修复.在输入待修复图像I和掩码图像M的同时,系统也进行了初始化操作:在待修复区域,flag=0;否则,flag=1.求p点邻域内已知像素点的个数Nqi等同于计算p点邻域内“1”的个数.假设q(x,y)为p邻域内已知像素点的坐标,则待修复区域内已知像素点个数最多为max Nqi,q∈φ(p),i∈(0,24).

(2)24邻域内已知像素点的曼哈顿距离权重和Sum(W)越大越优先被修复,如果权重和的值相等,则优先修复邻域内已知像素点个数少的像素点.在权重和相等的情况下,如果邻域内已知像素点个数越少,那么相对应的这些像素点的位置越靠近像素点p,对像素点p的贡献越大.像素点p与像素点q的曼哈顿距离d可表示为

式中,p为待修复像素点的坐标,q为已知像素点的坐标.对应于像素点p的24邻域内所有已知像素点的曼哈顿距离权重和为Sum(W),其中W是圆内25个像素点的权值矩阵,中心的“0”表示其本身的权值影响值,即待修复像素点受周围24个相关像素点的影响.对应的曼哈顿权值矩阵W的公式定义为

像素点p的曼哈顿距离权重和Sum(W)的公式定义为

(3)位于图像梯度变化剧烈的位置要优先被修复[11].换言之,法线与等值线方向的夹角θ越小,就越拥有较高的优先权.当像素点q在等照度线方向NP上时,g(p,q)=1,即方向向量与等照度线重合,此时g(p,q)最大,该已知像素点对待修复像素点的影响也最大.当像素点q离等照度线越远时,g(p,q)越小,则该像素点对待修复像素点的影响也越小.像素方向影响因子为

因此,构造综合影响因子z的公式为

综合二者得到边界上所有像素点的优先度之后,优先修复优先度最高的像素点.一般情况下,位于凸起区域的像素点优先于位于凹进区域的像素点,位于结构处的像素点优先于位于纹理处的像素点,位于拐点处的像素点优先于位于边缘处的像素点.

2.2 修复像素点p

根据式(2),待修复图像I上的像素点p也可以表示为

接着,由外向内扩散,用同样的方法依次修复每一个待修复像素点,并及时更新边界像素点及优先度值,重复操作,直到边界∂D=0为止.待所有的划痕都已被完全修复,保存并导出视频图像序列.同理,水平划痕修复算法的实现原理也一样.

2.3 算法描述

输入:待修复图像I,对应划痕掩膜图像M.

输出:修复后的图像IR.

步骤1 读入待修复的图像I及其划痕掩膜M.

步骤2 计算I的图像梯度gvalue及梯度方向gtheta

步骤3 根据M获取划痕区域所在的点集O与I的对照关系.

步骤4 根据对照关系求出点集O的邻域信息(具体的待修复像素点p的邻域已知像素点个数).

步骤5 根据优先原则确定当前要修复的划痕点p:第一优先原则,即24邻域内已知像素点个数越多的像素点越优先被修复;第二优先原则,即24邻域内已知像素点权重和越大的越优先被修复,权重和相等的情况下则优先修复邻域已知像素点个数较少的;第三优先原则,位于图像梯度变化剧烈的位置要优先被修复.

步骤6 修复划痕像素点p,并标记该像素点已被修复,即flag=1.

步骤7 更新对照关系,重复步骤(4)∼(6),直到划痕区域所在点集都被修复.

步骤8 返回修复结果IR.

3 实验结果与分析

本工作以Matlab为平台,运行环境为Intel 1.8 GHz处理器,4 GB内存.实验部分的视频素材取自2部不同影片的彩色视频序列.

3.1 修复效果对比

实验1:图2第1行的连续3帧序列图来源于《越剧西游》,像素大小为704×512,原画面中带有黑色水平、垂直划痕各一条,且划痕所在位置的背景比较单纯.

实验2:图2第2行的连续3帧序列图来源于《从奴隶到从军》,像素大小为720×480,原画面中带有白色水平、垂直划痕各一条,水平划痕所在背景比较单纯,垂直划痕所在背景比较复杂.

图2(d)分别对应实验1和实验2素材第2帧的掩膜图像,且掩膜图像中划痕所在像素点的个数分别为1 135和1 210.

图2 原损伤视频序列和掩膜图像Fig.2 Original damage video sequences and mask images

为了对比文献[1]、文献[2]、文献[3]和本算法的修复效果,以实验1和实验2素材第2帧为例,修复效果如图3所示.为了进一步观察受损图像的修复效果,局部放大实验1中八戒右肩头衣服与垂直划痕接壤的位置、实验2中复杂背景处的人脚与垂直划痕重合的位置,结果如图4所示.

由图3和4可见:对于划痕附近整体颜色比较单一的图像,文献[1]、文献[2]、文献[3]和本算法的修复效果都比较明显;对于背景相对复杂的图像,4种算法的优势和弊端存在差异.放大实验1和实验2框选出来的红色局部位置发现:两组图像中均存在深浅不一的修复痕迹,尤其是实验2.文献[1]算法不仅破坏了画面的结构性而且还产生了平滑效应,比如八戒右肩衣角处以及人脚、凳子和草坪的结合部分均出现了信息损失.文献[2]算法虽降低了平滑效应,但修复痕迹比较明显,比如在两组局部图像上都可以看出有少许残留的条形痕迹.文献[3]算法不仅修复不干净,而且修复的边缘有明显的阶梯效应,尤其在拐点对接处修复得特别粗糙,也十分影响观察者的视觉感受.用本算法修复的边缘线中间过渡都比较自然,虽也存在轻微的修复痕迹,但整体而言,较好地恢复了受损图像,保护了图像的纹理和结构信息.

图3 4种划痕修复算法的效果对比Fig.3 Eff ect comparisons of 4 kinds of scratch repair algorithms

图4 4种划痕修复算法的局部放大效果Fig.4 Local magnification effects of 4 kinds of scratch repair algorithms

为了突出本算法的实用性,本工作进行了如下的修复效果测试.如图5所示,在像素为538×307的原图上手工添加了各种方向的划痕直线.实验结果发现,文献[1]、文献[2]、文献[3]这3种算法根本无法修复这种复杂排列的划痕,而图5(c)是本算法修复的效果,能基本满足人类视觉上的要求.

图5 本算法的修复效果Fig.5 Repair effect of the algorithm

3.2 性能指标分析

目前,针对算法性能的分析有主观评价与客观评价两种方法.主观评价是由观察者直接用肉眼观察图像后打分所得,其优点是操作方式简单且结果的准确性、可信度很高,但是过分依赖于人眼,难以量化且比较耗时、繁琐.客观评价通过定义数学公式,并将这些公式量化后来衡量图像质量的好坏,其优点是成本低且易于实现,但是没有考虑人类的视觉特点.本工作结合了这二者的优点,从如下两个方面对各种算法的修复效果以及性能指标进行对比与分析.

3.2.1 主观评价

本工作邀请了40名观察者,分别针对4种算法修复前后的2组图像的“合理”和“完整”进行有效打分、评价.具体做法是先将修复前后的视频图像按一定规则交替播放给观察者,然后让观察者们自主打分,最后再计算所有分数的平均值作为该图像序列的评价值,具体数据如表1所示.可见,“平均分”栏数据显示出本算法的修复效果优于文献[2],文献[2]略优于文献[1],且文献[4]不适用于旧电影的划痕修复.

表1 4种划痕修复算法的主观评价结果比较Table 1 Comparisons of subjective evaluation results of 4 kinds of scratch repair algorithms

3.2.2 客观评价

为了检验本算法的性能,分别对4种算法修复前后视频的峰值信噪比(peak signal to noise ratio,PSNR)和结构相似性(structural similarity index,SSIM)值进行了对比分析,结果如表2所示.可见,修复后的视频质量较之前有了很大提高,且利用本算法修复的视频的PSNR和SSIM值均高于其他算法,所得图像也更接近原图像.

表2 4种划痕修复算法的客观评价结果比较Table 2 Comparisons of objective evaluation results of 4 kinds of scratch repair algorithms

另外,运行时间也是考量一个算法性能的重要条件.由表3可知:本算法的修复运行时间较文献[1]和文献[2]算法缩短了1/2,较文献[3]算法缩短了4 s左右,效率更高.

表3 4种划痕修复算法的运行时间比较Table 3 Comparisons of running time of 4 kinds of scratch repair algorithms s

综合显示,无论从主观评价还是客观评价,本算法的划痕修复效果均优于其他3种算法.

4 结束语

针对传统图像修复算法只利用待修复像素点的4邻域或8邻域信息进行修复的不足,本工作充分利用5×5邻域内的已知像素点,提出利用邻域像素点相关性的划痕修复算法.结果证明,本算法能较好地克服梯度效应、图像修复精度不高等问题,在主客观评价上均优于其他3种算法.当然本算法也存在一些缺陷,比如无法一次性修复多帧图片,在修复结构性很强或者背景较复杂的区域时,仍会出现一定的修复误差和模糊现象等,其中的部分原因是没有全面考虑综合因子.若在P z最大的时候确定优先被修复的像素点,则得到的修复效果会更优于本算法的效果.整体而言,本算法在旧电影、旧照片的划痕修复上有广泛的应用前景.