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     int otherToX = fromX - (toX - fromX);
 262     if (otherToX < 0) {
 263       // "to" should the be the first value not included, so, the first value off
 264       // the edge is -1
 265       otherToX = -1;
 266     } else if (otherToX > image.getWidth()) {
 267       otherToX = image.getWidth();
 268     }
 269     int otherToY = fromY - (toY - fromY);
 270     if (otherToY < 0) {
 271       otherToY = -1;
 272     } else if (otherToY > image.getHeight()) {
 273       otherToY = image.getHeight();
 274     }
 275     result += sizeOfBlackWhiteBlackRun(fromX, fromY, otherToX, otherToY);
 276     return result - 1.0f; // -1 because we counted the middle pixel twice
 277   }
 278
 279   /**
 280    * <p>This method traces a line from a point in the image, in the direction towards another point.
 281    * It begins in a black region, and keeps going until it finds white, then black, then white again.
 282    * It reports the distance from the start to this point.</p>
 283    *
 284    * <p>This is used when figuring out how wide a finder pattern is, when the finder pattern
 285    * may be skewed or rotated.</p>
 286    */
 287   private float sizeOfBlackWhiteBlackRun(int fromX, int fromY, int toX, int toY) {
 288     // Mild variant of Bresenham's algorithm;
 289     // see http://en.wikipedia.org/wiki/Bresenham's_line_algorithm
 290     boolean steep = Math.abs(toY - fromY) > Math.abs(toX - fromX);
 291     if (steep) {
 292       int temp = fromX;
 293       fromX = fromY;
 294       fromY = temp;
 295       temp = toX;
 296       toX = toY;
 297       toY = temp;
 298     }
 299
 300     int dx = Math.abs(toX - fromX);
 301     int dy = Math.abs(toY - fromY);
 302     int error = -dx >> 1;
 303     int ystep = fromY < toY ? 1 : -1;
 304     int xstep = fromX < toX ? 1 : -1;
 305     int state = 0; // In black pixels, looking for white, first or second time
 306     for (int x = fromX, y = fromY; x != toX; x += xstep) {
 307
 308       int realX = steep ? y : x;
 309       int realY = steep ? x : y;
 310       if (state == 1) { // In white pixels, looking for black
 311         if (image.get(realX, realY)) {
 312           state++;
 313         }
 314       } else {
 315         if (!image.get(realX, realY)) {
 316           state++;
 317         }
 318       }
 319
 320       if (state == 3) { // Found black, white, black, and stumbled back onto white; done
 321         int diffX = x - fromX;
 322         int diffY = y - fromY;
 323         return (float) Math.sqrt((double) (diffX * diffX + diffY * diffY));
 324       }
 325       error += dy;
 326       if (error > 0) {
 327         y += ystep;
 328         error -= dx;
 329         if (y == toY) {
 330           break;
 331         }
 332       }
 333     }
 334     int diffX = toX - fromX;
 335     int diffY = toY - fromY;
 336     return (float) Math.sqrt((double) (diffX * diffX + diffY * diffY));
 337   }
 338
 339   /**
 340    * <p>Attempts to locate an alignment pattern in a limited region of the image, which is
 341    * guessed to contain it. This method uses {@link AlignmentPattern}.</p>
 342    *
 343    * @param overallEstModuleSize estimated module size so far
 344    * @param estAlignmentX x coordinate of center of area probably containing alignment pattern
 345    * @param estAlignmentY y coordinate of above
 346    * @param allowanceFactor number of pixels in all directions to search from the center
 347    * @return {@link AlignmentPattern} if found, or null otherwise
 348    * @throws ReaderException if an unexpected error occurs during detection
 349    */
 350   protected AlignmentPattern findAlignmentInRegion(float overallEstModuleSize,
 351                                                    int estAlignmentX,
 352                                                    int estAlignmentY,
 353                                                    float allowanceFactor)
 354       throws ReaderException {
 355     // Look for an alignment pattern (3 modules in size) around where it
 356     // should be
 357     int allowance = (int) (allowanceFactor * overallEstModuleSize);
 358     int alignmentAreaLeftX = Math.max(0, estAlignmentX - allowance);
 359     int alignmentAreaRightX = Math.min(image.getWidth() - 1, estAlignmentX + allowance);
 360     if (alignmentAreaRightX - alignmentAreaLeftX < overallEstModuleSize * 3) {
 361       throw ReaderException.getInstance();
 362     }
 363
 364     int alignmentAreaTopY = Math.max(0, estAlignmentY - allowance);
 365     int alignmentAreaBottomY = Math.min(image.getHeight() - 1, estAlignmentY + allowance);
 366
 367     AlignmentPatternFinder alignmentFinder =
 368         new AlignmentPatternFinder(
 369             image,
 370             alignmentAreaLeftX,
 371             alignmentAreaTopY,
 372             alignmentAreaRightX - alignmentAreaLeftX,
 373             alignmentAreaBottomY - alignmentAreaTopY,
 374             overallEstModuleSize,
 375             resultPointCallback);
 376     return alignmentFinder.find();
 377   }
 378
 379   /**
 380    * Ends up being a bit faster than Math.round(). This merely rounds its argument to the nearest int,
 381    * where x.5 rounds up.
 382    */
 383   private static int round(float d) {
 384     return (int) (d + 0.5f);
 385   }
 386 }