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) {
  35
  36         }
  37
  38         GlobalHistogramBinarizer::~GlobalHistogramBinarizer() {
  39         }
  40
  41
  42         Ref<BitArray> GlobalHistogramBinarizer::estimateBlackRow(int y, Ref<BitArray> row){
  43                 valarray<int> histogram(0, LUMINANCE_BUCKETS);
  44                 LuminanceSource& source = *getSource();
  45                 int width = source.getWidth();
  46                 if (row == NULL || row->getSize() < width) {
  47                         row = new BitArray(width);
  48                 } else {
  49                         row->clear();
  50                 }
  51
  52                 for (int x = 0; x < width; x++) {
  53                         unsigned char pixel = source.getPixel(x, y);
  54                         histogram[pixel >> LUMINANCE_SHIFT]++;
  55                 }
  56                 int blackPoint = estimate(histogram) << LUMINANCE_SHIFT;
  57
  58
  59                 Ref<BitArray> array_ref(new BitArray(width));
  60                 BitArray& array = *array_ref;
  61
  62                 int left = source.getPixel(0, y);
  63                 int center = source.getPixel(1, y);
  64                 for (int x = 1; x < width - 1; x++) {
  65                         int right = source.getPixel(x+1, y);
  66                         // A simple -1 4 -1 box filter with a weight of 2.
  67                         int luminance = ((center << 2) - left - right) >> 1;
  68                         if (luminance < blackPoint) {
  69                                 array.set(x);
  70                         }
  71                         left = center;
  72                         center = right;
  73                 }
  74
  75                 return array_ref;
  76         }
  77
  78         Ref<BitMatrix> GlobalHistogramBinarizer::estimateBlackMatrix() {
  79                 // Faster than working with the reference
  80                 LuminanceSource& source = *getSource();
  81                 int width = source.getWidth();
  82                 int height = source.getHeight();
  83                 valarray<int> histogram(0, LUMINANCE_BUCKETS);
  84
  85
  86                 // Quickly calculates the histogram by sampling four rows from the image. This proved to be
  87                 // more robust on the blackbox tests than sampling a diagonal as we used to do.
  88                 for (int y = 1; y < 5; y++) {
  89                         int row = height * y / 5;
  90                         int right = (width << 2) / 5;
  91                         int sdf;
  92                         for (int x = width / 5; x < right; x++) {
  93                                 unsigned char pixel = source.getPixel(x, row);
  94                                 histogram[pixel >> LUMINANCE_SHIFT]++;
  95                                 sdf = histogram[pixel >> LUMINANCE_SHIFT];
  96                         }
  97                 }
  98
  99                 int blackPoint = estimate(histogram) << LUMINANCE_SHIFT;
 100
 101                 Ref<BitMatrix> matrix_ref(new BitMatrix(width, height));
 102                 BitMatrix& matrix = *matrix_ref;
 103                 for (int y = 0; y < height; y++) {
 104                         for (int x = 0; x < width; x++) {
 105                                 if (source.getPixel(x, y) <= blackPoint)
 106                                         matrix.set(x, y);
 107                         }
 108                 }
 109                 return matrix_ref;
 110         }
 111
 112         int GlobalHistogramBinarizer::estimate(valarray<int> &histogram) {
 113                 int numBuckets = histogram.size();
 114                 int maxBucketCount = 0;
 115
 116
 117                 // Find tallest peak in histogram
 118                 int firstPeak = 0;
 119                 int firstPeakSize = 0;
 120                 for (int i = 0; i < numBuckets; i++) {
 121                         if (histogram[i] > firstPeakSize) {
 122                                 firstPeak = i;
 123                                 firstPeakSize = histogram[i];
 124                         }
 125                         if (histogram[i] > maxBucketCount) {
 126                                 maxBucketCount = histogram[i];
 127                         }
 128                 }
 129
 130                 // Find second-tallest peak -- well, another peak that is tall and not
 131                 // so close to the first one
 132                 int secondPeak = 0;
 133                 int secondPeakScore = 0;
 134                 for (int i = 0; i < numBuckets; i++) {
 135                         int distanceToBiggest = i - firstPeak;
 136                         // Encourage more distant second peaks by multiplying by square of distance
 137                         int score = histogram[i] * distanceToBiggest * distanceToBiggest;
 138                         if (score > secondPeakScore) {
 139                                 secondPeak = i;
 140                                 secondPeakScore = score;
 141                         }
 142                 }
 143
 144                 // Put firstPeak first
 145                 if (firstPeak > secondPeak) {
 146                         int temp = firstPeak;
 147                         firstPeak = secondPeak;
 148                         secondPeak = temp;
 149                 }
 150
 151                 // Kind of arbitrary; if the two peaks are very close, then we figure there is so little
 152                 // dynamic range in the image, that discriminating black and white is too error-prone.
 153                 // Decoding the image/line is either pointless, or may in some cases lead to a false positive
 154                 // for 1D formats, which are relatively lenient.
 155                 // We arbitrarily say "close" is "<= 1/16 of the total histogram buckets apart"
 156                 if (secondPeak - firstPeak <= numBuckets >> 4) {
 157                         throw IllegalArgumentException("Too little dynamic range in luminance");
 158                 }
 159
 160                 // Find a valley between them that is low and closer to the white peak
 161                 int bestValley = secondPeak - 1;
 162                 int bestValleyScore = -1;
 163                 for (int i = secondPeak - 1; i > firstPeak; i--) {
 164                         int fromFirst = i - firstPeak;
 165                         // Favor a "valley" that is not too close to either peak -- especially not the black peak --
 166                         // and that has a low value of course
 167                         int score = fromFirst * fromFirst * (secondPeak - i) * (maxBucketCount - histogram[i]);
 168                         if (score > bestValleyScore) {
 169                                 bestValley = i;
 170                                 bestValleyScore = score;
 171                         }
 172                 }
 173
 174                 return bestValley;
 175         }
 176
 177 }