Method for locating user interface tags in a document processing system
First Claim
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.
7 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
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. - View Dependent Claims (12, 13, 14, 15, 16, 17)
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. - View Dependent Claims (19, 20)
-
Specification