Method of OCR template enhancement by pixel weighting

• US 5,379,349 A
• Filed: 09/01/1992
• Issued: 01/03/1995
• Est. Priority Date: 09/01/1992
• Status: Expired due to Fees

• Current Assignee: Canon Inc.
• Original Assignee: Canon USA, Inc. (Canon Inc.)
• Inventors: Avi-Itzhak, Hadar
• Primary Examiner(s): Moore, David K.
• Assistant Examiner(s): Cammarata, Michael
• Application Number:
  US07/937,732
• Time in Patent Office: 854 Days
• Field of Search: 382/15, 382/14, 382/41, 382/30, 382/23, 382/39, 382/9, 382/26, 382/36, 382/34
• US Class Current: 382/160
• CPC Class Codes: G06F 18/28 Determining representative reference patterns, e.g. by averaging or distorting; Generating dictionaries

Abstract

A library of L unenhanced images (pixel bit maps) is enhanced for optical character recognition (OCR) with respect to a pre-existing group of G input symbols (pixel bit maps) for creating a library of G recognition enhanced templates (pixel bit maps) of the G input symbols. The enhancement is accomplished by comparing each image of the library with each symbol of the group, and weighting the images with the highest potential for confusion. A primary comparison C* and a secondary comparison C** are identified from the L comparisons within each of the G sets of comparisons. A recognition margin is determined between each pair of identified comparisons C* and C**. The single pair of identified comparisons C* and C** is selected forming the smallest recognition margin M*. The single pair of images I_j * and I_j ** underlying the pair of identified comparisons C* and C** is identified. Certain pixels of the closest pixel image I_j * and the next closest pixel image I_j ** are weighted in order to increase the recognition margin M* therebetween. The steps are iterated until the library of pixel images has become a library of sufficiently enhanced symbol templates. The weighted pixel abberations generated in the enhanced templates are not present in the corresponding pixel symbol of the pre-existing group of G pixel symbols.

Claims

1. The method of matching an unknown input pixel symbol with a library of enhanced pixel templates by recognition enhancement of a library of L unenhanced pixel images (I₁ I₂ I₃ . . . I_j . . . I_L) with respect to a pre-existing group of G unknown input pixel symbols (S₁ S₂ S₃ . . . S_i . . . S_G) for providing a library of G recognition enhanced pixel templates (T₁ T₂ T₃ . . . T_i . . . T_G) of the G pixel symbols, comprising the steps of:

providing a library of L unenhanced pixel images (I₁ I₂ I₃ . . . I_j . . . I_L) to be enhanced to provide a library of G recognition enhanced pixel templates (T₁ T₂ T₃ . . . T_i . . . T_G);

providing a pre-existing group of G unknown input pixel symbols (S₁ S₂ S₃ . . . S_i . . . S_G);

comparing each of the G unknown input pixel symbols with each of the L pixel images to obtain G×

L comparisons forming G sets of L comparisons (C₁ C₂ C₃ . . . C_j . . . C_L), one set of L comparisons for each unknown input pixel symbol S_i of the G pixel symbols, each set of comparisons having a comparison C_i for each pixel image I_j ;

identifying the primary comparison C* from the L comparisons within each of the G sets of comparisons having the closest comparison with the unknown input pixel symbol S_i for that set of comparisons forming a collection of G primary comparisons C* (C₁ * C₂ * C₃ * . . . C_i * . . . C_L *);

identifying the secondary comparison C** from the L-1 remaining comparisons within each of the G sets of comparisons having the next closest comparison with the unknown input pixel symbol S_i for that set of comparisons forming a collection of G secondary comparisons C** (C₁ ** C₂ ** C₃ ** . . . C_i ** . . . C_L **), to provide G pairs of identified comparisons C* and C**, one pair from each of the G sets of comparisons;

determining G recognition margins (M₁ M₂ M₃ . . . M_i M_G), one recognition margin between each pair of identified comparisons C* and C**;

selecting the single pair of identified comparisons C* and C** having the smallest recognition margin M* of all of the G pairs of identified comparisons from the G sets of comparisons;

identifying the single pair of pixel images I* and I** corresponding to the pair of identified comparisons C* and C**;

weighting certain pixels of the closest pixel image I* and the next closest pixel image I** corresponding to the selected pair of identified comparisons C* and C** in order to incrementally increase the recognition margin M* therebetween causing the pixel images to become the closest pixel template T* or the next closest pixel template T** or both;

iterating the comparing, identifying, determining, selecting, and weighting steps until the library of pixel images has become a library of enhanced symbol templates (T₁ T₂ T₃ . . . T_i . . . T_G) which have been recognition enhanced with respect to the pre-existing group of G unknown input pixel symbols (S₁ S₂ S₃ . . . S_i . . . S_G), at least some templates of which have weighted pixel abberations not present in the corresponding pixel symbol of the pre-existing group of G unknown input pixel symbols; and

matching an unknown input pixel symbol of the group of G pixel symbols (S₁ S₂ S₃. . . S_i . . . S_G) with the library of enhanced templates (T₁ T₂ T₃ . . . T_i . . . T_G) by comparing the unknown pixel symbol with each of the enhanced pixel templates in the library of enhanced templates and selecting the enhanced template with the closest comparison.

2. The method of claim 1, wherein the recognition enhancement of the pixel templates is terminated when the smallest recognition margin is greater than a predetermined minimum value.

3. The method of claim 1, wherein the recognition enhancement of the pixel templates is terminated when the incremental increase in the smallest recognition margin each iteration is smaller than a predetermined minimum increase.

4. The method of claim 1, wherein the recognition enhancement of the pixel templates is terminated when a specified number of weighting iterations have been executed.

