數(shù)字視頻分析中快速邊緣檢測(cè)和運(yùn)動(dòng)估計(jì)研究

徐濟(jì)惠，祝曉東，劉翠娟，郭國(guó)文

（1.寧波城市職業(yè)技術(shù)學(xué)院，寧波　315100；2.浙江萬(wàn)里學(xué)院智能控制研究所，寧波　315100；3.寧波大學(xué)信息科學(xué)與工程學(xué)院，寧波　315100）

數(shù)字視頻分析中快速邊緣檢測(cè)和運(yùn)動(dòng)估計(jì)研究

徐濟(jì)惠1，祝曉東1，劉翠娟2，3，郭國(guó)文2

（1.寧波城市職業(yè)技術(shù)學(xué)院，寧波315100；2.浙江萬(wàn)里學(xué)院智能控制研究所，寧波315100；3.寧波大學(xué)信息科學(xué)與工程學(xué)院，寧波315100）

研究了將粒子群優(yōu)化算法同萬(wàn)有引力算法相結(jié)合進(jìn)行邊緣檢測(cè)，利用萬(wàn)有引力原理進(jìn)行啟發(fā)函數(shù)的計(jì)算，指導(dǎo)蟻群運(yùn)動(dòng)趨向，快速檢測(cè)出邊緣線，作為圖像分析的預(yù)處理結(jié)果；另外根據(jù)視頻圖像中局部運(yùn)動(dòng)集中在圖像中部概率較大的特性，提出對(duì)圖像的幾個(gè)小區(qū)域數(shù)據(jù)進(jìn)行全局運(yùn)動(dòng)估計(jì)，這樣大幅度減少了運(yùn)算量，實(shí)驗(yàn)中通過(guò)采樣4個(gè)六分之一原圖邊長(zhǎng)的矩形區(qū)域進(jìn)行全局估計(jì)，實(shí)驗(yàn)證實(shí)了在精度相同的情況下，運(yùn)算速度提高了九倍左右。

視頻；粒子群優(yōu)化算法；全局運(yùn)動(dòng)估計(jì)；邊緣檢測(cè)；估計(jì)誤差

0　前言

一般來(lái)說(shuō)，隨著圖像特征層次的提高，將更有利于進(jìn)行圖像處理和分析，而且直線特征比點(diǎn)特征更容易檢測(cè)，算法的穩(wěn)定性受限于參數(shù)特征提取的穩(wěn)定性和精確性。使用攝像機(jī)進(jìn)行視頻采樣時(shí)肯定會(huì)遇到尺寸壓縮、變焦和信號(hào)數(shù)字化處理等情況。為了能夠更好地進(jìn)行運(yùn)動(dòng)估計(jì)，必須對(duì)尺寸壓縮和變焦等情況采用圖像穩(wěn)定系統(tǒng)進(jìn)行處理（DIS，digital image stabilization），信號(hào)的數(shù)字化處理為圖像邊緣T穩(wěn)定提取提供了可能。這種數(shù)字圖像處理系統(tǒng)包括三部分：基于邊緣檢測(cè)的預(yù)處理部分；為減少運(yùn)算量，在運(yùn)動(dòng)估計(jì)中運(yùn)用相關(guān)邏輯運(yùn)算代替算術(shù)減運(yùn)算；在變焦處理中使用估計(jì)雙線性插值技術(shù)。

邊緣檢測(cè)是在圖像處理中經(jīng)常使用的技術(shù)，是為從圖像中提取信息的預(yù)處理工作。由于圖像密度是與場(chǎng)景輻射成比例的，所以物理邊緣可以表示為圖像中密度變換的函數(shù)［1］。在數(shù)字圖像處理的發(fā)展的幾十年中，目前已經(jīng)存在許多種邊緣檢測(cè)的算法和方法，例如比較經(jīng)典的邊緣檢測(cè)算法：Sobel，Prewitt，Canny等等。

