Method of optical mark recognition

• US 6,741,738 B2
• Filed: 02/02/2001
• Issued: 05/25/2004
• Est. Priority Date: 03/13/2000
• Status: Active Grant

• Current Assignee: Accusoft Corporation
• Original Assignee: TMS, Inc.
• Inventors: Taylor, Garland S.
• Primary Examiner(s): Johnson, Timothy M.
• Assistant Examiner(s): Kassa, Yosef
• Application Number:
  US09/776,439
• Publication Number:
  US 20010033688A1
• Time in Patent Office: 1,208 Days
• Field of Search: 382/103, 382/108, 382/112, 382/113, 382/116, 382/151, 382/187, 382/188, 382/184, 382/190, 382/201, 382/203, 382/209, 382/216, 382/224, 382/282, 382/284, 382/287, 382/291, 382/294, 358/538, 358/540, 358/450, 358/452
• US Class Current: 382/187
• CPC Class Codes: G06K 17/0032 Apparatus for automatic testing and analysing marked record carriers, used for examinations of the multiple choice answer type teaching apparatus working with questions and answers G09B7/00

Abstract

There is provided herein a new method of identifying when a particular hand-drawn selection has been made on, for example, a standardized test form. This method does not require the use of any particular form nor does it use registration marks. It is robust enough to be used when the form is somewhat misaligned on the scanning device. This method utilizes a scanned “blank” form which is then compared with a form containing user markings thereon. As a first step, the user'"'"'s form is mathematically iteratively aligned with the scanned blank form. As a next step, a fine-scale refinement is applied to each individual “bubble” (i.e., response field) of the user'"'"'s form to bring that feature into near exact alignment with the same bubble on the blank form. Finally, a quantitative measure of the similarity between the blank and user forms is used to determine whether or not the user has made a mark on the form within that response region.

Claims

1. A method of aligning a user-marked document for optical mark recognition, wherein is provided a reference document and at least one target document, comprising the steps of:

(a) selecting one of said at least one target documents;

(b) obtaining a digital representation of said selected target document, thereby obtaining a digital target document;

(c) obtaining a digital representation of said reference document at a predetermined digital resolution, thereby obtaining a digital reference document;

(d) selecting a reference region within said digital reference document, said reference region

(d1) corresponding to a predetermined portion of said reference document,

(d2) having a predetermined location within said digital reference document, and,

(d3) containing a plurality of reference pixels therein;

(e) selecting a target region of said digital target document, said target region

(e1) having a location at least approximately corresponding to said predetermined location within said digital reference document, and,

(e2) having a plurality of target pixels contained therein;

(f) determining from said reference pixels and said target pixels an offset between said reference region and said target region;

(g) performing steps (c) through (f) at least once;

(h) calculating an image adjustment rule from any offsets so calculated;

(i) applying said image adjustment rule, thereby at least approximately aligning said digital reference document and said selected digital target document;

(j) performing steps (c) through (i) at least twice using at least two different digital resolutions; and

,

(k) determining from said digital target document, said digital reference document, and from any adjustment rules so calculated whether said user-marked document contains a user mark within a predetermined region of said user-marked document.

2. A method according to claim 1, wherein said digital representation of said selected target document is a gray scale image.

3. A method according to claim 2, wherein said digital representation of said selected target document is a 4-bit digital gray scale image.

4. A method according to claim 1, wherein said digital representation of said selected target document is a digital color image.

5. A method according to claim 1, wherein step (a) includes the step of scanning said reference document at a predetermined resolution, thereby obtaining a digital reference image.

6. A method according to claim 1, step (h) includes the step of calculating an image adjustment rule using an affine transform.

7. A method according to claim 1, step (h) includes the step of calculating an image adjustment rule using a Delaunay triangulation method.

8. A method according to claim 1, wherein step (g) includes the step of repeating steps (d) through (f) at least three times.

