導(dǎo)語：如何才能寫好一篇貪婪算法的基本原理，這就需要搜集整理更多的資料和文獻(xiàn)，歡迎閱讀由公務(wù)員之家整理的十篇范文，供你借鑒。

篇1

關(guān)鍵詞：遺傳算法；貪婪思想；進(jìn)化逆轉(zhuǎn)；旅行商問題

中圖分類號： TP18 文獻(xiàn)標(biāo)識碼： A

0引言

遺傳算法（GA）是一種進(jìn)化算法，其基本原理是仿效生物界中的“物競天擇、適者生存”的演化法則。最早是由美國密歇根大學(xué)Holland教授提出，在20世紀(jì)80年代左右得到了進(jìn)一步發(fā)展。遺傳算法是把問題參數(shù)編碼為染色體，再利用迭代的方式進(jìn)行選擇、交叉以及變異等運(yùn)算來交換種群中染色體的信息，最終生成符合優(yōu)化目標(biāo)的染色體。目前遺傳算法主要多用于優(yōu)化問題[1]、圖像處理[2]、通訊工程[3]等領(lǐng)域。

旅行商問題（TSP）是典型的組合優(yōu)化問題，求解TSP問題傳統(tǒng)的算法有：窮舉法、分支限界法、動態(tài)規(guī)劃法[4-5]等。高海昌等[6] 對蟻群算法、遺傳算法、模擬退火算法、禁忌搜索、神經(jīng)網(wǎng)絡(luò)、粒子群優(yōu)化算法、免疫算法等進(jìn)行了論述。隨著研究的深入，許多改進(jìn)的算法不斷涌現(xiàn)，李瑋[7]采用矩陣編碼、交叉、變異的遺傳算法來解決TSP問題，雷玉梅[8]提出了一種分而治之的遺傳算法思想，姚明海[9]采用遺傳算法與其他智能算法結(jié)合的思想來解決問題。遺傳算法因其高效的搜索能力成為了解決TSP問題的有效方法之一。雖然遺傳算法能夠較為成功地求解TSP問題，但也存在搜索較慢的問題，特別是遺傳算法在解決TSP問題時容易出現(xiàn)早熟的問題。因此本文在交叉操作之前，將一半的當(dāng)前種群替換成隨機(jī)種群來防止早熟，再融合貪婪思想產(chǎn)生的初始群體[10]和貪婪思想引導(dǎo)的交叉算子[11]來加快收斂速度，用改進(jìn)的變異算子[12]進(jìn)行操作，由此而得到最優(yōu)解。

5 結(jié)束語

文章在基本的遺傳算法基礎(chǔ)上提出一定改進(jìn)，引用貪婪思想產(chǎn)生質(zhì)量相對較好的初始種群，同時又在貪婪思想引導(dǎo)的交叉操作操作之前，把當(dāng)前較差的一半種群替換成隨機(jī)種群，二者結(jié)合來提升收斂速度又防止了陷入局部最優(yōu)。實驗證明，本文研發(fā)的改進(jìn)遺傳算法較好地解決了TSP問題中收斂速度和早熟的問題，且具有較強(qiáng)的魯棒性，通用于類似的組合優(yōu)化問題。

參考文獻(xiàn)：

[1]袁滿，劉耀林.基于多智能體遺傳算法的土地利用優(yōu)化配置[J].農(nóng)業(yè)工程學(xué)報， 2014，30（1）： 191-199.

[2]門慧勇.基于遺傳算法的圖像分割優(yōu)化研究[D].長春：東北師范大學(xué)，2012.

[3]陳俠.基于改進(jìn)的遺傳算法的網(wǎng)絡(luò)編碼優(yōu)化方法研究[D].武漢：華中科技大學(xué)，2012.

[4]周康，強(qiáng)小利，同小軍，等.求解TSP算法[J].計算機(jī)工程與應(yīng)用，2007，43（29）：43-47，85.

[5]趙頌華.城市公共資源監(jiān)管設(shè)計新思維[J].科技資訊，2015（15）：31-32.

[6]高海昌，馮博琴，朱利.智能優(yōu)化算法求解TSP問題[J].控制與決策，2006，21（3）：241-247，252.

[7]李瑋.關(guān)于旅行商問題的改進(jìn)遺傳算法[D].重慶：重慶大學(xué)，2004.

[8]雷玉梅.基于改進(jìn)遺傳算法的大規(guī)模TSP問題求解方案[J].計算機(jī)與現(xiàn)代化，2015（2）：34-39.

[9]姚明海，王娜，趙連朋.改進(jìn)的模擬退火和遺傳算法求解TSP問題[J].計算機(jī)工程與應(yīng)用，2013， 49（14）：60-65.

[10]于瑩瑩，陳燕，李桃迎.改進(jìn)的遺傳算法求解旅行商問題[J].控制與決策，2014，29（8）： 1483-1488.

[11]謝勝利，唐敏，董金祥.求解TSP問題的一種改進(jìn)的遺傳算法[J].計算機(jī)工程與應(yīng)用，2002， 38（8）： 58-60，245.

篇2

【關(guān)鍵詞】壓縮感知；貪婪算法；線性規(guī)劃；隨機(jī)投影

1.引言

當(dāng)前大部分?jǐn)?shù)據(jù)采集系統(tǒng)都是基于傳統(tǒng)的香農(nóng)采樣定理來設(shè)計，按照這種方式采集的數(shù)據(jù)能夠充分表示原始信號，但是它們存在較大的冗余。因此，這些方法往往導(dǎo)致采集數(shù)據(jù)的泛濫和傳感器的浪費(fèi)。研究如何根據(jù)信號的一些特征來實現(xiàn)低于乃奎斯特采樣頻率的采集，以減少所需采集的數(shù)據(jù)量具有重要的意義。在過去的30年里，從噪聲中提取正弦信號的方法吸引了許多科學(xué)家的關(guān)注，但是利用信號的可壓縮性進(jìn)行數(shù)據(jù)采樣卻是一個新興的課題。其起源于對具有有限信息率信號（finite-rate-of-innovation signal，即單位時間內(nèi)具有有限自由度的信號）進(jìn)行采集的研究，利用固定的結(jié)構(gòu)性基函數(shù)（structured fixed deterministic sampling kernels）以兩倍于新息率而不是兩倍于奈奎斯特采樣頻率對連續(xù)信號進(jìn)行采集。Donoho等人提出的壓縮感知方法是一種可以廣泛應(yīng)用于可壓縮信號的采集方法。該方法所需要的傳感器數(shù)目大大減少，采集到的數(shù)據(jù)也具有更小的冗余度。因此，該理論提出后立即吸引了眾多科學(xué)家的關(guān)注，目前我國關(guān)于壓縮感知方法的研究也已開始起步，相信不久將有更多的人加入到關(guān)于壓縮感知的研究行列。

壓縮感知采集方法并不是對數(shù)據(jù)直接進(jìn)行采集，而是通過一組特定波形去感知信號，即將信號投影到給定波形上面（衡量與給定波形的相關(guān)度），感知到一組壓縮數(shù)據(jù)，最后利用最優(yōu)化的方法實現(xiàn)對壓縮數(shù)據(jù)解密，估計出原始信號的重要信息。壓縮感知關(guān)鍵的問題是如何給定用來感知信號的波形才能有效地恢復(fù)出原始信號的重要信息。涉及的關(guān)鍵因素在于給定的波形要與可以用來壓縮原始信號的波形組均不相干，并且不相干程度越高，感知數(shù)據(jù)包含的信息量越大，為準(zhǔn)確獲取重建原始信號所需的感知數(shù)據(jù)量就越少。Tao等人提出的受限等距性（Restricted Isometry Property，RIP）[2，3]、一致不確定性原理（Uniform Uncertainty Principle，UUP）和準(zhǔn)確重構(gòu)原理（Exact Reconstruction Principle，ERP）[4，5]進(jìn)一步回答了如何從壓縮數(shù)據(jù)中方便地提取信號有用信息的充分條件。

