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