近期又出現(xiàn)了多種新穎的算法，2007年，吳金波等提出了快速多級(jí)模糊邊緣檢測(cè)算法［2］，對(duì)模糊圖像實(shí)現(xiàn)快速準(zhǔn)確地邊緣檢測(cè)。同年，孫耕耘提出了基于萬(wàn)有引力的邊緣檢測(cè)法［3］，但是這種方法對(duì)內(nèi)存和時(shí)間的消耗都是巨大的，如果直接應(yīng)用這種方法處理尺寸為800*600的圖像，所需要的解內(nèi)存空間為2 800*600。2009年，Hanmandlu等提出了一種基于模糊邏輯的邊緣和角點(diǎn)的監(jiān)測(cè)方法［4］。2009年，Setayesh等提出了一種新的利用粒子群優(yōu)化算法原理對(duì)同質(zhì)基邊緣進(jìn)行檢測(cè)的方法［5］。2011年，Verma等人提出了利用蟻群覓食原理進(jìn)行邊緣監(jiān)測(cè)算法［6］，核心思想是根據(jù)一個(gè)蟻群優(yōu)化算法可以導(dǎo)出方向概率矩陣，蟻群覓食的運(yùn)動(dòng)方向就可以根據(jù)這個(gè)矩陣推動(dòng)出來(lái)。2011年付文龍等提出了基于遺傳規(guī)劃的全局邊緣檢測(cè)算法［7］，該算法的思想就是直接將整個(gè)圖像作為輸入數(shù)據(jù)，不經(jīng)過(guò)任何預(yù)處理和后處理，直接將圖像中的所有像素點(diǎn)歸類(lèi)為邊緣點(diǎn)或非邊緣點(diǎn)。

1　利用蟻群優(yōu)化邊緣檢測(cè)方法

蟻群優(yōu)化簡(jiǎn)稱(chēng)ACO（ant colony optimization），是Dorigo等在1996年最早提出了，算法的優(yōu)點(diǎn)是充分利用群的感知能力，同時(shí)避免由于分布式計(jì)算引起的不成熟的收斂。缺點(diǎn)是由于收斂速度慢，不太適合處理規(guī)模比較大的問(wèn)題。

在蟻群優(yōu)化過(guò)程中，利用幾個(gè)人工螞蟻來(lái)尋求一個(gè)優(yōu)化問(wèn)題的解，這些螞蟻群是通過(guò)特點(diǎn)通信機(jī)制按質(zhì)交換信息，這點(diǎn)同現(xiàn)實(shí)世界中的螞蟻行為非常接近。單獨(dú)一個(gè)螞蟻由于記憶能力是有限的，只能執(zhí)行簡(jiǎn)單的動(dòng)作，然而，蟻群的集體合作可以提高完成智能解決問(wèn)題的能力，例如可以發(fā)現(xiàn)從巢穴到食物源的最短路徑。蟻群覓食時(shí)留下?lián)]發(fā)性物質(zhì)，標(biāo)志它們覓食路線的信息索。蟻群就是這樣通過(guò)這些信息索來(lái)實(shí)現(xiàn)間接通信，這些信息索既是累加的，同時(shí)又是揮發(fā)的，這些信息可以協(xié)助蟻群完成尋找目標(biāo)的任務(wù)。

蟻群優(yōu)化算法要解決的問(wèn)題是，讓K個(gè)螞蟻在由M×N個(gè)節(jié)點(diǎn)組成的解空間χ中尋求優(yōu)化解決方案［8］。

算法實(shí)現(xiàn)可以描述為：

1）首先初始化所有參加運(yùn)算的K個(gè)螞蟻的坐標(biāo)位置，也就是對(duì)信息索矩陣進(jìn)行初始化，得到初始信息索矩陣τ（0）。

2）構(gòu)造蟻群的移動(dòng)步驟，對(duì)于各個(gè)螞蟻（k=1，2，…K）的每個(gè)步驟（n=1，2，…N）進(jìn)行循環(huán)計(jì)算，第k個(gè)螞蟻的第L步的移動(dòng)是按照蛻變概率矩陣Pi，j（n）計(jì)算得到的。

其中：τi，jn是連接節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的弧的信息索的值，Ωi表示的是螞蟻k在位置i節(jié)點(diǎn)時(shí)所對(duì)應(yīng)的所有相鄰節(jié)點(diǎn)的集合，ηi，j表示從節(jié)點(diǎn)i到節(jié)點(diǎn)j的啟發(fā)信息，α表示受信息索的影響因子，β表示受啟發(fā)信息影響的因子。

3）當(dāng)每一步螞蟻按照上式（1）移動(dòng)后，該算法就立即對(duì)信息索矩陣τi，jn進(jìn)行一次更新操作，為后續(xù)的算法執(zhí)行步驟做好準(zhǔn)備。

其中：當(dāng)節(jié)點(diǎn)（i，j）正好處在最佳路徑上，就不需要在繼續(xù)進(jìn)行迭代計(jì)算了。公式中ρ表示信息的揮發(fā)速度，Δki，j表示第k個(gè)螞蟻存留的信息總量。這里最佳路徑是要根據(jù)用戶(hù)定義的標(biāo)準(zhǔn)，這個(gè)最佳路徑既可以是同當(dāng)前構(gòu)建路徑的最佳吻合，也可以是從算法開(kāi)始點(diǎn)到當(dāng)前的最佳路徑，也可以是二者的綜合加權(quán)最佳。通?？梢愿鶕?jù)下式再進(jìn)行選擇：τn=（1-ψ）.τ（n-1）+ψτ（0）（3）

