Printer Friendly

Probabilistic 2D point interpolation and extrapolation via data modeling.

Mathematics and computer science are interested in methods of 2D curve interpolation and extrapolation using the set of key points (knots). A proposed method of Hurwitz- Radon Matrices (MHR) is such a method. This novel method is based on the family of Hurwitz-Radon (HR) matrices which possess columns composed of orthogonal vectors. Two-dimensional curve is interpolated via different functions as probability distribution functions: polynomial, sinus, cosine, tangent, cotangent, logarithm, exponent, arcsin, arccos, arctan, arcctg or power function, also inverse functions. It is shown how to build the orthogonal matrix operator and how to use it in a process of curve reconstruction.

Povzetek: Opisana je nova metoda 2D interpolacije in ekstrapolacije krivulj.

1 Introduction

Curve interpolation and extrapolation [1] represents one of the most important problems in mathematics: how to model the curve [2] via discrete set of two-dimensional points [3]? Also the matter of curve representation and parameterization is still opened in mathematics and computer sciences |4], The author wants to approach a problem of curve modeling by characteristic points. Proposed method relies on functional modeling of curve points situated between the basic set of the nodes or outside the nodes. The functions that are used in calculations represent whole family of elementary functions with inverse functions: polynomials, trigonometric, cyclometric, logarithmic, exponential and power function. These functions are treated as probability distribution functions in the range [0,1]. Nowadays methods apply mainly polynomial functions, for example Bernstein polynomials in Bezier curves, splines and NURBS [5]. Numerical methods for data interpolation or extrapolation are based on polynomial or trigonometric functions, for example Lagrange, Newton, Aitken and Hermite methods. These methods have some weak sides [6] and are not sufficient for curve interpolation and extrapolation in the situations when the curve cannot be build by polynomials or trigonometric functions. Proposed 2D curve interpolation and extrapolation is the functional modeling via any elementary functions and it helps us to fit the curve during the computations.

The main contributions of the paper are dealing with presentation the method that connects such problems as: interpolation, extrapolation, modeling, numerical methods and probabilistic methods. This is new approach to these problems. Differences from the previous papers of the author are connected with calculations without matrices (N = 1), new probabilistic distribution functions and novel look on shape modeling and curve reconstruction.

The method of Hurwitz-Radon Matrices (MHR) requires minimal assumptions: the only information about a curve is the set of at least two nodes. Proposed method of Hurwitz-Radon Matrices (MHR) is applied in curve modeling via different coefficients: polynomial, sinusoidal, cosinusoidal, tangent, cotangent, logarithmic, exponential, arcsin, arccos, arctan, arcctg or power. Function for MHR calculations is chosen individually at each interpolation and it represents probability distribution function of parameter [alpha] [member of] [0,1] for every point situated between two interpolation knots. MHR method uses two-dimensional vectors (x,y) for curve modeling--knots ([x.sub.i], [y.sub.i]) [member of] [R.sup.1] in MHR method:

1. MHR version with no matrices (N = 1) needs 2 knots or more;

2. At least five knots ([x.sub.1], [y.sub.i]), ([x.sub.2], [y.sub.2]), ([x.sub.3], [y.sub.3]), ([x.sub.4], [y.sub.4]) and ([x.sub.5], [y.sub.5]) if MHR method is implemented with matrices of dimension N = 2;

3. For more precise modeling knots ought to be settled at key points of the curve, for example local minimum or maximum and at least one node between two successive local extrema.

Condition 2 is connected with important features of MHR method: MHR version with matrices of dimension N = 2 (MHR-2) requires at least five nodes, MHR version with matrices of dimension N = 4 (MHR-4) needs at least nine nodes and MHR version with matrices of dimension N= 8 (MHR-8) requires at least 17 nodes. Condition 3 means for example the highest point of the curve in a particular orientation, convexity changing or curvature extrema. So this paper wants to answer the question: how to interpolate end extrapolate the curve by a set of knots?

Coefficients for curve modeling are computed using probability distribution functions: polynomials, power functions, sinus, cosine, tangent, cotangent, logarithm, exponent or arcsin, arccos, arctan, arcctg.

2 Probabilistic 2D interpolation and extrapolation

