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