SLWE概率估計方法在區(qū)間編碼中的應(yīng)用研究

陳　浩， 宿騰野， 滑　藝， 劉　東

(哈爾濱工業(yè)大學(xué) 電子與信息工程學(xué)院，150001 哈爾濱)

?

SLWE概率估計方法在區(qū)間編碼中的應(yīng)用研究

陳浩， 宿騰野， 滑藝， 劉東

(哈爾濱工業(yè)大學(xué) 電子與信息工程學(xué)院，150001 哈爾濱)

摘要:SLWE概率估計方法具有較強的適應(yīng)非平穩(wěn)數(shù)據(jù)能力，為拓展其在熵編碼中的應(yīng)用，更有效地編碼非平穩(wěn)數(shù)據(jù)，設(shè)計在區(qū)間編碼上的應(yīng)用方案. 首先針對概率估計模型替換時SLWE估計出的概率如何映射到區(qū)間的問題，不進行概率更新的計算，而是基于SLWE思想直接更新各字符所占區(qū)間大小，再根據(jù)區(qū)間編碼中總區(qū)間上下界計算方法調(diào)整總區(qū)間. 既結(jié)合SLWE應(yīng)對非平穩(wěn)數(shù)據(jù)的優(yōu)勢，又避免概率運算. 同時，針對更新各字符所占的整型數(shù)據(jù)區(qū)間后字符所占區(qū)間大小可能小于1導(dǎo)致編碼字符丟失的問題，采用設(shè)定每種字符最小區(qū)間作為閾值的控制方法. 對非平穩(wěn)數(shù)據(jù)編碼的實驗結(jié)果表明，基于SLWE的區(qū)間編碼比基于加窗法等傳統(tǒng)概率估計方法的壓縮率要高出1%～5%.

關(guān)鍵詞:熵編碼； 非平穩(wěn)數(shù)據(jù)； 隨機學(xué)習(xí)弱估計； 概率估計； 區(qū)間編碼

隨著編碼技術(shù)的發(fā)展，各種熵編碼方法應(yīng)運而生，如香農(nóng)編碼、霍夫曼編碼、算術(shù)編碼、區(qū)間編碼等. 熵編碼的編碼性能主要依賴概率估計模型與信源的實際特性相符的程度. 根據(jù)待編碼數(shù)據(jù)的統(tǒng)計特性不同，熵編碼的概率估計方法也有相應(yīng)的不同. 當(dāng)待編碼數(shù)據(jù)特性平穩(wěn)時，經(jīng)典的概率估計方法是最大似然法和貝葉斯參數(shù)估計法[1]；當(dāng)待編碼數(shù)據(jù)特性非平穩(wěn)時，主要的概率估計方法為基于“遺忘因子”的方法和加窗法.

文獻[3]提出基于“遺忘因子”的想法，當(dāng)已編碼字符總數(shù)達到一個事先設(shè)定的閾值時，將各種類字符的累積頻率乘上一個大于0小于1的實數(shù)，稱為“尺度調(diào)節(jié)(rescaling)”，所乘的實數(shù)叫做“遺忘因子(forgetting Factor)”. 而加窗法是通過分析一段特定緩存中的內(nèi)容去估計信源當(dāng)前待編碼符號的概率分布，這段緩存中存有W個之前已編碼的字符(即緩存長度是W，也可稱為窗長)，每編碼完一個新字符后，緩存中的內(nèi)容會進行一次移位，新字符存入到緩存中，最早進入緩存的字符被刪除. 文獻[4]從理論上分析了加窗法在非平穩(wěn)環(huán)境下的編碼性能，并討論了窗長與編碼冗余的關(guān)系.

近年來，弱估計算法為非平穩(wěn)數(shù)據(jù)的概率估計供了新的思路，其中有代表性的是隨機學(xué)習(xí)弱估計SLWE(stochastic learning weak estimator)，它是一種基于學(xué)習(xí)自動機LA(learning automata)理論的參數(shù)估計方法. LA屬于機器學(xué)習(xí)中的增強學(xué)習(xí)，文獻[7]提出，最初用于模擬生物在出生時具備很少的先天知識，不斷與隨機環(huán)境交互下的學(xué)習(xí)過程. Oommen及其合作者提出了在非平穩(wěn)環(huán)境下估計二項式和多項式分布的方法[5-7]. SLWE應(yīng)用在概率估計中，可節(jié)省加窗法的窗口中數(shù)據(jù)緩存的存儲空間，同時對于非平穩(wěn)數(shù)據(jù)有了更強的適應(yīng)性，并對多種類型的數(shù)據(jù)編碼均可使用[8].

