Automatic forms identification systems and methods
AssigneeLexmark International, Inc.
InventorsJose Eduardo Bastos dos Santos, Brian G. Anderson, David E. Kelley
Life of this patent
Estimating the term…
Abstract
Systems and methods automatically generate a model of a form or other document and identify the form or other document. In one aspect, a system and method normalize an image of a document and identify the relative positions of vertical and horizontal lines in the normalized image. The relative positions of vertical and horizontal lines of the normalized image are the model of the document image. The model may be stored in a record, such as an array. The system and method compare the relative positions of vertical and horizontal lines of the model to the relative positions of vertical and horizontal lines of other models to identify a matching model.
Claims34
A computer-readable storage medium encoded with a system for identifying a form from model data identifying relative positions of vertical and horizontal lines for a plurality of form models having;
- dimensions normalized for a selected scale, the system comprising a plurality of modules executable by at least one processor, the modules comprising:
- a preprocessing system to binarize, deskew, denoise, and despeckle an electronic form image of at least one document;
- a layout extractor to extract a frame of the form image by performing a morphological opening by reconstruction on the form image, the opening using a zero degree structuring element and a ninety degree structuring element, each structuring element having a size based on an average text size of average text in the form image;
- a model image generator to align, vectorize, and morphologically close the frame of the form image using the zero degree structuring element and the ninety degree structuring element to generate a model image;
- a model representation system to normalize dimensions of the model image for the selected scale, to generate a vertical projection profile of the normalized model image, to determine relative positions of vertical lines of the normalized model image from the vertical projection profile, to generate a horizontal projection profile of the normalized model image, to determine relative positions of horizontal lines of the normalized model image from the horizontal projection profile, and to generate an array with the relative positions of vertical lines and the relative positions of horizontal lines;
- and
- a matching system to:
- for each of the plurality of form models, align the relative positions of vertical lines of the normalized model image with closest corresponding relative positions of vertical lines of the form model;
- for each of the plurality of form models, align the relative positions of horizontal lines of the normalized model image with closest corresponding relative positions of horizontal lines of the form model;
- for each of the plurality of form models, compare the aligned relative positions of vertical lines of the normalized model image to the corresponding relative positions of vertical lines of the form model to determine a number of vertical line gaps between the model image and the form model, each vertical line gaps number indicating a location where at least one vertical line of the normalized model image does not have a corresponding vertical line in the form model;
- for each of the plurality of form models, compare the aligned relative positions of horizontal lines of the normalized model image to the corresponding relative positions of horizontal lines of the form model to determine a number of horizontal line gaps between the model image and the form model, each horizontal line gaps number indicating, a location where at least one horizontal line of the normalized model image does not have a corresponding horizontal line in the form model;
- for each of the plurality of form models, determine a first Euclidean noun between the aligned relative positions of vertical lines of the normalized model image and the corresponding relative positions of vertical lines of the form model;
- for each of the plurality of form models, determine a second Euclidean norm between the aligned relative positions of horizontal lines of the normalized model image and the corresponding relative positions of horizontal lines of the form model;
- determine a first smallest distance from the first Euclidean norms determine a second smallest distance from the second Euclidean norms;
- determine a smallest vertical line gaps number from the vertical line gaps numbers;
- determine a smallest horizontal line gaps number from the horizontal line gaps numbers;
- and
- select a particular form model from the plurality of form models, the particular form model having the first smallest distance, the second smallest distance, the smallest vertical line gaps number, and the smallest horizontal line gaps number.
A computer-readable storage medium encoded with a system for identifying a form from a plurality of form models identifying relative positions of vertical and horizontal lines for a corresponding normalized form image normalized for a same selected scale, the system comprising a plurality of modules executable by at least one processor, the modules comprising:
- a layout extractor to extract a frame of an electronic form image;
- a model image generator to align and vectorize the frame to generate a model image;
- a model representation system to normalize the it image for the same selected scale, to determine relative positions of vertical and horizontal lines of the normalized model image, and to generate a model with the relative positions of vertical lines of the normalized model image and the relative positions of horizontal lines of the normalized model image;
- and
- a matching system to:
- align the relative positions of vertical lines of the model with relative positions of vertical lines of at least one form model;
- align the relative positions of horizontal lines of the model with relative positions of horizontal lines of the at least one form model;
- determine a first Euclidean norm between the aligned relative positions of vertical lines of the model and the relative positions of vertical lines of the at least one form model;
- determine a second Euclidean norm between the aligned relative, positions of horizontal lines of the model and the relative positions of horizontal lines of the at least one form model;
- and
- determine whether the at least one form model matches the model based on the first Euclidean norm and the second Euclidean norm.
A computer-readable storage medium encoded with a system for identifying a plurality of form models comprising vertical position tags identifying relative positions of vertical lines for a corresponding normalized form image normalized for a same selected scale and horizontal position tags identifying relative positions of horizontal lines for the corresponding normalized form image normalized for the same selected scale, the system comprising a plurality of modules executable by at least one processor, the modules comprising:
- a layout extractor to extract a frame of another form image;
- a model image generator to align and vectorize the frame to generate a model image;
- a model representation system to normalize the model image for the same selected scale, to determine first relative vertical positions of vertical lines of the normalized model image using projection profiling, to determine first relative horizontal positions of horizontal lines of the normalized model image using projection profiling, and to generate a model with first vertical position tags identifying the first relative vertical positions of vertical lines of the normalized model image and first horizontal position tags identifying the first relative horizontal positions of horizontal lines of the normalized model image;
- and
- a matching system to:
- align the first vertical position tags with second vertical position tags of at least one form model;
- align the first horizontal position tags with second horizontal position tags of the at least one form model;
- calculate a first Euclidean norm between the aligned first and second vertical position tags;
- calculate a second Euclidean norm between the aligned first and second horizontal position tags;
- and
- select the at least one form model as a matching model when the first Euclidean norm is smaller than other first Euclidean norms calculated between the first vertical position tags and other vertical position tags of other form models and the second Euclidean norm is smaller than other second Euclidean norms calculated between the first horizontal position tags and other horizontal position tags of the other form models.
A computer-readable storage medium encoded with a system for identifying a plurality of form models comprising vertical position tags identifying relative positions of vertical lines for a corresponding normalized form image normalized for a same selected scale and horizontal position tags identifying relative positions of horizontal lines for the corresponding normalized form image normalized for the same selected scale, the system comprising a plurality of modules executable by at least one processor, the modules comprising:
- a layout extractor to extract a frame of another form image;
- a model image generator to align and vectorize the frame to generate a model image;
- a model representation system to normalize the model image for the same selected scale, to determine first relative vertical positions of vertical lines of the normalized model image using, projection profiling, to determine first relative horizontal positions of horizontal lines of the normalized model image using projection profiling, and to generate a model with first vertical position tags identifying the first relative vertical positions of vertical lines of the normalized model image and first horizontal position tags identifying the first relative horizontal positions of horizontal lines of the normalized model image;
- and
- a matching system to:
- align the first vertical position tags with second vertical position tags of at least one form model;
- align the first horizontal position tags with second horizontal position tags of the at least one form model;
- calculate a Euclidean norm between at least one member of a group consisting of:
- the aligned first and second vertical position tags;
- and
- the aligned first and second horizontal position tags;
- and
- select the at least one form model as a matching model when the Euclidean norm is smaller than other Euclidean norms calculated between at least one second member of a second group consisting of:
- the first vertical position tags and other vertical position tags of other form models;
- and
- the first horizontal position tags and horizontal position tags of the other form models.
A computer-readable storage medium encoded with a system for identifying a plurality of form models comprising vertical position tags identifying relative positions of vertical lines for a corresponding normalized form image normalized for a same selected scale and horizontal position tags identifying relative positions of horizontal lines for the corresponding normalized form image normalized for the same selected scale, the system comprising a plurality of modules executable by at least one processor, the modules comprising:
- a layout extractor to extract a frame of another form image;
- a model image generator to align and vectorize the frame to generate a model image;
- a model representation system to normalize the model image for the same selected scale, to determine first relative vertical positions of vertical lines of the normalized model image using projection profiling, to determine first relative horizontal positions of horizontal lines of the normalized model image using projection profiling, and to generate a model with first vertical position tags identifying the first relative vertical positions as a first vector and first horizontal position tags identifying the first relative horizontal positions as a second vector;
- and
- a matching system to compare the first vector to other first vectors, each other first vector having other first vertical position tags for a corresponding form model and align the first vertical position tags of the first vector with other first vertical position tags of the other first vectors, to compare the second vector to other second vectors, each other second vector having other second horizontal position tags for the corresponding form model and align the first horizontal position tags of the second vector with other second horizontal position tags of the other second vectors, and select a matching form model whose other first vector and other second vector most closely match the first vector and second vector,
- wherein the matching system compares the first vector to the other first vectors by calculating first Euclidean norms between the first vector and the other first vectors;
- compares the second vector to the other second vectors by calculating second Euclidean norms between the second vector and the other second vectors;
- and
- selects the matching form model whose other first vector and other second vector most closely match the first vector and second vector by selecting the matching form model having a smallest first Euclidean norm from the first Euclidean norms and a smallest second Euclidean norm from the second Euclidean norms.
A computer-readable storage medium encoded with a system for identifying a plurality of form models identifying, relative positions of vertical and horizontal lines for a corresponding normalized form image normalized for a same selected scale, the system comprising a plurality of modules executable by at least one processor, the modules comprising:
- a layout extractor to extract a frame of another form image;
- a model image generator to align and vectorize the frame to generate a model image;
- a model representation system to normalize the model image for the same selected scale to determine other relative positions of other vertical and horizontal lines of the normalized model image, and to generate another model identifying the other relative positions of the other vertical and horizontal lines;
- and
- a matching system to align the other relative positions of the other vertical lines of the another model to relative positions of vertical lines of the form models and align the other relative positions of the other horizontal lines of the another model to relative positions of horizontal lines of the form models to identity a matching model,
- wherein the matching system compares the first vector to the other first vectors by calculating first Euclidean norms between the first vector and the other first vectors;
- compares the second vector to the other second vectors by calculating second Euclidean norms between the second vector and the other second vectors;
- and
- selects the matching form model whose other first vector and other second vector most closely match the first vector and second vector by selecting the matching form model having a smallest first Euclidean norm from the first Euclidean norms and a smallest second Euclidean norm from the second Euclidean norms.
Dependencies are inferred from the claim text.