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.common.BitMatrix;
  23 import com.google.zxing.common.Collections;
  24 import com.google.zxing.common.Comparator;
  25 import com.google.zxing.common.DetectorResult;
  26 import com.google.zxing.common.GenericResultPoint;
  27 import com.google.zxing.common.GridSampler;
  28 import com.google.zxing.common.detector.MonochromeRectangleDetector;
  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 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   private final MonochromeRectangleDetector rectangleDetector;
  51
  52   public Detector(MonochromeBitmapSource image) {
  53     this.image = image;
  54     rectangleDetector = new MonochromeRectangleDetector(image);
  55   }
  56
  57   /**
  58    * <p>Detects a Data Matrix Code in an image.</p>
  59    *
  60    * @return {@link DetectorResult} encapsulating results of detecting a QR Code
  61    * @throws ReaderException if no Data Matrix Code can be found
  62    */
  63   public DetectorResult detect() throws ReaderException {
  64
  65     ResultPoint[] cornerPoints = rectangleDetector.detect();
  66     ResultPoint pointA = cornerPoints[0];
  67     ResultPoint pointB = cornerPoints[1];
  68     ResultPoint pointC = cornerPoints[2];
  69     ResultPoint pointD = cornerPoints[3];
  70
  71     // Point A and D are across the diagonal from one another,
  72     // as are B and C. Figure out which are the solid black lines
  73     // by counting transitions
  74     Vector transitions = new Vector(4);
  75     transitions.addElement(transitionsBetween(pointA, pointB));
  76     transitions.addElement(transitionsBetween(pointA, pointC));
  77     transitions.addElement(transitionsBetween(pointB, pointD));
  78     transitions.addElement(transitionsBetween(pointC, pointD));
  79     Collections.insertionSort(transitions, new ResultPointsAndTransitionsComparator());
  80
  81     // Sort by number of transitions. First two will be the two solid sides; last two
  82     // will be the two alternating black/white sides
  83     ResultPointsAndTransitions lSideOne = (ResultPointsAndTransitions) transitions.elementAt(0);
  84     ResultPointsAndTransitions lSideTwo = (ResultPointsAndTransitions) transitions.elementAt(1);
  85
  86     // Figure out which point is their intersection by tallying up the number of times we see the
  87     // endpoints in the four endpoints. One will show up twice.
  88     Hashtable pointCount = new Hashtable();
  89     increment(pointCount, lSideOne.getFrom());
  90     increment(pointCount, lSideOne.getTo());
  91     increment(pointCount, lSideTwo.getFrom());
  92     increment(pointCount, lSideTwo.getTo());
  93
  94     ResultPoint maybeTopLeft = null;
  95     ResultPoint bottomLeft = null;
  96     ResultPoint maybeBottomRight = null;
  97     Enumeration points = pointCount.keys();
  98     while (points.hasMoreElements()) {
  99       ResultPoint point = (ResultPoint) points.nextElement();
 100       Integer value = (Integer) pointCount.get(point);
 101       if (value.intValue() == 2) {
 102         bottomLeft = point; // this is definitely the bottom left, then -- end of two L sides
 103       } else {
 104         // Otherwise it's either top left or bottom right -- just assign the two arbitrarily now
 105         if (maybeTopLeft == null) {
 106           maybeTopLeft = point;
 107         } else {
 108           maybeBottomRight = point;
 109         }
 110       }
 111     }
 112
 113     if (maybeTopLeft == null || bottomLeft == null || maybeBottomRight == null) {
 114       throw ReaderException.getInstance();
 115     }
 116
 117     // Bottom left is correct but top left and bottom right might be switched
 118     ResultPoint[] corners = { maybeTopLeft, bottomLeft, maybeBottomRight };
 119     // Use the dot product trick to sort them out
 120     GenericResultPoint.orderBestPatterns(corners);
 121
 122     // Now we know which is which:
 123     ResultPoint bottomRight = corners[0];
 124     bottomLeft = corners[1];
 125     ResultPoint topLeft = corners[2];
 126
 127     // Which point didn't we find in relation to the "L" sides? that's the top right corner
 128     ResultPoint topRight;
 129     if (!pointCount.containsKey(pointA)) {
 130       topRight = pointA;
 131     } else if (!pointCount.containsKey(pointB)) {
 132       topRight = pointB;
 133     } else if (!pointCount.containsKey(pointC)) {
 134       topRight = pointC;
 135     } else {
 136       topRight = pointD;
 137     }
 138
 139     // Next determine the dimension by tracing along the top or right side and counting black/white
 140     // transitions. Since we start inside a black module, we should see a number of transitions
 141     // equal to 1 less than the code dimension. Well, actually 2 less, because we are going to
 142     // end on a black module:
 143
 144     // The top right point is actually the corner of a module, which is one of the two black modules
 145     // adjacent to the white module at the top right. Tracing to that corner from either the top left
 146     // or bottom right should work here, but, one will be more reliable since it's traced straight
 147     // up or across, rather than at a slight angle. We use dot products to figure out which is
 148     // better to use:
 149     int dimension;
 150     if (GenericResultPoint.crossProductZ(bottomLeft, bottomRight, topRight) <
 151         GenericResultPoint.crossProductZ(topRight, topLeft, bottomLeft)) {
 152       dimension = transitionsBetween(topLeft, topRight).getTransitions();
 153     } else {
 154       dimension = transitionsBetween(bottomRight, topRight).getTransitions();
 155     }
 156     dimension += 2;
 157
 158     BitMatrix bits = sampleGrid(image, topLeft, bottomLeft, bottomRight, dimension);
 159     return new DetectorResult(bits, new ResultPoint[] {pointA, pointB, pointC, pointD});
 160   }
 161
 162   /**
 163    * Increments the Integer associated with a key by one.
 164    */
 165   private static void increment(Hashtable table, ResultPoint key) {
 166     Integer value = (Integer) table.get(key);
 167     table.put(key, value == null ? INTEGERS[1] : INTEGERS[value.intValue() + 1]);
 168   }
 169
 170   private static BitMatrix sampleGrid(MonochromeBitmapSource image,
 171                                       ResultPoint topLeft,
 172                                       ResultPoint bottomLeft,
 173                                       ResultPoint bottomRight,
 174                                       int dimension) throws ReaderException {
 175
 176     // We make up the top right point for now, based on the others.
 177     // TODO: we actually found a fourth corner above and figured out which of two modules
 178     // it was the corner of. We could use that here and adjust for perspective distortion.
 179     float topRightX = (bottomRight.getX() - bottomLeft.getX()) + topLeft.getX();
 180     float topRightY = (bottomRight.getY() - bottomLeft.getY()) + topLeft.getY();
 181
 182     // Note that unlike in the QR Code sampler, we didn't find the center of modules, but the
 183     // very corners. So there is no 0.5f here; 0.0f is right.
 184     GridSampler sampler = GridSampler.getInstance();
 185     return sampler.sampleGrid(
 186         image,
 187         dimension,
 188         0.0f,
 189         0.0f,
 190         dimension,
 191         0.0f,
 192         dimension,
 193         dimension,
 194         0.0f,
 195         dimension,
 196         topLeft.getX(),
 197         topLeft.getY(),
 198         topRightX,
 199         topRightY,
 200         bottomRight.getX(),
 201         bottomRight.getY(),
 202         bottomLeft.getX(),
 203         bottomLeft.getY());
 204   }
 205
 206   /**
 207    * Counts the number of black/white transitions between two points, using something like Bresenham's algorithm.
 208    */
 209   private ResultPointsAndTransitions transitionsBetween(ResultPoint from, ResultPoint to) {
 210     // See QR Code Detector, sizeOfBlackWhiteBlackRun()
 211     int fromX = (int) from.getX();
 212     int fromY = (int) from.getY();
 213     int toX = (int) to.getX();
 214     int toY = (int) to.getY();
 215     boolean steep = Math.abs(toY - fromY) > Math.abs(toX - fromX);
 216     if (steep) {
 217       int temp = fromX;
 218       fromX = fromY;
 219       fromY = temp;
 220       temp = toX;
 221       toX = toY;
 222       toY = temp;
 223     }
 224
 225     int dx = Math.abs(toX - fromX);
 226     int dy = Math.abs(toY - fromY);
 227     int error = -dx >> 1;
 228     int ystep = fromY < toY ? 1 : -1;
 229     int xstep = fromX < toX ? 1 : -1;
 230     int transitions = 0;
 231     boolean inBlack = image.isBlack(steep ? fromY : fromX, steep ? fromX : fromY);
 232     for (int x = fromX, y = fromY; x != toX; x += xstep) {
 233       boolean isBlack = image.isBlack(steep ? y : x, steep ? x : y);
 234       if (isBlack != inBlack) {
 235         transitions++;
 236         inBlack = isBlack;
 237       }
 238       error += dy;
 239       if (error > 0) {
 240         y += ystep;
 241         error -= dx;
 242       }
 243     }
 244     return new ResultPointsAndTransitions(from, to, transitions);
 245   }
 246
 247   /**
 248    * Simply encapsulates two points and a number of transitions between them.
 249    */
 250   private static class ResultPointsAndTransitions {
 251     private final ResultPoint from;
 252     private final ResultPoint to;
 253     private final int transitions;
 254     private ResultPointsAndTransitions(ResultPoint from, ResultPoint to, int transitions) {
 255       this.from = from;
 256       this.to = to;
 257       this.transitions = transitions;
 258     }
 259     public ResultPoint getFrom() {
 260       return from;
 261     }
 262     public ResultPoint getTo() {
 263       return to;
 264     }
 265     public int getTransitions() {
 266       return transitions;
 267     }
 268     public String toString() {
 269       return from + "/" + to + '/' + transitions;
 270     }
 271   }
 272
 273   /**
 274    * Orders ResultPointsAndTransitions by number of transitions, ascending.
 275    */
 276   private static class ResultPointsAndTransitionsComparator implements Comparator {
 277     public int compare(Object o1, Object o2) {
 278       return ((ResultPointsAndTransitions) o1).getTransitions() - ((ResultPointsAndTransitions) o2).getTransitions();
 279     }
 280   }
 281
 282 }