trivial: haar and overflow, a few lossless media schemes
cr88192
issues:
one can include some divisions to keep the range sane (which incures
roundoff and thus makes it lossy);
one can increase the bit count (say, going from 8 to 16 bits) to prevent
overflow.
both these are not great, but a third idea comes up:
one does not preserve the full range of the data, thus it is allowed to
overflow, and assuming no other alterations occure the result is
reconstructed losslessly.
this seems obvious enough.
now the next one:
how exactly would this effect a compressor?
what would be the effect of applying it in multiple layers?
this is a little more difficult to imagine than the simple flat transforms I
had tried previously ("haar wavelets" afaik).
the idea here is this could be tried with audio:
I expect there to be a lot of difference between samples, but some degree of
"phase corellation".
now another idea comes up:
I process an input stream, grabbing globs of samples (2^n, where n is the
number of times the imput is transformed).
I then filter the samples a number of times, eg, seperating into "high" and
"low" components.
I then subtract the values from the previous glob of samples (my guess is
that tonal patterns should be largely eliminated by this).
the results (consisting of frames of sample globs) is, eg, arithmatic
encoded.
I am unsure how well this would work, I guess I could try.
likely it would be crappy.
misc:
I before (fairly recently) tried doing a variation of a haar wavelet on
video (first subtracting the previous frame, then doing the transform on the
result). then, again, I arithmatic coded the results.
(I forget exactly why I did the frame subtraction before the filtering
though, I think it was because this resulted in better compression due to
less "noise" being introduced as a result of variations elsewhere on the
image).
for decoding, I basically unfilter the frames and add them to the previous.
another thing I had wondered about was if I could reverse the stream by
starting with a future frame and sucessively subtracting the previous
frames' deltas. this seems like it could work, but I am unsure if it is
still lossless (or not prone to corruption). I had not tried this.
requirements: lossless, 320x240x15fps, around 4.5Mbps (dunno if this is at
all good for lossless video, since I don't really know of any common
lossless video codecs to compare with).
allowing loss (primarily temporal) allowed me to get it down to about 2Mbps,
but then it looked crappy.
my guess is better compression would require motion prediction (afaik not
necissarily lossy, eg, if I view it as just copying tiles around).
I have had good successes with similar for lightmaps (even if I omit
arithmatic coding in favor of rle due to the arith coder making decoding
take annoyingly long...).
maybe I should at some point compare haar wavelets with doing a haar
transform. it is a mystery for me which would have better results (I am
thinking maybe the transform could make things more regular though...).
maybe I should implement a huffman coder and play with that eventually as
well? possibly it could decode a faster than the arith coder I am using...
ok, I am still a newb to compression and am probably being stupid...
or something...
Thomas Richter
> I was thinking a little about the haar transform, and considering some
> issues:
> one can include some divisions to keep the range sane (which incures
> roundoff and thus makes it lossy);
> one can increase the bit count (say, going from 8 to 16 bits) to prevent
> overflow.
The funny thing is: You don't need to worry about overflows if you do it
right. Mathematically, the "unsigned char's" of C with addition and
subtraction form a perfectly fine "group structure", so you can add and
subtract just fine, and invert back. You'll get wrap-arounds, but
exactly the same on the reverse side.
> both these are not great,
...and unnecessary. (-: However, *common* wraparounds will spoil the
statistics.
> but a third idea comes up:
> one does not preserve the full range of the data, thus it is allowed to
> overflow, and assuming no other alterations occure the result is
> reconstructed losslessly.
>
> this seems obvious enough.
Hmm, depends on what "preverse the full range of the data" shall mean.
Of the original data: Yes, you'd had to if you want to be lossless. Of
the addition/subtraction/Haar wavelet: Yes, see above, that's possible.
> now the next one:
> how exactly would this effect a compressor?
Would cause "bogus" peaks where wraparounds happen.
> what would be the effect of applying it in multiple layers?
As in "applying the transform several times"? Problematic because you
get edges (and thus a lot of impulses) in all derived cascades.
> this is a little more difficult to imagine than the simple flat transforms I
> had tried previously ("haar wavelets" afaik).
>
> the idea here is this could be tried with audio:
> I expect there to be a lot of difference between samples, but some degree of
> "phase corellation".
This idea actually works well with audio (since you don't want to run a
lot of cascades there either). I wrote a simple lossless audio codec
quite a while ago that used a very similar idea. First delta
transformation, then bitplane decorrelation using Gray-codes, then
context-based arithmetic bitplane coding. Good enough to give 1:4
compression on average.
> now another idea comes up:
> I process an input stream, grabbing globs of samples (2^n, where n is the
> number of times the imput is transformed).
> I then filter the samples a number of times, eg, seperating into "high" and
> "low" components.
> I then subtract the values from the previous glob of samples (my guess is
> that tonal patterns should be largely eliminated by this).
Depends on what "previous" is. If this is the "previous" block, then
that's possibly not good enough. You can only expect correlation within
a small neighbourhood of the given sample, or if the data itself is
highly correlated (i.e. a sine wave, or close to it).
> the results (consisting of frames of sample globs) is, eg, arithmatic
> encoded.
Approximately the above idea, yes.
> I am unsure how well this would work, I guess I could try.
> likely it would be crappy.
Well, you get "close enough". You know, even the best lossless audio
codecs don't get that much better than 1:4 on average either.
> misc:
> I before (fairly recently) tried doing a variation of a haar wavelet on
> video (first subtracting the previous frame, then doing the transform on the
> result). then, again, I arithmatic coded the results.
> (I forget exactly why I did the frame subtraction before the filtering
> though, I think it was because this resulted in better compression due to
> less "noise" being introduced as a result of variations elsewhere on the
> image).
The idea of delta-coding video is pretty well-known, actually. It was
one of the first successfully used approaches. That, plus a tiny context
build around the currently compressed pixel. Not as great as H264, but
does a decent job for "home usage".
> for decoding, I basically unfilter the frames and add them to the previous.
> another thing I had wondered about was if I could reverse the stream by
> starting with a future frame and sucessively subtracting the previous
> frames' deltas. this seems like it could work, but I am unsure if it is
> still lossless (or not prone to corruption). I had not tried this.
How to you plan to reconstruct these - if you don't want to sent frames
"backwards"? Otherwise, you'd to reorder frames, similar to the
classical B-frames in the H26x codec family.
> requirements: lossless, 320x240x15fps, around 4.5Mbps (dunno if this is at
> all good for lossless video, since I don't really know of any common
> lossless video codecs to compare with).
> allowing loss (primarily temporal) allowed me to get it down to about 2Mbps,
> but then it looked crappy.
Ah, I'm not too much in the video business to judge that.
> my guess is better compression would require motion prediction (afaik not
> necissarily lossy, eg, if I view it as just copying tiles around).
Yes, better compression requires motion prediction + compensation.
> I have had good successes with similar for lightmaps (even if I omit
> arithmatic coding in favor of rle due to the arith coder making decoding
> take annoyingly long...).
>
> maybe I should at some point compare haar wavelets with doing a haar
> transform. it is a mystery for me which would have better results (I am
> thinking maybe the transform could make things more regular though...).
Neither, necessarely. Try longer wavelets, even a 5-3 is better than
Haar, and almost as simple.
> maybe I should implement a huffman coder and play with that eventually as
> well? possibly it could decode a faster than the arith coder I am using...
A good arithmetic coder can be almost as fast as coding bits directly,
i.e. as long as you don't want to *sell* the code and only use it
privately, I would suggest to have a look at the MQ or QM coder. That
can be made incredibly fast. The latter is in the traditional JPEG docs,
the former is a slight variation of it in JPEG2000. Google for JPEG2000
FDIS, you should find it.
So long,
Thomas
cr88192
"Thomas Richter" <th...@math.tu-berlin.de> wrote in message
news:415F2588...@math.tu-berlin.de...
> Hi,
>
>> I was thinking a little about the haar transform, and considering some
>> issues:
>> one can include some divisions to keep the range sane (which incures
>> roundoff and thus makes it lossy);
>> one can increase the bit count (say, going from 8 to 16 bits) to prevent
>> overflow.
>
> The funny thing is: You don't need to worry about overflows if you do it
> right. Mathematically, the "unsigned char's" of C with addition and
> subtraction form a perfectly fine "group structure", so you can add and
> subtract just fine, and invert back. You'll get wrap-arounds, but exactly
> the same on the reverse side.
>
the issue though is that an actual haar transform, on the reverse side,
requires a division:
A'=A+B
B'=A-B
A"=(A'+B')/2
B"=(A'-B')/2
and overflow seems to break this.
FF FF FF FF
FE FE 00 00
FC 00 00 00
--
7E 7E 00 00
3F 3F 3F 3F
one can modify this to keep it in range, but it is then lossy (it loses
low-order bits).
unless I am missing something, or there is some other way to do the
transform.
>> both these are not great,
>
> ...and unnecessary. (-: However, *common* wraparounds will spoil the
> statistics.
>
ok.
> > but a third idea comes up:
>> one does not preserve the full range of the data, thus it is allowed to
>> overflow, and assuming no other alterations occure the result is
>> reconstructed losslessly.
>>
>> this seems obvious enough.
>
> Hmm, depends on what "preverse the full range of the data" shall mean. Of
> the original data: Yes, you'd had to if you want to be lossless. Of the
> addition/subtraction/Haar wavelet: Yes, see above, that's possible.
>
yes, it works for the haar wavelet, but breaks for the haar transform (or at
least the losless variety).
>> now the next one:
>> how exactly would this effect a compressor?
>
> Would cause "bogus" peaks where wraparounds happen.
>
ok.
>> what would be the effect of applying it in multiple layers?
>
> As in "applying the transform several times"? Problematic because you get
> edges (and thus a lot of impulses) in all derived cascades.
>
makes sense.
>> this is a little more difficult to imagine than the simple flat
>> transforms I had tried previously ("haar wavelets" afaik).
>>
>> the idea here is this could be tried with audio:
>> I expect there to be a lot of difference between samples, but some degree
>> of "phase corellation".
>
> This idea actually works well with audio (since you don't want to run a
> lot of cascades there either). I wrote a simple lossless audio codec quite
> a while ago that used a very similar idea. First delta transformation,
> then bitplane decorrelation using Gray-codes, then context-based
> arithmetic bitplane coding. Good enough to give 1:4 compression on
> average.
>
ok, cool.
>> now another idea comes up:
>> I process an input stream, grabbing globs of samples (2^n, where n is the
>> number of times the imput is transformed).
>> I then filter the samples a number of times, eg, seperating into "high"
>> and "low" components.
>> I then subtract the values from the previous glob of samples (my guess is
>> that tonal patterns should be largely eliminated by this).
>
> Depends on what "previous" is. If this is the "previous" block, then
> that's possibly not good enough. You can only expect correlation within a
> small neighbourhood of the given sample, or if the data itself is highly
> correlated (i.e. a sine wave, or close to it).
>
makes sense.
I had just guessed that maybe it would be close enough to make it workable.
maybe not though.
>> the results (consisting of frames of sample globs) is, eg, arithmatic
>> encoded.
>
> Approximately the above idea, yes.
>
>> I am unsure how well this would work, I guess I could try.
>> likely it would be crappy.
>
> Well, you get "close enough". You know, even the best lossless audio
> codecs don't get that much better than 1:4 on average either.
>
hmm...
>> misc:
>> I before (fairly recently) tried doing a variation of a haar wavelet on
>> video (first subtracting the previous frame, then doing the transform on
>> the result). then, again, I arithmatic coded the results.
>> (I forget exactly why I did the frame subtraction before the filtering
>> though, I think it was because this resulted in better compression due to
>> less "noise" being introduced as a result of variations elsewhere on the
>> image).
>
> The idea of delta-coding video is pretty well-known, actually. It was one
> of the first successfully used approaches. That, plus a tiny context build
> around the currently compressed pixel. Not as great as H264, but does a
> decent job for "home usage".
>
yes, cool.
>> for decoding, I basically unfilter the frames and add them to the
>> previous. another thing I had wondered about was if I could reverse the
>> stream by starting with a future frame and sucessively subtracting the
>> previous frames' deltas. this seems like it could work, but I am unsure
>> if it is still lossless (or not prone to corruption). I had not tried
>> this.
>
> How to you plan to reconstruct these - if you don't want to sent frames
> "backwards"? Otherwise, you'd to reorder frames, similar to the classical
> B-frames in the H26x codec family.
>
actually, I was assuming file playback and editing (this I think would be
the main use of lossless video anyways). you could seek forwards in the
stream, then start jumping backwards and decoding frames.
reordering the stream would likely be necessary for stream playback, but if
you are playing a stream then reversing it is not really a likely assumption
anyways...
>> requirements: lossless, 320x240x15fps, around 4.5Mbps (dunno if this is
>> at all good for lossless video, since I don't really know of any common
>> lossless video codecs to compare with).
>> allowing loss (primarily temporal) allowed me to get it down to about
>> 2Mbps, but then it looked crappy.
>
> Ah, I'm not too much in the video business to judge that.
>
well, it is a signifigant improvement over uncompressed video, or
essentially about 28Mbps.
it is still pretty lame though, lossy compression does a lot better.
>> my guess is better compression would require motion prediction (afaik not
>> necissarily lossy, eg, if I view it as just copying tiles around).
>
> Yes, better compression requires motion prediction + compensation.
>
ok.
>> I have had good successes with similar for lightmaps (even if I omit
>> arithmatic coding in favor of rle due to the arith coder making decoding
>> take annoyingly long...).
>>
>> maybe I should at some point compare haar wavelets with doing a haar
>> transform. it is a mystery for me which would have better results (I am
>> thinking maybe the transform could make things more regular though...).
>
> Neither, necessarely. Try longer wavelets, even a 5-3 is better than Haar,
> and almost as simple.
>
ok, I will look into this.
>> maybe I should implement a huffman coder and play with that eventually as
>> well? possibly it could decode a faster than the arith coder I am
>> using...
>
> A good arithmetic coder can be almost as fast as coding bits directly,
> i.e. as long as you don't want to *sell* the code and only use it
> privately, I would suggest to have a look at the MQ or QM coder. That can
> be made incredibly fast. The latter is in the traditional JPEG docs, the
> former is a slight variation of it in JPEG2000. Google for JPEG2000 FDIS,
> you should find it.
>
ok.
the one I was using is a modified form of an example encoder/decoder from an
article. it is ok, but I want decompression to be fast.
the encoder doesn't need to be that fast, but I want a fast decoder.
I had thought some about huffman encoding, and had some ideas for possibly
how to decode the stream fairly fast (I am thinking I could read from the
stream in, eg, 32 bit chunks, shift off a few bits, and use masking and a
search for decoding).
another possible approach could be to view it as a set of steps, and for
each step if the value is all 1s I shift off the low bits and go to the next
step, and when there is a step not including all ones it becomes an array
index.
(dunno, I will probably have to gather more info to try to determine good
approaches).
but then I would still have to deal with limitations inherit in huffman, but
I do wonder how good huffman+rle could be, and if decode could be faster
than an arithmatic decoder.
the encoder I am using apparently works by reading/writing a single bit at a
time, which seems imo a fairly slow approach.
dunno how a good decoder would compare.
I am doubting it would be possible to get anywhere the speed of a pure rle
decoder, but I could at least probably get somewhat better compression.
or something...
cr88192
> the issue though is that an actual haar transform, on the reverse side,
> requires a division:
>
> A'=A+B
> B'=A-B
>
> A"=(A'+B')/2
> B"=(A'-B')/2
>
> and overflow seems to break this.
>
> FF FF FF FF
> FE FE 00 00
> FC 00 00 00
> --
> 7E 7E 00 00
> 3F 3F 3F 3F
>
> one can modify this to keep it in range, but it is then lossy (it loses
> low-order bits).
>
> unless I am missing something, or there is some other way to do the
> transform.
>
A'=A
B'=B-A
A"=A'
B"=A'+B'
will handle layering, and eliminates the need division (and the the problem
of dealing with overflows).
FF FF FF FF
FF FF 00 00
FF 00 00 00
--
FF FF 00 00
FF FF FF FF
FF 00 FF 00
FF FF 01 01
FF 01 00 00
or am I just reinventing stuff...
ok, I did go looking for info about other kinds of wavelets (5-3 and such).
mostly I just find lots of really mathy stuff that is not terribly easy for
me to follow (maybe I am just stupid). stuff talking about wavelets goes a
whole lot into talking about dft, fft and use of matrices as an
optimization, and uses mathy notation (personally I am far more comfortable
looking, eg, at a for loop and a few simple statements than a combination
summation and tensor notation with some other stuff mixed in). by the time
they get to wavelets (even the haar wavelet) they are still being overly
mathy, and not really explaining simple things (like how exactly the
matrices they are using are used to transform the input values). my goal is
to get a basic understanding of the process and the algo's for
filtering/unfiltering the data, and not trying to derive the algos from a
few abstract equations...
imo this is like people sitting there throwing formal semantics notation at
me as opposed to just a simpler but less formal terse description of the
behavior (or people's endless obsession on lamda calculus...).
this may just be me though. I may just be stupid, I just don't like overly
mathy stuff in cases where it is unnecessary.
Thomas Richter
> me being stupid:
> A'=A
> B'=B-A
> A"=A'
> B"=A'+B'
> will handle layering, and eliminates the need division (and the the problem
> of dealing with overflows).
This way you only implement the first step of the haar wavelet, you
also need to implement the "averaging" step for the low-pass. However,
even that can be made lossless. The trick here is named "lifting" of
wavelets:
(a,b) -> (a,b-a) -> (a + (b-a) / 2, b - a)
That is, in the first step, replace the second component by the
difference of the first and the second ("prediction step") in the next
step, you add half of the second component to the first ("update step").
You can easily convince yourself that this is identical to the haar
wavelet lowpass since
a + (b - a)/2 = a/2 + b/2
and it is also revertable, regardless of overflows, since the decoder
can easily revert the process: Just take the second component, half
it and subtract it from the first. Since the "errors" in the division in
the decoder are identical to the errors made on the encoder, you'll get
the original "a". By that, and the second component, you get back the
original first component.
Mathematically, the reason why this is invertible is that matrices
of the form
1 b and 1 0
0 1 a 1
are invertible in the matrix-modul Z_n. (Simple calculation)
and the fact that every wavelet can be written as a product of matrices
of the above form (Sweldon's lifting algorithm, you'll find this paper
on http://www.math.tu-berlin.de/~thor/imco)
> ok, I did go looking for info about other kinds of wavelets (5-3 and such).
> mostly I just find lots of really mathy stuff that is not terribly easy for
> me to follow (maybe I am just stupid).
In case you'll need a ready-prepared lifting for the 5-3: You find one
in the JPEG2000 FDIS, also on the above web page.
> stuff talking about wavelets goes a
> whole lot into talking about dft, fft and use of matrices as an
> optimization, and uses mathy notation (personally I am far more comfortable
> looking, eg, at a for loop and a few simple statements than a combination
> summation and tensor notation with some other stuff mixed in). by the time
> they get to wavelets (even the haar wavelet) they are still being overly
> mathy, and not really explaining simple things (like how exactly the
> matrices they are using are used to transform the input values). my goal is
> to get a basic understanding of the process and the algo's for
> filtering/unfiltering the data, and not trying to derive the algos from a
> few abstract equations...
Well, I understand that to some degree. I just hope you get you "curious
enough" to ask what's all behind that. (That's my prefered way, first get
it somehow working, then ask why it works, then make it better).
> imo this is like people sitting there throwing formal semantics notation at
> me as opposed to just a simpler but less formal terse description of the
> behavior (or people's endless obsession on lamda calculus...).
Then you'll might look into another Sweldon's paper (also on the above
web-page) named "Building your own wavelets at home". It is not at all
math-based, it explains in simple steps how "prediction" and "update" works.
So long,
Thomas
cr88192
"Thomas Richter" <th...@cleopatra.math.tu-berlin.de> wrote in message
news:cjrqof$8ah$1...@mamenchi.zrz.TU-Berlin.DE...
> Hi,
>
>> me being stupid:
>
>> A'=A
>> B'=B-A
>
>> A"=A'
>> B"=A'+B'
>
>> will handle layering, and eliminates the need division (and the the
>> problem
>> of dealing with overflows).
>
> This way you only implement the first step of the haar wavelet, you
> also need to implement the "averaging" step for the low-pass. However,
> even that can be made lossless. The trick here is named "lifting" of
> wavelets:
>
> (a,b) -> (a,b-a) -> (a + (b-a) / 2, b - a)
>
> That is, in the first step, replace the second component by the
> difference of the first and the second ("prediction step") in the next
> step, you add half of the second component to the first ("update step").
> You can easily convince yourself that this is identical to the haar
> wavelet lowpass since
>
> a + (b - a)/2 = a/2 + b/2
>
> and it is also revertable, regardless of overflows, since the decoder
> can easily revert the process: Just take the second component, half
> it and subtract it from the first. Since the "errors" in the division in
> the decoder are identical to the errors made on the encoder, you'll get
> the original "a". By that, and the second component, you get back the
> original first component.
>
> Mathematically, the reason why this is invertible is that matrices
> of the form
>
> 1 b and 1 0
> 0 1 a 1
>
> are invertible in the matrix-modul Z_n. (Simple calculation)
> and the fact that every wavelet can be written as a product of matrices
> of the above form (Sweldon's lifting algorithm, you'll find this paper
> on http://www.math.tu-berlin.de/~thor/imco)
>
ok, cool.
>> ok, I did go looking for info about other kinds of wavelets (5-3 and
>> such).
>> mostly I just find lots of really mathy stuff that is not terribly easy
>> for
>> me to follow (maybe I am just stupid).
>
> In case you'll need a ready-prepared lifting for the 5-3: You find one
> in the JPEG2000 FDIS, also on the above web page.
>
well, I can decipher specific math, but fail more at more abstract math...
>> stuff talking about wavelets goes a
>> whole lot into talking about dft, fft and use of matrices as an
>> optimization, and uses mathy notation (personally I am far more
>> comfortable
>> looking, eg, at a for loop and a few simple statements than a combination
>> summation and tensor notation with some other stuff mixed in). by the
>> time
>> they get to wavelets (even the haar wavelet) they are still being overly
>> mathy, and not really explaining simple things (like how exactly the
>> matrices they are using are used to transform the input values). my goal
>> is
>> to get a basic understanding of the process and the algo's for
>> filtering/unfiltering the data, and not trying to derive the algos from a
>> few abstract equations...
>
> Well, I understand that to some degree. I just hope you get you "curious
> enough" to ask what's all behind that. (That's my prefered way, first get
> it somehow working, then ask why it works, then make it better).
>
yes.
I am just using endless guessing and fiddling to try to get better
compression.
>> imo this is like people sitting there throwing formal semantics notation
>> at
>> me as opposed to just a simpler but less formal terse description of the
>> behavior (or people's endless obsession on lamda calculus...).
>
> Then you'll might look into another Sweldon's paper (also on the above
> web-page) named "Building your own wavelets at home". It is not at all
> math-based, it explains in simple steps how "prediction" and "update"
> works.
>
yes, cool.
maybe I am just lazy.
it is like:
I like c, and don't like too much fp, c seems more natural to me;
I don't like overly mathy stuff (I think fp was created by mathheads for
mathheads);
I am more in the "worse is better" mindset, but there is also "better is
better";
I don't get the endless obsession on lambda, yes, it converts to an
interesting language construct, but lambda in itself does not lead to a
worthwhile coding experience;
why do semantics need to be strictly defined when an approximate definition
is easier and allows more room in the implementation?
what purpose does the hindley-miller typesystem serve other than to be a
pita for newbies?
why does info about compression related stuff seem to be so damn mathy and
assume the reader doesn't understand computers? (I can't imagine much other
use, or why a non-programmer would give a crap about compression)
...
these seem like mysteries to me...
oh well, before this post I did another post on the toplevel about my
ongoing battle with lossless compression...
Thomas Richter
> it is like:
> I like c, and don't like too much fp, c seems more natural to me;
> I don't like overly mathy stuff (I think fp was created by mathheads for
> mathheads);
> I am more in the "worse is better" mindset, but there is also "better is
> better";
> I don't get the endless obsession on lambda, yes, it converts to an
> interesting language construct, but lambda in itself does not lead to a
> worthwhile coding experience;
> why do semantics need to be strictly defined when an approximate definition
> is easier and allows more room in the implementation?
> what purpose does the hindley-miller typesystem serve other than to be a
> pita for newbies?
> why does info about compression related stuff seem to be so damn mathy and
> assume the reader doesn't understand computers? (I can't imagine much other
> use, or why a non-programmer would give a crap about compression)
> ...
>
> these seem like mysteries to me...
Why mathematics? Well, I guess that's because this language (and it
really is) is as exact as it can be. You need to put vague ideas into
rigit concepts to get "unrefutable" results, and to get to a level of
abstraction so ideas can be more easily "ported" from other fields.
I would believe the most fruitful mathematical inventions come from
situations where you find yourself in the baffling situation that a
concept that was developed in one branch mysterically fits well into a
quite different busyness, and can be applied to form new ideas. For
that, one must try to find the "core" of an idea, and for that, one has
to formulate this as clear as possible.
For me, this "core" is best expressed in a mixture of math and C++
maybe, but people tend to think different. "math" is just the
standardization of this language. (-;
So long,
Thomas
cr88192
> cr88192 wrote:
>
>> it is like:
>> I like c, and don't like too much fp, c seems more natural to me;
>> I don't like overly mathy stuff (I think fp was created by mathheads for
>> mathheads);
>> I am more in the "worse is better" mindset, but there is also "better is
>> better";
>> I don't get the endless obsession on lambda, yes, it converts to an
>> interesting language construct, but lambda in itself does not lead to a
>> worthwhile coding experience;
>> why do semantics need to be strictly defined when an approximate
>> definition is easier and allows more room in the implementation?
>> what purpose does the hindley-miller typesystem serve other than to be a
>> pita for newbies?
>> why does info about compression related stuff seem to be so damn mathy
>> and assume the reader doesn't understand computers? (I can't imagine much
>> other use, or why a non-programmer would give a crap about compression)
>> ...
>>
>> these seem like mysteries to me...
>
>
> Why mathematics? Well, I guess that's because this language (and it really
> is) is as exact as it can be. You need to put vague ideas into
> rigit concepts to get "unrefutable" results, and to get to a level of
> abstraction so ideas can be more easily "ported" from other fields.
>
they may be rigid and abstract, but tend also to be far more obscure.
it also seems annoying that many people using math in books and similar try
to use the most obscure varieties they are really fammiliar with, when
really imo they should be sticking within the limits of, say, highschool
algebra, and possibly low-level calculus (if at all possible avoiding
concepts like limits or integrals, or even really using matrix math in any
more than a simple and straightforward way, and any fancy syntax).
for more obscure, eg, non-numerical types of math, it would be preferable
that they be avoided if possible. these are, imo, not that useful in a
general sense.
in many cases one may just be too lazy to bother to parse the math to figure
out how it is working (just like one can get tired over reading an overly
long-winded description of the topic, as opposed to a much smaller and
terser but still fairly complete description).
> I would believe the most fruitful mathematical inventions come from
> situations where you find yourself in the baffling situation that a
> concept that was developed in one branch mysterically fits well into a
> quite different busyness, and can be applied to form new ideas. For that,
> one must try to find the "core" of an idea, and for that, one has
> to formulate this as clear as possible.
>
well, imo there is a limit here.
data about, say, compression or filtering algorithms are unlikely to really
be relevant to non-programmers, so using something more like a programming
language makes more sense here (it is far easier to transliterate between
many languages than to map math syntax to some language).
math is typically mapped to ascii in rather inconsistent and horrid looking
ways (leaving one looking at a chunk of text being like "wtf is this?").
programming language syntax is typically allready in ascii, so no problem
here.
mathmaticians finding themselves drawn to filtering or compression really
should consider learning programming imo.
> For me, this "core" is best expressed in a mixture of math and C++
> maybe, but people tend to think different. "math" is just the
> standardization of this language. (-;
>
ok.
I have seen this effect in many catagories, but the most apparent with
graphics and compression algos.
often I have found other subjects, eg, basic physics or even things like
quaternions, to be often described in a much more programmer friendly way,
than, say, wavelet or dct filtering.
everything found is either highly mathy or "plain english", which is
tedious. the english descriptions are often worse than the math, as the
meaning is less clear and one has to try to decipher what exactly is being
said.
I am more for "worse is better" aproach, and math is more a "better is
better" topic.
one can solve things in half-assed and ugly ways, which often seems far more
"natural".
oh well, this is probably a pointless topic...
I am probably too stupid to really be commenting on this anyways.
Aleks Jakulin
>> In case you'll need a ready-prepared lifting for the 5-3: You find
>>
> well, I can decipher specific math, but fail more at more abstract
> math...
You can take a look at my wavelet "tutorial" that's based on analyzing
code: http://www.ailab.si/aleks/Wavelets/index.html
Aleks
--
mag. Aleks Jakulin
http://www.ailab.si/aleks/
Artificial Intelligence Laboratory,
Faculty of Computer and Information Science,
University of Ljubljana, Slovenia.
cr88192
"Aleks Jakulin" <a_jakulin@@hotmail.com> wrote in message
news:ck0gu5$q8i$1...@planja.arnes.si...
> cr88192 wrote:
>>> In case you'll need a ready-prepared lifting for the 5-3: You find
>>> in the JPEG2000 FDIS, also on the above web page.
>>>
>> well, I can decipher specific math, but fail more at more abstract
>> math...
>
> You can take a look at my wavelet "tutorial" that's based on analyzing
> code: http://www.ailab.si/aleks/Wavelets/index.html
>
I may look at it more later.
now I am just thinking something is kind of ammusing here:
apparently if someone isn't using raw math or overly verbose english
descriptions around here, then it is probably matlab...
I guess a plain c programmer is probably a minority around here or
something, but at least matlab is understandable, if albeit weird...
misc:
the code looks like the algo is lossy, so maybe something for later.
now, I am guessing the filter I often use is probably not a wavelet, but it
does at least serve as altering the data such that it is often more
compressible:
void LBXGL_LightCmpr_FilterEncode(byte *buf, int xs, int ys)
{
int i, j, k, l;
for(i=0; i<ys; i++)
{
k=0;
for(j=0; j<xs; j++)
{
l=buf[(i*xs)+j];
buf[(i*xs)+j]=l-k;
k=l;
}
}
for(i=0; i<xs; i++)
{
k=0;
for(j=0; j<ys; j++)
{
l=buf[(j*xs)+i];
buf[(j*xs)+i]=l-k;
k=l;
}
}
}
Aleks Jakulin
> apparently if someone isn't using raw math or overly verbose english
> descriptions around here, then it is probably matlab...
It's Mathematica, not MatLab.
> the code looks like the algo is lossy, so maybe something for later.
Quantization is lossy, the DWT itself is not.
Aleks
cr88192
> cr88192 wrote:
>> apparently if someone isn't using raw math or overly verbose english
>> descriptions around here, then it is probably matlab...
>
> It's Mathematica, not MatLab.
>
(err, I am not really that sure of the difference, having little
fammiliarity with either, or are they related somehow?).
it is still rather odd from a syntax perspective (apparently multiplication
is an implicit operator and function calls are done with '[' and array
indexing with '[[', rather odd imo).
I can't tell enough from the examples to get a good idea of its semantics (a
rough guess would be that it is a hybrid of imperative and declarative
languages). I would guess that it is following assign-once binding rules.
how exactly binding to array slots would work though is unclear.
>> the code looks like the algo is lossy, so maybe something for later.
>
> Quantization is lossy, the DWT itself is not.
>
I don't trust float ops to be lossless, as even though it maybe
mathematically lossless and roundoff error is unlikely in many cases, it is
still a possibility.
as presented the filters are using float values, and not only that but
values likely to incure roundoff (not whole or fractional powers of 2).
I am skeptical of the idea of using this filter for any lossless transforms.
the filters I have been using have been using integer math, along treating
the byte range as circular (because, like angles, going the opposite
direction can often lead to shorter distances).
I hope I am not seeming like an overly argumentative troll or anything.
Brian Raiter
> mathematically lossless and roundoff error is unlikely in many
> cases, it is still a possibility.
You say "it is still a possibility" like you think it's something that
you can never fully be rid of.
If you don't understand floating-point arithmetic (and most
programmers don't), then you shouldn't trust your own code,
certainly. But someone who does take the time to learn how to do FP
math can produce perfectly predictable results.
b
cr88192
"Brian Raiter" <b...@drizzle.com> wrote in message
news:ck1j21$f5e$1...@drizzle.com...
the level where I can fully predict roundoff).
just when one is multiplying by factors like -0.052980118 and such, I feel
somewhat dubious about it.
one can be careful and avoid it, I know, but I doubt the examples I was
looking at were such code.
for lossless filters I would rather be sticking to a more predictable subset
of integer math (namely addition and subtraction, no multiplication or
division as then things like sign, overflow, and modulus come into play and
have to be worked with...).
so, imo, it depends on where it is "safe".