2a:null 2b:["$","title",null,{"children":"octree color quantization | Tom MacWright | Observable"}] 30:T1107,md`### Creating a bit mask The first element to talk about is _bit masking_, which is not as macho as it sounds but does tend to look pretty intimidating. The original implementation in Python said this: \`\`\`js let mask = 0x80 >> level; \`\`\` This is assigning a variable mask to the value 0x80, which is [a hexadecimal literal](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Grammar_and_types#Numeric_literals) for the number 128. Neither 0x80 or 128 really immediately say their purpose, unless you’re an old hand at bit masking or a fresh Computer Science graduate. What they’re getting at is that they’re ways to create an 8-bit number with the first bit a 1 and the rest 0s. So I changed the representation to JavaScript’s \`0b\` syntax that lets you write out binary numbers as, simply, binary. \`\`\`js let mask = 0b10000000 >> level; \`\`\` The \`>>\` is a right shift. Given that the _level_ is a number from 0 to 8, here are the potential shifted values: | Shift | Shifted (binary) | Shifted (decimal) | | ----- | ------- | ------------ | ${Array.from( { length: 8 }, (_, i) => `| ${i} | ${(0b10000000 >> i) .toString(2) .padStart(8, "0")} | ${0b10000000 >> i} |` ).join("\n")}
As you can see, shifting the value moves the 1 around: that’s it. But that’s not the end of this pretty dense passage: \`\`\`js if (color.red & mask) \`\`\` At first glance, this might look like a simple ‘and’ statement, but the one & means that it’s something much different: a bitwise AND expression. At some point, we all accidentally write one & for our comparisons and end up with a bug - often enough that [eslint has a popular rule that bans &, and its also-tricky friend, |](https://eslint.org/docs/rules/no-bitwise), on the assumption that most people are using them accidentally. But this is no accident. Breaking apart this expression: because we just created a mask that has only one bit as a 1, and we’re doing an AND comparison with the color value, then there are only two outcomes to this binary AND comparison: either the color value also has a \`1\` bit in that position, or it doesn’t. If it has the bit, then the bitwise AND ends up being the same value as the mask, which is a positive number. It it doesn’t have the bit, then it ends up as 0b00000000, which is simply 0. JavaScript treats 0 as false, and every other number value as true, so this if statement is shorthand for: \`\`\`js if (color.red & mask !== 0) \`\`\` Okay, so, the next step. _[GRIPE] I have a little gripe here: bit operations are already tricky enough, but programmers tend to inadvertently make them even harder by mixing and matching different number systems. They’ll throw in a 1, 2, or 4 (decimal) number for 0b001, 0b010, and 0b100, and then use hex for something else. It just seems unhelpful to not only have these tough concepts in play and also lack consistency. In my opinion, JavaScript has a binary number syntax - the 0b syntax - and we should use it whenever we’re expressing masks. [GRIPE OVER]_ Hey, look: it’s another binary operator. \`\`\`js index |= 0b100 \`\`\` This is shorthand for: \`\`\`js index = index | 0b100 \`\`\` And | is the binary OR. Where binary AND lets us ‘pick’ bits in the previous step, we’re using OR to ‘set’ bits. \`index | 0b100\` will always give you a new value for index that has that 1 bit lit up. So, after this series of if & OR statements, we’ll end up with a variety of different values, determine by which of the three bits are 1s. Given 2 possibilities and 3 bits, there are 2³ = 8 different values possible - the numbers 0 to 7 - which is uncoincidentally the number of children of a node. _[TRIVIA] A group of four bits is called a [nibble](https://en.wikipedia.org/wiki/Nibble) - get it - smaller than a byte - but as far as I can tell, a group of three bits has no name. [END TRIVIA]_ ### Now for the easier stuff I covered indexing first because it’s a lot of complexity in a short run of code. The rest of the system isn’t quite as dense. So let’s look at it, from the outside in. The very outside level is the Quantizer class. This is the interface to the whole magic: we add colors from the original palette with addColor(color), and get a reduced palette using makePalette(colorCount). `31:T709,class Quantizer { constructor() { this.levels = Array.from({ length: MAX_DEPTH }, () => []); this.root = new Node(0, this); } addColor(color) { this.root.addColor(color, 0, this); } makePalette(colorCount) { let palette = []; let paletteIndex = 0; let leafCount = this.leafNodes.length; for (let level = MAX_DEPTH - 1; level > -1; level -= 1) { if (this.levels[level]) { for (let node of this.levels[level]) { leafCount -= node.removeLeaves(); if (leafCount <= colorCount) break; } if (leafCount <= colorCount) break; this.levels[level] = []; } } for (let node of this.leafNodes) { if (paletteIndex >= colorCount) break; if (node.isLeaf) palette.push(node.color); node.paletteIndex = paletteIndex; paletteIndex++; } return palette; } *makePaletteIncremental(colorCount) { let palette = []; let paletteIndex = 0; let leafCount = this.leafNodes.length; for (let level = MAX_DEPTH - 1; level > -1; level -= 1) { if (this.levels[level]) { for (let node of this.levels[level]) { leafCount -= node.removeLeaves(); if (leafCount <= colorCount) break; } if (leafCount <= colorCount) break; this.levels[level] = []; } yield; } for (let node of this.leafNodes) { if (paletteIndex >= colorCount) break; if (node.isLeaf) palette.push(node.color); node.paletteIndex = paletteIndex; paletteIndex++; } yield; return palette; } get leafNodes() { return this.root.leafNodes; } addLevelNode(level, node) { this.levels[level].push(node); } getPaletteIndex(color) { return this.root.getPaletteIndex(color, 0); } }32:T7fb,class Node { constructor(level, parent) { this._color = new Color(0, 0, 0); this.pixelCount = 0; this.paletteIndex = 0; this.children = []; this._debugColor; if (level < MAX_DEPTH - 1) parent.addLevelNode(level, this); } get isLeaf() { return this.pixelCount > 0; } get leafNodes() { let leafNodes = []; for (let node of this.children) { if (!node) continue; if (node.isLeaf) { leafNodes.push(node); } else { leafNodes.push(...node.leafNodes); } } return leafNodes; } addColor(color, level, parent) { if (level >= MAX_DEPTH) { this._color.add(color); this.pixelCount++; return; } let index = getColorIndex(color, level); if (!this.children[index]) { this.children[index] = new Node(level, parent); } this.children[index].addColor(color, level + 1, parent); } getPaletteIndex(color, level) { if (this.isLeaf) { return this.paletteIndex; } let index = getColorIndex(color, level); if (this.children[index]) { return this.children[index].getPaletteIndex(color, level + 1); } else { for (let node of this.children) { return node.getPaletteIndex(color, level + 1); } } } removeLeaves() { let result = 0; for (let node of this.children) { if (!node) continue; this._color.add(node._color); this.pixelCount += node.pixelCount; result++; } this.children = []; return result - 1; } get debugColor() { if (this._debugColor) return this._debugColor; if (this.isLeaf) return this.color; let c = new Color(); let count = 0; function traverse(node) { for (let child of node.children) { if (child.isLeaf) { c.add(child._color); count++; } else { traverse(child); } } } traverse(this); return c.normalized(count); } get color() { return this._color.normalized(this.pixelCount); } }33:T524,{ const height = 180; const c = DOM.context2d(width, height, 1); const tree = d3 .tree() .size([width - 50, height - 50]) .nodeSize([spread, 15]); let q = new Quantizer(); for (let color of imageColors) q.addColor(color); let hierarchy = makeDigestible(q.root); const t = tree(hierarchy); const linkVertical = d3 .linkVertical() .context(c) .x(d => d.x + 25) .y(d => d.y + 25); function draw() { c.strokeStyle = "#ccc"; c.beginPath(); for (let link of t.links()) linkVertical(link); c.stroke(); const circle = d3 .symbol() .type(d3.symbolCircle) .size(50) .context(c); for (const node of hierarchy.descendants()) { c.beginPath(); c.save(); c.fillStyle = node.data.debugColor.toCSS(); c.translate(node.x + 25, node.y + 25); circle(node); c.fill(); c.restore(); } } function zoomed() { c.save(); c.clearRect(0, 0, width, height); c.translate(d3.event.transform.x, d3.event.transform.y); c.scale(d3.event.transform.k, d3.event.transform.k); draw(); c.restore(); } d3.select(c.canvas).call( d3 .zoom() .scaleExtent([1 / 2, 4]) .on("zoom", zoomed) ); draw(); c.canvas.style = "cursor: move"; return c.canvas; }34:[{"id":"8c8b0ef6283975ce0c3198d8fd5255d20fee835b14ea7b68845786dd4ee8527fbfa555e8009fe5664dc510260330ecf7be45b5ba51e330922e4d8a1ef977c85c","href":"https://static.observableusercontent.com/files/8c8b0ef6283975ce0c3198d8fd5255d20fee835b14ea7b68845786dd4ee8527fbfa555e8009fe5664dc510260330ecf7be45b5ba51e330922e4d8a1ef977c85c","name":"flower.png","type":"image/png","lastModified":1572462191412.511,"size":11159}] 2e:{"id":"4cdeea86de2d1f38","slug":"octree-color-quantization","title":"octree color quantization","thumbnail":"4acaf43f0da0ea929adac3af4a49b5b4b54d0dac8adc76940dafc9e673c5ed89","access_level":"public","create_time":"$D2018-09-06T18:28:02.378Z","update_time":"$D2019-10-30T19:03:17.601Z","view_time":null,"first_public_time":"$D2018-09-27T21:23:10.571Z","has_unpublished_edits":null,"fork":false,"stars":40,"starred":false,"owner":{"type":"team","id":"b47c3705cfcd7c1b","login":"tmcw","name":"Tom MacWright","avatar_url":"https://avatars-next.observableusercontent.com/669bdd774da8a1b9c1b7706ecbc1ea5136b9932c3d5e86b753aa5a098005f674","tier":"starter_2024"},"version":1353,"publish_version":1353,"role":null,"authored":false,"authors":[{"type":"individual","id":"0bf14b8d9c6eb88a","login":"tmcw","name":"Tom MacWright","avatar_url":"https://avatars-next.observableusercontent.com/669bdd774da8a1b9c1b7706ecbc1ea5136b9932c3d5e86b753aa5a098005f674","tier":null}],"members":[{"type":"individual","id":"0bf14b8d9c6eb88a","login":"tmcw","name":"Tom MacWright","avatar_url":"https://avatars-next.observableusercontent.com/669bdd774da8a1b9c1b7706ecbc1ea5136b9932c3d5e86b753aa5a098005f674","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":17,"collection":null,"type":"notebook","body":{"titling":"auto","title":"octree color quantization","cells":[{"id":0,"value":"md`# octree color quantization\n\n

\n\noctree color quantization is a fascinating and surprisingly simple algorithm that allows us to reduce the number of unique colors in an image while keeping the general look of the image. I ported [this Python implementation of octree quantization](https://github.com/delimitry/octree_color_quantizer) by [Dmitry Alimov](https://github.com/delimitry) to JavaScript and dove deep into the algorithm, yielding a few neat visualizations.\n\nThis also talks a bit about bit operations in JavaScript, if that’s of interest to you, and quietly features plenty of pixel-level canvas manipulation. Also some pretty pictures - there’s something for everyone.\n\nLet’s begin.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":171,"value":"{\n let c = DOM.context2d(flower.width, flower.height, 1);\n c.putImageData(flower.data, 0, 0);\n c.canvas.style = 'width:240px;height:240px;image-rendering:pixelated;';\n return present(c.canvas, 'Starting image');\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":405,"value":"md`The starting image is ${flower.width}pxｘ${flower.height}px, so contains ${flower.width * flower.height}px total pixels. We’re starting with a very lil’ image because it’ll make the results of this experiment easier to visualize. In real life, this algorithm, implemented in fast languages with lots of performance tricks, can handle big images.\n\nLet’s get all the unique colors in that image. It was exported from Adobe Photoshop with _Quick Export as PNG…_, which \\`file\\` tells me creates a \\`PNG image data, 64 x 64, 8-bit/color RGBA, non-interlaced\\` image.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":150,"value":"imageColors = {\n let colors = [];\n for (let i = 0; i < data.length; i += 4) {\n colors.push(new Color(data[i], data[i + 1], data[i + 2]));\n }\n return colors;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":424,"value":"uniqueColors = new Set(imageColors.map(color => color.toString()))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":466,"value":"md`Here are all the colors in this image, arranged in roughly order of intensity (actually just a RGB sum). That there are 3909 colors for a 4096px image indicates that this image hasn’t really been reduced in palette in any of the steps up till now: PNG supports a lot of colors, and this image has mostly uniquely-colored pixels.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":439,"value":"present(\n drawPalette(\n [...uniqueColors]\n .map(c => {\n let rgb = c.split(\",\").map(c => parseInt(c));\n rgb.push(rgb[0] + rgb[1] + rgb[2]);\n return rgb;\n })\n .sort((b, a) => a[3] - b[3])\n ),\n \"Raw palette\"\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":551,"value":"md`We’re going to reduce this palette significantly, to this: 200 colors.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":528,"value":"present(\n drawPalette(\n [...generatedPalette].map(c => c.array).sort((b, a) => a[3] - b[3])\n ),\n \"Generated palette\"\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":580,"value":"md`How does this magic happen? This is a technique of color quantization: taking a broad set of colors and simplifying it into a smaller set that tries to color all the same major hues while eliminating similar colors that make the image larger. This is especially important for inefficient file formats like the GIF, which quickly balloon in size if they contain lots of unique colors.\n\nAs the name suggests, octree quantization uses a tree datastructure that allows each node to have at most 8 (oc) children.\n\nThe idea of the tree is that each branch contains similar colors, so that we can ‘bin’ them together and decide whether a color is popular enough to be included.\n\n### Indexing\n\nThe method that it uses for this is one of the parts of the code where different sorts of complexity all intersect, so let’s really pick it apart.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":595,"value":"function getColorIndex(color, level) {\n let index = 0;\n let mask = 0b10000000 >> level;\n if (color.red & mask) index |= 0b100;\n if (color.green & mask) index |= 0b010;\n if (color.blue & mask) index |= 0b001;\n return index;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":605,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"$31","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":727,"value":"md`### Quantizer → Node → Color\n\nThe quantizer instance contains arrays of Nodes for each level, and each Node contains a Color object. It’s tricky, though, that a Color doesn’t just represent a single pixel color: because similar colors are added together and averaged, a Color object might contain RGB values way outside of the normal range because many pixel colors are combined.\n\nThe code for deriving indexes that we examined in such depth is crucial here: it determines where in the tree each color value ends up. The index from 0→8 determines which child it becomes at which level. The indexing tries to group similar colors, so that if we reduce the tree to various zones, each zone contains similar colors and the zones in overview cover all the essential colors & tones in the image.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":127,"value":"$32","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":676,"value":"md`### Color abstraction\n\nThere isn’t much to see here: simply a class that represents a color, and includes utilities for adding colors together.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":145,"value":"class Color {\n constructor(red = 0, green = 0, blue = 0) {\n this.red = red;\n this.green = green;\n this.blue = blue;\n }\n\n clone() {\n return new Color(this.red, this.green, this.blue);\n }\n\n // We use this to shuttle the color into a canvas element.\n // The final element, a RGB sum, is used to do a rough color sort.\n get array() {\n return [this.red, this.green, this.blue, this.red + this.green + this.blue];\n }\n\n // Fast, easily reversible stringification. Used\n // to create the initial list of unique colors.\n toString() {\n return [this.red, this.green, this.blue].join(\",\");\n }\n\n toCSS() {\n return `rgb(${[this.red, this.green, this.blue]\n .map(n => Math.floor(n))\n .join(\",\")})`;\n }\n normalized(pixelCount) {\n return new Color(\n this.red / pixelCount,\n this.green / pixelCount,\n this.blue / pixelCount\n );\n }\n add(color) {\n this.red += color.red;\n this.green += color.green;\n this.blue += color.blue;\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":741,"value":"md`Okay, that’s a lot of code, but not that much mystery. It’s a tree, linked together by the Node class’s children and tiered by the Quantizer class’s levels. I think from here on out, it’ll be cool to use visualization more. So here’s the tree. You’ll notice a few things: that not all nodes actually have 8 children - that’s just the maximum number. And as you go down the tree, you see the color distinctions become clearer, whereas the very top of the tree shows the general groups of colors.\n\nYou can drag the slider or drag & zoom the tree to see it all.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1064,"value":"viewof spread = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":756,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1104,"value":"md`So, if it isn’t obvious, the higher the number of children a node can have, the wider the tree, and this tree is very wide.\n\nI’m not sure this alternative, a radial chart, is _informative_ per-se, but I’ll be darned if it doesn’t look nice.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1108,"value":"{\n const height = width;\n const c = DOM.context2d(width, height);\n\n const tree = d3.tree().size([2 * Math.PI, width / 2]);\n\n let q = new Quantizer();\n for (let color of imageColors) q.addColor(color);\n let hierarchy = makeDigestible(q.root);\n\n const t = tree(hierarchy);\n\n const linkRadial = d3\n .linkRadial()\n .context(c)\n .angle(d => d.x)\n .radius(d => d.y);\n\n c.translate(width / 2, height / 2);\n\n function radialPoint({ x, y }) {\n return [y * Math.cos((x -= Math.PI / 2)), y * Math.sin(x)];\n }\n\n c.lineWidth = 5;\n\n for (let link of t.links()) {\n c.beginPath();\n c.strokeStyle = link.target.data.debugColor.toCSS();\n linkRadial(link);\n c.stroke();\n }\n\n return html`

${c.canvas}

`;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1163,"value":"md`Enough dilly-dallying. How do we actually quantize that tree into a smaller set of colors? The core palette-selection routine is this one, Quantizer.makePalette:\n\n\\`\\`\\`js\nmakePalette(colorCount) {\n let palette = []; // The output palette\n let paletteIndex = 0;\n let leafCount = this.leafNodes.length;\n for (let level = MAX_DEPTH - 1; level > -1; level -= 1) {\n if (this.levels[level]) {\n for (let node of this.levels[level]) {\n leafCount -= node.removeLeaves();\n if (leafCount <= colorCount) break;\n }\n if (leafCount <= colorCount) break;\n this.levels[level] = [];\n }\n }\n for (let node of this.leafNodes) {\n if (paletteIndex >= colorCount) break;\n if (node.isLeaf) palette.push(node.color);\n node.paletteIndex = paletteIndex;\n paletteIndex++;\n }\n return palette;\n}\n\\`\\`\\`\n\nThis traverses through the tree from the _bottom-up_ (MAX_DEPTH - 1 up), 'folding up' and combining leaves until it fills the palette array with enough colors.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1177,"value":"{\n const height = width;\n const c = DOM.context2d(width, height);\n\n const tree = d3.tree().size([2 * Math.PI, width / 2]);\n\n let q = new Quantizer();\n for (let color of imageColors) q.addColor(color);\n\n c.translate(width / 2, height / 2);\n\n for (let step of q.makePaletteIncremental(animatedPaletteSize)) {\n c.clearRect(-width, -height, width * 2, height * 2);\n let hierarchy = makeDigestible(q.root);\n const t = tree(hierarchy);\n const linkRadial = d3\n .linkRadial()\n .context(c)\n .angle(d => d.x)\n .radius(d => d.y);\n function radialPoint({ x, y }) {\n return [y * Math.cos((x -= Math.PI / 2)), y * Math.sin(x)];\n }\n c.lineWidth = 5;\n for (let link of t.links()) {\n c.beginPath();\n c.strokeStyle = link.target.data.debugColor.toCSS();\n linkRadial(link);\n c.stroke();\n }\n yield html`

${c.canvas}

`;\n await Promises.delay(1000);\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1243,"value":"viewof animatedPaletteSize = slider({\n min: 50,\n max: 500,\n step: 1,\n value: 200,\n submit: \"Play\",\n description: \"It’s cool. If you missed it, hit Replay ☝️.\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1263,"value":"md`This thinned-out tree gives us the final palette, which we showed earlier. Then, it’s just a matter of picking each pixel from the original image, finding its index in the generated palette, and remapping it to the palette-derived image.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1265,"value":"{\n let q = new Quantizer();\n for (let color of imageColors) q.addColor(color);\n let p = q.makePalette(animatedPaletteSize);\n let c = DOM.context2d(flower.width, flower.height, 1);\n let output = c.getImageData(0, 0, flower.width, flower.height);\n for (let i = 0; i < flower.data.data.length; i += 4) {\n let inputColor = new Color(\n flower.data.data[i],\n flower.data.data[i + 1],\n flower.data.data[i + 2]\n );\n let idx = q.getPaletteIndex(inputColor);\n let c = p[idx].array;\n output.data[i + 0] = c[0];\n output.data[i + 1] = c[1];\n output.data[i + 2] = c[2];\n output.data[i + 3] = 255;\n }\n c.putImageData(output, 0, 0);\n c.canvas.style = \"width:240px;height:240px;image-rendering:pixelated;\";\n return present(c.canvas, \"Quantized image\");\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1321,"value":"md`## 🧙‍ Tada\n\nThis is a very cool algorithm that quite certainly runs every day behind the scenes in software you use. I hope you’ve liked this interactive explanation! As an Observable notebook, you can click on the left of any of these bits and twiddle around with alternative approaches and find ways to make it cooler. Let me know if you do make anything with it! [@tmcw](https://twitter.com/tmcw)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":680,"value":"md`

\n\n## Utilities / nothing to see here`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1179,"value":"// This method makes the palette object digestible to d3.\n// The palette has undefined elements in its arrays, and d3 does not like\n// that one bit. So this filters them out.\nmakeDigestible = node => {\n function removeUndefChildren(node) {\n if (!node.children) return node;\n node.children =\n node.children && node.children.filter(Boolean).map(removeUndefChildren);\n if (!node.children.length) delete node.children;\n return node;\n }\n\n return d3.hierarchy(removeUndefChildren(node));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":355,"value":"q = {\n let q = new Quantizer();\n for (let color of imageColors) q.addColor(color);\n return q;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":329,"value":"generatedPalette = q.makePalette(200)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"import {loadImage} from \"@tmcw/raster-image-utilities\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1246,"value":"import {slider} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":744,"value":"d3 = require(\"d3\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":31,"value":"MAX_DEPTH = 8","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3,"value":"flower = loadImage(await FileAttachment(\"flower.png\").url())","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":159,"value":"data = flower.data.data","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":472,"value":"present = (\n thing,\n name\n) => html`

\n${thing}\n

${name}

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":501,"value":"drawPalette = colorList => {\n let dimension = Math.ceil(Math.sqrt(colorList.length));\n let c = DOM.context2d(dimension, dimension, 1);\n let data = c.getImageData(0, 0, dimension, dimension);\n let i = 0;\n for (let c of colorList) {\n let color = c instanceof Color ? c.toArray() : c;\n data.data[i] = color[0];\n data.data[i + 1] = color[1];\n data.data[i + 2] = color[2];\n data.data[i + 3] = 255;\n i += 4;\n }\n c.putImageData(data, 0, 0);\n c.canvas.style = `width: ${dimension * 4}px; height: ${dimension *\n 4}px;image-rendering: pixelated`;\n return c.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":633,"value":"html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":815,"value":"html``","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":690,"value":"/**\n\nStash\n\n // getNodesPixelCount() {\n // let sum_count = this.pixelCount;\n // for (let node of this.children) {\n // if (node) {\n // sum_count += node.pixelCount;\n // }\n // }\n // return sum_count;\n // }\n \n */","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W34","stdlib":"1"}} 2f:"$2e:body"