2.壓縮感知中的信息獲取方法

本節(jié)我們將討論從感知到的數(shù)據(jù)中估計原始信號的幾種常見實用方法：基追蹤算法（Basis Pursuit，BP）、貪婪算法（Matching Pursuit，MP）、迭代閾值算法（iterative threshholding methods，iterative shrinkage algorithm）等。

2.1 基追蹤算法

首先需要指出的是基追蹤算法并不是一個最優(yōu)化原則，其原理是上述討論的給定一些限制條件后，通過極小化z，范數(shù)町以獲得最稀疏的解。與之問題等價的標(biāo)準(zhǔn)線性規(guī)劃問題為

極小化Z范數(shù)的方法能夠有效解決壓縮感知中的恢復(fù)問題，但是當(dāng)結(jié)合其它的一些先驗知識后，該問題可以被更加有效地解決。在此，我們僅簡單介紹貝葉斯壓縮感知方法（Bayesian compressed Sensing，BCS）和基于模型的壓縮感知方法（model based compressed sensing）。Ji等人提出的BCS借助傳統(tǒng)的貝葉斯方法和機(jī)器學(xué)習(xí)中的主動學(xué)習(xí)方法（active learning），通過將關(guān)于稀疏性的先驗信息用垂直先驗分布（hierarchical prior）來建模，提出了自適應(yīng)的感知方法以及相應(yīng)的恢復(fù)方法。而Baraniuk等人提出的針對基于模型可壓縮信號（model compressible signals）的壓縮感知方法中利用小波樹模型和塊稀疏模型，僅需要與稀疏程度相當(dāng)?shù)臏y度數(shù)即可實現(xiàn)信號的魯棒性恢復(fù)。

2.2 矩陣填充問題

矩陣填充理論與壓縮感知理論相比，壓縮感知理論利用的是信號在一組基下的稀疏性，而矩陣填充理論利用的是利用矩陣特征值的稀疏性（即低秩性）。假設(shè)一個秩為r的低秩矩陣X，坩硒是一個將矩陣中位于支撐域以外的元素投影成零的正交投影。即：

那么，x能夠通過如下的最優(yōu)化方法從部分觀測y中準(zhǔn)確的重構(gòu)出來：

該問題的求解同樣是一個NP難問題。當(dāng)部分觀測是從矩陣X中隨機(jī)選取的元素時，Candes指出該問題可以通過如下的凸規(guī)劃問題加以求解：

實際上，部分觀測矩陣l，是矩陣X在一些隨機(jī)矩陣上的隨機(jī)投影時，矩陣X同樣可以從觀測矩陣l中準(zhǔn)確地重構(gòu)出來。Ma等人進(jìn)一步指出，當(dāng)一個低秩的矩陣被稀疏噪聲污染的時候，利用噪聲的稀疏性和矩陣的低秩特性，同樣能夠把原始矩陣準(zhǔn)確地重構(gòu)出來，該理論被成功地用于人臉識別和視頻跟蹤中。

篇3

Abstract:The paper comment on digital image fusion what it researched maily,and introduce some typical technique of image fusion.

關(guān)鍵詞:數(shù)字圖像融合;主成分分析;演化計算;神經(jīng)網(wǎng)絡(luò);小波變換;模糊算法

Key words: digital image fusion;principal components analysis;evolutionary computation;neural network;wavelet transform;fuzzy algorithm

中圖分類號:TP399 文獻(xiàn)標(biāo)識碼:A文章編號:1006-4311(2010)20-0099-01

0引言

二十世紀(jì)九十年代以來,圖像融合技術(shù)的研究呈不斷上升的趨勢,應(yīng)用領(lǐng)域也遍及遙感圖像處理,可見光圖像處理,紅外圖像處理,醫(yī)學(xué)圖像處理等。尤其是近幾年來,多傳感器圖像融合技術(shù)已成為機(jī)器人,智能制造,智能交通,醫(yī)療診斷,遙感,保安,軍事應(yīng)用等領(lǐng)域的研究熱點問題。

1數(shù)字圖像融合的主要研究內(nèi)容

數(shù)字圖像融合是將兩個或者兩個以上的傳感器在同一時間(或不同時間)獲取的關(guān)于某個具體場景的圖像或者圖像序列信息加以綜合,以生成一個新的有關(guān)此場景的解釋,而這個解釋是從單一傳感器獲取的信息中無法得到的。圖像融合的目的是減少不確定性,其作用包括:①圖像增強(qiáng)。通過綜合來自多傳感器(或者單一傳感器在不同時間)的圖像,獲得比原始圖像清晰度更高的新圖像。②特征提取。通過融合來自多傳感器的圖像更好地提取圖像的特征,如線段,邊緣等。③去噪。④目標(biāo)識別與跟蹤。⑤三維重構(gòu)。

2圖像融合研究的發(fā)展現(xiàn)狀和研究熱點

多傳感器圖像融合是一個正在興起的,并有著廣泛應(yīng)用前景的研究領(lǐng)域。當(dāng)前圖像融合在特征級的研究重點在于提高融合圖像的空間分辨率的同時,盡量保持原圖像的光譜特征,從而保證后續(xù)分析理解的有效性。另外,圖像序列以及視頻信息的融合問題也是非常有意義的研究課題。

3幾類典型的數(shù)字圖像融合理論與方法

3.1 主成分分析法主成分分析法的幾何意義是把原始特征空間的特征軸旋轉(zhuǎn)到平行于混合集群結(jié)構(gòu)軸的方向去,得到新的特征軸。實際操作是將原來的各個因素指標(biāo)重新組合,組合后的新指標(biāo)是互不相關(guān)的。在由這些新指標(biāo)組成的新特征軸中,只用前幾個分量圖像就能完全表征原始集群的有效信息,圖像中彼此相關(guān)的數(shù)據(jù)被壓縮,而特征得到了突出。

3.2 演化計算法演化計算是模擬自然界生物演化過程產(chǎn)生的隨機(jī)優(yōu)化策略與技術(shù)。它具有穩(wěn)健性,通用性等優(yōu)點和自組織,自適應(yīng),自學(xué)習(xí)等職能特征,下面是幾種常用的演化計算方法:

3.2.1 遺傳算法GA(genetic algorithm)遺傳算法的基本思想是基于達(dá)爾文進(jìn)化論和孟德爾遺傳學(xué)說的。所以在算法中要用到進(jìn)化和遺傳學(xué)的概念,比如串(在算法中為二進(jìn)制串,對應(yīng)于遺傳學(xué)中的染色體);群體(個體的集合,串是群體的元素);基因(串中的元素,如有一個串S=1001,其中1,0,0,1這四個元素分別成為基因);基因位置;串結(jié)構(gòu)空間;參數(shù)空間;非線性;適應(yīng)度等。遺傳算法的原理可以簡要給出如下:

Choose an initial population;Determine the fitness of each individual;Perform selection.

Repeat:Perform crossover;Perform mutation;Determine the fitness of each individual;Perform selection;

