Les algorithmes de transformation

Les Algorithmes de transformations d’images

1. Qu’est qu’une transformations d’image ?

Une transformation d’image est une opération mathématique  qui permet d’agrandir, rétrécir, pivoter, incliner, tordre, anamorphoser une image

Les logiciels de traitement d’image et de traitement d’image astronomique notamment proposent des algorithmes qui permettent ces opérations. Il y a presque systématiquement plusieurs choix possibles, et selon les cas, certains conviennent mieux que d’autres.

Certains on un resultat extrêmement faible au niveau qualité de rendu mais cette faible qualité peut être recherchée volontairement afin de mettre en evidence certain particularisme

D’autres sont quasi parfaits et sont issus de procédés mathématiques très coûteux en temps machine.

Une interpolation est la recherche d’un résultat à partir d’une séquence logique

par exemple

si nous avons la suite suivante

1; 2; 3; 4; 5; ;?

on peut logiquement en déduire que le “?” sera un 6

de la même manière sur  cette série

1; 2; 3; ?; 5; 6; 7; ?; 9;

on peut encore facilement déduire que les valeurs manquantes sont 4 et 8

les images fonctionnent comme une suite de chiffres, ce que dans l’absolu elles sont : puisque chaque pixel à une valeur qui en général varie de 0 à 255

le zéro représente le noir et le 255 le blanc

les valeurs intermédiaires sont les niveaux de gris plus ou moins foncé à mesure que l’on tend vers le zéro ou le 255

sur cette image fortement grossie de 6pixel² nous avons donc 36 pixels

le but du “jeu” et d’agrandir cette image tout en essayant de préserver la définition : on ne veut pas simplement une image avec des pixels plus gros comme ceci

on va donc agrandir l’image 2 fois,  mais on va se retrouver avec des pixels manquants

l’interpolation consiste donc à “inventer” logiquement les pixels qu’on à pas… on va essayer de trouver leur valeur par une méthode logique et mathématique. C’est ce qu’on appelle un algorithme

Au final, après cette opération on devrait trouver une image  ressemblant à ceci

il s’agit la d’un cas “idéal” : dans la réalité les contrastes d’une image peuvent varier brusquement d’un endroit à l’autre rendant très problématique l’interpolation

Interpolation se produit également chaque fois que vous tournez ou déformer une image. L’exemple précédent était trompeur car il se prête idéalement bien à l’interpolation .

L’exemple suivant montre comment un détail de l’image peut être perdu assez rapidement:

Image Originale
Rotation bicubique à 45° : on note la perte de détails et apparition d’artefact (zone plus sombre)
 

ici une Rotation à 90 ° : il n’y a pas d’interpolation : l’opération se fait sans perte car aucun pixel n’a jamais à être repositionné sur la frontière entre deux pixels (et donc divisé)

 

En revanche si on procède en deux temps (2 x 45°) on enregistre des pertes : l’image bien que toujours reconnaissable devient floue

ici on a aggravé le problème en effectuant 6 interpolations en rotation de 15°
c’est toujours reconnaissable mais de plus en plus flou

Notez comment la plupart des détails sont perdus dès la première rotation, bien que l’image continue de se détériorer avec des rotations successives. Il faut donc éviter de tourner vos photos lorsque cela est possible

D’une manière quasi systématique les agrandissements d’images ont tendance à flouter cette dernière : on ne peut pas inventer ce qu’on ne voit pas et pour combler le manque, les pixels intermédiaires “reconstitués” ne font qu’ajouter une valeur intermédiaire entre ses pixels voisins mais ne rendent pas compte d’un détail qui existe peut-être mais qui est absent de la photo originelle du fait d’une résolution trop faible

2. 2 grandes familles d’interpolations

Les algorithmes d’interpolations peuvent être regroupés en deux catégories: d’adaptatif et non adaptatif. Les méthodes adaptatives varient en fonction des pixels à interpoler (bords tranchants ou texture lisse), alors que les méthodes non adaptatives traitent tous les pixels de manière égale.

Algorithmes non adaptatifs comprennent: plus proche voisin, bilinéaire, bicubique, spline, sinc, lanczos et d’autres. En fonction de leur complexité, ces algorithmes utilisent entre 0 à 256 pixels adjacents (ou plus) lors de l’interpolation. Bien sur : plus grande est l’emprise des pixels adjacents, plus long est le temps de calcul. Toute fois sur les PC modernes ce n’est plus un gros problème. Ces algorithmes peuvent être utilisés à la fois pour déformer et redimensionner une photo.

 

