4 ms·

I'll link the same paper TD-Linux did in the BPG discussion: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.41.6711&rep=rep1&type=pdf http://citeseerx

by derf_ 12y ago

I'll link the same paper TD-Linux did in the BPG discussion: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.41.6711&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.41.... The damning bits are this: "A fundamental weakness of fractal block coders is that the coders possess no control over the codebook. Codewords are too densely clustered around the very common all-zero subtree and too sparsely distributed elsewhere. This dense clustering of near-zerotrees increases codeword cost but contributes very little to image fidelity. ... At 0.25 b/pixel, over 80% of all coefficients in the 512 × 512 Lena image are assigned to zerotrees by our zerotree-augmented wavelet coder. Hence, only about 20% of the fractal coder’s codewords are significantly different from a zerotree. This redundancy is costly, since when using self-quantization we pay a substantial number of bits to differentiate between these essentially identical zero code words."

ska 12y ago
I haven't read that paper in ages, but Davis's points as I remember them aren't really fundamental. For example you can easily do IFS codecs in a wavelets domain and capture detail that zero trees miss, while still taking advantage of the energy concentration in that domain. This shows up in the focus on "fractal block coders" but the blocks here are not necessary. Not that I'm arguing for IFS codecs, mind, but Davis did miss the point a bit.
- derf_ 12y ago
  I'm not sure I'm following your argument. The point is that many regions of an image simply do not have detail. This is made obvious by sparseness in a wavelet representation, but the representation is not key to the argument. A concrete example might help. If I have an image with some large, flat sky region, then for every piece of sky, an IFS needs to say which other piece of sky it resembles, even though they are all largely the same. That costs bits which do nothing to improve quality. Davis is not the only one to make the observation (he cites two others in that paper), but he does quantify the magnitude of the problem. It's clear it requires some solution before IFS codecs have a chance of being competitive. This is complicated by the fact that in an IFS, it's not clear which regions are smooth without doing several iterations, but the decoder needs to do all of its codebook pruning before even the first iteration. I'm not aware of a practical solution ever being demonstrated.
  - ska 12y ago
    The point is that the concentration of energy in lower frequencies (i.e. the reason you see sparseness in the wavelet domain) is separable from the issue of using IFS. After all, using IFS means you encode an operator, not the signal. One way to demonstrate this (which was shown around the time of Davis's paper, if I recall correctly) is to do the IFS codec in the wavelet domain hierarchically (on quadtrees in the case of an orthonormal wavelet basis). This gives you a similar advantage of spending your encoder bits (which should still be handled by an entropy coder, regardless of method) primarily get spent where the image energy is, but does not truncate information as hard as, say, a zerotree approach. The problems Davis points out with IFS codecs done on blocks in the spatial domain are issues with block/patch operations and with operating in the spatial domain, not with IFS per se. The fundamental idea behind IFS codecs is that you encode a transform whose fixed point approximates your signal, you don't encode the signal directly. The real problem is the difficulty in embedding them, and the need to iterate a few times to converge the result.. which is what you allude to I think. [note, I really should revisit Davis's paper before discussing , because I'm operating from memory here...]

by derf_ 12y ago

ska 12y ago

I haven't read that paper in ages, but Davis's points as I remember them aren't really fundamental. For example you can easily do IFS codecs in a wavelets domain and capture detail that zero trees miss, while still taking advantage of the energy concentration in that domain. This shows up in the focus on "fractal block coders" but the blocks here are not necessary. Not that I'm arguing for IFS codecs, mind, but Davis did miss the point a bit.

derf_ 12y ago
I'm not sure I'm following your argument. The point is that many regions of an image simply do not have detail. This is made obvious by sparseness in a wavelet representation, but the representation is not key to the argument. A concrete example might help. If I have an image with some large, flat sky region, then for every piece of sky, an IFS needs to say which other piece of sky it resembles, even though they are all largely the same. That costs bits which do nothing to improve quality. Davis is not the only one to make the observation (he cites two others in that paper), but he does quantify the magnitude of the problem. It's clear it requires some solution before IFS codecs have a chance of being competitive. This is complicated by the fact that in an IFS, it's not clear which regions are smooth without doing several iterations, but the decoder needs to do all of its codebook pruning before even the first iteration. I'm not aware of a practical solution ever being demonstrated.
- ska 12y ago
  The point is that the concentration of energy in lower frequencies (i.e. the reason you see sparseness in the wavelet domain) is separable from the issue of using IFS. After all, using IFS means you encode an operator, not the signal. One way to demonstrate this (which was shown around the time of Davis's paper, if I recall correctly) is to do the IFS codec in the wavelet domain hierarchically (on quadtrees in the case of an orthonormal wavelet basis). This gives you a similar advantage of spending your encoder bits (which should still be handled by an entropy coder, regardless of method) primarily get spent where the image energy is, but does not truncate information as hard as, say, a zerotree approach. The problems Davis points out with IFS codecs done on blocks in the spatial domain are issues with block/patch operations and with operating in the spatial domain, not with IFS per se. The fundamental idea behind IFS codecs is that you encode a transform whose fixed point approximates your signal, you don't encode the signal directly. The real problem is the difficulty in embedding them, and the need to iterate a few times to converge the result.. which is what you allude to I think. [note, I really should revisit Davis's paper before discussing , because I'm operating from memory here...]