From abe15d5bb8bd23019ca9c4ab48f9385c6a92bd0e Mon Sep 17 00:00:00 2001
From: srowen <srowen@59b500cc-1b3d-0410-9834-0bbf25fbcc57>
Date: Sun, 23 Aug 2009 15:32:01 +0000
Subject: [PATCH] Improve detector logic to throw out false positive finder
 patterns in a more reasonable manner. Current logic didn't quite achieve its
 goal in some corner cases and needed rethinking and some simplification.
 Fixes a reported failure from the group list. Net change in passed test cases
 is -1 otherwise (for 270 degree rotation -- not vital) so I consider it a net
 tiny win.

git-svn-id: http://zxing.googlecode.com/svn/trunk@1039 59b500cc-1b3d-0410-9834-0bbf25fbcc57
---
 .../qrcode/detector/FinderPatternFinder.java  | 52 ++++++++-----------
 .../zxing/qrcode/QRCodeBlackBox2TestCase.java |  6 +--
 2 files changed, 25 insertions(+), 33 deletions(-)

diff --git a/core/src/com/google/zxing/qrcode/detector/FinderPatternFinder.java b/core/src/com/google/zxing/qrcode/detector/FinderPatternFinder.java
index 902c4bbb..199b895a 100755
--- a/core/src/com/google/zxing/qrcode/detector/FinderPatternFinder.java
+++ b/core/src/com/google/zxing/qrcode/detector/FinderPatternFinder.java
@@ -463,7 +463,7 @@ public class FinderPatternFinder {
     // 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 / (float) max;
     float totalDeviation = 0.0f;
     for (int i = 0; i < max; i++) {
@@ -480,25 +480,35 @@ public class FinderPatternFinder {
    * @throws ReaderException if 3 such finder patterns do not exist
    */
   private FinderPattern[] selectBestPatterns() throws ReaderException {
-    if (possibleCenters.size() < 3) {
+
+    int startSize = possibleCenters.size();
+    if (startSize < 3) {
       // Couldn't find enough finder patterns
       throw ReaderException.getInstance();
     }
-    Collections.insertionSort(possibleCenters, new CenterComparator());
+
+    // 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 (int i = 0; i < startSize; i++) {
+        totalModuleSize += ((FinderPattern) possibleCenters.get(i)).getEstimatedModuleSize();
+      }
+      float average = totalModuleSize / (float) startSize;
+      for (int i = 0; i < possibleCenters.size() && possibleCenters.size() > 3; i++) {
+        FinderPattern pattern = (FinderPattern) possibleCenters.get(i);
+        if (Math.abs(pattern.getEstimatedModuleSize() - average) > 0.2f * average) {
+          possibleCenters.remove(i);
+          i--;
+        }
+      }
+    }
 
     if (possibleCenters.size() > 3) {
       // Throw away all but those first size candidate points we found.
+      Collections.insertionSort(possibleCenters, new CenterComparator());      
       possibleCenters.setSize(3);
     }
-    //  We need to pick the best three. Find the most
-    // popular ones whose module size is nearest the average
-    float averageModuleSize = 0.0f;
-    for (int i = 0; i < 3; i++) {
-      averageModuleSize += ((FinderPattern) possibleCenters.elementAt(i)).getEstimatedModuleSize();
-    }
-    averageModuleSize /= 3.0f;
-    // We don't have java.util.Collections in J2ME
-    Collections.insertionSort(possibleCenters, new ClosestToAverageComparator(averageModuleSize));
 
     return new FinderPattern[]{
         (FinderPattern) possibleCenters.elementAt(0),
@@ -516,22 +526,4 @@ public class FinderPatternFinder {
     }
   }
 
-  /**
-   * <p>Orders by variance from average module size, ascending.</p>
-   */
-  private static class ClosestToAverageComparator implements Comparator {
-    private final float averageModuleSize;
-
-    private ClosestToAverageComparator(float averageModuleSize) {
-      this.averageModuleSize = averageModuleSize;
-    }
-
-    public int compare(Object center1, Object center2) {
-      return Math.abs(((FinderPattern) center1).getEstimatedModuleSize() - averageModuleSize) <
-          Math.abs(((FinderPattern) center2).getEstimatedModuleSize() - averageModuleSize) ?
-          -1 :
-          1;
-    }
-  }
-
 }
diff --git a/core/test/src/com/google/zxing/qrcode/QRCodeBlackBox2TestCase.java b/core/test/src/com/google/zxing/qrcode/QRCodeBlackBox2TestCase.java
index 2f88b46c..658b3238 100644
--- a/core/test/src/com/google/zxing/qrcode/QRCodeBlackBox2TestCase.java
+++ b/core/test/src/com/google/zxing/qrcode/QRCodeBlackBox2TestCase.java
@@ -28,9 +28,9 @@ public final class QRCodeBlackBox2TestCase extends AbstractBlackBoxTestCase {
   public QRCodeBlackBox2TestCase() {
     super("test/data/blackbox/qrcode-2", new MultiFormatReader(), BarcodeFormat.QR_CODE);
     addTest(23, 23, 0.0f);
-    addTest(20, 20, 90.0f);
-    addTest(21, 21, 180.0f);
-    addTest(19, 19, 270.0f);
+    addTest(21, 21, 90.0f);
+    addTest(20, 20, 180.0f);
+    addTest(18, 18, 270.0f);
   }
 
 }
\ No newline at end of file
-- 
2.20.1