Edge detection using hough transformation

• US 20030228057A1
• Filed: 06/10/2002
• Published: 12/11/2003
• Est. Priority Date: 06/10/2002
• Status: Active Grant

• Current Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Original Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Inventors: Paquette, Daniel R.
• Granted Patent: US 7,085,432 B2
• Time in Patent Office: Days
• US Class Current: 382/199
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/146 Aligning or centring of the image pick-up or image-field
• CPC Class Codes: G06V 30/18067 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation
• CPC Class Codes: G06V 30/424 Postal images, e.g. labels or addresses on parcels or postal envelopes

Abstract

A method identifies edges of an object in an image by analyzing an accumulator array produced via a Hough transformation of the image. The method includes the step of identifying a first cell in a first row of the array associated with a first edge of the object. The first is then searched for a second cell in the array associated with a second edge of the object, the second edge being parallel to the first edge. A second row shifted ninety degrees from the first row is then searched for a third cell in the array associated with a third edge of the object, the third edge being perpendicular to the first edge. The second row is then searched for a fourth cell in the array associated with a fourth edge in the image, the fourth edge being parallel to the third edge.

Claims

1. A method for identifying edges of an object in an image by analyzing an accumulator array produced via a Hough transformation of the image, the array including a plurality of rows each including a plurality of cells, said method comprising the steps of:

identifying a first cell in a first row of the array associated with a first edge of the object;

searching said first row for a second cell in the array associated with a second edge of the object, said second edge being parallel to said first edge;

searching a second row of the array shifted ninety degrees from said first row for a third cell in the array associated with a third edge of the object, said third edge being perpendicular to said first edge; and

searching said second row for a fourth cell in the array associated with a fourth edge in the image, said fourth edge being parallel to said third edge.

2. The method recited in claim 1, wherein said step of identifying a first cell comprises the step of selecting the first cell from a group of cells identified as potential edge lines in the array, said group of cells being determined by the steps of:

examining the cells in each row of the array by stepping through the cells in an inward direction from opposite ends of the row;

identifying a predetermined number of cells in each row having a magnitude above a predetermined threshold,

ceasing examination of the cells in each row once said predetermined number of cells are identified in the row; and

placing said identified cells in said group of cells.

3. The method recited in claim 2, wherein said step of identifying a predetermined number of cells in each row comprises the steps of:

identifying one of said cells having a magnitude above the predetermined threshold while stepping inward from a first one of said opposite ends of the row;

identifying another one of said cells having a magnitude above the predetermined threshold while stepping inward from the other of said opposite ends of the row; and

repeating the above steps until said predetermined number of cells in the row are identified.

4. The method recited in claim 1, wherein said step of searching said first row for a second cell comprises the step of examining the cells of said first row by stepping through the cells in an inward direction from an end of said first row opposite the end from which said first cell was identified.

5. The method recited in claim 1, wherein said step of searching a second row for a third cell comprises the step of examining the cells of said second row by stepping through the cells in an inward direction from an end of said second row that coincides with the end of said first row from which said first cell was identified.

6. The method recited in claim 5, wherein said step of searching said second row for a fourth cell comprises the step of examining the cells of said second row by stepping through the cells in an inward direction from an end of said second row opposite the end of said second row from which said third cell was identified.

7. The method recited in claim 1 further comprising the steps of:

constructing a first line on the image in accordance with parametric data associated with said first cell;

constructing a second line on the image in accordance with parametric data associated with said second cell;

constructing a third line on the image in accordance with parametric data associated with said third cell;

constructing a fourth line on the image in accordance with parametric data associated with said fourth cell;

identifying intersections of said first, second, third, and fourth lines as indicating corners of the object; and

identifying portions of said first, second, third, and fourth lines extending between said intersections as indicating edges of the object.

8. The method recited in claim 1 further comprising the steps of:

constructing three lines on said image in accordance with parametric data associated with three of said first, second, third, and fourth cells of the array;

constructing a fourth line on said image, said fourth line being estimated from the parametric data used to construct said three lines;

identifying intersections of said three lines and said fourth line as indicating corners of the object; and

identifying portions of said lines extending between said intersections of said lines as indicating edges of the object.

9. The method recited in claim 1, wherein the selected first cell and any identified second, third, or fourth cell associated with the selected first cell comprise a solution set for the edges of the object in the image, said method further comprising the steps of:

identifying solution sets for selected first cells;

assigning a confidence value to said solution sets, said confidence value being calculated as a function of parametric data associated with each cell in the solution set; and

identifying one of said solution sets as including cells indicative of edges of the object, said solution set being identified as a function of said confidence value.

10. A computer product for identifying edges of an object in an image by analyzing an accumulator array produced via a Hough transformation of the image, the array including a plurality of rows each including a plurality of cells, said computer product comprising:

a portion for identifying a first cell in a first row of the array associated with a first edge of the object;

a portion for searching said first row for a second cell in the array associated with a second edge of the object, said second edge being parallel to said first edge;

