Re: JPEG Compression Made Slightly-Less-Complicated (was Re: Reducing File Size with Photoshop)
From: William Robb [EMAIL PROTECTED]
From: Steve Jolly
OK. This is going to be bloody impossible to do entirely in text without
attachments, but I'll give it a try. :-)
I read it while sober.
Didn't make much sense.
I just read it while inebriated.
Didn't make any sense.
Can't I just think of it as a roll of pennies on a table top and get on
with life?
I think what he was trying to tell you is that jpeg does not look for
similar shapes but instead slices the picture in small 8x8 pixel chunks and
simplify these ('ah yes, this 8x8 block is all yellow, well, nearly enough
at least, I'll just jot down 'all yellow block here' and ignore the slight
color differences in this block. Next block, going from yellow to slightly
green, well, not exactly but no one will note the difference if I just make
it like it's going from yellow to slightly green, thats ok. Next one...')
The image format for your pennies are called fractal compressors. There are
some of these around, but they are so dead slow and uncommon no one really
uses them.
Was my translation ok for you?
Sam
Re: JPEG Compression Made Slightly-Less-Complicated (was Re: Reducing File Size with Photoshop)
William Robb wrote: I read it while sober. Didn't make much sense. I just read it while inebriated. Didn't make any sense. Can't I just think of it as a roll of pennies on a table top and get on with life? :-) Seriously though, thanks for the effort, sorry it was lost on my feeble brain. I got about half-way through and then realised hang on - they only teach this maths at university. I had a stab at explaining it without any formal maths, but I suspect that the task may be beyond me... I guess there's a reason I didn't go into any of the Science Communication fields... Still, thanks for reading it. :-) S
Re: JPEG Compression Made Slightly-Less-Complicated (was Re: Reducing File Size with Photoshop)
William Robb wrote: I just read it while inebriated. Me too. Nice feeling. I don'r give s**t. Life is cool.
RE: JPEG Compression Made Slightly-Less-Complicated (was Re: Reducing File Size with Photoshop)
Actually your explanation did make sense. Though I didn't grasp nearly all of it it helped to learn that they are processed in blocks. Helps me understand the behavior of both highly compressed and multiple generation jpeg files. Don't feel your efforts were totally wasted, I at least have a clue now. Which I didn't before. I knew HOW jpegs behaved, now I have at least a rough idea WHY they behave that way. Thanks! Don -Original Message- From: Steve Jolly [mailto:[EMAIL PROTECTED] Sent: Sunday, November 14, 2004 6:03 AM To: [EMAIL PROTECTED] Subject: Re: JPEG Compression Made Slightly-Less-Complicated (was Re: Reducing File Size with Photoshop) William Robb wrote: I read it while sober. Didn't make much sense. I just read it while inebriated. Didn't make any sense. Can't I just think of it as a roll of pennies on a table top and get on with life? :-) Seriously though, thanks for the effort, sorry it was lost on my feeble brain. I got about half-way through and then realised hang on - they only teach this maths at university. I had a stab at explaining it without any formal maths, but I suspect that the task may be beyond me... I guess there's a reason I didn't go into any of the Science Communication fields... Still, thanks for reading it. :-) S
Re: JPEG Compression Made Slightly-Less-Complicated (was Re: Reducing File Size with Photoshop)
- Original Message - From: Sam Jost Subject: Re: JPEG Compression Made Slightly-Less-Complicated (was Re: Reducing File Size with Photoshop) Was my translation ok for you? Works for me. Thanks William Robb
Re: JPEG Compression Made Slightly-Less-Complicated (was Re: Reducing File Size with Photoshop)
On Sun, 14 Nov 2004 09:12:50 +0100, Sam Jost wrote: The image format for your pennies are called fractal compressors. Other compression types that could be considered analogous to the pennies example would be Run-Length encoding and Quad-Tree encoding. In Run-Length Encoding (RLE), the pennies are analogous to individual pixels. One-dimensional RLE looks for sequences of pixels in a horizontal line that are the same color, and encodes them as a (color,count) pair. More complex RLE compressors will record either the colors of the pixels, or a (color,count) pair if the count is large enough that the pair is smaller than the data for the original run of pixels. In two-dimensional RLE, the algorithm encodes the first scan line the same way that one-dimensional RLE does. After the first scan line, it takes the differences in the colors of pixels between the current scan line and the previous scan line. It then encodes the runs in the difference. If two scan lines are the same, the difference between them is a single pair that covers the entire scan line, drastically reducing the stored size of the information. Faxes use encodings similar to this. Since a pixel in a fax image must be either black or white, fax compression doesn't need to store the colors directly; each line will start with a pixel of a certain color, and the colors will alternate from there. In fact, a compressed fax image is pretty much just a bunch of run lengths in scan line order. The algorithm assumes that the first run of pixels is white, for example. If it's really black, the algorithm inserts a white run of zero pixels into the output, so that every line starts with a pixel of the same color. Quad-Tree encoding does something similar, but different. In this encoding, the pennies are analogous to rectangles within the image. Quad-Tree encoding looks at the image data as a rectangle instead of a series of scan lines. It takes the entire image and splits it into four sections, down the middle vertically and across the middle horizontally. +---+---+ | | | | 1 | 2 | | | | +---+---+ | | | | 3 | 4 | | | | +---+---+ Conceptually, the beginning of the tree is a single color that represents the entire image. That color is the average color of each of the four sections. Each section is treated the same way, split into quarters and assigned the average color of its four sections, which are then split into four sections, ... until each section represents a pixel. The splitting can get tricky when the image dimensions aren't powers of two, or are different in one direction than the other, but it's not unmanageable. If the color of a section is close enough to the colors of the other three sections, or the average, or whatever, the values for some of the sections don't need to be saved. There are a ton of optimizations on both of these encodings that can have dramatic effects on which images compress well with each one. Fax images, for example, compress the run-length values on top of the run-length encoding. Quad-tree representations, on the other hand, can give really good progressive effects if the image is drawn as the image data is received. TTYL, DougF KG4LMZ
RE: JPEG Compression Made Slightly-Less-Complicated (was Re: Reducing File Size with Photoshop)
Thanks Steve! (Anybody seen my Exedrin?) :-( Don -Original Message- From: Steve Jolly [mailto:[EMAIL PROTECTED] Sent: Saturday, November 13, 2004 4:07 PM To: [EMAIL PROTECTED] Subject: JPEG Compression Made Slightly-Less-Complicated (was Re: Reducing File Size with Photoshop) William Robb wrote: This should be entertaining. Please, elucidate. OK. This is going to be bloody impossible to do entirely in text without attachments, but I'll give it a try. :-) The first thing that JPEG compression does is divide your image up into 8-pixel by 8-pixel blocks. These blocks are then compressed separately. This is the reason that highly-compressed JPEGs look blocky. :-) You're going to have to think like a mathematician now. What you think of as an 8-pixel by 8-pixel crop of your photo, a mathematician thinks of as a function. They would write something like B(x,y) - brightness as a function of position in two dimensions. Your 8x8 block contains the values of B(x,y) at 64 points in the image. The second thing that JPEG compression does is, for each block in the image, to take the data and runs it through a Discrete Cosine Tranformation, or DCT. This is just a mathematical equation - a black box that takes in a function B(x,y) and outputs another function A(u,v). Now, what are A, u and v, I hear you cry? That's where it starts getting tricky. A(u,v) is a new 8x8 block that contains *spatial frequencies* of the brightness information in the original 8x8 block. I reckon that needs a bit more explanation. Forget the two-dimensions aspect for a minute; think about a single 8x1 pixel crop of your image. If I draw a graph that shows their brightnesses, it might look something like this: B^ | || | | | || | | | | | | | | | | + x 1 2 3 4 5 6 7 8 pixel number Now, that looks a bit like a sine wave to me. If I draw a sine wave with a suitable frequency, I could get something that looks like this: B^ |* | * * * | * * |* * | * * +-*-- x 1 2 3 4 5 6 7 8 pixel number Now that's not quite the same shape as the original data, but it's a start. If we picked a second sine wave with a different frequency and added it to the first one, we could get closer. If we added a third one, we'd be closer still, and so on. As it happens, there's a quirk of maths that says that if we use eight very specific sine waves that are the same every time (but with different amplitudes and horizontal offsets) and add them, we can get *exactly* the same shape as we started out again. The formula that says what the amplitudes and offsets should be is the DCT. So, still thinking in *one* dimension, a DCT takes B(x) (The brightness of each of the eight positions represented by x) and outputs A(u), where A is the amplitude and horizontal offset of each of the eight sine waves represented by u. I hope it's not to hard to imagine that a *two* dimensional DCT takes B(x,y) and outputs A(u,v). Because if it is, I've lost you. :-) Right. So far, we haven't done any lossy compression. If we take A(u,v) and add all those sine waves together, we get B(x,y) back *exactly* as it was originally. The lossy bit happens next, in a process called quantisation. You see, the values of A aren't whole numbers (0,1,2,3 etc) like the original brightness values were; they're real numbers - they can take *any* value between zero and some maximum value that you don't need to know about. Because they can take an infinite number of values, they'd need an infinite amount of disk space to store them in, which isn't much good for a compression scheme. So, what we do is we take each of those numbers, and we work out what the closest we can get to it using a *fixed* number of bits is. And we don't use the same number of bits for each value of u and v, we take advantage of the fact that the human eye is less sensitive to certain spatial frequencies under certain circumstances to weight the process - frequencies that the eye sees better get encoded more accurately, and vice versa. You can vary the overall amount of compression by varying the total number of bits used to compress each block. And that's it! You can take all the bits that represent all the blocks, save them to a file and you have a new representation of the image; one that takes a bit of work to decode again, but that can take up much less storage space than the original while being perceptually identical. Well, I hope that made *some* kind of sense... you may have noticed that I only mentioned stuff relevant to greyscale images. Colour ones are more complicated (but use the same principles). S
Re: JPEG Compression Made Slightly-Less-Complicated (was Re: Reducing File Size with Photoshop)
On 13 Nov 2004 at 22:06, Steve Jolly wrote: Well, I hope that made *some* kind of sense... you may have noticed that I only mentioned stuff relevant to greyscale images. Colour ones are more complicated (but use the same principles). Well done. Rob Studdert HURSTVILLE AUSTRALIA Tel +61-2-9554-4110 UTC(GMT) +10 Hours [EMAIL PROTECTED] http://members.ozemail.com.au/~distudio/publications/ Pentax user since 1986, PDMLer since 1998
Re: JPEG Compression Made Slightly-Less-Complicated (was Re: Reducing File Size with Photoshop)
- Original Message - From: Steve Jolly Subject: JPEG Compression Made Slightly-Less-Complicated (was Re: Reducing File Size with Photoshop) OK. This is going to be bloody impossible to do entirely in text without attachments, but I'll give it a try. :-) I read it while sober. Didn't make much sense. I just read it while inebriated. Didn't make any sense. Can't I just think of it as a roll of pennies on a table top and get on with life? Seriously though, thanks for the effort, sorry it was lost on my feeble brain. William Robb
Re: JPEG Compression Made Slightly-Less-Complicated (was Re: Reducing File Size with Photoshop)
That was a dead-clear explanation, Steve. Thanks for taking the time to do this. I'm now much smarter than I was when I woke up this morning. :)
