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