王燕妮 ， 樊養(yǎng)余

（1.西安建筑科技大學(xué) 信息與控制工程學(xué)院，陜西 西安 710055；2.西北工業(yè)大學(xué) 電子信息學(xué)院，陜西 西安 710072）

1 引言

在視頻序列分析中，由于運(yùn)動(dòng)目標(biāo)在視頻序列中所占的信息量最大，經(jīng)常成為被分割提取的視頻對(duì)象[1]，因此在分割提取動(dòng)態(tài)的視頻對(duì)象時(shí)，重要的是區(qū)分出運(yùn)動(dòng)目標(biāo)和背景的范圍。遺傳算法是模擬生物進(jìn)化過程而建立的一種最優(yōu)化方法，在此提出一種新的自適應(yīng)遺傳視頻運(yùn)動(dòng)對(duì)象分割算法，確定自適應(yīng)遺傳機(jī)制、自適應(yīng)初代個(gè)體、選擇算子和結(jié)束判斷等。由于遺傳機(jī)制合理，并且自適應(yīng)調(diào)整交叉率和變異率，該算法在取得良好分割效果的同時(shí)降低了算法的復(fù)雜度，較好地提高了算法的收斂速度。

2 遺傳算法

一般的遺傳算法（Genetic Algorithm，GA）[2]分為 4 部分：編碼機(jī)制（encoding mechanism）、控制參數(shù)、適應(yīng)度函數(shù)（fitness function）、遺傳算子（genetic operator）。 編碼機(jī)制是GA的基礎(chǔ)，GA不是對(duì)研究對(duì)象直接進(jìn)行討論，而是通過某種編碼機(jī)制將對(duì)象統(tǒng)一賦予按一定順序排列成串的特定符號(hào)（字母）。在GA中適應(yīng)度函數(shù)描述每個(gè)個(gè)體的適宜程度。遺傳算子中最重要的有3種：選擇（selection）、交換 （crossover）和變異 （mutation）。通過選擇使適應(yīng)度大即優(yōu)良的個(gè)體有較大的存在機(jī)會(huì)，而適應(yīng)度小即低劣的個(gè)體繼續(xù)存在的機(jī)會(huì)也較小。交換算子有多種形式，最簡單的是單點(diǎn)交換（single point crossover），即從群體中隨機(jī)取出2個(gè)字符串，隨機(jī)確定交叉點(diǎn)，2個(gè)字符串互換再重新連接得到2個(gè)新字符串。得到的新字符串不一定都能保留在下一代，需和原來的字符串進(jìn)行比較，保留適應(yīng)度大的，交換后可進(jìn)行突變。遺傳算子用來改變字符串的某個(gè)位置上的字符。

3 自適應(yīng)遺傳視頻運(yùn)動(dòng)對(duì)象分割算法

自適應(yīng)算法的基本步驟如下：1）自適應(yīng)初代個(gè)體；2）自適應(yīng)選擇算子；3）交換變異算子；4）自適應(yīng)終止準(zhǔn)則；5）重復(fù)步驟1）～4），直到進(jìn)化結(jié)束滿足條件為止。

3.1 適應(yīng)度評(píng)估

在遺傳算法中，適應(yīng)度是衡量個(gè)體優(yōu)劣的標(biāo)志，優(yōu)勝劣汰是以個(gè)體適應(yīng)度的大小為依據(jù)的。適應(yīng)度函數(shù)決定了個(gè)體遺傳到下一代機(jī)會(huì)的大小，設(shè)計(jì)一個(gè)好的適應(yīng)度函數(shù)可提高遺傳算法的分割效率[3－4]。由于在視頻分割中通常采用均方誤差（Mean Square Error，MSE）和絕對(duì)誤差總和（Sum of Absolute Difference，SAD）作為目標(biāo)函數(shù)[5]，遺傳自適應(yīng)分割算法則采用與絕對(duì)誤差總和相關(guān)的函數(shù)作為適應(yīng)度函數(shù)，保證誤差越小的染色體適應(yīng)度值相應(yīng)越高。

算法中的適應(yīng)度函數(shù)F定義為

