羅 驍，李衛(wèi)忠

（空軍工程大學(xué) 防空反導(dǎo)學(xué)院，陜西 西安710051）

0 引 言

多描述編碼 （multiple description coding，MDC）是一種能夠在兼顧數(shù)據(jù)實(shí)時(shí)性的同時(shí)解決數(shù)據(jù)失真問(wèn)題的聯(lián)合信源信道編碼［1］。近年來(lái)不斷有新的MDC算法被提出，但其中很多研究主要考慮的是兩信道的情況［2－5］，Huihui Bai等［6］提出針對(duì)小波變換后的圖像不同子帶，按不同的掃描方向生成多個(gè)描述，再采取格型矢量量化的方式對(duì)各個(gè)描述中的系數(shù)進(jìn)行量化，由于矢量量化過(guò)程中計(jì)算復(fù)雜度高，使其應(yīng)用空間受到限制。Khelil等［9］提出了另一種基于小波的 多 描 述 變 換 編 碼 （multiple description transform coding，MDTC）方法，首先把源圖像分為4個(gè)描述 （一級(jí)小波變換后4個(gè)子帶系數(shù)組成的矢量），這4個(gè)描述使用相同的步長(zhǎng)進(jìn)行均勻量化，然后使用相關(guān)變換的方法形成多個(gè)描述，該方法能夠在不占用過(guò)多計(jì)算資源的條件下得到較好的重構(gòu)圖像，是當(dāng)前較為簡(jiǎn)單實(shí)用的MDTC 方法之一。但是，在系數(shù)量化時(shí)，由于每個(gè)子帶的能量和重要程度不一樣，使用同樣的步長(zhǎng)進(jìn)行均勻量化是不合適的。為此，本文在文獻(xiàn) ［9］的基礎(chǔ)上提出對(duì)子帶量化的改進(jìn)技術(shù)，該方法根據(jù)子帶各自的能量進(jìn)行量化，步長(zhǎng)優(yōu)化方法采取遺傳算法。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的方法在重構(gòu)圖像的客觀PSNR 表現(xiàn)和主觀視覺(jué)感受上均有改善。

1 多描述變換編碼

傳統(tǒng)的單描述編碼 （如DCT）方案引入變換往往是為了去除信源的相關(guān)性來(lái)提高編碼效率，而多描述變換編碼（MDTC）系統(tǒng)則是通過(guò)變換在描述中引入可控的冗余信息，使在丟包情況下，可以利用描述間的相關(guān)性從接收到的描述中把丟失的描述估計(jì)出來(lái)。圖1是兩個(gè)描述情形下的編碼過(guò)程，信源數(shù)據(jù)經(jīng)編碼后形成描述1和描述2，通過(guò)不同的信道傳輸?shù)浇獯a端，當(dāng)解碼端只接收到描述1或描述2時(shí)，通過(guò)重建可以恢復(fù)出質(zhì)量較低但可以接受的x∧1或x∧2，當(dāng)兩個(gè)描述都能正常接收時(shí)，可以得到高質(zhì)量的重構(gòu)x∧0。

圖1 兩個(gè)描述的變換編碼框架

通常，一個(gè)信源矢量x 的多描述變換編碼包括以下步驟：

（1）使用變換 （如DCT、DWT……）去除信源相關(guān)性。

（2）將信源矢量x 標(biāo)量量化為xq：xq＝［x］Q。其中，［.］Q表示量化取整。

（3）再對(duì)xq進(jìn)行離散變換引入冗余得到矢量y：y ＝T∧（xq）＝［T1［T2…［Tkxq］Q］Q］Q。其中，T∧是連續(xù)變換T 的離散變換，T 為k 個(gè)主對(duì)角線為1的上三角或下三角矩陣的乘積。

（4）將矢量y 的系數(shù)劃分為M 個(gè)集合 （描述），最后進(jìn)行熵編碼。

當(dāng)接收到所有內(nèi)容后，重構(gòu)過(guò)程是編碼的逆過(guò)程。假如部分系數(shù)丟失，這部分系數(shù)可以通過(guò)相關(guān)變換引入的統(tǒng)計(jì)相關(guān)從已接受到的系數(shù)中估計(jì)出來(lái)，估計(jì)值通過(guò)相關(guān)變換和量化的逆過(guò)程生成，參考文獻(xiàn) ［9］給出了詳細(xì)的編碼和重構(gòu)過(guò)程。

2 子帶均勻量化的多描述變換編碼

