基于邊緣檢測的快速斑點(diǎn)識(shí)別算法

謝丹桂 劉軍清 孫水發(fā) 雷幫軍

(三峽大學(xué)智能視覺與圖像信息研究所,湖北 宜昌 443002)

老影視資料以其獨(dú)特的方式見證并記錄了世界的歷史與現(xiàn)實(shí)、發(fā)展與進(jìn)步、苦難與輝煌,是同時(shí)代文化工作者的藝術(shù)結(jié)晶,具有重要的歷史價(jià)值與藝術(shù)價(jià)值.然而由于老影視資料膠片本身的化學(xué)物質(zhì)非常容易老化,而且以往的保存技術(shù)落后,同時(shí)老影視資料在反復(fù)播放拷貝過程中也受到了不同程度的損傷.這樣一來,現(xiàn)存的老影視資料能夠正常播放的很少,出現(xiàn)了如:斑點(diǎn)、閃爍、抖動(dòng)、褪色、劃痕等缺陷[1-2].對(duì)保存下來的老影視資料進(jìn)行修復(fù)并且重新保存到新的存儲(chǔ)載體極為重要.

斑點(diǎn)是分布在電影畫面中大小不一、形狀各異的亮塊或暗塊.斑點(diǎn)作為老影視資料最主要的缺陷之一,對(duì)老影視資料畫面質(zhì)量的影響非常大,因此斑點(diǎn)的識(shí)別與修復(fù)具有重要的應(yīng)用價(jià)值,其中快速準(zhǔn)確識(shí)別斑點(diǎn)是修復(fù)的必要前提.研究表明,斑點(diǎn)可看作隨機(jī)噪聲.因此對(duì)斑點(diǎn)的檢測主要依據(jù)斑點(diǎn)的空間連續(xù)性以及時(shí)間不連續(xù)性兩個(gè)特征[3].

Kakaram[4]提出的斑點(diǎn)檢測索引法(Spike Detection Index,SDI)將運(yùn)動(dòng)估計(jì)之后的前后幀與當(dāng)前幀對(duì)應(yīng)位置像素值的差值與閾值進(jìn)行比較來判斷是否為斑點(diǎn).該方法僅利用了斑點(diǎn)時(shí)間不連續(xù)性特征,存在很多誤識(shí)別.Nadenau M J[5]提出了等級(jí)差分斑點(diǎn)識(shí)別法(Rank Ordered Difference,ROD),該方法與SDI方法不同的是考慮了前后幀對(duì)應(yīng)位置臨近的像素與當(dāng)前像素的差別,改善了識(shí)別效果.Tilie.S[6]采用了ROD的簡化方法—簡化的等級(jí)差分斑點(diǎn)識(shí)別算法(Simplified Rank Ordered Difference,SROD).該方法只用一個(gè)閾值.在閾值較小的情況下,該方法識(shí)別性能要好于 ROD,但同時(shí)誤識(shí)別率要高一些.Gullu M K[7]在 2008年提出了一種兩級(jí)SROD方法,該方法在閾值較小的情況下先采用一次SROD算法保證所有斑點(diǎn)都被識(shí)別出來,然后依據(jù)識(shí)別出的斑點(diǎn)位置矩陣,提高閾值,采用局部運(yùn)動(dòng)估計(jì)的SROD斑點(diǎn)識(shí)別算法排除誤識(shí)別斑點(diǎn)像素.這種方法識(shí)別精度高,但因采用兩次SROD算法,大大增加了時(shí)間復(fù)雜度.

