Two dimentional Multimedia preprocessor

[chornobyl]

I got an idea about preprocessing multimedia data this way:
-choose some pixel
-select second pixel with closest color
among his 4 (maybe more) neighbours
-write addictional data about the choise to 2bit stream

As a resul we'll have two streams:
slowly changing 8bit data which could de easy compressed
addictional 2bit data which is not so easy but still compressible

Also this may be applied to 1,2,3 and more dimentional data as well as bitdepth

I would be glad to hear your opinions about this
sad but my skills not allow me to test it myself

[Shelwien]

Switching algorithms like that introduce some redundancy,
so it won't be really efficient.
By redundancy I mean that it would be possible to decode
the same pixel from 4 different codes.
With "switching schemes" like that its always possible to
improve compression by transforming them into "mixing schemes"
(by removing the redundancy).
For that you have to subdivide the interval (arithmetic coder's interval)
into subintervals per each coding choice, proportional to the probability
of that choice, and then merge the subintervals corresponding to the
same pixel value.
But its up to you how to make it fast
It might be more practical to make a contextual predictor... actually
PNG does have something like that ("filters"), not very adaptive though.

[chornobyl]

>By redundancy I mean that it would be possible to decode the same pixel >from 4 different codes.
then how would decompressor decode it from 1 single code?

>With "switching schemes" like that its always possible to improve >compression by transforming them into "mixing schemes" (by removing the >redundancy).

remove redutancy from that "service stream" yep,
and how much mixing could squeze out of that 2bits

[Shelwien]

> then how would decompressor decode it from 1 single code?

I actually explained how.
By summing the probabilities of different codes corresponding
to the same decoded data.
Actually, algorithms like you explained are very simple cases
where redundancy really can be removed.
While there're still algorithms like LZ which have a similar
redundancy, but cannot be "fixed" that easily, as string
probabilities have to be merged there and its complex and slow.
Another, even more complicated case is spectral transformations
(like DCT in jpeg). DCT implementations are usually not bijective
even without quantization, so the only precise way to work with
them is imho by enumerating all the possible outputs from all the
possible spectral sets.

> remove redutancy from that "service stream" yep,

I meant removing whole "service stream".
But there's also another way.
You can mask the delta values for different bases
in such a way that there won't be alternate codes
for the same decoder output.
This is a PPM-like approach and its usually better
than keeping the redundancy, but worse than mixing.

> and how much mixing could squeze out of that 2bits

Up to 2 bits, I guess, but of course that depends on
data properties.
To get some estimation you can compare eg. Shkarin's
BMF with png, or PPMD vs LZMA on raw image data.

[chornobyl]

>DCT implementations are usually not bijective even without quantization
imho their precision is limited to ~12bit for 8 bit data, (ijg do so) if i remember right
What precision need to make it losless(bijective), i thought 16bit int is enough but now i'm doubt about that.

>To get some estimation you can compare eg. Shkarin's BMF with png, or >PPMD vs LZMA on raw image data.

tested on some drawing scans

  size  c.time 
 1953439   5 6-o2.7z
 1955696   4 6-o3.7z
 1960722   5 6-o4.7z
 1985729   7 6-o8.7z
 2218561 144 6-lz.7z
56431320     6.tif

 4639565   6 4-o3.7z
 4643738   8 4-o4.7z
 4676973   4 4-o2.7z
 4716066  15 4-o8.7z
 5328316 178 4-lz.7z
56433616     4.tif

[Shelwien]

> > DCT implementations are usually not bijective even
> > without quantization
>
> imho their precision is limited to ~12bit for 8 bit data,
> (ijg do so) if i remember right

There might be clipping. DCT is a sum of x[i]*cos()
so it looks like 15 bits (8+log2(8*+1) would be
a rough upper bound.

> What precision need to make it losless(bijective),

Lossless is one thing (x=iDCT(DCT(x)), but bijectivity
is necessary to avoid redundancy (one-to-one mapping).
If transformation is lossless, it doesn't mean that its not redundant.

> i thought 16bit int is enough but now i'm doubt about that.

Well, I have a lossless DCT-based audio codec which transforms
16-bit samples to 32-bit coefficients and back.
But its not only a matter of precision. Depending on implementation,
it might be lossy even with infinite precision, if rounding
is wrong.

> > To get some estimation you can compare eg. Shkarin's BMF
> > with png, or PPMD vs LZMA on raw image data.
>
> tested on some drawing scans

Yeah, something like that.

[chornobyl]

>but bijectivity is necessary to avoid redundancy (one-to-one mapping)
if i get right bijective compressor have unique output for every input
even more, if compressor:
for 2 intputs got 1 output=lossy
for 1 input got 2 outputs=redutant
for 2 input got 2 output=optimal(bijective)

is it true that bijective compressor could de/compress anything?

>Well, I have a lossless DCT-based audio codec which transforms 16-bit >samples to 32-bit coefficients and back.
i mean 16bit for 8bit input and of course 32bit for 16bit (as in your case)
And how good is it compress audio?

>But its not only a matter of precision. Depending on implementation, it >might be lossy even with infinite precision, if rounding is wrong.

well yes badly constructed program could destroy benefits of any algorithm

[Shelwien]

> > but bijectivity is necessary to avoid redundancy (one-to-one mapping)
>
> if i get right bijective compressor have unique output for every input

And vice versa.
http://en.wikipedia.org/wiki/Bijection

> > But its not only a matter of precision. Depending on
> > implementation, it might be lossy even with infinite
> > precision, if rounding is wrong.
>
> well yes every badly constructed program could destroy
> benefits of any algorithm

This is not the case. Algorithm description using traditional
infinite-precision maths is the cause of problems here.

[Shelwien]

> is it true that bijective compressor could de/compress anything?

It can transform anything.
But only data which fits the model is compressed.
Also its interesting how some unique tricks are required to stabilize
the output of bijective decompressor applied to random data
(basically, explicit randomization is required to avoid infinite
expansion of some common samples).

> > Well, I have a lossless DCT-based audio codec
> And how good is it compress audio?

Hardly compresses at all

[Mihai Cartoaje]

There might be clipping. DCT is a sum of x[i]*cos()
so it looks like 15 bits (8+log2(8*+1) would be
a rough upper bound.

11 bits (8 + log2(). I explained how to do a lossless DCT here:
http://groups.google.ca/group/comp.c...c0db6605a14b19

After that, ladder operators can be used. This uses the property that the matrix
[1 a]
[0 1]
is invertible over the integers.

[Shelwien]

Why, thanks.
I don't really have much experience with spectral transforms - had been
mostly using some libraries.
So, do you say that you know how to design a bijective DCT?
What about 1D DCT with N=1024? MDCT?
I see some clipping in your code (pixels?). How's that lossless?
Also its quite reasonable that the transform would be lossless
with integer coefficients, if you can get an integer inverse matrix.
But how far's that from real DCT then? More so with only 7bit coefficients...

[Mihai Cartoaje]

Why, thanks.
I don't really have much experience with spectral transforms - had been
mostly using some libraries.
So, do you say that you know how to design a bijective DCT?

Yes. Any orthonormal transformation can be made lossless because any orthonormal matrix can be composited from plane rotations. Any plane rotation can be composited from three matrices of the form,
[1 a]
[0 1]

Suppose this matrix is applied to a vector [x y]. In general, a will be real. This can be done as,
x += round(a * y)
The inverse of this is,
x -= round(a * y)

This is the technique I use in libima.

What about 1D DCT with N=1024? MDCT?

The 2D case is easier because much of the work can be done using additions and shifts (see my posts in the thread). In 1D you have a choice between doing lots of multiplications and have all the coefficients normalised. Or starting with the S transformation as a base, in which case the coefficients will have different normalisations. Duno.

I see some clipping in your code (pixels?). How's that lossless?

What are you refering to? I gave a proof of losslessness. Because the highest bit orders are not truncated by the shifts, the invertibility can be calculated algebraically for all but the lowest order of bits (hint: express each sample s as, s = s_e + s_o, with s_e a multiple of 2 and 0 <= s_o < 2). pixels/samples.

But how far's that from real DCT then? More so with only 7bit coefficients...

With real numbers, the technique I just described is exact. In the integer invertible case, I don't know. I never implemented a lossless DCT.

[Shelwien]

Well, I didn't miss anything then.
Of course, in theory DCT is lossless (and I have a lossless MDCT-based
audio codec which I made), but using real coefficients and rounding
requires a lot of attention to keep it lossless and avoid redundancy
at the same time, and it doesn't seem like there're sources of such
functions available.

Btw, there's a DCT-related problem which I'm especially interested in.
That is, probability mapping.
The idea is, basically, that while there're context correlations
(and quantization) in DCT space, that doesn't mean that all the
data dependencies can be tracked like that.
So, ideally, predictions of sequential model have to be mixed with
predictions of DCT model... which means that probability estimations
for DCT coefficients have to be somehow mapped back to the data
through the transform.
So, are there any ideas on which space to select for prediction
merging (original or spectral) and how to efficiently implement this
mapping? Taking into account that quantized spectral values map
to an intelval (or set?) of data values?

[Mihai Cartoaje]

I'll let Thomas Richter explain it:
http://groups.google.com/group/comp....e0d15ee28a8daa

And work out a small example. Suppose we want to have a lossless version of the 1D Haar transformation:
[sqrt(2)/2 sqrt(2)/2]
[-sqrt(2)/2 sqrt(2)/2]

This is a rotation:
[cos(theta) sin(theta)]
[-sin(theta) cos(theta)]

with theta = pi/4 radians. We express this as a composition of three matrices:
[1 a][1 0][1 a] = [cos(theta) sin(theta)]
[0 1][b 1][0 1] = [-sin(theta) cos(theta)]

multiplying, this gives,
a = (1 - cos(theta)) / sin(theta)
b = - sin(theta)

In this example,
a = sqrt(2) - 1
b = - sqrt(2)/2

This gives the algorithm,
x += round(a * y)
y += round(b * x)
x += round(a * y)

To get back our original samples, we invert every step in reverse order:
x -= round(a * y)
y -= round(b * x)
x -= round(a * y)

For a numerical example, we can pick [x y] = [100 0]. Doing the forward transformation:
x = x + round(a * 0) = 100 + 0 = 100
y = y + round(b * x) = 0 + round(-sqrt(2)/2 * 100) = -71
x = x + round(a * y) = 100 + round( (sqrt(2) - 1) * -71) = 100 - 29 = 71

So the transformed coefficients are [71 -71].

The inverse transformation is,
x = x - round(a * y) = 71 - round( (sqrt(2) - 1) * -71) = 71 + 29 = 100
y = y - round(b * x) = -71 - round(-sqrt(2)/2 * 100) = -71 + 71 = 0
x = x - round(a * y) = 100 - 0 = 100

And we get [100 0].

[Shelwien]

Thanks again
Anyway I don't understand how do I extend this to DCT of 1024 values
(with window function and reasonable speed),
but maybe your explanation would be of help if I give it some time.

[Shelwien]

btw, what would you recommend to use as a jpeg2000 decoder source?
most readable one, not speed-optimized or anything?
(For Ocarina Contest .

[Mihai Cartoaje]

To do a 1D 4 DCT, first you would have to do a 1D 4 Hadamard transformation using the 4-point transformation in the first thread. This would give basis functions like this:

----

-__-

--__

-_-_

Then to rotate the third and fourth coefficients by an angle,
cos(theta)/2 + sin(theta)/2 = cos(pi/ / sqrt(2)

Writing x = sin(theta), this can be reduced to a quadratic equation.

[Mihai Cartoaje]

I don't know how much work it would be to program a lossless 1024 DCT. You could design 8 and 16 DCTs and see if there is a pattern, and/or look if the fast Fourier transform can be used.

I only have common knowledge about Jpeg 2000 decoders.

[Shelwien]

> I don't know how much work it would be to program a lossless 1024 DCT.

Actually I use MDCT, which is slightly different.
And I don't really have any use for bijective DCT or MDCT currently -
its just that it'd be convenient to have one when i'd like to play with it
But I can send you that MDCT-based lossless codec source if you'd like
to check it out and maybe advice something.

> You could design 8 and 16 DCTs and see if there is a pattern,

Thing is, I don't have a clear view of this area.
I understand how's a working implementation works, but not quite
recognize the possibility to apply some relevant trick for optimization.
To learn that, once I tried to start from a dumb O(N^2) MDCT algorithm
and fully optimize it myself. And got something very ugly after
wasting quite a lot of time.

> and/or look if the fast Fourier transform can be used.

In fact, its already used. But there're lossy shifts which prevent
it from overflowing, and other lossy transformations in a few more
places.