From 8200a7ae095206a8f8919b54a434930a676d73b4 Mon Sep 17 00:00:00 2001
From: dswitkin
Date: Mon, 19 Nov 2007 17:26:22 +0000
Subject: [PATCH] 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
---
.../zxing/common/BlackPointEstimator.java | 26 ++++++-------
core/src/com/google/zxing/upc/UPCDecoder.java | 2 +
.../LCDUIImageMonochromeBitmapSource.java | 34 +++++++++++-----
.../BufferedImageMonochromeBitmapSource.java | 39 +++++++++++++------
.../zxing/client/j2se/CommandLineRunner.java | 10 +++--
5 files changed, 73 insertions(+), 38 deletions(-)
diff --git a/core/src/com/google/zxing/common/BlackPointEstimator.java b/core/src/com/google/zxing/common/BlackPointEstimator.java
index 2203fd39..32c80883 100644
--- 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
* count of the brightest luminance values that should be considered "black".
*
- * @param luminanceBuckets an array of counts of luminance values
+ * @param histogram an array of counts of luminance values
* @return index within argument of bucket corresponding to brightest values which should be
* considered "black"
*/
- public static int estimate(int[] luminanceBuckets) {
+ public static int estimate(int[] histogram) {
- int numBuckets = luminanceBuckets.length;
+ int numBuckets = histogram.length;
// Find tallest peak in histogram
int firstPeak = 0;
int firstPeakSize = 0;
for (int i = 0; i < numBuckets; i++) {
- if (luminanceBuckets[i] > firstPeakSize) {
+ if (histogram[i] > firstPeakSize) {
firstPeak = i;
- firstPeakSize = luminanceBuckets[i];
+ firstPeakSize = histogram[i];
}
}
@@ -61,7 +61,7 @@ public final class BlackPointEstimator {
for (int i = 0; i < numBuckets; i++) {
int distanceToBiggest = i - firstPeak;
// Encourage more distant second peaks by multiplying by square of distance
- int score = luminanceBuckets[i] * distanceToBiggest * distanceToBiggest;
+ int score = histogram[i] * distanceToBiggest * distanceToBiggest;
if (score > secondPeakScore) {
secondPeak = i;
secondPeakScore = score;
@@ -75,13 +75,13 @@ public final class BlackPointEstimator {
secondPeak = temp;
}
- // Find a valley between them that is low and close to the midpoint of the two peaks
- int bestValley = firstPeak;
- int bestValleyScore = 0;
- for (int i = firstPeak + 1; i < secondPeak; i++) {
- // Encourage low valleys near the mid point between peaks
- int score = (firstPeakSize - luminanceBuckets[i]) * (i - firstPeak) * (secondPeak - i);
- if (score > bestValleyScore) {
+ // Find a valley between them that is low and closer to the white peak
+ int bestValley = secondPeak;
+ int bestValleyScore = Integer.MAX_VALUE;
+ for (int i = secondPeak; i > firstPeak; i--) {
+ int distance = secondPeak - i + 3;
+ int score = distance * histogram[i];
+ if (score < bestValleyScore) {
bestValley = i;
bestValleyScore = score;
}
diff --git a/core/src/com/google/zxing/upc/UPCDecoder.java b/core/src/com/google/zxing/upc/UPCDecoder.java
index 99928f32..e2650c1d 100755
--- 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 16456287..2b7bd10a 100644
--- 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 479865c9..8d446f81 100644
--- 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 2baf6f01..8b4bbee4 100644
--- 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;
}
}
--
2.20.1