基于最短碼長(zhǎng)的Context加權(quán)編碼

摘 要：用Context加權(quán)來(lái)估計(jì)較為合理的條件概率分布并對(duì)當(dāng)前信源符號(hào)進(jìn)行編碼，能減小其編碼碼長(zhǎng)。本文對(duì)Context的加權(quán)系數(shù)進(jìn)行了研究，提出最優(yōu)化的權(quán)值是：多Context加權(quán)后，能夠使當(dāng)前信源符號(hào)的前m個(gè)信源符號(hào)的碼長(zhǎng)之和最短的那組權(quán)值。本文使用了多元優(yōu)化算法（MOA）對(duì)最短碼長(zhǎng)進(jìn)行尋優(yōu)從而得到最優(yōu)化的權(quán)值。并通過(guò)實(shí)驗(yàn)驗(yàn)證了該方法對(duì)于減小碼長(zhǎng)的有效性，得到已知信源長(zhǎng)度為10時(shí)，編碼的碼長(zhǎng)較短且計(jì)算復(fù)雜度低。

關(guān)鍵詞：Context加權(quán)；權(quán)值；多元優(yōu)化算法；最短碼長(zhǎng)

中圖分類(lèi)號(hào)：TP18

根據(jù)編碼理論可知，若對(duì)信源序列x1…xn進(jìn)行編碼，當(dāng)前符號(hào)的編碼長(zhǎng)度為：

但是p（xi/xi-1…x1）是不知道的，可用當(dāng)前符號(hào)xn之前的已知信源符號(hào)序列x1…xn來(lái)估計(jì)些個(gè)條件概率分布，這種估計(jì)條件概率的機(jī)制稱(chēng)為Context模型[1]。在p（xi/xi-1…x1）中如果已知的符號(hào)越多，而且所對(duì)應(yīng)的條件概率分布都有合理的估計(jì)，那么編碼的平均碼長(zhǎng)應(yīng)逐漸減小直至接近信源極限熵。假設(shè)用已知信源序列x1…xn對(duì)當(dāng)前信源符號(hào)xn進(jìn)行估計(jì)，M表示信源符號(hào)可能的取值個(gè)數(shù)，那么條件概率分布就有Mn-1個(gè)。當(dāng) 值較大時(shí)，在有限的已知信源符號(hào)中進(jìn)行統(tǒng)計(jì)，每種情況的條件概率分布將得不到充分的統(tǒng)計(jì)，造成“Context稀釋”，Rissanen將其稱(chēng)為“模型代價(jià)”[2]。為降低“模型代價(jià)”可以選取當(dāng)前符號(hào)之前的某k（k<

其中ωg為第g組模型所對(duì)應(yīng)的權(quán)值。用加權(quán)的方法合并多個(gè)Context模型既降低了“模型代價(jià)”又充分利用了多個(gè)已知符號(hào)的條件概率分布的信息，從而有可能降低對(duì)當(dāng)前信源符號(hào)xn編碼的碼長(zhǎng)。

如何對(duì)多個(gè)條件概率分布加權(quán)，在前人的研究中Willems等人提出了一種針對(duì)二進(jìn)制序列的CWT算法[3]，他們認(rèn)為在特定Context條件下所對(duì)應(yīng)的信源子序列可能是無(wú)記憶的也可能是有記憶的，該算法對(duì)這兩種模型下的概率分布進(jìn)行加權(quán)平均來(lái)獲得當(dāng)前符號(hào)的概率分布。Mahone等人采用的編碼同樣針對(duì)二進(jìn)制信源符號(hào)，其權(quán)值的調(diào)整是沿著編碼代價(jià)梯度方向進(jìn)行的[4]。Cao M D等人認(rèn)為權(quán)值ωg等于已知過(guò)去信源序列情況下模型g出現(xiàn)概率的大小。根據(jù)貝葉斯理論得出：模型g的權(quán)值ωg的負(fù)對(duì)數(shù)正比于利用該模型對(duì)過(guò)去信源序列進(jìn)行編碼所得的平均碼長(zhǎng)[5]。Pinho方法與Cao相近，但是其平均碼長(zhǎng)的計(jì)算是隨著編碼的進(jìn)行以遞歸濾波的辦法對(duì)權(quán)值進(jìn)行調(diào)整[6]。

