Method of Deriving Wordshapes for Subsequent Comparison

This invention relates to a method of recognizing 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, and more particularly, to a method of deriving a description of the shape of a word as a one dimensional signal.

The following related patent applications are hereby cross referenced and incorporated by reference for their teachings:

"Coarse and Fine Skew Measurement", Wayner et al., Ser. No. 07/737,863 filed Jul. 30, 1991, abandoned.

"Method for Comparing Word Shapes", Huttenlocher et al., Ser. No. 07/795,169, filed Nov. 19, 1991, abandoned.

"Method for Determining Boundaries of Words in Text", Huttenlocher et al., Ser. No. 07/794,392, filed Nov. 19, 1991, now U.S. Pat. No. 5,321,770.

"Optical Word Recognition by Examination by Word Shape", Huttenlocher et al., Ser. No. 07/796,119 filed Nov. 19, 1991, abandoned.

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, Mass., 1983, Chapters 1 and 4, are specifically incorporated herein by reference for their background teachings.

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.

An Appendix comprising 3 microfiche having a total of 274 frames thereon is included as part of this application.

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 defined by one of eight equally divergent vectors. Character features are 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 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 performed by simultaneously extracting a plurality of features, separation between lines, separation between characters, and separation between the lines and the characters are simultaneously performed, and a calculation time for normalizing the separated individual characters can be reduced, thereby performing preprocessing required for character recognition systematically at high speed.

OCR methods have sought to improve reliability by use of dictionary word verification methods, such as described in U.S. Pat. No. 4,010,445 to Hoshino. However, the underlying problem of accurate character detection of each character in a character string remains. The article "F6365 Japanese Document Reader" Fujitsu Sci. Tech. J., 26, 3, pp. 224-233 (October 1990) shows a character reader using the steps of block extraction, skew adjustment, block division, adjacent character segmentation, line extractions, and character recognition by pattern matching, with dictionary checking, and comparison.

It might be desirable, to identify a set of characters forming a word or character string as such, as shown, for example, in U.S. Pat. No. 2,905,927 to Reed, in which for a text string, a set of three scans across the text, parallel to its reading orientation are employed, each scan deriving information about transitions from black to white across the scan. When values derived from the three scans are reviewed, the information derived from the combination of three scans forms a unique identifier for a word that may then be compared to preset values for identification purposes. Two problems are noted with this method, first, that the image information or bitmap is lost in the conversion, and secondly, the process is rather gross in nature and depends heavily upon the uniform nature of the character in the image scanned. Loss of the image bitmap is a characteristic of the conversion of a bitmap containing textual information to representative character codes. U.S. Pat. No. 4,155,072 to Kawa suggests a similar arrangement, operable to produce a set of values representative of the leading and trailing edges of the character. From this information a quadratic correlation function is used for comparison to standard character patterns.

In addition to an OCR system operating on printed or typed textual images, numerous references deal with recognition of handwritten text which has been converted into an electronic representation. U.S. Pat. No. 4,731,857 to Tappert shows processing a word with the segmentation and recognition steps combined into an overall scheme. This is accomplished by a three step procedure. First, potential or trail segmentation points are derived. Second, all combinations of the segments that could reasonably be a character are sent to a character recognizor to obtain ranked choices and corresponding scores. Finally, the recognition results are sorted and combined so that the character sequences having the best cumulative scores are obtained as the best word choices. U.S. Pat. No. 4,764,972 to Yoshida et al. suggests a recognition system for recognizing a plurality of handwritten characters. A first memory is used to store isolated characters, and a second memory is used to store information, including interstroke character information, for connecting isolated characters. Finally, U.S. Pat. No. 4,933,977 to Ohnishi et al. discloses a method for identifying a plurality of handwritten connected figures, including identifying and prioritizing branches of the connected figures. Branches having the lowest priority within a recognition block are erased until a recognizable figure is obtained. From the recognition block extends a second block which is analyzed in the same fashion until a second figure is recognized.

The choice of entire words as the basic unit of recognition, has also been considered in signature recognition, where no attempt is made to maintain characters as having separate identities, and is suggested by U.S. Pat. No. 3,133,266 to Frishkopf, which still relies on subsequent feature identification methods for identifying characteristics of the image of the character. Signature recognition has also used comparison techniques between samples and known signatures, as shown in U.S. Pat. No. 4,495,644 to Parks et al. and U.S. Pat. No. 4,701,960 to Scott which suggest that features plotted on x-y coordinates during the signature process can be stored and used for signature verification.

U.S. Pat. No. 4,499,499 to Brickman et al. suggests a method of image compression in which the bitmap representation of a word is compared to a bitmap representation dictionary through superposition of the detected word over the stored word to derive a difference value which is compared to a reference value indicating a degree of certainty of a match. Neither OCR methods which seek to encode a bitmap into characters processable as information by computer or bitmap methods for manipulation of images have proven completely satisfactory for all purposes of text manipulation or processing.

In U.S. patent application Ser. No. 07/459,026, filed Dec. 29, 1989, now U.S. Pat. No. 5,167,016, entitled "Changing Characters in an Image", by Bagley et al, a method is shown for changing characters in text appearing in an image. The character to be changed is identified and if the changed version of the image includes a character not in the text prior to the change, a shape comparing process is used to identify a word containing the newly required character, copy the character, and insert it into its new position. In U.S. patent application Ser. No. 07/459,022, filed Dec. 29, 1989, abandoned, entitled "Editing Text in an Image", by Bagley et al, a method is shown for identifying and changing characters in text appearing in an image.

Alternative modes of expressing character recognition are known, such as U.S. Pat. No. 3,755,780 to Sammon et al., which discloses a method of recognizing characters wherein a shape of the character is represented by the number, position and shape of the character's contours. The number and position of the contour allow each character to be sorted according to these values. U.S. Pat. No. 4,903,312 to Sato discloses a character recognition system with variable subdivisions of a character region wherein a character is read to form a binary image. The binary image is then assigned a plurality of directionality codes which define a contour of the binary image. The binary image is then divided into a number of subregions, each of which has an equal number of directionality codes. A histogram of the directionality codes is calculated for each subregion. The histogram of the binary image is then compared with a number of known character contour histograms. Also, U.S. Pat. No. 4,949,281 to Hillenbrand et al. teaches the use of polynomials for generating and reproducing graphic objects, where the objects are predetermined in the form of reference contours in contour coordinates. Individual characters are represented as a linear field of outside contours which may be filtered, smoothed, and corner recognized before being broken into curve segments. Subsequently, the character is stored as a series of contour segments, each segment having starting points, base points and associated reference contours.

Certain signal processing techniques for comparing known signals to unknown signals are available if the word can be expressed in a relatively simple manner. U.S. Pat. No. 4,400,828 to Pirz et al. discloses a spoken word recognizor wherein an input word is recognized from a set of reference words by generating signals representative of the correspondence of an input word and the set of reference words and selecting a closest match. The word recognizor is used with a speech analysis system. A normalization and linear time warp device is disclosed. The input word and the set of reference words are processed electrically to determine correspondence. U.S. Pat. No. 4,977,603 to Irie et al. teaches an arrangement for pattern recognition utilizing the multiple similarity method, capable of taking structural features of a pattern to be recognized into account, so that sufficiently accurate pattern recognition can be achieved even when the pattern may involve complicated and diverse variations. The method includes the steps of: counting a number of occurrences, within each one of localized regions which subdivides a pattern to be recognized, of local patterns indicating possible arrangements of picture elements; deriving a vector quantity indicating distribution of black picture elements which constitute the pattern, from the numbers of occurrences of the local patterns; calculating multiple similarity, defined in terms of square of inner product of the vector quantity and one of prescribed standard vectors representing standard patterns; and recognizing the pattern by identifying the pattern with one of the standard pattern whose corresponding standard vectors gives the maximum values for the multiple similarity. "An Efficiently Computable Metric for Comparing Polygon Shapes," by Arkin, Chew, Huttenlocher, Kedem and Mitchell, Proceedings of the First Annual ACM-SIAM Symposium on Discrete Mathematics, January 1990 (pp. 129-137) suggests that metrics can be established for shape matching.

