Word spotting in bitmap images using word bounding boxes and hidden Markov models

• US 5,438,630 A
• Filed: 12/17/1992
• Issued: 08/01/1995
• Est. Priority Date: 12/17/1992
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Chen, Francine R., Wilcox, Lynn D., Bloomberg, Dan S.
• Primary Examiner(s): Mancuso, Joseph
• Assistant Examiner(s): DEL ROSSO, GERARD DOMNICK
• Application Number:
  US07/991,913
• Time in Patent Office: 957 Days
• Field of Search: 382/20, 382/9, 382/19, 382/26, 382/54, 382/55, 382/14, 382/15, 382/36, 382/37
• US Class Current: 382/159
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/262 using context analysis, e.g. lexical, syntactic or semantic context
• CPC Class Codes: G06V 30/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text

Abstract

Font-independent spotting of user-defined keywords in a scanned image. Word identification is based on features of the entire word without the need for segmentation or OCR, and without the need to recognize non-keywords. Font-independent character models are created using hidden Markov models (HMMs) and arbitrary keyword models are built from the character HMM components. Word or text line bounding boxes are extracted from the image, a set of features based on the word shape, (and preferably also the word internal structure) within each bounding box is extracted, this set of features is applied to a network that includes one or more keyword HMMs, and a determination is made. The identification of word bounding boxes for potential keywords includes the steps of reducing the image (say by 2×) and subjecting the reduced image to vertical and horizontal morphological closing operations. The bounding boxes of connected components in the resulting image are then used to hypothesize word or text line bounding boxes, and the original bitmaps within the boxes are used to hypothesize words. In a particular embodiment, a range of structuring elements is used for the closing operations to accommodate the variation of inter- and intra-character spacing with font and font size.

Claims

1. A processor-based method of determining whether a keyword made up of characters is present in a bitmap input image containing words, the words being considered to extend horizontally, the method comprising the steps of:

providing a set of previously trained single-character hidden Markov models (HMMs), each single-character HMM having a number of possible contexts, depending on whether the character has an ascender or a descender;

concatenating those single-character HMMs that correspond to the characters in the keyword so as to create a keyword HMM, the context of a given single-character HMM used to create the keyword HMM being determined on the basis of whether the keyword contains characters having ascenders or a descenders;

constructing an HMM network that includes a path passing through the keyword HMM;

locating a portion of the input image potentially containing a word;

providing an array of pixel values, referred to as a potential keyword, representing the portion of the input image;

horizontally sampling the potential keyword to provide a plurality of segments wherein each segment extends the entire height of the potential keyword and the sampling to provide segments is performed in a manner that is independent of the values of the pixels in the potential keyword;

for each segment, generating at least one feature that depends on the values of the pixels in the segment, thereby providing a set of features based on the potential keyword, the set of features providing shape information regarding the word potentially contained in the portion of the input image;

applying the set of features to the HMM network;

determining a probability for the potential keyword as applied to the path passing through the keyword HMM; and

comparing the probability, so determined, relative to an additional probability value so as to provide an indication whether the potential keyword is the keyword.

2. The method of claim 1 wherein:

each character on which one of the set of single-replacement HMMs is based has a number of distinct portions;

each character has a shape that is characterized by a number of feature vectors, at a corresponding number of horizontal locations along the character;

a given single-character HMM for a given character is characterized by a number of states, each state of which corresponds to one of the number of distinct portions of the given character; and

each state is characterized by a Gaussian distribution with mean vector and covariance matrix of the feature vectors that characterize the corresponding distinct portion of the given character.

3. The method of claim 1 wherein the step of locating includes performing at least one reduction operation on the input image.

4. The method of claim 1 wherein the step of locating includes performing at least one morphological operation on the input image.

5. The method of claim 1 wherein:

the HMM network includes an HMM that models non-keywords and includes an additional path passing through the non-keyword HMM but not passing through the keyword HMM;

the additional probability value is a probability determined for the potential keyword as applied to the additional path; and

the indication is whether the probability of the potential keyword as applied to the keyword HMM is sufficiently greater than the probability for the potential keyword as applied to the non-keyword HMM.

