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