core/src/com/google/zxing/common/BlackPointEstimator.java

   1 /*\r
   2  * Copyright 2007 ZXing authors\r
   3  *\r
   4  * Licensed under the Apache License, Version 2.0 (the "License");\r
   5  * you may not use this file except in compliance with the License.\r
   6  * You may obtain a copy of the License at\r
   7  *\r
   8  *      http://www.apache.org/licenses/LICENSE-2.0\r
   9  *\r
  10  * Unless required by applicable law or agreed to in writing, software\r
  11  * distributed under the License is distributed on an "AS IS" BASIS,\r
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
  13  * See the License for the specific language governing permissions and\r
  14  * limitations under the License.\r
  15  */\r
  16 \r
  17 package com.google.zxing.common;\r
  18 \r
  19 import com.google.zxing.BlackPointEstimationMethod;\r
  20 import com.google.zxing.MonochromeBitmapSource;\r
  21 import com.google.zxing.ReaderException;\r
  22 \r
  23 /**\r
  24  * <p>Encapsulates logic that estimates the optimal "black point", the luminance value\r
  25  * which is the best line between "white" and "black" in a grayscale image.</p>\r
  26  *\r
  27  * <p>For an interesting discussion of this issue, see\r
  28  * <a href="http://webdiis.unizar.es/~neira/12082/thresholding.pdf">this paper</a>.</p>\r
  29  *\r
  30  * NOTE: This class is not thread-safe.\r
  31  *\r
  32  * @author Sean Owen\r
  33  * @author dswitkin@google.com (Daniel Switkin)\r
  34  */\r
  35 public final class BlackPointEstimator {\r
  36 \r
  37   private static final int LUMINANCE_BITS = 5;\r
  38   private static final int LUMINANCE_SHIFT = 8 - LUMINANCE_BITS;\r
  39   private static final int LUMINANCE_BUCKETS = 1 << LUMINANCE_BITS;\r
  40 \r
  41   private static int[] luminances = null;\r
  42   private static int[] histogram = null;\r
  43 \r
  44   private BlackPointEstimator() {\r
  45   }\r
  46 \r
  47   private static void initArrays(int luminanceSize) {\r
  48     if (luminances == null || luminances.length < luminanceSize) {\r
  49       luminances = new int[luminanceSize];\r
  50     }\r
  51     if (histogram == null) {\r
  52       histogram = new int[LUMINANCE_BUCKETS];\r
  53     } else {\r
  54       for (int x = 0; x < LUMINANCE_BUCKETS; x++) {\r
  55         histogram[x] = 0;\r
  56       }\r
  57     }\r
  58   }\r
  59 \r
  60   /**\r
  61    * Calculates the black point for the supplied bitmap.\r
  62    *\r
  63    * @param source The bitmap to analyze.\r
  64    * @param method The pixel sampling technique to use.\r
  65    * @param argument The row index in the case of ROW_SAMPLING, otherwise ignored.\r
  66    * @return The black point as an integer 0-255.\r
  67    * @throws ReaderException An exception thrown if the blackpoint cannot be determined.\r
  68    */\r
  69   public static int estimate(MonochromeBitmapSource source, BlackPointEstimationMethod method,\r
  70       int argument) throws ReaderException {\r
  71     int width = source.getWidth();\r
  72     int height = source.getHeight();\r
  73     initArrays(width);\r
  74 \r
  75     if (method.equals(BlackPointEstimationMethod.TWO_D_SAMPLING)) {\r
  76       // We used to sample a diagonal in the 2D case, but it missed a lot of pixels, and it required\r
  77       // n calls to getLuminance(). We had a net improvement of 63 blackbox tests decoded by\r
  78       // sampling several rows from the middle of the image, using getLuminanceRow(). We read more\r
  79       // pixels total, but with fewer function calls, and more continguous memory.\r
  80       for (int y = 1; y < 5; y++) {\r
  81         int row = height * y / 5;\r
  82         int[] localLuminances = source.getLuminanceRow(row, luminances);\r
  83         int right = width * 4 / 5;\r
  84         for (int x = width / 5; x < right; x++) {\r
  85           histogram[localLuminances[x] >> LUMINANCE_SHIFT]++;\r
  86         }\r
  87       }\r
  88     } else if (method.equals(BlackPointEstimationMethod.ROW_SAMPLING)) {\r
  89       if (argument < 0 || argument >= height) {\r
  90         throw new IllegalArgumentException("Row is not within the image: " + argument);\r
  91       }\r
  92 \r
  93       int[] localLuminances = source.getLuminanceRow(argument, luminances);\r
  94       for (int x = 0; x < width; x++) {\r
  95         histogram[localLuminances[x] >> LUMINANCE_SHIFT]++;\r
  96       }\r
  97     } else {\r
  98       throw new IllegalArgumentException("Unknown method");\r
  99     }\r
 100     return findBestValley(histogram) << LUMINANCE_SHIFT;\r
 101   }\r
 102 \r
 103   /**\r
 104    * <p>Given an array of <em>counts</em> of luminance values (i.e. a histogram), this method\r
 105    * decides which bucket of values corresponds to the black point -- which bucket contains the\r
 106    * count of the brightest luminance values that should be considered "black".</p>\r
 107    *\r
 108    * @param buckets an array of <em>counts</em> of luminance values\r
 109    * @return index within argument of bucket corresponding to brightest values which should be\r
 110    *         considered "black"\r
 111    * @throws ReaderException if "black" and "white" appear to be very close in luminance\r
 112    */\r
 113   public static int findBestValley(int[] buckets) throws ReaderException {\r
 114     int numBuckets = buckets.length;\r
 115     int maxBucketCount = 0;\r
 116     // Find tallest peak in histogram\r
 117     int firstPeak = 0;\r
 118     int firstPeakSize = 0;\r
 119     for (int i = 0; i < numBuckets; i++) {\r
 120       if (buckets[i] > firstPeakSize) {\r
 121         firstPeak = i;\r
 122         firstPeakSize = buckets[i];\r
 123       }\r
 124       if (buckets[i] > maxBucketCount) {\r
 125         maxBucketCount = buckets[i];\r
 126       }\r
 127     }\r
 128 \r
 129     // Find second-tallest peak -- well, another peak that is tall and not\r
 130     // so close to the first one\r
 131     int secondPeak = 0;\r
 132     int secondPeakScore = 0;\r
 133     for (int i = 0; i < numBuckets; i++) {\r
 134       int distanceToBiggest = i - firstPeak;\r
 135       // Encourage more distant second peaks by multiplying by square of distance\r
 136       int score = buckets[i] * distanceToBiggest * distanceToBiggest;\r
 137       if (score > secondPeakScore) {\r
 138         secondPeak = i;\r
 139         secondPeakScore = score;\r
 140       }\r
 141     }\r
 142 \r
 143     // Put firstPeak first\r
 144     if (firstPeak > secondPeak) {\r
 145       int temp = firstPeak;\r
 146       firstPeak = secondPeak;\r
 147       secondPeak = temp;\r
 148     }\r
 149 \r
 150     // Kind of arbitrary; if the two peaks are very close, then we figure there is so little\r
 151     // dynamic range in the image, that discriminating black and white is too error-prone.\r
 152     // Decoding the image/line is either pointless, or may in some cases lead to a false positive\r
 153     // for 1D formats, which are relatively lenient.\r
 154     // We arbitrarily say "close" is "<= 1/16 of the total histogram buckets apart"\r
 155     if (secondPeak - firstPeak <= numBuckets >> 4) {\r
 156       throw ReaderException.getInstance();\r
 157     }\r
 158 \r
 159     // Find a valley between them that is low and closer to the white peak\r
 160     int bestValley = secondPeak - 1;\r
 161     int bestValleyScore = -1;\r
 162     for (int i = secondPeak - 1; i > firstPeak; i--) {\r
 163       int fromFirst = i - firstPeak;\r
 164       // Favor a "valley" that is not too close to either peak -- especially not the black peak --\r
 165       // and that has a low value of course\r
 166       int score = fromFirst * fromFirst * (secondPeak - i) * (maxBucketCount - buckets[i]);\r
 167       if (score > bestValleyScore) {\r
 168         bestValley = i;\r
 169         bestValleyScore = score;\r
 170       }\r
 171     }\r
 172 \r
 173     return bestValley;\r
 174   }\r
 175 \r
 176 }