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

HAL
open science

# Mise en œuvre expérimentale d'algorithmes d'identification stochastique d'images

Jean-Paul Chieze, Samer Attasi

► To cite this version:

Jean-Paul Chieze, Samer Attasi. Mise en œuvre expérimentale d'algorithmes d'identification stochas-tique d'images. [Rapport de recherche] IRIA-RR-099, IRIA. 1975, pp.39. hal-04716100

HAL Id: hal-04716100

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

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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
RIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

laboratoire de recherche
en informatique
et automatique

Mise en œuvre
expérimentale d'algorithmes
d'identification stochastique
d'images

Samer
J.P. Chieze-S. Attasi

Rapport de Recherche n°99

Janvier 1975
MISE EN OEUVRE EXPÉRIMENTALE
D'ALGORITHMES D'IDENTIFICATION STOCHASTIQUE
D'IMAGES

J.P. Chieze - S. Attasi

Résumé :

Ce rapport présente une série d'expérimentations réalisées au Laboratoire de calcul Hybride du LABORIA, dans le cadre du projet «traitement du signal en temps réel». Ces expérimentations ont permis une première validation de la modélisation stochastique des images développée récemment [ATTASI<sup>2,3,4</sup>].

Abstract :

The set of experiments, presented here has been realized at the «hybrid Computing Laboratory of LABORIA» within the project «Real time processing of signals». These experiments give a first validation to the stochastic modelization of images that has been recently developed [ATTASI<sup>2,3,4</sup>].
# SOMMAIRE

Page

I. Introduction. 1

II. Bases théoriques. 2

III. Mise en œuvre de l'identification stochastique. 4

IV. Application des algorithmes d'identification à des fonctions $\Lambda(.,.)$ calculées. 11

V. Application des algorithmes d'identification à des images simulées. 18

VI. Application des algorithmes d'identification à des images réelles. 28

VII. Conclusion. 38

BIBLIOGRAPHIE 39
La définition de modèles stochastiques récurrents permet souvent de trouver des solutions récursives optimales aux problèmes de traitement du signal. Ainsi le filtrage de KALMAN s'applique aux suites à un indice à représentation gaussienne markovienne [FAURRE, KAILATH, KALMAN]. Plus récemment des travaux au sein du LABORIA [ATTASI] ont permis de proposer une modélisation stochastique des images aboutissant à des algorithmes de traitement récursif. L'étude expérimentale présentée dans ce rapport permet :

- d'une part d'étudier la validité numérique des algorithmes d'identification stochastique,

- d'autre part d'établir la capacité de cette modélisation à représenter des images réelles.
## II. BASES THEORIQUES

Une modélisation statistique des images, considérées comme des échantillons de suites gaussiennes à deux indices a été proposée dans [ATTASI]. Ainsi, à tout ensemble d'images admettant la même fonction d'autocorrélation $+$, $\Lambda(\cdot, \cdot)$, on associe, s'ils existent, des modèles de la forme :

$$ (1) \qquad \begin{cases} Y_{i,j} = H X_{i,j} \\ X_{i,j} = F_1 X_{i-1,j} + F_2 X_{i,j-1} - F_1 F_2 X_{i-1,j-1} + V_{i-1,j-1} \end{cases} $$

où

* $\{V_{i,j}\}$ est une suite de variables indépendantes (bruit blanc) à valeurs dans $\mathbb{R}^n$, de covariance $Q = LL'$.

* $H, F_1, F_2$ sont des matrices de dimensions appropriées. De plus $F_1$ et $F_2$ commutent et ont toutes leurs valeurs propres à l'intérieur du cercle unité.

Nous rappelons ci-dessous les résultats qui nous intéressent.

Soit un ensemble d'images admettant la même fonction d'autocorrélation $\Lambda(\cdot, \cdot)$; alors :

i) s'il existe des modèles du type (1) que l'on peut associer à $\Lambda(\cdot, \cdot)$, il existe un modèle de dimension minimale (matrices $F_1$ et $F_2$ de dimensions minimales) unique à un changement de base près transformant le quadruplet $(H, F_1, F_2, L)$ en $(HT^{-1}, TF_1T^{-1}, TF_2T^{-1}, TL)$ où T est la matrice de changement de base.

+ La fonction d'autocorrélation d'une suite gaussienne "homogène" à deux indices $\{Y_{i,j}\}$ est définie par $\Lambda(k,l) = E[Y_{i+k,j+l} Y_{i,j}]$.
ii) à partir de la fonction $\Lambda(\cdot, \cdot)$, on peut trouver l'un des quadruplets $(H, F_1, F_2, L)$ de dimension minimale, en deux étapes :

a) déterminer un quadruplet $(H, F_1, F_2, G)$ de dimension minimale (lequel est défini à un changement de base près), vérifiant :

$$ (2) \qquad \forall i \ge 0, \forall j \ge 0 \qquad \Lambda(i,j) = H F_1^i F_2^j G $$

b) déterminer une matrice L unique donnée par les équations :

