Formless forms and paper web using a reference-based mark extraction technique

• US 5,692,073 A
• Filed: 07/30/1996
• Issued: 11/25/1997
• Est. Priority Date: 05/03/1996
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Cass, Todd A.
• Primary Examiner(s): Rogers, Scott A.
• Application Number:
  US08/688,704
• Time in Patent Office: 483 Days
• Field of Search: 382/219, 382/221, 382/222, 382/317, 382/218, 382/294, 382/283, 382/282, 382/217, 358/468, 358/453, 358/448, 235/375, 397/766, 397/773, 397/804, 397/793
• US Class Current: 382/219
• CPC Class Codes: G06F 40/174 Form filling; Merging
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1444 Selective acquisition, locating or processing of specific regions, e.g. highlighted text, fiducial marks or predetermined fields

Abstract

A processor is provided with first and second document images. The first image represents an instance of a reference document to which instance a mark has been added. The second image is selected from among a collection of document images and represents the reference document without the mark. The processor automatically extracts from the first document image a set of pixels representing the mark. This is done by performing a reference-based mark extraction technique in which the second document image serves as a reference image and in which substantially the entirety of the first document image is compared with substantially the entirety of the second document image. Also, the processor is provided with information about a set of active elements of the reference document. The reference document has at least one such active element and each active element is associated with at least one action. The processor interprets the extracted set of pixels representing the mark by determining whether the mark indicates any of the active elements of the reference document. If the mark indicates an active element, the processor facilitates the action with which the indicated active element is associated.

Claims

1. A method comprising the steps of:

providing a processor with a first document image comprising digital image data including a first plurality of pixels, the first document image representing an instance of a reference document to which instance a mark has been added, the reference document having a plurality of elements;

providing the processor with a second document image comprising digital image data including a second plurality of pixels, the second document image being selected from among a plurality of document images and representing the reference document without the mark;

with the processor, automatically extracting from the first document image a set of pixels representing the mark by performing a reference-based mark extraction technique wherein the second document image serves as a reference image and wherein substantially the entirety of the first document image is compared with substantially the entirety of the second document image;

providing the processor with information about a set of active elements of the reference document, each active element being one element among the plurality of elements of the reference document, the reference document having at least one such active element, each active element being associated with at least one action;

interpreting with the processor the extracted set of pixels representing the mark by determining whether any of the active elements of the reference document is indicated by the mark; and

if an active element is indicated by the mark, facilitating with the processor the action with which such active element is associated.

2. The method of claim 1 wherein, in the extracting step, the reference-based mark extraction technique includes a step of:

computing a robust difference of the first and second images via an image processing operation carded out without recognition by the processor of any symbolic content in either of the first or second document images.

3. The method of claim 2 wherein the step of computing a robust difference comprises:

determining a collection of pixels common to both the first and second images by matching pixels of the first image with pixels of the second image according to a matching criterion; and

eliminating as between the first and second images the pixels of the collection thus determined, thereby determining a set of discrepancy pixels including a set of pixels representing the mark.

4. The method of claim 1 wherein, in the extracting step, the reference-based mark extraction technique includes the steps of:

registering the first and second images with one another; and

computing a robust difference of the registered first and second images.

5. The method of claim 4 wherein the step of computing a robust difference comprises the steps of:

finding common elements as between the images; and

eliminating the found common elements to locate a discrepancy between the first and second document images.

6. The method of claim 4 wherein the steps of registering the first and second images and computing a robust difference of the registered images are performed piecewise on local subregions of the document images.

7. The method of claim 1 wherein the interpreting step comprises determining whether the mark is proximate to any active element.

8. A method comprising the steps of:

providing a processor with a first document image comprising digital image data including a first plurality of pixels, the first document image representing an instance of a reference document to which instance a mark has been added, the reference document having a plurality of elements;

generating an image-based index from the first document image without recognition of any symbolic content of the first document image;

selecting a second document image from among a plurality of document images according to the generated index, the second document image comprising digital image data including a second plurality of pixels, the second document image representing the reference document without the mark;

providing the processor with the second document image;

with the processor, automatically extracting from the first document image a set of pixels representing the mark by performing a reference-based mark extraction technique wherein the second document image serves as a reference image and wherein substantially the entirety of the first document image is compared with substantially the entirety of the second document image by computing a robust difference of the first and second images;

providing the processor with information about a set of active elements of the reference document, each active element being one element among the plurality of elements of the reference document, the reference document having at least one such active element, each active element being associated with at least one action;

interpreting with the processor the extracted set of pixels representing the mark by determining whether any of the active elements of the reference document is indicated by the mark; and

if an active element is indicated by the mark, facilitating with the processor the action with which such active element is associated.

9. The method of claim 8 wherein the step of computing a robust difference comprises:

determining a collection of pixels common to both the first and second images by matching pixels of the first image with pixels of the second image according to a matching criterion; and

eliminating as between the first and second images the pixels of the collection thus determined, thereby determining a set of discrepancy pixels including a set of pixels representing the mark.

10. A method comprising the steps of:

converting a first document instance into a first document image comprising digital image data including a first plurality of pixels, the first document instance being an instance of a reference document to which instance a mark has been added, the reference document having a plurality of elements, the reference document being a document other than a form;

converting a second document instance into a second document image comprising digital image data including a second plurality of pixels, the second document instance being an instance of the reference document without the mark;

annotating the second document image with a set of annotations comprising at least one annotation, each annotation establishing an association between an element of the reference document and at least one action, each element for which such an association is thus established being termed an "active element";

