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