System and method for curve fitting using randomized techniques

• US 20030065476A1
• Filed: 06/28/2001
• Published: 04/03/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 6,882,958 B2
• Time in Patent Office: Days
• 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) receiving 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, outputting information regarding the curve.

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 data points of the plurality of data points within a specified 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 data points, 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 points from the plurality of data points.

8. The method of claim 7, further comprising:

randomizing the plurality of data points after said receiving 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.

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

10. The method of claim 5, 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 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.

11. The method of claim 10, 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.

12. The method of claim 10, 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.

13. The 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 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.

14. The method of claim 13, 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.

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

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 data points comprising data points within said 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 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 data points.

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 radius;

removing one or more points from the second subset, wherein said one or more points 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;

the error for the curve on the culled subset;

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

the plurality of data points.

20. The 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.

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

a) receiving a plurality of data points;

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

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

d) pre-testing the curve against a first random subset of the plurality of data points, 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 data points, 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.

22. The method of claim 21, further comprising:

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

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

23. The method of claim 22, 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 from the random starting position.

24. The method of claim 21, wherein said second subset substantially comprises data points 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 data points of the plurality of data points within a specified 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 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.

29. The method of claim 28, 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.

30. The method of claim 28, 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.

31. The method of claim 28, 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 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.

32. The method of claim 31, 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.

33. The method of claim 31, 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 plus 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 plurality of data points.

34. The method of claim 21, wherein said outputting information comprises displaying the generated curve 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 data points, comprising data points which are within a specified 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, further comprising:

performing a refined curve fit, wherein the refined curve fit is performed using a third subset of the plurality of data points comprising data points within a specified radius of the curve, wherein performing the refined curve fit comprises iteratively culling outlying data points from the third subset, generating a culled subset of data points, 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 data points.

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

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

fitting a curve to the third subset of data points;

removing one or more points from the third subset, wherein said one or more points 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;

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 points; and

the plurality of data points.

39. The method of claim 21,

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.

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

a) receiving a plurality of data points, P;

b) randomizing the order of the plurality of data points P;

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

d) selecting two or more data points from P;

e) generating a curve using the two or more data points, 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 data points;

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

h) if a ratio of J to M exceeds a threshold, updating the recorded subset P_j and J to include all points in P whose distance from the curve is less than or equal to the specified 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 data points, and recording the two or more parameters defining the curve, wherein the curve comprises an estimated fit to the plurality of data points, 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 point count.

41. The method of claim 40, wherein said at least two points comprise N_c data points, 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 radius;

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

n) fitting an initial curve L₀ to the optimal set of data points 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 points from K_i, wherein said P_i points are furthest from curve L_i, thereby generating subset K_i+1 of 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_i+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 data points 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;

the score s_final; and

the plurality of data points P.

42. A memory medium operable to store program instructions for performing a curve fit on a received plurality of data points, wherein the program instructions are executable 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) if said first test results meet first criteria, outputting information regarding the curve.

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 data points, wherein said testing produces second test results, wherein said second subset is a random subset comprising randomly selected points from the plurality of data points;

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

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

randomizing the plurality of data points after said receiving 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.

46. The memory medium of claim 44,

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;

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

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 data points comprising data points within said 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 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 data points.

48. A memory medium operable to store program instructions for performing a curve fit on a received plurality of data points, 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 points of the plurality of data points;

c) pre-testing the curve against a first random subset of the plurality of data points, 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 data points, 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.

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

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

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 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 first 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 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 data points which are within the specified radius of the curve plus said number of the first subset of the plurality of data points which are within the specified 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 data points comprising data points within a specified radius of the curve, wherein performing the refined curve fit comprises iteratively culling outlying data points from the third subset, generating a culled subset of data points, 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 data points.

53. 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 data points;

wherein the program instructions are executable by the CPU 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) if said first test results meet first criteria, outputting information regarding the curve.

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 data points, wherein said testing produces second test results, wherein said second subset is a random subset comprising randomly selected points from the plurality of data points;

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

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

randomizing the plurality of data points after said receiving 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.

57. The system of claim 55,

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;

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

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 data points comprising data points within said 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 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 data points.

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 data points;

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 points of the plurality of data points;

c) pre-testing the curve against a first random subset of the plurality of data points, 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 data points, 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.

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 data points before said performing to produce a randomized list of the plurality of data points;

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 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 first 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 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 data points which are within the specified radius of the curve plus said number of the first subset of the plurality of data points which are within the specified 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 data points comprising data points within a specified radius of the curve, wherein performing the refined curve fit comprises iteratively culling outlying data points from the third subset, generating a culled subset of data points, 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 data points.