SCANNABLE FORM, SYSTEM AND METHOD FOR IMAGE ALIGNMENT AND IDENTIFICATION

• US 20050201639A1
• Filed: 03/11/2005
• Published: 09/15/2005
• Est. Priority Date: 03/12/2004
• Status: Abandoned Application

• Current Assignee: Hare & Associates
• Original Assignee: Hare & Associates
• Inventors: WU, Xaiojing
• Application Number:
  US10/906,914
• Publication Number:
  US 20050201639A1
• Time in Patent Office: Days
• US Class Current: 382/294
• CPC Class Codes: G06V 10/245 by locating a pattern; Special marks for positioning
• CPC Class Codes: G06V 30/40 Document-oriented image-based pattern recognition

Abstract

A scannable form, and a method and system of use which incorporates digitally encoded symbols which have identifiable centers that act as control points to permit a digital image to be aligned with a template containing the same control points. The digital encoding permits identification of the type of form and the spatial arrangement of the symbols permits alignment of the form with the template. Preferably, the digital symbols are geometrically symmetrical and the identifiable centers are centroids. Recognition of any three centroids is sufficient to allow the system to calculate transformation parameters to realign the image. Due to the geometrical symmetry, error correction is possible if any of the symbols are incorrectly identified.

Claims

1. A scannable form having at least one answer response area comprising:

a generally rectangular sheet; and

at least three digitally encoded symbols, each encoded symbol having an identifiable center for forming a control point, the symbols being printed on the sheet in a spatial arrangement relative to the at least one answer response area,

wherein when the form is scanned as an image, the control points in the image are compared to pre-determined control points in a known template for determining an alignment of the image with the known template.

2. The scannable form as described in claim 1 wherein recognition of three or more of the identifiable centers of the at least three digitally encoded symbols triggers calculation of transformation parameters for alignment of the image with the known template.

3. The scannable form as described in claim 1 wherein the symbols are geometrically symmetrical and have a fixed centroid for forming the control point.

4. The scannable form as described in claim 1 wherein the at least three digitally encoded symbols are a first set of the plurality of digitally encoded symbols.

5. The scannable form as described in claim 4 further comprising at least one additional redundant set of symbols.

6. The scannable form as described in claim 5 wherein the cumulative number of symbols in the first set and the at least one additional redundant set is three symbols.

7. The scannable form as described in claim 6 wherein the at least one redundant set of symbols comprises substantially identical symbols to the first set of symbols and the substantially identical symbols are arranged in pairs, each symbol of the pair being positioned at substantially the same horizontal position on the sheet.

8. A method for image alignment and recognition of a scannable form comprising:

providing a plurality of digitally encoded symbols, each symbol encoding a unique number or character, and having an identifiable center for forming a control point;

positioning at least three of the plurality of digitally encoded symbols on the scannable form in a spatial arrangement;

generating a digital image of the scannable form including the spatial arrangement;

identifying a known template having pre-determined control points for comparison of the scannable form thereto; and

determining the spatial arrangement of the control points in the digital image of at least three of the at least three digitally encoded symbols for determining alignment of the digital image compared to pre-determined control points of the known template.

9. The method as described in claim 8 wherein the digitally encoded symbols are decoded to identify the known template for comparison thereto.

10. The method as described in claim 8 wherein the template is identified manually by a user for comparison thereto.

11. The method as described in claim 8 wherein the digitally encoded symbols are geometrically symmetrical and have a fixed centroid for forming the control point.

12. The method as described in claim 8 wherein the at least three digitally encoded symbols are a first set of the plurality of digitally encoded symbols.

13. The method as described in claim 12 further comprising at least one additional redundant set of symbols.

14. The method as described in claim 13 wherein the cumulative number of symbols in the first set and the at least one additional redundant set is three symbols.

15. The method as described in claim 13 wherein the at least one redundant set of symbols comprises substantially identical symbols to the first set of symbols and the substantially identical symbols are arranged in pairs, each symbol of the pair being positioned at substantially the same horizontal position on the sheet.

16. The method as described in claim 8 wherein each of the encoded symbols has a control point for recognition of the alignment of the digital image.

17. The method as described in claim 8 wherein recognition of three or more of the at least three digitally encoded symbols triggers calculation of transformation parameters for alignment of the digital imate with the known template.

18. The method as described in claim 8 wherein each symbol is a two-dimensional matrix having light and dark data modules, each module representing a data bit.

