Geekly articles weekly

Convertissez des images en noir et blanc en graphiques ASCII à l'aide d'une décomposition matricielle non négative


En général, la conversion d'une image en graphiques ASCII est une tâche assez longue, mais il existe des algorithmes qui automatisent ce processus. Cet article traite de l'approche proposée par les chercheurs Paul D. O'Grady et Scott T. Rickard dans «Conversion automatique ASCII des images binaires en utilisant des contraintes non négatives» . La méthode qu'ils décrivent consiste à représenter le processus de conversion d'image comme un problème d'optimisation et à résoudre ce problème en utilisant une décomposition matricielle non négative. Voici une description de l'algorithme en question, ainsi que sa mise en œuvre:

Description de l'algorithme


L'image originale est divisée en blocs de taille M \ fois N où M et N - largeur et hauteur d'un caractère en pixels. Si la largeur \ hauteur de l'image n'est pas un multiple de la largeur \ hauteur du caractère, l'image est recadrée ou complétée par des zones blanches de la taille souhaitée.


Chacun K les blocs obtenus après la partition sont représentés comme un vecteur de longueur R = M * N dont les valeurs sont les intensités de couleur des pixels de l'image (valeurs de 0 à 255, où le pixel blanc correspond à la valeur 0 et le pixel noir correspond à 255). Les vecteurs résultants doivent être normalisés en utilisant la norme l_2 :

v_i = \ frac {v_i} {\ sqrt {\ sum ^ R_ {k = 1} {v ^ 2_k}}}


Les vecteurs normalisés sont réécrits sous forme de colonnes, formant ainsi une matrice V la taille R \ fois K .

La matrice résultante V doivent être représentés comme un produit de matrices W et H dont tous les éléments ne sont pas négatifs:

V_ {R \ fois K} = W_ {R \ fois L} H_ {L \ fois K}

Matrix W connu à l'avance: il est construit de manière similaire à la matrice V , mais au lieu de sections de l'image d'origine, des images de tous les symboles utilisés dans la génération de graphiques ASCII sont utilisées. Si le kit applicable comprend L caractères puis la matrice W aura une taille R \ fois L .
Il ne reste plus qu'à choisir une matrice H de manière à minimiser la valeur d'une fonction objective caractérisant la différence entre V et travailler WH . La dépendance suivante est utilisée comme une telle fonction:

D (V, W, H, \ beta) = \ sum_ {ik} \ bigg ({v_ {ik} \ frac {v_ {ik} ^ {\ beta-1} - [WH] ^ {\ beta-1} _ {ik}} {\ beta (\ beta-1)}} + [WH] ^ {\ beta-1} _ {ik} \ frac {[WH] _ {ik} -v_ {ik}} {\ beta } \ bigg)

Cette expression combine essentiellement plusieurs fonctions objectives: lorsque \ beta = 2 il est converti au carré de la distance euclidienne (Squared Euclidean Distance), lorsque \ beta \ rightarrow 1 s'approche de la distance de divergence Kullback-Leibler, et à \ beta \ rightarrow 0 - à la distance d'Itakura-Saito (divergence Itakura-Saito).

Sélection directe de matrice H produit comme suit: H initialisé avec des valeurs aléatoires de 0 à 1, après quoi ses valeurs sont mises à jour de manière itérative selon la règle suivante (le nombre d'itérations est fixé à l'avance):

h_ {jk} = h_ {jk} \ frac {\ sum ^ R_ {i = 1} {w_ {ij} \ frac {v_ {ik}} {[WH] ^ {2- \ beta} _ {ik}} }} {\ sum ^ R_ {i = 1} {w_ {ij} [WH] ^ {\ beta-1} _ {ik}}}

Chaque valeur h_ {ij} correspond au degré de similitude je personnage de l'ensemble avec j -ème section de l'image.


Donc, pour déterminer quel caractère doit être remplacé j section, il suffit de trouver la valeur maximale dans j e colonne de la matrice H . Le numéro de ligne dans lequel se trouve cette valeur sera le numéro du caractère souhaité dans l'ensemble. Vous pouvez également saisir une valeur seuil. \ epsilon , et si la valeur maximale trouvée est inférieure à ce seuil, alors la section d'image est remplacée par un espace. L'utilisation d'un espace peut avoir un effet positif sur l'apparence de l'image résultante par rapport à l'utilisation d'un symbole avec un faible degré de similitude.

Implémentation


L'algorithme est implémenté en C #. Les graphiques ASCII sont générés à l'aide de 95 caractères (de 0x20 à 0x7E) avec une taille de 11x23 pixels; La police utilisée est Courier. Vous trouverez ci-dessous le code source de la fonction permettant de convertir l'image d'origine en graphiques ASCII:

public static char[,] ConvertImage( Bitmap image, double beta, double threshold, ushort iterationsCount, ushort threadsNumber, Action<int> ProgressUpdated) { int charNumHor = (int)Math.Round((double)image.Width / glyphWidth); int charNumVert = (int)Math.Round((double)image.Height / glyphHeight); int totalCharactersNumber = charNumVert * charNumHor; int glyphSetSize = wNorm.ColumnCount; Matrix<double> v = SplitImage(image, charNumVert, charNumHor); Matrix<double> h = Matrix<double>.Build.Random( glyphSetSize, totalCharactersNumber, new ContinuousUniform()); int progress = 0; ushort step = (ushort)(iterationsCount / 10); for (ushort i = 0; i < iterationsCount; i++) { UpdateH(v, wNorm, h, beta, threadsNumber); if((i + 1) % step == 0) { progress += 10; if(progress < 100) { ProgressUpdated(progress); } } } var result = GetAsciiRepresentation(h, charNumVert, charNumHor, threshold); ProgressUpdated(100); return result; }

