Image analysis – Image enhancement or restoration – Object boundary expansion or contraction
Reexamination Certificate
1999-02-22
2004-06-22
Rogers, Scott (Department: 2626)
Image analysis
Image enhancement or restoration
Object boundary expansion or contraction
C711S133000
Reexamination Certificate
active
06754396
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method for processing of a single raster element of a skeletonized binary image through the use of tiles.
2. Description of the Related Art
An image skeleton represents the basic structure of an image and is created by decomposing the widths of raster objects in the image to uniform single pixel widths. This simplifies the task of certain recognition systems from character recognition to geometrical recognition.
The current state of the art provides a process for skeletonization of an image by stripping one layer of pixels after another. The process continues until the set of pixels left form a one pixel wide line and is defined as separating two “off” areas. This process is known as raster “thinning” or “erosion.”
The problems associated with the current skeletonization processes include their relatively slow speed and extensive memory utilization requirements. In order to skeletonize the image using the current techniques, two copies of the image must be maintained in memory. For large images, this could mean storing an extraordinary, amount of data. The larger the data file, the greater the access time. Therefore, the process of data retrieval and storage increases in time with the increased amount of data stored.
Also, every pixel in the image is evaluated regardless of whether the pixel will be removed or ignored. This requires a substantial increase in the number of points to be evaluated and increases the amount of time required to complete the process.
The prior art discloses a number of devices utilizing appropriated methods and apparatus for skeletonization of images used in pattern recognition. For example, U.S. Pat. No. 3,975,709 to Beun et al. and U.S. Pat. No. 5,224,179 to Denker et al. disclose methods of image thinning or skeletonization utilizing at least 3×3 pixel by pixel analysis to thin a character of interest.
Another reference, U.S. Pat. No. 5,335,290 to Cullen et al., teaches a character recognition system by extracting run lengths for each scanline from the bit mapped representation of the document image and classifying the data as image, text or as a horizontal or vertical line. However, there is no teaching of the process of skeletonization by run length comparison which is needed to increase speed of the pattern recognition.
Still another reference, U.S. Pat. No. 4,491,960 to Brown, describes a pattern comparison system wherein a raster scan of a hand print produces a topography to be compared to a given parameters for identification.
Yet another reference, Zhang et al., “A Fast Parallel Algorithm for Thinning Digital Patterns”, discloses skeletonization via pixel by pixel comparison and removal of subsequent outer pixels for character thinning.
However, the prior art fails to address the problem of size of data files and speed of skeletonization and does not disclose, teach or even suggest the embodiments of the claimed invention.
SUMMARY OF THE INVENTION
To address the requirements described above, the present invention discloses a method, apparatus, and article of manufacture for producing a skeleton from a raster image by overlaying a plurality of tiles on the raster image, wherein each of the tiles identifies a sub-region of the raster image comprised of a plurality of pixels. The sub-regions are selectively skeletonized and then cached for subsequent access. Some or all of the cache is invalidated when one or more of the sub-regions are modified. Only those sub-regions that have been modified are re-skeletonized, on an “as needed” basis.
REFERENCES:
patent: 3975709 (1976-08-01), Beun et al.
patent: 4491960 (1985-01-01), Brown
patent: 4665441 (1987-05-01), Sakaue et al.
patent: 5224179 (1993-06-01), Denker et al.
patent: 5335290 (1994-08-01), Cullen et al.
patent: 5875267 (1999-02-01), Djakovic
patent: 58-163078 (1983-09-01), None
Carlo Arcelli, “A Condition for digital Points Removal”, Oct. 1979Signal Processing, vol. 1, No. 4, pp. 283-285.
Theo Pavlidis, “A Thinning Algorithm for Discrete Binary Images”, 1980Computer Graphis and Image Processing, vol. 13, pp. 142-157.
T. Y. Zhang et al., “A Fast Parallel Algorithm fo rThinning Digital Patterns”, Mar. 1984Communications of the ACM, vol. 27, No. 3, pp. 236-239.
Autodesk, Inc.
Gates & Cooper LLP
Rogers Scott
LandOfFree
Method of processing of a single raster element of a... 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 of processing of a single raster element of a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of processing of a single raster element of a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3315793