文獻[9]曾嘗試將SLWE概率估計方法應(yīng)用FANO編碼這種并不常用的熵編碼中，并給出相應(yīng)的實現(xiàn)方法. 為拓展SLWE原理在熵編碼中的應(yīng)用，更有效的實現(xiàn)對非平穩(wěn)數(shù)據(jù)的壓縮編碼，將其在編碼性能更優(yōu)良的區(qū)間編碼上進行實現(xiàn). 區(qū)間編碼是由Martin提出[10]，與算術(shù)編碼本質(zhì)上類似，盡管在精度上稍微遜色，但比算術(shù)編碼在頻度統(tǒng)計中速度快很多[11]. 將SLWE概率估計方法應(yīng)用到區(qū)間編碼時，把原本的由概率更新改變各字符所占區(qū)間大小，從而通過總區(qū)間上下界的變化進行區(qū)間更新的方式，改進為將SLWE算法直接應(yīng)用到對各字符所占區(qū)間大小的改變上的方法，不先進行概率更新的計算，而是直接用SLWE算法中的思想對各字符所占區(qū)間大小進行更新，再根據(jù)區(qū)間編碼中總區(qū)間上下界計算方法來調(diào)整總區(qū)間大小，既結(jié)合了SLWE對非平穩(wěn)數(shù)據(jù)概率估計的優(yōu)勢，又避免了概率的具體運算. 從而提高編碼過程對非平穩(wěn)數(shù)據(jù)壓縮編碼的運算精度以及編碼效率.

1基于隨機學(xué)習(xí)弱估計的概率估計方法

1.1二項分布的SLWE概率估計過程

二項分布又稱伯努利分布，其特征由兩個參數(shù)決定：試驗的次數(shù)n和每次試驗成功的概率p，如果將二值信源每次產(chǎn)生二值符號的過程看做一次伯努利試驗，那么二項分布的參數(shù)估計問題就可看作通過編碼二值序列對信源特性進行估計的問題. 假設(shè)X是一個二項分布的隨機變量，取值為“1”或“2”，并且X遵循概率分布Q=[q1,q2]T，即

其中q1+q2=1.

設(shè)X(n)是隨機變量X在時刻n的具體值，根據(jù)SLWE理論，對于X(n)的概率估計是一個動態(tài)的過程，設(shè)對X(n)概率估計為P(n)=[p1(n),p2(n)]T，如果有參數(shù)λ稱為學(xué)習(xí)因子(0<λ<1)，則其概率更新方式如下：

(1)

1.2多項分布的SLWE概率估計過程

同樣，令x(n)為變量X在n時刻的實際觀測值，假設(shè)n時刻對Q的概率估計矢量為P(n)=[p1(n),…,pr(n)]T，其中pi(n)表示在n時刻對qi的估計，則根據(jù)SLWE理論，pi(n)更新方式如下

(2)

式中i,j為多項分布X中的任意變量，且j≠i，參數(shù)λ稱為學(xué)習(xí)因子，0<λ<1.

將運用多項分布情況下的SLWE概率估計方法，在信源信息為非平穩(wěn)數(shù)據(jù)的情況下，對區(qū)間編碼進行改進，以提高其編碼性能.

2區(qū)間編碼方法

一般的區(qū)間編碼以各種符號的統(tǒng)計頻率來估計概率，其編碼端和解碼端工作原理如下.

編碼端：輸入是信源符號集合S和待編碼序列Z，輸出是編碼產(chǎn)生的碼流Y. 處理步驟如下：

步驟1統(tǒng)計信源基本信息. 以字節(jié)為單位讀取待編碼數(shù)據(jù)，統(tǒng)計待編碼數(shù)據(jù)字節(jié)長度BBSIZE，字符種類數(shù)N.