6. The method of claim 1 wherein:

substantially all the segments have the same width;

the set of features for the potential keyword includes a plurality of feature vectors, each feature vector corresponding to a respective one of the segments; and

a given feature vector for a given segment represents pixel values of the given segment.

7. The method of claim 6 wherein a feature vector for a given segment of the potential keyword includes a representation of the topmost pixel in the given segment having a value above a threshold, a representation of the bottommost pixel in the given segment having a value above the threshold, and a set of autocorrelation values.

8. The method of claim 1 wherein the step of locating includes constructing bounding boxes, at least some of which enclose respective words in the image, the bounding boxes being considered to extend horizontally.

9. The method of claim 8 wherein at least some of the bounding boxes enclose respective portions of words in the image.

10. The method of claim 1 wherein the step of providing an array of pixel values includes proportionally scaling the height and width of the portion of the input image to provide a potential keyword with a height having a predefined number of pixels.

11. The method of claim 1 wherein the single-character HMMs were trained on a corpus containing bitmap images of text in a plurality of fonts.

12. A processor-based method Of determining whether a keyword made up of characters is present in a bitmap input image containing words, the words being considered to extend horizontally, the method comprising the steps of:

providing a set of previously trained single-character HMMs, each single-character HMM having a number of possible contexts, depending on whether the character has an ascender or a descender;

concatenating those single-character HMMs that correspond to the characters in the keyword so as to provide a keyword HMM, the context of a given single-character HMM used to create the keyword HMM being determined on the basis of whether the keyword contains characters having ascenders or descenders;

providing a non-keyword HMM;

constructing a network that includes a first path passing through the keyword HMM and a second path passing through the non-keyword HMM but not passing through the keyword HMM;

locating a portion of the input image potentially containing a word;

providing an array of pixel values, referred to as a potential keyword, representing the portion of the input image;

generating a set of features based on the potential keyword, the set of features providing shape information regarding the word potentially contained in the portion of the input image;

the set of features being generated at a plurality of uniformly spaced horizontal locations, thereby avoiding segmentation of the potential keyword in a manner that depends on values of the pixels in the potential keyword;

applying the set of features to the HMM network;

finding a path through the network that maximizes the probability of the set of features as applied to the network; and

determining whether the path that maximizes the probability passes through the keyword HMM so as to provide an indication whether the potential keyword is the keyword.

13. The method of claim 12 wherein:

each character has a plurality of distinct portions;

each character has a shape that is characterized by a number of feature vectors at a corresponding number of horizontal locations along the character;

a given single-character HMM for a given character is characterized by a plurality of states, each state of which corresponds to one of the number of distinct portions of the given character; and

each state is characterized by a Gaussian distribution with mean vector and covariance matrix of the feature vectors that characterize the corresponding distinct portion of the given character.

14. The method of claim 12 wherein the step of locating includes performing at least one reduction operation on the input image.

15. The method of claim 12 wherein the step of locating includes performing at least one morphological operation on the input image.

16. The method of claim 12 wherein the set of features for the potential keyword includes a plurality of multi-parameter feature vectors determined at respective ones of the plurality of uniformly spaced horizontal locations in the potential keyword, a given feature vector for a given horizontal location representing pixel values at the given horizontal location.

17. The method of claim 16 wherein a feature vector for a given horizontal location in the potential keyword includes a representation of the topmost pixel at the given horizontal location having a value above a threshold, a representation of the bottommost pixel at the given horizontal location having a value above the threshold, and a representation of pixel values between the topmost pixel having a value above the threshold and the bottommost pixel having a value above the threshold.

18. The method of claim 17 wherein the representation of pixel values includes a set of autocorrelation values.

19. The method of claim 17 wherein the representation of pixel values includes the number of pixel transitions through a threshold value.

20. The method of claim 12 wherein the step of locating includes constructing bounding boxes, at least some of which enclose respective words in the input image, the bounding boxes being considered to extend horizontally.

21. The method of claim 20 wherein at least some of the bounding boxes enclose respective portions of words in the input image.

