Re: pixel prediction for lossless image compression


"Phil Carmody" <thefatphil_demunged@xxxxxxxxxxx> wrote in message
news:87zmdi7k3h.fsf@xxxxxxxxxxxxxxxxxxxxxxx
"cr88192" <cr88192@xxxxxxxxxxxxxxxxxx> writes:
"Michael Schöberl" <MSchoeberl@xxxxxxxxxxxx> wrote in message
...
I used an image of mine, an evolver,

evolver?


http://en.wikipedia.org/wiki/Genetic_algorithm


prediction for
1 2 3 4
5 6 7 8
9 10 x

one generated result was this (more or less):
0.000 0.001 -0.019 -0.001
0.001 -0.738 0.762 0.001
-0.092 1.089

at least it seems, for final output entropy is a little lower than for a
more simplistic predictor (v7+v10-v6), although it could just be the case
for this image.

I don't suppose you could repeat the test, but with the identical image
either flipped in the x=y axis, or rotated by 90 degrees. I'm surious
about the non-symmetry between the two dimensions.


the non-symetry is apparent, however, it may be a result of the "shape" of
the data being considered which causes this asymetry to occure.


image rotated by 90 degrees, I get this (first run):
-0.000 0.002 -0.001 -0.001
-0.002 -1.000 0.999 -0.001
-0.002 0.999

which is more or less a plain ol' linear predictor...


second run:
-0.000 0.001 -0.037 -0.000
0.000 -0.697 0.732 -0.000
-0.099 1.103


this looks similar to the original filter.
I suspect the asymetry is likely a result of the irregular shape of the
predictor inputs, and not necissarily a part of the image.


Is it also possible to repeat the tests with v1, v2, v4, v5, v8 fixed to
zero? And also with v9 fixed to zero.


concievably, there is no reason why I couldn't, of course, the results would
be different.


I wonder if the variation around the mean optimum might be something
that could be adaptively followed while scanning the image.

So you start with the predictor
-0.74 0.76
-0.09 1.07 ?
but you use feedback from the error to adjust that with each step.
Perhaps also memorising the previous line's adapted settings, so
that you don't have to re-learn at every scan line. Quite what
feedback mechanism would be best, I don't know, perhaps a discrete
choice of "neighbouring" predictors which deviate by epsilon in each
term.


note, the algo is not "adaptive" in a conventional sense (it does not use
statistical feedback or predictor error as a means to adjust the filters,
nor is their any real "adjustment" logic or similar).

technically, it is a lot closer to being a plain-ol' genetic algorithm. an
initial set of filters is supplied as part of the input population, mostly
linear filters, eg:

-1 1
1 x

-1
-1 1
-1 1 x

....

note that these are not strictly necessary, but providing a few initially
"good" inputs allows finding much better results much quicker (vs with
initially random values, where it takes a lot longer for anything
"consistent" to start to form...).


along with a lot of "hybrids" they are combined with random variations
added, and a number of "generations" are performed, with the most productive
ones kept, hybridized, and mutated, to form a larger set of filters, and
this process repeats some-odd number of times.

ok, the total entropy for each test is used here. filters with a higher
entropy are generally viewed as less efficient than ones with a lower
entropy, and there is little regularity in the pixels the filter is expected
to predict (each pixel is chosen via a prng, and a certain number of pixels
are used per-test).


the example given was the predictor that, in general, performed best, and
eventually won out.


many of the other well-performing predictors were similar (however, because
of the heavy reliance on random-number generation, results aren't all that
reliably repeatable). this algo depends heavily on an effective prng. in my
case, the prng algo is fairly generic, but I seed the prng by using the
output from clock and loops as a means of computing a kind of hash (comes
out seeming random enough...).



the total entopy was also lower than with the input predictors.
I don't have proof this wasn't just formed as a consequence of the
particular images I was using, but I can understand the filter (including
its asymetry) so, I suspect the result is valid.


the same basic algo also got similarly mundane results when reasoning about
lz77 compression, and may have other uses. albeit, more conventional methods
are computationally cheaper, this has the advantage of finding potentially
interesting solutions (wheras, with more conventional algos, one has a
fairly good idea what the output is going to be...).


But how much would that really save? Maybe nothing?


dunno.

I have a new toy, which I am playing with some...


Phil
--
"Home taping is killing big business profits. We left this side blank
so you can help." -- Dead Kennedys, written upon the B-side of tapes of
/In God We Trust, Inc./.


.