式中的τn是代表所有螞蟻都已經(jīng)按照前面的步驟移到相應(yīng)的節(jié)點(diǎn)，并且信息索矩陣也都按公式（3）進(jìn)行了更新后的最終信息索矩陣。式中ψ代表信息索衰減的系數(shù)。

2　萬(wàn)有引力邊緣檢測(cè)方法

利用萬(wàn)有引力原理進(jìn)行邊緣檢測(cè)算法的核心思想是假設(shè)圖像中的每個(gè)像素被表示為不同灰度強(qiáng)度的“天體”。設(shè)想每個(gè)像素點(diǎn)向周?chē)噜彽狞c(diǎn)施加引力，同樣周?chē)噜彽狞c(diǎn)也向這個(gè)像素點(diǎn)施加引力，見(jiàn)圖1所示。這種情況下邊緣的特征就是大多數(shù)像素點(diǎn)存在有沿著一個(gè)特定方向的引力，所以可以利用這個(gè)特性檢測(cè)邊緣的存在。

對(duì)于圖像中的每個(gè)像素點(diǎn)（I，j），其鄰域可以設(shè)為是一個(gè)k×l像素點(diǎn)組成的域Ω，所有的鄰域像素點(diǎn)滿(mǎn)足條件（m，n）∈Ω&（m，n）≠（i，j）。每個(gè)像素點(diǎn)向周?chē)噜忺c(diǎn)施加的引力按下式計(jì)算：式中，→fi，j；m，n是表示點(diǎn) （m，n）和點(diǎn)（i，j）之間的相互引力，mi，j和mm，n表示這兩個(gè)點(diǎn)的灰度值，灰度值差別可以設(shè)想成萬(wàn)有引力對(duì)象的質(zhì)量不同，→r表示兩點(diǎn)之間的矢量距離。

圖1　基本邊緣結(jié)構(gòu)及相互之間作用力示意

對(duì)于矢量→fi，j；m，n也可以通過(guò)x和y方向的作用力來(lái)表示。

相鄰的各個(gè)點(diǎn)作用于點(diǎn)（i，j）的力總和為：→Fi，j=∑→fi，j；m，n=Fx^x+Fy^y（7）

其中：（m，n）∈Ω&（m，n）≠（i，j）

像素點(diǎn)（i，j）的邊緣強(qiáng)度由矢量→Fi，j的值決定的，其方向也是由矢量→Fi，j的方向所決定的。

只要選擇一個(gè)比較合適的閾值，就可以對(duì)原圖像產(chǎn)生一個(gè)邊緣圖像。

3　算法改進(jìn)

為了減少算法的計(jì)算機(jī)復(fù)雜度和內(nèi)存過(guò)高的需求，采取的方法是將蟻群優(yōu)化算法同萬(wàn)有引力原理相結(jié)合，處理邊緣檢測(cè)的問(wèn)題，利用萬(wàn)有引力原理進(jìn)行啟發(fā)函數(shù)計(jì)算，這個(gè)函數(shù)用來(lái)指導(dǎo)蟻群的趨向。

這是利用一種改進(jìn)的蟻群優(yōu)化算法來(lái)實(shí)現(xiàn)對(duì)邊緣的檢測(cè)。改進(jìn)的邊緣算法的核心思想是，利用一定數(shù)量的螞蟻在二維圖像上移動(dòng)，構(gòu)建一個(gè)信息矩陣，表示了圖像上一個(gè)個(gè)像素點(diǎn)的邊緣信息。先初始化所有螞蟻的位置，將螞蟻隨機(jī)分配到尺寸為M×N的圖像I中，用一個(gè)常數(shù)初始值將信息矩陣初始化為τ（0）。當(dāng)構(gòu)造第n步螞蟻移動(dòng)時(shí)，從K個(gè)螞蟻中任意選擇一個(gè)螞蟻，使這個(gè)螞蟻在圖像中連續(xù)移動(dòng)L個(gè)步長(zhǎng)，即這個(gè)改進(jìn)的螞蟻信息蛻變概率公式：

從節(jié)點(diǎn)（i，j）經(jīng)過(guò)若干步移動(dòng)到相鄰節(jié)點(diǎn)（i，j），τ，（n-1）