Plus proche voisin

C’est le système le plus rapide, le plus simple et dans presque tous les cas le moins satisfaisant

Il a parfois son utilité pour mettre en évidence des problèmes spécifiques sur une image

exemple :

on observe des ronds sombres autours des étoiles.

Pour rendre compte de la réalité objective de l’image on agrandi en utilisant “plus proche voisin” ainsi aucun dénaturage de l’image ne vient entraver ce qu’on cherche à démontrer

ici les pixels sont juste 6x plus gros. Il faut fortement éviter d’utiliser cette fonction pour autre chose qu’un agrandissement simple

merlan

pour les autres algorithmes, je vous propose de les essayer sur des images

Ci-dessous des images “test”

original original original

 

nous allons appliquer à ces images 36 rotations de 5 degrés : elle seront donc inversées puis on les inverse a 180° (cette dernière opération est sans perte)

Ici avec l’algorithme “proche voisin”

zp nnAnneaux visibles : 0 line nn picture nn

 

 

les images n’ont pratiquement plus rien a voir avec les originales c’est donc un procédé à déconseiller

Interpolation bilinéaire

L’interpolation bilinéaire, calcule la valeur issue du voisinage 2×2  pixels entourant le pixel  inconnu. Il prend alors une moyenne pondérée de ces 4 pixels pour arriver à sa valeur interpolée finale. Il en résulte des images beaucoup plus lisses qu’avec la méthode “plus proche voisin”.

graphe d'interpolation bilinéaire

Le diagramme de gauche est simplifié pour un cas où toutes les distances des pixels connus sont égales, de sorte que la valeur interpolée est tout simplement leur moyenne

voici le résultat sur nos images tests (les deux dernièrse sont agrandies 3x pour mieux rendre compte

zp blAnneaux visibles : 2 line bl picture bl

 

 

Interpolation Bicubique

cette méthode est similaire mais  va encore plus loin que la méthode bilinéaire en prenant en compte les 4×4 proche de pixels connus – pour un total de 16 pixels. Puisque ceux-ci sont à des distances différentes du pixel inconnu, les pixels plus proche sont affectés d’une pondération plus élevée dans le calcul.

graphe d'interpolation bicubique

Bicubique produit des images plus nettes que les deux méthodes précédentes, et est peut-être la combinaison idéale  temps de traitement / qualité. Pour cette raison, il est un standard dans de nombreux programmes de retouche d’image (y compris Adobe Photoshop), les pilotes d’imprimantes.

Actions sur nos images tests:

original

Anneaux visibles : 8,5

original original

c’est mieux, mais pas encore parfait

 

SPLINE & SINC

Il existe de nombreux autres interpolateurs qui prennent plus de pixels environnants en considération, et donc provoquent de gros calcul. Ces algorithmes comprennent spline et sinc, et conservent plus d’informations après une interpolation.Ils sont donc extrêmement utiles lorsque l’image nécessite plusieurs rotations / distorsions dans des étapes séparées. Cependant, pour des agrandissements en une seule étape ou rotations, ces algorithmes d’ordre supérieur sont légèrement moins performants que le bicubic alors que le temps de traitement est augmentée.

Spline 16 Pixels

7 anneaux sont visibles

Spline 36 Pixels

10 anneaux sont visibles

line spline36

picture spline36

Spline 64 Pixels

zp spline64 line spline64 picture spline64

Sinc 256 Pixels

20 anneaux sont visibles

line sinc256

picture sinc256

On retrouve même les artefacts JPG de la photo originale

les lignes ne bavent presque plus

Sinc 1024 Pixels

zp sinc1024 line sinc1024 picture sinc1024

 

les SINC 256 et 1024 sont donc, et de loin, les meilleurs algorithmes. il ne sont que très rarement disponibles dans le logiciel tant leur consommation de temps de calcul est considérable

pour le sinc 1024 songez qu’il faut calculer pour chaque pixel inconnue la valeurs de 1024 pixel  adjacents , pondéré en fonction de la distance.

Si vous avez une image couleur de 10 mega pixels, pour une simple rotation cela équivaut

10 millions * 1024 *3 (nombre de couche couleur en RVB) : 30 milliards d’opérations au minimum !

Il n’est pas rare qu’en astronomie nous pouvons avoir des centaines d’images à aligner

100 * 30 millard =  3 mille milliards d’opérations

les ordinateurs ont beau être très puissants, cela prendrait un certain temps quand même!

 

 

Comments are closed.