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