上述算法都要對(duì)當(dāng)前幀所有像素執(zhí)行斑點(diǎn)識(shí)別算法,時(shí)間復(fù)雜度非常大.本文提出了一種基于邊緣檢測的快速斑點(diǎn)識(shí)別方法.與以往的SDI算法[4]、ROD算法[5]、SROD算法[6]以及Gullu MK 的兩級(jí)SROD算法[7]不同,該算法利用邊緣檢測,將當(dāng)前畫面所有邊緣(包括斑點(diǎn)的邊緣和非斑點(diǎn)邊緣)檢測出來,然后依據(jù)邊緣像素點(diǎn),采用本文提出的正反掃描方法與局部運(yùn)動(dòng)估計(jì)的SROD算法完整地識(shí)別出所有斑點(diǎn).該算法只需對(duì)邊緣及其附近像素進(jìn)行斑點(diǎn)識(shí)別就可以找到所有斑點(diǎn),因此大大縮短了算法時(shí)間.同時(shí)斑點(diǎn)識(shí)別效果也有較明顯改善.

1 基于邊緣檢測的斑點(diǎn)識(shí)別算法

圖1 本文提出的斑點(diǎn)識(shí)別算法框圖

1.1 邊緣檢測算法的選取

根據(jù)斑點(diǎn)的特性,斑點(diǎn)與畫面背景之間必會(huì)形成明顯的邊緣輪廓,同時(shí)畫面其他對(duì)象也有邊緣輪廓.邊緣檢測將斑點(diǎn)邊緣與其他對(duì)象的邊緣檢測出來,如圖1所示.只要獲得斑點(diǎn)的部分邊緣,再利用本文提出的正反掃描方法,就能找到斑點(diǎn)其它像素,包括未檢測出來的斑點(diǎn)邊緣像素.因此,本文對(duì)邊緣檢測精度要求不高,不需要用定位精度高但同時(shí)復(fù)雜度也很高的邊緣檢測算法,如Canny[9]算法.而是盡量選擇時(shí)間復(fù)雜度小的檢測算法.本文選擇的是比較常用的Sobel[8]邊緣檢測算法.

1.2 局部運(yùn)動(dòng)估計(jì)的SROD斑點(diǎn)識(shí)別算法

邊緣檢測之后,得到的是邊緣點(diǎn)位置的二值掩模矩陣.根據(jù)二值掩模矩陣中的邊緣點(diǎn)位置,不僅要判斷出斑點(diǎn)邊緣,還要根據(jù)斑點(diǎn)邊緣找到所有完整的斑點(diǎn).本文采用提出的正反掃描方法結(jié)合局部運(yùn)動(dòng)估計(jì)的SROD進(jìn)行斑點(diǎn)識(shí)別.正反掃描的過程與局部運(yùn)動(dòng)估計(jì)的SROD算法同時(shí)進(jìn)行.正反掃描的思想是根據(jù)已識(shí)別到的斑點(diǎn)像素位置預(yù)測臨近可能的斑點(diǎn)像素位置,局部運(yùn)動(dòng)估計(jì)的SROD算法既要從邊緣點(diǎn)中辨別出斑點(diǎn)邊緣點(diǎn),又要對(duì)掃描過程中預(yù)測的斑點(diǎn)像素判斷是否是真正的斑點(diǎn)像素.

由于邊緣檢測將斑點(diǎn)識(shí)別的范圍縮小到邊緣點(diǎn)附近,在進(jìn)行斑點(diǎn)識(shí)別時(shí)就無需像以往的SROD算法一樣,需要在識(shí)別之前對(duì)整個(gè)前后幀進(jìn)行運(yùn)動(dòng)補(bǔ)償.為進(jìn)一步節(jié)省時(shí)間上的開支,本算法采用局部運(yùn)動(dòng)估計(jì)的SROD斑點(diǎn)識(shí)別方法.采用基于塊的運(yùn)動(dòng)估計(jì)算法,這一思想首先出現(xiàn)在參考文獻(xiàn)[7]中,只需對(duì)要識(shí)別的位置在前后幀對(duì)應(yīng)的區(qū)域進(jìn)行運(yùn)動(dòng)估計(jì).與文獻(xiàn)[7]不同的是,這里采用的塊大小為3×1,而不是2×2或4×4.原因是SROD算法采用了前后幀與當(dāng)前像素位置上下相鄰的元素作為算法的輸入,因此采用3×1的塊運(yùn)動(dòng)估計(jì)可以與SROD算法很好地結(jié)合起來,減少了矩陣變換過程,從而節(jié)省了時(shí)間開銷.

