User drawn circled region extraction from scanned documents

[0002] The present invention relates generally to the electronic documents and imaging. More particularly, the invention relates to a system and method for identifying a user-circled region on a scanned document or bit mapped image, to allow information within the encircled region to be further analyzed as by optical character recognition.

[0003] With the rapid development of computer technologies, more and more documents have been archived in electronic form. The electronic form raises an entirely new set of issues concerning information retrieval.

[0004] Unlike alphanumeric text files, which can be keyword searched easily, files containing bitmapped images or scanned information cannot be so readily searched. This is because bitmapped images and scanned documents represent printed words as graphical pictures made up of tiny black, white or colored dots that are not directly recognizable by a computer as characters or letters of the alphabet. Fortunately, in many cases these graphical pictures of characters and letters can be converted into computer-recognizable text characters by employing optical character recognition (OCR) software. Even with fast computers, the optical character recognition conversion process is a slow one. In many cases it is simply not practical to convert entire bitmapped image for scanned documents using optical character recognition software.

[0005] In cases where it is not practical to employ optical character recognition conversion, document image databases may be indexed by the user manually assigning a character-based text name or label to each bitmapped image or scanned image. The computer then associates the text name or label with the image data, so that the image data can be later retrieved by searching upon the text name or label.

[0006] Manual entry of appropriate text names and labels is labor intensive and often requires additional computer hardware, including keyboard or numeric keypad connected to the document imaging station. Taking a fresh look at the indexing problem, some have suggested embedding technology within the document imaging system that would recognize user-circled regions. Such regions, if identified, could serve to localize, and thus minimize, the optical character recognition process. The user would circle the graphical image of a desired keyword, and the system would then perform optical character recognition on the image data within the circle, converting it into a label that would then be associated with the image data file.

[0007] Unfortunately, while the idea has merit, it has proven quite difficult to accurately and repeatedly detect the user-circled region, particularly given the wide variation in handwriting quality from one user to the next. The problem is further compounded by the fact that some user-drawn circles may overlap or intersect with other circles (whether user-drawn or not); and because some user-drawn “circles” may not be fully closed. The latter problem can arise where the user simply does not fully finish drawing a circle, or where the user-drawn circle is broken by image dropout. Image dropout can occur, for example, when a light or thin circle is drawn and then processed by low resolution scanning equipment.

[0008] The present invention addresses these problems by a system and method that “traces” a circle candidate, identifies key geometric features of the traced shape and then generates a substitute circle using the identified points as a guide. The substitute circle, having been computer generated, forms a fully closed circle structure that may be more reliably relied upon for extracting text contained within the circled region.

[0009] In instances where the user does not draw a fully closed circle, the system can employ one of a variety of endpoint proximity algorithms to ascertain whether the users intent was to draw a fully enclosed circle, or not.

[0010] For a more complete understanding of the invention, its objects and advantages, refer to the following specification and to the accompanying drawings.

[0011] FIG. 1 is an example of a document page, showing a user-circled region;

[0012] FIG. 2 is an example of an electronic document displayed on screen and circled by use of a stylus;

[0013] FIG. 3 illustrates a document image database system in accordance with the invention;

[0014] FIG. 4 is a flowchart illustrating the preferred steps for extracting circled regions from scanned or bitmapped documents;

[0015] FIG. 5 is an example of overlapping objects;

[0016] FIG. 6 is an example of the overlapping objects of FIG. 5, showing contours and feature points;

[0017] FIG. 7 is an illustration of incoming and outgoing angles;

[0018] FIG. 8 is an example of reconnecting according to the preferred smoothness algorithm;

[0019] FIGS. 9A-9D illustrate four (4) different cases for connecting two (2) segments;

[0020] FIG. 10 illustrates the reconnecting of feature points using the example of FIGS. 5 and 6;

[0021] FIGS. 11A-11C illustrate three (3) alternate embodiments of a closed loop criterion function;

[0022] FIGS. 12A-12G illustrate examples of accepted and rejected objects;

[0023] FIGS. 13A-13B provide two (2) examples for closing a gap within a user-drawn circle for display.

