Theorie

2.1 Interpolation : généralités

2.2 Interpolation Shannon-Nyquist

2.2.1 Définition d'un signal discret

2.2.2 Signal à bande limitée et fréquence de Nyquist

2.2.3 Théorème de Shannon-Nyquist

2.3 Interpolation Spline

2.3.1 Definition

2.3.1 Exemple 1

2.3.1 Exemple 2

2.3.2 Interpolation avec des splines

2.3.3 Applications

2.4 Convolution

 

2.1 Interpolation : généralités

Afin de ne pas sombrer dans la complexité on se ramène à l’étude d’un signal unidimensionnel.

On définit le problème d’interpolation de la façon suivante :

Soient les points (couramment appelés échantillons) :

Il faut trouver une fonction (si possible : simple et lisse) avec :

 

Dans le cas bidimensionnel on doit trouver une fonction pour les points  de tel façon à ce que :

Il va de soi que l’interpolation dans le cas bi-dimensionnel est beaucoup plus difficile que celle du cas uni-dimensionnel. On utilise le plus souvent des fonctions sinusoïdales ou polynomiales comme fonctions d’interpolation.

2.2 Interpolation Shannon-Nyquist

Comme on l’avait déjà remarqué, une image est constituée de pixels, elle est donc discrète et non continue, comme les ondes qui touchent notre rétine. Mais pour pouvoir donner appliquer des procédés mathématiques à l’image il nous faut définir ce qu’est le signal discret.

 

2.2.1 Définition d’un signal discret

Un signal discret est un signal dont la variable indépendante appartient à Z.On note souvent un signal discret sous la forme . Une telle séquence de nombres provient d’un échantillonnage d’un signal continu , par une lecture de sa valeur à des intervalles de temps réguliers :

 

L’intervalle de temps  séparant deux mesures successives est appelé période d’échantillonnage, tandis que son inverse  est nommé fréquence d’échantillonnage. On associe canoniquement au signal discret  le signal dit signal à temps discret ou échantillonné, défini par :

 

2.2.2 Signal à bande limitée et fréquence de Nyquist

On dit qu’un signal continu x est à bande limitée sur [-B, B] si le support de sa transformée de Fourier est inclus dans [-B,B]. c’est-à-dire :

 

Pour se représenter intuitivement cette notion, on peut dire d’un tel signal qu’il ne comporte pas de détails de finesse inférieure à 1/B. Pour chaque signal continu x, on appelle fréquence de Nyquist (lorsqu’elle existe), la plus petite fréquence  telle que x soit à bande limitée sur .

Nous verrons pourquoi ce facteur de 2 apparaît lors de l’énoncé du théorème de Shannon-Nyquist.

Remarque : il est inutile de préciser que le niveau de détails perçus par l’œil est nettement supérieur à celui de l’oreille. L’œil est non seulement capable de capter des différences à une échelle de micromètres mais peut aussi distinguer entre des dizaines de milliers de nuances de couleurs. 

2.2.3 Théorème de Shannon-Nyquist

Soit x(t) un signal continu à bande limitée et fréquence de Nyquist . Alors un échantillonnage de x à la fréquence permet la reconstruction complète du signal  à condition que

Ce théorème permet donc de voir la fréquence de Nyquist d’un signal comme la fréquence minimale d’échantillonnage qui n’engendre aucune perte d’information.

Nous admettrons ce théorème dont la démonstration dépasserait le cadre de cet exposé.

On échantillonne cependant généralement avec une fréquence de 2,3 fois plus élevée que l’étendu de la fréquence du signal original. L’exemple classique est celui de l’échantillonnage du son qui se fait sur 44100Hz car l’être humain n’entend que des sons entre 20 et 20000Hz. Ainsi la plus grande partie des bandes musicales ont une fréquence de 44,1kHz ce qui permet, selon le théorème de Shannon-Nyquist, une reconstruction parfaite du son d’origine.

Mais revenons au zoom numérique. En agrandissant une image on diminue le taux d’échantillons de l’image. En effet, par rapport au nombre total de pixels de l’image on a moins de pixels originaux (donc d’échantilllons), puisqu’on insère de plus en plus de pixels interpolés. Avec un agrandissement de plus en plus fort il devient donc de plus en plus difficile de reconstruire l’image, car on s’éloigne de la fréquence de Nyquist.

S’y ajoutent encore deux autres contraintes : en tant qu’être humain, on compare inconsciemment l’image obtenue par zoom numérique avec l’idée de cette même image obtenue par zoom optique, qui quant à elle contient plus de détails. Il semble bizarre qu’un objet rapproché par zoom numérique ne montre pas plus de détails. Prenons l’exemple d’une porte qui se trouve dans le coin d’une image. Si dans la photo originale on ne voyait pas la poignée, on ne la verra pas non plus dans l’image agrandie, peu importe l’interpolation et le lissage !

Pire encore, l’œil humain est capable de distinguer autour de 1200dots/inch² (environ 858points/cm²). Et souvent on est loin d’avoir une telle résolution dans les photos digitales. Donc déjà à l’origine l’image n’est pas perçue de façon claire et nette par l’être humain. En zoomant cet effet s’aggrave.

