膠片電影中的快速斑塊修復(fù)算法研究

劉泉洋，劉云清，史俊，顏飛，張瓊

（長春理工大學(xué) 電子信息工程學(xué)院，長春 130022）

電影視頻檔案作為一種重要的信息記錄方式，記錄一個國家的社會歷史、政治、經(jīng)濟等各方面的重要事件，目前僅中國電影資料館就保存了近3萬部影像資料。早期的拍攝設(shè)備限制，大多數(shù)影片檔案以膠片的形式進行存儲，膠片在恒溫恒濕等特定條件下，其影像可以完好的保存百年以上。但現(xiàn)實并不能盡如人意，由于年代久遠，保存條件不夠理想或者轉(zhuǎn)印、播放次數(shù)過多等原因，電影膠片存在著灰塵、污垢、斑塊、掉色、圖像抖動、劃傷、閃爍、噪聲、變色、模糊［1］等各種問題。造成斑塊損傷的原因有很多，使得斑塊出現(xiàn)頻率最高，對視覺的影響較大，所以斑塊修復(fù)十分重要。斑塊屬于單幀突發(fā)性視頻失真，其特征主要表現(xiàn)有兩點：一是斑塊只存在于單幀圖像中，無前后幀信息關(guān)聯(lián)；二是斑塊的形狀不規(guī)則，出現(xiàn)的位置具有隨機性。針對上述斑塊的特征，很多學(xué)者提出了解決斑塊問題的優(yōu)秀算法。這些算法的修復(fù)質(zhì)量較好，但視頻修復(fù)時間較長。由于視頻修復(fù)需要處理的數(shù)據(jù)量十分龐大，為了進一步提高膠片電影中斑塊修復(fù)的速度，本文提出一種快速斑塊檢測與修復(fù)算法，該方法通過優(yōu)化斑塊檢測算法中的運動估計模型，簡化斑塊修復(fù)模型，提升斑塊檢測與修復(fù)的整體速度。

1 相關(guān)工作

1.1 斑塊檢測算法

斑塊的數(shù)學(xué)模型可表示為：

其中，向量i表征像素點空間坐標(biāo)；x(i)表示原圖像；z(i)是加入斑塊后的圖像；d(i)∈{0，1}：0表示該點沒有被斑塊覆蓋，1表示已被斑塊覆蓋；y(i)表示被斑塊覆蓋的區(qū)域。

常見的斑塊檢測算法有SDI（Spike Detection Index）檢 測 器［2］、ROD（Rank Ordered Difference）檢測器［3］、MRF（Markov Random Filed）檢測器［3］、AR（Autoregression）檢測器［3］等。SDI算法利用了斑塊在相鄰三幀間的不連續(xù)性來進行檢測。ROD檢測器首對參考幀進行運動補償，然后在參考幀各選取若干像素進行排序；最后進行多閾值判斷，類似于自適應(yīng)中心加權(quán)濾波器中的脈沖噪聲檢測部分的算法，ROD容易受到噪聲干擾。MRF模型由kokaram提出，其核心思想是最大化在前后參考幀圖像和當(dāng)前幀圖像觀測條件下掩膜函數(shù)的概率，MRF模型較為復(fù)雜，所以其計算復(fù)雜度較高。AR檢測器基本原理是根據(jù)當(dāng)前幀的圖像可由運動補償后的前向參考幀和后向參考幀來預(yù)測。上述檢測算法大多是先對圖像序列進行運動補償，再與參考幀做差值，對差值設(shè)置特定的閾值，生成掩模圖像。斑塊檢測算法除了MRF檢測器模型過于復(fù)雜，其他檢測算法耗時最多的部分的運動估計部分，因此，快速斑塊檢測算法的關(guān)鍵在于對運動估計模型的優(yōu)化。

圖1表示的是斑塊檢測算法簡化模型。首先對圖像序列進行運動估計，求出運動矢量后對圖像序列進行運動補償，對運動補償后的圖像與參考幀做差值處理，再對差值圖像做閾值分割處理，得出斑塊掩模圖像。

圖1 檢測器模型圖

上述模型的運動估計部分是整個模型的關(guān)鍵部分，也是耗時較多的部分。由于塊匹配算法（Block Matching Algorithm，BMA）在計算處理和硬件實現(xiàn)上較為容易［4］，使其成為運動估計算法中應(yīng)用最廣泛算法，被許多視頻壓縮編碼標(biāo)準所采用，如 H.261/3/4 和 MPEG-2/4［5］。

