Ryszard Kozera
email: ryszardkozera@sggw.pllyle.noakes@maths.uwa.edu.aup.szmielew@ieee.org

Lyle Noakes

Piotr Szmielew

Trajectory Estimation for Exponential Parameterization and Different Samplings

Keywords: Interpolation, numerical analysis, computer graphics and vision

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The sampled data points Q m = {q i } m i=0 with γ(t i ) = q i ∈ IR n define the pair ({t i } m i=0 , Q m ) commonly coined as non-reduced data. We also require here that t i < t i+1 and q i = q i+1 hold. Moreover, assume that γ : [0, T ] → IR n (with 0 < T < ∞) is sufficiently smooth (specified later) and that it defines a regular curve γ(t) = 0. In order to estimate the unknown curve γ with an arbitrary interpolant γ : [0, T ] → IR n it is necessary to assume that {t i } m i=0 ∈ V m G , i.e. that the following admissibility condition is satisfied: lim m→∞ δ m = 0, where δ m = max 0≤i≤m-1 (t i+1 -t i ).

(

) 1
We omit here the subscript m in δ m by setting δ = δ m . In this paper, two substantial subfamilies of V m G are discussed. The first one V m mol ⊂ V m G includes more-or-less uniform samplings [START_REF] Kozera | Curve modeling via interpolation based on multidimensional reduced data[END_REF], [START_REF] Noakes | More-or-less uniform samplings and lengths of curves[END_REF]:

βδ ≤ t i+1 -t i ≤ δ, (2)
for some β ∈ (0, 1]. The left inequality in [START_REF] Noakes | Length estimation for curves with ε-uniform samplings[END_REF] excludes samplings with distance between consecutive knots smaller then βδ. The right inequality follows from [START_REF] Janik | Reduced data for curve modeling -applications in graphics, computer vision and physics[END_REF]. Condition [START_REF] Noakes | Length estimation for curves with ε-uniform samplings[END_REF], as shown in [START_REF] Kozera | Curve modeling via interpolation based on multidimensional reduced data[END_REF], can be replaced by the equivalent condition (3) holding for each i = 0, 1, . . . m -1 and some constants 0 < K 1 ≤ K 2 :

K 1 m ≤ t i+1 -t i ≤ K 2 m . (3)
The second subfamily V m ε ⊂ V m G is that of ε-uniform samplings [START_REF] Noakes | Length estimation for curves with ε-uniform samplings[END_REF]:

t i = φ( iT m ) + O( 1 m 1+ε ), (4)
where ε 0, φ : [0, T ] → [0, T ] is smooth and φ > 0 (so that t i < t i+1 ). Clearly, the smaller ε gets, the bigger distortion of uniform distribution occurs (modulo φ). The case when ε = 0 needs a special attention so that the inequality t i < t i+1 holds. However, the latter is asymptotically guaranteed for all ε positive. Note that each ε-uniform sampling with ε > 0 is also more-or-less uniform [START_REF] Kozera | Curve modeling via interpolation based on multidimensional reduced data[END_REF].

Problem Formulation and Motivation

We say that the family F δ : [0, T ] → IR n satisfies F δ = O(δ α ) if F δ = O(δ α ), where • denotes the Euclidean norm. Another words there are constants K > 0 and δ 0 > 0 such that F δ ≤ Kδ α , for all δ ∈ (0, δ 0 ) and t ∈ [0, T ] - [START_REF] Ralston | A First Course in Numerical Analysis[END_REF].

A standard result for non-reduced data ({t i } m i=0 , Q m ) for piecewise r-degree polynomial γ = γr reads [START_REF] Kozera | Curve modeling via interpolation based on multidimensional reduced data[END_REF], [START_REF] De Boor | A Practical Guide to Splines[END_REF]:

Theorem 1. Let γ ∈ C r+1 be a regular curve γ : [0, T ] → IR n with knot pa- rameters {t i } m i=0 ∈ V m G given.
Then a piecewise r-degree Lagrange polynomial interpolation γr used with {t i } m i=0 known, yields a sharp estimate:

γr = γ + O(δ r+1 ). (5)
By ( 5) piecewise-quadratics (-cubics) γ2 (γ 3 ) yield cubic (quartic) order error terms.

In many applications in computer graphics and computer vision, engineering or physics, the so-called reduced data Q m are encountered (see e.g. [START_REF] Janik | Reduced data for curve modeling -applications in graphics, computer vision and physics[END_REF], [START_REF] Kocić | Blending parameterization of polynomial and spline interpolants[END_REF], [START_REF] Kvasov | Methods of Shape-Preserving Spline Approximation[END_REF], or [START_REF] Piegl | The NURBS Book[END_REF]), where the knots {t i } m i=0 are unknown and have to be first guessed somehow. A family of the so-called exponential parameterization { ti } m i=0 ≈ {t i } m i=0 is commonly used for curve modeling [START_REF] Kvasov | Methods of Shape-Preserving Spline Approximation[END_REF], [START_REF] Lee | Choosing nodes in parametric curve interpolation[END_REF]:

t0 = 0, ti+1 = ti + q i+1 -q i λ , (6)
where 0 ≤ λ ≤ 1 and i = 0, 1, . . . , m -1. The cases when λ ∈ {1, 0.5, 0}, yield cumulative chords, centripetal or blind uniform parameterizations, respectively. We call a piecewise r-degree polynomial based on [START_REF] Kozera | Curve modeling via interpolation based on multidimensional reduced data[END_REF] and Q m as γ = γr : [0, T ] → IR n , where T = m-1 i=0 q i+1 -q i λ . Note that in case of any reduced data Q m for asymptotics estimation of γ by γr , a re-parameterization ψ : [0, T ] → [0, T ] synchronizing both domains of γ and γr , needs to be defined (see e.g. [START_REF] Kozera | Curve modeling via interpolation based on multidimensional reduced data[END_REF]). Example 1. Figure 1 shows different γ2 passing through Q 2 with various λ ∈ {0, 1/3, 1/2, 5/6, 1} set in [START_REF] Kozera | Curve modeling via interpolation based on multidimensional reduced data[END_REF]. Such curves' fluctuation given different knots and interpolation schemes is commonly exploited for sparse data in 2D and 3D computer graphics in the context of curve modeling -see [START_REF] Kocić | Blending parameterization of polynomial and spline interpolants[END_REF], [START_REF] Kvasov | Methods of Shape-Preserving Spline Approximation[END_REF], or [START_REF] Piegl | The NURBS Book[END_REF].

Example 2. Another application, elucidating the influence of knots selection on interpolation stems from the computer vision field. Figure 2 shows the image of the same knee joint section. The goal is to isolate from such image the kneecap and to find its area, amounting here to A = 5237 pixels. The interpolation points Q m positioned on the boundary are selected e.g. by the physician (here m = 5). Of course, the internal parametrization of the kneecap boundary (i.e. some curve γ) remains unknown. Upon invoking γ2 (with three quadratic segments) coupled with guessed knots in accordance with [START_REF] Kozera | Curve modeling via interpolation based on multidimensional reduced data[END_REF] we obtain different estimates of γ by γ2 and consequently various kneecap area A λ approximations. Namely for λ ∈ {0, 1/4, 1/2, 3/4, 1} the following A ≈ A λ ∈ {5197, 5209, 5234, 5293, 5376} (in pixels) hold, respectively. The centripetal parameterization (i.e. for λ = 1/2) on this specific sparse data Q m yields the best result.

More real data examples emphasizing the importance of the knots' selection for a given interpolation scheme in computer graphics (light-source motion estimation or image rendering), computer vision (image segmentation or video compression), geometry (trajectory, curvature or area estimation) or in engineering and physics (fast particles' motion estimation) can be found e.g. in [START_REF] Janik | Reduced data for curve modeling -applications in graphics, computer vision and physics[END_REF]. The case when λ = 0, transforms (6) into to blind uniform knots' guesses ti = i. For r = 2 and λ = 0 in (6) the following holds [START_REF] Noakes | Length estimation for curves with ε-uniform samplings[END_REF]: Theorem 2. Let the unknown {t i } m i=0 be sampled ε-uniformly, where ε > 0 and γ ∈ C 4 . Then there is a uniform piecewise-quadratic Lagrange interpolant γ2 : [0, T = m] → IR n , calculable in terms of Q m (with ti = i) and piecewise C ∞ re-parameterization ψ : [0, T ] → [0, T ] such that sharp estimates hold:

γ2 • ψ = γ + O(δ min{3,1+2ε} ). (7)
Th. 2 with α ε>0 (0) = min{3, 1 + 2ε} extends to ε = 0 provided {t i } m i=0 satisfies t i < t i+1 and falls also into more-or-less uniformity [START_REF] Noakes | Length estimation for curves with ε-uniform samplings[END_REF]. The latter renders linear convergence order α ε=0 (0) = 1 -see [START_REF] Kozera | Curve modeling via interpolation based on multidimensional reduced data[END_REF]. Evidently, for ε-uniform samplings there is an acceleration from α ε=0 (0) = 1 via α 0<ε<1 (0) = 1 + 2ε to α ε≥1 (0) = 3.

Cumulative Chords -λ = 1

The opposite case when λ = 1 in (6) renders cumulative chords [START_REF] Kvasov | Methods of Shape-Preserving Spline Approximation[END_REF], [START_REF] Piegl | The NURBS Book[END_REF]. This choice of { ti } m i=0 uses the geometry of Q m and gives better trajectory estimation (at least for r = 2, 3) as opposed to λ = 0 and (7) [START_REF] Noakes | Cumulative chords piecewise-quadratics and piecewisecubics[END_REF]:

Theorem 3. Let γ be a regular C k curve in IR n , where k r + 1 and r = 2, 3 sampled according to (1). Let γr : [0, T = m-1 i=0 q i+1 -q i ] → IR n be the cumulative chord piecewise-quadratic(-cubic) interpolant defined by Q m and λ = 1 in (6). Then there is a piecewise-C r re-parameterization ψ : [0, T ] → [0, T ], with γr • ψ = γ + O(δ r+1 ). ( 8
)
The asymptotics from Th. 2 and Th. 3 are sharp -see [START_REF] Noakes | Cumulative chords piecewise-quadratics and piecewisecubics[END_REF] and [START_REF] Kozera | Curve modeling via interpolation based on multidimensional reduced data[END_REF]. For r = 2 and λ = 1, formula (8) yields the cubic order α(1) = 3 which not only improves [START_REF] Noakes | More-or-less uniform samplings and lengths of curves[END_REF] but also matches the non-reduced data case (5) (with r = 2, 3).

Exponential Parameterization -λ ∈ [0, 1]

Recent research by [START_REF] Kozera | Piecewise-quadratics and exponential parameterization for reduced data[END_REF] extends the results from Th. 2 (where λ = 0) and Th. 3 (where λ = 1 with r = 2) to the remaining cases of exponential parameterization [START_REF] Kozera | Curve modeling via interpolation based on multidimensional reduced data[END_REF] i.e. to λ ∈ [0, 1]. As proved in [START_REF] Kozera | Piecewise-quadratics and exponential parameterization for reduced data[END_REF], for more-or-less uniform samplings (2), ( 6) and r = 2 any choice of λ ∈ [0, 1) does not improve the asymptotics for γ approximation. In fact, for all λ ∈ [0, 1) we have α(λ) = 1. Indeed we obtain [START_REF] Kozera | Piecewise-quadratics and exponential parameterization for reduced data[END_REF]:

