ＪＰＥＧ２０００的系數位上下文建模算法及其應用研究

摘要：提出了系數位上下文建模算法，利用它可先建立每個位平面的上下文，再直接進行編碼，大大提高了編碼的并行性。利用它還可以容易地實現一次性掃描的快速編碼系統和位平面并行編碼系統。

關鍵詞：JPEG2000；優化截斷嵌入式塊編碼；上下文；一次性掃描編碼；并行位平面編碼

中圖分類號：TP391文獻標志碼：A

文章編號：1001-3695(2007)12-0370-04

0引言

作為新一代靜止圖像壓縮標準，JPEG2000具有諸多的優點：它能夠在相同的壓縮質量下獲得較高的壓縮比；可進行有損和無損壓縮；支持感興趣區域的編碼和圖像漸進傳輸；允許對碼流進行隨機訪問和處理；具有錯誤恢復功能；具有開放的框架結構等。JPEG2000優于JPEG的主要原因在于，它采用了離散小波變換（DWT）和基于優化截斷的嵌入式碼塊編碼算法（EBCOT）^[1，2]。

由于JPEG2000算法的復雜性，其效率和用途受到了限制。特別地，EBCOT是JPEG2000的核心算法。其運算時間占據了整個運算時間的較大部分。它對每個位平面的編碼需要三次掃描，明顯浪費了運算時間，而且各位平面的編碼很難并行實現，不能充分提高編碼速度。因此對EBCOT進行改進具有重要的意義。雖然有人提出了對位平面進行一次性掃描編碼的思想^[3]，但它的算法并非真正的一次性掃描算法。由于第二遍掃描（magnitude refinement）和第三遍掃描（cleanup）的系數位上下文需待第一遍掃描（significance propagation）完成后才能確定，使用了不止一次的掃描，未充分提高編碼速度。另外，雖然也有人研究過EBCOT的多位平面并行編碼算法^[4]，但由于各位平面的系數位上下文未事先確定，各位平面的編碼仍需三遍掃描，未充分開發位平面編碼的并行性。

1EBCOT編碼算法簡介

1．1JPEG2000的編/解碼過程和EBCOT算法的基本流程

JPEG2000的編/解碼過程如圖1所示。原始圖像數據經預處理后進行離散小波變換；接著對DWT進行量化，再運用EBCOT算法進行算術熵編碼；最后將碼流分層打包輸出。解碼則是編碼的逆過程，即先對碼流進行熵解碼；然后進行逆量化和小波逆變換；最后生成重建圖像數據。

EBCOT算法的基本流程可分為第一層塊編碼（tier1）和第二層分層裝配(tier2)。塊編碼是指先將小波變換后得到的每一個子帶分成16×16~64×64大小的塊；然后對每個編碼塊進行基于上下文的算術編碼，得到嵌入式碼流。分層裝配是在塊編碼完成后，遵循率失真最優的原則，選取合適的截斷點截斷每一碼塊的碼流，裝配成具有分辨率可伸縮性或質量可伸縮性的滿足預定編碼長度的最終碼流。

1．2系數位建模

系數位建模就是將小波變換系數劃分成固定大小的代碼塊，再將各個變換系數作位平面展開；然后對各個位平面進行掃描編碼^[5]。

在每個位平面上，按每四行一個條帶的方式，逐個條帶地掃描。在每個條帶中每四個系數作為一列進行掃描，直到掃描完編碼塊中的所有列；再掃描下一個條帶的系數，直到所有系數都掃描完為止。代碼塊內的掃描方式如圖2所示。

對位平面上系數位進行算術編碼需要利用該系數的上下文信息。一個系數X的上下文矢量（圖3）是由系數X鄰域系數的有效性狀態構成的二進制矢量。另外，當相鄰系數位于當前系數所屬的代碼塊外部時，它們被視為無效。

除最高位平面上只有清除掃描(cleanup)以外，其余位平面的編碼均需要經過有效性傳播掃描(significance propagation)、幅度細化掃描（magnitude refinement）和清除掃描。

