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