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. 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     dimension += 2;
 152
 153     BitMatrix bits = sampleGrid(image, topLeft, bottomLeft, bottomRight, dimension);
 154     return new DetectorResult(bits, new ResultPoint[] {pointA, pointB, pointC, pointD});
 155   }
 156
 157   /**
 158    * Increments the Integer associated with a key by one.
 159    */
 160   private static void increment(Hashtable table, ResultPoint key) {
 161     Integer value = (Integer) table.get(key);
 162     table.put(key, value == null ? INTEGERS[1] : INTEGERS[value.intValue() + 1]);
 163   }
 164
 165   private static BitMatrix sampleGrid(MonochromeBitmapSource image,
 166                                       ResultPoint topLeft,
 167                                       ResultPoint bottomLeft,
 168                                       ResultPoint bottomRight,
 169                                       int dimension) throws ReaderException {
 170
 171     // We make up the top right point for now, based on the others.
 172     // TODO: we actually found a fourth corner above and figured out which of two modules
 173     // it was the corner of. We could use that here and adjust for perspective distortion.
 174     float topRightX = (bottomRight.getX() - bottomLeft.getX()) + topLeft.getX();
 175     float topRightY = (bottomRight.getY() - bottomLeft.getY()) + topLeft.getY();
 176
 177     // Note that unlike in the QR Code sampler, we didn't find the center of modules, but the
 178     // very corners. So there is no 0.5f here; 0.0f is right.
 179     GridSampler sampler = GridSampler.getInstance();
 180     return sampler.sampleGrid(
 181         image,
 182         dimension,
 183         0.0f,
 184         0.0f,
 185         dimension,
 186         0.0f,
 187         dimension,
 188         dimension,
 189         0.0f,
 190         dimension,
 191         topLeft.getX(),
 192         topLeft.getY(),
 193         topRightX,
 194         topRightY,
 195         bottomRight.getX(),
 196         bottomRight.getY(),
 197         bottomLeft.getX(),
 198         bottomLeft.getY());
 199   }
 200
 201   /**
 202    * Counts the number of black/white transitions between two points, using something like Bresenham's algorithm.
 203    */
 204   private ResultPointsAndTransitions transitionsBetween(ResultPoint from, ResultPoint to) {
 205     // See QR Code Detector, sizeOfBlackWhiteBlackRun()
 206     int fromX = (int) from.getX();
 207     int fromY = (int) from.getY();
 208     int toX = (int) to.getX();
 209     int toY = (int) to.getY();
 210     boolean steep = Math.abs(toY - fromY) > Math.abs(toX - fromX);
 211     if (steep) {
 212       int temp = fromX;
 213       fromX = fromY;
 214       fromY = temp;
 215       temp = toX;
 216       toX = toY;
 217       toY = temp;
 218     }
 219
 220     int dx = Math.abs(toX - fromX);
 221     int dy = Math.abs(toY - fromY);
 222     int error = -dx >> 1;
 223     int ystep = fromY < toY ? 1 : -1;
 224     int xstep = fromX < toX ? 1 : -1;
 225     int transitions = 0;
 226     boolean inBlack = image.isBlack(steep ? fromY : fromX, steep ? fromX : fromY);
 227     for (int x = fromX, y = fromY; x != toX; x += xstep) {
 228       boolean isBlack = image.isBlack(steep ? y : x, steep ? x : y);
 229       if (isBlack != inBlack) {
 230         transitions++;
 231         inBlack = isBlack;
 232       }
 233       error += dy;
 234       if (error > 0) {
 235         y += ystep;
 236         error -= dx;
 237       }
 238     }
 239     return new ResultPointsAndTransitions(from, to, transitions);
 240   }
 241
 242   /**
 243    * Simply encapsulates two points and a number of transitions between them.
 244    */
 245   private static class ResultPointsAndTransitions {
 246     private final ResultPoint from;
 247     private final ResultPoint to;
 248     private final int transitions;
 249     private ResultPointsAndTransitions(ResultPoint from, ResultPoint to, int transitions) {
 250       this.from = from;
 251       this.to = to;
 252       this.transitions = transitions;
 253     }
 254     public ResultPoint getFrom() {
 255       return from;
 256     }
 257     public ResultPoint getTo() {
 258       return to;
 259     }
 260     public int getTransitions() {
 261       return transitions;
 262     }
 263     public String toString() {
 264       return from + "/" + to + '/' + transitions;
 265     }
 266   }
 267
 268   /**
 269    * Orders ResultPointsAndTransitions by number of transitions, ascending.
 270    */
 271   private static class ResultPointsAndTransitionsComparator implements Comparator {
 272     public int compare(Object o1, Object o2) {
 273       return ((ResultPointsAndTransitions) o1).getTransitions() - ((ResultPointsAndTransitions) o2).getTransitions();
 274     }
 275   }
 276
 277 }