Method of optical character recognition using feature recognition and baseline estimation

• US 7,454,063 B1
• Filed: 09/22/2005
• Issued: 11/18/2008
• Est. Priority Date: 09/22/2005
• Status: Expired due to Fees

• Current Assignee: National Security Agency
• Original Assignee: The United States of America As Represented By The Director National Security Agency
• Inventors: Kneisl, Kyle E, Otero, Jesse
• Primary Examiner(s): Ahmed; Samir A
• Assistant Examiner(s): Thirugnanam; Gandhi
• Application Number:
  US11/233,218
• Time in Patent Office: 1,153 Days
• Field of Search: 382/161, 382176-179, 382182-183, 382185-187, 382/209, 382/229, 382/306, 382/317, 382/321
• US Class Current: 382/187
• CPC Class Codes: G06V 30/2272 with lexical matching

Abstract

The present invention is a method of optical character recognition. First, text is received. Next all words in the text are identified and associated with the appropriate line in the document. The directional derivative of the pixellation density function defining the text is then taken, and the highest value points for each word are identified from this equation. These highest value points are used to calculate a baseline for each word. A median anticipated baseline is also calculated and used to verify each baseline, which is corrected as necessary. Each word is then parsed into feature regions, and the features are identified through a series of complex analyses. After identifying the main features, outlying ornaments are identified and associated with appropriate features. The results are then compared to a database to identify the features and then displayed.

Claims

1. A method of optical character recognition, comprising the steps of:

a) receiving an image with text;

b) identifying all locations of words in the text;

c) bounding each word in a bounding box;

d) identifying each line in the text;

e) grouping the bounding boxes by each line of text identified in step (d);

f) calculating a directional vertical derivative of a pixellation density function of the words contained in each bounding box;

g) identifying the highest value point in the directional vertical derivative of the pixellation density function for each bounding box;

h) identifying the bottom points of vertical lines intersecting the highest value point in the pixellation density function for each bounding box, wherein each vertical line terminates at the base of the crest that includes the highest value point;

i) approximating a first baseline for each word, each first baseline intersecting a bottom point;

j) calculating a median anticipated baseline for each word, wherein calculating the median anticipated baseline comprises extending each baseline approximated in step (i) a user-definable fixed distance past the final bounding box on each line of text, identifying an endpoint of each approximated baseline, calculating the statistical median of all endpoints, and approximating a median anticipated baseline through the calculated median endpoints;

k) verifying the first baseline for each word is the standard baseline;

l) determining the standard baseline if the difference between the first baseline approximated in step (i) for each bounding box and the median anticipated baseline approximated in step (j) is greater than a user-definable number of pixels in the y-direction on an x-y plane for each bounding box;

m) determining the thickness of the standard baseline for each word;

n) parsing each word into regions in which a feature may exist;

o) identifying all vertical strokes in the regions identified in step (n);

p) identifying the high value vertical peaks in each region identified in step (o);

q) identifying low value vertical peaks in each region (identified in step (o);

r) performing at least one of a statistical analysis, a physical analysis, a geometric analysis, and a linguistic analysis on at least one region identified in step (n) to identify all feature regions not identified in steps (o) and (p);

s) locating and identifying ornaments;

t) associating each ornament with its corresponding feature;

u) identifying characters by comparing the identified feature and associated ornaments to a user-definable database; and

v) displaying the results of step (u) in a user-definable format.

2. The method of claim 1, wherein the step of calculating the directional derivative of the pixellation density function comprises calculating the directional derivative of the pixellation density function comprises wherein the pixellation density function is calculated according to the equation

$\mathrm{PD}$

( y ) = ∑

x = LHS RHS ⁢

⁢

δ

x , y ⁢

Δ

⁢

⁢

PD Δ

⁢

⁢

y ≃

PD ⁡

( y + 1 ) - PD ⁡

( y - 1 ) 2

And wherein PD is the pixellation density, RHS is the right hand side of the text in a bounding box, LHS is the left hand side of the bounding box, and δ

_x,y is the characteristic function returning unity if the location (x,y) contains an active pixel, and returns the value zero otherwise.

3. The method of claim 2, wherein the step of verifying the first baseline for each word is an accurate baseline comprises verifying the first baseline is the standard baseline, wherein the first baseline is verified as the standard baseline if the pixel difference in the y-plane between the first baseline and the median anticipated baseline does not exceed a user-definable threshold.

