Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/zxing-cpp/core/src/HybridBinarizer.cpp @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
1 /*
2 * Copyright 2016 Nu-book Inc.
3 * Copyright 2016 ZXing authors
4 */
5 // SPDX-License-Identifier: Apache-2.0
6
7 #include "HybridBinarizer.h"
8
9 #include "BitMatrix.h"
10 #include "Matrix.h"
11
12 #include <algorithm>
13 #include <cstdint>
14 #include <fstream>
15 #include <memory>
16
17 #define USE_NEW_ALGORITHM
18
19 namespace ZXing {
20
21 // This class uses 5x5 blocks to compute local luminance, where each block is 8x8 pixels.
22 // So this is the smallest dimension in each axis we can accept.
23 static constexpr int BLOCK_SIZE = 8;
24 static constexpr int WINDOW_SIZE = BLOCK_SIZE * (1 + 2 * 2);
25 static constexpr int MIN_DYNAMIC_RANGE = 24;
26
27 HybridBinarizer::HybridBinarizer(const ImageView& iv) : GlobalHistogramBinarizer(iv) {}
28
29 HybridBinarizer::~HybridBinarizer() = default;
30
31 bool HybridBinarizer::getPatternRow(int row, int rotation, PatternRow& res) const
32 {
33 #if 1
34 // This is the original "hybrid" behavior: use GlobalHistogram for the 1D case
35 return GlobalHistogramBinarizer::getPatternRow(row, rotation, res);
36 #else
37 // This is an alternative that can be faster in general and perform better in unevenly lit sitations like
38 // https://github.com/zxing-cpp/zxing-cpp/blob/master/test/samples/ean13-2/21.png. That said, it fairs
39 // worse in borderline low resolution situations. With the current black box sample set we'd loose 94
40 // test cases while gaining 53 others.
41 auto bits = getBitMatrix();
42 if (bits)
43 GetPatternRow(*bits, row, res, rotation % 180 != 0);
44 return bits != nullptr;
45 #endif
46 }
47
48 using T_t = uint8_t;
49
50 /**
51 * Applies a single threshold to a block of pixels.
52 */
53 static void ThresholdBlock(const uint8_t* __restrict luminances, int xoffset, int yoffset, T_t threshold, int rowStride,
54 BitMatrix& matrix)
55 {
56 for (int y = yoffset; y < yoffset + BLOCK_SIZE; ++y) {
57 auto* src = luminances + y * rowStride + xoffset;
58 auto* const dstBegin = matrix.row(y).begin() + xoffset;
59 // TODO: fix pixelStride > 1 case
60 for (auto* dst = dstBegin; dst < dstBegin + BLOCK_SIZE; ++dst, ++src)
61 *dst = (*src <= threshold) * BitMatrix::SET_V;
62 }
63 }
64
65 #ifndef USE_NEW_ALGORITHM
66
67 /**
68 * Calculates a single black point for each block of pixels and saves it away.
69 * See the following thread for a discussion of this algorithm:
70 * http://groups.google.com/group/zxing/browse_thread/thread/d06efa2c35a7ddc0
71 */
72 static Matrix<T_t> CalculateBlackPoints(const uint8_t* __restrict luminances, int subWidth, int subHeight, int width, int height,
73 int rowStride)
74 {
75 Matrix<T_t> blackPoints(subWidth, subHeight);
76
77 for (int y = 0; y < subHeight; y++) {
78 int yoffset = std::min(y * BLOCK_SIZE, height - BLOCK_SIZE);
79 for (int x = 0; x < subWidth; x++) {
80 int xoffset = std::min(x * BLOCK_SIZE, width - BLOCK_SIZE);
81 int sum = 0;
82 uint8_t min = luminances[yoffset * rowStride + xoffset];
83 uint8_t max = min;
84 for (int yy = 0, offset = yoffset * rowStride + xoffset; yy < BLOCK_SIZE; yy++, offset += rowStride) {
85 for (int xx = 0; xx < BLOCK_SIZE; xx++) {
86 auto pixel = luminances[offset + xx];
87 sum += pixel;
88 if (pixel < min)
89 min = pixel;
90 if (pixel > max)
91 max = pixel;
92 }
93 // short-circuit min/max tests once dynamic range is met
94 if (max - min > MIN_DYNAMIC_RANGE) {
95 // finish the rest of the rows quickly
96 for (yy++, offset += rowStride; yy < BLOCK_SIZE; yy++, offset += rowStride) {
97 for (int xx = 0; xx < BLOCK_SIZE; xx++) {
98 sum += luminances[offset + xx];
99 }
100 }
101 }
102 }
103
104 // The default estimate is the average of the values in the block.
105 int average = sum / (BLOCK_SIZE * BLOCK_SIZE);
106 if (max - min <= MIN_DYNAMIC_RANGE) {
107 // If variation within the block is low, assume this is a block with only light or only
108 // dark pixels. In that case we do not want to use the average, as it would divide this
109 // low contrast area into black and white pixels, essentially creating data out of noise.
110 //
111 // The default assumption is that the block is light/background. Since no estimate for
112 // the level of dark pixels exists locally, use half the min for the block.
113 average = min / 2;
114
115 if (y > 0 && x > 0) {
116 // Correct the "white background" assumption for blocks that have neighbors by comparing
117 // the pixels in this block to the previously calculated black points. This is based on
118 // the fact that dark barcode symbology is always surrounded by some amount of light
119 // background for which reasonable black point estimates were made. The bp estimated at
120 // the boundaries is used for the interior.
121
122 // The (min < bp) is arbitrary but works better than other heuristics that were tried.
123 int averageNeighborBlackPoint =
124 (blackPoints(x, y - 1) + (2 * blackPoints(x - 1, y)) + blackPoints(x - 1, y - 1)) / 4;
125 if (min < averageNeighborBlackPoint) {
126 average = averageNeighborBlackPoint;
127 }
128 }
129 }
130 blackPoints(x, y) = average;
131 }
132 }
133 return blackPoints;
134 }
135
136 /**
137 * For each block in the image, calculate the average black point using a 5x5 grid
138 * of the blocks around it. Also handles the corner cases (fractional blocks are computed based
139 * on the last pixels in the row/column which are also used in the previous block).
140 */
141 static std::shared_ptr<BitMatrix> CalculateMatrix(const uint8_t* __restrict luminances, int subWidth, int subHeight, int width,
142 int height, int rowStride, const Matrix<T_t>& blackPoints)
143 {
144 auto matrix = std::make_shared<BitMatrix>(width, height);
145
146 #ifdef PRINT_DEBUG
147 Matrix<uint8_t> out(width, height);
148 Matrix<uint8_t> out2(width, height);
149 #endif
150
151 for (int y = 0; y < subHeight; y++) {
152 int yoffset = std::min(y * BLOCK_SIZE, height - BLOCK_SIZE);
153 for (int x = 0; x < subWidth; x++) {
154 int xoffset = std::min(x * BLOCK_SIZE, width - BLOCK_SIZE);
155 int left = std::clamp(x, 2, subWidth - 3);
156 int top = std::clamp(y, 2, subHeight - 3);
157 int sum = 0;
158 for (int dy = -2; dy <= 2; ++dy) {
159 for (int dx = -2; dx <= 2; ++dx) {
160 sum += blackPoints(left + dx, top + dy);
161 }
162 }
163 int average = sum / 25;
164 ThresholdBlock(luminances, xoffset, yoffset, average, rowStride, *matrix);
165
166 #ifdef PRINT_DEBUG
167 for (int yy = 0; yy < 8; ++yy)
168 for (int xx = 0; xx < 8; ++xx) {
169 out.set(xoffset + xx, yoffset + yy, blackPoints(x, y));
170 out2.set(xoffset + xx, yoffset + yy, average);
171 }
172 #endif
173 }
174 }
175
176 #ifdef PRINT_DEBUG
177 std::ofstream file("thresholds.pnm");
178 file << "P5\n" << out.width() << ' ' << out.height() << "\n255\n";
179 file.write(reinterpret_cast<const char*>(out.data()), out.size());
180 std::ofstream file2("thresholds_avg.pnm");
181 file2 << "P5\n" << out.width() << ' ' << out.height() << "\n255\n";
182 file2.write(reinterpret_cast<const char*>(out2.data()), out2.size());
183 #endif
184
185 return matrix;
186 }
187
188 #else
189
190 // Subdivide the image in blocks of BLOCK_SIZE and calculate one treshold value per block as
191 // (max - min > MIN_DYNAMIC_RANGE) ? (max + min) / 2 : 0
192 static Matrix<T_t> BlockThresholds(const ImageView iv)
193 {
194 int subWidth = (iv.width() + BLOCK_SIZE - 1) / BLOCK_SIZE; // ceil(width/BS)
195 int subHeight = (iv.height() + BLOCK_SIZE - 1) / BLOCK_SIZE; // ceil(height/BS)
196
197 Matrix<T_t> thresholds(subWidth, subHeight);
198
199 for (int y = 0; y < subHeight; y++) {
200 int y0 = std::min(y * BLOCK_SIZE, iv.height() - BLOCK_SIZE);
201 for (int x = 0; x < subWidth; x++) {
202 int x0 = std::min(x * BLOCK_SIZE, iv.width() - BLOCK_SIZE);
203 uint8_t min = 255;
204 uint8_t max = 0;
205 for (int yy = 0; yy < BLOCK_SIZE; yy++) {
206 auto line = iv.data(x0, y0 + yy);
207 for (int xx = 0; xx < BLOCK_SIZE; xx++)
208 UpdateMinMax(min, max, line[xx]);
209 }
210
211 thresholds(x, y) = (max - min > MIN_DYNAMIC_RANGE) ? (int(max) + min) / 2 : 0;
212 }
213 }
214
215 return thresholds;
216 }
217
218 // Apply gaussian-like smoothing filter over all non-zero thresholds and fill any remainig gaps with nearest neighbor
219 static Matrix<T_t> SmoothThresholds(Matrix<T_t>&& in)
220 {
221 Matrix<T_t> out(in.width(), in.height());
222
223 constexpr int R = WINDOW_SIZE / BLOCK_SIZE / 2;
224 for (int y = 0; y < in.height(); y++) {
225 for (int x = 0; x < in.width(); x++) {
226 int left = std::clamp(x, R, in.width() - R - 1);
227 int top = std::clamp(y, R, in.height() - R - 1);
228
229 int sum = in(x, y) * 2;
230 int n = (sum > 0) * 2;
231 auto add = [&](int x, int y) {
232 int t = in(x, y);
233 sum += t;
234 n += t > 0;
235 };
236
237 for (int dy = -R; dy <= R; ++dy)
238 for (int dx = -R; dx <= R; ++dx)
239 add(left + dx, top + dy);
240
241 out(x, y) = n > 0 ? sum / n : 0;
242 }
243 }
244
245 // flood fill any remaing gaps of (very large) no-contrast regions
246 auto last = out.begin() - 1;
247 for (auto* i = out.begin(); i != out.end(); ++i) {
248 if (*i) {
249 if (last != i - 1)
250 std::fill(last + 1, i, *i);
251 last = i;
252 }
253 }
254 std::fill(last + 1, out.end(), *(std::max(last, out.begin())));
255
256 return out;
257 }
258
259 static std::shared_ptr<BitMatrix> ThresholdImage(const ImageView iv, const Matrix<T_t>& thresholds)
260 {
261 auto matrix = std::make_shared<BitMatrix>(iv.width(), iv.height());
262
263 #ifdef PRINT_DEBUG
264 Matrix<uint8_t> out(iv.width(), iv.height());
265 #endif
266
267 for (int y = 0; y < thresholds.height(); y++) {
268 int yoffset = std::min(y * BLOCK_SIZE, iv.height() - BLOCK_SIZE);
269 for (int x = 0; x < thresholds.width(); x++) {
270 int xoffset = std::min(x * BLOCK_SIZE, iv.width() - BLOCK_SIZE);
271 ThresholdBlock(iv.data(), xoffset, yoffset, thresholds(x, y), iv.rowStride(), *matrix);
272
273 #ifdef PRINT_DEBUG
274 for (int yy = 0; yy < 8; ++yy)
275 for (int xx = 0; xx < 8; ++xx)
276 out.set(xoffset + xx, yoffset + yy, thresholds(x, y));
277 #endif
278 }
279 }
280
281 #ifdef PRINT_DEBUG
282 std::ofstream file("thresholds_new.pnm");
283 file << "P5\n" << out.width() << ' ' << out.height() << "\n255\n";
284 file.write(reinterpret_cast<const char*>(out.data()), out.size());
285 #endif
286
287 return matrix;
288 }
289
290 #endif
291
292 std::shared_ptr<const BitMatrix> HybridBinarizer::getBlackMatrix() const
293 {
294 if (width() >= WINDOW_SIZE && height() >= WINDOW_SIZE) {
295 #ifdef USE_NEW_ALGORITHM
296 auto thrs = SmoothThresholds(BlockThresholds(_buffer));
297 return ThresholdImage(_buffer, thrs);
298 #else
299 const uint8_t* luminances = _buffer.data();
300 int subWidth = (width() + BLOCK_SIZE - 1) / BLOCK_SIZE; // ceil(width/BS)
301 int subHeight = (height() + BLOCK_SIZE - 1) / BLOCK_SIZE; // ceil(height/BS)
302 auto blackPoints =
303 CalculateBlackPoints(luminances, subWidth, subHeight, width(), height(), _buffer.rowStride());
304
305 return CalculateMatrix(luminances, subWidth, subHeight, width(), height(), _buffer.rowStride(), blackPoints);
306 #endif
307 } else {
308 // If the image is too small, fall back to the global histogram approach.
309 return GlobalHistogramBinarizer::getBlackMatrix();
310 }
311 }
312
313 } // ZXing