From 985fc411759edc0a9996067d8ee9c55976614200 Mon Sep 17 00:00:00 2001 From: srowen Date: Sat, 7 Aug 2010 13:22:47 +0000 Subject: [PATCH] Issue 497 git-svn-id: http://zxing.googlecode.com/svn/trunk@1515 59b500cc-1b3d-0410-9834-0bbf25fbcc57 --- cpp/core/src/zxing/qrcode/QRCodeReader.cpp | 2 +- .../src/zxing/qrcode/detector/Detector.cpp | 54 ++++++++------ cpp/core/src/zxing/qrcode/detector/Detector.h | 5 +- .../qrcode/detector/FinderPatternFinder.cpp | 70 ++++++++++--------- .../qrcode/detector/FinderPatternFinder.h | 5 +- 5 files changed, 79 insertions(+), 57 deletions(-) diff --git a/cpp/core/src/zxing/qrcode/QRCodeReader.cpp b/cpp/core/src/zxing/qrcode/QRCodeReader.cpp index da116441..cc92e93e 100644 --- a/cpp/core/src/zxing/qrcode/QRCodeReader.cpp +++ b/cpp/core/src/zxing/qrcode/QRCodeReader.cpp @@ -43,7 +43,7 @@ namespace zxing { cout << "(1) created detector " << &detector << "\n" << flush; #endif - Ref detectorResult(detector.detect()); + Ref detectorResult(detector.detect(hints)); #ifdef DEBUG cout << "(2) detected, have detectorResult " << detectorResult.object_ << "\n" << flush; #endif diff --git a/cpp/core/src/zxing/qrcode/detector/Detector.cpp b/cpp/core/src/zxing/qrcode/detector/Detector.cpp index a50424c9..6c325586 100644 --- a/cpp/core/src/zxing/qrcode/detector/Detector.cpp +++ b/cpp/core/src/zxing/qrcode/detector/Detector.cpp @@ -25,6 +25,7 @@ #include #include #include +#include #include #include #include @@ -42,9 +43,9 @@ Ref Detector::getImage() { return image_; } -Ref Detector::detect() { +Ref Detector::detect(DecodeHints const& hints) { FinderPatternFinder finder(image_); - Ref info(finder.find()); + Ref info(finder.find(hints)); Ref topLeft(info->getTopLeft()); Ref topRight(info->getTopRight()); @@ -176,26 +177,32 @@ float Detector::calculateModuleSizeOneWay(Ref pattern, Ref= (int)image_->getWidth()) { - otherToX = image_->getWidth(); - } - int otherToY = fromY - (toY - fromY); - if (otherToY < 0) { - otherToY = -1; - } else if (otherToY >= (int)image_->getHeight()) { - otherToY = image_->getHeight(); - } - result += sizeOfBlackWhiteBlackRun(fromX, fromY, otherToX, otherToY); - return result - 1.0f; // -1 because we counted the middle pixel twice + float result = sizeOfBlackWhiteBlackRun(fromX, fromY, toX, toY); + + // Now count other way -- don't run off image though of course + float scale = 1.0f; + int otherToX = fromX - (toX - fromX); + if (otherToX < 0) { + scale = (float) fromX / (float) (fromX - otherToX); + otherToX = 0; + } else if (otherToX >= (int)image_->getWidth()) { + scale = (float) (image_->getWidth() - 1 - fromX) / (float) (otherToX - fromX); + otherToX = image_->getWidth() - 1; + } + int otherToY = (int) (fromY - (toY - fromY) * scale); + + scale = 1.0f; + if (otherToY < 0) { + scale = (float) fromY / (float) (fromY - otherToY); + otherToY = 0; + } else if (otherToY >= (int)image_->getHeight()) { + scale = (float) (image_->getHeight() - 1 - fromY) / (float) (otherToY - fromY); + otherToY = image_->getHeight() - 1; + } + otherToX = (int) (fromX + (otherToX - fromX) * scale); + + result += sizeOfBlackWhiteBlackRun(fromX, fromY, otherToX, otherToY); + return result - 1.0f; // -1 because we counted the middle pixel twice } float Detector::sizeOfBlackWhiteBlackRun(int fromX, int fromY, int toX, int toY) { @@ -254,6 +261,9 @@ Ref Detector::findAlignmentInRegion(float overallEstModuleSize int allowance = (int)(allowanceFactor * overallEstModuleSize); int alignmentAreaLeftX = max(0, estAlignmentX - allowance); int alignmentAreaRightX = min((int)(image_->getWidth() - 1), estAlignmentX + allowance); + if (alignmentAreaRightX - alignmentAreaLeftX < overallEstModuleSize * 3) { + throw zxing::ReaderException("region too small to hold alignment pattern"); + } int alignmentAreaTopY = max(0, estAlignmentY - allowance); int alignmentAreaBottomY = min((int)(image_->getHeight() - 1), estAlignmentY + allowance); diff --git a/cpp/core/src/zxing/qrcode/detector/Detector.h b/cpp/core/src/zxing/qrcode/detector/Detector.h index 2bafe801..e63aac19 100644 --- a/cpp/core/src/zxing/qrcode/detector/Detector.h +++ b/cpp/core/src/zxing/qrcode/detector/Detector.h @@ -27,6 +27,9 @@ #include namespace zxing { + +class DecodeHints; + namespace qrcode { class Detector : public Counted { @@ -51,7 +54,7 @@ public: ResultPoint > bottomLeft, Ref alignmentPattern, int dimension); Detector(Ref image); - Ref detect(); + Ref detect(DecodeHints const& hints); }; } } diff --git a/cpp/core/src/zxing/qrcode/detector/FinderPatternFinder.cpp b/cpp/core/src/zxing/qrcode/detector/FinderPatternFinder.cpp index 7dbd3343..fa02af3c 100644 --- a/cpp/core/src/zxing/qrcode/detector/FinderPatternFinder.cpp +++ b/cpp/core/src/zxing/qrcode/detector/FinderPatternFinder.cpp @@ -20,6 +20,7 @@ #include #include +#include #include #include #include @@ -49,7 +50,8 @@ public: class CenterComparator { public: bool operator()(Ref a, Ref b) { - return a->getCount() < b->getCount(); + // N.B.: we want the result in descending order ... + return a->getCount() > b->getCount(); } }; @@ -260,7 +262,7 @@ int FinderPatternFinder::findRowSkip() { // This is the case where you find top left first. Draw it out. hasSkipped_ = true; return (int)(abs(firstConfirmedCenter->getX() - center->getX()) - abs(firstConfirmedCenter->getY() - - center->getY())); + - center->getY()))/2; } } } @@ -284,51 +286,48 @@ bool FinderPatternFinder::haveMultiplyConfirmedCenters() { // OK, we have at least 3 confirmed centers, but, it's possible that one is a "false positive" // and that we need to keep looking. We detect this by asking if the estimated module sizes // vary too much. We arbitrarily say that when the total deviation from average exceeds - // 15% of the total module size estimates, it's too much. + // 5% of the total module size estimates, it's too much. float average = totalModuleSize / max; float totalDeviation = 0.0f; for (size_t i = 0; i < max; i++) { Ref pattern = possibleCenters_[i]; totalDeviation += abs(pattern->getEstimatedModuleSize() - average); } - return totalDeviation <= 0.15f * totalModuleSize; + return totalDeviation <= 0.05f * totalModuleSize; } vector > FinderPatternFinder::selectBestPatterns() { - sort(possibleCenters_.begin(), possibleCenters_.end(), CenterComparator()); - size_t size = 0; - size_t max = possibleCenters_.size(); - while (size < max) { - if (possibleCenters_[size]->getCount() < CENTER_QUORUM) { - break; - } - size++; - } + size_t startSize = possibleCenters_.size(); - if (size < 3) { + if (startSize < 3) { // Couldn't find enough finder patterns throw zxing::ReaderException("Could not find three finder patterns"); } - if (size == 3) { - // Found just enough -- hope these are good! - vector > result(3); - result[0] = possibleCenters_[0]; - result[1] = possibleCenters_[1]; - result[2] = possibleCenters_[2]; - return result; + // Filter outlier possibilities whose module size is too different + if (startSize > 3) { + // But we can only afford to do so if we have at least 4 possibilities to choose from + float totalModuleSize = 0.0f; + for (size_t i = 0; i < startSize; i++) { + totalModuleSize += possibleCenters_[i]->getEstimatedModuleSize(); + } + float average = totalModuleSize / (float) startSize; + for (size_t i = 0; i < possibleCenters_.size() && possibleCenters_.size() > 3; i++) { + if (abs(possibleCenters_[i]->getEstimatedModuleSize() - average) > 0.2f * average) { + possibleCenters_.erase(possibleCenters_.begin()+i); + i--; + } + } } - // Hmm, multiple found. We need to pick the best three. Find the most - // popular ones whose module size is nearest the average - // This does not work for multiple qr codes in the same image - float averageModuleSize = 0.0f; - for (size_t i = 0; i < size; i++) { - averageModuleSize += possibleCenters_[i]->getEstimatedModuleSize(); + if (possibleCenters_.size() > 3) { + // Throw away all but those first size candidate points we found. + sort(possibleCenters_.begin(), possibleCenters_.end(), CenterComparator()); } - averageModuleSize /= (float)size; - sort(possibleCenters_.begin(), possibleCenters_.end(), ClosestToAverageComparator(averageModuleSize)); + if (possibleCenters_.size() > 3) { + possibleCenters_.erase(possibleCenters_.begin()+3,possibleCenters_.end()); + } vector > result(3); result[0] = possibleCenters_[0]; @@ -389,7 +388,9 @@ FinderPatternFinder::FinderPatternFinder(Ref image) : image_(image), possibleCenters_(), hasSkipped_(false) { } -Ref FinderPatternFinder::find() { +Ref FinderPatternFinder::find(DecodeHints const& hints) { + bool tryHarder = hints.getTryHarder(); + size_t maxI = image_->getHeight(); size_t maxJ = image_->getWidth(); @@ -407,7 +408,10 @@ Ref FinderPatternFinder::find() { // modules in size. This gives the smallest number of pixels the center // could be, so skip this often. When trying harder, look for all // QR versions regardless of how dense they are. - size_t iSkip = MIN_SKIP; + int iSkip = (3 * maxI) / (4 * MAX_MODULES); + if (iSkip < MIN_SKIP || tryHarder) { + iSkip = MIN_SKIP; + } // This is slightly faster than using the Ref. Efficiency is important here BitMatrix& matrix = *image_; @@ -434,7 +438,9 @@ Ref FinderPatternFinder::find() { if (foundPatternCross(stateCount)) { // Yes bool confirmed = handlePossibleCenter(stateCount, i, j); if (confirmed) { - iSkip = 1; // Go back to examining each line + // Start examining every other line. Checking each line turned out to be too + // expensive and didn't improve performance. + iSkip = 2; if (hasSkipped_) { done = haveMultiplyConfirmedCenters(); } else { diff --git a/cpp/core/src/zxing/qrcode/detector/FinderPatternFinder.h b/cpp/core/src/zxing/qrcode/detector/FinderPatternFinder.h index afa2d89f..ac8489ea 100644 --- a/cpp/core/src/zxing/qrcode/detector/FinderPatternFinder.h +++ b/cpp/core/src/zxing/qrcode/detector/FinderPatternFinder.h @@ -27,6 +27,9 @@ #include namespace zxing { + +class DecodeHints; + namespace qrcode { class FinderPatternFinder { @@ -56,7 +59,7 @@ private: public: static float distance(Ref p1, Ref p2); FinderPatternFinder(Ref image); - Ref find(); + Ref find(DecodeHints const& hints); }; } } -- 2.20.1