---
title: "Choosing a thinning method"
output: rmarkdown::html_vignette
vignette: >
  %\VignetteIndexEntry{Choosing a thinning method}
  %\VignetteEngine{knitr::rmarkdown}
  %\VignetteEncoding{UTF-8}
---

```{r setup, include = FALSE}
knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>"
)
library(thinr)
```

Thinning reduces a binary shape to a one-pixel-wide centerline that preserves topology. Several algorithms exist; they differ in how aggressively they erode pixels, how well they preserve corners, and how fast they run. This vignette gives a short guide to choosing among the algorithms `thinr` provides.

## What's implemented

| Method        | Reference                                | Approach                                            |
|---------------|------------------------------------------|-----------------------------------------------------|
| `zhang_suen`  | Zhang & Suen (1984)                      | 2 sub-iterations, mixed-direction products          |
| `guo_hall`    | Guo & Hall (1989)                        | 2 sub-iterations, conditions tuned for diagonals    |
| `lee`         | Lee, Kashyap & Chu (1994), 2-D           | 4 directional sub-iterations + Euler-invariance     |
| `k3m`         | Saeed et al. (2010)                      | 6 phases of progressively permissive removal        |
| `hilditch`    | parallel form (Rutovitz-style)           | Single pass with look-ahead crossing-number check   |
| `opta`        | Naccache & Shinghal (1984)               | Safe-point thinning (SPTA)                          |
| `holt`        | Holt, Stewart, Clint & Perrott (1987)    | One subcycle with edge information on neighbours    |

`zhang_suen` is the default and matches `EBImage::thinImage()` behavior. The `thinImage()` wrapper is provided as a drop-in replacement.

`lee` is a 2-D adaptation of Lee's original 3-D algorithm. The 3-D case (volumetric thinning) is not implemented in this release.

The `hilditch` method implements the *parallel form* commonly cited as "Hilditch" in modern image-processing surveys; Hilditch's 1969 paper actually describes a sequential algorithm with within-pass deletion tracking and a different crossing-number definition. See Lam, Lee & Suen (1992) for the relationship between the two.

The K3M lookup tables `A_0 … A_5` are reproduced from Saeed et al. (2010), Section 3.3, page 327. OPTA's safe-point boolean expression and Holt's condition `H` are taken from the original papers; the Lam-Lee-Suen 1992 survey was used as cross-reference and one transcription error in Holt's middle clause (north vs east) was corrected against the original.

## A quick visual comparison

```{r}
# A 'V' shape — exercises diagonal preservation
make_v <- function() {
  m <- matrix(0L, 11, 11)
  for (k in seq(0, 5)) {
    m[2 + k, 2 + k] <- 1L
    m[2 + k, 10 - k] <- 1L
    m[3 + k, 2 + k] <- 1L
    m[3 + k, 10 - k] <- 1L
  }
  m
}
v <- make_v()
v
```

```{r}
thin(v, method = "zhang_suen")
```

```{r}
thin(v, method = "guo_hall")
```

```{r}
thin(v, method = "hilditch")
```

```{r}
thin(v, method = "k3m")
```

```{r}
thin(v, method = "holt")
```

The thinning algorithms produce broadly similar skeletons on this V — they all collapse the two diagonal strokes to single lines and meet at the bottom. Differences show up on more complex shapes:

- `zhang_suen` is the most aggressive on simple shapes.
- `guo_hall` and `k3m` preserve corners marginally better.
- `hilditch` has the look-ahead crossing-number check, which gives different connectivity properties at junctions.
- `holt` uses edge information about neighbouring pixels rather than a crossing-number check on the central pixel; it is specifically designed to preserve 2-pixel-wide lines.

## When to use which

- **`zhang_suen`** — the default. Most predictable behavior. Use for general purpose thinning and for compatibility with code that previously used `EBImage::thinImage()`.
- **`guo_hall`** — try this if your skeletons have lots of diagonal features and Zhang-Suen is breaking them at corners.
- **`lee`** — when you want directional processing (four sub-iterations per pass, one per cardinal direction). Sometimes produces cleaner skeletons on asymmetric inputs.
- **`k3m`** — strongest corner preservation in published comparative studies, at the cost of being slower (six phases per outer iteration vs. two for Zhang-Suen).
- **`hilditch`** — well-cited historical algorithm; the look-ahead crossing-number check makes its connectivity slightly different from the other parallel algorithms.
- **`opta`** — one-pass safe-point algorithm. Its `N2` condition protects two-4-adjacent-pixel diagonal patterns, which can leave stray pixels at bar corners (a documented property of SPTA).
- **`holt`** — when 2-pixel-wide lines should be preserved. The algorithm uses edge information from neighbouring pixels in a 5x5 window, allowing a single subcycle.

## Medial axis transform

The thinning algorithms above all produce binary 1-pixel-wide skeletons without width information. For tasks where local thickness matters, use `medial_axis()`:

