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