cpp/core/src/zxing/qrcode/detector/Detector.cpp

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