core/src/com/google/zxing/qrcode/detector/Detector.java

   1 /*
   2  * Copyright 2007 Google Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 package com.google.zxing.qrcode.detector;
  18
  19 import com.google.zxing.BlackPointEstimationMethod;
  20 import com.google.zxing.MonochromeBitmapSource;
  21 import com.google.zxing.ReaderException;
  22 import com.google.zxing.ResultPoint;
  23 import com.google.zxing.common.BitMatrix;
  24 import com.google.zxing.common.DetectorResult;
  25 import com.google.zxing.common.GridSampler;
  26 import com.google.zxing.qrcode.decoder.Version;
  27
  28 /**
  29  * <p>Encapsulates logic that can detect a QR Code in an image, even if the QR Code
  30  * is rotated or skewed, or partially obscured.</p>
  31  *
  32  * @author srowen@google.com (Sean Owen)
  33  */
  34 public final class Detector {
  35
  36   private final MonochromeBitmapSource image;
  37
  38   public Detector(MonochromeBitmapSource image) {
  39     this.image = image;
  40   }
  41
  42   /**
  43    * <p>Detects a QR Code in an image, simply.</p>
  44    *
  45    * @return {@link DetectorResult} encapsulating results of detecting a QR Code
  46    * @throws ReaderException if no QR Code can be found
  47    */
  48   public DetectorResult detect() throws ReaderException {
  49
  50     MonochromeBitmapSource image = this.image;
  51     if (!BlackPointEstimationMethod.TWO_D_SAMPLING.equals(image.getLastEstimationMethod())) {
  52       image.estimateBlackPoint(BlackPointEstimationMethod.TWO_D_SAMPLING, 0);
  53     }
  54
  55     FinderPatternFinder finder = new FinderPatternFinder(image);
  56     FinderPatternInfo info = finder.find();
  57
  58     FinderPattern topLeft = info.getTopLeft();
  59     FinderPattern topRight = info.getTopRight();
  60     FinderPattern bottomLeft = info.getBottomLeft();
  61
  62     float moduleSize = calculateModuleSize(topLeft, topRight, bottomLeft);
  63     int dimension = computeDimension(topLeft, topRight, bottomLeft, moduleSize);
  64     Version provisionalVersion = Version.getProvisionalVersionForDimension(dimension);
  65     int modulesBetweenFPCenters = provisionalVersion.getDimensionForVersion() - 7;
  66
  67     AlignmentPattern alignmentPattern = null;
  68     // Anything above version 1 has an alignment pattern
  69     if (provisionalVersion.getAlignmentPatternCenters().length > 0) {
  70
  71       // Guess where a "bottom right" finder pattern would have been
  72       float bottomRightX = topRight.getX() - topLeft.getX() + bottomLeft.getX();
  73       float bottomRightY = topRight.getY() - topLeft.getY() + bottomLeft.getY();
  74
  75       // Estimate that alignment pattern is closer by 3 modules
  76       // from "bottom right" to known top left location
  77       float correctionToTopLeft = 1.0f - 3.0f / (float) modulesBetweenFPCenters;
  78       int estAlignmentX = (int) (topLeft.getX() + correctionToTopLeft * (bottomRightX - topLeft.getX()));
  79       int estAlignmentY = (int) (topLeft.getY() + correctionToTopLeft * (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         }
  92       }
  93       if (alignmentPattern == null) {
  94         throw new ReaderException("Could not find alignment pattern");
  95       }
  96
  97     }
  98
  99     BitMatrix bits = sampleGrid(image, topLeft, topRight, bottomLeft, alignmentPattern, dimension);
 100
 101     ResultPoint[] points;
 102     if (alignmentPattern == null) {
 103       points = new ResultPoint[]{bottomLeft, topLeft, topRight};
 104     } else {
 105       points = new ResultPoint[]{bottomLeft, topLeft, topRight, alignmentPattern};
 106     }
 107     return new DetectorResult(bits, points);
 108   }
 109
 110   private static BitMatrix sampleGrid(MonochromeBitmapSource image,
 111                                       ResultPoint topLeft,
 112                                       ResultPoint topRight,
 113                                       ResultPoint bottomLeft,
 114                                       ResultPoint alignmentPattern,
 115                                       int dimension) throws ReaderException {
 116     float dimMinusThree = (float) dimension - 3.5f;
 117     float bottomRightX;
 118     float bottomRightY;
 119     float sourceBottomRightX;
 120     float sourceBottomRightY;
 121     if (alignmentPattern != null) {
 122       bottomRightX = alignmentPattern.getX();
 123       bottomRightY = alignmentPattern.getY();
 124       sourceBottomRightX = sourceBottomRightY = dimMinusThree - 3.0f;
 125     } else {
 126       // Don't have an alignment pattern, just make up the bottom-right point
 127       bottomRightX = (topRight.getX() - topLeft.getX()) + bottomLeft.getX();
 128       bottomRightY = (topRight.getY() - topLeft.getY()) + bottomLeft.getY();
 129       sourceBottomRightX = sourceBottomRightY = dimMinusThree;
 130     }
 131
 132     GridSampler sampler = GridSampler.getInstance();
 133     return sampler.sampleGrid(
 134         image,
 135         dimension,
 136         3.5f,
 137         3.5f,
 138         dimMinusThree,
 139         3.5f,
 140         sourceBottomRightX,
 141         sourceBottomRightY,
 142         3.5f,
 143         dimMinusThree,
 144         topLeft.getX(),
 145         topLeft.getY(),
 146         topRight.getX(),
 147         topRight.getY(),
 148         bottomRightX,
 149         bottomRightY,
 150         bottomLeft.getX(),
 151         bottomLeft.getY());
 152   }
 153
 154   /**
 155    * <p>Computes the dimension (number of modules on a size) of the QR Code based on the position
 156    * of the finder patterns and estimated module size.</p>
 157    */
 158   private static int computeDimension(ResultPoint topLeft,
 159                                       ResultPoint topRight,
 160                                       ResultPoint bottomLeft,
 161                                       float moduleSize) throws ReaderException {
 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         throw new ReaderException("Bad dimension: " + dimension);
 175     }
 176     return dimension;
 177   }
 178
 179   /**
 180    * <p>Computes an average estimated module size based on estimated derived from the positions
 181    * of the three finder patterns.</p>
 182    */
 183   private float calculateModuleSize(ResultPoint topLeft, ResultPoint topRight, ResultPoint bottomLeft) {
 184     // Take the average
 185     return (calculateModuleSizeOneWay(topLeft, topRight) +
 186         calculateModuleSizeOneWay(topLeft, bottomLeft)) / 2.0f;
 187   }
 188
 189   /**
 190    * <p>Estimates module size based on two finder patterns -- it uses
 191    * {@link #sizeOfBlackWhiteBlackRunBothWays(int, int, int, int)} to figure the
 192    * width of each, measuring along the axis between their centers.</p>
 193    */
 194   private float calculateModuleSizeOneWay(ResultPoint pattern, ResultPoint otherPattern) {
 195     float moduleSizeEst1 = sizeOfBlackWhiteBlackRunBothWays((int) pattern.getX(),
 196         (int) pattern.getY(),
 197         (int) otherPattern.getX(),
 198         (int) otherPattern.getY());
 199     float moduleSizeEst2 = sizeOfBlackWhiteBlackRunBothWays((int) otherPattern.getX(),
 200         (int) otherPattern.getY(),
 201         (int) pattern.getX(),
 202         (int) pattern.getY());
 203     if (Float.isNaN(moduleSizeEst1)) {
 204       return moduleSizeEst2;
 205     }
 206     if (Float.isNaN(moduleSizeEst2)) {
 207       return moduleSizeEst1;
 208     }
 209     // Average them, and divide by 7 since we've counted the width of 3 black modules,
 210     // and 1 white and 1 black module on either side. Ergo, divide sum by 14.
 211     return (moduleSizeEst1 + moduleSizeEst2) / 14.0f;
 212   }
 213
 214   /**
 215    * See {@link #sizeOfBlackWhiteBlackRun(int, int, int, int)}; computes the total width of
 216    * a finder pattern by looking for a black-white-black run from the center in the direction
 217    * of another point (another finder pattern center), and in the opposite direction too.</p>
 218    */
 219   private float sizeOfBlackWhiteBlackRunBothWays(int fromX, int fromY, int toX, int toY) {
 220
 221     float result = sizeOfBlackWhiteBlackRun(fromX, fromY, toX, toY);
 222
 223     // Now count other way -- don't run off image though of course
 224     int otherToX = fromX - (toX - fromX);
 225     if (otherToX < 0) {
 226       // "to" should the be the first value not included, so, the first value off
 227       // the edge is -1
 228       otherToX = -1;
 229     } else if (otherToX >= image.getWidth()) {
 230       otherToX = image.getWidth();
 231     }
 232     int otherToY = fromY - (toY - fromY);
 233     if (otherToY < 0) {
 234       otherToY = -1;
 235     } else if (otherToY >= image.getHeight()) {
 236       otherToY = image.getHeight();
 237     }
 238     result += sizeOfBlackWhiteBlackRun(fromX, fromY, otherToX, otherToY);
 239     return result - 1.0f; // -1 because we counted the middle pixel twice
 240   }
 241
 242   /**
 243    * <p>This method traces a line from a point in the image, in the direction towards another point.
 244    * It begins in a black region, and keeps going until it finds white, then black, then white again.
 245    * It reports the distance from the start to this point.</p>
 246    *
 247    * <p>This is used when figuring out how wide a finder pattern is, when the finder pattern
 248    * may be skewed or rotated.</p>
 249    */
 250   private float sizeOfBlackWhiteBlackRun(int fromX, int fromY, int toX, int toY) {
 251     // Mild variant of Bresenham's algorithm;
 252     // see http://en.wikipedia.org/wiki/Bresenham's_line_algorithm
 253     boolean steep = Math.abs(toY - fromY) > Math.abs(toX - fromX);
 254     if (steep) {
 255       int temp = fromX;
 256       fromX = fromY;
 257       fromY = temp;
 258       temp = toX;
 259       toX = toY;
 260       toY = temp;
 261     }
 262
 263     int dx = Math.abs(toX - fromX);
 264     int dy = Math.abs(toY - fromY);
 265     int error = -dx >> 1;
 266     int ystep = fromY < toY ? 1 : -1;
 267     int xstep = fromX < toX ? 1 : -1;
 268     int state = 0; // In black pixels, looking for white, first or second time
 269     for (int x = fromX, y = fromY; x != toX; x += xstep) {
 270
 271       int realX = steep ? y : x;
 272       int realY = steep ? x : y;
 273       if (state == 1) { // In white pixels, looking for black
 274         if (image.isBlack(realX, realY)) {
 275           state++;
 276         }
 277       } else {
 278         if (!image.isBlack(realX, realY)) {
 279           state++;
 280         }
 281       }
 282
 283       if (state == 3) { // Found black, white, black, and stumbled back onto white; done
 284         int diffX = x - fromX;
 285         int diffY = y - fromY;
 286         return (float) Math.sqrt((double) (diffX * diffX + diffY * diffY));
 287       }
 288       error += dy;
 289       if (error > 0) {
 290         y += ystep;
 291         error -= dx;
 292       }
 293     }
 294     int diffX = toX - fromX;
 295     int diffY = toY - fromY;
 296     return (float) Math.sqrt((double) (diffX * diffX + diffY * diffY));
 297   }
 298
 299   /**
 300    * <p>Attempts to locate an alignment pattern in a limited region of the image, which is
 301    * guessed to contain it. This method uses {@link AlignmentPattern}.</p>
 302    *
 303    * @param overallEstModuleSize estimated module size so far
 304    * @param estAlignmentX x coordinate of center of area probably containing alignment pattern
 305    * @param estAlignmentY y coordinate of above
 306    * @param allowanceFactor number of pixels in all directons to search from the center
 307    * @return {@link AlignmentPattern} if found, or null otherwise
 308    * @throws ReaderException if an unexpected error occurs during detection
 309    */
 310   private AlignmentPattern findAlignmentInRegion(float overallEstModuleSize,
 311                                                  int estAlignmentX,
 312                                                  int estAlignmentY,
 313                                                  float allowanceFactor)
 314       throws ReaderException {
 315     // Look for an alignment pattern (3 modules in size) around where it
 316     // should be
 317     int allowance = (int) (allowanceFactor * overallEstModuleSize);
 318     int alignmentAreaLeftX = Math.max(0, estAlignmentX - allowance);
 319     int alignmentAreaRightX = Math.min(image.getWidth() - 1, estAlignmentX + allowance);
 320     int alignmentAreaTopY = Math.max(0, estAlignmentY - allowance);
 321     int alignmentAreaBottomY = Math.min(image.getHeight() - 1, estAlignmentY + allowance);
 322
 323     AlignmentPatternFinder alignmentFinder =
 324         new AlignmentPatternFinder(
 325             image,
 326             alignmentAreaLeftX,
 327             alignmentAreaTopY,
 328             alignmentAreaRightX - alignmentAreaLeftX,
 329             alignmentAreaBottomY - alignmentAreaTopY,
 330             overallEstModuleSize);
 331     return alignmentFinder.find();
 332   }
 333
 334   /**
 335    * Ends up being a bit faster than Math.round(). This merely rounds its argument to the nearest int,
 336    * where x.5 rounds up.
 337    */
 338   private static int round(float d) {
 339     return (int) (d + 0.5f);
 340   }
 341
 342 }