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.WhiteRectangleDetector;
  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   // Trick to avoid creating new Integer objects below -- a sort of crude copy of
  41   // the Integer.valueOf(int) optimization added in Java 5, not in J2ME
  42   private static final Integer[] INTEGERS =
  43       { new Integer(0), new Integer(1), new Integer(2), new Integer(3), new Integer(4) };
  44   // No, can't use valueOf()
  45
  46   private final BitMatrix image;
  47   private final WhiteRectangleDetector rectangleDetector;
  48
  49   public Detector(BitMatrix image) {
  50     this.image = image;
  51     rectangleDetector = new WhiteRectangleDetector(image);
  52   }
  53
  54   /**
  55    * <p>Detects a Data Matrix Code in an image.</p>
  56    *
  57    * @return {@link DetectorResult} encapsulating results of detecting a Data Matrix Code
  58    * @throws NotFoundException if no Data Matrix Code can be found
  59    */
  60   public DetectorResult detect() throws NotFoundException {
  61
  62     ResultPoint[] cornerPoints = rectangleDetector.detect();
  63     ResultPoint pointA = cornerPoints[0];
  64     ResultPoint pointB = cornerPoints[1];
  65     ResultPoint pointC = cornerPoints[2];
  66     ResultPoint pointD = cornerPoints[3];
  67
  68     // Point A and D are across the diagonal from one another,
  69     // as are B and C. Figure out which are the solid black lines
  70     // by counting transitions
  71     Vector transitions = new Vector(4);
  72     transitions.addElement(transitionsBetween(pointA, pointB));
  73     transitions.addElement(transitionsBetween(pointA, pointC));
  74     transitions.addElement(transitionsBetween(pointB, pointD));
  75     transitions.addElement(transitionsBetween(pointC, pointD));
  76     Collections.insertionSort(transitions, new ResultPointsAndTransitionsComparator());
  77
  78     // Sort by number of transitions. First two will be the two solid sides; last two
  79     // will be the two alternating black/white sides
  80     ResultPointsAndTransitions lSideOne = (ResultPointsAndTransitions) transitions.elementAt(0);
  81     ResultPointsAndTransitions lSideTwo = (ResultPointsAndTransitions) transitions.elementAt(1);
  82
  83     // Figure out which point is their intersection by tallying up the number of times we see the
  84     // endpoints in the four endpoints. One will show up twice.
  85     Hashtable pointCount = new Hashtable();
  86     increment(pointCount, lSideOne.getFrom());
  87     increment(pointCount, lSideOne.getTo());
  88     increment(pointCount, lSideTwo.getFrom());
  89     increment(pointCount, lSideTwo.getTo());
  90
  91     ResultPoint maybeTopLeft = null;
  92     ResultPoint bottomLeft = null;
  93     ResultPoint maybeBottomRight = null;
  94     Enumeration points = pointCount.keys();
  95     while (points.hasMoreElements()) {
  96       ResultPoint point = (ResultPoint) points.nextElement();
  97       Integer value = (Integer) pointCount.get(point);
  98       if (value.intValue() == 2) {
  99         bottomLeft = point; // this is definitely the bottom left, then -- end of two L sides
 100       } else {
 101         // Otherwise it's either top left or bottom right -- just assign the two arbitrarily now
 102         if (maybeTopLeft == null) {
 103           maybeTopLeft = point;
 104         } else {
 105           maybeBottomRight = point;
 106         }
 107       }
 108     }
 109
 110     if (maybeTopLeft == null || bottomLeft == null || maybeBottomRight == null) {
 111       throw NotFoundException.getNotFoundInstance();
 112     }
 113
 114     // Bottom left is correct but top left and bottom right might be switched
 115     ResultPoint[] corners = { maybeTopLeft, bottomLeft, maybeBottomRight };
 116     // Use the dot product trick to sort them out
 117     ResultPoint.orderBestPatterns(corners);
 118
 119     // Now we know which is which:
 120     ResultPoint bottomRight = corners[0];
 121     bottomLeft = corners[1];
 122     ResultPoint topLeft = corners[2];
 123
 124     // Which point didn't we find in relation to the "L" sides? that's the top right corner
 125     ResultPoint topRight;
 126     if (!pointCount.containsKey(pointA)) {
 127       topRight = pointA;
 128     } else if (!pointCount.containsKey(pointB)) {
 129       topRight = pointB;
 130     } else if (!pointCount.containsKey(pointC)) {
 131       topRight = pointC;
 132     } else {
 133       topRight = pointD;
 134     }
 135
 136     // Next determine the dimension by tracing along the top or right side and counting black/white
 137     // transitions. Since we start inside a black module, we should see a number of transitions
 138     // equal to 1 less than the code dimension. Well, actually 2 less, because we are going to
 139     // end on a black module:
 140
 141     // The top right point is actually the corner of a module, which is one of the two black modules
 142     // adjacent to the white module at the top right. Tracing to that corner from either the top left
 143     // or bottom right should work here.
 144     int dimension = Math.min(transitionsBetween(topLeft, topRight).getTransitions(),
 145                              transitionsBetween(bottomRight, topRight).getTransitions());
 146     if ((dimension & 0x01) == 1) {
 147       // it can't be odd, so, round... up?
 148       dimension++;
 149     }
 150     dimension += 2;
 151
 152     //correct top right point to match the white module
 153     ResultPoint correctedTopRight = correctTopRight(bottomLeft, bottomRight, topLeft, topRight, dimension);
 154
 155     //We redetermine the dimension using the corrected top right point
 156     int dimension2 = Math.max(transitionsBetween(topLeft, correctedTopRight).getTransitions(),
 157                               transitionsBetween(bottomRight, correctedTopRight).getTransitions());
 158     dimension2++;
 159     if ((dimension2 & 0x01) == 1) {
 160       dimension2++;
 161     }
 162
 163     BitMatrix bits = sampleGrid(image, topLeft, bottomLeft, bottomRight, correctedTopRight, dimension2);
 164
 165     return new DetectorResult(bits, new ResultPoint[]{topLeft, bottomLeft, bottomRight, correctedTopRight});
 166   }
 167
 168   /**
 169    * Calculates the position of the white top right module using the output of the rectangle detector
 170    */
 171   private ResultPoint correctTopRight(ResultPoint bottomLeft,
 172                                       ResultPoint bottomRight,
 173                                       ResultPoint topLeft,
 174                                       ResultPoint topRight,
 175                                       int dimension) {
 176
 177                 float corr = distance(bottomLeft, bottomRight) / (float)dimension;
 178                 int norm = distance(topLeft, topRight);
 179                 float cos = (topRight.getX() - topLeft.getX()) / norm;
 180                 float sin = (topRight.getY() - topLeft.getY()) / norm;
 181
 182                 ResultPoint c1 = new ResultPoint(topRight.getX()+corr*cos, topRight.getY()+corr*sin);
 183
 184                 corr = distance(bottomLeft, bottomRight) / (float)dimension;
 185                 norm = distance(bottomRight, topRight);
 186                 cos = (topRight.getX() - bottomRight.getX()) / norm;
 187                 sin = (topRight.getY() - bottomRight.getY()) / norm;
 188
 189                 ResultPoint c2 = new ResultPoint(topRight.getX()+corr*cos, topRight.getY()+corr*sin);
 190
 191                 int l1 = Math.abs(transitionsBetween(topLeft, c1).getTransitions() - transitionsBetween(bottomRight, c1).getTransitions());
 192                 int l2 = Math.abs(transitionsBetween(topLeft, c2).getTransitions() - transitionsBetween(bottomRight, c2).getTransitions());
 193
 194                 if (l1 <= l2){
 195                         return c1;
 196                 }
 197
 198                 return c2;
 199   }
 200
 201   // L2 distance
 202   private static int distance(ResultPoint a, ResultPoint b) {
 203     return (int) Math.round(Math.sqrt((a.getX() - b.getX())
 204         * (a.getX() - b.getX()) + (a.getY() - b.getY())
 205         * (a.getY() - b.getY())));
 206   }
 207
 208   /**
 209    * Increments the Integer associated with a key by one.
 210    */
 211   private static void increment(Hashtable table, ResultPoint key) {
 212     Integer value = (Integer) table.get(key);
 213     table.put(key, value == null ? INTEGERS[1] : INTEGERS[value.intValue() + 1]);
 214   }
 215
 216   private static BitMatrix sampleGrid(BitMatrix image,
 217                                       ResultPoint topLeft,
 218                                       ResultPoint bottomLeft,
 219                                       ResultPoint bottomRight,
 220                                       ResultPoint topRight,
 221                                       int dimension) throws NotFoundException {
 222
 223     GridSampler sampler = GridSampler.getInstance();
 224
 225     return sampler.sampleGrid(image,
 226                               dimension,
 227                               0.5f,
 228                               0.5f,
 229                               dimension - 0.5f,
 230                               0.5f,
 231                               dimension - 0.5f,
 232                               dimension - 0.5f,
 233                               0.5f,
 234                               dimension - 0.5f,
 235                               topLeft.getX(),
 236                               topLeft.getY(),
 237                               topRight.getX(),
 238                               topRight.getY(),
 239                               bottomRight.getX(),
 240                               bottomRight.getY(),
 241                               bottomLeft.getX(),
 242                               bottomLeft.getY());
 243   }
 244
 245   /**
 246    * Counts the number of black/white transitions between two points, using something like Bresenham's algorithm.
 247    */
 248   private ResultPointsAndTransitions transitionsBetween(ResultPoint from, ResultPoint to) {
 249     // See QR Code Detector, sizeOfBlackWhiteBlackRun()
 250     int fromX = (int) from.getX();
 251     int fromY = (int) from.getY();
 252     int toX = (int) to.getX();
 253     int toY = (int) to.getY();
 254     boolean steep = Math.abs(toY - fromY) > Math.abs(toX - fromX);
 255     if (steep) {
 256       int temp = fromX;
 257       fromX = fromY;
 258       fromY = temp;
 259       temp = toX;
 260       toX = toY;
 261       toY = temp;
 262     }
 263
 264     int dx = Math.abs(toX - fromX);
 265     int dy = Math.abs(toY - fromY);
 266     int error = -dx >> 1;
 267     int ystep = fromY < toY ? 1 : -1;
 268     int xstep = fromX < toX ? 1 : -1;
 269     int transitions = 0;
 270     boolean inBlack = image.get(steep ? fromY : fromX, steep ? fromX : fromY);
 271     for (int x = fromX, y = fromY; x != toX; x += xstep) {
 272       boolean isBlack = image.get(steep ? y : x, steep ? x : y);
 273       if (isBlack != inBlack) {
 274         transitions++;
 275         inBlack = isBlack;
 276       }
 277       error += dy;
 278       if (error > 0) {
 279         if (y == toY) {
 280           break;
 281         }
 282         y += ystep;
 283         error -= dx;
 284       }
 285     }
 286     return new ResultPointsAndTransitions(from, to, transitions);
 287   }
 288
 289   /**
 290    * Simply encapsulates two points and a number of transitions between them.
 291    */
 292   private static class ResultPointsAndTransitions {
 293     private final ResultPoint from;
 294     private final ResultPoint to;
 295     private final int transitions;
 296     private ResultPointsAndTransitions(ResultPoint from, ResultPoint to, int transitions) {
 297       this.from = from;
 298       this.to = to;
 299       this.transitions = transitions;
 300     }
 301     public ResultPoint getFrom() {
 302       return from;
 303     }
 304     public ResultPoint getTo() {
 305       return to;
 306     }
 307     public int getTransitions() {
 308       return transitions;
 309     }
 310     public String toString() {
 311       return from + "/" + to + '/' + transitions;
 312     }
 313   }
 314
 315   /**
 316    * Orders ResultPointsAndTransitions by number of transitions, ascending.
 317    */
 318   private static class ResultPointsAndTransitionsComparator implements Comparator {
 319     public int compare(Object o1, Object o2) {
 320       return ((ResultPointsAndTransitions) o1).getTransitions() - ((ResultPointsAndTransitions) o2).getTransitions();
 321     }
 322   }
 323
 324 }