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

篇1

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

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

0引言

遺傳算法（GA）是一種進(jìn)化算法，其基本原理是仿效生物界中的“物競(jìng)天擇、適者生存”的演化法則。最早是由美國(guó)密歇根大學(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)的算法有：窮舉法、分支限界法、動(dòng)態(tài)規(guī)劃法[4-5]等。高海昌等[6] 對(duì)蟻群算法、遺傳算法、模擬退火算法、禁忌搜索、神經(jīng)網(wǎng)絡(luò)、粒子群優(yōu)化算法、免疫算法等進(jìn)行了論述。隨著研究的深入，許多改進(jìn)的算法不斷涌現(xiàn)，李瑋[7]采用矩陣編碼、交叉、變異的遺傳算法來解決TSP問題，雷玉梅[8]提出了一種分而治之的遺傳算法思想，姚明海[9]采用遺傳算法與其他智能算法結(jié)合的思想來解決問題。遺傳算法因其高效的搜索能力成為了解決TSP問題的有效方法之一。雖然遺傳算法能夠較為成功地求解TSP問題，但也存在搜索較慢的問題，特別是遺傳算法在解決TSP問題時(shí)容易出現(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ì)量相對(duì)較好的初始種群，同時(shí)又在貪婪思想引導(dǎo)的交叉操作操作之前，把當(dāng)前較差的一半種群替換成隨機(jī)種群，二者結(jié)合來提升收斂速度又防止了陷入局部最優(yōu)。實(shí)驗(yàn)證明，本文研發(fā)的改進(jìn)遺傳算法較好地解決了TSP問題中收斂速度和早熟的問題，且具有較強(qiáng)的魯棒性，通用于類似的組合優(yōu)化問題。

參考文獻(xiàn)：

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

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

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

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

[5]趙頌華.城市公共資源監(jiān)管設(shè)計(jì)新思維[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ì)算機(jī)與現(xiàn)代化，2015（2）：34-39.

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

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

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

壓縮感知采集方法并不是對(duì)數(shù)據(jù)直接進(jìn)行采集，而是通過一組特定波形去感知信號(hào)，即將信號(hào)投影到給定波形上面（衡量與給定波形的相關(guān)度），感知到一組壓縮數(shù)據(jù)，最后利用最優(yōu)化的方法實(shí)現(xiàn)對(duì)壓縮數(shù)據(jù)解密，估計(jì)出原始信號(hào)的重要信息。壓縮感知關(guān)鍵的問題是如何給定用來感知信號(hào)的波形才能有效地恢復(fù)出原始信號(hào)的重要信息。涉及的關(guān)鍵因素在于給定的波形要與可以用來壓縮原始信號(hào)的波形組均不相干，并且不相干程度越高，感知數(shù)據(jù)包含的信息量越大，為準(zhǔn)確獲取重建原始信號(hào)所需的感知數(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ù)中方便地提取信號(hào)有用信息的充分條件。

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

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

2.1 基追蹤算法

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

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

2.2 矩陣填充問題

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

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

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

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

篇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ì)算;神經(jīng)網(wǎng)絡(luò);小波變換;模糊算法

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

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

0引言

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

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

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

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

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

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

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

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

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

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)則一般是指?jìng)€(gè)體的適應(yīng)度達(dá)到給定的閾值,或者個(gè)體的適應(yīng)度的變化率為零。

3.2.2 粒子群算法(PSO)粒子群優(yōu)化算法是一種進(jìn)化計(jì)算技術(shù),源于對(duì)鳥群捕食的行為研究。設(shè)想有這樣一個(gè)場(chǎng)景:一群鳥在隨機(jī)搜索食物,在這個(gè)區(qū)域里只有一塊食物,所有的鳥都不知道食物在哪里,但是他們知道當(dāng)前的位置離食物還有多遠(yuǎn),那么找到食物的最優(yōu)策略是什么呢?最簡(jiǎn)單有效的方法就是搜尋目前離食物最近的鳥的周圍區(qū)域。PSO算法從這種模型中得到啟示并用于解決優(yōu)化問題。PSO中,每個(gè)優(yōu)化問題的解都是搜索空間中的一只鳥,我們稱之為“粒子”。所有的粒子都有一個(gè)由被優(yōu)化的函數(shù)決定的適應(yīng)值,每個(gè)粒子還有一個(gè)速度決定他們飛翔的方向和距離,然后粒子們就追隨當(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ā)式方法,該方法具有正反饋、分布式計(jì)算和富于建設(shè)性的貪婪啟發(fā)式搜索的特點(diǎn)。

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

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

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

4結(jié)束語

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

參考文獻(xiàn):

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

篇4

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

中圖分類號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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)用研究的一個(gè)重要方向。蟻群算法作為最成功的元啟發(fā)式算法之一，優(yōu)化性能很大程度上依賴于參數(shù)的設(shè)置，但要對(duì)其參數(shù)進(jìn)行最優(yōu)設(shè)置是一項(xiàng)復(fù)雜的工作，往往需要經(jīng)過大量的測(cè)試，這成為蟻群算法進(jìn)一步推廣應(yīng)用的一個(gè)瓶頸。

