Image Compression Using Fourier Transforms
pierrefra...@gmail.com
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,
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?
Thomas Richter
> I was wondering if there was a relatively straightforward algorithm
> for compressing image using Fourier transforms.
Yes. It is called JPEG. Except that it uses DCT, not fourier, which has
the advantage that the resulting values are real (not complex).
> 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,
What is a "lesser" frequency? You usually want to quantize the data
(represent it with less precision).
> then perform a run-length-encoding on the data to pack the zeroes.
That's also called JPEG, almost exactly, including the runlength part.
Here, for traditional reasons, the DCT is windowed to 8x8 blocks, but
surely larger block sizes are possible (though then not covered by the
standard).
> 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?
No, but you seem to have a bug somewhere.
So long,
Thomas
pierrefra...@gmail.com
> pierrefrancescos...@gmail.com wrote:
> > I was wondering if there was a relatively straightforward algorithm
> > for compressing image using Fourier transforms.
>
> Yes. It is called JPEG. Except that it uses DCT, not fourier, which has
> the advantage that the resulting values are real (not complex).
Thanks for your quick reply. I posted the same question on
scienceforums.com and physicsforums.com, and I have not received a
single reply yet.
I have looked at the JPEG compression methods, and I was hoping for
something a little bit easier to implement. JPEG involves converting
to YCrCb colors, the DCT transform, quantizing the results and doing
entropy coding. Since I am doing this for a course in Computational
Physics, I was looking for more straightforward methods.
> > 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,
>
> What is a "lesser" frequency? You usually want to quantize the data
> (represent it with less precision).
I meant a frequency with a lower amplitude value (i.e. when you have
the matrix representing the 2d transformed image, I am talking about
the values that are less than the others). Is there anyway to find a
good quantization table for grayscale or RGB images (or generate it)?
Since I am using Matlab, I was also hoping for a method that did not
involve bit size. The method does not have to produce 'good'
compression; I just need something that will produce an output matrix
with fewer elements than an input matrix.
glen herrmannsfeldt
Much research has gone into that problem, which you should
probably look at before trying to reinvent it.
JPEG uses 8 by 8 blocks, and DCT. For a blocked transform,
DCT is a much better choice, as the boundary condition makes
boundaries much less visible than DFT (FFT).
The blocked transform has the advantage that it works well
with images that have large areas with only low frequencies
(no sharp edges), but other areas that do have sharp edges.
In other words, put the bits where they do the most good.
(That won't help for resolution test patterns, but works
well for ordinary people pictures.)
-- glen
Rune Allnor
> On Apr 23, 3:24 pm, Thomas Richter <t...@math.tu-berlin.de> wrote:
>
> > pierrefrancescos...@gmail.com wrote:
> > > I was wondering if there was a relatively straightforward algorithm
> > > for compressing image using Fourier transforms.
>
> > Yes. It is called JPEG. Except that it uses DCT, not fourier, which has
> > the advantage that the resulting values are real (not complex).
>
> Thanks for your quick reply. I posted the same question on
> scienceforums.com and physicsforums.com, and I have not received a
> single reply yet.
>
> I have looked at the JPEG compression methods, and I was hoping for
> something a little bit easier to implement. JPEG involves converting
> to YCrCb colors, the DCT transform, quantizing the results and doing
> entropy coding. Since I am doing this for a course in Computational
> Physics, I was looking for more straightforward methods.
Physics and engineering share the somewhat depressing
charactersitics that the *ideas* might be very simple,
but *implementing* them might not.
As others already indicated, you think along the same
lines as the philosophy behind one of the more popular
image formats, so you have done something right.
However, as you also discovered, there are many practical
and political details to consider:
1) What color format to use in the encoding?
- What color formats exist?
- What color formats are in ude?
- How to convert back and forth between them?
- Are there patents or other legal issues involved?
2) What transform to use?
- What transforms exist? (DFT, DCT, SVD, wavelets,...)
- What types of results does each produce?
(copmplex/real, energy distributions,
numbers of basis vectors)
- What are the computational costs associated with
each transform? (forward/backward, complexity,
memory requirements, numerical sensitivity)
3) What number format to use?
- What are the requirements to hardware? (General
purpose/specialized)
and so on. These are the types of questions people who
design products and services have to consider. These
things take far more time than the actual technical
questions and details.
As for your project, just make some ad-hoc decisions
to get started. Something along the lines of
- Stick with B&W images, no colors
- Use the DCT tranbsform (it's a popular tool in
image processing, so it's worth learning)
- Use 8-bit unsigned integers for color encoding
- Use e.g. Huffman codes, since these are easy
to implement.
With a skeleton plan as the above, you get started.
Once you get to work, you obtain experience and might
see specific reasons why some of the items in your
plan are bad choises, and thus you have an informed
reasoon to change your plan.
In summary:
- You think along the right lines
- Ideas are simple, implementations are not
- Make ad-hoc decisions and set up a
skeleton plan of *simple* steps
- Get to work and gain hands-on experience
- Revise your plan as you gain experience
and can make informed decisions
Rune
glen herrmannsfeldt
> On 23 Apr, 21:45, pierrefrancescos...@gmail.com wrote:
>> > pierrefrancescos...@gmail.com wrote:
>> > > I was wondering if there was a relatively straightforward algorithm
>> > > for compressing image using Fourier transforms.
(snip)
>> I have looked at the JPEG compression methods, and I was hoping for
>> something a little bit easier to implement. JPEG involves converting
>> to YCrCb colors, the DCT transform, quantizing the results and doing
>> entropy coding. Since I am doing this for a course in Computational
>> Physics, I was looking for more straightforward methods.
Most likely YCrCb results in better compression, but if you
applied DCT separately to R, G, and B that should also work.
> Physics and engineering share the somewhat depressing
> charactersitics that the *ideas* might be very simple,
> but *implementing* them might not.
There should be enough left for some experiments, to show
how well, or not, different parameters affect the compression.
Compressing RGB is likely about 1/3 less compression, but
might simplify the algorithm, especially in hardware (fpga).
You might try different sizes than 8 by 8 for the DCT.
> As others already indicated, you think along the same
> lines as the philosophy behind one of the more popular
> image formats, so you have done something right.
> However, as you also discovered, there are many practical
> and political details to consider:
> 1) What color format to use in the encoding?
> - What color formats exist?
> - What color formats are in ude?
> - How to convert back and forth between them?
> - Are there patents or other legal issues involved?
> 2) What transform to use?
> - What transforms exist? (DFT, DCT, SVD, wavelets,...)
The periodic boundary conditions for DFT are not good
for a block algorithm. The others might work, though.
> - What types of results does each produce?
> (copmplex/real, energy distributions,
> numbers of basis vectors)
> - What are the computational costs associated with
> each transform? (forward/backward, complexity,
> memory requirements, numerical sensitivity)
This is certainly important. JPEG most likely considered
the computational resources available at the time, especially
in portable cameras. Those likely have changed over the years.
> 3) What number format to use?
> - What are the requirements to hardware? (General
> purpose/specialized)
> and so on. These are the types of questions people who
> design products and services have to consider. These
> things take far more time than the actual technical
> questions and details.
> As for your project, just make some ad-hoc decisions
> to get started. Something along the lines of
> - Stick with B&W images, no colors
RGB isn't much harder.
> - Use the DCT tranbsform (it's a popular tool in
> image processing, so it's worth learning)
> - Use 8-bit unsigned integers for color encoding
> - Use e.g. Huffman codes, since these are easy
> to implement.
> With a skeleton plan as the above, you get started.
(snip)
-- glen
Fred Marshall
http://en.wikipedia.org/wiki/YCbCr
"RGB signals are not efficient as a representation for storage and
transmission, since they have a lot of mutual redundancy.
YCbCr and Y'CbCr are a practical approximation to color processing and
perceptual uniformity, where the Primary colours corresponding roughly to
Red, Green and Blue are processed into perceptually meaningful information.
By doing this, subsequent image/video processing, transmission and storage
can do operations and introduce errors in perceptually meaningful ways.
Y'CbCr is used to separate out a luma signal (Y') that can be stored with
high resolution or transmitted at high bandwidth, and two chroma components
(Cb and Cr) that can be bandwidth-reduced, subsampled, compressed, or
otherwise treated separately for improved system efficiency.
One practical example would be decreasing the bandwidth or resolution
allocated to "color" compared to "black and white", since humans are more
sensitive to the black-and-white information (see image example to the
right)."
As I recall we used to carry Y along at a higher sample rate than Cr or Cb -
like a factor of 2. So, you might have samples like this:
Y Y Y Y
Cr Cb Cr Cb ... etc.
and you would run the Cr Cb "channel" through something like a polyphase
filter to get Cr and Cb individually.
... something like that....
Fred
glen herrmannsfeldt
> transmission, since they have a lot of mutual redundancy.
> YCbCr and Y'CbCr are a practical approximation to color processing and
> perceptual uniformity, where the Primary colours corresponding roughly to
> Red, Green and Blue are processed into perceptually meaningful information.
> By doing this, subsequent image/video processing, transmission and storage
> can do operations and introduce errors in perceptually meaningful ways.
> Y'CbCr is used to separate out a luma signal (Y') that can be stored with
> high resolution or transmitted at high bandwidth, and two chroma components
> (Cb and Cr) that can be bandwidth-reduced, subsampled, compressed, or
> otherwise treated separately for improved system efficiency.
When the analog NTSC system was developed, they did studies
on the visual resolution of different colors. The NTSC standard
supplies two color subcarriers such that more bandwidth is
supplied on the axis where the human visual system detects it.
That axis is not along the red, green, or blue direction, but
somewhere in between. The reference burst was designed such
that it is easy to decode along the red and blue axes,
but for full chroma resolution they should be decoded along
a different axis and then matrixed back to RGB. Only relatively
recently, just about at the time that digital TV was being
developed, did they market enhanced definition TVs that decoded
this extra chroma resolution.
http://en.wikipedia.org/wiki/YIQ
-- glen
aruzinsky
> ...
> I have looked at the JPEG compression methods, and I was hoping for
> something a little bit easier to implement. JPEG involves converting
> to YCrCb colors, the DCT transform, quantizing the results and doing
> entropy coding.
Here's an RGB JPEG:
http://www.general-cathexis.com/images/TufuseCircuitBoardSmall.jpg
Your browser can read it.
Jacko
The RLE is useually truncated to a few diagonal ordered terms, and
does not bother with the HF DCT terms. You may find a BWT transform
useful before your RLE. Arithmetic encoding is better if there is a
extreamly large number of zeros. You may also find weighting each
number in the DCT helps with the compression.
Other things you may find useful:
1. Do not pay that much attention to the phase of the high
frequencies, as actual textures may not need to be fully pixel
aligned.
2. 1 bit 4 times oversample the image in both x and y directions, to
have same 16 bit resolution per pixel, while reducing the arithmetic
to multiply by 0 or 1. with a 32*32 DCT Use the noise shaping to
reduce LF errors.
3. Use a nested average DCT so that large black areas are coded at a
lower resolution.
4. Use a Walsh transform.
cheers jacko
Nimo
> 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?"
Mihai Cartoaje
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
moosh
use. </sarcasm> But seriously, why share something the community can't
ultimately use without fear of litigation?
Mihai Cartoaje
R -= B
B += R >> 1
B -= G
G += round((Kb + Kr) * B + (Kr - Kb) * R / 2.0)
Mihai Cartoaje
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)
Thomas Richter
> 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
Mihai Cartoaje
If I obtain a patent and a company uses it, it would allow me to write
useful software so the community wins.
Mihai Cartoaje
art using 5 multiplications per pixel?
Mihai Cartoaje
R -= B
B -= G
G += round((Kb + Kr) * B + Kr * R)
B += round((0.5 - (1 - cos(45 - theta)) / sin(45 - theta)) * R)
Jens Dierks
> 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
Jens Dierks
...
> because the G multiplier above is 1.
> So in the end you need more multiplications?
Sorry, R and B are subtracted by a amount of G bevor, so G could be
correct calculated!
Mihai Cartoaje
> 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?
That is not lossless.
Jens Dierks
What do you mean with losless?
You can add values (beside the right scaling) to the color components
to fit in every window you decide.
You get every time losses in case of rounding errors.
Btw the inverse transform from YUV to RGB needs only 4
multiplications.
But i dont wanted to degrade your code, because a general way
to do a 3x3 matrix transform with only 5 multiplications sounds very
good to me.
Jens
Mihai Cartoaje
> I posted a comparison between YIQ and YCbCr at,
I corrected an error and redid the comparison:
http://groups.google.com/group/media-player/browse_thread/thread/4e0d4c83bba85be8
Mihai Cartoaje
> You can add values (beside the right scaling) to the color components
> to fit in every window you decide.
> You get every time losses in case of rounding errors.
It is lossless because the rounding errors are reversed at
reconstruction. This is the reconstruction algorithm for the above
color transform that is similar to JPEG YCbCr:
B -= round(-0.171 * R)
R -= round(-0.167 * B)
B -= round(-0.171 * R)
G -= round(Kb * B + Kr * R)
B += G
R += G