離散小波變換 （DWT）是最好的圖像編碼技術(shù)之一。本文采用在圖像壓縮領(lǐng)域廣泛使用的Daubechies 雙正交小波。一級(jí)小波分解將圖像分為4個(gè)子帶 （一個(gè)光滑的LL子帶和3個(gè)細(xì)節(jié)子帶：垂直HL 子帶，水平LH 子帶，對(duì)角HH 子帶）。其中，LL 子帶集中了大部分能量，其余3 個(gè)細(xì)節(jié)子帶只得到少量的能量 （其中HH 子帶最少）。因此，這就啟發(fā)我們?cè)诰鶆蛄炕桨钢懈鶕?jù)子帶能量大小來(lái)設(shè)計(jì)量化步長(zhǎng)，讓最重要的信息 （LL子帶）可以進(jìn)行高質(zhì)量的量化，而對(duì)代表高頻部分的系數(shù) （HL、LH、HH）進(jìn)行粗糙的量化。

文獻(xiàn) ［9］提出MDTC.DWT／UQ 編碼過(guò)程如下：

（1）對(duì)源圖像使用1級(jí)正交B9／7小波變換生成4個(gè)子帶：LL1，HL1，LH1，HH1。

（2）形成4個(gè)矢量 （描述）。

（3）DWT 系 數(shù) （4 個(gè) 矢 量）通 過(guò) 一 量 化 步 長(zhǎng)Δ 均 勻量化。

（4）相關(guān)變換應(yīng)用于4個(gè)矢量。

（5）與JPEG 類(lèi)似的熵編碼應(yīng)用于4個(gè)矢量［9］。

在第 （2）步，本文提出不同子帶的系數(shù)用不同尺寸步長(zhǎng)的均勻量化器進(jìn)行子帶均勻量化，而不是用一種不變的量化步長(zhǎng)進(jìn)行均勻量化。圖2描述了這種基于DWT 的圖像編碼過(guò)程。每個(gè)子帶或每個(gè)描述desi歸屬于一個(gè)量化步長(zhǎng)Δi。對(duì)一給定比特率，量化步長(zhǎng) ｛Δ1，Δ2，Δ3，Δ4｝的設(shè)置與各自的描述｛des1，des2，des3，des4｝相對(duì)應(yīng)，使在丟包情況下圖像的重構(gòu)失真最小化。為了達(dá)到根據(jù)各子帶所包含的能量進(jìn)行均勻量化的目的。4 個(gè)量化步長(zhǎng)的尺寸需要滿(mǎn)足關(guān)系Δ1＜Δ2≤Δ3＜Δ4或者Δ1＜Δ3≤Δ2＜Δ4。我們通過(guò)遺傳算法來(lái)解決這個(gè)最優(yōu)化問(wèn)題。

圖2 基于小波變換的多描述編碼

3 優(yōu)化算法

遺傳算法 （GA）是一種通過(guò)效仿生物進(jìn)化過(guò)程來(lái)搜索最優(yōu)解的隨機(jī)化搜索方法，具有魯棒性強(qiáng)、隨機(jī)搜索、控制簡(jiǎn)單等特點(diǎn)，適合于解決復(fù)雜和非線性系統(tǒng)優(yōu)化的問(wèn)題，目前已經(jīng)在生產(chǎn)調(diào)度、人工生命、圖像處理等領(lǐng)域獲得了廣泛的運(yùn)用。圖像子帶量化步長(zhǎng)的優(yōu)化為一個(gè)非線性過(guò)程，因此這里采用遺傳算法對(duì)量化步長(zhǎng)進(jìn)行優(yōu)化。當(dāng)給定目標(biāo)比特率Rt時(shí)，使用遺傳算法優(yōu)化4個(gè)量化步長(zhǎng)過(guò)程如下：

3.1 參數(shù)編碼方式設(shè)計(jì)和初始種群生成

遺傳算法首先要通過(guò)編碼將問(wèn)題的狀態(tài)空間轉(zhuǎn)換為算法的碼空間，然后才能隨機(jī)產(chǎn)生一定數(shù)量染色體 （問(wèn)題的解）組成的初始種群。針對(duì)步長(zhǎng)優(yōu)化問(wèn)題，最初隨機(jī)產(chǎn)生一個(gè)由20條染色體 （問(wèn)題的解）組成的種群，染色體是與4個(gè)量化步長(zhǎng)所構(gòu)成矢量Δ＝｛Δi，i＝1，2，3，4｝相對(duì)應(yīng)的編碼串。編碼方式采用能夠協(xié)調(diào)搜索和效率之間關(guān)系的二進(jìn)制編碼方法。在本文中，步長(zhǎng)范圍設(shè)定為5≤Δi≤35，每個(gè)量化步長(zhǎng)Δi由5位二進(jìn)制進(jìn)行編碼，編碼串的長(zhǎng)度為20位，如圖3所示。

