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     // Guess where a "bottom right" finder pattern would have been
  66     float bottomRightX = topRight.getX() - topLeft.getX() + bottomLeft.getX();
  67     float bottomRightY = topRight.getY() - topLeft.getY() + bottomLeft.getY();
  68
  69     AlignmentPattern alignmentPattern = null;
  70     // Anything above version 1 has an alignment pattern
  71     if (provisionalVersion.getAlignmentPatternCenters().length > 0) {
  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     float result = sizeOfBlackWhiteBlackRun(fromX, fromY, toX, toY);
 176     result += sizeOfBlackWhiteBlackRun(fromX, fromY, fromX - (toX - fromX), fromY - (toY - fromY));
 177     return result - 1.0f; // -1 because we counted the middle pixel twice
 178   }
 179
 180   /**
 181    * <p>This method traces a line from a point in the image, in the direction towards another point.
 182    * It begins in a black region, and keeps going until it finds white, then black, then white again.
 183    * It reports the distance from the start to this point.</p>
 184    *
 185    * <p>This is used when figuring out how wide a finder pattern is, when the finder pattern
 186    * may be skewed or rotated.</p>
 187    */
 188   private float sizeOfBlackWhiteBlackRun(int fromX, int fromY, int toX, int toY) {
 189     // Mild variant of Bresenham's algorithm;
 190     // see http://en.wikipedia.org/wiki/Bresenham's_line_algorithm
 191     boolean steep = Math.abs(toY - fromY) > Math.abs(toX - fromX);
 192     if (steep) {
 193       int temp = fromX;
 194       fromX = fromY;
 195       fromY = temp;
 196       temp = toX;
 197       toX = toY;
 198       toY = temp;
 199     }
 200
 201     int dx = Math.abs(toX - fromX);
 202     int dy = Math.abs(toY - fromY);
 203     int error = -dx >> 1;
 204     int ystep = fromY < toY ? 1 : -1;
 205     int xstep = fromX < toX ? 1 : -1;
 206     int state = 0; // In black pixels, looking for white, first or second time
 207     for (int x = fromX, y = fromY; x != toX; x += xstep) {
 208
 209       int realX = steep ? y : x;
 210       int realY = steep ? x : y;
 211       if (state == 1) { // In white pixels, looking for black
 212         if (image.isBlack(realX, realY)) {
 213           state++;
 214         }
 215       } else {
 216         if (!image.isBlack(realX, realY)) {
 217           state++;
 218         }
 219       }
 220
 221       if (state == 3) { // Found black, white, black, and stumbled back onto white; done
 222         int diffX = x - fromX;
 223         int diffY = y - fromY;
 224         return (float) Math.sqrt((double) (diffX * diffX + diffY * diffY));
 225       }
 226       error += dy;
 227       if (error > 0) {
 228         y += ystep;
 229         error -= dx;
 230       }
 231     }
 232     // Hmm, couldn't find all of what we wanted -- don't know
 233     return Float.NaN;
 234   }
 235
 236   /**
 237    * <p>Attempts to locate an alignment pattern in a limited region of the image, which is
 238    * guessed to contain it. This method uses {@link AlignmentPattern}.</p>
 239    *
 240    * @param overallEstModuleSize estimated module size so far
 241    * @param estAlignmentX x coordinate of center of area probably containing alignment pattern
 242    * @param estAlignmentY y coordinate of above
 243    * @param allowanceFactor number of pixels in all directons to search from the center
 244    * @return {@link AlignmentPattern} if found, or null otherwise
 245    * @throws ReaderException if an unexpected error occurs during detection
 246    */
 247   private AlignmentPattern findAlignmentInRegion(float overallEstModuleSize,
 248                                                  int estAlignmentX,
 249                                                  int estAlignmentY,
 250                                                  float allowanceFactor)
 251       throws ReaderException {
 252     // Look for an alignment pattern (3 modules in size) around where it
 253     // should be
 254     int allowance = (int) (allowanceFactor * overallEstModuleSize);
 255     int alignmentAreaLeftX = Math.max(0, estAlignmentX - allowance);
 256     int alignmentAreaRightX = Math.min(image.getWidth() - 1, estAlignmentX + allowance);
 257     int alignmentAreaTopY = Math.max(0, estAlignmentY - allowance);
 258     int alignmentAreaBottomY = Math.min(image.getHeight() - 1, estAlignmentY + allowance);
 259
 260     AlignmentPatternFinder alignmentFinder =
 261         new AlignmentPatternFinder(
 262             image,
 263             alignmentAreaLeftX,
 264             alignmentAreaTopY,
 265             alignmentAreaRightX - alignmentAreaLeftX,
 266             alignmentAreaBottomY - alignmentAreaTopY,
 267             overallEstModuleSize);
 268     return alignmentFinder.find();
 269   }
 270
 271   /**
 272    * Ends up being a bit faster than Math.round(). This merely rounds its argument to the nearest int,
 273    * where x.5 rounds up.
 274    */
 275   private static int round(float d) {
 276     return (int) (d + 0.5f);
 277   }
 278
 279 }