Theorem 4. Suppose γ is a regular C 3 curve in IR n sampled more-or-less uni- formly (2). Let γ2 : [0, T = m-1 i=0 q i+1 -q i λ ] → IR n be the piecewise-quadratic interpolant defined by Q m and (6) (with λ ∈ [0, 1]). Then there is a piecewise-C ∞ re-parameterization ψ : [0, T ] → [0, T ], such that for λ ∈ [0, 1) we have: γ2 • ψ = γ + O(δ). (9)
In addition, for either {t i } m i=0 uniform or λ = 1 used with samplings (1) the following holds:

γ2 • ψ = γ + O(δ 3 ). ( 10
)
Both ( 9) and ( 10) are sharp (proved analytically). Th. 4 underlines discontinuity of α(λ) at λ = 1 with the jump by 2 in respective convergence orders. Another unexpected fact comes from the proof of Th. 4. Namely, a natural candidate for a re-parameterization, i.e. a Lagrange quadratic ψ i : [t i , t i+2 ] → [ ti , ti+2 ] satisfying ψ i (t i+j ) = ti+j (for j = 0, 1, 2) can be a non-injective function [START_REF] Kozera | Piecewise-quadratics and exponential parameterization for reduced data[END_REF].

The most recent result [START_REF] Kozera | Exponential parameterization and ε-uniformly sampled reduced data[END_REF] shows that for ε-uniform samplings (4) (with ε > 0) the asymptotics established in Th. 4 improves from α(λ) = 1 to α ε>0 (λ) = min{3, 1 + 2ε}, for each λ ∈ [0, 1). Indeed the following holds [START_REF] Kozera | Exponential parameterization and ε-uniformly sampled reduced data[END_REF]: Theorem 5. Suppose γ is a regular C 4 curve in IR n sampled according to the ε-uniformity condition (4) with ε > 0. Let γ2 : [0, T = m-1 i=0 q i+1 -q i λ ] → IR n be the piecewise-quadratic interpolant defined by Q m and (6) (with λ ∈ [0, 1)). Then there is a piecewise-C ∞ re-parameterization ψ : [0, T ] → [0, T ], such that:

γ2 • ψ = γ + O(δ min{3,1+2ε} ). ( 11
)
By Th. 4, formula [START_REF] Kvasov | Methods of Shape-Preserving Spline Approximation[END_REF]

extends to ε = 0 (with λ ∈ [0, 1)) if extra condition (2) on 0-uniform sampling is imposed. The case λ = 1 by Th. 4 yields γ2 •ψ = γ+O(δ 3 ).
Again [START_REF] Kvasov | Methods of Shape-Preserving Spline Approximation[END_REF] is proved analytically to be sharp. Clearly, by Th. 5 an extra acceleration [START_REF] Kvasov | Methods of Shape-Preserving Spline Approximation[END_REF] in convergence rates for all λ ∈ [0, 1] and (4) with ε > 0 occurs. The latter coincides with Th. 2 holding for λ = 0. The formula [START_REF] Kvasov | Methods of Shape-Preserving Spline Approximation[END_REF] is only dependent on ε, not on λ. It should be pointed out that by [START_REF] Kozera | Exponential parameterization and ε-uniformly sampled reduced data[END_REF], for each ε > 0 the quadratic ψ i defines a genuine re-parameterization of [t i , t i+2 ] into [ ti , ti+2 ].

Aim of this Research

In this paper we verify experimentally the sharpness of asymptotics for trajectory estimation claimed by Th. 4 and Th. 5. By sharpness we understand the existence of at least one curve γ ∈ C r ([0, T ]) (with r set accordingly) sampled with some admissible samplings {t i } m i=0 ∈ V m G for which the asymptotic estimates in question are exactly matched. The tests conducted herein are confined merely to the planar and spatial curves. It should, however be emphasized that all quoted herein Theorems 1-5 admit regular curves in IR n . Some motivation standing behind the applications of interpolating reduced data is also here presented. More examples of real reduced n-dimensional data Q m which can be fitted with piecewise-quadratics γ2 or any other interpolation schemes based on exponential parameterization (6) can be found e.g. in [START_REF] Janik | Reduced data for curve modeling -applications in graphics, computer vision and physics[END_REF].

Experiments

All tests presented in this paper are performed in Mathematica 9.0 [14] on a 2.4GHZ Intel Core 2 Duo computer with 8GB RAM. Note that since T = m i=1 (t i+1 -t i ) ≤ mδ the following holds m -α = O(δ α ), for α > 0. Hence, the verification of any asymptotics expressed in terms of O(δ α ) can be performed by examining the claims of Th. 4 or Th. 5 in terms of O(1/m α ) asymptotics.

Note that for a parametric regular curve γ : [0, T ] → IR n , λ ∈ [0, 1] and m varying between m min ≤ m ≤ m max the i-th component of the error for γ estimation is defined here as follows:

E i m = sup t∈[ti,ti+2] (γ 2,i • ψ i )(t) -γ(t) = max t∈[ti,ti+2] (γ 2,i • ψ i )(t) -γ(t) , as Ẽi m (t) = (γ 2,i • ψ i )(t) -γ(t) ≥ 0 is continuous over each compact subinter- val [t i , t i+2 ] ⊂ [0, T ]. The maximal value E m of Ẽm (t) (the track-sum of Ẽi m (t)
), for each m = 2k (here k = 1, 2, 3, . . . , m/2) is found by using Mathematica optimization built-in functions: Maximize or FindMinimum (the latter applied to -Ẽm (t)). From the set of absolute errors {E m } mmax m=mmin the numerical estimate ᾱ(λ) of genuine order α(λ) is subsequently computed by using a linear regression applied to the pair of points (log(m), -log(E m )) (see also [START_REF] Kozera | Curve modeling via interpolation based on multidimensional reduced data[END_REF]). Since piecewisely deg(γ 2 ) = 2 the number of interpolation points {q i } m i=0 is odd i.e. m = 2k as indexing runs over 0 ≤ i ≤ m. The Mathematica built-in functions LinearModelFit renders the coefficient ᾱ(λ) from the computed regression line y(x) = ᾱ(λ)x + b based on pairs of points {(log(m), -log(E m ))} mmax m=mmin . Finally, recall that as justified in Th. 5 any ε-uniform sampling with ε > 0 gives asymptotically ψ i as re-parameterization of [t i , t i+2 ] into [ ti , ti+2 ]. Once ε = 0, one may apply a simple computational test (for m = m max ) by verifying whether either ψ

i (t i ) ≥ 0 and ψ (1) i (t i+2 ) > 0 or ψ (1) i (t i ) > 0 and ψ (1) i (t i+2 ) ≥ 0 hold over each subinter- val [t i , t i+2
]. The latter combined with the linearity of ψ (1) i guarantees that ψ i is a re-parameterization. More discussion on the issue of enforcing ψ i to be a re-parameterization can be found in [START_REF] Kozera | Exponential parameterization and ε-uniformly sampled reduced data[END_REF].

Fitting Reduced Data for Planar Curves

The testing commences with the simplest possible curve, i.e. a straight line.

Example 3. Consider a regular straight line: γ l (t) = t/ √ 5, 2t/ √ 5 ⊂ IR 2 for t ∈ [0, 1], sampled with δ 1 = i/m according to ε-uniform sampling (4) (with ε > 0):

t i+1 -t i = δ 1 (1 + δ ε 1 ) and t i+2 -t i = δ 1 (1 -δ ε 1 ), ( 12
)
where t 0 = 0 and t m = 1. The plot of γ l sampled by [START_REF] Piegl | The NURBS Book[END_REF], with ε = 0.5 and m = 12 is shown in Figure 3. Recalling (1), note that here δ = δ 1 (1 + δ ε 1 ). As

✵ ✁ ✵ ✂ ✵ ✄ ✵ ☎ ✵ ✂ ✵ ☎ ✵ ✆ ✵ ✝
Fig. 3. The plot of the line γ l sampled as in [START_REF] Piegl | The NURBS Book[END_REF], for m = 12 and ε = 0.5 ε > 0, the quadratic ψ i is a re-parameterization [START_REF] Kozera | Exponential parameterization and ε-uniformly sampled reduced data[END_REF]. The linear regression applied to m min = 100 ≤ m ≤ m max = 120 yields the estimates for ᾱε (λ) ≈ α ε (λ) = min{3, 1 + 2ε} which are presented in Table 1. An inspection of Table 1 confirms the sharpness or nearly sharpness of Th. 5. We pass now to the next example involving a spiral curve in IR 2 .

λ ε = 0.1 ε = 0.33 ε = 0.5 ε = 0.7 ε = 0.9 ε = 1 αε(λ) 1.
Example 4. Consider now the following regular spiral curve γ sp1 : [0, 1] → IR 2 : γ sp1 (t) = ((t + 0.2) cos(π(1 -t)), (t + 0.2) sin(π(1 -t))), sampled according to the following ε-uniform sampling (4):

t i = i m + (-1) i+1 m 1+ε , ( 13
)
with t 0 = 0 and t m = 1. Figure 4 shows γ sp1 (a dashed line) and γ2 (a continuous line) sampled by ( 13) with ε = 0.7, m = 12 and λ ∈ {0, 1}. The difference between both γ2 and γ sp1 on sparse data Q 12 is minor as they both overlap. The Th. 5, for ε > 0 yields

✁ ✵ ✁ ✵ ✂ ✵ ✄ ✵ ☎ ✶ ✵ ✶ ✁ ✵ ✶ ✵ ✁ ✵ ✆ ✵ ✂ ✵ ✝ ✵ ✄ ✵ ✞ a) b)
ψ i : [t i , t i+2 ] → [ ti , ti+2
] as a re-parameterization. The case of ε = 0 renders (13) as more-or-less uniform (3) with K 1 = 1/3 and K 2 = 5/3. Sufficient conditions for ψ i to be a re-parameterization are formulated in [START_REF] Kozera | Exponential parameterization and ε-uniformly sampled reduced data[END_REF]. The latter enables to verify the validity of Th. 4 also for ε = 0. The linear regression applied to m = 100 ≤ m ≤ m max = 120 renders computed ᾱε (λ) ≈ α ε (λ) = min{3, 1 + 2ε} (ε ≥ 0), which are listed in Table 2. Visibly, the sharpness or nearly sharpness of Th. 4 and Th. 5 is confirmed in Table 2. The last example involving curve in IR 2 refers to another spiral.

