Question:
La rotation est-elle une opération avec perte intrinsèque (pour les angles non multiples de 90 degrés)?
Alberto
2013-08-23 19:48:30 UTC
view on stackexchange narkive permalink

La déclaration de mattdm " ce flou est largement réversible si vous faites exactement la même chose à l'envers" a soulevé la question dans mon esprit. La rotation est une transformation géométrique de l'image qui consiste en une transformation spatiale des coordonnées et une interpolation d'intensité. Si la rotation n'est pas un multiple de 90 degrés, alors l'algorithme d'interpolation joue un rôle crucial.

Dans de tels cas, si nous utilisons un algorithme d'interpolation de moyenne (par exemple, bicubique), l'opération est avec perte * . Mais pouvons-nous utiliser une approche différente (par exemple, l'interpolation du voisin le plus proche) à la place et avoir notre image tournée "sans rotation"?

(*) Ce n'est que mon sentiment (je ne peux toujours pas le supporter avec une preuve mathématique): comme on ne peut pas savoir avec certitude quel pixel a contribué à quelle valeur, on ne peut pas inverser le moyennage. Mais je ne suis pas sûr que nous ne puissions pas utiliser de méthodes probabilistes pour estimer avec précision les valeurs originales.


Bien que je ne dispose pas des compétences mathématiques requises, j'ai moi-même effectué des tests (avec gimp ), mais après anti-rotation, les images diffèrent:

Test 1

source image

Figure 1 - Image source (256x256)

NN Rotated 9,5 degrees, rotated -9,5 degrees, difference

Figure 2 - De gauche à droite: a) image tournée de 9,5 degrés dans le sens des aiguilles d'une montre; b) image tournée à nouveau de 9,5 degrés dans le sens anti-horaire; et c) différence entre les images. Pour ces opérations, j'ai utilisé l'interpolation le plus proche voisin . Les images sont réduites après les opérations pour mieux s'adapter à la mise en page de ce site Web.

bicubic Rotated 9,5 degrees, rotated -9,5 degrees, difference Figure 3 - De gauche à droite: a) image tournée de 9,5 degrés dans le sens des aiguilles d'une montre; b) image tournée à nouveau de 9,5 degrés dans le sens anti-horaire; et c) différence entre les images. Pour ces opérations, j'ai utilisé une interpolation bicubique . Les images sont réduites après les opérations pour mieux s'adapter à la mise en page de ce site Web.

Test 2

Suite à la suggestion de @ unapiedra, j'ai fait un test plus simple: faire tourner une matrice 2x2. Ce cas n'est pas intéressant car, selon l'angle, soit toutes les cellules sont tournées du même angle, soit aucune cellule n'est tournée. Autrement dit, la rotation est toujours sans perte.

J'ai donc réessayé avec une matrice 3x3 et une rotation de 30 degrés:

rotating a 3x3 matrix without scaling

Figure 4 - De gauche à droite: a) image source; b) image tournée de 30 degrés dans le sens des aiguilles d'une montre; c) image tournée de 30 degrés dans le sens inverse des aiguilles d'une montre; d) différence. Les images sont mises à l'échelle pour s'adapter à ce site Web.

Dans ce cas, les différences sont évidentes. La rotation est clairement avec pertes ... Mais que se passe-t-il si je monte à l'échelle avant la rotation?

Test 3

rotating a previously upscaled 3x3 matrix

Figure 5 - De gauche à droite: a) image source; b) image mise à l'échelle d'un facteur 6x; c) image mise à l'échelle tournée de 30 degrés dans le sens des aiguilles d'une montre; d) image tournée de 30 degrés dans le sens inverse des aiguilles d'une montre; e) image transformée réduite; et f) différence (pas de différence). Les images sont mises à l'échelle pour s'adapter à ce site Web.

Dans ce cas, je mets à l'échelle par un facteur 6x. Raisonnement pour choisir ce facteur (malheureusement incorrect comme je l'ai vu avec un contre-exemple):

Un pixel pivoté à 30 degrés a des coordonnées de bas-gauche à haut-droite: [0,0] - [0,3660 , 1,3660]. Autrement dit, le côté projeté le plus court a une longueur de 0,36 pixels. Le théorème d'échantillonnage exige que nous échantillonnions à un taux double.

Ainsi, pour échantillonner avec précision une image pivotée de 30 degrés, je dois échantillonner chaque 0,17 pixel, ce qui donne un redimensionnement x5,88 facteur; 3 x 5,88 = 17,64, donc je rééchantillonne l'image source en une image 18x18.

