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     if (correctedTopRight == null){
 155         correctedTopRight = topRight;
 156     }
 157
 158     //We redetermine the dimension using the corrected top right point
 159     int dimension2 = Math.max(transitionsBetween(topLeft, correctedTopRight).getTransitions(),
 160                               transitionsBetween(bottomRight, correctedTopRight).getTransitions());
 161     dimension2++;
 162     if ((dimension2 & 0x01) == 1) {
 163       dimension2++;
 164     }
 165
 166     BitMatrix bits = sampleGrid(image, topLeft, bottomLeft, bottomRight, correctedTopRight, dimension2);
 167
 168     return new DetectorResult(bits, new ResultPoint[]{topLeft, bottomLeft, bottomRight, correctedTopRight});
 169   }
 170
 171   /**
 172    * Calculates the position of the white top right module using the output of the rectangle detector
 173    */
 174   private ResultPoint correctTopRight(ResultPoint bottomLeft,
 175                                       ResultPoint bottomRight,
 176                                       ResultPoint topLeft,
 177                                       ResultPoint topRight,
 178                                       int dimension) {
 179
 180                 float corr = distance(bottomLeft, bottomRight) / (float)dimension;
 181                 int norm = distance(topLeft, topRight);
 182                 float cos = (topRight.getX() - topLeft.getX()) / norm;
 183                 float sin = (topRight.getY() - topLeft.getY()) / norm;
 184
 185                 ResultPoint c1 = new ResultPoint(topRight.getX()+corr*cos, topRight.getY()+corr*sin);
 186
 187                 corr = distance(bottomLeft, bottomRight) / (float)dimension;
 188                 norm = distance(bottomRight, topRight);
 189                 cos = (topRight.getX() - bottomRight.getX()) / norm;
 190                 sin = (topRight.getY() - bottomRight.getY()) / norm;
 191
 192                 ResultPoint c2 = new ResultPoint(topRight.getX()+corr*cos, topRight.getY()+corr*sin);
 193
 194                 if (!isValid(c1)){
 195                         if (isValid(c2)){
 196                                 return c2;
 197                         }
 198                         return null;
 199                 } else if (!isValid(c2)){
 200                         return c1;
 201                 }
 202
 203                 int l1 = Math.abs(transitionsBetween(topLeft, c1).getTransitions() - transitionsBetween(bottomRight, c1).getTransitions());
 204                 int l2 = Math.abs(transitionsBetween(topLeft, c2).getTransitions() - transitionsBetween(bottomRight, c2).getTransitions());
 205
 206                 if (l1 <= l2){
 207                         return c1;
 208                 }
 209
 210                 return c2;
 211   }
 212
 213   private boolean isValid(ResultPoint p) {
 214           return (p.getX() >= 0 && p.getX() < image.width && p.getY() > 0 && p.getY() < image.height);
 215   }
 216
 217 // L2 distance
 218   private static int distance(ResultPoint a, ResultPoint b) {
 219     return (int) Math.round(Math.sqrt((a.getX() - b.getX())
 220         * (a.getX() - b.getX()) + (a.getY() - b.getY())
 221         * (a.getY() - b.getY())));
 222   }
 223
 224   /**
 225    * Increments the Integer associated with a key by one.
 226    */
 227   private static void increment(Hashtable table, ResultPoint key) {
 228     Integer value = (Integer) table.get(key);
 229     table.put(key, value == null ? INTEGERS[1] : INTEGERS[value.intValue() + 1]);
 230   }
 231
 232   private static BitMatrix sampleGrid(BitMatrix image,
 233                                       ResultPoint topLeft,
 234                                       ResultPoint bottomLeft,
 235                                       ResultPoint bottomRight,
 236                                       ResultPoint topRight,
 237                                       int dimension) throws NotFoundException {
 238
 239     GridSampler sampler = GridSampler.getInstance();
 240
 241     return sampler.sampleGrid(image,
 242                               dimension,
 243                               0.5f,
 244                               0.5f,
 245                               dimension - 0.5f,
 246                               0.5f,
 247                               dimension - 0.5f,
 248                               dimension - 0.5f,
 249                               0.5f,
 250                               dimension - 0.5f,
 251                               topLeft.getX(),
 252                               topLeft.getY(),
 253                               topRight.getX(),
 254                               topRight.getY(),
 255                               bottomRight.getX(),
 256                               bottomRight.getY(),
 257                               bottomLeft.getX(),
 258                               bottomLeft.getY());
 259   }
 260
 261   /**
 262    * Counts the number of black/white transitions between two points, using something like Bresenham's algorithm.
 263    */
 264   private ResultPointsAndTransitions transitionsBetween(ResultPoint from, ResultPoint to) {
 265     // See QR Code Detector, sizeOfBlackWhiteBlackRun()
 266     int fromX = (int) from.getX();
 267     int fromY = (int) from.getY();
 268     int toX = (int) to.getX();
 269     int toY = (int) to.getY();
 270     boolean steep = Math.abs(toY - fromY) > Math.abs(toX - fromX);
 271     if (steep) {
 272       int temp = fromX;
 273       fromX = fromY;
 274       fromY = temp;
 275       temp = toX;
 276       toX = toY;
 277       toY = temp;
 278     }
 279
 280     int dx = Math.abs(toX - fromX);
 281     int dy = Math.abs(toY - fromY);
 282     int error = -dx >> 1;
 283     int ystep = fromY < toY ? 1 : -1;
 284     int xstep = fromX < toX ? 1 : -1;
 285     int transitions = 0;
 286     boolean inBlack = image.get(steep ? fromY : fromX, steep ? fromX : fromY);
 287     for (int x = fromX, y = fromY; x != toX; x += xstep) {
 288       boolean isBlack = image.get(steep ? y : x, steep ? x : y);
 289       if (isBlack != inBlack) {
 290         transitions++;
 291         inBlack = isBlack;
 292       }
 293       error += dy;
 294       if (error > 0) {
 295         if (y == toY) {
 296           break;
 297         }
 298         y += ystep;
 299         error -= dx;
 300       }
 301     }
 302     return new ResultPointsAndTransitions(from, to, transitions);
 303   }
 304
 305   /**
 306    * Simply encapsulates two points and a number of transitions between them.
 307    */
 308   private static class ResultPointsAndTransitions {
 309     private final ResultPoint from;
 310     private final ResultPoint to;
 311     private final int transitions;
 312     private ResultPointsAndTransitions(ResultPoint from, ResultPoint to, int transitions) {
 313       this.from = from;
 314       this.to = to;
 315       this.transitions = transitions;
 316     }
 317     public ResultPoint getFrom() {
 318       return from;
 319     }
 320     public ResultPoint getTo() {
 321       return to;
 322     }
 323     public int getTransitions() {
 324       return transitions;
 325     }
 326     public String toString() {
 327       return from + "/" + to + '/' + transitions;
 328     }
 329   }
 330
 331   /**
 332    * Orders ResultPointsAndTransitions by number of transitions, ascending.
 333    */
 334   private static class ResultPointsAndTransitionsComparator implements Comparator {
 335     public int compare(Object o1, Object o2) {
 336       return ((ResultPointsAndTransitions) o1).getTransitions() - ((ResultPointsAndTransitions) o2).getTransitions();
 337     }
 338   }
 339
 340 }