User-enclosed region extraction from scanned document images

[0002] The present invention relates generally to document processing. More particularly, the invention relates to the extraction of a user-enclosed portion of text or non-text regions from bitmap images.

[0003] People like to scribble marks and notes on documents while reading. For example, when a person is reading a book or a magazine, he or she might draw circles with a pen over the parts that are of particular interest. When the person underlines a few lines, circles a paragraph, writes notes on a page these notes and marks often convey important cues to the content of the document and may serve as keys or references for communications with other people. As more and more paper documents are now being converted and archived in electronic media, it is useful if these underlines, highlights, circles, handwritten or Post-It notes on a paper document can be automatically identified, located, their associated contents extracted and preserved in a document management system.

[0004] The present invention describes a technique for locating and extracting one type of user-drawn marks from a scanned document—the user enclosed regions. The invention is based on the bi-connected component analysisi in graph theory. The invention first represents the content of the input image as run-length segments. The invention then constructs line adjacency graphs from the segments. Finally, the invention detects user-enclosed cicles as bi-connected components of the line adjacency graphs.

[0005] The present invention is useful in applications such as in an electronic filing system or in storage management for document databases. Currently, the burden of cutting and pasting a selective region from a page (for example, an article from a newspaper) for archival is on the user. However, a user is sometimes only interested in specific portions on a page. The circled region extraction technique offers a means for a user to simply mark the regions of interest and let the imaging process identify the regions and save them alone. Alternatively, different compression strategies may be applied to user-enclosed regions to preserve the quality of the image in these regions.

[0006] The present invention analyzes the image of the scanned document in its native bitmap format using a connected component module. The invention is writing system independent. It is capable of extracting user-enclosed regions from document images without regard to what character set or alphabet or even font style has been used. The connected component module then stores the components of the image that are connected. The connected component data is stored in a datastructure in the form of a line adjacency graph to expedite the further processing of the connected component data.

[0007] The connected component data is then analyzed by a graph traversal module to extract geometric properties of each connected component and store the geometric properties in a datastructure. The geometric features extracted are those geometric features that are necessary for further analysis by the invention.

[0008] The invention then separates the largest bi-connected component from the user-enclosed regions of the document image by utilizing a bi-connected component module. The bi-connected component module detects any enclosure regardless of shape. Furthermore, the user drawn enclosure can cross lines of text or graphics on the document paper and still be recognized as a bi-connected component. The bi-connected component module utilizes a depth-first search that allows the detection of the largest bi-connected component to be done in an efficient manner.

[0009] Following the bi-connected component module, a detection analysis filter further refines the extraction process by qualifying each user-enclosed candidate. These additional heuristics eliminate from the possible selection of user-enclosed regions those bi-connected areas that are not above a minimum size, or are photographic images.

[0010] After having selected the user-enclosed regions the extraction module separates the bitmap portion that lies within the user-enclosed region and stores that extracted portion of the document image in a storage medium for future reference and manipulation by the user. The present invention enables the user to save a large amount of disk storage space by extracting only the portions of the document image that the user is interested in.

[0011] For a more complete understanding of the invention, its objects and advantages, reference may be made to the following specification and to the accompanying drawings.

[0012] FIG. 1 is a block diagram giving an overview of the system architecture in which the invention may be employed;

[0013] FIG. 2 is a system block diagram of the preferred embodiment of the present invention;

[0014] FIG. 3aand 3bare the graphical representation of a connected component and its corresponding line adjacency graph;

[0015] FIG. 4 illustrates various geometric features of a connected component in the form of a line adjacency graph;

[0016] FIG. 5aillustrates a representation of a bi-connected graph of a connected component;

[0017] FIG. 5billustrates a representation of a non-bi-connected graph of a connected component; and

[0018] FIG. 5cillustrates the separation of a non-bi-connected component into separate bi-connected components.

[0019] The present invention is designed for locating and extracting user-enclosed regions from a scanned document. Accordingly, in FIG. 1, a system utilizing the invention to extract user-enclosed regions from scanned documents for storing and printing the extracted regions has been illustrated.

[0020] The user-enclosed region extraction device of the present invention is preferably either a computer implemented software program run on a suitable computer system or an embedded system suitable for incorporating into an imagining device, such as within the imaging processor of a scanner or the like. As illustrated in FIG. 1, the user-enclosed region extraction software program runs on a computer system 18. The computer system 18 is coupled to various peripheral devices through suitable communication connections where the peripheral devices perform various tasks such as scanning and printing. The computer system 18 can be any commercially available computer system. The presently preferred embodiment is designed to run on a Microsoft Windows 95/NT operating system Although, other operating systems, including Unix systems, may be used as well. The computer system 18 of the present invention is attached to the peripheral devices directly by communication interface cards, as are well known in the art, and by a standard communication cable. The peripheral devices may also be connected via network.

