Method for locating user interface tags in a document processing system

• US 6,470,096 B2
• Filed: 11/13/1998
• Issued: 10/22/2002
• Est. Priority Date: 11/13/1998
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Davies, Daniel, Craig, Julia A.
• Primary Examiner(s): Johns, Andrew W.
• Assistant Examiner(s): AZARIAN, SEYED H
• Application Number:
  US09/191,969
• Publication Number:
  US 20020085759A1
• Time in Patent Office: 1,439 Days
• Field of Search: 382/203, 382/204, 382/205, 382/206, 382/207, 382/208, 382/209, 382/219, 382/220, 235/462.27, 235/462.16, 707/531, 707/540
• US Class Current: 382/203
• CPC Class Codes: H04N 1/00968 by scanning marks on a sheet mark-sheet input means H04N1/00355; sensing record carriers G06K7/00
• CPC Class Codes: H04N 1/32144 embedded in the image data, i.e. enclosed or integrated in the image, e.g. watermark, super-imposed logo or stamp
• CPC Class Codes: H04N 2201/3205 of identification information, e.g. name or ID code H04N2201/3209 takes precedence
• CPC Class Codes: H04N 2201/3222 of processing required or performed, e.g. forwarding, urgent or confidential handling
• CPC Class Codes: H04N 2201/3269 of machine readable codes or marks, e.g. bar codes or glyphs

Abstract

A method for locating a substantially rectangular pattern, in any orientation, in a digitized image used in a document processing system operates by identifying all connected components within the image, discarding those that do not meet certain size criteria, and on the remaining connected components identifying eight compass-position extreme points, four of which may represent the corners of the rectangular pattern. The relationships among the extreme points are then analyzed to determine whether an expected diagonal length, expected height, and expected width of the pattern are all present within a selected tolerance.

Claims

1. A method for locating a substantially rectangular pattern in a digitized image, the pattern having an expected diagonal length, comprising the steps of:

receiving data representative of the digitized image;

identifying a connected component in the image;

finding a plurality of extreme points within the connected component;

determining whether the expected diagonal length is present between two of the plurality of extreme points;

if so, locating corners of a pattern candidate; and

determining whether a correctly-dimensioned substantially rectangular shape is defined by the corners.

2. The method of claim 1, wherein the pattern has an expected width and an expected height.

3. The method of claim 2, further comprising the steps, after identifying a connected component, of:

determining whether the connected component is substantially narrower or shorter than the smaller of the expected width and the expected height, and if so, rejecting the connected component; and

determining whether the connected component is substantially taller or wider than the greater of the expected width and the expected height, and if so, rejecting the connected component.

4. The method of claim 2, further comprising the steps, after identifying a connected component, of:

determining whether the connected component is substantially narrower or shorter than the smaller of the expected width and the expected height, and if so, rejecting the connected component; and

determining whether the connected component is substantially taller or wider than the expected diagonal length, and if so, rejecting the connected component.

5. The method of claim 2, wherein the finding step comprises identifying eight extreme points in positions corresponding to compass positions representing north, northeast, east, southeast, south, southwest, west, and northwest.

6. The method of claim 5, wherein the extreme points comprise four opposing pairs of extreme points.

7. The method of claim 6, wherein the step of determining whether the expected diagonal length is present comprises:

calculating the distance between each opposing pair of extreme points;

if the distance is substantially equal to the expected diagonal length, indicating that the expected diagonal length is present.

8. The method of claim 5, wherein the step of locating corners comprises the step of selecting a first corner point, a second corner point, a third corner point, and a fourth corner point from the eight extreme points such that the two points defining the expected diagonal length but no two adjacent compass positions are included in the corner points.

9. The method of claim 8, wherein the step of determining whether a correctly-dimensioned substantially rectangular shape is defined comprises the steps of:

determining whether either a distance from the first corner point to the second corner point or a distance from the third corner point to the fourth corner point is substantially equal to the expected width, and whether either a distance from the second corner point to the third corner point or a distance from the fourth corner point to the first corner point is substantially equal to the expected height, and if both width and height criteria are satisfied, indicating that a correctly-dimensioned substantially rectangular shape is defined by the four corner points; and

