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