Il s’ensuit qu’on est - faute de résolution (ou taux d’échantillonnage) - loin d’une reconstruction parfaite de l’image d’origine. Il est donc essentiel de trouver des fonctions d’interpolation particulièrement ingénieuses.

 

2.3 Interpolation Spline

 

De tous les procédés d’interpolation, l’interpolation par fonctions splines est le plus répandu. Nous allons y jeter un coup d’œil.

Les splines sont des fonctions s(x) définis sur un intervalle [a, b] dérivables et polynomiales par parties. Un spline se compose en une série de fonctions polynômes sur les intervalles , tout en maintenant la propriété d’être k-fois continûment dérivable sur l’intégralité de l’intervalle [a, b]. Le paramètre k est défini à l’avance et permet d’obtenir des transitions plus ou moins lisses entre deux intervalles.

2.3.1 Définition

 

Un spline de degré r avec son ensemble de points d’appui  (nos fameux échantillons), est une fonction définie sur l’intervalle [a, b] ayant les propriétés suivantes :

1.) s(x) est un polynôme de degré  sur chacun des intervalles

2.) s(x) est (r-1)-fois continûment dérivable sur [a, b]. (Dans le cas de r=1 on considère seulement que s(x) est continue)

On note l’ensemble de tous les splines de degré r et d’ensemble de points d’appui .

Notons qu’on rencontre le plus souvent des splines d’ordre r=1 ou r=3.

---

Exemple 1 : spline d’ordre 1

 

: s(x) est continu

 

Les polynômes sont donc des fonctions linéaires, le spline est donc composé de droites :

Puisque s(x) doit être continu, la fonction suivante n’est pas un élément de :

---

Exemple 2 : spline d’ordre 2

: s(x) est une fois continûment dérivable

Le spline est alors composé de fonctions paraboliques :

 

 

2.3.2 Interpolation avec des splines

Comment est-ce qu’on procède pour l’interpolation spline ? Examinons le problème suivant :

Soient les n+1 points :

Trouvons la fonction :

 avec

 

Cas  r = 1 :

s(x) étant une fonction linéaire  par parties, il nous suffit de trouver et pour tous les

L’équation d’une droite passant par les points  et  est :

En transformant nous obtenons pour  et :

Il va de soi que s(x_i) = y_i  (il suffit de jeter un coup d’œil sur le calcul fait auparavant ou de regarder le graphe pour s’en rendre compte) et ainsi s(x) est continue.

2.3.3 Applications

Comment applique-t-on cette théorie ? Il est intéressant de remarquer que dans le cas uni-dimensionnel on peut résoudre l’étude des polynômes à une combinaison linéaire des échantillons voisins. Dans le cas d’un signal échantillonné bi-dimensionnel (une image) on étudie donc l’entourage d’un pixel (les 8 ou plus pixels autours).

 Très concrètement, pour un pixel interpolé de l’image zoomé on doit donc déterminer son intervalle (ou dans d’autres termes : « où est-ce que ce pixel se trouverait dans l’image originale ? »). Le calcul est simple:

 

 

Coordonnées du pixel de l’image originale sont donc:

Ensuite on regarde le pixel d’entrée et on prend en compte l’entourage de celui-ci afin de calculer la valeur pour le pixel de sortie (on calcule en fait la valeur du polynôme en ce point, comme on l’a fait avec les moments pour le signal uni-dimensionel). Puisqu’on procède de la même façon pour tous les pixels cela revient à déplacer une sorte de fenêtre sur l’image originale. Ce procédé est appelé la convolution.

On remarque que plus le polynôme sera important, plus la fenêtre sera grande et ainsi plus le lissage sera important (mais aussi plus forte sera la diminution du contraste). Il existe des fonctions qui prennent en compte tous les pixels de l’image, cependant elles ne sont pas polynomiales mais de nature sinusoïdale. 

Autre remarque : on peut aussi bien exécuter ce traitement sur la transformée de Fourier de l’image. On mettra ainsi l’aspect sur la différence de fréquence entre les pixels (et donc sur le contraste). En général cela aboutit à des résultats meilleurs.

Examinons donc la convolution.

2.4 Convolution

Pour interpoler sur une image discrète on utilisera le procédé de la convolution. La convolution est une simple opération mathématique qui est fondamentale dans le traitement d’images. La convolution nous permet de multiplier deux matrices, souvent de tailles différentes, mais de même dimension (en général des matrices à deux dimensions) afin de produire une troisième matrice de même dimension. Ce procédé peut être utilisé dans le but d’implémenter des opérateurs qui calculent la valeur d’un pixel de l’image résultante par combinaison linéaire des valeurs des pixels de l’image d’origine.

Dans le contexte du traitement d’image une des deux matrices est en général une image en gris. La deuxième matrice est en générale beaucoup plus petite (en général de 1 à 16 pixels) et on la nomme le corps.

Prenons un exemple :