Considérez chaque étape individuellement:

1) Nous calculons le nombre de caractères pouvant tenir dans la largeur et la hauteur de l'image:

 int charNumHor = (int)Math.Round((double)image.Width / glyphWidth); int charNumVert = (int)Math.Round((double)image.Height / glyphHeight);

En utilisant les valeurs calculées, nous divisons l'image d'origine en blocs de la taille requise. Pour chaque bloc, nous écrivons les valeurs de l'intensité de couleur des pixels dans la colonne de matrice correspondante V (si nécessaire, nous développons l'image d'origine en ajoutant des valeurs nulles correspondant à des pixels blancs à la matrice), après quoi nous normalisons toutes les colonnes:

 private static Matrix<double> SplitImage( Bitmap image, int charNumVert, int charNumHor) { Matrix<double> result = Matrix<double>.Build.Dense( glyphHeight * glyphWidth, charNumHor * charNumVert); for (int y = 0; y < charNumVert; y++) { for (int x = 0; x < charNumHor; x++) { for (int j = 0; j < glyphHeight; j++) { for (int i = 0; i < glyphWidth; i++) { byte color = 0; if ((x * glyphWidth + i < image.Width) && (y * glyphHeight + j < image.Height)) { color = (byte)(255 - image.GetPixel( x * glyphWidth + i, y * glyphHeight + j).R); } result[glyphWidth * j + i, charNumHor * y + x] = color; } } } } result = result.NormalizeColumns(2.0); return result; }

2) Remplissez la matrice H valeurs aléatoires de 0 à 1:

 Matrix<double> h = Matrix<double>.Build.Random( glyphSetSize, totalCharactersNumber, new ContinuousUniform());

Nous appliquons la règle de mise à jour un nombre spécifié de fois à ses éléments:

 for (ushort i = 0; i < iterationsCount; i++) { UpdateH(v, wNorm, h, beta, threadsNumber); if((i + 1) % step == 0) { progress += 10; if(progress < 100) { ProgressUpdated(progress); } } }

La mise à jour directe des éléments de la matrice est implémentée comme suit (malheureusement, les problèmes associés à la division par zéro sont résolus à l'aide de quelques béquilles):

 private static void UpdateH( Matrix<double> v, Matrix<double> w, Matrix<double> h, double beta, ushort threadsNumber) { const double epsilon = 1e-6; Matrix<double> vApprox = w.Multiply(h); Parallel.For( 0, h.RowCount, new ParallelOptions() { MaxDegreeOfParallelism = threadsNumber }, j => { for (int k = 0; k < h.ColumnCount; k++) { double numerator = 0.0; double denominator = 0.0; for (int i = 0; i < w.RowCount; i++) { if (Math.Abs(vApprox[i, k]) > epsilon) { numerator += w[i, j] * v[i, k] / Math.Pow(vApprox[i, k], 2.0 - beta); denominator += w[i, j] * Math.Pow(vApprox[i, k], beta - 1.0); } else { numerator += w[i, j] * v[i, k]; if (beta - 1.0 > 0.0) { denominator += w[i, j] * Math.Pow(vApprox[i, k], beta - 1.0); } else { denominator += w[i, j]; } } } if (Math.Abs(denominator) > epsilon) { h[j, k] = h[j, k] * numerator / denominator; } else { h[j, k] = h[j, k] * numerator; } } }); }

3) La dernière étape consiste à sélectionner un symbole approprié pour chaque section d'image en trouvant les valeurs maximales dans les colonnes de la matrice H :

 private static char[,] GetAsciiRepresentation( Matrix<double> h, int charNumVert, int charNumHor, double threshold) { char[,] result = new char[charNumVert, charNumHor]; for (int j = 0; j < h.ColumnCount; j++) { double max = 0.0; int maxIndex = 0; for (int i = 0; i < h.RowCount; i++) { if (max < h[i, j]) { max = h[i, j]; maxIndex = i; } } result[j / charNumHor, j % charNumHor] = (max >= threshold) ? (char)(firstGlyphCode + maxIndex) : ' '; } return result; }

L'image résultante est écrite dans le fichier html. Le code source complet du programme peut être trouvé ici .

Exemples d'images générées


Voici des exemples d'images générées à différentes valeurs de paramètres \ beta et le nombre d'itérations. L'image originale avait une taille de 407x500 pixels, respectivement, l'image résultante avait une taille de 37x22 caractères.


Conclusion


Dans l'algorithme considéré, les inconvénients suivants peuvent être distingués:

  1. Traitement d'image long: selon la taille de l'image et le nombre d'itérations, cela peut prendre de plusieurs dizaines de secondes à plusieurs dizaines de minutes.
  2. Traitement de mauvaise qualité des images détaillées. Par exemple, une tentative de conversion d'une image d'un visage humain donne le résultat suivant:


Dans le même temps, la réduction du nombre de pièces en augmentant la luminosité et le contraste de l'image peut améliorer considérablement l'apparence de l'image résultante:


En général, malgré les inconvénients ci-dessus, nous pouvons conclure que l'algorithme donne des résultats satisfaisants.

Source: https://habr.com/ru/post/fr463193/

More articles:


All Articles