Source: http://www.google.com/patents/US5097520?ie=ISO-8859-1
Timestamp: 2015-04-18 15:56:26
Document Index: 715439140

Matched Legal Cases: ['Application No. 60', 'Application No. 60', 'art 1', 'art 5', 'art 5', 'art 6', 'art 7', 'art 9', 'art 2', 'art 6', 'art 41', 'art 27']

Patent US5097520 - Method of obtaining optimum threshold values - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsA binarization method obtains an optimum threshold value for binarization which is used when converting a multi-level image data which describes an input image into a black-and-white bi-level image data. The binarization method includes the steps of counting a first number of black picture elements by...http://www.google.com/patents/US5097520?utm_source=gb-gplus-sharePatent US5097520 - Method of obtaining optimum threshold valuesAdvanced Patent SearchPublication numberUS5097520 APublication typeGrantApplication numberUS 07/457,933Publication dateMar 17, 1992Filing dateDec 27, 1989Priority dateJan 20, 1989Fee statusPaidAlso published asDE4001613A1, DE4001613C2, US5351313Publication number07457933, 457933, US 5097520 A, US 5097520A, US-A-5097520, US5097520 A, US5097520AInventorsGoroh Bessho, Michiyoshi TachikawaOriginal AssigneeRicoh Company, Ltd.Export CitationBiBTeX, EndNote, RefManPatent Citations (5), Referenced by (15), Classifications (9), Legal Events (4) External Links: USPTO, USPTO Assignment, EspacenetMethod of obtaining optimum threshold values
US 5097520 AAbstract
1. A binarization method of obtaining an optimum threshold value for binarization which is used when converting a multi-level image data which describes an input image into a black-and-white bi-level image data, said binarization method comprising the steps of:obtaining cumulative values of histograms for each tone level from a darkest tone level to a predetermined tone level which is the second lightest tone level, each of said histograms being a number of picture elements having a corresponding one of the tone levels other that the lightest tone level; obtaining percentages of the cumulative values of histograms for each of the tone levels darker than the predetermined tone level with respect to the cumulative value of histograms for the predetermined tone level, so as to normalize the cumulative values of histograms for each of the tone levels darker than the predetermined tone level; and determining the optimum threshold value for binarization based on the percentages which are obtained for each of the tone levels. 2. The binarization method as claimed in claim 1 wherein said step of determining the optimum threshold value detects an arbitrary tone level at which the picture elements have the darkest tone level and obtains the optimum threshold based on said arbitrary tone level.
3. The binarization method as claimed in claim 1 wherein said step of determining the optimum threshold value includes:detecting a tone of the input image based on a rate of change of the percentages which are obtained for each of the tone levels; and obtaining the optimum threshold value based on said rate of change. 4. The binarization method as claimed in claim 1 which further comprises the step of obtaining the black-and-white bi-level image data by carrying out a binarization using said optimum threshold value which is determined by said step of determining the optimum threshold value.
5. The binarization method as claimed in claim 1 which further comprises the steps of setting said optimum threshold value which is determined by said step of determining the optimum threshold value in a scanner which scans the input image, and obtaining the black-and-white bi-level image data directly from an output of the scanner.
6. A binarization method of obtaining an optimum threshold value for binarization which is used when converting a multi-level image data which describes an input image into a black-and-white bi-level image data, said binarization method comprising the steps of:dividing the input image into a plurality of regions; obtaining cumulative values of histograms within each region for each of tone levels from a darkest tone level to a predetermined tone level which is the second lightest tone level, each of said histograms being a number of picture elements having a corresponding one of the tone levels other than the lightest tone level; obtaining percentages of the cumulative values of histograms within each region for each of the tone levels darker than the predetermined tone level with respect to the cumulative value of histograms for the predetermined tone level, so as to normalize the cumulative values of histograms for each of the tone levels darker than the predetermined tone level; and determining the optimum threshold value for binarization with respect to each region based on the percentages which are obtained for each of the tone levels. 7. The binarization method as claimed in claim 6 wherein said step of determining the optimum threshold value detects an arbitrary tone level at which the picture elements have the darkest tone level within each region and obtains the optimum threshold value with respect to each region based on said arbitrary tone level.
8. The binarization method as claimed in claim 6 wherein said step of determining the optimum threshold value includes:detecting a tone of the input image within each region based on a rate of change of the percentages which are obtained for each of the tone levels; and obtaining the optimum threshold value with respect to each region based on said rate of change. 9. The binarization method as claimed in claim 6 which further comprises the step of obtaining the black-and-white bi-level image data by carrying out a binarization with respect to each region using said optimum threshold value which is determined by said step of determining the optimum threshold value.
10. The binarization method as claimed in claim 6 which further comprises the steps of setting said optimum threshold value which is determined for each region by said step of determining the optimum threshold value in a scanner which scans the input image, and obtaining the black-and-white bi-level image data directly from an output of the scanner.
11. The binarization method as claimed in claim 1 wherein said step obtaining cumulative values of histograms includes:obtaining the histograms respectively related to the number of picture elements having one of the tone levels other than the lightest tone levels; and obtaining the cumulative values of the histograms. 12. The binarization method as claimed in claim 1 wherein said step of determining the optimum threshold value includes:obtaining an arbitrary normalized cumulative value of histograms which most closely approximates a preset normalized cumulative value of the histograms; and determining a tone level corresponding to the arbitrary normalized cumulative value of histograms as the optimum threshold value. 13. The binarization method as claimed in claim 1 wherein said step of determining the optimum threshold value includes:detecting an arbitrary tone level at which the picture elements have the darkest tone level; and determining the optimum threshold value by referring to a table which contains a relationship between tone levels and corresponding optimum threshold value using the detected arbitrary tone level. 14. The binarization method as claimed in claim 1 wherein said step of determining the optimum threshold value includes:detecting a rate of change of the percentages; and determining the optimum threshold value by referring to a table which contains a relationship between rates of change and corresponding optimum threshold values using the detected rate of change. 15. The binarization method as claimed in claim 6 wherein said step of obtaining cumulative values of histograms includes:obtaining within each region the histograms respectively related to the number of picture elements having one of the tone levels other than the lightest tone levels; and obtaining the cumulative value of the histograms within each region. 16. The binarization method as claimed in claim 6 wherein said step of determining the optimum threshold value includes:obtaining an arbitrary normalized cumulative value of histograms within each region which most closely approximates a preset normalized cumulative value of the histograms; and determining a tone level corresponding to the arbitrary normalized cumulative value of histograms as the optimum threshold value within each region. 17. The binarization method as claimed in claim 6 wherein said step of determining the optimum threshold value includes:detecting an arbitrary tone level at which the picture elements have the darkest tone level within each region; and determining the optimum threshold value within each region by referring to a table which contains a relationship between tone levels and corresponding optimum threshold values using the detected arbitrary tone level. 18. The binarization method as claimed in claim 6 wherein said step of determining the optimum threshold value includes:detecting a rate of change of the percentages within each region; and determining the optimum threshold value within each region by referring to a table which contains a relationship between rates of change and corresponding optimum threshold values using the detected rate of change. Description
Various binarization methods have been proposed. For example, the mode method, the differential histogram method and the p-Tile method are explained in H. Tamura, "Introduction to Computer Image Processing", Soken Shuppan (publisher), 1985, pp. 66-68. The mode method obtains a histogram of tones of the given image, and when the histogram has a distribution with two peaks, the threshold value is set to a valley between the two peaks. The differential histogram method determines the threshold value by using a differentiated value of the tone of the image (that is, the rate of change of the tone) instead of directly using the tone of the image, because it can be regarded that a boundary between an object and a background in the image is a portion where the tone suddenly changes. The p-Tile method processes the image with reference to the total area of the image.
On the other hand, N. Ohtsu, "Method of Determining Threshold Value from Tone Distribution", Article No. 145, National Conference of Information Group of the Electronic Communication Society, 1977 proposes a method of determining the threshold value from a tone distribution. This method only uses the zero order and first order moments of the tone distribution and determines the optimum threshold value based on an integration.
Furthermore, an optimum binarization method is proposed in a Japanese Published Patent Application No. 60-37952. According to this system, a multi-level video signal is stored in a video buffer, and a video signal which is read out from the video buffer is binarized by a slicing circuit which has a variable slicing level. The multi-level video signal is sliced at different slicing levels and is converted into a binarized (bi-level) video signal, and a line width amplification is obtained for each of the bi-level video signals. The line width amplification is a ratio is defined as (number of black picture elements)/(number of surrounding picture elements), where the number of black picture elements are the number of black picture elements making up the character and the number of surrounding picture elements are the number of white picture elements surrounding the character. The slicing level of the slicing circuit is set based on the obtained line width amplifications and a reference line width amplification.
In addition, it was found from experiments that the optimum binarization method proposed in the Japanese Published Patent Application No. 60-37952 cannot stably obtain the optimum threshold value depending on the tone of the document image.
FIG. 9 is a system block diagram showing an image processing system to which a-fourth embodiment of the binarization method according to the present invention is applied;
FIGS. 17A and 17B are flow charts showing an operation of the block system shown in FIG. 16 for explaining an operation of the seventh embodiment;
FIGS. 20A and 20B are flow charts showing an operation of the block system shown in FIG. 19 for explaining an operation of the eighth embodiment;
FIGS. 22A and 22B are flow charts showing an operation of the block system shown in FIG. 21 for explaining an operation of the ninth embodiment;
FIG. 24 is a flow chart showing an operation of the block system shown in FIG. 23 for explaining a operation of the tenth embodiment;
A multi-level image reading part 1 reads a multi-level image data which is obtained from a scanner 3 which scans a document image, and stores the multi-level image data in a multi-level image memory 4. In this embodiment, the multi-level image data has 16 gradation levels "0"through "15" and is obtained by quantizing the image data in 16 quantization levels. A tone histogram count part 5 reads the multi-level image data from the image memory 4 and counts the number of picture elements for each of the tone levels. Based on the tone histogram which is obtained in the count part 5, a threshold value calculation part 6 calculates an optimum threshold value by obtaining a characteristic value indicative of the tone of the document image. A binarization part 7 binarizes the multi-level image data into a bi-level image data based on the optimum threshold value. The bi-level image data is stored in a bi-level image memory 8. On the other hand, the bi-level image data is supplied to a character recognition part 9 and the like via a bi-level image output part 2 for use in making a character recognition and the like.
The threshold value calculation part 6 inputs the tone histogram and cumulates the number of picture elements which have tone levels greater than "0" for each tone level starting from the darkest (largest) tone level. The step S4 sets a tone level i to i=15. A step S5 sets a cumulative value slv to slv[i]=slv[i+1]+lv[i], and a step S6 decrements i to i=i-1. A step S7 discriminates whether or not i>0, and the process returns to the step S5 when the discrimination result in the step S7 is YES. The process advances to a step S8 when the discrimination result in the step S7 is NO.
For the sake of convenience, when it is assumed that the optimum normalized cumulative value is 70%, the value at the tone level "5" is closest to 70% in Table 1 and the optimum threshold value is considered as "5". Table 1 shows an examples of the normalized cumulative values for each of the tone levels.
63.30+0.956�1=62.256                                 Tone Level 5.9
63.30+0.956�2=62.212                                 Tone Level 5.8
63.30+0.956�7=69.992                                 Tone Level 5.3
63.30+0.956�8=70.948                                 Tone Level 5.2
63.30+0.956�9=71.904                                 Tone Level 5.1
Next, a description will be given of a second method of determining the optimum threshold value in this second embodiment. The flow chart shown in FIG. 4 shows this second method. Depending on the kind of scanner 3 used, the span differs for each tone level. Hence, in order to more accurately obtain the threshold value, a predetermined tone level at which the normalized cumulative value closest to the optimum normalized cumulative value 5% is obtained, and a tone level which is between this predetermined tone level and the next closest tone level and at which the normalized cumulative value becomes closest to the optimum normalized cumulative value 5% is obtained. A tone level is then calculated from a value which is obtained by dividing the above difference by 10 by making an approximation to the first place of the decimal. From Table 1, the tone level at which the normalized cumulative value is closest to the optimum normalized cumulative value 5% is the tone level "11" which has the normalized cumulative value 5.58%, and the next closest tone level is the tone level "12" which has the normalized cumulative value 1.51%. Hence, the difference between the normalized cumulative values for the two tone levels is divided by 10 to obtain (5.58-1.51)/10=0.407, and this value "0.407" is used to carry out the following calculation so as to obtain the fine tone levels between the tone levels "11" and "12".
1.51+0.407�1=1.197                                   Tone Level 11.9
1.51+0.407�2=2.324                                   Tone Level 11.8
1.51+0.407�8=4.766                                   Tone Level 11.2
1.51+0.407�9=5.173                                   Tone Level 11.1
When the relationship between the normalized cumulative value and the tone level is examined, it is found that the relationship is linear for certain tone levels. When the linear portion of the relationship is extracted and the regression line is obtained by applying the method of least squares, the inclination of the regression line, that is, the rate of change, differs depending on the tone of the document image as shown in FIG. 7. In other words the inclination of the regression line is steep for light document images and the inclination becomes more gradual as the tone of the document image becomes darker. By utilizing this relationship, it is possible to represent the tone characteristic of the document image.
Depending on the kind of scanner 23 used, the span differs for each tone level. Hence, in order to more accurately obtain the threshold value, a predetermined tone level at which the normalized cumulative value closest to the optimum normalized cumulative value 5% is obtained, and a tone level which is between this predetermined tone level and the next closest tone level and at which the normalized cumulative value becomes closest to the optimum normalized cumulative value 5% is obtained. A tone level is then calculated from a value which is obtained by dividing the above difference by 10 by making an approximation to the first place of the decimal. From Table 1, the tone level at which the normalized cumulative value is closest to the optimum normalized cumulative value 5% is the tone level "11" which has the normalized cumulative value 5.58% and the next closest tone level is the tone level "12" which has the normalized cumulative value 1.51% Hence, the difference between the normalized cumulative values for the two tone levels is divided by 10 to obtain (5.58-1.51)/10=0.407, and this value "0.407" is used to carry out the following calculation so as to obtain the fine tone levels between the tone levels "11" and "12".
Every time the tone histogram is obtained for one small region, a step S84 discriminates in the character region discrimination part 41 whether or not the number of picture elements vl[0] having the tone level "0" in the small region is smaller than a read discrimination threshold value CHR which is read out from the tone histogram memory 33. The small region is discriminated as a character region when lv[0]≧CHR. When the discrimination result in the step S84 is NO, a step S85 increments the number of character regions to char-- num=char-- num+1. The picture element having the tone level "0" corresponds to the picture elements making up the white background of the document image. A large number of white picture elements exist within the character region but white picture elements hardly exist within a photograph region, and this is the reason why it is possible to discriminate the character region. The steps S44 through S47 are carried out similarly to the fourth embodiment but only with respect to the small region which is discriminated as the character region. In other words, the cumulative histogram calculation part 27C forms the cumulative histogram slv[i] and stores this cumulative histogram slv[i] in the cumulative histogram memory 34.
Next, a description will be given of a ninth embodiment of the binarization method according to the present invention, by referring to FIGS. 21 and 22. FIG. 21 shows a image processing system to which the ninth embodiment is applied, and FIG. 22 shows a flow chart showing an operation of the block system shown in FIG. 21 for explaining an operation of the ninth embodiment. In FIGS. 21 and 22, those parts which are essentially the same as those corresponding parts in FIGS. 16 and 17 are designated by the same reference numerals, and a description thereof will be omitted.
TABLE 4______________________________________Tone    Tone        Cumulative                         NormalizedLevel   Histogram   Value     Cumulative Value______________________________________15        0            0      0.0014        0            0      0.0013        0            0      0.0012        7            7      0.0011       2580        2587     1.6810       8460        11047    7.219       21838        32885    21.468       14911        47796    31.197       19127        66923    43.676       19939        86862    56.695       18036       104898    68.464       14959       119857    78.223       16812       136669    89.192       16548       153217    100.001       100297      253514    --0       746486      1000000   --______________________________________
As may be seen by comparing FIGS. 27 and 23, the image processing system shown in FIG. 27 is essentially the same a that shown in FIG. 23 except that the part for determining the threshold value is modified similarly to the sixth embodiment.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS3466603 *Jun 22, 1965Sep 9, 1969IbmScanner threshold adjusting circuitUS3665326 *Mar 30, 1970May 23, 1972Us NavyAutomatic threshold detector with selectable percentage of threshold crossingsUS4430748 *Sep 21, 1981Feb 7, 1984Xerox CorporationImage thresholding systemUS4675909 *Feb 8, 1985Jun 23, 1987Nec CorporationBinary character signal producing apparatusUS4747149 *Mar 17, 1987May 24, 1988Nec CorporationOptical character recognition apparatus* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS5268773 *Mar 30, 1990Dec 7, 1993Samsung Electronics Co., Ltd.Document image signal processor having an adaptive thresholdUS5386301 *Aug 18, 1993Jan 31, 1995Ricoh Company, Ltd.Apparatus for producing a bilevel image suitable for a printing characteristic of a printing unitUS5455873 *Dec 3, 1990Oct 3, 1995Information International, Inc.Facsimile dynamic thresholding apparatus and method of use thereofUS5920655 *Feb 7, 1996Jul 6, 1999Canon Kabushiki KaishaBinarization image processing for multi-level image dataUS6064773 *Apr 1, 1997May 16, 2000Ricoh Company, Ltd.Image processing system for processing a multi-tone-level imageUS7873521Jul 8, 2005Jan 18, 2011Nippon Telegraph And Telephone CorporationSound signal detection system, sound signal detection server, image signal search apparatus, image signal search method, image signal search program and medium, signal search apparatus, signal search method and signal search program and mediumUS8289573 *Jan 12, 2009Oct 16, 2012Xerox CorporationMethod for reducing registration defects in color printingUS8330990 *Jan 12, 2009Dec 11, 2012Xerox CorporationMethod and system for modifying a multi-bit rasterized digital image to reduce registration artifactsUS20100177328 *Jan 12, 2009Jul 15, 2010Xerox CorporationMethod for reducing registration defects in color printingUS20100177329 *Jan 12, 2009Jul 15, 2010Xerox CorporationMethod for reducing registration defects in color printingCN1898720BJul 8, 2005Jan 25, 2012日本电信电话株式会社Acoustic signal detection system, acoustic signal detection server, video signal search device, video signal search method, video signal search program and recording medium, signal search device, signal search method and signal search program and recording mediumEP0731599A2 *Feb 9, 1996Sep 11, 1996Canon Kabushiki KaishaImage processing apparatus and method thereforEP1768102A1 *Jul 8, 2005Mar 28, 2007Nippon Telegraph and Telephone CorporationAcoustic signal detection system, acoustic signal detection server, video signal, search device, video signal, search method, video signal, search program and recording medium, signal device, signal search method, signal search program, and recording mediumEP2312475A1 *Jul 8, 2005Apr 20, 2011Nippon Telegraph and Telephone CorporationSound signal detection and image signal detectionWO1998047292A1 *Apr 9, 1998Oct 22, 1998Eidos Technologies LimitedA method of and a system for processing digital information* Cited by examinerClassifications U.S. Classification382/172, 358/466, 382/271International ClassificationG06K9/38, H04N1/403Cooperative ClassificationH04N1/403, G06K9/38European ClassificationH04N1/403, G06K9/38Legal EventsDateCodeEventDescriptionAug 26, 2003FPAYFee paymentYear of fee payment: 12Sep 7, 1999FPAYFee paymentYear of fee payment: 8Sep 5, 1995FPAYFee paymentYear of fee payment: 4Dec 27, 1989ASAssignmentOwner name: RICOH COMPANY, LTD., JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST.;ASSIGNORS:BESSHO, GOROH;TACHIKAWA, MICHIYOSHI;REEL/FRAME:005207/0664Effective date: 19891222RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services