Paper Info
Title
On the Computational Cost of Approximating and Recognizing Noise-Perturbed Straight Lines and Quadratic Arcs in the Plane
Abstract
Approximation of noisy data in the plane by straight line or elliptic or single-branch hyperbolic curve segments arises in pattern recognition, data compaction, and other problems. A number of questions concerning the efficient search for and approximation of data by such curves are examined. Recursive least-squares linear curve fitting is applied to the original or to transformed data in the plane to provide computationally simple algorithms for sequentially searching out appropriate data points and fitting straight line segments or quadratic arcs to the data found. The error minimized by the algorithms is interpreted. Central processing unit (CPU) times for estimating parameters for fitting straight lines and quadratic curves are determined and compared. CPU time for data search is also determined for the case of straight line fitting. Quadratic curve fitting is shown to require about six times as much CPU time as does straight line fitting. Curves relating CPU time and fitting error are determined for straight line fitting. A number of the preceding results are extended by using maximum likelihood curve estimation, and the modification of the classical least-squares curve fit resulting from the use of an a priori probability density function for the unknown curve parameters is determined.
Year
DOI
Venue
1976
10.1109/TC.1976.1674543
IEEE Transactions on Computers
Keywords
DocType
Volume
linear curve fitting,fitting error,quadratic arcs,straight line fitting,data compaction,data search,computational cost,quadratic curve fitting,fitting straight line,fitting straight line segment,appropriate data point,cpu time,noise-perturbed straight lines,pattern recognition
Journal
C-25
Issue
ISSN
Citations 
10
0018-9340
31
PageRank 
References 
Authors
42.99
4
2
Name
Order
Citations
PageRank
David B. Cooper1305109.53
N. Yalabik23744.95