圖3 量化步長(zhǎng)Δi 的編碼方式

因?yàn)?位二進(jìn)制可產(chǎn)生32種不同的編碼，步長(zhǎng)的編碼區(qū)間是 ［5，35］，所以各步長(zhǎng)編碼對(duì)應(yīng)的解碼公式為

3.2 適應(yīng)度函數(shù)

種群中個(gè)體 （染色體）的生存能力取決于其適應(yīng)度。適應(yīng)度函數(shù)f（Δ）分配給種群中每個(gè)個(gè)體Δ 一個(gè)數(shù)值，用于衡量解決方案的質(zhì)量?jī)?yōu)劣。適應(yīng)度高的個(gè)體即認(rèn)為其質(zhì)量高，遺傳到下一代的機(jī)會(huì)就大，在本文中，使用實(shí)際碼率與碼率誤差平方的比值作為適應(yīng)度函數(shù)

約束條件

其中Ra（Δ）是實(shí)際碼率，Rt是目標(biāo)碼率。

3.3 生成下一代

遺傳算法通過(guò)選擇、交叉、變異3 種方式控制種群的進(jìn)化過(guò)程。首先用某種方法選擇出當(dāng)前種群中一些適應(yīng)度值高的個(gè)體，然后以一定的概率對(duì)這些個(gè)體以進(jìn)行交叉，變異操作。最后在保持種群個(gè)體數(shù)目不變的情況下，用它們替代原種群中適應(yīng)度值最差的個(gè)體形成新種群。

（1）選擇。即按照適應(yīng)度選擇當(dāng)前種群中生命力強(qiáng)的個(gè)體，經(jīng)常使用的選擇策略包括比例選擇、保存最優(yōu)個(gè)體選擇、期望值選擇、排序選擇、確定式采樣選擇等。在本文中我們采用比例選擇策略，根據(jù)個(gè)體適應(yīng)度與總適應(yīng)度的比值進(jìn)行選擇，比值大的個(gè)體擁有更大的概率被選擇。

（2）交叉。即將種群中的個(gè)體進(jìn)行隨機(jī)配對(duì)，然后以一交叉概率交換它們中的部分基因。

交叉體現(xiàn)了信息交換的思想，控制著遺傳算法的全局搜索能力。通常交叉概率的取值范圍為0.40～0.99，本文中設(shè)定初始交叉概率Pc（1）為0.8，從第二代種群開(kāi)始采用自適應(yīng)的交叉概率

式中：N——遺傳代數(shù)，Pc（N）——第N 代的交叉概率，Nmax——最大遺傳代數(shù)，本文中Nmax＝500。代入式（4）可得

（3）變異。即為了提高種群的多樣性，以一定的概率對(duì)種群中個(gè)體串的某些基因座上的基因值作改變。通常變異概率的范圍為0.001～0.100，本文中設(shè)定初始變異概率Pm（1）為0.05，從第二代種群開(kāi)始采用自適應(yīng)的交叉概率

式中：Pm（N）——第N 代的變異概率。將數(shù)據(jù)代入式（6）得

不斷重復(fù)上述步驟直到滿(mǎn)足終止條件。生存下來(lái)的染色體具有良好的適應(yīng)度，作為優(yōu)化問(wèn)題的最優(yōu)解輸出，圖4是GA 優(yōu)化過(guò)程的流程。

圖4 遺傳算法流程

4 仿真結(jié)果和分析

4.1 實(shí)例驗(yàn)證

為了驗(yàn)證所提出量化方法的效果，將本文方法和文獻(xiàn)［9］中的方法MDTC.DWT／UQ 應(yīng)用在真實(shí)圖像上，測(cè)試圖像使用512×512 ‘bridge’，512×512 ‘lena’，512×512‘barbara’，用0.1bit／sample的 冗 余［9］分 配 給4 個(gè) 描 述。兩種方法的比較如圖5、圖6和表1所示。

