Embedded zerotrees of wavelet transforms: Difference between revisions

Revision as of 05:43, 28 June 2023

Latest revision as of 12:26, 7 August 2025

(13 intermediate revisions by 3 users not shown)

Line 1:

{{Short description|Lossy image compression algorithm}}

'''Embedded Zerotrees'''zerotrees of '''Waveletwavelet transforms''' ('''EZW''') is a lossy [[image compression]] [[algorithm]]. At low bit rates, i.e. high compression ratios, most of the coefficients produced by a [[Sub-band coding|subband transform]] (such as the [[wavelet transform]]) will be zero, or very close to zero. This occurs because "real world" images tend to contain mostly low frequency information (highly correlated). However where high frequency information does occur (such as edges in the image) this is particularly important in terms of human perception of the image quality, and thus must be represented accurately in any high quality coding scheme.

will be zero, or very close to zero. This occurs because "real world" images tend to contain mostly low frequency information (highly correlated). However where high frequency information does occur (such as edges in the image) this is particularly important in terms of human perception of the image quality, and thus must be represented accurately in any high quality coding scheme.

By considering the transformed coefficients as a [[Tree (graph theory)|tree]] (or trees) with the lowest frequency coefficients at the root node and with the children of each tree node being the spatially related coefficients in the next higher frequency subband, there is a high probability that one or more subtrees will consist entirely of coefficients which are zero or nearly zero, such subtrees are called '''zerotrees'''. Due to this, we use the terms node and coefficient interchangeably, and when we refer to the children of a coefficient, we mean the child coefficients of the node in the tree where that coefficient is located. We use '''children''' to refer to directly connected nodes lower in the tree and '''descendants''' to refer to all nodes which are below a particular node in the tree, even if not directly connected.

Line 29 ⟶ 28:

(5) Adaptive multilevel arithmetic coding which is a fast and efficient method for entropy coding strings of symbols.

== Embedded Zerotreezerotree Waveletwavelet Codingcoding ==

=== A. Encoding a coefficient of the significance map ===

In a significance map, the coefficients can be representingrepresented by the following four different symbols. With using these symbols to represent the image information, the coding will be less complicationcomplicated.

==== 1. Zerotree root ====

Line 38 ⟶ 37:

==== 2. Isolated zero ====

If the magnitude of a coefficient that is lesslower than a threshold T, but it still has some significant descendants, then this coefficient is called isolated zero.

==== 3. Positive significant coefficient ====

Line 47 ⟶ 46:

=== B. Defining threshold ===

The threshold usingused above can be defined as the type belowfollows.

==== 1. Initial threshold T₀:, (Assumeassuming C_max is the largest coefficient.): ====

<span>[[File:Threshold-0119.png|126x126px]]</span>

==== 2. Threshold T_i is iteratively reduced to half of the value of the previous threshold.: ====

[[File:Threshold-01192.png|frameless|133x133px]]

==== 1. Initial threshold T₀: (Assume C_max is the largest coefficient.) ====

<span>[[File:Threshold-0119.png|126x126px]]</span>

==== 2. Threshold T_i is reduced to half of the value of the previous threshold. ====

[[File:Threshold-01192.png|frameless|133x133px]]

=== C. Scanning order for coefficients ===

'''[[Raster scanningscan]]''' is theused rectangularin patterna of image capture and reconstruction. Using this scanning on EZW transform is to perform scanning the coefficients inway such way that no childchildren nodenodes isare scanned before itstheir parent nodenodes. Also, all positionscoefficients in a given subband are scanned before itthose movesof to the next subband.

=== D. Two-pass bitplane coding ===

Line 145 ⟶ 146:

[[Category:Image compression]]

[[Category:Lossless compression algorithms]]

[[Category:Trees (data structures)]]

[[Category:WaveletsLossy compression algorithms]]

[[Category:LosslessData compression algorithms]]