Обнаружение QR-кода с помощью JavaScript и OpenCV - приложение для веб-приложений дополненной реальности

Question

Я работаю над дополненной реальностью для браузеров, которая обнаруживает QR-код на бумаге DIN A4 и проектирует 3D-проект в комнате. До сих пор у меня есть рабочее решение, которое работает с кодами ARUCO, но для моего приложения мне нужен QR-код для проектирования 3D-объекта в правильной перспективе. Это работает также с кодами ARUCO, но только на близком расстоянии. Если маркер находится далеко, это не работает для меня. Решением этого является сканирование QR-кода, поскольку контуры могут быть обнаружены при больших размерах.

У меня есть решение, которое работает с QR-кодами, но код wirtten на C++. Я попытался перекодировать программу te C++ на JavaScript.

Это решение Уокинг, который отлично работает с ARUCO кодами в JavaScript:

вар JS = http://jeromeetienne.github.io/slides/augmentedrealitywiththreejs/

это основной файл: https://github.com/jeromeetienne/arplayerforthreejs

Это код в C++, который работает с QR-кодами:

вар C++ = https://github.com/xingdi-eric-yuan/qr-decoder

До сих пор я написал код из crdecoder.cpp в JavaScript. Вместо отслеживания ARUCO я хочу, чтобы wo использовал скрипт из qrdecoder.cpp, чтобы обнаружить QR-код и получить позицию. Код должен уже определять контуры с QR-кода и записывать его в «this.vecpair;» но он все еще не работает ...

Интерфейс для декодирования в JS-коде находится в файле «threex.jsarucomarker.js», а функция «QR.Detector();»

И это мой еще не законченный сценарий JS, который представляет собой сочетание кода ARUCO aruco.js от JS и QR-логики от скрипта qrdecoder.cpp C++.

var QR = QR || {}; 

QR.Marker = function(id, corners){ 
    this.id = id; 
    this.corners = corners; 
}; 

QR.Detector = function(){ 
    this.grey = new CV.Image(); 
    this.thres = new CV.Image(); 
    this.homography = new CV.Image(); 
    this.binary = []; 
    this.cont = []; 
    this.vec4i = []; 
    this.contours = this.cont.contours = []; 
}; 

QR.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); 

    //this.contours = this.findLimitedConturs(this.thres, 8.00, 0.2 * image.width * image.height); 

// console.log(this.contours); 

    this.vecpair = this.getContourPair(this.contours); 

    console.log(this.vecpair); 

    // ARUCO CODE.. MAYBE NOT NECESSARY 
    //this.candidates = this.findCandidates(this.contours, image.width * 0.10, 0.05, 10); 
    //this.candidates = this.clockwiseCorners(this.candidates); 
    //this.candidates = this.notTooNear(this.candidates, 10); 

    //return this.findMarkers(this.grey, this.candidates, 49); 
}; 

/* C++ 
struct FinderPattern{ 
    Point topleft; 
    Point topright; 
    Point bottomleft; 
    FinderPattern(Point a, Point b, Point c) : topleft(a), topright(b), bottomleft(c) {} 
}; 

bool compareContourAreas (std::vector<cv::Point> contour1, std::vector<cv::Point> contour2) { 
    double i = fabs(contourArea(cv::Mat(contour1))); 
    double j = fabs(contourArea(cv::Mat(contour2))); 
    return (i > j); 
} 
*/ 

QR.Detector.prototype.compareContourAreas = function(c1,c2){ 
    var i = abs(CV.contourArea(c1)); 
    var j = abs(CV.contourArea(c2)); 

    console.log(i+' -- '+j); 

    return (i > j); 
}; 


/* C++ 
Point getContourCentre(CONT& vec){ 
    double tempx = 0.0, tempy = 0.0; 
    for(int i=0; i<vec.size(); i++){ 
     tempx += vec[i].x; 
     tempy += vec[i].y; 
    } 
    return Point(tempx/(double)vec.size(), tempy/(double)vec.size()); 
} 
*/ 
QR.Detector.prototype.getContourCentre = function(vec){ 

}; 


/* C++ 
bool isContourInsideContour(CONT& in, CONT& out){ 
    for(int i = 0; i<in.size(); i++){ 
     if(pointPolygonTest(out, in[i], false) <= 0) return false; 
    } 
    return true; 
} 
*/ 
QR.Detector.prototype.isContourInsideContour = function(c_in, c_out){ 
    for(var i = 0; i<c_in.length; i++){ 

     //console.log('-- '+c_out+' -- '+c_in[i]); 

     if(CV.pointPolygonTest(c_out, c_in[i]) == false) return false; 
    } 
    return true; 
}; 

