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.BinaryBitmap;
  20 import com.google.zxing.ReaderException;
  21 import com.google.zxing.ResultPoint;
  22 import com.google.zxing.BinaryBitmap;
  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.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 BinaryBitmap image;
  50   private final MonochromeRectangleDetector rectangleDetector;
  51
  52   public Detector(BinaryBitmap 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     ResultPoint.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. The number of transitions could be higher than it should be
 147     // due to noise. So we try both and take the min.
 148
 149     int dimension = Math.min(transitionsBetween(topLeft, topRight).getTransitions(),
 150                              transitionsBetween(bottomRight, topRight).getTransitions());
 151     if ((dimension & 0x01) == 1) {
 152       // it can't be odd, so, round... up?
 153       dimension++;
 154     }
 155     dimension += 2;
 156
 157     BitMatrix bits = sampleGrid(image, topLeft, bottomLeft, bottomRight, dimension);
 158     return new DetectorResult(bits, new ResultPoint[] {pointA, pointB, pointC, pointD});
 159   }
 160
 161   /**
 162    * Increments the Integer associated with a key by one.
 163    */
 164   private static void increment(Hashtable table, ResultPoint key) {
 165     Integer value = (Integer) table.get(key);
 166     table.put(key, value == null ? INTEGERS[1] : INTEGERS[value.intValue() + 1]);
 167   }
 168
 169   private static BitMatrix sampleGrid(BinaryBitmap image,
 170                                       ResultPoint topLeft,
 171                                       ResultPoint bottomLeft,
 172                                       ResultPoint bottomRight,
 173                                       int dimension) throws ReaderException {
 174
 175     // We make up the top right point for now, based on the others.
 176     // TODO: we actually found a fourth corner above and figured out which of two modules
 177     // it was the corner of. We could use that here and adjust for perspective distortion.
 178     float topRightX = (bottomRight.getX() - bottomLeft.getX()) + topLeft.getX();
 179     float topRightY = (bottomRight.getY() - bottomLeft.getY()) + topLeft.getY();
 180
 181     // Note that unlike in the QR Code sampler, we didn't find the center of modules, but the
 182     // very corners. So there is no 0.5f here; 0.0f is right.
 183     GridSampler sampler = GridSampler.getInstance();
 184     return sampler.sampleGrid(
 185         image,
 186         dimension,
 187         0.0f,
 188         0.0f,
 189         dimension,
 190         0.0f,
 191         dimension,
 192         dimension,
 193         0.0f,
 194         dimension,
 195         topLeft.getX(),
 196         topLeft.getY(),
 197         topRightX,
 198         topRightY,
 199         bottomRight.getX(),
 200         bottomRight.getY(),
 201         bottomLeft.getX(),
 202         bottomLeft.getY());
 203   }
 204
 205   /**
 206    * Counts the number of black/white transitions between two points, using something like Bresenham's algorithm.
 207    */
 208   private ResultPointsAndTransitions transitionsBetween(ResultPoint from, ResultPoint to)
 209       throws ReaderException {
 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 }