基于分组鲁棒主成分分析的老电影修复

于冰,丁友东,董荪,黄曦

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

•数字影视技术•

基于分组鲁棒主成分分析的老电影修复

于冰1,2,丁友东1,2,董荪1,2,黄曦1,2

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

以老电影视频为研究对象,针对序列中存在的多种损伤类别,提出一种基于分组鲁棒主成分分析(robust principal component analysis,RPCA)的统一修复方法.采用镜头分割和去闪烁实现对视频序列的预处理.在多分辨率金字塔框架下,采用时空域分组的方式在最粗糙层构造观测矩阵,依次执行基于交替线性法的RPCA变换后,根据帧间误差信息得到大面积破损位置;利用上采样方式构造初步修复结果序列、破损掩模序列以及最近邻偏移矩阵集合,继而对原始序列进行修改,重复时空域分组RPCA变换,实现对老电影视频序列的修复.实验结果证明,该方法能够同时修复画面中的不同损伤,并取得良好的效果.

老电影;视频修复;鲁棒主成分分析

电影胶片自诞生之日起已百年有余,经过长时间的存放,现存影片大多会出现不同程度的多种损伤,主要有颜色退化、画面闪烁、撕裂变形、划痕、斑块、脏点、颗粒噪声等视觉问题,亟需修复保护.数字视频去噪、修复、颜色校正等增强方法由于能够移除多余内容、恢复丢失信息、改善画面质量而被广泛用于老电影数字化修复[1].

经过数十年的研究,老电影的数字化修复技术取得了长足发展.Sadhar等[2]针对影片中的颗粒噪声,提出一种基于粒子滤波的退化图像恢复方法,利用时空上下文信息完成损伤序列的去噪.划痕的修复关键在于确定其在每帧画面中的位置,Gullu等[3]首先通过建立竖直方向的一维亮度特征模型确定划痕候选集合,然后利用制定的分块匹配策略剔除误检,最后结合优先权和亮度变换规则完成缺损修复.针对斑块的检测和修复,Ren等[4]结合时空域信息和区域增长实现位置标记,Ahmed等[5]将损伤序列看作是原始部分和污损部分的连续混合,并采用一种贝叶斯框架完成对画面中斑块的修复.随后,Elgharib等[6]运用半透明退化模型扩展了该框架,以同时去除竖直划痕和斑点两类破损.在老电影中,各种损伤的大小、位置、退化程度各异,而上述的修复方案往往只针对一种或两种损伤,对于每帧画面均需重复应用多种修复方案,这在很大程度上降低了工程实践效率.

近年来,鲁棒主成分分析(robust principal component analysis,RPCA)理论备受关注,已成功应用于视频背景建模[7]、人脸图像对齐[8]、光度立体重建[9]等计算机图形学和图像处理领域.RPCA衍生于压缩感知中的恢复技术,故又被称为低秩矩阵恢复(low-rank matrix recovery).该方法在满足误差稀疏性的假设下,旨在把一个矩阵分解为低秩矩阵部分和误差矩阵部分.

视频序列在时空域均存在较强的相关性和冗余性,这就为帧间联合修复提供了有利条件.基于块的非局部视频去噪[10]取得了卓有成效的成果,通过图像分块聚合分组的方式,在充分挖掘视频帧间和帧内相似性和冗余性的基础上,利用稀疏三维变换域协同滤波实现去噪.在相似框架下,Ji等[11]提出了一种联合稀疏和低秩矩阵近似的方法,通过分组求解核范数最小化问题,完成视频去噪和修复.该方法可以看作是文献[10]和文献[7]思想的综合,将视频中的每帧画面分块并按相似规则聚合后,每组的图像块修复问题实质上和文献[7]中的背景和前景分离问题是一致的,污损图像块的有效信息和损伤信息分别对应于视频中的静态背景和动态前景.在大多数情况下,如果把每一个图像块按列拉伸后组合成一个观测矩阵,则该矩阵可通过RPCA变换分解为低秩矩阵和稀疏矩阵[12],从而可实现损伤元素的位置检测和误差恢复同步进行.该方法在无需噪声和损伤类型假设的前提下,实现了老电影序列的有效修复,但仍存在如下问题：首先,由于该方法的块分组策略只是简单地将视频中各帧的相似块组合在一起,对于镜头中场景内容变换较大的序列,往往造成结果模糊;其次,对于斑块、脏点等损伤,该方法能修复的损伤面积往往取决于划分图像块的大小,无法保证全面的修复效果;再次,该方法中RPCA的求解方法采用了较为耗时的加速逼近梯度(accelerated proximal gradient,APG)算法[11],影响了算法的应用推广.