$$ (3) \quad \left\{ \begin{array}{l} \forall i \ge 0, j \ge 0 \qquad \Lambda(i,-j) = H F_1^i P F_2^{j'} H' \\ G = P H' \\ P - F_1 P F_1' - F_2 P F_2' + F_1 F_2' P F_1' F_2' = Q = LL' \end{array} \right. $$

Notons que dans les équations (3), la matrice P représente la covariance du vecteur "d'état" $X_{i,j}$.
### III. MISE EN ŒUVRE DE L'IDENTIFICATION STOCHASTIQUE

L'identification stochastique d'une image {$Y_{i,j}$} admettant la fonction d'autocorrélation $\Lambda(\cdot, \cdot)$ consiste à trouver un modèle du type (1), de dimension minimale (les autres s'en déduisant simplement par "changement de base") caractérisé par :

- la covariance $Q$ du bruit {$V_{i,j}$},

- les matrices $H,F_1,F_2$.

#### III. 1. La description des algorithmes.

La fonction $\Lambda(i,j)$ étant donnée pour $0 \le i \le p, -p \le j \le p,$ on procède en deux étapes :

a) **1ère étape** : Algorithme de réalisation à deux indices.

A partir des valeurs de $\Lambda(i,j)$ pour $0 \le i \le p, 0 \le j \le p,$ l'algorithme de réalisation à deux indices défini dans [ATTASI] et dont une version a été décrite et mise en œuvre en FORTRAN dans [CLERGET], fournit le quadruplet $(H,F_1,F_2,G)$ défini par les équations (2).

Rappelons brièvement le principe et les étapes de cet algorithme. On définit à partir des données $\Lambda(\cdot, \cdot)$ une matrice $\mathcal{A}$ (matrice de Hankel généralisée) que l'on factorise suivant une **procédure récursive**, sous la forme :

$$ \mathcal{A} = \hat{\mathcal{P}} \mathcal{Q} $$

caractérisée par le fait que la matrice $\mathcal{Q}$ est constituée des **lignes indépendantes** de la matrice $\mathcal{A}$.

Il est démontré [ATTASI] alors que l'on a :
$$
(4) \quad \left\{
\begin{array}{l}
H = \text{1ère ligne de } \rho \text{ (toujours } 1,0\text{---0))), \\
G = \text{1ère ligne de } Q, \\
F_1 = \rho^{-1} \sigma_{\Gamma_1} \rho, \\
F_2 = \rho^{-1} \sigma_{\Gamma_2} \rho.
\end{array}
\right.
$$

où

* $\sigma_{\Gamma_1}$ et $\sigma_{\Gamma_2}$ sont des opérateurs définis de la manière suivante. L'indice de la ligne des matrices $\rho$, $\sigma_{\Gamma_1} \rho$, $\sigma_{\Gamma_2} \rho$ est défini par une bijection $\sigma = \mathbb{N}^2 \to \mathbb{N}$ ; $k = \sigma(i,j)$. La $1$-ligne $\Gamma_1$ d'indice $k = \sigma(i,j)$ de $\sigma_{\Gamma_1} \rho$ (resp. $\sigma_{\Gamma_2} \rho$) est identique à la ligne d'indice $k = \sigma(i+1,j)$ (resp. $k = \sigma(i,j+1)$) $2$-de $\rho$.

* $\rho^{-1}$ est l'inverse à gauche de la matrice de rang plein $\rho$.
La version mise en œuvre dans [CLERGET] et qui a été reprise ici consistait, à partir de raisonnements algébriques, à remarquer que les matrices $F_1$ et $F_2$ étaient simplement des sous matrices de $\rho$.

b) **2ème étape** : Calcul de la matrice de covariance $Q$ du bruit.

Pour cela on calcule d'abord la matrice $P$ de covariance de
l'état. Cette matrice $P$ doit être telle que :

$$
(5) \quad \Lambda(i,-j) = H F_1^i P F_2^j H' \quad 0 \le i \le p, 0 \le j \le q.
$$

(On montre que la condition $G = P H'$ est contenue dans l'équation (5)).

Deux méthodes de calcul de cette matrice P ont été envisagées :

1ère méthode :

Précisons quelques notations :

- soit n l'ordre du modèle (dimension de $F_1$ et $F_2$),

