Computer Graphics & Visualization @ufrj.br
//
// Helps keeping track of the distance from foreground pixels to the closest background pixel
// by marking pixels with the number of thinning steps before were removed
//
class StepCounter {
constructor (wid,hgt) {
[this.dist,this.wid,this.hgt] = [new Int16Array(wid*hgt),wid,hgt]
this.totalSteps = 0
}
// Called at the start of each thinning step
newStep() { this.totalSteps++};
// Called after removing a foreground pixel
mark (col,row) { this.dist[this.wid*row+col] = this.totalSteps; }
// Called for a remaining (not removed) foreground pixel. Returns
// the max number of steps for a removed pixel in its 8-connected neighborhood
distance (col,row) {
let maxDist = 0;
for (let [dcol,drow] of [[-1, -1], [0, -1], [1,-1],
[1, 0], [1, 1], [0, 1],
[-1, 1], [-1, 0]]) {
let d = this.dist[this.wid*(row+drow)+col+dcol];
maxDist = Math.max(d,maxDist)
}
return maxDist
}
}
// 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();
}
// 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();
}
// 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)<<i;
}
return localArtTable[index]>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
}
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.