C21 · Store and compare
Compression, rank and information
A representation can store coefficients instead of every pixel. Distinguish coefficient count, distortion and actual encoded file size.
Theory
Keep every pixel first: RLE and PNG
Lossless compression changes how numbers are written while allowing exact recovery. A long run of equal values can be recorded as value and count: RLE. It works well for runs but can enlarge a varied image. PNG takes a different path: predict each value from known neighbors, then compress the residual sequence.
Lossless: a different way to write the same numbers
Start with a small greyscale image: 8 × 4 pixels. Each pixel is one brightness byte: 0 is black and 255 is white. Lossless means every decoded number must match, not merely look similar.
RLE: how many times does a value repeat?
Read the first row from left to right. Replace each run with a “count, value” pair. Each number occupies one byte in this example. Select a pair to see its pixels.
8 bytes → 4 bytes of pairs → the same 8 bytes. RLE helps here. Alternating values make the encoding larger instead.
PNG: predict a neighbour, store the difference
PNG does not use this RLE encoding. It first transforms scanline bytes reversibly, then compresses them with DEFLATE. In our 8-bit greyscale example one byte is one pixel; RGB applies the same operation to channel bytes.
Click the image or use arrow keys. The solid frame selects a byte; dashed frames mark the neighbours used.
Sub predicts the original byte on the left. A missing neighbour at the left edge is 0.
48 − 48 = 0
Store the remainder modulo 256: 0
(0 + 48) mod 256 = 48
A different predictor changes the encoding, never the decoded pixels.
Prediction alone does not compress: 32 bytes become 36 with four filter labels. Savings come next if the transformed data contains more repeated sequences. A small difference of −8 is stored as byte 248; modulo-256 addition restores the original value.
DEFLATE: repeat a sequence, not just one colour
Read the 36 bytes in order. LZ77 emits a literal byte or “go back d bytes and copy n bytes”. Huffman coding writes those commands as bits. Select a command to inspect its actual bits in this PNG stream.
Underlined bytes in the rows above are being written. A dashed top edge marks existing bytes where the copy begins. If length exceeds distance, newly copied bytes become the source for the next repetition.
The first byte, 1, identifies the Sub filter. It is stored as a literal.
00110001Bits are shown in transmission order. This example uses a fixed Huffman table rather than a frequency-adapted one. A production PNG encoder can choose filters per row and dynamic tables.
What makes up the actual file size?
- Signature
- 8 B
- IHDR
- 25 B
- IDAT
- 45 B
- IEND
- 12 B
- Complete PNG
- 90 B
IDAT: 12 chunk bytes + 6 zlib bytes + 27 DEFLATE bytes. In a tiny image headers outweigh the pixels. This is the complete encoded file size, not an estimate from nonzero values.
JPEG: what can be discarded and where error appears
A photograph can often tolerate some error in exchange for a smaller file. JPEG separates luma from chroma, processes small blocks and represents them as sums of simple patterns. In the baseline process, the main loss comes from rounding coefficients after division by a step. The later coefficient coding does not itself cause that error.
JPEG: which changes can be made less noticeable?
Next is the usual DCT-based, lossy JPEG pipeline. Unlike PNG, reconstructed numbers can differ. JPEG also defines other modes; this lesson follows the common photographic variant.
- RGB → Y′CbCrSeparate a luma component from two colour-difference components. Conversion alone does not compress.RGB 210, 90, 50Y′ 121.3Cb 87.8Cr 191.3
- Chroma can use fewer samplesIn 4:2:0 a 2 × 2 area has four Y′ samples but only one Cb and one Cr sample. This separately loses colour detail. 4:4:4 skips this reduction.Y′Y′Y′Y′CbCr
- Each component → 8 × 8 blocks → DCTSubtract 128 from sample values. Transform 64 block values into 64 spatial-pattern coefficients. Without rounding, inverse DCT restores the block: the transform itself discards no information.
- Quantization introduces errorDivide a coefficient by its step Q and round; multiply by Q to reconstruct. For example: 23 / 10 → 2 → 20. The missing 3 cannot be recovered. Different frequencies use different steps.23÷ 102× 1020
- Zigzag → zero runs → bitsRead coefficients from low to high frequency. Code DC as a difference from the previous block; code AC using zero-run lengths and values. Huffman coding packs symbols without adding loss. Zigzag ordering itself also loses nothing.
- Reverse the steps → reconstruction → errorDecode bits, restore coefficients, apply inverse DCT and reconstruct colour. Compare both image details and error against the original. The number of retained coefficients is not a JPEG file size.
The next example examines one block: the pattern represented by a coefficient, what rounding does, and how reconstructed pixels change.
Cosine tiles add up to a block
DCT-II expands an 8×8 block in real cosine bases. The top-left DC coefficient stores the mean under the chosen normalization; moving right and down adds faster changes. Zero coefficients contribute nothing to reconstruction.
Each tile has bright and dark parts relative to zero: these are signed terms, not a finished photo. Its coefficient multiplies the whole tile. A zero coefficient adds nothing; a negative coefficient reverses the contribution signs. All 64 contributions together exactly reconstruct the source block.
One pattern and its contribution
Change horizontal and vertical frequencies. The left shows the pattern; the right shows that pattern multiplied by its source-block coefficient. Both scales stay fixed: a small coefficient makes the right tile fainter. Frequencies 0 and 0 give a constant pattern.
Exact values are in the point inspector
Blue − · white 0 · red +; scale -0.25…0.25
Exact values are in the point inspector
Blue − · white 0 · red +; scale -0.25…0.25
Inspect the selected point
What the plot shows
Frequency selects the shape; the coefficient determines how much to add or subtract. Even a small coefficient affects the whole block, not one pixel.
Parameters and details
This is one of 64 block patterns. Frequencies set its shape; the coefficient sets its sign and strength. Both tiles use one fixed −0.25…0.25 display scale; larger contributions saturate the display color, but exact values are not clipped. A negative contribution means subtraction, not negative brightness in the finished photo.
Select an image point. Arrows move it; Home and End reach row edges. Viewing does not change the calculation.
Changing the example requires JavaScript and Canvas. Computed images remain available above.
Which contributions can be discarded
Now add several tiles. Square side 1 retains only constant DC; side 2 retains four positions, and side 4 sixteen. Compare results with the same source block: retaining faster variations preserves more fine detail.
Discarding high frequencies and rounding coefficients lose information differently. The first removes selected patterns entirely; the second changes the strength of retained patterns. Sharp edges can develop oscillations. Dropping coefficients does not produce a JPEG: byte counts require actual encoding.
How many frequencies to retain
Begin with one coefficient, then expand the frequency square. In the stages, select coefficients and choose a cell; the basis and contribution stages show the cosine tile it adds. Then enable quantization.
Exact values are in the point inspector
Grayscale 0…1: black to white.
Exact values are in the point inspector
Grayscale 0…1: black to white.
Inspect the selected point
What the plot shows
One DC coefficient gives the block mean. Full 8×8 without quantization reconstructs the input; coarse coefficients lose detail and can ring.
- MSE
- 0.0025
- RMSE
- 0.05
- PSNR (range 0–1)
- 26.019 dB
- Retained positions
- 16
Parameters and details
Orthonormal DCT-II: a k×k low-frequency square, then uniform quantization. This is not a JPEG file: no color transform, JPEG tables, zigzag or entropy coding.
Select an image point. Arrows move it; Home and End reach row edges. Viewing does not change the calculation.
Changing the example requires JavaScript and Canvas. Computed images remain available above.
SVD adapts a basis to this matrix
SVD writes A as a sum of rank-one layers. The first r give the best rank-at-most-r approximation in squared error. Here directions are computed from by Jacobi rotations, suitable for a tiny teaching scene but sensitive to conditioning.
Storing r layers needs two vectors per layer plus singular values; high r can cost more than the input array. PCA of an image dataset organizes the matrix differently and usually centers data. It is mathematically related to, but not identical with, SVD of one photograph.
Add rank-one layers
Select the vertical vector, horizontal vector and their layer. Each layer cell multiplies two selected numbers. Select a layer cell to check that product; then add layers in descending singular-value order.
Exact values are in the point inspector
Blue − · white 0 · red +; scale -4…4
- Rank-one layer
- Previous sum + new layer
Exact values are in the point inspector
Grayscale 0…1: black to white.
Inspect the selected point
What the plot shows
Singular values belong to the source matrix and do not change when rank changes. The marker shows how many leading layers are included in the current image; the remaining tail is discarded.
- σ
- Layers included through this index: 3
Squared approximation error does not increase as layers are added. More layers need not save bytes.
- MSE
- 0.0005
- RMSE
- 0.0218
- PSNR (range 0–1)
- 33.221 dB
- Retained matrix energy
- 99.8505 %
Parameters and details
Jacobi diagonalization of AᵀA, followed by A VᵣVᵣᵀ. A bounded 16×16 teaching matrix: normal equations lose precision on ill-conditioned data. Layer count is not file size.
Select an image point. Arrows move it; Home and End reach row edges. Viewing does not change the calculation.
Changing the example requires JavaScript and Canvas. Computed images remain available above.
Information loss and coding are separate steps
Reference and further methods
Quantization makes values repeat more often. RLE codes run lengths; Huffman and arithmetic coding use symbol probabilities. Entropy describes expected information under a model, not the exact size of a short file with headers. Lossless coding must reproduce source symbols exactly.
PNG, WebP, AVIF and other formats differ in modes, compatibility and overhead. Sparse representations retain a few significant dictionary coefficients. Compressed sensing needs assumptions about sparsity and measurements; it cannot recover any image from any handful of pixels. Evaluate quality against actual bytes for a named codec.
Practice
Test the idea under another condition. Follow the task above the images; point inspection helps explain the result. This exploration is not scored.
Four coefficient positions versus sixteen
Start with a 2×2 square: four coefficient positions. Compare it with 4×4, select one newly included coefficient and inspect its cosine contribution. Enable quantization only after that comparison.
Exact values are in the point inspector
Grayscale 0…1: black to white.
Exact values are in the point inspector
Grayscale 0…1: black to white.
Inspect the selected point
What the plot shows
An extra position helps when its coefficient carries detail. Retained position count does not tell you the byte count; zero coefficients still occupy positions in this scheme.
- MSE
- 0.007
- RMSE
- 0.0839
- PSNR (range 0–1)
- 21.5258 dB
- Retained positions
- 4
Parameters and details
Orthonormal DCT-II: a k×k low-frequency square, then uniform quantization. This is not a JPEG file: no color transform, JPEG tables, zigzag or entropy coding.
Select an image point. Arrows move it; Home and End reach row edges. Viewing does not change the calculation.
Changing the example requires JavaScript and Canvas. Computed images remain available above.
Games
Four coefficient positions versus sixteen
How many low frequencies were retained in the target? Choose the coefficient-square side; quantization stays off.
Exact values are in the point inspector
Grayscale 0…1: black to white.
Exact values are in the point inspector
Grayscale 0…1: black to white.
Exact values are in the point inspector
Grayscale 0…1: black to white.
Compare your result with the reference.
Inspect the selected point
What the plot shows
An extra position helps when its coefficient carries detail. Retained position count does not tell you the byte count; zero coefficients still occupy positions in this scheme.
- MSE
- 0.007
- RMSE
- 0.0839
- PSNR (range 0–1)
- 21.5258 dB
- Retained positions
- 4
Parameters and details
Orthonormal DCT-II: a k×k low-frequency square, then uniform quantization. This is not a JPEG file: no color transform, JPEG tables, zigzag or entropy coding.
Select an image point. Arrows move it; Home and End reach row edges. Viewing does not change the calculation.
Changing the example requires JavaScript and Canvas. Computed images remain available above.
Test your explanation
Question 1 of 5
Only DCT DC remains. What results?
Exact values are in the point inspector
Grayscale 0…1: black to white.
Exact values are in the point inspector
Grayscale 0…1: black to white.
Exact values are in the point inspector
Grayscale 0…1: black to white.
Exact values are in the point inspector
Grayscale 0…1: black to white.
Exact values are in the point inspector
Blue − · white 0 · red +; scale -4…4
Exact values are in the point inspector
Blue − · white 0 · red +; scale -1…1
Choose one answer. It is checked immediately.
Limitations and references
Limits of this example
Executed: 8×8 DCT, uniform quantization and 16×16 low-rank approximation. Position count is not called JPEG size; no complete codec or compressed-sensing solver is implemented.