All of the references cited herein and above are incorporated by reference for their teachings.

In accordance with the invention, there is provided a method for representing a word, character or symbol string represented in image data, by shape, without a requirement for individually detecting and/or identifying the character or characters making up the string.

In accordance with one aspect of the invention, a method of forming a word shape is provided, from which information about a symbol string may be derived, including the steps of: a) identifying the limits of an image of a symbol string; b) identifying a reference with respect to the symbol string; c) deriving a set of one dimensional measurements about at least a portion of the shape of the symbol string with respect to the reference.

In accordance with another aspect of the invention, once orientation of a symbol string within an image is established, line spacing and word or symbol string spacing is established. Each discrete symbol string may then be surrounded by a bounding box, defining an approximation of the limits of the image of the symbol string. A reference line may then created extending through the symbol string image. Using these references, a series of measurement may be made with respect to the references and the symbol string, which define the shape of a portions of the symbol string. Because the set of measurement derived can be expressed in terms of position along a horizontal axis, the signal can be considered a single, independent variable signal.

In an alternative mode of expressing the present invention, considering image data i(x,y), which in one common case could be an array of image data in the form of a bitmap, the image of a symbol string is identified, and a boundary thereabout defined. From i(x,y), an edge signal e(x,y), which represents the edges of i(x,y) detected within the closed boundary, is derived. The edge signal is augmented by adding additional data to i(x,y) so that e(x,y) is a signal e'(x,y) defined over its entire domain with respect to an independent variable within the closed boundary. One, two, or more signals may be derived from e'(x,y) which are each one dimensional signals g'(t) where g is the signal of the independent variable t which is a reference frame dependent parameter.

In accordance with still another aspect of the invention, a method of forming a word shape from an image of text is provided, from which information about a discrete symbol string therein may be derived, including the steps of: a) detecting the skew of text within the image with respect to a reference; b) determining within the text image, upper and lower limits of any lines of text; c) operating on the image to distinguish between inter-symbol spacing and inter-string spacing; d) using said determined text line limits and said determined inter-string spacing to define limits of a symbol string; e) establishing a reference with respect to the image of the symbol string and the orientation of the image; and f) making a series of measurement with respect to the image and the reference, said series of measurements defining a shape or curve from which information about the symbol string may be derived.

The present invention seeks to avoid the problems inherent in OCR methods. Specifically, the signal to noise ratio inherent in image derivation, or the imaging process, is relatively small for a character, but relatively large compared to a larger character string. Moreover, word-to-word spacing tends to be larger than character to character spacing, and therefore, allows improved isolation and therefore identification of character strings as compared to identification of characters. OCR methods also tend to require several correct decisions about aspects of a character preparatory to a correct identification, including identification of portions of the character as ascenders, descenders, curves, etc., all of which are fallible. Identification by word shape in accordance with the invention, initially requires derivation of a signal representative of the word shape, and comparison of the derived signal to known word shape signals. Assumptions about the word are not made until the comparisons occur, thereby eliminating the impact of invalid assumptions which may erroneously impact subsequent comparisons and decisions. Furthermore, the present invention has the added advantage that the representative derived signal is generally invertible without a significant loss of information content.

In examining potential uses of computer processed text, it has been determined that, at least in certain cases, deriving each letter of the word is not required for processing requirements. Thus, for example, in a key word search of a text image, rather than converting, via OCR techniques, each letter of each word, and subsequently determining from the possibly flawed character coding whether one or more key words are present, a computer might instead generate and compare the shapes of words with the shape of the keyword, and evaluate whether the key word is present by shape. The output of such a system would most likely present an indication of the presence of the key words to an accuracy acceptable to a user. Furthermore, it is believed that the described method will have processing speed advantages over OCR methods.

The probability of an incorrect determination of a letter by OCR methods may be relatively low, however, the probabilities are multiplicatively cumulative over an entire word. Hence, using OCR to convert words into character code strings, prior to searching for or recognizing the words may result in considerable error. The present invention is directed towards implementing word recognition in a manner similar to that which humans use while reading or skimming a text passage. Furthermore, when using OCR the bitmap image of the letter is converted to a character code, and the bitmap becomes irretrievable for examination by a user. However, in the described word shape process, several advantages over this method are noted. First, the bitmap is not irretrievably lost, and a reasonable representation of the bitmap remains so that a user may examine a reconstructed bitmap for word determination, if desired. Secondly, by utilizing complete words, each letter has the context of the word to assist in the word's comparison to other word shapes. The presence of a poorly formed letter in a word only minimally affects the total identifiability of the word shape signal, by slightly increasing the difference value between two compared signals. Thirdly, in small words, which have the greatest probability of false recognition, it is noted that such words tend to carry relatively little information content. This is the reason that some indexing schemes, such as keyword searching, ignore the most common words in language as noise, with respect to the meaning of a text passage. Accordingly, the words in which errors are most likely to occur are the words which are of least importance in an information content sense. By contrast, the probability of failed detection is highest in OCR for longer words, i.e., words carrying the most information content, since the error is cumulative over the length of the word.

OCR methods convert from a bitmap to a representative character code, thereby losing the informational content of the bitmap. In general, the process is not reversible to obtain the original bitmap from the character code. However, identification of words based on shape, as described in accordance with the present invention, tends to retain bitmap information, thereby enabling a reasonable reconstruction of the bitmap from the single variable signal. Hence, a significant portion of the bitmap information is retained by the single variable signal used to represent the shape of the selected text or character string.

Other objects and advantages of the present invention will become apparent from the following description taken together with the drawings in which:

FIG. 1A shows a generalized system diagram of an image processing system in which the present invention would find use;

FIG. 1B shows a block system diagram of the arrangement of system components forming one embodiment of the inventive word shape recognition system;

FIG. 2 shows an image sample of example text over which the inventive process will be demonstrated;

FIG. 3 is a copy of a scanned image of the example text;

FIGS. 4A, 4B and 4C graphically illustrate the process used to determine the angle at which the example text is oriented in the image sample prior for further processing, while FIG. 4D shows graphs of the responses taken from the example text, which are used to determine the angle at which the example text is oriented in the image sample prior to further processing;

FIGS. 5A and 5B respectively show the derivation and use of a graph examining the sample image of the example text to determine baselines of text within the image;

FIGS. 6A and 6B are flowcharts illustrating the procedures executed to determine the baselines shown in FIG. 5A;

FIG. 7 shows the scanned image of the example text with baselines indicated thereon after derivation from the data shown in FIGS. 5A and 5B;

FIG. 8 is a flowchart illustrating the steps used in the application of a median filter to the image of FIG. 2;

FIG. 9 is an enlarged pictorial representation of a portion of the image of FIG. 2, illustrating the application of the median filter;

FIG. 10 demonstrates the resulting image after application of a median filter, a process known herein as blobifying, to the scanned image of the example text, which tends to render character strings as a single set of connected pixels;

FIG. 11 shows a subsequent step in the process, in which lines of white pixels are added to the blurred image to clearly delineate a line of character strings from adjacent lines of character strings;