SROD斑點(diǎn)識(shí)別算法原理利用了斑點(diǎn)的空間連續(xù)性與時(shí)間不連續(xù)性特性.首先需要構(gòu)建一個(gè)向量p(x,y,t),p(x,y,t)由經(jīng)過運(yùn)動(dòng)估計(jì)后的前后幀6個(gè)像素的像素值組成,如式(1)所示.在局部運(yùn)動(dòng)估計(jì)的SROD算法中,不是前后幀所有的像素都進(jìn)行運(yùn)動(dòng)補(bǔ)償,只有待識(shí)別的位置的點(diǎn)對(duì)應(yīng)在前后幀中的6個(gè)像素在識(shí)別時(shí)需要進(jìn)行運(yùn)動(dòng)補(bǔ)償.

式中,x,y表示待識(shí)別像素值的坐標(biāo)值;t表示當(dāng)前幀,t-1,t+1分別表示前一幀和后一幀;I(?)表示對(duì)應(yīng)幀對(duì)應(yīng)像素的灰度值.對(duì)p(x,y,t)向量進(jìn)行如下操作

若SROD(x,y,t)大于閾值 T,當(dāng)前點(diǎn)被判為斑點(diǎn),否則為非斑點(diǎn)像素.閾值T的設(shè)置采用自適應(yīng)的方法,即根據(jù)當(dāng)前幀圖像的灰度信息平均值與運(yùn)動(dòng)量大小來自動(dòng)調(diào)整 T的大小,該思想最初出自文獻(xiàn)[4].

1.3 正反掃描方法

首先,掩模矩陣存儲(chǔ)的是邊緣檢測之后的結(jié)果,也就是掩模矩陣中像素值為1的點(diǎn)對(duì)應(yīng)于當(dāng)前幀的像素是邊界點(diǎn)像素.正掃描過程如下:

從上往下,從左往右,依次掃描掩模矩陣.忽略掩模矩陣中值為0的點(diǎn).掩模矩陣中值為1的點(diǎn),對(duì)當(dāng)前幀相應(yīng)位置的像素做局部運(yùn)動(dòng)估計(jì)的SROD斑點(diǎn)識(shí)別.若確認(rèn)當(dāng)前像素為斑點(diǎn)像素,則對(duì)掩模矩陣中當(dāng)前位置的鄰近像素(如圖2(a)中箭頭所指位置像素)的像素值賦1.對(duì)應(yīng)于這些位置的當(dāng)前幀中的像素作為待識(shí)別的像素.這些待識(shí)別的點(diǎn),在后續(xù)的掃描過程中利用局部運(yùn)動(dòng)估計(jì)的SROD算法做進(jìn)一步判斷.若局部運(yùn)動(dòng)估計(jì)的SROD斑點(diǎn)識(shí)別算法確認(rèn)當(dāng)前像素為非斑點(diǎn)像素,則對(duì)掩模矩陣中當(dāng)前位置的像素值賦0.

通過不同數(shù)量處理器的反復(fù)試驗(yàn)數(shù)據(jù)分析，得到的結(jié)論是處理器的數(shù)目從少到多的遞增，對(duì)應(yīng)的收斂值越小，但計(jì)算時(shí)間是先減少，后增加。在試驗(yàn)中，當(dāng)處理器的數(shù)量為4時(shí)，收斂值時(shí)間花費(fèi)是最少的。處理器的數(shù)量再遞增到6，所花費(fèi)的時(shí)間并非減少，反而是增加，原因是處理器數(shù)量增加，并行蟻群算法的處理器間進(jìn)程信息傳遞及通訊時(shí)間花費(fèi)增大，因而使得總的計(jì)算花費(fèi)時(shí)間增加。對(duì)于收斂值隨著處理器的增加而減少的結(jié)果，原因是處理器數(shù)量增加，算法的搜尋區(qū)域更大，盡管花費(fèi)在搜尋的時(shí)間更多，但最優(yōu)解卻容易得到，可靠性更好。