- soient $\theta_1, \theta_2$, A trois matrices carrées de dimension n
définies par :
$$
\theta_1 = \begin{bmatrix} H \\ H F_1 \\ \vdots \\ H F_1^{n-1} \end{bmatrix} \quad \text{matrice d'observabilité du couple } (H, F_1) ;
$$

$$
\theta_2 = \begin{bmatrix} H \\ H F_2 \\ \vdots \\ H F_2^{n-1} \end{bmatrix} \quad \text{matrice d'observabilité du couple } (H, F_2) ;
$$

$$
A = \begin{bmatrix} 1_o \\ \vdots \\ 1_{n-1} \end{bmatrix} \quad \begin{array}{l} \text{où } l_i \text{ est la ligne d'éléments } \Lambda(i,j) \\ \text{pour } j = 0, -1, \dots, -n+1. \end{array}
$$

L'équation (5) s'écrit alors :

$$
A = \theta_1 P \theta_2 .
$$

On sait que θ₁ et θ₂ sont de rang n, donc inversibles. D'où la solution :

$$
(6) \quad P = \theta_1^{-1} A \theta_2^{-1}.
$$

Cette méthode, peu coûteuse en calculs, est valable dans le
cas où l'équation (5) peut être exactement vérifiée, mais elle est sen-
sible aux erreus d'estimation de la fonction d'autocorrélation, car elle
ne tient compte que de n² valeurs de cette fonction, et ne prend pas en
considération la symétrie de P.

On a préféré utiliser une autre méthode de calcul de la matrice P.
Il s'agit d'une méthode de moindres carrés exposée ci-dessous.

2ème méthode :

On se propose de trouver une matrice symétrique P minimisant
une norme l² de la suite { ̃$\Lambda_{i,j}$ } définie par :
$$
(7) \quad \left\{
\begin{array}{l}
\tilde{\Lambda}_{i,j} = \Lambda(i,j) - H F_1^i F_2^j P H' \\
\tilde{\Lambda}_{i,-j} = \Lambda(i,-j) - H F_1^i P F_2^j H'
\end{array}
\right.
\qquad 0 \le i \le p, 0 \le j \le p
$$

En notant $(H F_1^i)_k$ l'élément k du vecteur ligne $H F_1^i$ ($K = 1, \dots, n$)
et en remarquant que :

$$
H = [1, 0, \dots, 0] \text{ et } P H' = [P_{11}, \dots, P_{1,n}],
$$

les équations (7) deviennent :

$$
(8) \quad \left\{
\begin{array}{l}
\tilde{\Lambda}_{i,j} = \Lambda(i,j) - \sum_{k=1}^{n} (H F_1^i F_2^j)_k P_{1k} , \\
\\
\tilde{\Lambda}_{i,-j} = \Lambda(i,-j) - \sum_{k=1}^{n} (H F_1^i)_k P_{kl} (H F_2^j)_l \\
\qquad i = 0, \dots, p \text{ et } j = 0, \dots, p.
\end{array}
\right.
$$

Les équations (8) conduisent à la résolution d'une équation matricielle
de la forme :

$$
(9) \qquad A X = B,
$$

où

* X est, compte tenu de la symétrie de P, le vecteur d'élément
P<sub>kl</sub> pour k = 1, ..., n et l = k, ..., n.

* B est un vecteur dont les éléments notés B_m représentent
les Λ(.,.) rangés dans un ordre donné.

* A est une matrice de dimension $\left[ (p+1)(2p+1) \times \frac{n(n+1)}{2} \right]$ dont les lignes notées $L_m$ sont définies par :

$$
\bullet L_m = [(H F_1^i F_2^j)_1, \dots, (H F_1^i F_2^j)_n, 0, \dots, 0],
$$

• $L_m = [(H F_1^i F_2^j)_1, \dots, (H F_1^i F_2^j)_n, 0, \dots, 0]$,
pour les indices m tels que $B_m = \Lambda(i,j) (0 \le j \le p)$ ;
$$ \bullet L_m = [(H F_1^i)_1 (H F_2^j)_1, (H F_1^i)_1 (H F_2^j)_2 + (H F_1^i)_2 (H F_2^j)_1, \dots, (H F_1^i)_n (H F_2^j)_n], $$

pour les indices m tels que $B_m = \Lambda(i, -j) (0 \le j \le p)$.

Il est bien connu [GANTMACHER] que la "solution aux moindres carrés" de l'équation (9), qui est définie comme étant le vecteur X qui minimise le critère :

$$ (10) \quad J = (A X - B)' (A X - B), $$

est donnée par :

$$ (11) \quad X = (A'A)^{-1} A' B. $$

De plus, si l'on veut introduire, dans la norme $l^2$ de la suite $\{\tilde{A}_{i,j}\}$, une matrice de pondération C, le problème se ramène à trouver un vecteur X qui minimise le critère quadratique :

$$ (12) \quad J = (A C X - B)' (A C X - B), $$

et la solution devient :

$$ (13) \quad X = (A' C A)^{-1} A' C B. $$

La matrice C choisie a été la matrice diagonale d'éléments $C_{mm} = B_m^2 = \Lambda^2(.,.)$.

### III. 2. Les séries d'expériences – Les critères choisis.

Les algorithmes décrits ci-dessus ont été implantés en assembleur sur le calculateur numérique T 2000 du laboratoire de calcul hybride du LABORIA. +

+ "Le temps de calcul correspondant à ces algorithmes est de quelques secondes pour des représentations allant jusqu'à l'ordre trois. Il demeure négligeable devant le temps requis pour l'acquisition de l'image et le temps nécessaire pour l'estimation de la fonction $\Lambda(.,.)$ (plusieurs minutes chacun pour une image 128 x 128). D'autre part la place mémoire requise n'est pas critique pour un minicalculateur ; elle est de l'ordre de 4k-mots.
Trois séries d'expériences ont été menées successivement, et
les résultats présentés dans les chapitres IV, V, VI :

i) Les algorithmes d'identification ont été appliqués à une suite $\Lambda(\cdot, \cdot)$ calculée à partir de la donnée des matrices $H, F_1, F_2, Q$. Cette étape a permis de déterminer la précision numérique intrinsèque des algorithmes.

ii) Les algorithmes d'identification ont été appliqués à une suite $\Lambda(\cdot, \cdot)$ représentant l'estimée de la fonction d'autocorrélation d'une image simulée à partir du modèle correspondant aux matrices $H, F_1, F_2, Q$. Cette étape a permis d'étudier la sensibilité de ces algorithmes à des erreurs sur les valeurs de $\Lambda(\cdot, \cdot)$.

iii) Les algorithmes d'identification ont été appliqués à une suite $\Lambda(\cdot, \cdot)$ représentant l'estimée de la fonction d'autocorrélation d'images réelles. Cette étape a permis de vérifier la représentativité de la modélisation considérée.

La précision de l'identification a été mésurée en comparant
dans chaque cas la suite $\Lambda(\cdot, \cdot)$ sur laquelle les algorithmes ont été
appliqués à la suite $\hat{\Lambda}(\cdot, \cdot)$ représentant la fonction d'autocorrélation
du modèle obtenu. Deux mesures de la distance relative entre les suites
$\Lambda(\cdot, \cdot)$ et $\hat{\Lambda}(\cdot, \cdot)$ ont été utilisées :

- distance quadratique d :

$$
(14) \quad \sum_{i,j} [\Lambda(i,j) - \hat{\Lambda}(i,j)]^2 \\
d = \frac{\sum_{i,j} \Lambda^2(i,j)}{\sum_{i,j} \Lambda^2(i,j)}
$$

- distance quadratique pondérée D :

$$
(15) \quad D = \frac{\sum_{i,j} \frac{1}{i^2 + j^2} [\Lambda(i,j) - \tilde{\Lambda}(i,j)]^2}{\sum_{i,j} \frac{1}{i^2 + j^2} \Lambda^2(i,j)}
$$
La comparaison de ces deux mesures fournit en outre une idée
sur la distribution des erreurs relatives en fonction de i et j. Notons
qu'une mesure de l'erreur relative maximale,

$$
\sup_{(i,j)} \frac{\Lambda_{i,j} - \Lambda_{i,j}^{\hat{\Lambda}}}{\Lambda_{i,j}}
$$

pourrait être envisagée, mais ne serait pas significative en pratique
car les valeurs de Λ(i,j) pour i et j élevés sont elles-mêmes faibles
en valeur absolue et entachées d'erreurs relatives importantes.

La commutativité (cas où la dimension des représentations est
supérieure à 1) de matrices F₁ et F₂ dans les représentations obtenues
a été étudiée. Il est difficile, en dehors des enseignements ultérieurs
qu'apporteront les expériences de traitement d'images à partir de ces
modèles, de définir un critère et une mesure quantitative de la commu-
tativité, qui soient significatifs en pratique. Néanmoins, la mesure
suivante :

$$
(16) \quad \delta = \frac{\| F_1 F_2 - F_2 F_1 \|}{\sqrt{\| F_1 F_2 \| \| F_2 F_1 \|}}
$$

où

$||F||$ = module de la plus "grande valeur propre" de la matrice F,
a été calculée pour quelques exemples, notamment pour les images "réelles".
Cette mesure garde le même ordre de grandeur que la mesure d de la précision
quadratique de l'identification définie ci-dessus.
# IV. APPLICATION DES ALGORITHMES D'IDENTIFICATION A DES FONCTIONS $\Lambda(.,.)$

## CALCULEES

L'objet de cette série d'expériences est de tester la précision intrinsèque des algorithmes d'identification. A cette fin, on a procédé de la manière suivante :

1) A partir de données $H, F_1, F_2, P$, un programme calcule :

$$ egin{cases} 
\Lambda(i,j) = H F_1^i F_2^j P H' \\ 
\Lambda(i,-j) = H F_2^j P F_1^i H' 
\end{cases} 
\quad 0 \le i \le p; \ 0 \le j \le p $$

et visualise cette fonction sous la forme d'une "surface" + dans l'espace $\mathbb{R}^3$.

2) Les algorithmes d'identification stochastique décrits dans le paragraphe précédent sont appliqués à la suite $\Lambda(i,j)$ ainsi calculée, et donnent les matrices $\hat{H}, \hat{F}_1, \hat{F}_2, \hat{P}, \hat{Q}$ du modèle.

3) On compare, avec les mesures décrites au paragraphe précédent la suite initiale $\Lambda(i,j)$ à la suite $\hat{\Lambda}(i,j)$ donnée par :

$$ egin{cases} 
\hat{\Lambda}(i,j) = \hat{H} \hat{F}_1^i \hat{F}_2^j \hat{P} \hat{H}', \\ 
\Lambda(i,-j) = \hat{H} \hat{F}_1^i \hat{P} \hat{F}_2^j \hat{P} \hat{H}'. 
\end{cases} $$

Les pages suivantes présentent les résultats obtenus pour des quadruplets de dimension 1, 2 et 3. Pour chaque exemple, ont été figurés sur la même page, la "surface" + représentant la fonction $\Lambda(.,.)$, le modèle obtenu par l'application des algorithmes d'identification, et la valeur des mesures de la précision de l'identification.

<footnote>+ Cette surface est obtenue en portant sur 3 axes mobiles les valeurs respectives de i, j, $\Lambda(i,j)$ pour $0 \le i \le p, -p \le j \le p$, et en joignant les points à i constant puis à j constant. Cette surface est enfin projetée orthogonalement sur deux axes fixes. La position des axes mobiles a été choisie dans chaque cas de manière à permettre une bonne visualisation de la surface.</footnote>
Il apparaît ainsi que la précision intrinsèque des algorithmes (accumulation des erreurs dues au nombre limité de bits dans les registres de la machine) est parfaitement acceptable compte tenu de la précision de la machine (18 bits).
MATRICE F1
+.80000+00

MATRICE F2
+.85000+00

COVARIANCE P DE X1
+.10000+01

COVARIANCE Q DU BRUIT;
+.52723-01

DISTANCE PONDEREE
+.00000+00

DISTANCE QUADRATIQUE
+.00000+00

<figure><img src="image_3.png" /><figcaption>Figure IV.1.</figcaption></figure>
<figure><img src="image_4.png" /><figcaption>Figure IV.2.</figcaption></figure>
MATRICE
.461861.00 .577341.00
.308201.00 .823761.00

MATRICE F2
.000001.00 .100001.01
.840001.00 .786081.00

COVARIANCE P DE X1
.000081.00 .400011.00
.400011.00 .840001.00

COVARIANCE Q OU BRUIT
.128571.00 .518441.01
.518451.01 .820061.01

DISTANCE POND'EREE .577001.00

DISTANCE QUADRATIQUE .107841.00

<figure><img src="image_5.png" /><figcaption>Figure IV.3.</figcaption></figure>
<table><tbody><tr><td>DISTANCE</td><td>0.073108</td></tr><tr><td>DISTANCE</td><td>0.073105</td></tr></tbody></table>

<figure><img src="image_6.png" /><figcaption>Figure IV.4.</figcaption></figure>
<table><tbody><tr><td>MATRICE F1</td><td></td><td></td><td></td></tr><tr><td>+,50008+00</td><td>-,13078+00</td><td>+,63382+00</td></tr><tr><td>+,31008+00</td><td>-,45088+00</td><td>+,11338+01</td></tr><tr><td>+,50002+00</td><td>-,13088+01</td><td>+,18168+01</td></tr><tr><td>MATRICE F2</td><td></td><td></td><td></td></tr><tr><td>+,00008+00</td><td>+,10000+01</td><td>+,00000+00</td></tr><tr><td>+,00008+00</td><td>-,00008+00</td><td>+,10008+01</td></tr><tr><td>+,49007+00</td><td>-,15000+01</td><td>+,20000+01</td></tr><tr><td>COVARIANCE P DE X<sub>1</sub></td><td></td><td></td><td></td></tr><tr><td>+,30181+01</td><td>+,20222+01</td><td>+,10126+01</td></tr><tr><td>+,20222+01</td><td>+,23154+01</td><td>+,17900+01</td></tr><tr><td>+,10128+01</td><td>+,17900+01</td><td>+,17774+01</td></tr><tr><td>COVARIANCE Q DU BRUIT</td><td></td><td></td><td></td></tr><tr><td>+,50463+00</td><td>+,87945+01</td><td>-,14888+00</td></tr><tr><td>+,87800+01</td><td>+,34282+00</td><td>+,29000+00</td></tr><tr><td>-,14885+00</td><td>+,29007+00</td><td>+,36763+00</td></tr></tbody></table>

DISTANCE PONDEREE +,90258+04

DISTANCE QUADRATIQUE +,18185+03

<figure><img src="image_7.png" /><figcaption>Figure IV.5.</figcaption></figure>
# V. APPLICATION DES ALGORITHMES D'IDENTIFICATION A DES IMAGES SIMULEES

Ainsi qu'il a été déjà expliqué, l'objet de cette série d'expériences est d'étudier la sensibilité des algorithmes d'identification à des erreurs sur les valeurs $\Lambda(.,.)$.

## V. 1. Description de l'expérimentation.

Chaque expérience est composée de deux phases :

- simulation et stockage de l'image sur bande magnétique ou disque,

- estimation de la fonction $\Lambda(.,.)$ et application des algorithmes d'identification.

### V. I. I. Simulation.

On génère une image de dimensions $M \times M$ à partir des équations récurrentes :

$$ (17) \quad \left\{ \begin{array}{ll} x_{0,1} = 0 & 0 \le l \le M-1 \\ x_{k,0} = 0 & 0 \le k \le M-1 \\ x_{k,l} = F_1 x_{k-1,l} + F_2 x_{k,l-1} - F_1 F_2 x_{k-1,l-1} + L u_{k-1,l-1} & 1 \le k \le M-1 \\ & 1 \le l \le M-1 \\ y_{k,l} = H x_{k,l} & \end{array} \right. $$

où

• Les "données" $H = (1, 0\cdots0), F_1 (n \times n), F_2 (n \times n), L (n \times 1)$ sont conformes aux conditions exprimées dans le chapitre II.

• $\{u_{k,l}\}$ est obtenue par échantillonnage sur convertisseur analogique digital du signal analogique fourni par un générateur de bruit pseudo blanc.
<figure><img src="image_8.png" /></figure>

Pour assurer la "stationnarité" de l'image {$Y_{k,l}$}, ou ne garde
pour le traitement ultérieur qu'une partie de dimensions (N × N) de l'image
définie par les indices (k,l) tels que :

$$
\begin{equation} \tag{18}
\begin{aligned}
& M - N \le k \le M - 1, \\
& M - N \le 1 \le M - 1.
\end{aligned}
\end{equation}
$$

En pratique, nous avons pris M = 192, N = 128.

V. 1. 2. Identification de l'image simulée.

La fonction d'autocorrélation Λ(.,.) de l'image ainsi simulée est
estimée par :

$$
(19) \qquad \left\{
\begin{aligned}
\Lambda^{(N)}(i,j) &= \frac{1}{(N-i)(N-j)} \sum_{k=0}^{N-i-1} \sum_{l=0}^{N-j-1} Y_{k+i,l+j}^{N} Y_{k,l}^{N} \\
&\qquad \qquad \qquad \quad 0 \le i \le p \\
\Lambda^{(N)}(i,-j) &= \frac{1}{(N-i)(N-j)} \sum_{k=0}^{N-i-1} \sum_{l=j}^{N-1} Y_{k+i,l-j}^{N} Y_{k,l}^{N}
\end{aligned}
\right.
$$

Les algorithmes d'identification sont ensuite appliqués à la fonction Λ(.,.)^{(N)}.
En pratique, nous avons retenu p=10 ; ce qui semble réaliser un compromis
tenant compte de plusieurs facteurs :

* Une représentation "suffisante" de la fonction Λ(.,.).

* La dimension maximale n<sub>max</sub> = P/2 autorisée pour les algorithmes d'identification.

* Le temps d'estimation de la fonction Λ(.,.), qui varie comme (p+1) (2p+1) N².
## V. 2. Discussion et interprétation des résultats.

Etant donné le but de cette série d'expériences, il convient de préciser les sources d'erreur sur les valeurs de $\Lambda(.,.)$ que l'expérimentation décrite ci-dessus, introduit.

La simulation par les équations (17) et l'estimation de $\Lambda(.,.)$ par les équations (19) introduit diverses sources d'erreur :

i) La corrélation non identiquement nulle existant entre les échantillons $\{u_{k,l}\}$ du générateur de bruit pseudo blanc.

ii) La non stationnarité de l'image obtenue dûe aux conditions initiales de l'équation (17).

iii) Les erreurs "d'arrondis" dans les calculs matriciels très importants nécessaires pour générer l'image.

