The present invention relates to an image data compressor device (d) for compressing digital image data.
The field of the invention is the use of wavelet transforms to compress/decompress digital image data.
Conventional wavelet transform coding codes an image in three steps. A first step decorrelates the image by transforming its pixels into wavelet coefficients distributed in sub-bands at several resolution levels. A second step quantifies the wavelet coefficients obtained in the first step. A third step entropically codes the wavelet coefficients quantified in the second step.
The person skilled in the art knows that this type of coding can be optimized only if three hypotheses are verified: the wavelet transform must be orthogonal, the wavelet coefficients must be coded using a zero order entropic code with no statistical interdependency of the coefficients, and the limits of "high-resolution quantifying", within which the probability densities of the wavelet coefficients vary little within a quantifying box, must be complied with.
If the above hypotheses are not verified, in theory complete bit rate assignment, by selecting a quantifying increment that is a priori different for each sub-band, is required. In practice, the coding remains qualitatively valid if the hypotheses are no longer formally verified. This is the'case in particular if the wavelet transform is not orthogonal but bi-orthogonal or if the wavelet coefficients of the same sub-band are not coded independently because they are not independent.
Similarly, if the high-resolution quantifying hypothesis is not verified, the coder may be slightly modified by replacing its uniform quantifier with a central interval quantifier of twice the size (zero-centered quantifying interval or Dead Zone). This is because the distribution of the wavelet coefficients in each sub-band is a Laplace distribution (or a generalized Gaussian distribution) with a peak at 0 where it can no longer be reasonably considered as quasi-constant, especially at low bit rates (i.e. at high compression rates). A Laplace function is a special case of a generalized Gaussian function.
To attempt to improve coding under the conditions cited above (i.e. in the case of a bi-orthogonal transform or a transform not yielding independent coefficients), it has been proposed. .to,exploit the interdependency of neighbor wavelet coefficients in the same sub-band by employing contextual entropic coding that takes into account a conditional
probability density instead of a simple probability density. This conditional
density models the law governing the appearance of a wavelet coefficient
conditionally on its surroundings.
The term "intraband dependency" used hereinafter refers to a
dependency between a coefficient q.k.k1 (or Wj,k[n,m]) and the neighbor
coefficients of the same scale or sub-band Wjk, for example q,k-i,k' and Cj,k.k'-i or
These intraband dependencies are used in particular by
coders that code positions of significant coefficients in "run-length" mode and
by EBCOT/JPEG2000 coders.
Moreover, the term "interband dependency" used hereinafter refers
to a dependency between a coefficient q,k,k' and a coefficient at the same
position on the higher scale, for example q+u/2,kV2. These interband
dependencies are used in particular by "zero tree" coders (as developed by
Shapiro) and by the SPIHT coder (as developed by Said and Pearlman).
The above dependencies stem from the representation of each
quantified wavelet coefficient Q(q,k,k'n) in the form of a data string including its
significant coefficient bit (Nj,k,kin = 0 or 1), and, if that bit has the value one (1),
its sign (Sj,k,k'n, which has the value ±1) and its absolute value (Aj,k,k'n).
For example, zero tree coding exploits the statistical interdependency
of the significant coefficient bits (Nj,k,k'n), whereas EBCOT coding exploits the
statistical interdependency of the significant coefficient bits (Nj,k.k'n) and the
intersign dependency Sj,k,k'n of neighbor wavelet coefficients quantified with
different increments.
The above contextual codes use particularly complex processing
methods that require the coders to learn as many histograms as there are
contexts, which significantly limits their rate of adaptation and prevents their
use in the context of compression with a high input bit rate (large images) and
in real time, in particular for remote sensing.
One object of the invention is therefore to improve upon the above
situation.
To this end the invention proposes a wavelet transform method
dedicated to compressing digital image data, comprising a step of
transforming digital image data into wavelet coefficients divided into subbands,
a step of quantifying said wavelet coefficients, and a step of
entropically coding said quantified wavelet coefficients.
The method is characterized in that it comprises, between the
transformation and quantifying steps, a step of estimating, for each coefficient
of each sub-band of an image, first and second sets of prediction parameters
respectively associated with "North-South" and "West-East" directions as a
function of the values of the wavelet coefficients of its North and West
neighbors, and, in the entropic coding step, there are determined for each
coefficient of each sub-band of the image prediction values of the
esperance and the width of a Laplace (or generalized Gaussian) function
representing its probability density as a function of said first and/or second sets
of prediction parameters and the quantified wavelet coefficient of its North
neighbor or its West neighbor, and said quantified wavelet coefficients are
coded entropically using the associated esperances and widths determined
in this way.
Estimating the prediction parameters considerably simplifies the
prediction phase of the entropic coding step, in which digital image data at
high bit rates is compressed in real time, in particular for remote sensing.
The method of the invention may have other features and in
particular, separately or in combination:
- in the entropic coding step, when it is possible, North and West esperance
prediction values and North and West width prediction values may be
determined for the Laplace function of each quantified wavelet coefficient.
The North (or West) esperance prediction value is then preferably defined by
the product of a first prediction parameter of the first (or second) set and the
value of the North (or West) neighbor quantified wavelet coefficient and the
North (or West) width prediction value is defined by the sum of a second
prediction parameter of the first (or second) set and the product of a third
prediction parameter of the first (or second) set and the absolute value of the
North (or West) neigbour quantified wavelength coefficient. In this case four
situations must be envisaged, according to the environment of the wavelet
coefficient concerned. In the absence of a North neighbor coefficient, the
esperance and width prediction values of the Laplace function are made
identical to the West esperance and West width prediction values. In the
absence of a West neighbor coefficient, the esperance and width prediction
values of the Laplace function are made identical to the North esperance
and North width prediction values. In the absence of West and North neighbor
coefficients, fixed Laplace coding is effected. Finally, in the presence of West
and North neighbor coefficients, the esperance and width prediction values
of the Laplace function are respectively made identical to the half-sum of the
North and West esperance prediction values and to the half-sum of the North
and West width prediction values,
- the prediction parameters of the first and second sets may be estimated by
regression.
- For example, the first prediction parameters of the first and second sets
may estimated by a first regression obtained by solving an equation of the
type W[n+l,m] = 0.W[n,m] where W[n,m] is the value of a wavelet
coefficient and W[n+l,m] is the value of the neighbor wavelet coefficient
of W[n,m], and 6 is a first prediction parameter. For example, the first
equation may be solved by the least squares method, the first prediction
parameter of a first or second set then being equal to the ratio between
the non-normalized covariance and variance of the values of the wavelet
coefficients associated with the first or second set.
- Similarly, the second and third prediction parameters of the first set may be
estimated by a second regression obtained by solving a first system of
equations of the type |W[n,m] - 0N.W[n,m-l] | = aN + 0N | W[n,m-l] |,
where W[n,m] is the value of a wavelet coefficient, Wn,m-l is the value of
the North neighbor wavelet coefficient of Wn,m, and 0N, aN and /?N are
respectively first, second and third prediction parameters of the first set,
and the second and third prediction parameters of the second set may be
estimated by a second regression obtained by solving a second system of
equations of the type |W[n,m] - 0w.W[n-l,m]| = aw + /?w| W[n-l,m] |,
where Wn-l,m is the value of the West neighbor wavelet coefficient of
Wn,m and 0w, aw and /3w are respectively first, second and third
prediction parameters of the second set. For example, the first and second
systems of equations may be solved by the least squares method,
- a neighbor quantified wavelet coefficient of null value may be replaced by
a product of the quantifying increment used during the quantifying step and
a selected constant strictly greater than zero and less than or equal to one (1)
and preferably equal to 1/3,
- in the entropic coding step, after determining the esperance and width
prediction values, the Laplace function may be discretized. Alternatively, in
the entropic coding step, iterative coding may follow determination of the
esperance and width prediction values.
The invention also relates to a device for compressing digital image
data by wavelet transformation, comprising processing means having a
module for transforming digital image data it receives into wavelet
coefficients distributed in sub-bands, a module for quantifying wavelet
coefficients, and a module for entropically coding the quantified wavelet
coefficients.
The device is characterized in that its processing means further
comprise an estimator module adapted to estimate for each coefficient of
each sub-band of the image first and second sets of prediction parameters
respectively associated with "North-South" and "West-East" directions as a
function of the values of the wavelet coefficients of its North and West
neighbors and the entropic coder module is adapted to determine for each
coefficient of each sub-band of the image prediction values of the
esperance and the width of a Laplace (or generalized Gaussian) function
representing its probability density as a function of the first and/or second set
of prediction parameters and of the quantified wavelet coefficient of its North
neighbor or its West neighbor and to code the quantified wavelet coefficients
entropically using the determined associated esperances and widths.
The device of the invention may have other features and in particular,
separately or in combination:
- when it is possible, the entropic coder module may determine for the
Laplace function of each quantified wavelet coefficient North and West
esperance prediction values and North and West width prediction values. The
North (or West) esperance prediction value is then preferably defined by the
product of a first prediction parameter of the first (or second) set and the
value of the North (or West) neighbor quantified wavelet coefficient, and the
North (or West) width prediction value is defined by the sum of a second
prediction parameter of the first (or second) set and the product of a third
prediction parameter of the first (or second) set and the absolute value of the
North (or West) neighbor quantified wavelet coefficient. In this case, the
entropic coder module preferably processes four separate situations. In the
absence of a North neighbor coefficient, it makes the esperance and width
prediction values of the Laplace function identical to the West esperance
and West width prediction values. In the absence of a West neighbor
coefficient, it makes the esperance and width prediction values of the
Laplace function equal to the North esperance and North width prediction
values. In the absence of West and North neighbor coefficients, it effects fixed
Laplace coding. Finally, in the presence of West and North neighbor
coefficients, it makes the esperance and width prediction values of the
Laplace function respectively equal to the half-sum of the North and West
esperance prediction values and to the half-sum of the North and West width
prediction values,
• its estimator module may estimate the prediction values of the first and
second sets by regression.
• For example, the estimator module may estimate the first prediction
parameters of the first and second sets by a first regression obtained by
solving a first equation of the type W[n+l,m] = 0.W[n,m], where W[n,m] is
the value of a wavelet coefficient, W[n+l,m] is the value of the neighbor
wavelet coefficient of W[n,m], and e is a first prediction parameter. In this
case, the estimator module may solve said first equation by the least
squares method, for example. The first prediction parameter of a first or
second set is then equal to the ratio between the non-normalized
covariance and variance of the values of the wavelet coefficients
associated with the first or second set.
• Also, the estimator module may estimate the second and third prediction
parameters of the first set by a second regression obtained by solving a first
system of equations |W[n,m] - 0N.W[n,m-l] | = aw + /?N| W[n,m-l] |, where
W[n,m] is the value of a wavelet coefficient, Wn,m-i is the value of the North
neighbor wavelet coefficient of Wn,m, and 0N, ON and /?N are respectively
first, second and third prediction parameters of the first set, and estimate
the second and third prediction parameters of the second set by a second
regression obtained by solving a second system of equations |W[n,m] -
0w.W[n-l,m] | = aw + (Sw| W[n-l,m] |, where Wn-i,m is the value of the West
neighbor wavelet coefficient of Wn,m, and 0w, aw and /8w are respectively
first, second and third prediction parameters of the second set. In this case,
the estimator module may solve the first and second systems of equations
by the least squares method, for example,
- its entropic coding module, in the presence of a neighbor quantified
wavelet coefficient of null value, may replace it by a product of the
quantifying increment used by the quantifier module and a selected constant
strictly greater than zero and less than or equal to one (1), and preferably
equal to 1/3,
- after predicting the esperance and the width, its entropic coder module
may discretize the Laplace function. Alternatively, after predicting the
esperance and the width, the entropic coding module may proceed to
iterative coding.
The invention further relates to a digital image data
compressor/decompressor, or codec, comprising a compressor of the above
type.
Other features and advantages of the invention will become
apparent on reading the following detailed description and examining the
appended drawings, in which:
- Figure 1 is a functional block diagram of a digital image data compressor of
the invention, and
- Figure 2 shows the decomposition of an image into sub-bands with different
levels of resolution.
The appended drawings constitute part of the description of the
invention and may, if necessary, contribute to the definition of the invention.
An object of the invention is to enable the use of wavelet transforms
to compress and decompress digital image data.
Conventional wavelet transform compression (or coding)
decomposes an image I into sub-bands Wj,k called LH, HL, HH and LL, and then
transforms the digital image data l[n,m], which defines the intensity and the
colour of the pixels of the image I, into wavelets, and more particularly into an
array [n,m] of wavelet coefficients, and then quantifies the wavelet
coefficients before coding them entropically.
Here, n and m are integers that vary within the limits of the image: n
designates the column and is in the range [0, nmax - 1] and m designates the
row and is in the range [0, mmax - 1]. Thus a sub-band Wj.k is defined by a twodimensional
array of wavelet coefficients Wj,k[n,m] in which the indices n and
m vary in sub-ranges [0, nmax/2i-l] and [0, mmax / 2 - 1]. In this case N =
is the number of pixels of the image I and 1% = N/22i is the number of
wavelet coefficients in a sub-band Wj,k.
The sub-bands are coded separately, the low-pass sub-band being
coded with DPCM differential coding, and the resulting differences can be
coded by a method similar to that used for a high-pass sub-band.
Moreover, Wj,k[n,m-l] and Wj,k[n-l,m] designate the "North" and
"West" neighbors of a wavelet coefficient Wj,k[n,m]. To guarantee that a
coefficient Wj,k[n,m] will always be coded after its North and West neighbors,
which are used to determine its value, the wavelet coefficients to be coded
are processed in a particular order, namely in increasing lexicographical order
over the pair (am).
Compression in accordance with the invention differs from
conventional wavelet transform compression in particular in that it comprises,
between its (conventional) transform step and its (conventional) quantifying
step, a step in which, for each coefficient Wj,k[n,m] of each sub-band Wj,k of
an image I, there are estimated first and second sets of prediction
parameters, respectively associated with North-South and West-East
directions, as a function of the values of the wavelet coefficients of its North
neighbor Wj,k[n,m-l ] or West neighbor Wj,k[n-l ,m].
The first and second sets of prediction parameters are then used
during the entropic coding step to determine for each wavelet coefficient
Wj,k[n,m] of each sub-band Wj,k of the image I prediction values of the
esperance (or mean) /x and the width a of a Laplace function (or distribution)
representing its probability density as a function of a (North or West) neighbor
quantified wavelet coefficient:
where c represents a wavelet coefficient Wj,k[am], c' represents either the
North neighbor wavelet coefficient Wj,k[n,m-l] of c or the West neighbor
wavelet coefficient Wj,k[n-l,m] of c, and M(C') and CT(C') respectively represent
the esperance and the width as a function of the neighbor wavelet
coefficient c' concerned.
The esperance p and the width a of a Laplace distribution of density P
are defined by the following equations:
H = \xP(x)dx
cr= fa-fi\P(x)dx
The various steps of the compression method of the invention are
described in more detail next.
As indicated above, compression begins with a step in which the
pixels of the image I are transformed into wavelet coefficients Wj,k[n,m]. The
transformation step being entirely conventional, it will not be described here.
For example, it may be implemented using the Daubechies/Antonini 7-9 biorthogonal
wavelet transform, which is not strictly orthogonal but virtually
orthogonal; this preserves the energy of the images to within a few percent.
At the end of this transformation step, all of the wavelet coefficients
Wj,k[n,m] of a given sub-band Wj.k are therefore available.
The transformation step is followed by a step of estimating prediction
parameters for each wavelet coefficient Wj.k[n,m] of each sub-band Wj,k.
Hereinafter, to simplify the notation, the indices j and k of the sub-bands will no
longer be indicated. Consequently, W[n,m] designates a wavelet coefficient
belonging to a sub-band Wj,k[n,m], whether that is a LH, HH, HL or LL sub-band
(for example coded in DPCM for boustrophedon scanning).
As indicated above, the estimation step is intended to determine first
and second sets of prediction parameters that are used subsequently (during
the entropic coding step) to predict the values of the esperance (or mean) ^
and the width a of a Laplace function (or distribution) representing the
probability density of a quantified wavelet coefficient allowing for the value
assumed by the quantified wavelet coefficient of either or both of its North
and West neighbors.
The esperance M and the width a are defined relative to the
prediction parameters of the first and second sets. For example, each set
includes three prediction parameters 6 (first), a (second) and p (third), and the
equations linking those parameters to the esperance n and the width a take
the following forms:
a = a + /3.c' (2)
where, as indicated above, c' designates the context representing either the
North neighbor wavelet coefficient W[n,m-l] of c (or W[n,m]) or the West
neighbor wavelet coefficient W[n-l ,m] of c.
10
In fact, as will emerge hereinafter, two esperance and width
predictions are used, according to the neighbor concerned (North or East): a
North prediction relates to the North esperance PN and the North width