[0021] In the present invention a user will take a document 10 and circle or enclose the desired contents within the document 10 by using a pen or any other writing utensil that leaves a mark which is readable by a scanner 14 or a fax machine 16. The scanner 14 will transmit the data over the communication link to the computer 18. The computer 18 extracts the user-enclosed region and in the preferred embodiment stores the extracted image 22 in the personal computer's hard disk 20. The user may print the extracted user-enclosed regions if desired, on a printing device such as a laser printer 24.

[0022] Referring to FIG. 2, a software block diagram of the system is illustrated. The functional blocks illustrated in FIG. 2 are embodied in and operated by the processor of the computer system 18. The computer-implemented software system employs a group of processing modules, each designed to perform different data manipulation functions. These processing modules have been illustrated by enclosed rectangles. The data structures have been illustrated using open-ended rectangles, to distinguish them from the processing modules. Also, to aid in understanding the invention, the processing modules of the invention have been arranged in a top-down order, showing the sequence in which various modules are placed in service.

[0023] An exemplary page of image data, such as a page 27 from a magazine article, has been illustrated. Although the visual image of page 27 is illustrated here, it will be understood that the page 27 actually comprises image data, such as bitmap image data, in which individual black or white pixels of the image are stored as binary numbers.

[0024] First, the connected component analysis is performed by an analyzer 28 upon the bitmap image data of the page 27. A connected component in a binary image is a maximal set of touching black pixels. Essentially, the connected component extraction process starts with a given data element within the bitmap image data of the page 27 and analyzes the adjacent data elements to determine whether they comprise part of a connected component. For example, the black dots that form the letter “A” or a user drawn circle are all connected and thus comprise a connected component.

[0025] In the preferred embodiment the connected component analysis is performed in a raster-scan fashion whereby contiguous black pixels in the same horizontal line are created and treated as a single unit called a segment. A line adjacency graph algorithm is then used to represent the segments produced by the connected component analyzer 28 in a line adjacency graph that is to be stored in a connected component LAG data structure 30.

[0026] FIGS. 3aand 3billustrate how a connected component from a bitmap image is converted into a line adjacency graph for storage in the connected component LAG data structure 30. The overlapping black segments at the top of the connected component shown in FIG. 3ahave corresponding representations in the line adjacency graph shown in FIG. 3b. Each black segment is represented as a node in the line adjacency graph. For example, the connected component shown in FIG. 3acontains a segment 50 along scan line 54 which is represented as a node 64 in the corresponding line adjacency graph that is shown in FIG. 3a. Likewise, segment 52 along scan line 56 is represented as node 68. Scan lines 54 and 56 are adjacent in the image. If two or more black segments are adjacent in the vertical plane, that adjacency is represented as an edge in the line adjacency graph. For example, the segments 50 and 52 are adjacent in the vertical plane, therefore the corresponding nodes 64 and 68 are joined by a line 66 in the corresponding line adjacency graph. Segments that are separated in the horizontal plane are also separated in the line adjacency graph of the connecting component. For example, the black segments 60 and 62 are separated by a space along the scan line 58. The corresponding nodes 70 and 72 corresponding to segments 60 and 62 are also separated in the graph.

[0027] After the connected component LAG datastructure 30 has been populated by the connected component analyzer 28, a graph traversal module 32 is then called upon to extract certain geometric features from each connected component and store them in a geometric features datastructure 36. FIG. 4 illustrates various geometric features of a connected component which include the width and height of a bounding box 75 where the bounding box 75 is defined as the smallest rectangle that can encompass the connected component. Further geometric features include the an area of the bounding box 75, number of holes 76, the number of upward and downward arcs 78, the number of downward ends 80 and 82, the number of upward ends 74, and various other geometric features.

[0028] After the geometric features datastructure 36 has been populated, a bi-connected component module 38 is used to separate all bi-connected components from the rest of the image content. The bi-connected component module 38 accesses the connected component LAG datastructure 30 to analyze each line adjacency graph of a connected component for bi-connected components.

