2 * GlobalHistogramBinarizer.cpp
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.
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
13 * http://www.apache.org/licenses/LICENSE-2.0
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.
22 #include <zxing/common/GlobalHistogramBinarizer.h>
24 #include <zxing/common/IllegalArgumentException.h>
29 const int LUMINANCE_BITS = 5;
30 const int LUMINANCE_SHIFT = 8 - LUMINANCE_BITS;
31 const int LUMINANCE_BUCKETS = 1 << LUMINANCE_BITS;
33 GlobalHistogramBinarizer::GlobalHistogramBinarizer(Ref<LuminanceSource> source) :
34 Binarizer(source), cached_matrix_(NULL), cached_row_(NULL), cached_row_num_(-1) {
38 GlobalHistogramBinarizer::~GlobalHistogramBinarizer() {
42 Ref<BitArray> GlobalHistogramBinarizer::getBlackRow(int y, Ref<BitArray> row) {
44 if (row == cached_row_num_) {
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);
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]++;
63 int blackPoint = estimate(histogram) << LUMINANCE_SHIFT;
66 Ref<BitArray> array_ref(new BitArray(width));
67 BitArray& array = *array_ref;
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) {
82 cached_row_ = array_ref;
89 Ref<BitMatrix> GlobalHistogramBinarizer::getBlackMatrix() {
91 if (cached_matrix_ != NULL) {
92 return cached_matrix_;
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);
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;
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];
117 int blackPoint = estimate(histogram) << LUMINANCE_SHIFT;
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)
129 cached_matrix_ = matrix_ref;
135 int GlobalHistogramBinarizer::estimate(vector<int> &histogram) {
136 int numBuckets = histogram.size();
137 int maxBucketCount = 0;
140 // Find tallest peak in histogram
142 int firstPeakSize = 0;
143 for (int i = 0; i < numBuckets; i++) {
144 if (histogram[i] > firstPeakSize) {
146 firstPeakSize = histogram[i];
148 if (histogram[i] > maxBucketCount) {
149 maxBucketCount = histogram[i];
153 // Find second-tallest peak -- well, another peak that is tall and not
154 // so close to the first one
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) {
163 secondPeakScore = score;
167 // Put firstPeak first
168 if (firstPeak > secondPeak) {
169 int temp = firstPeak;
170 firstPeak = secondPeak;
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");
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) {
196 bestValleyScore = score;
203 Ref<Binarizer> GlobalHistogramBinarizer::createBinarizer(Ref<LuminanceSource> source) {
204 return Ref<Binarizer> (new GlobalHistogramBinarizer(source));