λ ε = 0.0 ε = 0.1 ε = 0.33 ε = 0.5 ε = 0.7 ε = 0.9 ε = 1.0 αε(λ)
Example 5. Let a planar regular convex spiral γ sp : [0, 5π] → IR 2 : γ sp (t) = ((6π -t) cos(t), (6π -t) sin(t)) be sampled according to (13) (rescaled by factor 5π) with t 0 = 0 and t m = 5π. Figure 5 illustrates γ sp (a dashed line) and γ2 (a continuous line) coupled with [START_REF] Lee | Choosing nodes in parametric curve interpolation[END_REF], for ε = 0.33, m = 22 and λ ∈ {0, 1}. The difference between γ sp and γ2 on reduced data Q 22 is transparent (at least for λ = 0). As explained previously, the sampling (13) enforces ψ i to be a re- parameterization for ε > 0. For ε = 0 one needs to resort to the sufficient conditions for ψ

> 0 to hold (see [START_REF] Kozera | Exponential parameterization and ε-uniformly sampled reduced data[END_REF]). In order to estimate the relevant coefficients α ε (λ) a linear regression is again applied to 100 = m min ≤ m ≤ m max = 120. The numerical results are listed in Table 3. Some computed α ε (λ) from Table 3 exceed convergence orders claimed by Th. 5. However, the first column in Table 3 shows the sharpness of Th. 4.

λ ε = 0.0 ε = 0.1 ε = 0.33 ε = 0.5 ε = 0.7 ε = 0.9 ε = 1.0 αε(λ)

Fitting Reduced Data for Spatial Curves

The next example deals with the reduced data Q m obtained by sampling the regular spatial curve in IR 3 . Example 6. We verify now the sharpness of Th. 4 and Th. 5 for a quadratic elliptical helix: γ h (t) = (2 cos(t), sin(t), t 2 ), with t ∈ [0, 2π] and sampled ε-uniformly (4) (here φ = id) according to:

t i =            2πi m if i even, 2πi m + 2π 2m 1+ε if i = 4k + 1, 2πi m -2π 2m 1+ε if i = 4k + 3. ( 14
)
The last knot t m is set to 2π. Figure 6 illustrates the curve γ h sampled in accordance with [START_REF]Wolfram Mathematica[END_REF] for ε = 0.5 and m = 22. For ε > 0, by Th. 5 each quadratic

ψ i : [t i , t i+2 ] → [ ti , ti+2
] is a re-parameterization. Note that ε = 0 in ( 14) yields also more-or-less uniform sampling (3) with K 1 = π and K 2 = 3π. The latter is stipulated by Th. 4. The sufficient conditions for {t i } m i=0 to yield ψ i as re-parameterization are specified in [START_REF] Kozera | Exponential parameterization and ε-uniformly sampled reduced data[END_REF]. The linear regression is used here for m min = 100 ≤ m ≤ m max = 120. The corresponding computed estimates ᾱε (λ) ≈ α ε (λ) = min{3, 1 + 2ε} are shown in Table 4. The experiments are consistent with the asymptotics from Th. 5. Thus the sharpness of ( 11) is also generically herein confirmed. Note also that the estimated convergence orders ᾱε=0 (λ) are substantially faster than those claimed by Th. 4.

The linear regression is used to estimate the asymptotic convergence rates α ε (λ) for sufficiently large m. The estimates may sometimes be misleading when m is not sufficiently large.

λ ε = 0.0 ε = 0.1 ε = 0.33 ε = 0.5 ε = 0.7 ε = 0.9 ε = 1.0 αε(λ) 1

Conclusions

In this paper we discussed the problem of trajectory estimation via piecewise--quadratic interpolation based on reduced data Q m . In particular, the exponential parameterization (6) which depends on parameter λ ∈ [0, 1] is herein examined. The latter is commonly used in computer graphics for curve modeling -see e.g. [START_REF] De Boor | A Practical Guide to Splines[END_REF], [START_REF] Kocić | Blending parameterization of polynomial and spline interpolants[END_REF], [START_REF] Kvasov | Methods of Shape-Preserving Spline Approximation[END_REF] or [START_REF] Piegl | The NURBS Book[END_REF]. Special cases of ( 6) with λ = 0 (see e.g. [START_REF] Noakes | Length estimation for curves with ε-uniform samplings[END_REF]) or λ = 1 (see e.g. [START_REF] Noakes | Cumulative chords piecewise-quadratics and piecewisecubics[END_REF] or [START_REF] Kozera | Curve modeling via interpolation based on multidimensional reduced data[END_REF]) have been studied in the literature. Recent results from [START_REF] Kozera | Piecewise-quadratics and exponential parameterization for reduced data[END_REF] and [START_REF] Kozera | Exponential parameterization and ε-uniformly sampled reduced data[END_REF] with full mathematical proofs analyze the asymptotics in question for the remaining cases of λ ∈ (0, 1).

Th. 4 claims that the if {t i } m i=0 is more-or-less uniform (2) there is no acceleration in trajectory estimation once λ varies within the interval [0, 1). The convergence orders are constant, i.e. α(λ) = 1 for all λ ∈ [0, 1). In addition, there is a discontinuity at λ = 1 with a jump to α(1) = 3 (valid for the general class of admissible samplings (1)).

It is known [START_REF] Noakes | Length estimation for curves with ε-uniform samplings[END_REF] that further acceleration can be achieved for ε-uniform samplings (4) (for ε > 0) and λ = 0 by reaching α ε (0) = min{3, 1 + 2ε}. The most recent result by [START_REF] Kozera | Exponential parameterization and ε-uniformly sampled reduced data[END_REF] extends the latter to arbitrary λ ∈ [0, 1) and ε ≥ 0. The case ε = 0 is also admitted provided the curve γ is sampled according to [START_REF] Noakes | Length estimation for curves with ε-uniform samplings[END_REF]. As established in Th. 5 the acceleration amounting to α ε (λ) = min{3, 1 + 2ε} is merely dependent on ε (not on λ ∈ [0, 1]). Visibly the discontinuity in α ε (λ) at λ = 1 is removed for ε ≥ 1. It should also be emphasized that the proof of Th. 5 shows that the Lagrange quadratic ψ i : [t i , t i+2 ] → [ ti , ti+2 ] satisfying ψ i (t i+j ) = ti+j (for j = 0, 1) forms a genuine re-parameterization in case of ε-uniform samplings (with ε > 0). The above theorem also formulates sufficient conditions for admissible samplings (1) (including the case ε = 0) guaranteeing ψ i to render a re-parameterization.

We experimentally verify here the sharpness of the asymptotics established in [START_REF] Kozera | Piecewise-quadratics and exponential parameterization for reduced data[END_REF] and [START_REF] Kozera | Exponential parameterization and ε-uniformly sampled reduced data[END_REF]. Various numerical tests conducted in this paper confirm, at least for the examined curves in IR 2 or IR 3 and samplings [START_REF] Piegl | The NURBS Book[END_REF], [START_REF] Lee | Choosing nodes in parametric curve interpolation[END_REF] or [START_REF]Wolfram Mathematica[END_REF] the sharpness of asymptotics claimed by both Th. 4 (see [START_REF] De Boor | A Practical Guide to Splines[END_REF] and ( 10)) and Th. 5 (see [START_REF] Kvasov | Methods of Shape-Preserving Spline Approximation[END_REF]). Though all discussed herein results refer to the dense reduced data Q m , high convergence orders yield in practice satisfactory approximation on sparse data. Thus as α(λ) = 3 for either λ = 1 or ε ≥ 1 and λ ∈ [0, 1], we should expect for sufficiently sparse Q m (but not too dense) a good performance in γ ≈ γ2 .

A possible extension of this work is to study other smooth interpolation schemes [START_REF] De Boor | A Practical Guide to Splines[END_REF] combined with reduced data Q m and exponential parameterization (6) -see [START_REF] Kvasov | Methods of Shape-Preserving Spline Approximation[END_REF]. Certain clues may be given in [START_REF] Floater | Chordal cubic spline interpolation is fourth order accurate[END_REF], where complete C 2 splines are dealt with for λ = 1, to obtain the fourth orders of convergence in length estimation. The analysis of C 1 interpolation for reduced data with cumulative chords (i.e. again with λ = 1) can additionally be found in [START_REF] Kozera | Curve modeling via interpolation based on multidimensional reduced data[END_REF] or [START_REF] Kozera | C 1 interpolation with cumulative chord cubics[END_REF]. More discussion on applications (including real data examples -see [START_REF] Janik | Reduced data for curve modeling -applications in graphics, computer vision and physics[END_REF]) and theory of non-parametric interpolation can be found e.g. in [START_REF] Kozera | Curve modeling via interpolation based on multidimensional reduced data[END_REF], [START_REF] Kocić | Blending parameterization of polynomial and spline interpolants[END_REF], [START_REF] Kvasov | Methods of Shape-Preserving Spline Approximation[END_REF] or [START_REF] Piegl | The NURBS Book[END_REF].

Fig. 1 .

 1 Fig. 1. Interpolating three points Q2 = {(0, 0), (0, 0.05), (1, 0)} with γ2, for λ = 0, 1/3, 1/2, 5/6, 1 ∈ [0, 1]

Fig. 2 .

 2 Fig. 2. Isolating the kneecap with γ2, for a) λ = 0, b) λ = 0.5, c) λ = 1

Fig. 4 .

 4 Fig. 4. The plot of the spiral γsp1 sampled as in (13) (a dashed line) and interpolant γ2 (a continuous line), for m = 12 and ε = 0.7 with either a) λ = 0 or b) λ = 1

Fig. 5 .

 5 Fig. 5. The plot of the spiral γsp sampled as in (13) (a dashed line) and interpolant γ2 (a continuous line), for m = 22 and ε = 0.33 with either a) λ = 0 or b) λ = 1

Fig. 6 .

 6 Fig.[START_REF] Kozera | Curve modeling via interpolation based on multidimensional reduced data[END_REF]. The plot of the helix γ h sampled as in[START_REF]Wolfram Mathematica[END_REF], for m = 22 and ε = 0.5

Table 1 .

 1 Computed ᾱε(λ) ≈ αε(λ) = 1 + 2ε for γ l and sampling (12) interpolated by γ2 with some discrete values λ ∈ [0, 1) and ε ∈ (0, 1]

		20	1.66	2.00	2.40	2.80	3.00
	0.00	1.47	1.80	2.10	2.46	2.85	3.04
	0.10	1.45	1.80	2.10	2.46	2.85	3.04
	0.33	1.42	1.80	2.10	2.46	2.85	3.04
	0.50	1.39	1.80	2.10	2.46	2.85	3.04
	0.70	1.37	1.79	2.10	2.47	2.85	3.04
	0.90	1.36	1.79	2.10	2.47	2.85	3.04

Table 2 .

 2 Estimated ᾱε(λ) ≈ αε(λ) = 1 + 2ε for γsp1 and sampling (13) interpolated by γ2 with λ ∈ [0, 1] and ε ∈ [0, 1]

		1.000	1.200	1.660	2.000	2.400	2.800	3.000
	0.00	0.981	1.286	1.716	2.023	2.419	2.96	3.004
	0.10	0.983	1.282	1.718	2.029	2.435	2.97	3.005
	0.33	0.985	1.277	1.726	2.051	2.496	2.93	3.016
	0.50	0.988	1.276	1.740	2.081	2.584	3.01	3.017
	0.70	0.995	1.283	1.778	2.178	2.782	2.94	3.030
	0.90	1.036	1.354	2.051	2.271	3.005	2.89	3.031
	αε(1)	3.000	3.000	3.000	3.000	3.000	3.000	3.000
	1.00	3.057	2.990	2.996	3.007	3.016	2.88	3.031

