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.common.BitArray;
  20 import com.google.zxing.MonochromeBitmapSource;
  21
  22 /**
  23  * This class takes a bitmap, and attempts to return a String which is the contents of the UPC
  24  * barcode in the image. It should be scale-invariant, but does not make any corrections for
  25  * rotation or skew.
  26  *
  27  * @author dswitkin@google.com (Daniel Switkin)
  28  */
  29 final class UPCDecoder {
  30
  31   private static final byte[] BITMAP_SEARCH_PATTERN = { 50, 49, 51, 48, 52, 46, 54, 43, 57, 40, 60 };
  32   private static final byte[] START_END_PATTERN = { 1, 1, 1 };
  33   private static final byte[] MIDDLE_PATTERN = { 1, 1, 1, 1, 1 };
  34   private static final byte[][] DIGIT_PATTERNS = {
  35     { 30, 20, 10, 10 }, // 0
  36     { 20, 20, 20, 10 }, // 1
  37     { 20, 10, 20, 20 }, // 2
  38     { 10, 40, 10, 10 }, // 3
  39     { 10, 10, 30, 20 }, // 4
  40     { 10, 20, 30, 10 }, // 5
  41     { 10, 10, 10, 40 }, // 6
  42     { 10, 30, 10, 20 }, // 7
  43     { 10, 20, 10, 30 }, // 8
  44     { 30, 10, 10, 20 }  // 9
  45   };
  46   private static final int TOLERANCE = 5;
  47
  48   private MonochromeBitmapSource bitmap;
  49   private int width;
  50   private int height;
  51   private StringBuffer result;
  52
  53   UPCDecoder(MonochromeBitmapSource bitmap) {
  54           this.bitmap = bitmap;
  55     width = bitmap.getWidth();
  56     height = bitmap.getHeight();
  57   }
  58
  59   // To decode the image, we follow a search pattern defined in kBitmapSearchPattern. It is a
  60   // list of percentages which translate to row numbers to scan across. For each row, we scan
  61   // left to right, and if that fails, we reverse the row in place and try again to see if the
  62   // bar code was upside down.
  63   String decode() {
  64     BitArray rowData = new BitArray(width);
  65     String longestResult = "";
  66     int found = -1;
  67     for (int x = 0; x < BITMAP_SEARCH_PATTERN.length; x++) {
  68       int row = height * BITMAP_SEARCH_PATTERN[x] / 100;
  69       bitmap.getBlackRow(row, rowData, 0, width);
  70
  71       if (decodeRow(rowData)) {
  72         found = x;
  73         break;
  74       }
  75       //Log("decode: row " + row + " normal result: " + mResult);
  76       if (result.length() > longestResult.length()) {
  77         longestResult = result.toString();
  78       }
  79
  80       rowData.reverse();
  81       if (decodeRow(rowData)) {
  82         found = x;
  83         break;
  84       }
  85       //Log("decode: row " + row + " inverted result: " + mResult);
  86       if (result.length() > longestResult.length()) {
  87         longestResult = result.toString();
  88       }
  89     }
  90
  91     if (found >= 0) {
  92       return result.toString();
  93     } else {
  94       return "";
  95     }
  96   }
  97
  98   /**
  99    * UPC-A bar codes are made up of a left marker, six digits, a middle marker, six more digits,
 100    * and an end marker, reading from left to right. For more information, see:
 101    * <a href="http://en.wikipedia.org/wiki/Universal_Product_Code">
 102    * http://en.wikipedia.org/wiki/Universal_Product_Code</a>
 103    */
 104   private boolean decodeRow(BitArray rowData) {
 105     // TODO: Add support for UPC-E Zero Compressed bar codes.
 106     // TODO: Add support for EAN-13 (European Article Number) bar codes.
 107     // FIXME: Don't trust the first result from findPattern() for the start sequence - resume from
 108     // that spot and try to start again if finding digits fails.
 109     result = new StringBuffer();
 110     int rowOffset = findPattern(rowData, 0, START_END_PATTERN, false);
 111     if (rowOffset < 0) {
 112       return false;
 113     }
 114     //Log("Start pattern ends at column " + rowOffset);
 115
 116     rowOffset = decodeOneSide(rowData, rowOffset);
 117     if (rowOffset < 0) {
 118       return false;
 119     }
 120
 121     rowOffset = findPattern(rowData, rowOffset, MIDDLE_PATTERN, true);
 122     if (rowOffset < 0) {
 123       return false;
 124     }
 125     //Log("Middle pattern ends at column " + rowOffset);
 126
 127     rowOffset = decodeOneSide(rowData, rowOffset);
 128     if (rowOffset < 0) {
 129       return false;
 130     }
 131
 132     // We could attempt to read the end pattern for sanity, but there's not much point.
 133     // UPC-A codes have 12 digits, so any other result is garbage.
 134     return result.length() == 12;
 135   }
 136
 137   private int decodeOneSide(BitArray rowData, int rowOffset) {
 138     int[] counters = new int[4];
 139     for (int x = 0; x < 6 && rowOffset < width; x++) {
 140       recordPattern(rowData, rowOffset, counters, 4);
 141       for (int y = 0; y < 4; y++) {
 142         rowOffset += counters[y];
 143       }
 144       char c = findDigit(counters);
 145       if (c == '-') {
 146         return -1;
 147       } else {
 148         result.append(c);
 149       }
 150     }
 151     return rowOffset;
 152   }
 153
 154   // Returns the horizontal position just after the pattern was found if successful, otherwise
 155   // returns -1 if the pattern was not found. Searches are always left to right, and patterns
 156   // begin on white or black based on the flag.
 157   private int findPattern(BitArray rowData, int rowOffset, byte[] pattern, boolean whiteFirst) {
 158     int[] counters = new int[pattern.length];
 159     int width = this.width;
 160     boolean isWhite = false;
 161     while (rowOffset < width) {
 162       isWhite = !rowData.get(rowOffset);
 163       if (whiteFirst == isWhite) {
 164         break;
 165       }
 166       rowOffset++;
 167     }
 168
 169     int counterPosition = 0;
 170     for (int x = rowOffset; x < width; x++) {
 171       boolean pixel = rowData.get(x);
 172       if ((!pixel && isWhite) || (pixel && !isWhite)) {
 173         counters[counterPosition]++;
 174       } else {
 175         if (counterPosition == pattern.length - 1) {
 176           if (doesPatternMatch(counters, pattern)) {
 177             return x;
 178           }
 179           for (int y = 2; y < pattern.length; y++) {
 180             counters[y - 2] = counters[y];
 181           }
 182           counterPosition--;
 183         } else {
 184           counterPosition++;
 185         }
 186         counters[counterPosition] = 1;
 187         isWhite = !isWhite;
 188       }
 189     }
 190     return -1;
 191   }
 192
 193   /**
 194    * Records a pattern of alternating white and black pixels, returning an array of how many
 195    * pixels of each color were seen. The pattern begins immediately based on the color of the
 196    * first pixel encountered, so a patternSize of 3 could result in WBW or BWB.
 197    */
 198   private void recordPattern(BitArray rowData, int rowOffset, int[] counters, int patternSize) {
 199     for (int i = 0; i < counters.length; i++) {
 200       counters[i] = 0;
 201     }
 202     boolean isWhite = !rowData.get(rowOffset);
 203
 204     int counterPosition = 0;
 205     int width = this.width;
 206     for (int x = rowOffset; x < width; x++) {
 207       boolean pixel = rowData.get(x);
 208       if ((!pixel && isWhite) || (pixel && !isWhite)) {
 209         counters[counterPosition]++;
 210       } else {
 211         counterPosition++;
 212         if (counterPosition == patternSize) {
 213           return;
 214         } else {
 215           counters[counterPosition] = 1;
 216           isWhite = !isWhite;
 217         }
 218       }
 219     }
 220   }
 221
 222   /**
 223    * This is an optimized version of doesPatternMatch() which is specific to recognizing digits.
 224    * The average is divided by 7 because there are 7 bits per digit, even though the color only
 225    * alternates four times. kDigitPatterns has been premultiplied by 10 for efficiency. Notice
 226    * that the contents of the counters array are modified to save an extra allocation, so don't
 227    * use these values after returning from this call.
 228    */
 229   private static char findDigit(int[] counters) {
 230     // TODO: add EAN even parity support
 231     int total = counters[0] + counters[1] + counters[2] + counters[3];
 232     int average = total * 10 / 7;
 233     for (int x = 0; x < 4; x++) {
 234       counters[x] = counters[x] * 100 / average;
 235     }
 236
 237     for (int x = 0; x < 10; x++) {
 238       boolean match = true;
 239       for (int y = 0; y < 4; y++) {
 240         int diff = counters[y] - DIGIT_PATTERNS[x][y];
 241         if (diff > TOLERANCE || diff < -TOLERANCE) {
 242           match = false;
 243           break;
 244         }
 245       }
 246       if (match) {
 247         return (char) ((int) '0' + x);
 248       }
 249     }
 250     return '-';
 251   }
 252
 253   /**
 254    * Finds whether the given set of pixel counters matches the requested pattern. Taking an
 255    * average based on the number of counters offers some robustness when antialiased edges get
 256    * interpreted as the wrong color.
 257    */
 258   private static boolean doesPatternMatch(int[] counters, byte[] pattern) {
 259     // TODO: Remove the divide for performance.
 260     int total = 0;
 261     int numCounters = counters.length;
 262     for (int x = 0; x < numCounters; x++) {
 263       total += counters[x];
 264     }
 265     int average = total * 10 / counters.length;
 266
 267     for (int x = 0; x < numCounters; x++) {
 268       int scaledCounter = counters[x] * 100 / average;
 269       int scaledPattern = pattern[x] * 10;
 270       if (scaledCounter < scaledPattern - TOLERANCE || scaledCounter > scaledPattern + TOLERANCE) {
 271         return false;
 272       }
 273     }
 274     return true;
 275   }
 276
 277 }