Image analysis – Image segmentation – Using projections
Reexamination Certificate
1994-02-14
2001-06-19
Chang, Jon (Department: 2623)
Image analysis
Image segmentation
Using projections
C382S177000, C382S289000
Reexamination Certificate
active
06249604
ABSTRACT:
This invention relates to a method of determining the boundaries of text or character strings represented in an array of image data by shape, without a requirement for individually detecting and/or identifying the character or characters making up the strings.
CROSS REFERENCE
The following related applications are hereby incorporated by reference for their teachings:
“Coarse and Fine Skew Measurement,” Wayner et al., Ser. No. 07/737,863, filed Jul. 30, 1991 now abandoned.
“Optical Word Recognition by Examination of Word Shape,” Huttenlocher et al., Ser. No. 07/796,119, filed Nov. 19, 1991 now abandoned.
“Method for Comparing Word Shapes,” Huttenlocher et al., Ser. No. 07/795,169, filed Nov. 19,1991 now abandoned.
“A Method of Deriving Wordshapes for Subsequent Comparison,” Huttenlocher et al., Ser. No. 07/794,391, filed Nov. 19, 1991 now abandoned.
INCORPORATION BY REFERENCE
The article “Performance Tradeoffs in Dynamic Time Warping Algorithms for Isolated Word Recognition”, by Myers, Rabiner, and Rosenberg, IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol. ASSP-28, No. 6, December 1980, and the book, “Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison”, by Sankoff and Kruskal, Addison-Wesley Publishing Company, Inc., Reading, Massachusetts, 1983, Chapters 1 and 4, are specifically incorporated herein by reference for their teachings.
COPYRIGHT NOTIFICATION
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owners have no objection to the facsimile reproduction, by anyone, of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
MICROFICHE APPENDIX
An appendix comprising 3 microfiche having a total of 274 frames thereon is included as part of this application.
BACKGROUND OF THE INVENTION
Text in electronically encoded documents (electronic documents) tends to be found in either of two formats, each distinct from the other In a first format, the text may be in a bitmap format, in which text is defined only in terms of an array of image data or pixels, essentially indistinguishable from adjacent images which are similarly represented. In this format, text is generally incapable of being subjected to processing by a computer based on textual content alone. In a second format, hereinafter referred to as a character code format, the text is represented as a string of character codes (e.g. ASCII code). In the character code format, the image or bitmap of the text is not available.
Conversion from bitmap to character code format using an optical character recognition (OCR) process carries a significant cost in terms of time and processing effort. Each bitmap of a character must be distinguished from its neighbors, its appearance analyzed, and in a decision making process, identified as a distinct character in a predetermined set of characters. For example, U.S. Pat. No. 4,864,628 to Scott discloses a method for reading data which circumnavigates a character image. Data representative of the periphery of the character is read to produce a set of character parameters which are then used to compare the character against a set of reference parameters and identify the character. U.S. Pat. No. 4,326,190 to Borland et al. teaches a character feature detection system for reading alphanumeric characters. A digitized binary image is used, characters images are traced from boundary points to boundary points, wherein the transitions are are defined by one of eight equally divergent vectors. Character features a subsequently extracted from the vector data to form a feature set. The feature set is then analyzed to form a set of secondary features which are used to identify the character. U.S. Pat. No. 4,813,078 to Fujiwara et al. discloses a character recognition apparatus employing a similar process, where picture change points are identified and accumulated according to direction and background density, and are used to enable more accurate identification of characters which are generally erroneously recognized. Furthermore, U.S. Pat. No. 4,833,721 to Okutomi et al. teaches a similar system, operating on character outlines, which may be employed as a man/machine interface for an electronic apparatus.
Additional references which describe alternative methods and apparatus for identification of characters within a digitized image are: U.S. Pat. No. 3,755,780 to Sammon et al. teaches a method for recognizing characters by the number, position and shape of alternating contour convexities as viewed from two sides of the character; U.S. Pat. No. 3,899,771 to Saraga et al., which teaches the use of linear traverse employing shifted edge lines for character recognition; U.S. Pat. No. 4,817,166 to Gonzales et al., which teaches the application of character recognition techniques in an apparatus for reading a license plate which includes a character alignment section and a correction section; and U.S. Pat. No. 4,566,128 to Araki, which discloses a method for compressing character image data using a divided character image to recognize and classify contours, enabling the compressed storage of the character image as a group of closed-loop line segments. In addition, U.S. Pat. No. 4,956,869 to Miyatake et al. suggests a a more efficient method for tracing contour lines to prepare contour coordinates of a figure within an image consisting of a plurality of lines.
When the electronic document has been derived by scanning an original, however, image quality and noise in its reproduction contribute to uncertainty in the actual appearance of the bitmap. A degraded bitmap appearance may be caused by a original document of poor quality, by scanning error, or by similar factors affecting the digitized representation of the image. Therefore, the decision process employed in identifying a character has an inherent uncertainty about it. A particular problem in this regard is the tendency of characters in text to blur, or merge. Most character identifying processes commence with an assumption that a character is an independent set of connected pixels. When this assumption fails, due to the quality of the input image, character identification also fails. A variety of attempts have been made to improve character detection. U.S. Pat. No. 4,926,490 to Mano discloses a method and apparatus for recognizing characters on a document wherein characters of a skewed document are recognized. A rectangle is created around each character image, oriented with the detection orientation rather than the image orientation, and position data for each rectangle is stored in a table. The rectangle is created by detecting a character's outline. U.S. Pat. No. 4,558,461 to Schlang discloses a text line bounding system wherein skewed text is adjusted by analyzing vertical patches of a document. After the skew has been determined, each text line is bounded by determining a top, bottom, left, and right boundary of the text line. U.S. Pat. No. 3,295,105 to Gray et al. discloses a scan controller for normalizing a character in a character recognition apparatus wherein a character is analyzed by determining certain character characteristics including top, bottom, right and left character boundaries. U.S. Pat. No. 4,918,740 to Ross discloses a processing means for use in an optical character recognition system wherein sub-line information is used to analyze a character and identify it. U.S. Pat. No. 4,558,461 to Schlang suggests a text line bounding system for nonmechanically adjusting for skewed text in scanned text. The skew angle of the text is then established, following which the-text lines are statistically bounded. The actual text data is then rotated according to the orientation established for conventional processing. U.S. Pat. No. 4,809,344 to Peppers et al. teaches preprocessing of character recognition so as to obtain data necessary for character recognition. Page segmentation is perf
Hopcroft Michael J.
Huttenlocher Daniel P.
Wayner Peter C.
Chang Jon
Xerox Corporation
LandOfFree
Method for determining boundaries of words in text 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 for determining boundaries of words in text, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for determining boundaries of words in text will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2451160