Until some stopping criterion applies.

這兒所指的某種結(jié)束準(zhǔn)則一般是指個體的適應(yīng)度達(dá)到給定的閾值,或者個體的適應(yīng)度的變化率為零。

3.2.2 粒子群算法(PSO)粒子群優(yōu)化算法是一種進(jìn)化計算技術(shù),源于對鳥群捕食的行為研究。設(shè)想有這樣一個場景:一群鳥在隨機(jī)搜索食物,在這個區(qū)域里只有一塊食物,所有的鳥都不知道食物在哪里,但是他們知道當(dāng)前的位置離食物還有多遠(yuǎn),那么找到食物的最優(yōu)策略是什么呢?最簡單有效的方法就是搜尋目前離食物最近的鳥的周圍區(qū)域。PSO算法從這種模型中得到啟示并用于解決優(yōu)化問題。PSO中,每個優(yōu)化問題的解都是搜索空間中的一只鳥,我們稱之為“粒子”。所有的粒子都有一個由被優(yōu)化的函數(shù)決定的適應(yīng)值,每個粒子還有一個速度決定他們飛翔的方向和距離,然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索。PSO初始化為一群隨機(jī)粒子(隨機(jī)解),然后通過迭代找到最優(yōu)解。

3.2.3 蟻群算法蟻群算法(ant colony optimization,ACO),又稱螞蟻算法,是一種用來在圖中尋找優(yōu)化路徑的機(jī)率型技術(shù)。它由Marco Dorigo于1992年在他的博士論文中引入,其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。蟻群算法是一種求解組合最優(yōu)化問題的新型通用啟發(fā)式方法,該方法具有正反饋、分布式計算和富于建設(shè)性的貪婪啟發(fā)式搜索的特點。

3.3 神經(jīng)網(wǎng)絡(luò)法神經(jīng)網(wǎng)絡(luò)法是在現(xiàn)代神經(jīng)生物學(xué)和認(rèn)知科學(xué)對人類信息處理研究成果的基礎(chǔ)上提出的,它有大規(guī)模并行處理、連續(xù)時間動力學(xué)和網(wǎng)絡(luò)全局作用等特點,將存儲體和操作合二為一?，F(xiàn)實世界中圖像噪聲總是不可避免地存在,甚至有時信息會有缺失,在這種情況下,神經(jīng)網(wǎng)絡(luò)融合法也能以合理的方式進(jìn)行推理。

3.4 小波變換法自從1989年Mallat提出了二維小波分解方法后,小波變換在圖像處理中迅速得到了廣泛的應(yīng)用。在圖像融合領(lǐng)域,小波變換方法也是一種重要的方法。對于圖像融合,在頻率域進(jìn)行比在時間域進(jìn)行更為有效,融合算法的設(shè)計必須把融合的技術(shù)目的和圖像的頻率域表現(xiàn)結(jié)合起來考慮。

3.5 模糊圖像融合所謂模糊性是指客觀事物在形態(tài)及類屬方面的不分明性,其根源是在類似事物間存在一系列過渡狀態(tài),它們互相滲透,互相貫通,使得彼此之間沒有明顯的分界線。圖像融合模糊算法的基本原理是利用模糊隸屬度函數(shù)量化不同目標(biāo)類型和相應(yīng)像素值之間的關(guān)系。

4結(jié)束語

圖像融合是一個眾多學(xué)科感興趣的十分活躍的研究領(lǐng)域。圖像融合也還有許多問題急需解決。首先,圖像融合技術(shù)缺乏理論指導(dǎo)。雖然關(guān)于圖像融合技術(shù)的公開報道很多,但每篇文章都是針對一個具體的應(yīng)用問題,對圖像融合技術(shù)還沒有一個統(tǒng)一的理論框架。所以,建立圖像融合的理論框架是目前的一個發(fā)展方向。再者由于圖像的特殊性,在設(shè)計圖像融合算法時一定要考慮到計算速度和所需的存儲量,如何得到實時、可靠、穩(wěn)定、實用的融合算法和硬件電路是目前研究的一個熱點。另外,建立客觀的圖像融合技術(shù)評價標(biāo)準(zhǔn)也是急需解決的問題。

參考文獻(xiàn):

[1]覃征等.數(shù)字圖像融合[M].西安交通大學(xué)出版社,2004.

篇4

關(guān)鍵詞：蟻群算法；參數(shù)選擇；人工設(shè)置；自適應(yīng)調(diào)整

中圖分類號：TP312文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2010)20-5588-03

Study on Parameter Selection of Ant Colony Algorithm

HUANG Shao-rong

(Department of Information Management, Guangdong Justice Police Vocational College, Guangzhou 510520, China)

Abstract: Ant colony algorithm (ACA) is a new stochastic optimization algorithm which shows many excellent characters and has succeeded in solving many difficult optimization problems and NP-hard problems. The parameters have an important role in the result of ant colony algorithm. This paper introduces the theory of ACA based on Traveling Salesman Problem (TSP), analyses the function and influence of parameters in ACA, and then introduces the methods of parameters selection in two ways: set the parameters manually and adjust the parameters adaptively. At last, it has compares and summarizes each method.

Key words: ant colony algorithm; parameter selection; manually set; adaptively adjust

如何為元啟發(fā)式算法設(shè)置合理的參數(shù)是啟發(fā)式算法理論和應(yīng)用研究的一個重要方向。蟻群算法作為最成功的元啟發(fā)式算法之一，優(yōu)化性能很大程度上依賴于參數(shù)的設(shè)置，但要對其參數(shù)進(jìn)行最優(yōu)設(shè)置是一項復(fù)雜的工作，往往需要經(jīng)過大量的測試，這成為蟻群算法進(jìn)一步推廣應(yīng)用的一個瓶頸。

1 基本蟻群算法

蟻群算法是由Colorni、Dorigo和Maniezzo于20世紀(jì)90年代初通過模擬自然界中螞蟻集體尋徑的行為而提出的一種基于種群的啟發(fā)式仿生進(jìn)化算法[1]。由于蟻群算法具有分布性、并行性、全局性、魯棒性強(qiáng)等特點，已經(jīng)在求解NP-難問題和眾多應(yīng)用問題中顯示出良好的優(yōu)化性能和發(fā)展?jié)摿Α?/p>

以TSP問題為例，采用常用的any-cycle模型，簡單闡述蟻群算法的基本原理：

設(shè)有m只螞蟻，每只螞蟻訪問n個城市，規(guī)定螞蟻走合法路線，除非周游完成，不允許轉(zhuǎn)到已訪問城市。初始時刻，各路徑的信息量τij(0)相等，m只螞蟻被放置到不同的城市上。螞蟻k（k=1,2...,m）在運(yùn)動過程中，根據(jù)各條路徑上信息量和前方路徑的長短決定轉(zhuǎn)移方向，Pkij (t)表示在t時刻螞蟻k由城市i轉(zhuǎn)移到j(luò)的概率：

(1)

其中：

allowed k―螞蟻k下一步允許轉(zhuǎn)移到的城市集合，隨k的行進(jìn)而改變；

τij(t)―t時刻路徑（i,j）上的信息量；

α―信息啟發(fā)式因子；

β―期望啟發(fā)式因子；

ηij(t)―城市i轉(zhuǎn)到j(luò)的期望程度，一般?。害莍j(t)=1/dij（dij表示相鄰兩個城市的距離）；

當(dāng)螞蟻k完成周游后，根據(jù)式(2)-(4)更新螞蟻訪問過的每一條邊上的信息素：

