Image skeletonization method

• US 5,224,179 A
• Filed: 12/30/1991
• Issued: 06/29/1993
• Est. Priority Date: 12/20/1988
• Status: Expired due to Fees

• Current Assignee: AT&T, Inc.
• Original Assignee: AT&T, Inc.
• Inventors: Henderson, Donnie, Denker, John S., Graf, Hans P., Hubbard, Wayne E., Jackel, Lawrence D., O'Gorman, Lawrence, Howard, Richard E.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US07/814,956
• Time in Patent Office: 547 Days
• Field of Search: 382/55, 382/54, 382/27, 382/49, 382/50
• US Class Current: 382/259
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/168 Smoothing or thinning of the pattern; Skeletonisation
• CPC Class Codes: G06V 30/20 Combination of acquisition, preprocessing or recognition functions

Abstract

A method for improved thinning or skeletonizing handwritten characters or other variable-line-width images. The method scans a template set over the image to be thinned. Each template has a specific arrangement of dark and light pixels. At least one of those templates includes either more than three pixels per row or more than three rows of pixels. An odd number is good choice. Moreover, the templates are chosen so that each template can unconditionally delete image pixels without consideration of the effect of such deletions on the behavior of the other templates. Thus the templates are independent of each other.

Claims

1. A method for thinning lines of an image composed of an array of pixels, comprising:

a first step of selecting a window of size k×

k, where k is an integer≧

3,

a step of applying thinning criteria to a portion of said image covered by said window to determine whether a core subportion of said image can be deleted,

a step of deleting said core subportion when said step of applying thinning criteria indicate that said core subportion should be deleted,

a step of reducing the size of said window by decreasing the value of k by one when said step of applying thinning criteria indicate that said core subportion should not be deleted,

a step of returning control to said step of applying thinning criteria when said step of reducing size yields a size of k greater than 2, and

a step of selecting another window following said step of returning control and following said step of deleting.

2. The method of claim 1 wherein said core subportion is of size (k-2)×

(k-2).

3. The method of claim 1, further including a step, following said step of selecting another window, of selecting another portion of said image to interact with said template in said step of applying a thinning criteria.

4. The method of claim 1 wherein said step of applying thinning criteria applies said thinning criteria to different portions of said image in parallel.

5. The method of claim 1 wherein said step of applying thinning criteria sequentially applies said thinning criteria to different portions of said image.