The method of Hurwitz--Radon Matrices (MHR) is computing points between two successive nodes of the curve: calculated points are interpolated and parameterized for real number [alpha] [member of] [0,1] in the range of two successive nodes. Data extrapolation is possible for [alpha] < 0 or [alpha] > 1. MHR calculations are dealing with square matrices of dimension TV = 1, 2, 4 or 8. Matrices [A.sub.i], 7 = 1, 2 ... m satisfying

[A.sub.j], [A.sub.k] + [A.sub.k][A.sub.j] = 0, [A.sup.2.sub.j] = -I for [not member of] k; j, k = 1, 2 ... m

are called a family of Hurwitz--Radon matrices. They were discussed by Adolf Hurwitz and Johann Radon separately in 1923. A family of Hurwitz-Radon (HR) matrices [7] are skew-symmetric: [A.sub.i.sup.T] = -[A.sub.i] - and [A.sub.-1.sup.i] = - [A.sub.i]. Only for dimensions N = 1, 2, 4 or 8 the family of HR matrices consists of N - 1 matrices. For N = 1 there is no matrices but only calculations with real numbers. For N = 2:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For N = 4 there are three HR matrices with integer entries:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For N = 8 we have seven HR matrices with elements 0, [+ or -] 1. So far HR matrices have found applications in Space-Time Block Coding (STBC) [8] and orthogonal design [9], in signal processing [10] and Hamiltonian Neural Nets [11].

How coordinates of knots are applied for interpolation and extrapolation? If knots are represented by the following points {([x.sub.i], [y.sub.i]) i = 1, 2, n} then HR matrices combined with the identity matrix [I.sub.N] are used to build the orthogonal Hurwitz--Radon Operator (OHR).

For point [p.sub.i] = {[x.sub.1], [y.sub.1]) and [x.sub.1] [not equal to] 0 OHR of dimension TV = 1 is the matrix (real number) [M.sub.1].

[M.sub.1]([p.sub.1]) = 1[x.sub.1.sup.2] [[x.sub.1] x [y.sub.1]] = [y.sub.1]/[x.sub.1]. (1)

For points [x.sub.1] = ([x.sub.1], [y.sub.1]) and [p.sub.2] = ([x.sub.2], [y.sub.2]) OHR of dimension N = 2 is build via matrix [M.sub.2].

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (1)

For points [x.sub.1] = ([x.sub.1], [y.sub.1]), [p.sub.2] = ([x.sub.2], [x.sub.2]). [p.sub.3] = ([x.sub.3], [x.sub.3]) and [p.sub.4] = ([x.sub.4], [y.sub.4]) OHR [M.sub.4] of dimension N = 4 is introduced:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

For knots [p.sub.1] = ([x.sub.1], [y.sub.1]), p2 = ([x.sub.2], [y.sub.2]), ... and [p.sub.8] = ([x.sub.8], [y.sub.8]) OHR Mg of dimension TV = 8 is constructed [12] similarly as (1) and (2):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (3)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (4)

and [u.bar] = [([u.sub.0], [u.sub.1], ..., [u.sub.7]).sup.T] (4). OHR operators [M.sub.N] (0)-(3) satisfy the condition of interpolation

[M.sub.n] x x = y (5)

for x = [([x.sub.1], [x.sub.2] ..., [x.sub.n]).sup.T] [member of] [R.sup.N], x [not equal to] 0, y = [([y.sub.1], [y.sub.2] ..., [y.sub.n]).sup.T] [member of] [R.sup.N] and N = 1, 2, 4 or 8.

2.1 Distribution functions in MHR interpolation and extrapolation

Points settled between the nodes are computed [13] using MHR method [14], Each real number c [member of] [a;b] is calculated by a convex combination

c = [alpha] x a + +(1 - [alpha]) x b for

[alpha] = b - c/b - a [member of] [0,1]. (6)

The weighted average OHR operator M of dimension N = 1, 2, 4 or 8 is build:

M = [gamma] x A + (1 - [gamma]) x B. (7)

The OHR matrix A is constructed (l)-(3) by every second knot [p.sub.1]=([x.sub.1]=a,[y.sub.1]), [p.sub.3]=([x.sub.3],[y.sub.3]), ... and [p.sub.2N-1]=([x.sub.2N-1],[y.sub.2N-1]):

A = [M.sub.N]([p.sub.1], [p.sub.3], ..., [p.sub.2N-1])

