<figure><img src="image_1.png" /></figure>

HAL
open science

# Pattern recognition by a piecewise polynomial approximation with variable joints

Christian Charles, Yves Lechevallier

<figure><img src="image_2.png" /></figure>

## To cite this version:

Christian Charles, Yves Lechevallier. Pattern recognition by a piecewise polynomial approximation with variable joints. [Research Report] IRIA-RR-338, IRIA. 1979, pp.23. hal-04716617

HAL Id: hal-04716617

https://inria.hal.science/hal-04716617v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
liv. 05674 RR338

IRIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_4.png" /></figure>

PATTERN RECOGNITION
BY A PIECEWISE
POLYNOMIAL APPROXIMATION
WITH VARIABLE JOINTS

Christian CHARLES
Yves LECHEVALIER

Rapport de Recherche N° 338

Janvier 1979

23p.
# PATTERN RECOGNITION BY A PIECEWISE POLYNOMIAL APPROXIMATION WITH VARIABLE JOINTS

Christian Charles, Yves Lechevallier

IRIA/LABORIA

## Résumé :

Lorsque nous désirons mémoriser de façon condensée l'information fournie par une fonction $g(x)$ échantillonnée en différents points d'un intervalle $[a,b]$, nous cherchons une fonction dépendant d'un petit nombre de paramètres qui approxime au mieux $g(x)$, au sens des normes $L_2$ et $L_\infty$. En pratique les fonctions les plus utilisées sont les polynomes ; toutefois, ceux-ci ne peuvent avoir de pentes infinies suivies de pentes nulles sur de courts intervalles si leurs degrés sont faibles, ce qui est nécessaire pour éviter les instabilités numériques. Nous avons donc choisi une approximation par des fonctions polynomiales par morceaux. Ces fonctions sont définies par division de l'intervalle $[a,b]$ en sous-intervalles dont les limites sont variables. Bien que la fonction approximante soit non linéaire et qu'on ne possède de solution générale, ce problème est de grande importance puisque la clé du succès d'une approximation locale réside dans l'emplacement de ces points limites.

Les algorithmes que nous présentons emploient de façon simultanée la classification automatique (algorithme de transfert, algorithme de Fisher) et les techniques de régression (norme $L_2$) ou de résolution d'un système linéaire surdimensionné au sens de Chebyshev (norme $L_\infty$).

Ces algorithmes présentent l'avantage de pouvoir être aisément généralisés aux cas de contours et permettent d'introduire des contraintes de continuité, de dérivabilité (fonctions splines) aux points limites, donnant ainsi ces propriétés à la fonction approximante globale sur $[a,b]$.

## Abstract :

The algorithms we propose for recognizing and memorizing curves employ simultaneously regression techniques and non hierarchical clustering.

We simultaneously search for a K-contiguous partition of the set of data and for K-regression hyperplanes that optimize a criterion measuring the proximity between the classes and the hyperplanes. In order to store a curve, we use the points separating two of the classes as well as the polynomial functions.

We also propose regression algorithms under local constraints enabling the stored curve to be continuous, with continuous derivatives or spline.
# 1. - INTRODUCTION

Let $g(x)$ be a given function defined on $[a,b]$. We want to find an approximating function in a given class of functions that will best approaches $g(x)$ in a certain sense on $[a,b]$. This problem appears when we are desirable to store a reduced amount of information which permits the effective reconstruction of original curves.

Practically the approximating functions considered are polynomials, rational fractions, trigonometric sums. The most often used are polynomials. However polynomials of low order cannot have consecutive infinite and small slopes while the approximation is unstable with high order polynomial. Another class of approximating functions is that of piecewise polynomials. These functions are defined by dividing the whole interval $[a,b]$ into sub-intervals with variable limits (or knots). But the approximating function is non linear when the knots are variable and there is no general solution. Nevertheless the problem is of considerable importance since the key to the successful use of piecewise polynomials is to have the location of the knots as variable.