[0024] The system and method for extracting user-drawn circled regions can be applied in a wide variety of different applications. FIG. 1 illustrates an example of a document page with two (2) user-drawn circled regions at 20 and 22. Note that circle 20 is partially closed and circle 22 overlaps with an adjacent rectangular annotation. The document can be suitably digitized using a variety of different devices, including scanners, fax machines, digital photocopy machines, and the like. Once digitized, the document is represented as a bitmapped image, or scanned image. As will be more fully explained, the extraction system and method locates the user-drawn circled regions and extracts the encircled region content. The content may then be further processed as with optical character recognition software. The user-drawn circles can be applied using any suitable drawing instrument.

[0025] Alternatively, the document can be an electronic document, displayed upon the screen of a computer or document imaging display, for example. FIG. 2 illustrates an electronic document displayed upon the screen of a laptop computer 26 and in which the user-drawn circles are formed using a stylus 28 to draw on digitizing pad 30.

[0026] The embodiment of FIG. 2 illustrates that the document does not necessarily need to originate as a paper document. Rather, the document can be generated by software that creates a bitmapped image, such as any of the popular paintbrush programs or photo manipulation programs. Alternatively, the document can be input using a digital camera or video camera. To illustrate, FIG. 2 shows a digital camera 32 connected to computer 26. This camera can be used to take a picture of the document of interest. Thereafter, the user draws circled regions using stylus 28.

[0027] To further illustrate some of the possible uses for the invention, refer to FIG. 3, which shows an exemplary electronic document imaging system. The system includes a document imaging server 40 that has an associated storage medium such as a disk array 42. The server is coupled through suitable network communication link 44 to a variety of document input devices and viewing devices. For example, a digital copy machine 46 or flatbed scanner 48 can be used to convert paper documents into electronic form for storage by the server 40. Once digitized and stored, the document images may be viewed on any suitable workstations such as computer workstation 50.

[0028] Documents are stored in the document image database as a series of digital image data records to which an associated index label is attached, as illustrated diagrammatically at 52. The user-drawn circled region extraction system of the invention uses the extracted region to generate the index label by which the digital image data may be later retrieved. The region extraction system software may be hosted by any suitable processor in the system. Such processors include, for example, the server 40, the workstation 50, and even the processors associated with the copy machine 46 or flatbed scanner 48.

[0029] The presently preferred embodiment of the circled region extraction process is illustrated in FIG. 4.

[0030] The presently preferred contour analysis technique is illustrated in FIG. 4. The technique is based on identifying the contour of a candidate object. The candidate object may include user-drawn circles, machine printed frames or other non-text materials on the page. By analyzing the contour using a feature extraction module, the algorithm extracts the user-drawn circle. The contour is represented by a sequence of points with different curvature values. This makes it possible to distinguish a user-drawn circle from a machine-printed frame through a post processing analytical technique. Referring to FIG. 4, to speed up the algorithm further, an optional pre-processing step may be performed at 250. The first step (step 252) is to find the connected components within a given page. In this step the image is scanned line-by-line and each pixel is labeled if it is connected with its neighboring pixels. After labeling the pixels for connectivity, a bounding box is calculated for each connected component. These bounding boxes are used to extract the candidate area in the image.

[0031] Next (at step 254) connected components representing text are eliminated. This is accomplished by analyzing the size of the bounding box and eliminating those connected components that have bounding boxes below a predetermined size. Eliminating connected components that are not likely user-drawn circle candidates helps speed up subsequent processing. However, if sufficient processing power is available, step 254 can be eliminated.

[0032] Next, halftone images are eliminated at step 256. Halftone images compose large connected components. The algorithm detects halftone images by assessing the black-to-white pixel ratio within the bounding box associated with the connected component in question. Halftone images tend to have more black pixels than areas containing text. Again, if sufficient processing power is available, it may not be necessary to eliminate half tone images at step 256. The preferred embodiment eliminates half tone images as user-drawn circle candidates, thus significantly improving processing speed.

[0033] The contour analysis technique may generate more feature points than are actually required when there are extraneous characters touching the contour in question. This can occur, for example, when the user draws a circle that happens to intersect with other characters on the page.

[0034] The optional pre-processing step eliminates these touching characters by performing a morphological operation to simplify the shape of the contour in the region where the user-drawn circle and extraneous character intersect.

