Purpose: Convert binary shapes obtained from edge/boundary detection or thresholding to 1-pixel wide lines. For example, the thresholded version of hand written or printed alphanumerics can be thinned for better represetation and further processing.
Method: iteratively delete pixels inside the shape to shrink it without shortening it or breaking it apart.
Some Definitions: To decide whether an edge pixel should be deleted, consider its 8 neighbors in the 3 by 3 neighborhood, , , , , , , and , and define:
The Algorithm: This is a 2-pass process:
A problem: When part of the shape is only 2-pixel wide, all pixels are boundary points and will be marked and then deleted. We want to delete only one side at a time.
The Solution: A two-step process:
Modified Algorithm: Repeat until no more change can be made:
Let represent the event ``''. Then
can be represented by:
Similarly, we see hat edges on N, W, SW, or SE side will be deleted in the second pass.