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
 145
 146     int dimensionTop = transitionsBetween(topLeft, topRight).getTransitions();
 147     int dimensionRight = transitionsBetween(bottomRight, topRight).getTransitions();
 148
 149     if ((dimensionTop & 0x01) == 1) {
 150       // it can't be odd, so, round... up?
 151       dimensionTop++;
 152     }
 153     dimensionTop += 2;
 154
 155     if ((dimensionRight & 0x01) == 1) {
 156         // it can't be odd, so, round... up?
 157         dimensionRight++;
 158       }
 159       dimensionRight += 2;
 160
 161     BitMatrix bits;
 162     ResultPoint correctedTopRight;
 163
 164     if (dimensionTop >= dimensionRight * 2 || dimensionRight >= dimensionTop * 2){
 165         //The matrix is rectangular
 166
 167         correctedTopRight =
 168             correctTopRightRectangular(bottomLeft, bottomRight, topLeft, topRight, dimensionTop, dimensionRight);
 169         if (correctedTopRight == null){
 170                 correctedTopRight = topRight;
 171         }
 172
 173         dimensionTop = transitionsBetween(topLeft, correctedTopRight).getTransitions();
 174         dimensionRight = transitionsBetween(bottomRight, correctedTopRight).getTransitions();
 175
 176         if ((dimensionTop & 0x01) == 1) {
 177           // it can't be odd, so, round... up?
 178           dimensionTop++;
 179         }
 180
 181         if ((dimensionRight & 0x01) == 1) {
 182           // it can't be odd, so, round... up?
 183           dimensionRight++;
 184         }
 185
 186         bits = sampleGrid(image, topLeft, bottomLeft, bottomRight, correctedTopRight, dimensionTop, dimensionRight);
 187
 188     } else {
 189         //The matrix is square
 190
 191         int dimension = Math.min(dimensionRight, dimensionTop);
 192         //correct top right point to match the white module
 193         correctedTopRight = correctTopRight(bottomLeft, bottomRight, topLeft, topRight, dimension);
 194         if (correctedTopRight == null){
 195                 correctedTopRight = topRight;
 196         }
 197
 198         //We redetermine the dimension using the corrected top right point
 199         int dimensionCorrected = Math.max(transitionsBetween(topLeft, correctedTopRight).getTransitions(),
 200                                   transitionsBetween(bottomRight, correctedTopRight).getTransitions());
 201         dimensionCorrected++;
 202         if ((dimensionCorrected & 0x01) == 1) {
 203           dimensionCorrected++;
 204         }
 205
 206         bits = sampleGrid(image,
 207                           topLeft,
 208                           bottomLeft,
 209                           bottomRight,
 210                           correctedTopRight,
 211                           dimensionCorrected,
 212                           dimensionCorrected);
 213     }
 214
 215
 216     return new DetectorResult(bits, new ResultPoint[]{topLeft, bottomLeft, bottomRight, correctedTopRight});
 217   }
 218
 219   /**
 220    * Calculates the position of the white top right module using the output of the rectangle detector
 221    * for a rectangular matrix
 222    */
 223   private ResultPoint correctTopRightRectangular(ResultPoint bottomLeft,
 224                 ResultPoint bottomRight, ResultPoint topLeft, ResultPoint topRight,
 225                 int dimensionTop, int dimensionRight) {
 226
 227                 float corr = distance(bottomLeft, bottomRight) / (float)dimensionTop;
 228                 int norm = distance(topLeft, topRight);
 229                 float cos = (topRight.getX() - topLeft.getX()) / norm;
 230                 float sin = (topRight.getY() - topLeft.getY()) / norm;
 231
 232                 ResultPoint c1 = new ResultPoint(topRight.getX()+corr*cos, topRight.getY()+corr*sin);
 233
 234                 corr = distance(bottomLeft, topLeft) / (float)dimensionRight;
 235                 norm = distance(bottomRight, topRight);
 236                 cos = (topRight.getX() - bottomRight.getX()) / norm;
 237                 sin = (topRight.getY() - bottomRight.getY()) / norm;
 238
 239                 ResultPoint c2 = new ResultPoint(topRight.getX()+corr*cos, topRight.getY()+corr*sin);
 240
 241                 if (!isValid(c1)){
 242                         if (isValid(c2)){
 243                                 return c2;
 244                         }
 245                         return null;
 246                 } else if (!isValid(c2)){
 247                         return c1;
 248                 }
 249
 250                 int l1 = Math.abs(dimensionTop - transitionsBetween(topLeft, c1).getTransitions()) +
 251                                         Math.abs(dimensionRight - transitionsBetween(bottomRight, c1).getTransitions());
 252                 int l2 = Math.abs(dimensionTop - transitionsBetween(topLeft, c2).getTransitions()) +
 253                 Math.abs(dimensionRight - transitionsBetween(bottomRight, c2).getTransitions());
 254
 255                 if (l1 <= l2){
 256                         return c1;
 257                 }
 258
 259                 return c2;
 260   }
 261
 262   /**
 263    * Calculates the position of the white top right module using the output of the rectangle detector
 264    * for a square matrix
 265    */
 266   private ResultPoint correctTopRight(ResultPoint bottomLeft,
 267                                       ResultPoint bottomRight,
 268                                       ResultPoint topLeft,
 269                                       ResultPoint topRight,
 270                                       int dimension) {
 271
 272                 float corr = distance(bottomLeft, bottomRight) / (float) dimension;
 273                 int norm = distance(topLeft, topRight);
 274                 float cos = (topRight.getX() - topLeft.getX()) / norm;
 275                 float sin = (topRight.getY() - topLeft.getY()) / norm;
 276
 277                 ResultPoint c1 = new ResultPoint(topRight.getX() + corr * cos, topRight.getY() + corr * sin);
 278
 279                 corr = distance(bottomLeft, bottomRight) / (float) dimension;
 280                 norm = distance(bottomRight, topRight);
 281                 cos = (topRight.getX() - bottomRight.getX()) / norm;
 282                 sin = (topRight.getY() - bottomRight.getY()) / norm;
 283
 284                 ResultPoint c2 = new ResultPoint(topRight.getX() + corr * cos, topRight.getY() + corr * sin);
 285
 286                 if (!isValid(c1)) {
 287                         if (isValid(c2)) {
 288                                 return c2;
 289                         }
 290                         return null;
 291                 } else if (!isValid(c2)) {
 292                         return c1;
 293                 }
 294
 295                 int l1 = Math.abs(transitionsBetween(topLeft, c1).getTransitions() -
 296                       transitionsBetween(bottomRight, c1).getTransitions());
 297                 int l2 = Math.abs(transitionsBetween(topLeft, c2).getTransitions() -
 298                       transitionsBetween(bottomRight, c2).getTransitions());
 299
 300     return l1 <= l2 ? c1 : c2;
 301   }
 302
 303   private boolean isValid(ResultPoint p) {
 304           return (p.getX() >= 0 && p.getX() < image.width && p.getY() > 0 && p.getY() < image.height);
 305   }
 306
 307   /**
 308    * Ends up being a bit faster than Math.round(). This merely rounds its
 309    * argument to the nearest int, where x.5 rounds up.
 310    */
 311   private static int round(float d) {
 312     return (int) (d + 0.5f);
 313   }
 314
 315 // L2 distance
 316   private static int distance(ResultPoint a, ResultPoint b) {
 317     return round((float) Math.sqrt((a.getX() - b.getX())
 318         * (a.getX() - b.getX()) + (a.getY() - b.getY())
 319         * (a.getY() - b.getY())));
 320   }
 321
 322   /**
 323    * Increments the Integer associated with a key by one.
 324    */
 325   private static void increment(Hashtable table, ResultPoint key) {
 326     Integer value = (Integer) table.get(key);
 327     table.put(key, value == null ? INTEGERS[1] : INTEGERS[value.intValue() + 1]);
 328   }
 329
 330   private static BitMatrix sampleGrid(BitMatrix image,
 331                                       ResultPoint topLeft,
 332                                       ResultPoint bottomLeft,
 333                                       ResultPoint bottomRight,
 334                                       ResultPoint topRight,
 335                                       int dimensionX,
 336                                       int dimensionY) throws NotFoundException {
 337
 338     GridSampler sampler = GridSampler.getInstance();
 339
 340     return sampler.sampleGrid(image,
 341                               dimensionX,
 342                               dimensionY,
 343                               0.5f,
 344                               0.5f,
 345                               dimensionX - 0.5f,
 346                               0.5f,
 347                               dimensionX - 0.5f,
 348                               dimensionY - 0.5f,
 349                               0.5f,
 350                               dimensionY - 0.5f,
 351                               topLeft.getX(),
 352                               topLeft.getY(),
 353                               topRight.getX(),
 354                               topRight.getY(),
 355                               bottomRight.getX(),
 356                               bottomRight.getY(),
 357                               bottomLeft.getX(),
 358                               bottomLeft.getY());
 359   }
 360
 361   /**
 362    * Counts the number of black/white transitions between two points, using something like Bresenham's algorithm.
 363    */
 364   private ResultPointsAndTransitions transitionsBetween(ResultPoint from, ResultPoint to) {
 365     // See QR Code Detector, sizeOfBlackWhiteBlackRun()
 366     int fromX = (int) from.getX();
 367     int fromY = (int) from.getY();
 368     int toX = (int) to.getX();
 369     int toY = (int) to.getY();
 370     boolean steep = Math.abs(toY - fromY) > Math.abs(toX - fromX);
 371     if (steep) {
 372       int temp = fromX;
 373       fromX = fromY;
 374       fromY = temp;
 375       temp = toX;
 376       toX = toY;
 377       toY = temp;
 378     }
 379
 380     int dx = Math.abs(toX - fromX);
 381     int dy = Math.abs(toY - fromY);
 382     int error = -dx >> 1;
 383     int ystep = fromY < toY ? 1 : -1;
 384     int xstep = fromX < toX ? 1 : -1;
 385     int transitions = 0;
 386     boolean inBlack = image.get(steep ? fromY : fromX, steep ? fromX : fromY);
 387     for (int x = fromX, y = fromY; x != toX; x += xstep) {
 388       boolean isBlack = image.get(steep ? y : x, steep ? x : y);
 389       if (isBlack != inBlack) {
 390         transitions++;
 391         inBlack = isBlack;
 392       }
 393       error += dy;
 394       if (error > 0) {
 395         if (y == toY) {
 396           break;
 397         }
 398         y += ystep;
 399         error -= dx;
 400       }
 401     }
 402     return new ResultPointsAndTransitions(from, to, transitions);
 403   }
 404
 405   /**
 406    * Simply encapsulates two points and a number of transitions between them.
 407    */
 408   private static class ResultPointsAndTransitions {
 409     private final ResultPoint from;
 410     private final ResultPoint to;
 411     private final int transitions;
 412     private ResultPointsAndTransitions(ResultPoint from, ResultPoint to, int transitions) {
 413       this.from = from;
 414       this.to = to;
 415       this.transitions = transitions;
 416     }
 417     public ResultPoint getFrom() {
 418       return from;
 419     }
 420     public ResultPoint getTo() {
 421       return to;
 422     }
 423     public int getTransitions() {
 424       return transitions;
 425     }
 426     public String toString() {
 427       return from + "/" + to + '/' + transitions;
 428     }
 429   }
 430
 431   /**
 432    * Orders ResultPointsAndTransitions by number of transitions, ascending.
 433    */
 434   private static class ResultPointsAndTransitionsComparator implements Comparator {
 435     public int compare(Object o1, Object o2) {
 436       return ((ResultPointsAndTransitions) o1).getTransitions() - ((ResultPointsAndTransitions) o2).getTransitions();
 437     }
 438   }
 439
 440 }