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

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