Abstract:
The invention described herein provides a method and apparatus for document processing that efficiently separates and interrelates single modalities, such as text, handwriting, and images. In particular, the present invention starts with the recognition of text characters and words for the efficient separation of text paragraphs from images by maintaining their relationships for a possible reconstruction of the original page. The text separation and extraction is based on a hierarchical framing process. The process starts with the framing of a single character, after its recognition, continues with the recognition and framing of a word, and ends with the framing of all text lines. The method and apparatus described herein can process different types of documents, such as typed, handwritten, skewed, mixed, but not half-tone ones.

Description:
PRIORITY CLAIM UNDER 35 U.S.C. §119(e) 
   This patent application claims the priority benefit of the filing date of a provisional application, Ser. No. 60/354,149, filed in the United States Patent and Trademark Office on Feb. 4, 2002. 

   STATEMENT OF GOVERNMENT INTEREST 
   The invention described herein may be manufactured and used by or for the Government for governmental purposes without the payment of any royalty thereon. 

   BACKGROUND OF THE INVENTION 
   The recognition of printed and handwritten characters and words is an important research field with many applications existing in post offices for identifying the postal code from the addresses on the envelopes and sorting the mail, in banks for check processing, in libraries for computerizing the storage of books and texts, and also as reading devices for blind people, etc. Although many methodologies and systems have been developed for optical character recognition (OCR), OCR remains a challenging area. In particular, a good OCR system spends on the average about 2–3 seconds for the recognition of a handwritten character from a handwritten word. An extreme case is the OCR system by Loral, which is based on a very expensive parallel multiprocessor system of 1024 Intel-386 microprocessors, where each 386 CPU processes only one character at a time. There are also many OCR methods based on neural networks, such as the AT&amp;T Bell labs OCR chip, the multiple Neural Networks OCR approach, etc. There are some other OCR methods based on human like recognition. One of them uses a fuzzy graph based OCR approach, with adaptive learning capabilities, which reduces the character dimensions to speed up the recognition process. It scans the text page, detects a character, extracts and recognizes it, produces the appropriate ASCII code, and sends it to the host computer in a few milliseconds simulated average test time. Image Processing and Pattern Recognition (IPPR) are two older research fields with many significant contributions. The recognition and extraction of objects from images is a small sub-field of IPPR. There are many successful methods based on neural nets or graphs to recognize different kind of objects (faces, cars, chairs, tables, buildings, etc) under very noisy conditions. 
   Recently, attention has been focused on the document processing field due to multimedia applications. Although document processing is an interesting research field, it introduces many difficult problems associated with the recognition of text characters from images. For instance, there are cases where a document can be considered either as text or as image, like images generated by text characters. Also, artistic letters in very old and valuable books, where the starting letter of each paragraph look like a complex image. In some cases, however, the text is handwritten, and the problem becomes more difficult. Several methods have been developed for document processing. Most of these methods deal with the segmentation of a page and the separation of text from images. One prior art method is a “top-down” approach and produces good results under the condition that the examined page can be separated into blocks. Another prior art method is algorithmic “bottom up” process with good performance in several categories of pages with good spacing features, and “non overlapping” blocks. Yet another prior art method exists and is also a “bottom up” process with very good performance especially in long text uniform strings. Still another prior art method exists that separates images from text (typed or handwritten) by maintaining their relationships. 
   OBJECTS AND SUMMARY OF THE INVENTION 
   One object of the present invention is to provide a method and apparatus for processing documents by separating text from images yet maintaining their relationship for reconstruction. 
   Another object of the present invention is to provide a method and apparatus for recognizing single characters, words, and lines of text. 
   Yet another object of the present invention is to provide a method and apparatus for recognizing typed as well as handwritten words and letters. 
   The invention described herein provides a method and apparatus for document processing that efficiently separates and interrelates single modalities, such as text, handwriting, and images. In particular, the present invention starts with the recognition of text characters and words for the efficient separation of text paragraphs from images by maintaining their relationships for a possible reconstruction of the original page. The text separation and extraction is based on a hierarchical framing process. The method starts with the framing of a single character, after its recognition, continues with the recognition and framing of a word, and ends with the framing of all text lines. The method and apparatus described herein can process different types of documents, such as typed, handwritten, skewed, mixed, but not half-tone ones. 
   According to an embodiment of the present invention, method for separating text from images, comprises the steps of: a first step of scanning a binarized page of text so as to detect a character; a first step of creating a temporal window on the binarized page and a second step of scanning the temporal window so as to extract a character shape; graphing line segments; recognizing and framing a character; a first step of connecting adjacent character frames in the same word; a second step of creating multi-frame word blocks; recognizing hand-written words; a second step of connecting word frames; saving the coordinates of lines of text and paragraphs on a given page; and extracting images from a page. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1A  graphically depicts the scanning of a binarized page of text. 
       FIG. 1B  depicts the method steps for scanning and detecting a character within a binarized page of text. 
       FIG. 2A  graphically depicts the temporal window created on a page of binarized text. 
       FIG. 2B  depicts the method steps for scanning within a temporal window and extraction of a character shape. 
       FIG. 3A  graphically depicts a graph of line segments. 
       FIG. 3B  depicts the method steps for graphing line segments. 
       FIG. 4A  graphically depicts recognition and framing of a character. 
       FIG. 4B  depicts the method steps for recognizing and framing a character. 
       FIG. 5  graphically depicts the framing of a character. 
       FIG. 6A  graphically depicts the connection of adjacent character frames in the same word. 
       FIG. 6B  depicts the method steps for connecting adjacent character frames in the same word. 
       FIG. 7  graphically depicts the eight possible connection patterns for adjacent character frames of the same word. 
       FIG. 8A  graphically depicts the creation of a multi-frame word block. 
       FIG. 8B  depicts the method steps for creating a multi-frame word block. 
       FIG. 9A  graphically depicts the recognition of handwritten words. 
       FIG. 9B  depicts the method steps for recognizing handwritten words. 
       FIG. 10  depicts graphically the connection of word frames. 
       FIG. 11  depicts graphically saving the coordinates of lines of text and paragraphs on a given page. 
       FIG. 12  depicts the method steps for extracting an image from a page. 
   

   DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
   Binarization &amp; Character Detection 
   Referring to  FIG. 1A  and  FIG. 1B , the entire text page is initially binarized  100  and its pyramidal form is generated  110 . A “pyramidal” representation of a 2D array (i.e., an image of a document page in the present invention) is the hierarchically reduced representations of the array from the original representation comprising N×N pixels, to the final representation comprising 1×1 pixels. All such diminishing array representations (or layers) portray a “pyramidal” structure of reduced size in layers. Then the page area is scanned  120  for the isolation and interrelation of informative regions R k (ij), kεZ, with text or images. When the first top “informative” region R 1 —a region with text or image—is detected  130 , the methodology defines that particular region at the “first pyramidal” level  140  (i.e., the “first pyramidal” level in the present invention is the original page of N×N pixels) and focuses  150  on the upper left corner of the region to detect a text character  160 , if possible. 
   Character Recognition 
   Referring to  FIG. 2A  and  FIG. 2B , the character recognition process starts with the creation of a temporal window  170  Wnxm, of nxm pixels. This window W covers the upper left area of the actual (in size) region R 1 . A scanning process takes place  180  within window Wnxm, to detect the edges of possible character or the shape of an unknown object. When an edge is detected  190 , a Chain Code (CC) method is used to extract the shape  200  of the unknown character or object. The “unknown” shape extracted by the CC method is represented  205  as a string S:
 
 S=cn   k1 ( dj   k1 ) n   k2 ( dj   k2 ) . . .  cn ( dj   ll ) . . .  n   lm  ( dj   lm ) cc  
 
