System and method for curve fitting using randomized techniques

• US 6,882,958 B2
• Filed: 06/28/2001
• Issued: 04/19/2005
• 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): WACHSMAN, HAL D
• Application Number:
  US09/894,497
• Publication Number:
  US 20030065476A1
• Time in Patent Office: 1,391 Days
• Field of Search: 702179-181, 702/86, 702/97, 702/127, 702157-159, 702/167, 702/108, 702/FOR.131, 702/FOR.134, 702/FOR.139, 702/FOR.141, 702/FOR.146, 702/FOR.147, 702/FOR.156, 702/FOR.157, 702/FOR.160, 702/FOR.163, 702/FOR.169, 702/FOR.170, 702/FOR.171, 382/199, 382/195, 382/200, 382/266, 382/281, 382/285, 707/6, 707/7, 345/442, 345/441, 700/187
• US Class Current: 702/179
• CPC Class Codes: G06F 17/17 Function evaluation by approximation methods, e.g. inter- or extrapolation, smoothing, least mean square method G06F17/18 takes precedence ; interpolation for numerical control G05B19/18
• CPC Class Codes: G06V 10/752 Contour matching

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 curve fitting, the method comprising:

(a) storing a plurality of data points in a memory of the computer;

(b) generating a curve based on two or more random points of the plurality of data points;

(c) testing the curve against a first subset of the plurality of data points, wherein the first subset is less than all of the plurality of data points, wherein said testing produces first test results;

(d) performing (b) and (c) a plurality of times to determine a curve which meets 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 said first criteria, storing information regarding the curve, wherein said information specifies a curve fit of the plurality of data points.

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 data points of the plurality of data points within a specified radius of the curve meeting or exceeding a specified minimum value.

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

after (b) and before (c), pre-testing the curve against a second subset of the plurality of data points, wherein the second subset is less than all of the plurality of data points, wherein said pre-testing produces second test results;

