X-Git-Url: http://git.rot13.org/?p=zxing.git;a=blobdiff_plain;f=cpp%2Fcore%2Fsrc%2Fzxing%2Fqrcode%2Fdetector%2FFinderPatternFinder.cpp;h=52cd1cc13210a6b3ebecdcd871201d27ae7b6632;hp=af6609d9c32ee2e1344bf47433e66cd004226e86;hb=d59aa5593ed5a911b1141be85d1888088c21e859;hpb=1bd3f8056f89c3e7c5163326ce2145de97acb829

diff --git a/cpp/core/src/zxing/qrcode/detector/FinderPatternFinder.cpp b/cpp/core/src/zxing/qrcode/detector/FinderPatternFinder.cpp
index af6609d9..52cd1cc1 100644
--- a/cpp/core/src/zxing/qrcode/detector/FinderPatternFinder.cpp
+++ b/cpp/core/src/zxing/qrcode/detector/FinderPatternFinder.cpp
@@ -20,8 +20,11 @@
 
 #include <zxing/qrcode/detector/FinderPatternFinder.h>
 #include <zxing/ReaderException.h>
+#include <zxing/DecodeHints.h>
 #include <vector>
 #include <cmath>
+#include <cstdlib>
+#include <algorithm>
 
 namespace zxing {
 namespace qrcode {
@@ -32,20 +35,23 @@ class ClosestToAverageComparator {
 private:
   float averageModuleSize_;
 public:
+  ClosestToAverageComparator() : averageModuleSize_(0.0f) { }
+  
   ClosestToAverageComparator(float averageModuleSize) :
       averageModuleSize_(averageModuleSize) {
   }
-  int operator()(Ref<FinderPattern> a, Ref<FinderPattern> b) {
+  bool 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 ? 1 : 0;
+    return dA < dB;
   }
 };
 
 class CenterComparator {
 public:
-  int operator()(Ref<FinderPattern> a, Ref<FinderPattern> b) {
-    return b->getCount() - a->getCount();
+  bool operator()(Ref<FinderPattern> a, Ref<FinderPattern> b) {
+    // N.B.: we want the result in descending order ...
+    return a->getCount() > b->getCount();
   }
 };
 
@@ -133,10 +139,10 @@ float FinderPatternFinder::crossCheckVertical(size_t startI, size_t centerJ, int
     return NAN;
   }
 
-  // If we found a finder-pattern-like section, but its size is more than 20% different than
+  // If we found a finder-pattern-like section, but its size is more than 40% different than
   // the original, assume it's a false positive
   int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] + stateCount[3] + stateCount[4];
-  if (5 * abs(stateCountTotal - originalStateCountTotal) >= originalStateCountTotal) {
+  if (5 * abs(stateCountTotal - originalStateCountTotal) >= 2 * originalStateCountTotal) {
     return NAN;
   }
 
@@ -230,6 +236,9 @@ bool FinderPatternFinder::handlePossibleCenter(int* stateCount, size_t i, size_t
       if (!found) {
         Ref<FinderPattern> newPattern(new FinderPattern(centerJ, centerI, estimatedModuleSize));
         possibleCenters_.push_back(newPattern);
+        if (callback_ != 0) {
+          callback_->foundPossibleResultPoint(*newPattern);
+        }
       }
       return true;
     }
@@ -256,7 +265,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;
       }
     }
   }
@@ -280,51 +289,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<FinderPattern> pattern = possibleCenters_[i];
     totalDeviation += abs(pattern->getEstimatedModuleSize() - average);
   }
-  return totalDeviation <= 0.15f * totalModuleSize;
+  return totalDeviation <= 0.05f * totalModuleSize;
 }
 
 vector<Ref<FinderPattern> > 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<Ref<FinderPattern> > 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<Ref<FinderPattern> > result(3);
   result[0] = possibleCenters_[0];
@@ -381,11 +387,14 @@ float FinderPatternFinder::distance(Ref<ResultPoint> p1, Ref<ResultPoint> p2) {
   return (float)sqrt(dx * dx + dy * dy);
 }
 
-FinderPatternFinder::FinderPatternFinder(Ref<BitMatrix> image) :
-    image_(image), possibleCenters_(), hasSkipped_(false) {
+FinderPatternFinder::FinderPatternFinder(Ref<BitMatrix> image,
+                                           Ref<ResultPointCallback>const& callback) :
+    image_(image), possibleCenters_(), hasSkipped_(false), callback_(callback) {
 }
 
-Ref<FinderPatternInfo> FinderPatternFinder::find() {
+Ref<FinderPatternInfo> FinderPatternFinder::find(DecodeHints const& hints) {
+  bool tryHarder = hints.getTryHarder();
+
   size_t maxI = image_->getHeight();
   size_t maxJ = image_->getWidth();
 
@@ -393,7 +402,7 @@ Ref<FinderPatternInfo> FinderPatternFinder::find() {
   // We are looking for black/white/black/white/black modules in
   // 1:1:3:1:1 ratio; this tracks the number of such modules seen so far
 
-  // As this is used often, we use an integer array instead of valarray
+  // As this is used often, we use an integer array instead of vector
   int stateCount[5];
   bool done = false;
 
@@ -403,7 +412,10 @@ Ref<FinderPatternInfo> 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_;
@@ -430,7 +442,9 @@ Ref<FinderPatternInfo> 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 {