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