System and method for performing edge detection in an image

• US 20030053696A1
• Filed: 06/28/2001
• Published: 03/20/2003
• Est. Priority Date: 06/28/2001
• Status: Active Grant

• Current Assignee: National Instruments Corporation (Emerson Electric Company)
• Original Assignee: National Instruments Corporation (Emerson Electric Company)
• Inventors: Nair, Dinesh, Wenzel, Lothar, Rajagopal, Ram, Schmidt, Darren
• Granted Patent: US 7,013,047 B2
• Time in Patent Office: Days
• US Class Current: 382/199
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/149 involving deformable models, e.g. active contour models
• 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

Abstract

A system and method for performing a curve fit on a plurality of data points. In an initial phase, a subset P_max of the plurality of points which represents an optimal curve is determined. This phase is based on a statistical model which dictates that after trying at most N_min random curves, each connecting a randomly selected two or more points from the input set, one of the curves will pass within a specified radius of the subset P_max of the input points. The subset P_max may then be used in the second phase of the method, where a refined curve fit is made by iteratively culling outliers from the subset P_max with respect to a succession of optimal curves fit to the modified subset P_max at each iteration. The refined curve fit generates a refined curve, which may be output along with a final culled subset K_final of P_max.

Claims

1. A computer-implemented method for performing edge detection in an image comprising a plurality of pixels, the method comprising:

a) receiving the plurality of pixels;

b) generating a curve based on two or more random pixels of the plurality of pixels;

c) testing the curve against a first subset of the plurality of pixels, wherein said testing produces first test results;

d) if said first test results meet first criteria, outputting information regarding the curve, wherein the curve comprises a detected edge in the image.

2. The method of claim 1, wherein the method comprises performing (b) and (c) a plurality of times to determine a curve which meets the first criteria.

3. The method of claim 2, wherein said performing (b) and (c) a plurality of times comprises performing (b) and (c) in an iterative manner until ending criteria are met.

4. The method of claim 3, wherein said ending criteria comprise one or more of:

the number of iterations meeting or exceeding an iteration threshold; and

a number of pixels of the plurality of pixels within a specified pixel radius of the curve meeting or exceeding a specified minimum value.

5. The method of claim 1, further comprising:

pre-testing the curve against a second subset of the plurality of pixels, wherein said testing produces second test results;

wherein, if said second test results meet second criteria, then performing c) and d).

6. The method of claim 5, wherein the second subset is smaller than the first subset.

7. The method of claim 5, wherein the second subset is a random subset comprising randomly selected pixels from the plurality of pixels.

8. The method of claim 7, further comprising:

randomizing the plurality of pixels after said receiving to generate a randomized list of the plurality of pixels;

wherein said randomly selected pixels from the plurality of pixels are selected by traversing the randomized list.

9. The method of claim 8, wherein said randomizing the plurality of pixels further comprises selecting a random starting position in the randomized list, and wherein said traversing the randomized list comprises traversing the randomized list starting at the random starting position.

10. The method of claim 5, wherein said pre-testing the curve against a second subset of the plurality of pixels comprises:

determining a number of the second subset of the plurality of pixels which are within the specified pixel radius of the curve;

wherein said second test results comprise said number of the second subset of the plurality of pixels which are within the specified pixel radius of the curve.

11. The method of claim 10, wherein said second criteria comprise said number of the second subset of the plurality of pixels which are within the specified pixel radius of the curve meeting or exceeding a threshold value.

12. The method of claim 10, wherein said second criteria comprise said number of the second subset of the plurality of pixels which are within the specified pixel radius of the curve meeting or exceeding a specified fraction of the second subset.

13. The method of claim 1, wherein said testing the curve against a first subset of the plurality of pixels comprises:

determining a number of the first subset of the plurality of pixels which are within the specified pixel radius of the curve;

wherein said first test results comprise said number of the first subset of the plurality of pixels which are within the specified pixel radius of the curve.

