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.common.BitArray;
  21 import com.google.zxing.MonochromeBitmapSource;
  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   private static class CharResult {
 105     public char character;   // the encoded character
 106     public int parity;       // one of the parity types above
 107   }
 108
 109   private static final int TOLERANCE = 5;
 110
 111   private MonochromeBitmapSource bitmap;
 112   private int width;
 113   private int height;
 114   private StringBuffer result;
 115
 116   UPCDecoder(MonochromeBitmapSource bitmap) {
 117           this.bitmap = bitmap;
 118     width = bitmap.getWidth();
 119     height = bitmap.getHeight();
 120   }
 121
 122   // To decode the image, we follow a search pattern defined in kBitmapSearchPattern. It is a
 123   // list of percentages which translate to row numbers to scan across. For each row, we scan
 124   // left to right, and if that fails, we reverse the row in place and try again to see if the
 125   // bar code was upside down.
 126   String decode() {
 127     BitArray rowData = new BitArray(width);
 128     String longestResult = "";
 129     int found = -1;
 130     for (int x = 0; x < BITMAP_SEARCH_PATTERN.length; x++) {
 131       int row = height * BITMAP_SEARCH_PATTERN[x] / 100;
 132       bitmap.estimateBlackPoint(BlackPointEstimationMethod.ROW_SAMPLING, row);
 133       bitmap.getBlackRow(row, rowData, 0, width);
 134
 135       if (decodeRow(rowData)) {
 136         found = x;
 137         break;
 138       }
 139       //Log("decode: row " + row + " normal result: " + result);
 140       if (result.length() > longestResult.length()) {
 141         longestResult = result.toString();
 142       }
 143
 144       rowData.reverse();
 145       if (decodeRow(rowData)) {
 146         found = x;
 147         break;
 148       }
 149       //Log("decode: row " + row + " inverted result: " + result);
 150       if (result.length() > longestResult.length()) {
 151         longestResult = result.toString();
 152       }
 153     }
 154
 155     if (found >= 0) {
 156       return result.toString();
 157     } else {
 158       return "";
 159     }
 160   }
 161
 162   /**
 163    * UPC-A bar codes are made up of a left marker, six digits, a middle marker, six more digits,
 164    * and an end marker, reading from left to right. For more information, see:
 165    * <a href="http://en.wikipedia.org/wiki/Universal_Product_Code">
 166    * http://en.wikipedia.org/wiki/Universal_Product_Code</a>
 167    */
 168   private boolean decodeRow(BitArray rowData) {
 169     // TODO: Add support for UPC-E Zero Compressed bar codes.
 170     // FIXME: Don't trust the first result from findPattern() for the start sequence - resume from
 171     // that spot and try to start again if finding digits fails.
 172     result = new StringBuffer();
 173     int rowOffset = findPattern(rowData, 0, START_END_PATTERN, false);
 174     if (rowOffset < 0) {
 175       return false;
 176     }
 177     //Log("Start pattern ends at column " + rowOffset);
 178
 179     rowOffset = decodeOneSide(rowData, rowOffset, true);
 180     if (rowOffset < 0) {
 181       return false;
 182     }
 183
 184     rowOffset = findPattern(rowData, rowOffset, MIDDLE_PATTERN, true);
 185     if (rowOffset < 0) {
 186       return false;
 187     }
 188     //Log("Middle pattern ends at column " + rowOffset);
 189
 190     // Pass in false for checkBothParities(). For an EAN-13 barcode, only the
 191     // left had side will use mixed parities.
 192     rowOffset = decodeOneSide(rowData, rowOffset, false);
 193     if (rowOffset < 0) {
 194       return false;
 195     }
 196     return verifyResult();
 197   }
 198
 199
 200   // Verifies the checksum. This is computed by adding up digits in the even
 201   // indices (0, 2, 4...) then adding the digits in the odd indices (1, 3, 5..)
 202   // and multiplying by 3. The total, plus the final checksum digit, should be
 203   // divisible by 10.
 204   //
 205   // Note that for a UPC barcode, we add the additional '0' to the front
 206   // (converting it to a EAN-13 code) for purposes of calculating the checksum
 207   //
 208   private boolean verifyResult() {
 209     // TODO - handle compressed barcodes.
 210
 211     // length is 12 for UPC and 13 for EAN-13
 212     if (result.length() != 12 && result.length() != 13)
 213       return false;
 214
 215     int checksum = 0;
 216     int end = result.length()-2;
 217     int factor = 3;
 218     // Calculate from penultimate digit down to first. This avoids having to
 219     // account for the optional '0' on the front, which won't actually affect
 220     // the calculation.
 221     for (int i = end; i >= 0; i--) {
 222       int value = (result.charAt(i) - (int) '0') * factor;
 223       checksum += value;
 224       factor = factor == 3 ? 1 : 3;
 225     }
 226     int endValue = (result.charAt(end+1) - (int) '0');
 227     //Log("checksum + endValue = " + (checksum + endValue));
 228     return (checksum + endValue) % 10 == 0;
 229   }
 230
 231   private int decodeOneSide(BitArray rowData, int rowOffset, boolean checkBothParities) {
 232     int[] counters = new int[4];
 233     byte firstDigitPattern = 0;
 234     char firstDigit = '-';
 235     for (int x = 0; x < 6 && rowOffset < width; x++) {
 236       recordPattern(rowData, rowOffset, counters, 4);
 237       for (int y = 0; y < 4; y++) {
 238         rowOffset += counters[y];
 239       }
 240       CharResult foundChar = new CharResult();
 241       findDigit(counters, foundChar, checkBothParities);
 242       if (foundChar.parity == UNKNOWN_PARITY)
 243         return -1;
 244       if (foundChar.parity == EVEN_PARITY)
 245         firstDigitPattern |= 1 << (5-x);
 246       result.append(foundChar.character);
 247     }
 248     for (int i = 0; i < FIRST_DIGIT_ENCODINGS.length; i++) {
 249       if (firstDigitPattern == FIRST_DIGIT_ENCODINGS[i]) {
 250         firstDigit = (char) ((int) '0' + i);
 251         break;
 252       }
 253     }
 254     if (firstDigit == '-')
 255       return -1;
 256     if (firstDigit != '0')
 257       result.insert(0, firstDigit);
 258     return rowOffset;
 259   }
 260
 261   // Returns the horizontal position just after the pattern was found if successful, otherwise
 262   // returns -1 if the pattern was not found. Searches are always left to right, and patterns
 263   // begin on white or black based on the flag.
 264   private int findPattern(BitArray rowData, int rowOffset, byte[] pattern, boolean whiteFirst) {
 265     int[] counters = new int[pattern.length];
 266     int width = this.width;
 267     boolean isWhite = false;
 268     while (rowOffset < width) {
 269       isWhite = !rowData.get(rowOffset);
 270       if (whiteFirst == isWhite) {
 271         break;
 272       }
 273       rowOffset++;
 274     }
 275
 276     int counterPosition = 0;
 277     for (int x = rowOffset; x < width; x++) {
 278       boolean pixel = rowData.get(x);
 279       if ((!pixel && isWhite) || (pixel && !isWhite)) {
 280         counters[counterPosition]++;
 281       } else {
 282         if (counterPosition == pattern.length - 1) {
 283           if (doesPatternMatch(counters, pattern)) {
 284             return x;
 285           }
 286           for (int y = 2; y < pattern.length; y++) {
 287             counters[y - 2] = counters[y];
 288           }
 289           counterPosition--;
 290         } else {
 291           counterPosition++;
 292         }
 293         counters[counterPosition] = 1;
 294         isWhite = !isWhite;
 295       }
 296     }
 297     return -1;
 298   }
 299
 300   /**
 301    * Records a pattern of alternating white and black pixels, returning an array of how many
 302    * pixels of each color were seen. The pattern begins immediately based on the color of the
 303    * first pixel encountered, so a patternSize of 3 could result in WBW or BWB.
 304    */
 305   private void recordPattern(BitArray rowData, int rowOffset, int[] counters, int patternSize) {
 306     for (int i = 0; i < counters.length; i++) {
 307       counters[i] = 0;
 308     }
 309     boolean isWhite = !rowData.get(rowOffset);
 310
 311     int counterPosition = 0;
 312     int width = this.width;
 313     for (int x = rowOffset; x < width; x++) {
 314       boolean pixel = rowData.get(x);
 315       if ((!pixel && isWhite) || (pixel && !isWhite)) {
 316         counters[counterPosition]++;
 317       } else {
 318         counterPosition++;
 319         if (counterPosition == patternSize) {
 320           return;
 321         } else {
 322           counters[counterPosition] = 1;
 323           isWhite = !isWhite;
 324         }
 325       }
 326     }
 327   }
 328
 329   /**
 330    * This is an optimized version of doesPatternMatch() which is specific to recognizing digits.
 331    * The average is divided by 7 because there are 7 bits per digit, even though the color only
 332    * alternates four times. kDigitPatterns has been premultiplied by 10 for efficiency. Notice
 333    * that the contents of the counters array are modified to save an extra allocation, so don't
 334    * use these values after returning from this call.
 335    */
 336   private static void findDigit(int[] counters, CharResult result, boolean checkBothParities) {
 337     result.parity = UNKNOWN_PARITY;
 338     int total = counters[0] + counters[1] + counters[2] + counters[3];
 339     int average = total * 10 / 7;
 340     for (int x = 0; x < 4; x++) {
 341       counters[x] = counters[x] * 100 / average;
 342     }
 343
 344     for (int x = 0; x < 10; x++) {
 345       boolean match = true;
 346       for (int y = 0; y < 4; y++) {
 347         int diff = counters[y] - DIGIT_PATTERNS[x][y];
 348         if (diff > TOLERANCE || diff < -TOLERANCE) {
 349           match = false;
 350           break;
 351         }
 352       }
 353       if (match) {
 354         result.parity = ODD_PARITY;
 355         result.character =  (char) ((int) '0' + x);
 356         return;
 357       }
 358     }
 359     // If first pattern didn't match, look for even parity patterns, as used in
 360     // EAN-13 barcodes.
 361     if (checkBothParities) {
 362       for (int x = 0; x < 10; x++) {
 363         boolean match = true;
 364         for (int y = 0; y < 4; y++) {
 365           int diff = counters[y] - EVEN_PARITY_PATTERNS[x][y];
 366           if (diff > TOLERANCE || diff < -TOLERANCE) {
 367             match = false;
 368             break;
 369           }
 370         }
 371         if (match) {
 372           result.parity = EVEN_PARITY;
 373           result.character =  (char) ((int) '0' + x);
 374           return;
 375         }
 376       }
 377     }
 378   }
 379
 380   /**
 381    * Finds whether the given set of pixel counters matches the requested pattern. Taking an
 382    * average based on the number of counters offers some robustness when antialiased edges get
 383    * interpreted as the wrong color.
 384    */
 385   private static boolean doesPatternMatch(int[] counters, byte[] pattern) {
 386     // TODO: Remove the divide for performance.
 387     int total = 0;
 388     int numCounters = counters.length;
 389     for (int x = 0; x < numCounters; x++) {
 390       total += counters[x];
 391     }
 392     int average = total * 10 / counters.length;
 393
 394     for (int x = 0; x < numCounters; x++) {
 395       int scaledCounter = counters[x] * 100 / average;
 396       int scaledPattern = pattern[x] * 10;
 397       if (scaledCounter < scaledPattern - TOLERANCE || scaledCounter > scaledPattern + TOLERANCE) {
 398         return false;
 399       }
 400     }
 401     return true;
 402   }
 403
 404 }