步驟2初始化概率估計模型. 設(shè)定在n時刻總區(qū)間大小為R(n)，信源符號集合S中各符號的頻率為fi(n)，其中i表示S中第i種字符(0≤i≤N-1)，所有編碼數(shù)據(jù)的總頻率為FTF(n)(TotalFrequency)，

在n=0時刻，初始化累積頻率為ccumf(0)=0.

步驟4編碼和區(qū)間規(guī)格化. 首先定義在n時刻待編碼字符i的概率為pi(n)=fi(n)/FTF(n)，編碼順序在字符i之前的字符0到i-1的累計概率為ccump(n)=ccumf(n)/FTF(n)，則當(dāng)前總區(qū)間按照各個符號的概率進行更新，區(qū)間更新方法為

(3)

式中：L(n)為總區(qū)間下界，R(n)為區(qū)間范圍，L(n+1)為更新后的總區(qū)間下界，R(n+1)為更新后的區(qū)間范圍，當(dāng)更新后的區(qū)間范圍小于指定閾值R0時，或者以字節(jié)為單位比較新區(qū)間的上下界并且上下界的高位字節(jié)相等時，移出高位的字節(jié)作為輸出碼流，同時對區(qū)間進行規(guī)格化處理.

同時對累積頻率進行更新:

按照步驟3～5所述依次對所有8bit字符進行編碼. 為能夠準(zhǔn)確的進行解碼操作，需要對最后一個符號的映射區(qū)間范圍完全移出，同時保留該區(qū)間內(nèi)某一個二進制數(shù)V，形成碼流Y，并將其傳遞給解碼器.

解碼端：輸入是編碼產(chǎn)生的碼流Y，信源符號集合S，輸出是解碼序列Z. 處理步驟如下：

步驟1讀取信源基本信息以及待解碼文件，得到原數(shù)據(jù)長度BBSIZE，符號種類數(shù)N，以及編碼時保留的最后一個符號區(qū)間內(nèi)的二進制數(shù)V.

步驟2初始化概率模型，方法與編碼端相同.

步驟3計算累積頻率估計值ccumfe(n)，由公式

從而有

令ccumfe(0)=(V-L(0))/(R(0)/TTF(0))，得到累積概率的初始估計值，并且有估計不等式:

每編碼一個字符，保持在當(dāng)前n時刻的估計式ccumf(n)≤ccumfe(n)<(ccumf(n)+fi(n))，從而根據(jù)此式估計ccumfe(n)值.

步驟4解碼器解碼與編碼器編碼保持一致，根據(jù)累計頻率估計值，輸出所在區(qū)間的字符，并更新當(dāng)前區(qū)間范圍，即L(n+1)←L(n)+R(n)×ccumfe(n)/FTF(n),

R(n+1)←R(n)×fi(n)/FTF(n).

并判斷是否需要區(qū)間規(guī)格化.

步驟5根據(jù)步驟4中解碼出的字符更新頻率表，并根據(jù)當(dāng)前區(qū)間范圍以及新的頻率表重新為各字符分配所屬區(qū)間.

按照上述步驟3～5所述依次對所有8bit字符進行編碼，直到解碼結(jié)束.

本文重點研究如何用SLWE算法實現(xiàn)編碼端和解碼端步驟5中概率更新的過程，并對實現(xiàn)過程中所遇到的相關(guān)問題給出解決和改進方法.

3基于SLWE的區(qū)間編碼設(shè)計方法

首先通過對原區(qū)間編碼過程的分析.

1)SLWE應(yīng)用到區(qū)間編碼中，核心是概率估計模型替換的過程，但同時會面臨新的概率模型所估計出的概率如何映射到區(qū)間的問題.

在原區(qū)間編碼中，各種字符在n時刻的估計概率是pi(n)=fi(n)/FTF(n)，可知各種字符的概率更新是由頻率的更新得到. 并由式(3)，每編碼一個字符，按照相應(yīng)各字符概率的變化來計算新的區(qū)間下界，從而將概率映射到區(qū)間，進行區(qū)間更新，最后根據(jù)區(qū)間的變化得到輸出碼流.

