Implemented row sampling for histograms and tweaked the valley finding algorithm

for better performance.

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

diff --git a/core/src/com/google/zxing/common/BlackPointEstimator.java b/core/src/com/google/zxing/common/BlackPointEstimator.java
index 2203fd3..32c8088 100644 (file)
--- a/core/src/com/google/zxing/common/BlackPointEstimator.java
+++ b/core/src/com/google/zxing/common/BlackPointEstimator.java
@@ -36,21 +36,21 @@ public final class BlackPointEstimator {
    * decides which bucket of values corresponds to the black point -- which bucket contains the\r
    * count of the brightest luminance values that should be considered "black".</p>\r
    *\r
-   * @param luminanceBuckets an array of <em>counts</em> of luminance values\r
+   * @param histogram an array of <em>counts</em> of luminance values\r
    * @return index within argument of bucket corresponding to brightest values which should be\r
    *  considered "black"\r
    */\r
-  public static int estimate(int[] luminanceBuckets) {\r
+  public static int estimate(int[] histogram) {\r
 \r
-    int numBuckets = luminanceBuckets.length;\r
+    int numBuckets = histogram.length;\r
 \r
     // Find tallest peak in histogram\r
     int firstPeak = 0;\r
     int firstPeakSize = 0;\r
     for (int i = 0; i < numBuckets; i++) {\r
-      if (luminanceBuckets[i] > firstPeakSize) {\r
+      if (histogram[i] > firstPeakSize) {\r
         firstPeak = i;\r
-        firstPeakSize = luminanceBuckets[i];\r
+        firstPeakSize = histogram[i];\r
       }\r
     }\r
 \r
@@ -61,7 +61,7 @@ public final class BlackPointEstimator {
     for (int i = 0; i < numBuckets; i++) {\r
       int distanceToBiggest = i - firstPeak;\r
       // Encourage more distant second peaks by multiplying by square of distance\r
-      int score = luminanceBuckets[i] * distanceToBiggest * distanceToBiggest;\r
+      int score = histogram[i] * distanceToBiggest * distanceToBiggest;\r
       if (score > secondPeakScore) {\r
         secondPeak = i;\r
         secondPeakScore = score;\r
@@ -75,13 +75,13 @@ public final class BlackPointEstimator {
       secondPeak = temp;\r
     }\r
 \r
-    // Find a valley between them that is low and close to the midpoint of the two peaks\r
-    int bestValley = firstPeak;\r
-    int bestValleyScore = 0;\r
-    for (int i = firstPeak + 1; i < secondPeak; i++) {\r
-      // Encourage low valleys near the mid point between peaks\r
-      int score = (firstPeakSize - luminanceBuckets[i]) * (i - firstPeak) * (secondPeak - i);\r
-      if (score > bestValleyScore) {\r
+    // Find a valley between them that is low and closer to the white peak\r
+    int bestValley = secondPeak;\r
+    int bestValleyScore = Integer.MAX_VALUE;\r
+    for (int i = secondPeak; i > firstPeak; i--) {\r
+      int distance = secondPeak - i + 3;\r
+      int score = distance * histogram[i];\r
+      if (score < bestValleyScore) {\r
         bestValley = i;\r
         bestValleyScore = score;\r
       }\r

diff --git a/core/src/com/google/zxing/upc/UPCDecoder.java b/core/src/com/google/zxing/upc/UPCDecoder.java
index 99928f3..e2650c1 100755 (executable)
--- a/core/src/com/google/zxing/upc/UPCDecoder.java
+++ b/core/src/com/google/zxing/upc/UPCDecoder.java
@@ -16,6 +16,7 @@
 
 package com.google.zxing.upc;
 
+import com.google.zxing.BlackPointEstimationMethod;
 import com.google.zxing.common.BitArray;
 import com.google.zxing.MonochromeBitmapSource;
 
@@ -66,6 +67,7 @@ final class UPCDecoder {
     int found = -1;
     for (int x = 0; x < BITMAP_SEARCH_PATTERN.length; x++) {
       int row = height * BITMAP_SEARCH_PATTERN[x] / 100;
+      bitmap.estimateBlackPoint(BlackPointEstimationMethod.ROW_SAMPLING, row);
       bitmap.getBlackRow(row, rowData, 0, width);
 
       if (decodeRow(rowData)) {

diff --git a/javame/src/com/google/zxing/client/j2me/LCDUIImageMonochromeBitmapSource.java b/javame/src/com/google/zxing/client/j2me/LCDUIImageMonochromeBitmapSource.java
index 1645628..2b7bd10 100644 (file)
--- a/javame/src/com/google/zxing/client/j2me/LCDUIImageMonochromeBitmapSource.java
+++ b/javame/src/com/google/zxing/client/j2me/LCDUIImageMonochromeBitmapSource.java
@@ -35,6 +35,11 @@ final class LCDUIImageMonochromeBitmapSource implements MonochromeBitmapSource {
   private final int height;
   private int blackPoint;
   private BlackPointEstimationMethod lastMethod;
+  private int lastArgument;
+  
+  private static final int LUMINANCE_BITS = 5;
+  private static final int LUMINANCE_SHIFT = 8 - LUMINANCE_BITS;
+  private static final int LUMINANCE_BUCKETS = 1 << LUMINANCE_BITS;
 
   LCDUIImageMonochromeBitmapSource(final Image image) {
     width = image.getWidth();
@@ -42,6 +47,8 @@ final class LCDUIImageMonochromeBitmapSource implements MonochromeBitmapSource {
     rgbPixels = new int[width * height];
     image.getRGB(rgbPixels, 0, width, 0, 0, width, height);
     blackPoint = 0x7F;
+    lastMethod = null;
+    lastArgument = 0;
   }
 
   public boolean isBlack(int x, int y) {
@@ -71,21 +78,28 @@ final class LCDUIImageMonochromeBitmapSource implements MonochromeBitmapSource {
   }
 
   public void estimateBlackPoint(BlackPointEstimationMethod method, int argument) {
-    if (method.equals(BlackPointEstimationMethod.TWO_D_SAMPLING)) {
-      if (!BlackPointEstimationMethod.TWO_D_SAMPLING.equals(lastMethod)) {
-        int[] luminanceBuckets = new int[32];
+    if (!method.equals(lastMethod) || argument != lastArgument) {
+      int[] histogram = new int[LUMINANCE_BUCKETS];
+      if (method.equals(BlackPointEstimationMethod.TWO_D_SAMPLING)) {
         int minDimension = width < height ? width : height;
         for (int n = 0, offset = 0; n < minDimension; n++, offset += width + 1) {
-          luminanceBuckets[computeRGBLuminance(rgbPixels[offset]) >> 3]++;
+          histogram[computeRGBLuminance(rgbPixels[offset]) >> LUMINANCE_SHIFT]++;
         }
-        blackPoint = BlackPointEstimator.estimate(luminanceBuckets) << 3;
+      } else if (method.equals(BlackPointEstimationMethod.ROW_SAMPLING)) {
+        if (argument < 0 || argument >= height) {
+          throw new IllegalArgumentException("Row is not within the image: " + argument);
+        }
+        int offset = argument * width;
+        for (int x = 0; x < width; x++) {
+          histogram[computeRGBLuminance(rgbPixels[offset + x]) >> LUMINANCE_SHIFT]++;
+        }
+      } else {
+        throw new IllegalArgumentException("Unknown method: " + method);
       }
-    } else if (method.equals(BlackPointEstimationMethod.ROW_SAMPLING)) {
-      // TODO
-    } else {
-      throw new IllegalArgumentException("Unknown method: " + method);
+      blackPoint = BlackPointEstimator.estimate(histogram) << LUMINANCE_SHIFT;
+      lastMethod = method;
+      lastArgument = argument;
     }
-    lastMethod = method;
   }
 
   public BlackPointEstimationMethod getLastEstimationMethod() {

diff --git a/javase/src/com/google/zxing/client/j2se/BufferedImageMonochromeBitmapSource.java b/javase/src/com/google/zxing/client/j2se/BufferedImageMonochromeBitmapSource.java
index 479865c..8d446f8 100644 (file)
--- a/javase/src/com/google/zxing/client/j2se/BufferedImageMonochromeBitmapSource.java
+++ b/javase/src/com/google/zxing/client/j2se/BufferedImageMonochromeBitmapSource.java
@@ -35,10 +35,17 @@ public final class BufferedImageMonochromeBitmapSource implements MonochromeBitm
   private final BufferedImage image;
   private int blackPoint;
   private BlackPointEstimationMethod lastMethod;
+  private int lastArgument;
+  
+  private static final int LUMINANCE_BITS = 5;
+  private static final int LUMINANCE_SHIFT = 8 - LUMINANCE_BITS;
+  private static final int LUMINANCE_BUCKETS = 1 << LUMINANCE_BITS;
 
   public BufferedImageMonochromeBitmapSource(BufferedImage image) {
     this.image = image;
     blackPoint = 0x7F;
+    lastMethod = null;
+    lastArgument = 0;
   }
 
   public boolean isBlack(int x, int y) {
@@ -69,26 +76,34 @@ public final class BufferedImageMonochromeBitmapSource implements MonochromeBitm
   }
 
   public void estimateBlackPoint(BlackPointEstimationMethod method, int argument) {
-    if (method.equals(BlackPointEstimationMethod.TWO_D_SAMPLING)) {
-      if (!BlackPointEstimationMethod.TWO_D_SAMPLING.equals(lastMethod)) {
-        int width = image.getWidth();
-        int height = image.getHeight();
-        int[] luminanceBuckets = new int[32];
+    if (!method.equals(lastMethod) || argument != lastArgument) {
+      int width = image.getWidth();
+      int height = image.getHeight();
+      int[] histogram = new int[LUMINANCE_BUCKETS];
+      if (method.equals(BlackPointEstimationMethod.TWO_D_SAMPLING)) {
         int minDimension = width < height ? width : height;
         int startI = height == minDimension ? 0 : (height - width) >> 1;
         int startJ = width == minDimension ? 0 : (width - height) >> 1;
         for (int n = 0; n < minDimension; n++) {
           int pixel = image.getRGB(startJ + n, startI + n);
-          luminanceBuckets[computeRGBLuminance(pixel) >> 3]++;
+          histogram[computeRGBLuminance(pixel) >> LUMINANCE_SHIFT]++;
         }
-        blackPoint = BlackPointEstimator.estimate(luminanceBuckets) << 3;
+      } else if (method.equals(BlackPointEstimationMethod.ROW_SAMPLING)) {
+        if (argument < 0 || argument >= height) {
+          throw new IllegalArgumentException("Row is not within the image: " + argument);
+        }
+        int[] rgbArray = new int[width];
+        image.getRGB(0, argument, width, 1, rgbArray, 0, width);
+        for (int x = 0; x < width; x++) {
+          histogram[computeRGBLuminance(rgbArray[x]) >> LUMINANCE_SHIFT]++;
+        }
+      } else {
+        throw new IllegalArgumentException("Unknown method: " + method);
       }
-    } else if (method.equals(BlackPointEstimationMethod.ROW_SAMPLING)) {
-      // TODO
-    } else {
-      throw new IllegalArgumentException("Unknown method: " + method);
+      blackPoint = BlackPointEstimator.estimate(histogram) << LUMINANCE_SHIFT;
+      lastMethod = method;
+      lastArgument = argument;
     }
-    lastMethod = method;
   }
 
   public BlackPointEstimationMethod getLastEstimationMethod() {

diff --git a/javase/src/com/google/zxing/client/j2se/CommandLineRunner.java b/javase/src/com/google/zxing/client/j2se/CommandLineRunner.java
index 2baf6f0..8b4bbee 100644 (file)
--- a/javase/src/com/google/zxing/client/j2se/CommandLineRunner.java
+++ b/javase/src/com/google/zxing/client/j2se/CommandLineRunner.java
@@ -40,9 +40,11 @@ public final class CommandLineRunner {
     File inputFile = new File(args[0]);
     if (inputFile.exists()) {
       if (inputFile.isDirectory()) {
+        int successful = 0;
         for (File input : inputFile.listFiles()) {
-          decode(input.toURI());
+          if (decode(input.toURI())) successful++;
         }
+        System.out.println("Decoded " + successful + " files successfully");
       } else {
         decode(inputFile.toURI());
       }
@@ -51,17 +53,19 @@ public final class CommandLineRunner {
     }
   }
 
-  private static void decode(URI uri) throws IOException {
+  private static boolean decode(URI uri) throws IOException {
     BufferedImage image = ImageIO.read(uri.toURL());
     if (image == null) {
       System.err.println(uri.toString() + ": Could not load image");
-      return;
+      return false;
     }
     try {
       String result = new MultiFormatReader().decode(new BufferedImageMonochromeBitmapSource(image)).getText();
       System.out.println(uri.toString() + ": " + result);
+      return true;
     } catch (ReaderException e) {
       System.out.println(uri.toString() + ": No barcode found");
+      return false;
     }
   }