Преобразование черно-белых изображений в ASCII-графику при помощи неотрицательного матричного разложения

В общем случае преобразование изображения в ASCII-графику представляет собой довольно трудоемкую задачу, однако существуют алгоритмы, позволяющие автоматизировать данный процесс. В данной статье рассматривается подход, предложенный исследователями Paul D. O’Grady и Scott T. Rickard в работе «Automatic ASCII Art Conversion of Binary Images Using Non-Negative Constraints». Описанный ими метод предполагает представление процесса преобразования изображения как задачи оптимизации и решение этой задачи при помощи неотрицательного матричного разложения. Ниже приведены описание рассматриваемого алгоритма, а также его реализация:

Описание алгоритма

Исходное изображение разбивается на блоки размером $\$inline\$M\backslash times\; N\$inline\$$, где $\$inline\$M\$inline\$$ и $\$inline\$N\$inline\$$ — ширина и высота одного символа в пикселях. Если ширина\высота изображения не кратна ширине\высоте символа, то картинка обрезается или дополняется белыми областями нужного размера.


Каждый из $\$inline\$K\$inline\$$ блоков, полученных после разбиения, представляется в виде вектора длиной $\$inline\$R=M*N\$inline\$$, значениями которого являются интенсивности цвета пикселей изображения (значения от 0 до 255, где белому пикселю соответствует значение 0, а черному — 255). Полученные векторы следует нормировать, используя норму $\$inline\$l\_2\$inline\$$:

$\$\$display\$\$v\_i=\; \backslash frac\{v\_i\}\{\backslash sqrt\{\backslash sum^R\_\{k=1\}\{v^2\_k\}\}\}\$\$display\$\$$

Нормированные векторы переписываются в виде столбцов, образуя таким образом матрицу $\$inline\$V\$inline\$$ размером $\$inline\$R\backslash times\; K\$inline\$$.

Полученную матрицу $\$inline\$V\$inline\$$ нужно представить в виде произведения матриц $\$inline\$W\$inline\$$ и $\$inline\$H\$inline\$$, все элементы которых неотрицательны:

$\$\$display\$\$V\_\{R\; \backslash times\; K\}=W\_\{R\backslash times\; L\}\; H\_\{L\; \backslash times\; K\}\$\$display\$\$$

Матрица $\$inline\$W\$inline\$$ известна заранее: она строится аналогично матрице $\$inline\$V\$inline\$$, но вместо участков исходной картинки используются изображения всех символов, используемых при генерации ASCII-графики. Если применяемый набор включает в себя $\$inline\$L\$inline\$$ символов, то матрица $\$inline\$W\$inline\$$ будет иметь размер $\$inline\$R\backslash times\; L\$inline\$$.
Остается лишь подобрать матрицу $\$inline\$H\$inline\$$ таким образом, чтобы минимизировать значение некоторой целевой функции, характеризующей разницу между $\$inline\$V\$inline\$$ и произведением $\$inline\$WH\$inline\$$. В качестве такой функции используется следующая зависимость:

$\$\$display\$\$D(V,W,H,\backslash beta)=\backslash sum\_\{ik\}\backslash bigg(\{v\_ik\backslash frac\{v\_\{ik\}^\{\backslash beta-1\}-[WH]^\{\backslash beta-1\}\_\{ik\}\}\{\backslash beta(\backslash beta-1)\}\}+[WH]^\{\backslash beta-1\}\_\{ik\}\backslash frac\{[WH]\_\{ik\}-v\_\{ik\}\}\{\backslash beta\}\backslash bigg)\$\$display\$\$$

Данное выражение по сути объединяет в себе несколько целевых функций: при $\$inline\$\backslash beta\; =\; 2\$inline\$$ оно преобразуется в квадрат евклидова расстояния (Squared Euclidean Distance), при $\$inline\$\backslash beta\; \backslash rightarrow\; 1\$inline\$$ приближается к расстоянию Кульбака-Лейблера (Kullback-Leibler Divergence), а при $\$inline\$\backslash beta\; \backslash rightarrow\; 0\$inline\$$ — к расстоянию Итакуры-Сайто (Itakura-Saito Divergence).

Непосредственно подбор матрицы $\$inline\$H\$inline\$$ производится следующим образом: $\$inline\$H\$inline\$$ инициализируется случайными значениями от 0 до 1, после чего ее значения итеративно обновляются согласно следующему правилу (количество итераций задается заранее):

$\$\$display\$\$h\_\{jk\}=h\_\{jk\}\backslash frac\{\backslash sum^R\_\{i=1\}\{w\_\{ij\}\backslash frac\{v\_\{ik\}\}\{[WH]^\{2-\backslash beta\}\_\{ik\}\}\}\}\{\backslash sum^R\_\{i=1\}\{w\_\{ij\}[WH]^\{\backslash beta-1\}\_\{ik\}\}\}\$\$display\$\$$

Каждое значение $\$inline\$h\_\{ij\}\$inline\$$ соответствует степени схожести $\$inline\$i\$inline\$$-го символа из используемого набора с $\$inline\$j\$inline\$$-м участком изображения.


Таким образом, чтобы определить, каким символом следует заменить $\$inline\$j\$inline\$$-й участок, достаточно найти максимальное значение в $\$inline\$j\$inline\$$-м столбце матрицы $\$inline\$H\$inline\$$. Номер строки, в котором располагается данное значение, и будет номером искомого символа в наборе. Кроме того, можно ввести некоторое пороговое значение $\$inline\$\backslash epsilon\$inline\$$, и если найденное максимальное значение меньше этого порога, то участок изображения заменяется пробелом. Использование пробела может положительно сказаться на виде результирующего изображения по сравнению с использованием символа с низкой степенью схожести.

Реализация

Реализация алгоритма выполнена на языке 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);

Используя рассчитанные значения, разобьем исходное изображение на блоки необходимого размера. Для каждого блока запишем значения интенсивности цвета пикселей в соответствующий столбец матрицы $\$inline\$V\$inline\$$ (при необходимости расширим исходное изображение, добавив в матрицу нулевые значения, соответствующие белым пикселям), после чего нормализуем все столбцы:

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) Заполним матрицу $\$inline\$H\$inline\$$ случайными значениями от 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) Последний шаг состоит в выборе для каждого участка изображения подходящего символа путем нахождения максимальных значений в столбцах матрицы $\$inline\$H\$inline\$$:

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

Полученное изображение записывается в html-файл. Полный исходный код программы можно найти тут.

Примеры сгенерированных изображений

Ниже представлены примеры изображений, сгенерированных при различных значениях параметра $\$inline\$\backslash beta\$inline\$$ и количествах итераций. Исходное изображение имело размер 407x500 пикселей, соответственно результирующие изображения имели размер 37x22 символов.

Заключение

В рассматриваемом алгоритме можно выделить следующие недостатки:

1. Долгая обработка изображений: в зависимости от размера картинки и количества итераций ее обработка может занимать от нескольких десятков секунд до нескольких десятков минут.
2. Низкое качество обработки детализированных изображений. Например, попытка преобразования изображения человеческого лица дает следующий результат:
   
   
   

В то же время уменьшение количества деталей за счет увеличения яркости и контрастности изображения позволяет значительно улучшить вид результирующего изображения:


В целом несмотря на перечисленные недостатки можно сделать вывод о том, что алгоритм дает удовлетворительные результаты.