Transformée de quantification moyenne successive optimisée

L'algorithme de transformation de quantification moyenne successive (SMQT) est une transformation non linéaire qui révèle l'organisation ou la structure des données et supprime des propriétés telles que le gain et le biais. Dans un article intitulé The Successive Mean Quantization Transform, SMQT est "appliqué au traitement de la parole et au traitement des images". L'algorithme, lorsqu'il est appliqué aux images, "peut être considéré comme une focalisation progressive sur les détails d'une image".

Selon un autre article intitulé SMQT-based Tone Mapping Operators for High Dynamic Range Images, il produira une « image avec des détails améliorés ». L'article décrit deux techniques d'application de cette transformation à une image.

1. Appliquer SMQT sur la luminance de chaque pixel - il décrit la formule pour obtenir la luminance à partir du RVB de chaque pixel.

2. Appliquez SMQT sur chaque canal de RVB séparément - pour les canaux R, G et B individuellement.

L'image suivante montre le résultat des deux techniques :

En appliquant la deuxième technique à une photo du Bruin Theatre de nuit, on voit comment l'algorithme zoome progressivement sur les détails de l'image et révèle des détails originellement cachés par l'obscurité :

Dans cet article, nous examinerons de plus près le fonctionnement de cet algorithme et explorerons une optimisation simple qui permet à l'algorithme d'être beaucoup plus performant dans les applications pratiques de traitement d'image.

L'algorithme SMQT

Dans l'article original, l'algorithme est décrit de manière abstraite. Pour mieux comprendre SMQT, nous allons parcourir quelques exemples simples.

Supposons que nous ayons le vecteur suivant (vous pouvez le considérer comme un tableau) :

Dans le cas d'une image couleur, nous pouvons la considérer comme trois vecteurs distincts, chacun représentant un canal de couleur particulier (RVB), et chaque élément du vecteur représentant l'intensité du pixel correspondant.

Les étapes impliquées dans l'application de l'algorithme SMQT sont :

1. Calculez la moyenne du vecteur, qui dans ce cas est 29,58.