```{r}
m <- matrix(0L, 9, 11)
m[3:7, 3:9] <- 1L      # 5x7 solid rectangle
medial_axis(m)
```

```{r}
result <- medial_axis(m, return_distance = TRUE)
result$skeleton
round(result$distance, 3)
```

The distance is the Euclidean distance from each foreground pixel to the nearest background pixel.

## Distance transform

`distance_transform()` exposes the distance transform itself as a stand-alone utility, with a choice of metric:

```{r}
m <- matrix(1L, 5, 5)
m[1, 1] <- 0L
distance_transform(m, metric = "manhattan")
distance_transform(m, metric = "chessboard")
round(distance_transform(m, metric = "euclidean"), 3)
```

The Euclidean implementation uses the linear-time separable algorithm of Felzenszwalb and Huttenlocher (2012); the others use the classical Rosenfeld and Pfaltz (1968) two-pass sweep.

## Inputs and outputs

`thin()`, `medial_axis()`, and `thinImage()` accept logical, integer, and numeric matrices. Non-zero values are foreground. The return matrix matches the storage mode of the input — logical in, logical out; integer in, integer out; numeric in, numeric out.

`distance_transform()` always returns a numeric matrix.

Higher-dimensional arrays (e.g. 3-D volumes) are not yet supported.

## Performance

A simple `bench::mark()` comparison on a moderate image (illustrative):

```{r eval = FALSE}
library(bench)
m <- matrix(0L, 200, 200)
m[50:150, 50:150] <- 1L  # solid square

bench::mark(
  zs       = thin(m, method = "zhang_suen"),
  gh       = thin(m, method = "guo_hall"),
  hild     = thin(m, method = "hilditch"),
  k3m      = thin(m, method = "k3m"),
  ma       = medial_axis(m),
  dt_eucl  = distance_transform(m, metric = "euclidean"),
  iterations = 5,
  check = FALSE
)
```

All thinning algorithms are `O(iterations × pixels)`. Constant factors are smallest for `zhang_suen` and `guo_hall`; `holt` and `k3m` are the most expensive because of their look-aheads. The Euclidean distance transform is `O(pixels)` via Felzenszwalb-Huttenlocher; medial axis is `O(pixels)` since it just adds a single linear pass over the DT.

For 200×200 images all algorithms finish in a few milliseconds on modern hardware.

## References

### Thinning

- Zhang, T. Y. & Suen, C. Y. (1984). A fast parallel algorithm for thinning digital patterns. *Communications of the ACM*, 27(3), 236–239. \doi{10.1145/357994.358023}
- Guo, Z. & Hall, R. W. (1989). Parallel thinning with two-subiteration algorithms. *Communications of the ACM*, 32(3), 359–373. \doi{10.1145/62065.62074}
- Lee, T.-C., Kashyap, R. L., & Chu, C.-N. (1994). Building skeleton models via 3-D medial surface axis thinning algorithms. *CVGIP: Graphical Models and Image Processing*, 56(6), 462–478. \doi{10.1006/cgip.1994.1042}
- Saeed, K., Tabędzki, M., Rybnik, M., & Adamski, M. (2010). K3M: A universal algorithm for image skeletonization and a review of thinning techniques. *International Journal of Applied Mathematics and Computer Science*, 20(2), 317–335. \doi{10.2478/v10006-010-0024-4}
- Hilditch, C. J. (1969). Linear skeletons from square cupboards. In B. Meltzer & D. Michie (Eds.), *Machine Intelligence 4* (pp. 403–420). Edinburgh University Press.
- Naccache, N. J. & Shinghal, R. (1984). An investigation into the skeletonization approach of Hilditch. *Pattern Recognition*, 17(3), 279–284.
- Holt, C. M., Stewart, A., Clint, M., & Perrott, R. H. (1987). An improved parallel thinning algorithm. *Communications of the ACM*, 30(2), 156–160. \doi{10.1145/12527.12531}

### Survey

- Lam, L., Lee, S.-W., & Suen, C. Y. (1992). Thinning methodologies — a comprehensive survey. *IEEE Transactions on Pattern Analysis and Machine Intelligence*, 14(9), 869–885. \doi{10.1109/34.161346}

### Medial axis and distance transform

- Blum, H. (1967). A transformation for extracting new descriptors of shape. In *Models for the Perception of Speech and Visual Form* (pp. 362–380). MIT Press.
- Felzenszwalb, P. F. & Huttenlocher, D. P. (2012). Distance transforms of sampled functions. *Theory of Computing*, 8(19), 415–428. \doi{10.4086/toc.2012.v008a019}
- Rosenfeld, A. & Pfaltz, J. L. (1968). Distance functions on digital pictures. *Pattern Recognition*, 1(1), 33–61. \doi{10.1016/0031-3203(68)90013-7}