🚀 Big News: Socket Acquires Coana to Bring Reachability Analysis to Every Appsec Team.Learn more →
Socket
Book a DemoInstallSign in
Socket
Book a DemoInstallSign in

contours.ts

Package Overview
Dependencies
Maintainers
1
Versions
7
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

contours.ts - npm Package Compare versions

Comparing version

0.1.3
to
0.1.4

66

dist/contours.d.ts
import { ImageDataLike } from './types/ImageDataLike';
import { Point } from './types/Point';
import { Circle, Rectangle } from './types/ShapeType';
interface ContourFinderOptions {
blur: boolean;
threshold: number;
}
/**

@@ -7,5 +12,9 @@ * Contour tracing on a black and white image

export declare class ContourFinder {
private readonly data;
private static readonly THRESHOLD;
private data;
private readonly width;
private readonly height;
private readonly channels;
readonly contours: Point[][];
private isSimplified;
/**

@@ -15,3 +24,3 @@ * Caches information about visited points

private visited;
constructor(imageData: ImageDataLike);
constructor(imageData: ImageDataLike, options?: ContourFinderOptions);
/**

@@ -21,4 +30,12 @@ * Converts x,y to index postion of pixel

*/
pointToIndex(point: Point): number;
private pointToIndex;
/**
* Blurs the image
*/
private blur;
/**
* Threshold image data
*/
private toBitData;
/**
* Returns next clockwise pixel based on current position and direction

@@ -38,34 +55,4 @@ * @param previous previous point

*
* Moore-Neighbor tracing algorithm:
* Moore-Neighbor tracing algorithm: https://en.wikipedia.org/wiki/Moore_neighborhood
*
* Input: A square tessellation, T, containing a connected component P of black cells.
*
* Output: A sequence B (b1, b2 ,..., bk) of boundary pixels i.e. the contour.
*
* Define M(a) to be the Moore neighborhood of pixel a.
* Let p denote the current boundary pixel.
* Let c denote the current pixel under consideration i.e. c is in M(p).
*
* Begin
*
* Set B to be empty.
* From bottom to top and left to right scan the cells of T until a black pixel, s, of P is found.
* Insert s in B.
* Set the current boundary point p to s i.e. p=s
* Backtrack i.e. move to the pixel from which s was entered.
* Set c to be the next clockwise pixel in M(p).
*
* While c not equal to s do
*
* If c is black
* insert c in B
* set p=c
* backtrack (move the current pixel c to the pixel from which p was entered)
* else
* advance the current pixel c to the next clockwise pixel in M(p)
*
* end While
*
* End
*
* @param first first black pixel found

@@ -79,7 +66,12 @@ * @param firstPrevious Previous pixel for first

*/
extract(): Point[][];
private extract;
/**
* Applies threshold to image data
* Simplifies contours using Ramer–Douglas–Peucker algorithm
*/
threshold(): ContourFinder;
simplify(epsilon?: number): ContourFinder;
/**
* Approximate contours to shapes
*/
approximate(): Array<Rectangle | Circle | Point[]>;
}
export {};

283

dist/contours.ts.cjs.development.js

@@ -5,6 +5,2 @@ 'use strict';

