Source: http://www.google.com/patents/US6269186?dq=7,117,286
Timestamp: 2016-07-31 09:56:15
Document Index: 695986598

Matched Legal Cases: ['ART=0', 'ART=0', 'ART=0', 'ART=0', 'ART=0', 'ART=0', 'ART=0', 'ART=43', 'ART=43', 'ART=43', 'ART=43', 'ART=43', 'ART=43']

Patent US6269186 - Image processing apparatus and method - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsThis invention relates to an image processing method of quantizing a multivalued image to perform image processing. The luminance frequency of the multivalued image is calculated, a quantization threshold for quantization is specified on the basis of the calculated luminance frequency, a representative...http://www.google.com/patents/US6269186?utm_source=gb-gplus-sharePatent US6269186 - Image processing apparatus and methodAdvanced Patent SearchPublication numberUS6269186 B1Publication typeGrantApplication numberUS 08/993,143Publication dateJul 31, 2001Filing dateDec 18, 1997Priority dateDec 20, 1996Fee statusPaidPublication number08993143, 993143, US 6269186 B1, US 6269186B1, US-B1-6269186, US6269186 B1, US6269186B1InventorsTakeshi MakitaOriginal AssigneeCanon Kabushiki KaishaExport CitationBiBTeX, EndNote, RefManPatent Citations (10), Non-Patent Citations (1), Referenced by (21), Classifications (13), Legal Events (4) External Links: USPTO, USPTO Assignment, EspacenetImage processing apparatus and method
US 6269186 B1Abstract
This invention relates to an image processing method of quantizing a multivalued image to perform image processing. The luminance frequency of the multivalued image is calculated, a quantization threshold for quantization is specified on the basis of the calculated luminance frequency, a representative value used for quantization of the multivalued image is calculated on the basis of the specified quantization threshold and the luminance frequency, and the multivalued image is quantized using the calculated representative value. The quantization threshold is an average luminance value obtained when the histogram distribution converges to make the skew of the histogram distribution of the luminance frequency fall within a predetermined range. The representative value is an average luminance value in each distribution region of the histogram distribution of the luminance frequency that is divided by the quantization threshold.
In addition to a simple binarization method using a fixed threshold set in advance, conventional binarization methods include the Otsu's method (Otsu, “Automatic Threshold Selection Method Based on Discrimination and Least Square Rule”, the transactions of the Institute of Electronics and Communication Engineers of Japan, Vol. J63-D, No. 4, pp. 349-356, 1980) in which, when the histogram is divided into two classes at a certain threshold, a threshold obtained when the variance between the classes is maximized is used as a binarization threshold, and a binarization method of setting the threshold for an image having a gradation in accordance with the local density.
The present invention has been made to solve the above problems, and has as its object to provide an image processing apparatus and method for setting a proper quantization threshold between the object density and background density within an input image to perform image processing.
In step S201, image data is input by the input unit 101 via the image input device 2 such as a scanner, and stored in the memory unit 102. The image data is input as 8-bit multivalued image data. In step S202, the quantization threshold calculation unit 104 determines a quantization threshold optimal for image region separation (to be described below) for the multivalued image input in step S201, and the quantization unit 105 generates a quantized image using the quantization threshold. In step S203, the region separation unit 106 performs image region separation for the quantized image generated in step S202, and outputs region data added with the attribute of the image to the image processing unit 108. In step S204, the image processing unit 108 binarizes a region designated as “text” in the region data separated in step S203, and extracts the binarized region from the binary image. The character recognition unit 107 performs OCR processing for the binary image, and outputs a recognized character code.
FIG. 3 is a flow chart showing the procedure of quantization processing in this embodiment. Referring to FIG. 3, in step S301, an 8-bit multivalued image is input from the memory unit 102 in the image processing apparatus 1 to a memory (not shown) or the like. In step S302, the multivalued image is extracted in units of processing blocks (64�64 pixels). Note that the multivalued image is read by the image input device 2 such as a scanner, and stored in the memory unit 102 in advance. In step S303, the luminance frequency accumulation unit 103 calculates the histogram of each processing block. In this case, the frequencies of eight bits, i.e., digital values “0” to “255” are calculated using all the pixels of the processing block. As a result, a histogram like the one shown in FIG. 6 is obtained.
In step S304, parameters START and END are respectively set to “0” and “255”. The parameters START and END respectively correspond to the start and end points of the statistic of a luminance value to be calculated in the subsequent steps S305 and S306.
In step S305, an average value AV of pixels corresponding to digital values START to END is calculated. For example, if START=0 and END=255, the average value AV of pixels having values “0” to “255” (all pixels in this case) is calculated. If START=0 and END=177, the average value AV of pixels having values “0” to “177” is calculated.
Sk=(Σ(Xi−AV){circumflex over ( )}3)/D (1)
where “{circumflex over ( )}” means the power, and Xi is the luminance value of the pixel. D is the variance value of the whole image, and calculated by equation (2):
D=Σ(Xi−AV){circumflex over ( )}2 (2)
In equation (1), the skew value is calculated by cubing the difference between the luminance value of each pixel and the average value. The power is not limited to the third power as far as it is the odd-numbered power.
Sk<−1.0 (3)
If inequality (3) is “true” for the calculated skew value in step S307, the flow advances to step S312; if inequality (3) is “false”, the flow shifts to step S308. In step S312, the average value AV is set in END without changing START. The flow returns to step S305 to calculate the average value AV of the values START to END again.
Sk>1.0 (4)
If inequality (4) is “true” for the calculated skew value in step S308, the processing shifts to step S313; if inequality (4) is “false”, the processing advances to step S309. In step S313, the average value AV is set in START without changing END. The flow returns to step S305 to calculate the average value AV of the values START to END again.
In step S309, the average value AV obtained when both the conditions in steps S307 and S308 are “false” is set as a quantization threshold TH. In step S310, quantization processing using the quantization threshold TH is performed.
FIG. 6 shows the histogram of a given image (8-bit input). In FIG. 6, the abscissa indicates the digital value of the luminance having “0” (black) at the left end and “255” (white) at the right end, and the ordinate indicates the frequency of each digital value.
In the first processing through steps S305 and S306, the average value AV and the skew value Sk are calculated for START=0 and END=225 to obtain “177” and “−78.9”, respectively. In this case, since the skew value Sk is smaller than “−1.0”, START=0 and END=177 are set in step S312 of FIG. 3. In the second processing, the average value AV and the skew value Sk are calculated for START=0 and END=177 to obtain “91” and “−8.6”, respectively. Also in this case, since the skew value Sk is smaller than “−1.0”, START=0 and END=91 are set in step S312 of FIG. 3.
In the third processing, the average value AV and the skew value Sk are calculated for START=0 and END=91 to obtain “43” and “9.6”, respectively. In this case, since the skew value Sk exceeds “1.0”, START=43 and END=91 are set in step S313 of FIG. 3.
In the fourth processing, the average value AV and the skew value Sk are calculated for START=43 and END=91 to obtain “72” and “−7.0”, respectively. As for these values, since the skew value Sk is smaller than “−1.0”, START=43 and END=72 are set in step S312 of FIG. 3.
In the fifth processing, the average value AV and the skew value Sk are calculated for START=43 and END=72 to obtain “58” and “−2.2”, respectively. Since the skew value Sk is also smaller than “−1.0”, START=43 and END=58 are set in step S312 of FIG. 3. In the sixth processing, the average value AV and the skew value Sk are calculated for START=43 and END=58 to obtain “50” and “−0.4”, respectively.
In the sixth processing, the skew value Sk becomes “−1.0” or larger and “1.0” or smaller, and does not satisfy the conditions in steps S307 and S308 of FIG. 3 (NO in steps S307 and S308). The processing advances to step S309 to set “50” as the quantization threshold TH. In step S310, quantization processing using the quantization threshold TH is performed, and the quantized image is stored in the memory unit 102 of the image processing apparatus 1.
This quantization is performed using the average value of a region frequency smaller than the quantization threshold TH as representative value “1”, and the average value of a region frequency larger than the quantization threshold TH as representative value “2”. An image is quantized by the two values. Note that the representative values are not limited to them so long as they represent the features of a region frequency smaller than the quantization threshold TH and a region frequency larger than the quantization threshold TH. For example, the median value may be employed instead of the average value.
In step S804, the regions are classified depending on the width and height of each region and the number of black pixels in the region, and labeled with attributes. The attributes of the region include, e.g., “table”, “outer frame region”, and “text”. In step S805, the widths and heights of all regions labeled “text” are averaged. If the obtained average width is larger than the average height, the processing image is regarded to be a horizontal writing; otherwise, the processing image is regarded as a vertical writing, thereby determining a character construction. At the same time, the character size of one character is determined by the average height for the horizontal writing or the average width for the vertical writing.
From the histogram of all the regions “text” in the vertical direction (for the horizontal writing) or the horizontal direction (for the vertical writing) on the image region separation image, the columns and line spacing of the writing are detected. In step S806, of the regions “text”, one having a large character size is determined as a “title”. In the conventional region determination for a binarized image, even if a band indicating title emphasis exists on the background of the region determined as a title, the existence of the band cannot be recognized because the background information is lost. For the same reason, even if title characters themselves are colored, they are determined as only “black characters”. The band is inserted in the background of the title or the title characters are colored because the document producer wants to discriminate the title from another title. In the conventional method, however, all the titles are determined as equal “titles”.
In quantization of this embodiment, the average value of a region at the left block having a block unit of 64�64 pixels that is smaller than the calculated quantization threshold TH, in this case, the average pixel value BBV of the character region “T” of the character “TITLE” is calculated to be 64. In this block, the average value of a region larger than the quantization threshold TH, in this case, the average value WBV of the region corresponding to the background color is calculated to be 200. BBV and WBV are added in block units of 64�64 pixels in addition to a normal binarized image. Therefore, the title character color and the background color can be discriminated.
In this embodiment, processing shown in FIG. 10 is performed for a region determined as a title. In step S1001, region determination is performed using only image information quantized in the above manner. Processing in step S1002 is executed for the region determined as “title”. In FIG. 10, reference symbols WBV, BBV, PW, and PB are as follows.
WBV and PW are compared with each other. When WBV is smaller than PW, the background color of this block is estimated to have a background color darker than the background on the paper sheet. Then, BBV and PB are compared with each other. When BBV is larger than PB, the density of a character printed in this block is estimated to be that of a colored character lower than that of a normal black character. Therefore, when WBV is smaller than PW, or BBV is larger than PB, the title in this region is determined to have a background color or character color emphasizing the title, and the flow branches to step S1003. Otherwise, the flow shifts to step S1004. In step S1003, the region is labeled “emphasized title”. In step S1004, a region is labeled “normal title”.
In step S807, regions “title” and “text” present independently of each other are joined to one region in accordance with the interval between the regions “title” and “text” and surrounding regions.
“Number”: the detection order of regions
“Attribute”: attribute information of a region; the following nine types of attributes are prepared;
“Route” indicates an input image itself.
“Text” indicates a character.
“Emphasized title” indicates an emphasized title region.
“Normal title” indicates a normal title region.
“Table” indicates a table region.
“Noise region” indicates that a region cannot be determined as either character or image.
“Outer frame region” indicates a ruled line or the like.
“Photographic image” indicates a photography region.
“Line image” indicates a line image region.
“Start point coordinates”:
“End point coordinates”:
“Number of pixels”:
“Character construction information”:
three types of character construction information “vertical writing”, “horizontal writing”, and “unknown”
As for the region data shown in FIG. 11, only a region having “attribute” of “text” hierarchically holds region data about lines (line region data) before joining in step S807 of FIG. 8.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4832447 *Dec 4, 1987May 23, 1989Board Of Trustees Operating Michigan State UniversityJoint transform image correlation using a nonlinear spatial light modulator at the fourier planeUS5150433 *Dec 1, 1989Sep 22, 1992Eastman Kodak CompanyHistogram/variance mechanism for detecting presence of an edge within block of image dataUS5337373 *Jul 30, 1993Aug 9, 1994International Business Machines CorporationAutomatic threshold generation techniqueUS5386508 *Aug 16, 1991Jan 31, 1995Fuji Xerox Co., Ltd.Apparatus for generating programs from inputted flowchart imagesUS5649024 *Nov 17, 1994Jul 15, 1997Xerox CorporationMethod for color highlighting of black and white fontsUS5701367 *Oct 20, 1994Dec 23, 1997Fuji Xerox Co., Ltd.Image data coding system for controlling amounts of code data for character image and natural image regionsUS5841551 *Jan 25, 1996Nov 24, 1998Minolta Co., Ltd.Data processorUS5867593 *Oct 8, 1996Feb 2, 1999Olympus Optical Co., Ltd.Image region dividing apparatusUS5872864 *Nov 27, 1995Feb 16, 1999Olympus Optical Co., Ltd.Image processing apparatus for performing adaptive data processing in accordance with kind of imageUS5920655 *Feb 7, 1996Jul 6, 1999Canon Kabushiki KaishaBinarization image processing for multi-level image data* Cited by examinerNon-Patent CitationsReference1"An Automatic Threshold Selection Method Based On Discriminant and Least Squares Criteria", by Nobuyuki Otsu, Journal of Papers of The Institute of Electronics, Information and Communication Engineers vol. J63-D, No. 4, pp. 349-356, 1980. (English abstract).Referenced byCiting PatentFiling datePublication dateApplicantTitleUS6690011 *Jan 14, 2003Feb 10, 2004Honda Giken Kogyo Kabushiki KaishaInfrared image-processing apparatusUS6753880 *Sep 24, 2001Jun 22, 2004Hitachi, Ltd.Display device and display driving device for displaying display dataUS6917704 *May 23, 2001Jul 12, 2005Matsushita Electric Industrial Co., Ltd.Image processing method, image processing apparatus and image processing systemUS7099507 *Nov 5, 1999Aug 29, 2006Ricoh Company, LtdMethod and system for extracting title from document imageUS7151549Apr 14, 2004Dec 19, 2006Hitachi, Ltd.Display device and display driving device for displaying display dataUS7186978Oct 15, 2004Mar 6, 2007Millennium Enginerring And Integration CompanyCompact emissivity and temperature measuring infrared detectorUS7254276 *Jan 23, 2003Aug 7, 2007Fujifilm CorporationNoise reduction in image capturing apparatusUS7418133 *Apr 28, 2005Aug 26, 2008Quisda CorporationImage correction systems and methods thereofUS7471414 *Mar 18, 2003Dec 30, 2008Ricoh Company, Ltd.Image processing method and apparatus, and computer readable data storing medium storing a program for image processingUS7526139 *Sep 7, 2006Apr 28, 2009Seiko Epson CorporationImage processing for improving character readability of characters disposed on an imageUS7852358Dec 14, 2010Hitachi, Ltd.Display device with control of steady-state current of a generation circuitUS20010021033 *Mar 6, 2001Sep 13, 2001Alps Electric Co., Ltd.Image forming apparatus which discriminates tone and gives appropriate outputUS20020021834 *May 23, 2001Feb 21, 2002Akio KojimaImage processing method, image processing apparatus and image processing systemUS20020145581 *Sep 24, 2001Oct 10, 2002Yasuyuki KudoDisplay device and display driving device for displaying display dataUS20030142876 *Jan 23, 2003Jul 31, 2003Masahiko SugimotoImage capturing apparatusUS20040196236 *Apr 14, 2004Oct 7, 2004Yasuyuki KudoDisplay device and display driving device for displaying display dataUS20050244054 *Apr 28, 2005Nov 3, 2005Wen-Hsuan HsiehImage correction systems and methods thereofUS20060081777 *Oct 15, 2004Apr 20, 2006Millennium Engineering And Integration CompanyCompact emissivity and temperature measuring infrared detectorUS20070065012 *Sep 7, 2006Mar 22, 2007Seiko Epson CorporationImage processing apparatus, image processing method, and program productUS20070085793 *Dec 12, 2006Apr 19, 2007Yasuyuki KudoDisplay device and display driving device for displaying display dataUS20090041352 *Aug 7, 2008Feb 12, 2009Naoki OkamotoImage formation device, image formation method, and computer-readable recording medium recording image formation program* Cited by examinerClassifications U.S. Classification382/172, 358/462, 382/270, 358/466, 382/176International ClassificationH04N1/41, G06K9/20, G06K9/38Cooperative ClassificationG06K2209/01, G06K9/00456, G06K9/38European ClassificationG06K9/00L2, G06K9/38Legal EventsDateCodeEventDescriptionDec 18, 1997ASAssignmentOwner name: CANON KABUSHIKI KAISHA, JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:MAKITA, TAKESHI;REEL/FRAME:009007/0669Effective date: 19971209Jan 4, 2005FPAYFee paymentYear of fee payment: 4Dec 31, 2008FPAYFee paymentYear of fee payment: 8Jan 3, 2013FPAYFee paymentYear of fee payment: 12RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services