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
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