5. The method of claim 1, wherein the recognition enhancement of the pixel templates is terminated when a preassigned period of iteration processing time has expired.

6. The method of claim 1, wherein the recognition enhancement of the pixel templates is terminated when the individual templates in clusters of similarly shaped templates have progressed to the same recognition margin and have become mutual anti-characters.

7. The method of claim 1, wherein L is greater than G and G is equal to T.

8. The method of claim 1, wherein the group of G pixel symbols are alpha-numeric symbols and the library of T pixel templates are the same alpha-numerics enhanced by weighted pixel abberations.

9. The method of claim 8, wherein L is equal to G, and G is equal to T.

10. The method of claim 9, wherein the library of G pixel images are alpha-numeric symbols corresponding to the alpha-numeric symbols of the group of G pixel symbols.

11. The method of claim 9, wherein the library of G pixel images are alpha-numeric symbols identical to the alpha-numeric symbols of the group of G pixel symbols.

12. The method of claim 1, wherein the G×

L comparisons are numerical coefficients of comparison, the value of which indicates the degree of pixel similarity between the pixel symbol S_i and the pixel image I_j under comparison.

13. The method of claim 12, wherein a coefficient having a high value indicates a close comparison between S_i and I_j, and a coefficient having a low value indicates a remote comparison between S_i and I_j.

14. The method of claim 12, wherein the recognition margin is the difference between the comparisons C* and C** of each selected pair of comparisons.

15. The method of claim 14, wherein the recognition enhancement with respect to a particular pixel symbol S_i involves maximizing the minimum recognition margin between the primary comparison C* and the maximum secondary comparison C** which form the selected pair of identified comparisons C* and C** for the pixel symbol S_i, in the general relationship:

space="preserve" listing-type="equation">maximize M=min[C*-max(C**)]

where

M is the recognition margin between C* and C**,

C* is the primary comparison for the template T* which is the closest template in the library to the pixel symbol S_i, and

C** is the secondary comparison for the template T** which is the second closest template in the library to the pixel symbol S_i.

16. The method of claim 15, wherein only the closest pixel image I* is weighted causing the closest pixel image I* to become the closest pixel template T*.

17. The method of claim 16, wherein the weighting added to the closest template T* each iteration is determined by the first derivative of the recognition margin M* relative to the template T*:

space="preserve" listing-type="equation">W*=u*(dM/dT*)=u*(dC*/dT*-dC**/dT*)

where

W* is the weighting added each iteration, and

u* is a weighting factor mu* for dM/dT*.

18. The method of claim 17, wherein each iteration of the enhancement process produces a new T* template which is slightly different from the old T* template:

##EQU4## where n is the number of the iteration,

T*_n+1 is the new T* template, and

T*_n is the old T* template.

19. The method of claim 15, wherein only the next closest pixel image I** is weighted causing the next closest pixel image I** to become the next closest pixel template T**.

20. The method of claim 19, wherein the weighting added to the next closest template T** each iteration is determined by the first derivative of the recognition margin M** relative to the template T**:

space="preserve" listing-type="equation">W**=u**(dM/dT**)=u**(dC*/dT**-dC**/dT**)

where

W** is the weighting added each iteration, and

u** is a weighting factor mu** for dM/dT**.

21. The method of claim 20, wherein each iteration of the enhancement process produces a new T** template which is slightly different from the old T** template:

##EQU5## where

n is the number of the iteration,

T*_n+1 is the new T** template, and

T**_n is the old T** template.

22. The method of claim 15, wherein both the closest pixel image I* and the next closest pixel image I** are weighted causing the closest pixel image I* to become the closest pixel template T* and the next closest pixel image I** to become the next closest pixel template T**.

23. The method of claim 22, wherein the weighting added to T* and to template T** each iteration are determined by the first derivative of the recognition margins M* and M** relative to templates T* and T**:

space="preserve" listing-type="equation">W*=u*(dM/dT*)=u*(dC*/dT*-dC**/dT*)

space="preserve" listing-type="equation">W**=u**(dM/dT**)=u**(dC*/dT**-dC**/dT**)

where

W* is the weighting added to T* each iteration,

u* is a weighting factor mu* for dM/dT*,

W** is the weighting added to T** each iteration, and

u** is a weighting factor mu** for dM/dT**.

24. The method of claim 23, wherein the weighting factor u* is equal to the weighting factor u**.

25. The method of claim 23, wherein each iteration produces a new T* and T** templates which are slightly different from the old T* and T** templates:

space="preserve" listing-type="equation">T*.sub.n+1 =T*.sub.n +W*=T*.sub.n +u*(dC*/dT*-dC**/dT*)

space="preserve" listing-type="equation">T**.sub.n+1 =T**.sub.n +W**=T**.sub.n +u**(dC*/dT**-dC**/dT**)

where

n is the number of the iteration,

T*_n+1 is the new T* template,

T*_n is the old T* template,

T**_n+1 is the new T** template, and

T**_n is the old T** template.

26. The method of claim 12, wherein the value of each numerical coefficient of comparison C_j is based on a pixel by pixel comparison between each pixel of pixel symbol S_i and each pixel of pixel image I_j under comparison.

27. The method of claim 26, wherein the pixel by pixel comparison is the dot product between each pixel of pixel symbol S_i and each pixel of pixel image I_j under comparison.

28. The method of claim 26, wherein the pixel by pixel comparison is based on the Cauchy-Shwartz Function:

##EQU6## where (S_i) is the input symbol under comparison,

(T_i) is the enhanced template under comparison,

(∥

S_i ∥

) is the symbol norm, and

(∥

T_i ∥

) is the template norm.