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