[0035] Next, the user-drawn circle is identified by examining different candidate areas on the page. The first step in this procedure, depicted at 258, involves generating the contour of the candidate object. This is performed by tracing the outline of the object.

[0036] By way of illustration, refer to FIG. 5, which shows an example of two (2) candidate areas. Note that these areas happen to overlap, which makes the user-drawn circle detection problem more difficult. Also note that shape 60 has a gap at 61 where the circle was either not fully formed or contains a dropout or some other defect. The algorithm must determine which of the contours is the user-drawn circle. In FIG. 5 there are four (4) possibilities: the elliptical shape 60, the rectangular shape 62, the overlapping intersection 64 of shapes 60 and 62, and the combined outer boundary shape 66 of shapes 60 and 62 combined.

[0037] The contour is represented in computer memory as an ordered set of points (coordinates of the boundary pixels). The tracing scheme first scans for the starting point (a border pixel that is not previously traced). Then the trace starts in either a clockwise or counter-clockwise direction along the convex outline of the object. When the trace goes back to the starting point, or to a point where no more black pixels can be found around the current one, the trace stops and the scanning process to find the next starting point continues.

[0038] FIG. 6 shows an example of the trace contours that would result when the tracing step 258 is performed on the overlapping objects of FIG. 5. Note that the contour tracing appears as closely spaced double lines that follow the inside and outside perimeters of the lines that define the objects.

[0039] Next the contours obtained during step 258 are analyzed by calculating feature points associated with each contour (step 260). Contours obtained from step 258 can be closed curves or broken curves, due to noise in the image. Feature points are defined as high curvature points, including junctions of circles with other objects. Curvature can be calculated using re-sampling techniques, however this may not be reliable when noise is generated during the digitization process. By observation, the feature points can be detected approximately at either the local maxima or local minima on the x and y direction, even though not all maxima and minima are feature points. In the preferred implementation the starting point and ending point of each contour are treated as feature points. FIG. 6 shows the applicable feature points at 70-86.

[0040] After feature points have been identified, the circled region is reconstructed using the feature points. This is illustrated at step 262. In essence, each contour generated at step 258 is broken into segments at the feature points. These segments are examined and reconnected such that segments belonging to different objects are separated and those belonging to the same object are connected.

[0041] The main criterion for reconnecting the contour segments is to check the smoothness when making the transition between neighboring segments. For each contour segment, a small area around its starting and ending points is examined. The points on the two ends are fitted into lines so that the slope (angles coming and going out of the segment) can be estimated. These estimated angles are used to assess whether two line segments are approaching one another such that they should be connected as belonging to the same contour or are crossing one another such that they belong to unrelated contours.

[0042] FIG. 7 shows how each contour segment is assessed. The starting and ending points are examined by fitting the endpoints into lines, so that the slope may be assessed. In FIG. 7, angle 1 is the incoming angle and angle 2 is the outgoing angle. The direction of the contour segment in FIG. 7 is from a to b. The incoming angle is estimated by fitting the first few points of the segment into a line and calculating its slope. The outgoing angle is estimated in a similar way by fitting the last points of the segment into a line. The angles are defined such that they are in a range of +or−180°.

[0043] For each segment contour, the algorithm examines all the starting and ending points that are located in its neighborhood areas. If there is only one neighbor, the algorithm does not need to check the smoothness of the changing of the angles. The algorithm simply connects the points together. If there are multiple neighbors, then the algorithm chooses the one neighbor that makes the smoothest transition. This is illustrated in FIG. 8. In FIG. 8 starting and ending points a and b would thus be connected.

[0044] FIGS. 9A-9D illustrate several cases for connecting the two (2) segments when the smoothness criterion is met. We refer to the left segment as segment 1 and the right segment to segment 2 in the following description. The dots appearing on the segments represent the starting points, The property of smoothness may best be defined as follows:

[0045] (a) Smoothness is defined as the difference of the outgoing angle of segment 1 and the incoming angle of segment 2. If the smoothness condition is satisfied, append segment 2 to segment 1.

[0046] (b) Smoothness is defined as the difference of the outgoing angle of segment 1 and the reverse of the outgoing angle of segment 2. If the smoothness condition is satisfied, reverse segment 2 and then append to segment 1.

