2 * Copyright 2007 Google Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 package com.google.zxing.upc;
19 import com.google.zxing.BlackPointEstimationMethod;
20 import com.google.zxing.MonochromeBitmapSource;
21 import com.google.zxing.common.BitArray;
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
28 * @author dswitkin@google.com (Daniel Switkin)
30 final class UPCDecoder {
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
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
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
68 // Parity of next 6 digits
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
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.
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:
87 // Odd Even Even Odd Odd Even
89 // 0 1 1 0 0 1 == 0x19
91 private static final byte[] FIRST_DIGIT_ENCODINGS = {
92 0x00, 0x0B, 0x0D, 0xE, 0x13, 0x19, 0x1C, 0x15, 0x16, 0x1A
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;
102 * Utility class for returning a matched character. Defines the character
103 * plus the parity used for encoding it.
105 private static class CharResult {
106 public char character; // the encoded character
107 public int parity; // one of the parity types above
110 private static final int TOLERANCE = 5;
112 private MonochromeBitmapSource bitmap;
115 private StringBuffer result;
117 UPCDecoder(MonochromeBitmapSource bitmap) {
118 this.bitmap = bitmap;
119 width = bitmap.getWidth();
120 height = bitmap.getHeight();
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.
130 BitArray rowData = new BitArray(width);
131 String longestResult = "";
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);
138 if (decodeRow(rowData)) {
142 //Log("decode: row " + row + " normal result: " + result);
143 if (result.length() > longestResult.length()) {
144 longestResult = result.toString();
148 if (decodeRow(rowData)) {
152 //Log("decode: row " + row + " inverted result: " + result);
153 if (result.length() > longestResult.length()) {
154 longestResult = result.toString();
159 return result.toString();
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>
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);
180 //Log("Start pattern ends at column " + rowOffset);
182 rowOffset = decodeOneSide(rowData, rowOffset, true);
187 rowOffset = findPattern(rowData, rowOffset, MIDDLE_PATTERN, true);
191 //Log("Middle pattern ends at column " + rowOffset);
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);
199 return verifyResult();
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
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
212 private boolean verifyResult() {
213 // TODO - handle compressed barcodes.
215 // length is 12 for UPC and 13 for EAN-13
216 if (result.length() != 12 && result.length() != 13) {
221 int end = result.length() - 2;
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
226 for (int i = end; i >= 0; i--) {
227 int value = (result.charAt(i) - (int)'0') * factor;
229 factor = factor == 3 ? 1 : 3;
231 int endValue = (result.charAt(end + 1) - (int)'0');
232 //Log("checksum + endValue = " + (checksum + endValue));
233 return (checksum + endValue) % 10 == 0;
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];
245 findDigit(counters, foundChar, checkBothParities);
246 if (foundChar.parity == UNKNOWN_PARITY) {
249 if (foundChar.parity == EVEN_PARITY) {
250 firstDigitPattern |= 1 << (5 - x);
252 result.append(foundChar.character);
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);
266 if (firstDigit == '-') {
269 if (firstDigit != '0') {
270 result.insert(0, firstDigit);
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.
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) {
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]++;
299 if (counterPosition == pattern.length - 1) {
300 if (doesPatternMatch(counters, pattern)) {
303 for (int y = 2; y < pattern.length; y++) {
304 counters[y - 2] = counters[y];
310 counters[counterPosition] = 1;
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.
322 private void recordPattern(BitArray rowData, int rowOffset, int[] counters, int patternSize) {
323 for (int i = 0; i < counters.length; i++) {
326 boolean isWhite = !rowData.get(rowOffset);
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]++;
336 if (counterPosition == patternSize) {
339 counters[counterPosition] = 1;
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.
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;
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) {
371 result.parity = ODD_PARITY;
372 result.character = (char)((int)'0' + x);
376 // If first pattern didn't match, look for even parity patterns, as used in
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) {
389 result.parity = EVEN_PARITY;
390 result.character = (char)((int)'0' + x);
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.
402 private static boolean doesPatternMatch(int[] counters, byte[] pattern) {
403 // TODO: Remove the divide for performance.
405 int numCounters = counters.length;
406 for (int x = 0; x < numCounters; x++) {
407 total += counters[x];
409 int average = total * 10 / counters.length;
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) {