00ij是節(jié)點(diǎn)（i，j）的信息索的值。Ω（i0，j0）是與節(jié)點(diǎn)（i0，j0）相鄰節(jié)點(diǎn)的集合，ηi，j表示在節(jié)點(diǎn)（i，j）的啟發(fā)信息，α和β這兩個(gè)常數(shù)，分別代表對(duì)于信息索矩陣和啟發(fā)矩陣的影響系數(shù)。

各個(gè)節(jié)點(diǎn)的啟發(fā)函數(shù)值，是評(píng)估這個(gè)節(jié)點(diǎn)是否為期望的路徑上節(jié)點(diǎn)的重要依據(jù)。啟發(fā)函數(shù)的功能就是在多條可行的路徑上選擇最佳的路徑方案，啟發(fā)函數(shù)是通過(guò)運(yùn)用萬(wàn)有引力原理來(lái)進(jìn)行計(jì)算的。在啟發(fā)函數(shù)中周?chē)噜忺c(diǎn)施加給中心節(jié)點(diǎn)的作用力定義為：

如圖2所示，分別利用Canny算法和改進(jìn)的算法，對(duì)兩幅圖像進(jìn)行邊緣檢測(cè)的結(jié)果，從實(shí)驗(yàn)結(jié)果可以看出傳統(tǒng)算法比本算法能檢測(cè)到更多的邊緣數(shù)目，但本算法可以減少計(jì)算時(shí)間和減少對(duì)內(nèi)存的消耗，對(duì)于實(shí)時(shí)性要求比較高的場(chǎng)合有非常重要的價(jià)值。

圖2　對(duì)Lena圖像和遙感地圖進(jìn)行邊緣檢測(cè)結(jié)果比較

其中本算法進(jìn)行邊緣檢測(cè)時(shí)需要設(shè)定的參數(shù)比較多，螞蟻數(shù)量同圖像尺寸有密切的關(guān)系，一般情況下不妨取：K=，對(duì)信息索矩陣的每一項(xiàng)進(jìn)行初始化為0.000 1，信息索矩陣的權(quán)重因子α設(shè)為2，啟發(fā)信息的權(quán)重β設(shè)為1，每個(gè)節(jié)點(diǎn)的相鄰節(jié)點(diǎn)集合數(shù)設(shè)為8，衰減率ρ設(shè)為0.05，每個(gè)構(gòu)造步中螞蟻的移動(dòng)次數(shù)L設(shè)為40，信息索的衰減率ψ設(shè)為1.5。

4　基于邊緣的全局運(yùn)動(dòng)估計(jì)

當(dāng)對(duì)視頻圖像的預(yù)處理完成后，即完成對(duì)邊緣的檢測(cè)，將圖像所有圖像處理產(chǎn)生邊緣像素和非邊緣像素兩類(lèi)，通過(guò)對(duì)相鄰連續(xù)的圖像的幀序列進(jìn)行計(jì)算匹配，估計(jì)出運(yùn)動(dòng)矢量。對(duì)于視頻運(yùn)動(dòng)估計(jì)可以通過(guò)對(duì)像素點(diǎn)的處理，也可以對(duì)邊緣線的處理：

圖3　視頻圖像運(yùn)動(dòng)的光流場(chǎng)計(jì)算處理結(jié)果

對(duì)于圖像穩(wěn)定系統(tǒng)中運(yùn)動(dòng)估計(jì)目的同其他應(yīng)用環(huán)境中的目的是有所不同的，只需要估計(jì)出一個(gè)全局運(yùn)動(dòng)矢量。為了能夠比較準(zhǔn)確估計(jì)出一幀的全局運(yùn)動(dòng)矢量，一種行之有效的方法是對(duì)一幀圖像的不同區(qū)域分別進(jìn)行運(yùn)動(dòng)估計(jì)，通過(guò)圖3也可以看出，視頻圖像的中央部分的局部運(yùn)動(dòng)比較明顯，為了準(zhǔn)確獲取全局運(yùn)動(dòng)矢量，要盡可能避免這些局部運(yùn)動(dòng)的干擾。一般是取接近邊緣的4個(gè)邊角的位置的區(qū)域，如圖4所示。由于攝像時(shí)，通常是將運(yùn)動(dòng)對(duì)象置為在畫(huà)面的中央?yún)^(qū)域，因此在畫(huà)面邊緣區(qū)域由于對(duì)象運(yùn)動(dòng)引起的局部運(yùn)動(dòng)的概率比較小，相反在畫(huà)面的中央?yún)^(qū)域出現(xiàn)局部運(yùn)動(dòng)的概率比較大，這種由先驗(yàn)經(jīng)驗(yàn)指導(dǎo)的選擇估計(jì)區(qū)域的方法可以保證比較準(zhǔn)確地估計(jì)出圖像幀的全局運(yùn)動(dòng)矢量。

