cpp/core/src/zxing/oned/ITFReader.cpp

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