iv) L'estimation des valeurs de $\Lambda(.,.)$ par les équations (19) est aussi une source d'erreur qui ne s'annule que lorsque le nombre de points de l'image tend vers l'infini.

L'effet de ces divers facteurs s'est manifesté, dans les conditions expérimentales que nous avons définies par une dispersion dans les valeurs de $\Lambda(.,.)$ représentant quelques % de la variance $\Lambda(0,0)$.

Les résultats présentés ci-dessous pour des images simulées d'ordre 1, 2 et 3, et suivant le même format qu'au chapitre IV montrent une dégradation prévisible de la précision de l'identification, qui demeure néanmoins satisfaisante puisque les distances quadratique et pondérée définies au chapitre II, ne dépassent guère 1 %. On observe aussi que la distance pondérée est toujours inférieure à la distance quadratique, parfois même d'un ordre de grandeur.
Ceci explique en partie la pondération introduite dans le calcul "aux moindres carrés" de la matrice P covariance de "l'état", pondération qui veut tenir compte du fait que les valeurs de Λ(i,j) pour |i| et |j| élevés, sont faibles en valeur absolue et sont toujours en pratique entachées d'erreurs relatives importantes.
MATRICE F1
+ .89411+00

MATRICE F2
+ .92807+00

COVARIANCE P DE X:
+ .13125-04

