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