core/src/com/google/zxing/oned/ITFReader.java

   1 /*\r
   2  * Copyright 2008 ZXing authors\r
   3  *\r
   4  * Licensed under the Apache License, Version 2.0 (the "License");\r
   5  * you may not use this file except in compliance with the License.\r
   6  * You may obtain a copy of the License at\r
   7  *\r
   8  *      http://www.apache.org/licenses/LICENSE-2.0\r
   9  *\r
  10  * Unless required by applicable law or agreed to in writing, software\r
  11  * distributed under the License is distributed on an "AS IS" BASIS,\r
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
  13  * See the License for the specific language governing permissions and\r
  14  * limitations under the License.\r
  15  */\r
  16 \r
  17 package com.google.zxing.oned;\r
  18 \r
  19 import com.google.zxing.BarcodeFormat;\r
  20 import com.google.zxing.DecodeHintType;\r
  21 import com.google.zxing.FormatException;\r
  22 import com.google.zxing.NotFoundException;\r
  23 import com.google.zxing.Result;\r
  24 import com.google.zxing.ResultPoint;\r
  25 import com.google.zxing.common.BitArray;\r
  26 \r
  27 import java.util.Hashtable;\r
  28 \r
  29 /**\r
  30  * <p>Implements decoding of the ITF format.</p>\r
  31  *\r
  32  * <p>"ITF" stands for Interleaved Two of Five. This Reader will scan ITF barcode with 6, 10 or 14\r
  33  * digits. The checksum is optional and is not applied by this Reader. The consumer of the decoded\r
  34  * value will have to apply a checksum if required.</p>\r
  35  *\r
  36  * <p><a href="http://en.wikipedia.org/wiki/Interleaved_2_of_5">http://en.wikipedia.org/wiki/Interleaved_2_of_5</a>\r
  37  * is a great reference for Interleaved 2 of 5 information.</p>\r
  38  *\r
  39  * @author kevin.osullivan@sita.aero, SITA Lab.\r
  40  */\r
  41 public final class ITFReader extends OneDReader {\r
  42 \r
  43   private static final int MAX_AVG_VARIANCE = (int) (PATTERN_MATCH_RESULT_SCALE_FACTOR * 0.42f);\r
  44   private static final int MAX_INDIVIDUAL_VARIANCE = (int) (PATTERN_MATCH_RESULT_SCALE_FACTOR * 0.8f);\r
  45 \r
  46   private static final int W = 3; // Pixel width of a wide line\r
  47   private static final int N = 1; // Pixed width of a narrow line\r
  48 \r
  49   private static final int[] DEFAULT_ALLOWED_LENGTHS = { 6, 10, 14, 44 };\r
  50 \r
  51   // Stores the actual narrow line width of the image being decoded.\r
  52   private int narrowLineWidth = -1;\r
  53 \r
  54   /**\r
  55    * Start/end guard pattern.\r
  56    *\r
  57    * Note: The end pattern is reversed because the row is reversed before\r
  58    * searching for the END_PATTERN\r
  59    */\r
  60   private static final int[] START_PATTERN = {N, N, N, N};\r
  61   private static final int[] END_PATTERN_REVERSED = {N, N, W};\r
  62 \r
  63   /**\r
  64    * Patterns of Wide / Narrow lines to indicate each digit\r
  65    */\r
  66   private static final int[][] PATTERNS = {\r
  67       {N, N, W, W, N}, // 0\r
  68       {W, N, N, N, W}, // 1\r
  69       {N, W, N, N, W}, // 2\r
  70       {W, W, N, N, N}, // 3\r
  71       {N, N, W, N, W}, // 4\r
  72       {W, N, W, N, N}, // 5\r
  73       {N, W, W, N, N}, // 6\r
  74       {N, N, N, W, W}, // 7\r
  75       {W, N, N, W, N}, // 8\r
  76       {N, W, N, W, N}  // 9\r
  77   };\r
  78 \r
  79   public Result decodeRow(int rowNumber, BitArray row, Hashtable hints) throws FormatException, NotFoundException {\r
  80 \r
  81     // Find out where the Middle section (payload) starts & ends\r
  82     int[] startRange = decodeStart(row);\r
  83     int[] endRange = decodeEnd(row);\r
  84 \r
  85     StringBuffer result = new StringBuffer(20);\r
  86     decodeMiddle(row, startRange[1], endRange[0], result);\r
  87     String resultString = result.toString();\r
  88 \r
  89     int[] allowedLengths = null;\r
  90     if (hints != null) {\r
  91       allowedLengths = (int[]) hints.get(DecodeHintType.ALLOWED_LENGTHS);\r
  92 \r
  93     }\r
  94     if (allowedLengths == null) {\r
  95       allowedLengths = DEFAULT_ALLOWED_LENGTHS;\r
  96     }\r
  97 \r
  98     // To avoid false positives with 2D barcodes (and other patterns), make\r
  99     // an assumption that the decoded string must be 6, 10 or 14 digits.\r
 100     int length = resultString.length();\r
 101     boolean lengthOK = false;\r
 102     for (int i = 0; i < allowedLengths.length; i++) {\r
 103       if (length == allowedLengths[i]) {\r
 104         lengthOK = true;\r
 105         break;\r
 106       }\r
 107 \r
 108     }\r
 109     if (!lengthOK) {\r
 110       throw FormatException.getFormatInstance();\r
 111     }\r
 112 \r
 113     return new Result(\r
 114         resultString,\r
 115         null, // no natural byte representation for these barcodes\r
 116         new ResultPoint[] { new ResultPoint(startRange[1], (float) rowNumber),\r
 117                             new ResultPoint(endRange[0], (float) rowNumber)},\r
 118         BarcodeFormat.ITF);\r
 119   }\r
 120 \r
 121   /**\r
 122    * @param row          row of black/white values to search\r
 123    * @param payloadStart offset of start pattern\r
 124    * @param resultString {@link StringBuffer} to append decoded chars to\r
 125    * @throws NotFoundException if decoding could not complete successfully\r
 126    */\r
 127   private static void decodeMiddle(BitArray row, int payloadStart, int payloadEnd,\r
 128       StringBuffer resultString) throws NotFoundException {\r
 129 \r
 130     // Digits are interleaved in pairs - 5 black lines for one digit, and the\r
 131     // 5\r
 132     // interleaved white lines for the second digit.\r
 133     // Therefore, need to scan 10 lines and then\r
 134     // split these into two arrays\r
 135     int[] counterDigitPair = new int[10];\r
 136     int[] counterBlack = new int[5];\r
 137     int[] counterWhite = new int[5];\r
 138 \r
 139     while (payloadStart < payloadEnd) {\r
 140 \r
 141       // Get 10 runs of black/white.\r
 142       recordPattern(row, payloadStart, counterDigitPair);\r
 143       // Split them into each array\r
 144       for (int k = 0; k < 5; k++) {\r
 145         int twoK = k << 1;\r
 146         counterBlack[k] = counterDigitPair[twoK];\r
 147         counterWhite[k] = counterDigitPair[twoK + 1];\r
 148       }\r
 149 \r
 150       int bestMatch = decodeDigit(counterBlack);\r
 151       resultString.append((char) ('0' + bestMatch));\r
 152       bestMatch = decodeDigit(counterWhite);\r
 153       resultString.append((char) ('0' + bestMatch));\r
 154 \r
 155       for (int i = 0; i < counterDigitPair.length; i++) {\r
 156         payloadStart += counterDigitPair[i];\r
 157       }\r
 158     }\r
 159   }\r
 160 \r
 161   /**\r
 162    * Identify where the start of the middle / payload section starts.\r
 163    *\r
 164    * @param row row of black/white values to search\r
 165    * @return Array, containing index of start of 'start block' and end of\r
 166    *         'start block'\r
 167    * @throws NotFoundException\r
 168    */\r
 169   int[] decodeStart(BitArray row) throws NotFoundException {\r
 170     int endStart = skipWhiteSpace(row);\r
 171     int[] startPattern = findGuardPattern(row, endStart, START_PATTERN);\r
 172 \r
 173     // Determine the width of a narrow line in pixels. We can do this by\r
 174     // getting the width of the start pattern and dividing by 4 because its\r
 175     // made up of 4 narrow lines.\r
 176     this.narrowLineWidth = (startPattern[1] - startPattern[0]) >> 2;\r
 177 \r
 178     validateQuietZone(row, startPattern[0]);\r
 179 \r
 180     return startPattern;\r
 181   }\r
 182 \r
 183   /**\r
 184    * The start & end patterns must be pre/post fixed by a quiet zone. This\r
 185    * zone must be at least 10 times the width of a narrow line.  Scan back until\r
 186    * we either get to the start of the barcode or match the necessary number of\r
 187    * quiet zone pixels.\r
 188    *\r
 189    * Note: Its assumed the row is reversed when using this method to find\r
 190    * quiet zone after the end pattern.\r
 191    *\r
 192    * ref: http://www.barcode-1.net/i25code.html\r
 193    *\r
 194    * @param row bit array representing the scanned barcode.\r
 195    * @param startPattern index into row of the start or end pattern.\r
 196    * @throws NotFoundException if the quiet zone cannot be found, a ReaderException is thrown.\r
 197    */\r
 198   private void validateQuietZone(BitArray row, int startPattern) throws NotFoundException {\r
 199 \r
 200     int quietCount = this.narrowLineWidth * 10;  // expect to find this many pixels of quiet zone\r
 201 \r
 202     for (int i = startPattern - 1; quietCount > 0 && i >= 0; i--) {\r
 203       if (row.get(i)) {\r
 204         break;\r
 205       }\r
 206       quietCount--;\r
 207     }\r
 208     if (quietCount != 0) {\r
 209       // Unable to find the necessary number of quiet zone pixels.\r
 210       throw NotFoundException.getNotFoundInstance();\r
 211     }\r
 212   }\r
 213 \r
 214   /**\r
 215    * Skip all whitespace until we get to the first black line.\r
 216    *\r
 217    * @param row row of black/white values to search\r
 218    * @return index of the first black line.\r
 219    * @throws NotFoundException Throws exception if no black lines are found in the row\r
 220    */\r
 221   private static int skipWhiteSpace(BitArray row) throws NotFoundException {\r
 222     int width = row.getSize();\r
 223     int endStart = 0;\r
 224     while (endStart < width) {\r
 225       if (row.get(endStart)) {\r
 226         break;\r
 227       }\r
 228       endStart++;\r
 229     }\r
 230     if (endStart == width) {\r
 231       throw NotFoundException.getNotFoundInstance();\r
 232     }\r
 233 \r
 234     return endStart;\r
 235   }\r
 236 \r
 237   /**\r
 238    * Identify where the end of the middle / payload section ends.\r
 239    *\r
 240    * @param row row of black/white values to search\r
 241    * @return Array, containing index of start of 'end block' and end of 'end\r
 242    *         block'\r
 243    * @throws NotFoundException\r
 244    */\r
 245 \r
 246   int[] decodeEnd(BitArray row) throws NotFoundException {\r
 247 \r
 248     // For convenience, reverse the row and then\r
 249     // search from 'the start' for the end block\r
 250     row.reverse();\r
 251     try {\r
 252       int endStart = skipWhiteSpace(row);\r
 253       int[] endPattern = findGuardPattern(row, endStart, END_PATTERN_REVERSED);\r
 254 \r
 255       // The start & end patterns must be pre/post fixed by a quiet zone. This\r
 256       // zone must be at least 10 times the width of a narrow line.\r
 257       // ref: http://www.barcode-1.net/i25code.html\r
 258       validateQuietZone(row, endPattern[0]);\r
 259 \r
 260       // Now recalculate the indices of where the 'endblock' starts & stops to\r
 261       // accommodate\r
 262       // the reversed nature of the search\r
 263       int temp = endPattern[0];\r
 264       endPattern[0] = row.getSize() - endPattern[1];\r
 265       endPattern[1] = row.getSize() - temp;\r
 266 \r
 267       return endPattern;\r
 268     } finally {\r
 269       // Put the row back the right way.\r
 270       row.reverse();\r
 271     }\r
 272   }\r
 273 \r
 274   /**\r
 275    * @param row       row of black/white values to search\r
 276    * @param rowOffset position to start search\r
 277    * @param pattern   pattern of counts of number of black and white pixels that are\r
 278    *                  being searched for as a pattern\r
 279    * @return start/end horizontal offset of guard pattern, as an array of two\r
 280    *         ints\r
 281    * @throws NotFoundException if pattern is not found\r
 282    */\r
 283   private static int[] findGuardPattern(BitArray row, int rowOffset, int[] pattern) throws NotFoundException {\r
 284 \r
 285     // TODO: This is very similar to implementation in UPCEANReader. Consider if they can be\r
 286     // merged to a single method.\r
 287     int patternLength = pattern.length;\r
 288     int[] counters = new int[patternLength];\r
 289     int width = row.getSize();\r
 290     boolean isWhite = false;\r
 291 \r
 292     int counterPosition = 0;\r
 293     int patternStart = rowOffset;\r
 294     for (int x = rowOffset; x < width; x++) {\r
 295       boolean pixel = row.get(x);\r
 296       if (pixel ^ isWhite) {\r
 297         counters[counterPosition]++;\r
 298       } else {\r
 299         if (counterPosition == patternLength - 1) {\r
 300           if (patternMatchVariance(counters, pattern, MAX_INDIVIDUAL_VARIANCE) < MAX_AVG_VARIANCE) {\r
 301             return new int[]{patternStart, x};\r
 302           }\r
 303           patternStart += counters[0] + counters[1];\r
 304           for (int y = 2; y < patternLength; y++) {\r
 305             counters[y - 2] = counters[y];\r
 306           }\r
 307           counters[patternLength - 2] = 0;\r
 308           counters[patternLength - 1] = 0;\r
 309           counterPosition--;\r
 310         } else {\r
 311           counterPosition++;\r
 312         }\r
 313         counters[counterPosition] = 1;\r
 314         isWhite = !isWhite;\r
 315       }\r
 316     }\r
 317     throw NotFoundException.getNotFoundInstance();\r
 318   }\r
 319 \r
 320   /**\r
 321    * Attempts to decode a sequence of ITF black/white lines into single\r
 322    * digit.\r
 323    *\r
 324    * @param counters the counts of runs of observed black/white/black/... values\r
 325    * @return The decoded digit\r
 326    * @throws NotFoundException if digit cannot be decoded\r
 327    */\r
 328   private static int decodeDigit(int[] counters) throws NotFoundException {\r
 329 \r
 330     int bestVariance = MAX_AVG_VARIANCE; // worst variance we'll accept\r
 331     int bestMatch = -1;\r
 332     int max = PATTERNS.length;\r
 333     for (int i = 0; i < max; i++) {\r
 334       int[] pattern = PATTERNS[i];\r
 335       int variance = patternMatchVariance(counters, pattern, MAX_INDIVIDUAL_VARIANCE);\r
 336       if (variance < bestVariance) {\r
 337         bestVariance = variance;\r
 338         bestMatch = i;\r
 339       }\r
 340     }\r
 341     if (bestMatch >= 0) {\r
 342       return bestMatch;\r
 343                 } else {\r
 344                         throw NotFoundException.getNotFoundInstance();\r
 345                 }\r
 346         }\r
 347 \r
 348 }\r