22. The method of claim 12 wherein the step of providing an array of pixel values includes proportionally scaling the height and width of the portion of the input image to provide a potential keyword with a height having a predefined number of pixels.

23. The method of claim 12 wherein the set of features further provides information regarding word internal structure.

37. The method of claim 12 wherein the single-character HMMs were trained on a corpus containing bitmap images of text in a plurality of fonts.

24. A processor-based method of determining whether a keyword made up of characters is present in a bitmap input image containing words, the words being considered to extend horizontally, the method comprising the steps of:

providing a set of previously trained single-character hidden Markov models (HMMs) wherein

each character on which one of the set of single-replacement HMMs is based has a number of distinct portions,

each character has a shape that is characterized by feature vectors at corresponding horizontal locations along the character,

a given single-character HMM for a given character is characterized by a number of states, each state of which corresponds to one of the number of distinct portions of the given character, and

each state is characterized by a probability distribution of the feature vectors that characterize the corresponding distinct portion of the given character;

each single-character HMM having a number of possible contexts, depending on whether the character has an ascender or a descender;

concatenating those single-character HMMs that correspond to the characters in the keyword so as to create a keyword HMM, the context of a given single-character HMM used to create the keyword HMM being determined on the basis of whether the keyword contains characters having ascenders or a descenders;

providing a non-keyword HMM;

constructing a network that includes a first path passing through the keyword HMM and a second path passing through the non-keyword HMM but not passing through the keyword HMM;

locating a portion of the input image potentially representing a word;

providing an array of pixel values, referred to as a potential keyword, representing the portion of the input image, the potential keyword having a plurality of vertically extending columns of pixels at respective ones of a plurality of uniformly spaced horizontal locations;

generating a plurality of feature vectors determined at respective ones of the plurality of horizontal locations in the potential keyword, a given feature vector for a given horizontal location being specified by pixel values in the column at the given horizontal location;

the plurality of feature vectors together representing word shape while being generated by uniform segmentation of the potential keyword, whereby segmentation of a type that depends on values of the pixels in the potential keyword is avoided;

applying the plurality of feature vectors to the HMM network;

finding a path through the network that maximizes the probability of the plurality of feature vectors as applied to the network; and

determining whether the path that maximizes the probability passes through the keyboard HMM, so as to provide an indication whether the potential keyword is the keyword.

25. The method of claim 24 wherein the step of locating includes performing at least one reduction operation on the input image.

26. The method of claim 24 wherein the step of locating includes performing at least one morphological operation on the input image.

27. The method of claim 24 wherein the step of locating comprises:

performing at least one reduction operation on the input image; and

performing at least one morphological operation on the input image, so reduced.

28. The method of claim 24 wherein a feature vector for a given horizontal location in the potential keyword includes a representation of the topmost pixel at the given horizontal location having a value above a threshold and a representation of the bottommost pixel at the given horizontal location having a value above the threshold.

29. The method of claim 24 wherein the step of locating includes constructing bounding boxes, at least some of which enclose respective words in the image, the bounding boxes being considered to extend horizontally.

30. The method of claim 29 wherein at least some of the bounding boxes enclose respective portions of words in the image.

31. The method of claim 24 wherein a feature vector for a given horizontal location includes a representation of the topmost pixel at the given horizontal location having a value above a threshold, a representation of the bottommost pixel at the given horizontal location having a value above the threshold, and a representation of pixel values between the topmost pixel having a value above the threshold and the bottommost pixel having a value above the threshold.

32. The method of claim 31 wherein the representation of pixel values includes a set of autocorrelation values.

33. The method of claim 31 wherein the representation of pixel values includes the number of pixel transitions.

34. The method of claim 24 wherein the step of providing an array of pixel values includes proportionally scaling the height and width of the portion of the input image to provide a potential keyword with a height having a predefined number of pixels.

35. The method of claim 24 wherein each feature vector contains a plurality of parameters.

36. The method of claim 24 wherein the single-character HMMs were trained on a corpus containing bitmap images of text in a plurality of fonts.