Object edge point filtering system for machine vision

• US 5,796,868 A
• Filed: 12/28/1995
• Issued: 08/18/1998
• Est. Priority Date: 12/28/1995
• Status: Expired due to Term

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Dutta-Choudhury, Paul
• Primary Examiner(s): SHALWALA, BIPIN H
• Application Number:
  US08/579,958
• Time in Patent Office: 964 Days
• Field of Search: 382/199, 382/103, 382/106, 382/151, 382/553, 382/201, 382/203, 382/204, 382/206, 382/260, 382/261, 382/262, 382/263, 382/265, 382/266, 382/270, 382/281, 382/308, 707/521, 711/118, 711/132, 345/418, 345/515, 345/516, 395/80
• US Class Current: 382/199
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20061 Hough transform
• CPC Class Codes: G06T 2207/20081 Training; Learning
• CPC Class Codes: G06T 7/12 Edge-based segmentation

Abstract

A system and method for filtering edge points in an edge image represented by an array of edge image coordinates each having an edge point magnitude. An edge map array is formed of edge map coordinates each assigned one of three edge indicator values indicative of the relationship between the corresponding edge image coordinate edge point magnitude and two preselected edge magnitude thresholds. An output edge point array is formed of output edge point coordinates to indicate those edge image coordinates and corresponding object image pixels that are validated by the system as being associated with likely object edge points. This is accomplished by constructing a first address stack to track memory addresses at which edge map coordinate values are stored and constructing a second address stack to track memory addresses at which output edge point coordinate values are stored as the output edge point array is constructed. Selected output edge point coordinates are assigned with a preselected edge point value by first scanning the edge map array for edge coordinates assigned the first preselected edge indicator value and, using the stacks to keep track of the addresses of these coordinates, neighboring edge map coordinates are examined for any edge map coordinates assigned with either the first or second preselected edge indicator values. The address of edge map coordinates found to be assigned with either the first or second preselected edge indicator values are then tracked by the stacks.

Claims

1. A method for filtering possible edge points in an edge image represented by an array of edge image coordinates each having an edge point magnitude in a preselected range of edge point magnitudes, the edge image corresponding to an image of an object represented by an array of pixels, comprising the steps of:

a. forming an edge map array of edge map coordinates arranged in correspondence with the edge image, each edge map coordinate assigned one of three preselected edge indicator values indicative of a relationship between the corresponding edge image coordinate edge point magnitude and two preselected edge point magnitude thresholds, the assigned edge map coordinate values being stored in an addressable memory;

b. forming an output edge point array of output edge point coordinates arranged in correspondence with the edge image, comprising the steps of;

c. initializing each output edge point coordinate to a first of two preselected edge point values, the initialized coordinate values being stored in an addressable memory;

d. constructing a first address stack to track memory addresses at which edge map coordinate values in the edge map array are stored;

e. constructing a second address stack to track memory addresses at which output edge point coordinate values in the output edge point array are stored;

f. assigning to selected of the initialized output edge point coordinates the second preselected edge point value, comprising the steps of;

g. scanning the edge map array for an edge map coordinate assigned the first preselected edge indicator value;

h. pushing on the first stack the edge map array address of a first encountered edge map coordinate assigned the first preselected edge indicator value;

i. pushing on the second stack the output edge point array address corresponding to the edge map array address pushed on the first stack in step h;

j. popping off of the first and second stacks the edge map coordinate address and corresponding output edge point coordinate address, respectively most recently pushed on the stacks;

k. assigning to the edge map coordinate whose address was popped off of the first stack in step j the third edge indicator value;

l. assigning to the output edge point coordinate whose address was popped off the second stack in step j the second preselected edge point value;

m. examining edge map coordinates in the edge map array that neighbor the edge map coordinate whose address was popped off the first stack in step j for any edge map coordinates assigned either the first or second preselected edge indicator values;

n. pushing on the first stack addresses of edge map coordinates found in step m to be assigned either the first or second preselected edge indicator values;

o. pushing on the second stack the output edge point coordinate address corresponding to any edge map array address pushed on the first stack in step n;

p. repeating steps j-o until all addresses are popped off the first and second stacks;

q. repeating steps g-p until the edge map array is entirely scanned, those selected output edge point coordinates in the resulting output edge point array assigned with the second preselected edge point value each representing a likely edge point in the object image.

2. The method of claim 1 wherein the two preselected edge point magnitude thresholds comprise a high magnitude threshold and a low magnitude threshold less than the high magnitude threshold.

3. The method of claim 2 wherein the three preselected edge indicator values comprise a first edge indicator value for indicating that an edge magnitude in the edge image is greater than the high edge magnitude threshold, a second edge indicator value for indicating that an edge magnitude in the edge image is equal to or less than the high edge magnitude threshold but greater than or equal to the low edge magnitude threshold, and a third edge indicator value for indicating that an edge magnitude in the edge image is less than the low edge magnitude threshold.

4. The method of claim 3 wherein the two preselected edge point values comprise a first edge point value for indicating that an output edge point coordinate does not likely represent an edge point in the object image, and a second edge point value for indicating that an output edge point coordinate does likely represent an edge point in the object image.

