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