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.MonochromeBitmapSource;
  20 import com.google.zxing.ReaderException;
  21 import com.google.zxing.ResultPoint;
  22 import com.google.zxing.common.BitMatrix;
  23 import com.google.zxing.qrcode.decoder.Version;
  24
  25 /**
  26  * <p>Encapsulates logic that can detect a QR Code in an image, even if the QR Code
  27  * is rotated or skewed, or partially obscured.</p>
  28  *
  29  * @author srowen@google.com (Sean Owen)
  30  */
  31 public final class Detector {
  32
  33   private final MonochromeBitmapSource image;
  34
  35   public Detector(MonochromeBitmapSource image) {
  36     this.image = image;
  37   }
  38
  39     /**
  40      * <p>Detects a QR Code in an image, simply.</p>
  41      *
  42      * @return {@link DetectorResult} encapsulating results of detecting a QR Code
  43      * @throws ReaderException if no QR Code can be found
  44      */
  45   public DetectorResult detect() throws ReaderException {
  46
  47     MonochromeBitmapSource image = this.image;
  48
  49     FinderPatternFinder finder = new FinderPatternFinder(image);
  50     FinderPatternInfo info = finder.find();
  51
  52     FinderPattern topLeft = info.getTopLeft();
  53     FinderPattern topRight = info.getTopRight();
  54     FinderPattern bottomLeft = info.getBottomLeft();
  55
  56     float moduleSize = calculateModuleSize(topLeft, topRight, bottomLeft);
  57     int dimension = computeDimension(topLeft, topRight, bottomLeft, moduleSize);
  58     Version provisionalVersion = Version.getProvisionalVersionForDimension(dimension);
  59     int modulesBetweenFPCenters = provisionalVersion.getDimensionForVersion() - 7;
  60
  61     // Guess where a "bottom right" finder pattern would have been
  62     float bottomRightX = topRight.getX() - topLeft.getX() + bottomLeft.getX();
  63     float bottomRightY = topRight.getY() - topLeft.getY() + bottomLeft.getY();
  64
  65     AlignmentPattern alignmentPattern = null;
  66     // Anything above version 1 has an alignment pattern
  67     if (provisionalVersion.getAlignmentPatternCenters().length > 0) {
  68
  69       // Estimate that alignment pattern is closer by 3 modules
  70       // from "bottom right" to known top left location
  71       float correctionToTopLeft = 1.0f - 3.0f / (float) modulesBetweenFPCenters;
  72       int estAlignmentX = (int) (topLeft.getX() + correctionToTopLeft * (bottomRightX - topLeft.getX()));
  73       int estAlignmentY = (int) (topLeft.getY() + correctionToTopLeft * (bottomRightY - topLeft.getY()));
  74
  75       // Kind of arbitrary -- expand search radius before giving up
  76       for (int i = 4; i <= 16; i <<= 1) {
  77         try {
  78           alignmentPattern = findAlignmentInRegion(moduleSize,
  79               estAlignmentX,
  80               estAlignmentY,
  81               (float) i);
  82           break;
  83         } catch (ReaderException re) {
  84           // try next round
  85         }
  86       }
  87       if (alignmentPattern == null) {
  88         throw new ReaderException("Could not find alignment pattern");
  89       }
  90
  91     }
  92
  93     GridSampler sampler = GridSampler.getInstance();
  94     BitMatrix bits = sampler.sampleGrid(image, topLeft, topRight, bottomLeft, alignmentPattern, dimension);
  95
  96     /*
  97     try {
  98       BufferedImage outImage =
  99           new BufferedImage(dimension,
 100                             dimension,
 101                             BufferedImage.TYPE_BYTE_BINARY);
 102       for (int i = 0; i < dimension; i++) {
 103         for (int j = 0; j < dimension; j++) {
 104           if (bits.get(i, j)) {
 105             outImage.setRGB(j, i, 0xFF000000);
 106           } else {
 107             outImage.setRGB(j, i, 0xFFFFFFFF);
 108           }
 109         }
 110       }
 111       ImageIO.write(outImage, "PNG", new File("/tmp/out.png"));
 112     } catch (IOException ioe) {
 113       ioe.printStackTrace();
 114     }
 115      */
 116
 117     ResultPoint[] points;
 118     if (alignmentPattern == null) {
 119       points = new ResultPoint[] { bottomLeft, topLeft, topRight };
 120     } else {
 121       points = new ResultPoint[] { bottomLeft, topLeft, topRight, alignmentPattern };
 122     }
 123     return new DetectorResult(bits, points);
 124   }
 125
 126   /**
 127    * <p>Computes the dimension (number of modules on a size) of the QR Code based on the position
 128    * of the finder patterns and estimated module size.</p>
 129    */
 130   private static int computeDimension(ResultPoint topLeft,
 131                                       ResultPoint topRight,
 132                                       ResultPoint bottomLeft,
 133                                       float moduleSize) throws ReaderException {
 134     int tltrCentersDimension = round(FinderPatternFinder.distance(topLeft, topRight) / moduleSize);
 135     int tlblCentersDimension = round(FinderPatternFinder.distance(topLeft, bottomLeft) / moduleSize);
 136     int dimension = ((tltrCentersDimension + tlblCentersDimension) >> 1) + 7;
 137     switch (dimension & 0x03) { // mod 4
 138       case 0:
 139         dimension++;
 140         break;
 141       // 1? do nothing
 142       case 2:
 143         dimension--;
 144         break;
 145       case 3:
 146         throw new ReaderException("Bad dimension: " + dimension);
 147     }
 148     return dimension;
 149   }
 150
 151   /**
 152    * <p>Computes an average estimated module size based on estimated derived from the positions
 153    * of the three finder patterns.</p>
 154    */
 155   private float calculateModuleSize(ResultPoint topLeft, ResultPoint topRight, ResultPoint bottomLeft) {
 156     // Take the average
 157     return (calculateModuleSizeOneWay(topLeft, topRight) +
 158             calculateModuleSizeOneWay(topLeft, bottomLeft)) / 2.0f;
 159   }
 160
 161     /**
 162      * <p>Estimates module size based on two finder patterns -- it uses
 163      * {@link #sizeOfBlackWhiteBlackRunBothWays(int, int, int, int)} to figure the
 164      * width of each, measuring along the axis between their centers.</p>
 165      */
 166   private float calculateModuleSizeOneWay(ResultPoint pattern, ResultPoint otherPattern) {
 167     float moduleSizeEst1 = sizeOfBlackWhiteBlackRunBothWays((int) pattern.getX(),
 168                                                             (int) pattern.getY(),
 169                                                             (int) otherPattern.getX(),
 170                                                             (int) otherPattern.getY());
 171     float moduleSizeEst2 = sizeOfBlackWhiteBlackRunBothWays((int) otherPattern.getX(),
 172                                                             (int) otherPattern.getY(),
 173                                                             (int) pattern.getX(),
 174                                                             (int) pattern.getY());
 175     if (Float.isNaN(moduleSizeEst1)) {
 176       return moduleSizeEst2;
 177     }
 178     if (Float.isNaN(moduleSizeEst2)) {
 179       return moduleSizeEst1;
 180     }
 181     // Average them, and divide by 7 since we've counted the width of 3 black modules,
 182     // and 1 white and 1 black module on either side. Ergo, divide sum by 14.
 183     return (moduleSizeEst1 + moduleSizeEst2) / 14.0f;
 184   }
 185
 186   /**
 187    * See {@link #sizeOfBlackWhiteBlackRun(int, int, int, int)}; computes the total width of
 188    * a finder pattern by looking for a black-white-black run from the center in the direction
 189    * of another point (another finder pattern center), and in the opposite direction too.</p>
 190    */
 191   private float sizeOfBlackWhiteBlackRunBothWays(int fromX, int fromY, int toX, int toY) {
 192     float result = sizeOfBlackWhiteBlackRun(fromX, fromY, toX, toY);
 193     result += sizeOfBlackWhiteBlackRun(fromX, fromY, fromX - (toX - fromX), fromY - (toY - fromY));
 194     return result - 1.0f; // -1 because we counted the middle pixel twice
 195   }
 196
 197   /**
 198    * <p>This method traces a line from a point in the image, in the direction towards another point.
 199    * It begins in a black region, and keeps going until it finds white, then black, then white again.
 200    * It reports the distance from the start to this point.</p>
 201    *
 202    * <p>This is used when figuring out how wide a finder pattern is, when the finder pattern
 203    * may be skewed or rotated.</p>
 204    */
 205   private float sizeOfBlackWhiteBlackRun(int fromX, int fromY, int toX, int toY) {
 206     // Mild variant of Bresenham's algorithm;
 207     // see http://en.wikipedia.org/wiki/Bresenham's_line_algorithm
 208     boolean steep = Math.abs(toY - fromY) > Math.abs(toX - fromX);
 209     if (steep) {
 210       int temp = fromX;
 211       fromX = fromY;
 212       fromY = temp;
 213       temp = toX;
 214       toX = toY;
 215       toY = temp;
 216     }
 217
 218     int dx = Math.abs(toX - fromX);
 219     int dy = Math.abs(toY - fromY);
 220     int error = -dx >> 1;
 221     int ystep = fromY < toY ? 1 : -1;
 222     int xstep = fromX < toX ? 1 : -1;
 223     int state = 0; // In black pixels, looking for white, first or second time
 224     for (int x = fromX, y = fromY; x != toX; x += xstep) {
 225
 226       int realX = steep ? y : x;
 227       int realY = steep ? x : y;
 228       if (state == 1) { // In white pixels, looking for black
 229         if (image.isBlack(realX, realY)) {
 230           state++;
 231         }
 232       } else {
 233         if (!image.isBlack(realX, realY)) {
 234           state++;
 235         }
 236       }
 237
 238       if (state == 3) { // Found black, white, black, and stumbled back onto white; done
 239         int diffX = x - fromX;
 240         int diffY = y - fromY;
 241         return (float) Math.sqrt((double) (diffX * diffX + diffY * diffY));
 242       }
 243       error += dy;
 244       if (error > 0) {
 245         y += ystep;
 246         error -= dx;
 247       }
 248     }
 249     // Hmm, couldn't find all of what we wanted -- don't know
 250     return Float.NaN;
 251   }
 252
 253   /**
 254    * <p>Attempts to locate an alignment pattern in a limited region of the image, which is
 255    * guessed to contain it. This method uses {@link AlignmentPattern}.</p>
 256    *
 257    * @param overallEstModuleSize estimated module size so far
 258    * @param estAlignmentX x coordinate of center of area probably containing alignment pattern
 259    * @param estAlignmentY y coordinate of above
 260    * @param allowanceFactor number of pixels in all directons to search from the center
 261    * @return {@link AlignmentPattern} if found, or null otherwise
 262    * @throws ReaderException if an unexpected error occurs during detection
 263    */
 264   private AlignmentPattern findAlignmentInRegion(float overallEstModuleSize,
 265                                                  int estAlignmentX,
 266                                                  int estAlignmentY,
 267                                                  float allowanceFactor)
 268       throws ReaderException {
 269     // Look for an alignment pattern (3 modules in size) around where it
 270     // should be
 271     int allowance = (int) (allowanceFactor * overallEstModuleSize);
 272     int alignmentAreaLeftX = Math.max(0, estAlignmentX - allowance);
 273     int alignmentAreaRightX = Math.min(image.getWidth() - 1, estAlignmentX + allowance);
 274     int alignmentAreaTopY = Math.max(0, estAlignmentY - allowance);
 275     int alignmentAreaBottomY = Math.min(image.getHeight() - 1, estAlignmentY + allowance);
 276
 277     AlignmentPatternFinder alignmentFinder =
 278         new AlignmentPatternFinder(
 279             image,
 280             alignmentAreaLeftX,
 281             alignmentAreaTopY,
 282             alignmentAreaRightX - alignmentAreaLeftX,
 283             alignmentAreaBottomY - alignmentAreaTopY,
 284             overallEstModuleSize);
 285     return alignmentFinder.find();
 286   }
 287
 288   /**
 289    * Ends up being a bit faster than Math.round(). This merely rounds its argument to the nearest int,
 290    * where x.5 rounds up.
 291    */
 292   private static int round(float d) {
 293     return (int) (d + 0.5f);
 294   }
 295
 296 }