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