圖5是兩種技術(shù)在不同丟包情況下 （丟失一數(shù)據(jù)包、丟失二數(shù)據(jù)包、丟失三數(shù)據(jù)包）的PSNR 值和碼率的關(guān)系曲線。從這些曲線中不難發(fā)現(xiàn)，在一個(gè)數(shù)據(jù)包丟失情況下，兩種方法的結(jié)果相差不多。然而，當(dāng)2或3個(gè)數(shù)據(jù)包丟失時(shí)，隨比特率增加本文方法比MDTC.DWT／UQ 在PSNR 上的表現(xiàn)更好。表1是目標(biāo)碼率為2.0bits／sample時(shí)，各測(cè)試圖像在不同丟包情況下重構(gòu)后的PSNR 值，從中可以看出，在2或3 包丟失情況下，利用本文方法比MDTC.DWT／UQ 在PSNR 值 上 提 升2－4dB。圖6 比 較 了 目 標(biāo) 碼 率 為2.0bits／sample， ‘bridge’圖像在0，1，2，3包丟失情況下兩種方法的重構(gòu)。其中a、b、c、d使用MDTC.DWT／UQ方法，e、f、g、h使用本文方法，重構(gòu)后的PSNR 值分別為（a）39.67dB、（b）39.52dB、（c）32.40dB、（d）27.91dB、（e）39.35dB、（f）39.14dB、（g）34.62dB、（h）29.95dB。容易注意到，使用新方法重建后的圖像視覺(jué)效果明顯改善。

圖5 bridge的峰值信噪比和碼率的關(guān)系曲線

圖6 bridge在0，1，2，3包丟失情況下兩種方法的重構(gòu)

表1 不同丟包數(shù)量下兩種方法的對(duì)比

4.2 算法分析

（1）假設(shè)檢驗(yàn)：考慮到本文使用的遺傳算法具有一定的隨機(jī)性，而且圖像重建質(zhì)量往往與具體的丟失信息相關(guān)，需要更具統(tǒng)計(jì)意義的數(shù)據(jù)證明本文方法的有效性。因此，本文對(duì)‘bridge’圖像進(jìn)行了更多的測(cè)試，然后利用測(cè)試結(jié)果和參數(shù)假設(shè)檢驗(yàn)的方法 （U 檢驗(yàn)）對(duì)網(wǎng)絡(luò)環(huán)境較差情況下 （2包丟失或3包丟失）兩種方法的優(yōu)劣做出進(jìn)一步分析。

將本文方法和文獻(xiàn) ［9］中的方法MDTC.DWT／UQ 在網(wǎng)絡(luò)環(huán)境較差情況下的PSNR 值分別看作母體X1和X2，給定目標(biāo)碼率為2.0bits／sample，用兩種方法對(duì) ‘bridge’圖像進(jìn)行50次測(cè)試，得到兩組容量為100的子樣PSNR 數(shù)據(jù)，經(jīng)計(jì)算：n1＝n2＝100，珡X1＝30.12，S1＝2.6，珡X2＝32.51，S2＝5.2。其中n1，珡X1，S1和n2，珡X2，S2分別為兩組數(shù)據(jù)的子樣容量、平均數(shù)、標(biāo)準(zhǔn)差。給定小概率a ＝5% ，查表得＝1.96，使

括號(hào)內(nèi)的事件為小概率事件，平均進(jìn)行20次抽樣只發(fā)生一次。假設(shè)H0：μ1 ≥μ2，H1：μ1 ＜μ2 ，拒絕區(qū)域?yàn)?/p>

計(jì)算得

易見(jiàn)珡X1－珡X2≤－1.14，故拒絕H0，即認(rèn)為在網(wǎng)絡(luò)環(huán)境較差情況下使用本文方法后圖像的PSNR 值有顯著提高。

（2）復(fù)雜性分析：在運(yùn)行速度上，本文方法比文獻(xiàn)［9］提出的MDTC.DWT／UQ 方法慢，原因在于子帶量化過(guò)程中使用遺傳算法，計(jì)算適應(yīng)度值時(shí)需要大量時(shí)間，我們?cè)u(píng)估候選方案時(shí)使用的適應(yīng)度函數(shù)f（Δ）對(duì)于L×L 圖像至多需要L2＋2L 次乘法和2L 次加法。實(shí)驗(yàn)結(jié)果表明GA找到最優(yōu)解需要大概400 次估值。因此，至少需要400×（L2＋2L）次乘法和400×（2L）加法，對(duì)于512×512圖像，優(yōu)化量化步長(zhǎng)需要總計(jì)約1.1億次計(jì)算，這樣的計(jì)算量對(duì)于專(zhuān)用的數(shù)字信號(hào)處理器 （DSP）是完全可以接受的。

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

