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