System and method for separating foreground information from background information on a document

• US 6,064,762 A
• Filed: 08/19/1996
• Issued: 05/16/2000
• Est. Priority Date: 12/20/1994
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Haenel, Walter
• Primary Examiner(s): Tran, Phuoc
• Application Number:
  US08/696,960
• Time in Patent Office: 1,366 Days
• Field of Search: 382/170, 382/171, 382/176, 382/168-172, 382/173, 358/462
• US Class Current: 382/171
• CPC Class Codes: G06V 10/28 Quantising the image, e.g. histogram thresholding for discrimination between background and foreground patterns

Abstract

Foreground information is separated from background information on a document where the foreground information is superimposed in an additive or subtractive manner on the background information. The document is divided into a plurality of segments and a frequency distribution of extreme values of the signal intensity in each of the segments is determined. The frequency distribution so determined exhibits one main mode (background mode) which essentially contains the background information. If an adequate foreground/background separation cannot be achieved with the first two steps, the determination of a frequency distribution of signal intensities of the whole document is effected in a third step and a sharper separation effected by a fourth step in which a joint evaluation of the two frequency distributions is determined. To determine a threshold value of a signal intensity for the background information in the document, this threshold value is derived in a fifth step, either from the flank of the background mode towards the foreground information or from one of the flanks of a further main mode opposite the background mode, preferably by a linear approximation of a point on one of the flanks of the two main modes.

Claims

1. Method of separating foreground information from background information on a document where the foreground information is superimposed on the background information, the steps of the method comprising:

dividing the document into a plurality of segments with a plurality of segments including an expected threshold value and a plurality of segments containing only background information;

generating from each said segment at least one signal representative of information within said segment;

determining at least one first frequency distribution of at least one extreme value of the intensity of said signals in a plurality of said segments, where the determined frequency distribution comprises one main mode representative of said background information;

determining a second frequency distribution of the intensity of signals from a plurality of said segments; and

jointly evaluating said first frequency distribution and said second frequency distribution to determine said threshold value.

2. Method in accordance with claim 1, wherein the step of jointly evaluating is effected by superimposition, preferably an additive or subtractive superimposition, of said first frequency distribution and said second frequency distribution.

3. Method in accordance with claim 1 further including a step of eliminating small subsidiary nodes by smoothing at least one of said first and/or second frequency distributions and/or the superimposition contained in the step of jointly evaluating.

4. Method in accordance with claim 3, wherein the smoothing step includes summing a number of adjacent points with weighting and normalizing the sum of the weights.

5. Method in accordance with claim 4, wherein the smoothing step uses a function chosen from a Gaussian function and a rectangular function.

6. Method in accordance with claim 1 further including

a step of deriving a threshold value of a signal intensity of the background information in the document, either:

from that flank of a first main background mode which is directed towards foreground information, or

from that flank of a second main mode which is directed opposite to said background mode.

7. Method in accordance with claim 6, wherein the step of deriving the threshold value exhibits a step of a linear approximation of a slope of a point on at least one of said flanks of said first or second main modes.

8. Method in accordance with claim 7, characterized in that the step of linear approximation is carried out on a point (P_max) with a maximum flank slope on each of said first and second main modes.

9. Method in accordance with claim 6, wherein the step of deriving the threshold value exhibits a step of weighting the threshold value obtained by linear approximation with that from areas enclosed by said two main modes.

10. Method in accordance with claim 6, further including a step of applying said threshold value for cleaning up background information in the document.

11. Method in accordance with claim 10, characterized in that said information within said document is divided up into information with signal intensities above and below said threshold value.

12. Method in accordance with claim 11 further including a step of eliminating that region of the information which contains said background information.

13. Method in accordance with claim 12, characterized in that, in a black and white conversion of electronic grey scale images, all information with a grey value lighter than a grey value corresponding to the threshold value is set to a grey value of `white`.

14. Method in accordance with claim 13, wherein all remaining information with a grey value darker than the grey value corresponding to the threshold value is set to a grey value of "black".

15. The method of claim 1 wherein said document comprises a highly structured background, and further comprises the step of reducing said background.

16. A program storage device readable by a machine, tangibly embodying a program of instructions executable by a machine to perform method steps for separating foreground information from background information on a document where the foreground information is superimposed on the background information, said method steps comprising:

dividing the document into a plurality of segments with a plurality of segments including an expected threshold value and a plurality of segments containing only background information;

generating from each said segment at least one signal representative of information within said segment;

determining at least one first frequency distribution of at least one extreme value of the intensity of said signals in a plurality of said segments, where the determined frequency distribution comprises one main mode representative of said background information;

determining a second frequency distribution of the intensity of signals from a plurality of said segments; and

jointly evaluating said first frequency distribution and said second frequency distribution to determine said threshold value.

17. An article of manufacture comprising:

a computer useable medium having computer readable program code means embodied therein for separating foreground information from background information on a document where the foreground information is superimposed on the background information, the computer readable program means in said article of manufacture comprising;

computer readable program code means for causing a computer to effect dividing the document into a plurality of segments with a plurality of segments including an expected threshold value and a plurality of segments containing only background information;

computer readable program code means for causing a computer to effect generating from each said segment at least one signal representative of information within said segment;

computer readable program code means for causing a computer to effect determining at least one first frequency distribution of at least one extreme value of the intensity of said signals in a plurality of said segments, where the determined frequency distribution comprises one main mode representative of said background information;

computer readable program code means for causing a computer to effect determining a second frequency distribution of the intensity of signals from a plurality of said segments; and

computer readable program code means for causing a computer to effect jointly evaluating said first frequency distribution and said second frequency distribution to determine said threshold value.