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

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

1 引言

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

2 遺傳算法

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

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

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

3.1 適應度評估

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

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

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

3.2 自適應初代個體選擇

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

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

3.3 自適應選擇算子

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

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

3.4 交換算子和變異算子

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

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

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

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

3.5 自適應終止準則

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

3.6 其他參數(shù)

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

4 仿真分析

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

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

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

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

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

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

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

表1 序列missamerica分割時間

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

5 小結(jié)

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

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