5. The method of claim 1 wherein the steps of constructing first and second stacks each further comprise the steps of determining the number of edge map coordinates in the edge map array assigned either the first or second preselected edge indicator values, and allocating a number of entries in each stack equal to at least the number of edge map coordinates assigned the either the first or second preselected edge indicator values.

6. The method of claim 1 wherein the steps of constructing first and second stacks each further comprise the steps of determining the total number of edge map coordinates in the edge map array, and allocating a number of entries in each stack equal to at least the total number of edge map coordinates.

7. The method of claim 1 wherein the step of examining edge map coordinates in the edge map array that neighbor the edge map coordinate whose address was popped off the first stack in step j comprises examining each of eight edge map coordinates that are closest neighbors to the edge map coordinate whose address was popped off the first stack.

8. The method of claim 1 wherein the step of forming an edge map array further comprises providing the edge map array with bounding rows and columns of edge map coordinates that together surround the array, each edge map coordinate in the bounding rows and columns assigned the third preselected edge indicator value.

9. The method of claim 1 wherein the step of scanning the edge map array for an edge map coordinate assigned the first preselected edge indicator value comprises the steps of forming a packet of digital bits representative of consecutive edge map coordinates in a row of the edge map array, and examining the packet of digital bits for the first preselected edge indicator value.

10. The method of claim 9 wherein each edge map coordinate value comprises a number, n, of bits, and the packet of digital bits includes an integer multiple of the number, n, of bits.

11. The method of claim 1 wherein the step of assigning to the edge map coordinate whose address was popped off of the first stack in step j the third edge indicator value, the step of assigning to the output edge point coordinate whose address was popped off the second stack in step j the second preselected edge point value, the step of examining edge map coordinates in the edge map array that neighbor the edge map coordinate whose address was popped off the first stack in step j, and the step of pushing on the first stack the address of any neighbor edge map coordinates found to be assigned either the first or second preselected edge indicator values together comprise the steps of:

examining edge map coordinates in the same row as the popped edge map coordinate address to locate edge map coordinates in that row assigned either the first or second preselected edge indicator values and located in an unbroken sequence including the edge map coordinate whose address was popped, and assigning to any such located coordinates and the popped edge map coordinate the third preselected edge indicator value, with the corresponding output edge point array coordinates assigned the second edge point value;

examining edge map coordinates in the row just above and the row just below the popped edge map coordinate beginning with an edge map coordinate in each of these rows that has an address one less than a leftmost edge map coordinate identified in the unbroken sequence and ending with an edge map coordinate in each of these rows that has an address one greater than a rightmost edge map coordinate identified in the unbroken sequence and based on the examination pushing on the first stack the address of each examined edge map coordinate in above and below rows that is both assigned either the first or second preselected edge indicator values and is either a first edge map coordinate examined in a given row or is located after an edge map coordinate assigned the third preselected edge indicator value.

12. The method of claim 1 further comprising the step of forming an edge point template representing an image of likely edge points in the object image based on the output edge point array.

13. The method of claim 1 further comprising the step of forming an edge point address list of the memory addresses corresponding to the output edge point array coordinates in the output edge point array assigned the second preselected edge point value.

14. The method of claim 1 further comprising the step of forming an edge point angle map array of edge angle values arranged in correspondence with the edge image, the edge angle values representing the angular orientation of corresponding output edge points in the output edge point array.

15. The method of claim 1 further comprising the step of forming the edge image by performing Sobel edge detection analysis on the object image.

16. The method of claim 1 further comprising the step of forming a filtered object image by setting to zero all pixels in a copy of the object image that correspond to output edge point coordinates in the output edge point array assigned with the first preselected edge point value.

17. A system for filtering possible edge points in an edge image represented by an array of edge image coordinates each having an edge point magnitude in a preselected range of edge point magnitudes, the edge image corresponding to an image of an object represented by an array of pixels, comprising:

means for forming an edge map array of edge map coordinates arranged in correspondence with the edge image array, each edge map coordinate assigned one of three preselected edge indicator values indicative of a relationship between the corresponding edge image coordinate edge point magnitude and two preselected edge threshold values, the assigned edge map coordinate values being stored in an addressable memory;

means for forming an output edge point array of output edge point coordinates arranged in correspondence with the edge image,

means for initializing each output edge point coordinate to a first of two preselected edge point values, the initialized output edge point coordinate values being stored in an addressable memory;

a first address stack for tracking memory addresses at which edge map coordinate values in the edge map array are stored;

a second address stack for tracking memory addresses at which output edge point coordinate values in the output edge point array are stored;

means for assigning to selected initialized output edge point coordinates the second preselected edge point value,

means for scanning the edge map array for an edge map coordinate assigned the first preselected edge indicator value;

means for pushing on the first stack the edge map array address of a first encountered edge map coordinate assigned the first preselected edge indicator value;

means for pushing on the second stack the output edge point array address corresponding to the edge map array address pushed on the first stack;