针对老电影破损特征以及上述修复方案的不足,本工作提出了一种基于分组鲁棒主成分分析的修复算法.本算法在基于块的多帧联合修复框架中加入大面积破损检测步骤,利用RPCA变换分解出的误差矩阵结合时空域信息定位破损区域位置;在修复过程中,引入交替线性法(alternating linearization method,ALM)对RPCA模型进行求解,实现低秩矩阵和误差矩阵的分离.相比传统的APG算法,本算法在时间效率和计算准确度方面均有提高.

1 算法框架

本工作设计的老电影修复算法主要分为3个处理阶段,总体框架如图1所示.首先,需要将整部电影按镜头划分为若干序列,为了避免分组误差,又需对镜头内的序列去闪烁.然后,在不同分辨率下进行检测和修复步骤.检测步骤用到的是金字塔的最粗糙层,通过分组RPCA变换的方式,输出低分辨率的修复序列和损伤序列,并结合时空域信息,筛选得到损伤掩模序列;修复步骤用到的是金字塔的最高层,而处理的对象是经过检测步骤输出结果修改后的视频序列,重复分组RPCA变换.最终通过分块聚合方式输出修复后的老电影序列.

图1 总体框架图Fig.1 Overall framework

2 算法描述

2.1 预处理

老电影视频包含多个场景,每个场景又包含多个镜头,而一个镜头表示内容上连续的视频片段,镜头内各帧存在显著的时间相关性.鉴于此,为了防止出现内容剧烈变化,本工作采用文献[13]中的方法将序列分割为多个镜头.因本工作采用基于块的分组方法,而块匹配对于图像的亮度变化反应敏感,故需在修复前对视频中存在的闪烁进行校正和消除.具体采用文献[14]中的颜色传递算法,通过选择参考帧并对其他帧分别作相对于参考帧的颜色传递,实现镜头内序列的闪烁消除.

2.2 块分组

对于有T帧的视频序列F={It}将其按空域分为若干有重叠的图像块,大小为N×N,用Pt(q)表示任意帧It中以像素q=(x,y)为左上角元素的矩形图像块.选定It中的任意块Pt(qR)为参考块.在这里,下标R∈X表示图像空间域中的一个坐标,集合X⊂Z2.那么,两个块之间的距离可以表示为

式中,距离D(·,·)是两图像块中像素平方差之和(sum of squared differences,SSD),u∈[0,N]×[0,N]是图像块大小范围内像素横纵坐标偏移,Υ表示自适应中值滤波操作[11],用来减少块匹配误差.如果D(Pt(qR),Pi(qj))是Ii所有块中相对于Pt(qR)距离最小的,则称Pi(qj)为Pt(qR)在帧Ii中的最近邻块,记为NN(Pt(qR),Pi(qj)).依此类推,目标是找到参考块在其他帧{I1,I2,…,It−1,It+1,…,IT}中的最近邻块,如果其他帧中的某个图像块满足条件

则将该图像块和Pt(qR)放在一起构成集合.式(2)中,下标i=1,2,…,t−1,t+1,…,T,阈值τ表示Pt(qR)与其他帧所有最近邻块距离从小到大排序后τ%位置的值.设置阈值τ是为了防止出现由于块之间相似度不高而造成结果中出现实际内容误消除.随后,对集合内的每个图像块向量化,并按顺序排列构成矩阵M,大小为m×n,这里,m为图像块中的元素数目,n为集合NtR中的元素数目.

如果用φ(Pt(qR),Pi(qj))=Pi(qj)−Pt(qR)表示参考块相对于其最近邻块的偏移量,可以看出搜索NN(·,·)等同于搜索φ(·,·),而所有偏移量的集合就构成了帧It相对于帧Ii的最近邻域(nearest neighbor field,NNF).为了提高计算速度,采用PatchMatch方法[15]求取近似最近邻域偏移.本算法是基于多帧联合的分组修复方法,故需计算参考帧相对于所有其他帧的最近邻域偏移集合,然后将该集合存放在一个三维矩阵中,用φt∈Rm×n×(T−1)表示,称作最近邻偏移矩阵.

2.3 鲁棒主成分分析

本工作采用RPCA变换从图像块中分离出稀疏误差,从而实现逐块修复的目的.模型假定原始矩阵结构良好(低秩),而且只有小部分元素被破坏,即误差是稀疏的.可以用以下优化模型来描述RPCA变换问题：