14. The method of claim 13, wherein said first criteria comprise said number of the first subset of the plurality of pixels which are within the specified pixel radius of the curve meeting or exceeding a specified fraction of the first subset.

15. The method of claim 1, wherein the first subset comprises substantially all of the plurality of pixels.

16. The method of claim 1, wherein said outputting information comprises displaying the generated curve on a display device.

17. The method of claim 1, wherein the curve comprises one of a line, a circle, and an ellipse.

18. The method of claim 1, further comprising:

performing a refined curve fit, wherein the refined curve fit is performed using a second subset of the plurality of pixels comprising pixels within said specified pixel radius of the curve, wherein the refined curve fit comprises iteratively culling outlying pixels from the second subset, generating a culled subset of pixels, and fitting a refined curve to the culled subset at each iteration until an ending condition is met, wherein the refined curve fit generates a refined curve, and

generating output, comprising one or more of information regarding the refined curve, and the culled subset of the plurality of pixels.

19. The method of claim 18, wherein said performing a refined curve fit comprises:

calculating a maximum error allowed for the refined curve fit based on the specified pixel radius;

removing one or more pixels from the second subset, wherein said one or more pixels are furthest from curve, thereby generating a culled subset;

fitting a curve to the culled subset;

calculating an error for the curve on the culled subset;

repeating said removing, said fitting, and said calculating one or more times to generate a refined curve; and

generating result output, wherein said result output comprises one or more of;

the culled subset;

the refined curve, wherein the refined curve comprises a refined detected edge in the image;

the error for the curve on the culled subset;

a score, indicating the fitness of the refined curve with respect to the plurality of pixels; and

the plurality of pixels.

20. The method of claim 1, wherein the image has a dimensionality greater than two.

21. A computer-implemented method for detecting an edge in an image comprising a plurality of pixels, the method comprising:

a) receiving the plurality of pixels;

b) performing the following steps c) through f) in an iterative manner;

c) generating a curve based on two or more random pixels of the plurality of pixels;

d) pre-testing the curve against a first random subset of the plurality of pixels, wherein said testing produces first test results;

e) if said first test results meet first criteria, testing the curve against a second subset of the plurality of pixels, thereby generating second test results;

f) if said second test results meet second criteria, storing information regarding the curve; and

g) outputting said information regarding the curve, wherein the curve comprises a detected edge in the image.

22. The method of claim 21, further comprising:

randomizing the order of the plurality of pixels before said performing to produce a randomized list of the plurality of pixels;

wherein said first random subset is selected by traversing said randomized list.

23. The method of claim 22, wherein said randomizing the plurality of pixels further comprises selecting a random starting position in the randomized list, and wherein said traversing the randomized list comprises traversing the randomized list from the random starting position.

24. The method of claim 21, wherein second subset substantially comprises pixels which are not in said first subset.

25. The method of claim 21, wherein said performing the steps c) through f) in an iterative manner comprises performing the steps c) through f) in an iterative manner until third criteria are met.

26. The method of claim 25, wherein said third criteria comprise one or more of:

the number of iterations meeting or exceeding an iteration threshold; and

a number of pixels of the plurality of pixels within a specified pixel radius of the curve meeting or exceeding a specified minimum value.

27. The method of claim 21, wherein the first subset is smaller than the second subset.

28. The method of claim 21, wherein said pre-testing the curve against a first subset of the plurality of pixels comprises:

determining a number of the first subset of the plurality of pixels which are within a specified pixel radius of the curve;

wherein said first test results comprise said number of the first subset of the plurality of pixels which are within the specified pixel radius of the curve.

29. The method of claim 28, wherein said first criteria comprise said number of the first subset of the plurality of pixels which are within the specified pixel radius of the curve meeting or exceeding a threshold value.

30. The method of claim 28, wherein said first criteria comprise said number of the first subset of the plurality of pixels which are within the specified pixel radius of the curve meeting or exceeding a specified fraction of the first subset.

31. The method of claim 28, wherein said testing the curve against the second subset of the plurality of pixels comprises:

determining a number of the second subset of the plurality of pixels which are within a specified pixel radius of the curve;

wherein said second test results comprise said number of the second subset of the plurality of pixels which are within the specified pixel radius of the curve.

32. The method of claim 31, wherein said second criteria comprise said number of the second subset of the plurality of pixels which are within the specified pixel radius of the curve meeting or exceeding a specified fraction of the second subset.

33. The method of claim 31, wherein said second criteria comprise said number of the second subset of the plurality of pixels which are within the specified pixel radius of the curve plus said number of the first subset of the plurality of pixels which are within the specified pixel radius of the curve meeting or exceeding a specified fraction of the plurality of pixels.

34. The method of claim 21, wherein said outputting information comprises displaying the detected edge on a display device.

35. The method of claim 21, wherein information regarding the curve comprises one or more of:

one or more parameters defining the curve;

a third subset of the plurality of pixels, comprising pixels which are within a specified pixel radius of the curve.

36. The method of claim 21, wherein the curve comprises one of a line, a circle, and an ellipse.

37. The method of claim 21, wherein the image has a dimensionality greater than two.

38. The method of claim 21, further comprising:

performing a refined curve fit, wherein the refined curve fit is performed using a third subset of the plurality of pixels comprising pixels within a specified pixel radius of the curve, wherein performing the refined curve fit comprises iteratively culling outlying pixels from the third subset, generating a culled subset of pixels, and fitting a refined curve to the culled subset at each iteration until an ending condition is met, thereby generating a refined curve, and

generating output, comprising one or more of information regarding the generated refined curve, and the culled subset of the plurality of pixels, wherein the generated refined curve comprises a refined detected edge in the image.

39. The method of claim 38, wherein said performing a refined curve fit comprises:

calculating a maximum error allowed for the refined curve fit based on the specified pixel radius;

fitting a curve to the third subset of pixels;

removing one or more pixels from the third subset, wherein said one or more pixels are furthest from the curve, thereby generating a culled subset;

fitting a curve to the culled subset;

calculating an error for the curve on the culled subset;

repeating said removing, said fitting, and said calculating one or more times to generate a refined curve; and

generating result output, wherein said result output comprises one or more of;

the culled subset;

the generated refined curve, wherein the generated refined curve comprises a refined detected edge in the image;

the calculated error for the curve on the culled subset;

a score, indicating the fitness of the refined curve with respect to the plurality of pixels; and

the plurality of pixels.

40. A computer-implemented method for detecting an edge in an image comprising a plurality of pixels, the method comprising:

a) receiving the plurality of pixels, P;

b) randomizing the order of the plurality of pixels P;

c) performing the following steps d) through j) in an iterative manner;

d) selecting two or more pixels from P;

e) generating a curve using the two or more pixels, wherein said generating comprises calculating two or more parameters defining the curve;

f) selecting a subset P_m of P, wherein P_m comprises M pixels;

g) determining and recording a subset P_j of P_m, wherein P_j comprises J pixels in P_m whose distance from the curve is less than or equal to a specified pixel radius.

h) if a ratio of J to M exceeds a threshold, updating the recorded subset P_j and J to include all pixels in P whose distance from the curve is less than or equal to the specified pixel radius;

i) if J exceeds all values of J calculated in previous iterations, recording the subset P_j as a subset P_max, comprising J_max pixels, and recording the two or more parameters defining the curve, wherein the curve comprises an estimated fit to the plurality of pixels, P;

j) testing for criteria to end said iterating; and

k) generating output, wherein said output comprises the subset P_max, and said two or more parameters defining the generated curve;

wherein said criteria comprise one or more of;

the number of iterations meeting or exceeding an iteration threshold; and

the value of J_max meeting or exceeding a minimum pixel count; and

wherein the generated curve comprises a detected edge in the image.

41. The method of claim 40, wherein said at least two pixels comprise N_c pixels, and wherein said performing a refined curve fit comprises:

l) calculating a maximum error err_max allowed for the refined curve fit based on the specified pixel radius;