FIG. 12 is a flowchart illustrating the steps required to add the white lines of FIG. 11;

FIGS. 13A and 13B are flowcharts representing the procedure which is followed to segment the image data in accordance with the blurred image of FIG. 10;

FIG. 14 shows the sample text with bounding boxes placed around each word group in a manner which uniquely identifies a subset of image pixels containing each character string;

FIGS. 15A and 15B illustrate derivation of a single independent value signal, using the example word "from", which appears in the sample image of example text;

FIG. 16 illustrates the resulting contours formed by the derivation process illustrated in FIGS. 10A, B;

FIG. 17 illustrates the steps associated with deriving the word shape signals;

FIGS. 18A, 18B, 18C and 18D illustrate derivation of a single independent value signal, using the example word "from";

FIGS. 19A, 19B, 19C and 19D illustrate derivation of a single independent value signal, using the example word "red", which does not appear in the sample image of example text;

FIG. 20 shows a simple comparison of the signals derived for the words "red" and "from" using a signal normalization method;

FIGS. 21A, 21B, and 21C illustrate the details of the discrepancy in font height, and the method for normalization of such discrepancies;

FIG. 22 is a flowchart detailing the steps used for one method of determining the relative difference between word shape contours;

FIG. 23 is a flowchart detailing the steps of a second method for determining the relative difference between word shape contours; and

FIGS. 24A and 24B are respective illustrations of the relationship between the relative difference values calculated and stored in an array, for both a non-slope-constrained and a slope-constrained comparison.

The Appendix contains source code listings for a series of image manipulation and signal processing routines which have been implemented to demonstrate the functionality of the present invention. Included in the Appendix are four sections which are organized as follows:

Section A, beginning at page 1, comprises the declarative or "include" files which are commonly shared among the functional code modules;

Section B, beginning at page 26, includes the listings for a series of library type functions used for management of the images, error reporting, argument parsing, etc.;

Section C, beginning at page 42, comprises numerous variations of the word shape comparison code, and further includes code illustrating alternative comparison techniques than those specifically cited in the following description;

Section D, beginning at page 145, comprises various functions for the word shape extraction operations that are further described in the following description.

Referring now to the drawings where the showings are for the purpose of illustrating a preferred embodiment of the invention, and not for limiting same, FIG. 1A shows a generalized image processing system, which covers numerous situations in which the present invention may find advantageous use. Generally, a source image may be derived from a source image derivation system 2, which may be a scanner, facsimile device, or storage system. The source image is forwarded to a computer processing device 4 which may be any of several well known devices including the inventive device described herein. In response to commands entered at user interface 6, processing device 4 produces an output at an output device 8, which may be a printer, display, facsimile device or other storage device. In essence, as is shown in the upper portion of FIG. 1, an input document is directed into a system and an output document is retrieved from it.

In the following description, an image is generally described as an image bitmap, where an image is represented as a plurality of image signals. These signals, commonly referred to as pixels, are typically denoted as black when intended to represent a corresponding mark or active position on a document from which they were produced. However, these constructs have been used for to enable the description of the present invention, and are in no way intended to limit the domain of such to that of black-and-white or binary images. Rather, the present invention is generally applicable across a broad range of image representation techniques.

FIG. 1B, shows a system which embodies the present invention for deriving, defining, and comparing words in terms of their shapes. It will, of course, be recognized that each element of the system may be many devices, or may simply be a program operated within a single device. Beginning with an input bitmap 10, whose source is indeterminate, and not part of the invention, a bitmap of an image is initially directed to a segmentation system 12, in which words, or character strings, or other multi-character units of understanding, will be derived. Initially, the image bitmap passes through skew detector 14, which determines the angle of orientation of text in the image. Using information about the orientation of the image, and the image itself, at text baseline processor 16, toplines and baselines of the text are determined, so that upper and lower boundaries of lines of text within the image are identified. At median filter 18, the function referred to as "blobify" is performed, which operates on the image so that each word group in a line may be treated as a single unit. As used herein, "word", "symbol string" or "character string" refers to a set of connected alphanumeric or punctuation elements, or more broadly, signs or symbols which together form a single unit of semantic understanding. It will be appreciated that these terms may also be used to refer to the images thereof. Such single units of understanding are characterized in an image as separated by a spacing greater than that which separates the elements, signs or symbols forming the unit. To the blobified image, a set of white lines are added at block 20, to clearly separate adjacent lines of text. The white lines are based on baseline determinations provided by processor 16. Using this information, i.e., the blobified words, which are clearly separated from adjacent words and words in adjacent lines, a bounding box is defined about the word at block 22, thereby identifying and enclosing the word.

Thereafter word shape signal computer 24 derives a word shape signal representing the individual words in the image, based on the original image and the bounding box determinations. This information is then available for use at a word shape comparator 26, for comparing word shape signals representative of known words from a word shape dictionary 28, with the as yet unidentified word shape signals. In an alternative embodiment word shape comparator 26 may be used to compare two or more word shapes determined from image 10. More importantly, word shape comparator 26 is not limited to the comparison of word shapes from unrecognized strings of characters to known word shapes. In a simplified context, comparator 26 is merely an apparatus for comparing one word shape against another to produce a relative indication of the degree of similarity between the two shapes.

In general, a method accomplishing the invention includes the following steps. Once orientation of the image is established and line spacing and word group spacing is established, each word can be surrounded by a bounding box. A reference line is then created extending through the character string image. The reference line may be a block having a finite thickness ranging from two-thirds of the x height to one-third of the x height, or in fact it may have a zero width. At the resolution of the image, the distance from the reference line to the upper edge of the text contour or bounding box is measured in a direction perpendicular to the reference line. Similarly, measurements may be made from the reference line to the lower bounding box edge or to the text contour along the lower portion of the word, whichever is closer. Because the set of values derived computationally can be expressed in terms of position along the horizontal axis versus length, the signal can be considered a single independent variable or one dimensional signal. Either or both of these sets of values may be used to describe the word shape. Additionally, although possibly less desirable, it is well within the scope of the invention to measure the distance of a perpendicular line drawn from the top of the bounding box or the bottom of the bounding box, to the first contact with the word or the reference line, as desired.

With a system and process for word shape derivation given, the invention may also be considered mathematically. Considering image data i(x,y), which in one common case could be an array of image data in the form of a bitmap, a character set is identified in one of many methods, perhaps as described above, which defines a boundary enclosing the selected symbol string within a subset of the array of image data. From i(x,y), an edge signal e(x,y), which represents the edges of i(x,y) detected within the closed boundary, is derived. The edge signal is augmented by adding additional data to i(x,y) so that e(x,y) is a signal e'(x,y) defined over its entire domain with respect to a single dimension or variable within the closed boundary. One, two, or more signals may be derived from e'(x,y) which are each one dimensional signals g'(t), where g is a function of parameter which is a reference frame dependent parameter.

It is important to realize that the mathematical process used for the derivation of the one dimensional signal is essentially reversible up to the information it contains, e.g., a bitmap may be reconstructed from the upper and lower bitmap contours, as illustrated in FIG. 16. It will be noted that if the reference has a finite thickness and is therefore taken out of the image, that that portion of the image is not identifiable, however, if it has a zero width the information still remains.

A recognition dictionary, or look up table of word shapes, can clearly be created through use of the described process. The process can be operated on using either scanned words as the source of the information, or in fact, they can be computer generated for a more "perfect" dictionary.

