magic-wand.js

// Magic Wand (Fuzzy Selection Tool) for Javascript
//
// The MIT License (MIT)
//
// Copyright (c) 2014, Ryasnoy Paul (ryasnoypaul@gmail.com)
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
    
MagicWand = (function () {
    var lib = {};

    /** Create a binary mask on the image by color threshold
      * Algorithm: Scanline flood fill (http://en.wikipedia.org/wiki/Flood_fill)
      * @param {Object} image: {Uint8Array} data, {int} width, {int} height, {int} bytes
      * @param {int} x of start pixel
      * @param {int} y of start pixel
      * @param {int} color threshold
      * @param {Uint8Array} mask of visited points (optional) 
      * @return {Object} mask: {Uint8Array} data, {int} width, {int} height, {Object} bounds
      */
    lib.floodFill = function(image, px, py, colorThreshold, mask) {

        var c, x, newY, el, xr, xl, dy, dyl, dyr, checkY,
            data = image.data,
            w = image.width,
            h = image.height,
            bytes = image.bytes, // number of bytes in the color
            maxX = -1, minX = w + 1, maxY = -1, minY = h + 1,
            i = py * w + px, // start point index in the mask data
            result = new Uint8Array(w * h), // result mask
            visited = new Uint8Array(mask ? mask : w * h); // mask of visited points

        if (visited[i] === 1) return null;

        i = i * bytes; // start point index in the image data
        var sampleColor = [data[i], data[i + 1], data[i + 2], data[i + 3]]; // start point color (sample)

        var stack = [{ y: py, left: px - 1, right: px + 1, dir: 1 }]; // first scanning line
        do {
            el = stack.shift(); // get line for scanning

            checkY = false;
            for (x = el.left + 1; x < el.right; x++) {
                dy = el.y * w;
                i = (dy + x) * bytes; // point index in the image data

                if (visited[dy + x] === 1) continue; // check whether the point has been visited
                // compare the color of the sample
                c = data[i] - sampleColor[0]; // check by red
                if (c > colorThreshold || c < -colorThreshold) continue;
                c = data[i + 1] - sampleColor[1]; // check by green
                if (c > colorThreshold || c < -colorThreshold) continue;
                c = data[i + 2] - sampleColor[2]; // check by blue
                if (c > colorThreshold || c < -colorThreshold) continue;

                checkY = true; // if the color of the new point(x,y) is similar to the sample color need to check minmax for Y 

                result[dy + x] = 1; // mark a new point in mask
                visited[dy + x] = 1; // mark a new point as visited

                xl = x - 1;
                // walk to left side starting with the left neighbor
                while (xl > -1) {
                    dyl = dy + xl;
                    i = dyl * bytes; // point index in the image data
                    if (visited[dyl] === 1) break; // check whether the point has been visited
                    // compare the color of the sample
                    c = data[i] - sampleColor[0]; // check by red
                    if (c > colorThreshold || c < -colorThreshold) break;
                    c = data[i + 1] - sampleColor[1]; // check by green
                    if (c > colorThreshold || c < -colorThreshold) break;
                    c = data[i + 2] - sampleColor[2]; // check by blue
                    if (c > colorThreshold || c < -colorThreshold) break;

                    result[dyl] = 1;
                    visited[dyl] = 1;

                    xl--;
                }
                xr = x + 1;
                // walk to right side starting with the right neighbor
                while (xr < w) {
                    dyr = dy + xr;
                    i = dyr * bytes; // index point in the image data
                    if (visited[dyr] === 1) break; // check whether the point has been visited
                    // compare the color of the sample
                    c = data[i] - sampleColor[0]; // check by red
                    if (c > colorThreshold || c < -colorThreshold) break;
                    c = data[i + 1] - sampleColor[1]; // check by green
                    if (c > colorThreshold || c < -colorThreshold) break;
                    c = data[i + 2] - sampleColor[2]; // check by blue
                    if (c > colorThreshold || c < -colorThreshold) break;

                    result[dyr] = 1;
                    visited[dyr] = 1;

                    xr++;
                }

                // check minmax for X
                if (xl < minX) minX = xl + 1;
                if (xr > maxX) maxX = xr - 1;

                newY = el.y - el.dir;
                if (newY >= 0 && newY < h) { // add two scanning lines in the opposite direction (y - dir) if necessary
                    if (xl < el.left) stack.push({ y: newY, left: xl, right: el.left, dir: -el.dir }); // from "new left" to "current left"
                    if (el.right < xr) stack.push({ y: newY, left: el.right, right: xr, dir: -el.dir }); // from "current right" to "new right"
                }
                newY = el.y + el.dir;
                if (newY >= 0 && newY < h) { // add the scanning line in the direction (y + dir) if necessary
                    if (xl < xr) stack.push({ y: newY, left: xl, right: xr, dir: el.dir }); // from "new left" to "new right"
                }
            }
            // check minmax for Y if necessary
            if (checkY) {
                if (el.y < minY) minY = el.y;
                if (el.y > maxY) maxY = el.y;
            }
        } while (stack.length > 0);

        return {
            data: result,
            width: image.width,
            height: image.height,
            bounds: {
                minX: minX,
                minY: minY,
                maxX: maxX,
                maxY: maxY
            }
        };
    };

    /** Apply the gauss-blur filter to binary mask
      * Algorithms: http://blog.ivank.net/fastest-gaussian-blur.html
      * http://www.librow.com/articles/article-9
      * http://elynxsdk.free.fr/ext-docs/Blur/Fast_box_blur.pdf
      * @param {Object} mask: {Uint8Array} data, {int} width, {int} height, {Object} bounds
      * @param {int} blur radius
      * @return {Object} mask: {Uint8Array} data, {int} width, {int} height, {Object} bounds
      */
    lib.gaussBlur = function(mask, radius) {

        var i, k, k1, x, y, val, start, end,
            n = radius * 2 + 1, // size of the pattern for radius-neighbors (from -r to +r with the center point)
            s2 = radius * radius,
            wg = new Float32Array(n), // weights
            total = 0, // sum of weights(used for normalization)
            w = mask.width,
            h = mask.height,
            data = mask.data,
            minX = mask.bounds.minX,
            maxX = mask.bounds.maxX,
            minY = mask.bounds.minY,
            maxY = mask.bounds.maxY;

        // calc gauss weights
        for (i = 0; i < radius; i++) {
            var dsq = (radius - i) * (radius - i);
            var ww = Math.exp(-dsq / (2.0 * s2)) / (2 * Math.PI * s2);
            wg[radius + i] = wg[radius - i] = ww;
            total += 2 * ww;
        }
        // normalization weights
        for (i = 0; i < n; i++) {
            wg[i] /= total;
        }

        var result = new Uint8Array(w * h), // result mask
            endX = radius + w,
            endY = radius + h;

        //walk through all source points for blur
        for (y = minY; y < maxY + 1; y++)
            for (x = minX; x < maxX + 1; x++) {
                val = 0;
                k = y * w + x; // index of the point
                start = radius - x > 0 ? radius - x : 0;
                end = endX - x < n ? endX - x : n; // Math.min((((w - 1) - x) + radius) + 1, n);
                k1 = k - radius;
                // walk through x-neighbors
                for (i = start; i < end; i++) {
                    val += data[k1 + i] * wg[i];
                }
                start = radius - y > 0 ? radius - y : 0;
                end = endY - y < n ? endY - y : n; // Math.min((((h - 1) - y) + radius) + 1, n);
                k1 = k - radius * w;
                // walk through y-neighbors
                for (i = start; i < end; i++) {
                    val += data[k1 + i * w] * wg[i];
                }
                result[k] = val > 0.5 ? 1 : 0;
            }

        return {
            data: result,
            width: w,
            height: h,
            bounds: {
                minX: minX,
                minY: minY,
                maxX: maxX,
                maxY: maxY
            }
        };
    };

    /** Create a border index array of boundary points of the mask with radius-neighbors
      * @param {Object} mask: {Uint8Array} data, {int} width, {int} height, {Object} bounds
      * @param {int} blur radius
      * @param {Uint8Array} visited: mask of visited points (optional) 
      * @return {Array} border index array of boundary points with radius-neighbors (only points need for blur)
      */
    function createBorderForBlur(mask, radius, visited) {

        var x, i, j, y, k, k1, k2,
            w = mask.width,
            h = mask.height,
            data = mask.data,
            visitedData = new Uint8Array(data),
            minX = mask.bounds.minX,
            maxX = mask.bounds.maxX,
            minY = mask.bounds.minY,
            maxY = mask.bounds.maxY,
            len = w * h,
            temp = new Uint8Array(len), // auxiliary array to check uniqueness
            border = [], // only border points
            x0 = Math.max(minX, 1),
            x1 = Math.min(maxX, w - 2),
            y0 = Math.max(minY, 1),
            y1 = Math.min(maxY, h - 2);

        if (visited && visited.length > 0) {
            // copy visited points (only "black")
            for (k = 0; k < len; k++) {
                if (visited[k] === 1) visitedData[k] = 1;
            }
        }

        // walk through inner values except points on the boundary of the image
        for (y = y0; y < y1 + 1; y++)
            for (x = x0; x < x1 + 1; x++) {
                k = y * w + x;
                if (data[k] === 0) continue; // "white" point isn't the border
                k1 = k + w; // y + 1
                k2 = k - w; // y - 1
                // check if any neighbor with a "white" color
                if (visitedData[k + 1] === 0 || visitedData[k - 1] === 0 ||
                    visitedData[k1] === 0 || visitedData[k1 + 1] === 0 || visitedData[k1 - 1] === 0 ||
                    visitedData[k2] === 0 || visitedData[k2 + 1] === 0 || visitedData[k2 - 1] === 0) {
                    //if (visitedData[k + 1] + visitedData[k - 1] + 
                    //    visitedData[k1] + visitedData[k1 + 1] + visitedData[k1 - 1] +
                    //    visitedData[k2] + visitedData[k2 + 1] + visitedData[k2 - 1] == 8) continue;
                    border.push(k);
                }
            }

        // walk through points on the boundary of the image if necessary
        // if the "black" point is adjacent to the boundary of the image, it is a border point
        if (minX == 0)
            for (y = minY; y < maxY + 1; y++)
                if (data[y * w] === 1)
                    border.push(y * w);

        if (maxX == w - 1)
            for (y = minY; y < maxY + 1; y++)
                if (data[y * w + maxX] === 1)
                    border.push(y * w + maxX);

        if (minY == 0)
            for (x = minX; x < maxX + 1; x++)
                if (data[x] === 1)
                    border.push(x);

        if (maxY == h - 1)
            for (x = minX; x < maxX + 1; x++)
                if (data[maxY * w + x] === 1)
                    border.push(maxY * w + x);

        var result = [], // border points with radius-neighbors
            start, end,
            endX = radius + w,
            endY = radius + h,
            n = radius * 2 + 1; // size of the pattern for radius-neighbors (from -r to +r with the center point)

        len = border.length;
        // walk through radius-neighbors of border points and add them to the result array
        for (j = 0; j < len; j++) {
            k = border[j]; // index of the border point
            temp[k] = 1; // mark border point
            result.push(k); // save the border point
            x = k % w; // calc x by index
            y = (k - x) / w; // calc y by index
            start = radius - x > 0 ? radius - x : 0;
            end = endX - x < n ? endX - x : n; // Math.min((((w - 1) - x) + radius) + 1, n);
            k1 = k - radius;
            // walk through x-neighbors
            for (i = start; i < end; i++) {
                k2 = k1 + i;
                if (temp[k2] === 0) { // check the uniqueness
                    temp[k2] = 1;
                    result.push(k2);
                }
            }
            start = radius - y > 0 ? radius - y : 0;
            end = endY - y < n ? endY - y : n; // Math.min((((h - 1) - y) + radius) + 1, n);
            k1 = k - radius * w;
            // walk through y-neighbors
            for (i = start; i < end; i++) {
                k2 = k1 + i * w;
                if (temp[k2] === 0) { // check the uniqueness
                    temp[k2] = 1;
                    result.push(k2);
                }
            }
        }

        return result;
    };

    /** Apply the gauss-blur filter ONLY to border points with radius-neighbors
      * Algorithms: http://blog.ivank.net/fastest-gaussian-blur.html
      * http://www.librow.com/articles/article-9
      * http://elynxsdk.free.fr/ext-docs/Blur/Fast_box_blur.pdf
      * @param {Object} mask: {Uint8Array} data, {int} width, {int} height, {Object} bounds
      * @param {int} blur radius
      * @param {Uint8Array} visited: mask of visited points (optional) 
      * @return {Object} mask: {Uint8Array} data, {int} width, {int} height, {Object} bounds
      */
    lib.gaussBlurOnlyBorder = function(mask, radius, visited) {

        var border = createBorderForBlur(mask, radius, visited), // get border points with radius-neighbors
            ww, dsq, i, j, k, k1, x, y, val, start, end,
            n = radius * 2 + 1, // size of the pattern for radius-neighbors (from -r to +r with center point)
            s2 = 2 * radius * radius,
            wg = new Float32Array(n), // weights
            total = 0, // sum of weights(used for normalization)
            w = mask.width,
            h = mask.height,
            data = mask.data,
            minX = mask.bounds.minX,
            maxX = mask.bounds.maxX,
            minY = mask.bounds.minY,
            maxY = mask.bounds.maxY,
            len = border.length;

        // calc gauss weights
        for (i = 0; i < radius; i++) {
            dsq = (radius - i) * (radius - i);
            ww = Math.exp(-dsq / s2) / Math.PI;
            wg[radius + i] = wg[radius - i] = ww;
            total += 2 * ww;
        }
        // normalization weights
        for (i = 0; i < n; i++) {
            wg[i] /= total;
        }

        var result = new Uint8Array(data), // copy the source mask
            endX = radius + w,
            endY = radius + h;

        //walk through all border points for blur
        for (i = 0; i < len; i++) {
            k = border[i]; // index of the border point
            val = 0;
            x = k % w; // calc x by index
            y = (k - x) / w; // calc y by index
            start = radius - x > 0 ? radius - x : 0;
            end = endX - x < n ? endX - x : n; // Math.min((((w - 1) - x) + radius) + 1, n);
            k1 = k - radius;
            // walk through x-neighbors
            for (j = start; j < end; j++) {
                val += data[k1 + j] * wg[j];
            }
            if (val > 0.5) {
                result[k] = 1;
                // check minmax
                if (x < minX) minX = x;
                if (x > maxX) maxX = x;
                if (y < minY) minY = y;
                if (y > maxY) maxY = y;
                continue;
            }
            start = radius - y > 0 ? radius - y : 0;
            end = endY - y < n ? endY - y : n; // Math.min((((h - 1) - y) + radius) + 1, n);
            k1 = k - radius * w;
            // walk through y-neighbors
            for (j = start; j < end; j++) {
                val += data[k1 + j * w] * wg[j];
            }
            if (val > 0.5) {
                result[k] = 1;
                // check minmax
                if (x < minX) minX = x;
                if (x > maxX) maxX = x;
                if (y < minY) minY = y;
                if (y > maxY) maxY = y;
            } else {
                result[k] = 0;
            }
        }

        return {
            data: result,
            width: w,
            height: h,
            bounds: {
                minX: minX,
                minY: minY,
                maxX: maxX,
                maxY: maxY
            }
        };
    };

    /** Create a border mask (only boundary points)
      * @param {Object} mask: {Uint8Array} data, {int} width, {int} height, {Object} bounds
      * @return {Object} border mask: {Uint8Array} data, {int} width, {int} height, {Object} offset
      */
    lib.createBorderMask = function(mask) {

        var x, y, k, k1, k2,
            w = mask.width,
            h = mask.height,
            data = mask.data,
            minX = mask.bounds.minX,
            maxX = mask.bounds.maxX,
            minY = mask.bounds.minY,
            maxY = mask.bounds.maxY,
            rw = maxX - minX + 1, // bounds size
            rh = maxY - minY + 1,
            result = new Uint8Array(rw * rh), // reduced mask (bounds size)
            x0 = Math.max(minX, 1),
            x1 = Math.min(maxX, w - 2),
            y0 = Math.max(minY, 1),
            y1 = Math.min(maxY, h - 2);

        // walk through inner values except points on the boundary of the image
        for (y = y0; y < y1 + 1; y++)
            for (x = x0; x < x1 + 1; x++) {
                k = y * w + x;
                if (data[k] === 0) continue; // "white" point isn't the border
                k1 = k + w; // y + 1
                k2 = k - w; // y - 1
                // check if any neighbor with a "white" color
                if (data[k + 1] === 0 || data[k - 1] === 0 ||
                    data[k1] === 0 || data[k1 + 1] === 0 || data[k1 - 1] === 0 ||
                    data[k2] === 0 || data[k2 + 1] === 0 || data[k2 - 1] === 0) {
                    //if (data[k + 1] + data[k - 1] + 
                    //    data[k1] + data[k1 + 1] + data[k1 - 1] +
                    //    data[k2] + data[k2 + 1] + data[k2 - 1] == 8) continue;
                    result[(y - minY) * rw + (x - minX)] = 1;
                }
            }

        // walk through points on the boundary of the image if necessary
        // if the "black" point is adjacent to the boundary of the image, it is a border point
        if (minX == 0)
            for (y = minY; y < maxY + 1; y++)
                if (data[y * w] === 1)
                    result[(y - minY) * rw] = 1;

        if (maxX == w - 1)
            for (y = minY; y < maxY + 1; y++)
                if (data[y * w + maxX] === 1)
                    result[(y - minY) * rw + (maxX - minX)] = 1;

        if (minY == 0)
            for (x = minX; x < maxX + 1; x++)
                if (data[x] === 1)
                    result[x - minX] = 1;

        if (maxY == h - 1)
            for (x = minX; x < maxX + 1; x++)
                if (data[maxY * w + x] === 1)
                    result[(maxY - minY) * rw + (x - minX)] = 1;

        return {
            data: result,
            width: rw,
            height: rh,
            offset: { x: minX, y: minY }
        };
    };
    
    /** Create a border index array of boundary points of the mask
      * @param {Object} mask: {Uint8Array} data, {int} width, {int} height
      * @return {Array} border index array boundary points of the mask
      */
    lib.getBorderIndices = function(mask) {

        var x, y, k, k1, k2,
            w = mask.width,
            h = mask.height,
            data = mask.data,
            border = [], // only border points
            x1 = w - 1,
            y1 = h - 1;

        // walk through inner values except points on the boundary of the image
        for (y = 1; y < y1; y++)
            for (x = 1; x < x1; x++) {
                k = y * w + x;
                if (data[k] === 0) continue; // "white" point isn't the border
                k1 = k + w; // y + 1
                k2 = k - w; // y - 1
                // check if any neighbor with a "white" color
                if (data[k + 1] === 0 || data[k - 1] === 0 ||
                    data[k1] === 0 || data[k1 + 1] === 0 || data[k1 - 1] === 0 ||
                    data[k2] === 0 || data[k2 + 1] === 0 || data[k2 - 1] === 0) {
                    //if (data[k + 1] + data[k - 1] + 
                    //    data[k1] + data[k1 + 1] + data[k1 - 1] +
                    //    data[k2] + data[k2 + 1] + data[k2 - 1] == 8) continue;
                    border.push(k);
                }
            }

        // walk through points on the boundary of the image if necessary
        // if the "black" point is adjacent to the boundary of the image, it is a border point
        for (y = 0; y < h; y++)
            if (data[y * w] === 1)
                border.push(y * w);

        for (x = 0; x < w; x++)
            if (data[x] === 1)
                border.push(x);

        k = w - 1;
        for (y = 0; y < h; y++)
            if (data[y * w + k] === 1)
                border.push(y * w + k);

        k = (h - 1) * w;
        for (x = 0; x < w; x++)
            if (data[k + x] === 1)
                border.push(k + x);

        return border;
    };
    
    /** Create a compressed mask with a "white" border (1px border with zero values) for the contour tracing
      * @param {Object} mask: {Uint8Array} data, {int} width, {int} height, {Object} bounds
      * @return {Object} border mask: {Uint8Array} data, {int} width, {int} height, {Object} offset
      */
    function prepareMask(mask) {
        var x, y,
            w = mask.width,
            data = mask.data,
            minX = mask.bounds.minX,
            maxX = mask.bounds.maxX,
            minY = mask.bounds.minY,
            maxY = mask.bounds.maxY,
            rw = maxX - minX + 3, // bounds size +1 px on each side (a "white" border)
            rh = maxY - minY + 3,
            result = new Uint8Array(rw * rh); // reduced mask (bounds size)

        // walk through inner values and copy only "black" points to the result mask
        for (y = minY; y < maxY + 1; y++)
            for (x = minX; x < maxX + 1; x++) {
                if (data[y * w + x] === 1)
                    result[(y - minY + 1) * rw + (x - minX + 1)] = 1;
            }

        return {
            data: result,
            width: rw,
            height: rh,
            offset: { x: minX - 1, y: minY - 1 }
        };
    };
        
    /** Create a contour array for the binary mask
      * Algorithm: http://www.sciencedirect.com/science/article/pii/S1077314203001401
      * @param {Object} mask: {Uint8Array} data, {int} width, {int} height, {Object} bounds
      * @return {Array} contours: {Array} points, {bool} inner, {int} label
      */
    lib.traceContours = function(mask) {
        var m = prepareMask(mask),
            contours = [],
            label = 0,
            w = m.width,
            w2 = w * 2,
            h = m.height,
            src = m.data,
            dx = m.offset.x,
            dy = m.offset.y,
            dest = new Uint8Array(src), // label matrix
            i, j, x, y, k, k1, c, inner, dir, first, second, current, previous, next, d;

        // all [dx,dy] pairs (array index is the direction)
        // 5 6 7
        // 4 X 0
        // 3 2 1
        var directions = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]];

        for (y = 1; y < h - 1; y++)
            for (x = 1; x < w - 1; x++) {
                k = y * w + x;
                if (src[k] === 1) {
                    for (i = -w; i < w2; i += w2) { // k - w: outer tracing (y - 1), k + w: inner tracing (y + 1)
                        if (src[k + i] === 0 && dest[k + i] === 0) { // need contour tracing
                            inner = i === w; // is inner contour tracing ?
                            label++; // label for the next contour

                            c = [];
                            dir = inner ? 2 : 6; // start direction
                            current = previous = first = { x: x, y: y };
                            second = null;
                            while (true) {
                                dest[current.y * w + current.x] = label; // mark label for the current point 
                                // bypass all the neighbors around the current point in a clockwise
                                for (j = 0; j < 8; j++) {
                                    dir = (dir + 1) % 8;

                                    // get the next point by new direction
                                    d = directions[dir]; // index as direction
                                    next = { x: current.x + d[0], y: current.y + d[1] };

                                    k1 = next.y * w + next.x;
                                    if (src[k1] === 1) // black boundary pixel
                                    {
                                        dest[k1] = label; // mark a label
                                        break;
                                    }
                                    dest[k1] = -1; // mark a white boundary pixel
                                    next = null;
                                }
                                if (next === null) break; // no neighbours (one-point contour)
                                current = next;
                                if (second) {
                                    if (previous.x === first.x && previous.y === first.y && current.x === second.x && current.y === second.y) {
                                        break; // creating the contour completed when returned to original position
                                    }
                                } else {
                                    second = next;
                                }
                                c.push({ x: previous.x + dx, y: previous.y + dy });
                                previous = current;
                                dir = (dir + 4) % 8; // next dir (symmetrically to the current direction)
                            }

                            if (next != null) {
                                c.push({ x: first.x + dx, y: first.y + dy }); // close the contour
                                contours.push({ inner: inner, label: label, points: c }); // add contour to the list
                            }
                        }
                    }
                }
            }

        return contours;
    };
    
    /** Simplify contours
      * Algorithms: http://psimpl.sourceforge.net/douglas-peucker.html 
      * http://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D0%BF%D1%80%D0%BE%D1%89%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BE%D0%BB%D0%B8%D0%B3%D0%BE%D0%BD%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B9_%D1%86%D0%B5%D0%BF%D0%B8
      * @param {Array} contours: {Array} points, {bool} inner, {int} label
      * @param {float} simplify tolerant
      * @param {int} simplify count: min number of points when the contour is simplified
      * @return {Array} contours: {Array} points, {bool} inner, {int} label, {int} initialCount
      */
    lib.simplifyContours = function(contours, simplifyTolerant, simplifyCount) {
        var lenContours = contours.length,
            result = [],
            i, j, k, c, points, len, resPoints, lst, stack, ids,
            maxd, maxi, dist, r1, r2, r12, dx, dy, pi, pf, pl;

        // walk through all contours 
        for (j = 0; j < lenContours; j++) {
            c = contours[j];
            points = c.points;
            len = c.points.length;

            if (len < simplifyCount) { // contour isn't simplified
                resPoints = [];
                for (k = 0; k < len; k++) {
                    resPoints.push({ x: points[k].x, y: points[k].y });
                }
                result.push({ inner: c.inner, label: c.label, points: resPoints, initialCount: len });
                continue;
            }

            lst = [0, len - 1]; // always add first and last points
            stack = [{ first: 0, last: len - 1 }]; // first processed edge

            do {
                ids = stack.shift();
                if (ids.last <= ids.first + 1) // no intermediate points
                {
                    continue;
                }

                maxd = -1.0; // max distance from point to current edge
                maxi = ids.first; // index of maximally distant point

                for (i = ids.first + 1; i < ids.last; i++) // bypass intermediate points in edge
                {
                    // calc the distance from current point to edge
                    pi = points[i];
                    pf = points[ids.first];
                    pl = points[ids.last];
                    dx = pi.x - pf.x;
                    dy = pi.y - pf.y;
                    r1 = Math.sqrt(dx * dx + dy * dy);
                    dx = pi.x - pl.x;
                    dy = pi.y - pl.y;
                    r2 = Math.sqrt(dx * dx + dy * dy);
                    dx = pf.x - pl.x;
                    dy = pf.y - pl.y;
                    r12 = Math.sqrt(dx * dx + dy * dy);
                    if (r1 >= Math.sqrt(r2 * r2 + r12 * r12)) dist = r2;
                    else if (r2 >= Math.sqrt(r1 * r1 + r12 * r12)) dist = r1;
                    else dist = Math.abs((dy * pi.x - dx * pi.y + pf.x * pl.y - pl.x * pf.y) / r12);

                    if (dist > maxd) {
                        maxi = i; // save the index of maximally distant point
                        maxd = dist;
                    }
                }

                if (maxd > simplifyTolerant) // if the max "deviation" is larger than allowed then...
                {
                    lst.push(maxi); // add index to the simplified list
                    stack.push({ first: ids.first, last: maxi }); // add the left part for processing
                    stack.push({ first: maxi, last: ids.last }); // add the right part for processing
                }

            } while (stack.length > 0);

            resPoints = [];
            len = lst.length;
            lst.sort(function(a, b) { return a - b; }); // restore index order
            for (k = 0; k < len; k++) {
                resPoints.push({ x: points[lst[k]].x, y: points[lst[k]].y }); // add result points to the correct order
            }
            result.push({ inner: c.inner, label: c.label, points: resPoints, initialCount: c.points.length });
        }

        return result;
    };

    return lib;
})();