m) setting an optimal set of pixels K₀ to P_max;

n) fitting an initial curve L₀ to the optimal set of pixels K₀;

o) calculating an error err₀ for the initial curve L₀ on K₀;

p) determining if an ending condition is true;

q) if said ending condition is not true, performing the following steps r) through u) iteratively, until said ending condition is true, wherein K_i is a state of the set K₀ at each iteration i, and L_i is a corresponding line fitted to K_i;

r) removing P_i pixels from K_i, wherein said P_i pixels are furthest from curve L_i, thereby generating subset K_i+1 or K_i;

s) fitting a curve L_i+1 to subset K_i+1;

t) calculating an error err_i+1 for the curve L_i+1 on subset K₁₊1;

u) incrementing i;

wherein said ending condition comprises one or more of;

err_i meeting or exceeding err_max; and

a count of K_i being equal to N_c;

v) calculating a score s_final of a final curve L_final on a final subset K_final, wherein L_final and subset K_final comprise final states of L_i and K_i, respectively; and

w) calculating an error err_final of the curve L_final on the plurality of pixels P;

x) generating result output, wherein said result output comprises one or more of;

the final subset K_final;

the size of K_final;

the curve L_final, comprising a refined detected edge in the image;

the score s_final; and

the plurality of pixels P.

42. A memory medium operable to store program instructions for performing edge detection in a received image comprising a plurality of pixels, wherein the program instructions are executable to perform:

a) generating a curve based on two or more random pixels of the plurality of pixels;

b) testing the curve against a first subset of the plurality of pixels, wherein said testing produces first test results;

c) if said first test results meet first criteria, outputting information regarding the curve, wherein the curve comprises a detected edge in the image.

43. The memory medium of claim 42, wherein the program instructions are further executable to perform (a) and (b) a plurality of times to determine a curve which meets the first criteria.

44. The memory medium of claim 42, wherein the program instructions are further executable to perform:

pre-testing the curve against a second subset of the plurality of pixels, wherein said testing produces second test results, wherein said second subset is a random subset comprising randomly selected pixels from the plurality of pixels;

wherein, if said second test results meet second criteria, then performing b) and c).

45. The memory medium of claim 44, wherein the program instructions are further executable to perform:

randomizing the plurality of pixels after said receiving to generate a randomized list of the plurality of pixels;

wherein said randomly selected pixels from the plurality of pixels are selected by traversing the randomized list.

46. The memory medium of claim 44,

wherein said pre-testing the curve against a second subset of the plurality of pixels comprises determining a number of the second subset of the plurality of pixels which are within a specified pixel radius of the curve;

wherein said second test results comprise said number of the second subset of the plurality of pixels which are within the specified pixel radius of the curve;

wherein said second criteria comprise said number of the second subset of the plurality of pixels which are within the specified pixel radius of the curve meeting or exceeding a threshold value;

wherein said testing the curve against a first subset of the plurality of pixels comprises determining a number of the first subset of the plurality of pixels which are within the specified pixel radius of the curve;

wherein said first test results comprise said number of the first subset of the plurality of pixels which are within the specified pixel radius of the curve; and

wherein said first criteria comprise said number of the first subset of the plurality of pixels which are within the specified pixel radius of the curve meeting or exceeding a threshold value.

47. The memory medium of claim 42, wherein the program instructions are further executable to perform:

performing a refined curve fit, wherein the refined curve fit is performed using a second subset of the plurality of pixels comprising pixels within said specified pixel radius of the curve, wherein the refined curve fit comprises iteratively culling outlying pixels from the second subset, generating a culled subset of pixels, and fitting a refined curve to the culled subset at each iteration until an ending condition is met, wherein the refined curve fit generates a refined curve, and

generating output, comprising one or more of information regarding the refined curve, and the culled subset of the plurality of pixels, wherein the curve comprises a refined detected edge in the image.

48. A memory medium operable to store program instructions for performing edge detection in an image comprising a plurality of pixels, wherein the program instructions are executable to perform:

a) performing the following steps b) through e) in an iterative manner;

b) generating a curve based on two or more random pixels of the plurality of pixels;

c) pre-testing the curve against a first random subset of the plurality of pixels, wherein said testing produces first test results;

d) if said first test results meet first criteria, testing the curve against a second subset of the plurality of pixels, thereby generating second test results;

e) if said second test results meet second criteria, storing information regarding the curve; and

f) outputting said information regarding the curve, wherein the curve comprises a detected edge in the image.

49. The memory medium of claim 48, wherein the program instructions are further executable to perform:

randomizing the order of the plurality of pixels before said performing to produce a randomized list of the plurality of pixels;

wherein said first random subset is selected by traversing said randomized list.

50. The memory medium of claim 48,

wherein said pre-testing the curve against a first subset of the plurality of pixels comprises determining a number of the first subset of the plurality of pixels which are within a specified pixel radius of the curve;

wherein said first test results comprise said number of the first subset of the plurality of pixels which are within the specified pixel radius of the curve;

wherein said first criteria comprise said number of the first subset of the plurality of pixels which are within the specified pixel radius of the curve meeting or exceeding a first threshold value;

wherein said testing the curve against the second subset of the plurality of pixels comprises determining a number of the second subset of the plurality of pixels which are within the specified pixel radius of the curve;

wherein said second test results comprise said number of the second subset of the plurality of pixels which are within the specified pixel radius of the curve; and

wherein said second criteria comprise said number of the second subset of the plurality of pixels which are within the specified pixel radius of the curve meeting or exceeding a second threshold value.

51. The memory medium of claim 50, wherein said second criteria further comprise said number of the second subset of the plurality of pixels which are within the specified pixel radius of the curve plus said number of the first subset of the plurality of pixels which are within the specified pixel radius of the curve meeting or exceeding the specified second threshold value.

52. The memory medium of claim 48, wherein the program instructions are further executable to perform:

performing a refined curve fit, wherein the refined curve fit is performed using a third subset of the plurality of pixels comprising pixels within a specified pixel radius of the curve, wherein performing the refined curve fit comprises iteratively culling outlying pixels from the third subset, generating a culled subset of pixels, and fitting a refined curve to the culled subset at each iteration until an ending condition is met, thereby generating a refined curve, and

generating output, comprising one or more of information regarding the generated refined curve, and the culled subset of the plurality of pixels, wherein the curve comprises a refined detected edge in the image.

53. A computer based system for performing edge detection in an image comprising a plurality of pixels, the system comprising:

a CPU;

a memory medium coupled to the CPU, wherein the memory is operable to store program instructions for performing edge detection, and wherein the CPU is operable to execute the program instructions; and

an input which is operable to receive the plurality of pixels;

wherein the program instructions are executable by the CPU to perform;

a) generating a curve based on two or more random pixels of the plurality of pixels;

b) testing the curve against a first subset of the plurality of pixels, wherein said testing produces first test results;

c) if said first test results meet first criteria, outputting information regarding the curve, wherein the refined curve comprises a detected edge in the image.

54. The system of claim 53, wherein the program instructions are further executable by the CPU to perform (a) and (b) a plurality of times to determine a curve which meets the first criteria.

55. The system of claim 53, wherein the program instructions are further executable by the CPU to perform:

pre-testing the curve against a second subset of the plurality of pixels, wherein said testing produces second test results, wherein said second subset is a random subset comprising randomly selected pixels from the plurality of pixels;

wherein, if said second test results meet second criteria, then performing b) and c).

56. The system of claim 55, wherein the program instructions are further executable by the CPU to perform:

randomizing the plurality of pixels after said receiving to generate a randomized list of the plurality of pixels;

wherein said randomly selected pixels from the plurality of pixels are selected by traversing the randomized list.

57. The system of claim 55,

wherein said pre-testing the curve against a second subset of the plurality of pixels comprises determining a number of the second subset of the plurality of pixels which are within a specified pixel radius of the curve;