而SLWE應(yīng)用到區(qū)間編碼時，考慮區(qū)間編碼的輸出碼流是由區(qū)間的不斷更新變化得到的. 因此，可將式(3)中R(n)×ccump(n)設(shè)定為n時刻待編碼字符i之前的字符0～i-1的累積區(qū)間，即：CCUMR(n)=R(n)×ccump(n)，同時將R(n)×pi(n)設(shè)定為n時刻待編碼字符i所占區(qū)間的大小，即

從而

同時，將SLWE應(yīng)用到區(qū)間編碼時，由于各種字符的估計概率是用區(qū)間代替的，在每編碼一個字符時，總區(qū)間都會發(fā)生變化，相應(yīng)的各種字符所占區(qū)間也需要進行同比例的縮放，從而才能保證當(dāng)前各種字符的估計概率不變. 因此，在每編碼完一個字符時，記錄下編碼前后總區(qū)間的變化情況，編碼前總區(qū)間為R(n)，編碼后總區(qū)間大小為R(n+1)，每次編碼之后記錄下m=R(n+1)/R(n)，則非待編碼字符i所占區(qū)間更新為rj(n+1)=λ×[m×rj(n)]，其中，j=0,…,N-1,j≠i.

2)由于設(shè)定了各字符所占區(qū)間，而計算機實現(xiàn)時，區(qū)間是用整型數(shù)據(jù)表示，在對個字符所占區(qū)間進行更新時，更新后的各種字符所占區(qū)間大小可能出現(xiàn)小于1的情況，從而可能導(dǎo)致編碼字符丟失的問題.

對此，對每種字符設(shè)定了最小區(qū)間r(n)min=R(n)×pmin≥1作為閾值，其中R(n)為當(dāng)前總區(qū)間，Pmin為經(jīng)驗參數(shù)，從而保證每編碼一個字符，總區(qū)間大小更新后，都會給出一個具體的最小區(qū)間，使得各字符所占區(qū)間的變化是有下限的，不能無限減小. 當(dāng)某一時刻計算出的某種字符所占的區(qū)間大小小于r(n)min時，以r(n)min作為該種字符的新區(qū)間.

綜上所述，結(jié)合區(qū)間編碼的整體框架，設(shè)計如圖1扭不的編碼端其工作流程如下：

步驟1統(tǒng)計信源基本信息. 以字節(jié)為單位讀取待編碼數(shù)據(jù)，統(tǒng)計待編碼數(shù)據(jù)長度BBSIZE，對不同種類符號編號的最大值為m0，符號編號的最小值為m1，符號種類數(shù)N=m0-m1+1，各符號種類分別用索引0,…,N-1表示；

步驟2初始化. 對32位系統(tǒng)，可初始化區(qū)間上界為H=0xffffffff，區(qū)間下界為L=0x00000000，則原始區(qū)間大小為R(0)=0xffffffff，初始化各個符號占據(jù)的初始區(qū)間長度為ri(0)=R(0)/N，i=0,…,N-1，初始化區(qū)間規(guī)格化時的臨界閾值R0=0x00001000.

步驟4編碼和區(qū)間規(guī)格化. 記錄當(dāng)前區(qū)間長度R(n)，然后根據(jù)當(dāng)前待編碼字符對區(qū)間進行更新，更新方式為：

L(n+1)←L(n)+CCUMR(n),R(n+1)←ri(n).

當(dāng)新區(qū)間長度R(n+1)≤R0或以字節(jié)為單位比較新區(qū)間的上界和下界，上下界的高位字節(jié)相等時，移出高位的字節(jié)作為輸出碼流，同時對區(qū)間進行規(guī)格化處理，具體做法為將R(n+1)和L(n+1)分別左移8位，即R(n+1)←R(n+1)?8，L(n+1)←L(n+1)?8. 最后計算編碼后區(qū)間和編碼前區(qū)間的比值m=R(n+1)/R(n)；

步驟5更新概率估計表. 根據(jù)SLWE算法，對各字符所在區(qū)間大小進行更新，具體過程與編碼端相同.

