Geekly articles weekly

Konvertieren Sie Schwarzweißbilder mit nicht negativer Matrixzerlegung in ASCII-Grafiken


Im Allgemeinen ist das Konvertieren eines Bildes in ASCII-Grafiken eine ziemlich zeitaufwändige Aufgabe, aber es gibt Algorithmen, die diesen Prozess automatisieren. Dieser Artikel beschreibt den von den Forschern Paul D. O'Grady und Scott T. Rickard vorgeschlagenen Ansatz in "Automatische ASCII-Kunstkonvertierung von Binärbildern unter Verwendung nicht negativer Einschränkungen". Die von ihnen beschriebene Methode beinhaltet die Darstellung des Bildkonvertierungsprozesses als Optimierungsproblem und die Lösung dieses Problems unter Verwendung einer nicht negativen Matrixzerlegung. Nachfolgend finden Sie eine Beschreibung des betreffenden Algorithmus sowie dessen Implementierung:

Beschreibung des Algorithmus


Das Originalbild ist in Größenblöcke unterteilt M \ mal N. wo M. und N. - Breite und Höhe eines Zeichens in Pixel. Wenn die Breite \ Höhe des Bildes nicht ein Vielfaches der Breite \ Höhe des Zeichens ist, wird das Bild zugeschnitten oder durch weiße Bereiche der gewünschten Größe ergänzt.


Jeder von K. Blöcke, die nach der Partition erhalten werden, werden als Vektor der Länge dargestellt R = M * N. deren Werte sind die Farbintensitäten der Bildpixel (Werte von 0 bis 255, wobei das weiße Pixel dem Wert 0 und das schwarze Pixel 255 entspricht). Die resultierenden Vektoren sollten unter Verwendung der Norm normalisiert werden l_2 ::

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


Die normalisierten Vektoren werden in Form von Spalten umgeschrieben, wodurch eine Matrix gebildet wird V. die Größe R \ mal K. .

Die resultierende Matrix V. müssen als Produkt von Matrizen dargestellt werden W. und H. Alle Elemente davon sind nicht negativ:

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

Matrix W. im Voraus bekannt: Es ist ähnlich wie die Matrix aufgebaut V. Anstelle von Abschnitten des Originalbilds werden jedoch Bilder aller Symbole verwendet, die bei der Erzeugung von ASCII-Grafiken verwendet werden. Wenn das zutreffende Kit enthält L. Zeichen dann die Matrix W. wird eine Größe haben R \ mal L. .
Es bleibt nur eine Matrix zu wählen H. um den Wert einer Zielfunktion zu minimieren, die den Unterschied zwischen charakterisiert V. und arbeiten WH . Die folgende Abhängigkeit wird als solche Funktion verwendet:

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)

Dieser Ausdruck kombiniert im Wesentlichen mehrere objektive Funktionen: wann \ beta = 2 es wird in das Quadrat der euklidischen Entfernung (quadratische euklidische Entfernung) umgewandelt, wenn \ beta \ rightarrow 1 nähert sich der Kullback-Leibler-Divergenzstrecke und bei \ beta \ rightarrow 0 - bis zur Entfernung von Itakura-Saito (Itakura-Saito-Divergenz).

Direkte Matrixauswahl H. wie folgt hergestellt: H. Initialisiert mit zufälligen Werten von 0 bis 1, wonach die Werte gemäß der folgenden Regel iterativ aktualisiert werden (die Anzahl der Iterationen wird im Voraus festgelegt):

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}}}

Jeder Wert h_ {ij} entspricht dem Ähnlichkeitsgrad ich Zeichen aus dem Set mit j -th Abschnitt des Bildes.


So bestimmen Sie, welches Zeichen ersetzt werden soll j Abschnitt reicht es aus, den Maximalwert in zu finden j th Spalte der Matrix H. . Die Zeilennummer, in der sich dieser Wert befindet, ist die Nummer des gewünschten Zeichens im Satz. Sie können auch einen Schwellenwert eingeben. \ epsilon Wenn der gefundene Maximalwert unter diesem Schwellenwert liegt, wird der Bildabschnitt durch ein Leerzeichen ersetzt. Die Verwendung eines Leerzeichens kann sich positiv auf das Erscheinungsbild des resultierenden Bildes auswirken, verglichen mit der Verwendung eines Symbols mit geringem Ähnlichkeitsgrad.

Implementierung


Der Algorithmus ist in C # implementiert. ASCII-Grafiken werden mit 95 Zeichen (von 0x20 bis 0x7E) mit einer Größe von 11x23 Pixel generiert. Die verwendete Schriftart ist Courier. Unten finden Sie den Quellcode für die Funktion zum Konvertieren des Originalbilds in ASCII-Grafiken:

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; }

Betrachten Sie jeden Schritt einzeln:

1) Wir berechnen, wie viele Zeichen in die Breite und Höhe des Bildes passen können:

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

Mit den berechneten Werten teilen wir das Originalbild in Blöcke der erforderlichen Größe. Für jeden Block schreiben wir die Werte der Pixelfarbintensität in die entsprechende Matrixspalte V. (Falls erforderlich, erweitern wir das Originalbild, indem wir der Matrix Nullwerte hinzufügen, die weißen Pixeln entsprechen.) Anschließend normalisieren wir alle Spalten:

 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) Füllen Sie die Matrix H. Zufallswerte von 0 bis 1:

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

Wir wenden die Aktualisierungsregel eine bestimmte Anzahl von Malen auf ihre Elemente an:

 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); } } }

Die direkte Aktualisierung der Matrixelemente wird wie folgt implementiert (leider werden die mit der Division durch Null verbundenen Probleme mit einigen Krücken gelöst):

 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) Der letzte Schritt besteht darin, ein geeignetes Symbol für jeden Bildabschnitt auszuwählen, indem die Maximalwerte in den Matrixspalten ermittelt werden 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; }

Das resultierende Bild wird in die HTML-Datei geschrieben. Den vollständigen Quellcode des Programms finden Sie hier .

Beispiele für generierte Bilder


Nachfolgend finden Sie Beispiele für Bilder, die mit verschiedenen Parameterwerten erstellt wurden \ beta und die Anzahl der Iterationen. Das Originalbild hatte eine Größe von 407 x 500 Pixel, das resultierende Bild hatte eine Größe von 37 x 22 Zeichen.


Fazit


In dem betrachteten Algorithmus können die folgenden Nachteile unterschieden werden:

  1. Lange Bildverarbeitung: Abhängig von der Größe des Bildes und der Anzahl der Iterationen kann die Verarbeitung mehrere zehn Sekunden bis einige zehn Minuten dauern.
  2. Verarbeitung von Detailbildern in schlechter Qualität. Ein Versuch, ein Bild eines menschlichen Gesichts zu konvertieren, führt beispielsweise zu folgendem Ergebnis:


Gleichzeitig kann die Reduzierung der Anzahl der Teile durch Erhöhen der Helligkeit und des Kontrasts des Bildes das Erscheinungsbild des resultierenden Bildes erheblich verbessern:


Im Allgemeinen können wir trotz der obigen Nachteile den Schluss ziehen, dass der Algorithmus zufriedenstellende Ergebnisse liefert.

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

More articles:


All Articles