🎞️ 👨‍👦‍👦 🥢 使用非负矩阵分解将黑白图像转换为ASCII图形 👈🏾 👩🏽‍🚀 🕚

通常，将图像转换为ASCII图形是一项非常耗时的任务，但是有一些算法可以自动执行此过程。本文讨论了研究人员Paul D. O'Grady和Scott T. Rickard在“使用非负约束对二进制图像进行自动ASCII艺术转换”中提出的方法。他们描述的方法涉及将图像转换过程表示为优化问题，并使用非负矩阵分解解决此问题。以下是有关算法及其实现的说明：

算法说明

原始图像分为大小块 $M \次N$ 在哪里

和

-一个字符的宽度和高度，以像素为单位。如果图像的宽度\高度不是字符的宽度\高度的倍数，则将图片裁剪或补充所需大小的白色区域。

每个

分区后获得的块表示为长度向量 R = M * N

其值是图像像素的颜色强度（值从0到255，其中白色像素对应于值0，黑色像素对应于255）。结果向量应使用范数归一化 l_2

：

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

归一化的矢量以列的形式重写，从而形成矩阵

大小 $R \倍K$ 。

所得矩阵

需要表示为矩阵的乘积 w ^

和

所有元素均为非负数：

$V_ {R \乘以K} = W_ {R \乘以L} H_ {L \乘以K}$

矩阵

事先已知：它的构造类似于矩阵

，而不是原始图像的各个部分，而是使用ASCII图形生成中使用的所有符号的图像。如果适用的套件包括

字符然后矩阵

将有一个大小 $R \乘L$ 。
只剩下选择一个矩阵 ^ h

从而最大程度地减少一些表征两者之间差异的目标函数的值

和工作

。以下依赖项用作此类功能：

$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）$

该表达式本质上结合了几个目标函数： $\ beta = 2$ 它将转换为欧几里德距离的平方（平方欧几里德距离），当 $\ beta \ rightarrow 1$ 接近Kullback-Leibler发散距离，并且在 $\ beta \ rightarrow 0$ -到板仓斋藤（Itakura-Saito Divergence）的距离。

直接矩阵选择 ^ h

产生如下：

使用0到1之间的随机值进行初始化，然后根据以下规则（其迭代次数已预先设置）迭代更新其值：

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

每个值 $h_ {ij}$ 对应相似度

集合中的字符

图像的第-部分。

因此，确定应替换哪个字符

部分中，找到最大值就足够了

矩阵的第列

。该值所在的行号将是集合中所需字符的编号。您也可以输入一些阈值。 $\ epsilon$ ，如果找到的最大值小于此阈值，则图像部分将被空格替换。与使用低相似度的符号相比，使用空格可以对所得图像的外观产生积极影响。

实作

该算法在C＃中实现。 ASCII图形使用95个字符（从0x20到0x7E）生成，大小为11x23像素；使用的字体是Courier。以下是将原始图像转换为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; }

分别考虑每个步骤：

1）我们计算出图像的宽度和高度可以容纳多少个字符：

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

使用计算出的值，我们将原始图像分成所需大小的块。对于每个块，我们在相应的矩阵列中写入像素颜色强度的值

（如果需要，我们通过向矩阵添加与白色像素对应的零值来扩展原始图像），然后对所有列进行归一化：

 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）填写矩阵

从0到1的随机值：

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

我们将更新规则对其元素应用指定的次数：

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

直接更新矩阵元素的实现方式如下（遗憾的是，使用拐杖可以解决与零除有关的问题）：

 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）最后一步是通过在矩阵列中找到最大值为每个图像部分选择合适的符号 ^ 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; }