Image Compression Using Fourier Transforms

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,
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?

pierrefrancescoster@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).

> 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

On Apr 23, 3:24&#4294967295;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.

> > 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.

> > 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,
> &#4294967295; &#4294967295; &#4294967295; &#4294967295; Thomas

In comp.dsp pierrefrancescoster@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,
> 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?

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

On 23 Apr, 21:45, pierrefrancescos...@gmail.com wrote:
> On Apr 23, 3:24&#4294967295;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

In comp.dsp Rune Allnor <allnor@tele.ntnu.no> wrote:
> On 23 Apr, 21:45, pierrefrancescos...@gmail.com wrote:
(snip)

>> > 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

Wikipedia does a pretty good job of explaining "why YCrCb?":
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

In comp.dsp Fred Marshall <fmarshallx@remove_the_x.acm.org> wrote:
> 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

On Apr 23, 1:45�pm, pierrefrancescos...@gmail.com wrote:
> ...
> 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.

On Apr 23, 8: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,
> 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?

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