1） Significance propagation掃描對系數本身不是有效但其八鄰域內存在有效系數的系數進行編碼。當系數位變為有效時，還需對其系數極性位進行編碼。

2） Magnitude refinement掃描對那些已經標記為有效的但在當前位平面中未被編碼的系數進行編碼。這種編碼也要利用上下文信息。

3）Cleanup掃描對不屬于前兩種掃描的系數進行編碼。特別地，在cleanup掃描中，如果被掃描的列內四個相鄰系數均屬于cleanup掃描，而且這四個系數的八鄰域系數全都是無效的，則進行具有獨立上下文的游程長度編碼（run－length coding）。在游程長度編碼中，如果一列內的四個系數均為0，則分配符號值0；如果一列內的四個系數中至少存在一個有效系數，就分配符號值1。此后，對該有效系數的位置（00，01，10，11）作算術編碼，并對系數的極性進行編碼。

1．3EBCOT編碼算法分析

EBCOT(包括tier1和tier2)是JPEG2000編碼系統的核心算法；第一層編碼 （tier1）又是EBCOT的核心部分。EBCOT的編碼實驗表明，EBCOT占了編碼系統的大部分運算時間，而tier1又占了EBCOT的大部分時間。Tier1的三次編碼浪費了大量的運算時間。因此，若能對原算法進行改進以獲得基于一次性掃描的快速編碼算法或多位平面并行編碼算法，則能降低EBCOT的運算時間，提高JPEG2000的編碼速度^[3，4，6]。

2系數位上下文建模算法

在EBCOT原算法中多個位平面的編碼必須串行進行，而且每個位平面的編碼需要三次掃描：首先掃描當前位平面，對所有屬于重要性傳播掃描的系數進行編碼；然后再次掃描位平面， 對所有屬于幅度細化掃描的系數進行編碼；最后掃描位平面，對所有屬于清除掃描的系數進行編碼。重復三次掃描，明顯浪費了大量時間。由于各位平面的系數上下文未事先確定，一次性掃描編碼和多位平面并行編碼難以實現。為此，本文提出了先建立碼塊內所有系數在各個位平面中上下文的算法及相應的編碼算法。下面介紹這些算法的思想和步驟。

不妨設編碼塊的大小為64×64，展開成位平面的個數為NP，建立的上下文存放在數組f[NP][64][64]中。數組中元素為16位二進制數。每位表示的意義以及相關常數的定義如下：

#define JPC_NESIG 0x0001右邊第1位為1表示東北角鄰域系數有效，0表示無效；

#define JPC_SESIG 0x0002右邊第2位為1表示東南角鄰域系數有效，0表示無效；

#define JPC_SWSIG 0x0004右邊第3位為1表示西南角鄰域系數有效，0表示無效；

#define JPC_NWSIG 0x0008右邊第4位為1表示西北角鄰域系數有效，0表示無效；

#define JPC_NSIG 0x0010右邊第5位為1表示正北鄰域系數有效，0表示無效；

#define JPC_ESIG 0x0020右邊第6位為1表示正東鄰域系數有效，0表示無效；

#define JPC_SSIG 0x0040右邊第7位為1表示正南鄰域系數有效，0表示無效；

#define JPC_WSIG 0x0080右邊第8位為1表示正西鄰域系數有效，0表示無效；

#define JPC_OTHSIGMSK 0x00ff右邊8位全1表示8鄰域系數中至少有一個系數有效；

#define JPC_NSGN 0x0100右邊第9位為1表示正北鄰域系數為負，0表示正；

#define JPC_ESGN 0x0200右邊第10位為1表示正東鄰域系數為負，0表示正；

#define JPC_SSGN 0x0400右邊第11位為1表示正南鄰域系數為負，0表示正；

#define JPC_WSGN 0x0800右邊第12位為1表示正西鄰域系數為負，0表示正；

#define JPC_SIG 0x1000左邊第4位為1表示本系數有效，0表示無效；

