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     PerspectiveTransform transform = 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     return transform;
 182   }
 183
 184   private static BitMatrix sampleGrid(BitMatrix image,
 185                                       PerspectiveTransform transform,
 186                                       int dimension) throws NotFoundException {
 187
 188     GridSampler sampler = GridSampler.getInstance();
 189     return sampler.sampleGrid(image, dimension, transform);
 190   }
 191
 192   /**
 193    * <p>Computes the dimension (number of modules on a size) of the QR Code based on the position
 194    * of the finder patterns and estimated module size.</p>
 195    */
 196   protected static int computeDimension(ResultPoint topLeft,
 197                                         ResultPoint topRight,
 198                                         ResultPoint bottomLeft,
 199                                       float moduleSize) throws NotFoundException {
 200     int tltrCentersDimension = round(ResultPoint.distance(topLeft, topRight) / moduleSize);
 201     int tlblCentersDimension = round(ResultPoint.distance(topLeft, bottomLeft) / moduleSize);
 202     int dimension = ((tltrCentersDimension + tlblCentersDimension) >> 1) + 7;
 203     switch (dimension & 0x03) { // mod 4
 204       case 0:
 205         dimension++;
 206         break;
 207         // 1? do nothing
 208       case 2:
 209         dimension--;
 210         break;
 211       case 3:
 212         throw NotFoundException.getNotFoundInstance();
 213     }
 214     return dimension;
 215   }
 216
 217   /**
 218    * <p>Computes an average estimated module size based on estimated derived from the positions
 219    * of the three finder patterns.</p>
 220    */
 221   protected float calculateModuleSize(ResultPoint topLeft,
 222                                       ResultPoint topRight,
 223                                       ResultPoint bottomLeft) {
 224     // Take the average
 225     return (calculateModuleSizeOneWay(topLeft, topRight) +
 226         calculateModuleSizeOneWay(topLeft, bottomLeft)) / 2.0f;
 227   }
 228
 229   /**
 230    * <p>Estimates module size based on two finder patterns -- it uses
 231    * {@link #sizeOfBlackWhiteBlackRunBothWays(int, int, int, int)} to figure the
 232    * width of each, measuring along the axis between their centers.</p>
 233    */
 234   private float calculateModuleSizeOneWay(ResultPoint pattern, ResultPoint otherPattern) {
 235     float moduleSizeEst1 = sizeOfBlackWhiteBlackRunBothWays((int) pattern.getX(),
 236         (int) pattern.getY(),
 237         (int) otherPattern.getX(),
 238         (int) otherPattern.getY());
 239     float moduleSizeEst2 = sizeOfBlackWhiteBlackRunBothWays((int) otherPattern.getX(),
 240         (int) otherPattern.getY(),
 241         (int) pattern.getX(),
 242         (int) pattern.getY());
 243     if (Float.isNaN(moduleSizeEst1)) {
 244       return moduleSizeEst2 / 7.0f;
 245     }
 246     if (Float.isNaN(moduleSizeEst2)) {
 247       return moduleSizeEst1 / 7.0f;
 248     }
 249     // Average them, and divide by 7 since we've counted the width of 3 black modules,
 250     // and 1 white and 1 black module on either side. Ergo, divide sum by 14.
 251     return (moduleSizeEst1 + moduleSizeEst2) / 14.0f;
 252   }
 253
 254   /**
 255    * See {@link #sizeOfBlackWhiteBlackRun(int, int, int, int)}; computes the total width of
 256    * a finder pattern by looking for a black-white-black run from the center in the direction
 257    * of another point (another finder pattern center), and in the opposite direction too.</p>
 258    */
 259   private float sizeOfBlackWhiteBlackRunBothWays(int fromX, int fromY, int toX, int toY) {
 260
 261    float result = sizeOfBlackWhiteBlackRun(fromX, fromY, toX, toY);
 262
 263    // Now count other way -- don't run off image though of course
 264    float scale = 1.0f;
 265    int otherToX = fromX - (toX - fromX);
 266    if (otherToX < 0) {
 267      scale = (float) fromX / (float) (fromX - otherToX);
 268      otherToX = 0;
 269    } else if (otherToX > image.getWidth()) {
 270      scale = (float) (image.getWidth() - fromX) / (float) (otherToX - fromX);
 271      otherToX = image.getWidth();
 272    }
 273    int otherToY = (int) (fromY - (toY - fromY) * scale);
 274
 275    scale = 1.0f;
 276    if (otherToY < 0) {
 277      scale = (float) fromY / (float) (fromY - otherToY);
 278      otherToY = 0;
 279    } else if (otherToY > image.getHeight()) {
 280      scale = (float) (image.getHeight() - fromY) / (float) (otherToY - fromY);
 281      otherToY = image.getHeight();
 282    }
 283    otherToX = (int) (fromX + (otherToX - fromX) * scale);
 284
 285    result += sizeOfBlackWhiteBlackRun(fromX, fromY, otherToX, otherToY);
 286    return result;
 287  }
 288
 289   /**
 290    * <p>This method traces a line from a point in the image, in the direction towards another point.
 291    * It begins in a black region, and keeps going until it finds white, then black, then white again.
 292    * It reports the distance from the start to this point.</p>
 293    *
 294    * <p>This is used when figuring out how wide a finder pattern is, when the finder pattern
 295    * may be skewed or rotated.</p>
 296    */
 297   private float sizeOfBlackWhiteBlackRun(int fromX, int fromY, int toX, int toY) {
 298     // Mild variant of Bresenham's algorithm;
 299     // see http://en.wikipedia.org/wiki/Bresenham's_line_algorithm
 300     boolean steep = Math.abs(toY - fromY) > Math.abs(toX - fromX);
 301     if (steep) {
 302       int temp = fromX;
 303       fromX = fromY;
 304       fromY = temp;
 305       temp = toX;
 306       toX = toY;
 307       toY = temp;
 308     }
 309
 310     int dx = Math.abs(toX - fromX);
 311     int dy = Math.abs(toY - fromY);
 312     int error = -dx >> 1;
 313     int ystep = fromY < toY ? 1 : -1;
 314     int xstep = fromX < toX ? 1 : -1;
 315     int state = 0; // In black pixels, looking for white, first or second time
 316     for (int x = fromX, y = fromY; x != toX; x += xstep) {
 317
 318       int realX = steep ? y : x;
 319       int realY = steep ? x : y;
 320       if (state == 1) { // In white pixels, looking for black
 321         if (image.get(realX, realY)) {
 322           state++;
 323         }
 324       } else {
 325         if (!image.get(realX, realY)) {
 326           state++;
 327         }
 328       }
 329
 330       if (state == 3) { // Found black, white, black, and stumbled back onto white; done
 331         int diffX = x - fromX;
 332         int diffY = y - fromY;
 333         if (xstep < 0) {
 334             diffX++;
 335         }
 336         return (float) Math.sqrt((double) (diffX * diffX + diffY * diffY));
 337       }
 338       error += dy;
 339       if (error > 0) {
 340         if (y == toY) {
 341           break;
 342         }
 343         y += ystep;
 344         error -= dx;
 345       }
 346     }
 347     int diffX = toX - fromX;
 348     int diffY = toY - fromY;
 349     return (float) Math.sqrt((double) (diffX * diffX + diffY * diffY));
 350   }
 351
 352   /**
 353    * <p>Attempts to locate an alignment pattern in a limited region of the image, which is
 354    * guessed to contain it. This method uses {@link AlignmentPattern}.</p>
 355    *
 356    * @param overallEstModuleSize estimated module size so far
 357    * @param estAlignmentX x coordinate of center of area probably containing alignment pattern
 358    * @param estAlignmentY y coordinate of above
 359    * @param allowanceFactor number of pixels in all directions to search from the center
 360    * @return {@link AlignmentPattern} if found, or null otherwise
 361    * @throws NotFoundException if an unexpected error occurs during detection
 362    */
 363   protected AlignmentPattern findAlignmentInRegion(float overallEstModuleSize,
 364                                                    int estAlignmentX,
 365                                                    int estAlignmentY,
 366                                                    float allowanceFactor)
 367       throws NotFoundException {
 368     // Look for an alignment pattern (3 modules in size) around where it
 369     // should be
 370     int allowance = (int) (allowanceFactor * overallEstModuleSize);
 371     int alignmentAreaLeftX = Math.max(0, estAlignmentX - allowance);
 372     int alignmentAreaRightX = Math.min(image.getWidth() - 1, estAlignmentX + allowance);
 373     if (alignmentAreaRightX - alignmentAreaLeftX < overallEstModuleSize * 3) {
 374       throw NotFoundException.getNotFoundInstance();
 375     }
 376
 377     int alignmentAreaTopY = Math.max(0, estAlignmentY - allowance);
 378     int alignmentAreaBottomY = Math.min(image.getHeight() - 1, estAlignmentY + allowance);
 379
 380     AlignmentPatternFinder alignmentFinder =
 381         new AlignmentPatternFinder(
 382             image,
 383             alignmentAreaLeftX,
 384             alignmentAreaTopY,
 385             alignmentAreaRightX - alignmentAreaLeftX,
 386             alignmentAreaBottomY - alignmentAreaTopY,
 387             overallEstModuleSize,
 388             resultPointCallback);
 389     return alignmentFinder.find();
 390   }
 391
 392   /**
 393    * Ends up being a bit faster than Math.round(). This merely rounds its argument to the nearest int,
 394    * where x.5 rounds up.
 395    */
 396   private static int round(float d) {
 397     return (int) (d + 0.5f);
 398   }
 399 }