if said second test results meet second criteria, then performing (c) through (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 points from the plurality of data points.

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

randomizing the plurality of data points after said storing to generate a randomized list of the plurality of data points;

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

7. The computer-implemented method of claim 6, wherein said randomizing the plurality of data points 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 data points comprises:

determining a number of the second subset of the plurality of data points which are within a specified radius of the curve;

wherein said second test results comprise said number of the second subset of the plurality of data points which are within the specified 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 data points which are within the specified 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 data points which are within the specified 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 data points comprises:

determining a number of the first subset of the plurality of data points which are within a specified radius of the curve;

wherein said first test results comprise said number of the first subset of the plurality of data points which are within the specified 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 data points which are within the specified 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 data points.

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 data points comprising data points within a specified radius of the curve, wherein the refined curve fit comprises iteratively culling outlying data points from the second subset, generating a culled subset of data points, and fitting a new 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 data points.

17. The computer-implemented method of claim 16, wherein said performing the refined curve fit comprises:

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

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

fitting the new curve to the culled subset;

calculating an error for the new curve on the culled subset;

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

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

the culled subset;

the refined curve;

the error for the refined curve on the culled subset;

an error for the refined curve with respect to the plurality of data points;

a score, indicating the fitness of the refined curve with respect to the culled subset; and

a score, indicating the fitness of the refined curve with respect to the plurality of data points.

18. The computer-implemented method of claim 1, wherein the plurality of data points comprises pixels of an image;

and wherein the curve fitting method operates to perform edge detection on the image.

19. A memory medium operable to store program instructions for performing a curve fit on a stored plurality of data points, wherein the program instructions are executable by a processor to perform:

(a) generating a curve based on two or more random points of the plurality of data points;

(b) testing the curve against a first subset of the plurality of data points, wherein the first subset is less than all of the plurality of data points, wherein said testing produces first test results;

(c) performing (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

(d) if said first test results meet said first criteria, storing information regarding the curve, wherein said information specifies a curve fit of the plurality of data points.

20. The memory medium of claim 19, wherein said ending criteria comprise one or more of:

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

a number of data points of the plurality of data points within a specified radius of the curve meeting or exceeding a specified minimum value.

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

after (a) and before (b), pre-testing the curve against a second subset of the plurality of data points, wherein the second subset is less than all of the plurality of data points, wherein said pre-testing produces second test results, wherein said second subset is a random subset comprising randomly selected points from the plurality of data points; and

if said second test results meet second criteria, then performing (b) through (d).

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

randomizing the plurality of data points to generate a randomized list of the plurality of data points;

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

23. The memory medium of claim 21,

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

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

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

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

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

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

24. 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 data points comprising data points within a specified radius of the curve, wherein the refined curve fit comprises iteratively culling outlying data points from the second subset, generating a culled subset of data points, and fitting a new 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 data points.

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

a CPU;

a memory medium coupled to the CPU, wherein the memory medium 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 data points for storage in the memory medium;

wherein the program instructions are executable by the CPU to;

(a) generate a curve based on two or more random points of the plurality of data points;

(b) test the curve against a first subset of the plurality of data points, to produce first test results, wherein the first subset is less than all of the plurality of data points;

(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 data points of the plurality of data points within a specified radius of the curve meeting or exceeding a specified minimum value; and

if said first test results meet said first criteria, storing information regarding the curve, wherein said information specifies a curve fit of the plurality of data points.

26. The system of claim 25, 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 data points to produce second test results, wherein said second subset is a random subset comprising randomly selected points from the plurality of data points; and

if said second test results meet second criteria, perform (b) through (d).

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

randomize the plurality of data points to generate a randomized list of the plurality of data points;

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

28. The system of claim 26,

wherein, in pre-testing the curve against a second subset of the plurality of data points, the program instructions are further executable by the CPU to determine a number of the second subset of the plurality of data points which are within a specified radius of the curve;

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

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

wherein, in testing the curve against the first subset of the plurality of data points, the program instructions are further executable by the CPU to determine a number of the first subset of the plurality of data points which are within the specified radius of the curve;

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

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

29. The system of claim 25, 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 data points comprising data points within a specified radius of the curve, wherein, in performing the refined curve fit, the program instructions are executable by the CPU to;

iteratively cull outlying data points from the second subset;

generate a culled subset of data points; and

fit a new 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 data points.

30. A computer-implemented method for curve fitting, the method comprising:

(a) storing a plurality of data points;

(b) generating a curve based on two or more random points of the plurality of data points;

(c) testing the curve against a first subset of the plurality of data points, wherein the first subset is less than all of the plurality of data points, wherein said testing includes determining a number of the first subset of the plurality of data points which are within a specified radius of the curve, wherein said testing the curve against a first subset produces first test results, wherein said first test results include said number of the first subset of the plurality of data points which are within the specified radius of the curve; and

if said first test results meet first criteria, performing steps (d) and (e);

(d) testing the curve against a second subset of the plurality of data points, wherein said testing the curve against a second subset of the plurality of data points produces second test results; and

(e) if said second test results meet second criteria, storing information regarding the curve, wherein said information specifies a curve fit of the plurality of data points.

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

32. The computer-implemented method of claim 30, wherein the first subset is a random subset comprising randomly selected points from the plurality of data points.

33. The computer-implemented method of claim 32, further comprising:

randomizing the plurality of data points after said storing to generate a randomized list of the plurality of data points;

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

34. The computer-implemented method of claim 33, wherein said randomizing the plurality of data points 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.

35. The computer-implemented method of claim 34, wherein said testing the curve against the first subset of the plurality of data points comprises:

determining a number of the first subset of the plurality of data points which are within a specified radius of the curve;

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

36. The computer-implemented method of claim 35, wherein said first criteria comprise said number of the first subset of the plurality of data points which are within the specified radius of the curve meeting or exceeding a threshold value.

37. The computer-implemented method of claim 35, wherein said first criteria comprise said number of the first subset of the plurality of data points which are within the specified radius of the curve meeting or exceeding a specified fraction of the first subset.

38. A computer-implemented method for curve fitting, the method comprising:

a) storing a plurality of data points;

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

c) testing the curve against a first subset of the plurality of data points, wherein the first subset is less than all of the plurality of data points, wherein said testing produces first test results, wherein said testing the curve against a first subset of the plurality of data points comprises;

determining a number of the first subset of the plurality of data points which are within a specified radius of the curve, wherein said first test results comprise said number of the first subset of the plurality of data points which are within the specified radius of the curve;

d) if said first test results meet first criteria, storing information regarding the curve, wherein said information specifies a curve fit of the plurality of data points.