Step 1根據(jù)信源基本信息，給定參數(shù)pmin，并根據(jù)更新后的區(qū)間R(n+1)計算各字符所占區(qū)間的下限，即最小區(qū)間r(n+1)min=R(n+1)×pmin，初始化學(xué)習(xí)因子λ，設(shè)n+1刻除字符i外的其他字符所占區(qū)間為SSUMR(0)=0.

Step 2依次計算序號為j=0,…,N-1, j≠i的字符所占區(qū)間大小.

其中j=0,…,N-1,j≠i.

Step 4計算ri(n+1)=R(n+1)-SSUMR(n+1).

步驟6編碼收尾階段. 按照步驟3～5，對所有待編碼數(shù)據(jù)進行編碼. 編碼結(jié)束時，移出映射區(qū)間內(nèi)所有的位. 分別將碼流和待編碼數(shù)據(jù)的相關(guān)信息以文件形式保存.

同時設(shè)計了如圖2所示的解碼端框架，工作流程如下：

步驟1讀取信源基本信息文件，得到原數(shù)據(jù)長度BBSIZE，對不同種類符號最大值m0，符號編碼最小值m1，計算符號種類數(shù)N=m0-m1+1.

步驟2與編碼過程中的初始化過程一樣初始化區(qū)間上界H=0xffffffff、區(qū)間下界L=0x00000000，初始化各個符號占據(jù)的初始區(qū)間長度ri(0)=R(0)/N，i=0,…,N-1，初始化區(qū)間規(guī)格化時的臨界閾值R0=0x00001000. 并以字節(jié)為單位讀取碼流文件，設(shè)定初始標(biāo)識符T=0x00000000，通過計算機運算，將每4個字節(jié)碼流信息存儲于T.

步驟3根據(jù)T和當(dāng)前區(qū)間下界L以及各符號的區(qū)間長度進行解碼，解碼過程中得到當(dāng)前符號的索引i. 具體做法為尋找滿足下述關(guān)系的i:

步驟4首先記錄當(dāng)前區(qū)間長度R(n)，然后根據(jù)i對區(qū)間進行更新，更新方式與編碼過程中的更新方式一致，即

更新后的區(qū)間長度為第i種字符所在的區(qū)間長度ri(n+1)，即R(n+1)←ri(n+1). 當(dāng)新區(qū)間長度R(n+1)小于指定閾值R0或以字節(jié)為單位比較新區(qū)間的上界和下界，上下界的高位字節(jié)相等時，對區(qū)間進行規(guī)格化處理，即：將R(n+1)和L(n+1)分別左移8位，R(n+1)←R(n+1)?8， L(n+1)←L(n+1)?8，同時以字節(jié)為單位讀取碼流文件并與T進行或運算，之后將T左移8位. 計算編碼后區(qū)間和編碼前區(qū)間的比值m=R(n+1)/R(n).

步驟5根據(jù)SLWE算法對各字符所在區(qū)間大小進行更新，具體過程如下：

Step 1根據(jù)信源基本信息，給定參數(shù)Pmin，并根據(jù)更新后的區(qū)間R(n+1)計算各字符所在區(qū)間的下限R(n+1)min=R(n+1)·Pmin，初始化學(xué)習(xí)因子λ，定義變量SSUMR(0)=0.

Step 2依次計算序號為，j=0,…,N-1, j≠i的字符所占區(qū)間大小

Step 4計算ri(n+1)=R(n+1)-SSUMR(n+1).

輸出此次解碼后得到的字符，形成解碼有序.

步驟6當(dāng)解出的數(shù)據(jù)總長度小于原數(shù)據(jù)長度BBSIZE時，重復(fù)進行步驟3、4、5.

圖1　編碼流程圖

圖2　解碼流程圖

4實驗結(jié)果及討論

實驗中，對仿真數(shù)據(jù)在不同概率估計方法下的熵值進行分析和比較，驗證基于SLWE的概率估計方法對信源熵值估計的有效性. 并在試驗中考察學(xué)習(xí)因子λ在何種范圍下，概率估計的效果較好. 對真實數(shù)據(jù)的編碼實驗中，應(yīng)用已有的基于不同概率估計方法的區(qū)間編碼原理，分別對不同的數(shù)據(jù)類型進行編碼實驗，并對相應(yīng)的壓縮率進行比較和有針對性的分析，從而驗證基于SLWE的區(qū)間編碼方法，在編碼非平穩(wěn)數(shù)據(jù)時的優(yōu)越性.