To demonstrate the process of the invention, at FIG. 2, a sample image, taken from a public domain source is shown, having several lines of text contained therein. FIG. 2 demonstrates approximately how the image would appear on the page of text, while FIG. 3, shows a scanned image of the page, which demonstrates an enlargement of the image of a bitmap that would present problems to known OCR methods. Looking at, for example, the image of the word 50 "practitioner" in the first line of the text image, it may be seen that several of the letters run together. Also, at the lower left hand portion of the image, circled and numbered 52, noise is present. Looking at the word "practitioner's", circled and numbered 54, the running together of a punctuation mark and a letter is further noted.

With reference again to FIG. 1B, in one possible embodiment of the invention, skew detector 14, may be implemented as described in the U.S. patent application for "Coarse and Fine Skew Measurement", Ser. No. 07/737,863 by Wayner et al., abandoned, which has been previously incorporated by reference. A general method for determining the orientation of the text lines in the image, looks at a small number of randomly selected edge pixels (defined as a black pixel adjacent to at least one white pixel), and for each edge pixel considers, at FIG. 4A, a number of lines, 56a, 56b, 56c being examples, extending from the pixel at evenly spaced angular increments over a specified range of angles. The edge pixels are selected randomly from the set of all image pixels by the function RandomEdgePixel() (Appendix, page 243). FIGS. 4A (see lines 56a, 56b, 56c), 4B (see lines 58a, 58b, 58c) and 4C (see lines 60a, 60b, 60c) represent a series of increasingly smaller angular ranges over which the above mentioned technique is applied to illustrative edge pixels to accurately determine the angular orientation of the text within the image. Subsequent to finding edge pixels and defining the lines, skew detector 14 traces the path of each line, determining the lengths, in pixels, of strings of successive black pixels which are intersected by the line. Upon reaching the image boundary, an average black pixel string length is calculated by summing the lengths of the individual strings, and dividing the sum by the total number of distinct strings which were found. This operation is carried out for all the lines, thereby arriving at an average black pixel string length for each line extending from the selected edge pixel. These lengths are plotted on FIG. 4D as curve A, showing minima at approximately 0 and 3.14 radians. Curve A is a graphical representation of the summation/averaging function over each of a series of angled lines extending from the edge pixel, and spread over a range from 0 to 2.pi. radians. Once a first minimum has been located, verification of the minimum (in the example, approximately 0 radians) is achieved by determining whether a second minimum exists at approximately n radians from the first minimum. Upon verifying the existence of a second minima (in the example, approximately 3.14 or .pi. radians), a coarse skew angle is identified. Subsequently, it is necessary to more closely determine the skew angle of the text. This is accomplished by utilizing a number of lines which extend from a randomly selected edge pixel, where the lines differ by smaller angular increments, and the angular range is centered about the coarse skew angle. However, the fine skew angle may be determined by analyzing the total number of black pixels contained along a predetermined length of the lines. More specifically, the number of pixels over a unit distance are plotted as curve B on FIG. 4D, and the fine skew angle is determined by identifying the maxima of the curve. In other words, the point of the curve where the highest concentration of black pixels per unit line length exists, more accurately represents the angle of the text lines in the image. As shown by curve B, this results in a fine skew angle of approximately 0 radians, where the line intersects with the most black pixels along its length, and therefore is representative of the closest angle of orientation that needs to be determined.

Alternatively, the skew angle may be determined as indicated by the NewFine() function (Appendix, page 245), which determines the skew angle using multiple iterations of the procedure described with respect to the fine angle determination. As indicated by FIGS. 4A, 4B, and 4C, each iteration would also use lines covering an increasingly smaller angular range, until a desired skew angle accuracy is reached. In the implementation illustrated by FIGS. 4A, 4B, and 4C, the desired accuracy is achieved by a series of three iterations, each using a series of 180 distinct angles about the selected edge pixel.

In the next process step, illustrated in the graphs of FIG. 5A and FIGS. 5B, text baseline processor 16 identifies the characteristic lines, upper topline and lower baseline, of each line of text. The process steps executed by text baseline processor 16 are illustrated in detail in FIG. 6A and 6B. The histogram of FIG. 5A, shown to the left along the image, is derived by examining lines, at the resolution of the image, and oriented parallel to the skew orientation of the image, as defined by the previously determined skew angle. These parallel lines spanning the image are used to determine the number of black pixels intersected by each of the lines. Along lines passing through inter text line spaces, no black pixels should be intercepted, while along lines through the text, large numbers of black pixels should be intercepted.

More specifically, the function BaseLines(), (Appendix page 160), first finds the coordinates of a "main" line, block 142, constructed through the center of the image and perpendicular to the text lines, as determined by the skew angle passed to the function as shown by block 140. Next, Line Engine Procedure 144 is executed, where by proceeding along the main line from one end to the other, at a series of points along the main line, perpendicular branch lines are constructed which extend outwardly from the main line for a fixed distance, block 146. Along the branch lines, the number of black vertical edge pixels are counted, block 148, and the number of black pixels intersected by the lines are counted, block 150, and summed for the opposing pairs of lines, block 152. Black vertical edge pixels, as counted by block 148, are defined as black pixels having a white neighboring pixel at either the upper or lower neighboring pixel position. LineEngine()procedure 144 is repeated until all points, and associated branch lines, along the main line have been processed, as determined by decision block 154. An x-height value may be returned from this procedure, which will subsequently be used by the word shape computer 24.

Subsequently, the counts for all the branch lines are analyzed to determine the branch line pairs having the highest ration of black vertical edge pixels to black pixels. In general, those lines having the highest percentages would correspond to lines passing along the upper and lower edges of the characters which form the text lines. As illustrated in the enlarged view of FIG. 5B, a definite distinction exists between those branch lines having a high vertical edge pixel ratio, line 82, and those having a low ratio, line 84. Application of a filter mask and comparison of the maximum peaks within the mask enables the identification of those lines which represent the text toplines and baselines, for example, line 82. The process is implemented in the maxFilter.c module, beginning at line 57, the code for which is also incorporated in the newBaselines.c module at line 274, page 214. Baseline determination is described in further detail in a copending U.S. Patent Application, for a "Method for Determining Boundaries of Words in Text", Huttenlocher et al., (Attorney Docket No. D/91161), which has been previously incorporated herein by reference. An additional test may also be applied to the histogram operation of step 150. This added test, a boolean test, may be used to assure that a minimum run of black pixels was detected during the analysis of the line. For example, a flag, which is cleared at the start of each branch line analysis, may be set whenever a series of five sequential black pixels are detected along the line. This test would assure that small noise or image artifacts are not recognized as baselines due to a high vertical edge pixel ratio.

As an alternative method, it is possible to utilize the total number of black pixels lying along the branch lines to determine the locations of the baselines. Using histogram curve BL, which represents the number of black pixels counted along the branch lines, it is possible to determine which branch lines have the most black pixel intersections. Applying a threshold of the maximum allows the determination of the upper and lower characteristic line pairs for each text line. Hence, the rising and falling portions of the histogram curve BL, constitute the characteristic lines of the text, and the threshold would be used to specifically identify the localized maxima surrounding an intervening minima, thereby enabling identification of the baseline positions which would be used for further processing. More importantly, this alternative approach, illustrated as step 162, may be utilized to identify the upper and lower baselines of a baseline pair, based upon the slope of the BL histogram curve. It is important to note that there is little additional processing associated with the identification step as the histogram information was collected previously during step 150. Once the preliminary characteristic line or baseline pairs are identified, block 162, a verification step, block 164, is executed to verify that the baseline pairs are separated by more than a minimum distance, the minimum distance being established by calculating the average line pair separation for all line pairs in the image. After verification, the valid baseline information is stored by output block 166 for later use by the white line addition and segmentation blocks, 18 and 20, respectively.