The OHR matrix B is computed (l)-(3) by knots [p.sub.2]=([x.sub.2]=b,[y.sub.2]), [p.sub.4]=([x.sub.4],[y.sub.4]), ... and [p.sub.2N]=([x.sub.2N],[Y.sub.2N]):

B = [M.sub.N]([p.sub.2], [p.sub.4], ..., [p.sub.2N]).

Vector of first coordinates C is defined for

[c.sub.i] = [alpha] x [x.sub.2i-1] + (1 - [alpha]) x [x.sub.2i], i = 1, 2, ..., N (8)

and C = [[[c.sub.1], [c.sub.2], ..., [c.sub.N]].sup.T]. The formula to calculate second coordinates y([c.sub.i]) is similar to the interpolation formula (5):

Y(C) = M x C (9)

where Y(C) = [[y([c.sub.1]), y([c.sub.2]), ..., y([c.sub.N])].sup.T]. So interpolated value y([c.sub.i]) from (9) depends on two, four, eight or sixteen (2N) successive nodes. For example N = 1 results in computations without matrices:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (10)

Formula (10) shows a clear calculation for interpolation of any point between two successive nodes ([x.sub.1],[y.sub.1]) and ([x.sub.2],[y.sub.2]). Key question is dealing with coefficient [gamma] in (7). Basic MHR version means [gamma] = [alpha] and then (10):

y([c.sub.1]) = [[alpha].sup.2] x [y.sub.1] + [(1 - [alpha]).sup.2] [y.sub.2] + [alpha](1 - [alpha])([[y.sub.1]/[x.sub.1]] [x.sub.2] + [[y.sub.2]/[x.sub.2]][x.sub.1]). (11)

Formula (11) represents the simplest way of MHR calculations (N = 1, [gamma] = [alpha]) and it differs from linear interpolation y(c) = [alpha] X [y.sub.1] + (1 - [alpha])[y.sub.2]. MHR is not a linear interpolation.

Each interpolation requires specific distribution of parameter [alpha] (7) and [gamma] depends on parameter [alpha] [member of] [0,1]:

[gamma] = F([alpha]), F:[0,1] [right arrow] [0,1], F(0) = 0, F(1)=1

and F is strictly monotonic.

Coefficient [gamma] is calculated using different functions (polynomials, power functions, sinus, cosine, tangent, cotangent, logarithm, exponent, arcsin, arccos, arctan or arcctg, also inverse functions) and choice of function is connected with initial requirements and curve specifications. Different values of coefficient [gamma] are connected with applied functions F(a). These functions (12)-(41) represent the probability distribution functions for random variable [alpha] [member of] [0,1] and real number s > 0:

1. power function

y = [[alpha].sup.s] with s > 0. (12)

For s = 1: basic version of MHR method when [gamma] = [alpha].

2. sinus

[gamma] = sin([[alpha].sup.s] x [pi]/2), s > 0 (13)

or

[gamma] = [sin.sup.s] ([alpha] x [pi]/2), s > 0. (14)

For s = 1: [gamma] = sin([alpha] x [pi]/2). (15)

3. cosine

[gamma] = 1 - cos([[alpha].sup.s] x [pi]/2), s > 0 (16)

or

[gamma] = 1 - [cos.sup.s]([alpha] x [pi]/2), s > 0. (17)

For s = 1: y = 1 - cos([alpha] x [pi]/2). (18)

4. tangent

[gamma] = tan([[alpha].sup.s] x [pi]/4), s > 0 (19)

or

[gamma] = [tan.sup.s]([alpha] x [pi]/4), s > 0. (20)

For s = 1: [gamma] = tan([alpha] x [pi]/4). (21)

5. logarithm

[gamma] = [log.sub.2]([[alpha].sup.s] + 1), s > 0 (22)

or

[gamma] = [log.sub.2.sup.s]([alpha] + 1), s > 0. (23)

For s = 1: [gamma] = [log.sub.2]([alpha] + 1). (24)

6. exponent

[gamma] = [([a.sup.[alpha]] - 1/a - 1).sup.s], s > 0 and a > 0 and a [not equal to] 1. (25)

For s = 1 and a = 2: [gamma] = [2.sup.[alpha]] - 1. (26)

7. arc sine

[gamma] = 2/[pi] x arcsin([[alpha].sup.s]), s > 0 (27)