2. Divisez le vecteur en deux, en laissant les nombres inférieurs ou égaux à 29,58 dans la moitié gauche et les nombres supérieurs dans la moitié droite :

   15	4	0	5	18	32	48	60	64	59	47	31
   0	0	0	0	0	1	1	1	1	1	1	1

   La deuxième ligne est le code que nous allons créer pour chaque valeur. Les valeurs inférieures ou égales à 29,58 obtiennent un 0 dans son code, et les nombres supérieurs à 29,58 obtiennent un 1 (c'est binaire).

3. Maintenant, les deux vecteurs résultants sont séparés individuellement, de manière récursive, en suivant la même règle. Dans notre exemple, la moyenne du premier vecteur est (15 + 4 + 0 + 5 + 18) / 5 = 8,4, et la moyenne du deuxième vecteur est (32 + 48 + 60 + 64 + 59 + 47 + 31) / 7 = 48,7. Chacun de ces deux vecteurs est ensuite divisé en deux vecteurs supplémentaires, et un deuxième bit de code est ajouté à chacun en fonction de sa comparaison avec la moyenne. Voici le résultat :

   4	0	5	15	18	32	47	31	48	60	64	59
   00	00	00	01	01	dix	dix	dix	11	11	11	11

   Notez qu'un 0 a été à nouveau ajouté pour les nombres inférieurs ou égaux à la moyenne (pour chaque vecteur) et un 1 pour les nombres supérieurs à la moyenne.

4. Cet algorithme est répété récursivement :

   0	4	5	15	18	32	31	47	48	60	64	59
   000	001	001	010	011	100	100	101	110	111	111	111

   0	4	5	15	18	31	32	47	48	60	59	64
   0000	0010	0011	0100	0110	1000	1001	1010	1100	1110	1110	1111

   0	4	5	15	18	31	32	47	48	59	60	64
   00000	00100	00110	01000	01100	10000	10010	10100	11000	11100	11101	11110

   À ce stade, chaque vecteur n'a qu'un seul élément. Ainsi, pour chaque étape successive, un 0 sera ajouté, car le nombre sera toujours égal à lui-même (la condition pour un 0 est que le nombre doit être inférieur ou égal à la moyenne, qui est lui-même).

Jusqu'à présent, nous avons un niveau de quantification de L=5. Si nous devions utiliser L=8, nous devions ajouter trois 0 à chaque code. Le résultat de la conversion de chaque code de binaire en entier (pour L=8) serait :

Le vecteur final est trié par ordre croissant. Pour obtenir le vecteur de sortie, nous devons remplacer la valeur d'origine du vecteur d'entrée par son code.

Notez que dans le vecteur résultant :

• Le gain a été supprimé. L'original avait un faible gain, avec sa plage allant de 0 à 64. Maintenant, son gain va de 0 à 240, soit presque toute la plage 8 bits. On dit que le gain est supprimé car peu importe si nous multiplions tous les éléments du vecteur d'origine par un nombre, tel que 2, ou si nous divisons tous par 2, le vecteur de sortie serait à peu près le même. Sa plage serait d'environ toute la plage du vecteur de destination (8 bits pour L=8). Si nous multiplions le vecteur d'entrée par deux, le vecteur de sortie sera en fait le même, car à chaque étape, les mêmes nombres qui étaient en dessous ou au-dessus de la moyenne continueront d'être en dessous ou au-dessus, et nous ajouterons les mêmes 0 ou 1 à la sortie. Ce n'est que si nous le divisons que le résultat serait à peu près le même, et pas exactement le même, car les nombres impairs comme 15 devront être arrondis et les calculs peuvent alors varier. Nous sommes passés d'une image sombre à une image avec ses pixels allant des couleurs sombres (0) aux couleurs plus claires (240), en utilisant toute la gamme.
• Le biais est supprimé, même si nous ne pouvons pas tout à fait l'observer dans cet exemple. C'est parce que nous n'avons pas de biais puisque notre valeur la plus basse est 0. Si nous avions réellement un biais, il aurait été supprimé. Si nous prenons n'importe quel nombre 'K' et l'ajoutons à chaque élément du vecteur d'entrée, le calcul des nombres au-dessus et au-dessous de la moyenne à chaque étape ne variera pas. La sortie sera toujours la même. Cela rendrait également les images trop lumineuses pour devenir des images allant des couleurs sombres aux couleurs claires.
• Nous avons une image avec des détails améliorés. Notez comment, pour chaque étape récursive que nous prenons, nous zoomons sur les détails et construisons la sortie en révélant ces détails autant que possible. Et puisque nous appliquerons cette technique à chaque canal RVB, nous révélerons autant de détails que possible, tout en perdant des informations sur les tons d'origine de chaque couleur.

Étant donné une image comme un vecteur de pixels RVB, chaque point étant de 8 bits pour R, 8 pour G et 8 pour B ; nous pouvons en extraire trois vecteurs, un pour chaque couleur, et appliquer l'algorithme à chaque vecteur. Ensuite, nous formons à nouveau le vecteur RVB à partir de ces trois vecteurs de sortie et nous avons l'image traitée SMQT, comme cela a été fait avec celle du Bruin Theatre.

Complexité

L'algorithme exige que pour chaque niveau de quantification (L), N éléments doivent être inspectés dans un premier passage pour trouver la moyenne de chaque vecteur, puis dans un second passage, chacun de ces N éléments doit être comparé à la moyenne correspondante dans afin de diviser chaque vecteur à tour de rôle. Enfin, les éléments N doivent être remplacés par leurs codes. La complexité de l'algorithme est donc O((L*2*N) + N) = O((2*L + 1)*N), soit O(L*N).

Le graphe extrait de l'article est cohérent avec la complexité O(L*N). Plus le L est faible, plus le traitement est rapide de manière approximativement linéaire (plus grand nombre d'images par seconde). Afin d'améliorer la vitesse de traitement, l'article suggère d'abaisser les valeurs de L : "sélectionner un niveau L inférieur peut être un moyen direct de réduire la vitesse de traitement mais avec une qualité d'image réduite".

Amélioration