#define JPC_REFINE 0x2000左邊第3位為1表示本系數已被細化，0表示未被細化；

#define JPC_SigPass 0x4000左邊第2位為1表示本系數屬于有效性傳播掃描。

基于上述假設，可給出如下系數位上下文建模算法。

功能：掃描編碼塊內的所有系數，計算它們在各位平面中的上下文。

輸入：一個小波系數編碼塊D[M][N]（M<66，N<66）。

輸出：存放編碼塊系數在各位平面中上下文的三維數組f [NP][66][66]。

步驟：

4實驗結果

通過改進開放圖像壓縮軟件包Jasper中的第一層編碼方法，本文實現了上述系數位上下文建模算法及相應的編碼算法。改進的編碼系統在編碼每個碼塊時，首先建立其所有系數在各個位平面上的上下文；然后依次對各個位平面進行編碼。本文用典型的測試圖像進行壓縮編碼和解壓重建，測得的實驗數據如表1所示。從表1可見，新算法的編碼速度可以達到甚至超過原算法的編碼速度，而且壓縮圖像的重構質量完全一樣。置（00，01，10，11）作算術編碼，并對系數的極性進行編碼。然后，調用清理掃描步子程序Clnpass_step對該列內剩下的系數進行逐個編碼。

5系數位上下文建模算法的應用

5．1基于一次性掃描的快速JPEG2000編碼系統

采用本文的系數位上下文建模算法，先建立所有系數在各個位平面上的上下文，可實現一次性掃描的快速編碼，充分提高編碼速度。

5．2位平面并行的EBCOT編碼系統

為了進一步提高JPEG2000的編碼速度，有些人曾致力于EBCOT硬件結構或EBCOT并行編碼系統的研究，如Chiang提出了編碼過程并行（coding pass parallel）結構，Lian提出了基于列的結構，以及較新的位平面編碼并行結構^[4]。

但這些編碼結構仍然未充分開發編碼的并行性，如較新的位平面編碼并行結構。其每個位平面的編碼仍需三遍掃描，未充分提高編碼速度。若利用本文的系數位上下文建模算法則能容易地實現所有位平面的并行編碼，而且每個位平面的編碼僅需一次掃描即可完成，可大大提高編碼速度。

6結束語

JPEG2000是新一代靜止圖像壓縮標準，比傳統標準JPEG等具有更多的優點。但由于算法復雜，其效率和應用未能得到充分發揮。而EBCOT是JPEG2000的核心算法，但占用較多的運算時間。于是不少人曾致力于改進EBCOT編碼方法，提出了不少快速編碼方法或技術，如基于一次性掃描的快速編碼系統和位平面并行編碼結構，但他們的方法并未充分開發編碼的并行性。于是本文提出了先建立碼塊所有系數在各個位平面內的上下文的算法及相應的編碼算法，使EBCOT的編碼速度達到或超過了原算法的編碼速度，而且依賴新的系數位上下文建模算法，可容易地實現真正的一次性掃描編碼和多位平面并行編碼，有利于JPEG2000的實際應用。

參考文獻：

[1]胡棟.靜止圖像編碼的基本方法與國際標準[M]. 北京:北京郵電大學出版社，2003.

[2]TAUBMAN D.JPEG2000圖像壓縮基礎、標準和實踐[M].魏江力，柏正堯，等譯.北京:電子工業出版社，2004.

[3]張宏偉，劉正光，陳紅新.基于JPEG2000的一次性掃描、高效編碼算法的研究[J]. 計算機應用，2005，25（5）：1069－1071.

[4]劉凱，吳成柯，李云松，等.比特平面并行的EBCOT編碼及其VLSI結構[J].計算機學報，2004，27(7):928-935.

[5]小野定康，鈴木純司. JPEG2000技術[M].強增福，譯.北京:科學出版社，2004.

[6]ADAMS M D， KOSSENTINI F. Jasper: a software－based JPEG2000 codec implementation//Proc of IEEE International Conference on Image Processing. Vancouver:[s.n.]， 2000:53-56.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”