上述的研究中均沒(méi)有涉及到權(quán)值的最優(yōu)化問(wèn)題，在本文中我們探索了權(quán)值的優(yōu)化問(wèn)題，主要思路是：希望加權(quán)后的條件概率分布對(duì)過(guò)去的一段已知信源序列進(jìn)行編碼的碼長(zhǎng)最短?？紤]到用優(yōu)化算法來(lái)尋找上述權(quán)值最優(yōu)解的結(jié)果可能不唯一，本文采用多元優(yōu)化算法（MOA），該算法允許在整個(gè)解空間內(nèi)找到多組最優(yōu)解且不容易陷入局部最優(yōu)。本文以下部分分別討論了碼長(zhǎng)的計(jì)算及其在Context加權(quán)中的應(yīng)用、多元優(yōu)化算法（MOA）、實(shí)驗(yàn)設(shè)計(jì)及分析，最后給出結(jié)論。

1 碼長(zhǎng)的計(jì)算

用多個(gè)Context模型進(jìn)行加權(quán)合并得到當(dāng)前符號(hào)的條件概率分布首先應(yīng)估計(jì)每個(gè)Context模型的條件概率分布。在模型g中對(duì)當(dāng)前信源符號(hào)xn而言若選取已知信源符號(hào)xn-n1（g）…xn-nk（g）作為條件，則所有可能的組合有I=Mk種，于是該模型中所有Context組合可用集合D（g）={Ci（g） |i=1…I}表示。假設(shè)p（xn=j/Ci（g））表示在該模型中出現(xiàn)第i號(hào)Context組合時(shí)當(dāng)前符號(hào)取值為j的條件概率，則該概率可用下式估計(jì)：

在對(duì)當(dāng)前信源符號(hào)xn進(jìn)行編碼時(shí)，根據(jù)公式1可知當(dāng)前符號(hào)的編碼長(zhǎng)度與當(dāng)前符號(hào)的條件概率有關(guān)，而當(dāng)前符號(hào)的條件概率是由多個(gè)Context模型中當(dāng)前條件概率分布加權(quán)合并而成的（公式2）。若當(dāng)前信源符號(hào)取值為j時(shí)，加權(quán)后的條件概率P（xn=j/Cω）實(shí)際上是下式計(jì)算的：

于是最優(yōu)化的權(quán)值為：G組Context加權(quán)后，能夠使當(dāng)前信源符號(hào)的前m個(gè)信源符號(hào)的碼長(zhǎng)之和最短的那組權(quán)值?？紤]到信源的相關(guān)性，下一段信源序列編碼時(shí)，使用該組權(quán)值對(duì)多組Context加權(quán)后進(jìn)行編碼也應(yīng)得到較短的碼長(zhǎng)。由于統(tǒng)計(jì)特性會(huì)隨時(shí)間變化，條件概率也是逐漸改變的，在一段信源編碼后應(yīng)對(duì)權(quán)值進(jìn)行更新。

2 多元優(yōu)化MOA算法

