core/src/com/google/zxing/upc/UPCDecoder.java

   1 /*
   2  * Copyright 2007 Google Inc.
   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.upc;
  18
  19 import com.google.zxing.BlackPointEstimationMethod;
  20 import com.google.zxing.MonochromeBitmapSource;
  21 import com.google.zxing.common.BitArray;
  22
  23 /**
  24  * This class takes a bitmap, and attempts to return a String which is the contents of the UPC
  25  * barcode in the image. It should be scale-invariant, but does not make any corrections for
  26  * rotation or skew.
  27  *
  28  * @author dswitkin@google.com (Daniel Switkin)
  29  */
  30 final class UPCDecoder {
  31
  32   private static final byte[] BITMAP_SEARCH_PATTERN = { 50, 49, 51, 48, 52, 46, 54, 43, 57, 40, 60 };
  33   private static final byte[] START_END_PATTERN = { 1, 1, 1 };
  34   private static final byte[] MIDDLE_PATTERN = { 1, 1, 1, 1, 1 };
  35   private static final byte[][] DIGIT_PATTERNS = {
  36     { 30, 20, 10, 10 }, // 0
  37     { 20, 20, 20, 10 }, // 1
  38     { 20, 10, 20, 20 }, // 2
  39     { 10, 40, 10, 10 }, // 3
  40     { 10, 10, 30, 20 }, // 4
  41     { 10, 20, 30, 10 }, // 5
  42     { 10, 10, 10, 40 }, // 6
  43     { 10, 30, 10, 20 }, // 7
  44     { 10, 20, 10, 30 }, // 8
  45     { 30, 10, 10, 20 }  // 9
  46   };
  47
  48   /** Alternative even-parity patterns for EAN-13 barcodes. */
  49   private static final byte[][] EVEN_PARITY_PATTERNS = {
  50     { 10, 10, 20, 30 }, // 0
  51     { 10, 20, 20, 20 }, // 1
  52     { 20, 20, 10, 20 }, // 2
  53     { 10, 10, 40, 10 }, // 3
  54     { 20, 30, 10, 10 }, // 4
  55     { 10, 30, 20, 10 }, // 5
  56     { 40, 10, 10, 10 }, // 6
  57     { 20, 10, 30, 10 }, // 7
  58     { 30, 10, 20, 10 }, // 8
  59     { 20, 10, 10, 30 }  // 9
  60   };
  61
  62   // For an EAN-13 barcode, the first digit is represented by the parities used
  63   // to encode the next six digits, according to the table below. For example,
  64   // if the barcode is 5 123456 789012 then the value of the first digit is
  65   // signified by using odd for '1', even for '2', even for '3', odd for '4',
  66   // odd for '5', and even for '6'. See http://en.wikipedia.org/wiki/EAN-13
  67   //
  68   //                Parity of next 6 digits
  69   //    Digit   0     1     2     3     4     5
  70   //       0    Odd   Odd   Odd   Odd   Odd   Odd
  71   //       1    Odd   Odd   Even  Odd   Even  Even
  72   //       2    Odd   Odd   Even  Even  Odd   Even
  73   //       3    Odd   Odd   Even  Even  Even  Odd
  74   //       4    Odd   Even  Odd   Odd   Even  Even
  75   //       5    Odd   Even  Even  Odd   Odd   Even
  76   //       6    Odd   Even  Even  Even  Odd   Odd
  77   //       7    Odd   Even  Odd   Even  Odd   Even
  78   //       8    Odd   Even  Odd   Even  Even  Odd
  79   //       9    Odd   Even  Even  Odd   Even  Odd
  80   //
  81   // Note that the encoding for '0' uses the same parity as a UPC barcode. Hence
  82   // a UPC barcode can be converted to an EAN-13 barcode by prepending a 0.
  83   //
  84   // The encodong is represented by the following array, which is a bit pattern
  85   // using Odd = 0 and Even = 1. For example, 5 is represented by:
  86   //
  87   //              Odd Even Even Odd Odd Even
  88   // in binary:
  89   //                0    1    1   0   0    1   == 0x19
  90   //
  91   private static final byte[] FIRST_DIGIT_ENCODINGS = {
  92     0x00, 0x0B, 0x0D, 0xE, 0x13, 0x19, 0x1C, 0x15, 0x16, 0x1A
  93   };
  94
  95
  96   // Parity types indicating how a given digit is encoded
  97   private static final int UNKNOWN_PARITY  = 0;
  98   private static final int ODD_PARITY      = 1;
  99   private static final int EVEN_PARITY     = 2;
 100
 101   /**
 102    * Utility class for returning a matched character. Defines the character
 103    * plus the parity used for encoding it.
 104    */
 105   private static class CharResult {
 106     public char character;   // the encoded character
 107     public int parity;       // one of the parity types above
 108   }
 109
 110   private static final int TOLERANCE = 5;
 111
 112   private MonochromeBitmapSource bitmap;
 113   private int width;
 114   private int height;
 115   private StringBuffer result;
 116
 117   UPCDecoder(MonochromeBitmapSource bitmap) {
 118           this.bitmap = bitmap;
 119     width = bitmap.getWidth();
 120     height = bitmap.getHeight();
 121   }
 122
 123   /**
 124    * To decode the image, we follow a search pattern defined in kBitmapSearchPattern. It is a
 125    * list of percentages which translate to row numbers to scan across. For each row, we scan
 126    * left to right, and if that fails, we reverse the row in place and try again to see if the
 127    * bar code was upside down.
 128    */
 129   String decode() {
 130     BitArray rowData = new BitArray(width);
 131     String longestResult = "";
 132     int found = -1;
 133     for (int x = 0; x < BITMAP_SEARCH_PATTERN.length; x++) {
 134       int row = height * BITMAP_SEARCH_PATTERN[x] / 100;
 135       bitmap.estimateBlackPoint(BlackPointEstimationMethod.ROW_SAMPLING, row);
 136       bitmap.getBlackRow(row, rowData, 0, width);
 137
 138       if (decodeRow(rowData)) {
 139         found = x;
 140         break;
 141       }
 142       //Log("decode: row " + row + " normal result: " + result);
 143       if (result.length() > longestResult.length()) {
 144         longestResult = result.toString();
 145       }
 146
 147       rowData.reverse();
 148       if (decodeRow(rowData)) {
 149         found = x;
 150         break;
 151       }
 152       //Log("decode: row " + row + " inverted result: " + result);
 153       if (result.length() > longestResult.length()) {
 154         longestResult = result.toString();
 155       }
 156     }
 157
 158     if (found >= 0) {
 159       return result.toString();
 160     } else {
 161       return "";
 162     }
 163   }
 164
 165   /**
 166    * UPC-A bar codes are made up of a left marker, six digits, a middle marker, six more digits,
 167    * and an end marker, reading from left to right. For more information, see:
 168    * <a href="http://en.wikipedia.org/wiki/Universal_Product_Code">
 169    * http://en.wikipedia.org/wiki/Universal_Product_Code</a>
 170    */
 171   private boolean decodeRow(BitArray rowData) {
 172     // TODO: Add support for UPC-E Zero Compressed bar codes.
 173     // FIXME: Don't trust the first result from findPattern() for the start sequence - resume from
 174     // that spot and try to start again if finding digits fails.
 175     result = new StringBuffer();
 176     int rowOffset = findPattern(rowData, 0, START_END_PATTERN, false);
 177     if (rowOffset < 0) {
 178       return false;
 179     }
 180     //Log("Start pattern ends at column " + rowOffset);
 181
 182     rowOffset = decodeOneSide(rowData, rowOffset, true);
 183     if (rowOffset < 0) {
 184       return false;
 185     }
 186
 187     rowOffset = findPattern(rowData, rowOffset, MIDDLE_PATTERN, true);
 188     if (rowOffset < 0) {
 189       return false;
 190     }
 191     //Log("Middle pattern ends at column " + rowOffset);
 192
 193     // Pass in false for checkBothParities(). For an EAN-13 barcode, only the
 194     // left had side will use mixed parities.
 195     rowOffset = decodeOneSide(rowData, rowOffset, false);
 196     if (rowOffset < 0) {
 197       return false;
 198     }
 199     return verifyResult();
 200   }
 201
 202
 203   /**
 204    * Verifies the checksum. This is computed by adding up digits in the even
 205    * indices (0, 2, 4...) then adding the digits in the odd indices (1, 3, 5..)
 206    * and multiplying by 3. The total, plus the final checksum digit, should be
 207    * divisible by 10.
 208    *
 209    * Note that for a UPC barcode, we add the additional '0' to the front
 210    * (converting it to a EAN-13 code) for purposes of calculating the checksum
 211    */
 212   private boolean verifyResult() {
 213     // TODO - handle compressed barcodes.
 214
 215     // length is 12 for UPC and 13 for EAN-13
 216     if (result.length() != 12 && result.length() != 13) {
 217       return false;
 218     }
 219
 220     int checksum = 0;
 221     int end = result.length() - 2;
 222     int factor = 3;
 223     // Calculate from penultimate digit down to first. This avoids having to
 224     // account for the optional '0' on the front, which won't actually affect
 225     // the calculation.
 226     for (int i = end; i >= 0; i--) {
 227       int value = (result.charAt(i) - (int)'0') * factor;
 228       checksum += value;
 229       factor = factor == 3 ? 1 : 3;
 230     }
 231     int endValue = (result.charAt(end + 1) - (int)'0');
 232     //Log("checksum + endValue = " + (checksum + endValue));
 233     return (checksum + endValue) % 10 == 0;
 234   }
 235
 236   private int decodeOneSide(BitArray rowData, int rowOffset, boolean checkBothParities) {
 237     int[] counters = new int[4];
 238     byte firstDigitPattern = 0;
 239     CharResult foundChar = new CharResult();
 240     for (int x = 0; x < 6 && rowOffset < width; x++) {
 241       recordPattern(rowData, rowOffset, counters, 4);
 242       for (int y = 0; y < 4; y++) {
 243         rowOffset += counters[y];
 244       }
 245       findDigit(counters, foundChar, checkBothParities);
 246       if (foundChar.parity == UNKNOWN_PARITY) {
 247         return -1;
 248       }
 249       if (foundChar.parity == EVEN_PARITY) {
 250         firstDigitPattern |= 1 << (5 - x);
 251       }
 252       result.append(foundChar.character);
 253     }
 254     // If checkBothParities is true then we're potentially looking at the left
 255     // hand side of an EAN-13 barcode, where the first digit is encoded by the
 256     // parity pattern. In that case, calculate the first digit by checking
 257     // the parity patterns.
 258     if (checkBothParities) {
 259       char firstDigit = '-';
 260       for (int i = 0; i < FIRST_DIGIT_ENCODINGS.length; i++) {
 261         if (firstDigitPattern == FIRST_DIGIT_ENCODINGS[i]) {
 262           firstDigit = (char)((int)'0' + i);
 263           break;
 264         }
 265       }
 266       if (firstDigit == '-') {
 267         return -1;
 268       }
 269       if (firstDigit != '0') {
 270         result.insert(0, firstDigit);
 271       }
 272     }
 273     return rowOffset;
 274   }
 275
 276   /**
 277    * Returns the horizontal position just after the pattern was found if successful, otherwise
 278    * returns -1 if the pattern was not found. Searches are always left to right, and patterns
 279    * begin on white or black based on the flag.
 280    */
 281   private int findPattern(BitArray rowData, int rowOffset, byte[] pattern, boolean whiteFirst) {
 282     int[] counters = new int[pattern.length];
 283     int width = this.width;
 284     boolean isWhite = false;
 285     while (rowOffset < width) {
 286       isWhite = !rowData.get(rowOffset);
 287       if (whiteFirst == isWhite) {
 288         break;
 289       }
 290       rowOffset++;
 291     }
 292
 293     int counterPosition = 0;
 294     for (int x = rowOffset; x < width; x++) {
 295       boolean pixel = rowData.get(x);
 296       if ((!pixel && isWhite) || (pixel && !isWhite)) {
 297         counters[counterPosition]++;
 298       } else {
 299         if (counterPosition == pattern.length - 1) {
 300           if (doesPatternMatch(counters, pattern)) {
 301             return x;
 302           }
 303           for (int y = 2; y < pattern.length; y++) {
 304             counters[y - 2] = counters[y];
 305           }
 306           counterPosition--;
 307         } else {
 308           counterPosition++;
 309         }
 310         counters[counterPosition] = 1;
 311         isWhite = !isWhite;
 312       }
 313     }
 314     return -1;
 315   }
 316
 317   /**
 318    * Records a pattern of alternating white and black pixels, returning an array of how many
 319    * pixels of each color were seen. The pattern begins immediately based on the color of the
 320    * first pixel encountered, so a patternSize of 3 could result in WBW or BWB.
 321    */
 322   private void recordPattern(BitArray rowData, int rowOffset, int[] counters, int patternSize) {
 323     for (int i = 0; i < counters.length; i++) {
 324       counters[i] = 0;
 325     }
 326     boolean isWhite = !rowData.get(rowOffset);
 327
 328     int counterPosition = 0;
 329     int width = this.width;
 330     for (int x = rowOffset; x < width; x++) {
 331       boolean pixel = rowData.get(x);
 332       if ((!pixel && isWhite) || (pixel && !isWhite)) {
 333         counters[counterPosition]++;
 334       } else {
 335         counterPosition++;
 336         if (counterPosition == patternSize) {
 337           return;
 338         } else {
 339           counters[counterPosition] = 1;
 340           isWhite = !isWhite;
 341         }
 342       }
 343     }
 344   }
 345
 346   /**
 347    * This is an optimized version of doesPatternMatch() which is specific to recognizing digits.
 348    * The average is divided by 7 because there are 7 bits per digit, even though the color only
 349    * alternates four times. kDigitPatterns has been premultiplied by 10 for efficiency. Notice
 350    * that the contents of the counters array are modified to save an extra allocation, so don't
 351    * use these values after returning from this call.
 352    */
 353   private static void findDigit(int[] counters, CharResult result, boolean checkBothParities) {
 354     result.parity = UNKNOWN_PARITY;
 355     int total = counters[0] + counters[1] + counters[2] + counters[3];
 356     int average = total * 10 / 7;
 357     for (int x = 0; x < 4; x++) {
 358       counters[x] = counters[x] * 100 / average;
 359     }
 360
 361     for (int x = 0; x < 10; x++) {
 362       boolean match = true;
 363       for (int y = 0; y < 4; y++) {
 364         int diff = counters[y] - DIGIT_PATTERNS[x][y];
 365         if (diff > TOLERANCE || diff < -TOLERANCE) {
 366           match = false;
 367           break;
 368         }
 369       }
 370       if (match) {
 371         result.parity = ODD_PARITY;
 372         result.character =  (char)((int)'0' + x);
 373         return;
 374       }
 375     }
 376     // If first pattern didn't match, look for even parity patterns, as used in
 377     // EAN-13 barcodes.
 378     if (checkBothParities) {
 379       for (int x = 0; x < 10; x++) {
 380         boolean match = true;
 381         for (int y = 0; y < 4; y++) {
 382           int diff = counters[y] - EVEN_PARITY_PATTERNS[x][y];
 383           if (diff > TOLERANCE || diff < -TOLERANCE) {
 384             match = false;
 385             break;
 386           }
 387         }
 388         if (match) {
 389           result.parity = EVEN_PARITY;
 390           result.character =  (char)((int)'0' + x);
 391           return;
 392         }
 393       }
 394     }
 395   }
 396
 397   /**
 398    * Finds whether the given set of pixel counters matches the requested pattern. Taking an
 399    * average based on the number of counters offers some robustness when antialiased edges get
 400    * interpreted as the wrong color.
 401    */
 402   private static boolean doesPatternMatch(int[] counters, byte[] pattern) {
 403     // TODO: Remove the divide for performance.
 404     int total = 0;
 405     int numCounters = counters.length;
 406     for (int x = 0; x < numCounters; x++) {
 407       total += counters[x];
 408     }
 409     int average = total * 10 / counters.length;
 410
 411     for (int x = 0; x < numCounters; x++) {
 412       int scaledCounter = counters[x] * 100 / average;
 413       int scaledPattern = pattern[x] * 10;
 414       if (scaledCounter < scaledPattern - TOLERANCE || scaledCounter > scaledPattern + TOLERANCE) {
 415         return false;
 416       }
 417     }
 418     return true;
 419   }
 420
 421 }