Embedded Zerotree Wavelets
To explain how the coefficients are set to zero, an encoder specially
designed to use wavelet transforms is used.
Shapiro’s Embedded Zerotree Wavelet (EZW) encoder is based on a
type of coding called progressive encoding (also called embedded encoding) that
compresses an image into a bit stream with increasing accuracy. This means that as more bits are added to
the stream, the decoded image contains more detail; a property similar to JPEG
encoded images. This property can be
thought of in the same way as significant digits of a decimal number, such as
pi, where the more significant digits that are used determine accuracy of the
number.
The EZW encoder violates the observation that larger coefficients are
more important than smaller ones, by encoding the coefficients in decreasing
order, during several passes. For each
pass, a threshold is chosen which all coefficients are measured against. If a wavelet
coefficient
is larger than the threshold it is encoded and removed from the image, if it is
smaller than the threshold it is left for the next pass. When all the wavelet
coefficients have been passed over, the threshold is lowered and the image is
scanned again to add more detail to the already encoded image. This process is
repeated until all the wavelet coefficients have been encoded completely. Now the dependency between the wavelet
coefficients across different scales must be used to effectively encode large
parts of the image that are below the current set threshold.
A wavelet transform works by transforming a signal from time domain
into a joint time-scale domain, meaning the wavelet coefficients are two
dimentional. If the desired signal is
to be compressed, the coefficient values and their position in time must be
encoded. If the signal is an image,
such as the fingerprint images, the position in time is expressed better as a
position in space. After the image is
transformed by wavelets, it can be represented by ‘trees’ because of the many
samplings that are done in the transform.
Each coefficient in a low level can be thought of as having four
descendants in the next higher level. A
type of tree structure is formed because every coefficient has four other
coefficients attached to it, as seen below in Figure 10.
Figure 10. The relation between wavelet coefficients on different levels.
A zerotree is a tree similar
to the one in Figure 10, in which all of the nodes are equal to or smaller than
the one above it. The tree is coded
with a single symbol and recomposed by the decoder as a tree filled with zeros. This zerotree takes advantage of the fact
that all the wavelet coefficients will be zero if in a certain area of the
image, there are no sharp edges.
After these steps, but
before the compressed data is saved, all the floating numbers must be converted
into integers in a method called quantization.
Since the human eye sees according to a logarithmic scale, the error
margin is very small when approximating small coefficients, but large when
approximating large coefficients. Once
the floating numbers have been converted into integers, entropy coding is
done. Entropy coding takes advantage of
the fact that a single number can represent many zeros. To make entropy coding even more effective,
a variable bit rate per scale is used to give more importance to larger
coefficients and less importance to small scale coefficients. This process proves to be a very effective
tool in fingerprint compression because it allows more data to be sent over a
modem or stored electronically. The
entire FBI method can be described by the schematic shown in Figure 11.
Figure 11. FBI process for compressing and decompressing images.