一個新的嵌入式零樹小波圖像編碼的多位平面并行算法

摘要：發現了一個EZW（EmbeddedZerotreeWavelet)編碼的多位平面并行算法，其每個位平面的編碼僅需對位平面進行一遍掃描，大大提高了EZW的編碼速度。

關鍵詞：嵌入式小波零樹編碼;多位平面并行編碼;圖像編碼;編碼速度

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

文章編號：1001—3695(2007)03—0283—03

嵌入式小波零樹編碼（EmbeddedZerotreeWavelet，EZW）是一種典型的小波圖像編碼算法。它是一種非常有效和實用的圖像壓縮技術，曾為其他小波圖像編碼算法的產生奠定過基礎[2—5，8—11]。但它也存在著一些問題，其中一個主要問題是編碼按照閾值遞減的次序分多個層次串行進行，且在每次編碼過程中，主掃描又需要對小波分解矩陣進行多遍掃描，大大降低了編碼的速度，而且編碼難以用并行算法優化[3—6，8—10]，因此很難滿足圖像實時處理的需要。為了解決這個問題，有人提出了一些頗有意義的并行處理方案。例如，Vanhoof[1]，Hsiao等人[6]提出了多棵樹并行處理的方案。這種方案雖然理論上簡單，但因數據帶寬有限，多棵樹的并行讀寫難以實現；于是又有人提出了多個位平面并行的零樹編碼方案[10]，但每個位平面的編碼仍需對小波矩陣進行正、反方向的兩次掃描，未能充分提高零樹編碼的速度。筆者經研究發現，可以設計出一個多位平面并行編碼的算法，大大提速EZW的編碼，更好地滿足圖像實時處理的需要。

1EZW算法的基本步驟

EZW算法包含下列基本處理步驟[7—11]：

(3）主掃描。

EZW的編碼共需e+1次主掃描。第i次主掃描將小波系數與閾值T_i-1進行比較，絕對值不小于閾值的系數稱為有效系數，否則稱為無效系數。主掃描輸出如下幾種符號類型：

①POS為正有效系數；

②NEG為負有效系數；

③ZTR為一個零樹的根，但其父系數不是零樹的根；

④IZ為本身是無效系數，但至少有一個有效的后代系數；

⑤ZERO為零樹上的一個系數，但不是零樹的根。

在掃描過程中，用一個主表(或稱有效值映射表)來記錄這些符號和有效系數值。每次主掃描結束后，將有效系數置為0，以免下次主掃描又對它們編碼。

主掃描一般由以下三個階段組成：

①第一遍掃描系數矩陣，按“之”字順序逐個檢查小波系數，以區分有效系數與無效系數，并為無效系數標記有效子孫的存在性；

②第二遍掃描系數矩陣，利用第一遍掃描所積累的信息，對無效系數進一步區分ZTR和IZ；

③第三遍掃描系數矩陣，把標志為POS，NEG，ZTR或IZ的系數分別映射為符號P，N，T或Z，并把這些符號存于主表中；同時把標志為POS，NEG的有效系數值也記錄到主表中，而在系數矩陣中用0代替它們。

由于每次主掃描過程需要對小波系數矩陣掃描三遍，整個編碼過程又需要對小波系數矩陣進行e+1次主掃描，因此共需掃描3(e+1)遍，大大降低了編碼的速度。因此，筆者提出了僅需一遍掃描的改進算法，對于提高編碼速度大有幫助。

（4）輔掃描。

對主掃描產生的主表中的有效系數進行量化，并用輔表來記錄量化符號。

（5）輸出編碼信息。將包括閾值、主表和輔表在內的編碼信息傳輸給解碼器。

2EZW編碼的多位平面并行算法

2.1算法的基本思想

為了更好地描述算法，引入兩個概念:①概念父系數，即在除去系數絕對值大于當前位平面閾值兩倍的系數后所形成的零樹結構中，當前系數的父系數;②概念子系數，即在除去系數絕對值大于當前位平面閾值兩倍的系數后所形成的零樹結構中，當前系數的直系子系數。在一個系數與概念父系數或概念子系數之間，可能存在多個系數絕對值大于當前位平面閾值兩倍的系數，但它們被忽略不計。另外，還用1，2，3，4，0分別表示系數類型POS，NEG，ZTR，IZ，ZERO。

仔細分析EZW編碼的層次結構可以發現，編碼是按e+1個層次串行進行的，第l(0≤l≤e)層編碼只需跳過大于等于2^e-l+1的系數，僅對小于2^e-l+1的系數進行編碼。因此可容易地分離位平面之間的關聯，而實現位平面編碼的并行操作。在每個位平面的編碼過程中，僅需參考當前系數的父系數或直系子系數的類型來確定當前系數的類型，從而可把EZW主掃描的前兩遍掃描合二為一；另外，可根據當前系數的行列坐標計算出它在第三遍掃描中輸出到主表的順序位置，從而可在第一遍掃描過程中完成一個系數的類型確定后，直接把它輸出到對應本位平面的主表D中。因此，僅需對小波系數矩陣掃描一遍，即可完成對一個位平面的編碼。

假定使用基于分布式存儲機群系統和消息傳遞體系結構的超級服務器系統來進行圖像編碼。為了實現位平面編碼的并行處理，各處理機需要設置如下一些中間數據結構：①用于暫存圖像小波系數矩陣的二維數組W；②存放本次位平面編碼中零樹結構上的系數類型及其有效兒孫標記的三維數組

2.2算法描述

2.3算法分析

上面的并行算法把每個位平面分配給一個處理機處理，由于巧妙地分離了位平面之間的關聯，使這些位平面可被完全并行地編碼，因此編碼速度提高了e+1倍。另外，并行算法中每個位平面的編碼僅需掃描一遍即可完成，而串行算法中每個位平面的編碼需要掃描三遍，這樣每個位平面的編碼速度又提高了三倍。因此本并行算法使編碼速度提高了大約3(e+1)倍，比其他已有的位平面編碼并行算法的速度還要快。

3結束語

雖然EZW算法是一種有效實用的圖像編碼算法，但它也存在著自身的缺陷。其中的一個問題就是EZW的編碼需要對小波系數矩陣進行多次多遍掃描，使EZW的編碼速度大大降低，而且難以用并行算法優化，因此很難滿足圖像實時處理的需要。為此，許多人研究和改進了零樹編碼算法，并提出了一些有意義的并行方案，如多棵樹并行處理的方案和多個位平面并行編碼的方案，但這些改進方法仍然存在著難以實現或未使編碼速度充分提高等問題。

近來筆者找到了一個EZW編碼的多位平面并行算法，在每個位平面的編碼過程中僅需對位平面進行一遍掃描，使得EZW的編碼速度大大提高，能更好地滿足圖像實時處理的需要。

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