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

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

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

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

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

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

1EZW算法的基本步驟

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

(3）主掃描。

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

①POS為正有效系數(shù)；

②NEG為負有效系數(shù)；

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

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

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

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

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

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

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

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

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

（4）輔掃描。

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

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

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

2.1算法的基本思想

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

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

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

2.2算法描述

2.3算法分析

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

3結(jié)束語

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

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

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