塊匹配算法采用為二維宏塊搜索匹配運動矢量最優(yōu)值［6］。對于全局運動估計的搜索，完整二維宏塊存在大量的信息冗余，會增大搜索匹配過程中的計算量，很難通過優(yōu)化搜索策略和宏塊位置等方法大幅度提升算法運算速度。

1.2 一維塊匹配運動估計算法

為了進一步提高算法的速度，降低算法實現(xiàn)的復(fù)雜度，本文提出了一維塊匹配運動估計算法（One-dimensional block matching algorithm，OB?MA）。

（1）一維特征矩陣

通過對運動矢量的特點進行分析，運動矢量精度是單位像素，方向和大小均不確定。因此本文采用先對運動矢量正交分解，分解為兩個分矢量。如圖2所示，其中運動矢量MV的分量x為水平方向和分量y為垂直方向。

圖2 運動矢量分解圖

求解運動矢量分量x和運動矢量分量y需要使用一維特征矩陣X和一維特征矩陣Y，一維特征矩陣求解過程如下：

其中，A和B為權(quán)重系數(shù)矩陣；λ為權(quán)重系數(shù)矩陣A的權(quán)重系數(shù)；μ為權(quán)重系數(shù)矩陣B的權(quán)重系數(shù)，權(quán)重系數(shù)為設(shè)定值，本文設(shè)置的值為灰度級的倒數(shù)；P為匹配宏塊矩陣，形狀為（n，m），特征矩陣X的形狀為（1，m）；PT為矩陣P的轉(zhuǎn)置矩陣，形狀為（m，n），特征矩陣Y的形狀為（1，n）。

（2）一維三步搜索法

相比于全搜索法（Full Search，F(xiàn)S）要遍歷搜索區(qū)域所有像素點，三步搜索法的搜索點數(shù)大幅減少［7］。有別于全搜索法逐一遍歷所有像素點，三步搜索法每一步搜索是搜索邊界上的8個點以及正方形的中心點共9個搜索點進行比較，根據(jù)匹配準則得出最佳匹配點，搜索步長等于或者略大于最大搜索范圍的一半。上一步比較得到的最佳匹配點作為下一個新的搜索步的搜索中心。當(dāng)搜索范圍大于7時，搜索步數(shù)大于3步。三步搜索法的搜索方式如圖3所示，其中圓形為第一步搜索點，方形為第二步搜索點，三角形為第三步搜索點。

圖3 三步搜索法

本文的特征矩陣X和特征矩陣Y是一維矩陣，因此需要將二維三步搜索法改為一維三步搜索法（One-dimensional Three Step Search，OTSS）。一維三步搜索法的搜索步驟與三步搜索法類似，每步搜索對搜索邊界上的2個點以及中心點共3個搜索點進行比較，本文匹配準則使用最小絕對誤差和準則（SAD），搜索步長等于或者略大于最大搜索范圍的一半。上一步比較后得到的最優(yōu)匹配點，作為下一步新的搜索中心。一維三步搜索法如圖4所示，其中圓形為第一步搜索點，方形為第二步搜索點，三角形為第三步搜索點，橫軸表示水平或垂直方向的像素坐標(biāo)。

圖4 一維三步搜索法

一維塊匹配算法步驟如下：

（1）首先讀取當(dāng)前幀圖像和前一幀圖像，提取當(dāng)前幀圖像是匹配宏塊區(qū)域，使用權(quán)重系數(shù)矩陣求出匹配宏塊的特征矩陣X和特征矩陣Y。

（2）提取前一幀圖像匹配宏塊的最大可能出現(xiàn)區(qū)域，使用權(quán)重系數(shù)矩陣求出最大可能出現(xiàn)區(qū)域的特征矩陣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最優(yōu)值。

（4）最后將運動矢量分量最優(yōu)值組合為完整運動矢量MV。

1.3 斑塊修復(fù)算法

斑塊的修復(fù)過程實質(zhì)上尋找合適的像素信息填入斑塊區(qū)域的插值過程。最簡單的方法是直接使用參考幀中相同位置的像素內(nèi)容去代換當(dāng)前幀中斑塊遮蓋的內(nèi)容，而這種方法顯然只能使用在靜態(tài)圖像序列中，動態(tài)圖像序列修復(fù)效果較差［8］。在此基礎(chǔ)上是加入運動補償?shù)膸g預(yù)測方法，對運動圖像序列修復(fù)有較好的效果。

