Method for determining corners of an object represented by image data

• US 20070071324A1
• Filed: 09/27/2005
• Published: 03/29/2007
• Est. Priority Date: 09/27/2005
• Status: Abandoned Application

• Current Assignee: Lexmark International Incorporated (Ninestar Corporation)
• Original Assignee: Lexmark International Incorporated (Ninestar Corporation)
• Inventors: Thakur, Khageshwar
• Application Number:
  US11/236,031
• Publication Number:
  US 20070071324A1
• Time in Patent Office: Days
• US Class Current: 382/199
• CPC Class Codes: G06T 2207/10008 from scanner, fax or copier
• CPC Class Codes: G06T 2207/30176 Document
• CPC Class Codes: G06T 7/13 Edge detection
• CPC Class Codes: G06T 7/70 Determining position or orientation of objects or cameras camera calibration G06T7/80
• CPC Class Codes: G06V 10/243 by compensating for image skew or non-uniform image deformations
• CPC Class Codes: G06V 10/44 Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components
• CPC Class Codes: H04N 1/00681 Detecting the presence, position or size of a sheet or correcting its position before scanning H04N1/047 takes precedence; mode signalling H04N1/333; skew detection or correction in image signals H04N1/3878
• CPC Class Codes: H04N 1/00708 Size or dimensions
• CPC Class Codes: H04N 1/0071 Width
• CPC Class Codes: H04N 1/00713 Length
• CPC Class Codes: H04N 1/00737 using the scanning elements as detectors
• CPC Class Codes: H04N 1/00753 of a sheet relative to a particular backgroud
• CPC Class Codes: H04N 1/00795 Reading arrangements details of scanning heads H04N1/024; scanning arrangements therefor H04N1/04

Abstract

A method for determining corners of an object represented by image data includes determining edge data associated with the object; finding estimated corners for the edge data; determining segment data of the edge data by ignoring data within a predetermined distance from the estimated corners; extending the segment data to define a plurality of lines having points of intersection; and defining ideal corners at the points of intersection of the plurality of lines.

Claims

1. A method for determining corners of an object represented by image data, comprising:

determining edge data associated with said object;

finding estimated corners for said edge data;

determining segment data of said edge data by ignoring data within a predetermined distance from said estimated corners;

extending said segment data to define a plurality of lines having points of intersection; and

defining ideal corners at said points of intersection of said plurality of lines.

2. The method of claim 1, wherein said segment data is extended by processing said segment data using a least squares fit algorithm to obtain a straight line for each segment represented by said segment data, and then projecting each said straight line a distance sufficient to establish said points of intersection.

3. The method of claim 1, wherein said object is a substantially rectangular substrate.

4. The method of claim 1, wherein said substantially rectangular substrate is one of a document and a photograph.

5. The method of claim 1, wherein said object represented by said image data is one of a plurality of objects represented by said image data.

6. The method of claim 1, wherein said edge data of said object includes at least two substantially orthogonal edges.

7. The method of claim 1, wherein said image data is generated during a scanning operation, said image data including outer boundary data, background data and foreground data, said foreground data corresponding to said object.

8. The method of claim 7, wherein said background is represented in said image data at a background level, said method further comprising clipping said outer boundary data to said background level.

9. The method of claim I, wherein the act of determining edge data includes:

processing said image data to generate a cyclic list of connected points along edges of said object;

filtering out any branched edges in said edge data.

10. A method for determining corners of an object represented by image data, comprising:

(a) processing said image data to generate a cyclic edge data list of connected points along edges of said object;

(b) identifying an origin point P0 from said connected points;

(c) fetching a first point P<sub>−

n</sub> a distance DL from point P0 in a clockwise direction in said cyclic edge data list, wherein n is a count value;

(d) fetching a second point P_+n, a distance DR from P0 in a counterclockwise direction in said cyclic edge data list;

(e) determining a distance DH between said first point P<sub>−

n</sub> and said second point P_+n; and

(f) if DH²=DL²+DR²+Tr, wherein Tr is a tolerance range, then point P0 is designated as an estimated corner.

11. The method of claim 10, further comprising filtering out any branched edges in said cyclic edge data list prior to identifying said origin point P0.

12. The method of claim 10, wherein if DH²>

DL²+DR²+Tr, then point P0 is not at an estimated corner, and the method further comprising;

(g) selecting a new origin point P0=P0+k, wherein k is an offset count value; and

(h) repeating acts (c) though (f).

13. The method of claim 12, wherein acts (c) through (h) are repeated until all estimated corners are identified.

14. The method of claim 13, further comprising:

determining segment edge data from said cyclic edge data list by ignoring data within a predetermined distance from said estimated corners;

extending said segment edge data to define a plurality of lines having points of intersection; and

defining ideal corners of said object at said points of intersection of said plurality of lines.

15. The method of claim 14, wherein said segment data is extended by processing said segment data using a least squares fit algorithm to obtain a straight line for each segment represented by said segment data, and then projecting each said straight line a distance sufficient to establish said points of intersection.

16. The method of claim 12, wherein k is selected by the equation:

$k=\frac{\left(D_H^2-D_L^2-D_R^2\right)·<br><br>n}{2·<br><br>D_L^2}$

17. The method of claim 12, wherein k is selected by the equation:

$k=-\frac{\left(D_H^2-D_L^2-D_R^2\right)·<br><br>n}{2·<br><br>D_L^2}$

18. The method of claim 10, wherein said tolerance range Tr is zero.

19. The method of claim 10, wherein said tolerance range Tr is 0.0 to 0.1 millimeters.

20. A method for determining corners of an object represented by image data, comprising:

(a) processing said image data to generate a cyclic edge data list of connected points along edges of said object;

(b) filtering out any branched edges in said cyclic edge data list;

(c) identifying an origin point P0 from said connected points;

(d) fetching a first point P<sub>−

n</sub> a distance DL from point P0 in a clockwise direction in said cyclic edge data list, wherein n is a count value;

(e) fetching a second point P_+n a distance DR from P0 in a counterclockwise direction in said cyclic edge data list;

(f) determining a distance DH between said first point P<sub>−

n</sub> and said second point P_+n; and

(g) if DH²>

DL²+DR²+Tr, then point P0 is not at an estimated corner, then the method further;

(h) selecting a new origin point P0=P0+k, wherein k is an offset count value; and

(i) repeating acts (d) though (g).

21. The method of claim 20, wherein acts (c) through (i) are repeated until all estimated corners are identified.

22. The method of claim 21, further comprising:

determining segment edge data from said cyclic edge data list by ignoring data within a predetermined distance from said estimated corners;

extending said segment edge data to define a plurality of lines having points of intersection; and

defining ideal corners of said object at said points of intersection of said plurality of lines.

23. The method of claim 22, wherein said segment data is extended by processing said segment data using a least squares fit algorithm to obtain a straight line for each segment represented by said segment data, and then projecting each said straight line a distance sufficient to establish said points of intersection.

24. The method of claim 20, wherein k is selected by the equation:

$k=\frac{\left(D_H^2-D_L^2-D_R^2\right)·<br><br>n}{2·<br><br>D_R^2}$

25. The method of claim 20, wherein k is selected by the equation:

$k=-\frac{\left(D_H^2-D_L^2-D_R^2\right)·<br><br>n}{2·<br><br>D_L^2}$

26. The method of claim 20, wherein said tolerance range Tr is zero.

27. The method of claim 20, wherein said tolerance range Tr is 0.0 to 0.1 millimeters.