式中：si為當(dāng)前群體中第i個(gè)染色體的絕對(duì)誤差總和，F(xiàn)（si）為其適應(yīng)度值，N是當(dāng)前群體包含的個(gè)體數(shù)目，median（）為中值函數(shù)。適應(yīng)度函數(shù)值較大的存在機(jī)會(huì)大，為優(yōu)秀個(gè)體，繼續(xù)存在的機(jī)會(huì)也較大。這樣就可以節(jié)省適應(yīng)度評(píng)估的時(shí)間，提高算法的運(yùn)行速度。

3.2 自適應(yīng)初代個(gè)體選擇

由于初代個(gè)體的優(yōu)劣影響到整個(gè)進(jìn)化過程的收斂速度。現(xiàn)有的遺傳分割算法通常采用隨機(jī)或中心偏離的方法來選擇初代個(gè)體，在此采用二者相結(jié)合的方法。

首先在視頻圖像區(qū)域內(nèi)隨機(jī)選取一些位置的對(duì)應(yīng)塊作為初代子個(gè)體，然后選取其區(qū)域中心及附近位置的對(duì)應(yīng)塊作為初代個(gè)體群，其中包括區(qū)域中心子個(gè)體及周圍上、下、左和右方4個(gè)位置對(duì)應(yīng)的5個(gè)塊作為初代個(gè)體群。中心偏離方法利用視頻圖像的時(shí)間相關(guān)性，當(dāng)圖像運(yùn)動(dòng)較為緩慢時(shí)，優(yōu)秀個(gè)體大多分布在中心區(qū)域，因而可保證初代個(gè)體的質(zhì)量。當(dāng)圖像劇烈運(yùn)動(dòng)時(shí)，在初代個(gè)體群的選擇中進(jìn)一步利用視頻圖像的時(shí)空相關(guān)性[6－7]，以保證初代個(gè)體的質(zhì)量。計(jì)算當(dāng)前選擇塊周圍上、下、左和右方4個(gè)塊的SAD值，分別與當(dāng)前塊的SAD值求絕對(duì)差。根據(jù)經(jīng)驗(yàn)值，若差值小于閾值450，則選出作為初始個(gè)體；否則遺棄，作為下次選擇的對(duì)象。

3.3 自適應(yīng)選擇算子

選擇算子是將當(dāng)前群體中適應(yīng)度較高的個(gè)體按照某種規(guī)則遺傳到下一代群體中的操作，在選擇中，優(yōu)勢個(gè)體以較大的概率被復(fù)制到下一代，而劣勢個(gè)體則要面對(duì)一定的壓力。選擇的目標(biāo)就在于使種群中個(gè)體的適應(yīng)度值增大。但由于在遺傳算法執(zhí)行的不同階段，個(gè)體間差異也不同，若用相同的選擇策略可能會(huì)導(dǎo)致如下問題：當(dāng)個(gè)體差異較大時(shí)，選擇概率大的個(gè)體可能在淘汰掉劣勢個(gè)體的同時(shí)，也遺失了存在于劣勢個(gè)體中的部分優(yōu)良基因；當(dāng)個(gè)體差異很小時(shí)，可能會(huì)由于選擇概率不夠而使搜索趨于隨機(jī)化，導(dǎo)致收斂速度慢。因此，采用一種隨著算法的執(zhí)行和個(gè)體的變化而不斷變化的自適應(yīng)選擇方案。

采用與適應(yīng)度成一定正比比例的概率。首先計(jì)算出群體中所有個(gè)體適應(yīng)度的總和，其次計(jì)算出每個(gè)個(gè)體的相對(duì)適應(yīng)度大小，即每個(gè)個(gè)體在所有個(gè)體適應(yīng)度總和中所占的比例。根據(jù)適應(yīng)度以某種概率選擇個(gè)體，適應(yīng)度越高，它被重復(fù)選擇的可能性越大，而適應(yīng)度小的個(gè)體往往未能選中，從而實(shí)現(xiàn)優(yōu)勝劣汰。若相對(duì)適應(yīng)度大于80%，則將此個(gè)體遺傳到下一代群體中；若相對(duì)適應(yīng)度為70%～80%，則將它留下來，繼續(xù)組合新的群體并跟蹤；若相對(duì)適應(yīng)度小于70%，則認(rèn)為此個(gè)體適應(yīng)度較小，選擇概率小，甚至丟棄。

