{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "7fb27b941602401d91542211134fc71a",
   "metadata": {},
   "source": [
    "# Dithering algorithm comparison\n",
    "\n",
    "Migrated from `dither_test/`. The 6-colour ACeP palette can only show Black, White, Yellow,\n",
    "Red, Blue, Green — so the dithering algorithm choice has a big effect on perceived image\n",
    "quality. This notebook applies a curated set of error-diffusion and ordered-dithering\n",
    "algorithms to a few real photos from Immich and shows them side-by-side, with timing.\n",
    "\n",
    "Production uses Atkinson with perceptual weighting (`atkinson_weighted` is the closest\n",
    "match — the actual production version is numba-JIT'd, equivalent to `atkinson_fast`). This\n",
    "notebook is the place to evaluate alternatives if you want to switch.\n",
    "\n",
    "Algorithm taxonomy:\n",
    "- **Error diffusion** (`floyd_steinberg`, `atkinson`, `jarvis`, `stucki`, `sierra`,\n",
    "  `sierra_lite`, `burkes`) — quantise pixels left-to-right, push the rounding error onto\n",
    "  unprocessed neighbours.\n",
    "- **Ordered** (`bayer4`, `bayer8`, `bayer4_strong`) — add a deterministic threshold pattern\n",
    "  before quantising. No error spreading; pattern is independent of content.\n",
    "- **PIL built-ins** (`pil_fs`, `pil_none`) — for reference."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "acae54e37e7d407bbb7b55eff062a284",
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "\n",
    "sys.path.insert(0, \".\")\n",
    "from _helpers import bootstrap, download_image, fetch_pool, immich_client, show_grid, silenced\n",
    "\n",
    "bootstrap()\n",
    "\n",
    "import time\n",
    "\n",
    "import numpy as np\n",
    "from _dither import DITHER_ALGORITHMS, PALETTE_NAMES, PALETTE_RGB, apply_dithering\n",
    "from PIL import Image\n",
    "from waveshare_epd.epd7in3e import EPD_HEIGHT, EPD_WIDTH, _crop_center\n",
    "\n",
    "# Pure-Python algorithms run at ~30s per 800x480 image; keep a curated subset by default.\n",
    "# Toggle SHOW_ALL = True to run everything (will take several minutes).\n",
    "DEFAULT_ALGOS = [\n",
    "    \"atkinson_fast\",\n",
    "    \"atkinson\",\n",
    "    \"atkinson_weighted\",\n",
    "    \"floyd_steinberg\",\n",
    "    \"floyd_steinberg_weighted\",\n",
    "    \"jarvis\",\n",
    "    \"sierra_lite\",\n",
    "    \"burkes\",\n",
    "    \"bayer4\",\n",
    "    \"bayer8\",\n",
    "    \"pil_fs\",\n",
    "    \"none\",\n",
    "]\n",
    "SHOW_ALL = False\n",
    "ALGOS = list(DITHER_ALGORITHMS.keys()) if SHOW_ALL else DEFAULT_ALGOS\n",
    "\n",
    "N_PHOTOS = 2  # one image cycle per photo\n",
    "SEED = 11"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "9a63283cbaf04dbcab1f6479b197f3a8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "IMG_5070.JPG\n",
      "010061480009_6A.jpg\n"
     ]
    },
    {
     "data": {
      "image/jpeg": "/9j/4AAQSkZJRgABAQAAAQABAAD/2wBDAAgGBgcGBQgHBwcJCQgKDBQNDAsLDBkSEw8UHRofHh0aHBwgJC4nICIsIxwcKDcpLDAxNDQ0Hyc5PTgyPC4zNDL/2wBDAQkJCQwLDBgNDRgyIRwhMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjL/wAARCAA8AWgDASIAAhEBAxEB/8QAHwAAAQUBAQEBAQEAAAAAAAAAAAECAwQFBgcICQoL/8QAtRAAAgEDAwIEAwUFBAQAAAF9AQIDAAQRBRIhMUEGE1FhByJxFDKBkaEII0KxwRVS0fAkM2JyggkKFhcYGRolJicoKSo0NTY3ODk6Q0RFRkdISUpTVFVWV1hZWmNkZWZnaGlqc3R1dnd4eXqDhIWGh4iJipKTlJWWl5iZmqKjpKWmp6ipqrKztLW2t7i5usLDxMXGx8jJytLT1NXW19jZ2uHi4+Tl5ufo6erx8vP09fb3+Pn6/8QAHwEAAwEBAQEBAQEBAQAAAAAAAAECAwQFBgcICQoL/8QAtREAAgECBAQDBAcFBAQAAQJ3AAECAxEEBSExBhJBUQdhcRMiMoEIFEKRobHBCSMzUvAVYnLRChYkNOEl8RcYGRomJygpKjU2Nzg5OkNERUZHSElKU1RVVldYWVpjZGVmZ2hpanN0dXZ3eHl6goOEhYaHiImKkpOUlZaXmJmaoqOkpaanqKmqsrO0tba3uLm6wsPExcbHyMnK0tPU1dbX2Nna4uPk5ebn6Onq8vP09fb3+Pn6/9oADAMBAAIRAxEAPwD5/ooooAKKKKACiiigAr3/APZl/wCZp/7dP/a1eAV7/wDsy/8AM0/9un/tagD6AooooAKKKKACiiigArCrdrCr4bjT/lx/29/7adOH6hRRRXwx1BRRRQAUUUUAeafFv/mD/wDbb/2SvNK9L+Lf/MH/AO23/sleaV9zk/8AuUPn+bP0bIf+RfT+f/pTCiiivTPYCiiigAooooA5Ciiiv6XP57CiiigAooooAK7z4bf8xP8A7Zf+z1wdd58Nv+Yn/wBsv/Z6+Q48/wCSfxH/AG5/6XE8zOf9yn8vzR3tFFFfzkfDBRRRQAUUUUAFFFFAHzTRRRX6Wfr4UUUUAFFFFABXv/7Mv/M0/wDbp/7WrwCvf/2Zf+Zp/wC3T/2tQB9AUUUUAFFFFABRRRQAVhVu1hV8Nxp/y4/7e/8AbTpw/UKKKK+GOoKKKKACiiigDzT4t/8AMH/7bf8AsleaV6X8W/8AmD/9tv8A2SvNK+5yf/cofP8ANn6NkP8AyL6fz/8ASmFFFFemewFFFFABRRRQByFFFFf0ufz2FFFFABRRRQAV3nw2/wCYn/2y/wDZ64Ou8+G3/MT/AO2X/s9fIcef8k/iP+3P/S4nmZz/ALlP5fmjvaKKK/nI+GCiiigAooooAKKKKAPmmiiiv0s/XwooooAKKKKACvf/ANmX/maf+3T/ANrV4BXv/wCzL/zNP/bp/wC1qAPoCiiigAooooAKKKKACsKt2sKvhuNP+XH/AG9/7adOH6hRRRXwx1BRRRQAUUUUAeafFv8A5g//AG2/9krzSvS/i3/zB/8Att/7JXmlfc5P/uUPn+bP0bIf+RfT+f8A6Uwooor0z2AooooAKKKKAOQooor+lz+ewooooAKKKKACu8+G3/MT/wC2X/s9cHXefDb/AJif/bL/ANnr5Djz/kn8R/25/wClxPMzn/cp/L80d7RRRX85HwwUUUUAFFFFABRRRQB800UUV+ln6+FFFFABRRRQAV7/APsy/wDM0/8Abp/7WrwCvf8A9mX/AJmn/t0/9rUAfQFFFFABRRRQAUUUUAFYVbtYVfDcaf8ALj/t7/206cP1CiiivhjqCiiigAooooA80+Lf/MH/AO23/sleaV6X8W/+YP8A9tv/AGSvNK+5yf8A3KHz/Nn6NkP/ACL6fz/9KYUUUV6Z7AUUUUAFFFFAHIUUUV/S5/PYUUUUAFFFFABXefDb/mJ/9sv/AGeuDrvPht/zE/8Atl/7PXyHHn/JP4j/ALc/9LieZnP+5T+X5o72iiiv5yPhgooooAKKKKACiiigD//Z",
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAWgAAAA8CAIAAADE77fXAAACBUlEQVR4Ae3UgQnAQAwDsbb775yOYQ70C8TIj98n+O4umPrtZU5GDv6N60F/vd8sMQECawHDsW7AfQJBAcMRLE1kAmsBw7FuwH0CQQHDESxNZAJrAcOxbsB9AkEBwxEsTWQCawHDsW7AfQJBAcMRLE1kAmsBw7FuwH0CQQHDESxNZAJrAcOxbsB9AkEBwxEsTWQCawHDsW7AfQJBAcMRLE1kAmsBw7FuwH0CQQHDESxNZAJrAcOxbsB9AkEBwxEsTWQCawHDsW7AfQJBAcMRLE1kAmsBw7FuwH0CQQHDESxNZAJrAcOxbsB9AkEBwxEsTWQCawHDsW7AfQJBAcMRLE1kAmsBw7FuwH0CQQHDESxNZAJrAcOxbsB9AkEBwxEsTWQCawHDsW7AfQJBAcMRLE1kAmsBw7FuwH0CQQHDESxNZAJrAcOxbsB9AkEBwxEsTWQCawHDsW7AfQJBAcMRLE1kAmsBw7FuwH0CQQHDESxNZAJrAcOxbsB9AkEBwxEsTWQCawHDsW7AfQJBAcMRLE1kAmsBw7FuwH0CQQHDESxNZAJrAcOxbsB9AkEBwxEsTWQCawHDsW7AfQJBAcMRLE1kAmsBw7FuwH0CQQHDESxNZAJrAcOxbsB9AkEBwxEsTWQCawHDsW7AfQJBAcMRLE1kAmsBw7FuwH0CQQHDESxNZAJrgR/+VQV3J+6g7AAAAABJRU5ErkJggg==",
      "text/plain": [
       "<PIL.Image.Image image mode=RGB size=360x60>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "client = immich_client()\n",
    "pool_assets = fetch_pool(client, pool_size=20, seed=SEED)\n",
    "\n",
    "with silenced():\n",
    "    sources = []\n",
    "    for asset in pool_assets[:N_PHOTOS]:\n",
    "        img = download_image(client, asset)\n",
    "        sources.append((asset, _crop_center(img, EPD_WIDTH, EPD_HEIGHT)))\n",
    "\n",
    "for asset, _ in sources:\n",
    "    print(asset.get(\"originalFileName\") or asset[\"id\"])\n",
    "\n",
    "# Render the 6-colour palette as a tiny banner so the colour budget is visible.\n",
    "swatch_h = 60\n",
    "swatch_w = 60\n",
    "palette_strip = np.zeros((swatch_h, swatch_w * len(PALETTE_RGB), 3), dtype=np.uint8)\n",
    "for i, rgb in enumerate(PALETTE_RGB):\n",
    "    palette_strip[:, i * swatch_w : (i + 1) * swatch_w] = rgb\n",
    "Image.fromarray(palette_strip)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "8dd0d8092fe74a7c96281538738b07e2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[IMG_5070.JPG]\n",
      "  Atkinson (Numba Fast)               0.38s\n",
      "  Atkinson                            3.82s\n",
      "  Atkinson (Weighted)                 4.23s\n",
      "  Floyd-Steinberg                     3.95s\n",
      "  Floyd-Steinberg (Weighted)          4.27s\n",
      "  Jarvis-Judice-Ninke                 8.48s\n",
      "  Sierra Lite                         3.30s\n",
      "  Burkes                              5.56s\n",
      "  Ordered (Bayer 4x4)                 2.18s\n",
      "  Ordered (Bayer 8x8)                 2.20s\n",
      "  Floyd-Steinberg (PIL)               0.01s\n",
      "  No Dithering (PIL)                  0.00s\n",
      "[010061480009_6A.jpg]\n",
      "  Atkinson (Numba Fast)               0.01s\n",
      "  Atkinson                            3.89s\n",
      "  Atkinson (Weighted)                 4.23s\n",
      "  Floyd-Steinberg                     3.84s\n",
      "  Floyd-Steinberg (Weighted)          4.26s\n",
      "  Jarvis-Judice-Ninke                 8.55s\n",
      "  Sierra Lite                         3.27s\n",
      "  Burkes                              5.59s\n",
      "  Ordered (Bayer 4x4)                 2.25s\n",
      "  Ordered (Bayer 8x8)                 2.19s\n",
      "  Floyd-Steinberg (PIL)               0.01s\n",
      "  No Dithering (PIL)                  0.00s\n"
     ]
    }
   ],
   "source": [
    "results = []  # list of dict per (photo, algo)\n",
    "for asset, source in sources:\n",
    "    name = asset.get(\"originalFileName\") or asset[\"id\"]\n",
    "    print(f\"[{name}]\")\n",
    "    photo_results = []\n",
    "    for algo in ALGOS:\n",
    "        info = DITHER_ALGORITHMS[algo]\n",
    "        t0 = time.perf_counter()\n",
    "        out = apply_dithering(source, algo)\n",
    "        dt = time.perf_counter() - t0\n",
    "        photo_results.append({\"algo\": algo, \"name\": info[\"name\"], \"image\": out, \"duration\": dt})\n",
    "        print(f\"  {info['name']:32s}  {dt:6.2f}s\")\n",
    "    results.append({\"asset\": asset, \"source\": source, \"algos\": photo_results})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "72eea5119410473aa328ad9291626812",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 4942736 characters]",
      "text/plain": [
       "<Figure size 2000x1280 with 16 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/png": "[encoded data, 5257100 characters]",
      "text/plain": [
       "<Figure size 2000x1280 with 16 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# One grid per photo: original + every algorithm.\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "for entry in results:\n",
    "    panels = [entry[\"source\"]] + [r[\"image\"] for r in entry[\"algos\"]]\n",
    "    titles = [\"original (cropped)\"] + [f\"{r['name']}\\n{r['duration']:.2f}s\" for r in entry[\"algos\"]]\n",
    "    cols = 4\n",
    "    rows = (len(panels) + cols - 1) // cols\n",
    "    fig, axes = plt.subplots(rows, cols, figsize=(5.0 * cols, 3.2 * rows))\n",
    "    axes = np.atleast_2d(axes)\n",
    "    name = entry[\"asset\"].get(\"originalFileName\") or entry[\"asset\"][\"id\"]\n",
    "    fig.suptitle(name, fontsize=12)\n",
    "    for k in range(rows * cols):\n",
    "        ax = axes[k // cols][k % cols]\n",
    "        if k < len(panels):\n",
    "            ax.imshow(panels[k])\n",
    "            ax.set_title(titles[k], fontsize=10)\n",
    "        ax.axis(\"off\")\n",
    "    plt.tight_layout()\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "8edb47106e1a46a883d545849b8ab81b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "algorithm                          avg time  description\n",
      "Atkinson (Numba Fast)                 0.20s  Numba-accelerated Atkinson (~150x faster, requires numba)\n",
      "Atkinson                              3.86s  Bill Atkinson (Apple), diffuses only 75% of error for cleaner results\n",
      "Atkinson (Weighted)                   4.23s  Atkinson with perceptual color weighting\n",
      "Floyd-Steinberg                       3.90s  Classic error diffusion (1976), good balance of speed and quality\n",
      "Floyd-Steinberg (Weighted)            4.26s  Floyd-Steinberg with perceptual color weighting\n",
      "Jarvis-Judice-Ninke                   8.51s  Larger diffusion kernel (1976), smoother gradients but slower\n",
      "Sierra Lite                           3.28s  Faster Sierra variant with smaller kernel\n",
      "Burkes                                5.57s  Simplified two-row error diffusion\n",
      "Ordered (Bayer 4x4)                   2.22s  Ordered dithering with 4x4 Bayer matrix\n",
      "Ordered (Bayer 8x8)                   2.20s  Ordered dithering with 8x8 Bayer matrix\n",
      "Floyd-Steinberg (PIL)                 0.01s  PIL built-in Floyd-Steinberg implementation\n",
      "No Dithering (PIL)                    0.00s  Simple nearest-color quantization without error diffusion\n"
     ]
    }
   ],
   "source": [
    "# Per-algorithm summary across both photos: mean runtime + a single representative panel.\n",
    "from collections import defaultdict\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "agg = defaultdict(list)\n",
    "for entry in results:\n",
    "    for r in entry[\"algos\"]:\n",
    "        agg[r[\"algo\"]].append(r[\"duration\"])\n",
    "\n",
    "print(f\"{'algorithm':32s}  {'avg time':>9s}  description\")\n",
    "for algo in ALGOS:\n",
    "    info = DITHER_ALGORITHMS[algo]\n",
    "    avg = np.mean(agg[algo])\n",
    "    print(f\"{info['name']:32s}  {avg:>8.2f}s  {info['description']}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "10185d26023b46108eb7d9f57d49d2b3",
   "metadata": {},
   "source": [
    "## Picking an algorithm\n",
    "\n",
    "- **Photographs** — `atkinson_fast` (production), `atkinson_weighted`, or\n",
    "  `floyd_steinberg_weighted`. Atkinson loses some detail (only diffuses 6/8 of the error)\n",
    "  but gives cleaner edges; FS preserves detail at the cost of more visible noise.\n",
    "- **Graphics / illustrations / posters** — `bayer4` or `bayer8`. The pattern is regular\n",
    "  (no \"wormy\" artifacts) and well-suited to large flat regions.\n",
    "- **Speed-critical paths** — `atkinson_fast` (numba-JIT). Pure-Python error-diffusion\n",
    "  algorithms are ~150× slower than the JIT'd version on this resolution.\n",
    "\n",
    "The `none` row (PIL nearest-colour) shows what happens with no dithering at all — useful as\n",
    "a baseline to confirm the dithering is buying you something.\n",
    "\n",
    "**To compare more algorithms** set `SHOW_ALL = True` in the setup cell. Expect several\n",
    "minutes of CPU time per photo for the slow pure-Python implementations."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "frame (3.12.13)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