τij(t+n)=(1-ρ)?τij(t)+ Δτij(t) (2)

(3)

(4)

其中：

ρ―信息素?fù)]發(fā)系數(shù)；

Δτij(t)―本次循環(huán)中路徑(i,j)上的信息量增量；

Δτkij(t)―螞蟻k本次循環(huán)中在路徑(i,j)上留下的信息素數(shù)量；

Lk―螞蟻k環(huán)游一周的路徑長度；

Q―信息素強(qiáng)度因子，常量。

眾多的研究已經(jīng)表明蟻群算法具有很強(qiáng)的發(fā)現(xiàn)較好解的能力，但作為啟發(fā)式概率型優(yōu)化算法，蟻群算法存在著早熟收斂，對參數(shù)依賴性強(qiáng)的缺點。對于不同版本的蟻群算法或具體的應(yīng)用問題，甚至不同的具體實例，算法需要不同的參數(shù)設(shè)置來獲取最優(yōu)的性能。傳統(tǒng)對參數(shù)的設(shè)置是根據(jù)應(yīng)用者有限的經(jīng)驗習(xí)慣人為地調(diào)整，往往需要做大量的數(shù)據(jù)測試，不僅耗費(fèi)時間而且影響了算法最優(yōu)性能的發(fā)揮，成為蟻群算法應(yīng)用的一大缺陷。

2 控制參數(shù)對算法性能的影響[2]

蟻群算法含有一系列對算法性能有重要影響的控制參數(shù)，包括：

1）啟發(fā)式因子α和β：α表示信息素的重要性，反映了蟻群在運(yùn)動過程中所殘留的信息量在指導(dǎo)蟻群搜索中的相對重要程度。α越大，信息素在路徑選擇上所起作用越大，螞蟻選擇以前走過路徑的可能性就越大，搜索的隨機(jī)性減弱；α越小，易使蟻群算法過早陷入局部最優(yōu)。當(dāng)α=0時，將不會利用信息素信息，搜索降為貪婪搜索。

β表示能見度的重要性，反映了啟發(fā)式信息在指導(dǎo)蟻群搜索過程中的相對重要程度。這些啟發(fā)式信息表現(xiàn)為尋優(yōu)過程中先驗性、確定性因素。β越大，城市之間距離對路徑選擇所起作用越大，螞蟻在局部點上選擇局部最短路徑的可能性越大，雖然加快了收斂速度，但減弱了隨機(jī)性，易于陷入局部最優(yōu)。當(dāng)β=0時，將忽略對有吸引力的解的顯式傾向，算法等同于性能較差的簡單蟻群優(yōu)化（SACO）。

α和β決定了以往的搜索經(jīng)驗和問題的固有啟發(fā)信息之間的相對重要性，出現(xiàn)在絕大部分的蟻群算法中，對算法性能的影響至關(guān)重要，是最重要的兩個參數(shù)。由于α和β是在信息素濃度和啟發(fā)式信息之間取得平衡的轉(zhuǎn)移概率Pkij的兩大決定因子，通過調(diào)節(jié)α和β可以很好地處理探索--開發(fā)之間的關(guān)系。

2）信息素?fù)]發(fā)系數(shù)ρ：模仿人類記憶特點，隨著新信息的增加，舊的信息將逐步忘卻、削弱，故引入ρ表示信息素的揮發(fā)率，為了防止信息的無限積累，ρ的取值范圍設(shè)定為[0,1]。

ρ的大小直接關(guān)系到蟻群算法的全局搜索能力及其收斂速度；ρ增大，則信息素?fù)]發(fā)加快，對過去的歷史經(jīng)驗不太敏感，突出最近路徑上留下的信息對選擇的影響。

相應(yīng)地，用1-ρ表示信息的殘留系數(shù)。1-ρ反映了螞蟻個體之間相互影響的強(qiáng)弱，其大小對蟻群算法的收斂性能影響非常大。在0.1-0.99范圍內(nèi)，1-ρ與迭代次數(shù)近似成正比，這是由于1-ρ很大，路徑上的殘留信息占主導(dǎo)地位，信息正反饋作用相對較弱，搜索的隨機(jī)性增強(qiáng)，因而蟻群算法的收斂速度慢。若1-ρ較小時，正反饋作用占主導(dǎo)地位，搜索的隨機(jī)性減弱，導(dǎo)致收斂速度快，但易陷于局部最優(yōu)。

3）信息素強(qiáng)度因子Q：Q表示螞蟻循環(huán)一周或一個過程釋放在所經(jīng)路徑上的信息素總量。在一定程度上影響處算法的收斂速度，Q越大，則每次螞蟻經(jīng)過所留下的信息素越多，在已遍歷路徑上信息素的累積越快，加強(qiáng)蟻群搜索時的正反饋性，有助于算法的快速收斂。

4）螞蟻數(shù)量m：蟻群算法成功在于多只螞蟻的共同協(xié)作行為，通過釋放信息素，螞蟻之間相互傳遞有關(guān)搜索空間的經(jīng)驗與知識。對同一規(guī)模的處理問題，m越大，即螞蟻數(shù)量多，會提高蟻群算法的全局搜索能力和穩(wěn)定性，但數(shù)量過多會導(dǎo)致大量曾被搜索過的路徑上的信息量變化趨于平均，信息正反饋作用減弱，隨機(jī)性增強(qiáng)，收斂速度變慢。反之，如果m越小，即螞蟻數(shù)目太少，會使從來未被搜索到的解上的信息量減小到接近于0，全局搜索的隨機(jī)性減弱，雖然提高了收斂速度，但算法穩(wěn)定性差，出現(xiàn)早熟現(xiàn)象。另一個就是對計算復(fù)雜度的影響，使用的螞蟻越多，需要建立的路徑就越多，對信息素釋放的計算也就越多。

3 參數(shù)選擇

控制參數(shù)直接影響算法的性能，包括找到的解的質(zhì)量及其計算開銷。參數(shù)選擇在算法應(yīng)用中顯得尤其重要，為了提高算法的性能，必須優(yōu)化相關(guān)的控制參數(shù)。自從Dorigo等對AS系統(tǒng)中的參數(shù)下選取進(jìn)行了初步研究[3]以來，很多學(xué)者在實驗基礎(chǔ)上進(jìn)行了深入研究并提供了一些參數(shù)設(shè)置參考值和優(yōu)化參數(shù)值的啟發(fā)式方法。

1）人工設(shè)置參數(shù)：葉志偉等對α、β和ρ這三個對算法的影響較大的參數(shù)的最優(yōu)配置進(jìn)行了研究，得出：在any-cycle模型中，α=1，β=5，ρ=0.5時，算法性能最優(yōu)；ant-density模型中，α=1，β=10，ρ=0.1時，算法性能最優(yōu)；ant-quantity模型中，α=1，β=5，ρ=0.001時，算法性能最優(yōu)[4]；而蔣玲艷等在分析了這三個參數(shù)不同組合對算法性能的影響基礎(chǔ)上，總結(jié)出參數(shù)設(shè)置規(guī)則：當(dāng)α∈[0.1,0.3]，β∈[3,6]，ρ∈[0.01,0.3]時，算法總體上有較好的性能，不易早熟，而且所需的迭代次數(shù)較少[5]。