Piecewise functional approximation is one method for preprocessing wave form data (Hor 74] ; Lav 74]. The data are fitted according to an error criterion with line segments. Such an approach is also proposed by McC 74], Lav 72] and [Dor 76]. Such preprocessing usually results in arbitrary segmentations. For BEL 61] the use of dynamic programming is appropriated. [Alb 73] and [Duf 74] propose the use the least squares method.

The algorithms we propose for recognizing and memorizing curves employ simultaneously regression techniques and non-hierarchical clustering. We simultaneously look for a K-contiguous partition and for K regression lines that optimize a criterion measuring the proximity between the regression lines $f_j(x)$ and the function $g(x)$.
The problem of data reduction is more and more important in all fields
where computers are used (for instance in automatic cartography). When we
want an efficient reconstruction of original curves we store the points
separating two contiguous classes and the K regression lines.

We also propose regression algorithms under local constraints enabling
the stored curve to have some mathematical properties. Finally we generalize
the method to the case of outlines (contours).
## 2. - THE PROBLEM

Our aim is to determine (K-1) points of subdivision $t_1, \dots, t_{K-1}$ which minimize the objective function

$$ \sum_{j=1}^{K} \int_{t_{j-1}}^{t_j} (g(x) - f_j(x))^2 dx $$

where $t_o = a, t_K = b$ and $a < t_1 < \dots < t_{K-1} < b$

$g$ is the observed function

