US5572601A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Mark sensing on a form
Assignee: Xerox Corp
•
Filing: 1994-10-19
•
Granted: 1996-11-05
•
Expires: 2014-10-19
Abstract
Abstract A robust technique for determining whether a field (43, 45, 47a-d) on a form (40'), which has been converted to a binary input image, contains a mark utilizes an approach of making an initial determination of the approximate location of the field, and then refining such determination. The form is assumed to have registration marks (fiducials) with the field at a known location relative to the fiducials. The fiducials are identified (50), and the approximate location of the field is determined (55) from the fiducial positions and the known relation between the fiducials and the field. At this point, a portion of the image (referred to as the subimage) is extracted (57). The subimage is typically somewhat larger than the field so that it can be assumed that the field is within the subimage. The field has machine-printed lines along at least part of the field perimeter. In order to distinguish these lines from hand-printed marks in the field, a copy of the subimage is subjected to a set of operations (60) on the actual pixels in the subimage that provides nominal information on the location of these lines. The boundaries of the subimage are then changed (62) to nominally exclude the lines.
Inventors
- 👤 Dan S. Bloomberg
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 07:29
CPC Classifications
G; G06; G06V; G06V10/00; G06V10/20; G06V10/22
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
277 words
A method, performed by a processor-based machine on a bitmap input image, for registering to a field in the input image, the field having an associated border line of a particular thickness along a particular edge, the field assumed to be at a known location relative to a set of registration fiducials in the input image, the method comprising operating the processor-based machine to perform the steps of: locating the set of fiducials; determining the approximate location of the field on the basis of the locations of the fiducials; extracting a portion of the input image that is expected to include the field, the portion being referred to as the subimage; the subimage having a boundary, referred to as the particular subimage boundary, that corresponds in orientation and relative position to the particular edge; determining the location of the smallest enclosing rectangle of the largest connected component in the subimage; the smallest enclosing rectangle having a side, referred to as the particular rectangle side, that corresponds in orientation and relative position to the particular edge; and moving the particular subimage boundary so that it is spaced inwardly from the particular rectangle side by a distance that exceeds the particular line thickness by a particular amount, thereby providing a modified subimage that (a) excludes the border line for cases when there is no mark in the field and for cases when there is a mark entirely in the field, and (b) does not exclude the border line for cases when a mark touches the border line and connected ON pixels from the mark extend outwardly from the border line by a perpendicular distance that exceeds the particular amount.
Claim 2
Independent Claim
277 words
A method, performed by a processor-based machine on a bitmap input image, for registering to a field in the input image, the field having an associated border line of a particular thickness along a particular edge, the field assumed to be at a known location relative to a set of registration fiducials in the input image, the method comprising operating the processor-based machine to perform the steps of: locating the set of fiducials; determining the approximate location of the field on the basis of the locations of the fiducials; extracting a portion of the input image that is expected to include the field, the portion being referred to as the subimage; the subimage having a boundary, referred to as the particular subimage boundary, that corresponds in orientation and relative position to the particular edge; determining the location of the smallest enclosing rectangle of the largest connected component in the subimage; the smallest enclosing rectangle having a side, referred to as the particular rectangle side, that corresponds in orientation and relative position to the particular edge; and moving the particular subimage boundary so that it is spaced inwardly from the particular rectangle side by a distance that exceeds the particular line thickness by a particular amount, thereby providing a modified subimage that (a) excludes the border line for cases when there is no mark in the field and for cases when there is a mark entirely in the field, and (b) does not exclude the border line for cases when a mark touches the border line and connected ON pixels from the mark extend outwardly from the border line by a perpendicular distance that exceeds the particular amount.
Claim 3
Dependent Claim
16 words
The method of claim 1 wherein the particular edge of the field is a horizontal edge.
Claim 4
Dependent Claim
86 words
The method of claim 1 wherein: the field has three additional border lines of the particular thickness along three additional edges so as to define a rectangle of ON pixels surrounding the field; and the method further comprises the steps of moving additional boundaries of the subimage that correspond in orientation and relative position to the additional edges so that the additional boundaries of the subimage are spaced inwardly from the sides of the smallest enclosing rectangle by a distance that exceeds the particular line thickness.
Claim 5
Dependent Claim
144 words
The method of claim 1 wherein: the particular edge is a particular horizontal edge; the field has an additional border line of the particular thickness along a particular vertical edge so as to define a right-angle bracket of ON pixels, defined by vertical and horizontal lines along particular vertical and horizontal edges of the field; the subimage has particular vertical and horizontal boundaries that correspond in relative position to the particular vertical and horizontal edges; the smallest enclosing rectangle has particular vertical and horizontal sides that correspond in relative position to the particular vertical and horizontal edges; and the method further comprises the step of moving the particular vertical boundary of the subimage so that the particular vertical boundary of the subimage is spaced inwardly from the particular vertical side of the smallest enclosing rectangle by a distance that exceeds the particular line thickness.
Claim 6
Dependent Claim
36 words
The method of claim 1, and further comprising the step, performed after said moving step, of determining whether the ON pixels in the modified subimage meet a criterion that specifies whether the field contains a mark.
Claim 7
Dependent Claim
23 words
The method of claim 5 wherein the criterion is whether the number of ON pixels in the modified subimage exceeds a particular number.
Claim 8
Dependent Claim
41 words
The method of claim 5, and further comprising the step, performed before said step of determining whether the ON pixels in the modified subimage meet a criterion, of opening the modified subimage with a solid structuring element to remove pepper noise.
Claim 9
Dependent Claim
81 words
The method of claim 5, and further comprising the steps, performed after said moving step and before said step of determining whether the ON pixels in the modified subimage meet a criterion, of: opening a copy of the modified subimage with a horizontal hit-miss structuring element to remove all ON pixels other than thin horizontal lines and storing the result as a temporary subimage; and subtracting the temporary subimage from the modified subimage in order to remove thin horizontal lines therefrom.
Claim 10
Independent Claim
300 words
A method, performed by a processor-based machine on a bitmap input image, for determining whether a field in the input image contains a mark, the field having an associated border line of a particular thickness along a particular edge, the field assumed to be at a known location relative to a set of registration fiducials in the input image, the method comprising operating the processor-based machine to perform the steps of: locating the set of fiducials; determining the approximate location of the field on the basis of the locations of the fiducials; extracting a portion of the input image, the portion being referred to as a subimage, that is expected to include the field; the subimage having a boundary, referred to as the particular subimage boundary, that corresponds in orientation and relative position to the particular edge; determining the location of the smallest enclosing rectangle of the largest connected component in the subimage; the smallest enclosing rectangle having a side, referred to as the particular rectangle side, that corresponds in orientation and relative position to the particular edge; moving the particular subimage boundary so that it is spaced inwardly from the particular rectangle side by a distance that exceeds the particular line thickness by a particular amount, thereby providing a modified subimage that (a) excludes the border line for cases when there is no mark in the field and for cases when there is a mark entirely in the field, and (b) does not exclude the border line for cases when a mark touches the border line and connected ON pixels from the mark extend outwardly from the border line by a perpendicular distance that exceeds the particular amount; and determining whether the ON pixels in the modified subimage meet a criterion that specifies whether the field contains a mark.
Claim 11
Independent Claim
300 words
A method, performed by a processor-based machine on a bitmap input image, for determining whether a field in the input image contains a mark, the field having an associated border line of a particular thickness along a particular edge, the field assumed to be at a known location relative to a set of registration fiducials in the input image, the method comprising operating the processor-based machine to perform the steps of: locating the set of fiducials; determining the approximate location of the field on the basis of the locations of the fiducials; extracting a portion of the input image, the portion being referred to as a subimage, that is expected to include the field; the subimage having a boundary, referred to as the particular subimage boundary, that corresponds in orientation and relative position to the particular edge; determining the location of the smallest enclosing rectangle of the largest connected component in the subimage; the smallest enclosing rectangle having a side, referred to as the particular rectangle side, that corresponds in orientation and relative position to the particular edge; moving the particular subimage boundary so that it is spaced inwardly from the particular rectangle side by a distance that exceeds the particular line thickness by a particular amount, thereby providing a modified subimage that (a) excludes the border line for cases when there is no mark in the field and for cases when there is a mark entirely in the field, and (b) does not exclude the border line for cases when a mark touches the border line and connected ON pixels from the mark extend outwardly from the border line by a perpendicular distance that exceeds the particular amount; and determining whether the ON pixels in the modified subimage meet a criterion that specifies whether the field contains a mark.
Claim 12
Dependent Claim
13 words
The method of claim 9 wherein the border line is a horizontal line.
Claim 13
Dependent Claim
13 words
The method of claim 9 wherein the border line is a vertical line.
Claim 14
Dependent Claim
83 words
The method of claim 9 wherein: the field has three additional border lines of the particular thickness along three additional edges so as to define a rectangle of ON pixels surrounding the field; and the method further comprises moving additional boundaries of the subimage that correspond in orientation and relative position to the additional edges so that the additional boundaries of the subimage are spaced inwardly from the sides of the smallest enclosing rectangle by a distance that exceeds the particular line thickness.
Claim 15
Dependent Claim
144 words
The method of claim 9 wherein: the particular edge is a particular horizontal edge; the field has an additional border line of the particular thickness along a particular vertical edge so as to define a right-angle bracket of ON pixels, defined by vertical and horizontal lines along particular vertical and horizontal edges of the field; the subimage has particular vertical and horizontal boundaries that correspond in relative position to the particular vertical and horizontal edges; the smallest enclosing rectangle has particular vertical and horizontal sides that correspond in relative position to the particular vertical and horizontal edges; and the method further comprises the step of moving the particular vertical boundary of the subimage so that the particular vertical boundary of the subimage is spaced inwardly from the particular vertical side of the smallest enclosing rectangle by a distance that exceeds the particular line thickness.
Claim 16
Dependent Claim
41 words
The method of claim 9, and further comprising the step, performed before said step of determining whether the ON pixels in the modified subimage meet a criterion, of opening the modified subimage with a solid structuring element to remove pepper noise.
Claim 17
Dependent Claim
76 words
The method of claim 9, and further comprising the steps, performed before said step of determining whether the ON pixels in the modified subimage meet a criterion, of: opening a copy of the modified subimage with a horizontal hit-miss structuring element to remove all ON pixels other than thin horizontal lines and storing the result as a temporary subimage; and subtracting the temporary subimage from the modified subimage in order to remove thin horizontal lines therefrom.
Claim 18
Dependent Claim
16 words
The method of claim 9 wherein the particular edge of the field is a horizontal edge.
Claim 19
Dependent Claim
23 words
The method of claim 9 wherein the criterion is whether the number of ON pixels in the modified subimage exceeds a particular number.
Claim 20
Independent Claim
320 words
A method, performed by a processor-based machine on a bitmap input image, for determining whether a field contains a mark, the field having a border line of a particular thickness along at least one edge, the field assumed to be at a known location relative to a set of registration fiducials in the input image, comprising operating the processor-based machine to perform the steps of: locating the set of fiducials; determining the approximate location of the field on the basis of the locations of the fiducials; extracting a portion of the input image, the portion being referred to as a subimage, that is expected to include the field; the subimage having boundaries that correspond in orientation and relative position to respective edges of the field; determining the location of the smallest enclosing rectangle of the largest connected component within the subimage; the smallest enclosing rectangle having sides that correspond in orientation and relative position to respective edges of the field; each edge of the field thus having associated therewith a corresponding boundary of the subimage and a corresponding side of the rectangle; for each edge of the field that has a border line therealong, moving that edge's corresponding subimage boundary so that it is spaced inwardly from that edge's corresponding rectangle side by a distance that exceeds the particular line thickness by a particular amount so as to provide a modified subimage that (a) excludes the border line for cases when there is no mark in the field and for cases when there is a mark entirely in the field, and (b) does not exclude the border line for cases when a mark touches the border line and connected ON pixels from the mark extend outwardly from the border line by a perpendicular distance that exceeds the particular amount; and determining whether the ON pixels in the modified subimage meet a criterion that specifies whether the field contains a mark.
Claim 21
Independent Claim
320 words
A method, performed by a processor-based machine on a bitmap input image, for determining whether a field contains a mark, the field having a border line of a particular thickness along at least one edge, the field assumed to be at a known location relative to a set of registration fiducials in the input image, comprising operating the processor-based machine to perform the steps of: locating the set of fiducials; determining the approximate location of the field on the basis of the locations of the fiducials; extracting a portion of the input image, the portion being referred to as a subimage, that is expected to include the field; the subimage having boundaries that correspond in orientation and relative position to respective edges of the field; determining the location of the smallest enclosing rectangle of the largest connected component within the subimage; the smallest enclosing rectangle having sides that correspond in orientation and relative position to respective edges of the field; each edge of the field thus having associated therewith a corresponding boundary of the subimage and a corresponding side of the rectangle; for each edge of the field that has a border line therealong, moving that edge's corresponding subimage boundary so that it is spaced inwardly from that edge's corresponding rectangle side by a distance that exceeds the particular line thickness by a particular amount so as to provide a modified subimage that (a) excludes the border line for cases when there is no mark in the field and for cases when there is a mark entirely in the field, and (b) does not exclude the border line for cases when a mark touches the border line and connected ON pixels from the mark extend outwardly from the border line by a perpendicular distance that exceeds the particular amount; and determining whether the ON pixels in the modified subimage meet a criterion that specifies whether the field contains a mark.
Claim 22
Dependent Claim
23 words
The method of claim 18 wherein the criterion is whether the number of ON pixels in the modified subimage exceeds a particular number.
Claim 23
Dependent Claim
41 words
The method of claim 18 wherein the field has an edge that has no border line therealong, and further comprising the step, performed before said determining step, of moving the boundary corresponding to the edge that has no border line therealong.
Claim 24
Independent Claim
248 words
A method, performed by a processor-based machine on a bitmap input image, for registering to a field in the input image, the field having a perimeter with a border comprising connected ON pixels along at least a portion of the perimeter, the field assumed to be at a known location relative to a set of registration fiducials in an input image, the method comprising the operating the processor-based machine to perform steps of: locating the set of fiducials; determining the approximate location of the field on the basis of the locations of the fiducials; extracting a portion of the input image that is expected to include the field, the portion being referred to as the subimage and being characterized by a boundary; determining the location of the smallest enclosing rectangle of the largest connected component within the subimage, the smallest enclosing rectangle thus providing nominal information regarding the location of the border in the subimage; and modifying the boundary of the subimage by moving at least a portion of the boundary inwardly so as to (a) exclude the border line based on the nominal information for cases when there is no mark in the field and for cases when there is a mark entirely in the field, and (b) not exclude the border line for at least some cases when a mark touches the border line and connected ON pixels from the mark extend outwardly from the border line by a perpendicular distance that exceeds a particular amount.
Claim 25
Independent Claim
248 words
A method, performed by a processor-based machine on a bitmap input image, for registering to a field in the input image, the field having a perimeter with a border comprising connected ON pixels along at least a portion of the perimeter, the field assumed to be at a known location relative to a set of registration fiducials in an input image, the method comprising the operating the processor-based machine to perform steps of: locating the set of fiducials; determining the approximate location of the field on the basis of the locations of the fiducials; extracting a portion of the input image that is expected to include the field, the portion being referred to as the subimage and being characterized by a boundary; determining the location of the smallest enclosing rectangle of the largest connected component within the subimage, the smallest enclosing rectangle thus providing nominal information regarding the location of the border in the subimage; and modifying the boundary of the subimage by moving at least a portion of the boundary inwardly so as to (a) exclude the border line based on the nominal information for cases when there is no mark in the field and for cases when there is a mark entirely in the field, and (b) not exclude the border line for at least some cases when a mark touches the border line and connected ON pixels from the mark extend outwardly from the border line by a perpendicular distance that exceeds a particular amount.
Claim 26
Dependent Claim
107 words
The method of claim 21 wherein: the border includes a straight line segment of ON pixels characterized by a particular line thickness along a particular edge of the field; the subimage has a boundary, referred to as the particular subimage boundary, that corresponds in orientation and relative position to the particular edge; the smallest enclosing rectangle has a side, referred to as the particular rectangle side, that corresponds in orientation and relative position to the particular edge; and said modifying step includes moving the particular subimage boundary so that it is spaced inwardly from the particular rectangle side by a distance that exceeds the particular line thickness.
Claim 27
Dependent Claim
16 words
The method of claim 22 wherein the particular edge of the field is a horizontal edge.
Claim 28
Dependent Claim
54 words
The method of claim 21 wherein: the border is a rectangle of ON pixels characterized by a particular line thickness; and said modifying step includes moving the boundaries of the subimage so that they are spaced inwardly from the sides of the smallest enclosing rectangle by a distance that exceeds the particular line thickness.
Claim 29
Dependent Claim
121 words
The method of claim 21 wherein: the border includes a right-angle bracket of ON pixels, defined by vertical and horizontal lines along particular vertical and horizontal edges of the field and characterized by a particular line thickness; the subimage has particular vertical and horizontal boundaries that correspond in relative position to said particular vertical and horizontal edges; the smallest enclosing rectangle has particular vertical and horizontal sides that correspond in relative position to the particular vertical and horizontal edges; and said modifying step includes moving the particular vertical and horizontal boundaries of the subimage so that they are spaced inwardly from the particular vertical and horizontal sides of the smallest enclosing rectangle by a distance that exceeds the particular line thickness.
Claim 30
Dependent Claim
13 words
The method of claim 21 wherein said border consists only of straight lines.
References Cited (Backward Citations)
US4352012A
Cited
JPS62272751A
Cited
JPS6395578A
Cited
US4933979A
Cited
JPS63242060A
Cited
US5014331A
Cited
US5140650A
Cited
US4893333A
Cited
US5075895A
Cited
US5099340A
Cited
EP0398185A2
Cited
US5140139A
Cited
US5065437A
Cited
JPH04181390A
Cited
US5129014A
Cited
US5131049A
Cited
US5048109A
Cited
EP0431961A2
Cited
US5187753A
Cited
US5202933A
Cited
US5134669A
Cited
US5181255A
Cited
US5229589A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-11-05 | 2000-05-06 | 2000-11-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-11-05 | 2004-05-06 | 2004-11-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-11-05 | 2008-05-06 | 2008-11-05 | $7700.00 | Window Closed / Lapsed |