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