Image analysis – Image enhancement or restoration – Object boundary expansion or contraction
Reexamination Certificate
1998-11-25
2002-04-23
Mehta, Bhavesh (Department: 2721)
Image analysis
Image enhancement or restoration
Object boundary expansion or contraction
C382S259000, C382S242000
Reexamination Certificate
active
06377710
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to a method and apparatus for performing thinning, or skeletonization, of binary images or figures. More particularly, the invention is directed to a method implemented in a system for encoding a figure using a mid-crack boundary representation to identify the boundary contour of the figure. Then, the boundary contour of the figure is traversed while the boundary is selectively displaced inward. The boundary contour is also concurrently re-encoded based on the selectively displaced boundary.
While the invention is particularly directed to the art of image processing and skeletonization or thinning, and will thus be described with specific reference thereto, it will be appreciated that the invention may have usefulness in other fields and applications.
By way of background, thinning, or skeletonization, is a prominent step in many line drawing, document, and general image analysis systems. As will be recognized by those of skill in the art, a thinned figure is useful in a variety of different ways, depending on the specific application.
As shown in
FIG. 1
, the binary image of a pen stroke
10
, for example, is typically several pixels in width when extracted by known techniques such as edge detection or thresholding. Oftentimes, however, only the path of the stroke is of interest in analyzing the shape of the stroke. Information on this path of interest is captured by the skeleton
12
of the stroke. The skeleton
12
is typically represented as a chain of pixel locations, which is compatible with a parametric representation such as a spline, leading to shape and semantic level analysis.
Known approaches to skeletonization include distance transform, raster-based erosion—which is performed by repeatedly scanning the image with k×k masks—and contour-based erosion. Under raster-based erosion methods, each raster pass over the image requires examination of the local
8
pixel neighborhood of each pixel to determine whether that pixel lies on the outer extent of the figure. This, of course, is a primary factor in determining whether the pixel can be removed.
Contour-based erosion methods also work by testing the local neighborhoods of pixels to determine whether they can be removed at the current thinning step. However, with a contour-based method, the algorithm proceeds to traverse the boundary contours of figures and test only those pixels that are known to lie on the boundary, i.e., candidates for removal. Because contour-based erosion procedures, in general, examine fewer pixels than exhaustive raster scanning methods, contour-based erosion routines run faster on serial computers, which are not able to examine all pixel neighborhoods in parallel.
Although known contour-based erosion techniques vary, a bounding contour of a figure is most often represented in terms of center locations of pixels lying on the contour boundary. In addition to the boundary description, a bitmap representation of the figure is maintained and updated along with the boundary description. The boundary is traversed, and for each pixel on the boundary, the 8 pixel neighborhood is examined. A rule base or procedure is then consulted to determine whether the center pixel may be deleted and the boundary contour moved. These contour-based erosion techniques, however, do not efficiently thin figures because such techniques require examination of the entire 8 pixel neighborhood of a pixel being considered for erosion.
A thinning algorithm based on safe-point testing and mid-crack code tracing has been proposed in F. Y. Shih and W-T. Wong, “A New Safe-Point Thinning Algorithm Based on the Mid-Crack Code Tracing,”
IEEE Trans. on Systems, Man, and Cybernetics,
Vol. 25, No. 2, pp. 370-378 (February 1995) this proposal, thinning is treated as the deletion of “nonsafe” border pixels from the contour to the center of the object layer-by-layer and deletion is determined by masking a 3×3 weighted template and by the use of look-up tables. A major disadvantage to the system is that use of the 3×3 template requires analysis of the 8 pixel neighborhood surrounding the pixel of interest, such analysis contributing to the overall inefficiency of the Shih and Wong algorithm
The present invention provides a new and improved image processing method and apparatus for thinning binary figures based on a contour-based erosion which overcomes the above noted problems and difficulties and others. The present invention is thus an improvement over known methods.
SUMMARY OF THE INVENTION
A method and system are provided for thinning a binary figure within an image that has white and black pixels with boundaries therebetween and midpoints on such boundaries for each pixel.
In one aspect of the invention, the method and system provide for scanning the image, encoding the boundary contour of the figure, storing the encoded representation, and selectively converting black pixels to white pixels based on the encoded representation and a set of predetermined rules.
In another aspect of the invention, the scanning comprises locating a starting point on the figure, the starting point being defined as a midpoint on a horizontal boundary above a first boundary between black and white pixels encountered during the scanning.
In another aspect of the invention, the encoding includes tracing from midpoint to midpoint along the contour of the figure to generate a mid-crack chain code for the figure, the tracing commencing at the starting point and proceeding in selected directions having predetermined codes.
In another aspect of the invention, the converting includes selectively converting black pixels to white pixels along the contour of the figure to generate a target contour based on a chain code and a predetermined set of rules stored in a lookup table, wherein the rules require an examination ot fewer than 8 pixels surrounding a black pixel being considered for conversion and are based on a condition that the target contour be a boundary between a white pixel and a black pixel.
In another aspect of the invention, a plurality of figures in an image are successively and incrementally thinned.
Further scope of the applicability of the present invention will become apparent from the detailed description provided below. It should be understood, however, that the detailed description and specific examples, while indicating preferred embodiments of the invention, are given by way of illustration only, since various changes and modifications within the spirit and scope of the invention will become apparent to those skilled in the art.
REFERENCES:
patent: 4093941 (1978-06-01), Bryan et al.
patent: 4520505 (1985-05-01), Yamamoto et al.
patent: 4539704 (1985-09-01), Pastor
patent: 4574357 (1986-03-01), Pastor et al.
patent: 4777651 (1988-10-01), McCann et al.
patent: 5025314 (1991-06-01), Tang et al.
patent: 5072412 (1991-12-01), Henderson, Jr. et al.
patent: 5448263 (1995-09-01), Martin
patent: 5583949 (1996-12-01), Smith et al.
patent: 5717869 (1998-02-01), Moran et al.
patent: 5717879 (1998-02-01), Moran et al.
patent: 5754674 (1998-05-01), Ott et al.
patent: 5778092 (1998-07-01), Macleod et al.
patent: 5786814 (1998-07-01), Moran et al.
patent: 5907842 (1999-05-01), Mennemeier
patent: 5940538 (1999-08-01), Spiegel et al.
patent: 5970170 (1999-10-01), Kadashevich et al.
patent: 5978511 (1999-11-01), Horiuchi et al.
F. Y. Shih and W-T. Wong, “A New Safe-Point Thinning Algorithm Based on the Mid-Crack Code Tracing”,IEEE Trans. on Systems, Man, and Cybernetics, vol. 25, No. 2, pp. 370-378 (Feb. 1995).
Bayat Ali
Fay Sharpe Fagan Minnich & McKee LLP
Mehta Bhavesh
Xerox Corporation
LandOfFree
Method and apparatus for extracting the skeleton of a binary... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for extracting the skeleton of a binary..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for extracting the skeleton of a binary... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2860475