COVARIANCE Q DU BRUIT:
+ .30508-06

DISTANCE POND'EREE + .55978-02

DISTANCE QUADRATIQUE + .17182-01

<figure><img src="image_9.png" /><figcaption>Figure V.1.</figcaption></figure>
MATRIZ
+ .90881
MATRIZ
+ .85250
COVARIANCE
+ .40742
COVARIANCE
+ .20185
DISTANCE
+ .21941
DISTANCE
+ .99261

<figure><img src="image_10.png" /><figcaption>Figure V.2.</figcaption></figure>
MATRICE F₁
+ .29702100 .12698100
-.14309100 .16781100

MATRICE F₂
+ .00000100 .10000100
-.25795100 -.45504100

COVARIANCE Q DE
+ .42278101 .16270102
+.76270102 .10875102

COVARIANCE Q DE BRUTT
+ .31831101 .17982102
+.79982102 .11909102

DISTANCE POUDEE .12309103

DISTANCE QUADRATIQUE .17317103

<figure><img src="image_11.png" /><figcaption>Figure V.3.</figcaption></figure>
<figure><img src="image_12.png" /><figcaption>Figure V.4.</figcaption></figure>
MATRICE F1
+ .278178+00 + .62000+00
-.13203+00 + .50821+00

MATRICE F2
+ .00000+00 + .10000+01
-.23828+00 + .51081+00

