基于分組魯棒主成分分析的老電影修復

于冰,丁友東,董蓀,黃曦

(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