System and method for performing edge detection in an image

• US 7,013,047 B2
• Filed: 06/28/2001
• Issued: 03/14/2006
• Est. Priority Date: 06/28/2001
• Status: Expired due to Term

• 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
• Primary Examiner(s): MARIAM, DANIEL G
• Application Number:
  US09/894,272
• Publication Number:
  US 20030053696A1
• Time in Patent Office: 1,720 Days
• Field of Search: 382/173, 382/181, 382/190, 382/199, 382/203, 382/206, 382/209, 382/218, 382/228, 382/300, 382/316, 358/504, 702/127, 702/179
• 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) storing the plurality of pixels in a memory of a computer;

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 the first subset is less than all of the plurality of pixels, wherein said testing produces first test results;

d) performing (b) and (c) a plurality of times to determine a curve which meets the first criteria, wherein said performing (b) and (c) a plurality of times comprises performing (b) and (c) in an iterative manner until ending criteria are met; and

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

2. The computer-implemented method of claim 1, 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.

3. The computer-implemented method of claim 1, further comprising:

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

wherein, if said second test results meet second criteria, then performing c)–

e).

4. The computer-implemented method of claim 3, wherein the second subset is smaller than the first subset.

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

6. The computer-implemented method of claim 5, further comprising:

randomizing the plurality of pixels after said storing 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.

7. The computer-implemented method of claim 6, 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.

8. The computer-implemented method of claim 3, 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.

9. The computer-implemented method of claim 8, 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.

10. The computer-implemented method of claim 8, 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.

11. The computer-implemented 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.

12. The computer-implemented method of claim 11, 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.

13. The computer-implemented method of claim 1, wherein the first subset comprises substantially all of the plurality of pixels.

14. The computer-implemented method of claim 1, further comprising:

displaying the generated curve on a display device.

15. The computer-implemented method of claim 1, wherein the curve comprises one of a line, a circle, and an ellipse.

16. The computer-implemented 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 and storing output, comprising one or more of information regarding the refined curve, and the culled subset of the plurality of pixels.

17. The computer-implemented method of claim 16, 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 and storing 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.

18. The computer-implemented method of claim 1, wherein the image has a dimensionality greater than two.

19. 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 the first subset is less than all of the plurality of pixels, wherein said testing produces first test results;

c) performing (a) and (b) a plurality of times to determine a curve which meets the first criteria, wherein said performing (a) and (b) a plurality of times comprises performing (a) and (b) in an iterative manner until ending criteria are met; and

;

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

20. The memory medium of claim 19, 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, and wherein the second subset is less than all of the plurality of pixels;

wherein, if said second test results meet second criteria, then performing b)–

d).

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

randomizing the plurality of pixels 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.

22. The memory medium of claim 20,

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.

23. The memory medium of claim 19, 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.

24. 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;

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

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

(c) perform (a) and (b) a plurality of times to determine a curve which meets first criteria, wherein said performing (a) and (b) a plurality of times comprises performing (a) and (b) in an iterative manner until ending criteria are met, and 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 radius of the curve meeting or exceeding a specified minimum value;

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

25. The system of claim 24, wherein the program instructions are further executable by the CPU to:

after (a) and before (b), pre-test 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, and wherein the second subset is less than all of the plurality of pixels;

wherein, if said second test results meet second criteria, then perform b)–

d).

26. The system of claim 25, wherein the program instructions are further executable by the CPU to:

randomize the plurality of pixels 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.

27. The system of claim 25,

wherein in pre-testing the curve against a second subset of the plurality of pixels, the program instructions are executable by the CPU to determine 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 in testing the curve against a first subset of the plurality of pixels, the program instructions are executable by the CPU to determine 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.

28. The system of claim 24, wherein the program instructions are further executable by the CPU to:

perform 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 in performing the refined curve fit, the program instructions are executable by the CPU to iteratively cull outlying pixels from the second subset, generate a culled subset of pixels, and fit 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

generate 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.

29. 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;

d) 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

e) 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.

30. A computer-implemented method for performing edge detection in a received image comprising a plurality of pixels, comprising:

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;

d) 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

e) 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.

31. 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;

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

b) test 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, output information regarding the curve, wherein the curve comprises a detected edge in the image;

d) perform 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 in performing the refined curve fit, the program instructions are executable by the CPU to iteratively cull outlying pixels from the second subset, generate a culled subset of pixels, and fit 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

e) generate 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.

32. A system for performing edge detection in a received image comprising a plurality of pixels, comprising:

means for storing a plurality of pixels;

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

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

means for, if said first test results meet first criteria, outputting information regarding the curve, wherein the curve comprises a detected edge in the image;

means for 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

means for 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.