Information Technology Reference
In-Depth Information
removes correlation between a coefficient and its neighbours, they may not be
statistically independent even if they are uncorrelated. The main reasons for this is that
small and especially zero coefficients in wavelet subbands tend to clump together,
located at points corresponding to smooth areas in the image, and are grouped
together across subbands in the parent-child relationship. After binarization, a context
is selected, and the probabilities for 0 and 1 that are maintained in the appropriate
context will be fed to the arithmetic coding function along with the value itself to be
coded [8].
5.4.3 Arithmetic Coding
Conceptually, an arithmetic coder can be thought of a progressive way of
producing variable-length codes for entire sequences of symbols based on the
probabilities of their constituent symbols. For example, if we know the probability
of 0 and 1 in a binary sequence, we also know the probability of the sequence
itself occurring. So if
P(0)=0.2, P(1)=0.8
then
P(11101111111011110101)=(0.2)3(0.8)17=1.8x10-4 (assuming independent
occurrences).
Information theory then says that optimal entropy coding of this sequence requires
12.4
. AC produces a code-word very close to this optimal
length, and implementations can do so progressively, outputting bits when
possible as more bits arrive. All arithmetic coding (AC) requires estimates of the
probabilities of symbols as they occur, and this is where context modelling fits in.
Since AC can, in effect, assign a fractional number of bits to a symbol, it is very
efficient for coding symbols with probabilities very close to 1, without the
additional complication of run-length coding. The aim of context modelling within
Dirac is to use information about the symbol stream to be encoded to produce
accurate probabilities as close to 1 as possible. Dirac computes these estimates for
each context by maintaining a 16 bit probability word representing the probability
of a zero value in that context. When a value has been coded, the probability is
modified by incrementing (if zero was coded) or decrementing this value by a
delta. The delta value itself depends only on the probability and is derived from a
look-up table. If the probability is near 1 or 0, the delta is approximately 1/256; if
the probability is near 1/2, the delta is approximately 1/32. This avoids the need to
maintain explicit counts of 1 and 0 and makes for very efficient updating. There is
no rescaling or division in the computation, and the estimate adapts rapidly for
balanced probabilities and slowly for highly skewed probabilities, as it should.
The non-zero values in the higher frequency sub-bands of the wavelet
transform are often in the same part of the picture as they are in lower frequency
sub-bands. Dirac creates statistical models of these correlations and arithmetic
coding allows us to exploit these correlations to achieve better compression. The
Search WWH ::
Custom Search