US 6,882,958 B2 · System and method for curve fitting using randomized techniques

Abstract

A system and method for performing a curve fit on a plurality of data points. In an initial phase, a subset Pmax 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 Nmin 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 Pmax of the input points. The subset Pmax 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 Pmax with respect to a succession of optimal curves fit to the modified subset Pmax at each iteration. The refined curve fit generates a refined curve, which may be output along with a final culled subset Kfinal of Pmax.

Claims48

Dependent claims

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.

3 more elements

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.

2 more elements

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.

10 more elements

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.

3 more elements

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.

5 more elements

Dependencies are inferred from the claim text.

System and method for curve fitting using randomized techniques

Life of this patent

System and method for curve fitting using randomized techniques

Life of this patent

Abstract

Claims48