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