/* C++ 
vector<CONT > findLimitedConturs(Mat contour, float minPix, float maxPix){ 
    vector<CONT > contours; 
    vector<Vec4i> hierarchy; 
    findContours(contour, contours, hierarchy, RETR_TREE, CHAIN_APPROX_SIMPLE); 
    cout<<"contours.size = "<<contours.size()<<endl; 
    int m = 0; 
    while(m < contours.size()){ 
     if(contourArea(contours[m]) <= minPix){ 
      contours.erase(contours.begin() + m); 
     }else if(contourArea(contours[m]) > maxPix){ 
      contours.erase(contours.begin() + m); 
     }else ++ m; 
    } 
    cout<<"contours.size = "<<contours.size()<<endl; 
    return contours; 
} 
*/ 
QR.Detector.prototype.findLimitedConturs = function(contour, minPix, maxPix){ 

     this.contours = this.cont.contours = []; 
     this.hierarchy = this.vec4i.hierarchy = []; 

     CV.findContours(contour, this.contours); 

     // console.log(this.contours); 

     var m = 0; 
     while(m < this.contours.length){ 
      if(CV.contourArea(this.contours[m]) <= minPix){ 
       this.contours.splice(this.contours[0] + m,1); 
      }else if(CV.contourArea(this.contours[m]) > maxPix){ 
       this.contours.splice(this.contours[0] + m,1); 
      }else ++ m; 
     } 

     // console.log(this.contours.length); 

     return this.contours; 

}; 

/* 
vector<vector<CONT > > getContourPair(vector<CONT > &contours){ 
    vector<vector<CONT > > vecpair; 
    vector<bool> bflag(contours.size(), false); 

    for(int i = 0; i<contours.size() - 1; i++){ 
     if(bflag[i]) continue; 
     vector<CONT > temp; 
     temp.push_back(contours[i]); 
     for(int j = i + 1; j<contours.size(); j++){ 
      if(isContourInsideContour(contours[j], contours[i])){ 
       temp.push_back(contours[j]); 
       bflag[j] = true; 
      } 
     } 
     if(temp.size() > 1){ 
      vecpair.push_back(temp); 
     } 
    } 
    bflag.clear(); 
    for(int i=0; i<vecpair.size(); i++){ 
     sort(vecpair[i].begin(), vecpair[i].end(), compareContourAreas); 
    } 
    return vecpair; 
} 
*/ 
QR.Detector.prototype.getContourPair = function(contours){ 
    this.vecpair = this.cont.vecpair = []; 
    var bflag = new Array(contours.length, false); // similar to c++: vector<bool> bflag(contours.size(), false);? 

    for(var i = 0; i<contours.length - 1; i++){ 
     if(bflag[i] == false){ //similar to c++: if(bflag[i]) continue; ??   
      var temp = this.cont.temp = []; 

      //console.log(contours[i]); 

      temp.push(contours[i]); //similar to c++: temp.push_back(contours[i]); ?? 
      for(var j = i + 1; j<contours.length; j++){ 
       if(this.isContourInsideContour(contours[j], contours[i])){ 
        temp.push(contours[j]); 
        bflag[j] = true; 

        // console.log('true'); 
       } 
      } 
      if(temp.length > 1){ 
       this.vecpair.push(temp); 
      } 
     } 
    } 

    //console.log(this.vecpair); 

    bflag = []; 

    //console.log(this.vecpair.length); 

    for(i=0; i<this.vecpair.length; i++){ 
     // sort(this.vecpair[0], this.vecpair[this.vecpair.length], compareContourAreas); 

     this.vecpair.sort(function(){ 

      console.log('hier'); 

      this.compareContourAreas(this.vecpair[i], this.vecpair[i].length); 
     }); 

     // console.log(this.vecpair); 
    } 


    return this.vecpair;  
}; 

/* C++ 
void eliminatePairs(vector<vector<CONT > >& vecpair, double minRatio, double maxRatio){ 
    cout<<"maxRatio = "<<maxRatio<<endl; 
    int m = 0; 
    bool flag = false; 
    while(m < vecpair.size()){ 
     flag = false; 
     if(vecpair[m].size() < 3){ 
      vecpair.erase(vecpair.begin() + m); 
      continue; 
     } 
     for(int i=0; i<vecpair[m].size() - 1; i++){ 
      double area1 = contourArea(vecpair[m][i]); 
      double area2 = contourArea(vecpair[m][i + 1]); 
      if(area1/area2 < minRatio || area1/area2 > maxRatio){ 
       vecpair.erase(vecpair.begin() + m); 
       flag = true; 
       break; 
      } 
     } 
     if(!flag){ 
      ++ m; 
     } 
    } 
    if(vecpair.size() > 3){ 
     eliminatePairs(vecpair, minRatio, maxRatio * 0.9); 
    } 
} 
*/ 
QR.Detector.prototype.eliminatePairs = function(){}; 

/* C++ 
double getDistance(Point a, Point b){ 
    return sqrt(pow((a.x - b.x), 2) + pow((a.y - b.y), 2)); 
} 
*/ 
QR.Detector.prototype.getDistance = function(){}; 