COVARIANCE P DE X₁
+ .27060+01 + .47301+02
+.47301+02 + .18262+02

COVARIANCE Q DU BRUIT
+ .21000+01 + .51945+02
+.51945+02 + .10734+02

DISTANCE PONDÉREE + .76580+03

DISTANCE QUADRATIQUE + .19629+01

<figure><img src="image_13.png" /><figcaption>Figure V.5.</figcaption></figure>
<table><tbody><tr><td>MATRICE F</td><td></td><td></td><td></td></tr><tr><td>• 2281.00</td><td>• 21791.00</td><td>• 21241.00</td></tr><tr><td>• 1001.00</td><td>• 9381.00</td><td>• 10061.01</td></tr><tr><td>• 3421.00</td><td>• 3251.01</td><td>• 15188.01</td></tr><tr><td>MATRICE F2</td><td></td><td></td><td></td></tr><tr><td>• 1001.00</td><td>• 10001.01</td><td>• 60000.00</td></tr><tr><td>• 3501.00</td><td>• 30001.00</td><td>• 10001.01</td></tr><tr><td>• 3115.01</td><td>• 3021.01</td><td>• 15249.01</td></tr></tbody></table>

<table><tbody><tr><td>COVARIANCE D1</td><td></td><td></td><td></td></tr><tr><td>• 18461.01</td><td>• 17951.01</td><td>• 17878.02</td></tr><tr><td>• 12351.01</td><td>• 14791.01</td><td>• 12551.01</td></tr><tr><td>• 72878.02</td><td>• 7551.01</td><td>• 14315.01</td></tr></tbody></table>

