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