means for popping off of the first and second stacks the edge map coordinate address and corresponding output edge point coordinate address, respectively most recently pushed on the stacks;

means for assigning to the edge map coordinate whose address was popped off of the first stack the third edge indicator value;

means for assigning to the output edge point coordinate whose address was popped off the second stack the second preselected edge point value;

means for examining edge map coordinates in the edge map array that neighbor the edge map coordinate whose address was popped off the first stack for any edge map coordinates assigned either the first or second preselected edge indicator values;

means for pushing on the first stack addresses of edge map coordinates found to be assigned either the first or second preselected edge indicator values;

means for pushing on the second stack the output edge point coordinate address corresponding to any edge map array address pushed on the first stack, those selected output edge points in the resulting output edge point array assigned with the second preselected edge point value each representing a likely edge point in the object image.

18. The system of claim 17 wherein the two preselected edge point magnitude thresholds comprise a high magnitude threshold and a low magnitude threshold less than the high magnitude threshold.

19. The system of claim 18 wherein the three preselected edge indicator values comprise a first edge indicator value for indicating that an edge point magnitude in the edge image is greater than the high edge point magnitude threshold, a second edge indicator value for indicating that an edge point magnitude in the edge image is equal to or less than the high edge point magnitude threshold but greater than or equal to the low edge point magnitude threshold, and a third edge indicator value for indicating that an edge point magnitude in the edge image is less than the low edge point magnitude threshold.

20. The system of claim 19 wherein the two preselected edge point values comprise a first edge point value for indicating that an output edge point coordinate does not likely represent an edge point in the object image, and a second edge point value for indicating that an output edge point coordinate does likely represent an edge point in the object image.

21. The system of claim 17 wherein the first and second stacks are each allocated with a number of stack entries equal to at least the number of edge map coordinates in the edge map array that are each assigned either the first or second preselected edge indicator values.

22. The system of claim 17 wherein the first and second stacks are each allocated with a number of stack entries equal to at least the total number of edge map coordinates in the edge map array.

23. The system of claim 17 wherein the means for examining edge map coordinates in the edge map array that neighbor the edge map coordinate whose address was popped off the first stack comprises means for examining each of eight edge map coordinates that are closest neighbors to the edge map coordinate whose address was popped off the first stack.

24. The system of claim 17 wherein the means for forming an edge map array further comprises means for providing the edge map array with bounding rows and columns of edge map coordinates that together surround the array, each edge map coordinate in the bounding rows and columns being assigned the third preselected edge indicator value.

25. The system of claim 17 wherein the means for scanning the edge map array for an edge map coordinate assigned the first preselected edge indicator value comprises means for forming a packet of digital bits representative of consecutive edge map coordinates in a row of the edge map array, and examining the packet of digital bits for the first preselected edge indicator value.

26. The system of claim 25 wherein each edge map coordinate value comprises a number, n, of bits, and the packet of digital bits includes an integer multiple of the number, n, of bits.

27. The system of claim 17 wherein the means for assigning to the edge map coordinate whose address was popped off of the first stack the third edge indicator value, the means for assigning to the output edge point coordinate whose address was popped off the second stack the second preselected edge point value, the means for examining edge map coordinates in the edge map array that neighbor the edge map coordinate whose address was popped off the first stack, and the means for pushing on the first stack the address of any neighbor edge map coordinates found to be assigned with either the first or second preselected edge indicator values together comprise:

means for examining edge map coordinates in the same row as the popped edge map coordinate address to locate edge map coordinates in that row assigned either the first or second preselected edge indicator values and located in an unbroken sequence including the edge map coordinate whose address was popped, assigning to any such located coordinates and the popped edge map coordinate the third preselected edge indicator value, with the corresponding output edge point array coordinates assigned the second edge point value;

means for examining edge map coordinates in the row just above and the row just below the popped edge map coordinate address beginning with an edge map coordinate in each of these rows that has an address one less than a leftmost edge coordinate identified in the unbroken sequence and ending with an edge map coordinate in each of these rows that has an address one greater than a rightmost edge map coordinate identified in the unbroken sequence; and

means for pushing on the first stack, based on the examination, the address of each examined edge map coordinated in above and below rows that is both assigned either the first or second preselected edge indicator values and is either a first map coordinate examined in a given row or is located after an edge map coordinate assigned the third preselected edge indicator value.

28. The system of claim 17 further comprising means for forming an edge point template representing an image of likely edge points in the object image based on the output edge point array.

29. The system of claim 17 further comprising means for forming an edge point address list of the memory addresses corresponding to the output edge point coordinates in the output edge point array assigned the second preselected edge point value.

30. The system of claim 17 further comprising means for forming an edge point angle map array of edge angle values arranged in correspondence with the edge image, the edge angle values representing the angular orientation of corresponding output edge points in the output edge point array.

31. The system of claim 17 further comprising a Sobel edge detector for analyzing the object image to produce the edge image.

32. The system of claim 17 further comprising means for forming a filtered object image in which all pixels in a copy of the object image that correspond to coordinates in the output edge point array assigned with the first preselected edge point value are set to zero.