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>TODO: Include reference to paper with similar ideas</p>\r
  24  *\r
  25  * @author srowen@google.com (Sean Owen)\r
  26  */\r
  27 public final class BlackPointEstimator {\r
  28 \r
  29   private BlackPointEstimator() {\r
  30   }\r
  31 \r
  32   /**\r
  33    * <p>Given an array of <em>counts</em> of luminance values (i.e. a histogram), this method\r
  34    * decides which bucket of values corresponds to the black point -- which bucket contains the\r
  35    * count of the brightest luminance values that should be considered "black".</p>\r
  36    *\r
  37    * @param luminanceBuckets an array of <em>counts</em> of luminance values\r
  38    * @return index within argument of bucket corresponding to brightest values which should be\r
  39    *  considered "black"\r
  40    */\r
  41   public static int estimate(int[] luminanceBuckets) {\r
  42 \r
  43     int numBuckets = luminanceBuckets.length;\r
  44 \r
  45     // Find tallest peak in histogram\r
  46     int firstPeak = 0;\r
  47     int firstPeakSize = 0;\r
  48     for (int i = 0; i < numBuckets; i++) {\r
  49       if (luminanceBuckets[i] > firstPeakSize) {\r
  50         firstPeak = i;\r
  51         firstPeakSize = luminanceBuckets[i];\r
  52       }\r
  53     }\r
  54 \r
  55     // Find second-tallest peak -- well, another peak that is tall and not\r
  56     // so close to the first one\r
  57     int secondPeak = 0;\r
  58     int secondPeakScore = 0;\r
  59     for (int i = 0; i < numBuckets; i++) {\r
  60       int distanceToBiggest = i - firstPeak;\r
  61       // Encourage more distant second peaks by multiplying by square of distance\r
  62       int score = luminanceBuckets[i] * distanceToBiggest * distanceToBiggest;\r
  63       if (score > secondPeakScore) {\r
  64         secondPeak = i;\r
  65         secondPeakScore = score;\r
  66       }\r
  67     }\r
  68 \r
  69     // Put firstPeak first\r
  70     if (firstPeak > secondPeak) {\r
  71       int temp = firstPeak;\r
  72       firstPeak = secondPeak;\r
  73       secondPeak = temp;\r
  74     }\r
  75 \r
  76     // Find a valley between them that is low and close to the midpoint of the two peaks\r
  77     int bestValley = firstPeak;\r
  78     int bestValleyScore = 0;\r
  79     for (int i = firstPeak + 1; i < secondPeak; i++) {\r
  80       // Encourage low valleys near the mid point between peaks\r
  81       int score = (firstPeakSize - luminanceBuckets[i]) * (i - firstPeak) * (secondPeak - i);\r
  82       if (score > bestValleyScore) {\r
  83         bestValley = i;\r
  84         bestValleyScore = score;\r
  85       }\r
  86     }\r
  87 \r
  88     return bestValley;\r
  89   }\r
  90 \r
  91 }