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