where n km  ε Z, dj km  ε {1,2,3,4,5,6,7,8}, c=0, cc=9, and i,j,k,l,mεZ.
 
   Referring to  FIG. 3A  and  FIG. 3B , a line generation and recognition process is applied  210  on the string S and its segments are recognized  220  either as straight lines (SL) or as curved lines (CL). At this point the present invention converts  230  a string S into a graph G:
 
 f:S→G=N   1   a   r   12   N   2   a   r   23    N   3   . . . a   r   nk   N   k  
 
where a line segment (SL or CL) corresponds to a graph node:
 
 f:SL   i   →N   i    or CL   j    →N   i  
 
where each graph node N i  represents the properties of the corresponding segment:
 
 N   i ={Realtive Starting Point (SP), Length (L), Direction (D), Curvature (K)}
 
and each are a r   ij  represents the relationships between segments:
 
a r   ij ={connectivity (co), parallelism (p), symmetry (sy), relative size (rs), relative distance (rd), relative orientation (ro), similarity (si), . . . }, r ε{co, p, sy, rm, rd, si}
 
   For the actual matching process, each node N i  has only property in the curvature (K). 
   Referring to  FIG. 4A  and  FIG. 4B , in the event that a text character is extracted  240  and represented in a graph form, a fuzzy graph matching process takes place  250  within a graph data base to classify  260  the character. The classification of a character is associated with attributes, such as orientation, size, and font. If, however, the extracted pattern is not recognizable  265 , the present invention considers it as a possible piece of an image or drawing  270 . Thus, the present invention saves the unknown pattern&#39;s coordinates  280  and continues the extraction  240  of the next pattern. If the new extracted pattern is also unrecognizable as a text character  240 , the present invention repeats its attempts until it covers that particular informative region, by generating a block (or blocks) of non-text patterns and saving each block&#39;s coordinates  280  for future reconstruction. 
   Character Framing 
   Referring to  FIG. 5 , when a particular character is recognized by the present invention, its attributes are used for the generation of its frame  290  (see  FIG. 4B ). This a flexible process since it provides the ability to frame characters with different skews and size.  FIG. 5  shows the framing of a character by using the maximum points sp (for top) and cp (for left side), and the frames of different size characters. If it is determined that a particular character has overlapping parts with adjacent characters  275  (see  FIG. 4B ), a voting recognition process is used to appropriately recognize it  300  (see  FIG. 4B ). 
   Connecting Character Frames 
   Referring to  FIG. 6A  and  FIG. 6B , when the framing of the first character is completed  310 , the character extraction and recognition process is repeated  320  with the next neighboring character which has the same or different orientation (v) with the previous one. Thus, after the framing of the next character, the present invention connects these two frames into one  330 , once it has been determined that they belong to the same word  340 . The connection (or synthesis) of two frames (see  FIG. 6A ) starts with the use of the frames orientations (v i , v j , i,jεZ+) to match  350  one of the eight possible connection patterns (see  FIG. 7 ). The present invention assumes that two consecutive characters belong to the same word if the distance between them is equal or smaller than (dc), where dc is a predefined parameter. The connection block (cb) is generated by the projection of h i  into the other frame&#39;s high h j . Thus, the shape of cb varies according to the orientations of these two frames. 
   Word Framing 
   Referring to  FIG. 8A  and  FIG. 8B , the present invention repeats character framing  310  (also see  FIG. 4B ) until it is determined  360  that the distance between the last two consecutive characters is greater than dc. Thus, at the end of this step, the present invention creates a multi-frame block  370  for the extracted word by using the character frames and their projections to each other,  FIG. 8A  shows graphically the synthesis of frames and connection blocks by using the eight possible connection patterns (see  FIG. 7 ). In particular, frame (W) is connected to the frame (h) by using connection pattern “e”, frame (h) is connected to the frame (e) using connection pattern “e”, frames (e) and (r) use connection pattern “b”, and frames (r) and (e) use connection pattern “a”. 
   Word Recognition 
   Referring to  FIG. 9A  and  FIG. 9B , the present invention has the ability to recognize handwritten words by appropriately segmenting them  380  and temporarily saving  390  their recognizable ASCII codes. It then composes  400  these codes into text words and compares  410  them with the contents of the lexicon database. If it is determined that a character is not isolated from the adjacent characters  420 , due to overlapping and/or underlining, the present invention moves the window Wnxm into three positions (left, center, right, see table-1) around the character  430  and each time a character recognition is performed. This means that three character recognition attempts are made  435  for a possible single character, in an effort to optimize the correct recognition of each character and the “best” segmentation of the examined word. The three recognizable character outputs are compared  440  in a voting section and the character with more than two appearances is selected  450  as the one with the higher probability. At the end of this process, the selected character is saved in the memory  460 . The same process is repeated until it is determined  470  that the “last” character of the examined word has been recognized and saved in the memory. At this point the present invention extracts the length of that particular word  480 , defines the starting character (if possible)  490  and attempts a fuzzy matching process with the known words in the lexicon database  500 . As a result of this matching process, a number of words associated with their matching probability are retrieved from the lexicon database. Thus, the word with the highest probability (if any) is selected as the correct one. The word given in  FIG. 9A , the fuzzy matching to lexicon database, provides as a first choice the word “animation” (55%) and second choice the word “animosity” (11%). It has been shown that the word recognition process has an 89% success on different styles of handwritten words. 
   Text Line Framing 
   Referring to  FIG. 10 , the connection of word frames follows a similar procedure, like the connection of character frames, by connecting  510  the last frame of each word with the first frame of the next one. Thus, a text line frame may be a multi-skew block, which covers only the characters frames and the space of the connection blocks. 
   Connecting and Extracting Text Line Frames 
   Referring to  FIG. 11 , in order to extract text lines from a document, it is necessary to save the coordinates (x,y)  520  and the relative orientation (rv)  530  of the first character frame of each text line relative to the borders of the document page. Thus, the framing and the extraction of paragraphs or the entire text of a document page is obtained by interrelating the extracted text line blocks  540  with numbers (#N)  550  according to their relative positions on the document page. 
   Extracting Images 
   Referring to  FIG. 12 , the extraction of the images is based on a sequential scanning of the image region  560 , by saving the coordinates (X,Y) of the upper left top pattern  570  and its relative orientation (RV)  580  regarding with the borders of the document page. 
   While the preferred embodiments have been described and illustrated, it should be understood that various substitutions, equivalents, adaptations and modifications of the invention may be made thereto by those skilled in the art without departing from the spirit and scope of the invention. Accordingly, it is to be understood that the present invention has been described by way of illustration and not limitation.