{ "cells": [ { "cell_type": "markdown", "id": "8e891743", "metadata": {}, "source": [ "# Lesson 17: Image Compression — Lossless and Lossy\n", "\n", "Storing an image as raw pixels costs 1 byte per channel per pixel, no matter what the image contains. Compression exploits various types of redundancy in images --- i.e., the fact that real images are not random. This lesson covers both **lossless** compression (the decoded image is bit-for-bit identical to the original — e.g., PNG) and **lossy** compression (the decoded image is only an approximation — e.g., JPEG)." ] }, { "cell_type": "code", "execution_count": null, "id": "1b04411c", "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "import cv2\n", "import heapq\n", "from collections import Counter\n", "import matplotlib.pyplot as plt" ] }, { "cell_type": "markdown", "id": "d0f55397", "metadata": {}, "source": [ "## Lossless compression\n", "\n", "### Run-length encoding (RLE)\n", "\n", "The simplest lossless scheme: instead of storing every pixel, store `(value, run length)` pairs for consecutive runs of identical pixels. This works great on images with large flat regions (synthetic graphics, scanned text, masks), but it does nothing useful on real photographs." ] }, { "cell_type": "code", "execution_count": null, "id": "13fc2593", "metadata": {}, "outputs": [], "source": [ "def rle_encode(array):\n", " flat = array.ravel()\n", " change_points = np.where(np.diff(flat) != 0)[0] + 1\n", " starts = np.concatenate([[0], change_points])\n", " ends = np.concatenate([change_points, [len(flat)]])\n", " return [(flat[s], e - s) for s, e in zip(starts, ends)]\n", "\n", "def rle_decode(runs, shape):\n", " flat = np.concatenate([np.full(length, value) for value, length in runs])\n", " return flat.reshape(shape).astype(np.uint8)\n", "\n", "flat_regions_img = np.zeros((80, 80), dtype=np.uint8)\n", "cv2.rectangle(flat_regions_img, (10, 10), (70, 70), 200, -1)\n", "sp = flat_regions_img.shape\n", "\n", "plt.imshow(flat_regions_img, cmap='gray')\n", "plt.title(f'Image with flat regions ({sp[1]}x{sp[0]}) = {sp[0]*sp[1]} bytes')\n", "plt.axis('off')\n", "plt.show()\n", "\n", "runs = rle_encode(flat_regions_img)\n", "decoded = rle_decode(runs, flat_regions_img.shape)\n", "print('exact reconstruction?', np.array_equal(decoded, flat_regions_img))\n", "\n", "raw_bytes = flat_regions_img.size\n", "rle_bytes = len(runs) * 3 # roughly: 1 byte value + 2 bytes run length, per run\n", "print(f'raw size: {raw_bytes} bytes')\n", "print(f'RLE size: ~{rle_bytes} bytes ({raw_bytes / rle_bytes:.1f}x smaller)')" ] }, { "cell_type": "markdown", "id": "e0a4224d", "metadata": {}, "source": [ "### Huffman coding: fewer bits for common values\n", "\n", "A more sophisticated lossless method is **Huffman coding**, which takes advantage of the fact that some pixel values (e.g., a common background gray) occur far more often than others. It builds a variable-length code where frequent values get short codes and rare values get longer ones — which is provably optimal among prefix codes.\n", "\n", "Shannon's **entropy** gives the theoretical floor on average bits/pixel for *any* code based only on the value distribution (ignoring spatial structure):\n", "\n", "$$H = -\\sum_i p_i \\log_2 p_i$$\n", "\n", "where $p_i$ is the probability that a certain pixel value occurs in the image, and the summation is over all possible pixel values." ] }, { "cell_type": "code", "execution_count": null, "id": "5b5af366", "metadata": {}, "outputs": [], "source": [ "rng = np.random.default_rng(0)\n", "photo_like = np.zeros((100, 100), dtype=np.uint8)\n", "cv2.rectangle(photo_like, (10, 10), (90, 90), 200, -1)\n", "cv2.circle(photo_like, (50, 50), 25, 120, -1)\n", "photo_like = np.clip(photo_like.astype(np.float64) + rng.normal(0, 5, photo_like.shape), 0, 255).astype(np.uint8)\n", "sp = photo_like.shape\n", "\n", "counts = Counter(photo_like.ravel().tolist())\n", "total = sum(counts.values())\n", "probs = {value: count / total for value, count in counts.items()}\n", "entropy = -sum(p * np.log2(p) for p in probs.values())\n", "\n", "\n", "def build_huffman_codes(probs):\n", " heap = [[p, [symbol, '']] for symbol, p in probs.items()]\n", " heapq.heapify(heap)\n", " while len(heap) > 1:\n", " lo = heapq.heappop(heap)\n", " hi = heapq.heappop(heap)\n", " for pair in lo[1:]:\n", " pair[1] = '0' + pair[1]\n", " for pair in hi[1:]:\n", " pair[1] = '1' + pair[1]\n", " heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])\n", " return {symbol: code for symbol, code in heap[0][1:]}\n", "\n", "codes = build_huffman_codes(probs)\n", "avg_bits = sum(probs[symbol] * len(code) for symbol, code in codes.items())\n", "\n", "plt.imshow(photo_like, cmap='gray')\n", "plt.title(f'Image with noise ({sp[1]}x{sp[0]}) = {sp[0]*sp[1]} bytes')\n", "plt.axis('off')\n", "plt.show()\n", "\n", "print(f'naive fixed-width encoding: 8.00 bits/pixel')\n", "print(f'Shannon entropy (theoretical floor): {entropy:.2f} bits/pixel')\n", "print(f'Huffman coding achieves: {avg_bits:.2f} bits/pixel')" ] }, { "cell_type": "markdown", "id": "af98762f", "metadata": {}, "source": [ "Huffman coding gets close to the entropy bound (it can only match it exactly when every probability happens to be a power of 2). Real lossless formats like PNG combine an idea like this (Huffman/arithmetic coding) with a **predictive filter** first — predicting each pixel from its neighbors and encoding only the (usually small) prediction error, which has much lower entropy than the raw pixel values." ] }, { "cell_type": "markdown", "id": "9d68a53f", "metadata": {}, "source": [ "## Lossy compression: the DCT\n", "\n", "JPEG's core idea is to take advantage of the human visual system's tendency to overlook fine details. JPEG divides the image into small 8x8 blocks, then transforms each block into the frequency domain so that it can discard the high-frequency components that are barely noticeable to the human eye. JPEG uses the **discrete cosine transform (DCT)**, which is a close relative of the Fourier transform from Lesson 15. Like the DFT, the DCT re-expresses a block as a sum of frequency components — but it uses only cosines (no imaginary part) to avoid boundary artifacts." ] }, { "cell_type": "code", "execution_count": null, "id": "44ca9891", "metadata": {}, "outputs": [], "source": [ "block = photo_like[6:14, 6:14].astype(np.float64) # a block straddling the rectangle's sharp edge\n", "dct_block = cv2.dct(block)\n", "\n", "energy = dct_block**2\n", "print(f'fraction of block energy in top-left 2x2 coefficients: {energy[:2, :2].sum() / energy.sum():.2%}')\n", "print(f'fraction of block energy in top-left 4x4 coefficients: {energy[:4, :4].sum() / energy.sum():.2%}')\n", "\n", "fig, axes = plt.subplots(1, 2, figsize=(6, 3))\n", "axes[0].imshow(block, cmap='gray')\n", "axes[0].set_title('8x8 pixel block')\n", "axes[1].imshow(np.log1p(np.abs(dct_block)), cmap='gray')\n", "axes[1].set_title('log|DCT coefficients|\\n(top-left = low frequency)')\n", "for ax in axes:\n", " ax.axis('off')\n", "plt.tight_layout()\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "15fb76c1", "metadata": {}, "source": [ "### Quantization: throwing away the coefficients that matter least\n", "\n", "Compression happens by **quantizing** the DCT coefficients — dividing by some value and rounding. The values to be divided by are taken from a quantization table, which are designed based on human visual sensitivity. Many coefficients (especially high-frequency ones, which carry the least energy) become exactly zero and take almost no space to store." ] }, { "cell_type": "code", "execution_count": null, "id": "38022b5b", "metadata": {}, "outputs": [], "source": [ "def keep_top_left(dct_block, n):\n", " \"\"\"Zero out every coefficient outside the top-left nxn corner (crude stand-in for JPEG-style quantization).\"\"\"\n", " masked = np.zeros_like(dct_block)\n", " masked[:n, :n] = dct_block[:n, :n]\n", " return masked\n", "\n", "fig, axes = plt.subplots(1, 4, figsize=(10, 3))\n", "for ax, n in zip(axes, [8, 4, 2, 1]):\n", " kept = keep_top_left(dct_block, n)\n", " reconstructed = cv2.idct(kept)\n", " nonzero = np.count_nonzero(kept)\n", " ax.imshow(reconstructed, cmap='gray', vmin=block.min(), vmax=block.max())\n", " ax.set_title(f'{nonzero}/64 coeffs kept', fontsize=9)\n", " ax.axis('off')\n", "plt.tight_layout()\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "cc85dc65", "metadata": {}, "source": [ "Even keeping just the top-left 2x2 (4 out of 64 coefficients — a 16x reduction) preserves most of the block's overall structure; only the finest detail is lost." ] }, { "cell_type": "markdown", "id": "cdb035e7", "metadata": {}, "source": [ "## Real JPEG: the rate-distortion tradeoff\n", "\n", "Real JPEG encoding follows this same DCT-then-quantize recipe per block (with a carefully designed, frequency-dependent quantization table, plus run-length and Huffman coding of the resulting sparse coefficients — combining the lossy and lossless ideas from this lesson). We use OpenCV's built-in encoder directly, sweeping the quality setting, and measure both file size and reconstruction error." ] }, { "cell_type": "code", "execution_count": null, "id": "7f1c23dc", "metadata": {}, "outputs": [], "source": [ "def psnr(original, reconstructed):\n", " mse = np.mean((original.astype(np.float64) - reconstructed.astype(np.float64))**2)\n", " return float('inf') if mse == 0 else 10 * np.log10(255**2 / mse)\n", "\n", "color_img = np.zeros((200, 200, 3), dtype=np.uint8)\n", "cv2.rectangle(color_img, (20, 20), (180, 180), (255, 120, 30), -1)\n", "cv2.circle(color_img, (100, 100), 60, (30, 200, 255), -1)\n", "color_img = np.clip(color_img.astype(np.float64) + rng.normal(0, 8, color_img.shape), 0, 255).astype(np.uint8)\n", "sp = color_img.shape\n", "\n", "qualities = [10, 30, 50, 80, 95, 100]\n", "sizes, psnrs = [], []\n", "for q in qualities:\n", " ok, encoded = cv2.imencode('.jpg', color_img, [cv2.IMWRITE_JPEG_QUALITY, q])\n", " decoded = cv2.imdecode(encoded, cv2.IMREAD_COLOR)\n", " sizes.append(len(encoded))\n", " psnrs.append(psnr(color_img, decoded))\n", "\n", "plt.imshow(color_img)\n", "plt.title(f'Image with noise ({sp[1]}x{sp[0]}) = {sp[0]*sp[1]*sp[2]} bytes')\n", "plt.axis('off')\n", "plt.show()\n", "\n", "raw_size = color_img.size\n", "print(f'{\"quality\":>8} {\"file size (bytes)\":>18} {\"compression ratio\":>18} {\"PSNR (dB)\":>10}')\n", "for q, s, p in zip(qualities, sizes, psnrs):\n", " print(f'{q:>8} {s:>18} {raw_size / s:>17.1f}x {p:>10.2f}')" ] }, { "cell_type": "code", "execution_count": null, "id": "4399409f", "metadata": {}, "outputs": [], "source": [ "fig, axes = plt.subplots(1, 2, figsize=(9, 3.5))\n", "axes[0].plot(qualities, sizes, marker='o')\n", "axes[0].set_xlabel('JPEG quality')\n", "axes[0].set_ylabel('file size (bytes)')\n", "axes[0].set_title('Size vs. quality')\n", "\n", "axes[1].plot(sizes, psnrs, marker='o')\n", "axes[1].set_xlabel('file size (bytes)')\n", "axes[1].set_ylabel('PSNR (dB)')\n", "axes[1].set_title('Rate-distortion curve')\n", "plt.tight_layout()\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "b231403d", "metadata": {}, "source": [ "This is the fundamental tradeoff of lossy compression: every extra byte you're willing to spend buys diminishing returns in quality (the rate-distortion curve flattens out at high quality), and there is no free lunch — only a choice of where on the curve to sit. For a typical photograph, JPEG quality of 75 will not be noticeable unless you zoom in, and it will reduce the file size by 6--8x." ] }, { "cell_type": "markdown", "id": "b52c60e3", "metadata": {}, "source": [ "## JPEG or PNG? Choosing the right format\n", "\n", "The trade-offs above translate into a practical rule:\n", "\n", "- Use **JPEG for photographs**. Photographs are dominated by smooth gradients — exactly what the DCT concentrates into a few low-frequency coefficients, so discarding the rest is barely visible and JPEG buys a large size reduction for a small perceptual loss. \n", "\n", "- Use **PNG for graphics** (screenshots, diagrams, text, icons, anything with flat regions or sharp edges). Graphics are the opposite case: a sharp edge spreads energy across *all* DCT frequencies, so the same quantization that photos tolerate shows up as visible ringing and blocking around edges and text. Lossless compression handles flat regions and sharp edges almost for free (that's exactly what RLE and the predictive filter above are good at), so PNG is often both artifact-free *and* smaller than JPEG for this kind of content." ] }, { "cell_type": "code", "execution_count": null, "id": "5d61db34", "metadata": {}, "outputs": [], "source": [ "photo = cv2.cvtColor(cv2.imread('../img/house.png'), cv2.COLOR_BGR2RGB)\n", "\n", "graphic = np.full((100, 200, 3), 255, dtype=np.uint8)\n", "cv2.rectangle(graphic, (20, 20), (180, 100), (40, 40, 40), -1)\n", "cv2.putText(graphic, 'REPORT', (30, 70), cv2.FONT_HERSHEY_SIMPLEX, 1.1, (255, 255, 255), 2)\n", "cv2.line(graphic, (30, 80), (160, 80), (255, 255, 255), 2)\n", "\n", "def encode_sizes(image, jpeg_quality=75):\n", " ok, jpg = cv2.imencode('.jpg', image, [cv2.IMWRITE_JPEG_QUALITY, jpeg_quality])\n", " ok, png = cv2.imencode('.png', image, [cv2.IMWRITE_PNG_COMPRESSION, 9])\n", " return jpg, png\n", "\n", "jpg_photo, png_photo = encode_sizes(photo)\n", "jpg_graphic, png_graphic = encode_sizes(graphic)\n", "\n", "print(f'{\"\":12} {\"Original\":>11} {\"PNG\":>11} {\"JPEG (q75)\":>11}')\n", "print(f'{\"photograph\":12} {int(np.prod(photo.shape)):>9} B {len(png_photo):>9} B {len(jpg_photo):>9} B (PNG is bigger than JPEG by {len(png_photo)/len(jpg_photo):.1f}x)')\n", "print(f'{\"graphic\":12} {int(np.prod(graphic.shape)):>9} B {len(png_graphic):>9} B {len(jpg_graphic):>9} B (PNG is smaller than JPEG by {len(png_graphic)/len(jpg_graphic):.1f}x)')\n", "\n", "fig, axes = plt.subplots(2, 2, figsize=(7, 7))\n", "axes[0, 0].imshow(photo); axes[0, 0].set_title(f'Photo: original ({int(np.prod(photo.shape))} B)')\n", "axes[0, 1].imshow(cv2.imdecode(jpg_photo, cv2.IMREAD_COLOR)); axes[0, 1].set_title(f'Photo: JPEG q75 ({len(jpg_photo)} B)')\n", "axes[1, 0].imshow(graphic); axes[1, 0].set_title(f'Graphic: original ({int(np.prod(graphic.shape))} B)')\n", "axes[1, 1].imshow(cv2.imdecode(jpg_graphic, cv2.IMREAD_COLOR)); axes[1, 1].set_title(f'Graphic: JPEG q75 ({len(jpg_graphic)} B)')\n", "for ax in axes.ravel():\n", " ax.axis('off')\n", "plt.tight_layout()\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "4cb4e672", "metadata": {}, "source": "

Photo by Peter Herrmann on Unsplash

" }, { "cell_type": "markdown", "id": "37905393", "metadata": {}, "source": [ "### A closer look at JPEG artifacts\n", "\n", "Zooming into a high-contrast region (the roofline against the sky) at a much lower quality setting makes the cost of aggressive quantization visible directly: blocky 8x8 squares and ringing around the sharp edge, exactly the failure mode described above." ] }, { "cell_type": "code", "execution_count": null, "id": "88198599", "metadata": {}, "outputs": [], "source": [ "y0, y1, x0, x1 = 10, 60, 50, 150 # roofline against the sky\n", "\n", "low_q = 10\n", "jpg_low_q, _ = encode_sizes(photo, jpeg_quality=low_q)\n", "decoded_low_q = cv2.imdecode(jpg_low_q, cv2.IMREAD_COLOR)\n", "\n", "zoom = 4\n", "original_crop = cv2.resize(photo[y0:y1, x0:x1], None, fx=zoom, fy=zoom, interpolation=cv2.INTER_NEAREST)\n", "jpeg_crop = cv2.resize(decoded_low_q[y0:y1, x0:x1], None, fx=zoom, fy=zoom, interpolation=cv2.INTER_NEAREST)\n", "\n", "fig, axes = plt.subplots(1, 2, figsize=(8, 4))\n", "axes[0].imshow(original_crop)\n", "axes[0].set_title('Original crop (zoomed 4x)')\n", "axes[1].imshow(jpeg_crop)\n", "axes[1].set_title(f'Same crop, JPEG q{low_q}\\n(full image: {len(jpg_low_q)} B)')\n", "for ax in axes:\n", " ax.axis('off')\n", "plt.tight_layout()\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "617f2677", "metadata": {}, "source": [ "### Exercise\n", "\n", "1. Run the RLE experiment on `photo_like` (which has Gaussian noise) instead of `flat_regions_img`. How many runs does it produce, and what does that say about RLE's suitability for noisy natural images?\n", "2. `keep_top_left` is a deliberately crude stand-in for real quantization (which shrinks *all* coefficients gradually rather than hard-zeroing a block of them). Replace it with `np.round(dct_block / step) * step` for a few different `step` values, and compare the visual artifacts to the top-left-corner version.\n", "3. At very low JPEG quality, you may notice a visible grid pattern aligned with the 8x8 block boundaries (\"blocking artifacts\"). Given what block boundaries have to do with the DCT, explain why quantizing each block *independently* would produce exactly this kind of artifact." ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python", "version": "3.x" } }, "nbformat": 4, "nbformat_minor": 5 }