<table><tbody><tr><td>COVARIANCE Q D. BRUT</td><td></td><td></td><td></td></tr><tr><td>• 12431.02</td><td>• 12881.04</td><td>• 86942.03</td></tr><tr><td>• 18981.04</td><td>• 48721.03</td><td>• 74448.04</td></tr><tr><td>• 86942.03</td><td>• 74445.04</td><td>• 58511.03</td></tr></tbody></table>

DISTANCE POLYDROME .115441-02

DISTANCE POLAROTIQUE .104881-01

<figure><img src="image_14.png" /><figcaption>Figure V.6.</figcaption></figure>
Cette série d'expériences tend à montrer la représentativité de la modélisation étudiée et l'utilité pratique des algorithmes d'identification. Ainsi le "signal" $Y(i, j)$ représente la densité lumineuse au point de coordonées $(i, j)$ d'une image.

### VI. 1. Description de l'expérimentation.

Un appareil fonctionnant sur le principe du bélinographe et destiné normalement à la transmission d'images par téléphone a été adapté à l'installation du centre de calcul hybride du LABORIA [voir notice technique dans la bibliothèque du laboratoire de calcul hybride]. Les signaux fournis par cet appareil sont échantillonnés et stockés sur bande magnétique par l'intermédiaire du calculateur numérique T 2000. On obtient alors une "discrétisation" de l'intensité lumineuse lue sur l'image avec une définition de 100 ou 200 lignes par pouce et d'un sous multiple de 2400 points par ligne de 10 pouces. Ces valeurs sont exprimées en "pourcentage de blanc" avec une précision relative de l'ordre de 1%.

En pratique pour des raisons de temps de traitement et d'encombrement mémoire, on s'est limité jusqu'à présent à 128 lignes de 128 points chacune. La "taille" des images que l'on peut ainsi traiter dépend de la "définition" choisie. Pour 100 lignes par pouce et 1200 points par ligne, on obtient une image d'environ 3 cm x 3,2 cm ; pour 50 lignes par pouce et 600 points par ligne, on obtient une image 6 cm x 6,4 cm, etc...

On n'a plus alors qu'à appliquer les étapes décrites au chapitre V (estimation de la fonction d'autocorrélation, algorithmes d'identification) en ayant pris soin de "centrer" l'image, en retirant aux données lues sur la bande magnétique, leur valeur moyenne.
## VI.2. Interprétation des résultats.

Les résultats des expériences décrites ci-dessus sont présentés pour deux images d'origines différentes.

La première image est obtenue en balayant un écran à mémoire à l'aide de la sortie du générateur du bruit pseudo blanc. Il s'agit bien d'un phénomène physique aléatoire non "simulé". La seconde image est une photographie en noir et blanc d'un laboratoire d'informatique. Des parties de tailles diverses, reproduites ci-dessous avec les résultats correspondants, ont été analysées dans les deux images.

Le format des résultats est le même que pour les essais précédents. La valeur des distances quadratiques et pondérées définies au chapitre II, sont comparables, moyennant une légère dégradation, aux valeurs de ces distances dans les exemples simulés du chapitre V. On observe aussi correctivement une dégradation de la "qualité" de la commutativité des matrices $F_1$ et $F_2$, bien que la distance $δ$ "mesurant" la commutativité, introduite au chapitre II, ne dépasse pas quelques %.
<figure><img src="image_15.png" /><figcaption>Figure VI.1.</figcaption></figure>
MATRICE 1
+ .087811-02 .100000-01
+ .074811-01 .100000-01

MATRICE 2
+ .000000-00 .100000-01
+ .561071-01 .144000-00

COVARIANCE P DE
+ .526011-02 .374821-02
+ .374821-02 .205181-02