or

[gamma] = [(2/[pi] - arcsin [alpha]).sup.s], s > 0. (28)

For s = 1: [gamma] = 2/[pi] x arcsin([alpha]). (29)

8. arc cosine

[gamma] = 1-2/[pi] X arccos([[alpha].sup.s]), S > 0 (30)

or

[gamma] = 1-[(2/[pi] X arccos [alpha]).sup.s], s > 0. (31)

For s = 1: [gamma] = 1-2/[pi] x arccos([alpha]). (32)

9. arc tangent

[gamma] = 4/[pi] arctan([[alpha].sup.s]), s > 0 (33)

or

[gamma] = [(4/[pi] X arctan [alpha]).sup.s], s > 0. (34)

For s = 1: [gamma] = 4/[pi] x arctan([alpha]). (35)

10. cotangent

[gamma] = ctg([pi]/2 - [[alpha].sup.s] x [pi]/4), s > 0 (36)

or

y = [ctg.sup.s] ([pi]/2 - [alpha] x [pi]/4), s > 0. (37)

For s = 1: [gamma] = ctg([pi]/2 - a x [pi]/4). (38)

11. arc cotangent

[gamma] = 2 - 4/[pi] x arcctg([[alpha].sup.s]), s > 0 (39)

or

[gamma] = [(2 - 4/[pi] x arcctg [alpha]).sup.s], s > 0. (40)

For s = 1: [gamma] = 2 - 4/[pi] arcctg([alpha]). (41)

Functions used in y calculations (12)-(41) are strictly monotonic for random variable [alpha] [member of] [0,1] as [gamma] = F([alpha]) is probability distribution function. Also inverse function [F.sup.-1]([alpha]) is appropriate for [gamma] calculations. Choice of function and value s depends on curve specifications and individual requirements. Interpolating of coordinates for curve points using (6)-(9) is called by author the method of Hurwitz--Radon Matrices (MHR) [15]. So here are five steps of MHR interpolation:

Step 1: Choice of knots at key points.

Step 2: Fixing the dimension of matrices N = 1, 2, 4 or 8: N= 1 is the most universal for calculations (it needs only two nodes to compute unknown points between them) and it has the lowest computational costs (10); MHR with N = 2 uses four successive nodes to compute unknown coordinate; MHR version for N = 4 applies eight successive nodes to get unknown point and MHR with N = 8 needs sixteen successive nodes to calculate unknown coordinate (it has the biggest computational costs).

Step 3: Choice of distribution [alpha] = F([alpha]): basic distribution for [gamma] = [alpha].

Step 4: Determining values of a: a = 0.1, 0.2 ... 0.9 (nine points) or 0.01, 0.02 ... 0.99 (99 points) or others.

Step 5: The computations (9).

These five steps can be treated as the algorithm of MHR method of curve modeling and interpolation (6)-(9).

Considering nowadays used probability distribution functions for random variable [alpha] [member of] [0,1]--one distribution is dealing with the range [0,1]: beta distribution. Probability density function f for random variable a [member of] [0,1] is:

f([alpha]) = c x [[alpha].sup.s] x [(1 - [alpha]).sup.r], s [greater than or equal to] 0, r [greater than or equal to] 0 (42)

When r = 0 probability density function (42) represents f([alpha]) = c x [[alpha].sup.s] and then probability distribution function F is like (12), for example f([alpha]) = 3[[alpha].sup.2] and [gamma]=[[alpha].sup.3]. If s and r are positive integer numbers then [gamma] is the polynomial, for example f([alpha]) = 6[alpha](1 - [alpha]) and [gamma] = 3[[alpha].sup.2]-2[[alpha].sup.3]. So beta distribution gives us coefficient [gamma] in (7) as polynomial because of interdependence between probability density f and distribution F functions:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (43)

For example (43): f([alpha]) = [alpha] x [e.sup.[alpha]] and [gamma] = F([alpha]) = ([alpha] - 1)[e.sup.[alpha]] + 1.

What is very important: two curves may have the same set of nodes but different N or [gamma] results in different interpolations (Fig.6-13). Here are some applications of MHR method with basic version ([gamma] = [alpha]): MHR-2 is MHR version with matrices of dimension N = 2 and MHR-4 means MHR version with matrices of dimension N= 4.