常見的斑塊修復(fù)算法有MRF插值算法［2］、3D AR插值算法［3］、多級中值濾波器插值算法（Multistage Median Filter，MMF）［4］、空間插值算法［4］、控制粘貼算法［4］。MRF 插值算法的核心思想是在前后幀圖像和當(dāng)前幀圖像的觀測條件下尋找斑塊區(qū)域的最大后驗估計?？臻g插值算法是利用視頻信號在空間上存在的相關(guān)性，使用幀內(nèi)相鄰的原始圖像像素來重構(gòu)搜索區(qū)域的圖像數(shù)據(jù)。3D插值算法利用了當(dāng)前幀與前后幀之間在時間上的相關(guān)性，對當(dāng)前幀的像素進行基于相鄰若干幀對應(yīng)點的線性合并，使之獲得最佳預(yù)測結(jié)果。MMF算法采用中值濾波器理論，當(dāng)前幀的某個點進行多次中值濾波處理?？刂普迟N算法是一種簡化的AR模型，對于當(dāng)前幀的某一需要修復(fù)的像素，該算法僅從參考前幀和參考后幀提取相應(yīng)的點粘貼到當(dāng)前像素位置，對比前一幀和后一幀的哪個更合適被用來填補，這可以被看作是一步AR插值法。上述修復(fù)算法是在檢測模型生成掩模圖像后，根據(jù)前后幀信息修復(fù)斑塊區(qū)域。由于膠片電影拍攝設(shè)備的限制，導(dǎo)致其清晰度較低，所以對修復(fù)算法的精度要求不高，即使采用直接填補法，也可以達到很好的修復(fù)效果，同時提高修復(fù)算法的速度。

1.4 基于運動補償?shù)膯螀⒖紟迯?fù)算法

根據(jù)視頻圖像序列的特點，當(dāng)視頻畫面幀非場景切換幀時，人眼觀察到的斑塊是本幀畫面與前一幀畫面像素信息發(fā)生突變導(dǎo)致，所以本算法省略了控制粘貼法對后一幀信息的使用，只使用前一幀畫面作為參考幀。當(dāng)視頻畫面幀是場景切換幀時，只使用后一幀畫面作為參考幀。本文使用的斑塊修復(fù)算法入式：

其中，zmc為z加入運動補償后的圖像；f是場景切換標(biāo)識位，0表示非場景切換幀，1表示場景切換幀。

2 算法流程

本算法將視頻幀序列分為場景切換幀和非場景切換幀，場景切換幀的修復(fù)使用的參考幀為當(dāng)前幀的后一幀圖像，非場景切換幀修復(fù)使用的參考幀為當(dāng)前幀的前一幀圖像。整體算法可分為三步：首先根據(jù)參考幀求出當(dāng)前幀的運動矢量；然后對當(dāng)前幀圖像進行運動補償，與參考幀做差值圖像，設(shè)定閾值求出斑塊掩模圖像；最后根據(jù)掩模圖像利用參考幀信息修復(fù)當(dāng)前幀圖像?？焖侔邏K檢測與修復(fù)算法流程圖如圖5所示。

圖5 算法流程圖

3 實驗結(jié)果

為了驗證本文提出的快速斑塊檢測與修復(fù)算法的性能，分別從主觀和客觀兩方面分析本文提出的算法與改進前算法。改進前算法中的運動估計模塊為傳統(tǒng)的二維塊匹配算法；修復(fù)模塊為控制粘貼算法，控制粘貼算法中的前后幀判別依據(jù)選擇峰值信噪比。本文提出的快速斑塊檢測與修復(fù)算法的運動估計模塊選擇一維塊匹配算法；修復(fù)模塊為基于運動補償?shù)膮⒖紟迯?fù)算法。

3.1 實驗平臺

本文進行實驗的計算機配置為AMD Ryzen5 2600 CPU（3.40 GHz），內(nèi)存為16 GB；操作系統(tǒng)為Window10；編程環(huán)境為python3.6。

3.2 算法性能主觀評價