COVARIANCE Q DU BRUT
+ .115131-02 .648011-03
+ .047001-03 .194371-03

DISTANCE PONDRIEE .518131-02
DISTANCE QUADRATIQUE .547101-01

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

<figure><img src="image_17.png" /><figcaption>Figure VI.2.</figcaption></figure>
MATRICE F₁
+ .970411-00 .100000-00
+ .831781-01 .100000-00

MATRICE F₂
+ .000001-00 .100000-01
+ .879571-01 .382701-00

COVARIANCE P OF X₁
+ .500411-02 .37721-02
+ .377121-02 .213201-02

COVARIANCE Q DU BRUIT
+ .108021-02 .022241-03
+ .022241-03 .220711-03

DISTANCE PONDERÉE .623171-02
DISTANCE QUADRATIQUE .962851-01

<figure><img src="image_18.png" /><figcaption>Figure VI.3.</figcaption></figure>
<figure><img src="image_19.png" /></figure>

VI.6.

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

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

VI.5.

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

VI.7.
MATRICE F1
.116631+01 .12251+00
.154271+00 .174740+00

MATRICE F2
.000001+00 .100001+01
-.212281+00 .98011+00

COVARIANCE P DE X1
.080161-02 .558631-02
.558631-02 .387291-02

COVARIANCE Q DU BRUIT
.105291-02 .586901-03
.586901-03 .241881-03

DISTANCE PONDÉREE .816151-02

DISTANCE QUADRATIQUE .345281-01

<figure><img src="image_23.png" /><figcaption>Figure VI.5.</figcaption></figure>
MATRICE F1
+ .80373 = .00

MATRICE F2
+ .84881 = .00

COVARIANCE P DE X6
+ .12382 = .01

COVARIANCE Q DU BRUIT,
+ .87702 = .03

DISTANCE PONDEREE
+ .28846 = .01

DISTANCE QUADRATIQUE
+ .86470 = .01

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

<figure><img src="image_25.png" /><figcaption>Figure VI.6.</figcaption></figure>
MATRICE F1
+ .933081+00

MATRICE F2
+ .88081+00

COVARIANCE P DE X¹
+ .140718-01

COVARIANCE O DU BRUIT
+ .404038 03

DISTANCE PONDEREE
+ .48022-01

DISTANCE QUADRATIQUE
+ .6018-01

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

<figure><img src="image_27.png" /><figcaption>Figure VI.7.</figcaption></figure>
MATRICE 1
+ .808921-00

MATRICE F2
+ .808721-00

COVARIANCE P DE V1
+ .869951-02

COVARIANCE O DU BRUIT
+ .447108-03

DISTANCE PONDEREE
+ .441508-01

DISTANCE QUADRATIQUE
+ .797728-01

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

<figure><img src="image_29.png" /><figcaption>Figure VI.8.</figcaption></figure>
## VII. CONCLUSION

La validité en pratique d'une formalisation mathématique qui n'était pas naturelle à priori nous paraît ainsi confirmée par l'expérimentation présentée.

Quant au "caractère opérationnel" des algorithmes d'identification proprement dits, les séries d'expérimentations décrites ici sont tout-à-fait encourageantes à la lumière de l'expérience déjà acquise par le LABORIA pour appliquer des algorithmes d'identification stochastique de nature algébrique à des signaux réels, dans le cas plus simple, des suites à un indice.

Dans ce dernier cas des méthodes ont été développées [APPLEVITCH, GAGALOWICZ] permettant à partir d'une "première identification" d'optimiser les paramètres de la représentation. Si les résultats ultérieurs de filtrage et de lissage l'exigent, de telles méthodes pourraient être étendues aux images.
BIBLIOGRAPHIE

[1] J.D. APPLEVITCH. "Approximation of Discrete Linear Systems". INT. J. Control. Vol.17. N° 3. pp.565-575. (1973).

[2] S. ATTASI. "Modélisation et traitement de suites à deux indices". Thèse de Doctorat d'état, PARIS VI. A paraître.

[3] S. ATTASI. "Modèles stochastiques de suites gaussiennes à deux indices". Rapport LABORIA. N° 31. (Septembre 1973).

[4] S. ATTASI. "Modèles stochastiques de suites gaussiennes à deux indices". Rapport LABORIA. N° 56. (Février 1974).

[5] M. CLERGET. "Systèmes linéaires positifs non stationnaires". Rapport LABORIA. N° 65. (1974).

[6] P. FAURRE. "Réalisations markoviennes de processus stationnaires". Rapport LABORIA. N° 13. (Mars 1973).

[7] A. GAGALOWICZ. "Obtention du triplet (F,G,H) de systèmes multivariables". Thèse de Docteur ingénieur, PARIS SUD. (Décembre 1974).

[8] GANTMACHER. "Théorie des matrices". DUNOD.

[9] T. KAILATH. "An Innovation Approach to Least Square Estimation". (IEEE. AC). Vol.13. N° 6. pp.646-655. (1968). PART.7. Vol.18. N° 6. pp.601-607. (1973).

[10] R.E. KALMAN. "Linear Stochastic Filterng Theory. Reappraisal and Outlook. Sym or System Theory. Polytechnic Inst. of Brooklyn". (Avril 1965).