4. The method of claim 3, wherein the step of identifying the high value vertical peaks in each identified feature region further comprises setting a threshold value to determine what constitutes high value vertical peaks based on the values of all points in the bounding box.

5. The method of claim 4, wherein the step of identifying characters by comparing the identified feature and associated ornaments to a user-definable database further comprises comparing identified features and associated ornaments to similarly associated features and ornaments in a database to find a match.

6. The method of claim 5, wherein the step of performing a statistical analysis on at least one feature region further comprises determining characteristic features of a feature region of a page and comparing the attributes of a specific feature region to those characteristics to identify the feature.

7. The method of claim 6, wherein the step of performing a physical analysis of at least one feature region further comprises examining the physical properties of each feature region and comparing them to the characteristic physical properties of the features of the given lexicon.

8. The method of claim 7, wherein the step of verifying the first baseline for each word is the standard baseline comprises verifying the first baseline is the standard baseline, wherein the first baseline is verified as an accurate baseline if the pixel difference in the y-plane between the first baseline and the median anticipated baseline does not exceed a user-definable threshold or if the difference does exceed a user-definable threshold and median anticipated baseline does not have a pixellation density consistent with the baseline, the associated bounding box location compared to the median anticipated baseline location exceeds a user-definable tolerance, or the geometry of the text in the bounding box meets a user-specified criteria, otherwise substituting the median anticipated baseline for the first baseline.

9. The method of claim 8, wherein the step of performing a linguistic analysis of at least one feature region further comprises performing linguistic analysis tests to identify a feature according to the linguistic properties of the feature and wherein linguistic rules are stored in a database and compared with all features that were identified as possible matches in previous analysesto find a match.

10. The method of claim 1, wherein the step of verifying the first baseline for each word is the standard baseline comprises verifying the first baseline is an accurate baseline, wherein the first baseline is verified as the standard baseline if the pixel difference in the y-plane between the first baseline and the median anticipated baseline does not exceed a user-definable threshold.

11. The method of claim 1, wherein the step of identifying the high value vertical peaks in each identified feature region further comprises setting a threshold value to determine what constitutes high value vertical peaks based on the values of all points in the bounding box.

12. The method of claim 1, wherein the step of identifying characters by comparing the identified feature and associated ornaments to a user-definable database further comprises comparing identified features and associated ornaments to similarly associated features and ornaments in a database to find a match.

13. The method of claim 1, wherein the step of performing a statistical analysis on at least one feature region further comprises determining characteristic features of at least one feature region of a page and comparing the attributes of a specific feature region to those characteristics to identify the feature.

14. The method of claim 1, wherein the step of performing a physical analysis of at least one feature region further comprises examining the physical properties of a feature region and comparing them to the characteristic physical properties of the features of the given lexicon.

15. The method of claim 1, wherein the step of verifying the first baseline for each word is the standard baseline comprises verifying the first baseline is the standard baseline, wherein the first baseline is verified as an accurate baseline if the pixel difference in the y-plane between the first baseline and the median anticipated baseline does not exceed a user-definable threshold or if the difference does exceed a user-definable threshold and median anticipated baseline does not have a pixellation density consistent with the baseline, the associated bounding box location compared to the median anticipated baseline location exceeds a user-definable tolerance, or the geometry of the text in the bounding box meets a user-specified criteria, otherwise substituting the median anticipated baseline for the first baseline.

16. The method of claim 1, wherein the step of performing a linguistic analysis of at least one feature region further comprises performing linguistic analysis tests to identify a feature according to the linguistic properties of the feature and wherein linguistic rules are stored in a database and compared with all features that were identified as possible matches in the previous analyses to find a match.

17. The method of claim 1, wherein the step of calculating a median anticipated baseline further consists of calculating the median anticipated baseline using the bottom points of the vertical lines associated with the peak of each crest of the derivative of the pixellation density function, wherein the median anticipated baseline is calculated by plotting each crest on an x-y plane, taking an average of the y-coordinates associated with each bottom point and plotting a zero-slope horizontal line having a y-coordinate equal to the resulting average y-coordinate.

18. The method of claim 9, wherein the step of calculating a median anticipated baseline further consists of calculating the median anticipated baseline using the bottom points of the vertical lines associated with the peak of each crest of the derivative of the pixellation density function, wherein the median anticipated baseline is calculated by plotting each crest on an x-y plane, taking an average of the y-coordinates associated with each bottom point and plotting a zero-slope horizontal line having a y-coordinate equal to the resulting average y-coordinate.