1 基本蟻群算法

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

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

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

(1)

其中：

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

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

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

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

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

當(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)上留下的信息素?cái)?shù)量；

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

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

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

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

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

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

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

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

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

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

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

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

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

3 參數(shù)選擇

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

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

對(duì)于所有參數(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ī)模）時(shí)基本蟻群算法能較快地求得最優(yōu)解[7]。張毅等則提出了最優(yōu)的算法參數(shù)組合為：α=1、β=5、ρ=0.6、Q=1000、m=城市規(guī)模。在該算法參數(shù)設(shè)置原則下，基本蟻群算法對(duì)任意TSP問題總能比較快速地求得全局最優(yōu)解[8]。

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

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

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

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

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

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

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

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)驗(yàn)而定。因此，對(duì)蟻群算法的參數(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é)報(bào),2004,29(7):597-601.

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

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

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

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

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

篇5

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

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

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

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

（; ; ）

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

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

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

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

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

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

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

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

SVC視頻流傳輸系統(tǒng)如圖1所示。它包括源端、差錯(cuò)信道與用戶端。視頻源與流媒體服務(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)時(shí)間，采用離散值（時(shí)隙長(zhǎng)為δ）。記s（t）為t時(shí)刻后播放畫面的時(shí)間基準(zhǔn)，n（t）是t時(shí)隙中播放器應(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)采用自動(dòng)重傳請(qǐng)求（Automatic Repeat reQuest, ARQ）策略，如果出現(xiàn)傳輸錯(cuò)誤，收端通過反饋信道發(fā)送重傳請(qǐng)求。本文參照文獻(xiàn)［1］的方法作合理的簡(jiǎn)化，假定系統(tǒng)允許足夠次數(shù)的重傳，保證進(jìn)入緩沖區(qū)的數(shù)據(jù)包都是正確的與嚴(yán)格按順序到達(dá)的。在這種情況下，網(wǎng)絡(luò)的錯(cuò)誤與丟包可以等效為數(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ī)丟包。壞信道對(duì)應(yīng)信道出現(xiàn)突發(fā)錯(cuò)誤時(shí)的情況，而突發(fā)長(zhǎng)度對(duì)應(yīng)信道處于壞狀態(tài)的平均滯留時(shí)間。記信道狀態(tài)為j∈{g,b}，g與b分別指好狀態(tài)與壞狀態(tài)。兩狀態(tài)的平均滯留時(shí)間分別記為Tg與Tb，相應(yīng)的丟包概率記為pgPe（g）與pbPe（b）。

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

播放過程中，如果t時(shí)刻出現(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é)請(qǐng)求（lR（t）為動(dòng)態(tài)參考點(diǎn)，τ為某常數(shù)），計(jì)算調(diào)節(jié)期長(zhǎng)度如下：

TC－ln－1（4）

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

C （5）

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

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

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

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

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

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

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

1）收端統(tǒng)計(jì)當(dāng)前時(shí)隙中的接收數(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包頭，重組視頻幀，記成功重組的完整幀長(zhǎng)度為y（t），其在GOP中的幀編號(hào)為i1,2,…,Ngop（其中，整數(shù)Ngop為SVC的GOP長(zhǎng)度）。記視頻幀長(zhǎng)度為{fi（t）,i1,2，…,Ngop}，并如下估算，

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

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

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

a）播出中斷風(fēng)險(xiǎn)：計(jì)算lKnl（KR^ （t）,i），其中i是當(dāng)前接收幀的GOP編號(hào)；nl（z,i）給出從編號(hào)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)險(xiǎn)：計(jì)算lKnl（b（t）+KR^ （t）－B0,i），其中i是當(dāng)前播放幀的GOP編號(hào)。

令ΔlKlK－K。若ΔlK>0，則存在溢出風(fēng)險(xiǎn)。這時(shí)啟動(dòng)調(diào)節(jié)，以ΔlK代入式（9）計(jì)算參數(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） 。

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

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

仿真實(shí)驗(yàn)采用四個(gè)長(zhǎng)約10min的視頻測(cè)試序列，它們由標(biāo)準(zhǔn)序列經(jīng)重復(fù)生成。相應(yīng)的標(biāo)準(zhǔn)序列分別是：Mobile、Football、Foreman與Bus，基本長(zhǎng)度為256、288、288與144，重復(fù)次數(shù)為72、64、64與128。視頻編解碼采用聯(lián)合可伸縮視頻模型（JSVM）參考軟件7.10版本，幀率為30fps，輸出碼流為單一的空間分辨率，含一個(gè)基礎(chǔ)層與三個(gè)增強(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)時(shí)隙取為1/30s。緩沖區(qū)大小B0為128B的倍數(shù)，相當(dāng)于約5s時(shí)間（L150）。令B10.75B0與L036。

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

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

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

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

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

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

4 結(jié)語

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

參考文獻(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.