Figures 2-5 show interpolation of continues functions connected with determined formula. So these functions are interpolated and modeled. Without knowledge about the formula, curve interpolation has to implement the coefficients [gamma] (12)-(43), but MHR is not limited only to these coefficients. Each strictly monotonic function F between points (0;0) and (1:1) can be used in MHR interpolation. MHR 2D data extrapolation is possible for [alpha] < 0 or [alpha]>l.

3 Implementations of 2D probabilistic interpolation

Curve knots (0.1; 10), (0.2;5), (0.4;2.5), (1;1) and (2;5) from Fig.1 are used in some examples of MHR interpolation with different [gamma]. Points of the curve are calculated for N = 1 and [gamma] = [alpha] (11) in example 1 and with matrices of dimension N = 2 in examples 2 - 8 for [alpha] = 0.1, 0.2, ..., 0.9.

These eight examples demonstrate possibilities of curve interpolation for key nodes. Reconstructed values and interpolated points, calculated by MHR method, are applied in the process of curve modeling. Every curve can be interpolated by some distribution function as parameter [gamma]. This parameter is treated as probability distribution function for each curve.

4 MHR 2D modeling versus polynomial interpolation

4.1 Example 4.1

Let us consider a graph of function f(x) = 2/x in range [0.4,1.6], There are given five interpolation nodes for x = 0.4, 0.7, 1.0, 1.3, 1.6. The curve y = 2/x reconstructed by basic MHR method (12) with IV = 2 for s = 1 looks not precisely:

Lagrange interpolation polynomial is not to be accepted:

For better reconstruction of the curve, appropriate parameters in MHR method (12) is calculated. Choice of parameter s is connected with comparison of accurate values w, for function f(x) = 2/x in control points [p.sub.i], situated in the middle between interpolation nodes ([alpha]=0.5), and values in control points [p.sub.i] computed by MHR method. Control points are settled in the middle between interpolation nodes, because interpolation error of MHR method is the biggest. Choice of coefficient s is done by criterion: difference between precise values [w.sub.i] and values reconstructed by MHR method is the smallest. Control points pf in this example are established for [x.sub.i] = 0.55, 0.85, 1.15, 1.45. Four values of the curve are compared for parameter 5 = 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2.0. The smallest difference is calculated for s = 1.5:

[absolute value of (w1 - 3.694)] + [absolute value of (w3 - 1.632) + [absolute value of (w2 - 2.302)] + [absolute value of (w4- 1.329)] = 0.266 (44)

Calculations for average OHR operator M(7) are done:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Computed values appear in (44). Other results:

a) s=0.1

[absolute value of (w1 - 5.815)] + [absolute value of (w3 - 1.939)] + [absolute value of (w2 - 3.209)] + [absolute value of (w4 - 1 601) = 3.456

b) s=0.2:

[absolute value of (w1 - 5.587)] + [absolute value of (w3 - 1.906)] + [absolute value of (w2 - 3.111)] + [absolute value of (w4 - 1.572)] = 3.068

c) s=0.3:

[absolute value of (w1 - 5.373) + [absolute value of (w3 - 1.875)] + [absolute value of (w2 - 3.02)] + [absolute value of (w4 - 1.544)] = 2.704

d) s=0.4:

[absolute value of (w1 - 5.174)] + [absolute value of w3 - 1.846)] + [absolute value of (w2 - 2.935)] + [absolute value of (w4 - 1.519)] = 2.366

e) s=0.5:

[absolute value of (w1 - 4988)] + [absolute value of (w3 - 1.819)] + [absolute value of (w2 - 2.856)] + [absolute value of (w4 - 1.495)] = 2.05

f) s=0.6:

[absolute value of (w1 - 4.815)] + [absolute value of (w3 - 1.794)] + [absolute value of (w2 - 2.782)] + [absolute value of (w4 - 1.473)] = 1.756

g) s=0.7:

[absolute value of (w1 - 4.653)] + [absolute value of (w3 - 1.771)] + [absolute value of (w2 - 2.712)] + [absolute value of (w4 - 1.452)] = 1.48

h) s=0.8:

[absolute value of (w1 - 4.503)] + [absolute value of (w3 - 1.749) + [absolute value of (w2 - 2.648)] + [absolute value of (w4 - 1.433)] = 1.225

i) s=0.9:

[absolute value of (w1 - 4.362)] + [absolute value of (w3 - 1.728)] + [absolute value of (w2 - 2.588)] + [absolute value of (w4 - 1.415)] = 1.008

j) s=1:

[absolute value of w1 - 4.23)] + [absolute value of (w3 - 1.709) + [absolute value of (w2 - 2.532)] + [absolute value of (w4 - 1.398)] = 0.822

k) s=1.1:

[absolute value of (w1 - 4.108)] + [absolute value of (w3 - 1.692)] + [absolute value of (w2 - 2.479)] + [absolute value of (w4 - 1.382)] = 0.648

l) s=1.2:

[absolute value of (w1 - 3.994)] + [absolute value of (w3 - 1.675) + [absolute value of (w2-2.43)] + [absolute value of (w4 - 1.368)] = 0.51

m) s=1.3:

[absolute value of (w1 - 3.887)] + [absolute value of (w3 - 1.66)] + [absolute value of (w2 - 2.385)] + [absolute value of (w4 - 1.354) = 0.387

n) s=1.4:

[absolute value of (w1 - 3.787)] + [absolute value of (w3 - 1.645)] + [absolute value of (w2 - 2.342)] + [absolute value of (w4 - 1.341)] = 0.294

o) s=1.6:

[absolute value of w1 - 3.608)] + [absolute value of (w3 - 1.619)] + [absolute value of (w2 - 2.265)] + [absolute value of (w4 - 1.318)] = 0.298

p) s=1.7:

[absolute value of (w1 - 3.527)] + [absolute value of (w3 - 1.608)] + [absolute value of (w2 - 2.231)] + [absolute value of (w4 - 1.308)] = 0.434

q) s=1.8:

[absolute value of (w1 -3.451)] + [absolute value of (w3 - 1.597)] + [absolute value of (w2 - 2.199)] + [absolute value of (w4 - 1.298)] = 0.563

r) s=1.9:

[absolute value of (w1 - 3.381)] + [absolute value of (w3 - 1.587)] + [absolute value of (w2 - 2.169) + [absolute value of (w4 - 1.289)] = 0.682

s) s=2.0:

[absolute value of (w1 - 3.315)] + [absolute value of (w3 - 1.577)] + [absolute value of (w2 - 2.14) + [absolute value of (w4 - 1.281)] = 0.795

One can see the changes of interpolation error. Reconstruction of the curve y=2/x by MHR method for N = 2 and [gamma] = [[alpha].sup.1.5] looks as follows:

Figure 16 represents the curve y = 2/x more precisely then classical interpolation and Figure 14. If we would like to have better parameter s (with two digits after coma), calculations are done:

a) s=1.49: [absolute value of w1-3.703] + [absolute value of w3-1.633] + [absolute value of w2-2.306] + [absolute value of w4-1.33] = 0.269

b) s=1.51: [absolute value of w1- 3.683] + [absolute value of w3-1.631] + [absolute value of w2-2.299] + [absolute value of w4-1.328] = 0.262

c) s=1.52: [absolute value of w1-3.677] + [absolute value of w3-1.629] + [absolute value of w2-2.295] + [absolute value of w4-1.327] = 0 .261

d) s=1.53: [absolute value of w1-3.668] + [absolute value of w3-1.628] + [absolute value of w2-2.291] + [absolute value of w4-1.326] = 0.258

e) s=1.54: [absolute value of w1-3.659] + [absolute value of w3-1.627] + [absolute value of w2-2.287] + [absolute value of w4-1.325] = 0.255

f) s=1.55: [absolute value of w1-3.65] + [absolute value of w3-1.626] + [absolute value of w2-2.284] + [absolute value of w4-1.324] = 0.251

g) s=1.56: [absolute value of w1-3.642] + [absolute value of w3-1.624] + [absolute value of w2-2.28] + [absolute value of w4-1.323] = 0.25

h) s=1.57: [absolute value of w1-3.633] + [absolute value of w3-1.623] + [absolute value of w2-2.276] + [absolute value of w4-1.321] = 0.255

i) s=1.58: [absolute value of w1-3.625] + [absolute value of w3-1.622] + [absolute value of w2-2.273] + [absolute value of w4-1.32] = 0.268

j) s=1.59: [absolute value of w1-3.616] + [absolute value of w3-1.621] + [absolute value of w2-2.269] + [absolute value of w4-1.319] = 0.283

