/*\r
- * Copyright 2007 Google Inc.\r
+ * Copyright 2007 ZXing authors\r
*\r
* Licensed under the Apache License, Version 2.0 (the "License");\r
* you may not use this file except in compliance with the License.\r
\r
package com.google.zxing.common;\r
\r
+import com.google.zxing.BlackPointEstimationMethod;\r
+import com.google.zxing.MonochromeBitmapSource;\r
+import com.google.zxing.ReaderException;\r
+\r
/**\r
* <p>Encapsulates logic that estimates the optimal "black point", the luminance value\r
* which is the best line between "white" and "black" in a grayscale image.</p>\r
*\r
* <p>For an interesting discussion of this issue, see\r
- * <a href="http://webdiis.unizar.es/~neira/12082/thresholding.pdf">http://webdiis.unizar.es/~neira/12082/thresholding.pdf</a>.\r
- * </p>\r
+ * <a href="http://webdiis.unizar.es/~neira/12082/thresholding.pdf">this paper</a>.</p>\r
+ *\r
+ * NOTE: This class is not threadsafe.\r
*\r
- * @author srowen@google.com (Sean Owen)\r
+ * @author Sean Owen\r
* @author dswitkin@google.com (Daniel Switkin)\r
*/\r
public final class BlackPointEstimator {\r
\r
+ private static final int LUMINANCE_BITS = 5;\r
+ private static final int LUMINANCE_SHIFT = 8 - LUMINANCE_BITS;\r
+ private static final int LUMINANCE_BUCKETS = 1 << LUMINANCE_BITS;\r
+\r
+ private static int[] luminances = null;\r
+ private static int[] histogram = null;\r
+\r
private BlackPointEstimator() {\r
}\r
\r
+ private static void initArrays(int luminanceSize) {\r
+ if (luminances == null || luminances.length < luminanceSize) {\r
+ luminances = new int[luminanceSize];\r
+ }\r
+ if (histogram == null) {\r
+ histogram = new int[LUMINANCE_BUCKETS];\r
+ } else {\r
+ for (int x = 0; x < LUMINANCE_BUCKETS; x++) {\r
+ histogram[x] = 0;\r
+ }\r
+ }\r
+ }\r
+\r
+ /**\r
+ * Calculates the black point for the supplied bitmap.\r
+ *\r
+ * @param source The bitmap to analyze.\r
+ * @param method The pixel sampling technique to use.\r
+ * @param argument The row index in the case of ROW_SAMPLING, otherwise ignored.\r
+ * @return The black point as an integer 0-255.\r
+ * @throws ReaderException An exception thrown if the blackpoint cannot be determined.\r
+ */\r
+ public static int estimate(MonochromeBitmapSource source, BlackPointEstimationMethod method,\r
+ int argument) throws ReaderException {\r
+ int width = source.getWidth();\r
+ int height = source.getHeight();\r
+ initArrays(width);\r
+\r
+ if (method.equals(BlackPointEstimationMethod.TWO_D_SAMPLING)) {\r
+ // We used to sample a diagonal in the 2D case, but it missed a lot of pixels, and it required\r
+ // n calls to getLuminance(). We had a net improvement of 63 blackbox tests decoded by\r
+ // sampling several rows from the middle of the image, using getLuminanceRow(). We read more\r
+ // pixels total, but with fewer function calls, and more continguous memory.\r
+ for (int y = 1; y < 5; y++) {\r
+ int row = height * y / 5;\r
+ int[] localLuminances = source.getLuminanceRow(row, luminances);\r
+ int right = width * 4 / 5;\r
+ for (int x = width / 5; x < right; x++) {\r
+ histogram[localLuminances[x] >> LUMINANCE_SHIFT]++;\r
+ }\r
+ }\r
+ } else if (method.equals(BlackPointEstimationMethod.ROW_SAMPLING)) {\r
+ if (argument < 0 || argument >= height) {\r
+ throw new IllegalArgumentException("Row is not within the image: " + argument);\r
+ }\r
+\r
+ int[] localLuminances = source.getLuminanceRow(argument, luminances);\r
+ for (int x = 0; x < width; x++) {\r
+ histogram[localLuminances[x] >> LUMINANCE_SHIFT]++;\r
+ }\r
+ } else {\r
+ throw new IllegalArgumentException("Unknown method");\r
+ }\r
+ return findBestValley(histogram) << LUMINANCE_SHIFT;\r
+ }\r
+\r
/**\r
* <p>Given an array of <em>counts</em> of luminance values (i.e. a histogram), this method\r
* 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 histogram an array of <em>counts</em> of luminance values\r
- * @param biasTowardsWhite values higher than 1.0 suggest that a higher black point is desirable (e.g.\r
- * more values are considered black); less than 1.0 suggests that lower is desirable. Must be greater\r
- * than 0.0; 1.0 is a good "default"\r
+ * @param buckets 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
+ * considered "black"\r
+ * @throws ReaderException if "black" and "white" appear to be very close in luminance\r
*/\r
- public static int estimate(int[] histogram, float biasTowardsWhite) {\r
-\r
- if (Float.isNaN(biasTowardsWhite) || biasTowardsWhite <= 0.0f) {\r
- throw new IllegalArgumentException("Illegal biasTowardsWhite: " + biasTowardsWhite);\r
- }\r
-\r
- int numBuckets = histogram.length;\r
-\r
+ public static int findBestValley(int[] buckets) throws ReaderException {\r
+ int numBuckets = buckets.length;\r
+ int maxBucketCount = 0;\r
// Find tallest peak in histogram\r
int firstPeak = 0;\r
int firstPeakSize = 0;\r
for (int i = 0; i < numBuckets; i++) {\r
- if (histogram[i] > firstPeakSize) {\r
+ if (buckets[i] > firstPeakSize) {\r
firstPeak = i;\r
- firstPeakSize = histogram[i];\r
+ firstPeakSize = buckets[i];\r
+ }\r
+ if (buckets[i] > maxBucketCount) {\r
+ maxBucketCount = buckets[i];\r
}\r
}\r
\r
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 = histogram[i] * distanceToBiggest * distanceToBiggest;\r
+ int score = buckets[i] * distanceToBiggest * distanceToBiggest;\r
if (score > secondPeakScore) {\r
secondPeak = i;\r
secondPeakScore = score;\r
secondPeak = temp;\r
}\r
\r
+ // Kind of arbitrary; if the two peaks are very close, then we figure there is so little\r
+ // dynamic range in the image, that discriminating black and white is too error-prone.\r
+ // Decoding the image/line is either pointless, or may in some cases lead to a false positive\r
+ // for 1D formats, which are relatively lenient.\r
+ // We arbitrarily say "close" is "<= 1/16 of the total histogram buckets apart"\r
+ if (secondPeak - firstPeak <= numBuckets >> 4) {\r
+ throw ReaderException.getInstance();\r
+ }\r
+\r
// Find a valley between them that is low and closer to the white peak\r
int bestValley = secondPeak - 1;\r
int bestValleyScore = -1;\r
for (int i = secondPeak - 1; i > firstPeak; i--) {\r
- int fromFirst = (int) (biasTowardsWhite * (i - firstPeak));\r
+ int fromFirst = i - firstPeak;\r
// Favor a "valley" that is not too close to either peak -- especially not the black peak --\r
// and that has a low value of course\r
- int score = fromFirst * fromFirst * (secondPeak - i) * (256 - histogram[i]);\r
+ int score = fromFirst * fromFirst * (secondPeak - i) * (maxBucketCount - buckets[i]);\r
if (score > bestValleyScore) {\r
bestValley = i;\r
bestValleyScore = score;\r
projects / zxing.git / blobdiff