式中,M∈Rm×n是观测矩阵,A∈Rm×n是低秩矩阵,对应于视频块修复后的内容,E∈Rm×n是稀疏部分,对应于数据中的噪声、误差等.对核范数f(A)=∥A∥∗和ℓ1范数g(E)= ρ∥E∥1利用Nesterov平滑技术[16]进行处理得到两个平滑函数,分别用fσ(A)和gσ(E)表示,σ> 0表示平滑参数.而fσ(A)和gσ(E)的最优解Wσ(A)和Zσ(E)[17]为

式中,U Diag(γ)VT是A/σ的奇异值分解.这样就把式(3)转化为以下平滑问题：

本工作采用交替线性法[17]对上述约束问题进行求解,由于同时极小化A和E较为困难,因此采用交替迭代的策略.首先,初始化惩罚参数µ,在第k+1次迭代时,Ak+1和Ek+1分别可以表示为

2.4 大面积损伤检测

通过对老电影的损伤特征进行分析,可以发现画面损伤呈现出大小不定性,有些帧中会出现大面积的损伤,如果只使用文献[11]的修复框架,往往会因为若干包含在破损区域内部的图像块无法正确找到匹配块而造成错误修复结果.因此,本工作在修复前加入了大面积损伤检测步骤.对视频序列F={It}下采样构造一组金字塔,第1层为原始图像层,第L层为最粗糙层.第L层的序列用FL={表示,检测步骤对该层视频进行操作.首先,选定ItL为参考帧,采用按块分组的方式构造观测矩阵,对每一组观测矩阵依次执行RPCA变换,实现低秩矩阵和误差矩阵的分离;然后,对每组中的低秩矩阵和误差矩阵分别反变换为修复块组和误差块组,并按记录的坐标放置到原始位置.由于本工作是按可重叠图像块划分的,因此采用相加取平均的聚合方式得到每个坐标位置的像素值.最终得到两个视频序列,分别是修复序列其中误差序列包含了影片中的破损部分和由于目标运动、误匹配等原因造成的冗余误差.

分析大面积破损区域的特点可以发现,如果某帧有损伤,则其前后同一位置往往并不存在破损.据此,先通过选定的阈值对参考帧及其前后帧进行二值化,得到的二值图像分别表示为然后计算参考帧的初始破损掩模,式中,(x,y)表示参考帧中坐标(x,y)处的初始掩模图像值.在此之后,通过形态学膨胀和腐蚀运算,连接临近封闭区域、平滑边界、去除细小区域,得到参考帧最终破损掩模图像,记为.对视频序列中的每帧图像重复执行此过程,得到集合并在执行的同时记录各帧最近邻偏移矩阵,从而形成集合

在完成最粗糙层的分组RPCA变换后,采用最近邻插值的上采样方法得到金字塔最高分辨率层的修复序列最近邻域偏移矩阵集合至此完成了检测步骤的执行.

2.5 视频序列修复

本算法的修复阶段同样是应用检测步骤的分组修复方式,对输入的视频序列选定It为参考帧,计算其最近邻偏移矩阵ϕt,这样就可以结合由检测步骤得出的破损掩模,实现对参考帧的修改.具体方式如下：

式中,It,m表示被修改后的参考帧.然后,还需对最近邻域偏移矩阵进行修改,

式中,ϕt,m表示被修改后的最近邻偏移矩阵.在修复步骤中执行如上修改操作,主要是针对画面中存在的大面积破损的视频序列进行修复.这样,一旦某帧中出现大的损伤区域,在块分组构造观测矩阵后,通过以上方式修改后的帧在执行RPCA变换时,由于保证了每列均被采用,就会避免矩阵无法有效低秩分解的情况出现.图2是利用破损掩模修改参考帧的示例,可以看出通过修改操作,破损区域中被填充了部分采样信息.

图2 参考帧修改过程Fig.2 Reference frame modification process

利用本工作提出的基于关键帧的分组修复方法,通过遍历参考帧空间域所有重叠图像块,完成一帧的修复,这样依次进行,直到完成对所有时间域各帧的遍历.在完成第一个参考帧的修复后,其他帧只有少部分块未被匹配,未实现分解.本工作把每一帧均作为关键帧,但除第一个关键帧外,对以后关键帧中的图像块设置了是否已被修复的标志;对已被修复的块,在接下来的循环操作中,不作RPCA变换,这样就在最大程度节省算法执行时间的前提下实现了老电影序列多帧联合修复.

3 实验结果分析

为了验证所提出算法的可行性,针对老电影中常见损伤的修复问题进行仿真实验,并分别与其他算法的修复效果进行对比.采用Matlab 2012a作为编程工具,实验环境为Intel Xeon 2.9 GHz处理器以及16 GB内存的计算机.本工作对合成的降质视频序列和真实老电影序列分别进行了实验验证,合成数据选用标准视频序列“foreman”和“mother-daughter”,大小均为288×352像素,视频帧数均为T=50,并添加混合噪声和人为损伤;真实数据选用有代表性的黑白和彩色老电影《马路天使》和《孙悟空三打白骨精》中的某个镜头,分辨率分别为720×576和704×512像素,镜头中视频帧数分别为T=100和24.以上实验数据均来自互联网.

对合成数据进行实验,并采用峰值信噪比(peak signal to noise ratio,PSNR)作为修复效果的评价指标.本算法设置遍历空间域图像块的采样步长为s_r=4,块大小为p_s=32×32,阈值τ为90%.图3显示了采用不同算法对“foreman”序列中某一帧的修复结果,合成帧是由图3(b)中的损伤掩模、σ=10的高斯噪声、s=20的椒盐噪声混合而成.可以看出,文献[10]的算法虽然能在一定程度上改善画面质量,但并不能实现损伤修复,而本算法结果与文献[11]的修复效果相当.图4显示了采用3种算法修复大面积损伤的结果,合成帧是由图4(b)中的损伤掩模、σ=5的高斯噪声、s=10的椒盐噪声混合而成.可见,文献[11]的算法由于未考虑损伤的大小,而只使用固定大小的划分图像块方式,不能有效实现破损区域的块匹配,从而造成如图4(e)所示的“块效应”修复结果,而本算法则能够有效实现修复.表1列出了在使用相同掩模和不同噪声强度的情况下,不同算法在两个视频帧上的PSNR值,可见本算法优于文献[10]和[11]的算法.

图3 “foreman”的修复实验结果Fig.3 Experimental results of“foreman”

图4 “mother-daughter”的修复实验结果Fig.4 Experimental results of“mother-daughter”

表1 不同算法的PSNR值Table 1 PSNR values of different algorithms

对两组真实影片镜头进行实验,采用不同的参数设定.对于黑白老电影视频序列,采用本算法遍历空间域图像块的采样步长设置为s r=16,块大小为ps=32×32,阈值τ为50%, RPCA变换迭代次数为30.图5显示了两种算法在序列同一帧上的修复结果,可以看出,原始帧中存在颗粒噪声、斑点、划痕等多种损伤,采用基于分组RPCA变换的方法能够很好地完成画面修复.而同等参数设置下文献[11]的算法虽然完成了损伤去除,但存在模糊和过修复现象,一方面是因为基于APG的RPCA变换在迭代次数较少的情况下会产生较大的分解误差,另一方面是由于分组规则中未设置阈值而产生聚合模糊后果.对于彩色老电影视频序列,采用本算法遍历空间域图像块的采样步长设置为sr=4,块大小为ps=32×32,阈值τ为100%, RPCA变换迭代次数为50.图6显示了两种算法的修复结果,可以看出,虽然文献[11]的算法能有效解决划痕、脏点等问题,但明显的大面积斑块依然存在;而本算法在借助检测步骤生成的有效辅助数据基础上,实现了画面的有效修复.

表2是文献[11]的算法和本算法的执行时间比较.可见,本算法基于交替线性法的RPCA变换拥有较快的收敛速度,故在迭代次数较少的情况下,即可实现较好的修复效果.另外,通过引入PatchMatch近似最近邻分组方法,本算法还克服了文献[11]中三步分级搜索(three step search,TSS)算法块匹配耗时多的缺点.所以,本算法在不同参数设定情况下的时间效率均较文献[11]算法有明显提高.

图5 黑白老电影的修复实验结果Fig.5 Experimental results of the black-white vintage film

图6 彩色老电影的修复实验结果Fig.6 Experimental results of the colour vintage with

表2 不同算法执行时间比较Table 2 Comparison of execution time of different algorithms

4 结束语

本工作提出了一种基于分组鲁棒主成分分析的老电影修复方法,将视频修复问题转化为时空域的分块RPCA变换问题,通过基于迭代线性求解的方式,实现了修复序列和误差序列的分离;同时,考虑到画面中的损伤分布大小不一的特点,设计了一种先检测后修复的框架,较好地完成了对不同损伤类型视频的修复.在未来的工作中,将重点研究更加快速的RPCA求解算法和鲁棒性更强的破损区域检测方法,从而实现对老电影的高效准确修复.

[1]Simone C,Tunc O A,Nikolce S,et al.Advanced tools and framework for historical film restoration[J].Journal of Electronic Imaging,2017,26(1)：11-21.

[2]Sadhar S I,Rajagopalan A N.Image estimation in film-grain noise[J].IEEE Signal Processing Letters,2005,12(3)：238-241.

[3]Gullu M K,Urhan O,Erturk S.Scratch detection via temporal coherency analysis and removal using edge priority based interpolation[C]//IEEE International Symposium on Circuits and Systems.2006：1-4.

[4]Ren J,Vlachos T.Efficient detection of temporally impulsive dirt impairments in archived films[J].Signal Processing,2007,87(3)：541-551.

[5]Ahmed M A,Pitie F,Kokaram A C.Extraction of non-binary blotch mattes[C]//IEEE International Conference on Image Processing.2009：2757-2760.

[6]Elgharib M A,Pitie F,Kokaram A.Blotch and scratch removal in archived film using a semi-transparent corruption model and a ground-truth generation technique[J].Current Opinion in Hematology,2013,2013(11)：1-20.

[7]Bouwmans T,Zahzah E H.Robust PCA via principal component pursuit：a review for a comparative evaluation in video surveillance[J].Computer Vision&Image Understanding, 2014,122(4)：22-34.

[8]Wu K K,Wang L,Soong F K,et al.A sparse and low-rank approach to efficient face alignment for photo-real talking head synthesis[C]//IEEE International Conference on Acoustics.2011： 1397-1400.

[9]Wu L,Ganesh A,Shi B,et al.Robust photometric stereo via low-rank matrix completion and recovery[C]//Computer Vision—ACCV 2010.2010：703-717.

[10]Dabov K,Foi A,Egiazarian K.Video denoising by sparse 3D transform-domain collaborative filtering[C]//Signal Processing Conference.2007：145-149.

[11]Ji H,Huang S,Shen Z,et al.Robust video restoration by joint sparse and low rank matrix approximation[J].SIAM Journal on Imaging Sciences,2011,4(4)：1122-1142.

[12]Wright J,Ganesh A,Rao S,et al.Robust principal component analysis：exact recovery of corrupted low-rank matrices via convex optimization[C]//23rd Annual Conference on Neural Information Processing Systems.2009：20-56.

[13]Adjeroh D A,Lee M C.Scene-adaptive transform domain video partitioning[J].IEEE Transactions on Multimedia,2004,6(1)：58-69.

[14]Hacohen Y,Shechtman E,Dan B G,et al.Non-rigid dense correspondence with applications for image enhancement[J].ACM Transactions on Graphics,2011,30(4)：70-79.

[15]Barnes C,Shechtman E,Finkelstein A,et al.PatchMatch：a randomized correspondence algorithm for structural image editing[J].ACM Transactions on Graphics,2009,28(3)：24-33.

[16]Nesterov Y.Smooth minimization of non-smooth functions[J].Mathematical Programming, 2005,103(1)：127-152.

[17]Goldfarb D,Ma S,Scheinberg K.Fast alternating linearization methods for minimizing the sum of two convex functions[J].Mathematical Programming,2013,141(1)：349-382.本文彩色版可登陆本刊网站查询：http：//www.journal.shu.edu.cn

Group-based vintage film inpainting using robust principal component analysis

YU Bing1,2,DING Youdong1,2,DONG Sun1,2,HUANG Xi1,2
(1.Shanghai Film Academy,Shanghai University,Shanghai 200072,China; 2.Shanghai Engineering Research Center of Motion Picture Special Effects,Shanghai University, Shanghai 200072,China)

In this paper,a new group-based method using robust principal component analysis(RPCA)is proposed to deal with multiple categories of damage in vintage film sequences.Pre-processing of the video sequence is achieved by shot segmentation and flicker elimination.In a framework of multi-resolution pyramid,an observation matrix is constructed on the coarsest level by space-time domain grouping.After performing RPCA transform based on the alternating linear method in sequence,locations of large area damage are obtained based on inter-frame error information.An initial inpainting result sequence,a break mask sequence,and a nearest neighbor offset matrix set using an upsampling method are constructed.The original sequence is then modified.By repeating the space-time grouping RPCA transform,inpainting of the vintage film sequence is realized.Experimental results show that the method can simultaneously repair differentdamages in the screen with good performance.

vintage film;video inpainting;robust principal component analysis(RPCA)

TP 391.41

A

1007-2861(2017)03-0315-09

10.12066/j.issn.1007-2861.1923

2017-03-17

国家自然科学基金资助项目(61402278);上海市自然科学基金资助项目(14ZR1415800);上海大学电影学高峰学科和上海电影特效工程技术研究中心资助项目(16dz2251300);上海市科委科技攻关资助项目(16511101302)

丁友东(1967—),男,教授,博士生导师,博士,研究方向为计算机图形学、数字影视动技术. E-mail：ydding@shu.edu.cn