3.4 交換算子和變異算子

在遺傳算法中，交叉是產(chǎn)生新個(gè)體的主要手段。交叉算子的好壞直接影響算法的收斂性能。以某個(gè)概率p隨機(jī)互換兩個(gè)個(gè)體之間的基因片段，產(chǎn)生新的基因型。運(yùn)算過程為：首先對(duì)群體中的個(gè)體進(jìn)行兩兩隨機(jī)配對(duì)，然后對(duì)每一對(duì)相互配對(duì)的個(gè)體，隨機(jī)設(shè)置一個(gè)基因位置為交叉點(diǎn)，交叉概率為0.6～0.8。若染色體的長度為L，則共有L－1個(gè)可能的交叉點(diǎn)位置。最后對(duì)每一對(duì)相互配對(duì)的個(gè)體，依設(shè)定的交叉概率p在其交叉點(diǎn)處相互交換兩個(gè)個(gè)體的部分染色體，從而產(chǎn)生出兩個(gè)新的個(gè)體。

變異操作采用自適應(yīng)變異算子來隨機(jī)改變個(gè)體某一位的值，按照一定的概率從中選取若干個(gè)體，按一定的策略進(jìn)行變異操作，即改變碼值某一位的值。變異運(yùn)算增加了群體的多樣性，避免算法過早陷入局部最優(yōu)解。進(jìn)行取反運(yùn)算，1變0或0變1，或者采用同或或異或算子，這是一種二元變異操作，需要兩個(gè)染色體個(gè)體參與。

當(dāng)兩個(gè)染色體進(jìn)行同或操作時(shí)，若兩個(gè)染色體同一基因位上的等位基因相同，則變異后的染色體該基因位取1，否則取0。對(duì)于異或算子則正好與同或相反，若兩個(gè)染色體同一基因位上的等位基因相同，則變異后的染色體該基因位取0，否則取1。同或或異或算子使同一基因位上的基因經(jīng)過變異后，至少有一個(gè)0和一個(gè)1同時(shí)存在，可以有效地保持同一基因位上等位基因的多樣性，從而最大限度地避免遺傳算法早熟現(xiàn)象的發(fā)生。

自適應(yīng)變異操作對(duì)于適應(yīng)度值高于70%的個(gè)體，變異算子設(shè)置較小值為0.3%，這樣可以使其較小變異，從而進(jìn)入下一代。而對(duì)于適應(yīng)度值低于70%的個(gè)體，變異算子設(shè)置較大值為3%，使該個(gè)體被淘汰掉。在保持群體多樣性的同時(shí)，保證了算法的收斂性。

3.5 自適應(yīng)終止準(zhǔn)則

為了避免算法發(fā)生“過早收斂”和搜索過程中的“停滯現(xiàn)象”，當(dāng)算法執(zhí)行到最大迭代次數(shù)G，群體的最高適應(yīng)度值仍未發(fā)生變化時(shí)，具有最高適應(yīng)度值的個(gè)體灰度值為最佳閾值，算法結(jié)束。否則重復(fù)以上過程，并用找到的最佳閾值分割視頻圖像。

3.6 其他參數(shù)

設(shè)染色體長度L為8，種群數(shù)P為12，繁衍代數(shù)G為20，交叉概率和變異概率根據(jù)個(gè)體的適應(yīng)度自適應(yīng)調(diào)節(jié)。算法流程圖如圖1所示。

4 仿真分析

為驗(yàn)證算法的有效性，在配置為P4 CPU 3.0 GHz，512 Mbyte內(nèi)存以上的計(jì)算機(jī)上分別采用最大類間方差法（Otsu）和AGS對(duì)視頻圖像進(jìn)行分割實(shí)驗(yàn)。

實(shí)驗(yàn)1：視頻序列forman分割圖像結(jié)果的比較。

AGS算法中設(shè)置參數(shù)為：染色體長度L為8，種群數(shù)P為12，繁衍代數(shù)G為20，交叉概率和變異概率分別采用自適應(yīng)調(diào)節(jié)。對(duì)于視頻序列forman（352×288）的第5幀，分別使用灰度閾值（threshold）分割法、Otsu算法和AGS算法，分割實(shí)驗(yàn)結(jié)果如圖2所示。