Ici, nous trouverons un moyen d'améliorer la vitesse sans réduire la qualité de l'image. nous analyserons le processus de transformation et trouverons un algorithme plus rapide. Afin d'avoir une perspective plus complète à ce sujet, voyons un exemple avec des nombres répétés :

Les vecteurs ne peuvent plus être divisés et des zéros doivent être ajoutés jusqu'à ce que nous arrivions au L souhaité.

Pour simplifier, supposons que l'entrée puisse aller de 0 à 31, et la sortie de 0 à 7 (L=3), comme on peut le voir dans l'exemple.

Notez que le calcul de la moyenne du premier vecteur (16 + 25 + 31 + 31 + 25 + 16 + 7 + 1 + 1 + 7) / 10 = 16 donne le même résultat que le calcul de la moyenne du dernier vecteur entier, puisqu'il est juste le même vecteur avec les éléments dans un ordre différent : (1 + 1 + 7 + 7 + 16 + 16 + 25 + 25 + 31 + 31) / 10 = 16.

Dans la deuxième étape, nous devons calculer chaque vecteur de manière récursive. Nous calculons donc la moyenne des entrées grisées, qui sont les 6 premiers éléments ((16 + 16 + 7 + 1 + 1 + 7) / 6 = 8), et la moyenne des entrées vides, qui sont les 4 derniers éléments ((25 + 31 + 31 + 25) / 4 = 28) :

Remarquons encore que si on utilise le dernier vecteur, celui qui est complètement ordonné, les résultats sont les mêmes. Pour les 6 premiers éléments on a : ((1 + 1 + 7 + 7 + 16 + 16) / 6 = 8), et pour les 4 derniers éléments : ((25 + 25 + 31 + 31) / 4 = 28) . Puisqu'il ne s'agit que d'un ajout, l'ordre des sommations n'a pas d'importance.

Idem pour l'étape suivante :

Les calculs sont les mêmes qu'avec le dernier vecteur : ((7 + 1 + 1 + 7) / 4 = 4) sera égal à ((1 + 1 + 7 + 7) / 4 = 4).

Et il en sera de même pour le reste des vecteurs et des étapes.

Le calcul de la moyenne est simplement la somme des valeurs des éléments de l'intervalle, divisée par le nombre d'éléments de l'intervalle. Cela signifie que nous pouvons précalculer toutes ces valeurs et éviter de répéter ce calcul L fois.

Voyons les étapes pour appliquer ce que nous appellerons l'algorithme FastSMQT à notre exemple :

1. Créez un tableau avec 32 colonnes et 3 lignes comme vous pouvez le voir ci-dessous. La première ligne du tableau représente l'index du tableau (0 à 31) et n'a pas besoin d'être inclus lors du codage du tableau. Mais il est explicitement montré pour rendre l'exemple plus facile à suivre.

2. Itérez les N éléments une fois en comptant la fréquence de chaque valeur. Dans notre exemple, les éléments 1, 7, 16, 25 et 31 ont tous une fréquence de 2. Tous les autres éléments ont une fréquence de 0. Cette étape a une complexité de O(N).