9. A method according to claim 1, wherein step (i) includes the step of applying said image adjustment rule by mathematically relocating said selected digital target document according to said image adjustment rule.

10. An apparatus for aligning a user-marked document for use in optical mark recognition according to the method of claim 1, comprising:

(a) a computer configurable to access said digital reference document and said digital target document, wherein said computer contains instructions programming said computer to perform said method.

11. An apparatus according to claim 10, further comprising:

(b) an electronic scanner,

(b1) said scanner being configurable to scan at a plurality of different digital resolutions, and,

(b2) said scanner for obtaining digital representations of at least said reference document at a plurality of predetermined digital resolutions, thereby creating digital reference documents at said plurality of predetermined digital resolutions, said digital reference documents being positionable to be made accessible by said computer.

12. A device adapted for use by a digital computer wherein a plurality of computer instructions defining the method of claim 1 are encoded,

said device being readable by said digital computer,

said computer instructions programming said digital computer to perform said method, and,

said device being selected from the group consisting of computer RAM, computer ROM, a PROM chip, flash RAM, a ROM card, a RAM card, a floppy disk, a magnetic disk, a magnetic tape, a magneto-optical disk, an optical disk, a CD-ROM disk, or a DVD disk.

13. A method according to claim 1, wherein said step (f) includes the steps of:

(f1) selecting a trial offset,

(f2) calculating a numerical distance between a plurality of said reference pixels and a corresponding plurality of said target pixels using said trial offset,

(f3) performing steps (f1) and (f2) a plurality of times,

(f4) determining from any numerical distances so calculated an offset between said reference pixels and said target pixels.

14. A method according to claim 13, wherein step (f4) includes the step of:

(i) calculating a minimum value of any numerical distances so determined, said minimum value being associated with a particular trial offset,

(ii) selecting said particular trial offset corresponding to said minimum numerical distance as an offset between said reference pixels and said target pixels.

15. A method according to claim 13, wherein said step (f2) includes the steps of:

(i) subtracting pixel-by-pixel a plurality of said reference pixels from said target pixels using said trail offset, thereby producing a plurality of pixel differences,

(ii) squaring any pixel differences so produced, thereby producing squared pixel differences, and,

(iii) summing together any squared pixel differences so produced, thereby calculating a numerical distance between said plurality of reference pixels and said corresponding plurality of target pixels.

16. A method according to claim 1, wherein said digital reference document has a reference document intensity level, and wherein step (c) includes the steps of:

(c1) obtaining a digital representation of said selected target document, thereby obtaining a digital target document, said digital target document having a target image intensity level, and,

(c2) adjusting said target image intensity level to at least approximately match said reference document intensity level.

17. A method according to claim 16, wherein step (c2) includes the step of adjusting said target image intensity level to at least approximately match said reference document intensity level using a Delaunay triangulation method.

18. A method of aligning a user-marked document for optical mark recognition, wherein is provided a reference document and at least one target document, comprising the steps of:

(a) selecting one of said at least one target documents;

(b) obtaining a digital representation of said selected target document, thereby obtaining a digital target document;

(c) obtaining a digital representation of said reference document, thereby obtaining a digital reference document;

(d) selecting a reference region within said digital reference document, said reference region

(d1) corresponding to a predetermined portion of said reference document,

(d2) having a predetermined location within said digital reference document, and,

(d3) containing a plurality of reference pixels therein;

(e) selecting a target region of said digital target document, said target region

(e1) having a location at least approximately corresponding to said predetermined location within said digital reference document, and,

(e2) having a plurality of target pixels contained therein;

(f) selecting a trial offset;

(g) calculating a numerical distance between a plurality of said reference pixels and a corresponding plurality of said target pixels using said trial offset;

(h) performing steps (f) and (g) a plurality of times, using at least two different trial offsets;

(i) determining from any numerical distances so calculated an offset between said reference pixels and said target pixels;

(j) performing steps (e) through (i) at least once,

