2 * AlignmentPatternFinder.cpp
5 * Created by Christian Brunschen on 14/05/2008.
6 * Copyright 2008 ZXing authors All rights reserved.
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
12 * http://www.apache.org/licenses/LICENSE-2.0
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.
21 #include "AlignmentPatternFinder.h"
22 #include <zxing/ReaderException.h>
23 #include <zxing/common/BitArray.h>
32 float AlignmentPatternFinder::centerFromEnd(valarray<int> &stateCount, int end) {
33 return (float)(end - stateCount[2]) - stateCount[1] / 2.0f;
36 bool AlignmentPatternFinder::foundPatternCross(valarray<int> &stateCount) {
37 float maxVariance = moduleSize_ / 2.0f;
38 for (size_t i = 0; i < 3; i++) {
39 if (abs(moduleSize_ - stateCount[i]) >= maxVariance) {
46 float AlignmentPatternFinder::crossCheckVertical(size_t startI, size_t centerJ, int maxCount,
47 int originalStateCountTotal) {
48 int maxI = image_->getHeight();
49 valarray<int> stateCount(0, 3);
52 // Start counting up from center
54 while (i >= 0 && image_->get(centerJ, i) && stateCount[1] <= maxCount) {
58 // If already too many modules in this state or ran off the edge:
59 if (i < 0 || stateCount[1] > maxCount) {
62 while (i >= 0 && !image_->get(centerJ, i) && stateCount[0] <= maxCount) {
66 if (stateCount[0] > maxCount) {
70 // Now also count down from center
72 while (i < maxI && image_->get(centerJ, i) && stateCount[1] <= maxCount) {
76 if (i == maxI || stateCount[1] > maxCount) {
79 while (i < maxI && !image_->get(centerJ, i) && stateCount[2] <= maxCount) {
83 if (stateCount[2] > maxCount) {
87 int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2];
88 if (5 * abs(stateCountTotal - originalStateCountTotal) >= originalStateCountTotal) {
92 return foundPatternCross(stateCount) ? centerFromEnd(stateCount, i) : NAN;
95 Ref<AlignmentPattern> AlignmentPatternFinder::handlePossibleCenter(valarray<int> &stateCount, size_t i, size_t j) {
96 int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2];
97 float centerJ = centerFromEnd(stateCount, j);
98 float centerI = crossCheckVertical(i, (int)centerJ, 2 * stateCount[1], stateCountTotal);
99 if (!isnan(centerI)) {
100 float estimatedModuleSize = (float)(stateCount[0] + stateCount[1] + stateCount[2]) / 3.0f;
101 int max = possibleCenters_->size();
102 for (int index = 0; index < max; index++) {
103 Ref<AlignmentPattern> center((*possibleCenters_)[index]);
104 // Look for about the same center and module size:
105 if (center->aboutEquals(estimatedModuleSize, centerI, centerJ)) {
106 Ref<AlignmentPattern> result(new AlignmentPattern(centerJ, centerI, estimatedModuleSize));
110 AlignmentPattern *tmp = new AlignmentPattern(centerJ, centerI, estimatedModuleSize);
111 // Hadn't found this before; save it
113 possibleCenters_->push_back(tmp);
115 Ref<AlignmentPattern> result;
119 AlignmentPatternFinder::AlignmentPatternFinder(Ref<BitMatrix> image, size_t startX, size_t startY, size_t width,
120 size_t height, float moduleSize) :
121 image_(image), possibleCenters_(new vector<AlignmentPattern *> ()), startX_(startX), startY_(startY),
122 width_(width), height_(height), moduleSize_(moduleSize) {
125 AlignmentPatternFinder::~AlignmentPatternFinder() {
126 for (size_t i = 0; i < possibleCenters_->size(); i++) {
127 (*possibleCenters_)[i]->release();
128 (*possibleCenters_)[i] = 0;
130 delete possibleCenters_;
133 Ref<AlignmentPattern> AlignmentPatternFinder::find() {
134 size_t maxJ = startX_ + width_;
135 size_t middleI = startY_ + (height_ >> 1);
136 // Ref<BitArray> luminanceRow(new BitArray(width_));
137 // We are looking for black/white/black modules in 1:1:1 ratio;
138 // this tracks the number of black/white/black modules seen so far
139 valarray<int> stateCount(0, 3);
140 for (size_t iGen = 0; iGen < height_; iGen++) {
141 // Search from middle outwards
142 size_t i = middleI + ((iGen & 0x01) == 0 ? ((iGen + 1) >> 1) : -((iGen + 1) >> 1));
143 // image_->getBlackRow(i, luminanceRow, startX_, width_);
148 // Burn off leading white pixels before anything else; if we start in the middle of
149 // a white run, it doesn't make sense to count its length, since we don't know if the
150 // white run continued to the left of the start point
151 while (j < maxJ && !image_->get(j, i)) {
154 int currentState = 0;
156 if (image_->get(j, i)) {
158 if (currentState == 1) { // Counting black pixels
159 stateCount[currentState]++;
160 } else { // Counting white pixels
161 if (currentState == 2) { // A winner?
162 if (foundPatternCross(stateCount)) { // Yes
163 Ref<AlignmentPattern> confirmed(handlePossibleCenter(stateCount, i, j));
164 if (confirmed != 0) {
168 stateCount[0] = stateCount[2];
173 stateCount[++currentState]++;
176 } else { // White pixel
177 if (currentState == 1) { // Counting black pixels
180 stateCount[currentState]++;
184 if (foundPatternCross(stateCount)) {
185 Ref<AlignmentPattern> confirmed(handlePossibleCenter(stateCount, i, maxJ));
186 if (confirmed != 0) {
193 // Hmm, nothing we saw was observed and confirmed twice. If we had
194 // any guess at all, return it.
195 if (possibleCenters_->size() > 0) {
196 Ref<AlignmentPattern> center((*possibleCenters_)[0]);
200 throw zxing::ReaderException("Could not find alignment pattern");