基于5×5鄰域像素點(diǎn)相關(guān)性的劃痕修復(fù)算法

徐 敏, 丁友東, 于 冰, 李 暢, 吳 彪, 張婉瑩

(1.上海大學(xué)上海電影學(xué)院,上海200072;2.上海大學(xué)上海電影特效工程技術(shù)研究中心,上海200072)

劃痕是舊電影、舊照片中比較常見(jiàn)的一種畫(huà)面損傷.由于年代久遠(yuǎn)、存放的技術(shù)條件有限、多次轉(zhuǎn)印播放以及膠片本身老化等原因,會(huì)造成影片在前后幀幾乎相同的位置持續(xù)出現(xiàn)不同長(zhǎng)度和寬度的劃痕.如果不及時(shí)對(duì)其進(jìn)行修復(fù)整理,破損區(qū)域還會(huì)繼續(xù)擴(kuò)散,甚至禍及畫(huà)面中的其他地方.手工修復(fù)對(duì)修圖師自身的技術(shù)水平要求很高,消耗時(shí)間也長(zhǎng),因此尋求高效的數(shù)字圖像修復(fù)算法很有現(xiàn)實(shí)意義.已有的劃痕修復(fù)算法大致分為空間插值[1]、小波域修復(fù)[2]、改進(jìn)的圖像修補(bǔ)算法[3-4]3種,且都趨向于幀內(nèi)修復(fù).在修復(fù)較長(zhǎng)較寬的劃痕時(shí),這些算法容易產(chǎn)生模糊、假邊緣和階梯效應(yīng),且難于理解和實(shí)現(xiàn)[5].一般來(lái)說(shuō),劃痕兩端的距離較遠(yuǎn)、相關(guān)性較弱,并且劃痕兩側(cè)存在余弦衰減區(qū)域,待修復(fù)區(qū)域鄰域一層像素點(diǎn)會(huì)存在噪聲和游離的衰減區(qū)域點(diǎn)或跳變點(diǎn)[6].如果僅僅通過(guò)傳統(tǒng)的4鄰域或8鄰域中的相關(guān)像素點(diǎn)來(lái)修復(fù),肯定會(huì)產(chǎn)生錯(cuò)誤積累,出現(xiàn)劃痕修復(fù)不徹底和模糊現(xiàn)象.本工作改進(jìn)了傳統(tǒng)圖像修補(bǔ)算法,并將其應(yīng)用到舊的影視資料的劃痕修復(fù)中.本工作的主要思想是利用待修復(fù)區(qū)域與周圍24個(gè)鄰近像素點(diǎn)的相關(guān)性,通過(guò)定義劃痕邊界待修復(fù)像素點(diǎn)的優(yōu)先度來(lái)確定填充順序;并結(jié)合圖像本身的結(jié)構(gòu)特征,依次修復(fù)每一個(gè)像素點(diǎn)并及時(shí)更新此像素點(diǎn)及其附近邊界像素點(diǎn)的優(yōu)先度,重復(fù)操作直至待修復(fù)區(qū)域像素點(diǎn)的個(gè)數(shù)為0.

1 劃痕修復(fù)問(wèn)題的數(shù)學(xué)描述

劃痕修復(fù)是一個(gè)病態(tài)問(wèn)題,即不可能將一幅圖像完全修復(fù)到出現(xiàn)劃痕損壞之前的狀態(tài).在實(shí)際應(yīng)用中,只能利用圖像中未被損壞的信息,按照一定原則去修復(fù)劃痕所在區(qū)域.劃痕修復(fù)實(shí)際上是不可逆的,但可以通過(guò)一些技術(shù)手段使修復(fù)后的劃痕所在區(qū)域與原圖近似相等.對(duì)于帶有劃痕的圖像I,其像素點(diǎn)可以分為兩類:一類是完整正常的區(qū)域ID;另一類是劃痕所在區(qū)域IS.舊電影膠片上出現(xiàn)的劃痕大多為水平劃痕和垂直劃痕兩種,寬度為3～10個(gè)像素,傾斜角小于5?,劃痕處的灰度值與相鄰行或列的灰度值的差值絕對(duì)值在5～30之間,且經(jīng)常出現(xiàn)在亮或暗的地方[7].記描述劃痕的掩膜圖像為M,是一個(gè)二值圖像,標(biāo)記待修復(fù)區(qū)域?yàn)?,已知區(qū)域?yàn)?,則對(duì)應(yīng)的像素點(diǎn)S的公式可表示為