4.1面向仿真數(shù)據(jù)的概率估計實驗

本部分實驗主要根據(jù)各概率估計算法對仿真數(shù)據(jù)的估計熵與其實際熵的偏離程度評價各算法的適用情況. 表1是對不同特性仿真數(shù)據(jù)的真實熵值，靜態(tài)模型以及add-half準(zhǔn)則的估計熵，和用SLWE方法的估計熵之間的比較情況. 其中，對于靜態(tài)模型，在編碼過程中概率模型不隨時刻的改變而改變. 靜態(tài)概率模型的建立往往需要信源的先驗知識，若沒有相關(guān)的先驗知識，可通過遍歷整個待編碼字符串，統(tǒng)計其分布特征來建立概率模型.

“add-half”法則是由Krichevskii提出的對貝葉斯參數(shù)估計法的一種實現(xiàn)方法[12]，從通用編碼(Universal coding)角度來說，在貝葉斯參數(shù)估計法中，“add-half”法則是最優(yōu)的.

仿真數(shù)據(jù)為二值偽隨機序列，L表示某種給定概率特性的信源持續(xù)作用的時間，N為不同種類信源的個數(shù)，L越大說明某種信源持續(xù)作用的時間越長，表示其統(tǒng)計特性越平穩(wěn)，N越大說明該仿真數(shù)據(jù)特性變化的越頻繁，表示其統(tǒng)計特性越不平穩(wěn). 另外，為了更貼近實際數(shù)據(jù)的特性變化，上述過程中的L可設(shè)置為可變的，這種情況下用Lmax為產(chǎn)生的數(shù)據(jù)中可能的最大平穩(wěn)段數(shù)據(jù)長度.

實驗中首先產(chǎn)生指定特性的仿真數(shù)據(jù)，然后分別計算仿真數(shù)據(jù)的真實熵以及用各種概率估計算法得到的概率模型下的估計熵(λ取0.9、0.95、0.99)，為了消除仿真數(shù)據(jù)的偶然性因素影響，每組實驗進行100次，取均值.

實驗結(jié)果見表1，當(dāng)數(shù)據(jù)特性非平穩(wěn)時(N=3, N=5的情況下)，SLWE算法的估計熵更接近真實熵，并且學(xué)習(xí)因子λ不同，逼近程度也不一樣.

圖3給出信源特性不同時，SLWE方法中不同學(xué)習(xí)因子λ下概率估計算法的概率估計曲線與反映信源真實特性的概率曲線之間的關(guān)系. 從圖中可以看出，λ的大小主要影響信源特性發(fā)生突變時概率估計曲線相對于信源真實特性變化曲線的滯后情況，λ較小時，概率估計曲線滯后較小，而λ較大時(接近1)，概率估計曲線滯后較大. 但λ較小時，概率估計曲線的波動較大，說明此時概率模型易受已編碼符號中短暫的異常分布影響，而λ較大時，這種影響就很弱，表現(xiàn)為曲線波動較小.

另外，對于表1中給出的幾種情況，均為λ=0.95時，估計效果最佳. 圖4是對于Lmax=10 000, N=10和Lmax=10 000, N=5兩種特性的二值仿真數(shù)據(jù)分別在上述兩種方法在給定參數(shù)選擇范圍下均選取最優(yōu)參數(shù)時估計熵與真實熵的相對偏差曲線比較情況. 從圖中可看出，對于指定特性的仿真數(shù)據(jù)，兩種方法在均選取最優(yōu)參數(shù)的情況下，相對偏差曲線非常接近，SLWE算法略小于加窗法.

圖3　不同學(xué)習(xí)因子λ下SLWE概率跟蹤曲線

(a) L=10 000, N=10

(b) L=10 000, N=5

4.2面向真實數(shù)據(jù)的編碼實驗

本部分利用第3節(jié)中設(shè)計的基于SLWE概率估計算法的區(qū)間編碼對真實數(shù)據(jù)進行編碼實驗，并與基于靜態(tài)模型的區(qū)間編碼和基于遺忘因子法的區(qū)間編碼進行比較.

