Деректерді тегістеу алгоритмі: Савицкий-Голай сүзгісі

Algorithm to smooth data points

A Savitzky–Golay filter is a digital filter that can be applied to a set of digital data points for the purpose of smoothing the data, that is, to increase the precision of the data without distorting the signal tendency. This is achieved, in a process known as convolution, by fitting successive sub sets of adjacent data points with a low degree polynomial by the method of linear least squares. When the data points are equally spaced, an analytical solution to the least squares equations can be found, in the form of a single set of "convolution coefficients" that can be applied to all data sub sets, to give estimates of the smoothed signal, (or derivatives of the smoothed signal) at the central point of each sub set. The method, based on established mathematical procedures, was popularized by Abraham Savitzky and Marcel J. E. Golay, who published tables of convolution coefficients for various polynomials and sub set sizes in 1964. Some errors in the tables have been corrected. The method has been extended for the treatment of 2 and 3 dimensional data. Savitzky and Golay's paper is one of the most widely cited papers in the journal Analytical Chemistry and is classed by that journal as one of its "10 seminal papers" saying "it can be argued that the dawn of the computer controlled analytical instrument can be traced to this article".

The "moving average filter" is a trivial example of a Savitzky Golay filter that is commonly used with time series data to smooth out short term fluctuations and highlight longer term trends or cycles. Each subset of the data set is fit with a straight horizontal line as opposed to a higher order polynomial. An unweighted moving average filter is the simplest convolution filter. The moving average is often used for a quick technical analysis of financial data, like stock prices, returns or trading volumes. It is also used in economics to examine gross domestic product, employment or other macroeconomic time series. It was not included in some tables of Savitzky Golay convolution coefficients as all the coefficient values are identical, with the value .

An alternative to fitting m data points by a simple polynomial in the subsidiary variable, z, is to use orthogonal polynomials. where P0,  , Pk is a set of mutually orthogonal polynomials of degree 0,  , k. Full details on how to obtain expressions for the orthogonal polynomials and the relationship between the coefficients b and a are given by Guest. This is also equivalent to fitting the first (m + 1)/2 points with the same polynomial, and similarly for the last points.

The idea of two dimensional convolution coefficients can be extended to the higher spatial dimensions as well, in a straightforward manner, by arranging multidimensional distribution of the kernel nodes in a single row. Following the aforementioned finding by Nikitas and Pappa Louisi The precision of the floating point numbers is gradually increased in each iteration, by using GNU MPFR. Once the obtained C's in two consecutive iterations start having same significant digits until a pre specified distance, the convergence is assumed to have reached. If the distance is sufficiently large, the computation yields a highly accurate C. PCCC employs rational number calculations, by using GNU Multiple Precision Arithmetic Library, and yields a fully accurate C, in the rational number format. In the end, these rational numbers are converted into floating point numbers, until a pre specified number of significant digits. A database of C's that are calculated by using ACCC, for symmetric kernels and both symmetric and asymmetric polynomials, on unity spaced kernel nodes, in the 1, 2, 3, and 4 dimensional spaces, is made available. Chandra Shekhar has also laid out a mathematical framework that describes usage of C calculated on unity spaced kernel nodes to perform filtering and partial differentiations (of various orders) on non uniformly spaced kernel nodes,
The sum of squared convolution coefficients for smoothing is equal to the value of the central coefficient.

One way to mitigate distortion and improve noise removal is to use a filter of smaller width and perform more than one convolution with it. For two passes of the same filter this is equivalent to one pass of a filter obtained by convolution of the original filter with itself. For example, 2 passes of the filter with coefficients (1/3, 1/3, 1/3) is equivalent to 1 pass of the filter with coefficients
(1/9, 2/9, 3/9, 2/9, 1/9). The disadvantage of multipassing is that the equivalent filter width for passes of an –point function is so multipassing is subject to greater end effects. Nevertheless, multipassing has been used to great advantage. For instance, some 40–80 passes on data with a signal to noise ratio of only 5 gave useful results. The noise reduction formulae given above do not apply because correlation between calculated data points increases with each pass.

Convolution maps to multiplication in the Fourier co domain. The discrete Fourier transform of a convolution filter is a real valued function which can be represented as

θ runs from 0 to 180 degrees, after which the function merely repeats itself. The plot for a 9 point quadratic/cubic smoothing function is typical. At very low angle, the plot is almost flat, meaning that low frequency components of the data will be virtually unchanged by the smoothing operation. As the angle increases the value decreases so that higher frequency components are more and more attenuated. This shows that the convolution filter can be described as a low pass filter: the noise that is removed is primarily high frequency noise and low frequency noise passes through the filter. Some high frequency noise components are attenuated more than others, as shown by undulations in the Fourier transform at large angles. This can give rise to small oscillations in the smoothed data and phase reversal, i. e., high frequency oscillations in the data get inverted by Savitzky–Golay filtering.

Compared with other smoothing filters, e. g. convolution with a Gaussian or multi pass moving average filtering, Savitzky–Golay filters have an initially flatter response and sharper cutoff in the frequency domain, especially for high orders of the fit polynomial (see frequency characteristics). For data with limited signal bandwidth, this means that Savitzky–Golay filtering can provide better signal to noise ratio than many other filters; e. g., peak heights of spectra are better preserved than for other filters with similar noise suppression. Disadvantages of the Savitzky–Golay filters are comparably poor suppression of some high frequencies (poor stopband suppression) and artifacts when using polynomial fits for the first and last points. Alternative smoothing methods that share the advantages of Savitzky–Golay filters and mitigate at least some of their disadvantages are Savitzky–Golay filters with properly chosen fitting weights, Whittaker–Henderson smoothing (a method closely related to smoothing splines), and convolution with a windowed sinc function.