An important advantage of these baseline determination methods, are that they are highly insensitive to noise or extraneous marks in the interline space. FIG. 7 shows the result of the baseline determination on the example image of the sample text, showing that baseline pair, baseline and topline B.sub.n and B.sub.n ', respectively, have been located on the image, indicating those portions of the image in which a predominant portion of the text occurs. While some portions of the character ascender strokes are outside the baselines, no detriment to the remainder of the process is noted. Of course, a smaller threshold value might enable the system to capture more of the ascending strokes.

With reference again to FIG. 1B in conjunction with FIGS. 8 and 9, the next process step is a word group isolation step. A filter 18 is applied to a copy of the image which results in an image that tends to render the word into blobs distinguishable from one another. The filter is applied with a small window, to each area, to render as black those areas that are partly black. As shown in FIG. 8, the blobify function (Appendix page 165) first initializes mask variables which establish the mask size and angle, block 180, and then processes the upper scanline to initialize the data array, block 182. Median filtering is accomplished by sequentially moving the mask window through the image, blocks 184 and 186, and whenever the number of black pixels appearing in the window exceeds a threshold value, the target pixel, about which the window is located, is set to black. FIG. 9, which illustrates some examples of the filter process, has a mask window 200 placed over a portion of the image. For example, with a twenty percent threshold and a generally rectangular mask having twenty-one pixels, arranged at an angel approximately equal to the skew determined for the text, the result of filtering in window 200 would be the setting of pixel 204 to black. Similarly, window 206, which primarily lies within the intercharacter spacing between the pixel representations of the letters "r" and "o", would cause pixel 208 to be set to black. On the other hand, window 210, which lies in the region between word groups, would not have a sufficient number of black pixels present within the window to cause pixel 212 to be set to black. The size, shape and orientation of mask window 200 is optimized to reduce the filling in between text lines, while maximizing the fill between letters common to a single word.

As illustrated by FIG. 10, the result of the median filtering is that the relatively small spacing between characters in a word generally becomes inconsequential, and is filled with black pixels. Words become a single connected set of pixels, i.e., no white spaces completely separate characters in a single word. However, the relatively large spacing between character strings or between words, is a larger space outside of the ability of the filter to turn into black, and therefore serves to distinguish adjacent symbol strings. With reference now to FIGS. 7 and 10, it can be seen that the first two words of the sample text, "A" and "practitioner" have been "blobified", as this process is referred to, so that, for example, the "p" of "practitioner" is no longer separated from the "r" of that word. (Compare, FIG. 3). Once again, despite the blobifying or blurring of characters, "A" and "practitioner" remain as discrete blobs of connected symbols, or words.

With reference again to FIG. 1B, as an adjunct to this step, white line addition 20, superimposes upon the blobified image of FIG. 10 a series of white pixel lines to make certain that lines of text are maintained separately from adjacent lines of text (i.e., no overlapping of the filtered text lines). With reference to FIGS. 10 and 11, noting the circled areas 258 and 258', a combination of an ascender and descender has resulted in an interline merging of two words. The text line overlap illustrated in area 258 of FIG. 10 is exactly what is eliminated by superimposing the white lines on the blobified or filtered image.

This superposition of white lines operation, the outcome of which is illustrated by FIG. 11, is carried out by the process illustrated in FIG. 12 as executed in the DrawMiddleLines() function (Appendix page 233). Generally, white lines WL are added to the image, approximately halfway between adjacent baseline and topline pairs, to assure that there is no cross-text line blobifying. Once again, FIG. 11 shows the result of white line addition to the blobified image of FIG. 10.

Referring now to FIG. 12, white line addition block 20 begins by initializing variables in step 280 and subsequently reads in the topline location from the baseline information of the first text line. The topline information is discarded, block 282, and the next baseline and topline locations are popped from the storage stack or list, blocks 284 and 286, respectively. With respect to the image, this baseline-topline pair respectively represents the bottom and top of adjacent text lines. Next, at step 288, the point lying at the center of the pair is located to provide a starting point for the white lines which are drawn from the center of the image in an outward direction. The endpoints of the white lines are calculated in step 290, using the skew angle determined by skew detector 14 of FIG. 1B. White lines are drawn or superimposed on the blobified image at step 292, and the process is continued until all text lines have been effectively separated, as controlled by test block 294.

With reference again to FIG. 1B, as a result of the blobify or median filtering, the position of bounding boxes about each connected set of pixels formed in the blobify step may be determined. Bounding boxes are placed only about those connected components or words that are in a text line lying between the superimposed white lines. The bounding boxes are placed at the orientation of the text line, by identifying the extreme points of each group of connected pixels in the direction of the text line, and in the direction orthogonal to the text line, as opposed to the image coordinate system. This operation is performed by the function FindBorders(), (Appendix, page 172). Generally, the FindBorders function steps through all pixels within the image to find the bounding boxes of the connected characters (Paint Component), to determine the coordinates of the upper left corner of each box, as well as the length and width of the box.

Referring now to FIGS. 13A and 13B, which detail the FindBorders() procedure, segmentation step 22 begins by placing a white border completely around the filtered image, step 300. This is done to avoid running outside the edge of the array of image pixels. Next, pixel and line counters, x and y, respectively, are initialized to the first pixel location inside the border. Calling the ReadPixel procedure, block 304, the pixel color (black or white) is returned and tested in block 306. If the pixel is white, no further processing is necessary and processing would continue at block 322. Otherwise, the PaintComponent() procedure (Appendix, page 171) is called and begins by storing the location of the black pixel in a queue, block 308. Subsequently, in a copy of the image, the pixel is set to white and the boundaries of the box, surrounding the connected pixels or components, are updated, blocks 310 and 312, respectively. Next, adjoining black pixels are set to white, block 314, and the locations of the black pixels are added to the end of the queue, block 316. At block 318 the queue pointers are tested to determine if the queue is empty. If not empty, the next pixel in the queue is retrieved, block 320, and processing continues at block 312. Otherwise, if the queue is empty, all of the connected black pixels will have been set to white and the box boundaries will reflect a box which encompasses the connected components. Subsequently, the boundaries of the box which encompasses the word segment are verified and may be adjusted to an orthogonal coordinate system oriented with respect to the skew of the text lines, block 322.

It will no doubt be apparent here that while finding each text line is an integral part of the described method, and serves to make the present embodiment more robust, other methods of deriving the information acquired by that step are possible. The primary use of the text line finding function is a) to determine x-height, and b) define the white line addition for separating interline blobs. Certainly this step may be removed, with a sacrifice in robustness, or other means of deriving the necessary information may be available.

The looping process continues at block 324 which checks pixel counter x to determine if the end of the scanline has been reached, and if not, increments the counter at block 326 before continuing the process at block 304. If the end of the scanline has been reached, pixel counter x is reset and scanline counter y is incremented at block 328. Subsequently, block 330 checks the value of scanline counter y to determine if the entire image has been processed. If so, processing is completed. Otherwise, processing continues at block 304 for the first pixel in the new scanline.

Thus, as shown in FIG. 14, for the word "practitioner" the extremities of the connected character image define the bounding box. Once bounding boxes have been established, it is then possible at this step, to eliminate noise marks from further consideration. Noise marks are determined: 1) if a bounding box corner is outside the array of image pixels (Appendix, page 171); 2) if a box spans multiple text lines in the array (Appendix 229), or lies completely outside a text line; 3) if boxes are too small compared to a reference .epsilon., in either or both longitudinal or latitudinal directions, and accordingly are discarded. Noise marks 70 and 72 and others will be not be considered words. The OnABaseline() function (Appendix, page 229) is an example of a function used to eliminate those boxes lying outside of the baseline boundaries.