對于所有參數(shù)（α、β、ρ、Q、m），段海濱提出了調(diào)整步驟[6]：首先根據(jù)“城市規(guī)模/螞蟻數(shù)目≈1.5”的原則確定螞蟻數(shù)目m；然后粗調(diào)取值范圍較大的α、β和Q；最后微調(diào)取值范圍較小的ρ。詹士昌等指出當(dāng)α∈[1,5]，β∈[1,5]，ρ=0.3，Q=100， （n為城市規(guī)模）時基本蟻群算法能較快地求得最優(yōu)解[7]。張毅等則提出了最優(yōu)的算法參數(shù)組合為：α=1、β=5、ρ=0.6、Q=1000、m=城市規(guī)模。在該算法參數(shù)設(shè)置原則下，基本蟻群算法對任意TSP問題總能比較快速地求得全局最優(yōu)解[8]。

人工設(shè)置參數(shù)需要大量的數(shù)據(jù)測試，蟻群中的所有螞蟻均采用相同的參數(shù)，而且只能為算法設(shè)定一個合適的初始參數(shù)，而不能在執(zhí)行過程中隨時調(diào)整參數(shù)，影響了算法的性能。

2）自適應(yīng)調(diào)整參數(shù)：針對人工設(shè)置參數(shù)的局限，學(xué)者們提出了自適應(yīng)地調(diào)整參數(shù)的改進(jìn)算法，主要是利用蟻群算法具有容易與其它優(yōu)化算法或局部搜索算法結(jié)合的優(yōu)點，在蟻群算法中混合其它啟發(fā)式算法以對其參數(shù)進(jìn)行訓(xùn)練和優(yōu)化，主要有：

① 運(yùn)用遺傳算法優(yōu)化蟻群算法的控制參數(shù)[9]：利用遺傳算法快速性、隨機(jī)性、全局收斂性的特點，每條染色體代表蟻群算法的一個參數(shù)值集合，通過選擇、交叉和變異等操作不斷優(yōu)化蟻群算法參數(shù)。

② 運(yùn)用粒子群優(yōu)化算法優(yōu)化蟻群算法的控制參數(shù)[10]：粒子群優(yōu)化算法具有非常快地逼迫最優(yōu)解的速度，可以有效對蟻群算法的控制參數(shù)進(jìn)行優(yōu)化。粒子被表示成一個多維的實數(shù)編碼串，代表蟻群算法的一個參數(shù)值集合，再引入適應(yīng)度函數(shù)并結(jié)合粒子群算法得到各參數(shù)的最優(yōu)組合。

③ 運(yùn)用差分演化算法優(yōu)化蟻群算法的控制參數(shù)：將蟻群算法的參數(shù)作為差分演化算法解空間的向量元素，自適應(yīng)地尋找蟻群算法最優(yōu)參數(shù)組合的同時求解問題的最優(yōu)解。

在蟻群算法中引入其它啟發(fā)式算法的混合算法，不僅使蟻群算法有效擺脫了對參數(shù)設(shè)置的依賴，而且克服了早熟收斂的缺點，大大提高了算法發(fā)現(xiàn)最優(yōu)解的能力，具有更好的全局優(yōu)化性能。

此外，研究者還提出了根據(jù)蟻群算法的不同進(jìn)化階段或當(dāng)連續(xù)幾代進(jìn)化后的最優(yōu)解沒有明顯變化時，自適應(yīng)調(diào)整參數(shù)，以提高最優(yōu)解的求解質(zhì)量的改進(jìn)方案[11]。這類改進(jìn)算法能夠有效提高算法的優(yōu)化性能，但這些方法并不是通用的，只能使用于特定的算法模型或針對特定的問題。

4 小結(jié)

蟻群算法作為一種隨機(jī)算法，其性能很大程度上受算法參數(shù)的影響，好的參數(shù)可以使算法快速收斂于優(yōu)質(zhì)解，而參數(shù)設(shè)置不當(dāng)，將導(dǎo)致算法找到的解質(zhì)量差，容易陷于局部最優(yōu)，并且收斂速度慢甚至不收斂。由于蟻群算法參數(shù)空間的龐大性和各參數(shù)之間的關(guān)聯(lián)性，很難設(shè)置最優(yōu)參數(shù)組合以使蟻群算法優(yōu)化性能最佳，至今還沒有完善的理論依據(jù)，沒有參數(shù)選擇方面的公式可循，通常根據(jù)經(jīng)驗而定。因此，對蟻群算法的參數(shù)進(jìn)行深入分析，了解參數(shù)之間的關(guān)聯(lián)，提出好的參數(shù)設(shè)置方案，以便更合理地設(shè)置參數(shù)或者自適應(yīng)地調(diào)整參數(shù)是非常有意義的，不僅能有效地提高算法的優(yōu)化性能，而且完善了算法的理論研究，進(jìn)一步推廣蟻群算法在優(yōu)化領(lǐng)域上的應(yīng)用。

參考文獻(xiàn)：

[1] Colorni A,Dorigo M,Maniezzo V.Distributed Optimization by Ant Colonies[C]//The First European Conference on Artificial Life.France: Elsevier,1991:134-142.

[2] 汪定偉.智能優(yōu)化方法[M].北京:高等教育出版社,2007.

[3] Dorigo M,Maniezzo V,Colorni A.Ant system: optimization by a Colony of Cooperating Agents[J].IEEE Transactions on System,Man and Cybernetics,1996,26(1):29-41.

[4] 葉志偉,鄭肇葆.蟻群算法中參數(shù)α,β,ρ設(shè)置的研究-以TSP問題為例[J].武漢大學(xué)學(xué)報,2004,29(7):597-601.

[5] 蔣玲艷,張軍,鐘樹鴻.蟻群算法的參數(shù)分析[J].計算機(jī)工程與應(yīng)用,2007,43(20):31-36.

[6] 段海濱.蟻群算法原理及應(yīng)用[M].北京:科學(xué)出版社,2005.

[7] 詹士昌,徐婕,吳俊.蟻群算法中關(guān)鍵參數(shù)的選擇[J].科技通報,2003,19(5):381-386.

[8] 張毅,梁艷春.蟻群算法中求解參數(shù)最優(yōu)選擇[J].分析計算機(jī)應(yīng)用研究,2007(8).

[9] Botee H,Bonabeau E.Evolving Ant Colony Optimization[J].Complex Systems,1998,1(2):149-159.

篇5

基金項目:國家自然科學(xué)基金資助項目（61075013）;電子科技大學(xué)青年科技基金資助項目（TX0706）。

作者簡介:李曉峰（1963-）, 男, 四川成都人，教授, 主要研究方向：多媒體圖像傳輸、無線通信系統(tǒng)； 劉洪盛（1966-）, 男，吉林吉林人，博士，主要研究方向：通信信號處理、多媒體傳輸； 任通菊（1964-）, 女,四川成都人, 碩士, 主要研究方向：通信技術(shù)。

文章編號:1001-9081（2011）07-1956-03doi:10.3724/SP.J.1087.2011.01956

（電子科技大學(xué) 通信與信息工程學(xué)院， 成都 611731）

（; ; ）

摘 要:為了應(yīng)對H.264可伸縮視頻編碼（SVC）應(yīng)用中網(wǎng)絡(luò)特性的波動，提出了一種預(yù)測播放中斷與緩沖區(qū)溢出風(fēng)險進(jìn)行及早調(diào)節(jié)的自適應(yīng)媒體播放（AMP）算法。該算法估算網(wǎng)絡(luò)流量與視頻圖像組（GOP）結(jié)構(gòu)中各幀長度用于風(fēng)險預(yù)測，通過K步調(diào)節(jié)過程實現(xiàn)良好的調(diào)節(jié)平滑性與速度，并利用SVC的可伸縮性盡量減少溢出帶來的質(zhì)量損失。仿真結(jié)果表明，該算法在抑制播放中斷、處理緩沖區(qū)溢出與抖動性能等方面，優(yōu)于現(xiàn)行的平滑AMP與常規(guī)AMP算法。

