T
T
tj572019-01-24 21:20:02
C++ / C#
tj57, 2019-01-24 21:20:02

How to fix the dither method to build the gradient?

There is a program that builds a matrix for a gradient using dithering. It implements 4 methods: Ordered, Random, Floyd-Steinberg, Jarvis-Judice-Ninke. I create a matrix of a certain size and use one of the methods to convert it to a gradient from white to black and output the result to a .pgm file, type P5. If I convert the file to .png, I get the following image:
5c4a00da0c6d3623154052.png
However, when the image is enlarged, you can see the stripes (if you look closely):
5c4a0127eaab4151198141.png
This indicates that the dithering does not work quite correctly. For all methods, the result is the same. How to fix this problem?
The code:

#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();

}

Answer the question

In order to leave comments, you need to log in

1 answer(s)
V
vasiliev, 2019-02-10
@tj57

As a result, stripes are visible, because. this pure gradient with no dither.
This can be seen by simply opening the pgm file in a text editor.
Methods do not work because they are poorly written. More specifically, the wrong data type was chosen for the source gradient pixel: integer instead of floating (or fixed) point.
The ordered_dither and random_dither methods have the following code:

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

Here the condition will never work, because the requiredShade variable is an integer.
In the fs_dither and jjn_dither methods, result is a vector of integer variables:
int oldpixel = result[i][j];
int newpixel = round(result[i][j]); 
int quanterror = oldpixel - newpixel;

oldpixel and newpixel are always the same, quanterror is always zero.
I think the problems can be solved by changing the pixel type to float / double, and from the dithering functions, return an array of ints (or uint8_t), like this:
Accordingly, in the rest of the code, also check and change the types of variables, where required.
I advise you to learn basic types in C and master the debugger.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question