pixel flipper, data sifter. trying to see what I can while I'm here
Public
Edited
Mar 21, 2023
Importers
dictionary = new AR.Dictionary("APRILTAG_36h11")
viewof index = Inputs.range([0, dictionary.codeList.length - 1], {label: "ID", step: 1, value: 0})
pattern = dictionary.generatePattern(index)
{
let size = 200;
let ctx = DOM.context2d(size, size)
let rw = size / dictionary.markSize;
ctx.fillStyle = "black"
ctx.fillRect(0, 0, size, size)
pattern.forEach(d => {
ctx.fillStyle = d.code ? "white" : "black"
ctx.fillRect((d.x + 1) * rw, (d.y + 1) * rw, rw, rw)
})
return ctx.canvas
}
<div style="width:200px">${dictionary.generateSVG(10)}</div>
Plot.cell(pattern, { x: "x", y: "y", fill: "code", stroke:"code"}).plot({
marks: [
Plot.rect([{x1:-2, x2: 7, y1:-2, y2: 7}], {x1:"x1",x2:"x2", y1:"y1", y2:"y2", fill:"black"})
],
width: 200,
height: 200,
padding: 0,
y: { axis: false },
x: { axis: false },
color: {
domain: [0, 1],
range: ["black", "white"]
}
})
AR = {
let AR = {};
AR.DICTIONARIES = {
ARUCO: ARUCO,
ARUCO_MIP_36h12: ARUCO_MIP_36h12,
APRILTAG_36h11: APRILTAG_36h11,
};
AR.Dictionary = function (dicName) {
this.codes = {};
this.codeList = [];
this.tau = 0;
this._initialize(dicName);
};
AR.Dictionary.prototype._initialize = function (dicName) {
this.codes = {};
this.codeList = [];
this.tau = 0;
this.nBits = 0;
this.markSize = 0;
this.dicName = dicName;
var dictionary = AR.DICTIONARIES[dicName];
if (!dictionary)
throw 'The dictionary "' + dicName + '" is not recognized.';
this.nBits = dictionary.nBits;
this.markSize = Math.sqrt(dictionary.nBits) + 2;
for (var i = 0; i < dictionary.codeList.length; i++) {
var code = null;
if (typeof dictionary.codeList[i] === 'number')
code = this._hex2bin(dictionary.codeList[i], dictionary.nBits);
if (typeof dictionary.codeList[i] === 'string')
code = this._hex2bin(parseInt(dictionary.codeList[i], 16), dictionary.nBits);
if (Array.isArray(dictionary.codeList[i]))
code = this._bytes2bin(dictionary.codeList[i], dictionary.nBits);
if (code === null)
throw 'Invalid code ' + i + ' in dictionary ' + dicName + ': ' + JSON.stringify(dictionary.codeList[i]);
if (code.length != dictionary.nBits)
throw 'The code ' + i + ' in dictionary ' + dicName + ' is not ' + dictionary.nBits + ' bits long but ' + code.length + ': ' + code;
this.codeList.push(code);
this.codes[code] = {
id: i
};
}
this.tau = dictionary.tau || this._calculateTau();
};
AR.Dictionary.prototype.find = function (bits) {
var val = '',
i, j;
for (i = 0; i < bits.length; i++) {
var bitRow = bits[i];
for (j = 0; j < bitRow.length; j++) {
val += bitRow[j];
}
}
var minFound = this.codes[val];
if (minFound)
return {
id: minFound.id,
distance: 0
};
for (i = 0; i < this.codeList.length; i++) {
var code = this.codeList[i];
var distance = this._hammingDistance(val, code);
if (this._hammingDistance(val, code) < this.tau) {
if (!minFound || minFound.distance > distance) {
minFound = {
id: this.codes[code].id,
distance: distance
};
}
}
}
return minFound;
};
AR.Dictionary.prototype._hex2bin = function (hex, nBits) {
return hex.toString(2).padStart(nBits, '0');
};
AR.Dictionary.prototype._bytes2bin = function (byteList, nBits) {
var bits = '', byte;
for (byte of byteList) {
bits += byte.toString(2).padStart(bits.length + 8 > nBits?nBits - bits.length:8, '0');
}
return bits;
};
AR.Dictionary.prototype._hammingDistance = function (str1, str2) {
if (str1.length != str2.length)
throw 'Hamming distance calculation require inputs of the same length';
var distance = 0,
i;
for (i = 0; i < str1.length; i++)
if (str1[i] !== str2[i])
distance += 1;
return distance;
};
AR.Dictionary.prototype._calculateTau = function () {
var tau = Number.MAX_VALUE;
for(var i=0;i<this.codeList.length;i++)
for(var j=i+1;j<this.codeList.length;j++) {
var distance = this._hammingDistance(this.codeList[i], this.codeList[j]);
tau = distance < tau ? distance : tau;
}
return tau;
};
AR.Dictionary.prototype.generatePattern = function (id) {
var code = this.codeList[id];
if(!code) return []
var size = this.markSize - 2;
let pattern = []
for(var y=0;y<size;y++) {
for(var x=0;x<size;x++) {
pattern.push({x, y, code: +code[y*size+x]})
}
}
return pattern;
};
AR.Dictionary.prototype.generateSVG = function (id) {
var code = this.codeList[id];
if (code == null)
throw 'The id "' + id + '" is not valid for the dictionary "' + this.dicName + '". ID must be between 0 and ' + (this.codeList.length-1) + ' included.';
var size = this.markSize - 2;
var svg = '<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 '+ (size+4) + ' ' + (size+4) + '">';
svg += '<rect x="0" y="0" width="' + (size+4) + '" height="' + (size+4) + '" fill="white"/>';
svg += '<rect x="1" y="1" width="' + (size+2) + '" height="' + (size+2) + '" fill="black"/>';
for(var y=0;y<size;y++) {
for(var x=0;x<size;x++) {
if (code[y*size+x]=='1')
svg += '<rect x="' + (x+2) + '" y="' + (y+2) + '" width="1" height="1" fill="white"/>';
}
}
svg += '</svg>';
return svg;
};
AR.Marker = function (id, corners, hammingDistance) {
this.id = id;
this.corners = corners;
this.hammingDistance = hammingDistance;
};
AR.Detector = function (config) {
config = config || {};
this.grey = new CV.Image();
this.thres = new CV.Image();
this.homography = new CV.Image();
this.binary = [];
this.contours = [];
this.polys = [];
this.candidates = [];
config.dictionaryName = config.dictionaryName || 'ARUCO_MIP_36h12';
this.dictionary = new AR.Dictionary(config.dictionaryName);
this.dictionary.tau = config.maxHammingDistance != null ? config.maxHammingDistance : this.dictionary.tau;
};
AR.Detector.prototype.detectImage = function (width, height, data) {
return this.detect({
width: width,
height: height,
data: data
});
};
AR.Detector.prototype.detectStreamInit = function (width, height, callback) {
this.streamConfig = {};
this.streamConfig.width = width;
this.streamConfig.height = height;
this.streamConfig.imageSize = width * height * 4; //provided image must be a sequence of rgba bytes (4 bytes represent a pixel)
this.streamConfig.index = 0;
this.streamConfig.imageData = new Uint8ClampedArray(this.streamConfig.imageSize);
this.streamConfig.callback = callback || function (image, markerList) {};
};
//accept data chunks of different sizes
AR.Detector.prototype.detectStream = function (data) {
for (var i = 0; i < data.length; i++) {
this.streamConfig.imageData[this.streamConfig.index] = data[i];
this.streamConfig.index = (this.streamConfig.index + 1) % this.streamConfig.imageSize;
if (this.streamConfig.index == 0) {
var image = {
width: this.streamConfig.width,
height: this.streamConfig.height,
data: this.streamConfig.imageData
};
var markerList = this.detect(image);
this.streamConfig.callback(image, markerList);
}
}
};
AR.Detector.prototype.detectMJPEGStreamInit = function (width, height, callback, decoderFn) {
this.mjpeg = {
decoderFn: decoderFn,
chunks: [],
SOI: [0xff, 0xd8],
EOI: [0xff, 0xd9]
};
this.detectStreamInit(width, height, callback);
};
AR.Detector.prototype.detectMJPEGStream = function (chunk) {
var eoiPos = chunk.findIndex(function (element, index, array) {
return this.mjpeg.EOI[0] == element && array.length > index + 1 && this.mjpeg.EOI[1] == array[index + 1];
});
var soiPos = chunk.findIndex(function (element, index, array) {
return this.mjpeg.SOI[0] == element && array.length > index + 1 && this.mjpeg.SOI[1] == array[index + 1];
});
if (eoiPos === -1) {
this.mjpeg.chunks.push(chunk);
} else {
var part1 = chunk.slice(0, eoiPos + 2);
if (part1.length) {
this.mjpeg.chunks.push(part1);
}
if (this.mjpeg.chunks.length) {
var jpegImage = this.mjpeg.chunks.flat();
var rgba = this.mjpeg.decoderFn(jpegImage);
this.detectStream(rgba);
}
this.mjpeg.chunks = [];
}
if (soiPos > -1) {
this.mjpeg.chunks = [];
this.mjpeg.chunks.push(chunk.slice(soiPos));
}
};
AR.Detector.prototype.detect = function (image) {
CV.grayscale(image, this.grey);
CV.adaptiveThreshold(this.grey, this.thres, 2, 7);
this.contours = CV.findContours(this.thres, this.binary);
//Scale Fix: https://stackoverflow.com/questions/35936397/marker-detection-on-paper-sheet-using-javascript
//this.candidates = this.findCandidates(this.contours, image.width * 0.20, 0.05, 10);
this.candidates = this.findCandidates(this.contours, image.width * 0.01, 0.05, 10);
this.candidates = this.clockwiseCorners(this.candidates);
this.candidates = this.notTooNear(this.candidates, 10);
return this.findMarkers(this.grey, this.candidates, 49);
};
AR.Detector.prototype.findCandidates = function (contours, minSize, epsilon, minLength) {
var candidates = [],
len = contours.length,
contour, poly, i;
this.polys = [];
for (i = 0; i < len; ++i) {
contour = contours[i];
if (contour.length >= minSize) {
poly = CV.approxPolyDP(contour, contour.length * epsilon);
this.polys.push(poly);
if ((4 === poly.length) && (CV.isContourConvex(poly))) {
if (CV.minEdgeLength(poly) >= minLength) {
candidates.push(poly);
}
}
}
}
return candidates;
};
AR.Detector.prototype.clockwiseCorners = function (candidates) {
var len = candidates.length,
dx1, dx2, dy1, dy2, swap, i;
for (i = 0; i < len; ++i) {
dx1 = candidates[i][1].x - candidates[i][0].x;
dy1 = candidates[i][1].y - candidates[i][0].y;
dx2 = candidates[i][2].x - candidates[i][0].x;
dy2 = candidates[i][2].y - candidates[i][0].y;
if ((dx1 * dy2 - dy1 * dx2) < 0) {
swap = candidates[i][1];
candidates[i][1] = candidates[i][3];
candidates[i][3] = swap;
}
}
return candidates;
};
AR.Detector.prototype.notTooNear = function (candidates, minDist) {
var notTooNear = [],
len = candidates.length,
dist, dx, dy, i, j, k;
for (i = 0; i < len; ++i) {
for (j = i + 1; j < len; ++j) {
dist = 0;
for (k = 0; k < 4; ++k) {
dx = candidates[i][k].x - candidates[j][k].x;
dy = candidates[i][k].y - candidates[j][k].y;
dist += dx * dx + dy * dy;
}
if ((dist / 4) < (minDist * minDist)) {
if (CV.perimeter(candidates[i]) < CV.perimeter(candidates[j])) {
candidates[i].tooNear = true;
} else {
candidates[j].tooNear = true;
}
}
}
}
for (i = 0; i < len; ++i) {
if (!candidates[i].tooNear) {
notTooNear.push(candidates[i]);
}
}
return notTooNear;
};
AR.Detector.prototype.findMarkers = function (imageSrc, candidates, warpSize) {
var markers = [],
len = candidates.length,
candidate, marker, i;
for (i = 0; i < len; ++i) {
candidate = candidates[i];
CV.warp(imageSrc, this.homography, candidate, warpSize);
CV.threshold(this.homography, this.homography, CV.otsu(this.homography));
marker = this.getMarker(this.homography, candidate);
if (marker) {
markers.push(marker);
}
}
return markers;
};
AR.Detector.prototype.getMarker = function (imageSrc, candidate) {
var markSize = this.dictionary.markSize;
var width = (imageSrc.width / markSize) >>> 0,
minZero = (width * width) >> 1,
bits = [],
rotations = [],
square, inc, i, j;
for (i = 0; i < markSize; ++i) {
inc = (0 === i || (markSize - 1) === i) ? 1 : (markSize - 1);
for (j = 0; j < markSize; j += inc) {
square = {
x: j * width,
y: i * width,
width: width,
height: width
};
if (CV.countNonZero(imageSrc, square) > minZero) {
return null;
}
}
}
for (i = 0; i < markSize - 2; ++i) {
bits[i] = [];
for (j = 0; j < markSize - 2; ++j) {
square = {
x: (j + 1) * width,
y: (i + 1) * width,
width: width,
height: width
};
bits[i][j] = CV.countNonZero(imageSrc, square) > minZero ? 1 : 0;
}
}
rotations[0] = bits;
var foundMin = null;
var rot = 0;
for (i = 0; i < 4; i++) {
var found = this.dictionary.find(rotations[i]);
if (found && (foundMin === null || found.distance < foundMin.distance)) {
foundMin = found;
rot = i;
if (foundMin.distance === 0)
break;
}
rotations[i + 1] = this.rotate(rotations[i]);
}
if (foundMin)
return new AR.Marker(foundMin.id, this.rotate2(candidate, 4 - rot), foundMin.distance);
return null;
};
AR.Detector.prototype.rotate = function (src) {
var dst = [],
len = src.length,
i, j;
for (i = 0; i < len; ++i) {
dst[i] = [];
for (j = 0; j < src[i].length; ++j) {
dst[i][j] = src[src[i].length - j - 1][i];
}
}
return dst;
};
AR.Detector.prototype.rotate2 = function (src, rotation) {
var dst = [],
len = src.length,
i;
for (i = 0; i < len; ++i) {
dst[i] = src[(rotation + i) % len];
}
return dst;
};
return AR
}
CV = {
let CV = {};
CV.Image = function (width, height, data) {
this.width = width || 0;
this.height = height || 0;
this.data = data || [];
};
CV.grayscale = function (imageSrc, imageDst) {
var src = imageSrc.data,
dst = imageDst.data,
len = src.length,
i = 0,
j = 0;
for (; i < len; i += 4) {
dst[j++] =
(src[i] * 0.299 + src[i + 1] * 0.587 + src[i + 2] * 0.114 + 0.5) & 0xff;
}
imageDst.width = imageSrc.width;
imageDst.height = imageSrc.height;
return imageDst;
};
CV.threshold = function (imageSrc, imageDst, threshold) {
var src = imageSrc.data,
dst = imageDst.data,
len = src.length,
tab = [],
i;
for (i = 0; i < 256; ++i) {
tab[i] = i <= threshold ? 0 : 255;
}
for (i = 0; i < len; ++i) {
dst[i] = tab[src[i]];
}
imageDst.width = imageSrc.width;
imageDst.height = imageSrc.height;
return imageDst;
};
CV.adaptiveThreshold = function (imageSrc, imageDst, kernelSize, threshold) {
var src = imageSrc.data,
dst = imageDst.data,
len = src.length,
tab = [],
i;
CV.stackBoxBlur(imageSrc, imageDst, kernelSize);
for (i = 0; i < 768; ++i) {
tab[i] = i - 255 <= -threshold ? 255 : 0;
}
for (i = 0; i < len; ++i) {
dst[i] = tab[src[i] - dst[i] + 255];
}
imageDst.width = imageSrc.width;
imageDst.height = imageSrc.height;
return imageDst;
};
CV.otsu = function (imageSrc) {
var src = imageSrc.data,
len = src.length,
hist = [],
threshold = 0,
sum = 0,
sumB = 0,
wB = 0,
wF = 0,
max = 0,
mu,
between,
i;
for (i = 0; i < 256; ++i) {
hist[i] = 0;
}
for (i = 0; i < len; ++i) {
hist[src[i]]++;
}
for (i = 0; i < 256; ++i) {
sum += hist[i] * i;
}
for (i = 0; i < 256; ++i) {
wB += hist[i];
if (0 !== wB) {
wF = len - wB;
if (0 === wF) {
break;
}
sumB += hist[i] * i;
mu = sumB / wB - (sum - sumB) / wF;
between = wB * wF * mu * mu;
if (between > max) {
max = between;
threshold = i;
}
}
}
return threshold;
};
CV.stackBoxBlurMult = [
1, 171, 205, 293, 57, 373, 79, 137, 241, 27, 391, 357, 41, 19, 283, 265
];
CV.stackBoxBlurShift = [
0, 9, 10, 11, 9, 12, 10, 11, 12, 9, 13, 13, 10, 9, 13, 13
];
CV.BlurStack = function () {
this.color = 0;
this.next = null;
};
CV.stackBoxBlur = function (imageSrc, imageDst, kernelSize) {
var src = imageSrc.data,
dst = imageDst.data,
height = imageSrc.height,
width = imageSrc.width,
heightMinus1 = height - 1,
widthMinus1 = width - 1,
size = kernelSize + kernelSize + 1,
radius = kernelSize + 1,
mult = CV.stackBoxBlurMult[kernelSize],
shift = CV.stackBoxBlurShift[kernelSize],
stack,
stackStart,
color,
sum,
pos,
start,
p,
x,
y,
i;
stack = stackStart = new CV.BlurStack();
for (i = 1; i < size; ++i) {
stack = stack.next = new CV.BlurStack();
}
stack.next = stackStart;
pos = 0;
for (y = 0; y < height; ++y) {
start = pos;
color = src[pos];
sum = radius * color;
stack = stackStart;
for (i = 0; i < radius; ++i) {
stack.color = color;
stack = stack.next;
}
for (i = 1; i < radius; ++i) {
stack.color = src[pos + i];
sum += stack.color;
stack = stack.next;
}
stack = stackStart;
for (x = 0; x < width; ++x) {
dst[pos++] = (sum * mult) >>> shift;
p = x + radius;
p = start + (p < widthMinus1 ? p : widthMinus1);
sum -= stack.color - src[p];
stack.color = src[p];
stack = stack.next;
}
}
for (x = 0; x < width; ++x) {
pos = x;
start = pos + width;
color = dst[pos];
sum = radius * color;
stack = stackStart;
for (i = 0; i < radius; ++i) {
stack.color = color;
stack = stack.next;
}
for (i = 1; i < radius; ++i) {
stack.color = dst[start];
sum += stack.color;
stack = stack.next;
start += width;
}
stack = stackStart;
for (y = 0; y < height; ++y) {
dst[pos] = (sum * mult) >>> shift;
p = y + radius;
p = x + (p < heightMinus1 ? p : heightMinus1) * width;
sum -= stack.color - dst[p];
stack.color = dst[p];
stack = stack.next;
pos += width;
}
}
return imageDst;
};
CV.gaussianBlur = function (imageSrc, imageDst, imageMean, kernelSize) {
var kernel = CV.gaussianKernel(kernelSize);
imageDst.width = imageSrc.width;
imageDst.height = imageSrc.height;
imageMean.width = imageSrc.width;
imageMean.height = imageSrc.height;
CV.gaussianBlurFilter(imageSrc, imageMean, kernel, true);
CV.gaussianBlurFilter(imageMean, imageDst, kernel, false);
return imageDst;
};
CV.gaussianBlurFilter = function (imageSrc, imageDst, kernel, horizontal) {
var src = imageSrc.data,
dst = imageDst.data,
height = imageSrc.height,
width = imageSrc.width,
pos = 0,
limit = kernel.length >> 1,
cur,
value,
i,
j,
k;
for (i = 0; i < height; ++i) {
for (j = 0; j < width; ++j) {
value = 0.0;
for (k = -limit; k <= limit; ++k) {
if (horizontal) {
cur = pos + k;
if (j + k < 0) {
cur = pos;
} else if (j + k >= width) {
cur = pos;
}
} else {
cur = pos + k * width;
if (i + k < 0) {
cur = pos;
} else if (i + k >= height) {
cur = pos;
}
}
value += kernel[limit + k] * src[cur];
}
dst[pos++] = horizontal ? value : (value + 0.5) & 0xff;
}
}
return imageDst;
};
CV.gaussianKernel = function (kernelSize) {
var tab = [
[1],
[0.25, 0.5, 0.25],
[0.0625, 0.25, 0.375, 0.25, 0.0625],
[0.03125, 0.109375, 0.21875, 0.28125, 0.21875, 0.109375, 0.03125]
],
kernel = [],
center,
sigma,
scale2X,
sum,
x,
i;
if (kernelSize <= 7 && kernelSize % 2 === 1) {
kernel = tab[kernelSize >> 1];
} else {
center = (kernelSize - 1.0) * 0.5;
sigma = 0.8 + 0.3 * (center - 1.0);
scale2X = -0.5 / (sigma * sigma);
sum = 0.0;
for (i = 0; i < kernelSize; ++i) {
x = i - center;
sum += kernel[i] = Math.exp(scale2X * x * x);
}
sum = 1 / sum;
for (i = 0; i < kernelSize; ++i) {
kernel[i] *= sum;
}
}
return kernel;
};
CV.findContours = function (imageSrc, binary) {
var width = imageSrc.width,
height = imageSrc.height,
contours = [],
src,
deltas,
pos,
pix,
nbd,
outer,
hole,
i,
j;
src = CV.binaryBorder(imageSrc, binary);
deltas = CV.neighborhoodDeltas(width + 2);
pos = width + 3;
nbd = 1;
for (i = 0; i < height; ++i, pos += 2) {
for (j = 0; j < width; ++j, ++pos) {
pix = src[pos];
if (0 !== pix) {
outer = hole = false;
if (1 === pix && 0 === src[pos - 1]) {
outer = true;
} else if (pix >= 1 && 0 === src[pos + 1]) {
hole = true;
}
if (outer || hole) {
++nbd;
contours.push(
CV.borderFollowing(src, pos, nbd, { x: j, y: i }, hole, deltas)
);
}
}
}
}
return contours;
};
CV.borderFollowing = function (src, pos, nbd, point, hole, deltas) {
var contour = [],
pos1,
pos3,
pos4,
s,
s_end,
s_prev;
contour.hole = hole;
s = s_end = hole ? 0 : 4;
do {
s = (s - 1) & 7;
pos1 = pos + deltas[s];
if (src[pos1] !== 0) {
break;
}
} while (s !== s_end);
if (s === s_end) {
src[pos] = -nbd;
contour.push({ x: point.x, y: point.y });
} else {
pos3 = pos;
s_prev = s ^ 4;
while (true) {
s_end = s;
do {
pos4 = pos3 + deltas[++s];
} while (src[pos4] === 0);
s &= 7;
if ((s - 1) >>> 0 < s_end >>> 0) {
src[pos3] = -nbd;
} else if (src[pos3] === 1) {
src[pos3] = nbd;
}
contour.push({ x: point.x, y: point.y });
s_prev = s;
point.x += CV.neighborhood[s][0];
point.y += CV.neighborhood[s][1];
if (pos4 === pos && pos3 === pos1) {
break;
}
pos3 = pos4;
s = (s + 4) & 7;
}
}
return contour;
};
CV.neighborhood = [
[1, 0],
[1, -1],
[0, -1],
[-1, -1],
[-1, 0],
[-1, 1],
[0, 1],
[1, 1]
];
CV.neighborhoodDeltas = function (width) {
var deltas = [],
len = CV.neighborhood.length,
i = 0;
for (; i < len; ++i) {
deltas[i] = CV.neighborhood[i][0] + CV.neighborhood[i][1] * width;
}
return deltas.concat(deltas);
};
CV.approxPolyDP = function (contour, epsilon) {
var slice = { start_index: 0, end_index: 0 },
right_slice = { start_index: 0, end_index: 0 },
poly = [],
stack = [],
len = contour.length,
pt,
start_pt,
end_pt,
dist,
max_dist,
le_eps,
dx,
dy,
i,
j,
k;
epsilon *= epsilon;
k = 0;
for (i = 0; i < 3; ++i) {
max_dist = 0;
k = (k + right_slice.start_index) % len;
start_pt = contour[k];
if (++k === len) {
k = 0;
}
for (j = 1; j < len; ++j) {
pt = contour[k];
if (++k === len) {
k = 0;
}
dx = pt.x - start_pt.x;
dy = pt.y - start_pt.y;
dist = dx * dx + dy * dy;
if (dist > max_dist) {
max_dist = dist;
right_slice.start_index = j;
}
}
}
if (max_dist <= epsilon) {
poly.push({ x: start_pt.x, y: start_pt.y });
} else {
slice.start_index = k;
slice.end_index = right_slice.start_index += slice.start_index;
right_slice.start_index -= right_slice.start_index >= len ? len : 0;
right_slice.end_index = slice.start_index;
if (right_slice.end_index < right_slice.start_index) {
right_slice.end_index += len;
}
stack.push({
start_index: right_slice.start_index,
end_index: right_slice.end_index
});
stack.push({
start_index: slice.start_index,
end_index: slice.end_index
});
}
while (stack.length !== 0) {
slice = stack.pop();
end_pt = contour[slice.end_index % len];
start_pt = contour[(k = slice.start_index % len)];
if (++k === len) {
k = 0;
}
if (slice.end_index <= slice.start_index + 1) {
le_eps = true;
} else {
max_dist = 0;
dx = end_pt.x - start_pt.x;
dy = end_pt.y - start_pt.y;
for (i = slice.start_index + 1; i < slice.end_index; ++i) {
pt = contour[k];
if (++k === len) {
k = 0;
}
dist = Math.abs((pt.y - start_pt.y) * dx - (pt.x - start_pt.x) * dy);
if (dist > max_dist) {
max_dist = dist;
right_slice.start_index = i;
}
}
le_eps = max_dist * max_dist <= epsilon * (dx * dx + dy * dy);
}
if (le_eps) {
poly.push({ x: start_pt.x, y: start_pt.y });
} else {
right_slice.end_index = slice.end_index;
slice.end_index = right_slice.start_index;
stack.push({
start_index: right_slice.start_index,
end_index: right_slice.end_index
});
stack.push({
start_index: slice.start_index,
end_index: slice.end_index
});
}
}
return poly;
};
CV.warp = function (imageSrc, imageDst, contour, warpSize) {
var src = imageSrc.data,
dst = imageDst.data,
width = imageSrc.width,
height = imageSrc.height,
pos = 0,
sx1,
sx2,
dx1,
dx2,
sy1,
sy2,
dy1,
dy2,
p1,
p2,
p3,
p4,
m,
r,
s,
t,
u,
v,
w,
x,
y,
i,
j;
m = CV.getPerspectiveTransform(contour, warpSize - 1);
r = m[8];
s = m[2];
t = m[5];
for (i = 0; i < warpSize; ++i) {
r += m[7];
s += m[1];
t += m[4];
u = r;
v = s;
w = t;
for (j = 0; j < warpSize; ++j) {
u += m[6];
v += m[0];
w += m[3];
x = v / u;
y = w / u;
sx1 = x >>> 0;
sx2 = sx1 === width - 1 ? sx1 : sx1 + 1;
dx1 = x - sx1;
dx2 = 1.0 - dx1;
sy1 = y >>> 0;
sy2 = sy1 === height - 1 ? sy1 : sy1 + 1;
dy1 = y - sy1;
dy2 = 1.0 - dy1;
p1 = p2 = sy1 * width;
p3 = p4 = sy2 * width;
dst[pos++] =
(dy2 * (dx2 * src[p1 + sx1] + dx1 * src[p2 + sx2]) +
dy1 * (dx2 * src[p3 + sx1] + dx1 * src[p4 + sx2])) &
0xff;
}
}
imageDst.width = warpSize;
imageDst.height = warpSize;
return imageDst;
};
CV.getPerspectiveTransform = function (src, size) {
var rq = CV.square2quad(src);
rq[0] /= size;
rq[1] /= size;
rq[3] /= size;
rq[4] /= size;
rq[6] /= size;
rq[7] /= size;
return rq;
};
CV.square2quad = function (src) {
var sq = [],
px,
py,
dx1,
dx2,
dy1,
dy2,
den;
px = src[0].x - src[1].x + src[2].x - src[3].x;
py = src[0].y - src[1].y + src[2].y - src[3].y;
if (0 === px && 0 === py) {
sq[0] = src[1].x - src[0].x;
sq[1] = src[2].x - src[1].x;
sq[2] = src[0].x;
sq[3] = src[1].y - src[0].y;
sq[4] = src[2].y - src[1].y;
sq[5] = src[0].y;
sq[6] = 0;
sq[7] = 0;
sq[8] = 1;
} else {
dx1 = src[1].x - src[2].x;
dx2 = src[3].x - src[2].x;
dy1 = src[1].y - src[2].y;
dy2 = src[3].y - src[2].y;
den = dx1 * dy2 - dx2 * dy1;
sq[6] = (px * dy2 - dx2 * py) / den;
sq[7] = (dx1 * py - px * dy1) / den;
sq[8] = 1;
sq[0] = src[1].x - src[0].x + sq[6] * src[1].x;
sq[1] = src[3].x - src[0].x + sq[7] * src[3].x;
sq[2] = src[0].x;
sq[3] = src[1].y - src[0].y + sq[6] * src[1].y;
sq[4] = src[3].y - src[0].y + sq[7] * src[3].y;
sq[5] = src[0].y;
}
return sq;
};
CV.isContourConvex = function (contour) {
var orientation = 0,
convex = true,
len = contour.length,
i = 0,
j = 0,
cur_pt,
prev_pt,
dxdy0,
dydx0,
dx0,
dy0,
dx,
dy;
prev_pt = contour[len - 1];
cur_pt = contour[0];
dx0 = cur_pt.x - prev_pt.x;
dy0 = cur_pt.y - prev_pt.y;
for (; i < len; ++i) {
if (++j === len) {
j = 0;
}
prev_pt = cur_pt;
cur_pt = contour[j];
dx = cur_pt.x - prev_pt.x;
dy = cur_pt.y - prev_pt.y;
dxdy0 = dx * dy0;
dydx0 = dy * dx0;
orientation |= dydx0 > dxdy0 ? 1 : dydx0 < dxdy0 ? 2 : 3;
if (3 === orientation) {
convex = false;
break;
}
dx0 = dx;
dy0 = dy;
}
return convex;
};
CV.perimeter = function (poly) {
var len = poly.length,
i = 0,
j = len - 1,
p = 0.0,
dx,
dy;
for (; i < len; j = i++) {
dx = poly[i].x - poly[j].x;
dy = poly[i].y - poly[j].y;
p += Math.sqrt(dx * dx + dy * dy);
}
return p;
};
CV.minEdgeLength = function (poly) {
var len = poly.length,
i = 0,
j = len - 1,
min = Infinity,
d,
dx,
dy;
for (; i < len; j = i++) {
dx = poly[i].x - poly[j].x;
dy = poly[i].y - poly[j].y;
d = dx * dx + dy * dy;
if (d < min) {
min = d;
}
}
return Math.sqrt(min);
};
CV.countNonZero = function (imageSrc, square) {
var src = imageSrc.data,
height = square.height,
width = square.width,
pos = square.x + square.y * imageSrc.width,
span = imageSrc.width - width,
nz = 0,
i,
j;
for (i = 0; i < height; ++i) {
for (j = 0; j < width; ++j) {
if (0 !== src[pos++]) {
++nz;
}
}
pos += span;
}
return nz;
};
CV.binaryBorder = function (imageSrc, dst) {
var src = imageSrc.data,
height = imageSrc.height,
width = imageSrc.width,
posSrc = 0,
posDst = 0,
i,
j;
for (j = -2; j < width; ++j) {
dst[posDst++] = 0;
}
for (i = 0; i < height; ++i) {
dst[posDst++] = 0;
for (j = 0; j < width; ++j) {
dst[posDst++] = 0 === src[posSrc++] ? 0 : 1;
}
dst[posDst++] = 0;
}
for (j = -2; j < width; ++j) {
dst[posDst++] = 0;
}
return dst;
};
return CV
}
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.