本文采用多元優(yōu)化MOA算法[7]對(duì)權(quán)值進(jìn)行求解，該算法用全局搜索元（GSA）和局部搜索元（LSA）交替合作地進(jìn)行全局和局部的搜索。算法首先生成GSA，以?xún)?yōu)勝劣汰決定其進(jìn)入或者退出隊(duì)列，實(shí)現(xiàn)全局搜索；然后根據(jù)隊(duì)列中的GSA的排列位置和它對(duì)應(yīng)搜索空間中的位置，生成不同規(guī)模的LSA組實(shí)現(xiàn)對(duì)不同的局部進(jìn)行不同粒度的局部搜索，以?xún)?yōu)勝劣汰決定LSA進(jìn)入或者退出GSA所對(duì)應(yīng)的棧。其結(jié)構(gòu)體（如圖1）是由1個(gè)位于頂部的隊(duì)列和n個(gè)掛接在隊(duì)列節(jié)點(diǎn)上的棧所組成。隊(duì)列中的每個(gè)節(jié)點(diǎn)下都掛載著一個(gè)棧。在隊(duì)列節(jié)點(diǎn)中，pPrior指向前一個(gè)隊(duì)列節(jié)點(diǎn)，pNext指向后一個(gè)隊(duì)列節(jié)點(diǎn)，pStack指向其下掛接的棧，pAtom指向一個(gè)全局搜索結(jié)構(gòu)元。同時(shí)每個(gè)隊(duì)列中包含一個(gè)Head和Last指針和一個(gè)最大長(zhǎng)度屬性。在棧節(jié)點(diǎn)中，pUpper指向上一個(gè)棧節(jié)點(diǎn)，pUnder指向下一個(gè)棧節(jié)點(diǎn)，pAtom指向一個(gè)局部搜索結(jié)構(gòu)元。同時(shí)每個(gè)棧包含了pTop棧頂指針、pBottom棧底指針，和一個(gè)最大深度的屬性。

結(jié)構(gòu)體中隊(duì)列的節(jié)點(diǎn)根據(jù)結(jié)構(gòu)元的適應(yīng)度值ffit按從右到左依次遞減，棧中節(jié)點(diǎn)根據(jù)結(jié)構(gòu)元的適應(yīng)度值ffit從上到下依次遞增。隊(duì)列中GSA在隊(duì)列中的位置越靠前，在其鄰域內(nèi)生成的LSA個(gè)數(shù)就越多，這樣就能大大增加找到更優(yōu)解的概率，在本文中定義適應(yīng)值函數(shù)f（x）為加權(quán)后的一段信源序列的碼長(zhǎng)Lm。算法具體流程如下：

Step1.初始化結(jié)構(gòu)體：按照結(jié)構(gòu)體的設(shè)定產(chǎn)生初始化GSA和LSA，并加入到結(jié)構(gòu)體。

Step2.產(chǎn)生GSA（全局搜索結(jié)構(gòu)元），更新隊(duì)列。

Step3.產(chǎn)生LSA（局部搜索結(jié)構(gòu)元），更新堆棧。

Step4.判斷群體性能是否滿足某一指標(biāo)，或者已完成預(yù)定迭代次數(shù)，不滿足則回到步驟Step2。

本文設(shè)置結(jié)構(gòu)體中隊(duì)列的長(zhǎng)度和各個(gè)棧的深度都為1000，搜索半徑為0～1之間，終止條件為迭代次數(shù)一千次。算法運(yùn)行結(jié)束后左上方的結(jié)構(gòu)體中即存放了最優(yōu)自適應(yīng)值及其權(quán)值。

3 實(shí)驗(yàn)方法及分析

本文選取原始灰度圖像進(jìn)行實(shí)驗(yàn)，為了更準(zhǔn)確構(gòu)建條件概率分布，先將圖像進(jìn)行了8級(jí)量化。若當(dāng)前像素稱(chēng)為x（i，j），當(dāng)前像素空間位置的上方的像素點(diǎn)稱(chēng)為x（i，j-1），左方的像素點(diǎn)稱(chēng)為x（i-1，j），用這兩個(gè)已知像素點(diǎn)建立兩組context模型。為了進(jìn)一步簡(jiǎn)化計(jì)算，將這兩個(gè)像素點(diǎn)量化成0或者1.即x（i，j-1） [0，3]，則x（i，j-1）=0，若x（i，j-1） [3，7]，則x（i，j-1）=1，同理量化像素點(diǎn)x（i，j-1）。即Contextci（g）表示有兩組Context（g=1，2），每組Context有兩種組合情況（i=0，1）。