With reference again to FIG. 1B, at word shape computer 24, a signal representing the image of a word, or at least a portion thereof, now isolated from its neighbors, is derived. The derived signal is referred to as a word shape contour. The shape contour for each word is determined using the MakeShell() function (Appendix, page 228). As illustrated in FIG. 15A, this function first moves along the top of each bounding box, and starting with each pixel location along the top of the box, scans downward relative to the page orientation, until either a black pixel, or the bottom of the box, is reached. A record of the set of distances d between the top of the box and the black pixel or box bottom is maintained. The set of distances d, accumulated over the length of the box, constitutes the top raw contour of the word shape. Subsequently, a bottom raw contour is produced in a similar manner as illustrated in FIG. 15B, for the same word depicted in FIG. 15A, by sequentially moving across the bottom of the box, and looking in an upwards direction, for either the first black pixel or the top of the bounding box.

With reference now to FIG. 17, at block 100 which preferably operates on the actual image as opposed to the filtered image, which could be used in this step, one or more reference lines are established through each word. In other terms, the data representing the symbol string is augmented, so that it is defined over the range of the symbol string. In one embodiment, a blackout bar, which may have a finite thickness or a zero thickness is constructed through the word, preferably having an upper limit or reference line at approximately two thirds of the x height, and a lower limit or reference line at approximately one-third of the x height (which was determined at the baseline determination step). At contour calculation 102, a set of measurements is derived, for the distance d between the upper or lower edge of the bounding box, and the word, or the nearer of the reference lines closer edge of the black out bar. The calculations measurements are made at the resolution of the image. With reference to FIG. 18A, where the calculations measurements are illustrated pictorially, it can be seen that the reference lines serve to allow the signal that will ultimately be derived from this step to be defined at every sampling position over the length of the word. In a preferred one embodiment, the calculations measurements of d are actually generated from the contour data derived in accordance with FIGS. 15A, 15B previously collected, and are adjusted to limit the distance d with either the upper or lower edge of the blackout bar as indicated. In the embodiment shown in FIG. 18A, measurements are made from the upper line of the bounding box to the upper reference line or the word, although this is not a requirement. Thus, for example, the measurement could alternatively be made from the reference line to either the upper or lower bounding line, or the character. FIG. 18B better shows how the set of measurements is used to form the signal output from block 104. The contour is represented as a set of measurements distance d', relative to the reference line. Measurement d' is therefore derived from the measurements shown in FIG. 18A, which designate the stopping point of line d, and the known position of the black out bar. Calculating the distance relative to the reference line enables scaling of the word shape contours to a common x height, thereby facilitating any subsequent comparison of the shapes. Accordingly, the distances d' represent a measurement from the reference line or blackout bar to the outer limits of the letter, and in the absence of a letter, provide a zero measurement. These measurement might be derived directly, but the proposed indirect methods appear easier to implement. FIGS. 18C and 18D shows that the sets of d' values can be plotted on a graph to form a one dimensional signal or curve representing the word shape. Details of the contour determination are contained in the function StoreOutlinePair() beginning in the Appendix at page 255. FIG. 16 is an image of the contour locations as established for the text sample of FIG. 2. It is important to note the informational content of FIG. 16, where, for the most part, it is relatively easy to recognize the words within the passage by their contours alone.

In studies of the information delivered by the appearance of English language words, it has been determined that in a majority of cases, words can be identified by viewing only approximately the top third of the image of the word. In other words, the upper portion of the word carries with it much of the information needed for identification thereof. In a significant portion of the remainder of cases, words that are unidentifiable by only the upper third of the image of the word, become identifiable when the identification effort includes the information carried by the lower third of the image of the word. A relatively small class of words requires information about the middle third of the word before identification can be made. It can thus be seen that a stepwise process might be used, which first will derive the upper word shape signal or contour, second will derive the lower word shape signal or contour, and thirdly derive a word shape signal central contour (from the reference line towards the word or bounding box), in a prioritized examination of word shape, as required. In the examples of FIG. 18A, 18B, and 18C, the word "from" is fairly uniquely identifiable from its upper portion only. In the examples of FIG. 19A, 19B, 19C and 19D, the word "red" is less uniquely identifiable from its upper portion, since it may be easily confused with the word "rod", and perhaps the word "rad". While the lower portion of the letter "a" may distinguish "red" and "rad", it is doubtful that the lower portion of the letter "o" will distinguish the words "red" from "rod". However, the central portions of "red", "rad", and "rod" are quite distinct.

With reference again to FIG. 1B, the next step performed is a comparison at word shape comparator 26. In one embodiment, the comparison is actually several small steps, each of which will be described. With reference to FIG. 20, generally, the two word shape signals, one a known word, the other an unknown string of characters are compared to find out whether or not they are similar. However, in this case, signal R is the upper contour of the word "red", while signal F is the upper contour of the word "from". Actually, relatively few signals could be expected to be exactly identical, given typical distinctions between character fonts, reproduction methods, and scanned image quality. However, the word shape signals to be compared may be scaled with respect to one another, so that they have the same x-heights. This is achieved by determining the x-height of the pair of word shape contours to be compared. Once determined, the ratios of the x-heights are used to determine a scale factor to be applied to one of the contours. As the x-height is a characteristic measurement for fonts, it is used to determine the scaling factor in both the horizontal and vertical directions. An example of the scaling operation is found in the fontNorm.c file beginning at line 172, where the StoreOutlinePair() function carries out the scaling operation in both the x and y, horizontal and vertical, directions. Alternatively, the shape signals may be compared without normalization and a weighting factor imposed upon the portion of the measured difference due to the unequal lengths. Furthermore, the amplitude or height of the signals has been normalized to further reduce the impact of the font size on the word shape comparison.

Referring next to FIGS. 21A-21C, which illustrate details of the ascender/descender normalization operation, each of the shape signals are normalized based upon a common relationship between the ascender and descender heights and the x-height of the text characters. As illustrated, the actual ascender heights of characters printed with supposedly similar font size, or what is now an appropriately scaled font size, may be slightly different. This occurs as a result of type faces or fonts which are small on body or large on body, implying that similar characters exhibit variations in height across fonts that are the same size, for example 24 point fonts. As an illustration, distance d.sub.1 in FIG. 21A represents the difference in ascender height for two occurrences of the letter "h." Likewise, distance d.sub.2 illustrates a similar difference between the heights of the letter "f" in FIG. 21B. As illustrated in FIG. 21C, the typical character may be broken into three sections, ascender portion 390, x-height portion 392, and descender portion 394. In addition, the relative heights of these sections are illustrated as a, c, and b, respectively. Again, the normalization operation applied to the shape contours is found in the fontNorm.c module, beginning at page 183 of the Appendix. Applying the operations described with respect to StoreOutlinePair() function, page 255 of the Appendix, the areas of the contour lying above the x-height are scaled as follows: ##EQU1## Similarly, the descenders are scaled by the following equation: ##EQU2## where, in both cases, the value used in the numerator (1.5) is arrived at based upon observation of the relationship between ascender or descender heights and the x-height. Also included within the StoreOutlinePair() function is an operation to remove the portions of the contours which do not represent portions of the text string. These regions lie at the ends of the bounding boxes illustrated in FIG. 14. For example, the box surrounding the word "practitioner" in FIG. 14 can be seen to extend beyond the actual word image. As further illustrated at the ends of the word "from" in FIGS. 18A-18D, the contour does not contain useful information. By removing these regions from the contour shape, less error will be introduced into the comparison operations.

