Abstract:
A method for increasing the accuracy of image data classification in a page analysis system for analyzing image data of a document page. The method includes inputting image data of a document page as pixel data, analyzing the pixel data in order to locate all connected pixels, rectangularizing connected pixel data into blocks, analyzing each of the blocks of pixel data in order to determine the type of image data contained in the block, outputting an attribute corresponding to the type of image data determined in the analyzing step, and performing optical character recognition to attempt to recognize a character of the block of image data in the case that the analyzing step cannot determine the type of image data contained in the block.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    1. Field of the Invention  
           [0002]    The present invention relates to a page analysis system for analyzing image data of a document page by utilizing a block selection technique, and particularly to such a system in which blocks of image data are classified based on characteristics of the image data. For example, blocks of image data may be classified as text data, titles, half-tone image data, line drawings, tables, vertical lines or horizontal lines.  
           [0003]    2. Incorporation by Reference  
           [0004]    U.S. patent application Ser. No. 07/873,012, “Method And Apparatus For Character Recognition”, Ser. No. 08/171,720, “Method And Apparatus For Selecting Text And Or Non-Text Blocks In A Stored Document”, Ser. No. 08/596,716, “Feature Extraction System For Skewed And Multi-Orientation Documents”, and Ser. No. 08/338,781, “Page Analysis System”, which are commonly owned by the assignee of the present invention, are incorporated herein by reference.  
           [0005]    3. Description of the Related Art  
           [0006]    Recently developed block selection techniques, such as the techniques described in the aforementioned U.S. patent application Ser. Nos. 07/873,012 and 08/717,720, are used in page analysis systems to provide automatic analysis of image data within a document page. In particular, these techniques are used to distinguish between different types of image data within the page. The results of such techniques are then used to choose a type of processing to be subsequently performed on the image data, such as optical character recognition (OCR), data compression, data routing, etc. For example, image data which a block selection technique has designated as text data is subjected to OCR processing, whereas image data which is designated as picture data is subjected to data compression. Due to the foregoing, various types of image data can be input and automatically processed without requiring user intervention.  
           [0007]    Block selection techniques are most beneficial when applied to composite documents. FIG. 1 shows an image of composite document page  1  as it appears after being subjected to a block selection technique. Document page  1  includes a logo within block  2 , a large font title within blocks  3  to  6 , large font decorative text within block  7 , text-sized decorative font within blocks  8  to  13 , various text-sized symbols within blocks  14  to  27  and a small symbol pattern within blocks  28  to  35 .  
           [0008]    Block selection techniques use a “blocked” document image such as that shown in FIG. 1 to create a hierarchical tree structure representing the document. FIG. 2 shows a hierarchical tree which represents document page  1 . The tree consists of root node  101 , which represents document page  1 , and various descendent nodes. Descendent nodes  102 ,  102 ,  104  to  106 ,  107 ,  108  to  113 ,  114  to  127  and  128  to  145  represent blocked areas  2 ,  3  to  6 ,  7 ,  8  to  13 ,  14  to  27  and  28  to  35 , respectively.  
           [0009]    In order to construct such a tree, block selection techniques such as those described in U.S. patent application Ser. Nos. 07/873,012 and 08/171,720 search each area of document page  1  to find “connected components”. As described therein, connected components comprise two or more pixels connected together in any of eight directions surrounding each subject pixel. The dimensions of the connected components are rectangularized to create corresponding “blocked” areas. Next, text connected components are separated from non-text connected components. The separated non-text components are thereafter classified as, e.g., tables, half-tone images, line drawings, etc. In addition, block selection techniques may combine blocks of image data which appear to be related in order to more efficiently process the related data.  
           [0010]    The separation and classification steps are performed by analyzing characteristics of the connected components such as component size, component dimension, average size of each connected component, average size of internal connected components and classification of adjacent connected components. However, despite using complex algorithms in conjunction with the foregoing factors in order to classify blocks of image data, block selection techniques often mis-identify or are unable to identify blocks of data within a document page.  
           [0011]    For example, as shown in FIG. 2, a conventional block selection technique may not be able to distinguish the content of blocks  2 ,  3  and  7  of page  1 . Accordingly, corresponding nodes  102 ,  103  and  107  are designated “unknown”.  
           [0012]    These problems occur because the classification algorithms applied by conventional block selection techniques are premised on many assumptions relating to data size, e.g., any data which falls within a given size threshold is classified as text data. Accordingly, any text data outside of that threshold will most likely not be characterized as text data. Also, text and non-text connected components are separated based on an assumption that text connected components are usually smaller than picture connected components. In addition, the algorithms also assume that text connected components comprise the majority of the connected components in a document page.  
           [0013]    Accordingly, conventional block selection techniques are inherently inaccurate because they rely on assumptions regarding size-related characteristics of document image data and do not attempt to actually recognize the content of the image data.  
           [0014]    Mis-identification of document image data due to these inherent inaccuracies results in significant problems when combining related blocks of image data. For example, the combining algorithm used in the present example requires that blocks which a block selection technique has designated as “unknown” be combined with any adjacent text blocks. Accordingly, because “unknown” blocks  2  and  3  of document page  1  are adjacent to “text” blocks  4  to  6 , these blocks are grouped together to form “text” block  36 , shown in FIG. 3. Therefore, the logo within original block  2  will be mistakenly processed as text. As also shown in FIG. 3, blocks  7  to  13 ,  14  to  27  and  28  to  35  are combined into single “text” blocks  38 ,  39  and  40 , respectively.  
           [0015]    Techniques have been developed to address the tendency of existing block selection techniques to mis-identify and/or erroneously combine image data. For example, U.S. patent application Ser. No. 08/361,240 describes a method for reviewing the data classifications resulting from a block selection technique and for editing the classifications in the case that any image data was misidentified by the block selection technique. However, such techniques require operator intervention and are therefore not adequate in cases where automation of the block selection technique is required.  
         SUMMARY OF THE INVENTION  
         [0016]    The present invention relates to a method for classifying blocks of image data within a document page which utilizes optical character recognition processing to address shortcomings in existing block selection techniques.  
           [0017]    Thus, according to one aspect of the invention, the present invention is a method for increasing the accuracy of image data classification in a page analysis system for analyzing image data of a document page. The method includes inputting image data of a document page as pixel data, analyzing the pixel data in order to locate all connected pixels, rectangularizing connected pixel data into blocks, analyzing each of the blocks of pixel data in order to determine the type of image data contained in the block, outputting an attribute corresponding to the type of image data determined in the analyzing step, and performing optical character recognition so as to recognize the type of image data in the block of image data in the case that the analyzing step cannot determine the type of image data contained in the block.  
           [0018]    In another aspect, the present invention is a method for accurately classifying image data in a page analysis system for analyzing image data of a document page. The method includes inputting image data of a document page as pixel data, combining and rectangularizing connected pixel data into blocks of image data, and analyzing and classifying the data as a type of data. In the case that the type of data is indicated as text data and a size of the text data is outside a predetermined size threshold, the method further comprises performing optical character recognition on the text data.  
           [0019]    This brief summary has been provided so that the nature of the invention may be understood quickly. A more complete understanding of the invention can be obtained by reference to the following detailed description of the preferred embodiments in connection with the attached drawings.  
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0020]    [0020]FIG. 1 is a representational view of a document page in which image data has been blocked by a block selection technique;  
         [0021]    [0021]FIG. 2 is a representational view of a hierarchical tree structure corresponding to the document of FIG. 1;  
         [0022]    [0022]FIG. 3 is a representational view of the document of FIG. 1 wherein the blocked image data has been combined according to a block selection technique;  
         [0023]    [0023]FIG. 4 is a perspective view showing the outward appearance of an apparatus according to the present invention;  
         [0024]    [0024]FIG. 5 is a block diagram of the FIG. 3 apparatus;  
         [0025]    [0025]FIG. 6 is a flow diagram describing a method for classifying document image data;  
         [0026]    [0026]FIG. 7 is a detailed flow diagram describing a method for classifying image data of a document page using optical character recognition;  
         [0027]    [0027]FIG. 8 is a representational view of a hierarchical tree produced by applying a portion of the method of FIGS. 6 and 7 to the FIG. 1 document;  
         [0028]    [0028]FIG. 9 is a representational view of a hierarchical tree produced by applying the method of FIGS. 6 and 7 to the FIG. 1 document;  
         [0029]    [0029]FIG. 10 is a representational view of the FIG. 1 document after being subjected to the method of FIGS. 5 and 6;  
         [0030]    [0030]FIG. 11 is a flow diagram for describing a method for classifying image data of a document page using optical character recognition processing; and  
         [0031]    [0031]FIG. 12 is a representational view of a hierarchical tree resulting from applying the method of FIG. 11 to the FIG. 10 document page.  
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0032]    [0032]FIG. 4 is a view showing the outward appearance of a representative embodiment of the present invention. Shown in FIG. 4 is computer system  41 , which may be a Macintosh or IBM PC or PC-compatible system having a windowing environment, such as Microsoft Windows™. Provided with computer system  41  is display screen  42  such as a color monitor, keyboard  44  for entering user commands, and pointing device  45  such as a mouse for pointing to and for manipulating objects displayed on display screen  42 .  
         [0033]    Computer system  41  also includes a mass storage device such as computer disk  46  for storing data files which include document image files in either compressed or uncompressed format, and for storing computer executable process steps embodying the present invention. Scanner  47  may be used to scan documents so as to provide bit map images of those documents to computer system  41 . Documents may also be input into computer system  41  from a variety of other sources, such as from network interface  49  or from other sources such as the World Wide Web through facsimile/modem interface  50  or through network interface  49 . Printer  51  is provided for outputting processed document images.  
         [0034]    It should be understood that although a programmable general purpose computer system is shown in FIG. 4, a dedicated, or stand-alone, computer or other type of data processing equipment can be used to execute the process steps of the present invention.  
         [0035]    [0035]FIG. 5 is a detailed block diagram showing the internal construction of computer system  41 . As shown in FIG. 5, computer system  41  includes central processing unit (“CPU”)  52  which interfaces with computer bus  54 . Also interfaced with computer bus  54  is scanner interface  55 , printer interface  56 , network interface  57 , facsimile/modem interface  59 , display interface  50 , main random access memory (“RAM”)  51 , disk  46 , keyboard interface  62  and mouse interface  64 .  
         [0036]    Main memory  61  interfaces with computer bus  54  so as to provide RAM storage to CPU  52  for executing stored process steps such as the process steps of a block selection technique according to the present invention. More specifically, CPU  52  loads process steps from disk  46  into main memory  61  and executes the stored process steps from memory  61  in order identify and classify image data within a document page such as document page  1 . As shown in FIG. 5, disk  46  also contains document images in either compressed or uncompressed format, hierarchical tree structure data produced by block selection systems, and application program files which include a block selection program and a block selection editor application for editing the results of a block selection program.  
         [0037]    [0037]FIG. 6 is a flow diagram describing the block selection technique of the present invention.  
         [0038]    In step S 601 , image data representing document page  1  is input into computer system  41  as pixel data. The document image data may be input either by scanner  47  or by another input means connected to network  49 . The image data is subsequently stored in RAM  61 . Once input, in step S 602 , the image data is analyzed so as to detect connected components within document page  1 . A connected component is a group of black pixels which is-completely surrounded by white pixels. Each connected component is rectangularized in step S 604 . Rectangularization results in creating the smallest rectangle that completely circumscribes a connected component. For a further description of rectangularization, the reader&#39;s attention is drawn to U.S. patent application Ser. No. 08/338,781, which is incorporated herein by reference.  
         [0039]    In step S 605 , a hierarchical tree structure is created by the block selection program. In this regard, the block selection program assigns a node in a hierarchical tree structure corresponding to each rectangular block circumscribing a connected component, as illustrated by the hierarchical tree structure of FIG. 2, which represents blocked document page  1 .  
         [0040]    Next, in step S 606 , each block is analyzed to determine if the connected component within the block meets certain criteria indicative of text data. If the block is smaller than a predetermined threshold size, it is initially determined to be non-text and flow proceeds to step S 609 . Alternatively, the text/non-text threshold may be based on the average height and width of other rectangles within the page. This text/non-text analysis is described in greater detail in U.S. patent application Ser. No. 07/873,012, which is incorporated herein by reference.  
         [0041]    If, in step S 606 , the block is determined to contain text data, flow proceeds to step S 607 , in which a node corresponding to the block is updated and an attribute of “text” is appended within the node.  
         [0042]    In step S 609 , the block is analyzed to determine if it contains non-text data. In this regard, in step S 609 , the block of image data undergoes several types of analysis in order to determine if the non-text data within the block represents a line (horizontal, vertical, dotted or slanted), a joint-line, a picture, line art, a frame, or a table. This classification of non-text data is performed based on complex analysis of various size thresholds and block location information, which are formulated mathematically and calculated dynamically. A more detailed description of non-text classification may be obtained by reference to U.S. patent application Ser. No. 07/873,012, which is incorporated herein by reference.  
         [0043]    Non-text analysis continues until the block has been identified as one of a non-text image type or until the block has been tested with respect to each non-text image type without being successfully identified. If the block data is determined to represent one of the non-text image types, then, in step S 610 , a corresponding node of the hierarchical tree is updated so as to contain an attribute of the identified non-text image type.  
         [0044]    On the other hand, if the block of image data cannot be identified as either text or as one of the non-text image types, then, in step S 611 , the block is preliminarily indicated as containing “unknown” data. In step S 612 , the “unknown” block is processed using an optical character recognition (OCR) technique. Thereafter, in step S 614 , the node of the hierarchical tree structure corresponding to the “unknown” block is updated in accordance with the result of step S 612 .  
         [0045]    [0045]FIG. 7 is a flow diagram which provides a more detailed description of the processing performed in steps S 612  and S 614 . In step S 701 , a connected component which was preliminarily indicated as “unknown” in step S 611  is examined using OCR processing. Next, in step S 702 , if the OCR processing cannot recognize the connected component, flow proceeds to step S 704 , in which a node corresponding to the component is updated so as to include a “picture” attribute. Flow then proceeds to step S 705 .  
         [0046]    If, in step S 702 , the OCR processing recognizes the connected component, the corresponding node is updated to include an “unknown” attribute. It may appear that, because the connected component was recognized in step S 702 , the corresponding node should be updated to include a “text” attribute. However, in the case that an “unknown” block includes text, designating this block as “unknown” does not preclude this block from being combined with a “text” block so as to produce more efficient blocking, as described above. In addition, such a redesignation may cause the “unknown” block, which may contain picture data, to be incorrectly combined with a “text” block during grouping of the blocks, as also described above. Therefore, designating the node corresponding to the recognized connected component as “unknown” results in more efficient processing.  
         [0047]    In step S 706 , the hierarchical tree is examined to determine if all blocks which had previously been preliminarily indicated as containing “unknown” connected components have been examined. If not, flow returns to step S 701  and proceeds as described above. If so, flow proceeds to step S 707 .  
         [0048]    [0048]FIG. 8 is a representative view of a hierarchical tree structure which results from the method of FIG. 7, prior to step S 707 . As shown, “unknown” node  102  has been updated to “picture” node  202 . In contrast, because blocks  3  and  7  contain OCR-recognizable connected components, blocks  3  and  7  are represented by “unknown” nodes  203  and  207 .  
         [0049]    Returning to FIG. 7, in step S 707 , it is determined whether the blocks of image data within document page  1  should be combined to create larger, more efficiently processable blocks of image data. If combination is necessary, flow proceeds to step S 709 , in which a hierarchical tree structure corresponding to document page  1  is updated. Flow then proceeds to step S 710 .  
         [0050]    If, in step S 707 , it is determined that the blocks do not require combination, flow proceeds to step S 710 , at which point post-processing of the blocks of image data occurs.  
         [0051]    [0051]FIG. 9 is a representative view of a hierarchical tree structure which results from the method of FIG. 7. Accordingly, “text” nodes  204  to  206  have been grouped with adjacent “unknown” node  203  to form “title” node  366 , “text” nodes  208  to  213  have been grouped with adjacent “unknown” node  207  to form “title” node  367 , “text” nodes  214  to  227  have been grouped together to form “text” node  368 , and “text” nodes  228  to  245  have been grouped together to form “text” node  369 . The resulting blocked page  1  is shown in FIG. 10. Advantageously, and in contrast to FIG. 3, “picture” block  70  is not grouped with “text” block  71 . Accordingly, the connected component within block  70  may be processed differently than the components of block  71 .  
         [0052]    The method of FIG. 11, to be discussed below, is a post-processing method implemented after a block selection technique has been applied to an image. In particular, the method of FIG. 11 is used to check the accuracy of block selection techniques and to update and correct the hierarchical tree data in preparation for all other post-processing. Although the method of FIG. 11 can be used in conjunction with any block selection technique, the method is described below with reference to the above-described technique to provide continuity to the reader.  
         [0053]    Thus, in step S 1101 , connected components within “text” blocks of document page  1  are compared to a threshold size. In this regard, the threshold size may be based on a fixed size threshold for each document page to be analyzed, such as the threshold-size values described in U.S. patent application Ser. No. 07/873,012, or may be calculated based on the average size of connected components within a document page. Therefore, in step S 1101 , if the size of most of the connected components within the block is outside of the threshold or if the block is a “title” block, flow proceeds to step S 1102  to perform OCR processing on the components within the block. On the other hand, if the text size of most of the connected components within the block falls within the threshold, flow proceeds to step S 1109 .  
         [0054]    Using this method on document page  1  of FIG. 10, the connected components of block  70  would not be evaluated in step S 1101  because block  70  is not a “text” block.  
         [0055]    Returning to the flow, in step S 1104 , the results of the OCR processing are examined to indicate whether most of the connected components within the block are recognizable. If not, the block is classified as a “picture” block in step S 1107 , and flow proceeds to step S 1110  and continues as described above.  
         [0056]    For example, blocks  72  and  73  do not meet the criteria of step S 1104 . Accordingly, corresponding nodes  367  and  368  would be reclassified as picture nodes  370  and  371 , shown in FIG. 10.  
         [0057]    If step S 1104  results in an affirmative determination, flow proceeds to step S 1105 , in which the OCR processing results are examined to determine whether most text lines within the subject block are recognizable. If not, flow proceeds to step S 1107  and continues as described above. If most text lines within the block are recognizable, flow proceeds to step S 1106 .  
         [0058]    In step S 1106 , the OCR processing results are examined to determine whether most of the connected components within the block are alphanumeric. If not, flow proceeds to step S 1107 . The connected components of “text” block  74 , which fall below the threshold size utilized in step S 1101 , are not alphanumeric and therefore “text” block  74  would be redesignated as “picture” block  372 .  
         [0059]    Flow then proceeds to step S 1110  as described above, wherein, in the case that all blocks of a document image have been analyzed, flow terminates.  
         [0060]    If, in step S 1106 , the OCR processing results indicate that most connected components of the subject block are alphanumeric, flow proceeds to S 1109 , wherein the “text” attribute of the subject block is confirmed. Flow then proceeds to step S 1110 , as described above.  
         [0061]    For example, “title” block  71  would pass the criteria of each of steps S 1104  to S 1106  and would therefore remain designated a “title” block. Accordingly, as shown in FIG. 12, the hierarchical tree structure of FIG. 9 has been altered by the method of FIG. 11. Specifically, “title” node  367  and “text” node  368  have been updated as “picture” nodes  370  and  371 , and “text” node  369  has been redesignated “picture” node  372 .  
         [0062]    The method of FIG. 11 therefore utilizes OCR processing to accurately identify image data so that such data can be subjected to proper processing.  
         [0063]    Of course, because the methods of FIGS. 6 and 7 and the method of FIG. 11 are employed at different points of a block selection technique, these methods may be used either separately or in conjunction with each other, as described above.  
         [0064]    The present invention further contemplates improving existing block selection techniques by employing OCR processing each time connected components within a block are evaluated, such as during separating, classifying and grouping blocks of image data. Therefore, the present invention can be embodied in a page analysis system in which results of OCR processing are used as a criterion in initially separating blocks of document image data into text and non-text blocks and/or in further classifying the blocks according to non-text data types.  
         [0065]    Although this system would embody the present invention, it is not a preferred embodiment, since OCR processing is quite time-consuming. Accordingly, it is presently inefficient to employ OCR processing in every situation in which it might be helpful. On the contrary, the foregoing embodiments were developed so as to reduce needless inefficiency resulting from OCR processing by applying such processing in a manner which maximizes its net positive impact.  
         [0066]    The invention has been described with respect to particular illustrative embodiments. It is to be understood that the invention is not limited to the above described embodiments and modifications thereto, and that various changes and modifications may be made by those of ordinary skill in the art without departing from the spirit and scope of the appended claims.