Наверное, некоторые из вас, дорогие читатели, видели то, как ранее отображались картинки на экранах старых мониторов – при довольно скромной цветовой палитре, с помощью одного простого алгоритма, удавалось добиться глубины цвета, и при этом не задействуя значительные ресурсы процессора.
Сегодня, мы хотим вам показать реализацию одного из таких алгоритмов, который позволяет используя дизеринг и небольшую палитру получать интересные изображения.
Для начала объясним в двух словах, что такое дизеринг.
Дизеринг – это такая схема смешивания цветов из ограниченной палитры, которая позволяет смешивая цвета из палитры определенным образом: к примеру отсутствующие цвета, могут получаться путем расстановки существующих цветов в шахматном (или ином) порядке, а также эффект может достигаться подмешиванием шума со специально подобранными характеристиками. Для достижения эффекта глубины цвета (скажем сразу, глубина, а также отсутствующие цвета, которые при этом не исчезают с обработанного изображения являются чистой воды иллюзией) есть несколько очень известных алгоритмов. Мы будем делать реализацию одного из таких алгоритмов, который называется алгоритмом Флойда-Стейнберга.
Данный алгоритм основан на распространении ошибки, что означает, что ошибки от квантования переносятся на соседние пиксели, с которыми далее продолжается работа. По сути для того, чтобы алгоритм работал надо фактически вычислить насколько пиксель, который заменит текущий отличается от существующего в изображении (это и есть та самая ошибка) и применить эту разницу с определенными коэффициентами к соседним пикселям. Фактически, нам необходимо выполнить перемножение полученной ошибки на следующую матрицу значений:
Здесь звездочкой обозначен текущий пиксель, а коэффициенты показаны для его ближайших соседей (в контексте данного алгоритма), и на схеме показан только один шаг алгоритма, а его надо повторить для всех пикселей в изображении. Повтор этого шага приводит к постоянному накоплению и продвижению разницы между исходным и пикселем результатом трансформации, что в итоге приводит к изменению всех пикселей в изображении.
Кроме этого, есть важный момент – алгоритм указывает только как привести пиксели к новым значениям, на основании уже известного значения для нового пикселя, но алгоритм не говорит как получить новое значение для текущего пикселя.
Как вы понимаете, решение о том, как это сделать переходит на самого программиста. И вот тут мы кое что придумали…
Однажды мы уже выкладывали набор палитр в удобной для загрузки форме, и мы как раз предлагаем использовать либо загрузку палитры из какого-либо файла этой коллекции, либо ее ручное создание (путь для истинных ценителей, так сказать). Но просто загрузки недостаточно, поскольку сама палитра – это просто набор цветов, а в данном случае необходимо для каждого пикселя из изображения найти наиболее “подходящий” цвет из палитры.
Для достижения подобных целей, а также для реализации всего алгоритма будем использовать библиотеку dlib, с помощью которой задача загрузки и поиска ближайшего цвета из палитры решаются так:
import std.algorithm;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.file;
import dlib.image;
Color4f[] getPalette(string filename)
{
Color4f[] palette;
auto extractField(string triplet)
{
auto content = triplet.split(";");
auto r = parse!float(content[0]);
auto g = parse!float(content[1]);
auto b = parse!float(content[2]);
return Color4f(r / 255.0f, g / 255.0f, b / 255.0f);
}
palette = (cast(string)(read(filename)))
.splitLines
.map!(a => extractField(a))
.array;
return palette;
}
auto calculateColorDistance(Color4f a, Color4f b)
{
auto dx = a.r - b.r;
auto dy = a.g - b.g;
auto dz = a.b - b.b;
return sqrt((dx ^^ 2) + (dy ^^ 2) + (dz ^^ 2));
}
auto nearestColorFromPalette(Color4f a, ref Color4f[] palette)
{
import std.math : abs;
float distance = float.max;
Color4f r = palette[0];
foreach (e; palette.sort!`a.luminance < b.luminance`)
{
auto d = calculateColorDistance(e, a);
if (d <= distance)
{
r = e;
distance = d;
}
}
return r;
}загрузку палитр мы уже рассматривали ранее, а вот про подход к поиску ближайшего цвета мы упоминали в записи про выборочное обесцвечивание. Но тут алгоритм поиска ближайшего цвета несколько отличается от того, что было при обесцвечивании: здесь также используется идея с минимальным расстоянием между цветами, но замена идет на цвет из палитры и только из присутствует только одна ветвь условия в if, поскольку в побочной ветви нет необходимости.
Сам алгоритм Флойда-Стейнберга можно выразить следующим псевдокодом:
for each y from top to bottom do
for each x from left to right do
oldpixel := pixels[x][y]
newpixel := nearestColorFromPalette(oldpixel)
pixels[x][y] := newpixel
quant_error := oldpixel - newpixel
pixels[x + 1][y ] := pixels[x + 1][y ] + quant_error × 7 / 16
pixels[x - 1][y + 1] := pixels[x - 1][y + 1] + quant_error × 3 / 16
pixels[x ][y + 1] := pixels[x ][y + 1] + quant_error × 5 / 16
pixels[x + 1][y + 1] := pixels[x + 1][y + 1] + quant_error × 1 / 16который можно буквально перевести на D следующим образом:
auto dithering(SuperImage simg, ref Color4f[] palette)
{
foreach (x; 0..simg.width)
{
foreach (y; 0..simg.height)
{
auto oldpixel = simg[x, y];
auto newpixel = nearestColorFromPalette(oldpixel, palette);
simg[x, y] = newpixel;
auto quant_error = oldpixel - newpixel;
simg[x + 1, y ] = simg[x + 1, y ] + quant_error * 7.0 / 16.0;
simg[x - 1, y + 1] = simg[x - 1, y + 1] + quant_error * 3.0 / 16.0;
simg[x , y + 1] = simg[x , y + 1] + quant_error * 5.0 / 16.0;
simg[x + 1, y + 1] = simg[x + 1, y + 1] + quant_error * 1.0 / 16.0;
}
}
return simg;
}И для испытания которого мы создадим палитру в стиле ZX-Spectrum и попробуем в качестве исходной картинки, взять изображение, созданное одним из авторов этого блога. Само изображение выглядит следующим образом:
Код для испытания:
void main()
{
//auto palette = getPalette(`bone.csv`);
/*
auto palette = [
Color4f(0.0f, 0.0f, 0.0f),
Color4f(1.0f, 1.0f, 1.0f)
];
*/
auto ZX_SPECTRUM_PALETTE =
[
Color4f(0.0f, 0.0f, 0.0f),
Color4f(0.0f, 0.0f, 238.0f),
Color4f(238.0 / 255.0f, 0.0f, 0.0f),
Color4f(238.0 / 255.0f, 0.0f, 238.0 / 255.0f),
Color4f(0.0f, 238.0 / 255.0f, 0.0f),
Color4f(0.0f, 238.0 / 255.0f, 238.0 / 255.0f),
Color4f(238.0 / 255.0f, 238.0 / 255.0f, 0.0f),
Color4f(238.0 / 255.0f, 238.0 / 255.0f, 238.0 / 255.0f),
Color4f(0.0f, 0.0f, 0.0f),
Color4f(0.0f, 0.0f , 255.0 / 255.0f),
Color4f(255.0 / 255.0f, 0.0, 0.0),
Color4f(255.0 / 255.0f, 0.0f, 255.0 / 255.0f),
Color4f(0.0f, 255.0 / 255.0f, 0.0f),
Color4f(0.0f, 255.0 / 255.0f, 255.0 / 255.0f),
Color4f(255.0 / 255.0f, 255.0 / 255.0f, 0.0f),
Color4f(255.0 / 255.0f, 255.0 / 255.0f, 255.0 / 255.0f)
];
alias palette = ZX_SPECTRUM_PALETTE;
auto img = loadImage(`dlang.jpg`);
img.dithering(palette);
img.saveImage(`dlang_dither.png`);
}Результат тестирования с палитрой от ZX Spectrum 48/128 (16 цветов):
Код очень простой и может быть использован не только с той палитрой, которую мы задали в примере для тестирования, но и с любой другой, которая представлена в форме массива (не обязательно упорядоченного) цветов типа Color4f. Также не обязательно в алгоритме использовать именно наш подход с поиском ближайшего цвета на основе кратчайшего расстояния между цветом из палитры и текущим, можно использовать и иные варианты – здесь выбор остается за вами.
Напоследок, мы оставляем ряд ссылок, которые использовались при подготовке данной статьи:
Полный код dub-скрипта из статьи:
#!/usr/bin/env dub
/+ dub.sdl:
dependency "dlib" version="~>1.0.0"
+/
import std.algorithm;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.file;
import dlib.image;
Color4f[] getPalette(string filename)
{
Color4f[] palette;
auto extractField(string triplet)
{
auto content = triplet.split(";");
auto r = parse!float(content[0]);
auto g = parse!float(content[1]);
auto b = parse!float(content[2]);
return Color4f(r / 255.0f, g / 255.0f, b / 255.0f);
}
palette = (cast(string)(read(filename)))
.splitLines
.map!(a => extractField(a))
.array;
return palette;
}
auto calculateColorDistance(Color4f a, Color4f b)
{
auto dx = a.r - b.r;
auto dy = a.g - b.g;
auto dz = a.b - b.b;
return sqrt((dx ^^ 2) + (dy ^^ 2) + (dz ^^ 2));
}
auto nearestColorFromPalette(Color4f a, ref Color4f[] palette)
{
import std.math : abs;
float distance = float.max;
Color4f r = palette[0];
foreach (e; palette.sort!`a.luminance < b.luminance`)
{
auto d = calculateColorDistance(e, a);
if (d <= distance)
{
r = e;
distance = d;
}
}
return r;
}
auto dithering(SuperImage simg, ref Color4f[] palette)
{
foreach (x; 0..simg.width)
{
foreach (y; 0..simg.height)
{
auto oldpixel = simg[x, y];
auto newpixel = nearestColorFromPalette(oldpixel, palette);
simg[x, y] = newpixel;
auto quant_error = oldpixel - newpixel;
simg[x + 1, y ] = simg[x + 1, y ] + quant_error * 7.0 / 16.0;
simg[x - 1, y + 1] = simg[x - 1, y + 1] + quant_error * 3.0 / 16.0;
simg[x , y + 1] = simg[x , y + 1] + quant_error * 5.0 / 16.0;
simg[x + 1, y + 1] = simg[x + 1, y + 1] + quant_error * 1.0 / 16.0;
}
}
return simg;
}
void main()
{
//auto palette = getPalette(`bone.csv`);
/*
auto palette = [
Color4f(0.0f, 0.0f, 0.0f),
Color4f(1.0f, 1.0f, 1.0f)
];
*/
auto ZX_SPECTRUM_PALETTE =
[
Color4f(0.0f, 0.0f, 0.0f),
Color4f(0.0f, 0.0f, 238.0f),
Color4f(238.0 / 255.0f, 0.0f, 0.0f),
Color4f(238.0 / 255.0f, 0.0f, 238.0 / 255.0f),
Color4f(0.0f, 238.0 / 255.0f, 0.0f),
Color4f(0.0f, 238.0 / 255.0f, 238.0 / 255.0f),
Color4f(238.0 / 255.0f, 238.0 / 255.0f, 0.0f),
Color4f(238.0 / 255.0f, 238.0 / 255.0f, 238.0 / 255.0f),
Color4f(0.0f, 0.0f, 0.0f),
Color4f(0.0f, 0.0f , 255.0 / 255.0f),
Color4f(255.0 / 255.0f, 0.0, 0.0),
Color4f(255.0 / 255.0f, 0.0f, 255.0 / 255.0f),
Color4f(0.0f, 255.0 / 255.0f, 0.0f),
Color4f(0.0f, 255.0 / 255.0f, 255.0 / 255.0f),
Color4f(255.0 / 255.0f, 255.0 / 255.0f, 0.0f),
Color4f(255.0 / 255.0f, 255.0 / 255.0f, 255.0 / 255.0f)
];
alias palette = ZX_SPECTRUM_PALETTE;
auto img = loadImage(`dlang.jpg`);
img.dithering(palette);
img.saveImage(`dlang_dither.png`);
}P.S: На самом деле какое-то подобие дизеринга мы уже делали вот в этой статье, если интересно, можете с ней ознакомится.