圖4　對(duì)圖像幀進(jìn)行全局運(yùn)動(dòng)估計(jì)的區(qū)域選擇

通常情況下在連續(xù)的兩幀圖像中，第一幀圖像的運(yùn)動(dòng)場(chǎng)稱(chēng)為參考場(chǎng)，連續(xù)的下一幀圖像的運(yùn)動(dòng)場(chǎng)稱(chēng)為比較場(chǎng)。運(yùn)用塊匹配方法來(lái)估計(jì)4個(gè)區(qū)域相應(yīng)的4個(gè)運(yùn)動(dòng)場(chǎng)，首先利用移位寄存器將前一幀的運(yùn)動(dòng)估計(jì)區(qū)域鎖存到當(dāng)前參考運(yùn)動(dòng)場(chǎng)塊里，然后將當(dāng)前圖像場(chǎng)中相應(yīng)的區(qū)域鎖存到比較場(chǎng)塊中，經(jīng)過(guò)圖像預(yù)處理后，圖像中只包括邊緣點(diǎn)和非邊緣點(diǎn)兩大類(lèi)，可以用0和1表示。

通過(guò)統(tǒng)計(jì)參照運(yùn)動(dòng)場(chǎng)塊中同比較場(chǎng)塊中所有像素的絕對(duì)誤差，進(jìn)行塊匹配運(yùn)算。在對(duì)每個(gè)運(yùn)動(dòng)估計(jì)區(qū)域的邊緣預(yù)處理過(guò)程中，可以將參考場(chǎng)中邊緣圖像及比較場(chǎng)的邊緣圖像都轉(zhuǎn)換成了二進(jìn)制邊緣圖像，所以就不需要進(jìn)行減運(yùn)算，而可以采用更加快速的邏輯異或運(yùn)算［9］。

所以對(duì)參考運(yùn)動(dòng)場(chǎng)塊同比較場(chǎng)塊進(jìn)行比較時(shí)，只需要比較對(duì)應(yīng)點(diǎn)是否同時(shí)為1或0值。利用公式（11）進(jìn)行匹配比較，當(dāng)比較場(chǎng)塊移動(dòng)到某個(gè)位置時(shí)，出現(xiàn)比較場(chǎng)塊中同參考運(yùn)動(dòng)場(chǎng)塊中對(duì)應(yīng)點(diǎn)的值相同的數(shù)目達(dá)到最多的情況時(shí)，也就是當(dāng)Cmax（m，n）為最大值時(shí)，就稱(chēng)為最佳匹配，此時(shí)所對(duì)應(yīng)的位移s（i，j）就是當(dāng)前區(qū)域的運(yùn)動(dòng)矢量。

式中的gt0，gt1分別代表參考場(chǎng)塊及當(dāng)前場(chǎng)塊，M×N為運(yùn)動(dòng)估計(jì)區(qū)域的尺寸，其中（i，j）對(duì)應(yīng)當(dāng)前比較場(chǎng)塊的相對(duì)平移量，p是指在搜索窗口的最大位移量。

假設(shè)s（xi，yi）代表利用上述方法獲得的4個(gè)運(yùn)動(dòng)估計(jì)區(qū)域的運(yùn)動(dòng)矢量，其中i表示4個(gè)區(qū)域中的編號(hào)。這里的s′（xi，yi）通常表示理想狀態(tài)環(huán)境中檢測(cè)到的運(yùn)動(dòng)矢量，但實(shí)際情況由于存在對(duì)比度不足、采集圖像中的噪聲、變焦和搖攝和運(yùn)動(dòng)估計(jì)區(qū)域中存在其他運(yùn)動(dòng)對(duì)象等原因，估算出的運(yùn)動(dòng)矢量，與在理想狀態(tài)估計(jì)出的矢量必然會(huì)存在誤差。為了盡量減少這些干擾，根據(jù)不同的環(huán)境和運(yùn)動(dòng)對(duì)象特點(diǎn)需要采集不同的策略，例如對(duì)于對(duì)比度不足和噪音等情況，這兩種情況屬于不可預(yù)知影響因素，可以通過(guò)在圖像預(yù)處理階段──邊緣檢測(cè)時(shí)利用三態(tài)匹配技術(shù)進(jìn)行處理；而對(duì)于可以預(yù)知的干擾因素，例如變焦和搖攝等所引起的干擾可以通過(guò)一些傳統(tǒng)的運(yùn)動(dòng)補(bǔ)償技術(shù)進(jìn)行預(yù)處理。

