core/src/com/google/zxing/datamatrix/detector/Detector.java

   1 /*
   2  * Copyright 2008 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.datamatrix.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.BlackPointEstimationMethod;
  23 import com.google.zxing.common.BitArray;
  24 import com.google.zxing.common.BitMatrix;
  25 import com.google.zxing.common.Collections;
  26 import com.google.zxing.common.Comparator;
  27 import com.google.zxing.common.DetectorResult;
  28 import com.google.zxing.common.GenericResultPoint;
  29 import com.google.zxing.common.GridSampler;
  30
  31 import java.util.Enumeration;
  32 import java.util.Hashtable;
  33 import java.util.Vector;
  34
  35 /**
  36  * <p>Encapsulates logic that can detect a Data Matrix Code in an image, even if the Data Matrix Code
  37  * is rotated or skewed, or partially obscured.</p>
  38  *
  39  * @author srowen@google.com (Sean Owen)
  40  */
  41 public final class Detector {
  42
  43   private static final int MAX_MODULES = 32;
  44
  45   // Trick to avoid creating new Integer objects below -- a sort of crude copy of
  46   // the Integer.valueOf(int) optimization added in Java 5, not in J2ME
  47   private static final Integer[] INTEGERS =
  48       { new Integer(0), new Integer(1), new Integer(2), new Integer(3), new Integer(4) };
  49
  50   private final MonochromeBitmapSource image;
  51
  52   public Detector(MonochromeBitmapSource image) {
  53     this.image = image;
  54   }
  55
  56   /**
  57    * <p>Detects a Data Matrix Code in an image.</p>
  58    *
  59    * @return {@link DetectorResult} encapsulating results of detecting a QR Code
  60    * @throws ReaderException if no Data Matrix Code can be found
  61    */
  62   public DetectorResult detect() throws ReaderException {
  63
  64     if (!BlackPointEstimationMethod.TWO_D_SAMPLING.equals(image.getLastEstimationMethod())) {
  65       image.estimateBlackPoint(BlackPointEstimationMethod.TWO_D_SAMPLING, 0);
  66     }
  67
  68     int height = image.getHeight();
  69     int width = image.getWidth();
  70     int halfHeight = height >> 1;
  71     int halfWidth = width >> 1;
  72     int iSkip = Math.max(1, height / (MAX_MODULES << 3));
  73     int jSkip = Math.max(1, width / (MAX_MODULES << 3));
  74
  75     int minI = 0;
  76     int maxI = height;
  77     int minJ = 0;
  78     int maxJ = width;
  79     ResultPoint pointA = findCornerFromCenter(halfHeight, -iSkip, minI, maxI, halfWidth,      0, minJ, maxJ, halfWidth >> 1);
  80     minI = (int) pointA.getY() - 1;
  81     ResultPoint pointB = findCornerFromCenter(halfHeight, 0,      minI, maxI, halfWidth, -jSkip, minJ, maxJ, halfHeight >> 1);
  82     minJ = (int) pointB.getX() - 1;
  83     ResultPoint pointC = findCornerFromCenter(halfHeight, 0,      minI, maxI, halfWidth,  jSkip, minJ, maxJ, halfHeight >> 1);
  84     maxJ = (int) pointC.getX() + 1;
  85     ResultPoint pointD = findCornerFromCenter(halfHeight,  iSkip, minI, maxI, halfWidth,      0, minJ, maxJ, halfWidth >> 1);
  86     maxI = (int) pointD.getY() + 1;
  87     // Go try to find point A again with better information -- might have been off at first.
  88     pointA = findCornerFromCenter(halfHeight, -iSkip, minI, maxI, halfWidth,      0, minJ, maxJ, halfWidth >> 2);
  89
  90     // Point A and D are across the diagonal from one another,
  91     // as are B and C. Figure out which are the solid black lines
  92     // by counting transitions
  93     Vector transitions = new Vector(4);
  94     transitions.addElement(transitionsBetween(pointA, pointB));
  95     transitions.addElement(transitionsBetween(pointA, pointC));
  96     transitions.addElement(transitionsBetween(pointB, pointD));
  97     transitions.addElement(transitionsBetween(pointC, pointD));
  98     Collections.insertionSort(transitions, new ResultPointsAndTransitionsComparator());
  99
 100     // Sort by number of transitions. First two will be the two solid sides; last two
 101     // will be the two alternating black/white sides
 102     ResultPointsAndTransitions lSideOne = (ResultPointsAndTransitions) transitions.elementAt(0);
 103     ResultPointsAndTransitions lSideTwo = (ResultPointsAndTransitions) transitions.elementAt(1);
 104
 105     // Figure out which point is their intersection by tallying up the number of times we see the
 106     // endpoints in the four endpoints. One will show up twice.
 107     Hashtable pointCount = new Hashtable();
 108     increment(pointCount, lSideOne.getFrom());
 109     increment(pointCount, lSideOne.getTo());
 110     increment(pointCount, lSideTwo.getFrom());
 111     increment(pointCount, lSideTwo.getTo());
 112
 113     ResultPoint maybeTopLeft = null;
 114     ResultPoint bottomLeft = null;
 115     ResultPoint maybeBottomRight = null;
 116     Enumeration points = pointCount.keys();
 117     while (points.hasMoreElements()) {
 118       ResultPoint point = (ResultPoint) points.nextElement();
 119       Integer value = (Integer) pointCount.get(point);
 120       if (value.intValue() == 2) {
 121         bottomLeft = point; // this is definitely the bottom left, then -- end of two L sides
 122       } else {
 123         // Otherwise it's either top left or bottom right -- just assign the two arbitrarily now
 124         if (maybeTopLeft == null) {
 125           maybeTopLeft = point;
 126         } else {
 127           maybeBottomRight = point;
 128         }
 129       }
 130     }
 131
 132     if (maybeTopLeft == null || bottomLeft == null || maybeBottomRight == null) {
 133       throw new ReaderException("Could not find three corners");
 134     }
 135
 136     // Bottom left is correct but top left and bottom right might be switched
 137     ResultPoint[] corners = new ResultPoint[] { maybeTopLeft, bottomLeft, maybeBottomRight };
 138     // Use the dot product trick to sort them out
 139     GenericResultPoint.orderBestPatterns(corners);
 140
 141     // Now we know which is which:
 142     ResultPoint bottomRight = corners[0];
 143     bottomLeft = corners[1];
 144     ResultPoint topLeft = corners[2];
 145
 146     // Which point didn't we find in relation to the "L" sides? that's the top right corner
 147     ResultPoint topRight;
 148     if (!pointCount.containsKey(pointA)) {
 149       topRight = pointA;
 150     } else if (!pointCount.containsKey(pointB)) {
 151       topRight = pointB;
 152     } else if (!pointCount.containsKey(pointC)) {
 153       topRight = pointC;
 154     } else {
 155       topRight = pointD;
 156     }
 157
 158     // Next determine the dimension by tracing along the top or right side and counting black/white
 159     // transitions. Since we start inside a black module, we should see a number of transitions
 160     // equal to 1 less than the code dimension. Well, actually 2 less, because we are going to
 161     // end on a black module:
 162
 163     // The top right point is actually the corner of a module, which is one of the two black modules
 164     // adjacent to the white module at the top right. Tracing to that corner from either the top left
 165     // or bottom right should work here, but, one will be more reliable since it's traced straight
 166     // up or across, rather than at a slight angle. We use dot products to figure out which is
 167     // better to use:
 168     int dimension;
 169     if (GenericResultPoint.crossProductZ(bottomLeft, bottomRight, topRight) <
 170         GenericResultPoint.crossProductZ(topRight, topLeft, bottomLeft)) {
 171       dimension = transitionsBetween(topLeft, topRight).getTransitions();
 172     } else {
 173       dimension = transitionsBetween(bottomRight, topRight).getTransitions();
 174     }
 175     dimension += 2;
 176
 177     BitMatrix bits = sampleGrid(image, topLeft, bottomLeft, bottomRight, dimension);
 178     return new DetectorResult(bits, new ResultPoint[] {pointA, pointB, pointC, pointD});
 179   }
 180
 181   /**
 182    * Attempts to locate a corner of the barcode by scanning up, down, left or right from a center
 183    * point which should be within the barcode.
 184    *
 185    * @param centerI center's i componennt (vertical)
 186    * @param di change in i per step. If scanning up this is negative; down, positive; left or right, 0
 187    * @param minI minimum value of i to search through (meaningless when di == 0)
 188    * @param maxI maximum value of i
 189    * @param centerJ center's j component (horizontal)
 190    * @param dj same as di but change in j per step instead
 191    * @param minJ see minI
 192    * @param maxJ see minJ
 193    * @param maxWhiteRun maximum run of white pixels that can still be considered to be within
 194    *  the barcode
 195    * @return a {@link ResultPoint} encapsulating the corner that was found
 196    * @throws ReaderException if such a point cannot be found
 197    */
 198   private ResultPoint findCornerFromCenter(int centerI, int di, int minI, int maxI,
 199                                            int centerJ, int dj, int minJ, int maxJ,
 200                                            int maxWhiteRun) throws ReaderException {
 201     int[] lastRange = null;
 202     for (int i = centerI, j = centerJ;
 203          i < maxI && i >= minI && j < maxJ && j >= minJ;
 204          i += di, j += dj) {
 205       int[] range;
 206       if (dj == 0) {
 207         // horizontal slices, up and down
 208         range = blackWhiteRange(i, maxWhiteRun, minJ, maxJ, true);
 209       } else {
 210         // vertical slices, left and right
 211         range = blackWhiteRange(j, maxWhiteRun, minI, maxI, false);
 212       }
 213       if (range == null) {
 214         if (lastRange == null) {
 215           throw new ReaderException("Center of image not within barcode");
 216         }
 217         // lastRange was found
 218         if (dj == 0) {
 219           int lastI = i - di;
 220           if (lastRange[0] < centerJ) {
 221             if (lastRange[1] > centerJ) {
 222               // straddle, choose one or the other based on direction
 223               return new GenericResultPoint(di > 0 ? lastRange[0] : lastRange[1], lastI);
 224             }
 225             return new GenericResultPoint(lastRange[0], lastI);
 226           } else {
 227             return new GenericResultPoint(lastRange[1], lastI);
 228           }
 229         } else {
 230           int lastJ = j - dj;
 231           if (lastRange[0] < centerI) {
 232             if (lastRange[1] > centerI) {
 233               return new GenericResultPoint(lastJ, dj < 0 ? lastRange[0] : lastRange[1]);
 234             }
 235             return new GenericResultPoint(lastJ, lastRange[0]);
 236           } else {
 237             return new GenericResultPoint(lastJ, lastRange[1]);
 238           }
 239         }
 240       }
 241       lastRange = range;
 242     }
 243     throw new ReaderException("Couldn't find an end to barcode");
 244   }
 245
 246   /**
 247    * Increments the Integer associated with a key by one.
 248    */
 249   private static void increment(Hashtable table, ResultPoint key) {
 250     Integer value = (Integer) table.get(key);
 251     table.put(key, value == null ? INTEGERS[1] : INTEGERS[value.intValue() + 1]);
 252   }
 253
 254   /**
 255    * Computes the start and end of a region of pixels, either horizontally or vertically, that could be
 256    * part of a Data Matrix barcode.
 257    *
 258    * @param fixedDimension if scanning horizontally, this is the row (the fixed vertical location) where
 259    *  we are scanning. If scanning vertically it's the colummn, the fixed horizontal location
 260    * @param maxWhiteRun largest run of white pixels that can still be considered part of the barcode region
 261    * @param minDim minimum pixel location, horizontally or vertically, to consider
 262    * @param maxDim maximum pixel location, horizontally or vertically, to consider
 263    * @param horizontal if true, we're scanning left-right, instead of up-down
 264    * @return int[] with start and end of found range, or null if no such range is found (e.g. only white was found)
 265    */
 266   private int[] blackWhiteRange(int fixedDimension, int maxWhiteRun, int minDim, int maxDim, boolean horizontal) {
 267
 268     int center = (minDim + maxDim) / 2;
 269
 270     BitArray rowOrColumn = horizontal ? image.getBlackRow(fixedDimension, null, 0, image.getWidth())
 271                                       : image.getBlackColumn(fixedDimension, null, 0, image.getHeight());
 272
 273     // Scan left/up first
 274     int start = center;
 275     while (start >= minDim) {
 276       if (rowOrColumn.get(start)) {
 277         start--;
 278       } else {
 279         int whiteRunStart = start;
 280         do {
 281           start--;
 282         } while (start >= minDim && !rowOrColumn.get(start));
 283         int whiteRunSize = whiteRunStart - start;
 284         if (start < minDim || whiteRunSize > maxWhiteRun) {
 285           start = whiteRunStart + 1; // back up
 286           break;
 287         }
 288       }
 289     }
 290
 291     // Then try right/down
 292     int end = center;
 293     while (end < maxDim) {
 294       if (rowOrColumn.get(end)) {
 295         end++;
 296       } else {
 297         int whiteRunStart = end;
 298         do {
 299           end++;
 300         } while (end < maxDim && !rowOrColumn.get(end));
 301         int whiteRunSize = end - whiteRunStart;
 302         if (end >= maxDim || whiteRunSize > maxWhiteRun) {
 303           end = whiteRunStart - 1;
 304           break;
 305         }
 306       }
 307     }
 308
 309     if (end > start) {
 310       return new int[] { start, end };
 311     } else {
 312       return null;
 313     }
 314   }
 315
 316   private static BitMatrix sampleGrid(MonochromeBitmapSource image,
 317                                       ResultPoint topLeft,
 318                                       ResultPoint bottomLeft,
 319                                       ResultPoint bottomRight,
 320                                       int dimension) throws ReaderException {
 321
 322     // We make up the top right point for now, based on the others.
 323     // TODO: we actually found a fourth corner above and figured out which of two modules
 324     // it was the corner of. We could use that here and adjust for perspective distortion.
 325     float topRightX = (bottomRight.getX() - bottomLeft.getX()) + topLeft.getX();
 326     float topRightY = (bottomRight.getY() - bottomLeft.getY()) + topLeft.getY();
 327
 328     // Note that unlike in the QR Code sampler, we didn't find the center of modules, but the
 329     // very corners. So there is no 0.5f here; 0.0f is right.
 330     GridSampler sampler = GridSampler.getInstance();
 331     return sampler.sampleGrid(
 332         image,
 333         dimension,
 334         0.0f,
 335         0.0f,
 336         dimension,
 337         0.0f,
 338         dimension,
 339         dimension,
 340         0.0f,
 341         dimension,
 342         topLeft.getX(),
 343         topLeft.getY(),
 344         topRightX,
 345         topRightY,
 346         bottomRight.getX(),
 347         bottomRight.getY(),
 348         bottomLeft.getX(),
 349         bottomLeft.getY());
 350   }
 351
 352   /**
 353    * Counts the number of black/white transitions between two points, using something like Bresenham's algorithm.
 354    */
 355   private ResultPointsAndTransitions transitionsBetween(ResultPoint from, ResultPoint to) {
 356     // See QR Code Detector, sizeOfBlackWhiteBlackRun()
 357     int fromX = (int) from.getX();
 358     int fromY = (int) from.getY();
 359     int toX = (int) to.getX();
 360     int toY = (int) to.getY();
 361     boolean steep = Math.abs(toY - fromY) > Math.abs(toX - fromX);
 362     if (steep) {
 363       int temp = fromX;
 364       fromX = fromY;
 365       fromY = temp;
 366       temp = toX;
 367       toX = toY;
 368       toY = temp;
 369     }
 370
 371     int dx = Math.abs(toX - fromX);
 372     int dy = Math.abs(toY - fromY);
 373     int error = -dx >> 1;
 374     int ystep = fromY < toY ? 1 : -1;
 375     int xstep = fromX < toX ? 1 : -1;
 376     int transitions = 0;
 377     boolean inBlack = image.isBlack(steep ? fromY : fromX, steep ? fromX : fromY);
 378     for (int x = fromX, y = fromY; x != toX; x += xstep) {
 379       boolean isBlack = image.isBlack(steep ? y : x, steep ? x : y);
 380       if (isBlack == !inBlack) {
 381         transitions++;
 382         inBlack = isBlack;
 383       }
 384       error += dy;
 385       if (error > 0) {
 386         y += ystep;
 387         error -= dx;
 388       }
 389     }
 390     return new ResultPointsAndTransitions(from, to, transitions);
 391   }
 392
 393   /**
 394    * Simply encapsulates two points and a number of transitions between them.
 395    */
 396   private static class ResultPointsAndTransitions {
 397     private final ResultPoint from;
 398     private final ResultPoint to;
 399     private final int transitions;
 400     private ResultPointsAndTransitions(ResultPoint from, ResultPoint to, int transitions) {
 401       this.from = from;
 402       this.to = to;
 403       this.transitions = transitions;
 404     }
 405     public ResultPoint getFrom() {
 406       return from;
 407     }
 408     public ResultPoint getTo() {
 409       return to;
 410     }
 411     public int getTransitions() {
 412       return transitions;
 413     }
 414     public String toString() {
 415       return from + "/" + to + '/' + transitions;
 416     }
 417   }
 418
 419   /**
 420    * Orders ResultPointsAndTransitions by number of transitions, ascending.
 421    */
 422   private static class ResultPointsAndTransitionsComparator implements Comparator {
 423     public int compare(Object o1, Object o2) {
 424       return ((ResultPointsAndTransitions) o1).getTransitions() - ((ResultPointsAndTransitions) o2).getTransitions();
 425     }
 426   }
 427
 428 }