Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/zxing-cpp/core/src/GlobalHistogramBinarizer.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 "GlobalHistogramBinarizer.h"
8
9 #include "BitMatrix.h"
10 #include "Pattern.h"
11 #include "ZXConfig.h"
12
13 #include <algorithm>
14 #include <array>
15 #include <utility>
16
17 namespace ZXing {
18
19 static constexpr int LUMINANCE_BITS = 5;
20 static constexpr int LUMINANCE_SHIFT = 8 - LUMINANCE_BITS;
21 static constexpr int LUMINANCE_BUCKETS = 1 << LUMINANCE_BITS;
22
23 using Histogram = std::array<uint16_t, LUMINANCE_BUCKETS>;
24
25 GlobalHistogramBinarizer::GlobalHistogramBinarizer(const ImageView& buffer) : BinaryBitmap(buffer) {}
26
27 GlobalHistogramBinarizer::~GlobalHistogramBinarizer() = default;
28
29 using ImageLineView = Range<StrideIter<const uint8_t*>>;
30
31 inline ImageLineView RowView(const ImageView& iv, int row)
32 {
33 return {{iv.data(0, row), iv.pixStride()}, {iv.data(iv.width(), row), iv.pixStride()}};
34 }
35
36 static void ThresholdSharpened(const ImageLineView in, int threshold, std::vector<uint8_t>& out)
37 {
38 out.resize(in.size());
39 auto i = in.begin();
40 auto o = out.begin();
41
42 *o++ = (*i++ <= threshold) * BitMatrix::SET_V;
43 for (auto end = in.end() - 1; i != end; ++i)
44 *o++ = ((-i[-1] + (int(i[0]) * 4) - i[1]) / 2 <= threshold) * BitMatrix::SET_V;
45 *o++ = (*i++ <= threshold) * BitMatrix::SET_V;
46 }
47
48 static auto GenHistogram(const ImageLineView line)
49 {
50 // This code causes about 20% of the total runtime on an AVX2 system for a EAN13 search on Lum input data.
51 // Trying to increase the performance by performing 2 or 4 "parallel" histograms helped nothing.
52 Histogram res = {};
53 for (auto pix : line)
54 res[pix >> LUMINANCE_SHIFT]++;
55 return res;
56 }
57
58 // Return -1 on error
59 static int EstimateBlackPoint(const Histogram& buckets)
60 {
61 // Find the tallest peak in the histogram.
62 auto firstPeakPos = std::max_element(buckets.begin(), buckets.end());
63 int firstPeak = narrow_cast<int>(firstPeakPos - buckets.begin());
64 int firstPeakSize = *firstPeakPos;
65 int maxBucketCount = firstPeakSize;
66
67 // Find the second-tallest peak which is somewhat far from the tallest peak.
68 int secondPeak = 0;
69 int secondPeakScore = 0;
70 for (int x = 0; x < Size(buckets); x++) {
71 int distanceToBiggest = x - firstPeak;
72 // Encourage more distant second peaks by multiplying by square of distance.
73 int score = buckets[x] * distanceToBiggest * distanceToBiggest;
74 if (score > secondPeakScore) {
75 secondPeak = x;
76 secondPeakScore = score;
77 }
78 }
79
80 // Make sure firstPeak corresponds to the black peak.
81 if (firstPeak > secondPeak) {
82 std::swap(firstPeak, secondPeak);
83 }
84
85 // If there is too little contrast in the image to pick a meaningful black point, throw rather
86 // than waste time trying to decode the image, and risk false positives.
87 if (secondPeak - firstPeak <= LUMINANCE_BUCKETS / 16) {
88 return -1;
89 }
90
91 // Find a valley between them that is low and closer to the white peak.
92 int bestValley = secondPeak - 1;
93 int bestValleyScore = -1;
94 for (int x = secondPeak - 1; x > firstPeak; x--) {
95 int fromFirst = x - firstPeak;
96 int score = fromFirst * fromFirst * (secondPeak - x) * (maxBucketCount - buckets[x]);
97 if (score > bestValleyScore) {
98 bestValley = x;
99 bestValleyScore = score;
100 }
101 }
102
103 return bestValley << LUMINANCE_SHIFT;
104 }
105
106 bool GlobalHistogramBinarizer::getPatternRow(int row, int rotation, PatternRow& res) const
107 {
108 auto buffer = _buffer.rotated(rotation);
109 auto lineView = RowView(buffer, row);
110
111 if (buffer.width() < 3)
112 return false; // special casing the code below for a width < 3 makes no sense
113
114 #if defined(__AVX__) // or defined(__ARM_NEON)
115 // If we are extracting a column (instead of a row), we run into cache misses on every pixel access both
116 // during the histogram calculation and during the sharpen+threshold operation. Additionally, if we
117 // perform the ThresholdSharpened function on pixStride==1 data, the auto-vectorizer makes that part
118 // 8x faster on an AVX2 cpu which easily recovers the extra cost that we pay for the copying.
119 ZX_THREAD_LOCAL std::vector<uint8_t> line;
120 if (std::abs(buffer.pixStride()) > 4) {
121 line.resize(lineView.size());
122 std::copy(lineView.begin(), lineView.end(), line.begin());
123 lineView = {{line.data(), 1}, {line.data() + line.size(), 1}};
124 }
125 #endif
126
127 auto threshold = EstimateBlackPoint(GenHistogram(lineView)) - 1;
128 if (threshold <= 0)
129 return false;
130
131 ZX_THREAD_LOCAL std::vector<uint8_t> binarized;
132 // the optimizer can generate a specialized version for pixStride==1 (non-rotated input) that is about 8x faster on AVX2 hardware
133 if (lineView.begin().stride == 1)
134 ThresholdSharpened(lineView, threshold, binarized);
135 else
136 ThresholdSharpened(lineView, threshold, binarized);
137 GetPatternRow(Range(binarized), res);
138
139 return true;
140 }
141
142 // Does not sharpen the data, as this call is intended to only be used by 2D Readers.
143 std::shared_ptr<const BitMatrix>
144 GlobalHistogramBinarizer::getBlackMatrix() const
145 {
146 // Quickly calculates the histogram by sampling four rows from the image. This proved to be
147 // more robust on the blackbox tests than sampling a diagonal as we used to do.
148 Histogram localBuckets = {};
149 {
150 for (int y = 1; y < 5; y++) {
151 int row = height() * y / 5;
152 const uint8_t* luminances = _buffer.data(0, row);
153 int right = (width() * 4) / 5;
154 for (int x = width() / 5; x < right; x++)
155 localBuckets[luminances[x] >> LUMINANCE_SHIFT]++;
156 }
157 }
158
159 int blackPoint = EstimateBlackPoint(localBuckets);
160 if (blackPoint <= 0)
161 return {};
162
163
164
165 return std::make_shared<const BitMatrix>(binarize(blackPoint));
166 }
167
168 } // ZXing