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

   1 /*
   2  *  GlobalHistogramBinarizer.cpp
   3  *  zxing
   4  *
   5  *  Copyright 2010 ZXing authors. All rights reserved.
   6  *
   7  * Licensed under the Apache License, Version 2.0 (the "License");
   8  * you may not use this file except in compliance with the License.
   9  * You may obtain a copy of the License at
  10  *
  11  *      http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  */
  19
  20 #include <zxing/common/GlobalHistogramBinarizer.h>
  21
  22 #include <zxing/common/IllegalArgumentException.h>
  23
  24 namespace zxing {
  25 using namespace std;
  26
  27 const int LUMINANCE_BITS = 5;
  28 const int LUMINANCE_SHIFT = 8 - LUMINANCE_BITS;
  29 const int LUMINANCE_BUCKETS = 1 << LUMINANCE_BITS;
  30
  31 GlobalHistogramBinarizer::GlobalHistogramBinarizer(Ref<LuminanceSource> source) :
  32   Binarizer(source), cached_matrix_(NULL), cached_row_(NULL), cached_row_num_(-1) {
  33
  34 }
  35
  36 GlobalHistogramBinarizer::~GlobalHistogramBinarizer() {
  37 }
  38
  39
  40 Ref<BitArray> GlobalHistogramBinarizer::getBlackRow(int y, Ref<BitArray> row) {
  41   if (y == cached_row_num_) {
  42     if (cached_row_ != NULL) {
  43       return cached_row_;
  44     } else {
  45       throw IllegalArgumentException("Too little dynamic range in luminance");
  46     }
  47   }
  48
  49   vector<int> histogram(LUMINANCE_BUCKETS, 0);
  50   LuminanceSource& source = *getLuminanceSource();
  51   int width = source.getWidth();
  52   if (row == NULL || static_cast<int>(row->getSize()) < width) {
  53     row = new BitArray(width);
  54   } else {
  55     row->clear();
  56   }
  57
  58   //TODO(flyashi): cache this instead of allocating and deleting per row
  59   unsigned char* row_pixels = NULL;
  60   try {
  61     row_pixels = new unsigned char[width];
  62     row_pixels = source.getRow(y, row_pixels);
  63     for (int x = 0; x < width; x++) {
  64       histogram[row_pixels[x] >> LUMINANCE_SHIFT]++;
  65     }
  66     int blackPoint = estimate(histogram) << LUMINANCE_SHIFT;
  67
  68     BitArray& array = *row;
  69     int left = row_pixels[0];
  70     int center = row_pixels[1];
  71     for (int x = 1; x < width - 1; x++) {
  72       int right = row_pixels[x + 1];
  73       // A simple -1 4 -1 box filter with a weight of 2.
  74       int luminance = ((center << 2) - left - right) >> 1;
  75       if (luminance < blackPoint) {
  76         array.set(x);
  77       }
  78       left = center;
  79       center = right;
  80     }
  81
  82     cached_row_ = row;
  83     cached_row_num_ = y;
  84     delete [] row_pixels;
  85     return row;
  86   } catch (IllegalArgumentException const& iae) {
  87     // Cache the fact that this row failed.
  88     cached_row_ = NULL;
  89     cached_row_num_ = y;
  90     delete [] row_pixels;
  91     throw iae;
  92   }
  93 }
  94
  95 Ref<BitMatrix> GlobalHistogramBinarizer::getBlackMatrix() {
  96   if (cached_matrix_ != NULL) {
  97     return cached_matrix_;
  98   }
  99
 100   // Faster than working with the reference
 101   LuminanceSource& source = *getLuminanceSource();
 102   int width = source.getWidth();
 103   int height = source.getHeight();
 104   vector<int> histogram(LUMINANCE_BUCKETS, 0);
 105
 106   // Quickly calculates the histogram by sampling four rows from the image.
 107   // This proved to be more robust on the blackbox tests than sampling a
 108   // diagonal as we used to do.
 109   unsigned char* row = new unsigned char[width];
 110   for (int y = 1; y < 5; y++) {
 111     int rownum = height * y / 5;
 112     int right = (width << 2) / 5;
 113     int sdf;
 114     row = source.getRow(rownum, row);
 115     for (int x = width / 5; x < right; x++) {
 116       histogram[row[x] >> LUMINANCE_SHIFT]++;
 117       sdf = histogram[row[x] >> LUMINANCE_SHIFT];
 118     }
 119   }
 120
 121   int blackPoint = estimate(histogram) << LUMINANCE_SHIFT;
 122
 123   Ref<BitMatrix> matrix_ref(new BitMatrix(width, height));
 124   BitMatrix& matrix = *matrix_ref;
 125   for (int y = 0; y < height; y++) {
 126     row = source.getRow(y, row);
 127     for (int x = 0; x < width; x++) {
 128       if (row[x] <= blackPoint)
 129         matrix.set(x, y);
 130     }
 131   }
 132
 133   cached_matrix_ = matrix_ref;
 134   delete [] row;
 135   return matrix_ref;
 136 }
 137
 138 int GlobalHistogramBinarizer::estimate(vector<int> &histogram) {
 139   int numBuckets = histogram.size();
 140   int maxBucketCount = 0;
 141
 142   // Find tallest peak in histogram
 143   int firstPeak = 0;
 144   int firstPeakSize = 0;
 145   for (int i = 0; i < numBuckets; i++) {
 146     if (histogram[i] > firstPeakSize) {
 147       firstPeak = i;
 148       firstPeakSize = histogram[i];
 149     }
 150     if (histogram[i] > maxBucketCount) {
 151       maxBucketCount = histogram[i];
 152     }
 153   }
 154
 155   // Find second-tallest peak -- well, another peak that is tall and not
 156   // so close to the first one
 157   int secondPeak = 0;
 158   int secondPeakScore = 0;
 159   for (int i = 0; i < numBuckets; i++) {
 160     int distanceToBiggest = i - firstPeak;
 161     // Encourage more distant second peaks by multiplying by square of distance
 162     int score = histogram[i] * distanceToBiggest * distanceToBiggest;
 163     if (score > secondPeakScore) {
 164       secondPeak = i;
 165       secondPeakScore = score;
 166     }
 167   }
 168
 169   // Put firstPeak first
 170   if (firstPeak > secondPeak) {
 171     int temp = firstPeak;
 172     firstPeak = secondPeak;
 173     secondPeak = temp;
 174   }
 175
 176   // Kind of arbitrary; if the two peaks are very close, then we figure there is
 177   // so little dynamic range in the image, that discriminating black and white
 178   // is too error-prone.
 179   // Decoding the image/line is either pointless, or may in some cases lead to
 180   // a false positive for 1D formats, which are relatively lenient.
 181   // We arbitrarily say "close" is
 182   // "<= 1/16 of the total histogram buckets apart"
 183   if (secondPeak - firstPeak <= numBuckets >> 4) {
 184     throw IllegalArgumentException("Too little dynamic range in luminance");
 185   }
 186
 187   // Find a valley between them that is low and closer to the white peak
 188   int bestValley = secondPeak - 1;
 189   int bestValleyScore = -1;
 190   for (int i = secondPeak - 1; i > firstPeak; i--) {
 191     int fromFirst = i - firstPeak;
 192     // Favor a "valley" that is not too close to either peak -- especially not
 193     // the black peak -- and that has a low value of course
 194     int score = fromFirst * fromFirst * (secondPeak - i) *
 195       (maxBucketCount - histogram[i]);
 196     if (score > bestValleyScore) {
 197       bestValley = i;
 198       bestValleyScore = score;
 199     }
 200   }
 201
 202   return bestValley;
 203 }
 204
 205 Ref<Binarizer> GlobalHistogramBinarizer::createBinarizer(Ref<LuminanceSource> source) {
 206   return Ref<Binarizer> (new GlobalHistogramBinarizer(source));
 207 }
 208
 209 } // namespace zxing