cpp/core/src/zxing/qrcode/detector/AlignmentPatternFinder.cpp

   1 /*
   2  *  AlignmentPatternFinder.cpp
   3  *  zxing
   4  *
   5  *  Created by Christian Brunschen on 14/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 "AlignmentPatternFinder.h"
  22 #include <zxing/ReaderException.h>
  23 #include <zxing/common/BitArray.h>
  24 #include <vector>
  25 #include <cmath>
  26 #include <cstdlib>
  27
  28 namespace zxing {
  29 namespace qrcode {
  30
  31 using namespace std;
  32
  33 float AlignmentPatternFinder::centerFromEnd(vector<int> &stateCount, int end) {
  34   return (float)(end - stateCount[2]) - stateCount[1] / 2.0f;
  35 }
  36
  37 bool AlignmentPatternFinder::foundPatternCross(vector<int> &stateCount) {
  38   float maxVariance = moduleSize_ / 2.0f;
  39   for (size_t i = 0; i < 3; i++) {
  40     if (abs(moduleSize_ - stateCount[i]) >= maxVariance) {
  41       return false;
  42     }
  43   }
  44   return true;
  45 }
  46
  47 float AlignmentPatternFinder::crossCheckVertical(size_t startI, size_t centerJ, int maxCount,
  48     int originalStateCountTotal) {
  49   int maxI = image_->getHeight();
  50   vector<int> stateCount(3, 0);
  51
  52
  53   // Start counting up from center
  54   int i = startI;
  55   while (i >= 0 && image_->get(centerJ, i) && stateCount[1] <= maxCount) {
  56     stateCount[1]++;
  57     i--;
  58   }
  59   // If already too many modules in this state or ran off the edge:
  60   if (i < 0 || stateCount[1] > maxCount) {
  61     return NAN;
  62   }
  63   while (i >= 0 && !image_->get(centerJ, i) && stateCount[0] <= maxCount) {
  64     stateCount[0]++;
  65     i--;
  66   }
  67   if (stateCount[0] > maxCount) {
  68     return NAN;
  69   }
  70
  71   // Now also count down from center
  72   i = startI + 1;
  73   while (i < maxI && image_->get(centerJ, i) && stateCount[1] <= maxCount) {
  74     stateCount[1]++;
  75     i++;
  76   }
  77   if (i == maxI || stateCount[1] > maxCount) {
  78     return NAN;
  79   }
  80   while (i < maxI && !image_->get(centerJ, i) && stateCount[2] <= maxCount) {
  81     stateCount[2]++;
  82     i++;
  83   }
  84   if (stateCount[2] > maxCount) {
  85     return NAN;
  86   }
  87
  88   int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2];
  89   if (5 * abs(stateCountTotal - originalStateCountTotal) >= 2 * originalStateCountTotal) {
  90     return NAN;
  91   }
  92
  93   return foundPatternCross(stateCount) ? centerFromEnd(stateCount, i) : NAN;
  94 }
  95
  96 Ref<AlignmentPattern> AlignmentPatternFinder::handlePossibleCenter(vector<int> &stateCount, size_t i, size_t j) {
  97   int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2];
  98   float centerJ = centerFromEnd(stateCount, j);
  99   float centerI = crossCheckVertical(i, (int)centerJ, 2 * stateCount[1], stateCountTotal);
 100   if (!isnan(centerI)) {
 101     float estimatedModuleSize = (float)(stateCount[0] + stateCount[1] + stateCount[2]) / 3.0f;
 102     int max = possibleCenters_->size();
 103     for (int index = 0; index < max; index++) {
 104       Ref<AlignmentPattern> center((*possibleCenters_)[index]);
 105       // Look for about the same center and module size:
 106       if (center->aboutEquals(estimatedModuleSize, centerI, centerJ)) {
 107         Ref<AlignmentPattern> result(new AlignmentPattern(centerJ, centerI, estimatedModuleSize));
 108         return result;
 109       }
 110     }
 111     AlignmentPattern *tmp = new AlignmentPattern(centerJ, centerI, estimatedModuleSize);
 112     // Hadn't found this before; save it
 113     tmp->retain();
 114     possibleCenters_->push_back(tmp);
 115     if (callback_ != 0) {
 116       callback_->foundPossibleResultPoint(*tmp);
 117     }
 118   }
 119   Ref<AlignmentPattern> result;
 120   return result;
 121 }
 122
 123 AlignmentPatternFinder::AlignmentPatternFinder(Ref<BitMatrix> image, size_t startX, size_t startY, size_t width,
 124                                                size_t height, float moduleSize,
 125                                                Ref<ResultPointCallback>const& callback) :
 126     image_(image), possibleCenters_(new vector<AlignmentPattern *> ()), startX_(startX), startY_(startY),
 127     width_(width), height_(height), moduleSize_(moduleSize), callback_(callback) {
 128 }
 129
 130 AlignmentPatternFinder::~AlignmentPatternFinder() {
 131   for (size_t i = 0; i < possibleCenters_->size(); i++) {
 132     (*possibleCenters_)[i]->release();
 133     (*possibleCenters_)[i] = 0;
 134   }
 135   delete possibleCenters_;
 136 }
 137
 138 Ref<AlignmentPattern> AlignmentPatternFinder::find() {
 139   size_t maxJ = startX_ + width_;
 140   size_t middleI = startY_ + (height_ >> 1);
 141   //      Ref<BitArray> luminanceRow(new BitArray(width_));
 142   // We are looking for black/white/black modules in 1:1:1 ratio;
 143   // this tracks the number of black/white/black modules seen so far
 144   vector<int> stateCount(3, 0);
 145   for (size_t iGen = 0; iGen < height_; iGen++) {
 146     // Search from middle outwards
 147     size_t i = middleI + ((iGen & 0x01) == 0 ? ((iGen + 1) >> 1) : -((iGen + 1) >> 1));
 148     //        image_->getBlackRow(i, luminanceRow, startX_, width_);
 149     stateCount[0] = 0;
 150     stateCount[1] = 0;
 151     stateCount[2] = 0;
 152     size_t j = startX_;
 153     // Burn off leading white pixels before anything else; if we start in the middle of
 154     // a white run, it doesn't make sense to count its length, since we don't know if the
 155     // white run continued to the left of the start point
 156     while (j < maxJ && !image_->get(j, i)) {
 157       j++;
 158     }
 159     int currentState = 0;
 160     while (j < maxJ) {
 161       if (image_->get(j, i)) {
 162         // Black pixel
 163         if (currentState == 1) { // Counting black pixels
 164           stateCount[currentState]++;
 165         } else { // Counting white pixels
 166           if (currentState == 2) { // A winner?
 167             if (foundPatternCross(stateCount)) { // Yes
 168               Ref<AlignmentPattern> confirmed(handlePossibleCenter(stateCount, i, j));
 169               if (confirmed != 0) {
 170                 return confirmed;
 171               }
 172             }
 173             stateCount[0] = stateCount[2];
 174             stateCount[1] = 1;
 175             stateCount[2] = 0;
 176             currentState = 1;
 177           } else {
 178             stateCount[++currentState]++;
 179           }
 180         }
 181       } else { // White pixel
 182         if (currentState == 1) { // Counting black pixels
 183           currentState++;
 184         }
 185         stateCount[currentState]++;
 186       }
 187       j++;
 188     }
 189     if (foundPatternCross(stateCount)) {
 190       Ref<AlignmentPattern> confirmed(handlePossibleCenter(stateCount, i, maxJ));
 191       if (confirmed != 0) {
 192         return confirmed;
 193       }
 194     }
 195
 196   }
 197
 198   // Hmm, nothing we saw was observed and confirmed twice. If we had
 199   // any guess at all, return it.
 200   if (possibleCenters_->size() > 0) {
 201     Ref<AlignmentPattern> center((*possibleCenters_)[0]);
 202     return center;
 203   }
 204
 205   throw zxing::ReaderException("Could not find alignment pattern");
 206 }
 207
 208 }
 209 }