Table 3 .

 3 Estimated ᾱε(λ) ≈ αε(λ) = 1 + 2ε for γsp and sampling (13) interpolated by γ2 with λ ∈ [0, 1] and ε ∈ [0, 1]

		1.000	1.200	1.660	2.000	2.400	2.800	3.000
	0.00	0.990	1.303	1.799	2.223	2.851	2.986	3.008
	0.10	0.990	1.299	1.812	2.342	2.911	2.986	3.007
	0.33	0.991	1.296	1.872	2.252	2.966	3.011	3.024
	0.50	0,995	1.303	1.989	2.711	2.995	3.020	3.022
	0.70	1.013	1.355	2.377	2.930	3.020	3.024	3.023
	0.90	1.291	2.092	2.986	2.043	3.033	3.033	3.024
	αε(1)	3.000	3.000	3.000	3.000	3.000	3.000	3.000
	1.00	3.000	2.866	2.901	2.938	2.976	2.995	3.000

Table 4 .

 4 Estimated ᾱε(λ) ≈ αε(λ) = 1 + 2ε for γ h and sampling (14) interpolated by γ2 with λ ∈ [0, 1] and ε ∈ [0, 1]

		.00	1.20	1.66	2.00	2.40	2.80	3.00
	0.10	2.99	1.26	1.74	2.09	2.54	2.97	3.01
	0.33	2.85	1.24	1.72	2.07	2.93	2.93	2.95
	0.50	3.24	1.23	1.70	2.06	3.01	3.01	3.04
	0.70	3.21	1.20	1.64	2.94	2.94	2.94	3.19
	0.90	3.21	1.15	2.89	2.89	2.89	2.89	3.22
	αε(1)	3.00	3.00	3.00	3.00	3.00	3.00	3.00
	1.00	3.21	2.89	2.91	2.92	2.93	2.88	3.21


Wladyslaw Homenda
email: homenda@mini.pw.edu.pl

Mariusz Rybnik
email: mariuszrybnik@gmail.com

Searching in the Structured Space of the Braille Music

Keywords: syntactic structuring, semantic mapping, data understanding, music representation

This paper presents a method for searching the Braille music information based on the semantic description. The searching method is based on comparison of node's metadata that aggregates subtree's structure of information. Methods for the metadata generation is specific to searching orientation and grammar. We focus on methods for notes' durations allocation as well as key and time distribution that are required in searching and rhythm analysis. We propose a syntax analysis method based on semantic analysis using attribute grammar.

Introduction

Exploring knowledge encapsulated in the information space needs structuring and agile searching methods. In this paper we remind structuring issues connected with the music information space. Then we propose methods for semantic analysis during parsing process which use attribute grammars. The further part is devoted to a method for semantic searching which uses information incorporated in derivation tree.

Any intelligent processing of natural communication languages requires uncovering structures of raw data. There are different ways leading to structuring. Our interest is focused on employing syntactic and semantic structuring of music information with an emphasis on music notations. It is obvious that raw data without any structuring is of no use in intelligent communication. Otherwise the processing covers some characters from alphabet without any meaning. The aim is to create a generic method to integrate syntactic and semantic structuring of music information. This structuring allows for optimized processing of music information described in different languages including Braille music notation and printed music notation. In this study we bind Braille music notation to printed music notation.

Syntax

Syntactic structuring of music information is the first stage of the analysis process. We utilize context-free grammars for syntactic structuring of Braille music notation and printed music notation. We continue the discussion of syntactic structuring outlined in [START_REF] Homenda | Querying in Spaces of Music Information[END_REF][START_REF] Homenda | Knowledge-Driven Syntactic Structuring: the Case of Multidimensional Space of Music Information[END_REF][START_REF] Homenda | Performing Operations on Structured Information Space of Braille Music[END_REF][START_REF] Homenda | Notes on automatic music conversions[END_REF].

Let us recall that we use formal grammars, which are systems G = (V, T, P, S) where: V is a finite set of nonterminal symbols (nonterminals), T is a finite set of terminal symbols (terminals), P is a finite set of productions and S is the initial symbol of grammar, S ∈ V . In general productions can be seen as a finite binary relation

P ⊂ (V ∪ T ) + × (V ∪ T ) * . A grammar G is context-free one (CFG) ⇐⇒ (∀p)(p ∈ P ⇒ p ∈ V × (V ∪ T ) * ).
Attribute grammar is a context free grammar allowing to tie semantics to syntax during syntax analysis. Attribute grammar attaches so called attributes to each of the nonterminals of the grammar. Such elements are divided into two disjoint sets: synthesized and inherited attributes.

Below a subset of productions for Braille music is presented ( [START_REF] Krolick | How to Read Braille Music[END_REF]). Because of the clarity attributes definitions are omitted. The whole set is specified in [START_REF] Homenda | Performing Operations on Structured Information Space of Braille Music[END_REF]

→ <pitch> | <interval> | <pitch> <prolongation> <pitch> → C1 | C2 | C4 | C8 | D1 | D2 | D4 | D8 | E1 | E2 | E4 | E8 | → F 1 | F 2 | F 4 | F 8 | G1 | G2 | G4 | G8 | A1 | A2 | A4 | A8 | → H1 | H2 | H4 | H8 | rest1 | rest2 | rest4 | rest8
Since there is no evidence that Braille music notation is a context-free language, we do not attempt to construct a context-free grammar generating the language of Braille music notation. Instead we use context-free grammars covering the language of Braille music notation. Such grammars will generate all constructions of Braille music notation and some others, which are not valid Braille music constructions. This approach cannot be used to generate Braille music scores or parts neither to check their correctness. However, since we employ context-free grammars for processing scores, which are assumed to be correct, this approach is proven. A discussion on construction of context-free grammars covering printed and Braille music notations is outlined in [START_REF] Homenda | Notes on automatic music conversions[END_REF].

The notion of lexicon is a fundamental concept of syntax analysis. The concept of lexicon for music notation was introduced in [START_REF] Homenda | Querying in Spaces of Music Information[END_REF] and then was developed in [START_REF] Homenda | Performing Operations on Structured Information Space of Braille Music[END_REF][START_REF] Homenda | Notes on automatic music conversions[END_REF]. Lexicon is the space of language constructions, each of them supplemented with possible derivation trees, also known as parsing trees. Lexicon includes relations between items of this space. Such a tree satisfies the following rules: a) it is a subtree of the derivation tree of the whole score, b) it is the minimal tree generating the given language construction, c) the minimal tree can be extended by a part of the path from the root of this tree toward the root of the score derivation tree. Due to the last condition, usually there are many trees for a given language construction.

Semantics

Languages allow to describe a real world of things, sensations, thoughts, ideas etc. Braille music notation describes the space of hearing sensations, which can be outlined as the space B × D × P of triples (b, d, p). Each triple defines the performed sound, where b is the beginning time, d is the duration and p is the pitch of the sound. In general, objects of the real world may be outlined with much richer set of features, but this simple triple is sufficient for our discussion, c.f. [START_REF] Homenda | Notes on automatic music conversions[END_REF].

Above-mentioned approach is very generic, it refers to physical essence of a sound and has not any links to a particular type of music description. This structure can be used for any music notation, especially for Braille music notation. The definition of the hearing sensation space is also very useful in case of other structural operations, e.g. conversion between different types of music description, c.f. [START_REF] Homenda | Notes on automatic music conversions[END_REF].

The purpose of using the world of real objects is to tie meaning to syntactic structures of music descriptions. The idea of collaborating syntactic and semantic has found the practical application to processing of music information. It has been involved in a real processing of Braille music accomplished in the Braille Score project, c.f. [START_REF] Grant No N R | Breaking accessibility barriers in information society. Braille Score -a computer music processing for blind people[END_REF].

As mentioned in the previous section, descriptions of music notation expressed in different languages and representation of music notation in different formats are cast on the world of hearing sensations. Such casts are called semantics of descriptions and representations of music information. Formally, let B is the lexicon of Braille music notation and H is the space of hearing sensation. Semantics S is a relation:

S ⊂ B × H
The space of language constructions is immersed in the space of sounds. The immersion gives values of real world to language constructions. The immersion defines meaning of language constructions, defines semantics.

Music data parsing

Parsing, also known as syntactic analysis, is aimed at structuring raw music data. The result of this process is parsing (derivation) tree compatible with specified grammar. Moreover, the attribute grammar produces semantic data attached to the tree's nodes.

Key and Time Signature Passage

All of the nonterminals in Braille music grammar are equipped with attributes connected with key and time signature. The knowledge of the key and time (as synthesized attributes) is discovered in productions and passed to the top of the tree, to the initial nonterminal:

<f if ths>→ | | | | | | | | | etc. <f if ths> .f if th = id
<time sig>→ num ind <beat> <beat type> <time sig> .beat = (<beat> .beatH, <beat type> .beatL) <beat>→ higher 1 | higher 2 | etc. <beat> .beatH = id <beat type>→ lower 1 | lower 2 | etc. <beat type> .beatL = id Key and time signature attributes are passed from the root of the tree to the other structures of the notation as inherited attributes. Each of the productions has a rule similar to this:

<part 1 >→<staf f> new line <part 2 > | <staf f> new line <staf f> .beat =<part 1 > .beat <part 2 > .beat =<part 1 > .beat
This method allows to distribute key and time signature info in structured space of music. Key and time knowledge flows from key/time signature branch to the root of the tree and then it is propagated to the lower parts of the tree.

Notes' Duration Identification and Passage

In case of Braille music notation, because of limited number of available characters, notes of the duration x and x 16 share the same symbol, e.g. whole note C and sixteenth note C are represented by the same Braille cell. This ambiguity demands contextual analysis to investigate the correct duration of the note.

This issue is a nondeterministic problem and it involves voices, because voices are fully filled in time dimension.