[0047] (c) Smoothness is defined as the difference of the reverse of the incoming angle of segment 1 and the incoming angle of segment 2. If the smoothness condition is satisfied, reverse segment 1, then append segment 2 to segment 1.

[0048] (d) Smoothness is defined as the difference of the incoming angle of segment 1 and the outgoing angle of segment 2. If the smoothness condition is satisfied, append segment 1 to segment 2.

[0049] Based on these criteria, the algorithm reconnects the contour segments that are split at the feature points. FIG. 10 shows the results after reconnection, in which process the segmented contours are formed into two (2) different objects, elliptical object 90 and rectangular object 92.

[0050] Referring once again to FIG. 4, using the circles reconstructed at step 262, the user-drawn circles are identified at step 264 through a series of tests. The first test is based on the size of the contour as well as the area the contour covers. If the length of the contour exceeds a predetermined threshold and the bounding box of the contour covers a predetermined area, the algorithm considers the contour to be a user-drawn circle.

[0051] However, in order to discriminate between user-drawn circles and machine-printed frames, such as rectangular frames, machine-printed circles or tables, the smoothness of the connected contour is examined. One way to measure smoothness is to calculate the average curvature along the connected contour. If smoothness exceeds a predetermined threshold, the contour is considered to be machine-printed. Smoothness scan be expressed as:

[0052] if {overscore (C)}≧T_curvature, machine generated

[0053] if {overscore (C)}<T_curvature, user drawn

[0054] T_curvature, threshold

[0055] $\stackrel{\_}{C}=\sum _{i}C\left(i\right),C\left(i\right)\text{is the curvature value along the curve}$

[0056] Because the algorithm reconstructs circled regions from the calculated feature points, it is able to identify user-drawn circles even if they contain small gaps or breaks. If desired, the user-drawn circle candidates can be further evaluated to determine if any gaps are sufficiently large to warrant rejection as user-drawn circles. The analysis (depicted at step 266) involves assessing the distant between the starting point and ending point of a contour. Distance can be assessed in a variety of different ways.

[0057] One technique for assessing distance is to determine whether one end point is within a predetermined radial distance from the other end point. See FIG. 11A. We refer to this as a circular distance function. Another technique is to define a square bounding box of predetermined size around one end point and to determine whether the other end point is within that bounding box. See FIG. 11B. We refer to this as the square distance function. A third technique is to define a square bounding box of predetermined size around one end point and then to rotate the bounding box around that end point to determine if at any rotational orientation the second end point falls within the bounding box. This will occur, if at all, when one corner of the bounding box lies on a line between the two end points. See FIG. 11C. We call this the Manhattan distance function.

[0058] If the contour fails to pass any of the above tests, then it is considered to be an open arc, as opposed to a user-drawn circle. Illustrations of accepted circles are shown in FIGS. 12A-12C. Rejected objects are shown in FIGS. 12D-12G. Once the user-drawn circle is identified as described above, the bounding box around its contour is used to delimit the region that will be extracted for subsequent optical character recognition analysis. This is illustrated at step 268. The image inside the bounding box of the contour is extracted and optical character recognition may be optionally performed on the extracted image.

[0059] As illustrated in FIG. 6, a user-drawn circle has two (2) edges that thus causes two (2) sets of contours to be generated, one inside the other. The algorithm uses the larger of the two (2) bounding boxes for region extraction.

[0060] In a document imaging system, the extracted circled region can be displayed in a variety of formats. One way is to output the circled regions as sub-images. Another is to output the entire page, with the user-circled regions highlighted in color. A further option is to have the inside of the circle highlighted. To do this, the gaps on the contour must be closed. Closure may be handled in several ways. Two (2) are illustrated in FIGS. 13A and 13B. In 13A, closure is effected by connecting the end points directly. In FIG. 13B closure is effected by having one end point connect with the point on the curve that has the minimum distance between the end point and the curve.

[0061] In addition to extracting the user-drawn region for display, the system can also process the extracted region using optical character recognition techniques to construct index labels for document storage and retrieval purposes.

[0062] While the invention has been described in its presently preferred embodiments, it will be understood that certain modifications can be made to these embodiments without departing from the spirit of the invention as set forth in the appended claims.