Computer Science Educators Stack Exchange is a question and answer site for those involved in the field of teaching Computer Science. It only takes a minute to sign up.
Sign up to join this community
I will teach a lesson on image file formats in a computer science high school class.
Regarding JPEG, I will say that it achieves lossy compression and that it is well suited for photographs but it should not be used for geometric drawings where it can generate artifacts, showing some examples.
However, is it possible to explain why JPEG works this way, without venturing into domain change (space to frequency conversion), Discrete Cosine Transformation, and so on?
I would start with the lossless algorithms, run-length is a good place to start. Then you can go on to discuss human perception, I like to use the example of hiding in plain site.
Ask which is harder to spot someone standing by a wall, or someone standing in the middle of a field. Use this as the basis for discussing lossy compression.
Explore images that look the same, but are different (when examined). One that I remember is an image white background, with a series of vertical thick black bars. Then to the right of each bar is a thin line with a linear gradient from dark to light. All black bars are identical, all thin lines are identical, however the lines get closer to the bars as you move to the right. (so multiple copies of the bar and line, but each copy to the right has the bar and line closer). This is perceived as the thin lines getting shorter to the right. An example of the hiding in plain sight illusion discussed above.
This relates to e-safety, digital literacy, ethics, etc.
As well as the ones you said: Cartoon (traditional, such as Simpsons), line drawings. There are certain uses of photograph that should not be lossy encoded. These include medical X-ray (especially of fractures), and of nuclear power rods or aircraft, to check for build quality (fractures). I mention these 3 as I know this has been done, at great cost (£Millions), and safety risk.
Let me point out that JPEG is not a file format but a set of algorithms, some lossy some lossless. However just after release someone made a library that used some of the algorithms (Discrete cosine transform, hoffman encoding, etc), to make a lossy compression algorithm, this became a de-facto standard).
I would start with the lossless algorithms seconded. JPEG is essentially quantization + sampling + classical lossless techniques + transform
$\endgroup$
Jan 28 '18 at 19:59
I mention these 3 as I know this has been done do you happen to have a reference for this? I bet it'd be an entertaining read.
$\endgroup$
Jan 28 '18 at 19:59
Let me start with a quick overview of how JPEG (as usually applied) compresses color images.
Colorspace and downscaling. Raw images are usually encoded in the RGB color space. The human eye is more sensitive to the luminosity of images than to their chromatic aspects — as an extreme example, we can understand black and white photos quite well. Therefore JPEG images store more information about luminosity and less about colors. This is implemented in two steps. First, the RGB color space is transformed into a different color space (in a linear fashion), YCbCr (similar to the TV color space YPbPr) in which Y is luminosity and Cb/Cr encode how much the pixels are blue rather than purple (Cb) and red rather than green (Cr). The Cb and Cr planes are then downscaled or subsampled, that is, their resolution is reduced, usually by a factor of 2 in the horizontal direction (the eye is more sensitive to the vertical direction). From this point on, the three planes are compressed individually.
Division into blocks. Each of the color planes is now divided into 8×8 non-overlapping blocks (in contrast, in MP3 the sections are partially overlapping), which will be compressed more-or-less individually. This division is the reason for the so-called blocking effects, since the superimposed grid cuts through features of the image.
Spectral compression by quantization. The basic insight behind JPEG is that nature is noisy, and this noise is filtered by the human visual system. It follows that we can throw away the noise without substantially affecting the way the image looks. It remains to decompose the image into its "substantial" and "noisy" components, and this is accomplished by a 2D Fourier transform. Recall we are trying to compress 8×8 blocks. The most important feature of a block is the average value of its 64 pixels, known as the DC component (or, zeroth Fourier coefficient); the DC components of all blocks are just a result of scaling down the original image by 8 in both dimensions. The importance of the other components, known as AC components, depends on their frequency — the higher frequencies correspond to noise, whereas the lower frequencies are more informative. However there is no clear cut distinction between features and noise. For this reason, we need to retain all components, albeit with different accuracy. Accordingly, we quantize the different components to various degrees, depending on the frequency: components corresponding to higher frequencies are quanrtized more. The exact quantization matrix depends on the disparity between the horizontal and vertical dimensions, and has been determined experimentally. (It also depends on the quality parameter of the compressor.)
Entropy encoding. It remains to encode the quantized components into bits, which is done using Huffman coding, a standard encoding scheme. Since the DC components of all blocks are a downscaled version of the entire image, we expect them to vary continuously. Therefore instead of encoding their actual values, we encode them differentially, that is, we encode the difference from the preceding DC value. The AC components don't have this behavior, and so are encoded absolutely.
Why does compressing geometric drawings result in artifacts? Geometric drawings are very different from natural images. They don't vary continuously. Spectral compression results in "smearing" effects, since we are only retaining the lower frequencies. The best illustration of this is the Gibbs phenomenon, which is the continuous analog of the same issue. When trying to represent a step function using Fourier series, we need to use all frequencies. If we suppress the high frequencies, we get something really different. Lines in a geometric drawing are the discrete analog of step functions.
Another problem is the blocking effects. Imagine a diagonal line. JPEG partitions the space around these lines into 8×8 blocks, which are compressed individually. No attempt is made for the resulting lines to match exactly, and indeed they probably don't. This is very apparent because lines are very clean and exact, something that cannot be said about real-life images.
Using software like Matlab, you can show the effect of quantization on a real-world image, and then compare it to the effect of quantization on clip art. You can vary the quantization steps to show the effect of downplaying the higher frequencies (and also what happens when trying to suppress the lower frequencies).
You can demonstrate the effect of blocking by varying the angle of a line which is compressed block-by-block, or fixing a line and varying the block size. You can use a low quality setting to emphasize the effect, and include the block boundaries to highlight its origins.
However, is it possible to explain why JPEG works this way, without venturing into domain change, DCT and so on?
Disclaimer 1: I'm not sure if this is more of a comment or an answer and
Disclaimer 2: this is not really my field, but
I'd be inclined to answer: no.
Firstly, I don't think it's necessary. I think the intuition behind the concept of transform (at least as in Fourier or DCT) is within the grasp of most high school kids that know some trigonometry: you can probably get away with drawing a simple function, decomposing it into sine waves and writing down their phase and amplitude while waving your hands a lot.
You'd then proceed to reconstruct the original function by means of summation and persuade the students that the representation in terms of 4/5 phase/amplitude coefficients is "more compact" (finite, even) than its representation in terms of infinite pairs in $R \times R$.
I'd argue it's also not possible because the DCT is also very much one of - if not the - working principles behind JPEG, differentiating it from classical lossy compression techniques.
Operation in the frequency domain is ultimately the reason why *PEG performs subjectively better than, say, resampling and requantizing at 240x180@16 colors, which is essentially a much naiver lossy compression method that operates purely in the space/time domain.
Note, finally, how the excellent Smith handbook - along with probably several other resources - explicitly calls JPEG “transform compression”.
