cpp/core/src/zxing/qrcode/detector/QREdgeDetector.cpp

   1 /*\r
   2  *  QREdgeDetector.cpp\r
   3  *  zxing\r
   4  *\r
   5  *  Created by Ralf Kistner on 7/12/2009.\r
   6  *  Copyright 2008 ZXing authors All rights reserved.\r
   7  *\r
   8  * Licensed under the Apache License, Version 2.0 (the "License");\r
   9  * you may not use this file except in compliance with the License.\r
  10  * You may obtain a copy of the License at\r
  11  *\r
  12  *      http://www.apache.org/licenses/LICENSE-2.0\r
  13  *\r
  14  * Unless required by applicable law or agreed to in writing, software\r
  15  * distributed under the License is distributed on an "AS IS" BASIS,\r
  16  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
  17  * See the License for the specific language governing permissions and\r
  18  * limitations under the License.\r
  19  */\r
  20 \r
  21 #include <zxing/qrcode/detector/QREdgeDetector.h>\r
  22 #include <zxing/common/EdgeDetector.h>\r
  23 #include <cstdlib>\r
  24 \r
  25 using namespace std;\r
  26 \r
  27 namespace zxing {\r
  28 namespace qrcode {\r
  29 \r
  30 static const float patternEdgeThreshold = 2;\r
  31 static const int patternEdgeWidth = 3;\r
  32 static const float patternEdgeSearchRatio = 1.1;\r
  33 static const int patternEdgeSkip = 2;\r
  34 \r
  35 static const float accurateEdgeThreshold = 3.3;\r
  36 static const int accurateEdgeWidth = 7;\r
  37 static const int accurateEdgeSkip = 2;\r
  38 \r
  39 static Point guessLastPattern(Point topLeft, Point topRight, Point bottomLeft) {\r
  40   return Point(topRight.x - topLeft.x + bottomLeft.x, topRight.y - topLeft.y + bottomLeft.y);\r
  41 }\r
  42 \r
  43 static Point rp(Ref<ResultPoint> rp) {\r
  44   return Point(rp->getX(), rp->getY());\r
  45 }\r
  46 \r
  47 QREdgeDetector::QREdgeDetector(Ref<BitMatrix> image) : Detector(image) { }\r
  48 \r
  49 Ref<PerspectiveTransform> QREdgeDetector::createTransform(Ref<ResultPoint> topLeft, Ref<ResultPoint> topRight, Ref <\r
  50       ResultPoint > bottomLeft, Ref<ResultPoint> alignmentPattern, int dimension) {\r
  51 \r
  52   if(alignmentPattern == NULL) {\r
  53     Point corner = findCorner(*Detector::getImage(), rp(topLeft), rp(topRight), rp(bottomLeft), dimension);\r
  54     return get1CornerTransform(rp(topLeft), rp(topRight), rp(bottomLeft), corner, dimension);\r
  55   } else {\r
  56     return Detector::createTransform(topLeft, topRight, bottomLeft, alignmentPattern, dimension);\r
  57   }\r
  58 }\r
  59 \r
  60 \r
  61 \r
  62 \r
  63 Point QREdgeDetector::findCorner(const BitMatrix& image, Point topLeft, Point topRight, Point bottomLeft, int dimension) {\r
  64   Point bottomRight = guessLastPattern(topLeft, topRight, bottomLeft);\r
  65 \r
  66   Line bottomEst = findPatternEdge(image, bottomLeft, topLeft, bottomRight, false);\r
  67   Line rightEst = findPatternEdge(image, topRight, topLeft, bottomRight, true);\r
  68 \r
  69   //return EdgeDetector::intersection(bottomEst, rightEst);\r
  70 \r
  71   Line bottom = EdgeDetector::findLine(image, bottomEst, false, accurateEdgeWidth, accurateEdgeThreshold, accurateEdgeSkip);\r
  72   Line right = EdgeDetector::findLine(image, rightEst, true, accurateEdgeWidth, accurateEdgeThreshold, accurateEdgeSkip);\r
  73 \r
  74 \r
  75   return EdgeDetector::intersection(bottom, right);\r
  76 }\r
  77 \r
  78 Line QREdgeDetector::findPatternEdge(const BitMatrix& image, Point pattern, Point opposite, Point direction, bool invert) {\r
  79   Point start = endOfReverseBlackWhiteBlackRun(image, pattern, opposite);\r
  80 \r
  81   float dx = pattern.x - start.x;\r
  82   float dy = pattern.y - start.y;\r
  83   float dist = sqrt(dx*dx + dy*dy);\r
  84 \r
  85   float dirX = direction.x - pattern.x;\r
  86   float dirY = direction.y - pattern.y;\r
  87   float dirSize = sqrt(dirX*dirX + dirY*dirY);\r
  88 \r
  89   float nx = dirX/dirSize;\r
  90   float ny = dirY/dirSize;\r
  91 \r
  92   float search = dist * patternEdgeSearchRatio;\r
  93   Point a(start.x + nx*search, start.y + ny*search);\r
  94   Point b(start.x - nx*search, start.y - ny*search);\r
  95 \r
  96   return EdgeDetector::findLine(image, Line(a, b), invert, patternEdgeWidth, patternEdgeThreshold, patternEdgeSkip);\r
  97 }\r
  98 \r
  99 \r
 100 Ref<PerspectiveTransform> QREdgeDetector::get1CornerTransform(Point topLeft, Point topRight, Point bottomLeft, Point corner, int dimension) {\r
 101   float dimMinusThree = (float) dimension - 3.5f;\r
 102 \r
 103   Ref<PerspectiveTransform> transform(PerspectiveTransform::quadrilateralToQuadrilateral(3.5f, 3.5f, dimMinusThree, 3.5f, dimension,\r
 104                                       dimension, 3.5f, dimMinusThree, topLeft.x, topLeft.y, topRight.x,\r
 105                                       topRight.y, corner.x, corner.y, bottomLeft.x, bottomLeft.y));\r
 106 \r
 107   return transform;\r
 108 }\r
 109 \r
 110 // Adapted from "sizeOfBlackWhiteBlackRun" in zxing::qrcode::Detector\r
 111 Point QREdgeDetector::endOfReverseBlackWhiteBlackRun(const BitMatrix& image, Point from, Point to) {\r
 112   int fromX = (int)from.x;\r
 113   int fromY = (int)from.y;\r
 114   int toX = (int)to.x;\r
 115   int toY = (int)to.y;\r
 116 \r
 117   bool steep = abs(toY - fromY) > abs(toX - fromX);\r
 118   if (steep) {\r
 119     int temp = fromX;\r
 120     fromX = fromY;\r
 121     fromY = temp;\r
 122     temp = toX;\r
 123     toX = toY;\r
 124     toY = temp;\r
 125   }\r
 126 \r
 127   int dx = abs(toX - fromX);\r
 128   int dy = abs(toY - fromY);\r
 129   int error = -dx >> 1;\r
 130   int ystep = fromY < toY ? -1 : 1;\r
 131   int xstep = fromX < toX ? -1 : 1;\r
 132   int state = 0; // In black pixels, looking for white, first or second time\r
 133 \r
 134   // In case there are no points, prepopulate to from\r
 135   int realX = fromX;\r
 136   int realY = fromY;\r
 137   for (int x = fromX, y = fromY; x != toX; x += xstep) {\r
 138     realX = steep ? y : x;\r
 139     realY = steep ? x : y;\r
 140 \r
 141     if(realX < 0 || realY < 0 || realX >= (int)image.getWidth() || realY >= (int)image.getHeight())\r
 142       break;\r
 143 \r
 144     if (state == 1) { // In white pixels, looking for black\r
 145       if (image.get(realX, realY)) {\r
 146         state++;\r
 147       }\r
 148     } else {\r
 149       if (!image.get(realX, realY)) {\r
 150         state++;\r
 151       }\r
 152     }\r
 153 \r
 154     if (state == 3) { // Found black, white, black, and stumbled back onto white; done\r
 155       return Point(realX, realY);\r
 156     }\r
 157     error += dy;\r
 158     if (error > 0) {\r
 159       y += ystep;\r
 160       error -= dx;\r
 161     }\r
 162   }\r
 163 \r
 164   // B-W-B run not found, return the last point visited.\r
 165   return Point(realX, realY);\r
 166 }\r
 167 \r
 168 } // namespace qrcode\r
 169 } // namespace zxing\r