Metadata-Version: 2.4
Name: centerline-svg
Version: 0.1.0
Summary: Trace the centerline (medial axis) of a solid shape in a PNG and emit an SVG. Pure standard library.
Project-URL: Homepage, https://github.com/anhnd/centerline-svg
Project-URL: Repository, https://github.com/anhnd/centerline-svg
Author-email: anhnd <anhnd350309@gmail.com>
License: MIT
License-File: LICENSE
Keywords: centerline,medial-axis,png,skeleton,svg,thinning,zhang-suen
Classifier: License :: OSI Approved :: MIT License
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Classifier: Topic :: Multimedia :: Graphics
Classifier: Topic :: Scientific/Engineering :: Image Processing
Requires-Python: >=3.9
Description-Content-Type: text/markdown

# Centerline Extraction (Medial Axis → SVG)

Turn each PNG (a single solid black shape, 1024×1024, white background) into an SVG whose
`<path>` elements follow the **centerline (medial axis / skeleton)** of the shape — the "pen
stroke" a person would draw — instead of tracing its outer contour.

Example: a letter **H** drawn with a thick stroke should come out as **three thin stroked
paths** (two vertical, one horizontal) joined at the two intersections.

- Sample inputs: `challenge_sample/*.png` (ampersand, arrow-pointer, arrow-turn-down-left, letter_H, letter_K, number_3, number_6)
- Reference outputs: `challenge_sample_results/*.svg`
- Constraint: **no third-party libraries** — everything from PNG decoding to the skeleton is hand-written (the packaged library depends on nothing but the Python standard library).

---

## Install & use

Packaged as **`centerline-svg`** (pure stdlib, no runtime dependencies).

```bash
pip install centerline-svg          # from PyPI (see PUBLISHING.md for TestPyPI)
```

As a library — input is an image (path **or** bytes), output is an SVG string:

```python
import centerline_svg

svg = centerline_svg.png_to_svg("arrow.png")                 # from a path
svg = centerline_svg.png_to_svg(open("arrow.png", "rb").read())  # from bytes

# optional debug flag: also dump one PNG per pipeline stage
svg = centerline_svg.png_to_svg("arrow.png", steps_dir="steps/")
```

Command line:

```bash
centerline-svg in.png out.svg                 # one file
centerline-svg in_dir/ out_dir/               # batch a folder
centerline-svg in.png out.svg --steps steps/  # + per-stage debug PNGs
```

Web demo (upload a PNG, get the SVG back) — see `webapp/`:

```bash
pip install -r webapp/requirements.txt && pip install -e .
uvicorn webapp.app:app --reload      # open http://127.0.0.1:8000
```

Deploy the demo to **Railway** straight from this source (the `Dockerfile` does
`pip install .`, so no PyPI publish is needed):

```bash
railway init --name pictographic     # create + link a project
railway up -c -y                     # upload current dir, build the Dockerfile, deploy
railway domain                       # get a public URL
```

Layout:

```
src/centerline_svg/
├── core.py     # the algorithm + fluent Pipeline (input image → output SVG)
├── render.py   # OPTIONAL step visualization (enabled only via steps_dir / --steps)
├── __init__.py # png_to_svg(...) public API
└── cli.py      # console entry point
webapp/app.py   # FastAPI upload-and-convert demo
```

---

## 0. What the data tells us (read before coding)

Dissecting `challenge_sample_results/letter_H.svg` (11 `<path>` elements) shows the
**reference is a classic thinning skeleton**, split into graph edges, each edge emitted as one
densely-sampled polyline:

- Only `M` + `L` commands (polylines) — **no Béziers, no smoothing, no simplification**.
- 5 long paths = the 5 main branches (two left verticals, two right verticals, one horizontal bar).
- 6 short paths (2 points each) = "stubs" connecting each branch tip to the **exact junction
  node** at `(177,516)` and `(847,516)`.
- Attributes: `stroke-width="45"`, `stroke-linecap="round"`, `stroke-linejoin="round"`, `fill="none"`.

Consequences for the approach:
1. **Go with thinning skeleton + graph tracing**, no curve fitting needed. To match the
   reference, emitting the skeleton pixel chains directly as polylines is enough.