掃描過程中,要進(jìn)行局部運(yùn)動(dòng)估計(jì)的SROD斑點(diǎn)識(shí)別的像素包括邊緣檢測得到的邊緣點(diǎn)和被判斷為斑點(diǎn)的鄰近的待識(shí)別點(diǎn).與當(dāng)前幀已被識(shí)別的區(qū)域?qū)?yīng)的掩模矩陣區(qū)域中,像素值為1的點(diǎn)表明當(dāng)前幀對(duì)應(yīng)點(diǎn)為斑點(diǎn)像素點(diǎn).當(dāng)前幀未被識(shí)別的區(qū)域,對(duì)應(yīng)掩模矩陣中像素值為1的點(diǎn),一部分是邊緣檢測之后還未經(jīng)局部運(yùn)動(dòng)估計(jì)SROD算法識(shí)別是否為斑點(diǎn)的邊緣點(diǎn),另一部分是已經(jīng)被識(shí)別為斑點(diǎn)的鄰近待識(shí)別點(diǎn).掃描過程中,對(duì)鄰近位置斑點(diǎn)像素預(yù)測依據(jù)的原理是斑點(diǎn)的空間連續(xù)性,即斑點(diǎn)像素附近的像素可能是斑點(diǎn)像素.

一般情況下,經(jīng)過正掃描與局部運(yùn)動(dòng)估計(jì)的SROD斑點(diǎn)識(shí)別,所有斑點(diǎn)基本上能完整找到.但在邊緣檢測時(shí),若最左或者最上方的邊緣缺失,就有可能造成后面識(shí)別的斑點(diǎn)不完整.此時(shí)需要根據(jù)正掃描已經(jīng)得到的斑點(diǎn)位置,也就是正掃描之后的掩模矩陣,再做一次反掃描.從下往上,從右往左進(jìn)行掃描就能把整個(gè)斑點(diǎn)找出來,這時(shí)掃描的臨接像素位置如圖2(b)中箭頭所指位置所示.

圖2 掃描中的鄰近像素

圖3給出了本文提出的斑點(diǎn)識(shí)別算法對(duì)視頻序列“永不消失的電波”中某一斑點(diǎn)幀的仿真結(jié)果,包括每一步的中間結(jié)果和最終斑點(diǎn)識(shí)別結(jié)果.這4個(gè)圖分別是含有斑點(diǎn)的當(dāng)前幀、當(dāng)前幀的Sobel邊緣檢測結(jié)果的二值掩模矩陣圖像、正掃描后斑點(diǎn)識(shí)別結(jié)果的二值掩模矩陣圖像、反掃描后斑點(diǎn)識(shí)別結(jié)果的二值掩模矩陣圖像.當(dāng)前幀中用紅色圈標(biāo)記的白色不規(guī)則的亮塊就是斑點(diǎn).Sobel邊緣檢測結(jié)果的二值掩模矩陣圖像中用紅色圈標(biāo)記的是相應(yīng)的斑點(diǎn)邊界.

圖3 老電影視頻序列“永不消失的電波”中的缺陷幀斑點(diǎn)識(shí)別結(jié)果

可以看出Sobel邊緣檢測出來的斑點(diǎn)邊緣不完整,最上與最左邊的邊緣都有缺失,因此正掃描識(shí)別到的斑點(diǎn)也不完整,需要反掃描才能得到完整的斑點(diǎn).經(jīng)過上面Sobel邊緣檢測、正反掃描以及局部運(yùn)動(dòng)估計(jì)的SROD斑點(diǎn)識(shí)別等步驟,最終得到本文提出的斑點(diǎn)識(shí)別算法的流程圖如圖4所示.

