自適應遺傳視頻運動對象分割算法*

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

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

1 引言

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

2 遺傳算法

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

3 自適應遺傳視頻運動對象分割算法

自適應算法的基本步驟如下：1）自適應初代個體；2）自適應選擇算子；3）交換變異算子；4）自適應終止準則；5）重復步驟1）～4），直到進化結束滿足條件為止。

3.1 適應度評估

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

算法中的適應度函數F定義為

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

3.2 自適應初代個體選擇

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

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

3.3 自適應選擇算子

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

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

3.4 交換算子和變異算子

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

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

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

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

3.5 自適應終止準則

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

3.6 其他參數

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

4 仿真分析

為驗證算法的有效性，在配置為P4 CPU 3.0 GHz，512 Mbyte內存以上的計算機上分別采用最大類間方差法（Otsu）和AGS對視頻圖像進行分割實驗。

實驗1：視頻序列forman分割圖像結果的比較。

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

實驗2：視頻序列football分割圖像結果的比較。

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

實驗3：分割時間的比較。

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

表1 序列missamerica分割時間

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

5 小結

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

[1] LIU Lijie，FAN 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] 高韜，于明.背景漸變的視頻對象分割算法研究及實現[J].電視技術，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-），教授，博士生導師，主要從事強噪聲中信號檢測與恢復、數據壓縮、信息安全、目標識別等方面的研究。