cpp/core/src/qrcode/detector/FinderPatternFinder.cpp

   1 /*
   2  *  FinderPatternFinder.cpp
   3  *  zxing
   4  *
   5  *  Created by Christian Brunschen on 13/05/2008.
   6  *  Copyright 2008 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 "FinderPatternFinder.h"
  22 #include "../../ReaderException.h"
  23 #include <vector>
  24 #include <cmath>
  25
  26 namespace qrcode {
  27   namespace detector {
  28
  29     using namespace std;
  30     using namespace common;
  31
  32     class ClosestToAverageComparator {
  33     private:
  34       float averageModuleSize_;
  35     public:
  36       ClosestToAverageComparator(float averageModuleSize) :
  37       averageModuleSize_(averageModuleSize) { }
  38       int operator()(Ref<FinderPattern> a, Ref<FinderPattern> b) {
  39         float dA = abs(a->getEstimatedModuleSize() - averageModuleSize_);
  40         float dB = abs(b->getEstimatedModuleSize() - averageModuleSize_);
  41         return dA < dB ? -1 : dA > dB ? 1 : 0;
  42       }
  43     };
  44
  45     class CenterComparator {
  46     public:
  47       int operator()(Ref<FinderPattern> a, Ref<FinderPattern> b) {
  48         return b->getCount() - a->getCount();
  49       }
  50     };
  51
  52     int FinderPatternFinder::CENTER_QUORUM = 2;
  53     int FinderPatternFinder::MIN_SKIP = 3;
  54     int FinderPatternFinder::MAX_MODULES = 57;
  55
  56     float FinderPatternFinder::centerFromEnd(valarray<int> &stateCount,
  57                                              int end) {
  58       return (float) (end - stateCount[4] - stateCount[3]) -
  59         stateCount[2] / 2.0f;
  60     }
  61
  62     bool FinderPatternFinder::foundPatternCross(valarray<int> &stateCount) {
  63       int totalModuleSize = 0;
  64       for (int i = 0; i < 5; i++) {
  65         if (stateCount[i] == 0) {
  66           return false;
  67         }
  68         totalModuleSize += stateCount[i];
  69       }
  70       if (totalModuleSize < 7) {
  71         return false;
  72       }
  73       float moduleSize = (float) totalModuleSize / 7.0f;
  74       float maxVariance = moduleSize / 2.0f;
  75       // Allow less than 50% variance from 1-1-3-1-1 proportions
  76       return abs(moduleSize - stateCount[0]) < maxVariance &&
  77         abs(moduleSize - stateCount[1]) < maxVariance &&
  78         abs(3.0f * moduleSize - stateCount[2]) < 3.0f * maxVariance &&
  79         abs(moduleSize - stateCount[3]) < maxVariance &&
  80         abs(moduleSize - stateCount[4]) < maxVariance;
  81     }
  82
  83     float FinderPatternFinder::crossCheckVertical(size_t startI, size_t centerJ,
  84                                                   int maxCount,
  85                                                   int originalStateCountTotal) {
  86
  87       int maxI = image_->getHeight();
  88       valarray<int> stateCount((const int)0, 5);
  89
  90       // Start counting up from center
  91       int i = startI;
  92       while (i >= 0 && image_->isBlack(centerJ, i)) {
  93         stateCount[2]++;
  94         i--;
  95       }
  96       if (i < 0) {
  97         return NAN;
  98       }
  99       while (i >= 0 && !image_->isBlack(centerJ, i) && stateCount[1] <= maxCount) {
 100         stateCount[1]++;
 101         i--;
 102       }
 103       // If already too many modules in this state or ran off the edge:
 104       if (i < 0 || stateCount[1] > maxCount) {
 105         return NAN;
 106       }
 107       while (i >= 0 && image_->isBlack(centerJ, i) && stateCount[0] <= maxCount) {
 108         stateCount[0]++;
 109         i--;
 110       }
 111       if (stateCount[0] > maxCount) {
 112         return NAN;
 113       }
 114
 115       // Now also count down from center
 116       i = startI + 1;
 117       while (i < maxI && image_->isBlack(centerJ, i)) {
 118         stateCount[2]++;
 119         i++;
 120       }
 121       if (i == maxI) {
 122         return NAN;
 123       }
 124       while (i < maxI && !image_->isBlack(centerJ, i) && stateCount[3] < maxCount) {
 125         stateCount[3]++;
 126         i++;
 127       }
 128       if (i == maxI || stateCount[3] >= maxCount) {
 129         return NAN;
 130       }
 131       while (i < maxI && image_->isBlack(centerJ, i) && stateCount[4] < maxCount) {
 132         stateCount[4]++;
 133         i++;
 134       }
 135       if (stateCount[4] >= maxCount) {
 136         return NAN;
 137       }
 138
 139       // If we found a finder-pattern-like section, but its size is more than 20% different than
 140       // the original, assume it's a false positive
 141       int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] + stateCount[3] + stateCount[4];
 142       if (5 * abs(stateCountTotal - originalStateCountTotal) >= originalStateCountTotal) {
 143         return NAN;
 144       }
 145
 146       return foundPatternCross(stateCount) ? centerFromEnd(stateCount, i) : NAN;
 147     }
 148
 149     float FinderPatternFinder::crossCheckHorizontal(size_t startJ, size_t centerI,
 150                                                     int maxCount,
 151                                                     int originalStateCountTotal)
 152     {
 153
 154       int maxJ = image_->getWidth();
 155       valarray<int> stateCount((const int)0, 5);
 156
 157       int j = startJ;
 158       while (j >= 0 && image_->isBlack(j, centerI)) {
 159         stateCount[2]++;
 160         j--;
 161       }
 162       if (j < 0) {
 163         return NAN;
 164       }
 165       while (j >= 0 && !image_->isBlack(j, centerI) &&
 166              stateCount[1] <= maxCount) {
 167         stateCount[1]++;
 168         j--;
 169       }
 170       if (j < 0 || stateCount[1] > maxCount) {
 171         return NAN;
 172       }
 173       while (j >= 0 && image_->isBlack(j, centerI) &&
 174              stateCount[0] <= maxCount) {
 175         stateCount[0]++;
 176         j--;
 177       }
 178       if (stateCount[0] > maxCount) {
 179         return NAN;
 180       }
 181
 182       j = startJ + 1;
 183       while (j < maxJ && image_->isBlack(j, centerI)) {
 184         stateCount[2]++;
 185         j++;
 186       }
 187       if (j == maxJ) {
 188         return NAN;
 189       }
 190       while (j < maxJ && !image_->isBlack(j, centerI) &&
 191              stateCount[3] < maxCount) {
 192         stateCount[3]++;
 193         j++;
 194       }
 195       if (j == maxJ || stateCount[3] >= maxCount) {
 196         return NAN;
 197       }
 198       while (j < maxJ && image_->isBlack(j, centerI) && stateCount[4] < maxCount) {
 199         stateCount[4]++;
 200         j++;
 201       }
 202       if (stateCount[4] >= maxCount) {
 203         return NAN;
 204       }
 205
 206       // If we found a finder-pattern-like section, but its size is significantly different than
 207       // the original, assume it's a false positive
 208       int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] +
 209       stateCount[3] + stateCount[4];
 210       if (5 * abs(stateCountTotal - originalStateCountTotal) >=
 211           originalStateCountTotal) {
 212         return NAN;
 213       }
 214
 215       return foundPatternCross(stateCount) ? centerFromEnd(stateCount, j) : NAN;
 216     }
 217
 218     bool FinderPatternFinder::handlePossibleCenter(valarray<int> &stateCount,
 219                                                    size_t i, size_t j) {
 220       int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] +
 221         stateCount[3] + stateCount[4];
 222       float centerJ = centerFromEnd(stateCount, j);
 223       float centerI = crossCheckVertical(i, centerJ, stateCount[2],
 224                                          stateCountTotal);
 225       if (!isnan(centerI)) {
 226         // Re-cross check
 227         centerJ = crossCheckHorizontal(centerJ, centerI, stateCount[2],
 228                                        stateCountTotal);
 229         if (!isnan(centerJ)) {
 230           float estimatedModuleSize = (float) stateCountTotal / 7.0f;
 231           bool found = false;
 232           size_t max = possibleCenters_.size();
 233           for (size_t index = 0; index < max; index++) {
 234             Ref<FinderPattern> center = possibleCenters_[index];
 235             // Look for about the same center and module size:
 236             if (center->aboutEquals(estimatedModuleSize, centerI, centerJ)) {
 237               center->incrementCount();
 238               found = true;
 239               break;
 240             }
 241           }
 242           if (!found) {
 243             Ref<FinderPattern> newPattern
 244               (new FinderPattern(centerJ, centerI,
 245                                  estimatedModuleSize));
 246             possibleCenters_.push_back(newPattern);
 247           }
 248           return true;
 249         }
 250       }
 251       return false;
 252     }
 253
 254     int FinderPatternFinder::findRowSkip() {
 255       size_t max = possibleCenters_.size();
 256       if (max <= 1) {
 257         return 0;
 258       }
 259       Ref<FinderPattern> firstConfirmedCenter;
 260       for (size_t i = 0; i < max; i++) {
 261         Ref<FinderPattern> center = possibleCenters_[i];
 262         if (center->getCount() >= CENTER_QUORUM) {
 263           if (firstConfirmedCenter == 0) {
 264             firstConfirmedCenter = center;
 265           } else {
 266             // We have two confirmed centers
 267             // How far down can we skip before resuming looking for the next
 268             // pattern? In the worst case, only the difference between the
 269             // difference in the x / y coordinates of the two centers.
 270             // This is the case where you find top left first. Draw it out.
 271             hasSkipped_ = true;
 272             return (int) (abs(firstConfirmedCenter->getX() - center->getX()) -
 273                           abs(firstConfirmedCenter->getY() - center->getY()));
 274           }
 275         }
 276       }
 277       return 0;
 278     }
 279
 280     bool FinderPatternFinder::haveMultiplyConfirmedCenters() {
 281       int confirmedCount = 0;
 282       float totalModuleSize = 0.0f;
 283       size_t max = possibleCenters_.size();
 284       for (size_t i = 0; i < max; i++) {
 285         Ref<FinderPattern> pattern = possibleCenters_[i];
 286         if (pattern->getCount() >= CENTER_QUORUM) {
 287           confirmedCount++;
 288           totalModuleSize += pattern->getEstimatedModuleSize();
 289         }
 290       }
 291       if (confirmedCount < 3) {
 292         return false;
 293       }
 294       // OK, we have at least 3 confirmed centers, but, it's possible that one is a "false positive"
 295       // and that we need to keep looking. We detect this by asking if the estimated module sizes
 296       // vary too much. We arbitrarily say that when the total deviation from average exceeds
 297       // 15% of the total module size estimates, it's too much.
 298       float average = totalModuleSize / max;
 299       float totalDeviation = 0.0f;
 300       for (size_t i = 0; i < max; i++) {
 301         Ref<FinderPattern> pattern = possibleCenters_[i];
 302         totalDeviation += abs(pattern->getEstimatedModuleSize() - average);
 303       }
 304       return totalDeviation <= 0.15f * totalModuleSize;
 305     }
 306
 307     ArrayRef<Ref<FinderPattern> > FinderPatternFinder::selectBestPatterns() {
 308       sort(possibleCenters_.begin(), possibleCenters_.end(),
 309            CenterComparator());
 310       size_t size = 0;
 311       size_t max = possibleCenters_.size();
 312       while (size < max) {
 313         if (possibleCenters_[size]->getCount() < CENTER_QUORUM) {
 314           break;
 315         }
 316         size++;
 317       }
 318
 319       if (size < 3) {
 320         // Couldn't find enough finder patterns
 321         throw new ReaderException("Could not find three finder patterns");
 322       }
 323
 324       if (size == 3) {
 325         // Found just enough -- hope these are good!
 326         Ref<FinderPattern> rawResult[] = {
 327           possibleCenters_[0], possibleCenters_[1], possibleCenters_[2]
 328         };
 329         ArrayRef<Ref<FinderPattern> > result(rawResult, 3);
 330         return result;
 331       }
 332
 333       // Hmm, multiple found. We need to pick the best three. Find the most
 334       // popular ones whose module size is nearest the average
 335       float averageModuleSize = 0.0f;
 336       for (size_t i = 0; i < size; i++) {
 337         averageModuleSize += possibleCenters_[i]->getEstimatedModuleSize();
 338       }
 339       averageModuleSize /= (float) size;
 340
 341       sort(possibleCenters_.begin(), possibleCenters_.end(),
 342            ClosestToAverageComparator(averageModuleSize));
 343
 344       Ref<FinderPattern> rawResult[] = {
 345         possibleCenters_[0], possibleCenters_[1], possibleCenters_[2]
 346       };
 347       ArrayRef<Ref<FinderPattern> > result(rawResult, 3);
 348       return result;
 349     }
 350
 351     ArrayRef<Ref<FinderPattern> > FinderPatternFinder::orderBestPatterns
 352     (ArrayRef<Ref<FinderPattern> > patterns) {
 353       // Find distances between pattern centers
 354       float abDistance = distance(patterns[0], patterns[1]);
 355       float bcDistance = distance(patterns[1], patterns[2]);
 356       float acDistance = distance(patterns[0], patterns[2]);
 357
 358       Ref<FinderPattern> topLeft;
 359       Ref<FinderPattern> topRight;
 360       Ref<FinderPattern> bottomLeft;
 361       // Assume one closest to other two is top left;
 362       // topRight and bottomLeft will just be guesses below at first
 363       if (bcDistance >= abDistance && bcDistance >= acDistance) {
 364         topLeft = patterns[0];
 365         topRight = patterns[1];
 366         bottomLeft = patterns[2];
 367       } else if (acDistance >= bcDistance && acDistance >= abDistance) {
 368         topLeft = patterns[1];
 369         topRight = patterns[0];
 370         bottomLeft = patterns[2];
 371       } else {
 372         topLeft = patterns[2];
 373         topRight = patterns[0];
 374         bottomLeft = patterns[1];
 375       }
 376
 377       // Use cross product to figure out which of other1/2 is the bottom left
 378       // pattern. The vector "top-left -> bottom-left" x "top-left -> top-right"
 379       // should yield a vector with positive z component
 380       if ((bottomLeft->getY() - topLeft->getY()) *
 381           (topRight->getX() - topLeft->getX()) <
 382           (bottomLeft->getX() - topLeft->getX()) *
 383           (topRight->getY() - topLeft->getY())) {
 384         Ref<FinderPattern> temp = topRight;
 385         topRight = bottomLeft;
 386         bottomLeft = temp;
 387       }
 388
 389       ArrayRef<Ref<FinderPattern> > results(3);
 390       results[0] = bottomLeft;
 391       results[1] = topLeft;
 392       results[2] = topRight;
 393       return results;
 394     }
 395
 396     float FinderPatternFinder::distance(Ref<ResultPoint> p1,
 397                                         Ref<ResultPoint> p2) {
 398       float dx = p1->getX() - p2->getX();
 399       float dy = p1->getY() - p2->getY();
 400       return (float)sqrt(dx*dx + dy*dy);
 401     }
 402
 403     FinderPatternFinder::FinderPatternFinder(Ref<MonochromeBitmapSource> image)
 404     : image_(image), possibleCenters_(), hasSkipped_(false) {
 405     }
 406
 407     Ref<FinderPatternInfo> FinderPatternFinder::find() {
 408       size_t maxI = image_->getHeight();
 409       size_t maxJ = image_->getWidth();
 410
 411       // We are looking for black/white/black/white/black modules in
 412       // 1:1:3:1:1 ratio; this tracks the number of such modules seen so far
 413       valarray<int> stateCount(5);
 414       bool done = false;
 415
 416       // Let's assume that the maximum version QR Code we support takes up 1/4
 417       // the height of the image, and then account for the center being 3
 418       // modules in size. This gives the smallest number of pixels the center
 419       // could be, so skip this often. When trying harder, look for all
 420       // QR versions regardless of how dense they are.
 421       size_t iSkip = MIN_SKIP;
 422
 423       for (size_t i = iSkip - 1; i < maxI && !done; i += iSkip) {
 424         // Get a row of black/white values
 425         Ref<BitArray> null;
 426         Ref<BitArray> blackRow = image_->getBlackRow(i, null, 0, maxJ);
 427         stateCount[0] = 0;
 428         stateCount[1] = 0;
 429         stateCount[2] = 0;
 430         stateCount[3] = 0;
 431         stateCount[4] = 0;
 432         int currentState = 0;
 433         for (size_t j = 0; j < maxJ; j++) {
 434           if (blackRow->get(j)) {
 435             // Black pixel
 436             if ((currentState & 1) == 1) { // Counting white pixels
 437               currentState++;
 438             }
 439             stateCount[currentState]++;
 440           } else { // White pixel
 441             if ((currentState & 1) == 0) { // Counting black pixels
 442               if (currentState == 4) { // A winner?
 443                 if (foundPatternCross(stateCount)) { // Yes
 444                   bool confirmed = handlePossibleCenter(stateCount, i, j);
 445                   if (confirmed) {
 446                     iSkip = 1; // Go back to examining each line
 447                     if (hasSkipped_) {
 448                       done = haveMultiplyConfirmedCenters();
 449                     } else {
 450                       int rowSkip = findRowSkip();
 451                       if (rowSkip > stateCount[2]) {
 452                         // Skip rows between row of lower confirmed center
 453                         // and top of presumed third confirmed center
 454                         // but back up a bit to get a full chance of detecting
 455                         // it, entire width of center of finder pattern
 456
 457                         // Skip by rowSkip, but back off by stateCount[2] (size
 458                         // of last center of pattern we saw) to be conservative,
 459                         // and also back off by iSkip which is about to be
 460                         // re-added
 461                         i += rowSkip - stateCount[2] - iSkip;
 462                         j = maxJ - 1;
 463                       }
 464                     }
 465                   } else {
 466                     // Advance to next black pixel
 467                     do {
 468                       j++;
 469                     } while (j < maxJ && !blackRow->get(j));
 470                     j--; // back up to that last white pixel
 471                   }
 472                   // Clear state to start looking again
 473                   currentState = 0;
 474                   stateCount[0] = 0;
 475                   stateCount[1] = 0;
 476                   stateCount[2] = 0;
 477                   stateCount[3] = 0;
 478                   stateCount[4] = 0;
 479                 } else { // No, shift counts back by two
 480                   stateCount[0] = stateCount[2];
 481                   stateCount[1] = stateCount[3];
 482                   stateCount[2] = stateCount[4];
 483                   stateCount[3] = 1;
 484                   stateCount[4] = 0;
 485                   currentState = 3;
 486                 }
 487               } else {
 488                 stateCount[++currentState]++;
 489               }
 490             } else { // Counting white pixels
 491               stateCount[currentState]++;
 492             }
 493           }
 494         }
 495         if (foundPatternCross(stateCount)) {
 496           bool confirmed = handlePossibleCenter(stateCount, i, maxJ);
 497           if (confirmed) {
 498             iSkip = stateCount[0];
 499             if (hasSkipped_) {
 500               // Found a third one
 501               done = haveMultiplyConfirmedCenters();
 502             }
 503           }
 504         }
 505       }
 506
 507       ArrayRef<Ref<FinderPattern> > patternInfo = selectBestPatterns();
 508       patternInfo = orderBestPatterns(patternInfo);
 509
 510       Ref<FinderPatternInfo> result(new FinderPatternInfo(patternInfo));
 511       return result;
 512     }
 513   }
 514 }