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

   1 /*\r
   2  *  Detector.cpp\r
   3  *  zxing\r
   4  *\r
   5  *  Created by Christian Brunschen on 14/05/2008.\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/Detector.h>\r
  22 #include <zxing/qrcode/detector/FinderPatternFinder.h>\r
  23 #include <zxing/qrcode/detector/FinderPattern.h>\r
  24 #include <zxing/qrcode/detector/AlignmentPattern.h>\r
  25 #include <zxing/qrcode/detector/AlignmentPatternFinder.h>\r
  26 #include <zxing/qrcode/Version.h>\r
  27 #include <zxing/common/GridSampler.h>\r
  28 #include <cmath>\r
  29 #include <sstream>\r
  30 \r
  31 namespace zxing {\r
  32 namespace qrcode {\r
  33 \r
  34 using namespace std;\r
  35 \r
  36 Detector::Detector(Ref<BitMatrix> image) :\r
  37     image_(image) {\r
  38 }\r
  39 \r
  40 Ref<BitMatrix> Detector::getImage() {\r
  41    return image_;\r
  42 }\r
  43 \r
  44 Ref<DetectorResult> Detector::detect() {\r
  45   FinderPatternFinder finder(image_);\r
  46   Ref<FinderPatternInfo> info(finder.find());\r
  47 \r
  48   Ref<FinderPattern> topLeft(info->getTopLeft());\r
  49   Ref<FinderPattern> topRight(info->getTopRight());\r
  50   Ref<FinderPattern> bottomLeft(info->getBottomLeft());\r
  51 \r
  52   float moduleSize = calculateModuleSize(topLeft, topRight, bottomLeft);\r
  53   int dimension = computeDimension(topLeft, topRight, bottomLeft, moduleSize);\r
  54   Version *provisionalVersion = Version::getProvisionalVersionForDimension(dimension);\r
  55   int modulesBetweenFPCenters = provisionalVersion->getDimensionForVersion() - 7;\r
  56 \r
  57   Ref<AlignmentPattern> alignmentPattern;\r
  58   // Anything above version 1 has an alignment pattern\r
  59   if (provisionalVersion->getAlignmentPatternCenters().size() > 0) {\r
  60 \r
  61 \r
  62     // Guess where a "bottom right" finder pattern would have been\r
  63     float bottomRightX = topRight->getX() - topLeft->getX() + bottomLeft->getX();\r
  64     float bottomRightY = topRight->getY() - topLeft->getY() + bottomLeft->getY();\r
  65 \r
  66 \r
  67     // Estimate that alignment pattern is closer by 3 modules\r
  68     // from "bottom right" to known top left location\r
  69     float correctionToTopLeft = 1.0f - 3.0f / (float)modulesBetweenFPCenters;\r
  70     int estAlignmentX = (int)(topLeft->getX() + correctionToTopLeft * (bottomRightX - topLeft->getX()));\r
  71     int estAlignmentY = (int)(topLeft->getY() + correctionToTopLeft * (bottomRightY - topLeft->getY()));\r
  72 \r
  73 \r
  74     // Kind of arbitrary -- expand search radius before giving up\r
  75     for (int i = 4; i <= 16; i <<= 1) {\r
  76       try {\r
  77         alignmentPattern = findAlignmentInRegion(moduleSize, estAlignmentX, estAlignmentY, (float)i);\r
  78         break;\r
  79       } catch (zxing::ReaderException re) {\r
  80         // try next round\r
  81       }\r
  82     }\r
  83     if (alignmentPattern == 0) {\r
  84       // Try anyway\r
  85     }\r
  86 \r
  87   }\r
  88 \r
  89   Ref<PerspectiveTransform> transform = createTransform(topLeft, topRight, bottomLeft, alignmentPattern, dimension);\r
  90   Ref<BitMatrix> bits(sampleGrid(image_, dimension, transform));\r
  91   std::vector<Ref<ResultPoint> > points(alignmentPattern == 0 ? 3 : 4);\r
  92   points[0].reset(bottomLeft);\r
  93   points[1].reset(topLeft);\r
  94   points[2].reset(topRight);\r
  95   if (alignmentPattern != 0) {\r
  96     points[3].reset(alignmentPattern);\r
  97   }\r
  98 \r
  99   Ref<DetectorResult> result(new DetectorResult(bits, points, transform));\r
 100   return result;\r
 101 }\r
 102 \r
 103 Ref<PerspectiveTransform> Detector::createTransform(Ref<ResultPoint> topLeft, Ref<ResultPoint> topRight, Ref <\r
 104     ResultPoint > bottomLeft, Ref<ResultPoint> alignmentPattern, int dimension) {\r
 105 \r
 106   float dimMinusThree = (float)dimension - 3.5f;\r
 107   float bottomRightX;\r
 108   float bottomRightY;\r
 109   float sourceBottomRightX;\r
 110   float sourceBottomRightY;\r
 111   if (alignmentPattern != 0) {\r
 112     bottomRightX = alignmentPattern->getX();\r
 113     bottomRightY = alignmentPattern->getY();\r
 114     sourceBottomRightX = sourceBottomRightY = dimMinusThree - 3.0f;\r
 115   } else {\r
 116     // Don't have an alignment pattern, just make up the bottom-right point\r
 117     bottomRightX = (topRight->getX() - topLeft->getX()) + bottomLeft->getX();\r
 118     bottomRightY = (topRight->getY() - topLeft->getY()) + bottomLeft->getY();\r
 119     sourceBottomRightX = sourceBottomRightY = dimMinusThree;\r
 120   }\r
 121 \r
 122   Ref<PerspectiveTransform> transform(PerspectiveTransform::quadrilateralToQuadrilateral(3.5f, 3.5f, dimMinusThree, 3.5f, sourceBottomRightX,\r
 123                                       sourceBottomRightY, 3.5f, dimMinusThree, topLeft->getX(), topLeft->getY(), topRight->getX(),\r
 124                                       topRight->getY(), bottomRightX, bottomRightY, bottomLeft->getX(), bottomLeft->getY()));\r
 125 \r
 126   return transform;\r
 127 }\r
 128 \r
 129 Ref<BitMatrix> Detector::sampleGrid(Ref<BitMatrix> image, int dimension, Ref<PerspectiveTransform> transform) {\r
 130   GridSampler &sampler = GridSampler::getInstance();\r
 131   return sampler.sampleGrid(image, dimension, transform);\r
 132 }\r
 133 \r
 134 int Detector::computeDimension(Ref<ResultPoint> topLeft, Ref<ResultPoint> topRight, Ref<ResultPoint> bottomLeft,\r
 135                                float moduleSize) {\r
 136   int tltrCentersDimension = lround(FinderPatternFinder::distance(topLeft, topRight) / moduleSize);\r
 137   int tlblCentersDimension = lround(FinderPatternFinder::distance(topLeft, bottomLeft) / moduleSize);\r
 138   int dimension = ((tltrCentersDimension + tlblCentersDimension) >> 1) + 7;\r
 139   switch (dimension & 0x03) { // mod 4\r
 140   case 0:\r
 141     dimension++;\r
 142     break;\r
 143     // 1? do nothing\r
 144   case 2:\r
 145     dimension--;\r
 146     break;\r
 147   case 3:\r
 148     ostringstream s;\r
 149     s << "Bad dimension: " << dimension;\r
 150     throw zxing::ReaderException(s.str().c_str());\r
 151   }\r
 152   return dimension;\r
 153 }\r
 154 \r
 155 float Detector::calculateModuleSize(Ref<ResultPoint> topLeft, Ref<ResultPoint> topRight, Ref<ResultPoint> bottomLeft) {\r
 156   // Take the average\r
 157   return (calculateModuleSizeOneWay(topLeft, topRight) + calculateModuleSizeOneWay(topLeft, bottomLeft)) / 2.0f;\r
 158 }\r
 159 \r
 160 float Detector::calculateModuleSizeOneWay(Ref<ResultPoint> pattern, Ref<ResultPoint> otherPattern) {\r
 161   float moduleSizeEst1 = sizeOfBlackWhiteBlackRunBothWays((int)pattern->getX(), (int)pattern->getY(),\r
 162                          (int)otherPattern->getX(), (int)otherPattern->getY());\r
 163   float moduleSizeEst2 = sizeOfBlackWhiteBlackRunBothWays((int)otherPattern->getX(), (int)otherPattern->getY(),\r
 164                          (int)pattern->getX(), (int)pattern->getY());\r
 165   if (isnan(moduleSizeEst1)) {\r
 166     return moduleSizeEst2;\r
 167   }\r
 168   if (isnan(moduleSizeEst2)) {\r
 169     return moduleSizeEst1;\r
 170   }\r
 171   // Average them, and divide by 7 since we've counted the width of 3 black modules,\r
 172   // and 1 white and 1 black module on either side. Ergo, divide sum by 14.\r
 173   return (moduleSizeEst1 + moduleSizeEst2) / 14.0f;\r
 174 }\r
 175 \r
 176 float Detector::sizeOfBlackWhiteBlackRunBothWays(int fromX, int fromY, int toX, int toY) {\r
 177 \r
 178   float result = sizeOfBlackWhiteBlackRun(fromX, fromY, toX, toY);\r
 179 \r
 180 \r
 181   // Now count other way -- don't run off image though of course\r
 182   int otherToX = fromX - (toX - fromX);\r
 183   if (otherToX < 0) {\r
 184     // "to" should the be the first value not included, so, the first value off\r
 185     // the edge is -1\r
 186     otherToX = -1;\r
 187   } else if (otherToX >= (int)image_->getWidth()) {\r
 188     otherToX = image_->getWidth();\r
 189   }\r
 190   int otherToY = fromY - (toY - fromY);\r
 191   if (otherToY < 0) {\r
 192     otherToY = -1;\r
 193   } else if (otherToY >= (int)image_->getHeight()) {\r
 194     otherToY = image_->getHeight();\r
 195   }\r
 196   result += sizeOfBlackWhiteBlackRun(fromX, fromY, otherToX, otherToY);\r
 197   return result - 1.0f; // -1 because we counted the middle pixel twice\r
 198 }\r
 199 \r
 200 float Detector::sizeOfBlackWhiteBlackRun(int fromX, int fromY, int toX, int toY) {\r
 201   // Mild variant of Bresenham's algorithm;\r
 202   // see http://en.wikipedia.org/wiki/Bresenham's_line_algorithm\r
 203   bool steep = abs(toY - fromY) > abs(toX - fromX);\r
 204   if (steep) {\r
 205     int temp = fromX;\r
 206     fromX = fromY;\r
 207     fromY = temp;\r
 208     temp = toX;\r
 209     toX = toY;\r
 210     toY = temp;\r
 211   }\r
 212 \r
 213   int dx = abs(toX - fromX);\r
 214   int dy = abs(toY - fromY);\r
 215   int error = -dx >> 1;\r
 216   int ystep = fromY < toY ? 1 : -1;\r
 217   int xstep = fromX < toX ? 1 : -1;\r
 218   int state = 0; // In black pixels, looking for white, first or second time\r
 219   for (int x = fromX, y = fromY; x != toX; x += xstep) {\r
 220 \r
 221     int realX = steep ? y : x;\r
 222     int realY = steep ? x : y;\r
 223     if (state == 1) { // In white pixels, looking for black\r
 224       if (image_->get(realX, realY)) {\r
 225         state++;\r
 226       }\r
 227     } else {\r
 228       if (!image_->get(realX, realY)) {\r
 229         state++;\r
 230       }\r
 231     }\r
 232 \r
 233     if (state == 3) { // Found black, white, black, and stumbled back onto white; done\r
 234       int diffX = x - fromX;\r
 235       int diffY = y - fromY;\r
 236       return (float)sqrt((double)(diffX * diffX + diffY * diffY));\r
 237     }\r
 238     error += dy;\r
 239     if (error > 0) {\r
 240       y += ystep;\r
 241       error -= dx;\r
 242     }\r
 243   }\r
 244   int diffX = toX - fromX;\r
 245   int diffY = toY - fromY;\r
 246   return (float)sqrt((double)(diffX * diffX + diffY * diffY));\r
 247 }\r
 248 \r
 249 Ref<AlignmentPattern> Detector::findAlignmentInRegion(float overallEstModuleSize, int estAlignmentX, int estAlignmentY,\r
 250     float allowanceFactor) {\r
 251   // Look for an alignment pattern (3 modules in size) around where it\r
 252   // should be\r
 253   int allowance = (int)(allowanceFactor * overallEstModuleSize);\r
 254   int alignmentAreaLeftX = max(0, estAlignmentX - allowance);\r
 255   int alignmentAreaRightX = min((int)(image_->getWidth() - 1), estAlignmentX + allowance);\r
 256   int alignmentAreaTopY = max(0, estAlignmentY - allowance);\r
 257   int alignmentAreaBottomY = min((int)(image_->getHeight() - 1), estAlignmentY + allowance);\r
 258 \r
 259   AlignmentPatternFinder alignmentFinder(image_, alignmentAreaLeftX, alignmentAreaTopY, alignmentAreaRightX\r
 260                                          - alignmentAreaLeftX, alignmentAreaBottomY - alignmentAreaTopY, overallEstModuleSize);\r
 261   return alignmentFinder.find();\r
 262 }\r
 263 \r
 264 }\r
 265 }\r