Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cornell!uw-beaver!uw-entropy!queets!adrianb
From: adrianb@queets.stat.washington.edu (Adrian Baddeley)
Newsgroups: comp.graphics
Subject: Re: Fingerprint enhancement
Message-ID: <1597@uw-entropy.ms.washington.edu>
Date: 9 Jul 89 22:19:19 GMT
References: <1269@servax0.essex.ac.uk> <5433@b11.ingr.com>
Sender: news@uw-entropy.ms.washington.edu
Reply-To: adrianb@castor.ms.washington.edu
Organization: UW Statistics, Seattle
Lines: 38

In article <1269@servax0.essex.ac.uk>, nigel@ese.essex.ac.uk (Nigel S.H. Brooks) writes:

> ... an algorithm to thin the lines down to single pixel width 

Methods from J. Serra, Image Analysis and Mathematical Morphology, 
Academic Press 1982:

(a) skeletonizing: use if lines are more than a few pixels thick
and vary in thickness.

	Compute distance transform of background.
		(see any text e.g. Rosenfeld and Kak)
	Best use the (5,5,7) distance, i.e. distance between horizontal
	or vertical neighbours is 5 and between diagonal neighbours 7.

	If say d(x) = distance from pixel x to nearest background pixel,
	the skeleton consists of all pixels x which do not have 
	a **neighbour** pixel y with d(y) > d(x) and 
	d(y) - d(x) = distance from y to x.

	This should be a 1-pixel-wide line down the middle of your thick lines.

(a) thinning: Use if your lines are only a few pixels thick and
uniform in thickness.  simple case:

	set any pixel to 0 when its 3x3 neighbourhood looks like
	0 0 0 		1 1 1		1 * 0
	* 1 * 	or	* 1 *	or	1 1 0 	etc...
	1 1 1		0 0 0		1 * 0
	(* = either 0 or 1 allowed). Iterate until no more changes occur. 

Both usually require tweaking to work well.

----
adrianb@castor.ms.washington.edu	(until 21 august 1989)
Adrian Baddeley, visiting Department of Statistics GN-22,
University of Washington, Seattle WA 98195, USA.
	tel (U of W): +1 206 545-2617 / 543-7237