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