Как исправить метод дизеринга для построения градиента?

Question

[tj57]

Есть программа, которая строит матрицу для градиента с помощью дизеринга. В ней реализованы 4 способа: Ordered, Random, Floyd-Steinberg, Jarvis-Judice-Ninke. Я создаю матрицу определенного размера и с помощью одного из методов преобразую её в градиент от белого цвета до чёрного и вывожу результат в файл формата .pgm, тип P5. Если перевести файл в .png, получаю такое изображение:



Однако, при увеличении картинки можно увидеть полосы (если хорошо присмотреться):

Это говорит о том, что дизеринг работает не совсем корректно. Для всех методов результат одинаковый. Как исправить эту проблему?

Код:

#include "stdafx.h"
#include <iostream>
#include<algorithm>
#include<iterator>
#include<fstream>
#include<vector>
#include<cassert>
#include <ctime>
#include <sstream>

using namespace std;

vector<vector<int>> make_gradient(int height, int width)
{
	assert(height > 0 && width > 0);

	int cf = height / 255;
	int color = 0;
	vector<vector<int>> result(height, vector<int>(width));
	for (int i = 0; i < height; i += cf)
	{
		for (int j = 0; j < cf; ++j)
		{
			fill(result[i + j].begin(), result[i + j].end(), color % 255);
		}
		color++;
	}
	stable_sort(result.begin(), result.end());
	return result;
}

vector<vector<int>> ordered_dither(int height, int width, vector<vector<int>> result)
{
	int ditherSize = 4;
	int diterLookup[] = { 0, 8, 2, 10, 12, 4, 14, 6, 3, 11, 1, 9, 15, 7, 13, 5 };

	for (int i = 0; i < height; i++)
	{
		for (int j = 0; j < width; j++)
		{
			int xlocal = i%ditherSize;
			int ylocal = j%ditherSize;
			int requiredShade = diterLookup[xlocal + ylocal * 4] * 255 / 16;
			if ((requiredShade > 0) && (requiredShade < 1))
			{
				if (requiredShade >= (result[i][j] % 1)) {
					result[i][j] = floor(result[i][j]);
				}
				else {
					result[i][j] = ceil(result[i][j]);
				}
			}
			else requiredShade = 0;
		}
	}
	return result;
}

vector<vector<int>> random_dither(int height, int width, vector<vector<int>> result)
{
	for (int i = 0; i < height; i++)
	{
		for (int j = 0; j < width; j++)
		{
			int requiredShade = (float)rand() / RAND_MAX;
			if ((requiredShade > 0) && (requiredShade < 1))
			{
				if (requiredShade >= (result[i][j] % 1)) {
					result[i][j] = floor(result[i][j]);
				}
				else {
					result[i][j] = ceil(result[i][j]);
				}
			}
			else requiredShade = 0;
		}
	}
	return result;
}

vector<vector<int>> fs_dither(int height, int width, vector<vector<int>> result)
{
	for (int i = 0; i < height; i++)
	{
		for (int j = 0; j < width; j++)
		{
			int oldpixel = result[i][j];
			int newpixel = round(result[i][j]);;
			result[i][j] = newpixel;
			int quanterror = oldpixel - newpixel;
			if (j < width - 1) {
				result[i][j + 1] += quanterror * 7 / 16;
			}
			if (i < height - 1) {
				if (j > 0) {
					result[i + 1][j - 1] += quanterror * 3 / 16;
				}
				result[i + 1][j] += quanterror * 5 / 16;
				if (j < width - 1) {
					result[i + 1][j + 1] += quanterror * 1 / 16;
				}
			}
		}
	}
	return result;
}

