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