Improve detector logic to throw out false positive finder patterns in a more reasonab...

[zxing.git] / core / src / com / google / zxing / qrcode / detector / FinderPatternFinder.java

diff --git a/core/src/com/google/zxing/qrcode/detector/FinderPatternFinder.java b/core/src/com/google/zxing/qrcode/detector/FinderPatternFinder.java
index 902c4bb..199b895 100755 (executable)
--- 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"\r
     // and that we need to keep looking. We detect this by asking if the estimated module sizes\r
     // vary too much. We arbitrarily say that when the total deviation from average exceeds\r
-    // 15% of the total module size estimates, it's too much.\r
+    // 5% of the total module size estimates, it's too much.\r
     float average = totalModuleSize / (float) max;\r
     float totalDeviation = 0.0f;\r
     for (int i = 0; i < max; i++) {\r
@@ -480,25 +480,35 @@ public class FinderPatternFinder {
    * @throws ReaderException if 3 such finder patterns do not exist\r
    */\r
   private FinderPattern[] selectBestPatterns() throws ReaderException {\r
-    if (possibleCenters.size() < 3) {\r
+\r
+    int startSize = possibleCenters.size();\r
+    if (startSize < 3) {\r
       // Couldn't find enough finder patterns\r
       throw ReaderException.getInstance();\r
     }\r
-    Collections.insertionSort(possibleCenters, new CenterComparator());\r
+\r
+    // Filter outlier possibilities whose module size is too different\r
+    if (startSize > 3) {\r
+      // But we can only afford to do so if we have at least 4 possibilities to choose from\r
+      float totalModuleSize = 0.0f;\r
+      for (int i = 0; i < startSize; i++) {\r
+        totalModuleSize += ((FinderPattern) possibleCenters.get(i)).getEstimatedModuleSize();\r
+      }\r
+      float average = totalModuleSize / (float) startSize;\r
+      for (int i = 0; i < possibleCenters.size() && possibleCenters.size() > 3; i++) {\r
+        FinderPattern pattern = (FinderPattern) possibleCenters.get(i);\r
+        if (Math.abs(pattern.getEstimatedModuleSize() - average) > 0.2f * average) {\r
+          possibleCenters.remove(i);\r
+          i--;\r
+        }\r
+      }\r
+    }\r
 \r
     if (possibleCenters.size() > 3) {\r
       // Throw away all but those first size candidate points we found.\r
+      Collections.insertionSort(possibleCenters, new CenterComparator());      \r
       possibleCenters.setSize(3);\r
     }\r
-    //  We need to pick the best three. Find the most\r
-    // popular ones whose module size is nearest the average\r
-    float averageModuleSize = 0.0f;\r
-    for (int i = 0; i < 3; i++) {\r
-      averageModuleSize += ((FinderPattern) possibleCenters.elementAt(i)).getEstimatedModuleSize();\r
-    }\r
-    averageModuleSize /= 3.0f;\r
-    // We don't have java.util.Collections in J2ME\r
-    Collections.insertionSort(possibleCenters, new ClosestToAverageComparator(averageModuleSize));\r
 \r
     return new FinderPattern[]{\r
         (FinderPattern) possibleCenters.elementAt(0),\r
@@ -516,22 +526,4 @@ public class FinderPatternFinder {
     }\r
   }\r
 \r
-  /**\r
-   * <p>Orders by variance from average module size, ascending.</p>\r
-   */\r
-  private static class ClosestToAverageComparator implements Comparator {\r
-    private final float averageModuleSize;\r
-\r
-    private ClosestToAverageComparator(float averageModuleSize) {\r
-      this.averageModuleSize = averageModuleSize;\r
-    }\r
-\r
-    public int compare(Object center1, Object center2) {\r
-      return Math.abs(((FinderPattern) center1).getEstimatedModuleSize() - averageModuleSize) <\r
-          Math.abs(((FinderPattern) center2).getEstimatedModuleSize() - averageModuleSize) ?\r
-          -1 :\r
-          1;\r
-    }\r
-  }\r
-\r
 }\r