(k) calculating an image adjustment rule from any offsets so determined; and

,

(l) determining from said digital target document, said digital reference document, and from any adjustment rules so calculated whether said user-marked document contains a user mark within a predetermined region of said user-marked document.

19. An apparatus for aligning a user-marked document for use in optical mark recognition according to the method of claim 18, comprising:

(a) a computer configurable to access said digital reference document and said digital target document, wherein said computer contains instructions programming said computer to perform said method.

20. A device adapted for use by a digital computer wherein a plurality of computer instructions defining the method of claim 18 are encoded,

said device being readable by said digital computer,

said computer instructions programming said digital computer to perform said method, and,

said device being selected from the group consisting of computer RAM, computer ROM, a PROM chip, flash RAM, a ROM card, a RAM card, a floppy disk, a magnetic disk, a magnetic tape, a magneto-optical disk, an optical disk, a CD-ROM disk, or a DVD disk.

21. A method according to claim 18, wherein said digital representation of said selected target document is a gray scale image.

22. A method according to claim 21, wherein said digital representation of said selected target document is a 4-bit digital gray scale image.

23. A method according to claim 18, wherein said digital representation of said selected target document is a color image.

24. A method of optical mark recognition wherein is provided

a reference document containing at least one reference bubble, and

at least one user-marked target document, each of said at least one user-marked target documents containing a target bubble corresponding to said reference bubble therein, and each of said user-marked target documents containing at least one marked target bubble marked by a user therein,

comprising the steps of:

(a) selecting one of said at least one target documents, said selected target document containing a selected target bubble therein;

(b) obtaining a digital representation of a region containing substantially all of said selected target bubble, thereby obtaining a digital target region, said digital target region containing target pixels therein;

(c) obtaining a digital representation of a region containing said reference bubble, thereby obtaining a digital reference bubble, said digital reference bubble containing reference pixels therein;

(d) selecting a pixel from among said reference pixels, said selected reference pixel having a particular location within said digital reference bubble;

(e) selecting a region within said digital target region and said target pixels therein, thereby producing a plurality of selected target pixels, said selected region corresponding at least approximately to said particular location within said digital reference bubble;

(f) calculating a numerical difference between said selected reference pixel and each of said selected target pixels, thereby producing a plurality of difference pixels;

(g) determining from said plurality of difference pixels a similarity value;

(h) performing steps (d) through (g) at least twice for at least two different selected reference pixels, thereby producing a plurality of similarity values; and

,

(i) determining from said plurality of similarity values whether said selected target bubble is a user-marked target bubble.

25. A method according to claim 24, wherein said digital representation of a region containing substantially all of said selected target bubble is a gray scale image.

26. A method according to claim 25, wherein said digital representation of a region containing substantially all of said selected target bubble is a color image.

27. A method according to claim 24, wherein step (i) includes the step of determining from said plurality of similarity values whether said selected target is a user-marked target bubble, an erased target bubble, or a blank target bubble.

28. An apparatus for aligning a user-marked document for use in optical mark recognition according to the method of claim 24, comprising:

(a) a computer configurable to access said digital reference document and said digital target document, wherein said computer contains instructions programming said computer to perform said method.

29. A device adapted for use by a digital computer wherein a plurality of computer instructions defining the method of claim 24 are encoded,

said device being readable by said digital computer,

said computer instructions programming said digital computer to perform said method, and,

said device being selected from the group consisting of computer RAM, computer ROM, a PROM chip, flash RAM, a ROM card, a RAM card, a floppy disk, a magnetic disk, a magnetic tape, a magneto-optical disk, an optical disk, a CD-ROM disk, or a DVD disk.

30. A method according to claim 24, wherein said selected region is a 3 pixel by 3 pixel region corresponding at least approximately to said particular location within said digital reference bubble.

31. A method according to claim 24, wherein step (i) includes the steps of:

