Algorithm GRI  Robust Geometric Resampling Algorithm (RGR)  Smoothing-Resampling Algorithm (SRALG)  SRALG-Based Interpolation Algorithm  Free Dot Gain Compensation Calculator  Free Ink Balance Online Tool  Free Utilities About the Author

Smoothing-Resampling Algorithm (SRALG)

If you wish to use the materials on this page, you are obliged to preserve the link to it.

In many practical situations, there is a need of calculating intermediate values by given data values, so that both the given and the original values are defined by a certain function unknown to us. It is assumed that the unknown function is meeting a certain criteria, such as being continuously differentiable. Normally, such problems are solved by approximation of the assumed function using other functions meeting the desired criteria.

In many cases, however, the functions are needed only to produce the resulting set of values. In and of themselves, they would have no further use afterwards. That fact is at the base of the proposed algorithmic approach.

Instead of searching for approximating functions, the assumed function would be approximated by a set of values calculated iteratively. When enough values have been calculated to achieve the desired resulting set, the process can be terminated.

In terms of signal processing, the proposed algorithm is, in fact, an algorithm of resampling which produces smoothed approximated values. As such, I name it SRALG (Smoothing-Resampling Algorithm). It has been tested and proved effective in a number of real computational problems, especially when the initial data error is known in advance and can be used to calculate the coefficient of smoothing (see the deviation calculation below).

Algorithm (single iteration):

  • The algorithm is given a collection of original points and a coefficient k (0<k<1).
  • Add the first original point to the result as is.
  • Add the middle of the line segment between first and second points to the result.
  • For every consequent original point starting with the third, perform the following operation:
    1. Let previous original point be p0.
    2. Let current original point be p1.
    3. Let the last point added to the result be m0.
    4. Find the middle between p0 and p1. Let it be m1.
    5. Find the middle between m0 and m1. Let it be mm.
    6. Find a point that divides the line segment between p0 and mm by the coefficient k.
      Add it to the result.
    7. Add m1 to the result.
  • Add the last point to the result as is.
SRALG

It is easily seen that the iterations of the algorithm above are designed in a manner which insures that the limit of all such iterations would be continuously differentiable.

Among the merits of the proposed algorithm are its simplicity, both for understanding and in terms of calculation time, the principle lack of artifacts caused by the usage of approximating functions of any particular kind, and the ease with which it may be generalized to be used in an n-dimensional space.

A special feature of SRALG is that it leaves unchanged a point which lies in the middle of a line segment defined by its neighbors, which is natural in the context of smoothing. This feature can be utilized during creation of other algorithms based on SRALG, such as my own SRALG-Based Interpolation Algorithm.

D.Grilikhes, PhD
March 24, 2013



MATLAB realization of one iteration of SRALG

function Y = iterSRALG( X,k )

% iterSRALG(X,k) Computes one iteration of SRALG

% on the siquense of points X(i,:)

% with the smoothig coefficient k.

% In this implementation, we assume that the points belong to

% some multi-dimentional space. k is assumed to be between 0 and 1.

% D.Grilikhes April 07, 2013

% Copyright 2013 Dmitry Grilikhes 

 

Y = zeros(size(X,1)*2-1, size(X,2));

Y(1,:) = X(1,:);

Y(2,:)=(X(1,:)+X(2,:))/2;

 

for i = 2:(size(X,1)-1)

    Y(2*(i-1)+1,:)=X(i,:)*(1-k/2)+k*(X(i-1,:)+X(i+1,:))/4;

    Y(2*(i-1)+2,:)=(X(i,:)+X(i+1,:))/2;

end

Y(size(X,1)*2-2,:) = (X(end,:)+X(end-1,:))/2;

Y(size(X,1)*2-1,:) = X(end,:);

end


Fig.1 Iterations of SRALG

SRALG illustration

Fig.1 SRALG in 3D

SRALG illustration

Matrix representation

In some cases it could be useful to realize SRALG as a sequense of matrix operations. It is trivial because of simplicity of representation of one SRALG iteration as multiplication below.
Matrix representation
where X1,X2,...Xn - are the data vectors in some vector space, and the matrix has n columns and 2n-1 rows.

Deviation from original data

It is very simple to calculate the deviation of each point from the original data point. In each iteration it shifts along the same line, towards the middle between its "neighbors" with the same coefficient k/2, so that the distance between it and this middle point becomes (1-k)/2. As a result, we have a geometric progression and can simply calculate the "shift" of point Xi after n iterations:
n-iteration shift,where X1,X2,...Xn - are data vectors in some vector space,

and the deviation of the point from its original will be limited by the limit below
n-iteration shift restriction.

© Dmitry Grilikhes, 2013


If you wish to use the materials on this page, you are obliged to preserve the link to it.

www.000webhost.com