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.NotFoundException;
  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 NotFoundException if no Data Matrix Code can be found
  61    */
  62   public DetectorResult detect() throws NotFoundException {
  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 NotFoundException.getNotFoundInstance();
 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 NotFoundException {
 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     // See QR Code Detector, sizeOfBlackWhiteBlackRun()
 209     int fromX = (int) from.getX();
 210     int fromY = (int) from.getY();
 211     int toX = (int) to.getX();
 212     int toY = (int) to.getY();
 213     boolean steep = Math.abs(toY - fromY) > Math.abs(toX - fromX);
 214     if (steep) {
 215       int temp = fromX;
 216       fromX = fromY;
 217       fromY = temp;
 218       temp = toX;
 219       toX = toY;
 220       toY = temp;
 221     }
 222
 223     int dx = Math.abs(toX - fromX);
 224     int dy = Math.abs(toY - fromY);
 225     int error = -dx >> 1;
 226     int ystep = fromY < toY ? 1 : -1;
 227     int xstep = fromX < toX ? 1 : -1;
 228     int transitions = 0;
 229     boolean inBlack = image.get(steep ? fromY : fromX, steep ? fromX : fromY);
 230     for (int x = fromX, y = fromY; x != toX; x += xstep) {
 231       boolean isBlack = image.get(steep ? y : x, steep ? x : y);
 232       if (isBlack != inBlack) {
 233         transitions++;
 234         inBlack = isBlack;
 235       }
 236       error += dy;
 237       if (error > 0) {
 238         if (y == toY) {
 239           break;
 240         }
 241         y += ystep;
 242         error -= dx;
 243       }
 244     }
 245     return new ResultPointsAndTransitions(from, to, transitions);
 246   }
 247
 248   /**
 249    * Simply encapsulates two points and a number of transitions between them.
 250    */
 251   private static class ResultPointsAndTransitions {
 252     private final ResultPoint from;
 253     private final ResultPoint to;
 254     private final int transitions;
 255     private ResultPointsAndTransitions(ResultPoint from, ResultPoint to, int transitions) {
 256       this.from = from;
 257       this.to = to;
 258       this.transitions = transitions;
 259     }
 260     public ResultPoint getFrom() {
 261       return from;
 262     }
 263     public ResultPoint getTo() {
 264       return to;
 265     }
 266     public int getTransitions() {
 267       return transitions;
 268     }
 269     public String toString() {
 270       return from + "/" + to + '/' + transitions;
 271     }
 272   }
 273
 274   /**
 275    * Orders ResultPointsAndTransitions by number of transitions, ascending.
 276    */
 277   private static class ResultPointsAndTransitionsComparator implements Comparator {
 278     public int compare(Object o1, Object o2) {
 279       return ((ResultPointsAndTransitions) o1).getTransitions() - ((ResultPointsAndTransitions) o2).getTransitions();
 280     }
 281   }
 282
 283 }