Simulation tree method One of the practical solutions of this nondeterministic issue is simulation tree. We assume, that the sound of each note lasts from the beginning of the note to its end, i.e. no articulation, ornamentation or dynamic has influence on the duration of the sound. This tree is defined as follows (lets be N = (n 0 , n 1 , ..., n k ) -notes in voice and S = (s 0 , s 1 , ..., s k+1 ) -time slots between neighboring notes, i.e. s 0 is the time when first note starts, s 1 -the time when first note ends and the second starts, etc.:

-nodes of the tree are labeled with elements from S -root of the tree is labeled with s 0 The draft of simulation tree is given in the Fig. 1. Such definition describes all possible time allocations. Each of the leaf of the simulation tree represents unique time allocation in the voice, because leaf in the tree is labeled by s k+1 -the space after last note in the voice. Incorrect time fillings are easily detectable. Braille music definition demands unambiguous situations in case of notes duration, i.e. there is only one path from the root to the leaf in the simulation tree is filled in correct way. Fig. 1 presents simulation tree for 3 notes. Let assume that notes may represent the same durations, e.g. C, D, and E whole/sixteenth notes (whole/sixteenth are described by the same Braille cell), and time signature has a proper value. This is a case that fits the scheme ,,one left and two rights", which leads to three concretizations: leftright-right, right-left-right and right-right-left (marked in the Fig. 1 as bold solid and dotted lines). Each of above mentioned filling schemes fills voice in correct manner but only one of them is desired and it is left-right-right (marked as bold, solid line), because in other case there should appear special character after s 1 (in the right part of the tree, where starts two dotted, bold lines; Braille specific). That character is to mark explicitly the duration of the note. Appearance of such Braille signs excludes some durations of the note and causes the tree to loose some paths. All paths are present in the tree in the Fig. 1, so there is no duration mark in the notation.

Attribute flow method

We propose method that bases on attribute grammar. Attribute grammars for music notation was introduced in [START_REF] Homenda | Knowledge-Driven Syntactic Structuring: the Case of Multidimensional Space of Music Information[END_REF]. In this paper we use concepts form this paper to resolve the problem of time/duration ambiguity of Braille music notation. In fact this method creates implicit simulation tree during syntax analysis.

Attribute flow method requires two stages (two attributes flows) during processing. Also we assume that all nonterminals located below ,,voice" element in First stage During first stage the attribute iDur1 is passed down to the leaf, change in sDur1 is attempt according to semantic rule, is passed toward the root to the ,,time element" nonterminal, it changes iDur1, then iDur1 is passed down to the leaf, ... This procedure lasts till the end of the notes in current voice. The example of attribute flow is presented in the Fig. 2 It allows to collect all possible variants of voice's time allocation. After that phase, when sDur1 is synthesized in ,,voice" nonterminal, the correct variant is chosen. According to remark in 2.2 paragraph, thanks to Braille music definition, there exists one unique time allocation. This one particular solution is assign to iDur2 attribute of ,,voice" nonterminal.

<note gf o>→<high 1 > | <interval> | <high 2 > <prolongation> <high 1 > .iDur1 =<note gf o> .iDur1 <note gf o> .sDur1 =<high 1 > .sDur1 <high 2 > .iDur1 =<note gf o> .iDur1 <prolongation> .iDur1 =<high 2 > .sDur1 <note gf o> .sDur1 =<prolongation> .sDur1 <high>→ N x , where N x = (N, x) ∈ {C, D, E, F, G, A, H, rest} × {1, 2, 4, 8} <high> .sDur1 = (<high> .iDur1 ∪ {x}, <high> .iDur1 ∪ {16x}) <prolongation 1 >→ * <prolongation 2 > <prolongation 2 > .iDur1 =<prolongation 1 > .iDur1 ∪ { 1 2 } <prolongation 1 > .sDur1 =<prolongation 2 > .sDur1 <prolongation>→ * <prolongation> .sDur1 =<prolongation> .iDur1 ∪ { 1 2 } <measure f m>→<voice> voice div <measure f m> | <voice> <voice> .iDur1 = () <voice> .iDur2 =chooseCorrectTimeAllocation(<voice> .sDur1, <voice> <time element 1 >→<note 1 > <time element 2 > | <note 2 > <note 2 > .iDur1 =<time element 1 > .iDur1 <time element 1 > .sDur1 =<note 2 > .sDur1 <time element 2 > .iDur1 =<time element 1 > .iDur1 <voice 1 >→<time element 1 > <voice 2 > | <time element 2 > <time element 1 > .iDur1 =<voice 1 > .iDur1 <voice 2 > .iDur1 =<time element 1 > .sDur1 <voice 1 > .sDur1 =<voice 2 > .sDur1 <time element 2 > .iDur1 =<voice 1 > .iDur1 <voice 1 > .sDur1 =<time element 2 > .sDur1
Second stage After the last note, the correct time allocation is chosen and is propagated in the tree. It uses iDur2 and sDur2 attributes in the same way the iDur1 and sDur1 were used in the first stage. In this phase each note cuts one proper time duration and assigns to itself. After the second stage, the notes have allocated correct durations.

General remarks Both methods are practical solutions of the nondeterministic problem of the note's time allocation. Simulation tree and attribute flow method are equivalent. In fact, the attribute flow method is implicit simulation tree method. It creates simulation tree during the process of generation of the all possible time allocations. Simulation tree is ,,orthogonal" to derivation tree, as it is shown in the Fig. 3.

There is a possibility to optimize proposed method of attribute flow by saving memory space. Optimization requires change in semantic rule for <high> production. The method will collect only one sign for each note during the first attribute flow (instead of duplicating the previous formulas): D,E,F,G,A,H The mentioned methods are applicable even if there is a need to check 2 |N | possible time allocations because of the fact that one voice does not contain huge numbers of notes. The average number of the notes in the one voice is about 10. This paragraph contains a description of selection searching operations.

<high>→ N x , where N x = (N, x) ∈ {C,
We discuss here a different types of grammars and their influence on selection performed in the structured space of music. Selection is a prelude to searching operation.

In this case we focused on rhythmic analysis preceded by notes' durations allocation. In previous paragraph we showed method for duration allocation as well as key and time signature distribution, which are crucial for rhythmic analysis in Braille music notation. Other types of searching information are easy to perform in similar way -as attributes flow during syntax analysis or in the space of sounds.

Different types of Grammars and Selection Operation

Music information is a data that can be presented in many different formats, e.g. printed music, Braille music, MIDI, etc. Each type is described by specified grammar, in this case they are approximated by context-free grammars. Moreover, in frames of one format there exist many grammars. Each of these grammars defines the same language (data format), but exposes different property of the language. The examples of such grammars are given in [START_REF] Homenda | Knowledge-Driven Syntactic Structuring: the Case of Multidimensional Space of Music Information[END_REF], where authors introduced two grammars for printed music: ,,time-prior-to-pitch" and ,,pitch-prior-to-time". [START_REF] Homenda | Knowledge-Driven Syntactic Structuring: the Case of Multidimensional Space of Music Information[END_REF] illustrates selection performed in the structured space of printed music notation.

Selection made in the notation space leads to selecting some nodes in the derivation tree. The structure of selected nodes in the tree differs depending on the grammar type. Some grammars make nodes to be consistent, i.e. there is some node that is an ancestor for all selected nodes and that node does not have unselected children as descendant. In other words, there exists one node, that derived all and only selected notation.

Some language has natural orientation, e.g. Braille music is voice oriented, i.e. selection of the notes in one voice is going to generate consistent selection in derivation tree. Other orientations for Braille music are also possible. In case of the printed music, in the paper [START_REF] Homenda | Knowledge-Driven Syntactic Structuring: the Case of Multidimensional Space of Music Information[END_REF] were given grammars: pitch and time oriented.

Semantic Searching

Semantic search allows to search for all occurrences of notation described in semantic way, e.g. all fifth accords. Syntax searching, where algorithm looks for the exact occurrence of the searching text, is a special case of semantic search.

During searching operation the lexicon is used. Let us assume that grammar type and selection operation generate consistent selection of nodes in the derivation tree. For each lexicon's element notation is described as data put in the root of the subtree. That description should be connected with the type of grammar and searching operation. Method for accord description, in case of interval analysis, were given by Allan Forte in [START_REF] Forte | The Structure of Atonal Music[END_REF]. Descriptions are applicable during syntax analysis thanks to attribute flow.

To search specified notation described by some semantic, all that should be done is searching nodes in the whole derivation tree. Lexicon contains many elements for one piece of notation. The difference between these elements is in subtrees -each subtree has different height. The bigger height, the more precise description it represents. Searching for a note which description is aggregated in nonterminal ,,<note>" means that any of such notes in the whole measure meets the condition. If searching for a note involves nonterminal ,,<measure>" it means that all occurrences of specified note in that particular time slot in all measures of the score are desired. Finally, nonterminal ,,<S>" defines exactly one occurrence of the searching note.

Semantic search requires semantic which is delivered during syntax analysis as floating attributes or as the world of hearing sensation (thanks to semantic mappings).

Semantic Searching Example

Fig. 4 presents an example of semantic searching in the structured space of Braille music. The task is to find all occurrences of the accords that have the same intervals and duration. Please note that Braille music allows to denote accords in more than one manner (c.f. [START_REF] Krolick | How to Read Braille Music[END_REF]), so our task is not an usual (syntax) search. Grammar presented in [START_REF] Homenda | Performing Operations on Structured Information Space of Braille Music[END_REF] allows for such operation. We tie with all ,,< time element >" nonterminals a vector that specifies desired information about derived structures. That activity can be done after allocation of notes' duration and key/time signatures passage in the derivation tree. The vector is labeled as [d; x 1 -x 2 -... -x n ] where d is the note (accord) duration, n + 1 is the number of noteheads in the accord, x k is the interval between (k -1)-th and k-th noteheads. Let us assume that we want to find all eighths accords built from intervals 4 and 3, so the vector is [8; 4 -3]. To fulfill this task all that should be done is vector (,,<time element>" nonterminal metadata) comparison. No syntax of the score is touched. The method points two occurrences, marked in the Fig. 4 with bold ellipses. The result of the operation is a piece of notation that is derived from the pointed nonterminals marked with bold ellipses.

Conclusions

This paper presents approach for searching in the structured information space of Braille music. Searching is understood as localization of specified node in the derivation tree, which corresponds to node of the subtree paired with the searched notation in the lexicon space. Our approach is rhythmic oriented, i.e. we investigate mutual time dependencies between notes. We needed to allocate duration for the notes to cope with that.

The direct expansion can be aimed at providing another methods for aggregating data at the subtree's root. The important issue is to connect with intelli-gent human-computer interface developing because conditions imposement is a bottleneck for the searching in the structured space of music data.

Fig. 1 .

 1 Fig. 1. Simulation tree draft for calculating duration

Fig. 2 .

 2 Fig. 2. Attribute flow during the first stage for production <voice>→<time element> <voice>

  , rest} × {1, 2, 4, 8} <high> .sDur1 =<high> .iDur1 ∪ {x} After applying the changes above the simulation tree is created in function ,,choose" and still allows to investigate the one, possible solution. It allows however to save memory during attribute flow, as original variant has space complexity O(|N | • 2 |N | ) and optimized method has space complexity O(|N |), where |N | is the number of notes in voice.

Fig. 3 .

 3 Fig. 3. Simulation and derivation tree in the attribute flow method

Fig. 4 .

 4 Fig. 4. Semantic Searching Example

Acknowledgment

The research is supported by the National Science Center, grant No 2011/01/B/ST6/06478, decision no DEC-2011/01/B/ST6/06478.


Michal Holis
email: michal.holis@vsb.cz

Lenka Skanderova
email: lenka.skanderova@vsb.cz

Martin Placek
email: martin.placek@vsb.cz

Jiri Dvorsky
email: jiri.dvorsky@vsb.cz

Ivan Zelinka
email: ivan.zelinka@vsb.cz

Solving Steel Alloying Using Differential Evolution and SOMA

Keywords: steel alloying, evolutionary algorithms, Differential evolution, SOMA

This paper proposes method for solving steel alloying problem using evolution algorithms SOMA and differential evolution. Both algorithms belong to the family of the evolution algorithms but the main ideas of these algorithms are different. In differential evolution new offspring is created during the evolution, the individuals are crossed and mutated, while in SOMA the individuals move in the space of the possible solutions and the mutation is replaced by perturbation. The main goal of this paper is to discover how much these algorithms are usable and suitable to solve the problem of steel alloying.

Introduction

Steel Alloying

It takes many steps to manufacture steel and every factory's step configuration may vary from the others. Commonly the process follows path similar to this: iron ore is smelted in iron smelters and distributed as a hot metal with temperature about 1400 • C to converter or electric arc furnace to improve its quality for following treatments. Hot metal is mixed with scrap and slag formers, the heat is heated up approximately to 1650 • C and first ferro-alloys are charged into the heat during tapping. This point is the first appliance of alloying process described below. Ladle with the heat is going to secondary metallurgy process, typically ladle furnace or vacuum treatment. This treatment part is exceptionally skipped, otherwise the steel quality is improved with accurate amount of alloys to achieve requested steel composition defined by steel grade and the temperature is modified for the last step. The final step of this process is casting on continuous casting machines to obtain final steel product like slabs, blooms or billets. More on this process can be found for example in book by Ahindra Ghosh and Amit Chatterjee [START_REF] Ghosh | Ironmaking and steelmaking: theory and practice[END_REF].

Target of the whole process is primarily to manufacture steel of requested quality (this is commonly referred to as target or final steel grade), secondly to reduce cost of the materials and energy used in the process.

To manufacture steel of certain grade, with specific chemical, electrical and mechanical properties, it is crucial to be sure that the steel is composed of correct elements in correct ratio's. Composition of the steel is modified in each step throughout the whole process with technique known as alloying.

Alloying is process of continually charging the steel with certain amount's of alloying materials (compounds of chemical elements) to gradually obtain the requested steel quality. Each of the materials has certain given ratio of all elements it is composed of. Also price of the material is known. Question is how to optimally choose amount of charged materials in each step when there are many charging materials composed of many chemical elements, with one element being commonly present in many materials. We also have to consider price of the final solution, since some materials are very cheap and some can be very expensive.

To solve the problem we are always presented with these input data:

weight of the input steel, input steel's composition vector (vector of ratios representing each element's presence in steel), list of alloying materials, their chemical solution and their unit prices, target steel grade represented with three vectors -one being optimal ratio of all chemical elements in final steel, second represents minimal ratio of any given element in final steel and last one represents maximal ratio of any given element in final steel.