providing the processor with the first and second document images and the set of annotations;

with the processor, automatically extracting from the first document image a set of pixels representing the mark by performing a reference-based mark extraction technique wherein the second document image serves as a reference image;

interpreting with the processor the extracted set of pixels representing the mark by determining, with reference to the set of annotations, whether any of the active elements of the reference document is indicated by the mark; and

if an active element is indicated by the mark, facilitating with the processor the action with which such active element is associated.

11. The method of claim 10 wherein the step of converting the second document instance comprises scanning a hardcopy instance of the second document with a digital scanning device.

12. The method of claim 10 wherein the step of converting the second document instance comprises rendering a symbolic description of the second document into a bitmap form.

13. The method of claim 10 wherein:

the step of converting the second document instance comprises scanning a collection of hardcopy document instances including the second document instance with at least one digital scanning device, thereby producing a collection of scanned document instances, and storing the scanned document instances in a database accessible to the processor; and

the providing step comprises retrieving the second document image from the database by generating an image-based index from the first document image without recognition of any symbolic content of the first document image and selecting a second document image from among the scanned document images in the database.

14. The method of claim 13 wherein:

the annotating step is performed prior to the providing step and comprises storing the set of annotations and wherein the providing step comprises contemporaneously retrieving the second document image and the set of annotations.

15. A method comprising the steps of:

providing a processor with a first document image comprising digital image data including a first plurality of pixels, the first document image representing an instance of a reference document to which instance a mark has been added, the reference document including a plurality of elements, the mark indicating a selection of a preferred element of the reference document, the preferred element whose selection is thus indicated being an element other than a form element;

providing the processor with a second document image comprising digital image data including a second plurality of pixels, the second document image being selected from among a plurality of document images and representing the reference document without the mark;

with the processor, automatically extracting from the first document image a set of pixels representing the mark by performing a reference-based mark extraction technique wherein the second document image serves as a reference image, the technique comprising at least one image-domain operation for comparing the first and second document images, the image-domain operation being an image processing operation carried out without recognition by the processor of any symbolic content in either of the first or second document images;

providing the processor with information about a set of active elements of the reference document, each active element being one element among the plurality of elements of the reference document, the reference document having at least one such active element, each active element being associated with at least one action;

interpreting with the processor the extracted set of pixels representing the mark, thereby determining whether the preferred element whose selection is indicated by the mark is an active element of the reference document; and

if the preferred element is thus determined to be an active element, facilitating with the processor the action with which the preferred element is associated.

16. The method of claim 15 in which the first providing step comprises providing the processor with a first document image wherein the selected element is an element other than a form element selected from the group consisting of:

a substantially blank region having a perimeter delimited at least in part by a perimetral boundary and within which blank region a substantial portion of the mark is disposed;

a substantially blank region substantially underscored by a baseline proximate to which baseline a substantial portion of the mark is disposed;

a textual word located in an array of textual words set apart from any surrounding text, the mark being proximate to the textual word; and

a graphical symbol located in an array of graphical symbols set apart from any nearby nonblank elements, the mark being proximate to the graphical symbol.

17. A method comprising the steps of:

scanning a hardcopy instance of a first document with a digital scanning device to produce a first document image comprising digital image data including a first plurality of pixels, the hardcopy instance being an instance of a reference document to which instance a mark has been added, the reference document having a plurality of elements, the reference document being a hypertext document having an associated set of active elements, each active element being associated with at least one action;

providing a processor with the first document image;

providing the processor with a second document image comprising digital image data including a second plurality of pixels, the second document image being selected from among a plurality of document images and representing the reference document without the mark;

providing the processor with the set of active elements for the reference document;

with the processor, automatically extracting from the first document image a set of pixels representing the mark by performing a reference-based mark extraction technique wherein the second document image serves as a reference image and wherein substantially the entirety of the first document image is compared with substantially the entirety of the second document image;

interpreting with the processor the extracted set of pixels representing the mark by determining whether any of the active elements of the reference document is indicated by the mark; and

if an active element is indicated by the mark, facilitating with the processor the action with which such active element is associated.

18. The method of claim 17 wherein:

the step of providing the processor with the second document image comprises rendering a representation of the second document, the representation being expressed in a language for expressing hypertext documents; and

the step of providing the processor with the set of active elements comprises obtaining information about the set of active elements from said representation of the second document.

19. The method of claim 17 wherein:

at least one action with which each active element is associated is an action of following a specified hypertext link; and

the facilitating step, if performed, comprises initiating a traversal of the specified hypertext link.

20. An article of manufacture comprising an information storage medium wherein is stored information comprising a software program for facilitating the steps of:

providing a processor with a first document image comprising digital image data including a first plurality of pixels, the first document image representing an instance of a reference document to which instance a mark has been added, the reference document having a plurality of elements;

providing the processor with a second document image comprising digital image data including a second plurality of pixels, the second document image being selected from among a plurality of document images and representing the reference document without the mark;

with the processor, automatically extracting from the first document image a set of pixels representing the mark by performing a reference-based mark extraction technique wherein the second document image serves as a reference image and wherein substantially the entirety of the first document image is compared with substantially the entirety of the second document image;

providing the processor with information about a set of active elements of the reference document, each active element being one element among the plurality of elements of the reference document, the reference document having at least one such active element, each active element being associated with at least one action;

interpreting with the processor the extracted set of pixels representing the mark by determining whether any of the active elements of the reference document is indicated by the mark; and

if an active element is indicated by the mark, facilitating with the processor the action with which such active element is associated.