vector<vector<int>> jjn_dither(int height, int width, vector<vector<int>> result)
{
	for (int i = 0; i < height; i++)
	{
		for (int j = 0; j < width; j++)
		{
			int oldpixel = result[i][j];
			int newpixel = round(result[i][j]);;
			result[i][j] = newpixel;
			int quanterror = oldpixel - newpixel;
			if (j < width - 1) {
				result[i][j + 1] += quanterror * 7 / 48;
				if (j<width - 2)
					result[i][j + 2] += quanterror * 5 / 48;
			}

			if (i < height - 1) {
				if (j > 0) {
					if (j > 1)
						result[i + 1][j - 2] += quanterror * 3 / 48;
					result[i + 1][j - 1] += quanterror * 5 / 48;
				}

				result[i + 1][j] += quanterror * 7 / 48;
				if (j < width - 1) {
					result[i + 1][j + 1] += quanterror * 5 / 48;
					if (j < width - 2)
						result[i + 1][j + 2] += quanterror * 3 / 48;
				}
			}

			if (i < height - 2) {
				if (j > 0) {
					if (j>1)
						result[i + 2][j - 2] += quanterror * 1 / 48;
					result[i + 2][j - 1] += quanterror * 3 / 48;
				}
				result[i + 2][j] += quanterror * 5 / 48;
				if (j < width - 1) {
					result[i + 2][j + 1] += quanterror * 3 / 48;
					if (j < width - 2)
						result[i + 2][j + 2] += quanterror * 1 / 48;
				}
			}

		}
	}
	return result;
}

int main(int argc, char *argv[])
{
	if (argc < 5) {
		cout << "usage:" << endl << "prog.exe <filename> <width> <height> <dithering>" << endl;
		return 0;
	}
	stringstream w(argv[2]);
	stringstream h(argv[3]);
	stringstream d(argv[4]);
	int numcols, numrows, dithering;

	if (!(w >> numcols)) {
		cout << "width is not a number" << endl;
		return 0;
	}
	if (numcols < 1) {
		cout << "width must be more than zero" << endl;
		return 0;
	}

	if (!(h >> numrows)) {
		cout << "height is not a number" << endl;
		return 0;
	}
	if (numrows < 1) {
		cout << "height must be more than zero" << endl;
		return 0;
	}

	if (!(d >> dithering)) {
		cout << "dithering is not a number" << endl;
		return 0;
	}
	if (dithering < 0 || dithering>4) {
		cout << "dithering must be [0-4]" << endl;
		return 0;
	}

	srand(time(0));
	ofstream file;

	file.open(argv[1]);

	if (!file)
	{
		cout << "can't open file" << endl;
		return 0;
	}

	file << "P5" << "\n";

	file << numrows << " " << numcols << "\n";

	file << 255 << "\n";

	vector<vector<int>> pixmap{ make_gradient(numrows, numcols) };
	switch (dithering) {
	case 1:
		pixmap = ordered_dither(numrows, numcols, pixmap);
		break;
	case 2:
		pixmap = random_dither(numrows, numcols, pixmap);
		break;
	case 3:
		pixmap = fs_dither(numrows, numcols, pixmap);
		break;
	case 4:
		pixmap = jjn_dither(numrows, numcols, pixmap);
		break;
	default:
		break;
	}
	for_each(pixmap.begin(), pixmap.end(), [&](const auto& v) {
		copy(v.begin(), v.end(), ostream_iterator<char>{file, ""});
	});

	file.close();

}

Comments

[Roman]

https://habr.com/ru/post/151157/

Answer 1

[vasiliev]

В результате видно полосы, т.к. этот чистый градиент без дизеринга.
Это можно посмотреть, просто открыв pgm-файл в текстовом редакторе.

Не работают методы потому, что плохо написаны. Конкретнее, выбран неправильный тип данных для пикселя исходного градиента: целочисленный вместо с плавающей (или фиксированной) точкой.

В методах ordered_dither и random_dither есть такой код:

int requiredShade = some_value;
if ((requiredShade > 0) && (requiredShade < 1))

Здесь условие никогда не сработает, т.к. переменная requiredShade - целочисленная.

В методах fs_dither и jjn_dither result - вектор целочисленных переменных:

int oldpixel = result[i][j];
int newpixel = round(result[i][j]); 
int quanterror = oldpixel - newpixel;

oldpixel и newpixel всегда совпадают, quanterror всегда оказывается нулём.

Думаю, проблемы можно решить, поменяв тип пикселя на float/double, а из функций дизеринга возвращать уже массив int'ов (или uint8_t), вроде такого:

vector<vector<int>> fs_dither(int height, int width, const vector<vector<float>> &input_gradient); // const & - чтобы вектор не копировался лишний раз

