thinr
Binary Image Thinning Algorithms
Thinning (skeletonization) algorithms for binary raster
images. Provides seven algorithms behind a single dispatching
function: Zhang-Suen (Zhang and Suen 1984)
thinr
Binary image thinning (skeletonization) algorithms for R, plus the medial axis transform and a fast Euclidean / Manhattan / Chessboard distance transform. Seven thinning algorithms sit behind a single dispatching function. EBImage, the dominant R/Bioconductor image toolkit, provides binary morphology (dilate, erode, distmap, watershed) but no thinning operator; thinr fills that gap in a small, dependency-light package.
Installation
# Once on CRAN:
# install.packages("thinr")
# From GitHub:
# install.packages("remotes")
remotes::install_github("humanpred/thinr")
Usage
library(thinr)
m <- matrix(0L, 11, 11)
m[3:9, 3:9] <- 1L # 7x7 solid square
# Default: Zhang-Suen
thin(m)
# Or pick an algorithm explicitly
thin(m, method = "guo_hall")
thin(m, method = "hilditch")
thin(m, method = "holt")
# Medial axis transform (returns binary skeleton + per-pixel width)
medial_axis(m)
medial_axis(m, return_distance = TRUE)
# Distance transform as a standalone utility
distance_transform(m, metric = "euclidean")
distance_transform(m, metric = "manhattan")
distance_transform(m, metric = "chessboard")
Algorithms
| Method | Reference |
|---|---|
zhang_suen |
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. Default. |
guo_hall |
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 |
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. 2-D adaptation; the 3-D form is not implemented. |
k3m |
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. Lookup tables A_0…A_5 reproduced from the paper. |
hilditch |
Parallel form commonly attributed to Hilditch. The original algorithm is Hilditch, C. J. (1969). Linear skeletons from square cupboards. In B. Meltzer & D. Michie (Eds.), Machine Intelligence 4 (pp. 403–420). Edinburgh University Press. The parallel form here uses Rutovitz-style R1–R4 conditions; see Lam, Lee & Suen (1992) for the precise differences. |
opta |
Naccache, N. J. & Shinghal, R. (1984). An investigation into the skeletonization approach of Hilditch. Pattern Recognition, 17(3), 279–284. Also called the Safe Point Thinning Algorithm (SPTA). |
holt |
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. One-subcycle, uses edge information about neighbours. |
Plus:
| Function | Reference |
|---|---|
medial_axis() |
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. Implementation finds ridge points of the squared Euclidean distance transform; returns the binary skeleton, optionally with per-pixel distance. |
distance_transform() |
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. Linear-time separable squared Euclidean transform; plus the Rosenfeld & Pfaltz (1968) two-pass forward + backward sweep for metric = "manhattan" and "chessboard". |
The survey by 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, was used as the cross-reference for the parallel-form Hilditch and for verifying OPTA's safe-point boolean expression.
See vignette("choosing-a-method") for guidance on choosing among the methods.
License
LGPL-3, the same licence as EBImage, so that an EBImage-based pipeline (or EBImage itself) can depend on thinr for the thinning operator EBImage does not provide, without licence friction.