[0029] A line adjacency graph connected component is defined as bi-connected if the removal of any of its nodes does not break the graph into disconnected sub-graphs. FIG. 5billustrates a non-bi-connected graph where disconnecting nodes 102 and 108, would yield separate connected components having 3 sub-graphs, as shown in FIG. 5c. FIG. 5ashows a bi-connected component where the removal of any one of the nodes 84, 86, 88, 90, 92, 94, and 96 will not break the graph into separate sub-graphs. A graph may contain several bi-connected components. A bi-connected component is, by definition, the largest sub-graph that is bi-connected. Thus the system decomposes a line adjacent graph into its bi-connected componenents. For example, the connected component that contains the nodes 84, 86, 88, 90, 92, 94 and 96 is a bi-connected component.

[0030] In the preferred embodiment of the invention the bi-connected component module 38 utilizes a depth-first search module 40 for determining the amount and size of the bi-connected component sub-graphs from the graph. The module 40 first initializes all nodes of the graph as being unvisited. Processing of the graph starts from an arbitrary node known as the root node. Each node is processed when it is first discovered. Once a node is processed a bit is then set, thereby indicating that the particular node has been visited. The adjacent nodes that are connected to the node being processed are scanned to determine if they have been processed. Each time an unvisited node is discovered it is processed recursively by the algorithm. After a node's adjacent neighbors have been processed, the algorithm returns to the previous node until it has returned to the root node and processed all nodes that are connected to that root node. Then the next unprocessed node in the graph is chosen as a root node and the same procedure is repeated again until every node in the entire graph has been visited. The information associated with each node is utilized to determine the largest bi-connected component of the line adjacency graph.

[0031] A detection analysis filter 42 supplies the functionality needed to reduce the false detection of user-enclosed regions after the bi-connected component module 38 has processed the line adjacency graphs of the connected component from the connected component LAG datastructure 30. For example, false bi-connected components may include a large print character like the letter “o”, a part of a photographic element that contains many holes, or graphic elements that contain holes. The above mentioned examples must be distinguished from the user-enclosed region. In order to reduce the false detection of user-enclosed circles in the presently preferred embodiment, a number of heuristics are employed to distinguish the user-enclosed region from bi-connected components that are not user-enclosed.

[0032] The first heuristic is a minimum size detector. The minimum size detector compares the bounding box 75 of all the bi-connected components that have been found by the bi-connected component module 38 to a predetermined size. Since characters that contain holes can be considered as connected components, and the characters are relatively small when compared with a typical user-enclosed region, a minimum size threshold is set for bi-connected components to be considered as a user-enclosed region. In the preferred embodiment the width and height of a bounding box must be {fraction (1/10)} of the total image width and height. For example, the detector first determines the width and height of the image, then compares the height and width of the bi-connected component to the height and width of the image. If the width and height are not greater than the width and height of the image then that particular bi-connected component is discarded as a possible user-enclosed region.

[0033] Another heuristic is a rectangle frame detector. In most newspaper and magazine articles a rectangle frame encloses text, photographs and graphics. The bi-connected component module will consider a rectangle frame a bi-connected component. The rectangle frame detector eliminates such bi-connected components from further consideration. The rectangle frame detector utilizes the fact that a rectangle has two parallel sides while the user-enclosed region will not have parallel sides. The rectangle frame detector calculates the distance from the left most pixel of a bi-connected component to its right most pixel along each scan line. The average distance and the standard deviation of all the scan lines is calculated. If the standard deviation is larger than a given threshold then the bi-connected component is considered a user-enclosed region candidate. In the preferred embodiment the threshold is set at 10% of the average distance. The bi-connected component that has a given standard deviation less than a predetermined threshold is discarded.

[0034] A third heuristic, a photograph element detector distinguishes a photographic region from a user-enclosed region. A photographic region typically has a much higher black-pixel density than the area that is user-enclosed. The photograph element detector calculates the percentage of black pixels in the bounding box 75. In the preferred embodiment of the invention the threshold percentage is calculated as 40%. If the pixel density is higher than 40% the bi-connected component is discarded from the list of user-enclosed regions.

[0035] An extraction module 44 extracts the image component enclosed by each user drawn enclosure. The extraction module 44 performs the extraction by identifying the leftmost black pixel and the rightmost black pixel on each scan line. The region bounded by the leftmost and rightmost black pixels is the user-enclosed region and is extracted. The extracted region 22 is, in the preferred embodiment, stored in a storage device 20 such as a hard disk.

[0036] While the invention has been described in its presently preferred embodiment, it will be understood that the invention is capable of certain modifications without departing from the spirit of the invention as set forth in the appended claims.