$f_j$ is the calculated function of the interval $[t_{j-1}, t_j[$

This problem must be analysed in two parts :

1. For a given K-contiguous partition find K-approximating functions by least squares methods.

2. For a given K approximating functions find a K-contiguous partition by non hierarchical clustering method.

These two parts are iterated until the criterion becomes stationary nevermore decreases.

We define the space of kernels $L_K$ as

$$ L_K = \{ L/L = (L_1, \dots, L_K) \} $$

Where $L_j, \Psi_j = 1, K$, is some characteristic defining the j-th approximating function $f_j$ among the class of approximating functions.

We also define $P_K$ as the space of K-contiguous partitions of $[a,b]$

$$ P_K = \{ P/P = (P_1, \dots, P_K) \} $$

where $P_j$ is an interval.
Practically the function g is only measured on T points of [a, b].

Let $y_t = g(t)$, $t = 1, \dots, T$ be the data, we suppose that

$$y_t = f_j(t) + u_t \quad \forall t \in [t_{j-1}, t_j[$$

where $f_j(t)$ is the approximating function of t that we want to find on $P_j$, and $u_t$ is a residual.

The criterion to be minimized will be defined as

$$W : \mathcal{L}_K \times \mathcal{P}_K \to \mathbb{R}^+$$

$$(L,P) \to W(L,P) = \sum_{j=1}^{k} \sum_{t \in P_j} (g(t) - f_j(t))^2$$

It measures on all $P_j$ the sum of squared distances between observed and calculated values. The problem is an optimization problem :

Minimize $W(L,P)$ for all $P \in \mathcal{P}_K$ and $L \in \mathcal{L}_K$

It is impossible to use the complete enumeration method for finding the best partition among all partitions into K clusters [Jen 69].

In the following section we give two methods for solving this problem.

## 3. - ALGORITHMS

### 3.1. - First method - Transfer method

This algorithm, as it is explained in [And 74] consists in improving a partitioning previously estimated by moving an element from one class to another, under the condition of contiguity, the best transfer being obtained by optimizing a criterion.

More precisely the method consists of four steps

**Step 1** choose a pair of data points which separates two classes

**Step 2** move the left hand element to the class on the right. If the criterion does not decrease try moving the right hand point to the left class, or else continue moving points until the criterion does not decrease any longer.

**Step 3** repeat Step 2 for all separation

**Step 4** repeat Steps 1, 2, 3, until no new transfer makes the criterion decrease. This method converges to a local optimum.
To associate a K-tuples of kernels to a K-contiguous partition, we shall
introduce the function h

$$
h : \mathbb{P}_K \to \mathbb{L}_K
$$

$$
P \to L = (L_1 \dots L_K)
$$

where $(L_i)$ $i = 1,K$ is defined in 2.1.

We define two sequences

$$
v_n = (L^{(n)}, P^{(n)}) \text{ and } u_n = W(v_n)
$$

$$
\text{Let } L^{(o)} = h(P^{(o)}) \text{ and } v_o = (L^{(o)}, P^{(o)})
$$

By using the transfer method described above (steps 1,2,3) simultaneously with
the function h we obtain L(1), P(1) and V₁.

Using step 4 we obtain L<sup>(2)</sup>, P<sup>(2)</sup>, V<sub>2</sub> and so on.

We finally obtain : $L^* = (L_1^* \dots L_K^*)$

$$
P^* = (P_1^* \dots P_K^*)
$$

$$
W(L^*, P^*)
$$

when no new transfer makes the criterion decrease.

As $u_n$ is a sequence in $R^+$ and decreases, it converges.

As $\mathbb{P}_K$ and $L^{(n)} \in h(\mathbb{P}_K) \subset \mathbb{L}_K$ are finite this algorithm converges in a finite number of steps.
## 3.2. - Second method - dynamic programming algorithm

A dynamic programming algorithm [Bel 61] and [Fis 58] permits to find an optimal partition without examining the whole set of partitions into K clusters.

In [Bel 61], Bellman uses a dynamic programming algorithm to solve the problem of the approximation of curves by polynomial functions of fixed order. The problem is to determine (K-1) points $t_1 ... t_{K-1}$ (where $a = t_0 < t_1 ... < t_{K-1} < t_K = b$) which minimize the function

$$ \sum_{j=1}^{K} \int_{t_{j-1}}^{t_j} \left( g(x) - \sum_{l=0}^{q} \alpha_j^l x^l \right)^2 dx $$

If a set $E = \{x_1, ..., x_T\}$ is a set of T ordered elements ($x_1 < ... < x_i < ... < x_T$) and if $w$ is a function defined on the set of intervals of E (the clusters verified the order constraint) which only depends on an interval $P_j$, then the dynamic programming algorithm allows to find the optimal partition $P$ (K-contiguous partition)

The optimality is defined according to the criterion $W$ :

$$ W(P) = \sum_{j=1}^{K} w(P_j) $$

This algorithm is based on the following recurrence relation

$$ [R1] . F_k(i) = \min_{1 \le i < j \le t} \{ C_{ij} + F_{k-1}(j) \} \begin{cases} \psi_j = i+1, ..., T-k \\ \psi_k = 2, ..., K \end{cases} $$

$$ C_{ij} = w(B) \text{ where } B = \{x_i, ..., x_{j-1}\} $$

and

$F_{k-1}(j)$ is the optimal value of the objective function $W$ for the division of the subpopulation $\{x_j, ..., x_T\}$ of $E$ into (k-1) clusters.
The first step of this algorithm consists in the complete enumeration of the divisions of [a, b] into two parts. We build the first division {$x_1$}, {$x_2$ ... $x_T$} and we compute the objective function on the set {$x_2$, ..., $x_T$}. We note this value $F_1(2)$. Then the construction of the j-th division is {$x_1$, ..., $x_j$}, {$x_{j+1}$, ..., $x_T$} and we compute the objective function of {$x_{j+1}$, ..., $x_T$}. Let be the obtained value $F_1(j+1)$.

We continue until the division {$x_1, ..., x_{T-1}$}, {$x_T$} and we obtain (K-1) division into two clusters of E. Thus, we find out the optimal division in 2 intervals which minimizes the criterion w and we initialize the based recurrence relation [R1]. From this recurrence relation the following steps are:

At step k we know the function $F_{k-2}(j)$ and the optimal division results $O_j^{k-2}$ into k-2 intervals of sets {$x_j, ..., x_T$}, for j = 1, T. We note $C_{ij}$ the value of w {$x_i, ..., x_{i-1}$}.

For the division

$$ \{x_1, \dots, x_{i-1}\}, \{x_i, \dots, x_{j-1}\}, O_j^{k-2} $$

the criterion value is

$$ C_{li} + C_{ij} + F_{k-2} (j) $$

and the minimum value, is obtained by.

$$ \text{Min} \quad \{C_{li} + C_{i,j} + F_{k-2}(j)\} \quad \text{for} \quad \begin{cases} i=1, \dots, T-k-2 \\ j=i+1, \dots, T-k-1 \end{cases} \\ 1<i<j<T $$

and we compute the function $F_{k-1}$ which is necessary to the following step :

$$ F_{k-1} (i) = \text{Min} \quad \{C_{ij} + F_{k-2} (j)\} \quad \text{for } j = i+1, \dots, T-k-1 \\ 1 \le i < j \le T $$
## 4. POLYNOMIAL APPROXIMATION OF CURVES

We search $f(t) = \sum_{j=0}^{q} \alpha_j t^j$, polynomial function of order q.

For each class $P_i$ ($i = 1, K$) we search the $(\alpha_0^i, \alpha_1^i, ..., \alpha_q^i)$ that
minimize :

$$ \sum_{t \in P_i} (y_t - \sum_{j=0}^{q} \alpha_j^i t^j)^2 $$

(least squares criterion)

We now omit the index i.

We shall use orthogonal polynomials to simplify the computations.

Let $\{\Phi_0^q(t) ... \Phi_q^q(t)\}$ be the orthogonal polynomials. We have :

$$ \Phi_0^q(t) = 1 $$

and $\forall k = 1,q$

$$ \Phi_k^q(t) = t^k + C_{k-1}^q(t) t^{k-1} + \dots + C_1^q(t) t + C_0^q(t) $$

where $\forall j = 0, k-1$

$$ \sum_{t} \Phi_{i}^{q}(t) \Phi_{j}^{q}(t) = 0 \quad \text{for } i,j = 0,q \text{ and } i \neq j $$

So $f(t)$ becomes :

$$ f(t) = \gamma_0 + \gamma_1 \Phi_1^q(t) + \dots + \gamma_q \Phi_q^q(t) $$

and $\alpha_k = \gamma_k + C_k (k+1) \gamma_{k+1} + \dots + C_k (q) \gamma_q$

$$ \forall k = 0,q $$

The estimated values of $\gamma_k$ are

$$ \hat{\gamma}_k = \frac{\sum_{t} y_t \Phi_k^q(t)}{\sum_{t} \Phi_k^2(t)} \quad \forall k = 0,q $$
So we obtain the following form for W

$$W = \sum_{j=1}^{K} \sum_{t \in P_j} \left( y_t - \sum_{l=0}^{q} \hat{\alpha}_l^j t^l \right)^2$$

Note that the global representation of the set of data is not made by a continuous function and that we have

$$L_j = \begin{bmatrix} \hat{\alpha}_o^j \\ \hat{\alpha}_1^j \\ \vdots \\ \vdots \\ \hat{\alpha}_q^j \end{bmatrix} \quad \forall j = 1, \dots, K$$

It is necessary to have (q+1) elements in the cluster $P_j$ for computing the values $(\hat{\alpha}_o^j, \dots, \hat{\alpha}_q^j)$ of $L_j$. In this case, the two algorithms are used with this constraint and the dynamic programming algorithm gives an optimal solution.

## 5. - THE MODIFIED MODEL

The curve we obtain by this method is not continuous. So we must introduce local constraints in the evaluation of the kernels. For example, this is useful if we want to store altitude curves.

In each class $P_i$ ($\forall i = 2, K$) we have

$$y_t = \alpha_0^i + \alpha_1^i t + \dots + \alpha_q^i t^q + u_t$$

$$\hat{y}_{t_{i-1}} = \alpha_0^i + \alpha_1^i t_{i-1} + \dots + \alpha_q^i t_{i-1}^q$$

where. $\hat{y}_{t_{i-1}}$ is the evaluated value of $y_{t_{i-1}}$

$t_{i-1}$ is the right element of $P_{i-1}$

$$\hat{y}_{t_{i-1}} = \sum_{j=0}^{q} \hat{\alpha}_j^{i-1} t_{i-1}^j$$
For the first class $P_1$ there is no constraint (so we evaluate $L_1$ as
in 4.

For $P_2 \dots P_K$ we have to minimize

$$
\sum_{i \neq 1} u_t^2 \quad \text{under the constraint } R_i \alpha_i = r_i
$$

where :

$$
R_i = [1, t_{i-1}, \dots, t_{i-1}^q]
$$

$$
r_i = \hat{y}_{t_{i-1}}
$$

$$
\alpha_i = \begin{bmatrix} \alpha_0^i \\ \vdots \\ \alpha_{q_i}^i \end{bmatrix}
$$

If we omit the index i this is equivalent to minimizing

$$
(Y - T\alpha)'(Y - T\alpha) \text{ under } R\alpha = x
$$

where . $Y$ is the vector of $y_t / t \in P_i$

. T is the matrix of rows (1,t, ... t<sup>q</sup>)

$$
\forall t \in P_i
$$

With the Lagrangian method, we obtain

$$
\hat{a} = (T'T)^{-1} T'Y - (T'T)^{-1} R' [R(T'T)^{-1} R']^{-1} [R(T'T)^{-1} T'Y - r]
$$

If we use orthogonal polynomials, $(T'T)^{-1}$ is easily obtained and
$R(T'T)^{-1} R'$ is a scalar.
## Convergence properties

- the first algorithm

We have only modified the function h. As we still use 3 the convergence is ensured

- the second algorithm

The partition obtained is not optimal when we use this algorithm because the approximating function depend of the precedent interval. But, if we use the spline function (see following section) as approximating function then this algorithm gives the optimal partition and this solution respects the continuity between the intervals.

# 6. - GENERALIZATION OF THIS ALGORITHM TO THE CASE OF A SPLINE FUNCTION

This algorithm can be generalized in such a way as to obtain continuous derivatives. It suffices to introduce other constraints.

## 6.1. - Spline function [Gre 69]

**Définition** : $\delta$ is a spline function of order k if there are points

$(x_i)_{i=0,m}$ such that

$$a = x_0 < x_1 \dots < x_{m-1} < x_m = b$$

where on each $[x_{i-1}, x_i]$, $\delta$ is polynomial function of order k, with (k-1) first continuous derivatives.

In this case we have on $P_2... P_K$

$$[1] \quad y_t = \gamma_0 + \gamma_1 \Phi_1(t) + \dots + \gamma_q \Phi_q(t) + u_t$$
$$ [2] \quad \hat{y}_{t_{i-1}}^{(j)} = \gamma_0 + \gamma_1 \Phi_1^{(j)}(t) + \dots + \gamma_q \Phi_q^{(j)}(t), \forall j = 0, q-1 $$

and where

1. $\hat{y}_{t_{i-1}}^{(j)}$ is the evaluation on $P_{i-1}$ of the function ($j=0$) and of its derivatives ($j = 1,q$) at $t_{i-1}$

2. $\Phi_k^{(j)}(t_{i-1})$ is the $j$th derivative of the $k$th orthogonal polynomial on $P_{i-1}$ at $t_{i-1}$

The estimates $\hat{\gamma}$ are given by 5.1. where

$$ R = \begin{bmatrix} 1 & \Phi_1(t_{i-1}) & \cdots & \Phi_q(t_{i-1}) \\ 0 & \Phi_1^{(1)}(t_{i-1}) & \cdots & \Phi_q^{(1)}(t_{i-1}) \\ \vdots & \vdots & \ddots & \vdots \\ 0 & \Phi_1^{(q-1)}(t_{i-1}) & \cdots & \Phi_q^{(q-1)}(t_{i-1}) \end{bmatrix}, r = \begin{bmatrix} \hat{y}_{t_{i-1}}^{(0)} \\ \vdots \\ \vdots \\ \vdots \\ \hat{y}_{t_{i-1}}^{(q-1)} \end{bmatrix} $$

## 6.2. - Interpolation SPLINE function

**Définition** : $\delta$ is an interpolation spline function of order $k$ if there are points $(x_i)_{i=0,m}$ with

$$ a = x_0 < x_1 < \dots < x_l < \dots < x_m = b $$
where on each $[x_{i-1}, x_i]$ $\delta$ is a polynomial function of order $k$, with $(k-1)$
first continuous derivatives and

$$
\left\{
\begin{array}{l}
\delta(x_i) = y_{x_i} \\
\\
\delta(x_{i-1}) = y_{x_{i-1}}
\end{array}
\right.
$$

where $y_i$ is the curve we want to recognize

In this case we have on ($P_2... P_K$) the equations [1],

$$
[2] \quad (\forall j = 1, \dots, q-1) \text{ and if } t_i \text{ is the left most element of } P_i
$$

$$
[3] \quad \left[
\begin{aligned}
y_{t_i} &= \gamma_0 + \gamma_1 \Phi_1 (t_i - 1) + \dots + \gamma_q \Phi_q (t_i - 1) \\
y_{t_i} &= \gamma_0 + \gamma_1 \Phi_1 (t_i) + \dots + \gamma_q \Phi_q (t_i)
\end{aligned}
\right.
$$

For $P_i$ we have only [1] and [3].

Here there is no estimation problem because we have (q+1) constraints on (q+1)
variables.

So we must solve a linear system of the form Rα = r

As R is quite triangular, the use of the Gauss-Seidel method is
very easy.

Three examples are given by figures 1, 2a and 2b.
## 6. The second algorithm with a spline function

In this case, the dynamic programming algorithm permits to find the covering into K intervals of [a, b]. If $t_1, \dots, t_{K-1}$ are the subdivision points then the covering into K clusters is

$$ [a, t_1], [t_1, t_2], \dots [t_{j-1}, t_j], \dots, [t_{K-1}, b] $$

The value of the interval $[t_j, t_{j+1}]$ does not depend of the two contiguous intervals because the spline function on $[t_j, t_{j+1}]$ goes to $y_{t_j}$ and $y_{t_{j+1}}$.

The spline function interpolation conserves the continuity and this algorithm finds the optimal solution

## 7. - GENERALIZATION

We generalize those algorithms to the case of a function defined by $(X_t, Y_t)$

$$ \forall t = 1, T $$

We search for a K-contiguous partition of $\{1, \dots, T\}$ and for the functions $f_j$ and $g_j$. $\forall j = 1, K$ defined by :

$$ \cdot X_t = f_j(t) + u_t \quad \forall t \in P_j $$

$$ \cdot Y_t = g_j(t) + v_t \quad \forall t \in P_j $$

that minimize

$$ W(L,P) = \sum_{j=1}^{K} \sum_{t \in P_j} \left[ (X_t - f_j(t))^2 + (Y_t - g_j(t))^2 \right] $$

If $f_j$ and $g_j$ are polynomial functions of t

$$ \cdot f_j(t) = \sum_{i=0}^{q} a_i^j t^i $$

$$ \cdot g_j(t) = \sum_{i=0}^{q'} b_i^j t^i $$
We use 3 and 4 for evaluating $(P_1...P_K)$ and $(L_1...L_K)$ where

$$L_j = [(\hat{a}_o^j...\hat{a}_q^j), (\hat{b}_o^j..., ...\hat{b}_q^j)]$$

We use two algorithm for solving this problem. In the case of dynamic programming algorithm we transform one contour into totally ordered set by a cut. One cut transforms one contour into totally ordered set. At the cut j we research the optimal cutting out of the (T+1) points {$j,...,T,1,...,j$}. The solution is the best optimal division of this T cuts. It is possible to generalize this problem in the case where the contour is defined in $\mathbb{R}^P$. One example is given by the figure 3.

## 8. - CONCLUSION

In the algorithms presented we can easily add linear equality constraints, so as to obtain continuity and derivability and still preserve convergence. These procedures can also be generalized to the case of uniform polynomial approximation. Also we minimize the following criterion :

$$\max_{j=1,...,K} \quad \max_{t_{j-1} \le x \le t_j} |g(x)-f_j(x)|$$

and we obtain a balanced error solution. In this case we use an ascending method for solving the over determined system of linear equations instead of least squares method. By these techniques we can conserve continuity and derivability if it is desirable.
<figure><img src="image_5.png" /><figcaption>Figure 1</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>Figure 2a</figcaption></figure>
<figure><img src="image_7.png" /><figcaption>Figure 2b</figcaption></figure>
<figure><img src="image_8.png" /><figcaption>Figure 3</figcaption></figure>

--- polynomial approximation function

— observed functions
BIBLIOGRAPHY

[Alb 74] ALBANO - "Representation of digitized contours in terms of conic arcs and straight line segments",
N.Y. University - Academic Press (1974).

[And 73] ANDERBERG - "Cluster analysis for applications",
N.Y. - Academy Press (1973).

[Bel 61] BELLMAN - "On the approximation of curves by line segments using dynamic programming",
Communication of the ACM (1961).

[Can 71] A. CANTONI - "Optimal curve fitting with piecewise linear functions",
IEEE Trans Computers C-20 (1971).

[Cha 77] C. CHARLES - "Regression typologique et reconnaissance des formes",
Thèse de 3e cycle 1977.

[McC 74] Mc CLURE - "Problems and methods of non linear feature generation in pattern analysis",
Princeton Conf. on Inform. Sciences and Systems 1974.

[Did 76] E. DIDAY - "Nouvelles méthodes et nouveaux concepts en classification automatique et reconnaissance des formes",
Thèse d'Etat 1972.

[Dor 71] A.A. DOROFEYUK - "Algorithms of automatic classification",
Automatica i telemechanica, N°12, 1971.

[Dor 76] A.A. DOROFEYUK, IBRAGIMLI Sh. D, MOVSUNIOV V.G. - "The use of the statistical equivalence criterion in the piecewise approximation problem",
Automatica i telemechanica, N°7, 1976.
[Duf 74] DUFOUR - "Programmes de mémorisation de profils et contours sous forme condensée",
Institut Géographique National (1974).

[Fis 58] FISHER W.D. - "On grouping for maximum homogeneity",
J.A.S.A. n° 53, pp. 789-798 (1958).

[Gre 69] GREVILLE - "Introduction to spline functions : Theory and application of spline functions",
N.Y. Academic Press (1969).

[Hor 74] HOROWITZ, PAVLIDIS - "Picture Segmentation by a Directed Split and Merge Procedure",
Departement of Electrical Engineering, Princeton University (1974).

[Jen 69] JENSEN R.E. - "A Dynamic Programming Algorithm for Cluster Analysis"
Oper. Res. 12, pp. 1084-1097, (1969).

[Lav 74] LAVEEN KANAL - "Patterns in pattern recognition : 1968, 1974",
IEEE, Vol. IT-20, n° 6, (1974).

[Lav 72] LAVIN - "Stochastic feature a lection"
Report n°3 on Pattern analysis (1972).Brown Univ. Providence.

[Lec 76] LECHEVALLIER Y. - "Classification automatique optimale sous contrainte d'ordre total",
Rapport de Recherche IRIA-LABORIA n° 200 (1977).

[Rao 71] RAO M.R. - "Cluster Analysis and Mathematical Programming",
J.A.S.A. pp. 622-626, (1971).