core/src/com/google/zxing/qrcode/detector/Detector.java

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