cpp/core/src/zxing/common/EdgeDetector.cpp

   1 /*
   2  *  EdgeDetector.cpp
   3  *  zxing
   4  *
   5  *  Created by Ralf Kistner on 7/12/2009.
   6  *  Copyright 2008 ZXing authors All rights reserved.
   7  *
   8  * Licensed under the Apache License, Version 2.0 (the "License");
   9  * you may not use this file except in compliance with the License.
  10  * You may obtain a copy of the License at
  11  *
  12  *      http://www.apache.org/licenses/LICENSE-2.0
  13  *
  14  * Unless required by applicable law or agreed to in writing, software
  15  * distributed under the License is distributed on an "AS IS" BASIS,
  16  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  17  * See the License for the specific language governing permissions and
  18  * limitations under the License.
  19  */
  20
  21 #include <zxing/common/EdgeDetector.h>
  22 #include <algorithm>
  23 #include <cmath>
  24
  25 using namespace std;
  26
  27 namespace zxing {
  28 namespace EdgeDetector {
  29
  30 void findEdgePoints(std::vector<Point>& points, const BitMatrix& image, Point start, Point end, bool invert, int skip, float deviation) {
  31   float xdist = end.x - start.x;
  32   float ydist = end.y - start.y;
  33   float length = sqrt(xdist * xdist + ydist * ydist);
  34
  35
  36   int var;
  37
  38   if (abs(xdist) > abs(ydist)) {
  39     // Horizontal
  40     if (xdist < 0)
  41       skip = -skip;
  42
  43     var = int(abs(deviation * length / xdist));
  44
  45     float dy = ydist / xdist * skip;
  46     bool left = (skip < 0) ^ invert;
  47     int x = int(start.x);
  48
  49     int steps = int(xdist / skip);
  50     for (int i = 0; i < steps; i++) {
  51       x += skip;
  52       if (x < 0 || x >= (int)image.getWidth())
  53         continue; // In case we start off the edge
  54       int my = int(start.y + dy * i);
  55       int ey = min(my + var + 1, (int)image.getHeight() - 1);
  56       int sy = max(my - var, 0);
  57       for (int y = sy + 1; y < ey; y++) {
  58         if (left) {
  59           if (image.get(x, y) && !image.get(x, y + 1)) {
  60             points.push_back(Point(x, y + 0.5f));
  61           }
  62         } else {
  63           if (!image.get(x, y) && image.get(x, y + 1)) {
  64             points.push_back(Point(x, y + 0.5f));
  65           }
  66         }
  67       }
  68     }
  69   } else {
  70     // Vertical
  71     if (ydist < 0)
  72       skip = -skip;
  73
  74     var = int(abs(deviation * length / ydist));
  75
  76     float dx = xdist / ydist * skip;
  77     bool down = (skip > 0) ^ invert;
  78     int y = int(start.y);
  79
  80     int steps = int(ydist / skip);
  81     for (int i = 0; i < steps; i++) {
  82       y += skip;
  83       if (y < 0 || y >= (int)image.getHeight())
  84         continue; // In case we start off the edge
  85       int mx = int(start.x + dx * i);
  86       int ex = min(mx + var + 1, (int)image.getWidth() - 1);
  87       int sx = max(mx - var, 0);
  88       for (int x = sx + 1; x < ex; x++) {
  89         if (down) {
  90           if (image.get(x, y) && !image.get(x + 1, y)) {
  91             points.push_back(Point(x + 0.5f, y));
  92           }
  93
  94         } else {
  95           if (!image.get(x, y) && image.get(x + 1, y)) {
  96             points.push_back(Point(x + 0.5f, y));
  97           }
  98         }
  99
 100       }
 101     }
 102
 103   }
 104 }
 105
 106 Line findLine(const BitMatrix& image, Line estimate, bool invert, int deviation, float threshold, int skip) {
 107   float t = threshold * threshold;
 108
 109   Point start = estimate.start;
 110   Point end = estimate.end;
 111
 112   vector<Point> edges;
 113   edges.clear();
 114   findEdgePoints(edges, image, start, end, invert, skip, deviation);
 115
 116   int n = edges.size();
 117
 118   float xdist = end.x - start.x;
 119   float ydist = end.y - start.y;
 120
 121   bool horizontal = abs(xdist) > abs(ydist);
 122
 123   float max = 0;
 124   Line bestLine(start, end);  // prepopulate with the given line, in case we can't find any line for some reason
 125
 126   for (int i = -deviation; i < deviation; i++) {
 127     float x1, y1;
 128     if (horizontal) {
 129       y1 = start.y + i;
 130       x1 = start.x - i * ydist / xdist;
 131     } else {
 132       y1 = start.y - i * xdist / ydist;
 133       x1 = start.x + i;
 134     }
 135
 136     for (int j = -deviation; j < deviation; j++) {
 137       float x2, y2;
 138       if (horizontal) {
 139         y2 = end.y + j;
 140         x2 = end.x - j * ydist / xdist;
 141       } else {
 142         y2 = end.y - j * xdist / ydist;
 143         x2 = end.x + j;
 144       }
 145
 146       float dx = x1 - x2;
 147       float dy = y1 - y2;
 148       float length = sqrt(dx * dx + dy * dy);
 149
 150       float score = 0;
 151
 152       for(int k = 0; k < n; k++) {
 153         const Point& edge = edges[k];
 154         float dist = ((x1 - edge.x) * dy - (y1 - edge.y) * dx) / length;
 155         // Similar to least squares method
 156         float s = t - dist * dist;
 157         if (s > 0)
 158           score += s;
 159       }
 160
 161       if (score > max) {
 162         max = score;
 163         bestLine.start = Point(x1, y1);
 164         bestLine.end = Point(x2, y2);
 165       }
 166     }
 167   }
 168
 169   return bestLine;
 170 }
 171
 172 Point intersection(Line a, Line b) {
 173   float dxa = a.start.x - a.end.x;
 174   float dxb = b.start.x - b.end.x;
 175   float dya = a.start.y - a.end.y;
 176   float dyb = b.start.y - b.end.y;
 177
 178   float p = a.start.x * a.end.y - a.start.y * a.end.x;
 179   float q = b.start.x * b.end.y - b.start.y * b.end.x;
 180   float denom = dxa * dyb - dya * dxb;
 181   if(denom == 0)  // Lines don't intersect
 182     return Point(INFINITY, INFINITY);
 183
 184   float x = (p * dxb - dxa * q) / denom;
 185   float y = (p * dyb - dya * q) / denom;
 186
 187   return Point(x, y);
 188 }
 189
 190 } // namespace EdgeDetector
 191 } // namespace zxing