这是有序抖动的正确实现吗？

Question

我对抖动感兴趣，命令抖动更精确。我花了很多时间在研究和实验上。并希望经过所有努力，我的代码能够正常工作。

我将提供执行抖动的代码和一些示例。

我的问题

• 它是如何工作的？
• 我的代码正确吗？
• 可以有任何简化吗？

---

这是这篇维基百科文章中抖动算法的伪代码，我的代码基于该文章。

以下是变量解释：

M(i, j)是第i行第j列c上的阈值图？是变换后的颜色，r是颜色空间中的扩散量。假设一个 RGB 调色板具有N³均匀选择的颜色，其中每个颜色坐标由一个八位字节表示，通常会选择：

---

现在，这是我的实现（伪代码）：

ditherMatrix = 4x4; // By 4x4 I mean the normal 4x4 dither matrix from the wikipedia article
ditherMatrixSize = 4;
offset = (ditherMatrixSize * (ditherMatrixSize / 2) - 0.5); 
/* In the wiki article it uses 0.5 as an offset, 
   but I have to do this instead. 
   Is this correct? Atleast it works. */

allowedChanelValues = 1; // example: 2 = (0 or 128 or 255 red, 0 or 128 or 255 green, 0 or 128 or 255 blue)
r = 255 / allowedChanelValues / (ditherMatrixSize * ditherMatrixSize);

// Applying the dither
transfromedColor.r = 
    currentPixel.r + r * ((ditherMatrix[x % ditherMatrixSize, y % ditherMatrixSize]) - offset);
transfromedColor.g = 
    currentPixel.g + r * ((ditherMatrix[x % ditherMatrixSize, y % ditherMatrixSize]) - offset);
transfromedColor.g = 
    currentPixel.g + r * ((ditherMatrix[x % ditherMatrixSize, y % ditherMatrixSize]) - offset);

// Quantizing, see https://youtu.be/0L2n8Tg2FwI 6:40 and 9:58 for explanation
transfromedColor.r = Round(allowedChanelValues * oldR / 255) * (255 / allowedChanelValues);
transfromedColor.g = Round(allowedChanelValues * oldG / 255) * (255 / allowedChanelValues);
transfromedColor.b = Round(allowedChanelValues * oldB / 255) * (255 / allowedChanelValues);

重要提示：现在，可以通过多种方式优化此代码，但这不是我的意图（目前）我只是希望它正常工作，然后我会看看可以优化的内容。

边注：当我刚开始时，我对值进行了硬编码，例如，我对 7.5 进行了硬编码，而不是 ditherMatrixSize * (ditherMatrixSize / 2) - 0.5。但是在尝试了其他抖动矩阵之后，我只是使用此代码来获取值而不是对其进行硬编码。

---

这里有些例子

（顶部 - 抖动，底部 - 原始。矩阵为4x4， allowedChanelValues 为1）

---

（左 - 抖动，右 - 原始。矩阵为4x4， allowedChanelValues 为1）

---

我之前谈到过是否可以简化代码。

我在这里找到了这个伪代码

  Threshold = COLOR(256/4, 256/4, 256/4); /* Estimated precision of the palette */
  For each pixel, Input, in the original picture:
    Factor  = ThresholdMatrix[xcoordinate % X][ycoordinate % Y];
    Attempt = Input + Factor * Threshold
    Color = FindClosestColorFrom(Palette, Attempt)
    Draw pixel using Color

为了实现这一点，我必须对矩阵进行归一化，使其范围从 0 到 1。这就是我实现它的方式：

factor = 1;
offset = (ditherMatrixSize * (ditherMatrixSize / 2) - 0.5d) / (ditherMatrixSize * ditherMatrixSize); 
// This time the offset is a bit different because I normalized the matrix
r = 256 / factor; // r is the same as the Threshold

transformedPixelColor.R = 
   currentPixel.R + r * (ditherMatrix[(x) % ditherMatrixSize, (y) % ditherMatrixSize] - offset)
transformedPixelColor.G = 
   currentPixel.G + r * (ditherMatrix[(x) % ditherMatrixSize, (y) % ditherMatrixSize] - offset)
