Method for compressing and decompressing forms by means of very large symbol matching

• US 5,182,656 A
• Filed: 07/30/1990
• Issued: 01/26/1993
• Est. Priority Date: 08/04/1989
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Walach, Eugeniusz, Karnin, Ehud D., Chevion, Dan S.
• Primary Examiner(s): Coles, Sr., Edward L.
• Assistant Examiner(s): Grant, II, Jerome
• Application Number:
  US07/559,813
• Time in Patent Office: 911 Days
• Field of Search: 358/403, 358/429, 358/434, 358/444, 358/450, 358/452, 358/455, 358/462, 358/464, 358/465, 358/401, 358/471, 358/473, 358/426, 358/431, 358/467
• US Class Current: 358/452
• CPC Class Codes: H04N 1/4115 involving the recognition of specific patterns, e.g. by symbol matching

Abstract

This method relates to the compression of information contained in filled-in forms (O) by separate handling of the corresponding empty forms (CP) and of the information written into them (VP). Samples of the empty forms are pre-scanned, the data obtained digitized and stored in a computer memory to create a forms library. The original, filled-in form (O) to be compressed is then scanned, the data obtained digitized and the retrieved representation of the empty form (CP) is then subtracted, the difference being the digital representation of the filled-in information (VP), which may now be compressed by conventional methods or, preferably, by an adaptive compression scheme using at least two compression ratios depending on the relative content of black pixels in the data to be compressed.

Claims

1. Method for compressing, for storing or transmitting, information contained in filled-in forms by separate handling of the corresponding empty forms and of the information written into them, characterized by the steps of:

pre-scanning the empty forms, digitizing data obtained, and storing digitized representations relating to each of the empty forms in a computer memory to create a form library,

scanning the original, filled-in form to be compressed, digitizing data obtained from the filled in form,

identifying a particular one of said empty forms in said forms library and retrieving the digital representation thereof,

subtracting said retrieved digital representation of the empty form from said digital representation of the scanned filled-in form, to generate a difference which is a digital representation of the filled-in information, and

compressing the digital representation of the filled-in information.

2. Method in accordance with claim 1, characterized in that scanning parameters, such as brightness and threshold level, are determined separately for the empty form and for said original filled-in form.

3. Method in accordance with claim 1, characterized in that prior to the subtraction step, registration information relating to relative position of the filled-in information with respect to the completed form determined and registration of said original filled-in form with said empty form is performed.

4. Method in accordance with claim 1, characterized in that said subtraction step involves removing, from the original filled-in form, all black pixels which belong to said corresponding empty form or which are located close to black pixels belonging to said corresponding empty form, and retaining all black pixels which belong to said filled-in information.

5. Method in accordance with claim 1, characterized in that said compression step involves all application of at least two different compression ratios depending on a content, in the data to be compressed, of portions containing a comparatively large number of black pixels and portions containing a comparatively small number of black pixels, with the data to be compressed being first subjected to a pre-filtering step to determined a relative compressibility thereof.

13. Method in accordance with any one of the preceding claims, characterized in that all steps are performed with a binary representations being maintained in a byte format without unpacking any of the bytes to their component pixels.

6. Method for compressing, for storing or transmitting, information contained in filled-in forms by separate handling of empty forms and of information written into them, characterized by the steps of:

pre-scanning the empty forms, digitalizing data obtained by pre-scanning the empty forms, and storing the digitized representations relating to each of the empty forms in a computer memory to create a forms library;

scanning an original, filled-in form to be compressed, digitizing data obtained from scanning the filled-in form, identifying a particular one of said empty forms in said forms library and retrieving a digital representation thereof;

using dimensionality reduction to determine registration information relating to relative position of the filled-in information with respect to the competed form;

registering said original filled-in form with said empty form;

subtracting said retrieved representation of the empty form from said digital representation of the scanned filled-in form, a difference being the digital representation of the filled-in information, and

compressing the digital representation of the filled-in information.

7. Method for compressing, for storing or transmitting, and reproducing information contained in filled-in forms by separate handling of corresponding empty forms and of information written into them, characterized by the steps of:

(a) storing digitized representations of empty forms in a computer memory to create a forms library;

(b) scanning an original, filed in form to be compressed;

(c) digitizing data obtained from said filled-in form;

(d) identifying the particular one of said empty forms in said forms library and retrieving the digital representation thereof;

(e) subtracting said retrieved digital representation of the empty form from said digital representation of the scanned filled-in form, to generate a difference which is a digital representation of the filled-in information, and

(f) compressing the digital representation of the filled-in information.

8. The method set forth in claim 7 further including the steps of:

(h) correlating the digital representation of the filled-in information (VP) and the particular one of said empty form to reconstruct the original completed form.

9. Method for compressing, for storing, or transmitting, information contained in filled-in forms by separate handling of corresponding empty forms and of information written into them, characterized by the steps of:

pre-scanning the empty forms, digitizing data obtained from pre-scanning the empty forms, and storing a digitized representations relating to each of the empty forms in a computer memory to create a forms library;

scanning an original, filled-in form to be compressed, digitizing data obtained from scanning the filled in form;

identifying a particular one of said empty forms in said forms library and retrieving the digital representation thereof;

determining registration information relating to a relative position of the filled-in information with respect to a completed form;

partitioning the scanned filled-in form into small segments;

estimating, for each segment, optimum shifts to be performed in x and y directions;

placing each segment of said original filled-in form at an appropriate area of an output image array using the shift information previously established, so that a complete, shifted image is obtained when placements for all segments have been completed;

subtracting said retrieved representation of the empty form from said digital representation of the scanned filled-in form, a difference being the digital representation of the filled information, and

compressing the digital representation of the filed in information.

10. Method in accordance with claim 9, characterized in that said original filed-in form is partitioned in a proportion corresponding at least approximately to 16 segments per page of 210×

297 mm size.

11. Method in accordance with claim 9, characterized in that said partitioning is performed such that the segments overlap at their margins by a distance corresponding to about two pixels.

12. Method in accordance with claim 9, characterized in that said estimated optimum shifts for each pair of neighbouring segments are checked for consistency by assuring that their difference does not exceed a predetermined threshold and, if it does, automatically calling for operator intervention.