由于當(dāng)整個(gè)圖像幀中，存在有一個(gè)或數(shù)個(gè)運(yùn)動(dòng)對(duì)象，引起局部運(yùn)動(dòng)而造成噪聲干擾的問(wèn)題往往要專(zhuān)門(mén)處理，這里重點(diǎn)研究由于變焦、搖攝和運(yùn)動(dòng)對(duì)象引起可預(yù)知干擾的情況下如何獲得理想的全局運(yùn)動(dòng)估計(jì)結(jié)果。首先計(jì)算獨(dú)立變量：Ix（i）和Iy（i）

其中：i=1，...，4

再計(jì)算兩個(gè)獨(dú)立的權(quán)αx（i）和αy（i）：

其中：k1和k2分別是兩個(gè)獨(dú)立的常量系數(shù)。再進(jìn)一步計(jì)算穩(wěn)定權(quán)重sx（i）和sy（i）：

式中的（x′i，y′i）表示前一次估計(jì)出的運(yùn)動(dòng)矢量。

利用計(jì)算獲得的獨(dú)立權(quán)重αx（i），αy（i）和穩(wěn)定權(quán)重sx（i）和sy（i），可以按式（15）整合得到比較準(zhǔn)確的運(yùn)動(dòng)矢量，更具有魯棒性。

從公式（13）和 （14）容易知道，隨著Ix（i）和Iy（i）增加，αx（i），αy（i）成比例減少，當(dāng)Ix（i）和Iy（i）增加都超過(guò)一個(gè)閾值時(shí)αx（i），αy（i）都為零。獨(dú)立權(quán)重αx（i），αy（i）可以理解為是各個(gè)小的運(yùn)動(dòng)估計(jì)區(qū)域的運(yùn)動(dòng)矢量同全局運(yùn)動(dòng)矢量的相似度，當(dāng)4個(gè)小區(qū)域估計(jì)出的運(yùn)動(dòng)矢量越接近，每個(gè)獨(dú)立權(quán)重就越大。

當(dāng)完成對(duì)圖像幀的運(yùn)動(dòng)矢量估計(jì)后，為了對(duì)運(yùn)動(dòng)的比較幀的圖像進(jìn)行運(yùn)動(dòng)補(bǔ)償，就要將這圖像沿著這個(gè)運(yùn)動(dòng)矢量相反的方向進(jìn)行移動(dòng)。這種移動(dòng)必然要擴(kuò)大圖像的范圍，在沒(méi)有任何圖像邊界以外信息的情況下，就需要通過(guò)數(shù)字圖像插值法對(duì)參考圖像和比較圖像的邊界進(jìn)行擴(kuò)充。對(duì)數(shù)字圖像進(jìn)行插值的方法有許多，其中最經(jīng)典的同時(shí)也是最簡(jiǎn)單的一種插值方法就是最近鄰居復(fù)制插值法，即需要插值點(diǎn)就復(fù)制最近鄰居的像素點(diǎn)的值。這種方法的優(yōu)點(diǎn)是比較容易通過(guò)硬件直接執(zhí)行，實(shí)時(shí)性比較高，缺點(diǎn)是在斜線邊緣容易產(chǎn)生馬賽克效應(yīng)。當(dāng)然還有一些比較精細(xì)的插值算法，比如高次多項(xiàng)式插值算法［10］，和級(jí)次濾波器保留邊緣插值法，這些方法都能對(duì)數(shù)字圖像的插值效果獲得比簡(jiǎn)單的最近鄰居復(fù)制插值法好很多，但缺點(diǎn)是由于這些方法的計(jì)算復(fù)雜，耗時(shí)很多，而且不適合利用硬件來(lái)進(jìn)行實(shí)時(shí)運(yùn)算。為了滿(mǎn)足兼顧運(yùn)算速度和插值精度的要求，對(duì)于一般的數(shù)字圖像穩(wěn)定系統(tǒng)中，變焦范圍不能太多，否則影響精度，原則上對(duì)于變焦不超過(guò)1.5倍的情況，為了實(shí)現(xiàn)速度和精度的雙重需求，可以使用一種逼近雙線性插值法來(lái)實(shí)現(xiàn)有級(jí)縮放圖像。一旦檢測(cè)到了運(yùn)動(dòng)矢量，運(yùn)動(dòng)補(bǔ)償工作就要開(kāi)始執(zhí)行，整個(gè)圖像被按照這個(gè)矢量方向相反的方向移動(dòng)。這時(shí)運(yùn)動(dòng)補(bǔ)償和逼近雙線性插值要同時(shí)協(xié)調(diào)進(jìn)行。