transformedPixelColor.B = 
   currentPixel.B + r * (ditherMatrix[(x) % ditherMatrixSize, (y) % ditherMatrixSize] - offset)

这与另一个相同。我什至找到了第三种抖动方式，但它更复杂，抖动方式与这两种相同，所以我不会介绍它。

所以你怎么看？算法是否正常工作？

先感谢您！

Answer 1

它看起来不正确。计算中的某个地方会累积错误。

有序抖动不需要浮点算术。它可以通过纯整数计算来实现。

预先计算矩阵中的值也很好。

下面是 C 代码，它使用矩阵 16x16 执行 3bpp 有序 diter (Bayer)，以获得最佳结果。

const   int BAYER_PATTERN_16X16[16][16] =   {   //  16x16 Bayer Dithering Matrix.  Color levels: 256
                                                {     0, 191,  48, 239,  12, 203,  60, 251,   3, 194,  51, 242,  15, 206,  63, 254  }, 
                                                {   127,  64, 175, 112, 139,  76, 187, 124, 130,  67, 178, 115, 142,  79, 190, 127  },
                                                {    32, 223,  16, 207,  44, 235,  28, 219,  35, 226,  19, 210,  47, 238,  31, 222  },
                                                {   159,  96, 143,  80, 171, 108, 155,  92, 162,  99, 146,  83, 174, 111, 158,  95  },
                                                {     8, 199,  56, 247,   4, 195,  52, 243,  11, 202,  59, 250,   7, 198,  55, 246  },
                                                {   135,  72, 183, 120, 131,  68, 179, 116, 138,  75, 186, 123, 134,  71, 182, 119  },
                                                {    40, 231,  24, 215,  36, 227,  20, 211,  43, 234,  27, 218,  39, 230,  23, 214  },
                                                {   167, 104, 151,  88, 163, 100, 147,  84, 170, 107, 154,  91, 166, 103, 150,  87  },
                                                {     2, 193,  50, 241,  14, 205,  62, 253,   1, 192,  49, 240,  13, 204,  61, 252  },
                                                {   129,  66, 177, 114, 141,  78, 189, 126, 128,  65, 176, 113, 140,  77, 188, 125  },
                                                {    34, 225,  18, 209,  46, 237,  30, 221,  33, 224,  17, 208,  45, 236,  29, 220  },
                                                {   161,  98, 145,  82, 173, 110, 157,  94, 160,  97, 144,  81, 172, 109, 156,  93  },
                                                {    10, 201,  58, 249,   6, 197,  54, 245,   9, 200,  57, 248,   5, 196,  53, 244  },
                                                {   137,  74, 185, 122, 133,  70, 181, 118, 136,  73, 184, 121, 132,  69, 180, 117  },
                                                {    42, 233,  26, 217,  38, 229,  22, 213,  41, 232,  25, 216,  37, 228,  21, 212  },
                                                {   169, 106, 153,  90, 165, 102, 149,  86, 168, 105, 152,  89, 164, 101, 148,  85  }
                                            };

//  Color ordered dither using 3 bits per pixel (1 bit per color plane)
void    makeDitherBayerRgb3bpp( BYTE* pixels, int width, int height )   noexcept
{
    int col = 0;
    int row = 0;

    for( int y = 0; y < height; y++ )
    {
        row = y & 15;   //  y % 16
        
        for( int x = 0; x < width; x++ )
        {
            col = x & 15;   //  x % 16

            pixels[x * 3 + 0]   = (pixels[x * 3 + 0] > BAYER_PATTERN_16X16[col][row] ? 255 : 0);
            pixels[x * 3 + 1]   = (pixels[x * 3 + 1] > BAYER_PATTERN_16X16[col][row] ? 255 : 0);
            pixels[x * 3 + 2]   = (pixels[x * 3 + 2] > BAYER_PATTERN_16X16[col][row] ? 255 : 0);
        }

        pixels  += width * 3;
    }
}

这是此实施的结果：

有关抖动的更多算法、源代码和演示，您可以查看此处