為驗證本文研究的概率估計算法應(yīng)用于實際熵編碼器對于編碼效果的影響，本文選取幾種常見格式的真實數(shù)據(jù)進行熵編碼實驗，相關(guān)介紹見表2. 數(shù)據(jù)的選取參考文獻[13]中的數(shù)據(jù)選取方法，主要包括bmp圖像、計算機中的系統(tǒng)文件、微軟word文檔和文本文檔，所選數(shù)據(jù)中前8種數(shù)據(jù)屬于非平穩(wěn)數(shù)據(jù)，后兩種Price.txt 和Rabinaranath Tagore.txt屬于平穩(wěn)數(shù)據(jù). 由于SLWE法與遺忘因子法的概率估計效果均與參數(shù)有關(guān)，為了公平起見，實驗中采用如下參數(shù)選取方式：遺忘因子法中設(shè)置β=0.5,Nmax=214，通過改變M調(diào)節(jié)算法的自適應(yīng)能力，M調(diào)節(jié)范圍為1～20，在給定的參數(shù)選擇范圍中選取壓縮率最高的M值，記錄下實驗結(jié)果；對于SLWE法，設(shè)置Pmin=0.001，通過改變λ調(diào)節(jié)算法的自適應(yīng)能力，λ的選取范圍為0.9到0.99，間隔為0.01，同樣在給定參數(shù)范圍內(nèi)選擇壓縮率最高的λ值，同樣記錄下實驗結(jié)果. 表中l(wèi)y表示碼流長度，B表示bytes，ρ為壓縮率，最后一欄Ave/tol列出所有實驗數(shù)據(jù)的總大小和壓縮后數(shù)據(jù)的總大小以及對各數(shù)據(jù)壓縮率的均值.

表2　實驗數(shù)據(jù)及相關(guān)描述

從表3中可看出SLWE算法與遺忘因子法一樣，在對非平穩(wěn)數(shù)據(jù)進行概率估計時能較好的適應(yīng)數(shù)據(jù)特性的變化，顯著的優(yōu)于靜態(tài)模型的概率估計效果，并且與遺忘因子法相比，在選定的數(shù)據(jù)范圍內(nèi)，SLWE算法也優(yōu)于遺忘因子法. 這說明SLWE算法非常適合非平穩(wěn)環(huán)境下的概率估計問題.

表3不同概率估計模型下的區(qū)間編碼編碼結(jié)果

5結(jié)論

本文以提高熵編碼的編碼性能為目的，以壓縮率為指標(biāo)，對熵編碼中概率估計模型進行改進. 編碼器參考的概率模型是否符合信源的實際特性會直接影響最后的編碼性能，當(dāng)待編碼數(shù)據(jù)特性非平穩(wěn)時，概率模型的建立問題將變得很復(fù)雜，原始概率模型往往會與信源的實際特性有所偏離，影響編碼性能，若概率模型能及時的反映待編碼數(shù)據(jù)這種特性變化，理論上可取得更好的編碼效果.

因此，本文設(shè)計基于SLWE的區(qū)間編碼方法為使概率模型所估計出的概率更好的映射到區(qū)間，在實現(xiàn)過程中，用區(qū)間累加替代原算法中的概率累加. 并且，通過設(shè)置最小區(qū)間避免了區(qū)間大小小于1的問題. 在對不同特性的非平穩(wěn)數(shù)據(jù)的概率估計仿真實驗和實際編碼實驗中，本文方法效果比加窗法和遺忘因子法等方法更好，這說明SLWE算法比較適合用于非平穩(wěn)數(shù)據(jù)的概率估計，同時改進后的區(qū)間編碼的編碼效率更高.

對于本文SLWE算法中的學(xué)習(xí)因子λ，通過仿真實驗得到最佳數(shù)值. 未來重點研究在于學(xué)習(xí)因子λ的選擇方法，實現(xiàn)學(xué)習(xí)因子λ可調(diào)的概率估計方法.

參考文獻

[1] DUTTWEILER D L, CHAMZAS C. Probability estimation in arithmetic and adaptive-Huffman entropy coders[J]. IEEE Transactions on Image Processing, 1995, 4(3): 237-246.

