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