Image Compression Using Fourier Transforms

On Apr 23, 12:21�pm, pierrefrancescos...@gmail.com wrote:
> I was wondering if there was a relatively straightforward algorithm
> for compressing image using Fourier transforms. I was thinking that I
> could transform an image into frequency space and then perform a

> lowpass filter on the image to set all the lesser frequencies to zero,

you mean this

" explicitly making low amp values to zero ";  then that's correct.


> then perform a run-length-encoding on the data to pack the zeroes.
> However, I have been running into trouble with this method,

since the
> decoded image largely has zero values (i.e. it is mostly black). Am I
> completely off target or what?

while decoding,  the DC co-eff will handle this job...
I think, you don't need to worry about that.

At the run-time the encoded zero's in RLE will be given
life with the help of main DC co-eff
which resides at the starting of each such macro block.

hope this is helpful to you.

best wishes
   nimo
__________

Bernard Shaw shaking hands with a lady: " I'm very glad to see you ".

Lady:"Well,I'm not".

Shaw: "Why don't you pretend as I do?"

I designed a lossless YIQ color transform that requires 2 or 5
multiplications per pixel. It is like this:

R -= B
B += R >> 1
B -= G
G += B >> 1
G += round(- (0.5 - Kb - Kr) * B + (Kr - Kb) * R / 2.0)
B -= round(((1 - cos(45 - theta)) / sin(45 - theta)) * R)
R += round(sin(45 - theta) * B)
B -= round((((1 - cos(45 - theta)) / sin(45 - theta)) - sin(45 -
theta) * cos(45 - theta) / (4 - sin(45 - theta) * sin(45 - theta))) *
R)
Y = G
I = R
Q = B

Patent pending. I posted a comparison between YIQ and YCbCr at,
http://groups.google.com/group/media-player/browse_thread/thread/329f6ba471f802bd

I also added a new transform to Libima. It can be done on a sub-region
of the image so it would be good for video. A video compressor could
separately transform the sub-region which is independently coded and
the sub-region which is motion compensated. It is described on my
website:
http://www.geocities.com/repstsb/index.html

<sarcasm> Hoorah, another algebraic formula protected from general
use. </sarcasm> But seriously, why share something the community can't
ultimately use without fear of litigation?

There is a simpler algorithm:

R -= B
B += R >> 1
B -= G
G += round((Kb + Kr) * B + (Kr - Kb) * R / 2.0)
B -= round(((1 - cos(45 - theta)) / sin(45 - theta)) * R)
R += round(sin(45 - theta) * B)
B -= round((((1 - cos(45 - theta)) / sin(45 - theta)) - sin(45 -
theta) * cos(45 - theta) / (4 - sin(45 - theta) * sin(45 - theta))) *
R)
Y = G
I = R
Q = B

It is possible to do any lossless linear color transform of the kind
YC1C2 using 5 multiplications. The steps are,

1. Transform the red and blue channels so that they are in the plane R
+ G + B = 0

2. Add multiples of the intermediate chroma channels to the green
channel to obtain the luma channel.

3. Find constants a, b, c such that the following algorithm transforms
the intermediate chroma channels into the desired chroma channels:

B += round(a * R)
R += round(b * B)
B += round(c * R)

The constants can be found through linear algebra representing,

      [1 0 0 ]
A = [0 1 0 ]
      [0 a 1 ]

And representing the first 2 steps as the matrix T, and the desired
transform as the matrix M, and solving the equation,

C B A T = M

For example, the JPEG YCbCr transform is,

[0.299, 0.587, 0.114]
[0.5, -0.418688, -0.081312]
[-0.168736, -0.331264, 0.5]]

To make the determinant 1, we can multiply the chroma channels by the
same multiple:

[.299, .587, .114]
[1.029, -.861, -.167]
[-.347, -.681, 1.029]

So the algorithm is,

R -= G
B -= G
G += round(Kb * B + Kr * R)
B += round(-0.171 * R)
R += round(-0.167 * B)
B += round(-0.171 * R)

Mihai Cartoaje wrote:
> It is possible to do any lossless linear color transform of the kind
> YC1C2 using 5 multiplications. 

And your point is...? A somewhat more useful observation would be: You 
could always implement it by lifting, thus making it lossless up to a 
scaling you can compensate for later on, for example. This is equally
trivial. (-:

So long,
	Thomas

People can apply for a license by emailing me.

If I obtain a patent and a company uses it, it would allow me to write
useful software so the community wins.

Prior art is 7 multiplications per pixel. Are there examples of prior
art using 5 multiplications per pixel?

If theta is different from 45 degrees, there is a simpler algorithm:

R -= B
B -= G
G += round((Kb + Kr) * B + Kr * R)
B += round((0.5 - (1 - cos(45 - theta)) / sin(45 - theta)) * R)
R += round(sin(45 - theta) * B)
B -= round((((1 - cos(45 - theta)) / sin(45 - theta)) - sin(45 -
theta) * cos(45 - theta) / (4 - sin(45 - theta) * sin(45 - theta))) *
R)
Y = G
I = R
Q = B

Mihai Cartoaje wrote:
> It is possible to do any lossless linear color transform of the kind
> YC1C2 using 5 multiplications
...
> For example, the JPEG YCbCr transform is,
> 
> [0.299, 0.587, 0.114]
> [0.5, -0.418688, -0.081312]
> [-0.168736, -0.331264, 0.5]]
> 
> To make the determinant 1, we can multiply the chroma channels by the
> same multiple:
> 
> [.299, .587, .114]
> [1.029, -.861, -.167]
> [-.347, -.681, 1.029]
> 
> So the algorithm is,
> 
> R -= G
> B -= G
> G += round(Kb * B + Kr * R)
> B += round(-0.171 * R)
> R += round(-0.167 * B)
> B += round(-0.171 * R)

But in this case G is not:  0.299 * R + 0.587 *G + 0.114 * B
because the G multiplier above is 1.
So in the end you need more multiplications?

And if you agree with me that YUV and YCbCr only differs in the
scaling of the color components (UV versus CbCr), and YUV can
be made like:
Y = 0.299 * R + 0.587 * G + 0.114 * B
U = (B - Y) * 0.493
V = (R - Y) * 0.877

than YCbCr could be made this way, only by changing the factors
for U and V to become Cb and Cr, with 5 multiplications?

Jens