Subsequent to the normalization operation, standard signal processing steps can be used to determine the similarity or dissimilarity of the two signals being compared. Alternatively, the following equation may be used: ##EQU3## where .DELTA..sub.string is the difference value between the two signals

f(x) is the known signal; and

g'(x) is the unknown signal.

In a simple determination, the difference could be examined and if it is close to zero, such would be indicated that there would be almost no difference between the two signals. However, the greater the amount of difference, the more likely that the word was not the same as the word to which it was being compared that value would be.

It is important to note that the embodiments described herein, as supported by the code listings of the Appendix, compare the word shape contours using the upper and lower contours for each word in conjunction with one another. This is an implementation specific decision, and is not intended to limit the invention to comparisons using only the top and bottom contours in conjunction with one another. In fact, sufficient information may be contained within the upper contours alone so as to significantly reduce the requirements for a comparison of the lower contours, thereby saving considerable processing effort.

The steps of this simplified comparison method, as first contemplated, are illustrated in FIG. 22. Beginning at step 410, the contour for the first word shape is retrieved from memory, and subsequently, the second word shape is retrieved by step 412. Next, the centers of gravity of the word shapes, defined by the upper and lower contours, are determined and aligned, step 414. The purpose of this step is to align the centers of the word contours to reduce the contour differences that would be attributable solely to any relative shift between the two sets of contours being compared. The center of gravity is determined by summing the areas under the curves (mass) and the distances between the contours (moments) which are then divided to give an indication of the center of gravity for the upper and lower contour pair. Once determined for both sets of contour pairs, the relative shift between the pairs is determined, step 416, and the contours are shifted prior to calculating the difference between the contours. The shifting of the contours is necessary to reduce any error associated with the establishment of the word shape boundaries and computation of the word shapes at block 24 of FIG. 1B. Step 418 handles those regions lying outside the overlapping range of the shifted contour pairs, determining the difference against a zero amplitude signal in the non-overlapping regions. This is done by summing the squared values of the, upper and lower, contours at the non-overlapping ends of the contours. Subsequently, the overlapping region of the contours are compared, step 420. The difference in this region is determined as the sum of the squared differences between the upper curves and the lower curves, as shown in the function L2Norm() on page 100 of the Appendix. Next, the values returned from steps 418 and 420 are added to determine a sum of the differences over the complete range defined by the shifted contours. This value may then be used as a relative indication of the similarity between the contour pairs for the two word shapes being compared.

An alternative to the center-of-gravity comparison method, uses a signal processing function known as time warping, as described in 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, Mass., 1983, Chapters 1 and 4, both specifically incorporated herein by reference, may be used to provide for compression and expansion of points along the contours until the best match is made. Then a score is derived based on the amount of difference between the contours being compared and the stretching required to make the contours match. Once again, the score providing a relative indication of the match between the two signals being compared.

Referring now to FIG. 23, which depicts the general steps of the dynamic warping method, the method relies on the use of a difference array or matrix to record the distances between each point of the first contour and points of the contour to which it is being compared. As illustrated in the figure, and detailed in the code listings contained in the Appendix, the process is similar for all of the measures which may be applied in the comparison.

First, the organization of the code is such that a data structure is used to dynamically control the operation of the various comparison functions. The structure DiffDescriptor, the declaration for which is found on page 9 of the Appendix (see diff.h), contains variables which define the measure to be applied to the contours, as well as, other factors that will be used to control the comparison. These factors include: normalization of the contour lengths before comparison; separate comparisons for the upper and lower contours; a centerWeight factor to direct the warping path; a bandwidth to constrain the warp path; a topToBottom ratio which enables the top contour comparison to be weighted more or less with respect to the bottom contour comparison; and a hillToValley ratio to selectively control weighting the contour differences when an unknown contour is being compared to a known or model word shape contour. Interpretation of the various factors is actually completed in the diff2.c module at page 56 of the Appendix, although descMain.c at page 49 provides an illustration of the interpretation of the factors.

In general, each measure implements a comparison technique, however, each is optimized for a specific type of dynamic comparison, for example, a slope limited dynamic warp having a non-unitary centerweight and a topToBottom weight greater than one. The first level of selection enables the use of a slope-constrained warping function for comparison, an unconstrained warp, or a simple, non-warped, comparison. Within both of the warp comparison methods, there are both separate comparison functions, where the top and bottom contours are warped independently, and parallel comparison functions, where the warp is applied to both the top and bottom contours simultaneously. Specific details of the comparison functions are generally contained within the newMatch.c file beginning at page 101 of the Appendix.

In the general embodiment, the dynamic warping process starts by allocating space for the path/distance array, step 450, which will hold the distance values generated during the comparison and warping of one word shape contour with respect to another. After allocating space, the border regions of the array must be initialized as the process used by all the warping measures is an iterative process using data previously stored in the array for the determination of the cumulative difference between the contours. At step 452, the array borders are initialized. Initialization of the first row of the array entails the determination of the square of the difference between a first point on the first contour and each point on the second contour. Subsequent to border initialization, the column and row index values, L1 and L2, respectively, are reset to 1 to begin processing the individual, non-border, points along the contours.

Processing of the contours proceeds at steps 458 through 464, where the difference in distance between each point along the second contour, with respect to a point on the first contour is calculated. Moreover, this difference, or distance, is calculated and then summed with a previously determined difference value. In addition, some of the previously determined difference values may be weighted differently, for example, in one embodiment weights of the difference values along the array diagonal may be modified by a centerWeight weighting factor. As an illustration, the operation of the NewMatch() function, beginning at line 106 on page 103, at first, the distance (rest) is calculated as the sum of the squares of the differences between a point on the first contour and a point on the second contour, over the upper and lower contours, where the top contour difference is weighted by the topToBottom variable. This distance (rest) is used in subsequent iterations to determine the horizontal, vertical and diagonal difference values in the loop beginning at line 137 on page 103. To determine each of these values, the current distance value, represented by rest, would be added to the previous values in the down, left, and down-left array positions, the down-left position value being the diagonal position which is weighted by the centerWeight factor as previously described. Referring to FIG. 24A, which illustrates the positional relationship between a previously determined value X, at array location 502, and subsequent array locations, the value X might be added to the difference values of subsequent locations to accumulate the total difference calculations is shown. When calculating the difference value for array location 504, the value in location 502 would be used as the down value. Similarly, when calculating the value in location 506, the value of location 502 would be used as the center-weighted down-left, or diagonal, value. After calculating the three difference values, steps 458, 460, and 462, the process continues by selecting the smallest of the three values, step 464, for insertion into the current array position, step 466. As illustrated in the Appendix at line 144 of page 103, the FMin() function from page 101 returns the minimum of the three values previously calculated, the value being inserted into the storage array pointed to by pointer dc.

Subsequently, the process illustrated in FIG. 23 continues by determining the differences between the point on the first contour, represented by L1, to points on the second contour, represented by L2. Decision step 468 controls the iterative processing of the points along the second contour by testing for the end of the contour, or swath. In the implementation shown in the Appendix, the index variables i and j are used in place of L1 and L2 to control the difference calculation loops. As indicated in the code for the NewMatch function beginning on page 102 of the Appendix, the swath is referred to as the bandwidth, and is determined by a desired bandwidth which is adjusted for the slope defined by the contour lengths (see page 102, lines 83-89). If no limit has been reached, processing for the next point would continue at step 458 after the value of L2 was incremented at step 470. Similarly, decision step 472 controls the processing of each point along the first contour, in conjunction with incrementing step 474. Once all the points have been processed with respect to one another, as evidenced by an affirmative response in step 472, the relative difference score, best score, is contained in the farthest diagonal position of the array (L1, L2). Subsequently, the value determined at step 476 is returned as an indication of the dynamically warped difference between the contours being compared.

