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