Model of the curve for s = 1.56 in (12) is more accurate then with s = 1.5.

Convexity of reconstructed curve is very important factor in MHR method with parameter s. Appropriate choice of parameter 5 is connected with regulation and controlling of convexity: model of the curve (Fig. 16) preserves monotonicity and convexity.

4.2 Example 4.2

This example considers a graph of function f{x) = 1/(1 + 5[x.sup.2]) in the range [-1,1]:

There are given five interpolation nodes for x = -1.0, -0.5, 0, 0.5, 1.0. It is an example of function with useless Lagrange interpolation polynomial: Runge phenomenon and unpleasant two minima.

Model of the curve y = 1/(1 + 5[x.sup.2]) in basic MHR method (12) for N = 2 and s = 1:

Reconstructed curve (Fig. 19) preserves monotonicity and symmetry for s = 1. Comparing precise values [w.sub.i] with values computed by MHR method in control points [p.sub.i], fixed for [x.sub.i] = -0.75, -0.25, 0.25, 0.75, identical the best results appear for s = 1 (12): [absolute value of w1-0.299] + [absolute value of w3-0.688] + [absolute value of w2-0.688] + [absolute value of w4- 0.299] = 0.221

(45)

and for s = 0.5, 0.6, 0.7, 0.8, 0.9, 1.1, 1.2, 1.3, 1.4, 1.5, 1.7, 1.8, 1.9. But only for s = 1 reconstructed curve is symmetric- look at values in (45). So if a case s = 1 appears among the best results, then model ought to be built for s = 1. And if a case s = 1 does not appear among the best results, then model ought to be built for 5 near by 1. Here is an example of reconstructed curve for s=1.5 (without feature of symmetry):

The best model of the curve y = 1/(l + 5[x.sup.2]), built by MHR method for s = 1 (Fig. 19), preserves monotonicity and symmetry. Convexity of the function (Fig. 17) can make some troubles.

5 Future research directions

Future works with MHR method are connected with object recognition after geometrical transformations of curve (translations, rotations, scaling)- only nodes are transformed and new curve (for example contour of the object) for new nodes is reconstructed. Also estimation of object area in the plane, using nodes of object contour, will be possible by MHR interpolation. Object area is significant feature for object recognition. Future works are dealing with smoothing the curve, parameterization of whole curve and possibility to apply MHR method to three-dimensional curves. Also case of equidistance nodes must be studied with all details. Another future research direction is to apply MHR method in artificial intelligence and computer vision, for example identification of a specific person's face or fingerprint, optical character recognition (OCR), image restoration, content-based image retrieval and pose estimation. Future works are connected with object recognition for any set of contour points. There are several specialized tasks based on recognition to consider and it is important to use the shape of whole contour for identification and detection of persons, vehicles or other objects. Other applications of MHR method will be directed to computer graphics, modeling and image processing.

6 Conclusion

The method of Hurwitz-Radon Matrices (MHR) enables interpolation of two-dimensional curves using different coefficients [gamma]: polynomial, sinusoidal, cosinusoidal, tangent, cotangent, logarithmic, exponential, arcsin, arccos, arctan, arcctg or power function [16], also inverse functions. Function for [gamma] calculations is chosen individually at each curve modeling and it is treated as probability distribution function: [gamma] depends on initial requirements and curve specifications. MHR method leads to curve interpolation via discrete set of fixed knots. So MHR makes possible the combination of two important problems: interpolation and modeling. Main features of MHR method are:

a) the smaller distance between knots the better;

b) calculations for coordinate x close to zero and near by extremum require more attention;

c) MHR interpolation of the function is more precise then linear interpolation;

d) minimum two interpolation knots for calculations without matrices when N=1. but MHR is not a linear interpolation;

e) interpolation of L points is connected with the computational cost of rank O(L);

f) MHR is well-conditioned method (orthogonal matrices)[17];

g) coefficient [gamma] is crucial in the process of curve probabilistic interpolation and it is computed individually for a single curve;

h) MHR 2D data extrapolation is possible for [alpha] < 0 or [alpha] > 1.

Future works are going to: choice and features of coefficient [gamma], implementation of MHR in object recognition [18], shape geometry, contour modeling and parameterization [19].

References

