一種基於滑動窗口的fgs帶寬快速分配算法的製作方法
2023-06-15 08:49:51 1
專利名稱：一種基於滑動窗口的fgs帶寬快速分配算法的製作方法
技術領域：
本發明涉及一種在異構網絡環境下，大規模交互式實時多媒體系統中視頻碼流的快速帶寬分配算法，尤其涉及一種基於滑動窗口的FGS(Fine Granularity Scalability，FGS，精細可擴展編碼)帶寬快速分配算法。
背景技術：
異構網絡環境下的實時視頻會議系統中需要解決的一個基本問題是網絡帶寬的自適應。在MPEG-4標準中提出的FGS編碼方式對DCT殘差係數做位平面編碼，可根據實際帶寬的變化對增強層作任意長度截取而解碼，其視頻質量與解碼長度成正比。
為了有效利用FGS碼流的這種特點，需要根據可用帶寬的變動，使用一種帶寬分配算法以保證接收端可以得到較恆定的圖像質量。目前為止，牛頓搜索法，二分搜索法，R-D曲線合成法等被提出並都取得了不錯的效果。這些算法使用了一種滑動窗口協議以保證自身的有效性。滑動窗口協議需要發送端維持較大的M幀緩衝區(即所謂的滑動窗口)，而每次發送出去的那幀並不是編碼器當前編碼完成的，而是第N-M幀(假設當前編完碼的是第N幀)。這樣即使接收端收到後馬上播放也會有M/fps秒的延遲(假設fps為發送端幀率)。這在實時視頻會議系統中，M/fps秒的延遲將會給交互效果帶來影響。此外，若M取值過小則會影響到算法有效性。
發明內容
本發明的技術解決問題克服現有技術的不足，提供一種基於滑動窗口的FGS快速帶寬分配算法，它根據相鄰幀的差異程度，以小滑動窗口插幀的方法來達到現有算法中大滑動窗口的效果，從而降低算法的時延。
本發明的技術解決方案一種基於滑動窗口的FGS快速帶寬分配算法，其特徵在於步驟如下 (1)由精細可擴展編碼FGS編碼器在編碼時提取當前編碼幀的速率-失真R-D(Rate-Distortion，R-D)曲線及絕對誤差和(Sum of Absolute Difference，SAD)信息曲線，即SAD信息，並將該幀存入滑動窗口，同時更新窗口的可用帶寬Rbudget； (2)若滑動窗口中真實幀數目小於預定閥值M，則轉到步驟(1)； (3)遍歷滑動窗口，對每個未做插幀處理的真實幀根據其SAD信息做插幀處理，其中插入幀標記為虛假幀，更新窗口的可用帶寬Rbudget； (4)根據插幀處理後的滑動窗口以及各個幀的R-D曲線，以當前窗口的可用帶寬Rbudget為上限，運行FGS帶寬分配算法； (5)根據FGS帶寬分配算法運行結果發送滑動窗口中第一幀，清除該幀及相關虛假幀，更新窗口可用帶寬值Rbudget，若還有未發送幀，則轉到步驟(1)。
根據本發明的又一個方面，其中步驟(1)進一步包括步驟 (a)由FGS編碼器在編碼時提取當前編碼幀的R-D曲線及SADavg值； (b)將當前編碼完成的視頻幀放入滑動窗口； (c)設滑動窗口內M幀的可用帶寬上限為Rbudget，算法開始時Rbudget為0，用下式更新RbudgetRbudget＝Rbudget+Rcur/fps，其中fps為發送端幀率，Rcur為當前實際測得的網絡可用帶寬，並記錄Rcur的值； 根據本發明的又一個方面，其中步驟(3)進一步包括 (a)根據標記查找滑動窗口內未做插幀處理的真實幀； (b)若第m幀為尚未做插幀處理的真實幀，則根據其SADavg值由方法getInsertNum得到值InsertNum，在窗口內第m幀之後插入InsertNum個第m幀，這樣窗口中就會有一模一樣的InsertNum+1個第m幀，同時標記區分真實幀和插入的虛假幀； (c)如果InsertNum的值大於0則以下式更新窗口的可用帶寬值Rbudget其中Rm是編碼第m幀時記錄的可能帶寬，Rn則是下一個真實幀在編碼時記錄的可能帶寬；若第m幀已經是窗口內最後一個真實幀，則取Rn＝Rm，即上式退化為 根據本發明的又一個方面，其中步驟(5)進一步包括 (a)根據算法結果發送滑動窗口內第一幀； (b)清除發送出去的那一幀，及與該幀相關的所有虛假幀； (c)更新窗口的可用帶寬Rbudget，令其中ri為當前發送幀的碼率，rj則是各個插入的虛假幀根據步驟(4)分配的發送碼率，InsertNum是該幀插入虛假幀的數量。
本發明與現有技術相比的優點在於本發明考慮視頻會議系統中，實時交互效果的需求，根據相鄰幀的差異程度，通過小滑動窗口插幀的方法來達到原來算法中大滑動窗口的效果。實驗表明，在不降低太多帶寬分配效能的前提下，該算法能充分達到低時延的目的。
圖1為本發明的算法基本流程圖； 圖2為已有算法的發送端緩衝區狀態圖； 圖3為本發明算法的發送端緩衝區狀態圖； 圖4為標準測試序列Foreman相應視頻幀的R-D曲線圖； 圖5為標準測試序列Coastguard相應視頻幀的R-D曲線圖； 圖6為本發明的實際測試時採用的可用帶寬變化圖； 圖7為本發明的實際測試碼率分配的比較圖； 圖8為本發明的實際測試延遲改善的比較圖。
具體實施例方式 下面參考附圖，對本發明的實施例進行詳細的說明。
首先對本發明的算法原理進行說明。
研究表明，相鄰視頻幀之間有著較強的時空相關性(這也是很多編碼器工作的原理所在)。這些相關性造成了編碼後相鄰幀的R-D曲線差異甚小；當然，若視頻中有鏡頭轉動、場景切換等，那麼幀之間的差異將會較大。如圖4、5所示，標準測試序列Foreman_Cif的第27、28、29幀的R-D曲線差異甚小，而Coastguard_Cif在第67、68、69幀處有鏡頭移動，故R-D曲線存在較大差異。本發明的算法利用了這種時空相關性設定較小的滑動窗口，依據相鄰幀之間的差異程度(一般以幀之間絕對誤差和SAD來量化衡量)，對小窗口內的各個視頻幀進行插幀處理，以達到原來算法大滑動窗口的效果，從而快速分配碼率。
具體而言，本發明所提出的改進算法基本流程如圖1所示。
本發明主要包括的核心思想根據視頻幀的SAD信息，以小滑動窗口插幀的方法來達到現有帶寬分配算法中大滑動窗口的效果，從而有效降低算法本身時延，但又不損失太多帶寬分配效能。
在描述算法前先定義如下變量及方法 1.設視頻幀率為fps，滑動窗口大小為M，令M＝αfps； 2.設窗口內M幀的可用帶寬上限為Rbudget，算法開始時令Rbudget＝0； 3.設視頻幀長為vHeight，寬為vWidth； 4.設SADm為第m幀的SAD值，定義該幀的平均SAD為SADavg＝SADm/vHeight/vWidth； 5.定義SAD閾值表SadThreshTable[1，...，n]＝{Sad1，Sad2，...，Sadn}，其中Sad1＜Sad2＜...＜Sadn；對應的插值數值表為InsertNumTable[1，...，n]＝{λ1，λ2，...，λn}，其中λ1＞λ2＞...＞λn。算法中就是將FGS編碼過程中得到的SADavg與SadThreshTable中預設的Sadi(1≤i≤n)比較，以判斷相應幀之後是否該插幀，以及該插入λi(1≤i≤n)幀。SADavg值越小說明前後幀差別不大可以插入較多的虛假幀，該值越大說明前後幀差距較大只能插入較少的虛假幀或者不能插入虛假幀； 6.方法getInsertNum定義如下 1)for i＝1 to n 2)if SADavg≤SadThreshTable[i]then 3)return InsertNumTable[i] 5)endif 6)endfor 7)return 0 本發明的算法描述如下 1.由FGS編碼器在編碼時提取當前編碼幀的R-D曲線及SADavg值，將其放入緩衝區，同時用下式更新RbudgetRbudget＝Rbudget+Rcur/fps，其中Rcur為當前實際測得的網絡可用帶寬，並記錄Rcur的值； 2.如果滑動窗口中真實視頻幀的數量小於M，則轉到步驟1； 3.遍歷滑動窗口，對每個未做插幀處理的真實幀(設為第m幀)做插幀處理根據第m幀的SADavg由方法getInsertNum得到值InsertNum，在第m幀之後插入InsertNum個第m幀。這樣窗口中會有InsertNum+1個第m幀。同時標記區分真實幀和虛假幀，若InsertNum大於0，則用下式更新Rbudget 其中Rm是編碼第m幀時記錄的可能帶寬，Rn則是下一個真實幀在編碼時記錄的可能帶寬；若第m幀已經是窗口內的最後一個真實幀，則取Rn＝Rm，即上式退化為 4.根據插幀處理後的滑動窗口以及各個幀的R-D曲線，以當前窗口的可用帶寬Rbudget為上限，運行現有的一種FGS帶寬分配算法；這裡，現有的算法可以是牛頓搜索法，二分搜索法，R-D曲線合成法等；以二分搜索法為例，運行算法的步驟如下 a.計算只發送窗口內所有幀基本層的最小失真Dw； b.計算若R＜Rbudget-δ，則令Dmin＝Dw；若R＞Rbudget+δ，則令Dmax＝Dw； c.否則，結束算法 算法中的Dmin和Dmax為預定義的最小和最大失真，δ則是平衡因子，保證算法在有限步驟內結束，Ri(D)則是各個視頻幀的R-D曲線方程。
5.根據算法結果發送滑動窗口中第一幀。清除該幀及與該幀相關的虛假幀，用下式更新Rbudget其中ri為當前發送幀碼率，InsertNum則是插入的虛假幀的數量，rj則是各個虛假幀根據步驟(4)分配的發送碼率。若還有未發送幀，轉到步驟1；否則，結束算法。
本發明的算法與原有算法最大的不同之處是運行算法前滑動窗口內不僅含有未發送的幀數據，還包含了根據每幀SAD值插入的虛假幀。這樣，真正運行算法的窗口大小不是M，而是插幀後的大小(如圖2，3所示)。如此一來，本發明就可以設定一個較小的滑動窗口，來達到原有算法需要的較大的滑動窗口。此外，α以及SadThreshTable和InsertNumTable的定義值應根據具體的應用而定。
以下通過本發明算法和現有算法的對比，對本發明在保障帶寬分配效能的前提下有效降低算法時延的改進予以說明。測試實驗採用標準測試序列Foreman_Cif，其解析度為352×288，共200幀，幀率取為20，即測試時間長度為10秒。
實驗以R-D曲線合成法和本發明的算法作對比。其中R-D曲線合成法的滑動窗口分別為50和10，本發明的算法取α為0.5，即滑動窗口大小為10。測試中所用的帶寬變化如圖6所示。此外，測試中定義SadThreshTable和InsertNumTable取值如下SadThreshTable[6]＝{2，4，8，16，32，64}，InsertNumTable[6]＝{10，8，6，4，2，1}(這些值為經驗值)。
如圖7所示，改進後的快速分配算法要好於同樣小窗口的R-D曲線合成法，且在多項統計上都較接近於使用大窗口的R-D曲線合成法。如圖8所示，由於使用了小滑動窗口，本發明的算法在處理每幀的消耗時間上卻有了大幅改進。
應用本發明的多媒體實時交互系統已多次在教育部、科技部的視頻會議中得到應用。在教育部，超過150個大學和各個省市的教育主管部門已經使用該系統作為教育部內部的協同和會議平臺。證明了實際的應用效果。
對於本領域的普通技術人員來說可顯而易見的得出其他優點和修改。因此，具有更廣方面的本發明並不局限於這裡所示出的並且所描述的具體說明及示例性實施例。因此，在不脫離由隨後權利要求及其等價體所定義的一般發明構思的精神和範圍的情況下，可對其作出各種修改。
權利要求
1.一種基於滑動窗口的FGS帶寬快速分配算法，其特徵在於步驟如下
(1)由精細可擴展編碼FGS編碼器在編碼時提取當前編碼幀的速率-失真R-D曲線及絕對誤差和SAD信息，並將該幀存入滑動窗口，同時更新窗口的可用帶寬Rbudget；
(2)若滑動窗口中真實幀數目小於預定閥值M，則轉到步驟(1)；
(3)遍歷滑動窗口，對每個未做插幀處理的真實幀根據其SAD信息做插幀處理，其中插入幀標記為虛假幀，更新窗口的可用帶寬Rbudget；
(4)根據插幀處理後的滑動窗口以及各個幀的R-D曲線，以當前窗口的可用帶寬Rbudget為上限，運行FGS帶寬分配算法；
(5)根據FGS帶寬分配算法運行結果發送滑動窗口中第一幀，清除該幀及相關虛假幀，更新窗口可用帶寬值Rbudget，若還有未發送幀，則轉到步驟(1)。
2.根據權利要求1的一種基於滑動窗口的FGS帶寬快速分配算法，其特徵在於所述的步驟(1)進一步包括
(a)由FGS編碼器在編碼時提取當前編碼幀的R-D曲線及SADavg值；
(b)將當前編碼完成的視頻幀放入滑動窗口；
(c)設滑動窗口內M幀的可用帶寬上限為Rbudget，算法開始時Rbudget為0，用下式更新RbudgetRbudget＝Rbudget+Rcur/fps，其中fps為發送端幀率，Rcur為當前實際測得的網絡可用帶寬，並記錄Rcur的值。
3.根據權利要求1的一種基於滑動窗口的FGS帶寬快速分配算法，其特徵在於所述的步驟(3)進一步包括
(a)根據標記查找滑動窗口內未做插幀處理的真實幀；
(b)若第m幀為未做插幀處理的真實幀，則根據其SADavg值由方法getInsertNum得到值InsertNum，在窗口內第m幀之後插入InsertNum個第m幀。這樣窗口中就會有一模一樣的InsertNum+1個第m幀，同時標記區分真實幀和插入的虛假幀；
(c)如果InsertNum的值大於0則以下式更新窗口的可用帶寬值Rbudget其中Rm是編碼第m幀時記錄的可能帶寬，Rn則是窗口內下一個真實幀在編碼時記錄的可能帶寬；若第m幀已經是窗口內最後一個真實幀，則取Rn＝Rm，即上式退化為
4.根據權利要求1的一種基於滑動窗口的FGS帶寬快速分配算法，其特徵在於所述的步驟(5)進一步包括
(a)根據算法結果發送滑動窗口內第一幀；
(b)清除發送出去的那一幀，及與該幀相關的所有虛假幀；
(c)更新窗口的可用帶寬Rbudget，令其中ri為當前發送幀的碼率，rj則是各個插入的虛假幀根據步驟(4)分配的發送碼率，InsertNum是該幀插入虛假幀的數量。
全文摘要
一種基於滑動窗口的FGS帶寬快速分配算法(1)由FGS編碼器在編碼時提取當前編碼幀的R-D曲線及絕對誤差和SAD)信息，並將該幀放入滑動窗口內，更新窗口的可用帶寬值；(2)若滑動窗口內真實幀數目小於預定閥值M，則轉到步驟(1)；(3)遍歷整個滑動窗口，對每個未做插幀處理的真實幀根據其SAD信息做插幀處理，其中插入幀標記為虛假幀，更新窗口的可用帶寬值；(4)根據插幀處理後的滑動窗口以及各個幀的R-D曲線，以當前窗口的可用帶寬為上限，運行FGS帶寬分配算法；(5)根據算法結果發送滑動窗口內第一幀，清除該幀及相關的虛假幀，更新窗口可用帶寬，若還有未發送幀則轉到步驟(1)。本發明根據相鄰幀的差異程度，以小滑動窗口插幀的方法來達到現有算法中大滑動窗口的效果，從而降低算法時延。
文檔編號H04N7/26GK101119489SQ20071012047
公開日2008年2月6日 申請日期2007年8月20日 優先權日2007年8月20日
發明者華 繆, 單寶松, 強 曾, 劉祥龍 申請人:北京航空航天大學