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

   1 /*\r
   2  * Copyright 2007 Google Inc.\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.ReaderException;\r
  20 \r
  21 /**\r
  22  * <p>Encapsulates logic that estimates the optimal "black point", the luminance value\r
  23  * which is the best line between "white" and "black" in a grayscale image.</p>\r
  24  *\r
  25  * <p>For an interesting discussion of this issue, see\r
  26  * <a href="http://webdiis.unizar.es/~neira/12082/thresholding.pdf">http://webdiis.unizar.es/~neira/12082/thresholding.pdf</a>.\r
  27  * </p>\r
  28  *\r
  29  * @author srowen@google.com (Sean Owen)\r
  30  * @author dswitkin@google.com (Daniel Switkin)\r
  31  */\r
  32 public final class BlackPointEstimator {\r
  33 \r
  34   private BlackPointEstimator() {\r
  35   }\r
  36 \r
  37   /**\r
  38    * <p>Given an array of <em>counts</em> of luminance values (i.e. a histogram), this method\r
  39    * decides which bucket of values corresponds to the black point -- which bucket contains the\r
  40    * count of the brightest luminance values that should be considered "black".</p>\r
  41    *\r
  42    * @param histogram an array of <em>counts</em> of luminance values\r
  43    * @return index within argument of bucket corresponding to brightest values which should be\r
  44    *         considered "black"\r
  45    * @throws ReaderException if "black" and "white" appear to be very close in luminance in the image\r
  46    */\r
  47   public static int estimate(int[] histogram) throws ReaderException{\r
  48 \r
  49     int numBuckets = histogram.length;\r
  50 \r
  51     // Find tallest peak in histogram\r
  52     int firstPeak = 0;\r
  53     int firstPeakSize = 0;\r
  54     for (int i = 0; i < numBuckets; i++) {\r
  55       if (histogram[i] > firstPeakSize) {\r
  56         firstPeak = i;\r
  57         firstPeakSize = histogram[i];\r
  58       }\r
  59     }\r
  60 \r
  61     // Find second-tallest peak -- well, another peak that is tall and not\r
  62     // so close to the first one\r
  63     int secondPeak = 0;\r
  64     int secondPeakScore = 0;\r
  65     for (int i = 0; i < numBuckets; i++) {\r
  66       int distanceToBiggest = i - firstPeak;\r
  67       // Encourage more distant second peaks by multiplying by square of distance\r
  68       int score = histogram[i] * distanceToBiggest * distanceToBiggest;\r
  69       if (score > secondPeakScore) {\r
  70         secondPeak = i;\r
  71         secondPeakScore = score;\r
  72       }\r
  73     }\r
  74 \r
  75     // Put firstPeak first\r
  76     if (firstPeak > secondPeak) {\r
  77       int temp = firstPeak;\r
  78       firstPeak = secondPeak;\r
  79       secondPeak = temp;\r
  80     }\r
  81 \r
  82     // Kind of aribtrary; if the two peaks are very close, then we figure there is so little\r
  83     // dynamic range in the image, that discriminating black and white is too error-prone.\r
  84     // Decoding the image/line is either pointless, or may in some cases lead to a false positive\r
  85     // for 1D formats, which are relatively lenient.\r
  86     // We arbitrarily say "close" is "<= 1/16 of the total histogram buckets apart"\r
  87     if (secondPeak - firstPeak <= histogram.length >> 4) {\r
  88       throw new ReaderException("Too little dynamic range in luminance");\r
  89     }\r
  90 \r
  91     // Find a valley between them that is low and closer to the white peak\r
  92     int bestValley = secondPeak - 1;\r
  93     int bestValleyScore = -1;\r
  94     for (int i = secondPeak - 1; i > firstPeak; i--) {\r
  95       int fromFirst = i - firstPeak;\r
  96       // Favor a "valley" that is not too close to either peak -- especially not the black peak --\r
  97       // and that has a low value of course\r
  98       int score = fromFirst * fromFirst * (secondPeak - i) * (256 - histogram[i]);\r
  99       if (score > bestValleyScore) {\r
 100         bestValley = i;\r
 101         bestValleyScore = score;\r
 102       }\r
 103     }\r
 104 \r
 105     return bestValley;\r
 106   }\r
 107 \r
 108 }