Abstract:
Systems and methods are provided for automatically determining the font of text in a captured document image. Sequences of turns (left, right, straight) around the boundaries of connected components of black pixels in the captured document image are determined. The probabilities of the sequences of turns have come from a particular font within a library of known fonts can be determined using training set statistics. Using these probabilities, the most probable source font is selected.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    1. Field of Invention  
           [0002]    This invention relates to systems and methods for automatically processing captured document images. More particularly, this invention relates to systems and methods for automatically recognizing the font of printed text.  
           [0003]    2. Description of Related Art  
           [0004]    A document image may be captured and converted to digital signals (pixels) by an image capture device, such as a scanner or a facsimile machine. Subsequent processing of these digital signals may include outputting to an image output terminal such as a viewing device or printer, data compression to a more compact format, or optical character recognition. A useful step in each of these exemplary subsequent processing is the automatic determination of the text font used in the document. Examples of the text fonts include, Postscript 10-point Helvetica, 12-point Helvetica-Bold, 11-point Times-Roman, and the like.  
         SUMMARY OF THE INVENTION  
         [0005]    The methods and systems of this invention can automatically determine the text fonts in a captured image.  
           [0006]    The methods and systems of this invention provide automatic determination of the text fonts in a captured image in a simple accurate, and language independent manner with the ability to work with smaller samples of text.  
           [0007]    In various exemplary embodiments of the methods and systems according to this invention, training data is used to determine the characteristic of a sample of the captured image.  
           [0008]    In one exemplary embodiment of the methods and systems according to this invention, the training data is divided into groups, each group consists of connected component boundary boxes of similar sizes.  
           [0009]    In one exemplary embodiment of the methods and systems according to this invention, the training data for each group consists of the probability for each chain code segment and the probability of each successive pair of chain code segments.  
           [0010]    In various exemplary embodiments of the methods and systems according to this invention, the training data includes training sets of various font types.  
           [0011]    In various exemplary embodiments of the methods and systems according to this invention, chain code segments for each component&#39;s boundary in the sample of the captured image data are determined.  
           [0012]    In one exemplary embodiment of the methods and systems according to this invention, for each training set, a group having a range of boundary box sizes that include the size of the boundary box of the sample of the captured image data is determined.  
           [0013]    In various exemplary embodiments of the methods and systems according to this invention, probabilities for each font type in the training sets are determined, and the font type of the captured image data is determined from the determined probabilities of the training data.  
           [0014]    These and other features and advantages of this invention are described in or are apparent from the following detailed description of various exemplary embodiments. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0015]    Various exemplary embodiments of this invention will be described in detail, with reference to the following figures, in which:  
         [0016]    [0016]FIG. 1 shows one exemplary image to be processed according to this invention;  
         [0017]    [0017]FIG. 2 shows one exemplary embodiment of a system that includes an image processing apparatus including the font type determination circuit or routine according to this invention;  
         [0018]    [0018]FIG. 3 shows one exemplary embodiment of the font type determination circuit or routine of FIG. 2;  
         [0019]    [0019]FIG. 4 is a flowchart outlining one exemplary embodiment of a method for processing an image according to this invention; and  
         [0020]    [0020]FIG. 5 is a flowchart outlining one exemplary embodiment of the image improvement data determining step of FIG. 4. 
     
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS  
       [0021]    A chain code is a sequence of north/south/east/west directions taken while traversing the boundary of a connected component. Starting at the lower left-hand corner, and moving in a counter-clockwise direction, a chain code is determined for the outer boundary.  
         [0022]    [0022]FIG. 1 shows one exemplary text image in which a chain code is determined. As shown in FIG. 1, for the letter ‘e’, the chain code determination starts at the pixel marked 0, and the first few directions are EEEENEEN . . . , starting at the center of the bottom edge of the pixel marked 0. After the first north/south/east/west direction, each subsequent direction can be equivalently given by the three-way choice of left/right/straight.  
         [0023]    In various exemplary embodiments of the methods and systems of this invention, training sets are determined, which consist of, for example, upper and lower case letters of the alphabet and the ten digits.  
         [0024]    In various exemplary embodiments of the methods and systems of this invention, each of the training sets is processed by determining the chain codes of each connected component, and grouping these chain codes according to the size of the bounding box of the component the chain codes came from. In one exemplary embodiment the methods and systems of this invention, the components with bounding boxes within similar range of widths and heights are grouped together.  
         [0025]    In various exemplary embodiments of the methods and systems of this invention, for each component in the group, frequencies of length-k chain code segments are determined. As shown in the example in FIG. 1, for k = 5  as the length of the chain code, the sequence of overlapping chain code segments is s 1 =EEEEN, s 2 =EEENE, S 3 =EENEE, etc, where s 1  is the sequence of chain codes segments as they appear in the boundary in a character.  
         [0026]    Because a chain code never doubles back on itself, that is, E is never followed by W, in this exemplary embodiment in FIG. 1, there are N=4·3 k-1  possible chain code segments, S 1 , . . . , S N , where S 1  is the list of all possible chain code segments. That is, the frequency of S k  is the number of times S k  appeared as an s i  in the components of the group, divided by the total number of chain code segments in that group.  
         [0027]    In various exemplary embodiments of the methods and systems of this invention, the data for each group consists of probabilities for each chain code segment P(S i ), and the probability of each successive pair of chain code segments, P(S i , S j ), where {S i , S j } is a segment pair which overlaps in k-1 positions.  
         [0028]    To determine the font type in the captured image, such as the font of a letter text of the captured image, the sequence of chain code segments s 1 , S 2 , . . . s n  is determined for that letter. The chain code sequence wraps around, so that s n  consists of the last direction followed by the first k-1 directions. For each training set, the group whose range of bounding box sizes includes the size of the bounding box of this letter is determined. Using the probabilities for the chain codes in the training sets, the product P(s 1 )·P(s 1| s 2 )·P(s 2 |S 3 )· . . .  
         [0029]    P(s n−1 |s n ) is determined. For each font, the product of probabilities is determined, and the font with the highest probability is selected as the font of the letter.  
         [0030]    That is, along the boundary of a component, by one pixel edge at each step, the state at time n is a segment of k consecutive directions S n =[d n+k+1 , . . . d n−1  d n ]. Segment s n  depends on segment s n−1  because the segments overlap in k−1 positions. However, in general, P(S n |S n−1 , S n−2 )=P(S n |s n−1 ), where s 1  and s i+1 , overlap in k−1 positions, since the only information that S n−2  adds is the direction d n−k−1  which is disjoint from S n ,.  
         [0031]    If a segment only occurs once, then the missing data&#39;s probability is 1/n, where n is the total number of segments in the training set. If the segment never occurs, P(S)=r/n is used, where r=(the number of segments with frequency one)/(the number of segments with frequency zero). With the number of possible segments is 4·3 k−1 , to determine the number of segments with frequency zero, 4·3 k−1 -(the number of distinct segments in the training set) is used.  
         [0032]    For missing pairs, the determination is similar. If N is the number of distinct segments that actually occur, then the number of possible pairs is 3N.  
         [0033]    It is to be appreciated that a plurality of different training sets may be used in the exemplary methods and systems of this invention. For example, the first set may consist of a plurality of pages with each page in a different font and letters in a given size range from the other pages. The second set may be in the same font and size range as the first set but with each page captured a plurality of times, so that there are three times more training data. The other sets may have the same number of pages as in the first set, but each page in one set uses only characters of a first size in the range, another using only characters of a different size in the range, and the last set using characters of another size. It should be appreciated that the training sets used will be obvious and predictable to those skilled in the art.  
         [0034]    In various exemplary embodiments of the methods and systems of this invention, the components in a training set are grouped by the size of a bounding box. Two exemplary grouping parameters include block size and overlap. In one exemplary embodiment, for a block size b for widths, and an overlap of 2, the bounding box widths w is grouped as Group 0, Group 1, Group 2, etc. Group 0 includes widths in the interval [0, b−1], Group 1 the interval [b−2, 2b−3], Group 2 [2b−4, 3b−5], etc.  
                                                                               0   0   1   2   . . .   b-2   b-1                           1                   b-2   b-1   b   . . .   2b-4   2b-3       2                                   2b-4   2b-3   2b-2                  
 
         [0035]    In this exemplary embodiment, the overlap between groups is 2 positions. For any width w, a group can be chosen that contains bounding boxes of at least one pixel wider and at least one pixel narrower than itself. When the overlap is 4 instead of 2, then the training set always contains characters at least two pixels on either side. Heights are done similarly, and then groups are determined corresponding to every combination of width and height ranges. It should be appreciated that several different grouping parameters may be done, and that the systems and methods of this invention are not limited to particular grouping parameters. It should also be appreciated that a training set of mixed size may be used instead of a training set of a fixed size.  
         [0036]    [0036]FIG. 2 shows one exemplary embodiment of a system that includes an image processing apparatus  200  incorporating the font type determining circuit or routine in accordance with this invention. As shown in FIG. 2, an image data source  100  and an input device  120  are connected to the image processing apparatus  200  over links  110  and  122 , respectively. The image data source  100  can be a digital camera, a scanner, or a locally or remotely located computer, or any other known or later developed device that is capable of generating or otherwise providing electronic image data. Similarly, the image data source  100  can be any suitable device that stores and/or transmits electronic image data, such as a client or a server of a network. The image data source  100  can be integrated with the image processing apparatus  200 , or the image data source  100  can be connected to the image processing apparatus  200  over a connection device, such as a modem, a local area network, a wide area network, an intranet, the Internet, any other distributed processing network, or any other known or later developed connection device.  
         [0037]    It should also be appreciated that, while the electronic image data can be generated at the time of printing an image from electronic image data, the electronic image data could have been generated at any time in the past. Moreover, the electronic image data need not have been generated from an original physical document, but could have been created from scratch electronically. The image data source  100  is thus any known or later developed device which is capable of supplying electronic image data over the link  110  to the image processing apparatus  200 . The link  110  can thus be any known or later developed system or device for transmitting the electronic image data from the image data source  100  to the image processing apparatus  200 .  
         [0038]    The input device  120  can be any known or later developed device for providing control information from a user to the image processing apparatus  200 . Thus, the input device  120  can be a control panel of the image processing apparatus  200 , or could be a control program executing on a locally or remotely located general purpose computer, or the like. As with the link  110  described above, the link  122  can be any known or later developed device for transmitting control signals and data input using the input device  120  from the input device  120  to the image processing apparatus  200 .  
         [0039]    As shown in FIG. 2, the image processing apparatus  200  includes a controller  210 , an input/output interface  220 , a memory  230 , a font type determining circuit or routine  240  and an image output terminal  300 , each of which is interconnected by a control and/or data bus  250 . The links  110  and  122  from the image data source  100  and the input device  120 , respectively, are connected to the input/output interface  220 . The electronic image data from the image data source  100 , and any control and/or data signals from the input device  120 , are input through the input interface  220 , and, under control of the controller  210 , are stored in the memory  230  and/or provided to the controller  210 .  
         [0040]    The memory  230  preferably has at least an alterable portion and may include a fixed portion. The alterable portion of the memory  230  can be implemented using static or dynamic RAM, a floppy disk and disk drive, a hard disk and disk drive, flash memory, or any other known or later developed alterable volatile or non-volatile memory device. If the memory includes a fixed portion, the fixed portion can be implemented using a ROM, a PROM, an EPROM, and EEPROM, a CD-ROM and disk drive, a DVD-ROM and disk drive, a writable optical disk and disk drive, or any other known or later developed fixed memory device.  
         [0041]    The image processing apparatus  200  shown in FIG. 2 is connected to the image output terminal  300  over the control and/or data bus  250 . Alternatively, the image output terminal  300  may be an integral part of the image processing apparatus  200 . An example of this alternative configuration would be a digital copier or the like. It should be appreciated that the image processing apparatus  200  can be any known or later developed type of image processing apparatus. There is no restriction on the form the image processing apparatus  200  can take.  
         [0042]    The links  110  and  122  can be any known or later developed device or system for connection, including a direct cable connection, a connection over a wide area network or a local area network, a connection over an intranet, a connection over the Internet, or a connection over any other distributed processing network or system. In general, the links  110  and  122  can be any known or later developed connection system or structure usable for connection.  
         [0043]    The font type determination circuit or routine  240  inputs signals from the image data source  100 . The font type determination circuit or routine  240  determines the font types such as the text font of the input data using training data stored in the memory  230 . The font type determination circuit or routine  240  outputs the determined font type to the image output terminal  300  over the control and/or data bus  250 . That is, based on the determination made by the font type determination circuit or routine  240  and the image data, the font type determination circuit or routine  240  controls the output from the image output terminal  300 . Accordingly, when the output images are output to the image output terminal  300 , the resulting image will be output on a receiving substrate or display with the determined font types.  
         [0044]    While FIG. 2 shows the font type determination circuit or routine  240  and the printing apparatus  300  as portions of an integrated system, the font type determination circuit or routine  240  could be provided as a separate device from the printing apparatus  300 . That is, the font type determination circuit or routine  240  may be a separate device attachable upstream of a stand-alone printing apparatus  300 . For example, the font type determination circuit or routine  240  may be a separate device which interfaces with both the image data source  100  and the printing apparatus  300 .  
         [0045]    Furthermore, the font type determination circuit or routine  240  may be implemented as software on the image processing apparatus  200  or the image data source  100 . Other configurations of the elements shown in FIG. 2. may be used without departing from the spirit and scope of this invention.  
         [0046]    It should be understood that various components of the image processing apparatus  200  shown in FIG. 1, such as the font type determination circuit or routine  240 , and the controller  210 , can each be implemented as software executed on a suitably programmed general purpose computer, a special purpose computer, a microprocessor or the like. In this case, these components can be implemented as one or more routines embedded in a printer driver, as resources residing on a server, or the like. Alternatively, these components can be implemented as physically distinct hardware circuits within an ASIC, or using an FPGA, a PDL, a PLA, or a PAL, or using discrete logic elements or discrete circuit elements. The particular form each of the components shown in FIG. 1 will take is a design choice and will be obvious and predictable to those skilled in the art.  
         [0047]    In one exemplary embodiment of this invention, the font type determination circuit or routine  240  determines the font of the text in the input data. The font type determination circuit or routine  240  determines chain code segments for each components boundary in the input data. For each training set stored in the memory  230 , the font type determination circuit or routine  240  determines a group having a range of boundary box sizes that include the size of the boundary box of the input data. The font type determination circuit or routine  240  then determines the probabilities for each font in the training sets, where the font of the input data is determined to be the font with the highest probability.  
         [0048]    [0048]FIG. 3 shows one exemplary embodiment of the font type determination circuit or routine of this invention. As shown in FIG. 3, in the font type determination circuit or routine  240 , the image sequence determination portion  242  determines the sequence of chain code segments S 1 , S 2 , . . . , s n  for a sample in the input data. As discussed above, the chain code sequence wraps around, so that s n  consists of the last direction followed by the first k−1 directions. The determined sequence is input to the group determination portion  244 .  
         [0049]    For each training set stored in the memory  230 , the group determination portion  244  determines the group having a range of bounding box sizes that includes the size of the bounding box of the sample in the input data. Using the probabilities for the chain codes in the training sets, the probability determination portion  246  determines the product P(s 1 )·P(s 1 |S 2 )·P(S 2| S 3 )· . . . ·P(S n−1 |s n ) of the probabilities. For each font type, the probability determination portion  246  determines the product of probabilities, where the font type with the highest probability is selected as the font type of the sample.  
         [0050]    [0050]FIG. 4 is a flowchart outlining one exemplary embodiment of an image processing method according to this invention. Beginning at step S 1000 , control continues to step S 1100 , where the document is input. Then, in step S 1200 , an image of the document is captured. Next, in step S 1300 , training data is input. Control then continues to step S 1400 .  
         [0051]    In step S 1400 , the font class is determined based on the captured image data and the training data. Then, in step S 1500 , image data with the determined font classification is output as the output data. Next, in step S 1600 , the process stops.  
         [0052]    [0052]FIG. 5 is a flowchart outlining one exemplary embodiment of the font type data determination step S 1400 . Beginning in step S 1400 , control continues to step S 1410 , where image data is input. Then, in step S 1420 , the sequence of chain code segments s 1 , S 2 , . . . , s n  for a sample in the input data is determined. Control then continues to step S 1430 .  
         [0053]    In step S 1430 , for each training set of the training data, the group having a range of bounding box sizes that includes the size of the bounding box of the sample in the input data is determined. Next, in step S 1440 , for each font type, using the probabilities for the chain codes in the input training sets, the product of the probabilities P(s 1 )·P(S 1 |S 2 )·P(S 2 |S 3 )· . . . ·P(s n−1 |S n ) is determined. Then, in step S 1450 , the font type with the highest probability is selected as the font type of the sample. Control then continues to step S 1460 , where control returns to step S 1500 .  
         [0054]    As shown in FIG. 1, the image processing apparatus  200  is preferably implemented on a programmed general purpose computer. However, the image processing apparatus  200  can also be implemented on a special purpose computer, a programmed microprocessor or microcontroller and peripheral integrated circuit elements, an ASIC or other integrated circuit, a digital signal processor, a hardwired electronic or logic circuit such as a discrete element circuit, a programmable logic device such as a PLD, PLA, FPGA or PAL, or the like. In general, any device, capable of implementing a finite state machine that is in turn capable of implementing the flowcharts shown in FIGS. 6 and 7, can be used to implement the image processing apparatus  200 .  
         [0055]    The foregoing description of the exemplary systems and methods for detection of this invention is illustrative, and variations in implementation will be apparent and predictable to persons skilled in the art. For example, while the systems and methods of this invention have been described with reference to desktop-captured images, any other type of image sensing device requiring accurate reconstruction of the underlying image can be used in conjunction with the systems and methods of this invention.  
         [0056]    Thus, while the systems and methods of this invention has been described in conjunction with the specific embodiments outlined above, it is evident that many alternatives, modifications and variations will be apparent to those skilled in the art. Accordingly, the exemplary embodiments of the systems and methods of this invention, as set forth above, are intended to be illustrative, not limiting. Various changes may be made without departing from the spirit and scope of the invention.