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