5　實(shí)驗(yàn)與分析

在對(duì)標(biāo)準(zhǔn)灰度視頻序列乒乓球（圖5）和花園（圖6）進(jìn)行了仿真實(shí)驗(yàn)中，圖像幀的分辨率為352×240，對(duì)連續(xù)的幀圖像4個(gè)頂點(diǎn)尺寸為60×40像素的小區(qū)域進(jìn)行采樣計(jì)算［11］。

圖5　乒乓球視頻的32-34幀

圖6　花園視頻20-22幀

例如利用全域匹配（full search FS）方法和本算法，分別是對(duì)全圖進(jìn)行匹配計(jì)算和對(duì)4個(gè)小區(qū)域進(jìn)行計(jì)算，對(duì)不一定數(shù)量的連續(xù)幀計(jì)算，得到的估計(jì)幀和原始實(shí)際真的平均方根錯(cuò)誤（MSE）趨勢(shì)數(shù)據(jù)如圖7所示。

圖7　計(jì)算不同幀數(shù)的視頻序列的MSE值趨勢(shì)圖

對(duì)不同視頻序列計(jì)算得到的估計(jì)幀和原始實(shí)際幀的平均方根錯(cuò)誤（MSE）的平均值如表1所示。

表1　對(duì)準(zhǔn)視頻的運(yùn)動(dòng)估計(jì)平均MSE值比較

對(duì)全局運(yùn)動(dòng)進(jìn)行估計(jì)的時(shí)候，每一幀圖像搜索的像素點(diǎn)個(gè)數(shù)是352*240=84 480個(gè)。在本算法中對(duì)于每一幀搜索的是4個(gè)小區(qū)域，對(duì)應(yīng)的像素點(diǎn)個(gè)數(shù)是60*40*4=9 600個(gè)，所以計(jì)算量減少了接近9倍（84 480/9 600=8.8）。而且本算法可以結(jié)合邊緣檢測(cè)的預(yù)處理結(jié)果，將一幅圖像進(jìn)行處理后所有的像素點(diǎn)都被分成緣點(diǎn)和非邊緣點(diǎn)兩類(lèi)，可以用二進(jìn)制0和1表示，如果配置專(zhuān)用硬件設(shè)備，這樣進(jìn)行全局估計(jì)匹配的時(shí)候僅僅需要進(jìn)行邏輯與或計(jì)算 （公式11），能夠更進(jìn)一步提高匹配速度。從圖7和表1可以看出本算法的運(yùn)動(dòng)估計(jì)誤差要比對(duì)全圖進(jìn)行計(jì)算估計(jì)要更小一些，尤其是對(duì)乒乓球標(biāo)準(zhǔn)視頻的估計(jì)準(zhǔn)確性更高，這是由于乒乓球視頻中存在由于球體和手臂等快速移動(dòng)對(duì)象引起的局部運(yùn)動(dòng)，在全局匹配的算法中，這些干擾被累加到了全局運(yùn)動(dòng)估計(jì)中了，引起了估計(jì)誤差，而本算法由于只對(duì)四周幾個(gè)小區(qū)域進(jìn)行匹配計(jì)算，能有效避開(kāi)了快速運(yùn)動(dòng)引起局部運(yùn)動(dòng)的干擾，所以對(duì)精確度提高效果更加明顯，花園視頻的中這種局部運(yùn)動(dòng)引起的干擾基本不存在，所以?xún)烧呷诌\(yùn)動(dòng)估計(jì)誤差基本接近。

6　總結(jié)

本文首先研究的就是利用選取圖像中的典型特征邊緣線作為運(yùn)動(dòng)估計(jì)的基本單元，比如線和拐點(diǎn)等，一般來(lái)說(shuō)，隨著圖像特征層次的提高，將更有利于進(jìn)行圖像處理和分析。為了克服傳統(tǒng)邊緣檢測(cè)方法計(jì)算量大，耗時(shí)多的缺點(diǎn)，通過(guò)將的粒子群優(yōu)化算法原理與萬(wàn)有引力原理的方法想結(jié)合，利用萬(wàn)有引力原理進(jìn)行啟發(fā)函數(shù)的計(jì)算結(jié)果指導(dǎo)粒子群運(yùn)動(dòng)趨向，從而快速檢測(cè)出邊緣線。另外，利用視頻幀圖像中，快速移動(dòng)對(duì)象集中在畫(huà)面中央的概率比較大的特性，為了能夠比較準(zhǔn)確估計(jì)出一幀的全局運(yùn)動(dòng)矢量，采取對(duì)一幀圖像的不同區(qū)域分別進(jìn)行運(yùn)動(dòng)估計(jì)，一般是取接近邊緣的4個(gè)邊角的位置的區(qū)域，這樣既可以避開(kāi)畫(huà)面中央局部運(yùn)動(dòng)數(shù)據(jù)引入全局運(yùn)動(dòng)估計(jì)的干擾，同時(shí)減少了運(yùn)動(dòng)估計(jì)匹配的計(jì)算量，通過(guò)實(shí)驗(yàn)表明，在保證精度的情況下，運(yùn)算速度提高了接近9倍，這對(duì)于視頻運(yùn)動(dòng)估計(jì)，編碼壓縮和解碼都具有非常重要的意義。

