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