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