determining whether either a distance from the first corner point to the second corner point or a distance from the third corner point to the fourth corner point is substantially equal to the expected height, and whether either a distance from the second corner point to the third corner point or a distance from the fourth corner point to the first corner point is substantially equal to the expected width, and if both height and width criteria are satisfied, indicating that a correctly-dimensioned substantially rectangular shape is defined by the four corner points.

10. The method of claim 1, further comprising the step of repeating the identifying, finding, determining, locating, and determining steps until all connected components in the image have been processed.

11. A system for locating a substantially rectangular pattern in a digitized image, the pattern having an expected diagonal length, the system comprising:

image receiving means for receiving data representative of the digitized image;

shape detection means coupled to said image receiving means, said shape detection means comprising;

symbol identification means for identifying a connected component in the image;

extreme point identification means of finding a plurality of extreme points within the connected component;

extreme point diagonal measurement means for determining whether the expected diagonal length is present between two of the plurality of extreme points;

corner points identification means for identifying corners of a pattern candidate having the expected diagonal length between tow of the plurality of extreme points; and

rectangle detection means for determining whether a substantially rectangular shape is defined by the corners.

12. The system of claim 11 wherein the pattern has an expected width and an expected height and the system further comprises:

means for determining whether the connected component is substantially narrower or shorter than the smaller of the expected width and the expected height, and if so, rejecting the connected component; and

means for determining whether the connected component is substantially taller or wider than the greater of the expected width and the expected height, and if so, rejecting the connected component.

13. The system of claim 11 further comprises means for determining whether the connected component is substantially taller or wider than the expected diagonal length, and if so, rejecting the connected component.

14. The system of claim 11, wherein the extreme point identification means further comprises means for identifying eight extreme points in positions corresponding to compass positions representing north, northeast, east, southeast, south, southwest, west, and northwest.

15. The system of claim 11 wherein the extreme points comprise four opposing pairs of extreme points and the extreme point diagonal measurement means further comprises means further comprises:

means for calculating the distance between each opposing pair of extreme points;

means for determining if the distance is substantially equal to the expected diagonal length and if it is, indicating that the expected diagonal length is present.

16. The system of claim 11, wherein the corner points identification means further comprises means for selecting a first corner point, a second corner point, a third corner point, and a fourth corner point from the eight extreme points such that the two points defining the expected diagonal length but no two adjacent compass positions are included in the corner points.

17. The system of claim 16, wherein the extreme point diagonal measurement means further comprises:

means for determining whether either a distance from the first corner point to the second corner point or a distance from the third corner point to the fourth corner point is substantially equal to the expected width, and whether either a distance from the second corner point to the third corner point or a distance from the fourth corner point to the first corner point is substantially equal to the expected height, and if both width and height criteria are satisfied, and indicating that a correctly-dimensioned substantially rectangular shape is defined by the four corner points; and

means for determining whether either a distance from the first corner point to the second corner point or a distance from the third corner point to the fourth corner point is substantially equal to the expected height, and whether either a distance from the second corner point to the third corner point or a distance from the fourth corner point to the first corner point is substantially equal to the expected width, and if both height and width criteria are satisfied, and indicating that a correctly-dimensioned substantially rectangular shape is defined by the four corner points.

18. A method for finding a polygon in an image, said polygon having at least one expected diagonal length, said method comprising the steps of:

receiving data representative of the digitized image;

identifying a connected component in the image;

finding a plurality of extreme points within the connected component;

determining whether the at least one expected diagonal length is present between two of the plurality of extreme points;

if so, locating corners of a pattern candidate; and

determining whether a correctly-dimensioned polygon is defined by the corners.

19. The method as recited in claim 18 wherein said polygon has at least two expected diagonal lengths and said determining step determines whether the at least two expected diagonal lengths are present between two different sets of the plurality of extreme points.

20. The method as recited in claim 18 wherein said polygon has n sides and said step of finding a plurality of extreme points within the connected component is comprised of finding 2n evenly spaced compass positions on said connected component.