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