Ordered dithering

Latest revision as of 16:57, 20 September 2015

todo - rewrite later

• http://forum.doom9.org/showthread.php?p=1509153#post1509153
• http://www.virtualdub.org/blog/pivot/entry.php?id=151
• https://engineering.purdue.edu/~bouman/ece637/notes/pdf/Halftoning.pdf (page 11)

It is ordered input dithering with a 02/31 recursive Bayer pattern (contrast normal 13/42 pattern) modified for equal sums in both rows and columns. Avery

Lee described the recursive generation in his blog a while ago on Dithering. I modified the resultant pattern for equal summing to eliminate an obvious

pattern visible in 16x16 cells.

The dithering is added as an extra lower 8 bits (4bits for chroma) on the input pixels, making 16bit data. This is then used as an index into a 65K LUT to

get the output 8 bit pixel. The dither pattern effectively replaces the 0.5 rounding term in generating the LUT.

without dithering:

i = 0..255
mapR[i] = int(min(max(i * r/255.0, 0.0), 1.0) * 255.0 + 0.5);
example: r=2, i=16 => mapR[16] = int(32/255.0 * 255.0 + 0.5) = 32

     for (int y=0; y<vi.height; ++y) {
       for (int x=0; x<vi.width; ++x) {
         p[x] = map[p[x]];
       }
       p += pitch;
     }

with dithering:

i = 0..256*256-1
mapR[i] = int(min(max(i * r - 127.5)/(255.0*256), 0.0), 1.0) * 255.0 + 0.5);
example: r=2, i=16*256 => mapR[16*256] = int((32*256 - 127.5)/(255.0*256) * 255.0 + 0.5) = 32
bias = -127.5 ??

     for (int y=0; y<vi.height; ++y) {
       const int _y = (y << 4) & 0xf0;
       for (int x=0; x<vi.width; ++x) {
         p[x] = map[ p[x]<<8 | ditherMap[(x&0x0f)|_y] ];
       }
       p += pitch;
     }

// 16x16 dither table:
_y = (y << 4) & 0xf0 = ...
ditherMap[(x&0x0f)|_y] = ...

y=15+3 => _y = (y << 4) & 0xf0 = 18/2^4 & (f*16 + 0*1) = 18/16 & 15*16 = 1 & 1111 0000 = 0
y=15*16 => _y = (y << 4) & 0xf0 = 15*16/2^4 & (f*16 + 0*1) = 15 & 15*16 = 1111 & 1111 0000 = 0
ditherMap[(x&0x0f)|_y] = ditherMap[(x & 1111) | 0] = ditherMap[x & 1111]
y=16*16 => _y = (y << 4) & 0xf0 = 16*16/2^4 & (f*16 + 0*1) = 16 & 15*16 = 1 0000 & 1111 0000 = 1
ditherMap[(x&0x0f)|_y] = ditherMap[(x & 1111) | 1]
* so each 256 pixels, the offset in ditherMap is shifted by one. 

// 4x4 dither table:
const int _y = (y << 2) & 0xC;
ditherMap4[(x&0x3)|_y];

http://web.archive.org/web/20130512190753/http://white.stanford.edu/~brian/psy221/reader/Bayer.1973.pdf