Pattern recognizing apparatus and method

• US 6,104,833 A
• Filed: 01/03/1997
• Issued: 08/15/2000
• Est. Priority Date: 01/09/1996
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Suwa, Misako, Naoi, Satoshi, Hotta, Yoshinobu
• Primary Examiner(s): Au, Amelia
• Assistant Examiner(s): COUSO, YON JUNG
• Application Number:
  US08/778,621
• Time in Patent Office: 1,320 Days
• Field of Search: 382/202, 382/203, 382/179, 382/178, 382/177, 382/176, 382/175, 382/112, 382/289, 382/171, 382/197, 382/190, 382/187, 382/304, 382/199
• US Class Current: 382/190
• CPC Class Codes: G06V 30/242 Division of the character sequences into groups prior to recognition; Selection of dictionaries
• 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

An environment recognizing unit extracts the first through N-th states from an input image and calls data corresponding to the first through N-th states from the first through N-th pattern recognizing units to perform a recognizing unit.

Claims

1. A pattern recognizing apparatus comprising:

layout analyzing means for analyzing a layout of an input image, wherein ruled lines, character boxes and black-character-box-touching characters are extracted;

quality analyzing means for analyzing a quality of the input image, wherein obscure characters are detected by both of a global quality analysis and a local quality analysis;

correction analyzing means for analyzing a correction state of the input image, wherein deletion lines are extracted from the input image;

pattern recognizing means for performing a pattern recognizing process on each state of a process object of the input image, said pattern recognizing means comprising a recognizing dictionary provided for each quality of characters, and recognizes the characters by appropriately utilizing a plurality of recognizing dictionaries based on a quality analyzed by said quality analyzing means, said recognizing dictionary comprising at least one of a standard dictionary, an obscure-character dictionary, a deformed-character dictionary, a framed-white-character dictionary, and a texture-background-character dictionary, wherein character recognizing processes of basic character recognizing process, character string recognizing process, box-touching character recognizing process, obscure character recognizing process and deformed character recognizing process, and non-character recognizing processes of deletion line recognizing process and noise recognizing process are performed; and

environment recognizing means for performing a recognizing process by extracting the state of the process object of the input image based on the layout quality or correction state, and selecting one or more pattern recognizing processes which will be performed for each state of the process object.

2. The pattern recognizing apparatus according to claim 1, further comprising:

pattern detecting means for detecting a pattern for each state of the process object.

3. The pattern recognizing apparatus according to claim 1, wherein said environment recognizing means comprises:

intermediate process result table generating means for generating an intermediate process result table storing a recognizing process for each state performed by said pattern recognizing means for each state according to a determination result on each state of the process object.

4. The pattern recognizing apparatus according to claim 1, wherein

said environment recognizing means performs the recognizing process according to priority until reliability of the recognizing process exceeds a predetermined value when a plurality of recognizing processes are called for a specific process object.

5. The pattern recognizing apparatus according to claim 1, wherein

said pattern recognizing means performs the recognizing process using knowledge based on the state of the process object.

6. The pattern recognizing apparatus according to claim 1, wherein

said pattern recognizing means performs the recognizing process using identification functions based on the state of the process object.

7. The pattern recognizing apparatus according to claim 1, wherein

said environment recognizing means makes said pattern recognizing means perform a plurality of recognizing processes for each state in document units or form page units.

8. The pattern recognizing apparatus according to claim 1, wherein

said quality analyzing means determines for a specified area an obscure character when a value obtained by dividing (number of linked areas having areas, lengths, and widths smaller than respective predetermined thresholds) by (number of all linked areas of the specified area) is larger than a predetermined value.

9. The pattern recognizing apparatus according to claim 1, wherein

said quality analyzing means determines for a specified area an obscure character when a value obtained by dividing (total length of interpolations when obscure ruled lines are completed) by (total length of ruled lines) is larger than a predetermined value.

10. The pattern recognizing apparatus according to claim 1, wherein

said quality analyzing means determines for a specified area a deformed character when a value obtained by dividing (number of linked areas whose density of black picture elements is larger than a predetermined threshold) by (number of all linked areas of the specified area) is larger than a predetermined value.

11. A pattern recognizing apparatus comprising:

state extracting means for extracting a state of a process object from an input image, said state extracting means comprising;

character extracting means for extracting as a candidate for a character a link pattern having a predetermined size of area from the input image;

character string extracting means for extracting adjacent characters from a plurality of character candidates as a candidate for a character string;

ruled line extracting means for extracting ruled lines from the input image;

character box extracting means for extracting a pattern of four ruled lines