[2] MERHAV N, FEDER M. A strong version of the redundancy-capacity theorem of universal coding[J]. IEEE Transactions on Information Theory, 1995, 41(3): 714-722.[3]GALLAGER R G. Variations on a theme by Huffman[J]. IEEE Transactions on Information Theory, 1978, 24(6): 668-674.

[4]SSNEHAG P, SHAO W, HUTTER M. Coding of non-stationary sources as a foundation for detecting change points and outliers in binary time-series[C]//Proceedings of the Tenth Australasian Data Mining Conference-Volume 134. Australian Computer Society, Inc., 2012: 79-84.

[5]YAZIDI A, OOMMEN B J, GRAMMO O C. A novel stochastic discretized weak estimator operating in non-stationary environments[C]//IEEE International Conference on Computing, Networking and Communications, 2012: 364-370.

[6]TSETLIN M L. On the behavior of finite automata in random media[J]. Avtomatika I Telemekhanika．1961, 22(10):1345-1354．

[7]OOMMEN B J, RUEDA L. Stochastic learning-based weak estimation of multinomial random variables and its applications to pattern recognition in non-stationary environments[J]. Pattern Recognition, 2006, 39(3): 328-341.

[8]SUDIP M, SUKHCHAIN S, MANAS K. MIRACLE: Mobility Prediction Inside a Coverage Hole Using Stochastic Learning Weak Estimator[J]. IEEE Transactions on Cybernetics , 2015, PP(99): 1-12.

[9]RUEDA L, OOMMEN B J. Stochastic automata-based estimators for adaptively compressing files with nonstationary distributions[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2006, 36(5): 1196-1200.

[10]MARTIN G N N. Range encoding: an algorithm for removing redundancy from a digitized message[C]//Proc. Institution of Electronic and Radio Engineers International Conference on Video and Data Recording. [S. l.]:[s. n.], 1979:1-11

[11]EVGENY B, LIU Kai, LI Yunsong. An Efficient Adaptive Binary Range Coder and Its VLSI Architecture[J]. IEEE Transactions on Circuits and Systems for Video Technology. 2015, 25(8):1435-1446.

[12]KRICHEVSKIV R E. Universal Compression and Retrieval[M]. Dordrecht, the Netherlands: Kluwer, 1994:217.

[13]ROS M, CUELLAR M P, DELGDO M, VILA A. Online recognition of human activities and adaptation to habit changes by means of learning automata and fuzzy temporal windows[J]. Information Sciences, 2013, 220(10):86-101.

(編輯王小唯苗秀芝)

The application for probability estimation of SLWE on range coder

CHEN Hao， SU Tengye， HUA Yi， LIU Dong

(School of Electronics and Information Engineering, Harbin Institute of Technology, 150001 Harbin, China)

Abstract:The probability estimate method of SLWE can adapt to the non-stationary data. In order to expand its application in entropy coding and code non-stationary data more effectively, an application scheme of SLWE in the range coding is designed. Firstly, to tackle the problem how to map the estimated probability by SLWE to the coding interval, instead of calculating the update probability, we propose to update the range of every character directly based on the idea of SLWE and then adjust the total range according to the computing method of the upper and lower range bounds for range encoding. It not noly combines the advantage of SLWE to cope with the non-stationary data, but also avoids the probability calculation. In addition, the coding range after the update for every character may be less than 1, which causes the loss of the character. To solve this problem, we present a control method to set the minimum range of each character. Experimental results for non-stationary data coding show that the SLWE-based range coder achieves 1%～5% higher than that using traditional probability estimation (e.g. windowing method) in terms of compression ratio.

Keywords:entropy coding; non-stationary data; stochastic learning weak estimator; probability estimate; range coder

中圖分類號:TN911.73

文獻標(biāo)志碼:A

文章編號:0367-6234(2016)05-0043-08

通信作者:陳浩，hit_hao@hit.edu.cn.

基金項目:國家863項目2012AA12A405;國家自然科學(xué)基金61102159.

作者簡介:陳浩(1978-)，男，副教授，博士.

收稿日期:2015-11-30.

doi：10.11918/j.issn.0367-6234.2016.05.006