39. The computer-implemented method of claim 38, wherein said first criteria comprise said number of the first subset of the plurality of data points which are within the specified radius of the curve meeting or exceeding a specified fraction of the first subset.

40. A computer-implemented method for curve fitting, the method comprising:

a) storing a plurality of data points;

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

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

d) if said first test results meet first criteria, storing information regarding the curve, wherein said information specifies a curve fit of the plurality of data points;

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

f) generating and storing output, comprising one or more of information regarding the refined curve, wherein said information specifies the refined curve fit of the plurality of data points, and the culled subset of the plurality of data points.

41. The computer-implemented method of claim 40, wherein said performing a refined curve fit comprises:

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

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

fitting the new curve to the culled subset;

calculating an error for the new curve on the culled subset;

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

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

the culled subset;

the refined curve;

the error for the refined curve on the culled subset;

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

the plurality of data points.

42. A memory medium operable to store program instrucfions for performing a curve fit on a stored plurality of data points, wherein the program instructions are executable by a processor to perform:

(a) generating a curve based on two or more random points of the plurality of data points;

(b) testing the curve against a first subset of the plurality of data points, wherein the first subset is less than all of the plurality of data points, wherein the first subset comprises randomly selected points from the plurality of data points, wherein said testing produces first test results; and

if said first test results meet first criteria,

(c) testing the curve against a second subset of the plurality of data points, wherein the second subset is less than all of the plurality of data points, wherein said testing produces second test results;

(d) performing (a) through (c) a plurality of times to determine a curve which meets second criteria; and

(e) if said second test results meet second criteria, storing information regarding the curve, wherein said information specifies a curve fit of the plurality of data points.

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

randomizing the plurality of data points to generate a randomized list of the plurality of data points;

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

44. The memory medium of claim 43,

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

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

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

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

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

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

45. A memory medium operable to store program instructions for performing a curve fit on a stored plurality of data points, wherein the program instructions are executable by a processor to perform:

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

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

c) performing (a) and (b) a plurality of times to determine a curve which meets first criteria;

d) if said first test results meet first criteria, storing information regarding the curve, wherein said information specifies a curve fit of the plurality of data points;

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

f) generating and storing output, comprising one or more of information regarding the refined curve, wherein said information specifies the refined curve fit of the plurality of data points, and the culled subset of the plurality of data points.

46. A memory medium operable to store program instructions for performing a curve fit on a stored plurality of data points, wherein the program instructions are executable by a processor to perform:

(a) generating a curve based on two or more random points of the plurality of data points;

(b) testing the curve against a first subset of the plurality of data points, wherein the first subset is less than all of the plurality of data points, wherein said testing produces first test results;

(c) performing (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 data points of the plurality of data points within a specified radius of the curve meeting or exceeding a specified minimum value; and

(d) if said first test results meet first criteria, storing information regarding the curve, wherein said information specifies a curve fit of the plurality of data points.

47. A computer-implemented method for curve fitting, the method comprising:

(a) storing a plurality of data points;

(b) generating a curve based on two or more random points of the plurality of data points;

(c) testing the curve against a first subset of the plurality of data points, wherein the first subset is less than all of the plurality of data points, wherein said testing produces first test results;

(d) performing (b) and (c) a plurality of times to determine a curve which meets 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 wherein said ending criteria comprise one or more of;

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

a number of data points of the plurality of data points within a specified radius of the curve meeting or exceeding a specified minimum value; and

(e) if said first test results meet first criteria, storing information regarding the curve, wherein said information specifies a curve fit of the plurality of data points.

48. A computer-implemented method for curve fitting, the method comprising:

(a) generating a curve based on two or more random points of a stored plurality of data points;

(b) pre-testing the curve against a first subset of the plurality of data points, wherein the first subset is less than all of the plurality of data points, wherein said pre-testing produces first test results, wherein said first subset is a random subset comprising randomly selected points from the plurality of data points; and

(c) if said first test results meet first criteria, testing the curve against a second subset of the plurality of data points, wherein said testing produces second test results;

(d) performing (a) through (c) a plurality of times to determine a curve which meets second criteria; and

(e) if said second test results meet said first criteria, storing information regarding the curve, wherein said information specifies a curve fit of the plurality of data points.