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">http://webdiis.unizar.es/~neira/12082/thresholding.pdf</a>.\r
  29  * </p>\r
  30  *\r
  31  * NOTE: This class is not threadsafe.\r
  32  *\r
  33  * @author Sean Owen\r
  34  * @author dswitkin@google.com (Daniel Switkin)\r
  35  */\r
  36 public final class BlackPointEstimator {\r
  37 \r
  38   private static final int LUMINANCE_BITS = 5;\r
  39   private static final int LUMINANCE_SHIFT = 8 - LUMINANCE_BITS;\r
  40   private static final int LUMINANCE_BUCKETS = 1 << LUMINANCE_BITS;\r
  41 \r
  42   private static int[] luminances = null;\r
  43   private static int[] histogram = null;\r
  44 \r
  45   private BlackPointEstimator() {\r
  46   }\r
  47 \r
  48   private static void initArrays(int luminanceSize) {\r
  49     if (luminances == null || luminances.length < luminanceSize) {\r
  50       luminances = new int[luminanceSize];\r
  51     }\r
  52     if (histogram == null) {\r
  53       histogram = new int[LUMINANCE_BUCKETS];\r
  54     } else {\r
  55       for (int x = 0; x < LUMINANCE_BUCKETS; x++) {\r
  56         histogram[x] = 0;\r
  57       }\r
  58     }\r
  59   }\r
  60 \r
  61   /**\r
  62    * Calculates the black point for the supplied bitmap.\r
  63    *\r
  64    * @param source The bitmap to analyze.\r
  65    * @param method The pixel sampling technique to use.\r
  66    * @param argument The row index in the case of ROW_SAMPLING, otherwise ignored.\r
  67    * @return The black point as an integer 0-255.\r
  68    * @throws ReaderException An exception thrown if the blackpoint cannot be determined.\r
  69    */\r
  70   public static int estimate(MonochromeBitmapSource source, BlackPointEstimationMethod method,\r
  71       int argument) throws ReaderException {\r
  72     int width = source.getWidth();\r
  73     int height = source.getHeight();\r
  74     initArrays(width);\r
  75 \r
  76     if (method.equals(BlackPointEstimationMethod.TWO_D_SAMPLING)) {\r
  77       int minDimension = width < height ? width : height;\r
  78       int startX = (width - minDimension) >> 1;\r
  79       int startY = (height - minDimension) >> 1;\r
  80       for (int n = 0; n < minDimension; n++) {\r
  81         int luminance = source.getLuminance(startX + n, startY + n);\r
  82         histogram[luminance >> LUMINANCE_SHIFT]++;\r
  83       }\r
  84     } else if (method.equals(BlackPointEstimationMethod.ROW_SAMPLING)) {\r
  85       if (argument < 0 || argument >= height) {\r
  86         throw new IllegalArgumentException("Row is not within the image: " + argument);\r
  87       }\r
  88 \r
  89       luminances = source.getLuminanceRow(argument, luminances);\r
  90       for (int x = 0; x < width; x++) {\r
  91         histogram[luminances[x] >> LUMINANCE_SHIFT]++;\r
  92       }\r
  93     } else {\r
  94       throw new IllegalArgumentException("Unknown method");\r
  95     }\r
  96     return findBestValley(histogram) << LUMINANCE_SHIFT;\r
  97   }\r
  98 \r
  99   /**\r
 100    * <p>Given an array of <em>counts</em> of luminance values (i.e. a histogram), this method\r
 101    * decides which bucket of values corresponds to the black point -- which bucket contains the\r
 102    * count of the brightest luminance values that should be considered "black".</p>\r
 103    *\r
 104    * @param buckets an array of <em>counts</em> of luminance values\r
 105    * @return index within argument of bucket corresponding to brightest values which should be\r
 106    *         considered "black"\r
 107    * @throws ReaderException if "black" and "white" appear to be very close in luminance\r
 108    */\r
 109   public static int findBestValley(int[] buckets) throws ReaderException {\r
 110     int numBuckets = buckets.length;\r
 111     int maxBucketCount = 0;\r
 112     // Find tallest peak in histogram\r
 113     int firstPeak = 0;\r
 114     int firstPeakSize = 0;\r
 115     for (int i = 0; i < numBuckets; i++) {\r
 116       if (buckets[i] > firstPeakSize) {\r
 117         firstPeak = i;\r
 118         firstPeakSize = buckets[i];\r
 119       }\r
 120       if (buckets[i] > maxBucketCount) {\r
 121         maxBucketCount = buckets[i];\r
 122       }\r
 123     }\r
 124 \r
 125     // Find second-tallest peak -- well, another peak that is tall and not\r
 126     // so close to the first one\r
 127     int secondPeak = 0;\r
 128     int secondPeakScore = 0;\r
 129     for (int i = 0; i < numBuckets; i++) {\r
 130       int distanceToBiggest = i - firstPeak;\r
 131       // Encourage more distant second peaks by multiplying by square of distance\r
 132       int score = buckets[i] * distanceToBiggest * distanceToBiggest;\r
 133       if (score > secondPeakScore) {\r
 134         secondPeak = i;\r
 135         secondPeakScore = score;\r
 136       }\r
 137     }\r
 138 \r
 139     // Put firstPeak first\r
 140     if (firstPeak > secondPeak) {\r
 141       int temp = firstPeak;\r
 142       firstPeak = secondPeak;\r
 143       secondPeak = temp;\r
 144     }\r
 145 \r
 146     // Kind of arbitrary; if the two peaks are very close, then we figure there is so little\r
 147     // dynamic range in the image, that discriminating black and white is too error-prone.\r
 148     // Decoding the image/line is either pointless, or may in some cases lead to a false positive\r
 149     // for 1D formats, which are relatively lenient.\r
 150     // We arbitrarily say "close" is "<= 1/16 of the total histogram buckets apart"\r
 151     if (secondPeak - firstPeak <= numBuckets >> 4) {\r
 152       throw ReaderException.getInstance();\r
 153     }\r
 154 \r
 155     // Find a valley between them that is low and closer to the white peak\r
 156     int bestValley = secondPeak - 1;\r
 157     int bestValleyScore = -1;\r
 158     for (int i = secondPeak - 1; i > firstPeak; i--) {\r
 159       int fromFirst = i - firstPeak;\r
 160       // Favor a "valley" that is not too close to either peak -- especially not the black peak --\r
 161       // and that has a low value of course\r
 162       int score = fromFirst * fromFirst * (secondPeak - i) * (maxBucketCount - buckets[i]);\r
 163       if (score > bestValleyScore) {\r
 164         bestValley = i;\r
 165         bestValleyScore = score;\r
 166       }\r
 167     }\r
 168 \r
 169     return bestValley;\r
 170   }\r
 171 \r
 172 }