core/src/com/google/zxing/pdf417/detector/Detector.java

   1 /*
   2  * Copyright 2009 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.pdf417.detector;
  18
  19 import com.google.zxing.BlackPointEstimationMethod;
  20 import com.google.zxing.MonochromeBitmapSource;
  21 import com.google.zxing.ReaderException;
  22 import com.google.zxing.ResultPoint;
  23 import com.google.zxing.common.BitArray;
  24 import com.google.zxing.common.BitMatrix;
  25 import com.google.zxing.common.DetectorResult;
  26 import com.google.zxing.common.GridSampler;
  27
  28 import java.util.Hashtable;
  29
  30 /**
  31  * <p>
  32  * Encapsulates logic that can detect a PDF417 Code in an image, even if the
  33  * PDF417 Code is rotated or skewed, or partially obscured.
  34  * </p>
  35  *
  36  * @author SITA Lab (kevin.osullivan@sita.aero)
  37  */
  38 public final class Detector {
  39
  40   public static final int MAX_AVG_VARIANCE = (int) ((1 << 8) * 0.42f);
  41   public static final int MAX_INDIVIDUAL_VARIANCE = (int) ((1 << 8) * 0.8f);
  42   // B S B S B S B S Bar/Space pattern
  43   private static final int[] START_PATTERN = {8, 1, 1, 1, 1, 1, 1, 3}; // 11111111
  44   // 0 1
  45   // 0 1
  46   // 0 1
  47   // 000
  48
  49   // B S B S B S B S B Bar/Space pattern
  50   private static final int[] STOP_PATTERN_REVERSE = {1, 2, 1, 1, 1, 3, 1, 1,
  51       7}; // 1111111 0 1 000 1 0 1 00 1
  52
  53   private final MonochromeBitmapSource image;
  54
  55   public Detector(MonochromeBitmapSource image) {
  56     this.image = image;
  57   }
  58
  59   /**
  60    * <p>
  61    * Detects a PDF417 Code in an image, simply.
  62    * </p>
  63    *
  64    * @return {@link DetectorResult} encapsulating results of detecting a PDF417
  65    *         Code
  66    * @throws ReaderException if no QR Code can be found
  67    */
  68   public DetectorResult detect() throws ReaderException {
  69     return detect(null);
  70   }
  71
  72   /**
  73    * <p>
  74    * Detects a PDF417 Code in an image, simply.
  75    * </p>
  76    *
  77    * @param hints optional hints to detector
  78    * @return {@link DetectorResult} encapsulating results of detecting a PDF417
  79    *         Code
  80    * @throws ReaderException if no PDF417 Code can be found
  81    */
  82   public DetectorResult detect(Hashtable hints) throws ReaderException {
  83     if (!BlackPointEstimationMethod.TWO_D_SAMPLING.equals(image
  84         .getLastEstimationMethod())) {
  85       image.estimateBlackPoint(BlackPointEstimationMethod.TWO_D_SAMPLING, 0);
  86     }
  87
  88     ResultPoint[] vertices = findVertices(image);
  89     if (vertices == null) { // Couldn't find the vertices
  90       // Maybe the image is rotated 180 degrees?
  91       vertices = findVertices180(image);
  92       /*
  93       * // Don't need this because the PDF417 code won't fit into // the
  94       * camera view finder when it is rotated. if (vertices == null) { //
  95       * Couldn't find the vertices // Maybe the image is rotated 90 degrees?
  96       * vertices = findVertices90(image); if (vertices == null) { //
  97       * Couldn't find the vertices // Maybe the image is rotated 270
  98       * degrees? vertices = findVertices270(image); } }
  99       */
 100     }
 101     if (vertices != null) {
 102       float moduleWidth = computeModuleWidth(vertices);
 103       if (moduleWidth < 1.0f) {
 104         throw ReaderException.getInstance();
 105       }
 106
 107       int dimension = computeDimension(vertices[4], vertices[6],
 108           vertices[5], vertices[7], moduleWidth);
 109
 110       // Deskew and sample image
 111       BitMatrix bits = sampleGrid(image, vertices[4], vertices[5],
 112           vertices[6], vertices[7], dimension);
 113       //bits.setModuleWidth(moduleWidth);
 114       return new DetectorResult(bits, new ResultPoint[]{vertices[4],
 115           vertices[5], vertices[6], vertices[7]});
 116     } else {
 117       throw ReaderException.getInstance();
 118     }
 119   }
 120
 121   /**
 122    * Locate the vertices and the codewords area of a black blob using the Start
 123    * and Stop patterns as locators.
 124    *
 125    * @param image the scanned barcode image.
 126    * @return the an array containing the vertices. vertices[0] x, y top left
 127    *         barcode vertices[1] x, y bottom left barcode vertices[2] x, y top
 128    *         right barcode vertices[3] x, y bottom right barcode vertices[4] x,
 129    *         y top left codeword area vertices[5] x, y bottom left codeword
 130    *         area vertices[6] x, y top right codeword area vertices[7] x, y
 131    *         bottom right codeword area
 132    */
 133   private static ResultPoint[] findVertices(MonochromeBitmapSource image) {
 134     int height = image.getHeight();
 135     int width = image.getWidth();
 136
 137     ResultPoint[] result = new ResultPoint[8];
 138     BitArray row = null;
 139     boolean found = false;
 140
 141     int[] loc = null;
 142     // Top Left
 143     for (int i = 0; i < height; i++) {
 144       row = image.getBlackRow(i, null, 0, width / 4);
 145       loc = findGuardPattern(row, 0, START_PATTERN);
 146       if (loc != null) {
 147         result[0] = new ResultPoint(loc[0], i);
 148         result[4] = new ResultPoint(loc[1], i);
 149         found = true;
 150         break;
 151       }
 152     }
 153     // Bottom left
 154     if (found) { // Found the Top Left vertex
 155       found = false;
 156       for (int i = height - 1; i > 0; i--) {
 157         row = image.getBlackRow(i, null, 0, width / 4);
 158         loc = findGuardPattern(row, 0, START_PATTERN);
 159         if (loc != null) {
 160           result[1] = new ResultPoint(loc[0], i);
 161           result[5] = new ResultPoint(loc[1], i);
 162           found = true;
 163           break;
 164         }
 165       }
 166     }
 167     // Top right
 168     if (found) { // Found the Bottom Left vertex
 169       found = false;
 170       for (int i = 0; i < height; i++) {
 171         row = image.getBlackRow(i, null, (width * 3) / 4, width / 4);
 172         row.reverse();
 173         loc = findGuardPattern(row, 0, STOP_PATTERN_REVERSE);
 174         if (loc != null) {
 175           result[2] = new ResultPoint(width - loc[0], i);
 176           result[6] = new ResultPoint(width - loc[1], i);
 177           found = true;
 178           break;
 179         }
 180       }
 181     }
 182     // Bottom right
 183     if (found) { // Found the Top right vertex
 184       found = false;
 185       for (int i = height - 1; i > 0; i--) {
 186         row = image.getBlackRow(i, null, (width * 3) / 4, width / 4);
 187         row.reverse();
 188         loc = findGuardPattern(row, 0, STOP_PATTERN_REVERSE);
 189         if (loc != null) {
 190           result[3] = new ResultPoint(width - loc[0], i);
 191           result[7] = new ResultPoint(width - loc[1], i);
 192           found = true;
 193           break;
 194         }
 195       }
 196     }
 197     return found ? result : null;
 198   }
 199
 200   /**
 201    * Locate the vertices and the codewords area of a black blob using the Start
 202    * and Stop patterns as locators. This assumes that the image is rotated 180
 203    * degrees and if it locates the start and stop patterns at it will re-map
 204    * the vertices for a 0 degree rotation.
 205    *
 206    * @param image the scanned barcode image.
 207    * @return the an array containing the vertices. vertices[0] x, y top left
 208    *         barcode vertices[1] x, y bottom left barcode vertices[2] x, y top
 209    *         right barcode vertices[3] x, y bottom right barcode vertices[4] x,
 210    *         y top left codeword area vertices[5] x, y bottom left codeword
 211    *         area vertices[6] x, y top right codeword area vertices[7] x, y
 212    *         bottom right codeword area
 213    */
 214   private static ResultPoint[] findVertices180(MonochromeBitmapSource image) {
 215     int height = image.getHeight();
 216     int width = image.getWidth();
 217
 218     ResultPoint[] result = new ResultPoint[8];
 219     BitArray row = null;
 220     boolean found = false;
 221
 222     int[] loc = null;
 223     // Top Left
 224     for (int i = height - 1; i > 0; i--) {
 225       row = image.getBlackRow(i, null, 0, width / 4);
 226       row.reverse();
 227       loc = findGuardPattern(row, 0, START_PATTERN);
 228       if (loc != null) {
 229         result[0] = new ResultPoint(width - loc[0], i);
 230         result[4] = new ResultPoint(width - loc[1], i);
 231         found = true;
 232         break;
 233       }
 234     }
 235     // Bottom Left
 236     if (found) { // Found the Top Left vertex
 237       found = false;
 238       for (int i = 0; i < height; i++) {
 239         row = image.getBlackRow(i, null, 0, width / 4);
 240         row.reverse();
 241         loc = findGuardPattern(row, 0, START_PATTERN);
 242         if (loc != null) {
 243           result[1] = new ResultPoint(width - loc[0], i);
 244           result[5] = new ResultPoint(width - loc[1], i);
 245           found = true;
 246           break;
 247         }
 248       }
 249     }
 250     // Top Right
 251     if (found) { // Found the Bottom Left vertex
 252       found = false;
 253       for (int i = height - 1; i > 0; i--) {
 254         row = image.getBlackRow(i, null, (width * 3) / 4, width / 4);
 255         loc = findGuardPattern(row, 0, STOP_PATTERN_REVERSE);
 256         if (loc != null) {
 257           result[2] = new ResultPoint(loc[0], i);
 258           result[6] = new ResultPoint(loc[1], i);
 259           found = true;
 260           break;
 261         }
 262       }
 263     }
 264     // Bottom Right
 265     if (found) { // Found the Top Right vertex
 266       found = false;
 267       for (int i = 0; i < height; i++) {
 268         row = image.getBlackRow(i, null, (width * 3) / 4, width / 4);
 269         loc = findGuardPattern(row, 0, STOP_PATTERN_REVERSE);
 270         if (loc != null) {
 271           result[3] = new ResultPoint(loc[0], i);
 272           result[7] = new ResultPoint(loc[1], i);
 273           found = true;
 274           break;
 275         }
 276       }
 277     }
 278     if (found) {
 279       return result;
 280     } else {
 281       return null;
 282     }
 283   }
 284
 285   /**
 286    * <p>
 287    * Estimates module size (pixels in a module) based on the Start and End
 288    * finder patterns.</p>
 289    *
 290    * @param vertices [] vertices[0] x, y top left barcode vertices[1] x, y bottom
 291    *                 left barcode vertices[2] x, y top right barcode vertices[3] x, y
 292    *                 bottom right barcode vertices[4] x, y top left Codeword area
 293    *                 vertices[5] x, y bottom left Codeword area vertices[6] x, y top
 294    *                 right Codeword area vertices[7] x, y bottom right Codeword area
 295    * @return the module size.
 296    */
 297   private static float computeModuleWidth(ResultPoint[] vertices) {
 298     float pixels1 = ResultPoint.distance(vertices[0], vertices[4]);
 299     float pixels2 = ResultPoint.distance(vertices[1], vertices[5]);
 300     float moduleWidth1 = (pixels1 + pixels2) / (17 * 2.0f);
 301     float pixels3 = ResultPoint.distance(vertices[6], vertices[2]);
 302     float pixels4 = ResultPoint.distance(vertices[7], vertices[3]);
 303     float moduleWidth2 = (pixels3 + pixels4) / (18 * 2.0f);
 304     return (moduleWidth1 + moduleWidth2) / 2.0f;
 305   }
 306
 307   /**
 308    * Computes the dimension (number of modules in a row) of the PDF417 Code
 309    * based on vertices of the codeword area and estimated module size.
 310    *
 311    * @param topLeft     of codeword area
 312    * @param topRight    of codeword area
 313    * @param bottomLeft  of codeword area
 314    * @param bottomRight of codeword are
 315    * @param moduleWidth estimated module size
 316    * @return the number of modules in a row.
 317    */
 318   private static int computeDimension(ResultPoint topLeft,
 319                                       ResultPoint topRight, ResultPoint bottomLeft, ResultPoint bottomRight,
 320                                       float moduleWidth) {
 321
 322     int topRowDimension = round(ResultPoint
 323         .distance(topLeft, topRight)
 324         / moduleWidth);
 325     int bottomRowDimension = round(ResultPoint.distance(bottomLeft,
 326         bottomRight)
 327         / moduleWidth);
 328     return ((((topRowDimension + bottomRowDimension) >> 1) + 8) / 17) * 17;
 329     /*
 330     * int topRowDimension = round(ResultPoint.distance(topLeft,
 331     * topRight)); //moduleWidth); int bottomRowDimension =
 332     * round(ResultPoint.distance(bottomLeft, bottomRight)); //
 333     * moduleWidth); int dimension = ((topRowDimension + bottomRowDimension)
 334     * >> 1); // Round up to nearest 17 modules i.e. there are 17 modules per
 335     * codeword //int dimension = ((((topRowDimension + bottomRowDimension) >>
 336     * 1) + 8) / 17) * 17; return dimension;
 337     */
 338   }
 339
 340   private static BitMatrix sampleGrid(MonochromeBitmapSource image,
 341                                       ResultPoint topLeft, ResultPoint bottomLeft, ResultPoint topRight,
 342                                       ResultPoint bottomRight, int dimension) throws ReaderException {
 343
 344     // Note that unlike in the QR Code sampler, we didn't find the center of
 345     // modules, but the
 346     // very corners. So there is no 0.5f here; 0.0f is right.
 347     GridSampler sampler = GridSampler.getInstance();
 348     return sampler.sampleGrid(image, dimension, 0.0f, // p1ToX
 349         0.0f, // p1ToY
 350         dimension, // p2ToX
 351         0.0f, // p2ToY
 352         dimension, // p3ToX
 353         dimension, // p3ToY
 354         0.0f, // p4ToX
 355         dimension, // p4ToY
 356         topLeft.getX(), // p1FromX
 357         topLeft.getY(), // p1FromY
 358         topRight.getX(), // p2FromX
 359         topRight.getY(), // p2FromY
 360         bottomRight.getX(), // p3FromX
 361         bottomRight.getY(), // p3FromY
 362         bottomLeft.getX(), // p4FromX
 363         bottomLeft.getY()); // p4FromY
 364
 365   }
 366
 367   /**
 368    * Ends up being a bit faster than Math.round(). This merely rounds its
 369    * argument to the nearest int, where x.5 rounds up.
 370    */
 371   private static int round(float d) {
 372     return (int) (d + 0.5f);
 373   }
 374
 375   /**
 376    * @param row       row of black/white values to search
 377    * @param rowOffset position to start search
 378    * @param pattern   pattern of counts of number of black and white pixels that are
 379    *                  being searched for as a pattern
 380    * @return start/end horizontal offset of guard pattern, as an array of two
 381    *         ints.
 382    */
 383   static int[] findGuardPattern(BitArray row, int rowOffset, int[] pattern) {
 384     int patternLength = pattern.length;
 385     int[] counters = new int[patternLength];
 386     int width = row.getSize();
 387     boolean isWhite = false;
 388
 389     int counterPosition = 0;
 390     int patternStart = rowOffset;
 391     for (int x = rowOffset; x < width; x++) {
 392       boolean pixel = row.get(x);
 393       if (pixel ^ isWhite) {
 394         counters[counterPosition]++;
 395       } else {
 396         if (counterPosition == patternLength - 1) {
 397           if (patternMatchVariance(counters, pattern,
 398               MAX_INDIVIDUAL_VARIANCE) < MAX_AVG_VARIANCE) {
 399             return new int[]{patternStart, x};
 400           }
 401           patternStart += counters[0] + counters[1];
 402           for (int y = 2; y < patternLength; y++) {
 403             counters[y - 2] = counters[y];
 404           }
 405           counters[patternLength - 2] = 0;
 406           counters[patternLength - 1] = 0;
 407           counterPosition--;
 408         } else {
 409           counterPosition++;
 410         }
 411         counters[counterPosition] = 1;
 412         isWhite = !isWhite;
 413       }
 414     }
 415     return null;
 416   }
 417
 418   /**
 419    * Determines how closely a set of observed counts of runs of black/white
 420    * values matches a given target pattern. This is reported as the ratio of
 421    * the total variance from the expected pattern proportions across all
 422    * pattern elements, to the length of the pattern.
 423    *
 424    * @param counters              observed counters
 425    * @param pattern               expected pattern
 426    * @param maxIndividualVariance The most any counter can differ before we give up
 427    * @return ratio of total variance between counters and pattern compared to
 428    *         total pattern size, where the ratio has been multiplied by 256.
 429    *         So, 0 means no variance (perfect match); 256 means the total
 430    *         variance between counters and patterns equals the pattern length,
 431    *         higher values mean even more variance
 432    */
 433   public static int patternMatchVariance(int[] counters, int[] pattern,
 434                                          int maxIndividualVariance) {
 435     int numCounters = counters.length;
 436     int total = 0;
 437     int patternLength = 0;
 438     for (int i = 0; i < numCounters; i++) {
 439       total += counters[i];
 440       patternLength += pattern[i];
 441     }
 442     if (total < patternLength) {
 443       // If we don't even have one pixel per unit of bar width, assume this
 444       // is too small
 445       // to reliably match, so fail:
 446       return Integer.MAX_VALUE;
 447     }
 448     // We're going to fake floating-point math in integers. We just need to
 449     // use more bits.
 450     // Scale up patternLength so that intermediate values below like
 451     // scaledCounter will have
 452     // more "significant digits"
 453     int unitBarWidth = (total << 8) / patternLength;
 454     maxIndividualVariance = (maxIndividualVariance * unitBarWidth) >> 8;
 455
 456     int totalVariance = 0;
 457     for (int x = 0; x < numCounters; x++) {
 458       int counter = counters[x] << 8;
 459       int scaledPattern = pattern[x] * unitBarWidth;
 460       int variance = counter > scaledPattern ? counter - scaledPattern
 461           : scaledPattern - counter;
 462       if (variance > maxIndividualVariance) {
 463         return Integer.MAX_VALUE;
 464       }
 465       totalVariance += variance;
 466     }
 467     return totalVariance / total;
 468   }
 469
 470 }