2b:null 2c:["$","title",null,{"children":"Ivan Kutsir’s “gaussBlur” | Fil | Observable"}] 31:T926,blur = { const { floor, max, min, round } = Math; function blurTransfer(V, r, n, vertical) { if (!r) return; // radius 0 is a noop const [source, target] = V, rc = Math.ceil(r), frac = (rc - r) / rc, frac_1 = r / rc, m = floor(source.length / n), w = 2 * rc + 1, w1 = 1 / w, ki = vertical ? m : 1, kj = vertical ? 1 : n, W = w * ki, R = rc * ki; for (let j = 0; j < m; ++j) { const k0 = kj * j, kn = k0 + ki * (n - 1); // faster loop for integer radius if (!frac) { for (let i = 0, sr = w * source[k0]; i < n + rc; ++i) { const k = ki * i + kj * j; sr += source[min(k, kn)] - source[max(k - W, k0)]; target[max(k - R, k0)] = sr * w1; } } else { for (let i = 0, sr = w * source[k0]; i < n + rc; ++i) { const k = ki * i + kj * j, index = max(k - R, k0); sr += source[min(k, kn)] - source[max(k - W, k0)]; target[index] = frac_1 * sr * w1 + frac * source[index]; } } } V.reverse(); // target becomes V[0] and will be used as source in the next iteration } return function blur() { var radius = 5, accessor, width, iterations = 3, direction = null; function blur(data) { const n = width || data.length, m = floor(data.length / n), V = [ accessor ? Float32Array.from(data, accessor) : Float32Array.from(data), new Float32Array(data.length) ]; for (var i = 0; i < iterations; i++) { if (direction !== "y" && n > 1) { blurTransfer(V, radius, n, false); } if (direction !== "x" && m > 1) { blurTransfer(V, radius, m, true); } } V[0].width = n; V[0].height = m; return V[0]; } blur.radius = _ => (_ === undefined ? radius : ((radius = +_), blur)); blur.width = _ => (_ === undefined ? width : ((width = round(+_)), blur)); blur.iterations = _ => _ === undefined ? iterations : ((iterations = +_), blur); blur.direction = _ => _ === undefined ? direction : ((direction = _), blur); blur.value = _ => typeof _ === "function" ? ((accessor = _), blur) : accessor; return blur; }; }32:T420,gaussBlur = { var radius = 5, accessor, width, iterations = 3, direction = null; return function blur() { function blur(data) { const n = width || data.length, m = Math.floor(data.length / n), V = [ accessor ? Float32Array.from(data, accessor) : Float32Array.from(data), new Float32Array(data.length) ]; for (var i = 0; i < data.length; i++) V[1][i] = V[0][i]; gaussBlur_4(V[0], V[1], n, m, radius); V.reverse(); V[0].width = n; V[0].height = m; return V[0]; } blur.radius = _ => (_ === undefined ? radius : ((radius = +_), blur)); blur.width = _ => _ === undefined ? width : ((width = Math.round(+_)), blur); blur.iterations = _ => _ === undefined ? iterations : ((iterations = +_), blur); blur.direction = _ => _ === undefined ? direction : ((direction = _), blur); blur.value = _ => typeof _ === "function" ? ((accessor = _), blur) : accessor; return blur; }; }33:T9b4,// Ivan Kutsir's algo // http://blog.ivank.net/fastest-gaussian-blur.html gaussBlur_4 = { return function gaussBlur_4(scl, tcl, w, h, r) { var bxs = boxesForGauss(r, 3); boxBlur_4(scl, tcl, w, h, (bxs[0] - 1) / 2); boxBlur_4(tcl, scl, w, h, (bxs[1] - 1) / 2); boxBlur_4(scl, tcl, w, h, (bxs[2] - 1) / 2); }; function boxBlur_4(scl, tcl, w, h, r) { for (var i = 0; i < scl.length; i++) tcl[i] = scl[i]; boxBlurH_4(tcl, scl, w, h, r); boxBlurT_4(scl, tcl, w, h, r); } function boxBlurH_4(scl, tcl, w, h, r) { var iarr = 1 / (r + r + 1); for (var i = 0; i < h; i++) { var ti = i * w, li = ti, ri = ti + r; var fv = scl[ti], lv = scl[ti + w - 1], val = (r + 1) * fv; for (var j = 0; j < r; j++) val += scl[ti + j]; for (var j = 0; j <= r; j++) { val += scl[ri++] - fv; tcl[ti++] = val * iarr; } for (var j = r + 1; j < w - r; j++) { val += scl[ri++] - scl[li++]; tcl[ti++] = val * iarr; } for (var j = w - r; j < w; j++) { val += lv - scl[li++]; tcl[ti++] = val * iarr; } } } function boxBlurT_4(scl, tcl, w, h, r) { var iarr = 1 / (r + r + 1); for (var i = 0; i < w; i++) { var ti = i, li = ti, ri = ti + r * w; var fv = scl[ti], lv = scl[ti + w * (h - 1)], val = (r + 1) * fv; for (var j = 0; j < r; j++) val += scl[ti + j * w]; for (var j = 0; j <= r; j++) { val += scl[ri] - fv; tcl[ti] = val * iarr; ri += w; ti += w; } for (var j = r + 1; j < h - r; j++) { val += scl[ri] - scl[li]; tcl[ti] = val * iarr; li += w; ri += w; ti += w; } for (var j = h - r; j < h; j++) { val += lv - scl[li]; tcl[ti] = val * iarr; li += w; ti += w; } } } function boxesForGauss(sigma, n) { // standard deviation, number of boxes var wIdeal = Math.sqrt((12 * sigma * sigma) / n + 1); // Ideal averaging filter width var wl = Math.floor(wIdeal); if (wl % 2 == 0) wl--; var wu = wl + 2; var mIdeal = (12 * sigma * sigma - n * wl * wl - 4 * n * wl - 3 * n) / (-4 * wl - 4); var m = Math.round(mIdeal); // var sigmaActual = Math.sqrt( (m*wl*wl + (n-m)*wu*wu - n)/12 ); var sizes = []; for (var i = 0; i < n; i++) sizes.push(i < m ? wl : wu); return sizes; } }34:T89e,// original code from D3 mmblur1 = { function blurX(source, target, r) { var n = source.width, m = source.height, w = (r << 1) + 1; for (var j = 0; j < m; ++j) { for (var i = 0, sr = 0; i < n + r; ++i) { if (i < n) { sr += source.data[i + j * n]; } if (i >= r) { if (i >= w) { sr -= source.data[i - w + j * n]; } target.data[i - r + j * n] = sr / Math.min(i + 1, n - 1 + w - i, w); } } } } // TODO Optimize edge cases. // TODO Optimize index calculation. // TODO Optimize arguments. function blurY(source, target, r) { var n = source.width, m = source.height, w = (r << 1) + 1; for (var i = 0; i < n; ++i) { for (var j = 0, sr = 0; j < m + r; ++j) { if (j < m) { sr += source.data[i + j * n]; } if (j >= r) { if (j >= w) { sr -= source.data[i + (j - w) * n]; } target.data[i + (j - r) * n] = sr / Math.min(j + 1, m - 1 + w - j, w); } } } } return function blur(source, r, n) { if (n === undefined) n = source.length; const m = source.length / n; var values0 = Float32Array.from(source), values1 = new Float32Array(n * m); blurX( { width: n, height: m, data: values0 }, { width: n, height: m, data: values1 }, r ); blurY( { width: n, height: m, data: values1 }, { width: n, height: m, data: values0 }, r ); blurX( { width: n, height: m, data: values0 }, { width: n, height: m, data: values1 }, r ); blurY( { width: n, height: m, data: values1 }, { width: n, height: m, data: values0 }, r ); blurX( { width: n, height: m, data: values0 }, { width: n, height: m, data: values1 }, r ); blurY( { width: n, height: m, data: values1 }, { width: n, height: m, data: values0 }, r ); return Object.assign(values0, { width: n, height: m }); }; // this is the true function in d3 /* function blur(source, r) { const k = 2; return blur(source, r >> k); }; */ }35:[] 2f:{"id":"d85e3cc1db985503","slug":null,"title":"Ivan Kutsir’s “gaussBlur”","thumbnail":"b42009b00eb7988469efea7dc7797087d186d2713987136a3ce9291009bd83c3","access_level":"unlisted","create_time":"$D2020-06-27T12:36:02.065Z","update_time":"$D2020-06-27T12:51:30.253Z","view_time":null,"first_public_time":null,"has_unpublished_edits":null,"fork":{"id":"6b810e3f43ae255e","slug":"moving-average-blur","title":"Moving average blur","owner":{"id":"da2a32154638c457","login":"fil","name":"Fil"}},"stars":1,"starred":false,"owner":{"type":"team","id":"da2a32154638c457","login":"fil","name":"Fil","avatar_url":"https://avatars-next.observableusercontent.com/d5b1777907117a2bdf2a07eb98600d7a9beb21639fde42b9753e95c88c7731a6","tier":"starter_2024"},"version":1444,"publish_version":1444,"role":null,"authored":false,"authors":[{"type":"individual","id":"45a379fcfcb14253","login":"fil","name":"Fil","avatar_url":"https://avatars-next.observableusercontent.com/d5b1777907117a2bdf2a07eb98600d7a9beb21639fde42b9753e95c88c7731a6","tier":null}],"members":[{"type":"individual","id":"45a379fcfcb14253","login":"fil","name":"Fil","avatar_url":"https://avatars-next.observableusercontent.com/d5b1777907117a2bdf2a07eb98600d7a9beb21639fde42b9753e95c88c7731a6","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Ivan Kutsir’s “gaussBlur”","cells":[{"id":0,"value":"md`# Ivan Kutsir’s “gaussBlur”`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1403,"value":"md`As suggested by Mikhail Kotelnikov in [this comment](https://observablehq.com/@fil/moving-average-blur), here is algorithm 4 from http://blog.ivank.net/fastest-gaussian-blur.html :`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1395,"value":"show(\n gaussBlur()\n .width(n)\n .radius(5)\n)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1407,"value":"md`Compare with the proposal for d3.blur:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":189,"value":"show(\n blur()\n .width(n)\n .radius(5)\n) // new code","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":741,"value":"n = 400","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":742,"value":"m = 300","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":71,"value":"source = Float32Array.from({ length: n * m }, Math.random)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":266,"value":"show(source => mmblur1(source, 5, n)) // calls the code extracted from d3-contour, for comparison","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":878,"value":"md`The moving average procedure also works in 1-D, resulting in a smooth approximation of data (here, a random walk). Note that this diverges a little from a previous [“Moving average” notebook](https://observablehq.com/@d3/moving-average): in our case the averaged data is defined everywhere on the domain (instead of losing the extremities), and the values are centered instead of being pushed at the end of the interval they average.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":848,"value":"embed(\n {\n title: \"1D smoothing of a random walk\",\n width: Math.max(300, width * 0.7),\n height: 250,\n layer: [\n {\n mark: \"line\",\n data: {\n values: [\n values.map((y, i) => ({\n x: i,\n y,\n type: \"source\"\n })),\n Array.from(blurred, (y, i) => ({\n x: i,\n y,\n type: \"blurred\"\n })),\n [\n { x: 0, y: 0, type: \"interval\" },\n { x: 2 * radius, y: 0, type: \"interval\" }\n ]\n ].flat()\n },\n encoding: {\n x: {\n field: \"x\",\n type: \"quantitative\"\n },\n y: {\n field: \"y\",\n type: \"quantitative\"\n },\n stroke: { field: \"type\", sort: null }\n }\n }\n ]\n },\n { actions: false }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":867,"value":"viewof radius = slider({\n min: 0,\n max: 15,\n value: 5,\n step: 0.01,\n description: \"radius (default: 5)\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1058,"value":"viewof iterations = slider({\n min: 1,\n max: 10,\n value: 3,\n step: 1,\n description: \"iterations (default: 3)\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":862,"value":"// random walk\nvalues = {\n let x = 1;\n return Array.from({ length: 300 }, () => (x += Math.sin(1e6 * x)));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":883,"value":"blurred = blur()\n .radius(radius)\n .iterations(iterations)(values)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1132,"value":"PROFILE = md`## Profile\n\nThe chart below shows how one Dirac signal (value 1 in position 0) is blurred with radius ${profile_radius} and ${profile_iterations} iterations. Note that the computation time is in ${tex`\\mathcal{O}`}(iterations) and independent of the radius—so you do want to keep it to the strict minimum (3 for a nice-looking bell-shaped curve).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1141,"value":"embed(\n {\n title: `Blurring profile for radius=${profile_radius} with ${profile_iterations} iterations`,\n width: Math.max(300, width * 0.7),\n height: 270,\n layer: [\n {\n mark: \"bar\",\n data: {\n values: Array.from(profile).map((y, i) => ({\n x: i - 29,\n y,\n type: \"profile\"\n }))\n },\n encoding: {\n x: {\n field: \"x\",\n type: \"quantitative\"\n },\n y: {\n field: \"y\",\n type: \"quantitative\",\n scale: { nice: false }\n }\n //stroke: { field: \"type\", sort: null }\n }\n }\n ]\n },\n { actions: false }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1145,"value":"viewof profile_radius = slider({\n min: 0,\n max: 15,\n value: 5,\n description: \"radius (default: 5)\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1149,"value":"viewof profile_iterations = slider({\n min: 0,\n max: 10,\n value: 3,\n step: 1,\n description: \"iterations (default: 3)\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1133,"value":"profile = gaussBlur()\n .iterations(profile_iterations)\n .radius(profile_radius)\n .width(1)(Float32Array.from({ length: 59 }, (d, i) => i === 29))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1237,"value":"d3.sum(profile)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":923,"value":"md`## API\n\nThe current API of this test version is:\n~~~{js}\nconst B = blur()\n .value([accessor = d => d])\n .radius([radius = 5])\n .iterations([iterations = 3])\n .width([width = 1])\n .direction([direction = null|\"x\"|\"y\"])\nB(data);\n~~~\n\nThe final API is still pending.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":457,"value":"blur()([0, 1, 2, 3, 8, 10, 12, 27])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":624,"value":"blur()\n .radius(2)\n .iterations(1)\n .width(4)([0, 1, 2, 3, 8, 10, 12, 27])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1036,"value":"md`A *value* accessor allows complex input data and intermediate computations:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1017,"value":"data = Array.from(values, (d, i) => ({ value: d, index: i }))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1008,"value":"blur().value(d => Math.sin(d.value))(data)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1050,"value":"md`And the function accepts iterables:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1046,"value":"blur()(new Set(values.slice().sort()))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1216,"value":"md`### Playing with 2D data`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":671,"value":"md`The graphs below show 1D blurring applied to 2D data (don't ask), and the {iterations, direction} options that the new function allows:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":629,"value":"show(blur()) // 1D horizontal","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":714,"value":"show(\n blur()\n .width(n)\n .direction(\"y\")\n)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1076,"value":"// compose a heavy \"x\" blur with a light \"y\" blur\nshow(data =>\n blur()\n .width(n)\n .radius(1)\n .iterations(1)\n .direction(\"y\")(\n blur()\n .width(n)\n .radius(20)\n .iterations(4)\n .direction(\"x\")(data)\n )\n)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1379,"value":"md`### Fractional blurring`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1122,"value":"show(\n blur()\n .width(n)\n .radius(.5)\n)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":284,"value":"$31","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1387,"value":"$32","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1383,"value":"$33","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":264,"value":"$34","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":111,"value":"d3 = require(\"d3@5\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":870,"value":"import { slider } from \"@jashkenas/inputs\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":847,"value":"embed = require(\"vega-embed@6\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":844,"value":"html``","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":110,"value":"function show(blur, { nn = n, runs = 10 } = {}) {\n const m = source.length / nn;\n const scale = Math.pow(2, -Math.ceil(Math.log2(Math.max(nn, m) / 400)));\n\n const w = scale * n,\n h = scale * m;\n const x = d3.scaleLinear([0, nn], [0, w]),\n y = d3.scaleLinear([0, m], [0, h]);\n const c = d3.scaleSequential(d3.interpolateGreys);\n\n const context = DOM.context2d(width, h);\n\n let blurred;\n let t = performance.now();\n for (let i = 0; i < runs; i++) blurred = blur(source);\n t = (performance.now() - t) / runs;\n\n // a rather inefficient way to show the output :-)\n function draw(array) {\n for (let k = 0; k < array.length; k++) {\n const i = k % nn,\n j = Math.floor(k / nn);\n context.fillStyle = c(array[i + n * j]);\n context.fillRect(x(i), y(j), x(i + 1) - x(i), y(j + 1) - y(j));\n }\n }\n\n draw(source);\n context.translate(x(nn) + 50, 0);\n context.fillStyle = \"red\";\n context.fillText(`${+t.toFixed(1)}ms`, -40, 10);\n draw(blurred);\n\n return context.canvas;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 30:"$2f:body"