La question «[Les rotations de« Windows Photo Viewer »sont-elles sans perte?] (Http://photo.stackexchange.com/questions/12361/are-windows-photo-viewer-rotations-lossless)» a abordé ce sujet pour un logiciel spécifique, pour des rotations d'angles multiples de 90 degrés.
Cinq réponses:
Szabolcs
2013-08-23 23:50:35 UTC
view on stackexchange narkive permalink

La rotation d'image est une opération avec perte, mais faire pivoter une image une fois puis la faire pivoter en arrière perdra probablement très peu de détails, en particulier par rapport à la compression JPEG classique.


La rotation d'image fonctionne comme ceci mathématiquement: / p>

Une image de niveau de gris se compose de valeurs de luminance L_ (x, y) à des positions de pixel entier x, y . Tout d'abord, une fonction d'argument réel f (x, y) est construite qui reproduit les valeurs L_ (x, y) au même code x, y > positions, mais donnera également des valeurs non entières x, y . Par conséquent, il interpole entre les positions entières x, y (c'est là qu'interviennent les méthodes d'interpolation --- il y a plusieurs choix possibles pour f (x, y) ).

Puis construis une version tournée g (x, y) = f (x cos (a) - y sin (a), x sin (a) + y cos (a)) par angle a . Cette opération est mathématiquement sans perte, sans compter les erreurs d'arrondi numérique lors de l'exécution du calcul sur un ordinateur à précision finie.

Enfin, les valeurs de g (x, y) sont calculées à un entier x, y se positionne à nouveau pour créer une image.


À ce stade, vous pouvez demander: pourquoi est-ce avec perte? Ne pouvons-nous pas simplement inverser tous ces calculs pour reconstruire le L_ (x, y) non pivoté d'origine, si nous savons quelle méthode d'interpolation a été utilisée pour construire f ?

C'est théoriquement possible, mais ce n'est pas ce qui se passe lorsque vous effectuez une rotation du même angle dans le sens opposé. Au lieu d'inverser précisément les opérations de rotation d'origine, une rotation de signe opposé est effectuée en utilisant la même séquence d'opérations que la rotation initiale utilisée. L'image inversée ne sera pas exactement la même que l'original.

De plus, si les valeurs de g (x, y) ont été arrondies à une faible précision (8- bit, 0..255), la perte d'informations est encore plus grande.


De nombreuses rotations accumulées rendront effectivement l'image floue. Voici un exemple de rotation d'une image Lena de 500 x 500 pixels 30 fois de 12 degrés, ce qui équivaut à une rotation complète de 360 ​​degrés:

enter image description here


Il y a une autre raison pour laquelle les opérations de type flou seront avec perte. On pourrait penser naïvement que l'inversion mathématique d'un flou devrait nous rendre l'image originale non floue. Ceci est théoriquement vrai tant que nous travaillons avec une précision infinie. La procédure s'appelle déconvolution et elle est utilisée dans la pratique pour accentuer les images floues en raison du flou de mouvement ou des raisons optiques.

Mais il y a un problème: le flou est insensible à petits changements dans l'image source. Si vous floutez deux images similaires, vous obtenez des résultats encore plus similaires. La suppression du flou est très sensible aux petits changements: si vous supprimez deux images légèrement différentes, vous obtenez deux résultats très différents. Nous ne travaillons généralement pas en haute précision (8 bits est en fait une précision assez faible), et les erreurs d'arrondi seront amplifiées lorsque vous tentez d'inverser un flou.

C'est la raison pour laquelle le flou est "irréversible" et pourquoi il perd des détails.

pourquoi parlez-vous de flou?
@Michael C'est un point important de la raison pour laquelle ces types d'opérations ne sont pas réversibles, même si mathématiquement, ils semblent réversibles. Ce que je veux dire, c'est qu'il ne s'agit pas seulement de l'existence d'erreurs d'arrondi, mais de ces erreurs qui s'amplifient souvent lorsque l'on tente d'inverser les opérations.
C'est également dû au fait que la taille de l'image est finie et que des données importantes sont perdues (dans le cas de la convolution)
"Au lieu d'inverser précisément les opérations de rotation d'origine, une rotation de signe opposé est effectuée en utilisant la même séquence d'opérations que la rotation initiale utilisée" - Je pense que c'est la réponse que je cherchais. Je n'accepte pas encore votre réponse car je joue à des maths (en essayant de trouver un facteur d'échelle comme je l'ai mentionné dans d'autres commentaires).
J'abandonne le raisonnement mathématique car je n'arrive nulle part. J'accepte votre réponse car c'est la plus détaillée et la plus convaincante.
Unapiedra
2013-08-23 20:38:47 UTC
view on stackexchange narkive permalink

La rotation n'est pas avec perte dans un contexte général, mais en combinaison avec des images, elle l'est.

La raison est le regroupement des valeurs de pixels. Si une image est tournée, l'emplacement de la plupart des pixels ne correspondra pas parfaitement à la structure de grille de l'image. L'interpolation est maintenant nécessaire pour décider où placer la valeur de ce pixel.

Dans l'interpolation du voisin le plus proche, la valeur du pixel est déplacée vers la cellule de la grille la plus proche (emplacement du pixel).

Dans l'interpolation bicubique, la valeur du pixel a un effet sur toutes les cellules de la grille proches dans le voisinage, essentiellement la valeur est distribuée aux pixels proches.

Bon point que la rotation n'est pas en soi avec perte, mais la rotation d'une orientation de grille de pixels vers une autre l'est. Alors que la plupart vont probablement en déduire cela à partir de la question, cela vaut la peine d'être souligné.
Êtes-vous en train de dire que la plupart ne liront pas la première phrase? "... mais en combinaison avec des images, c'est [avec perte]".
La réponse plus détaillée de szabolscs sera probablement acceptée et est un peu plus précise.
La perte réelle de données ne se produit qu'une fois que vous avez re-pixellisé l'image pivotée. Si votre logiciel de retouche d'image stocké un travail intermédiaire en interne en tant qu'image et valeur de rotation, mais uniquement pixellisé pour l'afficher à l'écran ou lorsqu'il est explicitement enregistré dans un format basé sur bitmap, vous pouvez alors donner une deuxième rotation de même ampleur mais annuler la rotation sans perte. (Attention, je ne sais pas comment les projets Photoshop / GIMP / etc stockent vos données.)
@Unapiedra - non, je vous donnais un +1 pour l'avoir signalé.
@AJHenderson ah désolé d'être grincheux
@DanNeely, c'est bien sûr ainsi que Lightroom le fait. L'ancien GIMP le stocke rastérisé. Sur le nouveau GIMP avec le moteur GEGL, il est peut-être possible de le faire.
Merci pour votre réponse. Cette moyenne distribuera les valeurs d'intensité, était pour moi clair. C'est pourquoi j'ai pensé qu'une opération sans perte impliquerait nécessairement une stratégie d'interpolation sans moyenne. En ce qui concerne le binning, mon intuition me dit encore qu'une mise à l'échelle appropriée devrait aider.
AJ Henderson
2013-08-23 20:14:24 UTC
view on stackexchange narkive permalink

Si vous augmentez suffisamment la résolution, je pense que vous devriez pouvoir la rendre sans perte, mais je pense qu'elle devrait être un peu plus grande. Vous auriez effectivement besoin de "remplir" suffisamment de pixels pour que l'erreur soit réduite à l'erreur d'arrondi consistant à inverser l'opération et à ramener la résolution à l'original. À ce stade, cependant, vous pouvez tout aussi bien stocker l'image d'origine dans un calque caché de l'image car vous ajoutez beaucoup plus de points de données qu'une copie de l'image n'en prendrait.

Donc, en pratique, cela doit être avec perte car il fait la moyenne des valeurs pour créer de nouveaux points et nécessiterait généralement plus de stockage supplémentaire pour une mise à l'échelle suffisante qu'il n'en faudrait pour simplement stocker une autre copie.

Votre idée est correcte mais ne peut fonctionner que pour un nombre fini de rotations possibles. Imaginez que vous définissez votre résolution intermédiaire pour obtenir une rotation sans perte de 3,22 degrés. Maintenant, faites une rotation de 3,23, votre résultat afficherait des pertes. Ceci est valable en général car il y a une infinité de rotations mais toujours un nombre fini de pixels.
@Unapiedra - ouais, honnêtement, il m'est venu à l'esprit qu'il devrait probablement être possible de conserver les informations dans au moins certains cas supplémentaires en augmentant la résolution, puis en la diminuant après la rotation, mais de toute façon, car cela n'est pas pratique en raison de la quantité de informations supplémentaires qui auraient besoin d'être stockées, je ne me suis pas donné la peine d'aller plus loin avec une preuve, car il n'y aurait aucune raison, en termes pratiques, de le faire plutôt que de stocker l'image non tournée en plus de l'image pivotée.
"Si vous augmentez suffisamment la résolution [...]" - C'est exactement mon intuition: il devrait être possible de trouver un facteur de zoom pour un angle donné qui nous permette un fonctionnement "rotation et anti-rotation" sans perte. Mais comment calculer ce facteur? Je suis entièrement d'accord avec l'observation: `` il n'y aurait aucune raison ... '', mais j'étudie maintenant ce sujet et cette question est plus théorique (selon `` dans les applications médicales, serait-il possible de faire une rotation sans perte une image pour la transformer davantage blahblah ')
Mon intuition me dit que je pourrais avoir une rotation sans perte si je rééchantillonne l'image source avec une résolution de deux fois ([théorème d'échantillonnage] (http://en.wikipedia.org/wiki/Nyquist%E2%80%93Shannon_sampling_theorem) ) la plus courte de la projection des bords des pixels. Par exemple, pour la rotation de 9,5 ° de la question, un pixel pivoté avec des coordonnées de haut à gauche en bas à droite [0,0] - [1,1] aurait les coordonnées [0,0] - [0,82,1,15 ]. Autrement dit, la projection de bord le plus court a une longueur de 0,82 pixels. Un rééchantillonnage tous les 0,41 pixel devrait suffire. Autrement dit, un zoom d'un facteur x2,43 ferait l'affaire.
Malheureusement, je l'ai testé dans GIMP et bien que j'aie obtenu de meilleurs résultats, l'opération n'est toujours pas sans perte :-(
@Unapiedra "Votre idée est correcte" ... Dans quels termes? D'après votre commentaire, je comprends qu'il est possible de calculer une résolution intermédiaire pratique basée sur l'angle de rotation? J'ai essayé, mais comme dans le commentaire précédent avoué, en vain.
@Alberto Je vous suggère d'essayer avec une image de 2x2 pixels et un angle impair (15,3 °) et une mise à l'échelle jusqu'à ce que vous trouviez une solution. Vous pouvez aussi le résoudre théoriquement (je pense) mais je n'ai pas le temps.
@Unapiedra Bonne suggestion. Je l'ai testé (en utilisant l'interpolation NN), mais l'opération est toujours sans perte. Soit toutes les cellules sont tournées, soit si l'angle est trop petit, aucune cellule n'est tournée du tout. Il n'y a pas de rotation qui ne peut modifier que quelques cellules. Cela renforce mon intuition qu'il doit y avoir une caractérisation des rotations sans perte associées à un facteur d'échelle ... Peut-être que les rotations sans perte ne sont possibles que pour certains angles?
Je suggère de demander sur math.stackexchange.com.
Michael Nielsen
2013-08-23 22:47:33 UTC
view on stackexchange narkive permalink

La théorie d'AJ sur l'augmentation de la résolution est correcte. Le problème est la taille relative des cellules (pixels) par rapport aux détails que nous pouvons distinguer. Plus les cellules sont grandes, plus nous devons pousser les résultats dans les bacs. Ici, je tourne avec une interpolation bicubique avec +10 et -10 et je compare avec abs (I1-I2). Deuxièmement, je redimensionne les lanczos x10, je fais pivoter avec une interpolation bicubique avec +10 et -10 et je redimensionne à la taille d'origine, et je compare avec abs (I1-I2).

Resize effect

Une différence significative dans la distribution des erreurs:

Stats

Donc deux questions: 1) est-il possible pour un angle de rotation donné de calculer un facteur de redimensionnement? et 2) l'interpolation ne va-t-elle pas introduire des erreurs, autrement dit, ne serait-il pas préférable de redimensionner et de faire pivoter avec le voisin le plus proche?
NN est le pire pour appliquer plusieurs transformations.
Throwback1986
2013-08-24 01:02:18 UTC
view on stackexchange narkive permalink

La rotation vers des angles "non cardinaux" sera toujours avec perte en raison de la précision finie des nombres à virgule flottante (et des méthodes) utilisées pour effectuer la rotation.

Notez que "avec perte" ne le fait pas équivaut toujours à "sensiblement avec perte".

* "Notez que" avec perte "ne signifie pas toujours" avec perte notable "." * Et nous sommes revenus à mon point d'origine - la rotation d'une image perd des informations, mais généralement pas assez pour être perceptible.


Ce Q&R a été automatiquement traduit de la langue anglaise.Le contenu original est disponible sur stackexchange, que nous remercions pour la licence cc by-sa 3.0 sous laquelle il est distribué.
Loading...