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