Commonly in practice this problem is solved with Dantzig's simplex algorithm, which is a linear programming solution that with given input parameters finds cheapest solution in given final steel's grade range. This however does not allow us to fine-tune optimal balance between precision of final solution and it's price. This can be solved by iteratively running the algorithm with different steel grade ranges and trying to found solution that we consider to be optimal both in precision and cost. However since the ranges are vectors there are so many combinations of minimal and maximal values that it is very inefficient and unpractical to proceed in this way. More on this matter can be found in book by Dantzig, George B. [START_REF] Dantzig | Linear programming[END_REF].

In this paper, we present how to overcome problems of the common solution with usage of evolution algorithms and fitness function suitable for solution of this problem is presented.

Evolution algorithms

The evolution algorithms have been successfully used to solve many practical and theoretical problems, see [START_REF] Alguliev | DESAMC+DocSum: Differential evolution with self-adaptive mutation and crossover parameters for multidocument summarization[END_REF][START_REF] Chakaravarthy | Performance evaluation of proposed Differential Evolution and Particle Swarm Optimization algorithms for scheduling m-machine flow shops with lot streaming[END_REF][START_REF] Subramanian | PRISM: PRIority based SiMulated annealing for a closed loop supply chain network design problem[END_REF]. In [START_REF] Koloseni | Differential Evolution Classifier with Optimized Distance Measures for the Features in the Data Sets[END_REF] the differential evolution is used as classifier for the features in the data set, in [START_REF] Coelho | Self-organizing migration algorithm applied to machining allocation of clutch assembly[END_REF] the algorithm SOMA is used to machining allocation of clutch assembly. Evolutionary techniques are applied in connection with, e.g. [START_REF] Senkerik | Evolutionary Techniques for Deterministic Chaos Control[END_REF][START_REF] Zelinka | An investigation on evolutionary reconstruction of continuous chaotic systems[END_REF][START_REF] Senkerik | Performance comparison of differential evolution and SOMA on chaos control optimization problems[END_REF], too. These algorithms are still improved, see [START_REF] Sun | A hybrid co-evolutionary cultural algorithm based on particle swarm optimization for solving global optimization problems[END_REF][START_REF] Zhou | A differential evolution algorithm with intersect mutation operator[END_REF]. They are based on two essential principles -crossing and mutation. These principles proceed from Darwin's evolution theory and Mendel's principle of crossing. They work with the population of individuals, which are developing (improving) during the evolution. Better individuals survive while worse ones die. In this paper differential evolution and SOMA have been chosen. Differential evolution Differential evolution (DE) is a population -based stochastic algorithm for global optimization. It was introduced by Ken Price and Rainer Storn and in this paper the original version is used for experiment design [START_REF] Chakraborty | Advances in Differential Evolution[END_REF]. Although this algorithm is very simple and efficient, in [START_REF] Chengfo | Improved differential evolution algorithms[END_REF] authors proved that it can not ensure the global convergence and they proposed two hybrids algorithms named QAISDE and GDISE to improve DE.

At the beginning of the algorithm the first population is generated. Each individual in population has its own set of parameters. The number of parameters is called dimension, we denote it D. In addition each individual has its fitness value. This value is very important because it says how good is this individual in current population. Fitness is the value of the cost function. Each parameter of the individual has low bound and high bound. It is not able to cross over these bounds [START_REF] Price | Differential Evolution A Practical Approach to Global Optimization[END_REF].In this article DE/best/1/exp has been chosen.

When the first population is generated, for each individual in population following steps are done:

1. Three other neighbors are chosen randomly (these individuals may not be the same). 2. The noise vector is created, see Eq. ( 1). 3. New individual is created. The random number from the interval [0, 1] is generated. If the number is smaller than crossing threshold CR, the parameter from the noise vector is chosen as a parameter of the new individual.

Otherwise the parameter from the actual parent is taken. 4. If the new individual has better fitness than its parent, it will replace the parent, otherwise the new individual is forgotten and the parent stays in the population.

The noise vector equation of DE/best/1/exp:

v j = x G r3,j + F x G r1,j -x G r2,j . (1)
where v j is the noise vector, x G r3,j , x G r1,j and x G r2,j are three randomly chosen individuals and F denotes the mutation constant.

Self organizing migration algorithm (SOMA) Unlike differential evolution, SOMA works on the principle of one population, which is changing in time. Application of this algorithm can be found for example in [START_REF] Zelinka | Investigation on Evolutionary Control and Optimization of Chemical Reactor, Soft computing models in industrial and environmental applications[END_REF][START_REF] Pavlech | Self-organizing Migration Algorithm on GPU with CUDA, Soft computing models in industrial and environmental applications[END_REF]. The beginning is the same like in DE. The first population is generated. But in SOMA no offspring is created. The principle of SOMA is the individuals are moving in the space of possible solutions and in the each generation (we say migration) they have a new positions. In [START_REF] Kadlec | A Novel Multi-Objective Self-Organizing Migrating Algorithm[END_REF] the novel multiobjective SOMA has been introduced.In this paper the strategy All to one has been chosen. At the begin the new population is generated. As well as in DE, each individual has its parameters and fitness, low and high bound. When we have the population the best individual is chosen (individual with the best fitness) -we call it leader. The following steps are done next for each individual in population:

1. The perturbation vector α is generated according to the parameter P RT , which is usually set to 0.11. The α is composed of 0 and 1 and it is important for the direction of the individual moving. (Individual can move to the leader in many directions.) 2. Individual will move to the leader. It moves by steps. For each step the next position and the new fitness is computed. Moving is finished when the parameter Step spreads the value of the parameter P athLength.

After migration of the individual its best position, which has been reached

during the migration, is chosen. 4. If the best reached position of the individual is better than the original one, the original one is replaced by the new position.

The crossing is replaced by philosophy that each individual moves in the space and each individual remembers the coordinates of the position, where the resolution has been the best in scope of its way to the leader. Moving of the individual is directed by the equation below [START_REF] Onwubolu | New Optimization Techniques in Engineering[END_REF].

x M L+1 i,j = x M L i,j,start + x M L L,j -x M L i,j,start tα j (2)
where

x M L+1 i,j
is a new position of the individual, x M L i,j,start denotes the individual's start position, x M L i,j,start is the actual leader's position, Step is marked as t and α denotes the value in j th position of α.

Experiment design

Our method is based on SOMA and DE using in steel alloying process. There were two main problems in experiment design -how to represent an individual in evolutionary algorithms and how to define its fitness function. From the view of steel alloying process, there were 14 compounds, which are added to the original steel composition. These compouds are consist of the elements. In result we needed the elements amount. In evolution algorithms the individuals consist of parameters. In this paper the parameters of individuals are represented by the compounds, which were added to the original steel composition. There were 14 compounds, so the individual's dimension (number of parameters) D has been 14. Each compound has been represented by one parameter in individual. In the end of the evolution the amount of the elements have been recomputed from the amount of compounds.

Fitness function presented in this paper is designed in the following manner:

parameters of each member in population represent weight of each alloying material that is to be charged to the steel (every member has as many parameters as there are alloying materials),

first the function computes weight of each element in input steel using it's weight and it's composition vector, using the value of each parameter of current member and composition vector of material it represents we can compute the weight of each chemical element that would be added to the steel, if materials the member represents would be charged to the steel, using weights of elements in original steel and computed weights of elements in charged materials the final presence of each material in final steel is computed, value of the fitness function is then equal to absolute distance of the optimal solution vector and this solution's vector, if this vector is out of range represented by minimal and maximal vector of solution, then penalization is applied to the fitness value, additionally price of all used materials is computed and added to the fitness value, to do this constant defining importance of price of final solution over it's accuracy is applied, with this constant we can control and fine-tune the solution to our specific needs.

Fitness Function Equation

If Cmin j < Mi•M atij +Sj •W nm k=0
M k +W -C j < Cmax j then fitness function is defined as follows (this is the case when given member represents valid solution that is in required composition range).

nm i=0     ne j=0 M i • M at ij + S j • W nm k=0 M k + W -C j   + P i • M i • P W   (3)
Otherwise we apply additional penalization constant to equation to discard the member from solution.

   nm i=0     ne j=0 M i • M at ij + S j • W nm k=0 M k + W -C j   + P i • M i • P W      • T (4)