關(guān)鍵詞:自適應(yīng)媒體播放；可伸縮視頻編碼；視頻流；多媒體通信

中圖分類號:TN919.8文獻(xiàn)標(biāo)志碼:A

Adaptive media playout algorithm for H.264 scalable video streaming

LI Xiao-feng, LIU Hong-sheng, RENG Tong-ju

（School of Communication and Information Engineering, University of Electronic Science and Technology of China, Chengdu Sichuan 611731,China）

Abstract: To cope with the variation of network conditions in scalable video streaming, a new Adaptive Media Playout （AMP） algorithm was proposed which predicates the risk of playout outage and buffer overflow and adjusts the frame rate in advance. The algorithm estimated the throughput of network and the lengths of frames in the video’s GOP structure for risk predication, realized adjustments in K steps for good smoothness and speed, and reduced quality loss of the video by exploiting the scalability of SVC stream. The simulation results show that the proposed algorithm outperforms the existing smooth and conventional AMP algorithms in outage suppressing, overflow processing and jitter performance.

Key words: Adaptive Media Playout （AMP）; Scalable Video Coding （SVC）; video streaming; multimedia communication

0 引言

視頻壓縮與網(wǎng)絡(luò)技術(shù)的發(fā)展促進(jìn)了各種視頻流媒體的廣泛應(yīng)用，典型的例子如：數(shù)字視頻廣播、視頻點播、可視會議與網(wǎng)絡(luò)視頻等。視頻序列以流的形式傳輸時，先到達(dá)終端的部分?jǐn)?shù)據(jù)立即被解碼播放，讓用戶及時收看內(nèi)容，而不必等待全部數(shù)據(jù)接收完畢。但是，網(wǎng)絡(luò)的傳輸特性是時變的，端到端的數(shù)據(jù)速率與時延總不穩(wěn)定。通過網(wǎng)絡(luò)傳輸?shù)囊曨l數(shù)據(jù)包在到達(dá)收端時可能發(fā)生突發(fā)的延遲，甚至出現(xiàn)短期中斷。為此，收端必須使用接收緩沖區(qū)應(yīng)付傳輸特性的變化。緩沖區(qū)太小難于應(yīng)付網(wǎng)絡(luò)變化，太大會引入過多的時延并耗費(fèi)存儲資源。如何有效利用接收緩沖區(qū)提高視頻傳輸可靠性是人們研究的熱點之一。

自適應(yīng)媒體播放（Adaptive Media Playout，AMP）技術(shù)是其中的重要方法之一。運(yùn)用AMP技術(shù)，終端根據(jù)接收緩沖區(qū)的狀況調(diào)整媒體播放速率。當(dāng)網(wǎng)絡(luò)流量低時，緩沖區(qū)存量減少，終端適量減慢播放速率，從而降低數(shù)據(jù)消耗，減少播放中斷風(fēng)險。研究表明: 在基本不影響用戶感受的條件下，音視頻流的播放速率可以變化約±25%［1］。調(diào)節(jié)音頻流的速度時需要通過特殊的信號處理保持音調(diào)等聲音特征的穩(wěn)定，而調(diào)節(jié)視頻流的速度可簡單地通過改變幀間間隔來實現(xiàn)。本文只討論視頻流的相關(guān)問題。

文獻(xiàn)［1-3］主要研究了基于緩沖區(qū)數(shù)據(jù)量實施調(diào)節(jié)的AMP方法。其基本原理是設(shè)置調(diào)節(jié)門限，當(dāng)緩沖區(qū)數(shù)據(jù)量低于門限時，增大播放視頻的幀間間隔s（s>1）倍，以降低緩沖區(qū)下溢出的概率。這類方法中要根據(jù)應(yīng)用合理地選擇門限。文獻(xiàn)［4-6］探討了以最佳視頻質(zhì)量為目標(biāo)，通過動態(tài)設(shè)置門限降低緩沖區(qū)中斷概率與起始等待時間的方法。其中文獻(xiàn)［5］以無線視頻流的應(yīng)用為背景提出了緩沖區(qū)下溢出的統(tǒng)計模型，通過動態(tài)建立模型參數(shù)來計算最佳門限。文獻(xiàn)［6］采用馬爾可夫模型研究中斷間隔、啟動預(yù)時延、視頻質(zhì)量與無線網(wǎng)絡(luò)信道狀況彼此之間的關(guān)系，進(jìn)而求出優(yōu)化的AMP策略。文獻(xiàn)［7］對發(fā)端的數(shù)據(jù)包調(diào)度策略與收端的播放速度進(jìn)行聯(lián)合優(yōu)化，并將視頻內(nèi)容特征納入考慮，通過復(fù)雜的貪婪算法進(jìn)行求解。文獻(xiàn)［8］采用G/G/1/∞與G/G/1/N統(tǒng)計模型對接收緩沖區(qū)進(jìn)行建模，推導(dǎo)了多種主要參數(shù)公式，提出了最佳視頻質(zhì)量函數(shù)，并通過復(fù)雜的優(yōu)化算法解出最佳策略。上述動態(tài)門限與統(tǒng)計模型等方法常常用到復(fù)雜的算法。文獻(xiàn)［9］不同于常規(guī)的門限調(diào)節(jié)方式，提出了一種基于緩沖區(qū)變化幅度的調(diào)節(jié)方法，結(jié)合較長的調(diào)節(jié)進(jìn)程實現(xiàn)了十分平滑的調(diào)節(jié)。但這種方法有時調(diào)節(jié)速度過于平緩，造成跟蹤信道變化的速度不夠。

近年來國際標(biāo)準(zhǔn)化組織提出一種能適應(yīng)異構(gòu)網(wǎng)絡(luò)與終端特性的有效方法――可伸縮視頻編碼（Scalable Video Coding，SVC）［10］。不同于常規(guī)的H.264，SVC編碼器生成的比特流由一個基礎(chǔ)層（Base Layer,BL）與多個增強(qiáng)層（Enhancement Layer,EL）構(gòu)成，在空間、時間與質(zhì)量方面具有可伸縮性。

本文針對SVC碼流的傳輸應(yīng)用，提出了一種通過預(yù)測接收緩沖區(qū)的上下溢出風(fēng)險，進(jìn)行平滑調(diào)節(jié)的方法。預(yù)測中基于SVC的圖像組（Grope Of Pictures，GOP）結(jié)構(gòu)中不同幀的長度估算提高預(yù)測準(zhǔn)確性，并在溢出處理中利用SVC的可伸縮性來避免BL丟失，減少質(zhì)量損失。

1 系統(tǒng)模型與典型算法

SVC視頻流傳輸系統(tǒng)如圖1所示。它包括源端、差錯信道與用戶端。視頻源與流媒體服務(wù)器按固定的標(biāo)稱幀率Rf（相應(yīng)的標(biāo)稱幀間間隔記為Tf 0）發(fā)送以H.264可伸縮壓縮編碼的NAL數(shù)據(jù)包，經(jīng)信道傳輸?shù)接脩艚K端，存入接收緩沖區(qū)中。播放器基于AMP策略按間隔Tf（t）從緩沖區(qū)中提取數(shù)據(jù)，播放畫面。這里t為系統(tǒng)時間，采用離散值（時隙長為δ）。記s（t）為t時刻后播放畫面的時間基準(zhǔn)，n（t）是t時隙中播放器應(yīng)從緩沖區(qū)中提取的幀數(shù)，有

