2. Solutions nlog(n)
Les deux méthodes choisies permettent d’alléger
considérablement les calculs et l’espace de mémoire occupé.
Avant d’entrer dans les détails de chaque méthode nous présentons si dessous le problème des bords, c’est à dire le rajout de suppositions sur l’image en dehors de ses bords. Ceci permettra de construire une matrice de convolution à partir d’une matrice de Réponse Impulsionnelle (RI). On donne comme préambule l’exemple à une seule dimension.
Soit un signal d’entrée x
convolué avec le bruit h qui donne un signal y réceptionné :
Le problème de déconvolution
est de retrouver le vecteur x=[x1,…,xn]t
en se donnant un vecteur de bruit ou de RI {système entrée-sortie}, mais qui
aura une dimension finie. Le problème mis sous forme matricielle est le
suivant :
Le problème ainsi posé n’a
pas de solution. Pour le résoudre nous devons faire certaines hypothèses sur xl=[x-m+1,…,x0]t
et xr=[xn+1,…,xn+m]t
pour réduire le nombre d’inconnues.
On peut décomposer notre
matrice comme suit :
D’après les hypothèses qui seront faites, nous aurons une certaine
combinaison linéaire de ces trois matrices.
Pour le cas 2D, la convolution entre l’image originale et la RI ne peut
être calculée que sur un nombre de pixels inférieur aux nombres de pixels de
l’image originale.
La
Figure 2.1 illustre une convolution. Les valeurs calculables, c’est à dire
l’image floue, sont représentées en vert. La Réponse (RI) est modélisée par le
grand carré en haut à gauche.
N’ayant pour reconstruire l’image que l’image floue (partie verte) et
la RI, il est nécessaire de faire des hypothèses sur les bords excédents de
l’image, c’est à dire la partie orange sur la figure 21.
Figure
2.1: Schématisation d’une convolution 2D.
Pour
la mise en forme matricielle du problème dans ce cas, nous construisons les
vecteurs x et y par balayage lexicographique [1] {soit ligne par
ligne, de gauche à droite et de haut en bas} et nous obtiendrons une matrice de
convolution H construite à partir des valeurs de la RI et qui
aura une forme donnée d’après les suppositions que nous ferons sur les bords.