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
  24 using namespace std;
  25
  26 namespace zxing {
  27 namespace EdgeDetector {
  28
  29 void findEdgePoints(std::vector<Point>& points, const BitMatrix& image, Point start, Point end, bool invert, int skip, float deviation) {
  30   float xdist = end.x - start.x;
  31   float ydist = end.y - start.y;
  32   float length = sqrt(xdist * xdist + ydist * ydist);
  33
  34
  35   int var;
  36
  37   if (abs(xdist) > abs(ydist)) {
  38     // Horizontal
  39     if (xdist < 0)
  40       skip = -skip;
  41
  42     var = int(abs(deviation * length / xdist));
  43
  44     float dy = ydist / xdist * skip;
  45     bool left = (skip < 0) ^ invert;
  46     int x = int(start.x);
  47
  48     int steps = int(xdist / skip);
  49     for (int i = 0; i < steps; i++) {
  50       x += skip;
  51       if (x < 0 || x >= (int)image.getWidth())
  52         continue; // In case we start off the edge
  53       int my = int(start.y + dy * i);
  54       int ey = min(my + var + 1, (int)image.getHeight() - 1);
  55       int sy = max(my - var, 0);
  56       for (int y = sy + 1; y < ey; y++) {
  57         if (left) {
  58           if (image.get(x, y) && !image.get(x, y + 1)) {
  59             points.push_back(Point(x, y + 0.5f));
  60           }
  61         } else {
  62           if (!image.get(x, y) && image.get(x, y + 1)) {
  63             points.push_back(Point(x, y + 0.5f));
  64           }
  65         }
  66       }
  67     }
  68   } else {
  69     // Vertical
  70     if (ydist < 0)
  71       skip = -skip;
  72
  73     var = int(abs(deviation * length / ydist));
  74
  75     float dx = xdist / ydist * skip;
  76     bool down = (skip > 0) ^ invert;
  77     int y = int(start.y);
  78
  79     int steps = int(ydist / skip);
  80     for (int i = 0; i < steps; i++) {
  81       y += skip;
  82       if (y < 0 || y >= (int)image.getHeight())
  83         continue; // In case we start off the edge
  84       int mx = int(start.x + dx * i);
  85       int ex = min(mx + var + 1, (int)image.getWidth() - 1);
  86       int sx = max(mx - var, 0);
  87       for (int x = sx + 1; x < ex; x++) {
  88         if (down) {
  89           if (image.get(x, y) && !image.get(x + 1, y)) {
  90             points.push_back(Point(x + 0.5f, y));
  91           }
  92
  93         } else {
  94           if (!image.get(x, y) && image.get(x + 1, y)) {
  95             points.push_back(Point(x + 0.5f, y));
  96           }
  97         }
  98
  99       }
 100     }
 101
 102   }
 103 }
 104
 105 Line findLine(const BitMatrix& image, Line estimate, bool invert, int deviation, float threshold, int skip) {
 106   float t = threshold * threshold;
 107
 108   Point start = estimate.start;
 109   Point end = estimate.end;
 110
 111   vector<Point> edges;
 112   edges.clear();
 113   findEdgePoints(edges, image, start, end, invert, skip, deviation);
 114
 115   int n = edges.size();
 116
 117   float xdist = end.x - start.x;
 118   float ydist = end.y - start.y;
 119
 120   bool horizontal = abs(xdist) > abs(ydist);
 121
 122   float max = 0;
 123   Line bestLine(start, end);  // prepopulate with the given line, in case we can't find any line for some reason
 124
 125   for (int i = -deviation; i < deviation; i++) {
 126     float x1, y1;
 127     if (horizontal) {
 128       y1 = start.y + i;
 129       x1 = start.x - i * ydist / xdist;
 130     } else {
 131       y1 = start.y - i * xdist / ydist;
 132       x1 = start.x + i;
 133     }
 134
 135     for (int j = -deviation; j < deviation; j++) {
 136       float x2, y2;
 137       if (horizontal) {
 138         y2 = end.y + j;
 139         x2 = end.x - j * ydist / xdist;
 140       } else {
 141         y2 = end.y - j * xdist / ydist;
 142         x2 = end.x + j;
 143       }
 144
 145       float dx = x1 - x2;
 146       float dy = y1 - y2;
 147       float length = sqrt(dx * dx + dy * dy);
 148
 149       float score = 0;
 150
 151       for(int k = 0; k < n; k++) {
 152         const Point& edge = edges[k];
 153         float dist = ((x1 - edge.x) * dy - (y1 - edge.y) * dx) / length;
 154         // Similar to least squares method
 155         float s = t - dist * dist;
 156         if (s > 0)
 157           score += s;
 158       }
 159
 160       if (score > max) {
 161         max = score;
 162         bestLine.start = Point(x1, y1);
 163         bestLine.end = Point(x2, y2);
 164       }
 165     }
 166   }
 167
 168   return bestLine;
 169 }
 170
 171 Point intersection(Line a, Line b) {
 172   float dxa = a.start.x - a.end.x;
 173   float dxb = b.start.x - b.end.x;
 174   float dya = a.start.y - a.end.y;
 175   float dyb = b.start.y - b.end.y;
 176
 177   float p = a.start.x * a.end.y - a.start.y * a.end.x;
 178   float q = b.start.x * b.end.y - b.start.y * b.end.x;
 179   float denom = dxa * dyb - dya * dxb;
 180   if(denom == 0)  // Lines don't intersect
 181     return Point(INFINITY, INFINITY);
 182
 183   float x = (p * dxb - dxa * q) / denom;
 184   float y = (p * dyb - dya * q) / denom;
 185
 186   return Point(x, y);
 187 }
 188
 189 } // namespace EdgeDetector
 190 } // namespace zxing