function approximate() {
console.log('yay');
}
function _extends() {

@@ -28,5 +24,89 @@ _extends = Object.assign || function (target) {

function distance(p1, p2) {
return Math.sqrt(Math.pow(p2.x - p1.x, 2) + Math.pow(p2.y - p1.y, 2));
}
function perpendicularDistance(point, start, end) {
if (start.x === end.x && start.y === end.y) {
return distance(point, start);
}
return Math.abs((start.y - end.y) * point.x + (end.x - start.x) * point.y + start.x * end.y - end.x * start.y) / distance(start, end);
}
/*
function DouglasPeucker(PointList[], epsilon)
// Find the point with the maximum distance
dmax = 0
index = 0
end = length(PointList)
for i = 2 to (end - 1) {
d = perpendicularDistance(PointList[i], Line(PointList[1], PointList[end]))
if (d > dmax) {
index = i
dmax = d
}
}
ResultList[] = empty;
// If max distance is greater than epsilon, recursively simplify
if (dmax > epsilon) {
// Recursive call
recResults1[] = DouglasPeucker(PointList[1...index], epsilon)
recResults2[] = DouglasPeucker(PointList[index...end], epsilon)
// Build the result list
ResultList[] = {recResults1[1...length(recResults1) - 1], recResults2[1...length(recResults2)]}
} else {
ResultList[] = {PointList[1], PointList[end]}
}
// Return the result
return ResultList[]
end
*/
/**
*
* Ramer–Douglas–Peucker algorithm: https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm
*
* @param contour array of polygon/contour points
* @param epsilon
*/
function RDP(contour, epsilon) {
if (epsilon === void 0) {
epsilon = 1;
}
var endIndex = contour.length - 1;
var collection = [];
var maxDistance = 0;
var index = 0; // no need to simplify 2 points... duh!
if (contour.length <= 2) return contour;
for (var i = 1; i < endIndex; i += 1) {
var _distance = perpendicularDistance(contour[i], contour[0], contour[endIndex]);
if (_distance > maxDistance) {
index = i;
maxDistance = _distance;
}
}
if (maxDistance > epsilon) {
collection = [].concat(RDP(contour.slice(0, index), epsilon), RDP(contour.slice(index, endIndex), epsilon));
} else {
collection = [contour[0], contour[endIndex]];
}
return collection;
}
/**
* Moore neighborhood
*/
var clockwiseOffset = {

@@ -71,6 +151,16 @@ '1,0': {

var ContourFinder = /*#__PURE__*/function () {
function ContourFinder(imageData) {
function ContourFinder(imageData, options) {
if (options === void 0) {
options = {
blur: false,
threshold: 85
};
}
this.contours = [];
this.isSimplified = false;
/**
* Caches information about visited points
*/
this.visited = {};

@@ -80,2 +170,13 @@ this.data = imageData.data;

this.height = imageData.height;
this.channels = this.data.length / (this.width * this.height); // preprocess image if multi channel
if (this.channels > 1) {
// blurs the image for better edge detection
if (options.blur) this.blur(); // threshold image to get bit data
if (options.threshold > 0) this.toBitData(options.threshold);
} // perform contour detection
this.extract();
}

@@ -94,2 +195,56 @@ /**

/**
* Blurs the image
*/
;
_proto.blur = function blur() {
var _this = this;
var _loop = function _loop(x) {
var _loop2 = function _loop2(y) {
var i = _this.pointToIndex({
x: x,
y: y
}); // average each channel of the pixel
var _loop3 = function _loop3(c) {
_this.data[i + c] = Object.values(clockwiseOffset).reduce(function (prev, curr) {
prev += _this.data[_this.pointToIndex({
x: x + curr.x,
y: y + curr.y
})] + c;
return prev;
}, _this.data[i + c]) / 9;
};
for (var c = 0; c < _this.channels; c += 1) {
_loop3(c);
}
};
for (var y = 0; y < _this.height; y += 1) {
_loop2(y);
}
};
for (var x = 0; x < this.width; x += 1) {
_loop(x);
}
}
/**
* Threshold image data
*/
;
_proto.toBitData = function toBitData(threshold) {
var bitData = []; // pixel average
for (var i = 0; i < this.data.length; i += this.channels) {
bitData.push(0.2126 * this.data[i] + 0.7152 * this.data[i + 1] + 0.0722 * this.data[i + 2] >= threshold ? 255 : 0);
}
this.data = bitData;
}
/**
* Returns next clockwise pixel based on current position and direction

@@ -143,36 +298,36 @@ * @param previous previous point

}
/*
Input: A square tessellation, T, containing a connected component P of black cells.
Output: A sequence B (b1, b2, ..., bk) of boundary pixels i.e. the contour.
Define M(a) to be the Moore neighborhood of pixel a.
Let p denote the current boundary pixel.
Let c denote the current pixel under consideration i.e. c is in M(p).
Let b denote the backtrack of c (i.e. neighbor pixel of p that was previously tested)
Begin
Set B to be empty.
From bottom to top and left to right scan the cells of T until a black pixel, s, of P is found.
Insert s in B.
Set the current boundary point p to s i.e. p=s
Let b = the pixel from which s was entered during the image scan.
Set c to be the next clockwise pixel (from b) in M(p).
While c not equal to s do
If c is black
insert c in B
Let b = p
Let p = c
(backtrack: move the current pixel c to the pixel from which p was entered)
Let c = next clockwise pixel (from b) in M(p).
else
(advance the current pixel c to the next clockwise pixel in M(p) and update backtrack)
Let b = c
Let c = next clockwise pixel (from b) in M(p).
end If
end While
End
*/
/**
*
* Moore-Neighbor tracing algorithm:
* Moore-Neighbor tracing algorithm: https://en.wikipedia.org/wiki/Moore_neighborhood
*
* Input: A square tessellation, T, containing a connected component P of black cells.
*
* Output: A sequence B (b1, b2 ,..., bk) of boundary pixels i.e. the contour.
*
* Define M(a) to be the Moore neighborhood of pixel a.
* Let p denote the current boundary pixel.
* Let c denote the current pixel under consideration i.e. c is in M(p).
*
* Begin
*
* Set B to be empty.
* From bottom to top and left to right scan the cells of T until a black pixel, s, of P is found.
* Insert s in B.
* Set the current boundary point p to s i.e. p=s
* Backtrack i.e. move to the pixel from which s was entered.
* Set c to be the next clockwise pixel in M(p).
*
* While c not equal to s do
*
* If c is black
* insert c in B
* set p=c
* backtrack (move the current pixel c to the pixel from which p was entered)
* else
* advance the current pixel c to the next clockwise pixel in M(p)
*
* end While
*
* End
*
* @param first first black pixel found

@@ -225,3 +380,2 @@ * @param firstPrevious Previous pixel for first

_proto.extract = function extract() {
var contours = [];
var skipping = false; // find first black pixel from top-left to bottom-right

@@ -250,3 +404,3 @@

contours.push(this.traceContour({
this.contours.push(this.traceContour({
x: x,

@@ -257,12 +411,30 @@ y: y

}
}
/**
* Simplifies contours using Ramer–Douglas–Peucker algorithm
*/
;
return contours;
_proto.simplify = function simplify(epsilon) {
var _this2 = this;
if (epsilon === void 0) {
epsilon = 1;
}
this.contours.forEach(function (contour, index) {
_this2.contours[index] = RDP(contour, epsilon);
});
this.isSimplified = true;
return this;
}
/**
* Applies threshold to image data
* Approximate contours to shapes
*/
;
_proto.threshold = function threshold() {
return this;
_proto.approximate = function approximate() {
if (!this.isSimplified) this.simplify(); // TODO: approximate contours
return [];
};

@@ -272,30 +444,5 @@

}();
ContourFinder.THRESHOLD = 85;
// https://rosettacode.org/wiki/Ramer-Douglas-Peucker_line_simplification#JavaScript
function RDP(contour, eps) {
var lastIndex = contour.length - 1;
var firstPoint = contour[0];
var lastPoint = contour[lastIndex];
var x21 = lastPoint.x - firstPoint.x;
var y21 = lastPoint.y - firstPoint.y;
var _contour$slice$map$re = contour.slice(1, lastIndex).map(function (p) {
return Math.abs(y21 * p.x - x21 * p.y + lastPoint.x * firstPoint.y - lastPoint.y * firstPoint.x);
}).reduce(function (p, c, i) {
var v = Math.max(p[0], c);
return [v, v === p[0] ? p[1] : i + 1];
}, [-1, 0]),
dMax = _contour$slice$map$re[0],
x = _contour$slice$map$re[1];
if (dMax > eps) {
return [].concat(RDP(contour.slice(0, x + 1), eps), RDP(contour.slice(x), eps).slice(1));
}
return [contour[0], contour[lastIndex]];
}
exports.ContourFinder = ContourFinder;
exports.RDP = RDP;
exports.approximate = approximate;
//# sourceMappingURL=contours.ts.cjs.development.js.map

2

dist/contours.ts.cjs.production.min.js

@@ -1,2 +0,2 @@

"use strict";function t(){return(t=Object.assign||function(t){for(var i=1;i<arguments.length;i++){var r=arguments[i];for(var e in r)Object.prototype.hasOwnProperty.call(r,e)&&(t[e]=r[e])}return t}).apply(this,arguments)}Object.defineProperty(exports,"__esModule",{value:!0});var i={"1,0":{x:1,y:1},"1,1":{x:0,y:1},"0,1":{x:-1,y:1},"-1,1":{x:-1,y:0},"-1,0":{x:-1,y:-1},"-1,-1":{x:0,y:-1},"0,-1":{x:1,y:-1},"1,-1":{x:1,y:0}};exports.ContourFinder=function(){function r(t){this.visited={},this.data=t.data,this.width=t.width,this.height=t.height}var e=r.prototype;return e.pointToIndex=function(t){return t.y*this.width+t.x},e.nextClockwise=function(t){var r=t.previous,e=t.boundary,n=t.start,o=void 0===n?r:n,s=i[r.x-e.x+","+(r.y-e.y)],a={x:e.x+s.x,y:e.y+s.y};return a.x<0||a.y<0||a.x>=this.width||a.y>=this.height?this.nextClockwise({previous:a,boundary:e,start:o}):a.x===o.x&&a.y===o.y?{previous:a,boundary:e}:0===this.data[this.pointToIndex(a)]?{previous:r,boundary:a}:this.nextClockwise({previous:a,boundary:e,start:o})},e.traceContour=function(i){var r=[t({},i)],e={x:i.x,y:i.y+1},n=t({},i),o=t({},e);do{var s=this.nextClockwise({previous:o,boundary:n});o=s.previous;var a=this.pointToIndex(n=s.boundary);this.visited[a]||(r.push(n),this.visited[a]=!0)}while(o.x!==e.x||o.y!==e.y||n.x!==i.x||n.y!==i.y);return r},e.extract=function(){for(var t=[],i=!1,r=0;r<this.width;r+=1)for(var e=this.height-1;e>=0;e-=1){var n=this.pointToIndex({x:r,y:e});0===this.data[n]?this.visited[n]||i?i=!0:(this.visited[n]=!0,t.push(this.traceContour({x:r,y:e}))):i=!1}return t},e.threshold=function(){return this},r}(),exports.RDP=function t(i,r){var e=i.length-1,n=i[0],o=i[e],s=o.x-n.x,a=o.y-n.y,h=i.slice(1,e).map((function(t){return Math.abs(a*t.x-s*t.y+o.x*n.y-o.y*n.x)})).reduce((function(t,i,r){var e=Math.max(t[0],i);return[e,e===t[0]?t[1]:r+1]}),[-1,0]),u=h[1];return h[0]>r?[].concat(t(i.slice(0,u+1),r),t(i.slice(u),r).slice(1)):[i[0],i[e]]},exports.approximate=function(){console.log("yay")};
"use strict";function t(){return(t=Object.assign||function(t){for(var i=1;i<arguments.length;i++){var r=arguments[i];for(var n in r)Object.prototype.hasOwnProperty.call(r,n)&&(t[n]=r[n])}return t}).apply(this,arguments)}function i(t,i){return Math.sqrt(Math.pow(i.x-t.x,2)+Math.pow(i.y-t.y,2))}Object.defineProperty(exports,"__esModule",{value:!0});var r={"1,0":{x:1,y:1},"1,1":{x:0,y:1},"0,1":{x:-1,y:1},"-1,1":{x:-1,y:0},"-1,0":{x:-1,y:-1},"-1,-1":{x:0,y:-1},"0,-1":{x:1,y:-1},"1,-1":{x:1,y:0}},n=function(){function n(t,i){void 0===i&&(i={blur:!1,threshold:85}),this.contours=[],this.isSimplified=!1,this.visited={},this.data=t.data,this.width=t.width,this.height=t.height,this.channels=this.data.length/(this.width*this.height),this.channels>1&&(i.blur&&this.blur(),i.threshold>0&&this.toBitData(i.threshold)),this.extract()}var s=n.prototype;return s.pointToIndex=function(t){return t.y*this.width+t.x},s.blur=function(){for(var t=this,i=function(i){for(var n=function(n){for(var s=t.pointToIndex({x:i,y:n}),o=function(o){t.data[s+o]=Object.values(r).reduce((function(r,s){return r+(t.data[t.pointToIndex({x:i+s.x,y:n+s.y})]+o)}),t.data[s+o])/9},h=0;h<t.channels;h+=1)o(h)},s=0;s<t.height;s+=1)n(s)},n=0;n<this.width;n+=1)i(n)},s.toBitData=function(t){for(var i=[],r=0;r<this.data.length;r+=this.channels)i.push(.2126*this.data[r]+.7152*this.data[r+1]+.0722*this.data[r+2]>=t?255:0);this.data=i},s.nextClockwise=function(t){var i=t.previous,n=t.boundary,s=t.start,o=void 0===s?i:s,h=r[i.x-n.x+","+(i.y-n.y)],e={x:n.x+h.x,y:n.y+h.y};return e.x<0||e.y<0||e.x>=this.width||e.y>=this.height?this.nextClockwise({previous:e,boundary:n,start:o}):e.x===o.x&&e.y===o.y?{previous:e,boundary:n}:0===this.data[this.pointToIndex(e)]?{previous:i,boundary:e}:this.nextClockwise({previous:e,boundary:n,start:o})},s.traceContour=function(i){var r=[t({},i)],n={x:i.x,y:i.y+1},s=t({},i),o=t({},n);do{var h=this.nextClockwise({previous:o,boundary:s});o=h.previous;var e=this.pointToIndex(s=h.boundary);this.visited[e]||(r.push(s),this.visited[e]=!0)}while(o.x!==n.x||o.y!==n.y||s.x!==i.x||s.y!==i.y);return r},s.extract=function(){for(var t=!1,i=0;i<this.width;i+=1)for(var r=this.height-1;r>=0;r-=1){var n=this.pointToIndex({x:i,y:r});0===this.data[n]?this.visited[n]||t?t=!0:(this.visited[n]=!0,this.contours.push(this.traceContour({x:i,y:r}))):t=!1}},s.simplify=function(t){var r=this;return void 0===t&&(t=1),this.contours.forEach((function(n,s){r.contours[s]=function t(r,n){void 0===n&&(n=1);var s,o,h,e=r.length-1,a=0,u=0;if(r.length<=2)return r;for(var d=1;d<e;d+=1){var x=(s=r[d],(o=r[0]).x===(h=r[e]).x&&o.y===h.y?i(s,o):Math.abs((o.y-h.y)*s.x+(h.x-o.x)*s.y+o.x*h.y-h.x*o.y)/i(o,h));x>a&&(u=d,a=x)}return a>n?[].concat(t(r.slice(0,u),n),t(r.slice(u,e),n)):[r[0],r[e]]}(n,t)})),this.isSimplified=!0,this},s.approximate=function(){return this.isSimplified||this.simplify(),[]},n}();n.THRESHOLD=85,exports.ContourFinder=n;
//# sourceMappingURL=contours.ts.cjs.production.min.js.map

283

dist/contours.ts.esm.js

@@ -1,5 +0,1 @@

function approximate() {
console.log('yay');
}
function _extends() {

@@ -23,5 +19,89 @@ _extends = Object.assign || function (target) {

function distance(p1, p2) {
return Math.sqrt(Math.pow(p2.x - p1.x, 2) + Math.pow(p2.y - p1.y, 2));
}
function perpendicularDistance(point, start, end) {
if (start.x === end.x && start.y === end.y) {
return distance(point, start);
}
return Math.abs((start.y - end.y) * point.x + (end.x - start.x) * point.y + start.x * end.y - end.x * start.y) / distance(start, end);
}
/*
function DouglasPeucker(PointList[], epsilon)
// Find the point with the maximum distance
dmax = 0
index = 0
end = length(PointList)
for i = 2 to (end - 1) {
d = perpendicularDistance(PointList[i], Line(PointList[1], PointList[end]))
if (d > dmax) {
index = i
dmax = d
}
}
ResultList[] = empty;
// If max distance is greater than epsilon, recursively simplify
if (dmax > epsilon) {
// Recursive call
recResults1[] = DouglasPeucker(PointList[1...index], epsilon)
recResults2[] = DouglasPeucker(PointList[index...end], epsilon)
// Build the result list
ResultList[] = {recResults1[1...length(recResults1) - 1], recResults2[1...length(recResults2)]}
} else {
ResultList[] = {PointList[1], PointList[end]}
}
// Return the result
return ResultList[]
end
*/
/**
*
* Ramer–Douglas–Peucker algorithm: https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm
*
* @param contour array of polygon/contour points
* @param epsilon
*/
function RDP(contour, epsilon) {
if (epsilon === void 0) {
epsilon = 1;
}
var endIndex = contour.length - 1;
var collection = [];
var maxDistance = 0;
var index = 0; // no need to simplify 2 points... duh!
if (contour.length <= 2) return contour;
for (var i = 1; i < endIndex; i += 1) {
var _distance = perpendicularDistance(contour[i], contour[0], contour[endIndex]);
if (_distance > maxDistance) {
index = i;
maxDistance = _distance;
}
}
if (maxDistance > epsilon) {
collection = [].concat(RDP(contour.slice(0, index), epsilon), RDP(contour.slice(index, endIndex), epsilon));
} else {
collection = [contour[0], contour[endIndex]];
}
return collection;
}
/**
* Moore neighborhood
*/
var clockwiseOffset = {

@@ -66,6 +146,16 @@ '1,0': {

var ContourFinder = /*#__PURE__*/function () {
function ContourFinder(imageData) {
function ContourFinder(imageData, options) {
if (options === void 0) {
options = {
blur: false,
threshold: 85
};
}
this.contours = [];
this.isSimplified = false;
/**
* Caches information about visited points
*/
this.visited = {};

@@ -75,2 +165,13 @@ this.data = imageData.data;

this.height = imageData.height;
this.channels = this.data.length / (this.width * this.height); // preprocess image if multi channel
if (this.channels > 1) {
// blurs the image for better edge detection
if (options.blur) this.blur(); // threshold image to get bit data
if (options.threshold > 0) this.toBitData(options.threshold);
} // perform contour detection
this.extract();
}

@@ -89,2 +190,56 @@ /**

/**
* Blurs the image
*/
;
_proto.blur = function blur() {
var _this = this;
var _loop = function _loop(x) {
var _loop2 = function _loop2(y) {
var i = _this.pointToIndex({
x: x,
y: y
}); // average each channel of the pixel
var _loop3 = function _loop3(c) {
_this.data[i + c] = Object.values(clockwiseOffset).reduce(function (prev, curr) {
prev += _this.data[_this.pointToIndex({
x: x + curr.x,
y: y + curr.y
})] + c;
return prev;
}, _this.data[i + c]) / 9;
};
for (var c = 0; c < _this.channels; c += 1) {
_loop3(c);
}
};
for (var y = 0; y < _this.height; y += 1) {
_loop2(y);
}
};
for (var x = 0; x < this.width; x += 1) {
_loop(x);
}
}
/**
* Threshold image data
*/
;
_proto.toBitData = function toBitData(threshold) {
var bitData = []; // pixel average
for (var i = 0; i < this.data.length; i += this.channels) {
bitData.push(0.2126 * this.data[i] + 0.7152 * this.data[i + 1] + 0.0722 * this.data[i + 2] >= threshold ? 255 : 0);
}
this.data = bitData;
}
/**
* Returns next clockwise pixel based on current position and direction

@@ -138,36 +293,36 @@ * @param previous previous point

}
/*
Input: A square tessellation, T, containing a connected component P of black cells.
Output: A sequence B (b1, b2, ..., bk) of boundary pixels i.e. the contour.
Define M(a) to be the Moore neighborhood of pixel a.
Let p denote the current boundary pixel.
Let c denote the current pixel under consideration i.e. c is in M(p).
Let b denote the backtrack of c (i.e. neighbor pixel of p that was previously tested)
Begin
Set B to be empty.
From bottom to top and left to right scan the cells of T until a black pixel, s, of P is found.
Insert s in B.
Set the current boundary point p to s i.e. p=s
Let b = the pixel from which s was entered during the image scan.
Set c to be the next clockwise pixel (from b) in M(p).
While c not equal to s do
If c is black
insert c in B
Let b = p
Let p = c
(backtrack: move the current pixel c to the pixel from which p was entered)
Let c = next clockwise pixel (from b) in M(p).
else
(advance the current pixel c to the next clockwise pixel in M(p) and update backtrack)
Let b = c
Let c = next clockwise pixel (from b) in M(p).
end If
end While
End
*/
/**
*
* Moore-Neighbor tracing algorithm:
* Moore-Neighbor tracing algorithm: https://en.wikipedia.org/wiki/Moore_neighborhood
*
* Input: A square tessellation, T, containing a connected component P of black cells.
*
* Output: A sequence B (b1, b2 ,..., bk) of boundary pixels i.e. the contour.
*
* Define M(a) to be the Moore neighborhood of pixel a.
* Let p denote the current boundary pixel.
* Let c denote the current pixel under consideration i.e. c is in M(p).
*
* Begin
*
* Set B to be empty.
* From bottom to top and left to right scan the cells of T until a black pixel, s, of P is found.
* Insert s in B.
* Set the current boundary point p to s i.e. p=s
* Backtrack i.e. move to the pixel from which s was entered.
* Set c to be the next clockwise pixel in M(p).
*
* While c not equal to s do
*
* If c is black
* insert c in B
* set p=c
* backtrack (move the current pixel c to the pixel from which p was entered)
* else
* advance the current pixel c to the next clockwise pixel in M(p)
*
* end While
*
* End
*
* @param first first black pixel found

@@ -220,3 +375,2 @@ * @param firstPrevious Previous pixel for first

_proto.extract = function extract() {
var contours = [];
var skipping = false; // find first black pixel from top-left to bottom-right

@@ -245,3 +399,3 @@

contours.push(this.traceContour({
this.contours.push(this.traceContour({
x: x,

@@ -252,12 +406,30 @@ y: y

}
}
/**
* Simplifies contours using Ramer–Douglas–Peucker algorithm
*/
;
return contours;
_proto.simplify = function simplify(epsilon) {
var _this2 = this;
if (epsilon === void 0) {
epsilon = 1;
}
this.contours.forEach(function (contour, index) {
_this2.contours[index] = RDP(contour, epsilon);
});
this.isSimplified = true;
return this;
}
/**
* Applies threshold to image data
* Approximate contours to shapes
*/
;
_proto.threshold = function threshold() {
return this;
_proto.approximate = function approximate() {
if (!this.isSimplified) this.simplify(); // TODO: approximate contours
return [];
};

@@ -267,28 +439,5 @@

}();
ContourFinder.THRESHOLD = 85;
// https://rosettacode.org/wiki/Ramer-Douglas-Peucker_line_simplification#JavaScript
function RDP(contour, eps) {
var lastIndex = contour.length - 1;
var firstPoint = contour[0];
var lastPoint = contour[lastIndex];
var x21 = lastPoint.x - firstPoint.x;
var y21 = lastPoint.y - firstPoint.y;
var _contour$slice$map$re = contour.slice(1, lastIndex).map(function (p) {
return Math.abs(y21 * p.x - x21 * p.y + lastPoint.x * firstPoint.y - lastPoint.y * firstPoint.x);
}).reduce(function (p, c, i) {
var v = Math.max(p[0], c);
return [v, v === p[0] ? p[1] : i + 1];
}, [-1, 0]),
dMax = _contour$slice$map$re[0],
x = _contour$slice$map$re[1];
if (dMax > eps) {
return [].concat(RDP(contour.slice(0, x + 1), eps), RDP(contour.slice(x), eps).slice(1));
}
return [contour[0], contour[lastIndex]];
}
export { ContourFinder, RDP, approximate };
export { ContourFinder };
//# sourceMappingURL=contours.ts.esm.js.map

2

dist/index.d.ts

@@ -1,3 +0,1 @@

export * from './approximate';
export * from './contours';
export * from './rdp';

10

dist/rdp.d.ts
import { Point } from './types/Point';
export declare function RDP(contour: Point[], eps: number): Point[];
export declare function perpendicularDistance(point: Point, start: Point, end: Point): number;
/**
*
* Ramer–Douglas–Peucker algorithm: https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm
*
* @param contour array of polygon/contour points
* @param epsilon
*/
export declare function RDP(contour: Point[], epsilon?: number): Point[];

26

package.json

@@ -6,10 +6,11 @@ {

"devDependencies": {
"@size-limit/preset-small-lib": "^4.9.0",
"@types/eslint": "^7.2.5",
"@size-limit/preset-small-lib": "^4.9.1",
"@types/eslint": "^7.2.6",
"@types/eslint-plugin-prettier": "^3.1.0",
"@types/jest": "^26.0.15",
"@typescript-eslint/eslint-plugin": "^4.8.2",
"@typescript-eslint/parser": "^4.8.2",
"eslint": "^7.14.0",
"eslint-config-prettier": "^6.15.0",
"@types/jest": "^26.0.19",
"@typescript-eslint/eslint-plugin": "^4.9.1",
"@typescript-eslint/parser": "^4.9.1",
"babel-eslint": "^10.1.0",
"eslint": "^7.15.0",
"eslint-config-prettier": "^7.0.0",
"eslint-config-react-app": "^6.0.0",

@@ -23,3 +24,3 @@ "eslint-config-standard": "^16.0.2",

"eslint-plugin-node": "^11.1.0",
"eslint-plugin-prettier": "^3.1.4",
"eslint-plugin-prettier": "^3.2.0",
"eslint-plugin-promise": "^4.2.1",

@@ -29,9 +30,10 @@ "eslint-plugin-react": "^7.21.5",

"eslint-plugin-standard": "^4.1.0",
"husky": "^4.3.0",
"husky": "^4.3.5",
"jest": "^26.6.3",
"size-limit": "^4.9.0",
"prettier": "^2.2.1",
"size-limit": "^4.9.1",
"ts-jest": "^26.4.4",
"tsdx": "^0.14.1",
"tslib": "^2.0.3",
"typescript": "^4.1.2"
"typescript": "^4.1.3"
},

@@ -94,3 +96,3 @@ "engines": {

"typings": "dist/index.d.ts",
"version": "0.1.3"
"version": "0.1.4"
}

153

README.md
# Contours.ts
Extract shapes & contours in an image, for browsers and node.js.
Extract contours & shapes from an image, for browsers and node.js.
[![NPM](https://nodei.co/npm/contours.ts.png?compact=true)](https://nodei.co/npm/contours.ts/)
![CI](https://github.com/mubaidr/contours.ts/workflows/CI/badge.svg)
[![codecov](https://codecov.io/gh/mubaidr/contours.ts/branch/master/graph/badge.svg?token=3SJIBJ1679)](https://codecov.io/gh/mubaidr/contours.ts)
[![codebeat badge](https://codebeat.co/badges/0c5399f3-60d7-466f-b87d-94dcc0b47d9f)](https://codebeat.co/projects/github-com-mubaidr-contours-ts-master)
[![codecov](https://codecov.io/gh/mubaidr/contours.ts/branch/master/graph/badge.svg?token=3SJIBJ1679)](https://codecov.io/gh/mubaidr/contours.ts)
[![All Contributors](https://img.shields.io/badge/all_contributors-1-orange.svg?style=flat-square)](#contributors)
[![NPM](https://nodei.co/npm/contours.ts.png)](https://nodei.co/npm/contours.ts/)
<!-- ALL-CONTRIBUTORS-BADGE:START - Do not remove or modify this section -->
<a href="https://patreon.com/mubaidr">
<img src="https://c5.patreon.com/external/logo/become_a_patron_button@2x.png" height="45">
</a>
[![All Contributors](https://img.shields.io/badge/all_contributors-1-orange.svg)](#contributors-)
<!-- ALL-CONTRIBUTORS-BADGE:END -->
## Features
### Extract Contours
### Approximate Contours to Shapes
## How to use
### Use
### Install
#### using pckage manager:
```bash
npm i contours.ts
```
Or
#### add to your webpage:
```html
<script src="unpkg.com/contours.ts"></script>
```
Or
#### download manually:
[Contours.ts](https://unpkg.com/contours.ts)
### Examples
#### Input Type
`ContourFinder` expects image data (multi-channel image data is suported) in following format:
```ts
import { ContourFinder } from 'contours.ts'
/*
if `imageData` is like `{
const imageData: {
data: number[] | Uint8ClampedArray
width: number
height: number
}`
} = {
data: [0,0,0],
width: 1,
height: 1
}
*/
```
const contours = new ContourFinder(imageData).threshold().extract()
#### Get Contours
```ts
import { ContourFinder } from 'contours.ts'
const { contours } = new ContourFinder(imageData, {
blur: true // blurs the image data
threshold: 85 // threshold image data
})
console.log(contours)
/*
- `contours` is collection of contours found in image
- each contour is collection of points.
e.g.
logs:
[
[{x: 0, y: 0}, {x: 1, y: 0}], //contour
[{x: 0, y: 1}, {x: 0, y: 0}, {x: 1, y: 0}, {x: 1, y: 1}] // another contour
[{x: 0, y: 0}, {x: 1, y: 0}], // contour
[{x: 0, y: 0}, {x: 1, y: 1}, {x: 2, y: 2}, {x: 3, y: 3}] // another contour
]
*/
```
### Install
#### Simplify Contours
Recommended way to install is by using package manager (npm, yarn etc):
```ts
import { ContourFinder } from 'contours.ts'
// simplify contours using Ramer–Douglas–Peucker algorithm
const { simplifiedContours } = new ContourFinder(imageData).simplify(epsilon)
```bash
npm i contours.ts
console.log(simplifiedContours)
/*
logs:
[
[{x: 0, y: 0}, {x: 1, y: 0}], // contour
[{x: 0, y: 0}, {x: 3, y: 3}] // another contour
]
*/
```
or use cdn:
#### Approximate Shapes
```html
<script src="//unpkg.com/contours.ts"></script>
```
```ts
import { ContourFinder } from 'contours.ts'
// Or approximate contours to shapes
const { shapeCollection } = new ContourFinder(imageData).approximate()
or download manually:
console.log(shapeCollection)
[contours.ts](https://unpkg.com/contours.ts)
/*
logs:
[
{x: 0, y: 0, width: 1, height: 1}, // Rect
{x: 1, y: 1, radius: 1}, // Circle
[{x: 0, y: 0}, {x: 3, y: 3}] // Polygon
]
*/
```
## Contributions
Contirbutions are welcome, entire code base is filled with comments and `tests` are defined using `jest`
Contirbutions are welcome, code is heavily commented and `tests` are defined using `jest`
## License
Distributed under the MIT License. See `LICENSE` for more information.
## Contact
Muhammad Ubaid Raza - [@mubaidr](https://twitter.com/mubaidr) - mubaidr@gmail.com
## Acknowledgements
This project is heavily inspired by the these:
- [benfoxall/contours](https://github.com/benfoxall/contours)
- [dkendal/moore-neighbor_contour_tracer](https://github.com/Dkendal/Moore-Neighbor_Contour_Tracer)
## Contributors ✨
Thanks goes to these wonderful people ([emoji key](https://allcontributors.org/docs/en/emoji-key)):
<!-- ALL-CONTRIBUTORS-LIST:START - Do not remove or modify this section -->
<!-- prettier-ignore-start -->
<!-- markdownlint-disable -->
<table>
<tr>
<td align="center"><a href="https://benjaminbenben.com"><img src="https://avatars3.githubusercontent.com/u/51385?v=4" width="100px;" alt=""/><br /><sub><b>Ben Foxall</b></sub></a><br /><a href="https://github.com/mubaidr/contours.ts/commits?author=benfoxall" title="Code">💻</a></td>
</tr>
</table>
<!-- markdownlint-enable -->
<!-- prettier-ignore-end -->
<!-- ALL-CONTRIBUTORS-LIST:END -->
This project follows the [all-contributors](https://github.com/all-contributors/all-contributors) specification. Contributions of any kind welcome!

181

src/contours.ts

@@ -0,3 +1,5 @@

import { RDP } from './rdp'
import { ImageDataLike } from './types/ImageDataLike'
import { Point } from './types/Point'
import { Circle, Rectangle } from './types/ShapeType'

@@ -23,2 +25,7 @@ /**

interface ContourFinderOptions {
blur: boolean
threshold: number
}
/**

@@ -28,6 +35,13 @@ * Contour tracing on a black and white image

export class ContourFinder {
private readonly data: Uint8ClampedArray | number[]
private static readonly THRESHOLD = 85
private data: Uint8ClampedArray | number[]
private readonly width: number
private readonly height: number
private readonly channels: number
public readonly contours: Point[][] = []
private isSimplified = false
/**

@@ -38,6 +52,25 @@ * Caches information about visited points

constructor(imageData: ImageDataLike) {
constructor(
imageData: ImageDataLike,
options: ContourFinderOptions = {
blur: false,
threshold: 85,
}
) {
this.data = imageData.data
this.width = imageData.width
this.height = imageData.height
this.channels = this.data.length / (this.width * this.height)
// preprocess image if multi channel
if (this.channels > 1) {
// blurs the image for better edge detection
if (options.blur) this.blur()
// threshold image to get bit data
if (options.threshold > 0) this.toBitData(options.threshold)
}
// perform contour detection
this.extract()
}

@@ -49,3 +82,3 @@

*/
pointToIndex(point: Point): number {
private pointToIndex(point: Point): number {
return point.y * this.width + point.x

@@ -55,2 +88,53 @@ }

/**
* Blurs the image
*/
private blur(): void {
for (let x = 0; x < this.width; x += 1) {
for (let y = 0; y < this.height; y += 1) {
const i = this.pointToIndex({
x,
y,
})
// average each channel of the pixel
for (let c = 0; c < this.channels; c += 1) {
this.data[i + c] =
Object.values(clockwiseOffset).reduce((prev, curr) => {
prev +=
this.data[
this.pointToIndex({
x: x + curr.x,
y: y + curr.y,
})
] + c
return prev
}, this.data[i + c]) / 9
}
}
}
}
/**
* Threshold image data
*/
private toBitData(threshold: number): void {
const bitData: number[] = []
// pixel average
for (let i = 0; i < this.data.length; i += this.channels) {
bitData.push(
0.2126 * this.data[i] +
0.7152 * this.data[i + 1] +
0.0722 * this.data[i + 2] >=
threshold
? 255
: 0
)
}
this.data = bitData
}
/**
* Returns next clockwise pixel based on current position and direction

@@ -110,36 +194,39 @@ * @param previous previous point

/*
Input: A square tessellation, T, containing a connected component P of black cells.
Output: A sequence B (b1, b2, ..., bk) of boundary pixels i.e. the contour.
Define M(a) to be the Moore neighborhood of pixel a.
Let p denote the current boundary pixel.
Let c denote the current pixel under consideration i.e. c is in M(p).
Let b denote the backtrack of c (i.e. neighbor pixel of p that was previously tested)
Begin
Set B to be empty.
From bottom to top and left to right scan the cells of T until a black pixel, s, of P is found.
Insert s in B.
Set the current boundary point p to s i.e. p=s
Let b = the pixel from which s was entered during the image scan.
Set c to be the next clockwise pixel (from b) in M(p).
While c not equal to s do
If c is black
insert c in B
Let b = p
Let p = c
(backtrack: move the current pixel c to the pixel from which p was entered)
Let c = next clockwise pixel (from b) in M(p).
else
(advance the current pixel c to the next clockwise pixel in M(p) and update backtrack)
Let b = c
Let c = next clockwise pixel (from b) in M(p).
end If
end While
End
*/
/**
*
* Moore-Neighbor tracing algorithm:
* Moore-Neighbor tracing algorithm: https://en.wikipedia.org/wiki/Moore_neighborhood
*
* Input: A square tessellation, T, containing a connected component P of black cells.
*
* Output: A sequence B (b1, b2 ,..., bk) of boundary pixels i.e. the contour.
*
* Define M(a) to be the Moore neighborhood of pixel a.
* Let p denote the current boundary pixel.
* Let c denote the current pixel under consideration i.e. c is in M(p).
*
* Begin
*
* Set B to be empty.
* From bottom to top and left to right scan the cells of T until a black pixel, s, of P is found.
* Insert s in B.
* Set the current boundary point p to s i.e. p=s
* Backtrack i.e. move to the pixel from which s was entered.
* Set c to be the next clockwise pixel in M(p).
*
* While c not equal to s do
*
* If c is black
* insert c in B
* set p=c
* backtrack (move the current pixel c to the pixel from which p was entered)
* else
* advance the current pixel c to the next clockwise pixel in M(p)
*
* end While
*
* End
*
* @param first first black pixel found

@@ -192,4 +279,3 @@ * @param firstPrevious Previous pixel for first

*/
public extract(): Point[][] {
const contours: Point[][] = []
private extract(): void {
let skipping = false

@@ -218,3 +304,3 @@

// we will trace contour starting from this black pixel
contours.push(
this.contours.push(
this.traceContour({

@@ -227,13 +313,26 @@ x,

}
return contours
}
/**
* Applies threshold to image data
* Simplifies contours using Ramer–Douglas–Peucker algorithm
*/
public simplify(epsilon = 1): ContourFinder {
this.contours.forEach((contour, index) => {
this.contours[index] = RDP(contour, epsilon)
})
public threshold(): ContourFinder {
this.isSimplified = true
return this
}
/**
* Approximate contours to shapes
*/
public approximate(): Array<Rectangle | Circle | Point[]> {
if (!this.isSimplified) this.simplify()
// TODO: approximate contours
return []
}
}

2

src/index.ts

@@ -1,3 +0,1 @@

export * from './approximate'
export * from './contours'
export * from './rdp'

119

src/rdp.ts

@@ -1,38 +0,99 @@

// https://rosettacode.org/wiki/Ramer-Douglas-Peucker_line_simplification#JavaScript
import { Point } from './types/Point'
export function RDP(contour: Point[], eps: number): Point[] {
const lastIndex = contour.length - 1
const firstPoint = contour[0]
const lastPoint = contour[lastIndex]
const x21 = lastPoint.x - firstPoint.x
const y21 = lastPoint.y - firstPoint.y
function distance(p1: Point, p2: Point): number {
return Math.sqrt((p2.x - p1.x) ** 2 + (p2.y - p1.y) ** 2)
}
const [dMax, x] = contour
.slice(1, lastIndex)
.map((p: { x: number; y: number }) =>
Math.abs(
y21 * p.x -
x21 * p.y +
lastPoint.x * firstPoint.y -
lastPoint.y * firstPoint.x
)
export function perpendicularDistance(
point: Point,
start: Point,
end: Point
): number {
if (start.x === end.x && start.y === end.y) {
return distance(point, start)
}
return (
Math.abs(
(start.y - end.y) * point.x +
(end.x - start.x) * point.y +
start.x * end.y -
end.x * start.y
) / distance(start, end)
)
}
/*
function DouglasPeucker(PointList[], epsilon)
// Find the point with the maximum distance
dmax = 0
index = 0
end = length(PointList)
for i = 2 to (end - 1) {
d = perpendicularDistance(PointList[i], Line(PointList[1], PointList[end]))
if (d > dmax) {
index = i
dmax = d
}
}
ResultList[] = empty;
// If max distance is greater than epsilon, recursively simplify
if (dmax > epsilon) {
// Recursive call
recResults1[] = DouglasPeucker(PointList[1...index], epsilon)
recResults2[] = DouglasPeucker(PointList[index...end], epsilon)
// Build the result list
ResultList[] = {recResults1[1...length(recResults1) - 1], recResults2[1...length(recResults2)]}
} else {
ResultList[] = {PointList[1], PointList[end]}
}
// Return the result
return ResultList[]
end
*/
/**
*
* Ramer–Douglas–Peucker algorithm: https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm
*
* @param contour array of polygon/contour points
* @param epsilon
*/
export function RDP(contour: Point[], epsilon = 1): Point[] {
const endIndex = contour.length - 1
let collection: Point[] = []
let maxDistance = 0
let index = 0
// no need to simplify 2 points... duh!
if (contour.length <= 2) return contour
for (let i = 1; i < endIndex; i += 1) {
const distance = perpendicularDistance(
contour[i],
contour[0],
contour[endIndex]
)
.reduce(
(p: number[], c: number, i: number) => {
const v = Math.max(p[0], c)
return [v, v === p[0] ? p[1] : i + 1]
},
[-1, 0]
)
if (dMax > eps) {
return [
...RDP(contour.slice(0, x + 1), eps),
...RDP(contour.slice(x), eps).slice(1),
if (distance > maxDistance) {
index = i
maxDistance = distance
}
}
if (maxDistance > epsilon) {
collection = [
...RDP(contour.slice(0, index), epsilon),
...RDP(contour.slice(index, endIndex), epsilon),
]
} else {
collection = [contour[0], contour[endIndex]]
}
return [contour[0], contour[lastIndex]]
return collection
}

0

src/types/ImageDataLike.ts

@@ -0,0 +0,0 @@ export interface ImageDataLike {

0

src/types/Point.ts

@@ -0,0 +0,0 @@ export interface Point {

0

src/types/ShapeType.ts

@@ -0,0 +0,0 @@ export enum ShapeTypes {

dist/approximate.d.ts
src/approximate.ts
dist/contours.ts.cjs.development.js.map

Sorry, the diff of this file is not supported yet

dist/contours.ts.cjs.production.min.js.map

Sorry, the diff of this file is not supported yet

dist/contours.ts.esm.js.map

Sorry, the diff of this file is not supported yet