29:null 2a:["$","title",null,{"children":"Document image segmentation | Alex Teixeira | Observable"}] 2f:T58a,md`# Document image segmentation This is my take on document image segmentation, using mostly pure javascript. The demo below uses a page from Leonardo Da Vinci's notebooks taken from the [Codex Atlanticus](http://codex-atlanticus.it/) database (definitely worth a visit!). Of course, you can upload some other image to play with it. Here you will find algorithms for: 1. *Image segmentation*, i.e., distinguishing the pixels corresponding to graphical marks (ink) from those of the background (paper). The algorithms take as input a source image and return a mask image, i.e., an image where the background pixels are set to transparent black (RGBA=[0,0,0,0]) and foreground pixels to opaque black (RGBA=[0,0,0,255]). Out of the 4 included algorithms, \`floodByColor()\` seems to yield the best results. 2. Computing *connected components*. There is only one function for that, \`getCirculations()\`, which takes as input a mask image and returns a list of simple polygons, each one enclosing a set of foreground pixels. Note that there is no support yet for determining connected components with holes. 3. *Image inpainting*. This is a hot topic in image processing and consists of closing the gaps left by the foreground pixels in the background pixels by trying to "guess" colors for the removed foreground pixels. Two algorithms are included, both very crude: \`blurInpaint()\` and \`quadtreeInpaint()\`. `30:T56c,{ if (!segmentation) return; let { curves, imgData, maskCanvas } = segmentation; let [w,h] = [imgData.width,imgData.height]; let canvas = DOM.canvas(w,h,1); let ctx = canvas.getContext('2d'); if (inpaintAlgorithm == 'none') { ctx.putImageData(imgData,0,0); ctx.globalCompositeOperation = "destination-out" ctx.drawImage(maskCanvas,0,0) ctx.globalCompositeOperation = "source-over" } else { ctx.drawImage(maskCanvas,0,0); let maskPixelData = ctx.getImageData(0,0,w,h); ctx.putImageData((inpaintAlgorithm == 'hierarchical' ? quadtreeInpaint : blurInpaint) (imgData, maskPixelData), 0, 0); } if (animateSegments) { let background = ctx.getImageData (0, 0, w, h); let { texture, pieces } = textureBigger (curves, imgData); let offsets = [Vec (-w,-h), Vec(-w,0), Vec(-w,h), Vec (0,-h), Vec(0,h), Vec(w,-h),Vec(w,0),Vec(w,h)]; for (let piece of pieces) { piece.pos = offsets[~~(Math.random()*8)].add(Vec(Math.random()*w,Math.random()*h)); } let n = 1000; for (let i = 0; i <= n; i++) { ctx.putImageData(background,0,0); let t = i / n; for (let piece of pieces) { let p = piece.pos.mix(Vec(piece.sx,piece.sy),t); ctx.drawImage(texture, piece.x, piece.y, piece.w, piece.h, p.x,p.y,piece.w,piece.h) } yield canvas; } } yield canvas }31:Tb89,{ let w = Math.min(width,img.width); let h = ~~(img.height*w/img.width); let canvas = DOM.canvas(w,h,1); let ctx = canvas.getContext('2d'); ctx.drawImage (img,0,0,w,h) let imgData = ctx.getImageData(0,0,w,h) let maskCanvas = DOM.canvas(w,h,1); let maskCtx = maskCanvas.getContext('2d'); let maskPixelData = maskCtx.createImageData(imgData) let pattern = ctx.createPattern(canvas,"repeat"); let x = 0, y = 0; let unionMask = function (newMaskPixelData) { let src = new Uint32Array (newMaskPixelData.data.buffer); let dst = new Uint32Array (maskPixelData.data.buffer); console.assert (src.length == dst.length); for (let i = 0; i < src.length; i++) { if (src [i] == 0) dst[i] = 0 } } let refresh = (unionFlag) => { let newMaskPixelData = null; if (operation == "edge") newMaskPixelData = erode(imageEdges(imgData, distThreshold)); else if (operation == "floodToEdge") newMaskPixelData = floodFillEdgeMask (imgData, x, y, distThreshold) else if (operation == "floodByColor") newMaskPixelData = floodFillMask (imgData, x, y, distThreshold) else if (operation == "colorSimilarity") newMaskPixelData = bgColorMask(imgData,mutable backgroundColor, distThreshold) else if (operation == "noMask") { let data = maskPixelData.data; for (let i = 0; i < data.length; i+=4) data [i+3] = 255; } if (unionFlag && newMaskPixelData) { unionMask(newMaskPixelData); } else if (newMaskPixelData) { maskPixelData = newMaskPixelData; } ctx.clearRect(0,0,w,h) maskCtx.putImageData(maskPixelData,0,0); if (drawSettings[0]) { ctx.putImageData(imgData,0,0); ctx.globalCompositeOperation = "destination-in" ctx.drawImage(maskCanvas,0,0) } let connected = getCirculations(maskPixelData); ctx.globalCompositeOperation = "source-over"; ctx.strokeStyle = 'red'; //ctx.fillStyle = pattern; let curves = [] for (let comp of connected.components) { if (comp == undefined || comp.points.length == 0) continue; let curve = new Curve(...comp.points); if (Math.abs(curve.area()) < minArea) continue; curve = curve.subsample (subsampleTol); curves.push (curve) if (drawSettings[1]) { ctx.beginPath(); let {x,y} = curve[0]; ctx.moveTo(x,y); for (let {x,y} of curve) { ctx.lineTo(x,y) } // ctx.fill() ctx.stroke() } } mutable segmentation = { imgData: imgData, maskCanvas : maskCanvas, curves : curves } } refresh() ctx.canvas.oncontextmenu = function (e) { e.preventDefault(); e.stopPropagation(); return false; } ctx.canvas.onmousedown = (e) => { x = e.offsetX; y = e.offsetY; let i = (w*y+x)*4; mutable backgroundColor = imgData.data.slice(i,i+4); refresh(e.buttons & 6); } return canvas }32:T41f,floodFillMask = function (pixelData, x, y, distThreshold = 10) { let [w,h] = [pixelData.width, pixelData.height]; let src = pixelData.data; let maskData = new ImageData(w,h); let dst = maskData.data; for (let i = 0; i < dst.length; i+=4) dst [i+3] = 255; let visited = new Uint8Array(src.length); let count = 0; let stack = [[x,y]]; let threshold2 = distThreshold*distThreshold while (stack.length) { let [x,y] = stack.pop(); let i = (w*y+x)*4; visited[i] = true; count++; let [R,G,B,A] = src.slice(i,i+4); let dist = (j) => { let [dr,dg,db,da] = [src[j]-R,src[j+1]-G,src[j+2]-B,src[j+3]-A]; return dr*dr+dg*dg+db*db+da*da; } dst[i+3] = 0; if (x > 0 && !visited[i-4] && dist(i-4) < threshold2) stack.push([x-1,y]); if (x+1 < w && !visited[i+4] && dist(i+4) < threshold2) stack.push([x+1,y]); if (y > 0 && !visited[i-w*4] && dist(i-w*4) < threshold2) stack.push([x,y-1]); if (y+1 < h && !visited[i+w*4] && dist(i+w*4) < threshold2) stack.push([x,y+1]); } return maskData }33:Ta73,blurInpaint = function (pixelData, maskData, blurSteps = 3) { let [w,h] = [pixelData.width, pixelData.height]; console.assert(w == maskData.width && h == maskData.height); let src = new Uint32Array (pixelData.data.buffer); let result = new ImageData(w,h); let dst = new Uint32Array (result.data.buffer); let mask = new Uint32Array (maskData.data.buffer); let size = w*h; let queue = [] let visited = new Uint8Array(size); // Set up queue and visited for (let x = 1; x+1 < w; x++) { for (let y = 1; y+1 < h; y++) { let i = y*w+x; dst[i] = src[i]; if (mask[i]) dst[i] = 0; else dst[i] = src[i]; if (mask[i] && !(mask[i-w-1] && mask[i-w] && mask[i-w+1] && mask[i-1] && mask[i+1] && mask[i+w-1] && mask[i+w] && mask[i+w+1])) { queue.push (i); } } } // A gaussian blur function let gauss = pixels => { let newValues = new Uint32Array(pixels.length); let rgbaWord = new Uint32Array(1); let rgba = new Uint8Array(rgbaWord.buffer); let n = 0; for (let i of pixels) { let [r,g,b] = [0,0,0]; let sum = 0; for (let [j,s] of [[i-w-1,0.073235],[i-w, 0.176765],[i-w+1,0.073235], [i-1, 0.176765],[i+1, 0.176765], [i+w-1, 0.073235],[i+w, 0.176765],[i+w+1,0.073235]]) { // for (let [j,s] of [[i-w-1,1],[i-w, 1],[i-w+1,1], // [i-1, 1],[i+1, 1], // [i+w-1, 1],[i+w, 1],[i+w+1,1]]) { if (!mask[j] || (visited[j] > 0 && visited[j] < 255)) { let k = j * 4; r += result.data[k++]*s; g += result.data[k++]*s; b += result.data[k++]*s; sum += s; } } if (sum > 0) { let k = i*4; rgba.set([Math.round(r/sum),Math.round(g/sum),Math.round(b/sum),255]); //rgba.set([r/sum,g/sum,b/sum,255]); newValues[n] = rgbaWord[0]; } n++; } n = 0; for (let i of pixels) { dst[i] = newValues[n++]; visited[i] = 1; } } // Inpaint pixels in queue and find neighbor masked pixels let first = 0; for (let run = 1; run <= width && queue.length - first > 0; run++) { let n = queue.length; gauss(queue.slice(first,n)); for (let q = first; q < n; q++) { let i = queue[q]; for (let j of [i-w-1, i-w, i-w+1, i-1, i+1, i+w-1, i+w, i+w+1]) { if (visited[j] == 0 && mask[j]) { queue.push (j); visited[j] = 255; } } } first = n; } while (blurSteps--) gauss(queue); return result }34:Tbe3,quadtreeInpaint = function (pixelData, maskData) { let [w,h] = [pixelData.width, pixelData.height]; console.assert(w == maskData.width && h == maskData.height); let k = Math.ceil(Math.log2(Math.max(w,h))); let n = 1< { let m = n/2; let half = new ImageData(m,m); let src = new Uint32Array (original.data.buffer); let dst = new Uint32Array (half.data.buffer); let rgbaWord = new Uint32Array(1); let rgba = new Uint8Array(rgbaWord.buffer); let average = (words) => { let [R,G,B,A] = [0,0,0,0]; let sum = 0; for (let w of words) { rgbaWord [0] = w; if (rgba[3]) { sum++; R += rgba[0]; G += rgba[1]; B += rgba[2]; } } if (sum>0) { rgba.set([Math.round(R/sum),Math.round(G/sum),Math.round(B/sum),255]) } else { rgbaWord [0] = 0 } return rgbaWord [0]; } for (let x = 0; x < m; x++) { for (let y = 0; y < m; y++) { let words = [src[2*y*n+2*x],src[2*y*n+2*x+1], src[2*y*n+n+2*x],src[2*y*n+n+2*x+1]] // if (x > 0 && y > 0) { // words.push (src[2*y*n+2*x-1],src[2*y*n+n+2*x-1], // src[2*y*n-n+2*x],src[2*y*n-n+2*x+1],src[2*y*n-n+2*x-1]) // } dst[y*m+x] = average(words) } } return half } // Replace original pixels with pixels of halved image if masked let double = (original, half, n) => { let m = n/2; let src = new Uint32Array (original.data.buffer); let dst = new Uint32Array (half.data.buffer); let rgbaWord = new Uint32Array(1); let rgba = new Uint8Array(rgbaWord.buffer); for (let x = 0; x < m; x++) { for (let y = 0; y < m; y++) { let fallback = dst[y*m+x]; for (let i of [2*y*n+2*x,2*y*n+2*x+1,2*y*n+n+2*x,2*y*n+n+2*x+1]) { rgbaWord[0] = src[i]; if (rgba[3] == 0) src[i] = fallback; } } } } // The algorithm, proper let pyramid = [base]; let N = n; for (let i = 0; i < k; i++) { let top = pyramid[i]; pyramid[i+1] = halve(top,N); N = N/2; } for (let i = k; i > 0; i--) { let bottom = pyramid[i]; N = N*2; double (pyramid[i-1],pyramid[i],N) } // Build return image let result = new ImageData(w,h); let res = new Uint32Array (result.data.buffer); for (let x = 0; x < w; x++) { for (let y = 0; y < h; y++) { let i = y*w+x; let j = y*n+x; res[i] = dst[j] } } return result }35:Tc31,class ConnectedComponents { constructor () { this.hash = [] this.components = [] this.edges = [] } json () { return JSON.parse(JSON.stringify(this)) } newComponentIndex () { for (let i = 0; i < this.components.length; i++) { if (this.components[i] === undefined) { return i; } } return this.components.length; } addVerticalEdge (edge) { //console.log (edge) this.edges.push(edge) let component = { index : this.newComponentIndex(), ymin : edge[0].y, ymax : edge[1].y, points : [edge[0],edge[1]] }; this.components [component.index] = component; if (this.hash[component.ymin] !== undefined) { let c = this.hash[component.ymin]; this.hash[component.ymin] = undefined; this.components[component.index] = undefined; if (c.ymin == component.ymin) { c.ymin = component.ymax; c.points.unshift(component.points[1]); } else { console.assert(c.ymax == component.ymin); c.ymax = component.ymax; c.points.push (component.points[1]); } component = c; } if (this.hash[component.ymin] != undefined && this.hash[component.ymin].index != component.index) { // console.log (JSON.parse(JSON.stringify (component)), "hit", // JSON.parse (JSON.stringify (this.hash[component.ymin]))); let c2 = this.hash[component.ymin]; console.assert (component.index != c2.index); console.assert (c2.ymin == component.ymin); this.components[c2.index] = undefined; this.hash[c2.ymin] = undefined; c2.points.reverse(); component.points.unshift(...c2.points.slice(0,c2.points.length-1)); component.ymin = c2.ymax; this.hash[c2.ymax] = undefined; } else { if (this.hash[component.ymax] !== undefined) { let c = this.hash[component.ymax]; this.hash[component.ymax] = undefined; if (c !== component) { this.components[component.index] = undefined; if (c.ymax == component.ymax) { c.ymax = component.ymin; component.points.reverse(); c.points.push(...component.points.slice(1)); } else { console.assert(c.ymin == component.ymax); c.ymin = component.ymin; c.points.unshift(...component.points.slice(0,component.points.length-1)); } component = c; } } } if (component.ymin < component.ymax) { this.hash[component.ymin] = this.hash[component.ymax] = component; } } addHorizontalEdge (edge) { this.edges.push(edge) console.assert(edge[0].y==edge[1].y); console.assert(this.hash[edge[0].y]); let c = this.hash[edge[0].y]; if (c != undefined) { if (c.ymin == edge[0].y) { c.points.unshift(edge[1]) } else { console.assert(c.ymax == edge[0].y); c.points.push(edge[1]) } } else { console.log ("Dangling h edge", edge) } } }36:T8b9,function getCirculations (imgdata) { let [w,h] = [imgdata.width,imgdata.height]; let data = imgdata.data; function getRuns (x) { let last = false; let run = null; let runs = []; for (let y = 0; y < h; y++) { let pixel = data[(w*y+x)*4+3]; let current = pixel > 0; if (current) { if (run != null) run.ymax = y+1; else { run = { x:x, ymin: y, ymax:y+1 }; runs.push (run); } } else { run = null } } return runs } function runDifference (runs0,runs1) { runs0 = runs0.slice(0); if (runs0.length == 0) return runs0; if (runs1.length == 0) return runs0; let result = []; let [i0,i1] = [0,0]; while ( i0 < runs0.length && i1 < runs1.length ) { let [r0,r1] = [runs0[i0], runs1[i1]]; if (r0.ymax <= r1.ymin) { result.push(r0); i0++; } else if (r1.ymax <= r0.ymin) { i1++; } else { if (r0.ymin < r1.ymin) { result.push ({x:r0.x, ymin: r0.ymin, ymax:r1.ymin}); r0 = {x:r0.x, ymin:r1.ymin, ymax:r0.ymax}; } else { r0 = {x:r0.x, ymin:r1.ymax, ymax:r0.ymax}; } if (r0.ymax <= r0.ymin) i0++; else runs0[i0] = r0; } } result.push.apply(result,runs0.slice(i0)) return result; } //let edges = []; let prevRuns = []; let connected = new ConnectedComponents(); let vEdge = (x) => { return (run) => [Vec(x,run.ymin),Vec(x,run.ymax)] }; for (let x= 0; x <= w; x++) { let runs = x == w ? [] : getRuns(x); let currMinusPrev = runDifference(runs, prevRuns); let prevMinusCurr = runDifference(prevRuns, runs); let verticalEdges = currMinusPrev.map(vEdge(x)).concat(prevMinusCurr.map(vEdge(x))); let horizontalEdges = []; for (let r of runs) { horizontalEdges.push ([Vec(r.x,r.ymin),Vec(r.x+1,r.ymin)]); horizontalEdges.push ([Vec(r.x,r.ymax),Vec(r.x+1,r.ymax)]); } for (let vEdge of verticalEdges) { connected.addVerticalEdge (vEdge); } for (let hEdge of horizontalEdges) { connected.addHorizontalEdge (hEdge); } prevRuns = runs } return connected; }37:T459,function texturePack (curves, imgData, showBoxes = false) { let tmpCanvas = DOM.canvas (imgData.width, imgData.height, 1); let tmpCtx = tmpCanvas.getContext("2d"); tmpCtx.putImageData(imgData,0,0); let pattern = tmpCtx.createPattern(tmpCanvas,"repeat"); let div = html`

`; let boxes = curves.map(c => { let mbr = c.mbr(); let size = mbr.size(); return { sx: mbr.min.x, sy: mbr.min.y, w: size.x, h: size.y, c:c } }) let rect = potpack(boxes) let canvas = DOM.canvas (rect.w, rect.h, 1) let ctx = canvas.getContext("2d") ctx.fillStyle = pattern; for (let box of [boxes[0]]) { ctx.setTransform(1, 0, 0, 1, 0, 0); // Reset transform if (showBoxes) { ctx.strokeStyle = 'black'; ctx.beginPath(); ctx.rect(box.x,box.y,box.w,box.h); ctx.stroke(); } ctx.translate(box.x-box.sx, box.y-box.sy); ctx.strokeStyle = pattern; ctx.beginPath() let {x,y} = box.c[0]; ctx.moveTo(x,y); for (let {x,y} of box.c) { ctx.lineTo(x,y) } ctx.fill() ctx.stroke() } return { texture: canvas, pieces: [boxes[0]] } }39:[{"id":"621edaa4f28ca818c8a50c5c76394ce3a93ee0c77d77c5cc28f2f9fd0033bda44a31a6164b7d9b5b0e0ece8052142e498a0da669da0d10b6c13742c63eff99d5","href":"https://static.observableusercontent.com/files/621edaa4f28ca818c8a50c5c76394ce3a93ee0c77d77c5cc28f2f9fd0033bda44a31a6164b7d9b5b0e0ece8052142e498a0da669da0d10b6c13742c63eff99d5","name":"000R-222@1.jpg","type":"image/jpeg","lastModified":1579032528054.152,"size":429602}] 2d:{"id":"d21f9a6817d36c01","slug":"document-image-segmentation","title":"Document image segmentation","thumbnail":"4f5c2ff8acb09f1b729f4d75594d71078f05d750356a95749426396a69d8013e","access_level":"public","create_time":"$D2020-01-14T20:08:48.054Z","update_time":"$D2020-01-30T00:08:31.284Z","view_time":null,"first_public_time":"$D2020-01-29T05:51:21.573Z","has_unpublished_edits":null,"fork":{"id":"9b699566c54c9485","slug":"document-image-segmentation","title":"Document image segmentation","owner":{"id":"e9fcee55f21948e0","login":"esperanc","name":"Claudio Esperança"}},"stars":2,"starred":false,"owner":{"type":"team","id":"e0e3267414e14df9","login":"alexteixeira1","name":"Alex Teixeira","avatar_url":"https://avatars-next.observableusercontent.com/c77d11623668832a1b9ee0abc7886db39db17509bf9e0e622fd40aab785ecefe","tier":"starter_2024"},"version":1436,"publish_version":1436,"role":null,"authored":false,"authors":[{"type":"individual","id":"27583d28ab97b9b0","login":"alexteixeira1","name":"Alex Teixeira","avatar_url":"https://avatars-next.observableusercontent.com/c77d11623668832a1b9ee0abc7886db39db17509bf9e0e622fd40aab785ecefe","tier":null}],"members":[{"type":"individual","id":"27583d28ab97b9b0","login":"alexteixeira1","name":"Alex Teixeira","avatar_url":"https://avatars-next.observableusercontent.com/c77d11623668832a1b9ee0abc7886db39db17509bf9e0e622fd40aab785ecefe","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":3,"collection":null,"type":"notebook","body":{"title":"Document image segmentation","cells":[{"id":0,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":954,"value":"md`## Document segments animation demo`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1001,"value":"md`Inpaint algorithm: ${bindRadioGroup ({options:[\"hierarchical\",\"blur\",\"none\"]}, viewof inpaintAlgorithm)}
\nAnimate segments ${bindCheckbox(\"\",viewof animateSegments)}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":766,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1015,"value":"md`Load new image: ${bindFile({multiple:false, accept:\".png,.jpg\", size:'20em'},viewof imgfile)}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":324,"value":"md`## Demo Interface for the algorithms.\n\n### Segmentation settings\nAlgorithm: ${bindRadioGroup ({options:[\"floodByColor\",\"floodToEdge\",\"edge\",\"colorSimilarity\",\"noMask\"]}, viewof operation)}
\nColor similarity threshold: \n${bindSliderNumber ({min:1,max:50,step:1}, viewof distThreshold)}
\n\n**Connected component post-processing**
\nMinimum Polygon Area: ${bindSliderNumber ({min:1,max:100,step:1}, viewof minArea)} pixels
\nPolygon Subsample Tolerance: ${bindSliderNumber ({min:0,max:50,step:1}, viewof subsampleTol)} pixels
\n\n**Display**
\n${bindCheckGroup({options:['maskedImage','polygons']}, viewof drawSettings)}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":30,"value":"{\n let [r,g,b,a] = backgroundColor;\n return html`Background Color

`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1213,"value":"comment('Click anywhere to set the background color / seed for the flood filling algorithms. Click with the right button to carve new background parts to the mask.')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1218,"value":"comment('Segmented parts packed into a texture')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1226,"value":"md`${bindCheckbox(\"boxes\", viewof showTextureBoxes)} Show boxes around the segment polygons`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1052,"value":"{\n if (!segmentation) return \"No segments computed yet\";\n let { curves, imgData } = segmentation;\n let canvas = textureBigger(curves, imgData, showTextureBoxes).texture\n return canvas\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1407,"value":"segmentation","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":336,"value":"comment('User Interface Variables')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":218,"value":"mutable bgPixAddress = ({x:-1,y:-1})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":299,"value":"mutable backgroundColor = [0,0,0,0]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":112,"value":"viewof distThreshold = new View(10)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":415,"value":"viewof operation = new View(\"floodByColor\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":677,"value":"viewof subsampleTol = new View (0)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":679,"value":"viewof minArea = new View (1)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1011,"value":"viewof drawSettings = new View(['maskedImage', 'polygons'])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1224,"value":"viewof showTextureBoxes = new View(false)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":999,"value":"viewof inpaintAlgorithm = new View('none')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1336,"value":"viewof animateSegments = new View(true)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":971,"value":"comment('The segmented image, mask and polygons')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":973,"value":"mutable segmentation = null","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1304,"value":"md`## Segmentation algorithms`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":145,"value":"comment(`Creates a mask where pixels similar to the background color are made transparent`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":81,"value":"bgColorMask = function (pixelData, bgPixel, distThreshold = 10) {\n let [R,G,B,A] = bgPixel;\n let src = pixelData.data;\n let maskData = new ImageData(pixelData.width, pixelData.height)\n let dst = maskData.data;\n let count = 0;\n let threshold2 = distThreshold*distThreshold\n for (let i = 0; i < src.length; i += 4) {\n let [dr,dg,db,da] = [src[i]-R,src[i+1]-G,src[i+2]-B,src[i+3]-A];\n let dist = dr*dr+dg*dg+db*db+da*da;\n if (dist < threshold2) {\n [dst[i],dst[i+1],dst[i+2],dst[i+3]] = [0,0,0,0];\n } else {\n [dst[i],dst[i+1],dst[i+2],dst[i+3]] = [0,0,0,255];\n count++;\n }\n };\n return maskData\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":339,"value":"comment('Creates a mask by flood-filling by color similarity starting with a seed background pixel at `x,y`')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":212,"value":"$32","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":692,"value":"comment('Creates a mask setting as foreground the pixels having in their 4-neighborhood pixels with significantly different colors')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":359,"value":"imageEdges = function (pixelData, distThreshold = 10) {\n let [w,h] = [pixelData.width, pixelData.height];\n let src = pixelData.data;\n let maskData = new ImageData(w,h);\n let dst = maskData.data;\n let threshold2 = distThreshold*distThreshold\n let dist = function(i,j) {\n let [dr,dg,db,da] = [src[j]-src[i],src[j+1]-src[i+1],src[j+2]-src[i+2],src[j+3]-src[i+3]];\n return dr*dr+dg*dg+db*db+da*da;\n }\n for (let x = 1; x < w-1; x++) {\n for (let y = 1; y < h-1; y++) {\n let i = (w*y+x)*4;\n let maxdist = Math.max(dist(i,i-w*4),dist(i,i+w*4),dist(i,i+4),dist(i,i-4));\n if (maxdist>=threshold2) dst[i+3] = 255;\n }\n }\n return maskData\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":695,"value":"comment('Creates a mask by first marking edge pixels and then flood-filling starting at pixel (`x`, `y`) up until hitting an edge pixel')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":378,"value":"floodFillEdgeMask = function (pixelData, x,y, distThreshold = 10) {\n let [w,h] = [pixelData.width, pixelData.height];\n let maskData = new ImageData(w,h);\n let src = pixelData.data;\n let dst = maskData.data;\n let edge = erode(imageEdges(pixelData, distThreshold)).data;\n for (let i = 0; i < dst.length; i+=4) dst [i+3] = 255;\n let visited = new Uint8Array(src.length);\n let count = 0;\n let stack = [[x,y]];\n while (stack.length) {\n let [x,y] = stack.pop();\n let i = (w*y+x)*4;\n visited[i] = true;\n count++;\n dst[i+3] = 0;\n if (x > 0 && !visited[i-4] && edge[i-4+3]==0) stack.push([x-1,y]);\n if (x+1 < w && !visited[i+4] && edge[i+4+3]==0) stack.push([x+1,y]);\n if (y > 0 && !visited[i-w*4] && edge[i-w*4+3]==0) stack.push([x,y-1]);\n if (y+1 < h && !visited[i+w*4] && edge[i+w*4+3]==0) stack.push([x,y+1]);\n }\n return maskData\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1307,"value":"md`## Inpainting algorithms`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":894,"value":"comment('Inpainting by gaussian blur. Does not work well on large \"holes\"')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":749,"value":"$33","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":898,"value":"comment('A very simple hierarchical inpainting algorithm. Works better on large holes but may lead to pixelation on small holes')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":820,"value":"$34","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1310,"value":"md`## Topological filters`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":208,"value":"comment('Erodes pixel buffer `maskData` with a 4-neighbor mask. `reference` is the transparent alpha value and dilation can be achieved by setting it to 255.')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":147,"value":"erode = function (maskData, reference = 0) {\n let [w,h] = [maskData.width, maskData.height];\n let data = maskData.data;\n let newMask = new ImageData(w,h) \n let newData = newMask.data;\n let i = 3;\n let w4 = w*4;\n for (let y = 0; y < h; y++) {\n for (let x = 0; x < w; x++) {\n if (data[i] != reference &&\n ( (x <= 0 || data[i-4] != reference) &&\n (x+1 >= w || data[i+4] != reference) &&\n (y <= 0 || data[i-w4] != reference) &&\n (y+1 >= h || data[i+w4] != reference))) {\n newData[i] = 255-reference; \n }\n else {\n newData[i] = reference;\n }\n i += 4;\n }\n }\n return newMask\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":746,"value":"comment('Inverse of `erode()`')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":398,"value":"dilate = (maskData)=> erode(maskData,255)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1312,"value":"md`## Connected component processing`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":702,"value":"comment('Auxiliary class for keeping track of circulations as vertical and horizontal edges are added in the left-to-right scanline algorithm implemented in `getCirculations()`')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":240,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":705,"value":"comment('Takes a binary image buffer (only alpha is used) and returns a list of curves delimiting the opaque (alpha != 0) regions')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":276,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":708,"value":"comment('Demo for `getCirculations()`')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":165,"value":"{\n let [w,h] = [800,600]\n let c = DOM.canvas(w,h,1);\n let ctx = c.getContext('2d');\n ctx.fillStyle = 'black';\n for (let i = 0; i < 40; i++) { \n ctx.beginPath(); \n let s = Math.random()*60+1 \n ctx.arc (Math.random()*800, Math.random()*600, s, 0, 2*Math.PI)\n ctx.fill();\n }\n\n let connected = getCirculations(ctx.getImageData(0,0,w,h));\n ctx.clearRect (0,0,w,h);\n ctx.fillStyle = 'gray';\n ctx.lineWidth = 1;\n ctx.transform(1, 0, 0, 1, 0, 0);\n \n ctx.strokeStyle = 'red';\n for (let comp of connected.components) {\n if (comp == undefined || comp.points.length == 0) continue;\n ctx.beginPath();\n let {x,y} = comp.points[0];\n ctx.moveTo(x,y);\n for (let {x,y} of comp.points) {\n ctx.lineTo(x,y)\n }\n ctx.fill()\n ctx.stroke()\n }\n return c\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1315,"value":"md`## Texture packing`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1048,"value":"comment('Given the contents of an image and the recognized polygons describing the segmented parts, returns an object with two elements: `texture`, containing a roughly square image where the segmented parts are packed tightly so that it that can be used as a texture, and `boxes`, containing an array with the original curves, their bounding boxes and where they are mapped in the texture.')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":729,"value":"$37","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1422,"value":"$38","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"md`## Libraries`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":718,"value":"//\n// A nice download function copied from \n// https://ourcodeworld.com/articles/read/189/how-to-create-a-file-and-generate-a-download-with-javascript-in-the-browser-without-a-server\n//\nfunction download(filename, text) {\n var element = document.createElement('a');\n element.setAttribute('href', 'data:text/plain;charset=utf-8,' + encodeURIComponent(text));\n element.setAttribute('download', filename);\n\n element.style.display = 'none';\n document.body.appendChild(element);\n\n element.click();\n\n document.body.removeChild(element);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"value":"import { bindSliderNumber, bindRadioGroup, bindCheckGroup, bindCheckbox, bindFile, View } from \"@esperanc/inline-inputs\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"import { comment } from \"@esperanc/notebook-css-utilities\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":199,"value":"import { Vec, Curve } from \"@esperanc/2d-geometry-utils\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":750,"value":"comment('Rectangle packing')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":732,"value":"potpack = require('potpack@1.0.1/index.js')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":996,"value":"comment('The loaded image for the demo')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":18,"value":"mutable img = {\n const image = new Image;\n image.crossOrigin = \"anonymous\";\n image.src = await FileAttachment(\"000R-222@1.jpg\").url()\n return image;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":908,"value":"viewof imgfile = new View(null)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":911,"value":"{\n if (imgfile == null) return\n let file = imgfile;\n let newimg = html``\n newimg.src = await Files.url(file[0]);\n mutable img = newimg;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W39","stdlib":"1","titling":"auto"}} 2e:"$2d:body"