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
  44   if (row == cached_row_num_) {
  45     return cached_row_;
  46   }
  47
  48   vector<int> histogram(LUMINANCE_BUCKETS, 0);
  49   LuminanceSource& source = *getLuminanceSource();
  50   int width = source.getWidth();
  51   if (row == NULL || static_cast<int>(row->getSize()) < width) {
  52     row = new BitArray(width);
  53   } else {
  54     row->clear();
  55   }
  56
  57   //TODO(flyashi): cache this instead of allocating and deleting per row
  58   unsigned char* row_pixels = new unsigned char[width];
  59   getLuminanceSource()->getRow(y,row_pixels);
  60   for (int x = 0; x < width; x++) {
  61     histogram[row_pixels[x] >> LUMINANCE_SHIFT]++;
  62   }
  63   int blackPoint = estimate(histogram) << LUMINANCE_SHIFT;
  64
  65
  66   Ref<BitArray> array_ref(new BitArray(width));
  67   BitArray& array = *array_ref;
  68
  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_ = array_ref;
  83   cached_row_num_ = y;
  84
  85   delete [] row_pixels;
  86   return array_ref;
  87 }
  88
  89 Ref<BitMatrix> GlobalHistogramBinarizer::getBlackMatrix() {
  90
  91   if (cached_matrix_ != NULL) {
  92     return cached_matrix_;
  93   }
  94
  95   // Faster than working with the reference
  96   LuminanceSource& source = *getLuminanceSource();
  97   int width = source.getWidth();
  98   int height = source.getHeight();
  99   vector<int> histogram(LUMINANCE_BUCKETS, 0);
 100
 101
 102   // Quickly calculates the histogram by sampling four rows from the image.
 103   // This proved to be more robust on the blackbox tests than sampling a
 104   // diagonal as we used to do.
 105   unsigned char* row = new unsigned char[width];
 106   for (int y = 1; y < 5; y++) {
 107     int rownum = height * y / 5;
 108     int right = (width << 2) / 5;
 109     int sdf;
 110     getLuminanceSource()->getRow(rownum,row);
 111     for (int x = width / 5; x < right; x++) {
 112       histogram[row[x] >> LUMINANCE_SHIFT]++;
 113       sdf = histogram[row[x] >> LUMINANCE_SHIFT];
 114     }
 115   }
 116
 117   int blackPoint = estimate(histogram) << LUMINANCE_SHIFT;
 118
 119   Ref<BitMatrix> matrix_ref(new BitMatrix(width, height));
 120   BitMatrix& matrix = *matrix_ref;
 121   for (int y = 0; y < height; y++) {
 122     getLuminanceSource()->getRow(y,row);
 123     for (int x = 0; x < width; x++) {
 124       if (row[x] <= blackPoint)
 125         matrix.set(x, y);
 126     }
 127   }
 128
 129   cached_matrix_ = matrix_ref;
 130
 131   delete [] row;
 132   return matrix_ref;
 133 }
 134
 135 int GlobalHistogramBinarizer::estimate(vector<int> &histogram) {
 136   int numBuckets = histogram.size();
 137   int maxBucketCount = 0;
 138
 139
 140   // Find tallest peak in histogram
 141   int firstPeak = 0;
 142   int firstPeakSize = 0;
 143   for (int i = 0; i < numBuckets; i++) {
 144     if (histogram[i] > firstPeakSize) {
 145       firstPeak = i;
 146       firstPeakSize = histogram[i];
 147     }
 148     if (histogram[i] > maxBucketCount) {
 149       maxBucketCount = histogram[i];
 150     }
 151   }
 152
 153   // Find second-tallest peak -- well, another peak that is tall and not
 154   // so close to the first one
 155   int secondPeak = 0;
 156   int secondPeakScore = 0;
 157   for (int i = 0; i < numBuckets; i++) {
 158     int distanceToBiggest = i - firstPeak;
 159     // Encourage more distant second peaks by multiplying by square of distance
 160     int score = histogram[i] * distanceToBiggest * distanceToBiggest;
 161     if (score > secondPeakScore) {
 162       secondPeak = i;
 163       secondPeakScore = score;
 164     }
 165   }
 166
 167   // Put firstPeak first
 168   if (firstPeak > secondPeak) {
 169     int temp = firstPeak;
 170     firstPeak = secondPeak;
 171     secondPeak = temp;
 172   }
 173
 174   // Kind of arbitrary; if the two peaks are very close, then we figure there is
 175   // so little dynamic range in the image, that discriminating black and white
 176   // is too error-prone.
 177   // Decoding the image/line is either pointless, or may in some cases lead to
 178   // a false positive for 1D formats, which are relatively lenient.
 179   // We arbitrarily say "close" is
 180   // "<= 1/16 of the total histogram buckets apart"
 181   if (secondPeak - firstPeak <= numBuckets >> 4) {
 182     throw IllegalArgumentException("Too little dynamic range in luminance");
 183   }
 184
 185   // Find a valley between them that is low and closer to the white peak
 186   int bestValley = secondPeak - 1;
 187   int bestValleyScore = -1;
 188   for (int i = secondPeak - 1; i > firstPeak; i--) {
 189     int fromFirst = i - firstPeak;
 190     // Favor a "valley" that is not too close to either peak -- especially not
 191     // the black peak -- and that has a low value of course
 192     int score = fromFirst * fromFirst * (secondPeak - i) *
 193       (maxBucketCount - histogram[i]);
 194     if (score > bestValleyScore) {
 195       bestValley = i;
 196       bestValleyScore = score;
 197     }
 198   }
 199
 200   return bestValley;
 201 }
 202
 203 Ref<Binarizer> GlobalHistogramBinarizer::createBinarizer(Ref<LuminanceSource> source) {
 204   return Ref<Binarizer> (new GlobalHistogramBinarizer(source));
 205 }
 206
 207 } // namespace zxing
 208