3. Maintenant que le vecteur de fréquence est rempli, nous devons itérer ce vecteur (le vecteur de fréquences, pas le vecteur d'entrée). On n'itère plus N éléments, mais R (R étant compris dans l'intervalle : 2^L), qui dans ce cas vaut 32 (0 à 31). Lors du traitement des pixels, N peut représenter plusieurs millions (mégapixels), mais R est généralement égal à 256 (un vecteur pour chaque couleur). Dans notre exemple, c'est 32. nous remplirons les deux lignes suivantes du tableau en même temps. La première de ces lignes (la seconde du tableau) aura la somme des fréquences jusqu'à présent. Le second (le troisième du tableau) aura la somme de la valeur de tous les éléments qui sont apparus jusqu'à présent.

   Dans notre exemple, lorsque nous arrivons à 1, nous mettons un 2 dans la deuxième ligne du tableau car deux 1 sont apparus jusqu'à présent. Et nous mettons également un 2 dans la troisième ligne du tableau, car 1 + 1 = 2. Nous continuons à écrire ces deux valeurs sur chacune des positions suivantes jusqu'à ce que nous arrivions à 7. Puisque le numéro 7 apparaît deux fois, nous ajoutons 2 au accumulateur de la deuxième ligne, car maintenant 4 numéros sont apparus jusqu'à présent (1, 1, 7, 7). Et nous ajoutons 7 + 7 = 14 à la troisième ligne, ce qui donne 2 + 14 = 16, car 1 + 1 + 7 + 7 = 16. Nous continuons avec cet algorithme jusqu'à ce que nous ayons fini d'itérer ces éléments. La complexité de cette étape est O(2^L), qui dans notre cas est O(32), et lorsque vous travaillez avec des pixels RVB, c'est O(256).

   je	0	1	2	...	6	7	8	...	15	16	17	...	24	25	26	...	30	31
   n	0	2	0	...	0	2	0	...	0	2	0	...	0	2	0	...	0	2
   n-cumulatif	0	2	2	...	2	4	4	...	4	6	6	...	6	8	8	...	8	dix
   somme	0	2	2	...	2	16	16	...	16	48	48	...	48	98	98	...	98	160

4. L'étape suivante consiste à supprimer du tableau les colonnes avec des éléments qui ont une fréquence de 0, et pour voir l'exemple plus clair, nous supprimerons également la deuxième ligne car elle n'est plus pertinente, comme vous le verrez.

   je	1	7	16	25	31
   n	2	4	6	8	dix
   somme	2	16	48	98	160

5. Rappelez-vous que nous pourrions utiliser le dernier vecteur (complètement ordonné) pour effectuer les calculs pour chaque étape et les résultats seront toujours les mêmes. Notez qu'ici, dans ce tableau, nous avons le dernier vecteur avec tous les pré-calculs déjà effectués.

   Nous devons essentiellement faire l'algorithme SMQT sur ce petit vecteur, mais contrairement au vecteur original avec lequel nous avons commencé, celui-ci sera beaucoup plus facile.

   Nous devons d'abord calculer la moyenne de tous les échantillons. Nous pouvons le trouver facilement par : sum[31] / n[31] = 160 / 10 = 16. Nous divisons donc le tableau en deux vecteurs et commençons à écrire le code binaire pour chacun :

   je	1	7	16	25	31
   n	2	4	6	8	dix
   somme	2	16	48	98	160
   code	0	0	0	1	1

   Maintenant, nous divisons à nouveau chaque vecteur. La moyenne du premier vecteur est : sum[16] / n[16] = 48 / 6 = 8. Et la moyenne du second vecteur est : (sum[31] – sum[16]) / (n[31] – n[16]) = (160 – 48) / (10 – 6) = 112 / 4 = 28.

   je	1	7	16	25	31
   n	2	4	6	8	dix
   somme	2	16	48	98	160
   code	00	00	01	dix	11

   Il ne reste qu'un seul vecteur à découper. La moyenne est : somme[7] / n[7] = 16 / 4 = 4.

   je	1	7	16	25	31
   n	2	4	6	8	dix
   somme	2	16	48	98	160
   code	000	001	010	100	110

   Comme vous pouvez le voir, le code de chaque élément est le même si nous avions suivi l'algorithme d'origine. Et nous avons fait le SMQT sur un vecteur beaucoup plus petit que celui avec N éléments et nous avons également pré-calculé toutes les valeurs dont nous avons besoin pour trouver la moyenne, il est donc simple et rapide de calculer le vecteur résultant.

   La complexité de cette étape est O(L*(2^L)), qui pour un L=8, et dans les besoins pratiques de traitement d'image, c'est O(8*(256)) = O(2048) = constante.

6. L'étape finale consiste à itérer à nouveau N éléments en remplaçant l'élément par son code pour chaque élément : element[i] = code[i]. La complexité est O(N). La complexité de FastSMQT est O(N) + O(2^L) + O(L*(2^L)) + O(N) = O(2*N) + O((L + 1)*(2 ^L)) = O(N + L*(2^L)) .

Parallélisme

Les deux algorithmes peuvent être parallélisés, bien qu'il soit plus efficace d'exécuter un algorithme par cœur à la place si plusieurs vecteurs doivent être transformés. Par exemple, lors du traitement d'images, nous pouvons traiter chaque canal RVB dans un noyau différent au lieu de paralléliser chacun de ces trois calculs.

Pour paralléliser l'algorithme SMQT, lorsque nous divisons un vecteur en deux, nous pouvons traiter chaque sous-vecteur dans un nouveau cœur si un cœur est disponible (en fait un sous-vecteur dans le cœur actuel et l'autre dans un nouveau cœur). Cela peut être fait de manière récursive jusqu'à ce que nous atteignions le nombre total de cœurs disponibles. Les remplacements de valeurs par des codes peuvent également se faire en parallèle pour.

L'algorithme FastSMQT peut également être parallélisé. Dans la première étape, le vecteur d'entrée doit être divisé en nombre de cœurs disponibles (C). Un vecteur de comptage de fréquence doit être créé pour chacune de ces parties, et être rempli en parallèle. Ensuite, nous ajoutons les valeurs de ces vecteurs dans un vecteur résultant de fréquences. La prochaine étape qui peut être parallélisée est la dernière, lorsque nous substituons les valeurs par leurs codes. Cela peut être fait en parallèle pour.

Comparaison de complexité

La complexité totale de l'algorithme SMQT original est O((2*L + 1)*N), qui est O(L*N).

La complexité de FastSMQT est O(N) + O(2^L) + O(L*(2^L)) + O(N) = O(2*N) + O((L + 1)*(2 ^L)) = O(N + L*(2^L)).

Étant donné un L fixe, la complexité devient juste O(N) pour les deux. Mais la constante qui multiplie N est beaucoup plus petite pour FastSMQT, et cela fait une grande différence dans le temps de traitement comme nous le verrons.

Le graphique suivant compare les performances des algorithmes SMQT et FastSMQT pour L=8, ce qui est le cas pour le traitement d'image. Le graphique montre le temps (en millisecondes) qu'il faut pour traiter N éléments. Notez que la complexité (avec constantes) de SMQT pour L=8 est O(17*N), tandis que pour FastSMQT est O(2*N + 2304).

Plus le N est grand, plus il faut de temps à SMQT pour traiter l'image. Pour FastSMQT, en revanche, la croissance est beaucoup plus lente.

Pour des valeurs encore plus grandes de N, la différence de performance est beaucoup plus apparente :

Ici, SMQT prend plusieurs secondes pour traiter certaines images, tandis que FastSMQT se situe toujours dans la zone de "quelques millisecondes".

Même avec plusieurs cœurs (deux, dans ce cas), FastSMQT est clairement supérieur à SMQT :

FastSMQT ne dépend pas de L. SMQT, d'autre part, dépend linéairement de la valeur de L. Par exemple, avec N = 67108864, le temps d'exécution de SMQT augmente avec l'augmentation de la valeur de L, alors que FastSMQT ne :

Conclusion

Toutes les techniques d'optimisation ne sont pas applicables à tous les algorithmes, et la clé de l'amélioration des performances d'un algorithme est souvent cachée dans une certaine compréhension du fonctionnement de l'algorithme. Cet algorithme FastSMQT tire parti des possibilités de précalcul des valeurs et de la nature des calculs de moyenne. En conséquence, il permet un traitement plus rapide que le SMQT d'origine. La vitesse n'est pas affectée par l'incrément de L, bien que L ne puisse pas être beaucoup plus grand que le 8 habituel car l'utilisation de la mémoire est de 2 ^ L, ce qui pour 8 est un 256 acceptable (nombre de colonnes dans notre tableau de fréquence), mais le gain de performances présente des avantages pratiques évidents.

Cette amélioration de la vitesse a permis à MiddleMatter d'implémenter l'algorithme dans une application iOS (et une application Android) qui améliore les images et les vidéos capturées dans des conditions de faible luminosité. Avec cette amélioration, il était possible d'effectuer un traitement vidéo dans l'application, qui serait autrement trop lent pour les appareils iOS.

Le code C++ pour les algorithmes SMQT et FastSMQT est disponible sur GitHub.