Method for performing character recognition on a pixel matrix

• US 5,825,923 A
• Filed: 09/05/1996
• Issued: 10/20/1998
• Est. Priority Date: 09/05/1996
• Status: Expired due to Term

• Current Assignee: Faxtrieve, Inc.
• Original Assignee: Faxtrieve, Inc.
• Inventors: Thompson, Archie L., Van Saun, Richard A.
• Primary Examiner(s): CHANG, JON CARLTON
• Application Number:
  US08/706,577
• Time in Patent Office: 775 Days
• Field of Search: 382/258, 382/203, 382/204, 382/205, 382/256, 382/257, 382/187, 382/190, 382/217, 382/218, 382/264, 382/298, 382/276, 382/253
• US Class Current: 382/204
• CPC Class Codes: G06V 10/44 Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components
• CPC Class Codes: G06V 30/10 Character recognition

Abstract

Pattern recognition, particularly character recognition, is effected by categorizing a cipher by a unique description using three feature sets identifying the type and location of lines which form the cipher, the location of the endpoints of each of the lines, and the location of the intersections of the lines. In the process according to the invention, lines are located by expanding or contracting the original image of the cipher to fit into a sparse space pixel matrix. The image is then thinned to define lines and so as not to obliterate lines which give the cipher its uniqueness. Once the cipher is thinned, fuzzy logic is used to "locate", that is, define a set of coordinates for, each line relative to an x-y coordinate system. (As each line is located, it is removed from the matrix image to facilitate locating the remaining lines.) After all the lines are located, the endpoints of each line are located and the intersect points are located. These three feature sets are encoded, resulting in three values, such as 64-bit integers. These three integers are then used as search keys to query a relational database which contains the integer sets for known characters. If a direct match is not found, a matching algorithm uses partial matches to extrapolate the correct character. Because the matrix is sparse, the likelihood of identifying the correct character is enhanced.

Claims

1. A method for recognizing ciphers, said method comprising the steps of:

inputting a digital representation of a cipher, along with a bits-to-pixel ratio of said digital representation, the number of pixels per row of said digital representation, the number of rows in said digital representation, and an indicator which represents a block boundary condition of said digital representation;

transforming said digital representation so that each individual pixel of image information is represented by an addressable data block;

smoothing said transformation;

locating enclosures in said smoothed transformation, said enclosures defining spatial boundaries;

sizing said smoothed transformation, resulting in selected erased enclosures;

restoring all erased enclosures in said sized transformation;

normalizing said enclosure-restored transformation so that stray marks are erased, to form a normalized image;

thinning said normalized image;

storing said thinned image in a sparse space matrix;

locating significant features in said thinned image;

quantizing location of said significant features; and

performing database searches using said quantized values as search keys to identify ciphers associated with said search keys.

3. The method of claim 1 wherein said locating enclosures step comprises the steps of:

locating a set of at least one pair of contiguous pixels which are off;

testing for a set of pixels which surround said off pixels and which are on; and

recording locations of said off pixels.

4. The method of claim 1 wherein said sizing step comprises the steps of:

calculating a horizontal factor;

calculating a vertical factor; and

calculating for each pixel in said smoothed transformation a new horizontal and vertical position based on said horizontal and vertical factors.

5. The method of claim 1 wherein said restoring step comprises:

calculating preferred locations of enclosures in the restored image;

testing said preferred locations to determine if the enclosures are present at said preferred locations; and

restoring said enclosures if said enclosures are not present.

6. The method of claim 1 wherein said normalizing step comprises:

testing whether a subject pixel in the top row of said enclosure-restored transformation is on;

if said subject pixel is on, testing the nearest six bottom neighbor pixels; and

turning said top row subject pixel on if all of said bottom six neighbor pixels are off.

7. The method of claim 1 wherein said normalizing step further comprises the steps of:

testing whether a subject pixel in the top row of said enclosure-restored transformation is off;

if said subject pixel is off, testing side pixels adjacent both sides of said subject pixel; and

turning said subject pixel on if both said side pixels are on.

8. The method of claim 1 wherein said normalizing step further comprises the steps of:

testing whether a subject pixel in any row except the top row of said enclosure-restored transformation is on;

if said subject pixel is on, testing the nearest top six neighbor pixels; and

turning said subject pixel off if all of the said nearest top six neighbor pixels are off.

9. The method of claim 1 wherein said normalizing step further comprises the steps of:

testing whether a subject pixel in the bottom row of said enclosure-restored transformation is off;

if said subject pixel is off, testing side pixels adjacent said subject pixel; and

turning said subject pixel on if both said side pixels are on.

10. The method of claim 1 wherein said normalizing step further comprises the steps of:

testing whether a subject pixel in any row except the top or bottom row of said enclosure-restored transformation is on and is not in the first or last column of said enclosure-restored transformation;

if said subject pixel is on, testing the top six nearest neighbors and the bottom six nearest neighbors; and

turning said subject pixel off if said top six nearest neighbors or said bottom six nearest neighbors are all off.

11. The method of claim 1 wherein said normalizing step further comprises the steps of:

testing whether a subject pixel is part of an enclosure;

if said pixel is not part of an enclosure, testing whether said subject pixel is off;

if said pixel is off, testing said pixels twelve nearest neighbors; and

turning on said subject pixel, if all of the said twelve nearest neighbors are on.

12. The method of claim 1 wherein said normalizing step further comprises the steps of:

testing whether said subject pixel is on;

if said subject pixel is on, testing the nearest eight neighbors; and

turning off said subject pixel if fewer than two of said nearest eight neighbors are on.

13. The method of claim 1 wherein said normalizing step further comprises the steps of:

testing for a blanking condition, said blanking condition being where a non-blank row in said enclosure-restored transformation is between two blank rows; and

deleting said non-blank row and said two blank rows if said blanking condition is true.

14. The method of claim 1 wherein said normalizing step further comprises the steps of:

testing for gaps in the first row, the second row and the third row of said enclosure-restored transformation;

if said gaps exist and there is only one gap per row, computing the length of each gap; and

filling in the gap in the first row if said gaps are directly above the succeeding gap and said lengths increase from top to bottom and the length of the top gap is less than five pixels.

15. The method of claim 1 wherein said normalizing step further comprises the steps of:

testing top row segment length of a top row segment in the top row;

if said top row segment length is less than five, testing next row segment length of the next row segment immediately below the top row segment in the top row; and

if the top row segment length is greater than five and the next row segment is completely beneath the top row segment, then deleting the top row segment.

16. The method of claim 1 wherein said normalizing step further comprises the steps of:

testing bottom row segment length of a bottom row segment in the bottom row;

if said bottom row segment length is less than five, testing previous row segment length of the previous row segment immediately above the bottom row segment in the bottom row; and

if the bottom row segment length is greater than five and the previous row segment is completely above the bottom row segment, deleting the bottom row segment.

17. The method of claim 1 wherein said thinning step comprises the steps of:

examining edges of the image, one edge at a time, for skeletal pixels;

thereafter

deleting pixels which are not skeletal;

repeating the process until only skeletal pixels remain; and

reducing final skeletal image to fit into a uniform size matrix.

18. The method of claim 17 wherein said examining step comprises the steps of:

comparing each edge pixel and its eight nearest neighbors to a set of twelve patterns; and

marking each said edge pixel as skeletal if said edge pixel and its eight nearest neighbors match any of said patterns.

19. The method of claim 17 wherein said examining step further comprises the steps of:

searching each row for a row segment longer then three pixels;

if a three-pixel row segment exists, examining pixels directly above and below said three-pixel row segment; and

if the position of a three-pixel row segment is blank, marking all pixels in position of the three-pixel row segment as skeletal.

20. The method of claim 17 wherein said examining step further comprises the steps of:

examining vertical lines; and

marking said vertical lines as skeletal if said vertical lines are longer than two rows and are less than three pixels wide.

21. The method of claim 1 wherein said locating step comprises the steps of:

computing an average length over all row segments in the image;

scanning for row segments which are greater in length than said average length;

for said row segments whose lengths are greater than average, scanning for row segment chains;

recording the location and length of said row segment chains;

determining type of line said row segment chains represent using fuzzy logic;

deleting said row segment chains from the image;

examining the remaining image for vertical lines;

determining whether said vertical lines are verticals or diagonals by using fuzzy logic;

recording the location, length and type of said lines;

erasing said lines from the image;

locating the remaining row segments;

recording the location of said row segments;

computing the locations of all intersect points;

recording said points;

computing the locations of all endpoints; and

recording said points.

22. The method of claim 1 wherein said quantizing step comprises the steps of:

assigning numeric values to each feature based upon x-y coordinate location of said each feature;

totaling said numeric values for line types;

totaling said numeric values for endpoints;

totaling said numeric values for intersect points;

totaling said numeric values for right diagonals; and

totaling said numeric values for left diagonals.

23. The method of claim 1 further comprising the steps of:

adding a known cipher and its quantized values to an relational database.

2. A method for recognizing ciphers, said method comprising the steps of:

inputting a digital representation of a cipher, along with a bits to pixel ratio of said digital representation, the number of pixels per row of said digital representation, the number of rows in said digital representation, and an indicator which represents a block boundary condition of said digital representation;

transforming said digital representation so that one pixel of image information is represented by a block;

smoothing said transformation wherein said smoothing step comprises the steps of;

testing the nearest eight neighbors of each "off" pixel;

testing the nearest forty-eight neighbors of said "off" pixel if said nearest eight neighbors are all "on"; and

turning said pixel on if any of the said nearest forty-eight neighbors are "off";

locating enclosures in said smoothed transformation, said enclosures defining spatial boundaries;

sizing said smoothed transformation, resulting in selected erased enclosures;

restoring all erased enclosures in said sized transformation;

normalizing said enclosure-restored transformation so that stray marks are erased, to form a normalized image;

thinning said normalized image;

storing said thinned image in a sparse space matrix;

locating significant features in said thinned image;

quantizing location of said significant features; and

performing database searches using said quantized values as search keys to identify ciphers associated with said search keys.

24. A method for recognizing ciphers, said method comprising the steps of;

inputting a digital representation of a cipher, along with a bits to pixel ratio of said digital representation, the number of pixels per row of said digital representation, the number of rows in said digital representation, and an indicator which represents a block boundary condition of said digital representation;

transforming said digital representation so that one pixel of image information is represented by a block;

smoothing said transformation wherein said smoothing step comprises the steps of;

testing adjacent neighbors of each "off" pixel;

testing next nearest neighbors of said "off" pixel if said adjacent neighbors are all "on"; and

turning said pixel on if any of the said next nearest neighbors are "off";

locating enclosures in said smoothed transformation, said enclosures defining spatial boundaries;

sizing said smoothed transformation, resulting in selected erased enclosures;

restoring all erased enclosures in said sized transformation;

normalizing said enclosure-restored transformation so that stray marks are erased, to form a normalized image;

thinning said normalized image;

storing said thinned image in a sparse space matrix;

locating significant features in said thinned image;

quantizing location of said significant features; and

performing database searches using said quantized values as search keys to identify ciphers associated with said search keys.