為了直觀對比本文提出的一維塊匹配算法與二維塊匹配算法的實際效果，選取測試視頻圖像序列中兩個不同場景，將未加入運動補償?shù)那昂髱钪祱D像與加入運動補償后的前后幀差值圖像進行對比?？紤]到差值圖像對比度較低，為了提高差值圖像的對比度，對樣本的結(jié)果做直方圖均衡化處理，最后得到對比度增強后的差值圖像，如圖 6、圖 7所示。圖 6（a）、圖 7（a）是未加入運動補償后，與前一幀參考幀的差值圖像；圖6（b）、圖 7（b）為加入運動補償后，與前一幀參考幀的差值圖像，運動估計算法為二維塊匹配算法；圖 6（c）、圖 7（c）為加入運動補償后，與前一幀參考幀的差值圖像。

通過圖6、圖7中2個不同場景下運動補償后的差值圖像對比分析，本文提出的運動估計算法的實際補償效果與傳統(tǒng)塊匹配法基本一致。

圖6 場景一前后幀差值圖像

圖7 場景二前后幀差值圖像

圖8、圖9和圖10為兩種算法在不同場景下的帶斑塊圖像修復(fù)效果，其中圖 8（a）、圖 9（a）和圖 10（a）為未修復(fù)的原始圖像，圖 8（b）、圖 9（b）和圖10（b）為改進前修復(fù)算法的修復(fù)效果，圖8（c）、圖9（c）和圖10（c）為改進算法的修復(fù)效果。

從主觀角度對比圖8、圖9、圖10中不同場景下斑塊修復(fù)算法的修復(fù)效果，改進后的算法修復(fù)效果與改進前算法修復(fù)效果基本一致。

圖8 場景一斑塊修復(fù)效果

圖9 場景二斑塊修復(fù)效果

圖10 場景三斑塊修復(fù)效果

3.3 算法性能客觀指標(biāo)

測試樣本選擇連續(xù)50幀視頻圖像序列，客觀指標(biāo)參數(shù)選擇算法的運行時間。如圖11所示，其中圖11（a）為運動估計模塊運行時間，圖11（b）為修復(fù)模塊運行時間，圖 11（c）為完整修復(fù)算法運行時間。

根據(jù)圖11（a）和表1中的運動估計平均時間可以看出，一維匹配運動估計算法運行時間少于二維塊匹配算法；根據(jù)圖11（b）和表1的修復(fù)模塊平均運行時間可以看出，本文提出單參考幀的修復(fù)算法運行時間少于傳統(tǒng)雙參考幀修復(fù)算法；根據(jù)圖11（c）和表1的完整算法平均運行時間可以看出，本文提出快速斑塊修復(fù)算法運行時間少于傳統(tǒng)斑塊修復(fù)算法。

圖11 運行時間

表1 改進前算法與改進后算法在連續(xù)50幀視頻序列平均運行時間/ms

通過以上數(shù)據(jù)分析，本文提出快速斑塊修復(fù)算法的運動估計模塊、修復(fù)模塊和算法整體的運行時間均少于傳統(tǒng)斑塊修復(fù)算法。由于膠片電影數(shù)字化后龐大的數(shù)據(jù)量，以及膠片電影中斑塊問題的普遍性，傳統(tǒng)修復(fù)算法面對龐大的數(shù)據(jù)量勢必會花費大量的時間，使用本文提出快速斑塊修復(fù)算法可以有效地解決此問題。

4 結(jié)論

傳統(tǒng)的斑塊修復(fù)算法依然停留在直接使用二維信息計算運動估計，使用前后幀作為參考幀修復(fù)斑塊。本文通過對膠片視頻與斑塊特點的研究，發(fā)現(xiàn)二維宏塊經(jīng)過權(quán)重系數(shù)矩陣降維后的一維特征矩陣具備二維矩陣的部分特征，使用一維特征矩陣代替二維矩陣進行運動估計，可以有效地提高運動估計模塊的效率；使用單參考幀修復(fù)斑塊，可以滿足膠片電影對清晰度的要求下，提高修復(fù)速度。本文提出的斑塊修復(fù)算法將一維塊匹配運動算法代替二維塊匹配運動算法，將單參考幀的斑塊修復(fù)算法代替雙參考幀的斑塊修復(fù)算法。實驗結(jié)果表明：本文提出的快速斑塊修復(fù)算法的速度比改進前的傳統(tǒng)算法快。下一步的研究方向是分析膠片電影中的劃痕問題，提高劃痕的修復(fù)效果和修復(fù)速度。