［1］Ziou，Tabbone S.Edge Detection Techniques-An Overview［J］. International Journal on Pattern Recognition and Image Analysis. 1998，8：537-559.

［2］Wu J，Yin Z，Xiong Y.The Fast Multilevel Fuzzy Edge Detection of Blurry Images［J］.IEEE Signal Processing Letters.2007，14（5）：344-347.

［3］Genyun Suna，Qinhuo Liua，Qiang Liua，et al.A novel approach for edge detection based on the theory of universal gravity［J］.Pattern Recognition，2007，40（10）：2766-2775.

［4］Hanmandlu M，Verma O P，Gangwar P，et al.Fuzzy Edge and Corner Detector for Color Images［J］.in Proc.ITNG.2009：1301 1306.

［5］Setayesh M，Zang M and Jonhnton M.A new homogeneity-based approach to edge detection using PSO［J］.24th International Conference Image and Vision Computing.New Zealand （IVCNZ）. 2009：231-236.

［6］VermaO P，Hanmandlu M，KumarP，etal.A NovelBacterial ForagingTechniqueforEdge Detection ［J］.Pattern Recognition Letters.2011，（8）：1187 1196，2011.

［7］Fu W L，Johnston M，Zhang M J.Genetic Programming for Edge Detection：A Global Approach［J］.Proceeding of the 2011 IEEE Congress on Evolutionary Computation.IEEE Press.2011：254-261.

［8］Verma O P，Sharma.An Optimal Edge Detection using Universal Law of Gravity and Ant Colony Aglorithm［A］.Information and Communication Technologies（WICT），2011nWorld Congress on Date of Conference［C］.2011：507-511.

［9］祝曉東，郁松年.運(yùn)用視頻技術(shù)的快速三維旋轉(zhuǎn)分析與計(jì)算的研究［J］.計(jì)算機(jī)科學(xué)，2013，40 （2）：289-299.

［10］Netravali A N，Haskell B G.Digital Pictures-Representation and Compression［M］.Plenum Press，1988.

［11］祝曉東，徐濟(jì)惠，郁松年.視頻分析中全局運(yùn)動(dòng)矢量快速估計(jì)的研究 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2013，34（3）：965-970.

Research Fast Edge Detection and Motion Estimation in Digital Video Analysis

Xu Jihui1，Zhu Xiaodong1，Liu Chuijuan2，3，Guo Guowen2
（1.Ningbo City college，Ningbo200072，China；2.Institute of Intelligent Control of Zhejiang Wanly College，Ningbo315100，China；3.Department of Information Science and Engineering，Ningbo University，Ningbo315100，China）

This paper first study the edge detection based on particle swarm optimization algorithm and universal gravitation algorithm in this paper.Using the principle of universal gravitation to calculate the heuristic function，guide the ant colony movement trend，and quickly detect the edge of the line.The detection results can be used as the preprocessing results of image analysis.We propose a global motion estimation based on several small domain data of the image according to the video of the local image motion is concentrated in the central part of the image of greater probability characteristics.In this way the amount of computation can be greatly reduced.We sampled four of 1/6 rectangular area original length in the experiment of global estimation.The experiment proves that the operation speed is increased by about nine times in the same accuracy.

video；particle swarm optimization algorithm；global motion estimation；edge detection；estimation error

1671-4598（2016）05-0242-04

10.16526/j.cnki.11-4762/tp.2016.05.068

TP306

A

2016-03-09；

2016-03-30。

國(guó)家自然科學(xué)基金項(xiàng)目（61103054）；浙江省科技廳/公益項(xiàng)目（2012C21032）；寧波市科技計(jì)劃項(xiàng)目（2014C50018，2015C50053）；浙江省教育廳科研項(xiàng)目（Y201329047）。

徐濟(jì)惠（1964-），男，浙江寧波人，副教授，主要從事圖像處理，視頻圖像分析等方向的研究。