31:T671,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. These are very simple-minded algorithms, but good enough for processing images taken from printed or handwritten documents. 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. *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()\`. The module for extracting individual circulations from groups of foreground pixels has been moved to [its own notebook](https://observablehq.com/@esperanc/bitmap-tracing) and is now capable of recognizing polygons with holes. Another cool feature shown here is how to pack all the recognized parts of the document into a texture, using the excelent [potpack](https://www.npmjs.com/package/potpack) package. `32:T744,{ 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'); ctx.imageSmoothingEnabled = false; 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 } = texturePack (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)]; while (true) { 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; } for (let i = 0; i < 100; i++) yield canvas; for (let i = n; i >= 0; 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 }33:Tbb6,{ 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 = 3, y = 3; // Default to a pixel just inside the border 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 }34: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 }35: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 }36:Te85,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]; //break; } } 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); let weightedAverage = (words_weights) => { let [R,G,B,A] = [0,0,0,0]; let sum = 0; for (let [w,p] of words_weights) { rgbaWord [0] = w; if (rgba[3]) { sum+=p; R += rgba[0]*p; G += rgba[1]*p; B += rgba[2]*p; //break; } } 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 fallback = dst[y*m+x]; if (x+1 < m && y+1 < m) { fallback = weightedAverage ([[fallback,9], [dst[y*m+x+1],4], [dst[y*m+m+x],4], [dst[y*m+m+x+1],1]]) } 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 }37:T47e,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.imageSmoothingEnabled = false; ctx.fillStyle = pattern; for (let box of boxes) { 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 } }38:[{"id":"621edaa4f28ca818c8a50c5c76394ce3a93ee0c77d77c5cc28f2f9fd0033bda44a31a6164b7d9b5b0e0ece8052142e498a0da669da0d10b6c13742c63eff99d5","href":"https://static.observableusercontent.com/files/621edaa4f28ca818c8a50c5c76394ce3a93ee0c77d77c5cc28f2f9fd0033bda44a31a6164b7d9b5b0e0ece8052142e498a0da669da0d10b6c13742c63eff99d5","name":"000R-222.jpg","type":"image/jpeg","lastModified":1578575653301.125,"size":429602},{"id":"06745a7b1fd4e52d1f666b25faeffb3cd1de8e2424897dfb99f6618ac844b6c966725b4ba14978d9b0471762c8d0a619fde551c0f53ff92cf62fd4524c6869ad","href":"https://static.observableusercontent.com/files/06745a7b1fd4e52d1f666b25faeffb3cd1de8e2424897dfb99f6618ac844b6c966725b4ba14978d9b0471762c8d0a619fde551c0f53ff92cf62fd4524c6869ad","name":"000R-268.jpg","type":"image/jpeg","lastModified":1579619027052.435,"size":552243},{"id":"77d5e48457c888a145dff7ade79cfc27acb263054c6fdf10b39aa96b5e5e038c136039201a2458412036aaa62f212966508b9c67b385263d18ec29c5aa150967","href":"https://static.observableusercontent.com/files/77d5e48457c888a145dff7ade79cfc27acb263054c6fdf10b39aa96b5e5e038c136039201a2458412036aaa62f212966508b9c67b385263d18ec29c5aa150967","name":"000R-138.jpg","type":"image/jpeg","lastModified":1579616177818.371,"size":536193}] 2f:{"title":"Document image segmentation","cells":[{"id":0,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":954,"value":"md`## Document segments animation demo`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1001,"value":"md`Inpaint algorithm: ${bindRadioGroup ({options:[\"hierarchical\",\"blur\",\"none\"]}, viewof inpaintAlgorithm)}
\nAnimate segments ${bindCheckbox(\"\",viewof animateSegments)}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":766,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":1015,"value":"md`Select an image: ${bindSelect({options:Object.keys(images)},viewof imageName)}
\nOr load new image: ${bindFile({multiple:false, accept:\".png,.jpg\", size:'20em'},viewof imgfile)}`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":30,"value":"{\n let [r,g,b,a] = backgroundColor;\n return html`Background Color

`\n}","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":20,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":1218,"value":"comment('Segmented parts packed into a texture')","pinned":false,"hidden":false,"mode":"ojs"},{"id":1226,"value":"md`${bindCheckbox(\"boxes\", viewof showTextureBoxes)} Show boxes around the segment polygons`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1052,"value":"{\n if (!segmentation) return \"No segments computed yet\";\n let { curves, imgData } = segmentation;\n let canvas = texturePack(curves, imgData, showTextureBoxes).texture\n return canvas\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":336,"value":"comment('User Interface Variables')","pinned":false,"hidden":false,"mode":"ojs"},{"id":218,"value":"mutable bgPixAddress = ({x:-1,y:-1})","pinned":true,"hidden":false,"mode":"ojs"},{"id":299,"value":"mutable backgroundColor = [0,0,0,0]","pinned":true,"hidden":false,"mode":"ojs"},{"id":112,"value":"viewof distThreshold = new View(10)","pinned":true,"hidden":false,"mode":"ojs"},{"id":415,"value":"viewof operation = new View(\"floodByColor\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":677,"value":"viewof subsampleTol = new View (0)","pinned":true,"hidden":false,"mode":"ojs"},{"id":679,"value":"viewof minArea = new View (1)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1011,"value":"viewof drawSettings = new View(['maskedImage', 'polygons'])","pinned":true,"hidden":false,"mode":"ojs"},{"id":1224,"value":"viewof showTextureBoxes = new View(false)","pinned":true,"hidden":false,"mode":"ojs"},{"id":999,"value":"viewof inpaintAlgorithm = new View('none')","pinned":true,"hidden":false,"mode":"ojs"},{"id":1336,"value":"viewof animateSegments = new View(true)","pinned":true,"hidden":false,"mode":"ojs"},{"id":971,"value":"comment('The segmented image, mask and polygons')","pinned":true,"hidden":false,"mode":"ojs"},{"id":973,"value":"mutable segmentation = null","pinned":true,"hidden":false,"mode":"ojs"},{"id":1304,"value":"md`## Segmentation algorithms`","pinned":false,"hidden":false,"mode":"ojs"},{"id":145,"value":"comment(`Creates a mask where pixels similar to the background color are made transparent`)","pinned":true,"hidden":false,"mode":"ojs"},{"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"},{"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"},{"id":212,"value":"$34","pinned":true,"hidden":false,"mode":"ojs"},{"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"},{"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"},{"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"},{"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"},{"id":1307,"value":"md`## Inpainting algorithms`","pinned":false,"hidden":false,"mode":"ojs"},{"id":894,"value":"comment('Inpainting by gaussian blur. Does not work well on large \"holes\"')","pinned":false,"hidden":false,"mode":"ojs"},{"id":749,"value":"$35","pinned":true,"hidden":false,"mode":"ojs"},{"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"},{"id":820,"value":"$36","pinned":true,"hidden":false,"mode":"ojs"},{"id":1310,"value":"md`## Topological filters`","pinned":true,"hidden":false,"mode":"ojs"},{"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"},{"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"},{"id":746,"value":"comment('Inverse of `erode()`')","pinned":false,"hidden":false,"mode":"ojs"},{"id":398,"value":"dilate = (maskData)=> erode(maskData,255)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1315,"value":"md`## Texture packing`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":729,"value":"$37","pinned":true,"hidden":false,"mode":"ojs"},{"id":11,"value":"md`## Libraries`","pinned":false,"hidden":false,"mode":"ojs"},{"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"},{"id":2,"value":"import { bindSliderNumber, bindRadioGroup, bindSelect, bindCheckGroup, bindCheckbox, bindFile, View } from \"@esperanc/inline-inputs\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":6,"value":"import { comment } from \"@esperanc/notebook-css-utilities\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":199,"value":"import { Vec, Curve } from \"@esperanc/2d-geometry-utils\"","pinned":true,"hidden":false,"mode":"ojs"},{"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"},{"id":1400,"value":"import { getCirculations } from \"@esperanc/bitmap-tracing\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":750,"value":"comment('Rectangle packing')","pinned":false,"hidden":false,"mode":"ojs"},{"id":732,"value":"potpack = require('potpack@1.0.1/index.js')","pinned":true,"hidden":false,"mode":"ojs"},{"id":996,"value":"comment('The loaded image for the demo')","pinned":false,"hidden":false,"mode":"ojs"},{"id":1418,"value":"images = ({ 'basket' : FileAttachment(\"000R-222.jpg\"),\n 'machine' : FileAttachment(\"000R-138.jpg\"),\n 'geometry' : FileAttachment(\"000R-268.jpg\")\n })","pinned":true,"hidden":false,"mode":"ojs"},{"id":1415,"value":"viewof imageName = new View('basket')","pinned":true,"hidden":false,"mode":"ojs"},{"id":18,"value":"mutable img = images[imageName].image()","pinned":true,"hidden":false,"mode":"ojs"},{"id":908,"value":"viewof imgfile = new View(null)","pinned":true,"hidden":false,"mode":"ojs"},{"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"}],"files":"$W38","stdlib":"1","titling":"auto"}