Tinkering with code and algorithms for fun
Ordered Error Diffusion DitheringH-curve and HI-curve dithering
Two dithering algorithms: Ostromoukhov, and Zhou-Fang
pixelWidth = width * window.devicePixelRatio | 0
function ostromoukhov(imageData, noSerpentine) {
const {width, height, data} = imageData;
const {ctx} = getCtx(width, height);
const error = new Float64Array(width * height * 3);
const out = new Uint8Array(3);
const coeff = coefficients_ostromoukhov;
const {ceil} = Math;
const dyErr = width * 3;
const ditherFunc = (x, y) => {
const idx = (x + y * width), idx3 = idx * 3, idx4 = idx * 4;
// iterate over each channel.
for (let i = 0; i < 3; i++) {
const err = error[idx3 + i],
v = ceil(toLinear(data[idx4 + i]) * 255),
v4 = v*4, // multiplied by four to look up coefficients quicker
right = coeff[v4],
downleft = coeff[v4+1],
down = coeff[v4+2],
sum = right + downleft + down;
const vOut = (v + err) > 0x7F ? 0xFF : 0;
out[i] = vOut;
const dErr = v - vOut + err;
// handle serpentine scanning, meaning
// we alternation left-to-right with right-to-left
// every row
const dxErr = !noSerpentine && (y&1) ? -3 : 3;
if (x < width-1) error[idx3 + i + dxErr] += dErr * right / sum ;
if (y < height - 1) {
if (x > 0) error[idx3 + i - dxErr + dyErr] += dErr * downleft / sum;
error[idx3 + i + dyErr] += dErr * down / sum
}
}
return toU32Color(out[0], out[1], out[2]);
};
const canvas = (noSerpentine ? render : renderSerpentine)(width, height, ditherFunc, ctx, imageData)
canvas.style.imageRendering = "auto";
return canvas;
}
function zhoufang(imageData, noSerpentine) {
const {width, height, data} = imageData;
const {ctx} = getCtx(width, height);
const error = new Float64Array(width * height * 3);
const out = new Uint8Array(3);
const coeff = coefficients_zhoufang;
const dyErr = width * 3;
const {ceil, random} = Math;
const bellcurveish = () => (random() + random() - random() - random()) * 0.375;
const ditherFunc = (x, y) => {
const idx = (x + y * width), idx3 = idx * 3, idx4 = idx * 4;
// use same random value for each channel
const randomVal = bellcurveish();
// iterate over each channel.
for (let i = 0; i < 3; i++) {
const err = error[idx3 + i],
v = ceil(toLinear(data[idx4 + i]) * 255),
v4 = v*4, // multiplied by four to look up coefficients quicker
right = coeff[v4],
downleft = coeff[v4+1],
down = coeff[v4+2],
sum = right + downleft + down;
const threshold = modulation(randomVal, v);
const vOut = (v + err) > threshold ? 0xFF : 0;
out[i] = vOut;
const dErr = v - vOut + err;
// handle serpentine scanning, meaning
// we alternation left-to-right with right-to-left
// every row
const dxErr = !noSerpentine && (y&1) ? -3 : 3;
if (x < width-1) error[idx3 + i + dxErr] += dErr * right / sum ;
if (y < height - 1) {
if (x > 0) error[idx3 + i - dxErr + dyErr] += dErr * downleft / sum;
error[idx3 + i + dyErr] += dErr * down / sum
}
}
return toU32Color(out[0], out[1], out[2]);
};
const canvas = (noSerpentine ? render : renderSerpentine)(width, height, ditherFunc, ctx, imageData)
canvas.style.imageRendering = "auto";
return canvas;
}
// Zhou and Fang recalibrated the kernels to work well with varying
// random threshold modulation. The result is that *without* this
// modulation it produces a different structure than Ostromoukhov's
// original dithering, which is still interesting. So I added it
// for demonstration purposes.
function zhoufangNoRandom(imageData, noSerpentine) {
const {width, height, data} = imageData;
const {ctx} = getCtx(width, height);
const error = new Float64Array(width * height * 3);
const out = new Uint8Array(3);
const coeff = coefficients_zhoufang;
const {ceil} = Math;
const dyErr = width * 3;
const ditherFunc = (x, y) => {
const idx = (x + y * width), idx3 = idx * 3, idx4 = idx * 4;
// iterate over each channel.
for (let i = 0; i < 3; i++) {
const err = error[idx3 + i],
v = ceil(toLinear(data[idx4 + i]) * 255),
v4 = v*4, // multiplied by four to look up coefficients quicker
right = coeff[v4],
downleft = coeff[v4+1],
down = coeff[v4+2],
sum = right + downleft + down;
const threshold = modulation(0, v);
const vOut = (v + err) > threshold ? 0xFF : 0;
out[i] = vOut;
const dErr = v - vOut + err;
// handle serpentine scanning, meaning
// we alternation left-to-right with right-to-left
// every row
const dxErr = !noSerpentine && (y&1) ? -3 : 3;
if (x < width-1) error[idx3 + i + dxErr] += dErr * right / sum ;
if (y < height - 1) {
if (x > 0) error[idx3 + i - dxErr + dyErr] += dErr * downleft / sum;
error[idx3 + i + dyErr] += dErr * down / sum
}
}
return toU32Color(out[0], out[1], out[2]);
};
const canvas = (noSerpentine ? render : renderSerpentine)(width, height, ditherFunc, ctx, imageData)
canvas.style.imageRendering = "auto";
return canvas;
}
function original(imageData) {
const {width, height} = imageData;
const {ctx} = getCtx(width, height);
ctx.putImageData(imageData, 0, 0);
return ctx.canvas
}
// Coefficients taken from Otromoukhov's sample code, which can be found at:
// https://perso.liris.cnrs.fr/victor.ostromoukhov/publications/publications_abstracts.html#SIGGRAPH01_VarcoeffED
// when moving left-to-right, the weights are for:
// weights for: right, down-left, down, sum (see picture above)
coefficients_ostromoukhov = Uint16Array.from([
13, 0, 5, 18, /* 0 */
13, 0, 5, 18, /* 1 */
21, 0, 10, 31, /* 2 */
7, 0, 4, 11, /* 3 */
8, 0, 5, 13, /* 4 */
47, 3, 28, 78, /* 5 */
23, 3, 13, 39, /* 6 */
15, 3, 8, 26, /* 7 */
22, 6, 11, 39, /* 8 */
43, 15, 20, 78, /* 9 */
7, 3, 3, 13, /* 10 */
501, 224, 211, 936, /* 11 */
249, 116, 103, 468, /* 12 */
165, 80, 67, 312, /* 13 */
123, 62, 49, 234, /* 14 */
489, 256, 191, 936, /* 15 */
81, 44, 31, 156, /* 16 */
483, 272, 181, 936, /* 17 */
60, 35, 22, 117, /* 18 */
53, 32, 19, 104, /* 19 */
237, 148, 83, 468, /* 20 */
471, 304, 161, 936, /* 21 */
3, 2, 1, 6, /* 22 */
459, 304, 161, 924, /* 23 */
38, 25, 14, 77, /* 24 */
453, 296, 175, 924, /* 25 */
225, 146, 91, 462, /* 26 */
149, 96, 63, 308, /* 27 */
111, 71, 49, 231, /* 28 */
63, 40, 29, 132, /* 29 */
73, 46, 35, 154, /* 30 */
435, 272, 217, 924, /* 31 */
108, 67, 56, 231, /* 32 */
13, 8, 7, 28, /* 33 */
213, 130, 119, 462, /* 34 */
423, 256, 245, 924, /* 35 */
5, 3, 3, 11, /* 36 */
281, 173, 162, 616, /* 37 */
141, 89, 78, 308, /* 38 */
283, 183, 150, 616, /* 39 */
71, 47, 36, 154, /* 40 */
285, 193, 138, 616, /* 41 */
13, 9, 6, 28, /* 42 */
41, 29, 18, 88, /* 43 */
36, 26, 15, 77, /* 44 */
289, 213, 114, 616, /* 45 */
145, 109, 54, 308, /* 46 */
291, 223, 102, 616, /* 47 */
73, 57, 24, 154, /* 48 */
293, 233, 90, 616, /* 49 */
21, 17, 6, 44, /* 50 */
295, 243, 78, 616, /* 51 */
37, 31, 9, 77, /* 52 */
27, 23, 6, 56, /* 53 */
149, 129, 30, 308, /* 54 */
299, 263, 54, 616, /* 55 */
75, 67, 12, 154, /* 56 */
43, 39, 6, 88, /* 57 */
151, 139, 18, 308, /* 58 */
303, 283, 30, 616, /* 59 */
38, 36, 3, 77, /* 60 */
305, 293, 18, 616, /* 61 */
153, 149, 6, 308, /* 62 */
307, 303, 6, 616, /* 63 */
1, 1, 0, 2, /* 64 */
101, 105, 2, 208, /* 65 */
49, 53, 2, 104, /* 66 */
95, 107, 6, 208, /* 67 */
23, 27, 2, 52, /* 68 */
89, 109, 10, 208, /* 69 */
43, 55, 6, 104, /* 70 */
83, 111, 14, 208, /* 71 */
5, 7, 1, 13, /* 72 */
172, 181, 37, 390, /* 73 */
97, 76, 22, 195, /* 74 */
72, 41, 17, 130, /* 75 */
119, 47, 29, 195, /* 76 */
4, 1, 1, 6, /* 77 */
4, 1, 1, 6, /* 78 */
4, 1, 1, 6, /* 79 */
4, 1, 1, 6, /* 80 */
4, 1, 1, 6, /* 81 */
4, 1, 1, 6, /* 82 */
4, 1, 1, 6, /* 83 */
4, 1, 1, 6, /* 84 */
4, 1, 1, 6, /* 85 */
65, 18, 17, 100, /* 86 */
95, 29, 26, 150, /* 87 */
185, 62, 53, 300, /* 88 */
30, 11, 9, 50, /* 89 */
35, 14, 11, 60, /* 90 */
85, 37, 28, 150, /* 91 */
55, 26, 19, 100, /* 92 */
80, 41, 29, 150, /* 93 */
155, 86, 59, 300, /* 94 */
5, 3, 2, 10, /* 95 */
5, 3, 2, 10, /* 96 */
5, 3, 2, 10, /* 97 */
5, 3, 2, 10, /* 98 */
5, 3, 2, 10, /* 99 */
5, 3, 2, 10, /* 100 */
5, 3, 2, 10, /* 101 */
5, 3, 2, 10, /* 102 */
5, 3, 2, 10, /* 103 */
5, 3, 2, 10, /* 104 */
5, 3, 2, 10, /* 105 */
5, 3, 2, 10, /* 106 */
5, 3, 2, 10, /* 107 */
305, 176, 119, 600, /* 108 */
155, 86, 59, 300, /* 109 */
105, 56, 39, 200, /* 110 */
80, 41, 29, 150, /* 111 */
65, 32, 23, 120, /* 112 */
55, 26, 19, 100, /* 113 */
335, 152, 113, 600, /* 114 */
85, 37, 28, 150, /* 115 */
115, 48, 37, 200, /* 116 */
35, 14, 11, 60, /* 117 */
355, 136, 109, 600, /* 118 */
30, 11, 9, 50, /* 119 */
365, 128, 107, 600, /* 120 */
185, 62, 53, 300, /* 121 */
25, 8, 7, 40, /* 122 */
95, 29, 26, 150, /* 123 */
385, 112, 103, 600, /* 124 */
65, 18, 17, 100, /* 125 */
395, 104, 101, 600, /* 126 */
4, 1, 1, 6, /* 127 */
4, 1, 1, 6, /* 128 */
395, 104, 101, 600, /* 129 */
65, 18, 17, 100, /* 130 */
385, 112, 103, 600, /* 131 */
95, 29, 26, 150, /* 132 */
25, 8, 7, 40, /* 133 */
185, 62, 53, 300, /* 134 */
365, 128, 107, 600, /* 135 */
30, 11, 9, 50, /* 136 */
355, 136, 109, 600, /* 137 */
35, 14, 11, 60, /* 138 */
115, 48, 37, 200, /* 139 */
85, 37, 28, 150, /* 140 */
335, 152, 113, 600, /* 141 */
55, 26, 19, 100, /* 142 */
65, 32, 23, 120, /* 143 */
80, 41, 29, 150, /* 144 */
105, 56, 39, 200, /* 145 */
155, 86, 59, 300, /* 146 */
305, 176, 119, 600, /* 147 */
5, 3, 2, 10, /* 148 */
5, 3, 2, 10, /* 149 */
5, 3, 2, 10, /* 150 */
5, 3, 2, 10, /* 151 */
5, 3, 2, 10, /* 152 */
5, 3, 2, 10, /* 153 */
5, 3, 2, 10, /* 154 */
5, 3, 2, 10, /* 155 */
5, 3, 2, 10, /* 156 */
5, 3, 2, 10, /* 157 */
5, 3, 2, 10, /* 158 */
5, 3, 2, 10, /* 159 */
5, 3, 2, 10, /* 160 */
155, 86, 59, 300, /* 161 */
80, 41, 29, 150, /* 162 */
55, 26, 19, 100, /* 163 */
85, 37, 28, 150, /* 164 */
35, 14, 11, 60, /* 165 */
30, 11, 9, 50, /* 166 */
185, 62, 53, 300, /* 167 */
95, 29, 26, 150, /* 168 */
65, 18, 17, 100, /* 169 */
4, 1, 1, 6, /* 170 */
4, 1, 1, 6, /* 171 */
4, 1, 1, 6, /* 172 */
4, 1, 1, 6, /* 173 */
4, 1, 1, 6, /* 174 */
4, 1, 1, 6, /* 175 */
4, 1, 1, 6, /* 176 */
4, 1, 1, 6, /* 177 */
4, 1, 1, 6, /* 178 */
119, 47, 29, 195, /* 179 */
72, 41, 17, 130, /* 180 */
97, 76, 22, 195, /* 181 */
172, 181, 37, 390, /* 182 */
5, 7, 1, 13, /* 183 */
83, 111, 14, 208, /* 184 */
43, 55, 6, 104, /* 185 */
89, 109, 10, 208, /* 186 */
23, 27, 2, 52, /* 187 */
95, 107, 6, 208, /* 188 */
49, 53, 2, 104, /* 189 */
101, 105, 2, 208, /* 190 */
1, 1, 0, 2, /* 191 */
307, 303, 6, 616, /* 192 */
153, 149, 6, 308, /* 193 */
305, 293, 18, 616, /* 194 */
38, 36, 3, 77, /* 195 */
303, 283, 30, 616, /* 196 */
151, 139, 18, 308, /* 197 */
43, 39, 6, 88, /* 198 */
75, 67, 12, 154, /* 199 */
299, 263, 54, 616, /* 200 */
149, 129, 30, 308, /* 201 */
27, 23, 6, 56, /* 202 */
37, 31, 9, 77, /* 203 */
295, 243, 78, 616, /* 204 */
21, 17, 6, 44, /* 205 */
293, 233, 90, 616, /* 206 */
73, 57, 24, 154, /* 207 */
291, 223, 102, 616, /* 208 */
145, 109, 54, 308, /* 209 */
289, 213, 114, 616, /* 210 */
36, 26, 15, 77, /* 211 */
41, 29, 18, 88, /* 212 */
13, 9, 6, 28, /* 213 */
285, 193, 138, 616, /* 214 */
71, 47, 36, 154, /* 215 */
283, 183, 150, 616, /* 216 */
141, 89, 78, 308, /* 217 */
281, 173, 162, 616, /* 218 */
5, 3, 3, 11, /* 219 */
423, 256, 245, 924, /* 220 */
213, 130, 119, 462, /* 221 */
13, 8, 7, 28, /* 222 */
108, 67, 56, 231, /* 223 */
435, 272, 217, 924, /* 224 */
73, 46, 35, 154, /* 225 */
63, 40, 29, 132, /* 226 */
111, 71, 49, 231, /* 227 */
149, 96, 63, 308, /* 228 */
225, 146, 91, 462, /* 229 */
453, 296, 175, 924, /* 230 */
38, 25, 14, 77, /* 231 */
459, 304, 161, 924, /* 232 */
3, 2, 1, 6, /* 233 */
471, 304, 161, 936, /* 234 */
237, 148, 83, 468, /* 235 */
53, 32, 19, 104, /* 236 */
60, 35, 22, 117, /* 237 */
483, 272, 181, 936, /* 238 */
81, 44, 31, 156, /* 239 */
489, 256, 191, 936, /* 240 */
123, 62, 49, 234, /* 241 */
165, 80, 67, 312, /* 242 */
249, 116, 103, 468, /* 243 */
501, 224, 211, 936, /* 244 */
7, 3, 3, 13, /* 245 */
43, 15, 20, 78, /* 246 */
22, 6, 11, 39, /* 247 */
15, 3, 8, 26, /* 248 */
23, 3, 13, 39, /* 249 */
47, 3, 28, 78, /* 250 */
8, 0, 5, 13, /* 251 */
7, 0, 4, 11, /* 252 */
21, 0, 10, 31, /* 253 */
13, 0, 5, 18, /* 254 */
13, 0, 5, 18 /* 255 */
])
// Coefficients from "Improving mid-tone quality
// of variable-coefficient error diffusion using
// threshold modulation" by Zhou and Fang
coefficients_zhoufang = {
const keyLevels = [
0, 13, 0, 5,
1, 1300249, 0, 499250,
2, 213113, 287, 99357,
3, 351854, 0, 199965,
4, 801100, 0, 490999,
10, 704075, 297466, 303694,
22, 46613, 31917, 21469,
32, 47482, 30617, 21900,
44, 43024, 42131, 14826,
64, 36411, 43219, 20369,
72, 38477, 53843, 7678,
77, 40503, 51547, 7948,
85, 35865, 34108, 30026,
95, 34117, 36899, 28983,
102, 35464, 35049, 29485,
107, 16477, 18810, 14712,
112, 33360, 37954, 28685,
127, 35269, 36066, 28664
];
const coefficients_zhoufang = new Uint32Array(256 * 4);
// initiate start (and mirrored endpoint)
let keyPrev, rightPrev, downleftPrev, downPrev;
keyPrev = keyLevels[0]
rightPrev = coefficients_zhoufang[0] = coefficients_zhoufang[255 * 4 + 0] = keyLevels[1];
downleftPrev = coefficients_zhoufang[1] = coefficients_zhoufang[255 * 4 + 1] = keyLevels[2];
downPrev = coefficients_zhoufang[2] = coefficients_zhoufang[255 * 4 + 2] = keyLevels[3];
coefficients_zhoufang[3] = coefficients_zhoufang[255 * 4 + 3] = keyLevels[1] + keyLevels[2] + keyLevels[3];
for (let i = 4; i < keyLevels.length; i += 4) {
const key = keyLevels[i],
right = keyLevels[i+1],
downleft = keyLevels[i+2],
down = keyLevels[i+3];
const delta = (key - keyPrev);
for (let j = 1; keyPrev + j <= key; j++) {
const keyj = (keyPrev + j) * 4,
rightj = (right * j + rightPrev * (delta - j)) / delta | 0,
downleftj = (downleft * j + downleftPrev * (delta - j)) / delta | 0,
downj = (down * j + downPrev * (delta - j)) / delta | 0,
sum = rightj + downleftj + downj;
coefficients_zhoufang[keyj] = coefficients_zhoufang[255*4 - keyj] = rightj;
coefficients_zhoufang[keyj + 1] = coefficients_zhoufang[255*4 - keyj + 1] = downleftj;
coefficients_zhoufang[keyj + 2] = coefficients_zhoufang[255*4 - keyj + 2] = downj;
coefficients_zhoufang[keyj + 3] = coefficients_zhoufang[255*4 - keyj + 3] = sum;
}
keyPrev = key;
rightPrev = right,
downleftPrev = downleft;
downPrev = down;
}
return coefficients_zhoufang
}
modulation = {
const keyLevels = [
0, 0,
44, 0.34,
64, 0.50,
85, 1.00,
95, 0.17,
102, 0.5,
107, 0.7,
112, 0.79,
127, 1.00
];
const strengths = new Float64Array(256);
let keyPrev = 0, strengthPrev = 0;
for (let i = 2; i < keyLevels.length; i += 2) {
const key = keyLevels[i], strength = keyLevels[i+1];
const delta = key - keyPrev;
for (let j = 1; keyPrev + j <= key; j++) {
strengths[keyPrev + j] = strengths[255 - (keyPrev+j)] =
128 + (strength * j + strengthPrev * (delta - j)) / delta;
}
keyPrev = key, strengthPrev = strength;
}
// weirdly, this varies the threshold between 128 - 255, not
// 64 - 192 which would be around the middle.
// But that's what the paper does so I assume the kernels are
// optimized for it.
return (randomVal, v) => 0x80 + strengths[v] * randomVal;
}
// used to create a set of tiles
bayer = (x, y) => {
let v = 0;
y ^= x;
for (let i = 0; i < 4; ++i) {
v = (v << 2) | (x & 1) + ((y & 1) << 1);
x >>= 1;
y >>= 1;
}
return v >>> 0;
}
getBayer = (tile = (pixelWidth/16)|0) => {
// 16 by 16 tiles
const ctx = DOM.canvas(16*tile, 16*tile).getContext('2d');
for (let i = 0; i < 16; i++) {
for (let j = 0; j < 16; j++) {
let color = (bayer(j, i) & 255).toString(16);
ctx.fillStyle = `#${color}${color}${color}`;
ctx.fillRect(j*tile, i*tile, tile, tile);
}
}
return ctx.getImageData(0, 0, 16*tile, 16*tile);
}
import {render, renderSerpentine, getCtx, toU32Color, toLinear, tosRGB} from "@jobleonard/canvas-tools"
import {aadams1, aadams2, parrot, david2, doggo, borsodi, haeckel1} from "@jobleonard/test-images"
import {toTestImg} from "@jobleonard/test-image-tool"
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.