Соотвественно, в остальном коде тоже проверить и поменять типы переменных, где требуется.

Советую изучить базовые типы в C и освоить отладчик.

Comments

[tj57]

Спасибо, я понял ошибки и исправил методы.

Получилось так:

#include "stdafx.h"
#include <iostream>
#include<algorithm>
#include<iterator>
#include<fstream>
#include<vector>
#include<cassert>
#include <ctime>
#include <sstream>

using namespace std;

vector<vector<int>> make_gradient(int height, int width)
{
	assert(height > 0 && width > 0);

	int cf = height / 255;
	int color = 0;
	vector<vector<int>> result(height, vector<int>(width));
	for (int i = 0; i < height; i += cf)
	{
		for (int j = 0; j < cf; ++j)
		{
			fill(result[i + j].begin(), result[i + j].end(), color % 255);
		}
		color++;
	}
	stable_sort(result.begin(), result.end());
	return result;
}

vector<vector<int>> ordered_dither(int height, int width)
{
	int ditherSize = 4;
	int ditherLookup[] = { 0, 8, 2, 10, 12, 4, 14, 6, 3, 11, 1, 9, 15, 7, 13, 5 };
	vector<vector<int>> result(height, vector<int>(width));

	for (int i = 0; i < height; i++)
	{
		double target = ((double)i + 0.5)*255.0 / height;

		for (int j = 0; j < width; j++)
		{
			int xlocal = i%ditherSize;
			int ylocal = j%ditherSize;
			double dither = ditherLookup[xlocal + ylocal * 4];
			int val = (int)round(target + dither);
			if (val < 0)
				val = 0;
			if (val > 255)
				val = 255;
			result[i][j] = val;
		}
	}
	return result;
}

vector<vector<int>> random_dither(int height, int width)
{
	assert(height > 0 && width > 0);

	vector<vector<int>> result(height, vector<int>(width));
	for (int i = 0; i < height; ++i)
	{
		
		double target = ((double)i + 0.5)*255.0 / height;
		for (int j = 0; j < width; ++j)
		{
			double dither = ((double)rand() - (double)rand()) / RAND_MAX;
			int val = (int)round(target + dither);
			if (val < 0)
				val = 0;
			if (val > 255)
				val = 255;
			result[i][j] = val;
		}
	}
	return result;
}

vector<vector<int>> fs_dither(int height, int width)
{
	vector<vector<int>> result(height, vector<int>(width));

	for (int i = 0; i < height; i++)
	{
		for (int j = 0; j < width; j++)
		{
			result[i][j] = ((double)i + 0.5)*255.0 / width;
		}
	}

	for (int i = 0; i < height - 1; i++)
	{
		for (int j = 0; j < width - 1; j++)
		{
			int oldpixel = result[i][j];
			int newpixel = round(oldpixel);
			result[i][j] = newpixel;
			int quanterror = oldpixel - newpixel;
			if (j < width - 1) {
				result[i][j + 1] += quanterror * 7 / 16;
			}
			if (i < height - 1) {
				if (j > 0) {
					result[i + 1][j - 1] += quanterror * 3 / 16;
				}
				result[i + 1][j] += quanterror * 5 / 16;
				if (j < width - 1) {
					result[i + 1][j + 1] += quanterror * 1 / 16;
				}
			}
		}
	}
		
	return result;
}

