Character recognition system and method

• US 20030169925A1
• Filed: 03/11/2003
• Published: 09/11/2003
• Est. Priority Date: 03/11/2002
• Status: Active Grant

• Current Assignee: IMDS Software, Inc.
• Original Assignee: IMDS Software, Inc.
• Inventors: Polonowski, Jean-Pierre
• Granted Patent: US 7,327,883 B2
• Time in Patent Office: Days
• US Class Current: 382/198
• CPC Class Codes: G06F 18/24137 Distances to cluster centroïds

Abstract

A system and method for translating a written document into a computer readable document by recognizing the character written on the document aim at recognizing typed or printed, especially hand-printed or handwritten characters, in the various fields of a form. Providing a pixel representation of the written document, the method allows translating a written document into a computer readable document by i) identifying at least one field into the pixel representation of the document; ii) segmenting each field so as to yield at least one segmented symbol; iii) applying a character recognition method on each segmented symbol; and iii) assigning a computer-readable code to each recognized character resulting from the character recognition method. The character recognition method includes doing a vector quantization on each segmented symbol, and doing a vector classification using a vector base. A learning base is also created based on the optimal elliptic separation method. System and method according to the present invention allow to achieve a substitution rate of near zero.

Claims

1. A method for translating a written document into a computer readable document comprising:

providing a pixel representation of the written document;

identifying at least one field into said pixel representation of the written document;

segmenting each said at least one field, yielding at least one segmented symbol;

applying a character recognition method on each segmented symbol; and

assigning a computer-readable code to each recognized character resulting from said character recognition method.

2. A method as recited in claim 1, wherein applying a character recognition method includes doing a vector quantization on each segmented symbol, and doing a vector classification using a vector base.

3. A method as recited in claim 2, wherein at least two fields are identified on said pixel representation of the written document;

at least two recognition engines, each including a vector quantization method and a vector classification method, being used on applying a character recognition method on each segmented symbol on said at least two fields.

4. A method as recited in claim 3, wherein a voting method is further used to allow the combination of the results of the at least two recognition engines using at least one of simple averages, weighted averages and veto rules.

5. A method as recited in claim 2, wherein doing a vector classification on each segmented symbol includes, for each segmented symbol, computing a similarity score for each possible class.

6. A method as recited in claim 5, wherein computing a similarity score includes comparing said vector quantization of said each segmented symbol and a predetermined vector quantization corresponding to said each possible class.

7. A method as recited in claim 6, wherein comparing said vector quantization of said each segmented symbol and a predetermined vector quantization corresponding to said each possible class is done using a separation method selected from the group consisting of an optimal linear separation method, an optimal elliptical separation method, a support vector machine, a quadratic vector machine, a modified quadratic discriminant function, and a K nearest neighbor.

8. A method as recited in claim 5, further comprising comparing said similarity score to a predetermined threshold.

9. A method as recited in claim 7, wherein said threshold is computed using a vector base.

10. A method as recited in claim 1, further comprising:

providing a pixel representation of the written document by digitizing said document.

11. A method as recited in claim 1, wherein said at least one field is a generally rectangular portion of the pixel representation of the written document.

12. A method as recited in claim 1, further comprising:

recognizing the type of document;

associating a predetermined format to said written document corresponding to said type of document;

wherein, identifying at least one field into said pixel representation of the document is done using said predetermined format.

13. A method as recited in claim 12, wherein recognizing the type of document includes identifying predetermined characteristic of the written document.

14. A method as recited in claim 13, wherein said predetermined characteristic includes general configuration of said document, text block, dimensions, and lines configurations.

15. A method as recited in claim 1, further comprising:

verifying at least one of said recognized characters.

16. A method as recited in claim 1, further comprising:

verifying at least one unrecognized character.

17. A method as recited in claim 16, wherein said verifying at least one unrecognized character includes at least one of a person verifying said at least one unrecognised character, applying a predetermined field validity rule, verifying in a stored database, verifying in a thesaurus, and applying an Intelligence Character Recognition method on said unrecognised character and at least one neighbour character.

18. A method as recited in claim 1, further comprising:

quality controlling at least one of said each recognized character.

19. A method as recited in claim 1, further comprising an operator verifying the validity of at least one of said recognized character by comparing said at least one of said recognized character with the a corresponding character on the written document.

20. A method as recited in claim 1, further comprising:

formatting at least one of the assigned computer-readable codes.

21. A method as recited in claim 1, wherein said computer readable code is an ASCII code.