(i1) calculating an average value of said plurality of similarity values, and,

(i2) determining from said average value whether said selected target bubble is a user-marked target bubble.

32. A method according to claim 24, wherein step (i) includes the steps of:

(i1) calculating a maximum value of said plurality of similarity values, and,

(i2) determining from said maximum value whether said selected target bubble is a user-marked target bubble.

33. A method of normalizing the relative intensity levels of one document with respect to another for use in OMR, wherein is provided

a reference document containing a plurality of reference regions therein, and

a target document, said target documents containing a corresponding plurality of target regions therein, each of said target regions corresponding to one of said reference regions,

comprising the steps of:

(a) selecting a reference region in said reference document;

(b) selecting a target region in said target document corresponding to said selected reference region, said target region having a target location within said target document;

(c) obtaining a digital representation of said reference region, thereby obtaining a digital reference region, said digital reference region containing reference pixels therein, and said reference region having a reference location within said reference document;

(d) obtaining a digital representation of said target region, thereby obtaining a digital reference region, said digital reference region containing reference pixels therein;

(e) determining an intensity level of said digital target region;

(f) determining an intensity level of said digital reference region;

(g) calculating an intensity differential between said intensity level of said digital target region and said intensity level of said digital reference region;

(h) performing steps (a) though (g) at least twice, thereby producing a plurality of intensity differentials;

(i) calculating a difference map using at least said plurality of intensity differentials together with any of said reference locations or said target locations;

(j) obtaining a digital representation of said reference document, thereby producing a digital reference document;

(k) obtaining a digital representation of said target document, thereby producing a digital target document; and

,

(l) modifying at least a portion of said digital target document according to said difference map, thereby at least approximately normalizing said digital target document relative to said digital reference document.

34. An apparatus for aligning a user-marked document for use in optical mark recognition according to the method of claim 33, comprising:

(a) a computer configurable to access said digital reference document and said digital target document, wherein said computer contains instructions programming said computer to perform said method.

35. A device adapted for use by a digital computer wherein a plurality of computer instructions defining the method of claim 33 are encoded,

said device being readable by said digital computer,

said computer instructions programming said digital computer to perform said method, and,

said device being selected from the group consisting of computer RAM, computer ROM, a PROM chip, flash RAM, a ROM card, a RAM card, a floppy disk, a magnetic disk, a magnetic tape, a magneto-optical disk, an optical disk, a CD-ROM disk, or a DVD disk.

36. A method according to claim 33, wherein step (i) includes the step of using a Delaunay triangulation method to calculate a difference map using at least said plurality of intensity differentials together with any of said reference locations or said target locations.

37. A method of aligning a user-marked document for optical mark recognition, wherein is provided a reference document and at least one target document, comprising the steps of:

(a) selecting one of said at least one target documents;

(b) obtaining a digital representation of said selected target document, thereby obtaining a digital target document;

(c) obtaining a digital representation of said reference document at a predetermined digital resolution, thereby obtaining a digital reference document;

(d) selecting a reference region within said digital reference document, said reference region

(d1) corresponding to a predetermined portion of said reference document,

(d2) having a predetermined location within said digital reference document, and,

(d3) containing a plurality of reference pixels therein;

(e) selecting a target region of said digital target document, said target region

(e1) having a location at least approximately corresponding to said predetermined location within said digital reference document, and,

(e2) having a plurality of target pixels contained therein;

(f) determining from said reference pixels and said target pixels an offset between said reference region and said target region;

(g) performing steps (c) through (f) at least once;

(h) calculating an image adjustment rule from any offsets so calculated;

(i) applying said image adjustment rule, thereby at least approximately aligning said digital reference document and said selected digital target document;

(j) performing steps (c) through (i) at least twice using at least two different digital resolutions; and

,

(k) aligning said digital target document and said digital reference document from any adjustment rules so calculated, thereby producing an aligned document for use in determining at least where on said user-marked document a user has marked.