19. The method as described in claim 18 wherein the two-dimensional matrix is a 4×

4 matrix.

20. The method as described in claim 18 wherein the two-dimensional matrix is a 5×

5 matrix.

21. The method as described in claim 18 wherein each two-dimensional matrix is contained in a border having a line width substantially equivalent to a width of an individual module within the symbol.

22. The method as described in claim 8 wherein when at least a portion of a symbol encoding is erroneous and wherein the spatial arrangement comprises:

providing adjacent symbols, all adjacent symbols having a first fixed hamming distance and providing non-adjacent symbols, all on-adjacent symbols having a second hamming distance;

further comprising;

determining whether the at least a portion of the identified symbol is adjacent another symbol and should have the first fixed hamming distance or is not adjacent another symbol and should have the second fixed hamming distance; and

predicting the identity of the erroneously encoded symbol by selecting a symbol from the plurality of symbols as being the symbol having the first or second fixed hamming distance.

23. The method as described in claim 22 wherein when the sheets are recognized as a batch in a batch mode, further comprising:

predicting the identity of the erroneously encoded symbol by selecting a symbol from the symbols identified for neighbors in the batch having the least hamming distance.

24. The method as described in claim 23 further wherein a symbol having the fixed hamming distance is not found in the symbols identified for neighbours in the batch further comprising:

predicting the identity of the erroneously encoded symbol by selecting a symbol from the plurality of symbols as being the symbol having the least hamming distance.

25. The method as described in claim 15 wherein when at least one symbol of the first set of symbols or the redundant set of symbols is not recognized further comprising:

predicting the identity of the unrecognized symbol from the symbol of the pair being positioned at substantially the same horizontal position on the sheet.

26. A method for image alignment and recognition comprising:

providing a plurality of digitally encoded symbols, each symbol encoding a unique number or character, and being geometrically symmetrical and having a fixed centroid for forming a control point;

positioning at least three of the plurality of digitally encoded symbols on the scannable form in a spatial arrangement;

generating a digital image of the scannable form including the spatial arrangement;

identifying a known template having pre-determined control points for comparison of the scannable form thereto; and

determining the spatial arrangement of the centroids of at least three of the at least three digitally encoded symbols for determining alignment of the digital image compared to the known template.

27. The method as described in claim 26 wherein the at least three digitally encoded symbols are a first set of the plurality of digitally encoded symbols.

28. The method as described in claim 27 further comprising at least one additional redundant set of symbols.

29. The method as described in claim 28 wherein the cumulative number of symbols in the first set and the at least one additional redundant set is three symbols.

30. The method as described in claim 28 wherein the at least one redundant set of symbols comprises substantially identical symbols to the first set of symbols and the substantially identical symbols are arranged in pairs, each symbol of the pair being positioned at substantially the same horizontal position on the sheet.

31. The method as described in claim 26 wherein each of the encoded symbols has a control point for recognition of the alignment of the digital image.

32. The method as described in claim 26 wherein recognition of three or more of the at least three digitally encoded symbols triggers calculation of transformation parameters for alignment of the digital image with the known template.

33. A system for preparing, administering and marking an examination comprising:

creating an examination having a plurality of user-defined questions;

selecting an answer sheet template from a plurality of customizable templates and customizing the template to contain markings representative of the answers to the plurality of user-defined questions;

printing a plurality of examination response sheets using the selected answer sheet template and having at least three digitally encoded symbols printed thereon, each symbol encoding a unique number or character for identification of the template, and each symbol having a center wherein the at least three digitally encoded symbols form at least three control points, the at least three control points being positioned on the plurality of response sheets in a spatial arrangement to permit recognition of an alignment of each of the printed answer sheets;

administering the examination, each exam answer sheet being marked at predetermined locations to indicate an answer to each of the plurality of user-defined questions;

scanning each of the plurality of answer sheets for forming a scanned digital image;

processing the scanned digital images for determining a location of the at least three control points for aligning each answer sheet with the known template; and

if aligned, comparing the scanned digital image to the template for matching markings thereon for scoring the answer sheet.

34. The system as described in claim 33 wherein each of the symbols is geometrically symmetrical and has a fixed centroid for forming the control point.

35. The system as described in claim 34 wherein recognition of three or more of the at least three centroids of the digitally encoded symbols triggers calculation of transformation parameters for alignment of the sheet with the known template.