22. A method for recognizing a character corresponding to a written symbol, comprising:

providing a pixel representation of the written symbol;

segmenting said pixel representation, yielding a segmented symbol;

doing a vector quantization on said segmented symbol, yielding a vector representation of said symbol;

for possible class(i), i ranging from 1 to N, N being the number of different possible classes;

providing a vector representation(i) for each class(i);

computing a similarity score(i) using said vector representation (i) of said symbol and said vector representation for class(i); and

comparing said similarity score(i) to a threshold(i); and

if only one of said similarity score(x) is superior than the corresponding threshold(x), x ranging form 1 to N; and

assigning to said written symbol a computer-readable code corresponding to said class(x).

23. A method as recited in claim 22, wherein said vector representation(i) for each class(i) is obtained through an optimal elliptical separation method.

24. A method as recited in claim 22, wherein said threshold(i) is computed using a vector base.

25. A method as recited in claim 22, wherein computing a similartity score (i) is done using a separation method selected from the group consisting of an optimal linear separation method, an optimal spherical separation method, a support vector machine, a quadratic vector machine, a modified quadratic discriminant function, and a K nearest neighbor.

26. A method as recited in claim 22, wherein said computer readable code is an ASCII code.

27. A method for creating a vector base for a character recognition method comprising:

for each of a plurality of characters(i), i ranging from 1 to N, N being the number of characters;

providing a pixel representation (i)

doing a vector quantization on each pixel representation(i), yielding a vector representation (i) for each pixel representation (i);

computing a similarity score (x) for each of a plurality of predetermined classes, x ranging from 1 to M, M being the number of predetermined classes, by comparing said vector representation (i) of each pixel representation to a provided vector quantization (x) corresponding to said each of a plurality of predetermined class;

a) if, for one of said plurality of predetermined classes (x), said similarity score(x) is superior to a predetermined threshold(x), said character (i) being considered already known;

b) if not, verifying if said character (i) belongs to one of said classes (x);

i. if no, said character (i) is rejected;

ii. if yes, said character (i) is associated to the corresponding class (x).

28. A character recognition learning method comprising:

providing a database of recognized characters;

each recognized characters belonging to a class and being represented by a quantization vector;

the number of different classes being C;

for each recognized character (i) in said database, measuring a distance(i) between a first quantization vector representing said each recognized character(i) and a second quantization vector representing a character from another class;

said second quantization vector having the shortest distance(i) with said first quantization vector among all quantization vectors representing characters from a class different than the class to which said each character (i) belongs; and

for each class(j), j ranging from 1 to C;

for a predetermined number of recognized character(k) member of class(j);

defining a same class sphere(k) comprising only quantization vectors which are members of class(j) and having a distance with said quantization vectors(k) less than distance(k); and

determining a number(k) of quantization vectors representing a character from class(j) and being part of same class sphere(k);

for each same class sphere(k), from said same class sphere having the largest number(k) to said same class sphere having the smallest number(k), applying an elliptic deformation until members of other classes are reached, yielding an optimized quantization vector for class(k).

29. A system for translating a written document into a computer-readable document:

a document digitizer for creating a pixel representation of the document;

a controller coupled to said digitizer for;

receiving said pixel representation of the document;

identifying at least one field in said pixel representation of the document;

segmenting each said at least one field, yielding at least one segmented symbol for each said at least one field;

applying a character recognition method on each segmented symbol; and

assigning a computer-readable code to each recognized character resulting from said character recognition method;

an output device coupled to said controller for displaying segmented symbols, from said at least one segmented symbol, unrecognized by said character recognition method; and

at least one input device coupled to said controller for entering a computer-readable code of humanly recognized character among displayed segmented symbols.

30. A system as recited in claim 29, wherein said document digitizer is a scanner.

31. A system as recited in claim 29, wherein said document digitizer is includes an optical reader.

32. A system as recited in claim 29, wherein said controller is selected from the group consisting of a computer, an electronic control circuit and a programmed chip.

33. A system as recited in claim 29, further comprising a storing device.

34. A system as recited in claim 29, wherein said at least one input device includes at least one of a pointing device and a keyboard.

35. A system for translating a written document into a computer readable document comprising:

means for providing a pixel representation of the written document;

means for identifying at least one field into said pixel representation of the document;

means for segmenting each said at least one field, yielding at least one segmented symbol;

means for applying a character recognition method on each segmented symbol; and

means for assigning a computer-readable code to each recognized character resulting from said character recognition method.