DSPRelated.com
Forums

Image Compression Using Fourier Transforms

Started by Unknown April 23, 2009
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&#4294967295;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&#4294967295;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