一般情況下,待修復(fù)像素點(diǎn)與鄰域已知像素點(diǎn)的分布情況以及紋理結(jié)構(gòu)信息高度相關(guān)[8].首先,鄰域已知像素點(diǎn)的分布可以從兩個(gè)維度去描述:已知像素點(diǎn)的個(gè)數(shù)、已知像素點(diǎn)離待修復(fù)像素點(diǎn)的距離.從信息論角度考慮,待修復(fù)像素點(diǎn)的信息能夠由鄰域內(nèi)已知像素點(diǎn)提供,越靠近待修復(fù)像素點(diǎn)的鄰域像素點(diǎn)能提供的信息量越大.如果兩個(gè)待修復(fù)像素點(diǎn)鄰域內(nèi)已知像素點(diǎn)的個(gè)數(shù)相同,則鄰域內(nèi)已知像素點(diǎn)距離權(quán)重和越大的越優(yōu)先被修復(fù).在本工作中,待修復(fù)像素點(diǎn)與其24鄰域內(nèi)像素點(diǎn)的距離可采用曼哈頓距離法衡量.距離越小,權(quán)值越大,相關(guān)性越強(qiáng);距離越大,權(quán)值越小,相關(guān)性越弱.其次,紋理結(jié)構(gòu)信息可以用圖像梯度來(lái)描述.圖像梯度體現(xiàn)了當(dāng)前像素點(diǎn)顏色值變化的快慢和方向[9].事實(shí)上,每一幅圖像都有其整體和局部上的紋理結(jié)構(gòu)信息,并反映在其鄰域像素點(diǎn)相關(guān)性上.對(duì)于具體的圖像,如果其垂直方向上的鄰域相關(guān)性大于其他方向,則這幅圖像的內(nèi)容呈垂直條紋效果[10].

本工作采用5×5的局部區(qū)域規(guī)模算子H,窗口步長(zhǎng)為1,構(gòu)造以H區(qū)域內(nèi)像素點(diǎn)顏色值為元素的向量[hi,j],0

2 基于24鄰域的劃痕修復(fù)算法及實(shí)現(xiàn)

基于24鄰域的劃痕修復(fù)算法的思路是先輸入待修復(fù)圖像,再通過(guò)邊界跟蹤算法鎖定待修復(fù)區(qū)域,然后按照一定的優(yōu)先準(zhǔn)則確定邊界上最先修復(fù)的像素點(diǎn)p,之后更新修復(fù)邊界,不斷迭代,直至邊界像素點(diǎn)個(gè)數(shù)為0.由于待修復(fù)區(qū)域的鄰域內(nèi)已知像素點(diǎn)個(gè)數(shù)最多的像素點(diǎn)一定在邊界上,所以邊界跟蹤等價(jià)于尋找鄰域已知像素點(diǎn)個(gè)數(shù)最多的待修復(fù)像素點(diǎn).定義優(yōu)先準(zhǔn)則是為了找到應(yīng)該最先被修復(fù)的像素點(diǎn)p.研究發(fā)現(xiàn),p點(diǎn)的修復(fù)順序主要與3個(gè)因素有關(guān):鄰域已知像素點(diǎn)的個(gè)數(shù)Nqi、鄰域已知像素點(diǎn)的分布Fqi、鄰域已知像素點(diǎn)的梯度Gqi.

2.1 優(yōu)先度計(jì)算

定義優(yōu)先度法則是根據(jù)像素點(diǎn)的初始狀態(tài)確定最先被修復(fù)的像素點(diǎn)p.圖1所示是一個(gè)寬度為5個(gè)像素的垂直劃痕灰度小樣.經(jīng)研究發(fā)現(xiàn),優(yōu)先度主要依賴于如下3個(gè)因素.

圖1 劃痕小樣Fig.1 Scratch samples

(1)24鄰域內(nèi)已知像素點(diǎn)個(gè)數(shù)越多的像素點(diǎn)越優(yōu)先被修復(fù).在輸入待修復(fù)圖像I和掩碼圖像M的同時(shí),系統(tǒng)也進(jìn)行了初始化操作:在待修復(fù)區(qū)域,flag=0;否則,flag=1.求p點(diǎn)鄰域內(nèi)已知像素點(diǎn)的個(gè)數(shù)Nqi等同于計(jì)算p點(diǎn)鄰域內(nèi)“1”的個(gè)數(shù).假設(shè)q(x,y)為p鄰域內(nèi)已知像素點(diǎn)的坐標(biāo),則待修復(fù)區(qū)域內(nèi)已知像素點(diǎn)個(gè)數(shù)最多為max Nqi,q∈φ(p),i∈(0,24).

(2)24鄰域內(nèi)已知像素點(diǎn)的曼哈頓距離權(quán)重和Sum(W)越大越優(yōu)先被修復(fù),如果權(quán)重和的值相等,則優(yōu)先修復(fù)鄰域內(nèi)已知像素點(diǎn)個(gè)數(shù)少的像素點(diǎn).在權(quán)重和相等的情況下,如果鄰域內(nèi)已知像素點(diǎn)個(gè)數(shù)越少,那么相對(duì)應(yīng)的這些像素點(diǎn)的位置越靠近像素點(diǎn)p,對(duì)像素點(diǎn)p的貢獻(xiàn)越大.像素點(diǎn)p與像素點(diǎn)q的曼哈頓距離d可表示為

式中,p為待修復(fù)像素點(diǎn)的坐標(biāo),q為已知像素點(diǎn)的坐標(biāo).對(duì)應(yīng)于像素點(diǎn)p的24鄰域內(nèi)所有已知像素點(diǎn)的曼哈頓距離權(quán)重和為Sum(W),其中W是圓內(nèi)25個(gè)像素點(diǎn)的權(quán)值矩陣,中心的“0”表示其本身的權(quán)值影響值,即待修復(fù)像素點(diǎn)受周圍24個(gè)相關(guān)像素點(diǎn)的影響.對(duì)應(yīng)的曼哈頓權(quán)值矩陣W的公式定義為

像素點(diǎn)p的曼哈頓距離權(quán)重和Sum(W)的公式定義為

(3)位于圖像梯度變化劇烈的位置要優(yōu)先被修復(fù)[11].換言之,法線與等值線方向的夾角θ越小,就越擁有較高的優(yōu)先權(quán).當(dāng)像素點(diǎn)q在等照度線方向NP上時(shí),g(p,q)=1,即方向向量與等照度線重合,此時(shí)g(p,q)最大,該已知像素點(diǎn)對(duì)待修復(fù)像素點(diǎn)的影響也最大.當(dāng)像素點(diǎn)q離等照度線越遠(yuǎn)時(shí),g(p,q)越小,則該像素點(diǎn)對(duì)待修復(fù)像素點(diǎn)的影響也越小.像素方向影響因子為

因此,構(gòu)造綜合影響因子z的公式為

綜合二者得到邊界上所有像素點(diǎn)的優(yōu)先度之后,優(yōu)先修復(fù)優(yōu)先度最高的像素點(diǎn).一般情況下,位于凸起區(qū)域的像素點(diǎn)優(yōu)先于位于凹進(jìn)區(qū)域的像素點(diǎn),位于結(jié)構(gòu)處的像素點(diǎn)優(yōu)先于位于紋理處的像素點(diǎn),位于拐點(diǎn)處的像素點(diǎn)優(yōu)先于位于邊緣處的像素點(diǎn).

2.2 修復(fù)像素點(diǎn)p

根據(jù)式(2),待修復(fù)圖像I上的像素點(diǎn)p也可以表示為

接著,由外向內(nèi)擴(kuò)散,用同樣的方法依次修復(fù)每一個(gè)待修復(fù)像素點(diǎn),并及時(shí)更新邊界像素點(diǎn)及優(yōu)先度值,重復(fù)操作,直到邊界?D=0為止.待所有的劃痕都已被完全修復(fù),保存并導(dǎo)出視頻圖像序列.同理,水平劃痕修復(fù)算法的實(shí)現(xiàn)原理也一樣.

2.3 算法描述

輸入:待修復(fù)圖像I,對(duì)應(yīng)劃痕掩膜圖像M.

輸出:修復(fù)后的圖像IR.

步驟1 讀入待修復(fù)的圖像I及其劃痕掩膜M.

步驟2 計(jì)算I的圖像梯度gvalue及梯度方向gtheta

步驟3 根據(jù)M獲取劃痕區(qū)域所在的點(diǎn)集O與I的對(duì)照關(guān)系.

步驟4 根據(jù)對(duì)照關(guān)系求出點(diǎn)集O的鄰域信息(具體的待修復(fù)像素點(diǎn)p的鄰域已知像素點(diǎn)個(gè)數(shù)).

步驟5 根據(jù)優(yōu)先原則確定當(dāng)前要修復(fù)的劃痕點(diǎn)p:第一優(yōu)先原則,即24鄰域內(nèi)已知像素點(diǎn)個(gè)數(shù)越多的像素點(diǎn)越優(yōu)先被修復(fù);第二優(yōu)先原則,即24鄰域內(nèi)已知像素點(diǎn)權(quán)重和越大的越優(yōu)先被修復(fù),權(quán)重和相等的情況下則優(yōu)先修復(fù)鄰域已知像素點(diǎn)個(gè)數(shù)較少的;第三優(yōu)先原則,位于圖像梯度變化劇烈的位置要優(yōu)先被修復(fù).

步驟6 修復(fù)劃痕像素點(diǎn)p,并標(biāo)記該像素點(diǎn)已被修復(fù),即flag=1.

步驟7 更新對(duì)照關(guān)系,重復(fù)步驟(4)～(6),直到劃痕區(qū)域所在點(diǎn)集都被修復(fù).

步驟8 返回修復(fù)結(jié)果IR.

3 實(shí)驗(yàn)結(jié)果與分析

本工作以Matlab為平臺(tái),運(yùn)行環(huán)境為Intel 1.8 GHz處理器,4 GB內(nèi)存.實(shí)驗(yàn)部分的視頻素材取自2部不同影片的彩色視頻序列.

3.1 修復(fù)效果對(duì)比

實(shí)驗(yàn)1:圖2第1行的連續(xù)3幀序列圖來(lái)源于《越劇西游》,像素大小為704×512,原畫(huà)面中帶有黑色水平、垂直劃痕各一條,且劃痕所在位置的背景比較單純.

實(shí)驗(yàn)2:圖2第2行的連續(xù)3幀序列圖來(lái)源于《從奴隸到從軍》,像素大小為720×480,原畫(huà)面中帶有白色水平、垂直劃痕各一條,水平劃痕所在背景比較單純,垂直劃痕所在背景比較復(fù)雜.

圖2(d)分別對(duì)應(yīng)實(shí)驗(yàn)1和實(shí)驗(yàn)2素材第2幀的掩膜圖像,且掩膜圖像中劃痕所在像素點(diǎn)的個(gè)數(shù)分別為1 135和1 210.

圖2 原損傷視頻序列和掩膜圖像Fig.2 Original damage video sequences and mask images

為了對(duì)比文獻(xiàn)[1]、文獻(xiàn)[2]、文獻(xiàn)[3]和本算法的修復(fù)效果,以實(shí)驗(yàn)1和實(shí)驗(yàn)2素材第2幀為例,修復(fù)效果如圖3所示.為了進(jìn)一步觀察受損圖像的修復(fù)效果,局部放大實(shí)驗(yàn)1中八戒右肩頭衣服與垂直劃痕接壤的位置、實(shí)驗(yàn)2中復(fù)雜背景處的人腳與垂直劃痕重合的位置,結(jié)果如圖4所示.

由圖3和4可見(jiàn):對(duì)于劃痕附近整體顏色比較單一的圖像,文獻(xiàn)[1]、文獻(xiàn)[2]、文獻(xiàn)[3]和本算法的修復(fù)效果都比較明顯;對(duì)于背景相對(duì)復(fù)雜的圖像,4種算法的優(yōu)勢(shì)和弊端存在差異.放大實(shí)驗(yàn)1和實(shí)驗(yàn)2框選出來(lái)的紅色局部位置發(fā)現(xiàn):兩組圖像中均存在深淺不一的修復(fù)痕跡,尤其是實(shí)驗(yàn)2.文獻(xiàn)[1]算法不僅破壞了畫(huà)面的結(jié)構(gòu)性而且還產(chǎn)生了平滑效應(yīng),比如八戒右肩衣角處以及人腳、凳子和草坪的結(jié)合部分均出現(xiàn)了信息損失.文獻(xiàn)[2]算法雖降低了平滑效應(yīng),但修復(fù)痕跡比較明顯,比如在兩組局部圖像上都可以看出有少許殘留的條形痕跡.文獻(xiàn)[3]算法不僅修復(fù)不干凈,而且修復(fù)的邊緣有明顯的階梯效應(yīng),尤其在拐點(diǎn)對(duì)接處修復(fù)得特別粗糙,也十分影響觀察者的視覺(jué)感受.用本算法修復(fù)的邊緣線中間過(guò)渡都比較自然,雖也存在輕微的修復(fù)痕跡,但整體而言,較好地恢復(fù)了受損圖像,保護(hù)了圖像的紋理和結(jié)構(gòu)信息.

圖3 4種劃痕修復(fù)算法的效果對(duì)比Fig.3 Eff ect comparisons of 4 kinds of scratch repair algorithms

圖4 4種劃痕修復(fù)算法的局部放大效果Fig.4 Local magnification effects of 4 kinds of scratch repair algorithms

為了突出本算法的實(shí)用性,本工作進(jìn)行了如下的修復(fù)效果測(cè)試.如圖5所示,在像素為538×307的原圖上手工添加了各種方向的劃痕直線.實(shí)驗(yàn)結(jié)果發(fā)現(xiàn),文獻(xiàn)[1]、文獻(xiàn)[2]、文獻(xiàn)[3]這3種算法根本無(wú)法修復(fù)這種復(fù)雜排列的劃痕,而圖5(c)是本算法修復(fù)的效果,能基本滿足人類視覺(jué)上的要求.

圖5 本算法的修復(fù)效果Fig.5 Repair effect of the algorithm

3.2 性能指標(biāo)分析

目前,針對(duì)算法性能的分析有主觀評(píng)價(jià)與客觀評(píng)價(jià)兩種方法.主觀評(píng)價(jià)是由觀察者直接用肉眼觀察圖像后打分所得,其優(yōu)點(diǎn)是操作方式簡(jiǎn)單且結(jié)果的準(zhǔn)確性、可信度很高,但是過(guò)分依賴于人眼,難以量化且比較耗時(shí)、繁瑣.客觀評(píng)價(jià)通過(guò)定義數(shù)學(xué)公式,并將這些公式量化后來(lái)衡量圖像質(zhì)量的好壞,其優(yōu)點(diǎn)是成本低且易于實(shí)現(xiàn),但是沒(méi)有考慮人類的視覺(jué)特點(diǎn).本工作結(jié)合了這二者的優(yōu)點(diǎn),從如下兩個(gè)方面對(duì)各種算法的修復(fù)效果以及性能指標(biāo)進(jìn)行對(duì)比與分析.

3.2.1 主觀評(píng)價(jià)

本工作邀請(qǐng)了40名觀察者,分別針對(duì)4種算法修復(fù)前后的2組圖像的“合理”和“完整”進(jìn)行有效打分、評(píng)價(jià).具體做法是先將修復(fù)前后的視頻圖像按一定規(guī)則交替播放給觀察者,然后讓觀察者們自主打分,最后再計(jì)算所有分?jǐn)?shù)的平均值作為該圖像序列的評(píng)價(jià)值,具體數(shù)據(jù)如表1所示.可見(jiàn),“平均分”欄數(shù)據(jù)顯示出本算法的修復(fù)效果優(yōu)于文獻(xiàn)[2],文獻(xiàn)[2]略優(yōu)于文獻(xiàn)[1],且文獻(xiàn)[4]不適用于舊電影的劃痕修復(fù).

表1 4種劃痕修復(fù)算法的主觀評(píng)價(jià)結(jié)果比較Table 1 Comparisons of subjective evaluation results of 4 kinds of scratch repair algorithms

3.2.2 客觀評(píng)價(jià)

為了檢驗(yàn)本算法的性能,分別對(duì)4種算法修復(fù)前后視頻的峰值信噪比(peak signal to noise ratio,PSNR)和結(jié)構(gòu)相似性(structural similarity index,SSIM)值進(jìn)行了對(duì)比分析,結(jié)果如表2所示.可見(jiàn),修復(fù)后的視頻質(zhì)量較之前有了很大提高,且利用本算法修復(fù)的視頻的PSNR和SSIM值均高于其他算法,所得圖像也更接近原圖像.

表2 4種劃痕修復(fù)算法的客觀評(píng)價(jià)結(jié)果比較Table 2 Comparisons of objective evaluation results of 4 kinds of scratch repair algorithms

另外,運(yùn)行時(shí)間也是考量一個(gè)算法性能的重要條件.由表3可知:本算法的修復(fù)運(yùn)行時(shí)間較文獻(xiàn)[1]和文獻(xiàn)[2]算法縮短了1/2,較文獻(xiàn)[3]算法縮短了4 s左右,效率更高.

表3 4種劃痕修復(fù)算法的運(yùn)行時(shí)間比較Table 3 Comparisons of running time of 4 kinds of scratch repair algorithms s

綜合顯示,無(wú)論從主觀評(píng)價(jià)還是客觀評(píng)價(jià),本算法的劃痕修復(fù)效果均優(yōu)于其他3種算法.

4 結(jié)束語(yǔ)

針對(duì)傳統(tǒng)圖像修復(fù)算法只利用待修復(fù)像素點(diǎn)的4鄰域或8鄰域信息進(jìn)行修復(fù)的不足,本工作充分利用5×5鄰域內(nèi)的已知像素點(diǎn),提出利用鄰域像素點(diǎn)相關(guān)性的劃痕修復(fù)算法.結(jié)果證明,本算法能較好地克服梯度效應(yīng)、圖像修復(fù)精度不高等問(wèn)題,在主客觀評(píng)價(jià)上均優(yōu)于其他3種算法.當(dāng)然本算法也存在一些缺陷,比如無(wú)法一次性修復(fù)多幀圖片,在修復(fù)結(jié)構(gòu)性很強(qiáng)或者背景較復(fù)雜的區(qū)域時(shí),仍會(huì)出現(xiàn)一定的修復(fù)誤差和模糊現(xiàn)象等,其中的部分原因是沒(méi)有全面考慮綜合因子.若在P z最大的時(shí)候確定優(yōu)先被修復(fù)的像素點(diǎn),則得到的修復(fù)效果會(huì)更優(yōu)于本算法的效果.整體而言,本算法在舊電影、舊照片的劃痕修復(fù)上有廣泛的應(yīng)用前景.