Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/zxing-cpp/core/src/ConcentricFinder.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 2020 Axel Waggershauser
3 */
4 // SPDX-License-Identifier: Apache-2.0
5
6 #include "ConcentricFinder.h"
7
8 #include "LogMatrix.h"
9 #include "RegressionLine.h"
10 #include "ZXAlgorithms.h"
11
12 namespace ZXing {
13
14 std::optional<PointF> AverageEdgePixels(BitMatrixCursorI cur, int range, int numOfEdges)
15 {
16 PointF sum = {};
17 for (int i = 0; i < numOfEdges; ++i) {
18 if (!cur.isIn())
19 return {};
20 cur.stepToEdge(1, range);
21 sum += centered(cur.p) + centered(cur.p + cur.back());
22 log(cur.p + cur.back(), 2);
23 }
24 return sum / (2 * numOfEdges);
25 }
26
27 std::optional<PointF> CenterOfDoubleCross(const BitMatrix& image, PointI center, int range, int numOfEdges)
28 {
29 PointF sum = {};
30 for (auto d : {PointI{0, 1}, {1, 0}, {1, 1}, {1, -1}}) {
31 auto avr1 = AverageEdgePixels({image, center, d}, range, numOfEdges);
32 auto avr2 = AverageEdgePixels({image, center, -d}, range, numOfEdges);
33 if (!avr1 || !avr2)
34 return {};
35 sum += *avr1 + *avr2;
36 }
37 return sum / 8;
38 }
39
40 std::optional<PointF> CenterOfRing(const BitMatrix& image, PointI center, int range, int nth, bool requireCircle)
41 {
42 #if 0
43 if (requireCircle) {
44 // alternative implementation with the aim of discarding closed loops that are not all circle like (M > 5*m)
45 auto points = CollectRingPoints(image, center, range, std::abs(nth), nth < 0);
46 if (points.empty())
47 return {};
48 auto res = Reduce(points, PointF{}, std::plus{}) / Size(points);
49
50 double m = range, M = 0;
51 for (auto p : points)
52 UpdateMinMax(m, M, maxAbsComponent(p - res));
53
54 if (M > 5 * m)
55 return {};
56
57 return res;
58 }
59 #endif
60 // range is the approximate width/height of the nth ring, if nth>1 then it would be plausible to limit the search radius
61 // to approximately range / 2 * sqrt(2) == range * 0.75 but it turned out to be too limiting with realworld/noisy data.
62 int radius = range;
63 bool inner = nth < 0;
64 nth = std::abs(nth);
65 log(center, 3);
66 BitMatrixCursorI cur(image, center, {0, 1});
67 if (!cur.stepToEdge(nth, radius, inner))
68 return {};
69 cur.turnRight(); // move clock wise and keep edge on the right/left depending on backup
70 const auto edgeDir = inner ? Direction::LEFT : Direction::RIGHT;
71
72 uint32_t neighbourMask = 0;
73 auto start = cur.p;
74 PointF sum = {};
75 int n = 0;
76 do {
77 log(cur.p, 4);
78 sum += centered(cur.p);
79 ++n;
80
81 // find out if we come full circle around the center. 8 bits have to be set in the end.
82 neighbourMask |= (1 << (4 + dot(bresenhamDirection(cur.p - center), PointI(1, 3))));
83
84 if (!cur.stepAlongEdge(edgeDir))
85 return {};
86
87 // use L-inf norm, simply because it is a lot faster than L2-norm and sufficiently accurate
88 if (maxAbsComponent(cur.p - center) > radius || center == cur.p || n > 4 * 2 * range)
89 return {};
90 } while (cur.p != start);
91
92 if (requireCircle && neighbourMask != 0b111101111)
93 return {};
94
95 return sum / n;
96 }
97
98 std::optional<PointF> CenterOfRings(const BitMatrix& image, PointF center, int range, int numOfRings)
99 {
100 int n = 1;
101 PointF sum = center;
102 for (int i = 2; i < numOfRings + 1; ++i) {
103 auto c = CenterOfRing(image, PointI(center), range, i);
104 if (!c) {
105 if (n == 1)
106 return {};
107 else
108 return sum / n;
109 } else if (distance(*c, center) > range / numOfRings / 2) {
110 return {};
111 }
112
113 sum += *c;
114 n++;
115 }
116 return sum / n;
117 }
118
119 static std::vector<PointF> CollectRingPoints(const BitMatrix& image, PointF center, int range, int edgeIndex, bool backup)
120 {
121 PointI centerI(center);
122 int radius = range;
123 BitMatrixCursorI cur(image, centerI, {0, 1});
124 if (!cur.stepToEdge(edgeIndex, radius, backup))
125 return {};
126 cur.turnRight(); // move clock wise and keep edge on the right/left depending on backup
127 const auto edgeDir = backup ? Direction::LEFT : Direction::RIGHT;
128
129 uint32_t neighbourMask = 0;
130 auto start = cur.p;
131 std::vector<PointF> points;
132 points.reserve(4 * range);
133
134 do {
135 log(cur.p, 4);
136 points.push_back(centered(cur.p));
137
138 // find out if we come full circle around the center. 8 bits have to be set in the end.
139 neighbourMask |= (1 << (4 + dot(bresenhamDirection(cur.p - centerI), PointI(1, 3))));
140
141 if (!cur.stepAlongEdge(edgeDir))
142 return {};
143
144 // use L-inf norm, simply because it is a lot faster than L2-norm and sufficiently accurate
145 if (maxAbsComponent(cur.p - centerI) > radius || centerI == cur.p || Size(points) > 4 * 2 * range)
146 return {};
147
148 } while (cur.p != start);
149
150 if (neighbourMask != 0b111101111)
151 return {};
152
153 return points;
154 }
155
156 static std::optional<QuadrilateralF> FitQadrilateralToPoints(PointF center, std::vector<PointF>& points)
157 {
158 auto dist2Center = [c = center](auto a, auto b) { return distance(a, c) < distance(b, c); };
159 // rotate points such that the first one is the furthest away from the center (hence, a corner)
160 std::rotate(points.begin(), std::max_element(points.begin(), points.end(), dist2Center), points.end());
161
162 std::array<const PointF*, 4> corners;
163 corners[0] = &points[0];
164 // find the oposite corner by looking for the farthest point near the oposite point
165 corners[2] = std::max_element(&points[Size(points) * 3 / 8], &points[Size(points) * 5 / 8], dist2Center);
166
167 // find the two in between corners by looking for the points farthest from the long diagonal
168 auto dist2Diagonal = [l = RegressionLine(*corners[0], *corners[2])](auto a, auto b) { return l.distance(a) < l.distance(b); };
169 corners[1] = std::max_element(&points[Size(points) * 1 / 8], &points[Size(points) * 3 / 8], dist2Diagonal);
170 corners[3] = std::max_element(&points[Size(points) * 5 / 8], &points[Size(points) * 7 / 8], dist2Diagonal);
171
172 std::array lines{RegressionLine{corners[0] + 1, corners[1]}, RegressionLine{corners[1] + 1, corners[2]},
173 RegressionLine{corners[2] + 1, corners[3]}, RegressionLine{corners[3] + 1, &points.back() + 1}};
174
175 if (std::any_of(lines.begin(), lines.end(), [](auto line) { return !line.isValid(); }))
176 return {};
177
178 std::array<const PointF*, 4> beg = {corners[0] + 1, corners[1] + 1, corners[2] + 1, corners[3] + 1};
179 std::array<const PointF*, 4> end = {corners[1], corners[2], corners[3], &points.back() + 1};
180
181 // check if all points belonging to each line segment are sufficiently close to that line
182 for (int i = 0; i < 4; ++i)
183 for (const PointF* p = beg[i]; p != end[i]; ++p) {
184 auto len = std::distance(beg[i], end[i]);
185 if (len > 3 && lines[i].distance(*p) > std::max(1., std::min(8., len / 8.))) {
186 #ifdef PRINT_DEBUG
187 printf("%d: %.2f > %.2f @ %.fx%.f\n", i, lines[i].distance(*p), std::distance(beg[i], end[i]) / 1., p->x, p->y);
188 #endif
189 return {};
190 }
191 }
192
193 QuadrilateralF res;
194 for (int i = 0; i < 4; ++i)
195 res[i] = intersect(lines[i], lines[(i + 1) % 4]);
196
197 return res;
198 }
199
200 static bool QuadrilateralIsPlausibleSquare(const QuadrilateralF q, int lineIndex)
201 {
202 double m, M;
203 m = M = distance(q[0], q[3]);
204 for (int i = 1; i < 4; ++i)
205 UpdateMinMax(m, M, distance(q[i - 1], q[i]));
206
207 return m >= lineIndex * 2 && m > M / 3;
208 }
209
210 static std::optional<QuadrilateralF> FitSquareToPoints(const BitMatrix& image, PointF center, int range, int lineIndex, bool backup)
211 {
212 auto points = CollectRingPoints(image, center, range, lineIndex, backup);
213 if (points.empty())
214 return {};
215
216 auto res = FitQadrilateralToPoints(center, points);
217 if (!res || !QuadrilateralIsPlausibleSquare(*res, lineIndex - backup))
218 return {};
219
220 return res;
221 }
222
223 std::optional<QuadrilateralF> FindConcentricPatternCorners(const BitMatrix& image, PointF center, int range, int lineIndex)
224 {
225 auto innerCorners = FitSquareToPoints(image, center, range, lineIndex, false);
226 if (!innerCorners)
227 return {};
228
229 auto outerCorners = FitSquareToPoints(image, center, range, lineIndex + 1, true);
230 if (!outerCorners)
231 return {};
232
233 auto res = Blend(*innerCorners, *outerCorners);
234
235 for (auto p : *innerCorners)
236 log(p, 3);
237
238 for (auto p : *outerCorners)
239 log(p, 3);
240
241 for (auto p : res)
242 log(p, 3);
243
244 return res;
245 }
246
247 std::optional<PointF> FinetuneConcentricPatternCenter(const BitMatrix& image, PointF center, int range, int finderPatternSize)
248 {
249 // make sure we have at least one path of white around the center
250 if (auto res1 = CenterOfRing(image, PointI(center), range, 1); res1 && image.get(*res1)) {
251 // and then either at least one more ring around that
252 if (auto res2 = CenterOfRings(image, *res1, range, finderPatternSize / 2); res2 && image.get(*res2))
253 return res2;
254 // or the center can be approximated by a square
255 if (FitSquareToPoints(image, *res1, range, 1, false))
256 return res1;
257 // TODO: this is currently only keeping #258 alive, evaluate if still worth it
258 if (auto res2 = CenterOfDoubleCross(image, PointI(*res1), range, finderPatternSize / 2 + 1); res2 && image.get(*res2))
259 return res2;
260 }
261 return {};
262 }
263
264 } // ZXing