s（t） （1）

與 n（t）「［δ－s（t－1）］/Tf（t）S（2）

式中「S為取整數(shù)運(yùn)算。

圖1 SVC視頻流傳輸系統(tǒng)

傳輸系統(tǒng)采用自動重傳請求（Automatic Repeat reQuest, ARQ）策略，如果出現(xiàn)傳輸錯誤，收端通過反饋信道發(fā)送重傳請求。本文參照文獻(xiàn)［1］的方法作合理的簡化，假定系統(tǒng)允許足夠次數(shù)的重傳，保證進(jìn)入緩沖區(qū)的數(shù)據(jù)包都是正確的與嚴(yán)格按順序到達(dá)的。在這種情況下，網(wǎng)絡(luò)的錯誤與丟包可以等效為數(shù)據(jù)速率的下降。記網(wǎng)絡(luò)端到端的原始數(shù)據(jù)率為R0，當(dāng)前丟包率為Pe（j），則等效的數(shù)據(jù)率為R（t）R0［1－Pe（j）］，其中， j為當(dāng)前信道狀態(tài)。不同狀態(tài)的信道具有不同的丟包率。本文采用Gilbert-Eilliott的兩狀態(tài)馬爾可夫丟包模型。信道在好狀態(tài)與壞狀態(tài)下以不同的概率隨機(jī)丟包。壞信道對應(yīng)信道出現(xiàn)突發(fā)錯誤時的情況，而突發(fā)長度對應(yīng)信道處于壞狀態(tài)的平均滯留時間。記信道狀態(tài)為j∈{g,b}，g與b分別指好狀態(tài)與壞狀態(tài)。兩狀態(tài)的平均滯留時間分別記為Tg與Tb，相應(yīng)的丟包概率記為pgPe（g）與pbPe（b）。

視頻流中每幀對應(yīng)的字節(jié)數(shù)各不相同，而且可以相差很大，比如，I幀與B幀可能相差十倍以上，因此，不宜采用文獻(xiàn)［9］的觀點取各幀字節(jié)長度一樣并對應(yīng)于單個數(shù)據(jù)包。本文將區(qū)別不同幀的長度，幀長信息從NAL包頭參數(shù)求取。設(shè)緩沖區(qū)尺寸為B0字節(jié)，可容納的平均幀數(shù)大約為L。數(shù)據(jù)存入緩沖區(qū)時以數(shù)據(jù)包為單位，而播出時以幀為單位。分別記B1（字節(jié)）為緩沖區(qū)的上溢出警戒線、L0（幀）為下溢出警戒線；ML/2為起始等待幀數(shù)。并記t時刻緩沖區(qū)的數(shù)據(jù)量為b（t）,包含的完整幀數(shù)為l（t）。緩沖區(qū)結(jié)構(gòu)如圖2所示。

播放過程中，如果t時刻出現(xiàn)l（t）

圖2 接收緩沖區(qū)結(jié)構(gòu)示意圖

常規(guī)AMP算法［1］的基本規(guī)則為:

Tf（t） （3）

平滑AMP算法［9］ 的基本規(guī)則為：

1）如果l（t）－lR（t）>τ則發(fā)出調(diào)節(jié)請求（lR（t）為動態(tài)參考點，τ為某常數(shù)），計算調(diào)節(jié)期長度如下：

TC－ln－1（4）

其中：T 0f與T1f分別是當(dāng)前與目標(biāo)間隔，T1f通過輸入數(shù)據(jù)速率估算；C稱為調(diào)節(jié)量，如下計算（以l（t）向下波動為例）：

C （5）

2）在調(diào)節(jié)期中，

Tf（t）T0f+（T1f－T0f）（t－t0）/T（6）

其中t0是調(diào)節(jié)期的起始時刻。

3）在非調(diào)節(jié)期中，保持Tf（t）Tf（t－1）。

平滑AMP算法只檢查緩沖區(qū)中幀數(shù)的波動，而不需直接對數(shù)據(jù)量設(shè)定門限，該算法通過調(diào)節(jié)期使調(diào)節(jié)過程十分平滑。但其調(diào)節(jié)幅度沒有控制，有時遠(yuǎn)大于±25%的范圍，使收視感覺不好。而且，其調(diào)節(jié)過程有時過于緩慢，來不及應(yīng)付信道變化。

2 基于預(yù)測的自適應(yīng)播放算法

本文提出的AMP方案對網(wǎng)絡(luò)流量與視頻參數(shù)進(jìn)行估算，并基于這兩項估算預(yù)測緩沖區(qū)的溢出與播放中斷風(fēng)險。具體策略如下。

1）收端統(tǒng)計當(dāng)前時隙中的接收數(shù)據(jù)包及其字節(jié)量，記當(dāng)前接收字節(jié)量為x（t）。估算信道流量為

R^ （t）λcR^ （t－1）+（1－λc）x（t）（7）

其中λc為正常數(shù)，0≤λc≤1。

由接收數(shù)據(jù)包分析NAL包頭，重組視頻幀，記成功重組的完整幀長度為y（t），其在GOP中的幀編號為i1,2,…,Ngop（其中，整數(shù)Ngop為SVC的GOP長度）。記視頻幀長度為{fi（t）,i1,2，…,Ngop}，并如下估算，

fi（t）λvfi（t－1）+（1－λv）y（t）（8）

其中λv為正常數(shù)，0≤λv≤1。

2）預(yù)測未來K幀期間的風(fēng)險（K為常數(shù)）。

a）播出中斷風(fēng)險：計算lKnl（KR^ （t）,i），其中i是當(dāng)前接收幀的GOP編號；nl（z,i）給出從編號i開始用z字節(jié)可組裝的完整視頻幀數(shù)。

令ΔlKlK+l（t）－K－L0。若ΔlK

ΔTf－2ΔlKTf（t）/[（K+ΔlK）（K+ΔlK+1）]（9）

若Tf（t）+K×ΔTf>1.25，改用ΔTf［1.25－Tf（t）］/K1，其中:

K1「+S（10）

b） 緩沖區(qū)溢出風(fēng)險：計算lKnl（b（t）+KR^ （t）－B0,i），其中i是當(dāng)前播放幀的GOP編號。

令ΔlKlK－K。若ΔlK>0，則存在溢出風(fēng)險。這時啟動調(diào)節(jié)，以ΔlK代入式（9）計算參數(shù)ΔTf。若Tf（t）+K×ΔTf

K1「+S（11）

3）在K步調(diào)節(jié)期中，Tf（t）Tf（t－1）+ΔTf ；在非調(diào)節(jié)期中，保持Tf（t）Tf（t－1） 。

算法中，計算nl（z,i）時利用{fi（t）}可以準(zhǔn)確估算幀數(shù)；式（9）按K步平滑調(diào)節(jié)原則計算間隔增量；而式（10）與（11）是為了確保在±25%的調(diào)節(jié)范圍內(nèi)完成平滑調(diào)節(jié)。當(dāng)?shù)竭_(dá)數(shù)據(jù)量超過緩沖區(qū)容量，本文基于SVC的可伸縮性進(jìn)行如下處理：由緩沖區(qū)中的NAL包頭提取SVC空間、時間與質(zhì)量層次編號D、T與Q，如下計算該NAL包的重要性，

