2e:null 2f:["$","title",null,{"children":"Labeling connected components | Bryan Gin-ge Chen | Observable"}] 34:T9ba,{ const div = md`## Introduction Suppose you want [to find the connected components](https://en.wikipedia.org/wiki/Connected-component_labeling) in a binary image. For instance, maybe you want to [count the number of objects on a table](https://blogs.mathworks.com/steve/2006/11/17/labeling-labeled-objects/) or [track some swarming bacterial cells](http://www.rowland.harvard.edu/labs/bacteria/movies/swarmecoli.php). Given a grid of black and white squares (1's and 0's in an array, if you prefer), each connected component (cluster) is a group of black squares that are all neighbors of each other. There are two natural choices for the neighbor relationships on a grid: - the nearest-neighbor (NN, or ["von Neumann"](https://en.wikipedia.org/wiki/Von_Neumann_neighborhood)) relationship , or - the next-nearest-neighbor (NNN, or ["Moore"](https://en.wikipedia.org/wiki/Moore_neighborhood)) relationship . In the [how it works](#howItWorks) section, I explain and demo an algorithm that labels all the squares in each cluster (under either definition) with a different marker (e.g. a number from 1 to *N*). First though, here are a few images showing the output of this algorithm, which colors each "foreground" cluster with a different (random) color. The first example uses cells from Tom MacWright's awesome notebook ["Dithering"](https://beta.observablehq.com/@tmcw/dithering) to illustrate the difference between these two choices; in particular, how most of the connected components merge together when you go from NN to NNN.` return div; }35:Tab5,viewof ditherExamples = { if (navigator.userAgent.match('HeadlessChrome')) return; const div = html`

`; const w = Math.min(Math.floor(width/3), dumbError.width); const h = (dumbError.height/dumbError.width)*w; const ctx = DOM.canvas(w * 3, h + 20).getContext('2d'); ctx.canvas.style.imageRendering = 'pixelated'; ctx.font = `${Math.min(12, w/15)}px monospace`; ctx.fillText('Random', 5, 15); ctx.fillText('Dumb Error', w+5, 15); ctx.fillText('Floyd Steinberg', 2*w+5, 15); function labelClone(ctx) { const clone = ctx.getImageData(0, 0, w, h); for (let x = 0; x < clone.data.length; x += 4) { clone.data[x] = clone.data[x + 1] = clone.data[x + 2] = clone.data[x + 3] = (clone.data[x] + clone.data[x + 1] + clone.data[x + 2]) > 0 ? 255 : 0; } return labelComponentsImageData(clone, nn.checked ? 'NN' : 'NNN', (num) => colorArrayTo4Tuple(colorArray2,num)); } function update() { if (labelCheck.checked) { const ctx0 = DOM.canvas(w, h).getContext('2d'); ctx0.drawImage(randomDither, 0, 0); const randomDitherLabel = labelClone(ctx0, randomDither); ctx.putImageData(randomDitherLabel.colored, 0, 20); ctx0.drawImage(dumbError, 0, 0); const dumbErrorLabel = labelClone(ctx0, dumbError); ctx.putImageData(dumbErrorLabel.colored, w, 20); ctx0.drawImage(floydSteinberg, 0, 0); const floydSteinbergLabel = labelClone(ctx0, floydSteinberg); ctx.putImageData(floydSteinbergLabel.colored, 2*w, 20); div.value={randomDitherLabel, dumbErrorLabel, floydSteinbergLabel}; div.dispatchEvent(new CustomEvent('input')); } else { ctx.drawImage(randomDither, 0, 20); ctx.drawImage(dumbError, w, 20); ctx.drawImage(floydSteinberg, 2*w, 20); div.value={randomDither, dumbError, floydSteinberg}; div.dispatchEvent(new CustomEvent('input')); } } const nn = div.querySelector('#nn2'); const neighbForm = div.querySelector('#neighbForm2'); const labelCheck = div.querySelector('#label2'); neighbForm.onchange = update; labelCheck.oninput = () => { mutable label2 = labelCheck.checked; update(); }; update(); div.appendChild(ctx.canvas); return div; }36:Tddd,viewof thresholdLabels = { if (navigator.userAgent.match('HeadlessChrome')) return; const div = html`

threshold: invert `; const height = Math.floor(image.height/image.width*width); const ctx = DOM.canvas(width, height).getContext('2d'); ctx.drawImage(image, 0,0, width,height); const origImage = ctx.getImageData(0,0, width,height); const radio = div.querySelector('#radioForm'); const orig = div.querySelector('#orig'); const thresh = div.querySelector('#thresh'); const threshRange = div.querySelector('#threshRange'); const neighbForm = div.querySelector('#neighbForm'); const nn = div.querySelector('#nn'); const invert = div.querySelector('#invert'); function update() { if (orig.checked) { div.value = image; div.dispatchEvent(new CustomEvent('input')); ctx.drawImage(image, 0,0, width, height); return; } // code from https://beta.observablehq.com/@tmcw/dithering const clone = new ImageData(new Uint8ClampedArray(origImage.data), width, height); for (let x = 0; x < clone.data.length; x += 4) { clone.data[x] = clone.data[x + 1] = clone.data[x + 2] = (clone.data[x] + clone.data[x + 1] + clone.data[x + 2]) > threshRange.valueAsNumber ? (invert.checked ? 0 : 255) : (invert.checked ? 255 : 0); if (!thresh.checked) clone.data[x + 3] = clone.data[x]; } if (thresh.checked) { div.value = clone; div.dispatchEvent(new CustomEvent('input')); ctx.putImageData(clone, 0, 0); } else { const cloneLabel = labelComponentsImageData(clone, nn.checked ? 'NN' : 'NNN', (num) => colorArrayTo4Tuple(colorArray3,num)); div.value = cloneLabel; div.dispatchEvent(new CustomEvent('input')); ctx.putImageData(cloneLabel.colored, 0, 0); } } radio.onchange = (event) => { if (orig.checked) { mutable radio1 = 'orig'; } else { mutable radio1 = thresh.checked ? 'thresh' : 'label'; } update(); }; threshRange.oninput = () => { mutable threshVal = threshRange.valueAsNumber; update(); }; neighbForm.onchange = () => { mutable neighb1 = nn.checked ? 'nn' : 'nnn'; update(); } invert.onchange = () => { mutable invertCheckbox = invert.checked; update(); }; update(); div.insertBefore(ctx.canvas, div.firstChild); return div; }37:Tbd4,viewof demo = { if (navigator.userAgent.match('HeadlessChrome')) return; const size = 25; const num = 15; const genD = algHistory[pt]; const div = drawDemo(testperc, genD, colorArray, num, num, size); const svg = d3.select(div).select('svg').select('g'); const right = svg.append('g') .attr('transform', `translate(${num*size})`) .append(() => uFviz); // hover events which couple left and right const dataLabeled = []; genD.labeled.forEach((col, x) => col.forEach((d, y) => { if (d) dataLabeled.push({x,y,key:d}) })); const labeledBoxG = svg.select('.labeledBoxes'); const labeledBoxes = labeledBoxG.selectAll("rect").data(dataLabeled); labeledBoxes.selectAll('rect').attr('stroke-width', 1) .attr("stroke", "pink"); const tabBoxG = svg.select('.tabBoxes'); const tabBoxes = tabBoxG.selectAll("rect"); function isWhiteBox() { return this.getAttribute('fill') !== colorArray[1]; } const strokeW = circleRad / 3; right.selectAll('.highlight').remove(); const circs = right.select('g').selectAll('g').data(dataLabels, d => d.key); function clear() { svg.selectAll('.highlight').remove(); right.selectAll('.highlight').remove(); tabBoxes.filter(isWhiteBox) .attr('stroke', 'white'); } function makeBox(key) { const boxesWithKey = dataLabeled.filter(({key:bkey}) => bkey === key); const offset = 3; for (const dat of boxesWithKey) { svg.append('rect') .classed('highlight', true) .attr('fill', 'none') .attr('x', dat.x*size + offset) .attr('y', dat.y*size + offset) .attr('height', size - 2*offset) .attr('width', size - 2*offset) .attr('stroke-width', 2) .attr('stroke', 'white'); } } function makeCirc(dat) { circs.filter(d => d.key === dat.key) .append('circle') .classed('highlight', true) .attr('cx', 0) .attr('cy', 0) .attr('r', circleRad * (dat.rank/5 + 1) + 7) .attr('fill', 'none') .attr('stroke-width', 4) .attr('stroke', 'lightgreen'); } function highlightCurr() { clear(); const currKey = genD.currLabel; const dat = dataLabels.find(({key}) => currKey === key); if (dat) { makeCirc(dat); makeBox(currKey); } } function labeledBoxOver() { clear(); const boxKey = d3.select(this).datum().key; makeBox(boxKey); const dat = dataLabels.find(({key}) => boxKey === key); makeCirc(dat); } labeledBoxes.on('mouseenter', labeledBoxOver); tabBoxes.on('mouseenter', highlightCurr); svg.on('mouseleave', highlightCurr); function circOver() { clear(); const dat = d3.select(this).datum(); makeCirc(dat); if (dat.key !== 0) makeBox(dat.key); else { tabBoxes.filter(isWhiteBox) .attr('stroke', 'gray'); } } circs.on('mouseenter.outlineLeft mouseover.outlineLeft', circOver); circs.on('mouseout.outlineLeft', highlightCurr); highlightCurr(); return div; }38:T51f,{ const size = 24; const div = md`The algorithm used in this notebook to label connected components is the [Hoshen–Kopelman algorithm](https://en.wikipedia.org/wiki/Hoshen%E2%80%93Kopelman_algorithm) / two-pass algorithm. Its steps are visualized above; on the left is [a random binary image](#testperc) with the algorithm's "current" labeling overlaid. Each disk on the right corresponds to the label of some dark squares on the right (except for ${html` `} which corresponds to the background). Linked disks are part of the same connected component. Hover over disks (grid squares) to see the corresponding labeled squares (disks). As you step forwards in time, new components are discovered by the algorithm (disks are added on the right) and known components are found to be the same (disks are linked together).`; return div; }39:Ta7c,description = md`The H-K algorithm relies on the [union-find data structure](/@bryangingechen/union-find-data-structure). All you need to know here is that this data structure can perform each of the following three operations in [nearly-constant time](https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Time_complexity): - *Make*: creates a new "set" in the data structure that will serve as a possible label, - *Link*: given two labels, it marks them as being part of the same connected component, and - *Find*: given a label, it returns a canonical label for its connected component. There are 2 stages to the H-K algorithm. I'll describe how it works for NN clusters first. In the first stage, the algorithm iterates over all the black squares in the array, by proceeding from top to bottom within each column, and then from left to right over all the columns. Then the current black square's neighbors to the left and above are considered (if they exist): - If neither of those two are black, then: - *Make* a new set in the union-find data structure, - the current square is given the label of the new set, and - the algorithm proceeds to the next square. - If one of the two left and above neighbors is black, then: - a *Find* operation is performed on the neighbor's label, - the current square is given the returned label, and - the algorithm proceeds to the next square. - If both of those two neighbors is black, then: - a *Link* operation is performed on the labels of the two neighbors, - the current square is given the label of the left square, and - the algorithm proceeds to the next square. At the end of this stage, all of the black squares have been assigned labels, but not all of the labels are final. There may still be some clusters with more than one label. In the second stage, the algorithm iterates over all the black squares in the array again, but simply updates the squares label to the output of a *Find* operation on its current label. When this is finished, each of the clusters will consist of squares with the same label. For NNN clusters, the only difference is that in the first stage, one has to consider not just the left neighbor and the neighbor above, but also the diagonal neighbors to the upper left and upper right as well. Then, *Link* operations are performed whenever more than one of the neighbors in the list [left, above, upper left, upper right] is black. Everything else is similar. Note that since triangular grids are equivalent to square grids with all NW-SE diagonal edges added, we can also find clusters on those grids as well by considering neighbors in the list [left, above, upper left].`3a:T8dd,md`## API This notebook provides two connected-component functions that you can import, one that labels 2D arrays, and one that labels [\`ImageData\` objects](https://developer.mozilla.org/en-US/docs/Web/API/Canvas_API/Tutorial/Pixel_manipulation_with_canvas): \`\`\`js import {labelComponents, labelComponentsImageData} from '@bryangingechen/labeling-connected-components' \`\`\` \`labelComponents(array[, type])\`: Returns an object containing \`{labeled, labels}\`, where \`labeled\` is a 2D array of the same size as \`array\` with all nonzero entries replaced with integers marking NN clusters if \`type\` is omitted or equal to \`"NN"\` and NNN clusters if \`type\` is \`"NNN"\`. If \`type\` is \`"T"\`, then the grid is treated as a triangular lattice. \`labels\` is the internally used union-find object. \`labelComponentsImageData(imageData[, type][, colorFunc])\`: If \`colorFunc\` is omitted, returns an object \`{labeled, labels}\`, where \`labeled\` is an [\`ImageData\`](https://developer.mozilla.org/en-US/docs/Web/API/ImageData) object with the same dimensions as \`imageData\` where all nonwhite pixels (colors not equal to \`rgba(255,255,255,1.0)\`) are replaced by "pixels" where the \`r,g,b,a\` values encode integer labels (see [\`convertTo4Tuple\`](#convertTo4Tuple) and [getFromTup](#getFromTup)) marking NN clusters if \`type\` is \`"NN"\` and NNN clusters if \`type\` is \`"NNN"\`. If \`type\` is \`"T"\`, then the grid is treated as a triangular lattice. \`labels\` is the underlying union-find object. (These 4-tuples of integers between 0 and 255 arise from [the way that pixels are encoded](https://developer.mozilla.org/en-US/docs/Web/API/ImageData/data) in a \`Uint8ClampedArray\` in the \`ImageData\` object.) If \`colorFunc\` is a function that maps integer labels to 4-tuples of integers between 0 and 255 (representing \`r\`, \`g\`, \`b\`, and \`a\` in an rgba color) then the returned object will also contain have a key \`colored\` associated to an \`ImageData\` object where the pixels are the result of applying \`colorFunc\` to the integer labels. For example, the three sub-objects in the object below are the output of \`labelComponentsImageData\` when applied to the 3 sub-images in the "dithering" graphic above:`3b:T7f5,function drawDemo(tab, genD, colorArray, X, Y) { const size = 25; const div = d3.select(html`

`); const svg = div.append("svg") .attr("width", width) .attr("height", (Y*width)/(2*X)) .attr("viewBox", `0 0 ${2*X*size} ${Y*size}`) .append('g'); const messageText = div.append("div") .attr("font-size", "16px") .attr("font-family", "serif") .attr("text-anchor", "middle") .attr("color", "currentColor") .html(genD.message); // background boxes let dataTab = []; tab.forEach((col, x) => col.forEach((d, y) => dataTab.push({x,y,key:d}))); const tabBoxes = svg.append("g") .classed('tabBoxes', true) .selectAll("rect").data(dataTab).enter().append("rect") .attr("x", d => d.x*size) .attr("y", d => d.y*size) .attr("width", size) .attr("height", size) .attr("fill-opacity", 0.3) .attr("fill", d => colorArray[d.key]); tabBoxes.append('title') .text(d => (d.key ? 'unlabeled filled' : 'unfilled')); // labeled boxes let dataLabeled = []; genD.labeled.forEach((col, x) => col.forEach((d, y) => { if (d) dataLabeled.push({x,y,key:d}) })); const labeledBoxes = svg.append("g") .classed('labeledBoxes', true) .selectAll("rect").data(dataLabeled).enter().append("rect") .attr("x", d => d.x*size) .attr("y", d => d.y*size) .attr("width", size) .attr("height", size) .attr("stroke", "white") .attr("fill", d => getColor(colorArray, d.key)); labeledBoxes.append('title') .text(d => 'current label: '+d.key); // highlight the "current" box if (genD.hasOwnProperty('x')) { svg.append("rect") .attr("x", d => genD.x*size) .attr("y", d => genD.y*size) .attr("width", size) .attr("height", size) .attr("fill", "none") .attr("stroke-width", 5) .attr("stroke", "gold"); } div.node().value = genD.labeled; // play nicely with viewof return div.node(); }3c:Tcb9,/* Hoshen-Kopelman-like */ // This demo only accepts 2D arrays and can only find NN clusters // if copy is true, the function copies the union-find object and label array before yielding // (note that this removes the union-find methods from the object) // otherwise, it just passes the reference function* labelComponentsDemo(tab, copy=false) { const labels = new UnionFind(1); const labeled = []; yield ({labels:copy ? JSON.parse(JSON.stringify(labels)) : labels, labeled:copy ? JSON.parse(JSON.stringify(labeled)) : labeled, message:'Initial binary image'}); // first pass; scan down column by column const tabl = tab.length; const h = tab[0].length; for (let i=0; i < tabl; i++) { const col = tab[i]; labeled.push(Array(h).fill(0)); for (let j=0; j < h; j++) { const dat = col[j]; let message = ''; if (dat) { const left = labeled[i-1] && labeled[i-1][j]; // either undefined or labeled[i-1][j] const above = labeled[i][j-1]; if (!left && !above) { // neither left nor above are labeled labeled[i][j] = labels.makeSet(); message = `neither left nor above are labeled, made new set ${makeSpan(labels, colorArray, labeled[i][j], 'make')}`; } else if (left && !above) { // left but not above labeled[i][j] = labels.find(left); message = `left is labeled but not above, labeling with ${makeSpan(labels, colorArray, labeled[i][j], 'label')}`; } else if (!left && above) { labeled[i][j] = labels.find(above); message = `above is labeled but not left, labeling with ${makeSpan(labels, colorArray, labeled[i][j], 'label')}`; } else { message = 'both left and above are labeled'; if (left != above) { labels.link(left, above); message += `, linking labels ${makeSpan(labels, colorArray, left, 'label')} and ${ makeSpan(labels, colorArray, above, 'label')}`; } labeled[i][j] = labels.find(left); message += `, labeling with ${makeSpan(labels, colorArray, labeled[i][j], 'label')}`; } yield ({labels:copy ? JSON.parse(JSON.stringify(labels)) : labels, labeled:copy ? JSON.parse(JSON.stringify(labeled)) : labeled, x:i,y:j, message:message, currLabel:labeled[i][j]}); } } } yield ({labels:copy ? JSON.parse(JSON.stringify(labels)) : labels, labeled:copy ? JSON.parse(JSON.stringify(labeled)) : labeled, message:'starting second pass'}); // second pass for (let i=0; i y * (w * 4) + x * 4; const getX = (index, w) => (index/4) % w; const getY = (index, w) => Math.floor(index / (4 * w)); // first pass for (let x = 0; x < cdl; x += 4) { // pixels go left to right, then down if (clone.data[x] !== 0 || clone.data[x+1] !== 0 || clone.data[x+2] !== 0 || clone.data[x+3] !== 0) { // pixel not white const X = getX(x, w); const Y = getY(x, w); const left = (X>0) ? getFromTup(getIndex(X-1, Y, w), clone.data) : undefined; const diagNW = (type !== 'NN' && X>0 && Y>0) ? getFromTup(getIndex(X-1, Y-1, w), clone.data) : undefined; // either undefined or labeled[i-1][j-1] const diagNE = (type === 'NNN' && X0) ? getFromTup(getIndex(X+1, Y-1, w), clone.data) : undefined; // either undefined or labeled[i-1][j+1] const above = (Y>0) ? getFromTup(getIndex(X, Y-1, w), clone.data) : undefined; const prevNeighbors = (type === 'NN') ? [left, above] : [left, above, diagNW, diagNE]; const currLabel = getLabel(labels, prevNeighbors); const tup = convertTo4Tuple(currLabel); clone.data[x] = tup[0]; clone.data[x+1] = tup[1]; clone.data[x+2] = tup[2]; clone.data[x+3] = tup[3]; } } // second pass for (let x = 0; x < cdl; x += 4) { // pixels go left to right, then down if (clone.data[x] !== 0 || clone.data[x+1] !== 0 || clone.data[x+2] !== 0 || clone.data[x+3] !== 0) { // pixel not white const currLabel = labels.find(getFromTup(x, clone.data)); const tup = convertTo4Tuple(currLabel); clone.data[x] = tup[0]; clone.data[x+1] = tup[1]; clone.data[x+2] = tup[2]; clone.data[x+3] = tup[3]; if (colorfunc !== null) { const colorTup = colorfunc(currLabel); colorA.data[x] = colorTup[0]; colorA.data[x+1] = colorTup[1]; colorA.data[x+2] = colorTup[2]; colorA.data[x+3] = colorTup[3]; } } } return (colorfunc !== null) ? {labeled:clone, colored:colorA, labels} : {labeled:clone, labels}; } else throw new TypeError('tab must be an ImageData object'); }3f:T70e,// https://beta.observablehq.com/@mbostock/linked-inputs function stepInput(view, maxStep) { const div = html`

Algorithm timestep:
(first pass: 0, second pass: ${maxStep/2}, end: ${maxStep})`; const range = div.querySelector("[type=range]"); const number = div.querySelector("[type=number]"); const timezero = div.querySelector('#timezero'); const timemid = div.querySelector('#timemid'); const timeend = div.querySelector('#timeend'); timezero.onclick = () => { view.value = 0; }; timemid.onclick = () => { view.value = maxStep/2; }; timeend.onclick = () => { view.value = maxStep; }; range.oninput = () => { number.value = range.valueAsNumber; view.value = number.valueAsNumber; }; // number.oninput = () => { // range.value = number.valueAsNumber; // view.value = number.valueAsNumber; // }; number.onchange = () => { number.value = Math.min(Math.floor(Math.max(number.value, 0)), maxStep); range.value = number.valueAsNumber; view.value = number.valueAsNumber; }; // https://beta.observablehq.com/@mbostock/synchronized-views const update = () => { number.value = view.value; range.value = number.valueAsNumber; }; view.addEventListener("input", update); invalidation.then(() => view.removeEventListener("input", update)); update(); return div; }40:[] 32:{"id":"113300f0aea48cd2","slug":"labeling-connected-components","title":"Labeling connected components","thumbnail":"e5dd90f683294996cd859b2bb814341f3956d3f7d391a07ca8bfe7f5b733cc85","access_level":"public","create_time":"$D2018-10-18T06:18:33.758Z","update_time":"$D2020-05-02T11:00:09.450Z","view_time":null,"first_public_time":"$D2019-01-26T03:53:05.570Z","has_unpublished_edits":null,"fork":false,"stars":17,"starred":false,"owner":{"type":"team","id":"d2fd23101beb2a61","login":"bryangingechen","name":"Bryan Gin-ge Chen","avatar_url":"https://avatars-next.observableusercontent.com/73f0dccc0b7fc5c845e6a52a58e01a2ae432cc529aaada0d10ab602137e603c0","tier":"starter_2024"},"version":2118,"publish_version":2118,"role":null,"authored":false,"authors":[{"type":"individual","id":"5c13a1a27cf52564","login":"bryangingechen","name":"Bryan Gin-ge Chen","avatar_url":"https://avatars-next.observableusercontent.com/73f0dccc0b7fc5c845e6a52a58e01a2ae432cc529aaada0d10ab602137e603c0","tier":null}],"members":[{"type":"individual","id":"5c13a1a27cf52564","login":"bryangingechen","name":"Bryan Gin-ge Chen","avatar_url":"https://avatars-next.observableusercontent.com/73f0dccc0b7fc5c845e6a52a58e01a2ae432cc529aaada0d10ab602137e603c0","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":5,"collection":{"id":"80583d7c09f19038","slug":"inputs","title":"Ingredients","owner":{"id":"d2fd23101beb2a61","login":"bryangingechen","name":"Bryan Gin-ge Chen"}},"type":"notebook","body":{"title":"Labeling connected components","cells":[{"id":0,"value":"md`# Labeling connected components\n\n${// thumbnail trick from https://beta.observablehq.com/@mootari/custom-notebook-thumbnail\nnavigator.userAgent.match('HeadlessChrome') ? html`

` : ''}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":902,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1641,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1001,"value":"md`In the next gadget, you may submit an image URL or load an image file from your computer (all processing is done locally in your browser – your file will not be uploaded anywhere). The default image is [\"Flock\" by Karunakar Rayker](https://www.flickr.com/photos/krayker/2659028334/), (CC BY 2.0).\n\nThe slider controls a threshold for conversion from an RGB image to a binary image. Selecting the \"labeled\" radio option performs connected components labeling on the **non-white** pixels of the \"thresholded\" image and displays the result. If the \"invert\" box is checked, the binary image is inverted before connected components are labeled; this exchanges the foreground and background.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1480,"value":"viewof image = imageInput({\n crossOrigin: \"anonymous\",\n initialUrl: \"https://c1.staticflickr.com/3/2134/2659028334_11d680a78b_b.jpg\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1536,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1842,"value":"{\n if (radio1 === 'label') {\n const set = new Set(thresholdLabels.labels.roots);\n return md`There are ${set.size-1} foreground connected components in the image above.`; // subtract off background\n } else \n return md`Choose \"labeled\" above to see the count of connected components.`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1740,"value":"howItWorks = md`## How it works: the Hoshen–Kopelman / two-pass algorithm\n\n*Drag the slider below to the right to step through the algorithm!*\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":89,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":945,"value":"{\n if (navigator.userAgent.match('HeadlessChrome')) return;\n const div = html`

\n \n ${stepInput(viewof pt, algHistory.length-1)}`;\n div.querySelector('button').onclick = event => {\n viewof pt.value = 0;\n viewof testperc.dispatchEvent(new CustomEvent('input'));\n };\n return div;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1751,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":998,"value":"$39","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1719,"value":"$3a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1873,"value":"ditherExamples","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2011,"value":"md`**Thanks for reading!** Questions? Comments? Let me know what you think on [the Observable forums](https://talk.observablehq.com/) or on twitter [@blockspins](https://twitter.com/blockspins)!`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1638,"value":"md`## Code`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2046,"value":"md`### variables`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":892,"value":"viewof testperc = {\n const p = 0.6;\n const size = 15;\n const div = md`\\`testperc = \\` a ${size} x ${size} array where each entry is 1 with probability ${p} and 0 with probability ${1-p}; dispatching an \\`input\\` event to \\`viewof testperc\\` regenerates a new random array.`;\n function reset(){\n div.value = percolation(p,size,size);\n }\n div.addEventListener('input', reset);\n reset();\n return div;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":86,"value":"algHistory = Array.from(labelComponentsDemo(testperc, true))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":264,"value":"colorArray = ['#ffffff', '#000000']","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1276,"value":"colorArray2 = ['#ffffff', '#000000']","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1679,"value":"colorArray3 = ['#ffffff', '#000000']","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1854,"value":"mutable invertCheckbox = false","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1858,"value":"mutable neighb1 = 'nn'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1860,"value":"mutable threshVal = 580","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1862,"value":"mutable radio1 = 'label'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1870,"value":"mutable neighb2 = 'nn'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1910,"value":"mutable label2 = true","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1636,"value":"md`### functions and imports`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":29,"value":"percolation = (p, X, Y) =>\n Array.from({ length: Y }, row =>\n Array.from({ length: X }, d => (Math.random() > p ? 0 : 1))\n )","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":918,"value":"function getColor(colorArray, key) {\n if (key < colorArray.length)\n return colorArray[key];\n while (colorArray.length < 16777216) {\n const color = '#' + (Math.random().toString(16) + \"000000\").substring(2, 8);\n colorArray.push(color);\n if (key < colorArray.length)\n return color;\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":72,"value":"$3b","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":14,"value":"$3c","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1029,"value":"function getLabel(uf, prevNeighbors) {\n const labeled = prevNeighbors.filter(d => d > 0);\n if (labeled.length === 0) {\n return uf.makeSet();\n } else if (labeled.length === 1) {\n return uf.find(labeled[0]);\n } else {\n const left = uf.find(labeled[0]);\n for (let j = 1; j < labeled.length; j++) {\n if (labeled[j] !== labeled[0])\n uf.link(left, labeled[j]);\n }\n return left;\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"value":"$3d","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1274,"value":"function colorArrayTo4Tuple(colorArray, num) {\n const tup = [];\n const color = getColor(colorArray, num);\n for (let j=0; j<3; j++) {\n tup.push(parseInt(color.slice(2*j+1, 2*j+3), 16));\n }\n tup.push(255); // no opacity\n return tup;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1527,"value":"// convert 4 adjacent entries in an array\n// to a 32-bit integer\nfunction getFromTup(ind, arr) {\n return (arr[ind])\n + 256*(arr[ind+1])\n + 65536*(arr[ind+2])\n + 16777216*(arr[ind+3]);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1531,"value":"// convert a 32-bit unsigned integer to a 4-tuple\nfunction convertTo4Tuple(num) {\n const tup = [];\n for (let j=0; j<4; j++) {\n tup.push(num % 256);\n num = Math.floor(num/256);\n }\n return tup;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1199,"value":"$3e","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"d3 = require('d3@5')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"// https://github.com/mikolalysenko/union-find\n// UnionFind = require('https://bundle.run/union-find@1.0.2')\n//UnionFind = require('https://packd.now.sh/union-find@1.0.2')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":534,"value":"import { svg as uFviz, dataLabels, circleRad, invertColor, UnionFind } with {\n labels,\n colorArray,\n uFconfig as config,\n d3\n} from \"@bryangingechen/union-find-data-structure\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":574,"value":"uFconfig = {\n const X = 15,\n Y = 15,\n size = 15,\n scale = 25;\n\n const svgW = X*scale,\n svgH = Y*scale;\n\n return ({W:svgW, H:svgH, R:Math.min(svgW, svgH)/6, L:5, \n size:size, x0:svgW/2, y0:svgH/2,\n hover:false});\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":551,"value":"labels = {\n if (pt) \n yield algHistory[pt-1].labels;\n\n yield algHistory[pt].labels;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":951,"value":"import {View} from '@mbostock/synchronized-views'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":931,"value":"viewof pt = new View(0)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":934,"value":"$3f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":870,"value":"function makeSpan(labels, colorArray, index, method) {\n const size = 32;\n const isTreeRoot = (labels.roots[index] === index);\n return `\n`;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1467,"value":"import {fileInput, imageInput} from \"@mbostock/file-input\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1630,"value":"import {randomDither, dumbError, floydSteinberg} with {data as data} from '@tmcw/dithering'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1647,"value":"data = {\n if (navigator.userAgent.match('HeadlessChrome'))\n return;\n const img = new Image();\n img.crossOrigin = '*';\n img.src = 'https://file-hamhdaleym.now.sh/';\n await new Promise(resolve => img.addEventListener('load', resolve));\n const ctx = DOM.canvas(img.width, img.height).getContext('2d');\n ctx.drawImage(img, 0, 0);\n return {\n data: ctx.getImageData(0, 0, img.width, img.height),\n width: img.width,\n height: img.height\n };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W40","stdlib":"1","titling":"auto"}} 33:"$32:body"