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