as a character box encompassing an area, said character box extracting means comprising;

attribute assigning means for assigning to the character box one attribute of a one character box, block character box, free-pitch character box, a regular table, and an irregular table based on a link state of the ruled lines and a size of a character box;

touching character extracting means for extracting a character touching the character box;

obscure character analyzing means for analyzing an obscure state of the input image;

deformed character analyzing means for analyzing a deformation state of the input image; and

correction feature extracting means for extracting a correction state of the input image;

pattern recognizing means for performing a pattern recognizing process on each state of the process object; and

recognizing process control means for allowing a recognizing process to be performed by calling one or more pattern recognizing processes for each state of the process object extracted by said state extracting means.

12. The pattern recognizing apparatus according to claim 11, wherein

said touching character extracting means comprises:

scanning means for scanning an inside of the character box extracted by said character box extracting means along the character box;

intersection detecting means for determining by said scanning whether or not an intersecting pattern exists;

determining means for determining a pattern to be a box touching character which intersects the character box when said intersection detecting means detects the pattern as an intersecting pattern;

partly-outside-character detecting means for determining whether or not the pattern is written partly outside to inside the scanned character box; and

removing means for removing the pattern written partly outside to inside the character box from box touching characters in the scanned character box.

13. The pattern recognizing apparatus according to claim 11, wherein

said pattern recognizing means comprises:

character recognizing means for recognizing a pattern of a character;

character string recognizing means for recognizing a pattern of a character string;

touching character recognizing means for recognizing a pattern of a character touching a character box;

obscure character recognizing means for recognizing a pattern of an obscure character;

deformed character recognizing means for recognizing a pattern of a deformed character;

corrected character recognizing means for recognizing a pattern of a corrected character; and

unique character recognizing means for recognizing a pattern of a unique character.

14. The pattern recognizing apparatus according to claim 13, wherein

said character recognizing means comprises:

a feature extracting unit for extracting a feature of an input unknown character as a feature vector;

a basic dictionary for preliminarily storing a feature of a character category as a feature vector; and

a collating unit for computing a distance between the feature vector of the unknown character and the feature vector of the character category, and recognizing as the unknown character a character category having a shortest distance between the character vectors of the unknown character.

15. The pattern recognizing apparatus according to claim 13, wherein

said character recognizing means comprises:

deformation computing means for computing a deformation of the unknown character by computing a number of convexity and concavity on an outline of an unknown character;

a segment dictionary for preliminarily storing a feature of a character category as a character vector;

a character segment generating unit for dividing an outline of a character at end points and generating character segments;

correspondence generating unit for generating a correspondence between a character segment of an unknown character and a character segment of the character category in a way that accumulated values of angle variations of the character segments are close to each other when the deformation indicates a value larger than a predetermined value; and

a collating unit for computing a distance between the feature vector of the unknown character and the feature vector of the character category based on the correspondence, and recognizing as the unknown character a character category having a shortest distance between the character vectors of the unknown character.

16. The pattern recognizing apparatus according to claim 13, wherein

said character string recognizing means comprises:

discriminant phase generating means for classifying sample data represented by P feature values indicating a feature of a pattern into a first group of successful detection and a second group of unsuccessful detection, and generating in a P-dimensional space a discriminant phase at an equal distance from centers of gravity of the first and second groups;

reliability computing means for obtaining a distance between positions of P feature values of input data and the discriminant phase in the P-dimensional space, and computing detection reliability of the input data based on the obtained distance; and

detection determining means for determining a position where the input data is detected based on the detection reliability of the input data and recognition reliability of detected input data.

17. The pattern recognizing apparatus according to claim 13, wherein

said touching character recognizing means comprises:

character box removing means for removing a character box from a box touching character;

character completing means for completing a character from an obscure character by removing the character box according to the direction of lines separated by removing the character box;

re-completing means for completing a pattern, which is separated when the character box is removed, by interpolating lines which overlap the character box before removing the character box;

learning pattern generating means for generating a learning pattern in which a character and a character box touch each other under a predetermined condition;

a knowledge table for storing recognition reliability of the learning pattern together with the predetermined condition, and storing a character re-recognizing method for the learning pattern when the recognition reliability is lower than a predetermined value; and

character re-recognizing means for re-recognizing a character by the character re-recognizing method stored in the knowledge table when a pattern completed by said character completing means or a pattern completed by said re-completing means meets the predetermined condition.

18. The pattern recognizing apparatus according to claim 13, wherein

said obscure character recognizing means comprises:

a feature extracting unit for extracting a feature of an input unknown character as a feature vector;