Notation used in these equation is summarized in Table 1.

For both evolution algorithms, DE and SOMA, the same dimension has been set, D = 14. In DE's experiments we were changing the parameters: the number of individuals in the population N P , the number of generations G, mutation constant F , and crossing threshold CR in order to find better evaluation of the cost function. In SOMA experiments these parameters were also modified: number of the migration cycles M igrations, the stopping position of the migrating individual P athLength, and the step size of the migrating individual Step. All tested combinations of input parameters are given in Table 2.

From chemical point of view fourteen, D = 14, chemical compounds have been used: FeMn (with high carbon level), FeMn (with medium carbon level), FeMn (with low carbon level), FeSiMn, FeCr (with high carbon level), FeCr (with low carbon level), FeNi, FeMo, FeW, FeNb, FeV, NV, FeTi and Cu. Composition of these compounds can be found in Table 4. For each element the minimum value, maximum value and optimal value in final steel alloy have been set, see Table 3.

Experimental Results

Our experimental results are summarized in Table 5. Highlighted rows represent runs that were unable to reach satisfying solution. First column of the table contains description of given settings along with it's parameters. Second column contains best achieved fitness value of all runs and next columns contain information about final computed solution of the steel. Progress of the best fitness values is show in Figures 1 and2. One hundred test runs using given setting were performed and each test run is displayed as one line in these charts. Only selection of plots of runs that were able to reach satisfying solution are presented in this paper.

From the results measured in our experiments we can see, that by using higher values then 0.5 for F in DE the evolution requires higher number of generations to successfully reach valid solution. With F = 0.5 we were able to reach satisfying solution even with only 50 members in whole population. Although some of the runs were unsuccessful and were unable to present valid solution, the runs that completed successfully yielded correct result reliably and we have not recorded single case when they would fail.

Conclusion

We have proposed alternative way to compute steel alloying recipe. Method using evolution algorithms has several advantages when compared to most commonly used Simplex method. It allows to incorporate final cost of used alloying materials into equation. Result of Simplex method is always cheapest solution in given range. Using our fitness function described in Section 2 we can control the importance of precise solution of final steel over it's price. All runs presented in our experiments that were able to achieve less then approximately 155 fitness value provide satisfactory results and are fully prepared to be used in real life environment on real life cases.

We would like to extend our work and try out more evolution algorithms to compare their results. Mainly we would like to design larger experiment to compare performance and precision of larger set of evolution algorithms on this problem. 153.164 0.040 0.083 0.972 0.001 0.001 1.271 0.941 0.000 0.000 0.000 0.001 0.010 0.001 0.000 0.000 96.680 DE (50, 1,500, 0.5, 0.6) 153.021 0.040 0.085 0.972 0.001 0.001 1.269 0.941 0.000 0.002 0.000 0.001 0.009 0.000 0.000 0.000 96.679 DE (50, 1,500, 0.5, 0.7) 152.896 0.040 0.085 0.970 0.001 0.001 1.270 0.940 0.000 0.000 0.000 0.001 0.010 0.000 0.000 0.000 96.681 DE (50, 2,000, 0.5, 0.5) 152.956 0.040 0.085 0.971 0.001 0.001 1.268 0.942 0.000 0.001 0.000 0.001 0.009 0.001 0.000 0.000 96.681 DE (50, 2,000, 0.5, 0.6) 152.858 0.040 0.085 0.971 0.001 0.001 1.270 0.943 0.000 0.000 0.000 0.000 0.009 0.000 0.000 0.000 96.681 DE (50, 2,000, 0.5, 0.7) 152.666 0.040 0.085 0.971 0.001 0.001 1.269 0.940 0.000 0.001 0.000 0.000 0.011 0.000 0.000 0.000 96.681 SOMA (1,000, 200, 0.1, 0.1) 152.582 0.040 0.085 0.972 0.001 0.001 1.268 0.940 0.000 0.000 0.000 0.000 0.012 0.000 0.000 0.000 96.681 SOMA (1,000, 200, 0.1, 0.11) 152.717 0.040 0.085 0.972 0.001 0.001 1.268 0.942 0.000 0.000 0.000 0.000 0.011 0.000 0.000 0.000 96.680 SOMA (1,000, 200, 0.1, 0.3) 152.935 0.040 0.085 0.971 0.001 0.001 1.268 0.940 0.000 0.004 0.000 0.000 0.008 0.000 0.000 0.000 96.681

Desired composition vectors

Fig. 1 .

 1 Fig. 1. Differential Evolution (N P : 50, G: 1500, F : 0.5, CR: 0.7)

  0.085 0.972 0.006 0.002 1.308 0.980 0.010 0.005 0.002 0.002 0.013 0.005 0.005 0.005 96.681

Fig. 2 .

 2 Fig. 2. SOMA (N P : 1000, M igrations: 200, P RT : 0.1, Step: 0.3)

Table 1 .

 1 The variables description from the Eqs. (3) and[START_REF] Koloseni | Differential Evolution Classifier with Optimized Distance Measures for the Features in the Data Sets[END_REF]

	Variable	Description
	nm	Total number of available alloying materials (compounds) used.
	nE	Total number of chemical elements that materials consists of.
	M	Individual being tested for it's fitness value. Bottom index specifies index
		of parameter whose value we want to obtain. Each parameter of member
		represents weight in kilograms (kg) of one material that would be charged
		to steel. Number of parameters of one member equals to number of all
		available alloying materials.
	Cmin	Desired minimal composition vector. Index denotes element whose repre-
		sentation in steel we want to obtain. Resulting number is again in range
		[0, 1].
	Cmax	Desired maximal composition vector. Index denotes element whose repre-
		sentation in steel we want to obtain. Resulting number is again in range
		[0, 1].
	P	Unit price of material for each kg.
	P W	Constant defining importance of final solution's cost over it's precision.

M at Material composition. First index specifies material, which's composition we are interested in. Second denotes index of element. Result is number in range [0, 1] (1 means 100% of material is composed with that element, 0 that element is not contained in compound) that represents element's representation in given material (compound). S Original steel composition vector. Index denotes element whose representation we are interested in. Resulting number is again in range [0, 1]. W Original steel's weight in kg. C Desired composition vector. Index denotes element whose representation in steel we want to obtain. Resulting number is again in range [0, 1]. T Penalization constant. Very high number that is used to multiply the final fitness function's value in case the solution is outside the [Cmin, Cmax] range.

Table 2 .

 2 Experiments setting for algorithms DE and SOMA.

	(a) Experiments setting for DE.	(b) Experiments setting for DE.
	D	N P	G	F	CR	D	N P		G	F	CR
	14	1000	1500	0.8	0.6	14	50		2000	0.8	0.6
	14	1000	1500	0.8	0.5	14	50		2000	0.8	0.5
	14	1000	1500	0.7	0.6	14	50		2000	0.7	0.6
	14	1000	1500	0.7	0.5	14	50		2000	0.7	0.5
	14	1000	1500	0.5	0.7	14	50		2000	0.5	0.7
	14	1000	1500	0.5	0.6	14	50		2000	0.5	0.6
	14	1000	1500	0.5	0.5	14	50		2000	0.5	0.5
	14	500	1000	0.8	0.6	14	50		1500	0.8	0.6
	14	500	1000	0.8	0.5	14	50		1500	0.8	0.5
	14	500	1000	0.7	0.6	14	50		1500	0.7	0.6
	14	500	1000	0.7	0.5	14	50		1500	0.7	0.5
	14	500	1000	0.5	0.7	14	50		1500	0.5	0.7
	14	500	1000	0.5	0.6	14	50		1500	0.5	0.6
	14	500	1000	0.5	0.5	14	50		1500	0.5	0.5
			(c) Experiments settings for SOMA ALLToOne.
		D	N P M igrations P athLength Step P RT
		14 1000		200		3 0.11	0.1
		14 1000		200		3	0.3	0.1
		14 1000		200		3	0.1	0.1

Table 5 .

 5 Experimental results.

	DE (50, 1,500, 0.5, 0.5)	DE (500, 1,000, 0.8, 0.6)	DE (500, 1,000, 0.8, 0.5)	DE (500, 1,000, 0.7, 0.6)	DE (500, 1,000, 0.7, 0.5)	DE (1,000, 1,500, 0.8, 0.6)	DE (1,000, 1,500, 0.8, 0.5)	DE (1,000, 1,500, 0.7, 0.6)	DE (1,000, 1,500, 0.7, 0.5)	DE (1,000, 1,500, 0.5, 0.7)	DE (1,000, 1,500, 0.5, 0.6)	DE (1,000, 1,500, 0.5, 0.5)	Settings
		926,096.500 0.209 0.169 0.895 0.001 0.001 1.144 0.706 0.035 0.042 0.009 0.037 0.022 0.024 0.006 0.021 96.678	352,591.900 0.085 0.121 0.883 0.001 0.001 1.205 0.969 0.006 0.014 0.003 0.015 0.033 0.002 0.000 0.010 96.652	325,398.300 0.065 0.078 0.803 0.001 0.001 1.278 0.960 0.028 0.012 0.016 0.032 0.021 0.016 0.000 0.015 96.675	139,756.300 0.060 0.084 0.895 0.001 0.001 1.305 0.955 0.009 0.001 0.013 0.007 0.008 0.006 0.001 0.002 96.654	334,186.400 0.075 0.105 0.947 0.001 0.001 1.195 0.916 0.007 0.015 0.003 0.026 0.028 0.013 0.005 0.009 96.656	146,710.100 0.050 0.091 0.953 0.001 0.001 1.287 0.933 0.009 0.007 0.002 0.008 0.007 0.004 0.001 0.022 96.624	100,347.300 0.055 0.083 0.918 0.001 0.001 1.274 0.948 0.003 0.014 0.002 0.003 0.014 0.007 0.000 0.004 96.674	15,789.470 0.042 0.084 0.958 0.001 0.001 1.273 0.940 0.000 0.000 0.007 0.003 0.012 0.002 0.000 0.004 96.674	153.689 0.040 0.085 0.957 0.001 0.001 1.273 0.949 0.000 0.003 0.000 0.002 0.010 0.000 0.000 0.000 96.680	153.578 0.039 0.083 0.972 0.001 0.001 1.269 0.942 0.000 0.003 0.000 0.001 0.008 0.002 0.000 0.000 96.680	153.518 0.040 0.083 0.969 0.001 0.001 1.270 0.943 0.000 0.001 0.000 0.001 0.011 0.000 0.000 0.000 96.680	Fitness C Si Mn P S Cr Ni Mo Cu Nb V Al Ti N W Fe	Alloying elements [%]

Acknowledgement This work was supported by the European Regional Development Fund in the IT4Innovations Centre of Excellence project (CZ.1.05/1.1.00/02.0070) and by the Development of human resources in research and development of latest soft computing methods and their application in practice project, reg. no. CZ.1.07/2.3.00/20.0072 funded by Operational Programme Education for Competitiveness, co-financed by ESF and state budget of the Czech Republic.


Tomasz Chlebus
email: tomasz.chlebus@pwr.wroc.pl