本文用貝葉斯平均求得的權(quán)值和一段信源序列的最短碼長(zhǎng)對(duì)應(yīng)的權(quán)值，分別對(duì)兩組Context模型進(jìn)行加權(quán)合并，再用算術(shù)編碼對(duì)圖像進(jìn)行編碼，最后得到每個(gè)像素點(diǎn)編碼后碼長(zhǎng)的比特?cái)?shù)。如表1所示：每幅圖第一列表示用貝葉斯平均求權(quán)值得到的結(jié)果，第二列表示由一段信源序列的最短碼長(zhǎng)求權(quán)值得到的結(jié)果。

由此表得知用一段信源序列最短碼長(zhǎng)求權(quán)值進(jìn)行Context編碼時(shí)，每個(gè)符號(hào)所需的比特?cái)?shù)比用貝葉斯平均計(jì)算碼長(zhǎng)求權(quán)值時(shí)編碼的比特?cái)?shù)要少，編碼效果較好。權(quán)值更新頻率越快，每個(gè)像素點(diǎn)的碼長(zhǎng)也越短，但是更新過(guò)于頻繁難免會(huì)消耗太多時(shí)間和計(jì)算量，造成浪費(fèi)。

上述采用當(dāng)前像素點(diǎn)的前50個(gè)像素的最短碼長(zhǎng)來(lái)計(jì)算權(quán)值，接下來(lái)研究信源序列長(zhǎng)度對(duì)實(shí)驗(yàn)結(jié)果的影響，表2表示分別用不同長(zhǎng)度的信源序列的最短碼長(zhǎng)所對(duì)應(yīng)的那組權(quán)值進(jìn)行加權(quán)編碼的結(jié)果：

4 結(jié)束語(yǔ)

由上訴實(shí)驗(yàn)結(jié)果對(duì)比分析之后可以得出：用當(dāng)前信源符號(hào)的前一段信源系列的最短碼長(zhǎng)所對(duì)應(yīng)的那組權(quán)值進(jìn)行Context加權(quán)編碼，其編碼長(zhǎng)度比用貝葉斯平均計(jì)算權(quán)值進(jìn)行加權(quán)的編碼長(zhǎng)度短。權(quán)值的更新理論上越快越好，但是更新過(guò)快，計(jì)算過(guò)于頻繁會(huì)難免造成浪費(fèi)，更新過(guò)慢可能會(huì)跳過(guò)最優(yōu)值。在已知信源序列的長(zhǎng)度方面，采用長(zhǎng)度為10的信源序列的最短碼長(zhǎng)求權(quán)值，最終得到的馬長(zhǎng)短且計(jì)算復(fù)雜度小。

參考文獻(xiàn)：

[1]Rissanen J.A universal data compression system[J].IEEE Transactions on information theory，1983（05）：656-664.

[2]Rissanen J.Universal coding，information，prediction，and estimation[J].Information Theory，IEEE Transactions on，1984（04）：629-636.

[3]Willems F M J，Shtarkov Y M，Tjalkens T J.The context-tree weighting method：Basic properties[J].Information Theory，IEEE Transactions on，1995（03）：653-664.

[4]Mahoney M V. Adaptive weighing of context models for lossless data compression[J]，2005.

[5]Cao M D，Dix T I，Allison L，et al.A simple statistical algorithm for biological sequence compression[C]//Data Compression Conference，2007.DCC'07.IEEE，2007：43-52.

[6]Pinho A J，Pratas D，F(xiàn)erreira P J S G.Bacteria DNA sequence compression using a mixture of finite-context models[C]//Statistical Signal Processing Workshop （SSP），2011 IEEE.IEEE，2011：125-128.

[7]Changxing Gou；Shi，Xin Ling；Li，Tian SongICMEME，A novel Multivariant Optimization Algorithm for Multimodal Optimization，ICMEME，2013：458-464.

作者簡(jiǎn)介：羅迪（1989-），女，云南昆明人，通信與信息系統(tǒng)專(zhuān)業(yè)研究生，主要研究方向：圖像建模壓縮。

基金項(xiàng)目：云南大學(xué)研究生科研創(chuàng)新基金重點(diǎn)項(xiàng)目（項(xiàng)目編號(hào)：ynuy201383）。

作者單位：云南大學(xué)，昆明 650000