Improved approach to 1D decoding -- better use of integer math by scaling pattern...

git-svn-id: http://zxing.googlecode.com/svn/trunk@441 59b500cc-1b3d-0410-9834-0bbf25fbcc57

diff --git a/core/src/com/google/zxing/oned/AbstractOneDReader.java b/core/src/com/google/zxing/oned/AbstractOneDReader.java
index d642547..86f0a7b 100644 (file)
--- a/core/src/com/google/zxing/oned/AbstractOneDReader.java
+++ b/core/src/com/google/zxing/oned/AbstractOneDReader.java
@@ -36,6 +36,7 @@ import java.util.Hashtable;
 public abstract class AbstractOneDReader implements OneDReader {
 
   private static final int INTEGER_MATH_SHIFT = 8;
+  public static final int PATTERN_MATCH_RESULT_SCALE_FACTOR = 256;
 
   public final Result decode(MonochromeBitmapSource image) throws ReaderException {
     return decode(image, null);
@@ -183,12 +184,13 @@ public abstract class AbstractOneDReader implements OneDReader {
    *
    * @param counters observed counters
    * @param pattern expected pattern
+   * @param maxIndividualVariance
    * @return ratio of total variance between counters and pattern compared to total pattern size,
    *  where the ratio has been multiplied by 256. So, 0 means no variance (perfect match); 256 means
    *  the total variance between counters and patterns equals the pattern length, higher values mean
    *  even more variance
    */
-  static int patternMatchVariance(int[] counters, int[] pattern) {
+  static int patternMatchVariance(int[] counters, int[] pattern, int maxIndividualVariance) {
     int numCounters = counters.length;
     int total = 0;
     int patternLength = 0;
@@ -204,16 +206,20 @@ public abstract class AbstractOneDReader implements OneDReader {
     // We're going to fake floating-point math in integers. We just need to use more bits.
     // Scale up patternLength so that intermediate values below like scaledCounter will have
     // more "significant digits"
-    patternLength <<= INTEGER_MATH_SHIFT;
-    int patternRatio = patternLength / total;
+    int unitBarWidth = (total << INTEGER_MATH_SHIFT) / patternLength;
+    maxIndividualVariance *= unitBarWidth;
 
     int totalVariance = 0;
     for (int x = 0; x < numCounters; x++) {
-      int scaledCounter = counters[x] * patternRatio;
-      int width = pattern[x] << INTEGER_MATH_SHIFT;
-      totalVariance += scaledCounter > width ? scaledCounter - width : width - scaledCounter;
+      int counter = counters[x] << INTEGER_MATH_SHIFT;
+      int scaledPattern = pattern[x] * unitBarWidth;
+      int variance = counter > scaledPattern ? counter - scaledPattern : scaledPattern - counter;
+      if (variance > maxIndividualVariance) {
+        return Integer.MAX_VALUE;
+      }
+      totalVariance += variance; 
     }
-    return (totalVariance << 8) / patternLength;
+    return totalVariance / total;
   }
 
   // This declaration should not be necessary, since this class is

diff --git a/core/src/com/google/zxing/oned/AbstractUPCEANReader.java b/core/src/com/google/zxing/oned/AbstractUPCEANReader.java
index f4b1fa6..4aa11f4 100644 (file)
--- a/core/src/com/google/zxing/oned/AbstractUPCEANReader.java
+++ b/core/src/com/google/zxing/oned/AbstractUPCEANReader.java
@@ -35,7 +35,8 @@ import java.util.Hashtable;
  */
 public abstract class AbstractUPCEANReader extends AbstractOneDReader implements UPCEANReader {
 
-  private static final int MAX_VARIANCE = 104;
+  private static final int MAX_AVG_VARIANCE = (int) (PATTERN_MATCH_RESULT_SCALE_FACTOR * 0.40625f);
+  private static final int MAX_INDIVIDUAL_VARIANCE = (int) (PATTERN_MATCH_RESULT_SCALE_FACTOR * 0.5f);
 
   /**
    * Start/end guard pattern.
@@ -207,7 +208,7 @@ public abstract class AbstractUPCEANReader extends AbstractOneDReader implements
         counters[counterPosition]++;
       } else {
         if (counterPosition == patternLength - 1) {
-          if (patternMatchVariance(counters, pattern) < MAX_VARIANCE) {
+          if (patternMatchVariance(counters, pattern, MAX_INDIVIDUAL_VARIANCE) < MAX_AVG_VARIANCE) {
             return new int[]{patternStart, x};
           }
           patternStart += counters[0] + counters[1];
@@ -242,12 +243,12 @@ public abstract class AbstractUPCEANReader extends AbstractOneDReader implements
   static int decodeDigit(BitArray row, int[] counters, int rowOffset, int[][] patterns)
       throws ReaderException {
     recordPattern(row, rowOffset, counters);
-    int bestVariance = MAX_VARIANCE; // worst variance we'll accept
+    int bestVariance = MAX_AVG_VARIANCE; // worst variance we'll accept
     int bestMatch = -1;
     int max = patterns.length;
     for (int i = 0; i < max; i++) {
       int[] pattern = patterns[i];
-      int variance = patternMatchVariance(counters, pattern);
+      int variance = patternMatchVariance(counters, pattern, MAX_INDIVIDUAL_VARIANCE);
       if (variance < bestVariance) {
         bestVariance = variance;
         bestMatch = i;

diff --git a/core/src/com/google/zxing/oned/Code128Reader.java b/core/src/com/google/zxing/oned/Code128Reader.java
index 1fc430c..8b027bb 100644 (file)
--- a/core/src/com/google/zxing/oned/Code128Reader.java
+++ b/core/src/com/google/zxing/oned/Code128Reader.java
@@ -142,7 +142,8 @@ public final class Code128Reader extends AbstractOneDReader {
       {2, 3, 3, 1, 1, 1, 2}
   };
 
-  private static final int MAX_VARIANCE = 56;
+  private static final int MAX_AVG_VARIANCE = (int) (PATTERN_MATCH_RESULT_SCALE_FACTOR * 0.1875f);
+  private static final int MAX_INDIVIDUAL_VARIANCE = (int) (PATTERN_MATCH_RESULT_SCALE_FACTOR * 0.25f);
 
   private static final int CODE_SHIFT = 98;
 
@@ -183,10 +184,10 @@ public final class Code128Reader extends AbstractOneDReader {
         counters[counterPosition]++;
       } else {
         if (counterPosition == patternLength - 1) {
-          int bestVariance = MAX_VARIANCE;
+          int bestVariance = MAX_AVG_VARIANCE;
           int bestMatch = -1;
           for (int startCode = CODE_START_A; startCode <= CODE_START_C; startCode++) {
-            int variance = patternMatchVariance(counters, CODE_PATTERNS[startCode]);
+            int variance = patternMatchVariance(counters, CODE_PATTERNS[startCode], MAX_INDIVIDUAL_VARIANCE);
             if (variance < bestVariance) {
               bestVariance = variance;
               bestMatch = startCode;
@@ -214,11 +215,11 @@ public final class Code128Reader extends AbstractOneDReader {
 
   private static int decodeCode(BitArray row, int[] counters, int rowOffset) throws ReaderException {
     recordPattern(row, rowOffset, counters);
-    int bestVariance = MAX_VARIANCE; // worst variance we'll accept
+    int bestVariance = MAX_AVG_VARIANCE; // worst variance we'll accept
     int bestMatch = -1;
     for (int d = 0; d < CODE_PATTERNS.length; d++) {
       int[] pattern = CODE_PATTERNS[d];
-      int variance = patternMatchVariance(counters, pattern);
+      int variance = patternMatchVariance(counters, pattern, MAX_INDIVIDUAL_VARIANCE);
       if (variance < bestVariance) {
         bestVariance = variance;
         bestMatch = d;

diff --git a/core/test/src/com/google/zxing/common/FalsePositivesBlackBoxTestCase.java b/core/test/src/com/google/zxing/common/FalsePositivesBlackBoxTestCase.java
index d078c15..9eef211 100644 (file)
--- a/core/test/src/com/google/zxing/common/FalsePositivesBlackBoxTestCase.java
+++ b/core/test/src/com/google/zxing/common/FalsePositivesBlackBoxTestCase.java
@@ -35,7 +35,7 @@ import java.io.IOException;
 public final class FalsePositivesBlackBoxTestCase extends AbstractBlackBoxTestCase {
 
   // This number should be reduced as we get better at rejecting false positives.
-  private static final int FALSE_POSITIVES_ALLOWED = 44;
+  private static final int FALSE_POSITIVES_ALLOWED = 23;
 
   // Use the multiformat reader to evaluate all decoders in the system.
   public FalsePositivesBlackBoxTestCase() {