2 實(shí)驗(yàn)結(jié)果及分析

本文將提出的算法與SROD斑點(diǎn)識(shí)別算法[6-7]中Gullu MK提出的兩級(jí)SROD斑點(diǎn)識(shí)別算法識(shí)別結(jié)果進(jìn)行了比較.算法在 PC機(jī)(處理器 Intel Core Duo、主頻1.83GHz、內(nèi)存1G)上實(shí)現(xiàn).表1給出了各個(gè)斑點(diǎn)識(shí)別算法在時(shí)間復(fù)雜度上的比較結(jié)果,所用斑點(diǎn)視頻幀來源于5個(gè)不同的老電影視頻序列.圖5、6中只給出了其中兩個(gè)序列的斑點(diǎn)幀斑點(diǎn)識(shí)別視覺對(duì)比效果.實(shí)驗(yàn)中的所有斑點(diǎn)均為老電影中實(shí)際存在的斑點(diǎn).

圖4 本文提出的斑點(diǎn)識(shí)別算法流程圖

圖5 視頻序列“劉三姐2”中斑點(diǎn)幀3種斑點(diǎn)識(shí)別算法識(shí)別視覺對(duì)比效果

圖5、6分別是劉三姐2、松花江上這兩種視頻序列中斑點(diǎn)幀的三種斑點(diǎn)識(shí)別算法識(shí)別效果的視覺對(duì)比.針對(duì)每個(gè)視頻序列,4個(gè)圖像依次為,含有斑點(diǎn)的當(dāng)前幀、SROD算法識(shí)別結(jié)果、Gullu MK的兩級(jí)SROD算法識(shí)別結(jié)果、提出的算法識(shí)別結(jié)果.從圖5、6可以看出,SROD算法存在很多誤識(shí)別,Gullu MK的兩級(jí)SROD算法識(shí)別精度高、效果明顯優(yōu)于SROD算法.而提出的算法的斑點(diǎn)識(shí)別效果幾乎可以同兩級(jí)SROD算法媲美.

圖6 視頻序列“松花江上”中斑點(diǎn)幀3種斑點(diǎn)識(shí)別算法識(shí)別視覺對(duì)比

由表1可以看出,Gullu MK提出的兩級(jí)SROD算法雖然識(shí)別效果好,但時(shí)間復(fù)雜度最高.提出的算法的時(shí)間復(fù)雜度遠(yuǎn)遠(yuǎn)小于Gullu MK的兩級(jí)SROD算法的以及SROD算法的.跟SROD算法相比,本文提出的算法所消耗的時(shí)間比SROD算法所耗時(shí)間的1/2還要少,甚至是SROD算法的1/4.

表1 3種算法時(shí)間復(fù)雜度比較(單位:s)

觀察3種算法時(shí)間復(fù)雜度以及視覺效果可以看出,SROD算法存在很多誤識(shí)別,Gullu MK的兩級(jí)SROD算法雖然取得了比較好的識(shí)別效果,但是由于采用了一次SROD算法加上一次局部運(yùn)動(dòng)估計(jì)的SROD算法的模式,時(shí)間復(fù)雜度非常高.本文提出算法不僅在效果上幾乎可以達(dá)到兩級(jí)SROD的性能,而且時(shí)間復(fù)雜度遠(yuǎn)遠(yuǎn)小于SROD算法以及兩級(jí)SROD算法.

提出的算法基于邊緣檢測的思想將識(shí)別范圍集中到邊緣區(qū)域,同時(shí)也縮小了運(yùn)動(dòng)估計(jì)誤差帶來的誤識(shí)別范圍,誤識(shí)別一般只會(huì)出現(xiàn)在邊緣區(qū)域.這也是從某種程度上來說,新的算法識(shí)別視覺效果要好于SROD斑點(diǎn)識(shí)別算法的原因之一.其次,局部運(yùn)動(dòng)估計(jì)的SROD檢測算法在運(yùn)動(dòng)估計(jì)的時(shí)候考慮了局部小范圍的運(yùn)動(dòng),而且本文中提出的算法運(yùn)動(dòng)估計(jì)中采用3×1的塊大小,相對(duì)于SROD算法的4×4的塊匹配更精確,這也是識(shí)別效果更好的原因.

