symbian/QQrDecoder/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