an obscure-character dictionary preliminarily storing features of character categories of obscure characters;

a collating unit for computing a distance between the feature vector of the unknown character and the feature vector of the character category, and recognizing as the unknown character a character category having a shortest distance between the character vectors of the unknown character.

19. The pattern recognizing apparatus according to claim 13, wherein

said deformed character recognizing means comprises:

a feature extracting unit for extracting a feature of an input unknown character as a feature vector;

a deformed-character dictionary preliminarily storing features of character categories of deformed characters;

a collating unit for computing a distance between the feature vector of the unknown character and the feature vector of the character category, and

recognizing as the unknown character a character category having a shortest distance between the character vectors of the unknown character.

20. The pattern recognizing apparatus according to claim 13, wherein

said corrected character recognizing means comprises:

histogram value computing means for computing a histogram value in a predetermined direction of a pattern extracted as a candidate for a corrected character;

line removing means for removing a line whose histogram value is larger than a predetermined value;

completing means for generating a completed pattern by interpolating obscure portion of the pattern which becomes obscure by removing the line;

character recognizing means for recognizing a character in the completed pattern; and

removed line recognizing means for regarding a line removed by said line removing means as a removed line when the completed pattern is recognized as a character, and regarding the line removed by said line removing means as a portion of a character when the completed pattern is rejected.

21. The pattern recognizing apparatus according to claim 13, wherein

said unique character recognizing means comprises:

clustering means for generating a plurality of clusters containing characters handwritten by a single writer as elements in each category after clustering the handwritten characters for each category;

cluster extracting means for extracting a cluster containing a number of elements smaller than a predetermined value from the cluster generated by said clustering means;

inter-cluster-distance computing means for computing a distance between a first cluster extracted by said cluster extracting means and a second cluster belonging to another category; and

category correcting means for integrating the first and second clusters when the distance between the first and second clusters is smaller than a predetermined value and correcting a category of handwritten characters belonging to the first cluster into a category of the second cluster.

22. The pattern recognizing apparatus according to claim 13, wherein

said recognizing process control means invokes said character recognizing means when said character extracting means extracts a candidate for a character, invokes said character string recognizing means when said character string extracting means extracts a candidate for a character, invokes said touching character recognizing means when said touching character extracting means extracts a character touching a character box, invokes said obscure character recognizing means when said obscure character analyzing means extracts an obscure state of the input image, invokes said deformed character recognizing means when said deformed character analyzing means extracts a deformed state of the input image, and invokes said corrected character recognizing means when said correction feature extracting means extracts a correction state of the input image.

23. The pattern recognizing apparatus according to claim 13, wherein

said recognizing process control means invokes said unique character recognizing means when character reliability determined by said character recognizing means is larger than a predetermined value.

24. The pattern recognizing apparatus according to claim 11, wherein

said recognizing process control means comprises:

process order control rule storage means storing an invoking procedure indicating which recognizing process performed by said pattern recognizing means is to be invoked based on an extraction result of a state of a process object from an input image;

a process order table storing an invoking order when a plurality of recognizing processes on a specific object are invoked by said pattern recognizing means;

intermediate process result table generating means for generating an intermediate process result table indicating an order of performing recognizing processes by said pattern recognizing means according to the invoking procedure and order for each process object; and

process performing rule storage means storing a procedure of instructing a subsequent process based on a result of a recognizing process entered on said intermediate process result table.

25. A pattern recognizing apparatus, comprising:

state extracting means for extracting a state of a process object from an input image, said state extracting means comprising;

character extracting means for extracting as a candidate for a character a link pattern having a predetermined size of area from the input image;

character string extracting means for extracting adjacent characters from a plurality of character candidates as a candidate for a character string;

ruled line extracting means for extracting ruled lines from the input image;

character box extracting means for extracting a pattern of four ruled lines as a character box encompassing an area;

touching character extracting means for extracting a character touching the character box;

obscure character analyzing means for analyzing an obscure state of the input image;

deformed character analyzing means for analyzing a deformation state of the input image; and

correction feature extracting means for extracting a correction state of the input image, said correction feature extracting means comprising;

line density computing means for computing a line density in a specified direction by counting a number of time at which a white picture element turns black or a black picture element turns white when an image in a rectangular area is scanned in the specified direction;

Euler number computing means for computing an Euler number by subtracting a number of holes contained in an image from a number of link elements in the image;

black picture element density computing means for computing a black picture element density by computing a ratio of an area of an object image to an area of a rectangle circumscribing the object image;

