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 /**\r
  20  * <p>Encapsulates logic that estimates the optimal "black point", the luminance value\r
  21  * which is the best line between "white" and "black" in a grayscale image.</p>\r
  22  *\r
  23  * <p>For an interesting discussion of this issue, see\r
  24  * <a href="http://webdiis.unizar.es/~neira/12082/thresholding.pdf">http://webdiis.unizar.es/~neira/12082/thresholding.pdf</a>.\r
  25  * </p>\r
  26  *\r
  27  * @author srowen@google.com (Sean Owen)\r
  28  * @author dswitkin@google.com (Daniel Switkin)\r
  29  */\r
  30 public final class BlackPointEstimator {\r
  31 \r
  32   private BlackPointEstimator() {\r
  33   }\r
  34 \r
  35   /**\r
  36    * <p>Given an array of <em>counts</em> of luminance values (i.e. a histogram), this method\r
  37    * decides which bucket of values corresponds to the black point -- which bucket contains the\r
  38    * count of the brightest luminance values that should be considered "black".</p>\r
  39    *\r
  40    * @param histogram an array of <em>counts</em> of luminance values\r
  41    * @param biasTowardsWhite values higher than 1.0 suggest that a higher black point is desirable (e.g.\r
  42    * more values are considered black); less than 1.0 suggests that lower is desirable. Must be greater\r
  43    * than 0.0; 1.0 is a good "default"\r
  44    * @return index within argument of bucket corresponding to brightest values which should be\r
  45    *         considered "black"\r
  46    */\r
  47   public static int estimate(int[] histogram, float biasTowardsWhite) {\r
  48 \r
  49     if (Float.isNaN(biasTowardsWhite) || biasTowardsWhite <= 0.0f) {\r
  50       throw new IllegalArgumentException("Illegal biasTowardsWhite: " + biasTowardsWhite);\r
  51     }\r
  52 \r
  53     int numBuckets = histogram.length;\r
  54 \r
  55     // Find tallest peak in histogram\r
  56     int firstPeak = 0;\r
  57     int firstPeakSize = 0;\r
  58     for (int i = 0; i < numBuckets; i++) {\r
  59       if (histogram[i] > firstPeakSize) {\r
  60         firstPeak = i;\r
  61         firstPeakSize = histogram[i];\r
  62       }\r
  63     }\r
  64 \r
  65     // Find second-tallest peak -- well, another peak that is tall and not\r
  66     // so close to the first one\r
  67     int secondPeak = 0;\r
  68     int secondPeakScore = 0;\r
  69     for (int i = 0; i < numBuckets; i++) {\r
  70       int distanceToBiggest = i - firstPeak;\r
  71       // Encourage more distant second peaks by multiplying by square of distance\r
  72       int score = histogram[i] * distanceToBiggest * distanceToBiggest;\r
  73       if (score > secondPeakScore) {\r
  74         secondPeak = i;\r
  75         secondPeakScore = score;\r
  76       }\r
  77     }\r
  78 \r
  79     // Put firstPeak first\r
  80     if (firstPeak > secondPeak) {\r
  81       int temp = firstPeak;\r
  82       firstPeak = secondPeak;\r
  83       secondPeak = temp;\r
  84     }\r
  85 \r
  86     // Find a valley between them that is low and closer to the white peak\r
  87     int bestValley = secondPeak - 1;\r
  88     int bestValleyScore = -1;\r
  89     for (int i = secondPeak - 1; i > firstPeak; i--) {\r
  90       int fromFirst = (int) (biasTowardsWhite * (i - firstPeak));\r
  91       // Favor a "valley" that is not too close to either peak -- especially not the black peak --\r
  92       // and that has a low value of course\r
  93       int score = fromFirst * fromFirst * (secondPeak - i) * (256 - histogram[i]);\r
  94       if (score > bestValleyScore) {\r
  95         bestValley = i;\r
  96         bestValleyScore = score;\r
  97       }\r
  98     }\r
  99 \r
 100     return bestValley;\r
 101   }\r
 102 \r
 103 }