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

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

（長春理工大學 電子信息工程學院，長春 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 結論

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