Polygon-based method for automatic extraction of selected text in a digitized document

Claim 1

A method of extracting marked text regions defined by hand drawn closed curves on a paper document, comprising the steps of: raster scanning said document; generating as the document is being scanned, a bit map representation of the document such that whenever a transition is detected, contour vectorization is used including contour pixel tracing and piecewise linear approximation to convert the bit map representation into a collection of closed polygons formed by a series of vectors; separating the collection of polygons into inner and outer groups of contours, and the separation criteria for said groups is made by the summing the cross products given by the equation: ##EQU4## sorting all of the inner and outer contours according to location in their respective groups; determining segmentation points by substrating the lower coordinate (LY i ) from the upper coordinate (UY i+1 ) and obtaining a positive value in each group of sorted contours such that overlapping contours are geometrically related to one another; establishing polygon blocks for all polygons having a geometrical relationship in the horizontal direction; use contour linking to examine the geometrical relationships of the coordinates of both the outer and inner contours of polygons to determine if they are geometrically overlapping; scanning the list of linked polygons to locate external inner contours of polygons; and extracting the inner contours of polygons formed by said hand drawn closed curves from said bit map representative document using the angular sum of the centerpoint of an outer countour.

Claim 2

A method of extracting marked text regions defined by hand drawn closed curves on a paper document, comprising the steps of: raster scanning said document; generating as the document is being scanned, a bit map representation of the document such that whenever a transition is detected, contour vectorization is used including contour pixel tracing and piecewise linear approximation to convert the bit map representation into a collection of closed polygons formed by a series of vectors; separating the collection of polygons into inner and outer groups of contours, and the separation criteria for said groups is made by the summing the cross products given by the equation: ##EQU4## sorting all of the inner and outer contours according to location in their respective groups; determining segmentation points by substrating the lower coordinate (LY i ) from the upper coordinate (UY i+1 ) and obtaining a positive value in each group of sorted contours such that overlapping contours are geometrically related to one another; establishing polygon blocks for all polygons having a geometrical relationship in the horizontal direction; use contour linking to examine the geometrical relationships of the coordinates of both the outer and inner contours of polygons to determine if they are geometrically overlapping; scanning the list of linked polygons to locate external inner contours of polygons; and extracting the inner contours of polygons formed by said hand drawn closed curves from said bit map representative document using the angular sum of the centerpoint of an outer countour.

Claim 5

A method of using contour vectorization to extract printed text regions identified by hand drawn closed curves on a paper document, comprising the steps of: scanning said paper document and generating a bit map representation of the document; converting said bit map representation, using contour pixel extraction and linear approximation, into a collection of polygons; calculate the coordinates of the end points of a diagonal of a rectangle that encompasses each polygon; classify the collection of polygons into two categories based on the feature R given by equation: ##EQU5## wherein the first category has a negative R indicating an inner contour of a polygon and the second category has a positive R indicating an outer contour of a polygon; sort all of the inner and outer polygon contours according to location by determining the segmentation points by substracting the lower coordinates (LY i ) from the upper coordinate (UY i+1 ) and obtain a positive value; calculate a value A given by equation: A=Σθ.sub.i such that when A=0 the contour is outside a hand drawn inner contour of the polygon and when A=2π identifies the hand drawn inner contour of a polygon and the region inside such polygon being the detected printed text.

Claim 6

A method of using contour vectorization to extract printed text regions identified by hand drawn closed curves on a paper document, comprising the steps of: scanning said paper document and generating a bit map representation of the document; converting said bit map representation, using contour pixel extraction and linear approximation, into a collection of polygons; calculate the coordinates of the end points of a diagonal of a rectangle that encompasses each polygon; classify the collection of polygons into two categories based on the feature R given by equation: ##EQU5## wherein the first category has a negative R indicating an inner contour of a polygon and the second category has a positive R indicating an outer contour of a polygon; sort all of the inner and outer polygon contours according to location by determining the segmentation points by substracting the lower coordinates (LY i ) from the upper coordinate (UY i+1 ) and obtain a positive value; calculate a value A given by equation: A=Σθ.sub.i such that when A=0 the contour is outside a hand drawn inner contour of the polygon and when A=2π identifies the hand drawn inner contour of a polygon and the region inside such polygon being the detected printed text.