SI （12）

其中，a,b,c∈（0,1）為權(quán)系數(shù)；β是使SI的范圍為0至1的歸一化因子。在緩沖區(qū)中依次刪除SI最小的數(shù)據(jù)包，直到緩沖區(qū)能夠容納新到達(dá)的數(shù)據(jù)包為止。由于基礎(chǔ)層（BL）的數(shù)據(jù)量比總的數(shù)據(jù)量小許多，通過這樣的處理可以完全避免BL的丟失，而且，刪除的數(shù)據(jù)包對應(yīng)的質(zhì)量損失是最小的。

3 仿真結(jié)果及分析

仿真實驗采用四個長約10min的視頻測試序列，它們由標(biāo)準(zhǔn)序列經(jīng)重復(fù)生成。相應(yīng)的標(biāo)準(zhǔn)序列分別是：Mobile、Football、Foreman與Bus，基本長度為256、288、288與144，重復(fù)次數(shù)為72、64、64與128。視頻編解碼采用聯(lián)合可伸縮視頻模型（JSVM）參考軟件7.10版本，幀率為30fps，輸出碼流為單一的空間分辨率，含一個基礎(chǔ)層與三個增強(qiáng)層。設(shè)定GOP＝8，Intra＝16，基礎(chǔ)層量化參數(shù)QP＝36。

信道采用兩狀態(tài)馬爾可夫丟包模型。主要參數(shù)為：Tg18.5s，Tb1.5s，pg0.01與pb0.80。網(wǎng)絡(luò)原始數(shù)據(jù)率R0設(shè)定為視頻流平均碼率的1.5倍。系統(tǒng)時隙取為1/30s。緩沖區(qū)大小B0為128B的倍數(shù)，相當(dāng)于約5s時間（L150）。令B10.75B0與L036。

為了評估本文所提方案的性能，本算法與常規(guī)AMP［1］、平滑AMP算法［9］與“25%約束的平滑AMP算法”相比較?！?5%約束的平滑AMP算法”指幀間隔調(diào)節(jié)范圍限制在±25%以內(nèi)的平滑AMP算法方案，通過限制便于在可接受的變速條件下進(jìn)行比較。三種參考算法以及本文算法分別簡記為AMP、SAMP（Smooth AMP）、SAMP25與PAMP（Predicative AMP）。SAMP算法中取τ7，PAMP算法中取K49。性能指標(biāo)為：播出中斷次數(shù)、幀間隔的歸一化范圍（Tf/Tf 0）、相對抖動dTf，以及溢出造成的平均峰值信噪比（PSNR）損失與BL丟失計數(shù)。相對抖動dTf可以衡量調(diào)節(jié)的平滑度，定義為（設(shè)序列總幀數(shù)為n）

dTf∑ni2Tf（t）－Tf（t－1）/Tf 0×100%（13）

表1給出了四種算法針對各測試序列的仿真實驗結(jié)果，所有數(shù)據(jù)為運(yùn)行100次的平均值?？梢钥吹剑罕疚乃惴ㄅcSAMP的播出中斷次數(shù)基本一樣（大約0.6次），都明顯優(yōu)于常規(guī)AMP算法；調(diào)節(jié)平滑程度也比常規(guī)AMP好許多。本文算法的幀間隔變化幅度控制在±25%以內(nèi)，而SAMP的變化幅度可能超過600%，后者的視覺感受會明顯降低。SAMP調(diào)節(jié)較緩慢，如果對其調(diào)節(jié)幅度進(jìn)行約束，從SAMP25的數(shù)據(jù)可見，SAMP的中斷次數(shù)會明顯上升。

表1 四種算法的性能參數(shù)對比

另一方面，SAMP算法依靠大幅度的調(diào)節(jié)使其溢出概率與BL丟失概率較低。本文PAMP算法采用基于SVC可伸縮性的溢出處理，避免了BL丟失，有效減少了視頻質(zhì)量損失。這種溢出處理方法同樣適用于其他幾種算法。表2給出了PAMP算法中溢出處理前后的數(shù)據(jù)比較，還給出了AMP與SAMP25的相應(yīng)數(shù)據(jù)。可見，幾種算法經(jīng)過處理后BL不再丟失,這對于視頻的收視質(zhì)量有很好的改善。溢出處理無助于播出中斷與調(diào)節(jié)范圍的控制，所以，本文算法比其他算法在綜合性能上有明顯的優(yōu)勢。

表2 啟用基于SVC的溢出處理前后比較

4 結(jié)語

面對網(wǎng)絡(luò)傳輸特性與流量的波動，自適應(yīng)媒體播放技術(shù)是有效利用接收緩沖區(qū)保障用戶視覺感受的一項重要技術(shù)。本文為SVC視頻流提出一種預(yù)測播放中斷與緩沖區(qū)溢出風(fēng)險進(jìn)行及早調(diào)節(jié)的AMP方法，通過對SVC視頻數(shù)據(jù)GOP結(jié)構(gòu)中各種幀長度的估算，使風(fēng)險預(yù)測更加準(zhǔn)確。通過K步調(diào)節(jié)過程使幀間隔的調(diào)節(jié)既比較平滑又有良好的速度；適度的調(diào)節(jié)范圍使視頻播放的主觀感受保持良好；而基于SVC可伸縮性的溢出處理最大限度地減少了溢出帶來的質(zhì)量損失。仿真實驗表明，本方法相對于現(xiàn)行的平滑AMP與常規(guī)AMP算法在抑制播放中斷、維持用戶視覺感受、處理緩沖區(qū)溢出與控制調(diào)節(jié)的平滑度等方面有較大的優(yōu)勢。

參考文獻(xiàn):

［1］ KALMAN M, STEINBACH E, GIROD B. Adaptive media playout for low-delay streaming over error-prone channels ［J］. IEEE Transactions on Circuits and Systems for Video Technology, 2004, 14（6）: 841-851.

［2］ STEINBACH E, FARBER N, GIROD B. Adptive playout for low latency video streaming［C］// Proceedings of 2001 International Conference on Image Processing. New York:IEEE, 2001:962-965.

［3］ CHUAN H C, HUANG C Y, CHIANG T. On the buffer dynamics of scalable video streaming over wireless network［C］// Proceedings of IEEE 60th Vehicular Technology Conference. New York:IEEE, 2004:2582-2586.

［4］ YANG Y H, LU MENGTING, CHEN H H. Smooth playout control for video streaming over error-prone channels［C］// Proceedings of the 8th IEEE International Symposium on Multimedia. Washington, DC: IEEE Computer Society, 2006:415-418.

［5］ CHUANG H C, HUANG C Y, CHIANG T H. Content-aware adaptive media playout controls for wireless video streaming［J］. IEEE Transactions on Multimedia,2007, 9（6）:1273-1283.

［6］ PARK S, KIM J. An adaptive media playout for intra-media synchronization of networked-video applications［J］. Journal of Visual Communication and Image Representation, 2008, 19（2）:106-120.

［7］ LI Y, MARKOPOULOU A, APOSTOLOPOULOS J, et al. Content-aware playout and packet scheduling for video streaming over wireless links［J］. IEEE Transactions on Multimedia, 2008, 10（8）:885-895.

［8］ LUAN T H, CAI L X,SHEN X. Impact of network dynamics on user's video quality: Analytical framework and QoS provision［J］. IEEE Transactions on Multimedia, 2010,12（1）:64-78.