30:Tb17,// Implementation of Zhang, T. Y. and Suen, Ching Y. (1984). “A Fast Parallel // Algorithm For Thinning Digital Patterns”, Communications of the ACM, Vol 27, No. 3, Maret 1984, pp.236-239. // Input image is an ImageData object, where the alpha channel is used to distinguish foreground from // background pixels. In particular, alpha = 0 is considered background and alpha>0 is considered foreground. // Returns an array of triples [x,y,d] where x,y are the coordinates of a skeleton pixel and d is an estimate // of the distance to the original shape border. function zhangSuen (image) { let wid = image.width; let hgt = image.height; let data = image.data; let data2 = image.data.slice(); // Copy of data let get = (col,row) => +(data[(col+row*wid)*4+3]!=0); let set = (col,row) => { data2[(col+row*wid)*4+3] = 255 }; let clear = (col,row) => { data2[(col+row*wid)*4+3] = 0 }; let stepCounter = new StepCounter(wid,hgt); // Performs the conditional removal of one pixel. Even is true // if this is an even iteration. // Returns 1 if pixel was removed and 0 if not function removePixel(col, row, even) { if (get(col,row) == 0) return 0; // Not 1 pixel let p2 = get(col-1, row); let p3 = get(col-1, row+1); let p4 = get(col, row+1); let p5 = get(col+1, row+1); let p6 = get(col+1, row); let p7 = get(col+1, row-1); let p8 = get(col, row-1); let p9 = get(col-1, row-1); let A = (p2 == 0 && p3 == 1) + (p3 == 0 && p4 == 1) + (p4 == 0 && p5 == 1) + (p5 == 0 && p6 == 1) + (p6 == 0 && p7 == 1) + (p7 == 0 && p8 == 1) + (p8 == 0 && p9 == 1) + (p9 == 0 && p2 == 1); let B = p2 + p3 + p4 + p5 + p6 + p7 + p8 + p9; let m1 = even ? (p2 * p4 * p6) : (p2 * p4 * p8); let m2 = even ? (p4 * p6 * p8) : (p2 * p6 * p8); if (A == 1 && (B >= 2 && B <= 6) && m1 == 0 && m2 == 0) { clear(col,row); stepCounter.mark(col,row); return 1; } return 0; } let even = true; // Performs one thinning step. // Returns the number of removed pixels function thinStep () { let result = 0; for (let row = 1; row < hgt-1; row++) { for (let col = 1; col < wid-1; col++) { result += removePixel(col,row,even); } } even = !even; data.set(data2); // Copy data2 back to data return result; } // Performs the thinning algorithm let n = 0; do { stepCounter.newStep(); n = thinStep() } while (n > 0); // Collect skeleton let collectSkeleton = () => { let skeleton = []; for (let row = 1; row < hgt-1; row++) { for (let col = 1; col < wid-1; col++) { if (get(col,row)) skeleton.push ([col,row,stepCounter.distance(col,row)]); } } return skeleton; } return collectSkeleton(); }31:T956,// Implementation of Guo, Z. and Hall, R.W. (1989). Parallel thinning with two subiteration algorithms, // Communications of the ACM 32(3): 359–373 function guoHall(image) { let wid = image.width; let hgt = image.height; let data = image.data; let data2 = image.data.slice(); // Copy of data let get = (col,row) => +(data[(col+row*wid)*4+3]!=0); let set = (col,row) => { data2[(col+row*wid)*4+3] = 255 }; let clear = (col,row) => { data2[(col+row*wid)*4+3] = 0 }; let stepCounter = new StepCounter(wid,hgt); // Performs the conditional removal of one pixel. Even is true // if this is an even iteration. // Returns 1 if pixel was removed and 0 if not function removePixel(col, row, even) { if (get(col,row) == 0) return 0; // Not 1 pixel let p2 = get(col-1, row); let p3 = get(col-1, row+1); let p4 = get(col, row+1); let p5 = get(col+1, row+1); let p6 = get(col+1, row); let p7 = get(col+1, row-1); let p8 = get(col, row-1); let p9 = get(col-1, row-1); let C = ((1-p2) & (p3 | p4)) + ((1-p4) & (p5 | p6)) + ((1-p6) & (p7 | p8)) + ((1-p8) & (p9 | p2)); if (C!=1) return 0; let N1 = (p9 | p2) + (p3 | p4) + (p5 | p6) + (p7 | p8); let N2 = (p2 | p3) + (p4 | p5) + (p6 | p7) + (p8 | p9); let N = N1 < N2 ? N1 : N2; if (N < 2 || N >3) return 0; let m = even ? ((p6 | p7 | (1-p9)) & p8) : ((p2 | p3 | (1-p5)) & p4); if (m == 0) { clear(col,row); stepCounter.mark(col,row); return 1; } return 0; } let even = true; // Performs one thinning step. // Returns the number of removed pixels function thinStep () { let result = 0; for (let row = 1; row < hgt-1; row++) { for (let col = 1; col < wid-1; col++) { result += removePixel(col,row,even); } } even = !even; data.set(data2); // Copy data2 back to data return result; } // Performs the thinning algorithm let n = 0; do { stepCounter.newStep(); n = thinStep() } while (n > 0); // Collect skeleton let collectSkeleton = () => { let skeleton = []; for (let row = 1; row < hgt-1; row++) { for (let col = 1; col < wid-1; col++) { if (get(col,row)) skeleton.push ([col,row,stepCounter.distance(col,row)]); } } return skeleton; } return collectSkeleton(); }32:T17f4,// Implements David Eberly's algorithm for 2D skeletonization // Details in https://www.geometrictools.com/Documentation/Skeletons.pdf eberly = { // Table that classifies local 8-bit neighborhoods as // to whether they are local articulation points let localArtTable = [ 0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0, 0,1,1,1,1,1,1,1,0,1,0,0,0,1,0,0, 0,1,1,1,1,1,1,1,0,1,0,0,0,1,0,0, 0,1,1,1,1,1,1,1,0,1,0,0,0,1,0,0, 0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 0,1,1,1,1,1,1,1,0,1,0,0,0,1,0,0, 0,1,1,1,1,1,1,1,0,1,0,0,0,1,0,0, 0,0,0,0,1,1,0,0,1,1,0,0,1,1,0,0, 1,1,1,1,1,1,1,1,1,1,0,0,1,1,0,0, 0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,1,1,0,0,1,1,0,0,1,1,0,0, 1,1,1,1,1,1,1,1,1,1,0,0,1,1,0,0, 0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0 ]; // x and y increments to obtain the 8 neighbors of // a pixel let neighbor8C = [ [-1, -1], [0, -1], [1,-1], [1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0]]; function eberly (image) { let wid = image.width; let hgt = image.height; let data = image.data; let stepCounter = new StepCounter(wid,hgt); // binarize let bindata = new Uint8ClampedArray(image.data.length/4); for (let i = 0; i < bindata.length; i++) bindata[i] = data[i*4+3]>0; let get = (col,row) => bindata[col+row*wid]; let set = (col,row,value) => { bindata[col+row*wid] = value }; let isInterior = (col,row) => get(col,row) == 1 && (get(col+1,row) && get(col-1,row) && get(col,row-1) && get(col,row+1)); let is3Interior = (col,row) => get(col,row) == 1 && ((get (col+1,row) > 0) + (get (col-1,row)>0) + (get(col,row-1) > 0) + (get(col,row+1)>0) == 3); let isBoundary = (col,row) => get(col,row) == 1 && (get (col+1,row) == 0 || get (col-1,row) == 0 || get(col,row-1) == 0 || get(col,row+1) == 0); let isLocalArticulation = (col, row) => { if (get (col,row) == 0) return false; let index = 0; for (let i = 0; i < 8; i++) { let [dcol,drow] = neighbor8C[i]; index |= (get (col+dcol,row+drow) > 0)<0; } // Marks the interior pixels with 2 and returns the total number of marked pixels function markInterior () { let count = 0; for (let row = 1; row < hgt-1; row++) { for (let col = 1; col < wid-1; col++) { if (isInterior(col,row)) { set (col,row,2); count++; } } } return count; } // Marks the 3-interior pixels with 3 and returns the total number of // marked pixels function mark3Interior () { let count = 0; for (let row = 1; row < hgt-1; row++) { for (let col = 1; col < wid-1; col++) { if (is3Interior(col,row)) { set (col,row,3); count++; } } } return count; } // Returns true if pixel col,row has a neighbor which is // an interior pixel. Method markInterior must have been // called previously function hasInteriorNeighbor (col, row) { for (let i = 0; i < 8; i++) { if (get (col+neighbor8C[i][0],row+neighbor8C[i][1])==2) return true; } return false; } // Returns true if pixel col,row has a neighbor which is // a 3-interior pixel. Method mark3Interior must have been // called previously function has3InteriorNeighbor (col, row) { for (let i = 0; i < 8; i++) { if (get (col+neighbor8C[i][0],row+neighbor8C[i][1])==3) return true; } return false; } // Performs one step of the Large Scale Thinning Algorithm. // Returns the number of removed pixels function largeScaleThinStep () { let result = 0; if (markInterior () == 0) return 0; for (let row = 1; row < hgt-1; row++) { for (let col = 1; col < wid-1; col++) { if (isBoundary (col,row) && (! isLocalArticulation(col,row)) && hasInteriorNeighbor(col,row)) { stepCounter.mark(col,row); set (col,row,0); result++; } } } // Unmark interior points for (let i = 0; i < bindata.length; i++) if (bindata[i] == 2) bindata[i] = 1; return result; } // Performs the large scale thinning algorithm function largeScaleThin () { stepCounter.newStep(); while (largeScaleThinStep()>0) {stepCounter.newStep();} } // Performs one step of the smaller scale thinning algorithm // returning the number of removed pixels function smallerScaleThinStep () { let result = 0; if (mark3Interior () == 0) return 0; for (let row = 1; row < hgt-1; row++) { for (let col = 1; col < wid-1; col++) { if (isBoundary (col,row) && (! isLocalArticulation(col,row)) && has3InteriorNeighbor(col,row)) { set (col,row,0); //stepCounter.mark(col,row); result++; } } } // Unmark interior points for (let i = 0; i < bindata.length; i++) if (bindata[i] == 3) bindata[i] = 1; return result; } // Perforns the smaller scale thinning algorithm function smallerScaleThin() { while (smallerScaleThinStep()>0) {stepCounter.newStep();} } largeScaleThin() smallerScaleThin() // Unbinarize for (let i = 0; i < bindata.length; i++) data[i*4+3] = bindata[i] == 1 ? 255 : 0; // Collect skeleton let collectSkeleton = () => { let skeleton = []; for (let row = 1; row < hgt-1; row++) { for (let col = 1; col < wid-1; col++) { if (get(col,row)) skeleton.push ([col,row,stepCounter.distance(col,row)]); } } return skeleton; } return collectSkeleton(); } return eberly }33:[] 2e:{"title":"Thinning","cells":[{"id":0,"value":"md`# Thinning\n\n[Thinning algorithms](https://homepages.inf.ed.ac.uk/rbf/HIPR2/thin.htm) are used to obtain skeletons of binary images. The idea is to remove black pixels until only a 1-pixel wide skeleton remains. This skeleton should preserve the connectivity of the original image.\n\nThis notebook contains the implementation of 3 thinning algorithms: Zhang-Suen, Guo-Hall and Eberly. All algorithms modify an input [ImageData](https://developer.mozilla.org/en-US/docs/Web/API/ImageData) object, where the alpha channel is used to distinguish foreground from background pixels. In particular, alpha = 0 is considered background and alpha>0 is considered foreground.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":12,"value":"viewof test = {\n let canvas = DOM.canvas(640,480,1);\n let ctx = canvas.getContext(\"2d\");\n ctx.font = 'bold 60px serif';\n ctx.fillText('Hello world ▇ ▲ ●', 10, 50);\n ctx.font = '14px sans-serif';\n let imgdata = ctx.getImageData(0,0,600,80);\n let skel = []\n skel [0] = zhangSuen(imgdata);\n ctx.putImageData (imgdata,0,80); ctx.fillText ('Zhang Suen', 520,120);\n imgdata = ctx.getImageData(0,0,600,80);\n skel[1] = guoHall(imgdata);\n ctx.putImageData (imgdata,0,160); ctx.fillText ('Guo Hall', 520,200);\n imgdata = ctx.getImageData(0,0,600,80);\n skel[2] = eberly(imgdata)\n ctx.putImageData (imgdata,0,240); ctx.fillText ('Eberly', 520,280);\n canvas.value = skel;\n return canvas;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":211,"value":"md`## Skeletons\n\nAll algorithms also return an array of triples [x,y,d] where x,y are the coordinates of a skeleton pixel and d is an estimate of the distance to the original shape border. This estimate is computed as the number of thinning steps needed to reach that remaining pixel. Below, these skeletons are plotted with 90% transparent balls having radii set to 0.75 of the estimated distance.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":151,"value":"{\n let canvas = DOM.canvas(640,480,1);\n let ctx = canvas.getContext(\"2d\");\n ctx.font = '14px sans-serif';\n let dy = 20;\n let names = [\"Zhang Suen\", \"Guo Hall\", \"Eberly\"];\n for (let s of test) {\n ctx.fillStyle = 'rgba(0,0,0,0.1)';\n for (let [x,y,dist] of s) {\n ctx.beginPath();\n ctx.arc(x,y+dy,dist*0.75,0,Math.PI*2);\n ctx.fill()\n }\n ctx.fillStyle = 'rgba(0,0,0,1)';\n ctx.fillText (names[0], 520,dy+30);\n names.shift()\n dy += 100\n }\n return canvas\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":171,"value":"//\n// Helps keeping track of the distance from foreground pixels to the closest background pixel\n// by marking pixels with the number of thinning steps before were removed\n//\nclass StepCounter {\n \n constructor (wid,hgt) {\n [this.dist,this.wid,this.hgt] = [new Int16Array(wid*hgt),wid,hgt]\n this.totalSteps = 0\n }\n \n // Called at the start of each thinning step\n newStep() { this.totalSteps++};\n\n // Called after removing a foreground pixel\n mark (col,row) { this.dist[this.wid*row+col] = this.totalSteps; }\n \n // Called for a remaining (not removed) foreground pixel. Returns\n // the max number of steps for a removed pixel in its 8-connected neighborhood\n distance (col,row) {\n let maxDist = 0;\n for (let [dcol,drow] of [[-1, -1], [0, -1], [1,-1],\n [1, 0], [1, 1], [0, 1],\n [-1, 1], [-1, 0]]) {\n let d = this.dist[this.wid*(row+drow)+col+dcol];\n maxDist = Math.max(d,maxDist)\n }\n return maxDist\n } \n}\n","pinned":true,"hidden":false,"mode":"ojs"},{"id":107,"value":"$30","pinned":true,"hidden":false,"mode":"ojs"},{"id":6,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":32,"value":"$32","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}