wherein said second test results comprise said number of the second subset of the plurality of pixels which are within the specified pixel radius of the curve;

wherein said second criteria comprise said number of the second subset of the plurality of pixels which are within the specified pixel radius of the curve meeting or exceeding a threshold value;

wherein said testing the curve against a first subset of the plurality of pixels comprises determining a number of the first subset of the plurality of pixels which are within the specified pixel radius of the curve;

wherein said first test results comprise said number of the first subset of the plurality of pixels which are within the specified pixel radius of the curve; and

wherein said first criteria comprise said number of the first subset of the plurality of pixels which are within the specified pixel radius of the curve meeting or exceeding a threshold value.

58. The system of claim 53, wherein the program instructions are further executable by the CPU to perform:

performing a refined curve fit, wherein the refined curve fit is performed using a second subset of the plurality of pixels comprising pixels within said specified pixel radius of the curve, wherein the refined curve fit comprises iteratively culling outlying pixels from the second subset, generating a culled subset of pixels, and fitting a refined curve to the culled subset at each iteration until an ending condition is met, wherein the refined curve fit generates a refined curve, and

generating output, comprising one or more of information regarding the refined curve, and the culled subset of the plurality of pixels, wherein the refined curve comprises a refined detected edge in the image.

59. A computer based system for performing a curve fit, comprising:

a CPU;

a memory medium coupled to the CPU, wherein the memory is operable to store program instructions, and wherein the CPU is operable to execute the program instructions; and

an input which is operable to receive a plurality of pixels;

wherein the program instructions are executable by the CPU to perform;

a) performing the following steps b) through e) in an iterative manner;

b) generating a curve based on two or more random pixels of the plurality of pixels;

c) pre-testing the curve against a first random subset of the plurality of pixels, wherein said testing produces first test results;

d) if said first test results meet first criteria, testing the curve against a second subset of the plurality of pixels, thereby generating second test results;

e) if said second test results meet second criteria, storing information regarding the curve; and

f) outputting said information regarding the curve, wherein the curve comprises a detected edge in the image.

60. The system of claim 59, wherein the program instructions are further executable by the CPU to perform:

randomizing the order of the plurality of pixels before said performing to produce a randomized list of the plurality of pixels;

wherein said first random subset is selected by traversing said randomized list.

61. The system of claim 59,

wherein said pre-testing the curve against a first subset of the plurality of pixels comprises determining a number of the first subset of the plurality of pixels which are within a specified pixel radius of the curve;

wherein said first test results comprise said number of the first subset of the plurality of pixels which are within the specified pixel radius of the curve;

wherein said first criteria comprise said number of the first subset of the plurality of pixels which are within the specified pixel radius of the curve meeting or exceeding a first threshold value;

wherein said testing the curve against the second subset of the plurality of pixels comprises determining a number of the second subset of the plurality of pixels which are within the specified pixel radius of the curve;

wherein said second test results comprise said number of the second subset of the plurality of pixels which are within the specified pixel radius of the curve; and

wherein said second criteria comprise said number of the second subset of the plurality of pixels which are within the specified pixel radius of the curve meeting or exceeding a second threshold value.

62. The system of claim 61, wherein said second criteria further comprise said number of the second subset of the plurality of pixels which are within the specified pixel radius of the curve plus said number of the first subset of the plurality of pixels which are within the specified pixel radius of the curve meeting or exceeding the specified second threshold value.

63. The system of claim 59, wherein the program instructions are further executable by the CPU to perform:

performing a refined curve fit, wherein the refined curve fit is performed using a third subset of the plurality of pixels comprising pixels within a specified pixel radius of the curve, wherein performing the refined curve fit comprises iteratively culling outlying pixels from the third subset, generating a culled subset of pixels, and fitting a refined curve to the culled subset at each iteration until an ending condition is met, thereby generating a refined curve, and

generating output, comprising one or more of information regarding the generated refined curve, and the culled subset of the plurality of pixels, wherein the generated refined curve comprises a refined detected edge in the image.