csharp/common/BlackPointEstimator.cs

   1 /*\r
   2 * Licensed under the Apache License, Version 2.0 (the "License");\r
   3 * you may not use this file except in compliance with the License.\r
   4 * You may obtain a copy of the License at\r
   5 *\r
   6 *      http://www.apache.org/licenses/LICENSE-2.0\r
   7 *\r
   8 * Unless required by applicable law or agreed to in writing, software\r
   9 * distributed under the License is distributed on an "AS IS" BASIS,\r
  10 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
  11 * See the License for the specific language governing permissions and\r
  12 * limitations under the License.\r
  13 */\r
  14 \r
  15 using System;\r
  16 namespace com.google.zxing.common\r
  17 {\r
  18 \r
  19     /// <summary> <p>Encapsulates logic that estimates the optimal "black point", the luminance value\r
  20     /// which is the best line between "white" and "black" in a grayscale image.</p>\r
  21     /// \r
  22     /// <p>For an interesting discussion of this issue, see\r
  23     /// <a href="http://webdiis.unizar.es/~neira/12082/thresholding.pdf">http://webdiis.unizar.es/~neira/12082/thresholding.pdf</a>.\r
  24     /// </p>\r
  25     /// \r
  26     /// </summary>\r
  27     /// <author>  srowen@google.com (Sean Owen)\r
  28     /// </author>\r
  29     /// <author>  dswitkin@google.com (Daniel Switkin)\r
  30     /// </author>\r
  31     public sealed class BlackPointEstimator\r
  32     { \r
  33           private BlackPointEstimator() \r
  34           {\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)\r
  48           {\r
  49             try{\r
  50           \r
  51                 int numBuckets = histogram.Length;\r
  52                 int maxBucketCount = 0;\r
  53                 // Find tallest peak in histogram\r
  54                 int firstPeak = 0;\r
  55                 int firstPeakSize = 0;\r
  56                 for (int i = 0; i < numBuckets; i++) {\r
  57                   if (histogram[i] > firstPeakSize) {\r
  58                     firstPeak = i;\r
  59                     firstPeakSize = histogram[i];\r
  60                   }\r
  61                   if (histogram[i] > maxBucketCount) {\r
  62                     maxBucketCount = histogram[i];\r
  63                   }\r
  64                 }\r
  65 \r
  66                 // Find second-tallest peak -- well, another peak that is tall and not\r
  67                 // so close to the first one\r
  68                 int secondPeak = 0;\r
  69                 int secondPeakScore = 0;\r
  70                 for (int i = 0; i < numBuckets; i++) {\r
  71                   int distanceToBiggest = i - firstPeak;\r
  72                   // Encourage more distant second peaks by multiplying by square of distance\r
  73                   int score = histogram[i] * distanceToBiggest * distanceToBiggest;\r
  74                   if (score > secondPeakScore) {\r
  75                     secondPeak = i;\r
  76                     secondPeakScore = score;\r
  77                   }\r
  78                 }\r
  79 \r
  80                 // Put firstPeak first\r
  81                 if (firstPeak > secondPeak) {\r
  82                   int temp = firstPeak;\r
  83                   firstPeak = secondPeak;\r
  84                   secondPeak = temp;\r
  85                 }\r
  86 \r
  87                 // Kind of aribtrary; if the two peaks are very close, then we figure there is so little\r
  88                 // dynamic range in the image, that discriminating black and white is too error-prone.\r
  89                 // Decoding the image/line is either pointless, or may in some cases lead to a false positive\r
  90                 // for 1D formats, which are relatively lenient.\r
  91                 // We arbitrarily say "close" is "<= 1/16 of the total histogram buckets apart"\r
  92                 if (secondPeak - firstPeak <= numBuckets >> 4) {\r
  93                   throw new ReaderException("");\r
  94                 }\r
  95 \r
  96                 // Find a valley between them that is low and closer to the white peak\r
  97                 int bestValley = secondPeak - 1;\r
  98                 int bestValleyScore = -1;\r
  99                 for (int i = secondPeak - 1; i > firstPeak; i--) {\r
 100                   int fromFirst = i - firstPeak;\r
 101                   // Favor a "valley" that is not too close to either peak -- especially not the black peak --\r
 102                   // and that has a low value of course\r
 103                   int score = fromFirst * fromFirst * (secondPeak - i) * (maxBucketCount - histogram[i]);\r
 104                   if (score > bestValleyScore) {\r
 105                     bestValley = i;\r
 106                     bestValleyScore = score;\r
 107                   }\r
 108                 }\r
 109 \r
 110                 return bestValley;\r
 111                 }\r
 112             catch (Exception e)\r
 113             {\r
 114                 throw (ReaderException) e; \r
 115             }\r
 116           }\r
 117     }\r
 118 }