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