實(shí)驗(yàn)2：視頻序列football分割圖像結(jié)果的比較。

AGS算法中設(shè)置參數(shù)為：染色體長度L為8，種群數(shù)P為12，繁衍代數(shù)G分別為5，10和20，交叉概率和變異概率自適應(yīng)調(diào)節(jié)，采用視頻序列football（352×240）的第1幀，分割實(shí)驗(yàn)結(jié)果如圖3所示。

實(shí)驗(yàn)3：分割時(shí)間的比較。

采用視頻序列missamerica的第1幀，分別用OTSU和改進(jìn)的AGS方法對(duì)運(yùn)行時(shí)間進(jìn)行比較。其中AGS算法的參數(shù)為：染色體長度L為8，種群數(shù)P為12，交叉概率和變異概率采用自適應(yīng)調(diào)節(jié)，分割時(shí)間如表1所示。

表1 序列missamerica分割時(shí)間

在實(shí)驗(yàn)1中，對(duì)視頻序列forman進(jìn)行分割比較，結(jié)果表明：當(dāng)AGS算法參數(shù)選擇合適的情況下，灰度閾值法和OTSU算法的分割結(jié)果均不如AGS算法分割效果好。在實(shí)驗(yàn)2中，對(duì)視頻序列football進(jìn)行分割，改變AGS算法的繁衍代數(shù)，分別取5，10和20。通過比較可以看出，繁衍代數(shù)越多，分割效果越好。在實(shí)驗(yàn)3中，分別用OTSU算法和AGS算法分割視頻序列missamerica的第1幀，AGS算法進(jìn)化12代左右就能得到最佳閾值，分割時(shí)間也減少了約0.05 s。

5 小結(jié)

視頻對(duì)象分割是視頻壓縮編碼中的重要環(huán)節(jié)，其優(yōu)劣直接決定整個(gè)編碼性能，研究視頻分割具有重要意義。提出一種自適應(yīng)遺傳視頻運(yùn)動(dòng)對(duì)象分割算法，引入自適應(yīng)進(jìn)化機(jī)制，包括初代個(gè)體的選擇，進(jìn)化算子及進(jìn)化結(jié)束判決，利用視頻圖像的內(nèi)在相關(guān)性來加速進(jìn)化過程，能夠與不確定性的進(jìn)化過程較好地匹配。仿真結(jié)果表明提出的算法可以實(shí)現(xiàn)較為精確的視頻圖像分割，同時(shí)保持較低的運(yùn)算復(fù)雜度。

[1] LIU Lijie，F(xiàn)AN Guoliang.Combined key-frame extraction and objectbased video segmentation[J].IEEE Trans.Circuit and System for Video Technology，2005，15（7）：869-884.

[2] HUA Gang，ZHENG Nanning，XUE Jianru.An approach based on improved genetic algorithm to selecting the threshold automatically in edge detection and its application in computer vision system[J].Mini-micro System，2002，23（3）：318-321.

[3] MO Xiaoran，WILSON R.Video modelling and segmentation using Gaussian mixture models[C]//Proc.IEEE International Conference on Pattern Recognition.Cambridge，UK：Institute of ElectricalandElectronics Engineers Inc，2004：854-857.

[4]BLEKAS K，LIKAS A，GALATSANOS N P，et al.A spatially constrained mixture model for image segmentation[J].IEEE Trans.Neural Networks，2005，16（2）：494-498.

[5] 高韜，于明.背景漸變的視頻對(duì)象分割算法研究及實(shí)現(xiàn)[J].電視技術(shù)，2006，30（7）：84-86.

[6] HAYIT G，JACOB G，ARNALDO M.A probabilistic framework for spatio-temporal video representation and indexing[C]//Proc.the 7th European Conference on Computer Vision.New York： Springer，2002：461-475.

[7] HAYIT G， JACOB G，ARNALDO M.Probabilistic spacetime video modeling via piecewise GMM[J].IEEE Trans.Pattern Analysis and Machine Intelligence，2004，26（3）：384-396.

樊養(yǎng)余（1960-），教授，博士生導(dǎo)師，主要從事強(qiáng)噪聲中信號(hào)檢測與恢復(fù)、數(shù)據(jù)壓縮、信息安全、目標(biāo)識(shí)別等方面的研究。