[1] Collins II. G.W.: Fundamental Numerical Methods and Data Analysis. Case Western Reserve University (2003)

[2] Chapra, S.C.: Applied Numerical Methods. McGraw-Hill (2012)

[3] Ralston, A., Rabinowitz, P.: A First Course in Numerical Analysis--Second Edition. Dover Publications, New York (2001)

[4] Zhang, D., Lu, G.: Review of Shape Representation and Description Techniques. Pattern Recognition 1(37), 1-19(2004)

[5] Schumaker, L.L.: Spline Functions: Basic Theory. Cambridge Mathematical Library (2007)

[6] Dahlquist, G., Bjoerck, A.: Numerical Methods. Prentice Hall, New York (1974)

[7] Eckmann, B.: Topology, Algebra, Analysis Relations and Missing Links. Notices of the American Mathematical Society 5(46), 520-527 (1999)

[8] Citko, W., Jakobczak, D., Sienko, W.: On Hurwitz--Radon Matrices Based Signal Processing. Workshop Signal Processing at Poznan University of Technology (2005)

[9] Tarokh, V., Jafarkhani, H., Calderbank, R.: Space-Time Block Codes from Orthogonal Designs. IEEE Transactions on Information Theory 5(45), 1456-1467 (1999)

[10] Sienko, W., Citko, W., Wilamowski, B.: Hamiltonian Neural Nets as a Universal Signal Processor. 28th Annual Conference of the IEEE Industrial Electronics Society IECON (2002)

[11] Sienko, W., Citko, W.: Hamiltonian Neural Net Based Signal Processing. The International Conference on Signal and Electronic System ICSES (2002)

[12] Jakobczak, D.: 2D and 3D Image Modeling Using Hurwitz-Radon Matrices. Polish Journal of Environmental Studies 4A(16), 104-107 (2007)

[13] Jakobczak, D.: Shape Representation and Shape Coefficients via Method of Hurwitz-Radon Matrices. Lecture Notes in Computer Science 6374 (Computer Vision and Graphics: Proc. ICCVG 2010, Part I), Springer-Verlag Berlin Heidelberg, 411-419(2010)

[14] Jakobczak, D.: Curve Interpolation Using Hurwitz-Radon Matrices. Polish Journal of Environmental Studies 3B(18), 126-130 (2009)

[15] Jakobczak, D.: Application of Hurwitz-Radon Matrices in Shape Representation. In: Banaszak, Z., Swic, A. (cds.) Applied Computer Science: Modelling of Production Processes 1(6), pp. 63-74. Lublin University of Technology Press, Lublin (2010)

[16] Jakobczak, D.: Object Modeling Using Method of Hurwitz-Radon Matrices of Rank k. In: Wolski, W., Borawski, M. (eds.) Computer Graphics: Selected Issues, pp. 79-90. University of Szczecin Press, Szczecin (2010)

[17] Jakobczak, D.: Implementation of Hurwitz-Radon Matrices in Shape Representation. In: Choras, R.S. (ed.) Advances in Intelligent and Soft Computing 84, Image Processing and Communications: Challenges 2, pp. 39-50. Springer-Verlag. Berlin Heidelberg (2010)

[18] Jakobczak, D.: Object Recognition via Contour Points Reconstruction Using Hurwitz-Radon Matrices. In: Jozefczyk, J., Orski, D. (eds.) Knowledge-Based Intelligent System Advancements: Systemic and Cybernetic Approaches, pp. 87-107. IGI Global, Hershey PA, USA (2011)

[19] Jakobczak, D.: Curve Parameterization and Curvature via Method of Hurwitz-Radon Matrices. Image Processing & Communications- An International Journal 1-2(16),49-56,(2011)

Dariusz Jacek Jakobczak

Department of Electronics and Computer Science, Technical University of Koszalin, Sniadeckich 2, 75-453 Koszalin, Poland

E-mail: dariusz.jakobczak@tu.koszalin.pi

Received: June 25, 2014
COPYRIGHT 2015 Slovenian Society Informatika
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2015 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Jakobczak, Dariusz Jacek
Publication:Informatica
Article Type:Report
Date:Mar 1, 2015
Words:5290
Previous Article:A rule-based system for automatic de-identification of medical narrative texts.
Next Article:Swarm intelligence and its application in abnormal data detection.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters