Skip to content

Pruning

Status: Stable

documented, exercised by the test suite and/or worked examples, with no known limitations recorded.

Description

Pruning[image]

removes one pixel from every free end of the foreground; Pruning[image, n] repeats that n times, which shortens each branch by up to n and deletes any branch shorter than that. Used after Thinning to remove the short spurs a skeleton grows at boundary irregularities. An end point has exactly one foreground neighbour, so an ISOLATED pixel is not one and survives: pruning shortens branches rather than erasing specks. Pruning[image, 0] is the image unchanged. The result is a "Bit" image.

Examples (13)

Every input below was run against the current Mathilda build and its output recorded.

Basic Examples (4)

In[1]:= line = Image[Table[If[i == 5, 1, 0], {i, 1, 9}, {j, 1, 12}]];

In[2]:= {Round[Total[Flatten[ImageData[line]]]], Round[Total[Flatten[ImageData[Pruning[line]]]]]}
Out[2]= {12, 10}

In[3]:= Round[Total[Flatten[ImageData[Pruning[line, 3]]]]]
Out[3]= 6

In[4]:= ImageType[Pruning[line]]
Out[4]= "Bit"

Properties & Relations (6)

In[5]:= line = Image[Table[If[i == 5, 1, 0], {i, 1, 9}, {j, 1, 12}]];

In[6]:= dot = Image[Table[If[i == 5 && j == 6, 1, 0], {i, 1, 9}, {j, 1, 12}]];

Zero passes is the identity -- the boundary a loop written with <= gets wrong

In[7]:= ImageData[Pruning[line, 0]] === ImageData[line]
Out[7]= True

An isolated pixel has no neighbours, so it is not an end point and survives any n

In[8]:= Round[Total[Flatten[ImageData[Pruning[dot, 5]]]]]
Out[8]= 1

Only ever deletes

In[9]:= Max[Flatten[ImageData[Pruning[line, 2]] - ImageData[line]]] <= 0
Out[9]= True

Each pass takes one pixel from each of the two ends

In[10]:= Table[Round[Total[Flatten[ImageData[Pruning[line, k]]]]], {k, 0, 4}]
Out[10]= {12, 10, 8, 6, 4}

Applications (3)

In[11]:= ImageData[Pruning[Image[{{0, 0, 0, 0}, {1, 1, 1, 0}, {0, 0, 0, 0}}], 1]]
Out[11]= {{0.0, 0.0, 0.0, 0.0}, {0.0, 1.0, 0.0, 0.0}, {0.0, 0.0, 0.0, 0.0}}

In[12]:= ImageData[Pruning[Image[{{0, 0, 0, 0}, {1, 1, 1, 0}, {0, 0, 0, 0}}], 0]]
Out[12]= {{0.0, 0.0, 0.0, 0.0}, {1.0, 1.0, 1.0, 0.0}, {0.0, 0.0, 0.0, 0.0}}

In[13]:= ImageType[Pruning[Image[{{0, 0, 0}, {1, 1, 1}, {0, 0, 0}}]]]
Out[13]= "Bit"

Algorithm

imagethin.c -- Thinning and Pruning: reducing a shape to its skeleton, and tidying it.

Both are ITERATIVE and both are defined on a BINARY image, which is what separates them from everything in imagefilter.c: a filter reads a window and writes one value, where these two delete pixels in passes and stop when a pass changes nothing. A neighbourhood kernel cannot express that — the result of one pass is the input to the next.

WHY ZHANG-SUEN. It is the standard two-subiteration thinning, and its two subiterations exist for a reason worth stating: deleting every deletable pixel in ONE pass severs a diagonal line, because two diagonal neighbours can each be individually removable while removing both disconnects the shape. Alternating the two conditions removes from opposite sides on alternating passes, which is what preserves connectivity. A single-pass "delete if removable" thinning looks correct on a thick blob and quietly breaks every diagonal stroke.

THRESHOLD. A non-binary image is thresholded at 0.5 rather than at "nonzero". Nonzero is the right rule for MorphologicalComponents, where the caller has usually binarised already, but for these two it would make almost every grey image entirely foreground and the skeleton would be a frame around the border. Callers wanting another rule should apply Binarize first, which is a decision they can see.

Implementation notes

Algorithm. builtin_pruning removes one pixel from every free end of the foreground. It builds a foreground mask (mask_from_image, channels averaged and thresholded at 0.5) and runs prune_pass n times — once by default, n times for Pruning[image, n], which shortens each branch by up to n and deletes any branch shorter than that; Pruning[image, 0] is the image unchanged. Each pass marks an end point — a foreground pixel with exactly one foreground neighbour — and deletes all marked pixels together after the pass (mirroring Thinning, so one deletion does not change a neighbour's verdict mid-pass). The "exactly one neighbour" rule is deliberate: an isolated pixel has zero foreground neighbours and so is not an end point and survives — pruning shortens branches, it does not erase specks, and a rule that deleted isolated pixels would quietly remove every one-pixel component. Pruning is the companion to Thinning, used to clean the short spurs a skeleton grows at boundary irregularities. The result is a "Bit" image.

Data structures. An unsigned char foreground mask of width · height and a per-pass calloc'd deletion map. The 8-neighbourhood count reuses the same neighbours/counting helpers as Thinning. Built into a "Bit" image (image_build_bit).

Complexity / limits. O(n · width · height) for n passes. Operates on a binary plane; a non-binary image is thresholded at 0.5.

  • Protected. Returns a "Bit" image, always a subset of the input.
  • An end point has exactly one foreground neighbour, so an isolated pixel is not one and survives: pruning shortens branches rather than erasing specks. A rule that removed isolated pixels would quietly delete every one-pixel component.
  • n passes shorten each branch by up to n, and remove any branch shorter than that entirely — which is what makes it the companion to Thinning, whose skeletons grow short spurs at boundary irregularities.
  • Pruning[image, 0] is the image unchanged.

Attributes: Protected.

References

See also: Thinning

Notes & additional examples

Notes

Pruning[image] removes one pixel from every free end of the foreground; Pruning[image, n] repeats that n times, shortening each branch by up to n and deleting any branch shorter than that. Pruning[image, 0] is the image unchanged.

It is used after Thinning to remove the short spurs a skeleton grows at boundary irregularities. An end point has exactly one foreground neighbour, so an isolated pixel (with none) is not one and survives: pruning shortens branches rather than erasing specks. As in Thinning, each pass marks then deletes together, so one removal does not change a neighbour's verdict mid-pass. The result is a "Bit" image.