cpp/core/src/zxing/common/GlobalHistogramBinarizer.cpp

   1 /*
   2  *  GlobalHistogramBinarizer.cpp
   3  *  zxing
   4  *
   5  *  Created by Ralf Kistner on 16/10/2009.
   6  *  Copyright 2008 ZXing authors All rights reserved.
   7  *
   8  * Licensed under the Apache License, Version 2.0 (the "License");
   9  * you may not use this file except in compliance with the License.
  10  * You may obtain a copy of the License at
  11  *
  12  *      http://www.apache.org/licenses/LICENSE-2.0
  13  *
  14  * Unless required by applicable law or agreed to in writing, software
  15  * distributed under the License is distributed on an "AS IS" BASIS,
  16  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  17  * See the License for the specific language governing permissions and
  18  * limitations under the License.
  19  */
  20
  21 #include <zxing/common/GlobalHistogramBinarizer.h>
  22
  23 #include <zxing/common/IllegalArgumentException.h>
  24
  25 namespace zxing {
  26 using namespace std;
  27
  28 const int LUMINANCE_BITS = 5;
  29 const int LUMINANCE_SHIFT = 8 - LUMINANCE_BITS;
  30 const int LUMINANCE_BUCKETS = 1 << LUMINANCE_BITS;
  31
  32 GlobalHistogramBinarizer::GlobalHistogramBinarizer(Ref<LuminanceSource> source) :
  33     Binarizer(source) {
  34
  35 }
  36
  37 GlobalHistogramBinarizer::~GlobalHistogramBinarizer() {
  38 }
  39
  40 Ref<BitMatrix> GlobalHistogramBinarizer::estimateBlackMatrix() {
  41   // Faster than working with the reference
  42   LuminanceSource& source = *getSource();
  43   int width = source.getWidth();
  44   int height = source.getHeight();
  45   valarray<int> histogram(0, LUMINANCE_BUCKETS);
  46
  47
  48   // Quickly calculates the histogram by sampling four rows from the image. This proved to be
  49   // more robust on the blackbox tests than sampling a diagonal as we used to do.
  50   for (int y = 1; y < 5; y++) {
  51     int row = height * y / 5;
  52     int right = (width << 2) / 5;
  53     int sdf;
  54     for (int x = width / 5; x < right; x++) {
  55       unsigned char pixel = source.getPixel(x, row);
  56       histogram[pixel >> LUMINANCE_SHIFT]++;
  57       sdf = histogram[pixel >> LUMINANCE_SHIFT];
  58     }
  59   }
  60
  61   int blackPoint = estimate(histogram) << LUMINANCE_SHIFT;
  62
  63   Ref<BitMatrix> matrix_ref(new BitMatrix(width, height));
  64   BitMatrix& matrix = *matrix_ref;
  65   for (int y = 0; y < height; y++) {
  66     for (int x = 0; x < width; x++) {
  67       if (source.getPixel(x, y) <= blackPoint)
  68         matrix.set(x, y);
  69     }
  70   }
  71   return matrix_ref;
  72 }
  73
  74 int GlobalHistogramBinarizer::estimate(valarray<int> &histogram) {
  75   int numBuckets = histogram.size();
  76   int maxBucketCount = 0;
  77
  78
  79   // Find tallest peak in histogram
  80   int firstPeak = 0;
  81   int firstPeakSize = 0;
  82   for (int i = 0; i < numBuckets; i++) {
  83     if (histogram[i] > firstPeakSize) {
  84       firstPeak = i;
  85       firstPeakSize = histogram[i];
  86     }
  87     if (histogram[i] > maxBucketCount) {
  88       maxBucketCount = histogram[i];
  89     }
  90   }
  91
  92   // Find second-tallest peak -- well, another peak that is tall and not
  93   // so close to the first one
  94   int secondPeak = 0;
  95   int secondPeakScore = 0;
  96   for (int i = 0; i < numBuckets; i++) {
  97     int distanceToBiggest = i - firstPeak;
  98     // Encourage more distant second peaks by multiplying by square of distance
  99     int score = histogram[i] * distanceToBiggest * distanceToBiggest;
 100     if (score > secondPeakScore) {
 101       secondPeak = i;
 102       secondPeakScore = score;
 103     }
 104   }
 105
 106   // Put firstPeak first
 107   if (firstPeak > secondPeak) {
 108     int temp = firstPeak;
 109     firstPeak = secondPeak;
 110     secondPeak = temp;
 111   }
 112
 113   // Kind of arbitrary; if the two peaks are very close, then we figure there is so little
 114   // dynamic range in the image, that discriminating black and white is too error-prone.
 115   // Decoding the image/line is either pointless, or may in some cases lead to a false positive
 116   // for 1D formats, which are relatively lenient.
 117   // We arbitrarily say "close" is "<= 1/16 of the total histogram buckets apart"
 118   if (secondPeak - firstPeak <= numBuckets >> 4) {
 119     throw IllegalArgumentException("Too little dynamic range in luminance");
 120   }
 121
 122   // Find a valley between them that is low and closer to the white peak
 123   int bestValley = secondPeak - 1;
 124   int bestValleyScore = -1;
 125   for (int i = secondPeak - 1; i > firstPeak; i--) {
 126     int fromFirst = i - firstPeak;
 127     // Favor a "valley" that is not too close to either peak -- especially not the black peak --
 128     // and that has a low value of course
 129     int score = fromFirst * fromFirst * (secondPeak - i) * (maxBucketCount - histogram[i]);
 130     if (score > bestValleyScore) {
 131       bestValley = i;
 132       bestValleyScore = score;
 133     }
 134   }
 135
 136   return bestValley;
 137 }
 138
 139 }