本文提出一種集成遺傳算法和小波變換的多描述編碼方法，該方法考慮到應(yīng)用小波變換后圖像低頻信息 （第一個(gè)描述）的重要性，使用遺傳算法優(yōu)化的量化步長(zhǎng)對(duì)4個(gè)子帶進(jìn)行不同程度的量化，很好地保護(hù)了在引入相關(guān)后各個(gè)描述中的低頻系數(shù)。與文獻(xiàn) ［9］相比本文方法既保證了多個(gè)描述同時(shí)到達(dá)時(shí)的編碼性能，又提高了任意描述到達(dá)時(shí)圖像的主客觀重建質(zhì)量，更適于在誤碼多發(fā)網(wǎng)絡(luò)環(huán)境下的圖像傳輸。不足之處在于本文提出的量化策略沒(méi)有對(duì)感興趣區(qū)中復(fù)雜的紋理特征 （高頻系數(shù)）進(jìn)行保護(hù)，下一步研究工作將圍繞感興趣區(qū)編碼ROI和本文方法的結(jié)合，進(jìn)一步提高圖像的視覺(jué)質(zhì)量。

［1］ZHANG Yang，ZHANG Nan，YIN Baocai.Overview of researches on multiple description coding ［J］.Chinese Journal of Computers，2007，30 （9）：1613－1624 （in Chinese）. ［張洋，張楠，尹寶才.多描述編碼研究現(xiàn)狀 ［J］.計(jì)算機(jī)學(xué)報(bào)，2007，30 （9）：1613－1624.］

［2］Nan Z，Yan L，F(xiàn)eng W，et al.Efficient multiple description image coding using directional lifting－based transform ［J］.IEEE Transactions on Circuits and Systems for Video Technology，2008，18 （5）：646－656.

［3］ZHENG Yi，SHI Ping.Wavelet－based multiple description video coding ［J］.Video Engineering，2012，36 （23）：43－46（in Chinese）.［鄭義，史萍.一種基于小波變換的多描述視頻編碼方法 ［J］.電視技術(shù)，2012，36 （23）：43－46.］

［4］LI Yan，WANG Shengqian，DENG Chengzhi，et al.Multiple description coding scheme based on redundant Ridgelet transform ［J］.Computer Engineering and Applications，2011，47（24）：146－149 （in Chinese）. ［李彥，汪勝前，鄧承志，等.一種基于冗余Ridgelet變換的圖像多描述編碼方法 ［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47 （24）：146－149.］

［5］JIANG Yuzhen，ZHU Yinghui，OUYANG Chunjuan.Multiple description video coding research based on complementary segmentation in compressed domain ［J］.Computer Engineering and Design，2009，30 （14）：3362－3364 （in Chinese）.［江玉珍，朱映輝，歐陽(yáng)春娟.基于壓縮域互補(bǔ)分割的視頻多描述編碼研究 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2009，30 （14）：3362－3364.］

［6］Huihui B，Ce Z，Yao Z.Optimized multiple description lattice vector quantization for wavelet image coding ［J］.IEEE Transactions on Circuits and Systems for Video Technology，2007，17 （7）：912－917.

［7］Zhang G.Efficient error recovery for multiple description video coding ［C］／／International Conference on Image Processing.Singapore：IEEE，2012：829－832.

［8］Choupany R，Wong S，Tolun M.Scalable video transmission over unreliable networks using multiple description wavelet coding ［C］／／Proceedings of IDCTA，2011.

［9］Khelil K，Bekka RE，Djebari A，et al.Multiple description wavelet－based image coding using correlating transforms ［J］.AEU－International Journal of Electronics and Communications，2007，61 （6）：411－417.

［10］Lin Chunyu，Zhao Yao，Zhu Ce.Two－stage multiple description image coding using TCQ ［J］.International Journal of Wavelets，Multiresolution and Information Processing，2009，7 （5）：665－673.

［11］LI Yun，LIU Gang，LAO Songyang.A genetic algorithm for community detection in complex networks ［J］.Journal of Central South University，2013，20 （5）：1269－1276.

［12］LI Cuiping，ZHENG Yaoxia，ZHANG Jia，et al.Ore grade interpolation model based on support vector machines optimized by genetic algorithms［J］.Journal of University of Science and Technology Beijing，2013 （7）：838－843（in Chinese）.［李翠平，鄭瑤瑕，張佳，等.基于遺傳算法優(yōu)化的支持向量機(jī)品位插值模型［J］.北京科技大學(xué)學(xué)報(bào)，2013 （7）：838－843.］

［13］Zhang Wen，Ghogho M.Hypothesis testing analysis and unknown parameter estimation of GPS signal detection ［J］.Journal of Central South University，2012，19 （5）：1290－1301.