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