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