line density determining means for determining the image circumscribed by the rectangle to be a candidate for a corrected character when the line density exceeds a predetermined value;

Euler number determining means for determining the image to be a candidate for a corrected character when the Euler number is negative and has an absolute number larger than a predetermined value; and

black picture element density determining means for determining the image to be a candidate for a corrected character when the black picture element density exceeds a predetermined value;

pattern recognizing means for performing a pattern recognizing process on each state of the process object; and

recognizing process control means for allowing a recognizing process to be performed by calling one or more pattern recognizing processes for each state of the process object extracted by said state extracting means.

26. A pattern recognizing apparatus comprising:

first pattern recognizing means for recognizing a pattern of a process object in a first state;

second pattern recognizing means for recognizing a pattern of a process object in a second state; and

environment recognizing means for extracting a state of the process object from an input image, instructing said first pattern recognizing means to perform a recognizing process on a process object in the first state, and instructing said second pattern recognizing means to perform a recognizing process on a process object in the second state;

wherein

said first and second pattern recognizing means comprise a recognizing dictionary provided for each quality of-characters, and recognize the characters by appropriately utilizing a plurality of recognizing dictionaries based on a quality of the input image, said recognizing dictionary comprising at least one of a standard dictionary, an obscure-character dictionary, a deformed-character dictionary, a framed-white-character dictionary, and a texture-background-character dictionary,

wherein character recognizing processes of basic character recognizing process, character string recognizing process, box-touching character recognizing process, obscure character-recognizing process and deformed character recognizing process, and non-character recognizing processes of deletion line recognizing process and noise recognizing-process are performed.

27. The pattern recognizing apparatus according to claim 26, wherein

said environment recognizing means instructs said first and second pattern recognizing means to perform recognizing processes on a process object when the first and second states are extracted from a single process object.

28. The pattern recognizing apparatus according to claim 26, wherein

said environment recognizing means computes reliability indicating certainty about recognition results obtained by said first and second pattern recognizing means, and outputs the recognition results as final results when the reliability is larger than a predetermined value.

29. A computer-readable storage medium used to direct a computer to perform the functions of:

extracting a state of a process object from an input image, wherein said extracting function further comprises the functions of;

extracting a character as a candidate for a character a link-pattern having a predetermined size of area from the input image;

extracting adjacent characters from a plurality of character candidates as a candidate for a character string;

extracting ruled lines from the input image;

extracting a pattern of four ruled lines as a character box encompassing an area, wherein said extracting function further comprises the function of;

assigning to the character box one attribute of a one character box, block character box, free-pitch character box, a regular table, and an irregular table based on a link state of the ruled lines and a size of a character box;

extracting a character touching the character box;

analyzing an obscure state of the input image;

analyzing a deformation state of the input image; and

extracting a correction state of the input image;

performing a pattern recognizing process exclusively for a first state on the process object in the first state; and

performing a pattern recognizing process exclusively for a second state on the process object in the second state.

30. A pattern recognizing method comprising the steps of:

extracting a state of a process object from an input image, wherein said extracting step further comprises the step of;

extracting a character as a candidate for a character a link pattern having a predetermined size of area from the input image;

extracting adjacent characters from a plurality of character candidates as a candidate for a character string;

extracting a pattern of four ruled lines as a character box encompassing an area, wherein said extracting step further comprises the step of;

assinging to the character box one attribute of a one character box block, character box, free-pitch character box, a regular table, and an irregular table, based on a link state of the ruled lines and a size of a character box;

extracting a character touching the character box;

analyzing an obscure state of the input image;

analyzing a deformation state of the input image; and

extracting a correction state of the input image; and

recognizing a pattern by selecting for the process object a recognizing process appropriate for the state.

31. A pattern recognizing method comprising the steps of:

extracting a state of a process object from an input image, wherein said extracting step further comprises the steps of;

extracting a character as a candidate for a character a link pattern having a predetermined size of area from the input image;

extracting adjacent characters from a plurality of character candidates as a candidate for a character string;

extracting ruled lines from the input image;

extracting a pattern of four ruled lines as a character box encompassing an area, wherein said extracting step further comprises the step of;

assigning to the character box one attribute of a one character box, block character box, free-pitch character box, a regular table, and an irregular table based on a link state of the ruled lines and a size of a character box;

extracting a character touching the character box;

analyzing an obscure state of the input image;

analyzing a deformation state of the input image; and

extracting a correction state of the input image;

performing a pattern recognizing process exclusively for a first state on the process object in the first state; and

performing a pattern recognizing process exclusively for a second state on the process object in the second state.