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  * @author srowen@google.com (Sean Owen)
  27  */
  28 public final class Detector {
  29
  30   private final MonochromeBitmapSource image;
  31
  32   public Detector(MonochromeBitmapSource image) {
  33     this.image = image;
  34   }
  35
  36   public DetectorResult detect() throws ReaderException {
  37
  38     MonochromeBitmapSource image = this.image;
  39
  40     FinderPatternFinder finder = new FinderPatternFinder(image);
  41     FinderPatternInfo info = finder.find();
  42
  43     FinderPattern topLeft = info.getTopLeft();
  44     FinderPattern topRight = info.getTopRight();
  45     FinderPattern bottomLeft = info.getBottomLeft();
  46
  47     float moduleSize = calculateModuleSize(topLeft, topRight, bottomLeft);
  48     int dimension = computeDimension(topLeft, topRight, bottomLeft, moduleSize);
  49     Version provisionalVersion = Version.getProvisionalVersionForDimension(dimension);
  50     int modulesBetweenFPCenters = provisionalVersion.getDimensionForVersion() - 7;
  51
  52     // Guess where a "bottom right" finder pattern would have been
  53     float bottomRightX = topRight.getX() - topLeft.getX() + bottomLeft.getX();
  54     float bottomRightY = topRight.getY() - topLeft.getY() + bottomLeft.getY();
  55
  56     AlignmentPattern alignmentPattern = null;
  57     // Anything above version 1 has an alignment pattern
  58     if (provisionalVersion.getAlignmentPatternCenters().length > 0) {
  59
  60       // Estimate that alignment pattern is closer by 3 modules
  61       // from "bottom right" to known top left location
  62       float correctionToTopLeft = 1.0f - 3.0f / (float) modulesBetweenFPCenters;
  63       int estAlignmentX = (int) (topLeft.getX() + correctionToTopLeft * (bottomRightX - topLeft.getX()));
  64       int estAlignmentY = (int) (topLeft.getY() + correctionToTopLeft * (bottomRightY - topLeft.getY()));
  65
  66       // Kind of arbitrary -- expand search radius before giving up
  67       for (int i = 4; i <= 16; i <<= 1) {
  68         try {
  69           alignmentPattern = findAlignmentInRegion(moduleSize,
  70               estAlignmentX,
  71               estAlignmentY,
  72               (float) i);
  73           break;
  74         } catch (ReaderException de) {
  75           // try next round
  76         }
  77       }
  78       if (alignmentPattern == null) {
  79         throw new ReaderException("Could not find alignment pattern");
  80       }
  81
  82     }
  83
  84     GridSampler sampler = GridSampler.getInstance();
  85     BitMatrix bits = sampler.sampleGrid(image,
  86         topLeft,
  87         topRight,
  88         bottomLeft,
  89         alignmentPattern,
  90         dimension);
  91
  92     /*
  93     try {
  94       BufferedImage outImage =
  95           new BufferedImage(dimension,
  96                             dimension,
  97                             BufferedImage.TYPE_BYTE_BINARY);
  98       for (int i = 0; i < dimension; i++) {
  99         for (int j = 0; j < dimension; j++) {
 100           if (bits.get(i, j)) {
 101             outImage.setRGB(j, i, 0xFF000000);
 102           } else {
 103             outImage.setRGB(j, i, 0xFFFFFFFF);
 104           }
 105         }
 106       }
 107       ImageIO.write(outImage, "PNG",
 108           new File("/home/srowen/out.png"));
 109     } catch (IOException ioe) {
 110       ioe.printStackTrace();
 111     }
 112      */
 113
 114     ResultPoint[] points;
 115     if (alignmentPattern == null) {
 116       points = new ResultPoint[] { bottomLeft, topLeft, topRight };
 117     } else {
 118       points = new ResultPoint[] { bottomLeft, topLeft, topRight, alignmentPattern };
 119     }
 120     return new DetectorResult(bits, points);
 121   }
 122
 123   private static int computeDimension(ResultPoint topLeft,
 124                                       ResultPoint topRight,
 125                                       ResultPoint bottomLeft,
 126                                       float moduleSize)
 127       throws ReaderException {
 128     int tltrCentersDimension =
 129         round(FinderPatternFinder.distance(topLeft, topRight) / moduleSize);
 130     int tlblCentersDimension =
 131         round(FinderPatternFinder.distance(topLeft, bottomLeft) / moduleSize);
 132     int dimension = ((tltrCentersDimension + tlblCentersDimension) >> 1) + 7;
 133     switch (dimension & 0x03) { // mod 4
 134       case 0:
 135         dimension++;
 136         break;
 137         // 1? do nothing
 138       case 2:
 139         dimension--;
 140         break;
 141       case 3:
 142         throw new ReaderException("Bad dimension: " + dimension);
 143     }
 144     return dimension;
 145   }
 146
 147   private float calculateModuleSize(ResultPoint topLeft,
 148                                     ResultPoint topRight,
 149                                     ResultPoint bottomLeft) {
 150     // Take the average
 151     return (calculateModuleSizeOneWay(topLeft, topRight) +
 152             calculateModuleSizeOneWay(topLeft, bottomLeft)) / 2.0f;
 153   }
 154
 155   private float calculateModuleSizeOneWay(ResultPoint pattern,
 156                                           ResultPoint otherPattern) {
 157     float moduleSizeEst1 = sizeOfBlackWhiteBlackRunBothWays((int) pattern.getX(),
 158                                                             (int) pattern.getY(),
 159                                                             (int) otherPattern.getX(),
 160                                                             (int) otherPattern.getY());
 161     float moduleSizeEst2 = sizeOfBlackWhiteBlackRunBothWays((int) otherPattern.getX(),
 162                                                             (int) otherPattern.getY(),
 163                                                             (int) pattern.getX(),
 164                                                             (int) pattern.getY());
 165     if (Float.isNaN(moduleSizeEst1)) {
 166       return moduleSizeEst2;
 167     }
 168     if (Float.isNaN(moduleSizeEst2)) {
 169       return moduleSizeEst1;
 170     }
 171     // Average them, and divide by 7 since we've counted the width of 3 black modules,
 172     // and 1 white and 1 black module on either side. Ergo, divide sum by 14.
 173     return (moduleSizeEst1 + moduleSizeEst2) / 14.0f;
 174   }
 175
 176   private float sizeOfBlackWhiteBlackRunBothWays(int fromX, int fromY, int toX, int toY) {
 177     float result = sizeOfBlackWhiteBlackRun(fromX, fromY, toX, toY);
 178     result += sizeOfBlackWhiteBlackRun(fromX, fromY, fromX - (toX - fromX), fromY - (toY - fromY));
 179     return result - 1.0f; // -1 because we counted the middle pixel twice
 180   }
 181
 182   private float sizeOfBlackWhiteBlackRun(int fromX, int fromY, int toX, int toY) {
 183     // Mild variant of Bresenham's algorithm;
 184     // see http://en.wikipedia.org/wiki/Bresenham's_line_algorithm
 185     boolean steep = Math.abs(toY - fromY) > Math.abs(toX - fromX);
 186     if (steep) {
 187       int temp = fromX;
 188       fromX = fromY;
 189       fromY = temp;
 190       temp = toX;
 191       toX = toY;
 192       toY = temp;
 193     }
 194
 195     int dx = Math.abs(toX - fromX);
 196     int dy = Math.abs(toY - fromY);
 197     int error = -dx >> 1;
 198     int ystep = fromY < toY ? 1 : -1;
 199     int xstep = fromX < toX ? 1 : -1;
 200     int state = 0; // In black pixels, looking for white, first or second time
 201     for (int x = fromX, y = fromY; x != toX; x += xstep) {
 202
 203       int realX = steep ? y : x;
 204       int realY = steep ? x : y;
 205       if (state == 1) { // In white pixels, looking for black
 206         if (image.isBlack(realX, realY)) {
 207           state++;
 208         }
 209       } else {
 210         if (!image.isBlack(realX, realY)) {
 211           state++;
 212         }
 213       }
 214
 215       if (state == 3) { // Found black, white, black, and stumbled back onto white; done
 216         int diffX = x - fromX;
 217         int diffY = y - fromY;
 218         return (float) Math.sqrt((double) (diffX * diffX + diffY * diffY));
 219       }
 220       error += dy;
 221       if (error > 0) {
 222         y += ystep;
 223         error -= dx;
 224       }
 225     }
 226     // Hmm, couldn't find all of what we wanted -- don't know
 227     return Float.NaN;
 228   }
 229
 230   private AlignmentPattern findAlignmentInRegion(float overallEstModuleSize,
 231                                                  int estAlignmentX,
 232                                                  int estAlignmentY,
 233                                                  float allowanceFactor)
 234       throws ReaderException {
 235     // Look for an alignment pattern (3 modules in size) around where it
 236     // should be
 237     int allowance = (int) (allowanceFactor * overallEstModuleSize);
 238     int alignmentAreaLeftX = Math.max(0, estAlignmentX - allowance);
 239     int alignmentAreaRightX = Math.min(image.getWidth() - 1,
 240         estAlignmentX + allowance);
 241     int alignmentAreaTopY = Math.max(0, estAlignmentY - allowance);
 242     int alignmentAreaBottomY = Math.min(image.getHeight() - 1,
 243         estAlignmentY + allowance);
 244
 245     AlignmentPatternFinder alignmentFinder =
 246         new AlignmentPatternFinder(
 247             image,
 248             alignmentAreaLeftX,
 249             alignmentAreaTopY,
 250             alignmentAreaRightX - alignmentAreaLeftX,
 251             alignmentAreaBottomY - alignmentAreaTopY,
 252             overallEstModuleSize);
 253     return alignmentFinder.find();
 254   }
 255
 256   /**
 257    * Ends up being a bit faster than Math.round()
 258    */
 259   private static int round(float d) {
 260     return (int) (d + 0.5f);
 261   }
 262
 263 }