The Cost Estimation of Production Orders

Keywords:

Time and cost oriented management of production orders requires methods and models of business processes in the enterprise as well as a structural analysis and a reference model of a production process based on a model of a production order. Estimating costs of the execution of a production order may contribute to initial and quite accurate analysis of the costs of the order. The developed method allows for estimation of the interdependence of costs in comparison with different clients. An example shows an analysis of costs of the manufacture of a frame for usual clients, who have no specific requirements, and for clients with additional requests regarding the products. The analysis of the costs of execution of such orders may help estimate the costs of diverse products in the future as well as predict cost variations for different orders. Additional operations may be taken into account and added to the final assessment of costs, which will allow for more accurate cost calculating and indicating orders with worse profitability or orders which cannot be executed due to excessive production costs. The method allows for assessment of production costs both in a sequential model and in distributed manufacturing.

INTRODUCTION

Requirements of market economy and increasing competition is forcing companies to change the management style in the direction of rationality and economic efficiency, which is based on the correct use of all outstanding offer companies the means of production. This is possible only if the decision-making processes are based on full information about the state of the company. Adequate information is required for economic decision making at all levels of management. Special role in the information system of economic information companies represent a high cost because the costs are the economic parameter, which shows the level of effort and resources involved in the production of economic activity. The focus is on cost management processes. Processes are identified, which raises the value of the so-called. value chain to be added. The management costs are related to the rationalization of their new methods of managing such a radical reconstruction processes. By contrast, directly aimed at cost management are the new cost accounting methods as developed in the U.S. cost accounting activities (Activity Based Costing -ABC) [START_REF] Cooper | Profit Priorities from Activity-Based Costing[END_REF] and a native of Japan, target costing (Target Costing) [START_REF] Pascoal | Targetcosting operationalization during product development: Model and application[END_REF], and the concept of product life management costs. Thus improving the balance sheet of a company is possible, inter alia, by carefully analyzing the cost of production and final demand. The best way to reduce costs is their foresight that can be made from the very beginning of its life cycle, so in the course of its conceptual design. Early diagnosis and determine the cost of the design, manufacture and distribution of finished products will allow the company to better manage their own capital and relationships with network providers. Basic data processing phase of construction-technological and organizational device manufacturing process is also called the phases of product development -design (Fig. 1). What is essential in costs of manufacturing process, especially during the development phase, is the possibility of influence of the designer and planner for the development costs implementation phases of the manufacturing process. As can be seen from the diagram as much as 70% of the cost is generated in the development phase of the product and its manufacturing processes. [START_REF] Bauer | Produkthaftung-Ansprüche an die Konstruktion haben einen Anteil von70%[END_REF] Items to be taken into account in this analysis are as follows:

• the purchase of materials,

• costs of materials,

• means of internal transport • costs associated with machines, tools and resources needed to manufacture,

• costs of servicing and ancillary staff (not production),

• storage of materials for the production in progress.

When examining the impact of individual elements on the final cost of the final product can be assumed that the cost of buying the materials will have the greatest impact on production. It is not always true. We are seeking suppliers of materials to choose from a number acceptable, which means that you can negotiate a purchase price of raw materials and components so that the costs incurred, did not influence significantly the cost of producing the product. On the other hand, need to pay special attention to the quality of the raw materials and components, whether they meet the requirements and whether the supply is consistent with the contract and the date.

Costs incurred during the production mainly generated by the many ingredients in the workplace and have a significant impact on the general costs of production, Fig. 2.

Places cost order at this stage of creating the finished product can be found primarily on the machinery, equipment and tools intended for machining and assembly components (in addition to the costs of course material, which is usually the price does not change dynamically). In order to solve problems cost please consider what factors influence the development of costs in the production process.

COSTS ESTIMATORS

RESOURCES •HUMAN, •MATERIAL, •NONMATERIAL RESOURCES (KNOW -HOW, SOFTWARE) INFRASTRUCTURE •CUBATURE, •PRODUCTION EQUIPMENT, •ENERGY, •SUPPLY AND TRANSPORT, PROCESS (machining & assambly) •TECHNOLOGY, •MATERIAL, •APPLIANCES •SUPPORT MEASURES PRODUCT •`PARTS •COMPONENTS, •MATERIALS, •SUPPORT MATERIALS

Fig. 2. Estimators costs in the production process [prep.]

Expenditure incurred in the almost three pillars (Fig. 3):

1. Product development, 2. Process development and production planning, 3. Machining, production control and logistic and assembly process management.

The most important step and also the point where the costs are planned and decisions are taken, often unknowingly, to the cost of production is where you prepare the documentation and product design, develop manufacturing technologies, identify the necessary resources and organization recalculate pre-project costs.

COST DATA MODEL FOR FORECAST

For the preparation of product documentation will be needed design, construction, technology, information on customer requirements. The costs of construction are not one of the most spending in the first phase of the product life, and therefore in the design. This happens because when the design is extremely difficult to assess whether the costs identified, incurred during this first phase will be in effect as they are scheduled.

The Cost Estimation of Production Orders

In the preparation phase of production should also take into account the cost of implementing the technology and technological burden of production. The structure should be taken into account the technological process of manufacturing the elements taken from the structure of construction and the identity of all aspects of production on some activities such as:

• The order of delivery of materials to production lines, • Transport equipment responsible for the internal transportation of raw materials, Cost based on the structure of the product it is necessary to determine when and what the costs and time are applied to the product. Analysis of the structure of the product, the tree cost and the time of manufacture is shown on Fig. 4 (Ishikawa diagram [4]).

Product (i) Product (i+1)

THE ALGORITHM OF COSTS ESTIMATING PROCESS

Taking into account these elements can be to build an algorithm of determining the cost of labour and production orders, which was presented at Fig. 5 and Fig. 6. By proceeding according to the individual steps away from the top of a full scenario in which there is to generate models: product, process and manufacturing system and manufacturing industry. These models are intended to identify the individual modes of production and providing the necessary data to apply methods, models and simulation tools.

The all-important issue in planning a new production facility is to determine the output level and pair it with an adequate production process. The output level is determined based on available expert and theoretical knowledge [START_REF] Kowalski | Hybrid Methods Aiding Organisational and Technological Production Preparation Using Simulation Models of Nonlinear Production Systems, Hybrid Artificial Intelligent Systems[END_REF].Very important information needed in this algorithm should be stored and accessed in knowledge bases and data bases. Data that are needed in order planning should include: specifications, procedures for KM and IT, and the other data that may be used in future. A significant role in this algorithm is modelling and simulation. Results of those to steps are easy to receive not incurring additional costs and charge on the production line. Of course there are needs that the enterprise that take or calculate order has to prepare a few variants of the order realization, but with sure they are less cost-intensive. There might to be more than one model in result, but all models should be stored in DB/KB, and be stored and analyzed in different productions orders. Continuous improvement of manufacturing system is important point of this method because the environment of production is changing dynamic.

Another important step is to generate simulation models, which will estimate the value sought. On this basis, a specific model of the aggregate costs and labour. The next step is to introduce data to the simulation programs such as Arena, ProModel and Igrafx and track the accuracy of the model built. With formula, you cannot tell right away whether it is best and meets the expectations. Therefore, on the basis of the model is base generates other variants that may arise during the actual production. The next step should be to compare the results with data from databases to determine the validity of the analysis and to be able to verify the developed models. Of course the model must be stable. Both supply (shipment) and production system should have to stable input. Ship stability system is rather complicated [START_REF] Kobyliński | System and risk approach to ship safety, with special emphasis of stability[END_REF], but in this model material delivery is realized by cells called kits. Following this analysis and find the best variant of the model, change the base model and deploy the generated model to an existing company. The company is a living, functioning organism, therefore, be still and seek to improve the system both in the form of the model and the actual conditions of production. The procedures for the determination of workload and direct costs:

• From the analyzes and the developed method can draw insights indicating that the full identification of the product model in the form of its hierarchical structure and complete information describing parameterized processes and production together with the available human and technical resources allows for accurate and rapid identification of the effort and cost of production job. It may be carried out in a simplified way, using tools such as MS Excel or in a multiple and multivariate analysis, with the help of simulation systems such as iGrafix or ProModel. Taking these elements set out in previous chapters, you can use them build an algorithm determining workload and cost of production job was, which is shown in Fig. 5 and Fig. 6. Items that are shown in the boxes, there are new procedures that have been introduced by the author to calculate the effort and cost of production order. Following each step from the top of the full scenario arises as a result of which there is to generate models of the product and the manufacturing process technology and manufacturing system. These models are intended to describe the various phases of production and providing the necessary data for the application of simulation tools.

SUMMARY

The algorithm for estimating the costs can be particularly useful for SMEs (small and medium-sized enterprises) [START_REF] Wilde | Small and Medium-Sized Enterprises, Customer Knowledge Management[END_REF], which for reasons of economic systems cannot implement ERP / Bus, and are devoid of advanced calculation tools which significantly reduces their competitiveness. CAD Tools / TPP / CAP / TPM today are already widely used in SMEs and can provide a basis to build custom implementations of storage product knowledge, technology and markets, which can significantly improve the competitiveness of not only business but also can ensure the stability of market

Fig. 1 .

 1 Fig. 1. Phase of product development and cost[START_REF] Bauer | Produkthaftung-Ansprüche an die Konstruktion haben einen Anteil von70%[END_REF]

Fig. 3 .

 3 Fig. 3. Factors affecting the cost of production orders (prep.)

Fig. 4 .

 4 Fig. 4. Model of balancing time and cost components in the node of the article (prep.) T -Production time T Ma -Time of material flow T wMa -Main time of material flow T bMa -Brake time of material flow T pz -Preparing and ending time T pzw -Main preparing and ending time T pzp -Subsidiary preparing and ending time K PF -Costs of final product K P1 -Costs of sub product K m1 -Cost of material flow K r1 -Cost of produce of subassembly K M1 -Cost of material

1 Fig. 5 . 7 .Fig. 8 .

 1578 Fig. 5. The algorithm of determination of workload and cost of production order (Part 1) (prep.)

Analysis of manufacturing process and current and

The Cost Estimation of Production Orders Described company manufactures freight and passenger trains as well as complete transportation systems. Wroclaw plant of the company consists of three divisions: Locomotives, Bogies, Service. The project presented in this paper was conducted in Bogies Division, where bogies frames for locomotives and for passenger trains are produced [START_REF] Burduk | Methods of risk evaluation in manufacturing systems[END_REF]. The following Fig. 7 presents an example of the deployment of machines from the ProModel simulation. Small parts Fig. 7. The plan layout production system simulation framework for ProModel [START_REF] Chlebus | Variant simulation and optimisation of production system in Bombardier Transportation Polska Company[END_REF] In addition, the final model was optimized in terms of:

• the optimal number of units of transport,

• shortening the length of road transport • optimal use of productive resources,

• optimal use of the production line.

After inputting new workstations in layout and applying some productions changes there are some interesting results which can see on (Fig. 8.) presented improved the productivity of a plot line for the new version.