在時(shí)間復(fù)雜度上,提出的算法占絕對(duì)優(yōu)勢的原因是:一是因?yàn)榛谶吘墮z測的思想將識(shí)別范圍集中到邊緣區(qū)域,縮短了識(shí)別時(shí)間;二是采用局部的運(yùn)動(dòng)估計(jì),無需對(duì)整個(gè)前后幀進(jìn)行運(yùn)動(dòng)估計(jì),只需對(duì)邊緣點(diǎn)及其附近的可能是斑點(diǎn)的像素點(diǎn)進(jìn)行運(yùn)動(dòng)估計(jì),進(jìn)一步縮短了時(shí)間.

3 結(jié) 論

本文提出了一種基于邊緣檢測的斑點(diǎn)識(shí)別算法.利用邊緣檢測將斑點(diǎn)識(shí)別范圍縮小到邊緣附近,并且將局部運(yùn)動(dòng)估計(jì)的優(yōu)勢有效地應(yīng)用到提出的算法中,與文中的掃描方式相結(jié)合,大大減少了時(shí)間復(fù)雜度,取得了很好的斑點(diǎn)識(shí)別效果,非常適合應(yīng)用到工程實(shí)際中.如何進(jìn)一步減少時(shí)間復(fù)雜度,提高斑點(diǎn)識(shí)別性能以及基于該算法的斑點(diǎn)修復(fù)是下一步要研究的重點(diǎn).

[1］堪安軍.數(shù)字視頻修復(fù)若干關(guān)鍵技術(shù)研究[D].北京:中國科學(xué)院研究生院,2006.

[2］陳 釗,關(guān)景火,徐 進(jìn),等.基于小波分解的電影膠片劃痕損傷數(shù)字修復(fù)技術(shù)[J].中國圖象圖形學(xué)報(bào),2006,11(11):58-63.

[3］SaitoT,Komatsu T,Ohuchi T.Practical Nonlinear Filtering for Removal of Blotches from Old Film[M].Proc.Conf.Image Processing,1999(3):164-168.

[4］Kokaram A C,Rayner P J.A System for the Removal of Impulsive Noise in Image Sequences[M].International Conference on SPIE Visual Communications in Image Processing,Boston,M A,1992,322-331.

[5］Nadenau M J,Mitra S K.Blotch and Scratch Detection in Image Sequences Based on Rank Ordered Differences[M].Proceedings of the Fifth Internet Workshop on Time-Varying Image Processing and Moving Object Recognition.Florence,Italy,1996:1-7.

[6］Tilie S,Laborelli L,Bloch I.A Contrario False Alarms Removal for Improving Blotch Detection in Digitized Films Restoration[M].Processings of 14th Int.Workshop on Systems,Signals and Image Processing,and 6th EURASIP Conf.Focused on Speech and Image Processing,M ultimedia Communications and Services,M aribor,Sloveniar,2007:410-413.

[7］Kemal Gullu M,Oguzhan U,Sarp E.Blotch Detection and Removal for Archive Film Restoration[J].AEUInternational Journal of Electronics and Communications.2008,62(9):534-543.

[8］Jagadish P,Shambhavi D S.A novel Digital Algorithm for Sobel Edge Detection[J].Communications in Computer and Information Science,2010,70(6):91-95.

[9］Pawlak Z,Peters J F,Skowron A.Rough Measures Rough Integrals and Sensor Fusion[M].Rough Sets and Granular Computing.Berlin:Springer,2003,125(11):263-272.