vector<vector<int>> jjn_dither(int height, int width)
{
	vector<vector<int>> result(height, vector<int>(width));

	for (int i = 0; i < height; i++)
	{
		for (int j = 0; j < width; j++)
		{
			result[i][j] = ((double)i + 0.5)*255.0 / width;
		}
	}

	for (int i = 0; i < height; i++)
	{
		for (int j = 0; j < width; j++)
		{
			int oldpixel = result[i][j];
			int newpixel = round(result[i][j]);;
			result[i][j] = newpixel;
			int quanterror = oldpixel - newpixel;
			if (j < width - 1) {
				result[i][j + 1] += quanterror * 7 / 48;
				if (j<width - 2)
					result[i][j + 2] += quanterror * 5 / 48;
			}

			if (i < height - 1) {
				if (j > 0) {
					if (j > 1)
						result[i + 1][j - 2] += quanterror * 3 / 48;
					result[i + 1][j - 1] += quanterror * 5 / 48;
				}

				result[i + 1][j] += quanterror * 7 / 48;
				if (j < width - 1) {
					result[i + 1][j + 1] += quanterror * 5 / 48;
					if (j < width - 2)
						result[i + 1][j + 2] += quanterror * 3 / 48;
				}
			}

			if (i < height - 2) {
				if (j > 0) {
					if (j>1)
						result[i + 2][j - 2] += quanterror * 1 / 48;
					result[i + 2][j - 1] += quanterror * 3 / 48;
				}
				result[i + 2][j] += quanterror * 5 / 48;
				if (j < width - 1) {
					result[i + 2][j + 1] += quanterror * 3 / 48;
					if (j < width - 2)
						result[i + 2][j + 2] += quanterror * 1 / 48;
				}
			}

		}
	}
	return result;
}

int main(int argc, char *argv[])
{
	if (argc < 5) {
		cout << "usage:" << endl << "prog.exe <filename> <width> <height> <dithering>" << endl;
		return 0;
	}
	stringstream w(argv[2]);
	stringstream h(argv[3]);
	stringstream d(argv[4]);
	int numcols, numrows, dithering;

	if (!(w >> numcols)) {
		cout << "width is not a number" << endl;
		return 0;
	}
	if (numcols < 1) {
		cout << "width must be more than zero" << endl;
		return 0;
	}

	if (!(h >> numrows)) {
		cout << "height is not a number" << endl;
		return 0;
	}
	if (numrows < 1) {
		cout << "height must be more than zero" << endl;
		return 0;
	}

	if (!(d >> dithering)) {
		cout << "dithering is not a number" << endl;
		return 0;
	}
	if (dithering < 0 || dithering>4) {
		cout << "dithering must be [0-4]" << endl;
		return 0;
	}

	srand(time(0));
	ofstream file;

	file.open(argv[1]);

	if (!file)
	{
		cout << "can't open file" << endl;
		return 0;
	}

	file << "P5" << "\n";

	file << numrows << " " << numcols << "\n";

	file << 255 << "\n";

	vector<vector<int>> pixmap;
	switch (dithering) {
	case 0:
		pixmap = make_gradient(numrows, numcols);
		break;
	case 1:
		pixmap = ordered_dither2(numrows, numcols);
		break;
	case 2:
		pixmap = random_dither(numrows, numcols);
		break;
	case 3:
		pixmap = fs_dither(numrows, numcols);
		break;
	case 4:
		pixmap = jjn_dither(numrows, numcols);
		break;
	default:
		break;
	}
	for_each(pixmap.begin(), pixmap.end(), [&](const auto& v) {
		copy(v.begin(), v.end(), ostream_iterator<char>{file, ""});
	});

	file.close();
}

Теперь при увеличении изображения полос нет:
Но есть небольшая проблема с ordered dithering: он работает, но не совсем корректно. Получается такой результат:
Не подскажете, как можно исправить ?

[vasiliev]

В ordered dithering вы по сути разбиваете картинку на кусочки 4х4 пиксела и добавляете к каждому из них матрицу

0, 8, 2, 10
12, 4, 14, 6
3, 11, 1, 9
15, 7, 13, 5

Поскольку паттерн имеет небольшой период и повторяется, его хорошо видно глазом.

Чтобы исправить, можно предложить увеличить размер паттерна или выбирать его случайным образом из нескольких вариантов, но можно ли это будет в таком случае называть ordered dithering - не знаю.

Ещё я и в этом методе, и в других, прибавлял бы не положительные числа, а равные в среднем нулю, чтобы не изменялась средняя яркость изображения после дизеринга.

[tj57]

vasiliev, я попробовал сделать матрицу 8х8 - там совсем неверный результат получается. Как я понял, такая картинка (которую я прикрепил выше) получается из-за того, что значения соседних пикселей различаются больше чем на 1. Мне кажется, проблема где-то здесь:

int xlocal = i%ditherSize;
int ylocal = j%ditherSize;
double dither = ditherLookup[xlocal + ylocal * 4];