2. The hint's "contour + perpendiculars + midpoints" method only works for **single strokes**
   and **breaks at intersections** — which is exactly what the challenge grades ("intersections
   preserve the right topology"). Skip it.
3. All 7 PNGs are **RGB 8-bit, no alpha** → mask = luminance `< 128`.

---

## 1. High-level architecture

```
PNG ─►① binary mask ─►② thinning (Zhang–Suen) ─►②b cleanup ─►③ pixels → graph ─►④ trace + prune ─►⑤ emit SVG
                                                                     ▲
                                             (aux) distance transform: stroke width + prune threshold
```

**Language: pure Python**, standard library only (`zlib`, `struct`, `math`, `sys`). One file
(`centerline.py`), one function per step. Run:

```
python3 centerline.py in.png out.svg            # one file
python3 centerline.py in_dir/ out_dir/          # whole folder
```

Runtime ≈ 5 s per 1024² image (the distance transform and the byte-level PNG de-filter are the
costs of staying pure-stdlib).

---

## 2. SEQUENCE FLOW — step by step

Each step lists: **In → Do → Out → Check**. Verify each step before moving on.

### Step 1 — Decode PNG into a pixel array (hand-written, using `zlib`)

- **In:** path to a `.png` file.
- **Do:**
  1. Verify the 8-byte signature `89 50 4E 47 0D 0A 1A 0A`.
  2. Walk the **chunks** `[len(4) | type(4) | data(len) | crc(4)]`. Read `IHDR` for
     `width, height, bit_depth, color_type`. Concatenate all `IDAT` data.
  3. `zlib.decompress(idat)` → decompressed byte stream = the **scanlines**, each scanline is
     1 leading **filter-type** byte + `width × bytes_per_pixel` data bytes.
  4. **Undo the filters** per scanline (the most error-prone part): for each byte `x`, recover
     `raw` per the 5 filter types:
     - 0 None: `raw = x`
     - 1 Sub: `raw = x + raw[a]` (a = left pixel)
     - 2 Up: `raw = x + raw[b]` (b = pixel above)
     - 3 Average: `raw = x + (raw[a] + raw[b]) // 2`
     - 4 Paeth: `raw = x + paeth(a, b, c)` (c = upper-left); all mod 256.
  5. Extract RGB channels (color_type=2 → 3 bytes/pixel).
- **Out:** `read_png(path) -> (w, h, pixels)` where `pixels[y][x] = (r,g,b)`.
- **Check:** print `w,h` = 1024×1024; count dark pixels, expect ~10–30% coverage.
- *Note:* Paeth predictor:
  `p = a+b-c; pa=|p-a|; pb=|p-b|; pc=|p-c|; return a if pa≤pb and pa≤pc, else b if pb≤pc, else c`.

### Step 2 — Threshold into a binary mask

- **In:** `pixels`.
- **Do:** `mask[y][x] = 1` if `0.299r + 0.587g + 0.114b < 128` (black = foreground), else 0.
  Pad the mask with a 1-px border of 0 so neighborhood steps never touch the edge.
- **Out:** `mask` (2D array of 0/1).
- **Check:** dump the mask to a PNG/ASCII-art and confirm it matches the shape.

### Step 3 — Thinning (Zhang–Suen) → 1-px skeleton

- **In:** `mask`.
- **Do:** iterate until **a full pass deletes nothing**. Each pass has **two sub-iterations**:
  - For each foreground pixel P, look at its 8 neighbors `P2..P9` (P2 = North, going clockwise).
  - `B(P)` = number of foreground neighbors; `A(P)` = number of `0→1` transitions going around
    `P2,P3,…,P9,P2`.
  - **Sub-iteration 1** marks P for deletion if: `2≤B≤6` **and** `A=1` **and** `P2·P4·P6=0`
    **and** `P4·P6·P8=0`.
  - **Sub-iteration 2**: `2≤B≤6` **and** `A=1` **and** `P2·P4·P8=0` **and** `P2·P6·P8=0`.
  - Within a sub-iteration: **evaluate conditions on the old image, delete all marked pixels at
    the end** (never delete in place).
- **Out:** `skel` — a mask that is exactly 1 px wide.
- **Check:** body pixels have ≤2 neighbors; the shape stays connected and holes are preserved
  (the 6 and the loop of the & still enclose a hole).
- **Why it works:** see section 3.

### Step 3b — Cleanup: remove redundant "staircase" pixels

- **In:** `skel`.
- **Do:** Zhang–Suen leaves 2-px **staircase** artifacts on diagonal/curved strokes (a smooth
  run where some pixels have 3–4 raw neighbors). Left alone, Step 4 reads each of those as a
  junction and shatters the stroke into hundreds of 2-px paths. Remove a pixel P when it is
  **redundant**: it has ≥2 neighbors (not an endpoint), its **crossing number ≤ 2** (not a real
  junction), and its foreground neighbors are still **8-connected without it** (removing it can't
  disconnect anything). Iterate to a fixed point. Straight and clean-diagonal line pixels have
  two *non-adjacent* neighbor groups, so they are kept.
- **Out:** a clean skeleton where body pixels really do have degree 2.
- **Check:** branch count drops from hundreds to a handful (see Results).
- *This is the single most important fix for real inputs — see "Bugs / gotchas" below.*

### Step 4 — Turn the skeleton into a graph

- **In:** `skel`.
- **Do:**
  1. For each skeleton pixel, count its skeleton neighbors (8-connected) = its **degree**.
  2. Classify: **endpoint** (degree 1), **junction** (degree ≥3), **body** (degree 2).
  3. Merge touching junction pixels into **one junction node** (take the centroid) to avoid
     fragmentation.
- **Out:** the set of special nodes (endpoints + junctions).
- **Check:** H has 4 endpoints + 2 junctions; the 6 has 1 endpoint + 1 junction + 1 loop.

### Step 5 — Trace the branches (graph edges)

- **In:** `skel` + the node set.
- **Do:** from each node, walk along the chain of **degree-2** pixels (marking visited) until you
  hit the next special node → that chain is one **branch polyline**. Handle:
  - **Pure loop** (a cycle with no special node, e.g. a circle): pick any pixel as the opening
    point and trace the loop back to itself.
  - Snap each branch tip to the **junction centroid** so strokes meet at a single point (like the
    "stubs" in the reference) → round joins make them merge cleanly.
- **Out:** a list of polylines (lists of `(x,y)` points).
- **Check:** branch count is roughly the reference path count (H≈11, K≈13, &≈18).

### Step 6 — Prune spurs + estimate stroke width

- **In:** the branch list + (aux) distance transform.
- **Do:**
  - **Distance transform (DT):** distance to the background for each foreground pixel via a
    **two-pass chamfer** (one top-left→bottom-right pass, one reverse). Use it to: estimate stroke
    width `W ≈ 2 × median(DT along the skeleton)`, and to threshold spur pruning.
  - **Prune spurs:** delete any branch that **ends at an endpoint** and is **shorter than ~the
    stroke radius** (spurs created by thinning at corners/rounded ends). Be careful not to prune a
    genuinely short stroke.
- **Out:** cleaned branch list + `W`.
- **Check:** tiny stub branches are gone; the main strokes are intact.

### Step 6b — Straighten & smooth (fixing where the medial axis is systematically wrong)

The raw skeleton is *topologically* right but *geometrically* wrong in three places, all
visible on the arrows. Each gets a targeted fix in `Pipeline.smooth()`:

1. **Straight strokes bend at their ends.** Near an end cap that isn't cut perpendicular
   to the stroke, and near any junction, the medial axis hooks sideways (that's what the
   distance-transform ridge really does there). So a chord through the branch endpoints is
   **rotated off the true axis**. Fix (`_fit_straight`): fit a **total-least-squares line
   to the stable interior only** (points ≥ ~1 stroke width of arc length away from both
   ends), and accept the branch as "straight" only if every interior point is within ~3 px
   of that line. Then **project the endpoints onto the fitted line** — the bent tails can
   no longer tilt the stroke. Curves and L-shaped branches fail the tolerance and skip this.
2. **The junction pixel isn't where the strokes actually cross.** Thinning leaves the node
   wherever peeling happened to converge. Fix (`_lsq_node`): re-solve each junction as the
   **least-squares intersection of the fitted axes** of its straight arms, then snap every
   arm's end to that node — all arms meet, dead straight, at one exact point.
   (`_straighten_junction_ends` first removes the medial-axis hook within ~1 stroke width
   of the node so the fit sees clean data.)
3. **Diagonal/curved runs are staircased.** For branches that are genuinely curved:
   **RDP** (ε≈2 px) removes the staircase, then **corner-aware Chaikin** rounds the result
   — splitting at vertices that turn more than ~45° so real corners (H/K joints, the
   arrow's 90° elbow) stay sharp while gentle curves (3, 6, &) get smooth.

- **Check:** arrow wings are straight lines meeting at a single node; 3/6/& stay curved.

### Step 7 — Emit SVG

- **In:** the branch list + `W`.
- **Do:** each branch → `<path d="M x0 y0 L x1 y1 L …" fill="none" stroke="#000"
  stroke-width="W" stroke-linecap="round" stroke-linejoin="round"/>`. Wrap in
  `<svg xmlns=... width=1024 height=1024 viewBox="0 0 1024 1024">…</svg>`.
- **Out:** `<name>.svg`.
- **Check:** render and compare side by side with the reference (overlay the faint original to
  check where the skeleton lands).

---

## 3. Why Zhang–Suen thinning is correct (the core to explain)

Notation: pixel P, 8 neighbors `P2..P9` (P2 = North, clockwise). `B(P)` = number of foreground
neighbors, `A(P)` = **crossing number** = number of `0→1` transitions going around `P2…P9,P2`.

- **`A(P)=1`** ⟺ P is a **simple boundary point**: there is exactly **one** connected run of
  foreground around P. Deleting such a point **cannot** disconnect the local shape, nor create or
  fill a hole → the **topology is preserved** (number of connected components and holes). If
  `A≥2` (e.g. P bridges two branches or sits next to a hole), deleting P would break something —
  this condition blocks that.
- **`B≥2`** preserves **line ends**: an endpoint has exactly one neighbor (`B=1`), so it is never
  deleted → strokes are not eaten back. **`B≤6`** avoids deleting an almost-surrounded interior
  pixel (not a boundary point worth simplifying).
- **The two alternating sub-iterations** `(c)(d)` vs `(c')(d')` only allow deletions on the
  **south-east** boundary, then the **north-west** boundary. Peeling symmetrically from both sides
  keeps the skeleton **centered**, and prevents deleting a whole 2-px-wide line in one pass (which
  would break the line).
- Iterate to convergence → a **1-px-wide, 8-connected skeleton with the same topology** as the
  shape. That is exactly the "skeleton a person would draw with a pen."

Known limitations: leaves slight **staircasing** on diagonal strokes and short **spurs** at
corners/rounded ends (hence the prune step). Improvements: **Guo–Hall** thinning has fewer spurs,
or add a staircase-removal pass.

---

## 4. Code structure

```
src/centerline_svg/core.py   # the algorithm + fluent Pipeline
│   ├── decode_png / read_png            # Step 1  (chunk parse + zlib + de-filter)
│   ├── to_mask(...)                     # Step 2
│   ├── zhang_suen(W, grid)              # Step 3
│   ├── cleanup_skeleton(W, skel)        # Step 3b (remove staircase pixels)
│   ├── distance_transform(...)          # aux (stroke width + prune threshold)
│   ├── trace_branches(W, skel)          # Steps 4+5 (graph + trace, uses crossing number)
│   ├── prune(branches, deg, ...)        # Step 6
│   ├── _fit_straight / _lsq_node        # Step 6b (axis fit + junction re-solve)
│   ├── smooth_polyline (RDP+Chaikin)    # Step 6b (corner-aware smoothing for curves)
│   ├── to_svg(polylines, ...)           # Step 7
│   └── class Pipeline                   # wires the steps; png_to_svg() drives it
src/centerline_svg/render.py # OPTIONAL step visualization (steps_dir / --steps only)
```

See **Install & use** at the top for the `png_to_svg()` API and the `centerline-svg` CLI.
The step visualization is a *flag*, not a separate program: pass `steps_dir=...`
(`--steps DIR` on the CLI) to also dump one PNG per stage; omit it for SVG-only.

## Results (this implementation vs the reference)

All 7 outputs land on the correct centerline with the right topology (junctions and loops
preserved). Path counts are lower than the reference because I trace long branches straight
through junctions instead of splitting into many stubs — same geometry, fewer `<path>` elements.

| shape | my paths | ref paths | notes |
|---|---|---|---|
| letter_H | 4 | 11 | ✓ |
| letter_K | 5 | 13 | ✓ |
| number_3 | 3 | 5 | ✓ |
| number_6 | 2 | 5 | ✓ loop + tail |
| ampersand | 7 | 18 | ✓ self-crossing (deg-4) + loop |
| arrow-pointer | 3 | 31 | ✓ (arrowhead Y-axis, see below) |
| arrow-turn-down-left | 3 | 10 | ✓ |

Stroke width is derived from the distance transform (`2×median radius`, ≈ 64–72 px here) rather
than the reference's fixed 45; it tracks the original stroke thickness more closely. Either is
acceptable per the brief.

## Bugs / gotchas I hit (owning every line)

1. **Neighbor index vs offset.** My crossing-number helper first did `(i + d) in skel` where `d`
   was already an absolute neighbor index, not an offset → every lookup missed and every pixel
   read as degree 0. Fix: test the neighbor indices directly. Lesson: pick one representation
   (indices *or* offsets) and stick to it.
2. **Infinite loop in tracing.** Before Step 3b, staircase body pixels had extra raw neighbors, so
   the branch/loop walk could bounce forever. Fixed by (a) consuming interior pixels and never
   stepping onto a used one, and (b) a hard step cap = skeleton size. Step 3b then removed the root
   cause, collapsing hundreds of spurious paths to a handful.
3. **Raw degree ≠ topological degree.** Counting raw 8-neighbors calls staircase pixels
   junctions. The **crossing number** (number of connected neighbor *runs*) is the correct degree
   and is what makes junction detection robust.

---

## 5. Where the output diverges from the reference (and why)

- **Rounded stroke ends (H, K):** the skeleton stops ~one stroke-radius short of the tip (the
  medial axis of a rounded end terminates at the center of the end-cap arc). `stroke-linecap="round"`
  plus the stroke width `W` fills that back in, so it **looks matching**. Endpoints landing slightly
  inside is **correct** (the reference does the same).
- **Arrows (arrow-pointer):** the medial axis of a **solid triangle** is a **Y** (three spokes to
  the three corners) — not a single pen stroke. This produces extra branches at the arrowhead. This
  is an **inherent divergence** of the medial axis itself; the two short spokes can be pruned to
  leave a single axis.
- **Diagonal strokes (K, &):** Zhang–Suen leaves staircasing. The reference emits the raw
  staircase; we instead straighten/smooth it (Step 6b), so our output is *cleaner than* the
  reference — straight strokes are dead straight at the true axis angle. This is a deliberate
  divergence.
- **Junction position:** the reference keeps the thinning node as-is; we re-solve it as the
  least-squares intersection of the stroke axes (Step 6b), which can shift it a few px — toward
  where the strokes actually cross.
- **Self-crossing & :** the overlap is a degree-4 junction; the graph keeps the topology correct,
  yielding many paths (~18).

---

## 6. What I'd improve with more time

- Replace Zhang–Suen with **Guo–Hall** or a **distance-transform + ridge** method for a smoother,
  spur-free skeleton.
- Fit **circular arcs / Béziers** on curved strokes (3, 6, &) instead of dense polylines.
- Smarter spur pruning using the **DT** (real spur vs real short stroke) instead of length alone.
- **Pair opposite arms through crossings** (the & self-intersection): join the two arms whose
  tangents line up into one continuous path through the node, so the two pen strokes glide
  through each other instead of four arms parking at one point.
- Handle arrowheads: detect the head triangle and replace the Y-spur with a single sharp tip.

---

## 7. Status

**Implemented, packaged, and working** — all 7 sample shapes produce correct centerlines
(see Results). The algorithm lives in `src/centerline_svg/core.py`, one function per step,
so each part is readable and independently verifiable; it is published as the pure-stdlib
`centerline-svg` package with a `png_to_svg()` API, a `centerline-svg` CLI, and a FastAPI
web demo in `webapp/`.

Regenerate the sample outputs:
```
centerline-svg challenge_sample/ out/
```

Publishing (TestPyPI then PyPI): see **`PUBLISHING.md`**.
