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 class Detector {
  37
  38   private final MonochromeBitmapSource image;
  39
  40   public Detector(MonochromeBitmapSource image) {
  41     this.image = image;
  42   }
  43
  44   protected MonochromeBitmapSource getImage() {
  45     return image;
  46   }
  47
  48   /**
  49    * <p>Detects a QR Code in an image, simply.</p>
  50    *
  51    * @return {@link DetectorResult} encapsulating results of detecting a QR Code
  52    * @throws ReaderException if no QR Code can be found
  53    */
  54   public DetectorResult detect() throws ReaderException {
  55     return detect(null);
  56   }
  57
  58   /**
  59    * <p>Detects a QR Code in an image, simply.</p>
  60    *
  61    * @param hints optional hints to detector
  62    * @return {@link DetectorResult} encapsulating results of detecting a QR Code
  63    * @throws ReaderException if no QR Code can be found
  64    */
  65   public DetectorResult detect(Hashtable hints) throws ReaderException {
  66
  67     MonochromeBitmapSource image = this.image;
  68     if (!BlackPointEstimationMethod.TWO_D_SAMPLING.equals(image.getLastEstimationMethod())) {
  69       image.estimateBlackPoint(BlackPointEstimationMethod.TWO_D_SAMPLING, 0);
  70     }
  71
  72     FinderPatternFinder finder = new FinderPatternFinder(image);
  73     FinderPatternInfo info = finder.find(hints);
  74
  75     return processFinderPatternInfo(info);
  76   }
  77
  78   protected DetectorResult processFinderPatternInfo(FinderPatternInfo info) throws ReaderException {
  79
  80     FinderPattern topLeft = info.getTopLeft();
  81     FinderPattern topRight = info.getTopRight();
  82     FinderPattern bottomLeft = info.getBottomLeft();
  83
  84     float moduleSize = calculateModuleSize(topLeft, topRight, bottomLeft);
  85     if (moduleSize < 1.0f) {
  86       throw ReaderException.getInstance();
  87     }
  88     int dimension = computeDimension(topLeft, topRight, bottomLeft, moduleSize);
  89     Version provisionalVersion = Version.getProvisionalVersionForDimension(dimension);
  90     int modulesBetweenFPCenters = provisionalVersion.getDimensionForVersion() - 7;
  91
  92     AlignmentPattern alignmentPattern = null;
  93     // Anything above version 1 has an alignment pattern
  94     if (provisionalVersion.getAlignmentPatternCenters().length > 0) {
  95
  96       // Guess where a "bottom right" finder pattern would have been
  97       float bottomRightX = topRight.getX() - topLeft.getX() + bottomLeft.getX();
  98       float bottomRightY = topRight.getY() - topLeft.getY() + bottomLeft.getY();
  99
 100       // Estimate that alignment pattern is closer by 3 modules
 101       // from "bottom right" to known top left location
 102       float correctionToTopLeft = 1.0f - 3.0f / (float) modulesBetweenFPCenters;
 103       int estAlignmentX = (int) (topLeft.getX() + correctionToTopLeft * (bottomRightX - topLeft.getX()));
 104       int estAlignmentY = (int) (topLeft.getY() + correctionToTopLeft * (bottomRightY - topLeft.getY()));
 105
 106       // Kind of arbitrary -- expand search radius before giving up
 107       for (int i = 4; i <= 16; i <<= 1) {
 108         try {
 109           alignmentPattern = findAlignmentInRegion(moduleSize,
 110               estAlignmentX,
 111               estAlignmentY,
 112               (float) i);
 113           break;
 114         } catch (ReaderException re) {
 115           // try next round
 116         }
 117       }
 118       // If we didn't find alignment pattern... well try anyway without it
 119     }
 120
 121     BitMatrix bits = sampleGrid(image, topLeft, topRight, bottomLeft, alignmentPattern, dimension);
 122
 123     ResultPoint[] points;
 124     if (alignmentPattern == null) {
 125       points = new ResultPoint[]{bottomLeft, topLeft, topRight};
 126     } else {
 127       points = new ResultPoint[]{bottomLeft, topLeft, topRight, alignmentPattern};
 128     }
 129     return new DetectorResult(bits, points);
 130   }
 131
 132   private static BitMatrix sampleGrid(MonochromeBitmapSource image,
 133                                       ResultPoint topLeft,
 134                                       ResultPoint topRight,
 135                                       ResultPoint bottomLeft,
 136                                       ResultPoint alignmentPattern,
 137                                       int dimension) throws ReaderException {
 138     float dimMinusThree = (float) dimension - 3.5f;
 139     float bottomRightX;
 140     float bottomRightY;
 141     float sourceBottomRightX;
 142     float sourceBottomRightY;
 143     if (alignmentPattern != null) {
 144       bottomRightX = alignmentPattern.getX();
 145       bottomRightY = alignmentPattern.getY();
 146       sourceBottomRightX = sourceBottomRightY = dimMinusThree - 3.0f;
 147     } else {
 148       // Don't have an alignment pattern, just make up the bottom-right point
 149       bottomRightX = (topRight.getX() - topLeft.getX()) + bottomLeft.getX();
 150       bottomRightY = (topRight.getY() - topLeft.getY()) + bottomLeft.getY();
 151       sourceBottomRightX = sourceBottomRightY = dimMinusThree;
 152     }
 153
 154     GridSampler sampler = GridSampler.getInstance();
 155     return sampler.sampleGrid(
 156         image,
 157         dimension,
 158         3.5f,
 159         3.5f,
 160         dimMinusThree,
 161         3.5f,
 162         sourceBottomRightX,
 163         sourceBottomRightY,
 164         3.5f,
 165         dimMinusThree,
 166         topLeft.getX(),
 167         topLeft.getY(),
 168         topRight.getX(),
 169         topRight.getY(),
 170         bottomRightX,
 171         bottomRightY,
 172         bottomLeft.getX(),
 173         bottomLeft.getY());
 174   }
 175
 176   /**
 177    * <p>Computes the dimension (number of modules on a size) of the QR Code based on the position
 178    * of the finder patterns and estimated module size.</p>
 179    */
 180   private static int computeDimension(ResultPoint topLeft,
 181                                       ResultPoint topRight,
 182                                       ResultPoint bottomLeft,
 183                                       float moduleSize) throws ReaderException {
 184     int tltrCentersDimension = round(ResultPoint.distance(topLeft, topRight) / moduleSize);
 185     int tlblCentersDimension = round(ResultPoint.distance(topLeft, bottomLeft) / moduleSize);
 186     int dimension = ((tltrCentersDimension + tlblCentersDimension) >> 1) + 7;
 187     switch (dimension & 0x03) { // mod 4
 188       case 0:
 189         dimension++;
 190         break;
 191         // 1? do nothing
 192       case 2:
 193         dimension--;
 194         break;
 195       case 3:
 196         throw ReaderException.getInstance();
 197     }
 198     return dimension;
 199   }
 200
 201   /**
 202    * <p>Computes an average estimated module size based on estimated derived from the positions
 203    * of the three finder patterns.</p>
 204    */
 205   private float calculateModuleSize(ResultPoint topLeft, ResultPoint topRight, 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.isBlack(realX, realY)) {
 297           state++;
 298         }
 299       } else {
 300         if (!image.isBlack(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 directons 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     return alignmentFinder.find();
 358   }
 359
 360   /**
 361    * Ends up being a bit faster than Math.round(). This merely rounds its argument to the nearest int,
 362    * where x.5 rounds up.
 363    */
 364   private static int round(float d) {
 365     return (int) (d + 0.5f);
 366   }
 367
 368 }