The code implementation found in the NewMatch() function on page 103 of the Appendix has optimized the execution of the aforedescribed warping process by reducing the large two-dimensional array to a pair of linear arrays which are updated as necessary. Due to this modification, the minimum difference, or best score, for the warp comparison value is found in the last location of the one-dimensional array. Furthermore, the final difference value, dc, may be subsequently normalized to account for the length differences between the two sets of contours being compared. Finally, such a value might subsequently be compared against a threshold or a set of similarly obtained difference values to determine whether the contours are close enough to declare a match between the words, or to determine the best match from a series of word shape comparisons.

In yet another embodiment, the dynamic time warping process previously described may be altered to compare the difference values contained in the difference array to a threshold value on a periodic basis. Upon comparison, the process may be discontinued when it is determined that sufficient difference exists to determine that the contours being compared do not match one another, possibly saving valuable processing time. Moreover, the sequential operation of word shape comparator 26 might be done in conjunction with sequential output from word shape computer 24, thereby enabling the parallel processing of a textual image when searching for a keyword.

Having described a basic implementation of the dynamic warping comparison measures, the distinctions of the other dynamic warp comparison methods included in the Appendix and the application of the control factors previously mentioned will be briefly described to illustrate the numerous possible embodiments of the present invention. First, the method previously described may also be implemented with the slope of the warp path being constrained as it moves across the array. Details of the implementation are found in the SlopeCMatch() function beginning on page 111 of the Appendix. This measure is further illustrated graphically in FIG. 24B, where the value of array location 512, X, may be added to only the three subsequent array locations shown. For example, X may be added to array location 514, when considered as the d2.vertline.1 value for location 514. The nomenclature used for the variable names, and followed in the figure, is as follows: d2.vertline.1 refers to the array location which is down 2 rows and left one column, d1.vertline.1, refers to the lower left diagonal array location, and d1.vertline.2 refers to the array location that is down one column on left 2 rows from the current array location. In a similar manner, X may be added as the d1.vertline.2 value for the calculation of the cumulative difference value for array location 516.

As is apparent from a comparison of FIGS. 24A and 24B, the slope constrained warping measure limits the warping path which can be followed during the generation of the cumulative difference value. The reason for implementing such a constraint is to prevent the warping process from removing, or compressing, a large area of one of the two contours being compared, without imposing a significant "cost" to such a compression.

Next, the method previously described with respect to the parallel warping process may also be implemented on only one pair of contours at a time, for example, the upper contours of two word shapes. The functions SepMatch() and SepCMatch(), as found in the Appendix on pages 104 and 113, respectively, implement the separate matching measure in both the non-slope-constrained and slope-constrained fashions previously described. In general, these measures separately calculate the difference between the top or bottom contours of a pair of wordshapes. The general implementation indicated for the measures in the code shows that these measures are typically used sequentially, first determining the warped difference for the top contours, and then adding to it the warped difference from the bottom contour comparison, resulting in a total difference for the wordshapes.

By carrying out the comparison methods described in a "piecewise" cascaded fashion, further processing benefits may also be derived. More specifically, cascaded comparison would entail, first, utilizing the upper contours of the words being compared to identify a word, or at least narrow the set of possible alternatives and, second, using the lower contour comparison to provide complete identification. It is believed that such an approach to word shape comparison operation 26 would considerably reduce processing time spent on identifying unknown word shapes by comparison to a dictionary of known word shapes, 28, as illustrated in FIG. 1B. Important to the cascaded comparison, is the constraint that the top and bottom warps applied to the contours must be relatively equivalent. This requirement arises from the fact that the upper and lower curves have a relationship to a common word, and if this relationship is not maintained during the warp analysis, the accuracy of the comparison will be compromised.

Alternatively, the dynamic warping technique may be applied as described, with the addition of a function suitable for accumulating the relative warp applied to the upper and lower curves in achieving the best match. For example, when a known, non-italicized word shape is compared to an unknown word shape, a shift in the warp applied to the upper curve relative to the lower curve could be indicative of an italicized word, however, the length of the warped region will remain the same for the top and bottom warps. Such a technique may prove useful in the identification of important words within a larger body of text, as these words are occasionally italicized for emphasis.

One of the control factors which has not been previously described is the bandwidth factor. As implemented, the bandwidth factor controls the relative width of the signal band in which the warping signal will be constrained. More specifically, the band width limitation is implemented by defining a region about the array diagonal in which the warp path which traverses the array is constrained. The constraint is implemented by assigning large values to those areas outside of the band width, so as to make it highly unlikely that the path would exceed the constraint.

Another factor which was briefly mentioned is the topToBottom factor. When applied, the value of this variable is used to weight the difference value determined for the top contour warping process. Therefore, use of a number greater than one, will cause the upper contour difference to be weighted more heavily than the lower contour difference. A very large number would effectively eliminate the lower contour difference completely and, likewise, a zero value would eliminate the upper contour difference completely. This factor is generally considered important to enable the upper contour to be weighted in proportion to its information content, as it generally carries more information regarding the word than does the lower contour.

The hillToValley ratio is a variable which is usually applied in situations when a known, or model, set of word shape contours is being compared against a set of word shape contours from an unknown image. In exercising this option, the model set of contours is passed as the comparison measure functions, for example, NewMatch() on page 102 of the Appendix. When determining the difference between points on the contours, the comparison functions commonly call the function SquareDifference() on page 101 of the Appendix to determine the sum of the squared difference. SquareDifference() applies the hillToValley ratio to the squared difference whenever it determines that the value of the model contour is less than the contour being compared. The result of applying a hillToValley value greater than one is that the relative "cost" of the difference when the model contour is less than the target contour is smaller than the same difference when the model contour is greater than the target contour. The basis for this type of weighting is that when comparing against a model contour, the comparison should treat those areas of the target contour that are subject to being "filled in" during a scanning or similar digitizing operation with less weight than regions not likely to be filled in, as evidenced by contour positions below the model contour. For instance, the regions where ascenders and descenders meet the body of the character are likely to be filled in during scanning, thereby causing the target contour to have a gradual contour in those regions, whereas the model contour would most likely have a defined peak or valley in these regions. Hence, the contour value of the model would be less than the contour value of the target, even though the characters may have been identical. Therefore, the hillToValley variable attempts to minimize the impact to the calculated difference value over these regions.

It is important to note that the aforedescribed measures and control factors allow the comparison measures to be conducted in numerous permutations. However, the flexibility which these measures permit is intended to enhance the applicability of the comparison process, so that when information is known about a particular word shape contour, for example, a model contour generated from a computer generated character font, the measures may place reliance on that information to make the comparisons more robust.

The mathematical explanation of the word shape derivation process suggests that alternative methods of deriving the word shape signal exist. Some possible alternatives are the establishment of the one dimensional signal using an alternative coordinate scheme, for example polar coordinates. Another possibility is generation of signal g(t), where g(t) represents the direction from each contour point to the succeeding contour point, where t would represent the point number.

The invention has been described with reference to a preferred embodiment, namely a software implementation, but the invention may be implemented using specialized hardware. Moreover, the invention has been described with respect to textual images. However, this invention would also be applicable for images that include non-textual image portions as well. Obviously, modifications will occur to others upon reading and understanding the specification taken together with the drawings. This embodiment is but one example, and various alternatives, modifications, variations or improvements may be made by those skilled in the art from this teaching which is intended to be encompassed by the following claims.