a portion for searching a second row of the array shifted ninety degrees from said first row for a third cell in the array associated with a third edge of the object, said third edge being perpendicular to said first edge; and

a portion for searching said second row for a fourth cell in the array associated with a fourth edge in the image, said fourth edge being parallel to said third edge.

11. The computer product recited in claim 10, wherein said portion for identifying a first cell comprises a portion for selecting the first cell from a group of cells identified as potential edge lines in the array, said computer product further comprising a portion for determining said group of cells, said portion for determining said group of cells comprising:

a portion for examining the cells in each row of the array by stepping through the cells in an inward direction from opposite ends of the row;

a portion for identifying a predetermined number of cells in each row having a magnitude above a predetermined threshold,

said portion for examining ceasing examination of the cells in each row once said predetermined number of cells are identified in the row; and

a portion for placing said identified cells in said group of cells.

12. The computer product recited in claim 11, wherein said portion for identifying a predetermined number of cells in each row comprises:

a portion for identifying one of said cells having a magnitude above the predetermined threshold while stepping inward from a first one of said opposite ends of the row;

a portion for identifying another one of said cells having a magnitude above the predetermined threshold while stepping inward from the other of said opposite ends of the row; and

a portion for repeating the above steps until said predetermined number of cells in the row are identified.

13. The computer product recited in claim 10, wherein said portion for searching said first row for a second cell comprises a portion for examining the cells of said first row by stepping through the cells in an inward direction from an end of said first row opposite the end from which said first cell was identified.

14. The computer product recited in claim 10, wherein said portion for searching a second row for a third cell comprises a portion for examining the cells of said second row by stepping through the cells in an inward direction from an end of said second row that coincides with the end of said first row from which said first cell was identified.

15. The computer product recited in claim 14, wherein said portion for searching said second row for a fourth cell comprises a portion for examining the cells of said second row by stepping through the cells in an inward direction from an end of said second row opposite the end of said second row from which said third cell was identified.

16. The computer product recited in claim 10 further comprising:

a portion for constructing a first line on the image in accordance with parametric data associated with said first cell;

a portion for constructing a second line on the image in accordance with parametric data associated with said second cell;

a portion for constructing a third line on the image in accordance with parametric data associated with said third cell;

a portion for constructing a fourth line on the image in accordance with parametric data associated with said fourth cell;

a portion for identifying intersections of said first, second, third, and fourth lines as indicating corners of the object; and

a portion for identifying portions of said first, second, third, and fourth lines extending between said intersections as indicating edges of the object.

17. The computer product recited in claim 10 further comprising:

a portion for constructing three lines on said image in accordance with parametric data associated with three of said first, second, third, and fourth cells of the array;

a portion for constructing a fourth line on said image, said fourth line being estimated from the parametric data used to construct said three lines;

a portion for identifying intersections of said three lines and said fourth line as indicating corners of the object; and

a portion for identifying portions of said lines extending between said intersections of said lines as indicating edges of the object.

18. The computer product recited in claim 10, wherein the selected first cell and any identified second, third, or fourth cell associated with the selected first cell comprise a solution set for the edges of the object in the image, said computer product further comprising:

a portion for identifying solution sets for selected first cells;

a portion for assigning a confidence value to said solution sets, said confidence value being calculated as a function of parametric data associated with each cell in the solution set; and

a portion for identifying one of said solution sets as including cells indicative of edges of the object, said solution set being identified as a function of said confidence value.

19. A method for identifying edges of an object in a graphical image by analyzing a Hough image of the graphical image, said method comprising the steps of:

searching the Hough image from a first edge of the Hough image towards the center of the Hough image for a first potential edge line in the graphical image;

searching the Hough image from a second edge of the Hough image opposite the first edge towards the center of the Hough image for a second potential edge line in the graphical image extending parallel to said first potential edge line;

searching the Hough image from a third edge of the Hough image transverse the first and second edges towards the center of the Hough image for a third potential edge line in the graphical image extending perpendicular to said first potential edge line;

searching the Hough image from a fourth edge of the Hough image opposite the third edge towards the center of the Hough image for a fourth potential edge line in the graphical image extending parallel to said third potential edge line.

20. The method recited in claim 19, wherein said Hough image comprises an accumulator array comprising a plurality of rows each including a plurality of cells;

said step of searching for a first potential edge line comprising the step of searching a first row of the array from a first end of the first row toward a center of the first row for a first cell indicative of said first edge line;

said step of searching for a second potential edge line comprising the step of searching said first row of the array from a second end of the first row opposite the first end of the first row toward a center of the first row for a second cell indicative of said second edge line;

said step of searching for a third potential edge line comprising the step of searching a second row of the array shifted ninety degrees from said first row of the array from a first end of the second row toward a center of the second row for a third cell indicative of said third edge line; and

said step of searching for a fourth potential edge line comprising the step of searching said second row of the array from a second end of the second row opposite the first end of the second row toward a center of the second row for a fourth cell indicative of said fourth edge line.