/* C++ 
FinderPattern getFinderPattern(vector<vector<CONT > > &vecpair){ 
    Point pt1 = getContourCentre(vecpair[0][vecpair[0].size() - 1]); 
    Point pt2 = getContourCentre(vecpair[1][vecpair[1].size() - 1]); 
    Point pt3 = getContourCentre(vecpair[2][vecpair[2].size() - 1]); 
    double d12 = getDistance(pt1, pt2); 
    double d13 = getDistance(pt1, pt3); 
    double d23 = getDistance(pt2, pt3); 
    double x1, y1, x2, y2, x3, y3; 
    double Max = max(d12, max(d13, d23)); 
    Point p1, p2, p3; 
    if(Max == d12){ 
     p1 = pt1; 
     p2 = pt2; 
     p3 = pt3; 
    }else if(Max == d13){ 
     p1 = pt1; 
     p2 = pt3; 
     p3 = pt2; 
    }else if(Max == d23){ 
     p1 = pt2; 
     p2 = pt3; 
     p3 = pt1; 
    } 
    x1 = p1.x; 
    y1 = p1.y; 
    x2 = p2.x; 
    y2 = p2.y; 
    x3 = p3.x; 
    y3 = p3.y; 
    if(x1 == x2){ 
     if(y1 > y2){ 
      if(x3 < x1){ 
       return FinderPattern(p3, p2, p1); 
      }else{ 
       return FinderPattern(p3, p1, p2); 
      } 
     }else{ 
      if(x3 < x1){ 
       return FinderPattern(p3, p1, p2); 
      }else{ 
       return FinderPattern(p3, p2, p1); 
      } 
     } 
    }else{ 
     double newy = (y2 - y1)/(x2 - x1) * x3 + y1 - (y2 - y1)/(x2 - x1) * x1; 
     if(x1 > x2){ 
      if(newy < y3){ 
       return FinderPattern(p3, p2, p1); 
      }else{ 
       return FinderPattern(p3, p1, p2); 
      } 
     }else{ 
      if(newy < y3){ 
       return FinderPattern(p3, p1, p2); 
      }else{ 
       return FinderPattern(p3, p2, p1); 
      } 
     } 
    } 
} 
*/ 

QR.Detector.prototype.getFinderPattern = function(){}; 

Это мои дополнительные функции CV для детектора Основной файл «cv.js» из проекта JavaScript выше https://github.com/jeromeetienne/arplayerforthreejs

Эти функции должны работать аналогично C++ версии

pointPolygonTest() = http://docs.opencv.org/2.4/doc/tutorials/imgproc/shapedescriptors/point_polygon_test/point_polygon_test.html

contourArea() = http://docs.opencv.org/2.4/modules/imgproc/doc/structural_analysis_and_shape_descriptors.html#double

//src: http://jsfromhell.com/math/is-point-in-poly 
    CV.pointPolygonTest = function(poly, pt){ 
     for(var c = false, i = -1, l = poly.length, j = l - 1; ++i < l; j = i) 
      ((poly[i].y <= pt.y && pt.y < poly[j].y) || (poly[j].y <= pt.y && pt.y < poly[i].y)) 
      && (pt.x < (poly[j].x - poly[i].x) * (pt.y - poly[i].y)/(poly[j].y - poly[i].y) + poly[i].x) 
      && (c = !c); 
     return c; 
    }; 

//http://stackoverflow.com/questions/16285134/calculating-polygon-area 
    CV.contourArea = function(cont){  
     //console.log('cont: '+cont); 

     var area = 0; // Accumulates area in the loop 
     var j = cont.length-1; // The last vertex is the 'previous' one to the first 

      for (var i=0; i<cont.length; i++) 
      { 
       area = area + (cont[j].x+cont[i].x) * (cont[j].y+cont[i].y) 
       //area = area + (X[j]+X[i]) * (Y[j]-Y[i]); 
       j = i; //j is previous vertex to i 
      } 
      return area/2; 

    }; 

Answer 1

Рабочая версия JavaScript которым определяет контуры QR Code

var CV = 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; 
}; 


//src: http://jsfromhell.com/math/is-point-in-poly 
CV.pointPolygonTest = function(poly, pt){ 
    for(var c = false, i = -1, l = poly.length, j = l - 1; ++i < l; j = i) 
     ((poly[i].y <= pt.y && pt.y < poly[j].y) || (poly[j].y <= pt.y && pt.y < poly[i].y)) 
     && (pt.x < (poly[j].x - poly[i].x) * (pt.y - poly[i].y)/(poly[j].y - poly[i].y) + poly[i].x) 
     && (c = !c); 
    return c; 
}; 

//http://stackoverflow.com/questions/16285134/calculating-polygon-area 
CV.contourArea = function(cont){  
    //console.log('cont: '+cont); 

    var area = 0; // Accumulates area in the loop 
    var j = cont.length-1; // The last vertex is the 'previous' one to the first 

     for (var i=0; i<cont.length; i++) 
     { 
      area = area + (cont[j].x+cont[i].x) * (cont[j].y+cont[i].y); 
      //area = area + (X[j]+X[i]) * (Y[j]-Y[i]); 
      j = i; //j is previous vertex to i 
     } 
     return area/2; 

};