#include <algorithm>
#include <zxing/qrcode/detector/FinderPatternFinder.h>
#include <zxing/ReaderException.h>
#include <zxing/DecodeHints.h>
#include <cstring>
using std::sort;
using std::max;
using std::abs;
using std::vector;
using zxing::Ref;
using zxing::qrcode::FinderPatternFinder;
using zxing::qrcode::FinderPattern;
using zxing::qrcode::FinderPatternInfo;
using zxing::BitMatrix;
using zxing::ResultPointCallback;
using zxing::ResultPoint;
using zxing::DecodeHints;
namespace {
class FurthestFromAverageComparator {
private:
const float averageModuleSize_;
public:
FurthestFromAverageComparator(float averageModuleSize) :
averageModuleSize_(averageModuleSize) {
}
int operator()(Ref<FinderPattern> a, Ref<FinderPattern> b) {
float dA = abs(a->getEstimatedModuleSize() - averageModuleSize_);
float dB = abs(b->getEstimatedModuleSize() - averageModuleSize_);
return dA < dB ? -1 : dA == dB ? 0 : 1;
}
};
class CenterComparator {
const float averageModuleSize_;
public:
CenterComparator(float averageModuleSize) :
averageModuleSize_(averageModuleSize) {
}
int operator()(Ref<FinderPattern> a, Ref<FinderPattern> b) {
if (a->getCount() != b->getCount()) {
return b->getCount() - a->getCount();
} else {
float dA = abs(a->getEstimatedModuleSize() - averageModuleSize_);
float dB = abs(b->getEstimatedModuleSize() - averageModuleSize_);
return dA < dB ? 1 : dA == dB ? 0 : -1;
}
}
};
}
int FinderPatternFinder::CENTER_QUORUM = 2;
int FinderPatternFinder::MIN_SKIP = 3;
int FinderPatternFinder::MAX_MODULES = 57;
float FinderPatternFinder::centerFromEnd(int* stateCount, int end) {
return (float)(end - stateCount[4] - stateCount[3]) - stateCount[2] / 2.0f;
}
bool FinderPatternFinder::foundPatternCross(int* stateCount) {
int totalModuleSize = 0;
for (int i = 0; i < 5; i++) {
int count = stateCount[i];
if (count == 0) {
return false;
}
totalModuleSize += count;
}
if (totalModuleSize < 7) {
return false;
}
int moduleSize = (totalModuleSize << 8) / 7;
int maxVariance = moduleSize / 2;
return abs(moduleSize - (stateCount[0] << 8)) < maxVariance &&
abs(moduleSize - (stateCount[1] << 8)) < maxVariance &&
abs(3.0f * moduleSize - (stateCount[2] << 8)) < 3 * maxVariance &&
abs(moduleSize - (stateCount[3] << 8)) < maxVariance &&
abs(moduleSize - (stateCount[4] << 8)) < maxVariance;
}
float FinderPatternFinder::crossCheckVertical(size_t startI, size_t centerJ, int maxCount, int originalStateCountTotal) {
int maxI = image_->getHeight();
int *stateCount = getCrossCheckStateCount();
int i = startI;
while (i >= 0 && image_->get(centerJ, i)) {
stateCount[2]++;
i--;
}
if (i < 0) {
return nan();
}
while (i >= 0 && !image_->get(centerJ, i) && stateCount[1] <= maxCount) {
stateCount[1]++;
i--;
}
if (i < 0 || stateCount[1] > maxCount) {
return nan();
}
while (i >= 0 && image_->get(centerJ, i) && stateCount[0] <= maxCount) {
stateCount[0]++;
i--;
}
if (stateCount[0] > maxCount) {
return nan();
}
i = startI + 1;
while (i < maxI && image_->get(centerJ, i)) {
stateCount[2]++;
i++;
}
if (i == maxI) {
return nan();
}
while (i < maxI && !image_->get(centerJ, i) && stateCount[3] < maxCount) {
stateCount[3]++;
i++;
}
if (i == maxI || stateCount[3] >= maxCount) {
return nan();
}
while (i < maxI && image_->get(centerJ, i) && stateCount[4] < maxCount) {
stateCount[4]++;
i++;
}
if (stateCount[4] >= maxCount) {
return nan();
}
int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] + stateCount[3] + stateCount[4];
if (5 * abs(stateCountTotal - originalStateCountTotal) >= 2 * originalStateCountTotal) {
return nan();
}
return foundPatternCross(stateCount) ? centerFromEnd(stateCount, i) : nan();
}
float FinderPatternFinder::crossCheckHorizontal(size_t startJ, size_t centerI, int maxCount,
int originalStateCountTotal) {
int maxJ = image_->getWidth();
int *stateCount = getCrossCheckStateCount();
int j = startJ;
while (j >= 0 && image_->get(j, centerI)) {
stateCount[2]++;
j--;
}
if (j < 0) {
return nan();
}
while (j >= 0 && !image_->get(j, centerI) && stateCount[1] <= maxCount) {
stateCount[1]++;
j--;
}
if (j < 0 || stateCount[1] > maxCount) {
return nan();
}
while (j >= 0 && image_->get(j, centerI) && stateCount[0] <= maxCount) {
stateCount[0]++;
j--;
}
if (stateCount[0] > maxCount) {
return nan();
}
j = startJ + 1;
while (j < maxJ && image_->get(j, centerI)) {
stateCount[2]++;
j++;
}
if (j == maxJ) {
return nan();
}
while (j < maxJ && !image_->get(j, centerI) && stateCount[3] < maxCount) {
stateCount[3]++;
j++;
}
if (j == maxJ || stateCount[3] >= maxCount) {
return nan();
}
while (j < maxJ && image_->get(j, centerI) && stateCount[4] < maxCount) {
stateCount[4]++;
j++;
}
if (stateCount[4] >= maxCount) {
return nan();
}
int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] + stateCount[3] + stateCount[4];
if (5 * abs(stateCountTotal - originalStateCountTotal) >= originalStateCountTotal) {
return nan();
}
return foundPatternCross(stateCount) ? centerFromEnd(stateCount, j) : nan();
}
bool FinderPatternFinder::handlePossibleCenter(int* stateCount, size_t i, size_t j) {
int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] + stateCount[3] + stateCount[4];
float centerJ = centerFromEnd(stateCount, j);
float centerI = crossCheckVertical(i, (size_t)centerJ, stateCount[2], stateCountTotal);
if (!isnan_z(centerI)) {
centerJ = crossCheckHorizontal((size_t)centerJ, (size_t)centerI, stateCount[2], stateCountTotal);
if (!isnan_z(centerJ) && crossCheckDiagonal((int)centerI, (int)centerJ, stateCount[2], stateCountTotal)) {
float estimatedModuleSize = (float)stateCountTotal / 7.0f;
bool found = false;
size_t max = possibleCenters_.size();
for (size_t index = 0; index < max; index++) {
Ref<FinderPattern> center = possibleCenters_[index];
if (center->aboutEquals(estimatedModuleSize, centerI, centerJ)) {
possibleCenters_[index] = center->combineEstimate(centerI, centerJ, estimatedModuleSize);
found = true;
break;
}
}
if (!found) {
Ref<FinderPattern> newPattern(new FinderPattern(centerJ, centerI, estimatedModuleSize));
possibleCenters_.push_back(newPattern);
if (callback_ != 0) {
callback_->foundPossibleResultPoint(*newPattern);
}
}
return true;
}
}
return false;
}
int FinderPatternFinder::findRowSkip() {
size_t max = possibleCenters_.size();
if (max <= 1) {
return 0;
}
Ref<FinderPattern> firstConfirmedCenter;
for (size_t i = 0; i < max; i++) {
Ref<FinderPattern> center = possibleCenters_[i];
if (center->getCount() >= CENTER_QUORUM) {
if (firstConfirmedCenter == 0) {
firstConfirmedCenter = center;
} else {
hasSkipped_ = true;
return (int)(abs(firstConfirmedCenter->getX() - center->getX()) - abs(firstConfirmedCenter->getY()
- center->getY()))/2;
}
}
}
return 0;
}
bool FinderPatternFinder::haveMultiplyConfirmedCenters() {
int confirmedCount = 0;
float totalModuleSize = 0.0f;
size_t max = possibleCenters_.size();
for (size_t i = 0; i < max; i++) {
Ref<FinderPattern> pattern = possibleCenters_[i];
if (pattern->getCount() >= CENTER_QUORUM) {
confirmedCount++;
totalModuleSize += pattern->getEstimatedModuleSize();
}
}
if (confirmedCount < 3) {
return false;
}
float average = totalModuleSize / (float)max;
float totalDeviation = 0.0f;
for (size_t i = 0; i < max; i++) {
Ref<FinderPattern> pattern = possibleCenters_[i];
totalDeviation += abs(pattern->getEstimatedModuleSize() - average);
}
return totalDeviation <= 0.05f * totalModuleSize;
}
vector< Ref<FinderPattern> > FinderPatternFinder::selectBestPatterns() {
size_t startSize = possibleCenters_.size();
if (startSize < 3) {
throw zxing::ReaderException("Could not find three finder patterns");
}
if (startSize > 3) {
float totalModuleSize = 0.0f;
float square = 0.0f;
for (size_t i = 0; i < startSize; i++) {
float size = possibleCenters_[i]->getEstimatedModuleSize();
totalModuleSize += size;
square += size * size;
}
float average = totalModuleSize / (float) startSize;
float stdDev = (float)sqrt(square / startSize - average * average);
sort(possibleCenters_.begin(), possibleCenters_.end(), FurthestFromAverageComparator(average));
float limit = max(0.2f * average, stdDev);
for (size_t i = 0; i < possibleCenters_.size() && possibleCenters_.size() > 3; i++) {
if (abs(possibleCenters_[i]->getEstimatedModuleSize() - average) > limit) {
possibleCenters_.erase(possibleCenters_.begin()+i);
i--;
}
}
}
if (possibleCenters_.size() > 3) {
float totalModuleSize = 0.0f;
for (size_t i = 0; i < possibleCenters_.size(); i++) {
float size = possibleCenters_[i]->getEstimatedModuleSize();
totalModuleSize += size;
}
float average = totalModuleSize / (float) possibleCenters_.size();
sort(possibleCenters_.begin(), possibleCenters_.end(), CenterComparator(average));
}
if (possibleCenters_.size() > 3) {
possibleCenters_.erase(possibleCenters_.begin()+3,possibleCenters_.end());
}
vector<Ref<FinderPattern> > result(3);
result[0] = possibleCenters_[0];
result[1] = possibleCenters_[1];
result[2] = possibleCenters_[2];
return result;
}
vector<Ref<FinderPattern> > FinderPatternFinder::orderBestPatterns(vector<Ref<FinderPattern> > patterns) {
float abDistance = distance(patterns[0], patterns[1]);
float bcDistance = distance(patterns[1], patterns[2]);
float acDistance = distance(patterns[0], patterns[2]);
Ref<FinderPattern> topLeft;
Ref<FinderPattern> topRight;
Ref<FinderPattern> bottomLeft;
if (bcDistance >= abDistance && bcDistance >= acDistance) {
topLeft = patterns[0];
topRight = patterns[1];
bottomLeft = patterns[2];
} else if (acDistance >= bcDistance && acDistance >= abDistance) {
topLeft = patterns[1];
topRight = patterns[0];
bottomLeft = patterns[2];
} else {
topLeft = patterns[2];
topRight = patterns[0];
bottomLeft = patterns[1];
}
if ((bottomLeft->getY() - topLeft->getY()) * (topRight->getX() - topLeft->getX()) < (bottomLeft->getX()
- topLeft->getX()) * (topRight->getY() - topLeft->getY())) {
Ref<FinderPattern> temp = topRight;
topRight = bottomLeft;
bottomLeft = temp;
}
vector<Ref<FinderPattern> > results(3);
results[0] = bottomLeft;
results[1] = topLeft;
results[2] = topRight;
return results;
}
float FinderPatternFinder::distance(Ref<ResultPoint> p1, Ref<ResultPoint> p2) {
float dx = p1->getX() - p2->getX();
float dy = p1->getY() - p2->getY();
return (float)sqrt(dx * dx + dy * dy);
}
FinderPatternFinder::FinderPatternFinder(Ref<BitMatrix> image,
Ref<ResultPointCallback>const& callback) :
image_(image), possibleCenters_(), hasSkipped_(false), callback_(callback) {
}
Ref<FinderPatternInfo> FinderPatternFinder::find(DecodeHints const& hints) {
bool tryHarder = hints.getTryHarder();
size_t maxI = image_->getHeight();
size_t maxJ = image_->getWidth();
int stateCount[5];
bool done = false;
int iSkip = (3 * maxI) / (4 * MAX_MODULES);
if (iSkip < MIN_SKIP || tryHarder) {
iSkip = MIN_SKIP;
}
BitMatrix& matrix = *image_;
for (size_t i = iSkip - 1; i < maxI && !done; i += iSkip) {
memset(stateCount, 0, sizeof(stateCount));
int currentState = 0;
for (size_t j = 0; j < maxJ; j++) {
if (matrix.get(j, i)) {
if ((currentState & 1) == 1) {
currentState++;
}
stateCount[currentState]++;
} else {
if ((currentState & 1) == 0) {
if (currentState == 4) {
if (foundPatternCross(stateCount)) {
bool confirmed = handlePossibleCenter(stateCount, i, j);
if (confirmed) {
iSkip = 2;
if (hasSkipped_) {
done = haveMultiplyConfirmedCenters();
} else {
int rowSkip = findRowSkip();
if (rowSkip > stateCount[2]) {
i += rowSkip - stateCount[2] - iSkip;
j = maxJ - 1;
}
}
} else {
stateCount[0] = stateCount[2];
stateCount[1] = stateCount[3];
stateCount[2] = stateCount[4];
stateCount[3] = 1;
stateCount[4] = 0;
currentState = 3;
continue;
}
currentState = 0;
memset(stateCount, 0, sizeof(stateCount));
} else {
stateCount[0] = stateCount[2];
stateCount[1] = stateCount[3];
stateCount[2] = stateCount[4];
stateCount[3] = 1;
stateCount[4] = 0;
currentState = 3;
}
} else {
stateCount[++currentState]++;
}
} else {
stateCount[currentState]++;
}
}
}
if (foundPatternCross(stateCount)) {
bool confirmed = handlePossibleCenter(stateCount, i, maxJ);
if (confirmed) {
iSkip = stateCount[0];
if (hasSkipped_) {
done = haveMultiplyConfirmedCenters();
}
}
}
}
vector< Ref <FinderPattern> > patternInfo = selectBestPatterns();
vector< Ref <ResultPoint> > patternInfoResPoints;
for(size_t i=0; i<patternInfo.size(); i++)
patternInfoResPoints.push_back(Ref<ResultPoint>(patternInfo[i]));
ResultPoint::orderBestPatterns(patternInfoResPoints);
patternInfo.clear();
for(size_t i=0; i<patternInfoResPoints.size(); i++)
patternInfo.push_back(Ref<FinderPattern>(static_cast<FinderPattern*>( &*patternInfoResPoints[i] )));
Ref<FinderPatternInfo> result(new FinderPatternInfo(patternInfo));
return result;
}
Ref<BitMatrix> FinderPatternFinder::getImage() {
return image_;
}
vector<Ref<FinderPattern> >& FinderPatternFinder::getPossibleCenters() {
return possibleCenters_;
}
bool FinderPatternFinder::crossCheckDiagonal(int startI, int centerJ, int maxCount, int originalStateCountTotal) const
{
int *stateCount = getCrossCheckStateCount();
int i = 0;
while (startI >= i && centerJ >= i && image_->get(centerJ - i, startI - i)) {
stateCount[2]++;
i++;
}
if (startI < i || centerJ < i) {
return false;
}
while (startI >= i && centerJ >= i && !image_->get(centerJ - i, startI - i) &&
stateCount[1] <= maxCount) {
stateCount[1]++;
i++;
}
if (startI < i || centerJ < i || stateCount[1] > maxCount) {
return false;
}
while (startI >= i && centerJ >= i && image_->get(centerJ - i, startI - i) &&
stateCount[0] <= maxCount) {
stateCount[0]++;
i++;
}
if (stateCount[0] > maxCount) {
return false;
}
int maxI = image_->getHeight();
int maxJ = image_->getWidth();
i = 1;
while (startI + i < maxI && centerJ + i < maxJ && image_->get(centerJ + i, startI + i)) {
stateCount[2]++;
i++;
}
if (startI + i >= maxI || centerJ + i >= maxJ) {
return false;
}
while (startI + i < maxI && centerJ + i < maxJ && !image_->get(centerJ + i, startI + i) &&
stateCount[3] < maxCount) {
stateCount[3]++;
i++;
}
if (startI + i >= maxI || centerJ + i >= maxJ || stateCount[3] >= maxCount) {
return false;
}
while (startI + i < maxI && centerJ + i < maxJ && image_->get(centerJ + i, startI + i) &&
stateCount[4] < maxCount) {
stateCount[4]++;
i++;
}
if (stateCount[4] >= maxCount) {
return false;
}
int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] + stateCount[3] + stateCount[4];
return
abs(stateCountTotal - originalStateCountTotal) < 2 * originalStateCountTotal &&
foundPatternCross(stateCount);
}
int *FinderPatternFinder::getCrossCheckStateCount() const
{
memset(crossCheckStateCount, 0, sizeof(crossCheckStateCount));
return crossCheckStateCount;
}