Line data Source code
1 : /*
2 : * liblierre - decoder_grid.c
3 : *
4 : * This file is part of liblierre.
5 : *
6 : * Author: Go Kudo <zeriyoshi@gmail.com>
7 : * SPDX-License-Identifier: MIT AND ISC
8 : *
9 : * This file contains code derived from quirc (https://github.com/dlbeer/quirc).
10 : * Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com>
11 : * Licensed under the ISC License.
12 : */
13 :
14 : #include "../internal/decoder.h"
15 :
16 : #define QR_VERSION_MIN 1
17 : #define QR_VERSION1_SIZE 17
18 : #define QR_VERSION_SIZE_INCREMENT 4
19 : #define QR_VERSION_ESTIMATION_OFFSET 15.0
20 : #define QR_VERSION2_MIN_SIZE 21
21 :
22 : #define FINDER_PATTERN_SIZE 7
23 : #define FINDER_PATTERN_CENTER 3
24 :
25 : #define TIMING_PATTERN_POSITION 6
26 : #define TIMING_PATTERN_OFFSET 7
27 : #define TIMING_PATTERN_MARGIN 14
28 :
29 : #define PERSPECTIVE_ADJUSTMENT_FACTOR 0.02
30 : #define PERSPECTIVE_STEP_DECAY 0.5
31 : #define PERSPECTIVE_REFINEMENT_PASSES 5
32 : #define PERSPECTIVE_PARAM_ITERATIONS 16
33 :
34 : #define CELL_SAMPLE_COUNT 3
35 : #define CELL_SAMPLE_OFFSET_1 0.3
36 : #define CELL_SAMPLE_OFFSET_2 0.5
37 : #define CELL_SAMPLE_OFFSET_3 0.7
38 : #define CELL_CENTER_OFFSET 0.5
39 :
40 : #define ROUNDING_OFFSET 0.5
41 : #define AVERAGE_FACTOR 0.5
42 : #define AVERAGE_DIVISOR 2.0
43 :
44 : #define ALIGNMENT_RING_RADIUS_1 1
45 : #define ALIGNMENT_RING_RADIUS_2 2
46 : #define ALIGNMENT_RING_RADIUS_3 3
47 :
48 : #define ALIGNMENT_SEARCH_AREA_FACTOR 100
49 : #define ALIGNMENT_SIZE_FACTOR_MIN 2
50 : #define ALIGNMENT_SIZE_FACTOR_MAX 2
51 : #define SPIRAL_DIRECTION_COUNT 4
52 :
53 : #define NUM_CORNERS 4
54 : #define NUM_CAPSTONES 3
55 :
56 : #define SQUARENESS_THRESHOLD 0.2
57 :
58 : const version_info_t lierre_version_db[LIERRE_DECODER_MAX_VERSION + 1] = {
59 : {0, {0}, {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}, {0, 0, 0}}},
60 : {26, {0}, {{26, 16, 1}, {26, 19, 1}, {26, 9, 1}, {26, 13, 1}}},
61 : {44, {6, 18, 0}, {{44, 28, 1}, {44, 34, 1}, {44, 16, 1}, {44, 22, 1}}},
62 : {70, {6, 22, 0}, {{70, 44, 1}, {70, 55, 1}, {35, 13, 2}, {35, 17, 2}}},
63 : {100, {6, 26, 0}, {{50, 32, 2}, {100, 80, 1}, {25, 9, 4}, {50, 24, 2}}},
64 : {134, {6, 30, 0}, {{67, 43, 2}, {134, 108, 1}, {33, 11, 2}, {33, 15, 2}}},
65 : {172, {6, 34, 0}, {{43, 27, 4}, {86, 68, 2}, {43, 15, 4}, {43, 19, 4}}},
66 : {196, {6, 22, 38, 0}, {{49, 31, 4}, {98, 78, 2}, {39, 13, 4}, {32, 14, 2}}},
67 : {242, {6, 24, 42, 0}, {{60, 38, 2}, {121, 97, 2}, {40, 14, 4}, {40, 18, 4}}},
68 : {292, {6, 26, 46, 0}, {{58, 36, 3}, {146, 116, 2}, {36, 12, 4}, {36, 16, 4}}},
69 : {346, {6, 28, 50, 0}, {{69, 43, 4}, {86, 68, 2}, {43, 15, 6}, {43, 19, 6}}},
70 : {404, {6, 30, 54, 0}, {{80, 50, 1}, {101, 81, 4}, {36, 12, 3}, {50, 22, 4}}},
71 : {466, {6, 32, 58, 0}, {{58, 36, 6}, {116, 92, 2}, {42, 14, 7}, {46, 20, 4}}},
72 : {532, {6, 34, 62, 0}, {{59, 37, 8}, {133, 107, 4}, {33, 11, 12}, {44, 20, 8}}},
73 : {581, {6, 26, 46, 66, 0}, {{64, 40, 4}, {145, 115, 3}, {36, 12, 11}, {36, 16, 11}}},
74 : {655, {6, 26, 48, 70, 0}, {{65, 41, 5}, {109, 87, 5}, {36, 12, 11}, {54, 24, 5}}},
75 : {733, {6, 26, 50, 74, 0}, {{73, 45, 7}, {122, 98, 5}, {45, 15, 3}, {43, 19, 15}}},
76 : {815, {6, 30, 54, 78, 0}, {{74, 46, 10}, {135, 107, 1}, {42, 14, 2}, {50, 22, 1}}},
77 : {901, {6, 30, 56, 82, 0}, {{69, 43, 9}, {150, 120, 5}, {42, 14, 2}, {50, 22, 17}}},
78 : {991, {6, 30, 58, 86, 0}, {{70, 44, 3}, {141, 113, 3}, {39, 13, 9}, {47, 21, 17}}},
79 : {1085, {6, 34, 62, 90, 0}, {{67, 41, 3}, {135, 107, 3}, {43, 15, 15}, {54, 24, 15}}},
80 : {1156, {6, 28, 50, 72, 94, 0}, {{68, 42, 17}, {144, 116, 4}, {46, 16, 19}, {50, 22, 17}}},
81 : {1258, {6, 26, 50, 74, 98, 0}, {{74, 46, 17}, {139, 111, 2}, {37, 13, 34}, {54, 24, 7}}},
82 : {1364, {6, 30, 54, 78, 102, 0}, {{75, 47, 4}, {151, 121, 4}, {45, 15, 16}, {54, 24, 11}}},
83 : {1474, {6, 28, 54, 80, 106, 0}, {{73, 45, 6}, {147, 117, 6}, {46, 16, 30}, {54, 24, 11}}},
84 : {1588, {6, 32, 58, 84, 110, 0}, {{75, 47, 8}, {132, 106, 8}, {45, 15, 22}, {54, 24, 7}}},
85 : {1706, {6, 30, 58, 86, 114, 0}, {{74, 46, 19}, {142, 114, 10}, {46, 16, 33}, {50, 22, 28}}},
86 : {1828, {6, 34, 62, 90, 118, 0}, {{73, 45, 22}, {152, 122, 8}, {45, 15, 12}, {53, 23, 8}}},
87 : {1921, {6, 26, 50, 74, 98, 122, 0}, {{73, 45, 3}, {147, 117, 3}, {45, 15, 11}, {54, 24, 4}}},
88 : {2051, {6, 30, 54, 78, 102, 126, 0}, {{73, 45, 21}, {146, 116, 7}, {45, 15, 19}, {53, 23, 1}}},
89 : {2185, {6, 26, 52, 78, 104, 130, 0}, {{75, 47, 19}, {145, 115, 5}, {45, 15, 23}, {54, 24, 15}}},
90 : {2323, {6, 30, 56, 82, 108, 134, 0}, {{74, 46, 2}, {145, 115, 13}, {45, 15, 23}, {54, 24, 42}}},
91 : {2465, {6, 34, 60, 86, 112, 138, 0}, {{74, 46, 10}, {145, 115, 17}, {45, 15, 19}, {54, 24, 10}}},
92 : {2611, {6, 30, 58, 86, 114, 142, 0}, {{74, 46, 14}, {145, 115, 17}, {45, 15, 11}, {54, 24, 29}}},
93 : {2761, {6, 34, 62, 90, 118, 146, 0}, {{74, 46, 14}, {145, 115, 13}, {46, 16, 59}, {54, 24, 44}}},
94 : {2876, {6, 30, 54, 78, 102, 126, 150, 0}, {{75, 47, 12}, {151, 121, 12}, {45, 15, 22}, {54, 24, 39}}},
95 : {3034, {6, 24, 50, 76, 102, 128, 154, 0}, {{75, 47, 6}, {151, 121, 6}, {45, 15, 2}, {54, 24, 46}}},
96 : {3196, {6, 28, 54, 80, 106, 132, 158, 0}, {{74, 46, 29}, {152, 122, 17}, {45, 15, 24}, {54, 24, 49}}},
97 : {3362, {6, 32, 58, 84, 110, 136, 162, 0}, {{74, 46, 13}, {152, 122, 4}, {45, 15, 42}, {54, 24, 48}}},
98 : {3532, {6, 26, 54, 82, 110, 138, 166, 0}, {{75, 47, 40}, {147, 117, 20}, {45, 15, 10}, {54, 24, 43}}},
99 : {3706, {6, 30, 58, 86, 114, 142, 170, 0}, {{75, 47, 18}, {148, 118, 19}, {45, 15, 20}, {54, 24, 34}}}};
100 :
101 59376704 : extern void perspective_map(const double *coeffs, double u, double v, decoder_point_t *result)
102 : {
103 : double denominator, x, y;
104 :
105 59376704 : denominator = 1.0 / (coeffs[6] * u + coeffs[7] * v + 1.0);
106 59376704 : x = (coeffs[0] * u + coeffs[1] * v + coeffs[2]) * denominator;
107 59376704 : y = (coeffs[3] * u + coeffs[4] * v + coeffs[5]) * denominator;
108 :
109 59376704 : result->x = (int32_t)(x + ROUNDING_OFFSET);
110 59376704 : result->y = (int32_t)(y + ROUNDING_OFFSET);
111 59376704 : }
112 :
113 882 : extern void perspective_setup(double *coeffs, const decoder_point_t *corners, double width, double height)
114 : {
115 : double x0, y0, x1, y1, x2, y2, x3, y3, width_denominator, height_denominator;
116 :
117 882 : x0 = corners[0].x;
118 882 : y0 = corners[0].y;
119 882 : x1 = corners[1].x;
120 882 : y1 = corners[1].y;
121 882 : x2 = corners[2].x;
122 882 : y2 = corners[2].y;
123 882 : x3 = corners[3].x;
124 882 : y3 = corners[3].y;
125 :
126 882 : width_denominator = 1.0 / (width * (x2 * y3 - x3 * y2 + (x3 - x2) * y1 + x1 * (y2 - y3)));
127 882 : height_denominator = 1.0 / (height * (x2 * y3 + x1 * (y2 - y3) - x3 * y2 + (x3 - x2) * y1));
128 :
129 882 : coeffs[0] = (x1 * (x2 * y3 - x3 * y2) + x0 * (-x2 * y3 + x3 * y2 + (x2 - x3) * y1) + x1 * (x3 - x2) * y0) *
130 : width_denominator;
131 882 : coeffs[1] = -(x0 * (x2 * y3 + x1 * (y2 - y3) - x2 * y1) - x1 * x3 * y2 + x2 * x3 * y1 + (x1 * x3 - x2 * x3) * y0) *
132 : height_denominator;
133 882 : coeffs[2] = x0;
134 882 : coeffs[3] = (y0 * (x1 * (y3 - y2) - x2 * y3 + x3 * y2) + y1 * (x2 * y3 - x3 * y2) + x0 * y1 * (y2 - y3)) *
135 : width_denominator;
136 882 : coeffs[4] = (x0 * (y1 * y3 - y2 * y3) + x1 * y2 * y3 - x2 * y1 * y3 + y0 * (x3 * y2 - x1 * y2 + (x2 - x3) * y1)) *
137 : height_denominator;
138 882 : coeffs[5] = y0;
139 882 : coeffs[6] = (x1 * (y3 - y2) + x0 * (y2 - y3) + (x2 - x3) * y1 + (x3 - x2) * y0) * width_denominator;
140 882 : coeffs[7] = (-x2 * y3 + x1 * y3 + x3 * y2 + x0 * (y1 - y2) - x3 * y1 + (x2 - x1) * y0) * height_denominator;
141 882 : }
142 :
143 1216 : extern void perspective_unmap(const double *coeffs, const decoder_point_t *image_point, double *grid_u, double *grid_v)
144 : {
145 : double x, y, denominator;
146 :
147 1216 : x = (double)image_point->x;
148 1216 : y = (double)image_point->y;
149 1216 : denominator =
150 1216 : 1.0 / (-coeffs[0] * coeffs[7] * y + coeffs[1] * coeffs[6] * y +
151 1216 : (coeffs[3] * coeffs[7] - coeffs[4] * coeffs[6]) * x + coeffs[0] * coeffs[4] - coeffs[1] * coeffs[3]);
152 :
153 1216 : *grid_u = -(coeffs[1] * (y - coeffs[5]) - coeffs[2] * coeffs[7] * y + (coeffs[5] * coeffs[7] - coeffs[4]) * x +
154 1216 : coeffs[2] * coeffs[4]) *
155 : denominator;
156 1216 : *grid_v = (coeffs[0] * (y - coeffs[5]) - coeffs[2] * coeffs[6] * y + (coeffs[5] * coeffs[6] - coeffs[3]) * x +
157 1216 : coeffs[2] * coeffs[3]) *
158 : denominator;
159 1216 : }
160 :
161 129 : static inline int32_t compute_line_intersection(const decoder_point_t *line1_start, const decoder_point_t *line1_end,
162 : const decoder_point_t *line2_start, const decoder_point_t *line2_end,
163 : decoder_point_t *intersection)
164 : {
165 : int32_t a, b, c, d, e, f, determinant;
166 :
167 129 : a = -(line1_end->y - line1_start->y);
168 129 : b = line1_end->x - line1_start->x;
169 129 : c = -(line2_end->y - line2_start->y);
170 129 : d = line2_end->x - line2_start->x;
171 129 : e = a * line1_end->x + b * line1_end->y;
172 129 : f = c * line2_end->x + d * line2_end->y;
173 :
174 129 : determinant = a * d - b * c;
175 129 : if (!determinant) {
176 0 : return 0;
177 : }
178 :
179 129 : intersection->x = (d * e - b * f) / determinant;
180 129 : intersection->y = (-c * e + a * f) / determinant;
181 :
182 129 : return 1;
183 : }
184 :
185 774 : static inline double compute_point_distance(const decoder_point_t *point_a, const decoder_point_t *point_b)
186 : {
187 : double delta_x, delta_y;
188 :
189 774 : delta_x = (double)abs(point_a->x - point_b->x) + 1.0;
190 774 : delta_y = (double)abs(point_a->y - point_b->y) + 1.0;
191 :
192 774 : return sqrt(delta_x * delta_x + delta_y * delta_y);
193 : }
194 :
195 129 : static inline void estimate_grid_size(decoder_t *decoder, int32_t grid_index)
196 : {
197 : grid_t *grid;
198 : capstone_t *cap_a, *cap_b, *cap_c;
199 : int32_t version;
200 : double distance_ab, distance_bc, capstone_ab_size, capstone_bc_size, vertical_modules, horizontal_modules,
201 : average_modules;
202 :
203 129 : grid = &decoder->grids[grid_index];
204 129 : cap_a = &decoder->capstones[grid->caps[0]];
205 129 : cap_b = &decoder->capstones[grid->caps[1]];
206 129 : cap_c = &decoder->capstones[grid->caps[2]];
207 :
208 129 : distance_ab = compute_point_distance(&cap_b->corners[0], &cap_a->corners[3]);
209 129 : capstone_ab_size = (compute_point_distance(&cap_b->corners[0], &cap_b->corners[3]) +
210 129 : compute_point_distance(&cap_a->corners[0], &cap_a->corners[3])) /
211 : AVERAGE_DIVISOR;
212 129 : vertical_modules = (double)FINDER_PATTERN_SIZE * distance_ab / capstone_ab_size;
213 :
214 129 : distance_bc = compute_point_distance(&cap_b->corners[0], &cap_c->corners[1]);
215 129 : capstone_bc_size = (compute_point_distance(&cap_b->corners[0], &cap_b->corners[1]) +
216 129 : compute_point_distance(&cap_c->corners[0], &cap_c->corners[1])) /
217 : AVERAGE_DIVISOR;
218 129 : horizontal_modules = (double)FINDER_PATTERN_SIZE * distance_bc / capstone_bc_size;
219 :
220 129 : average_modules = (vertical_modules + horizontal_modules) * AVERAGE_FACTOR;
221 129 : version = (int32_t)((average_modules - QR_VERSION_ESTIMATION_OFFSET) / (double)QR_VERSION_SIZE_INCREMENT);
222 :
223 129 : if (version < QR_VERSION_MIN) {
224 0 : version = QR_VERSION_MIN;
225 : }
226 :
227 129 : if (version > LIERRE_DECODER_MAX_VERSION) {
228 0 : version = LIERRE_DECODER_MAX_VERSION;
229 : }
230 :
231 129 : grid->grid_size = QR_VERSION_SIZE_INCREMENT * version + QR_VERSION1_SIZE;
232 129 : }
233 :
234 1063285 : static inline int32_t read_grid_cell(const decoder_t *decoder, int32_t grid_index, int32_t x, int32_t y)
235 : {
236 : const grid_t *grid;
237 : decoder_point_t image_point;
238 :
239 1063285 : grid = &decoder->grids[grid_index];
240 1063285 : perspective_map(grid->c, (double)x + CELL_CENTER_OFFSET, (double)y + CELL_CENTER_OFFSET, &image_point);
241 :
242 1061469 : if (image_point.y < 0 || image_point.y >= decoder->h || image_point.x < 0 || image_point.x >= decoder->w) {
243 0 : return 0;
244 : }
245 :
246 1064425 : return decoder->pixels[image_point.y * decoder->w + image_point.x] ? 1 : -1;
247 : }
248 :
249 6479352 : static inline int32_t compute_cell_fitness(const decoder_t *decoder, int32_t grid_index, int32_t x, int32_t y)
250 : {
251 : static const double sample_offsets[CELL_SAMPLE_COUNT] = {CELL_SAMPLE_OFFSET_1, CELL_SAMPLE_OFFSET_2,
252 : CELL_SAMPLE_OFFSET_3};
253 : const grid_t *grid;
254 : decoder_point_t image_point;
255 : int32_t score, sample_x, sample_y;
256 :
257 6479352 : grid = &decoder->grids[grid_index];
258 6479352 : score = 0;
259 :
260 25917408 : for (sample_y = 0; sample_y < CELL_SAMPLE_COUNT; sample_y++) {
261 77752224 : for (sample_x = 0; sample_x < CELL_SAMPLE_COUNT; sample_x++) {
262 58314168 : perspective_map(grid->c, (double)x + sample_offsets[sample_x], (double)y + sample_offsets[sample_y],
263 : &image_point);
264 :
265 58314168 : if (image_point.y < 0 || image_point.y >= decoder->h || image_point.x < 0 || image_point.x >= decoder->w) {
266 117277 : continue;
267 : }
268 :
269 58196891 : if (decoder->pixels[image_point.y * decoder->w + image_point.x]) {
270 36087148 : score++;
271 : } else {
272 22109743 : score--;
273 : }
274 : }
275 : }
276 :
277 6479352 : return score;
278 : }
279 :
280 384183 : static inline int32_t compute_ring_fitness(const decoder_t *decoder, int32_t grid_index, int32_t center_x,
281 : int32_t center_y, int32_t radius)
282 : {
283 : int32_t i, score;
284 :
285 384183 : score = 0;
286 :
287 1630773 : for (i = 0; i < radius * 2; i++) {
288 1246590 : score += compute_cell_fitness(decoder, grid_index, center_x - radius + i, center_y - radius);
289 1246590 : score += compute_cell_fitness(decoder, grid_index, center_x - radius, center_y + radius - i);
290 1246590 : score += compute_cell_fitness(decoder, grid_index, center_x + radius, center_y - radius + i);
291 1246590 : score += compute_cell_fitness(decoder, grid_index, center_x + radius - i, center_y + radius);
292 : }
293 :
294 384183 : return score;
295 : }
296 :
297 145071 : static inline int32_t compute_alignment_pattern_fitness(const decoder_t *decoder, int32_t grid_index, int32_t center_x,
298 : int32_t center_y)
299 : {
300 145071 : return compute_cell_fitness(decoder, grid_index, center_x, center_y) -
301 290142 : compute_ring_fitness(decoder, grid_index, center_x, center_y, ALIGNMENT_RING_RADIUS_1) +
302 145071 : compute_ring_fitness(decoder, grid_index, center_x, center_y, ALIGNMENT_RING_RADIUS_2);
303 : }
304 :
305 31347 : static inline int32_t compute_capstone_fitness(const decoder_t *decoder, int32_t grid_index, int32_t x, int32_t y)
306 : {
307 31347 : x += FINDER_PATTERN_CENTER;
308 31347 : y += FINDER_PATTERN_CENTER;
309 :
310 31347 : return compute_cell_fitness(decoder, grid_index, x, y) +
311 31347 : compute_ring_fitness(decoder, grid_index, x, y, ALIGNMENT_RING_RADIUS_1) -
312 62694 : compute_ring_fitness(decoder, grid_index, x, y, ALIGNMENT_RING_RADIUS_2) +
313 31347 : compute_ring_fitness(decoder, grid_index, x, y, ALIGNMENT_RING_RADIUS_3);
314 : }
315 :
316 10449 : static inline int32_t compute_total_grid_fitness(const decoder_t *decoder, int32_t grid_index)
317 : {
318 : const grid_t *grid;
319 : const version_info_t *version_info;
320 : int32_t version, score, i, j, alignment_count, expected_value;
321 :
322 10449 : grid = &decoder->grids[grid_index];
323 10449 : version = (grid->grid_size - QR_VERSION1_SIZE) / QR_VERSION_SIZE_INCREMENT;
324 :
325 10449 : if (version < QR_VERSION_MIN || version > LIERRE_DECODER_MAX_VERSION) {
326 0 : return 0;
327 : }
328 :
329 10449 : version_info = &lierre_version_db[version];
330 10449 : score = 0;
331 :
332 668736 : for (i = 0; i < grid->grid_size - TIMING_PATTERN_MARGIN; i++) {
333 658287 : expected_value = (i & 1) ? 1 : -1;
334 658287 : score += compute_cell_fitness(decoder, grid_index, i + TIMING_PATTERN_OFFSET, TIMING_PATTERN_POSITION) *
335 : expected_value;
336 658287 : score += compute_cell_fitness(decoder, grid_index, TIMING_PATTERN_POSITION, i + TIMING_PATTERN_OFFSET) *
337 : expected_value;
338 : }
339 :
340 10449 : score += compute_capstone_fitness(decoder, grid_index, 0, 0);
341 10449 : score += compute_capstone_fitness(decoder, grid_index, grid->grid_size - FINDER_PATTERN_SIZE, 0);
342 10449 : score += compute_capstone_fitness(decoder, grid_index, 0, grid->grid_size - FINDER_PATTERN_SIZE);
343 :
344 10449 : alignment_count = 0;
345 46008 : while (alignment_count < LIERRE_DECODER_MAX_ALIGNMENT && version_info->apat[alignment_count]) {
346 35559 : alignment_count++;
347 : }
348 :
349 28512 : for (i = 1; i + 1 < alignment_count; i++) {
350 18063 : score += compute_alignment_pattern_fitness(decoder, grid_index, TIMING_PATTERN_POSITION, version_info->apat[i]);
351 18063 : score += compute_alignment_pattern_fitness(decoder, grid_index, version_info->apat[i], TIMING_PATTERN_POSITION);
352 : }
353 :
354 37260 : for (i = 1; i < alignment_count; i++) {
355 135756 : for (j = 1; j < alignment_count; j++) {
356 108945 : score +=
357 108945 : compute_alignment_pattern_fitness(decoder, grid_index, version_info->apat[i], version_info->apat[j]);
358 : }
359 : }
360 :
361 10449 : return score;
362 : }
363 :
364 129 : static inline void refine_perspective(decoder_t *decoder, int32_t grid_index)
365 : {
366 : grid_t *grid;
367 : int32_t best_fitness, pass, i, j, test_fitness;
368 : double adjustment_steps[LIERRE_DECODER_PERSPECTIVE_PARAMS], original_value, step, new_value;
369 :
370 129 : grid = &decoder->grids[grid_index];
371 129 : best_fitness = compute_total_grid_fitness(decoder, grid_index);
372 :
373 1161 : for (i = 0; i < LIERRE_DECODER_PERSPECTIVE_PARAMS; i++) {
374 1032 : adjustment_steps[i] = grid->c[i] * PERSPECTIVE_ADJUSTMENT_FACTOR;
375 : }
376 :
377 774 : for (pass = 0; pass < PERSPECTIVE_REFINEMENT_PASSES; pass++) {
378 10965 : for (i = 0; i < PERSPECTIVE_PARAM_ITERATIONS; i++) {
379 10320 : j = i >> 1;
380 10320 : original_value = grid->c[j];
381 10320 : step = adjustment_steps[j];
382 10320 : new_value = (i & 1) ? original_value + step : original_value - step;
383 :
384 10320 : grid->c[j] = new_value;
385 10320 : test_fitness = compute_total_grid_fitness(decoder, grid_index);
386 :
387 10320 : if (test_fitness > best_fitness) {
388 226 : best_fitness = test_fitness;
389 : } else {
390 10094 : grid->c[j] = original_value;
391 : }
392 : }
393 :
394 5805 : for (i = 0; i < LIERRE_DECODER_PERSPECTIVE_PARAMS; i++) {
395 5160 : adjustment_steps[i] *= PERSPECTIVE_STEP_DECAY;
396 : }
397 : }
398 129 : }
399 :
400 761 : static inline void find_leftmost_point_callback(void *user_data, int32_t y, int32_t left, int32_t right)
401 : {
402 : corner_finder_data_t *finder;
403 : int32_t x_coords[2], i, distance;
404 :
405 761 : finder = (corner_finder_data_t *)user_data;
406 761 : x_coords[0] = left;
407 761 : x_coords[1] = right;
408 :
409 2283 : for (i = 0; i < 2; i++) {
410 1522 : distance = -finder->reference.y * x_coords[i] + finder->reference.x * y;
411 1522 : if (distance < finder->scores[0]) {
412 14 : finder->scores[0] = distance;
413 14 : finder->corners[0].x = x_coords[i];
414 14 : finder->corners[0].y = y;
415 : }
416 : }
417 761 : }
418 :
419 108 : static inline void search_alignment_pattern(decoder_t *decoder, int32_t grid_index)
420 : {
421 : static const int32_t direction_dx[SPIRAL_DIRECTION_COUNT] = {1, 0, -1, 0},
422 : direction_dy[SPIRAL_DIRECTION_COUNT] = {0, -1, 0, 1};
423 : grid_t *grid;
424 : capstone_t *capstone_a, *capstone_c;
425 : decoder_point_t point_a, search_point, point_c;
426 : region_t *region;
427 : int32_t expected_size, step_size, direction, i, region_id;
428 : double u, v;
429 :
430 108 : grid = &decoder->grids[grid_index];
431 108 : capstone_a = &decoder->capstones[grid->caps[0]];
432 108 : capstone_c = &decoder->capstones[grid->caps[2]];
433 :
434 108 : search_point = grid->align;
435 :
436 108 : perspective_unmap(capstone_a->c, &search_point, &u, &v);
437 108 : perspective_map(capstone_a->c, u, v + 1.0, &point_a);
438 108 : perspective_unmap(capstone_c->c, &search_point, &u, &v);
439 108 : perspective_map(capstone_c->c, u + 1.0, v, &point_c);
440 :
441 108 : expected_size = abs((point_a.x - search_point.x) * -(point_c.y - search_point.y) +
442 108 : (point_a.y - search_point.y) * (point_c.x - search_point.x));
443 :
444 108 : step_size = 1;
445 108 : direction = 0;
446 :
447 2220 : while (step_size * step_size < expected_size * ALIGNMENT_SEARCH_AREA_FACTOR) {
448 120989 : for (i = 0; i < step_size; i++) {
449 118877 : region_id = get_or_create_region(decoder, search_point.x, search_point.y);
450 :
451 118877 : if (region_id >= 0) {
452 13266 : region = &decoder->regions[region_id];
453 13266 : if (region->count >= expected_size / ALIGNMENT_SIZE_FACTOR_MIN &&
454 12218 : region->count <= expected_size * ALIGNMENT_SIZE_FACTOR_MAX) {
455 98 : grid->align_region = region_id;
456 98 : return;
457 : }
458 : }
459 :
460 118779 : search_point.x += direction_dx[direction];
461 118779 : search_point.y += direction_dy[direction];
462 : }
463 :
464 2112 : direction = (direction + 1) % SPIRAL_DIRECTION_COUNT;
465 2112 : if (!(direction & 1)) {
466 1052 : step_size++;
467 : }
468 : }
469 : }
470 :
471 129 : static inline void setup_grid_perspective(decoder_t *decoder, int32_t grid_index)
472 : {
473 : grid_t *grid;
474 : decoder_point_t corner_points[4];
475 :
476 129 : grid = &decoder->grids[grid_index];
477 :
478 129 : corner_points[0] = decoder->capstones[grid->caps[1]].corners[0];
479 129 : corner_points[1] = decoder->capstones[grid->caps[2]].corners[0];
480 129 : corner_points[2] = grid->align;
481 129 : corner_points[3] = decoder->capstones[grid->caps[0]].corners[0];
482 :
483 129 : perspective_setup(grid->c, corner_points, (double)(grid->grid_size - FINDER_PATTERN_SIZE),
484 129 : (double)(grid->grid_size - FINDER_PATTERN_SIZE));
485 129 : refine_perspective(decoder, grid_index);
486 129 : }
487 :
488 387 : static inline void rotate_capstone_corners(capstone_t *capstone, const decoder_point_t *origin,
489 : const decoder_point_t *direction)
490 : {
491 : decoder_point_t rotated_corners[NUM_CORNERS], *corner;
492 : int32_t j, best_index, score, best_score;
493 :
494 387 : best_index = 0;
495 387 : best_score = INT32_MAX;
496 :
497 1935 : for (j = 0; j < NUM_CORNERS; j++) {
498 1548 : corner = &capstone->corners[j];
499 1548 : score = (corner->x - origin->x) * -direction->y + (corner->y - origin->y) * direction->x;
500 :
501 1548 : if (score < best_score) {
502 1071 : best_index = j;
503 1071 : best_score = score;
504 : }
505 : }
506 :
507 1935 : for (j = 0; j < NUM_CORNERS; j++) {
508 1548 : rotated_corners[j] = capstone->corners[(j + best_index) % NUM_CORNERS];
509 : }
510 :
511 387 : lmemcpy(capstone->corners, rotated_corners, sizeof(capstone->corners));
512 387 : perspective_setup(capstone->c, capstone->corners, (double)FINDER_PATTERN_SIZE, (double)FINDER_PATTERN_SIZE);
513 387 : }
514 :
515 129 : static inline void create_qr_grid(decoder_t *decoder, int32_t cap_a, int32_t cap_b, int32_t cap_c)
516 : {
517 : decoder_point_t origin, direction;
518 : grid_t *grid;
519 : capstone_t *capstone;
520 : region_t *region;
521 : corner_finder_data_t finder;
522 : int32_t i, grid_index, temp;
523 :
524 129 : if (decoder->num_grids >= LIERRE_DECODER_MAX_GRIDS) {
525 0 : return;
526 : }
527 :
528 129 : origin = decoder->capstones[cap_a].center;
529 129 : direction.x = decoder->capstones[cap_c].center.x - decoder->capstones[cap_a].center.x;
530 129 : direction.y = decoder->capstones[cap_c].center.y - decoder->capstones[cap_a].center.y;
531 :
532 129 : if ((decoder->capstones[cap_b].center.x - origin.x) * -direction.y +
533 129 : (decoder->capstones[cap_b].center.y - origin.y) * direction.x >
534 : 0) {
535 13 : temp = cap_a;
536 13 : cap_a = cap_c;
537 13 : cap_c = temp;
538 13 : direction.x = -direction.x;
539 13 : direction.y = -direction.y;
540 : }
541 :
542 129 : grid_index = decoder->num_grids;
543 129 : grid = &decoder->grids[decoder->num_grids++];
544 :
545 129 : lmemset(grid, 0, sizeof(*grid));
546 129 : grid->caps[0] = cap_a;
547 129 : grid->caps[1] = cap_b;
548 129 : grid->caps[2] = cap_c;
549 129 : grid->align_region = -1;
550 :
551 516 : for (i = 0; i < NUM_CAPSTONES; i++) {
552 387 : capstone = &decoder->capstones[grid->caps[i]];
553 387 : rotate_capstone_corners(capstone, &origin, &direction);
554 387 : capstone->qr_grid = grid_index;
555 : }
556 :
557 129 : estimate_grid_size(decoder, grid_index);
558 :
559 129 : if (!compute_line_intersection(&decoder->capstones[cap_a].corners[0], &decoder->capstones[cap_a].corners[1],
560 129 : &decoder->capstones[cap_c].corners[0], &decoder->capstones[cap_c].corners[3],
561 : &grid->align)) {
562 0 : for (i = 0; i < NUM_CAPSTONES; i++) {
563 0 : decoder->capstones[grid->caps[i]].qr_grid = -1;
564 : }
565 :
566 0 : decoder->num_grids--;
567 :
568 0 : return;
569 : }
570 :
571 129 : if (grid->grid_size > QR_VERSION2_MIN_SIZE) {
572 108 : search_alignment_pattern(decoder, grid_index);
573 :
574 108 : if (grid->align_region >= 0) {
575 98 : region = &decoder->regions[grid->align_region];
576 98 : grid->align = region->seed;
577 :
578 98 : lmemset(&finder, 0, sizeof(finder));
579 98 : finder.reference = direction;
580 98 : finder.corners = &grid->align;
581 98 : finder.scores[0] = -direction.y * grid->align.x + direction.x * grid->align.y;
582 :
583 98 : flood_fill_seed(decoder, region->seed.x, region->seed.y, (lierre_pixel_t)grid->align_region,
584 : LIERRE_PIXEL_BLACK, NULL, NULL);
585 98 : flood_fill_seed(decoder, region->seed.x, region->seed.y, LIERRE_PIXEL_BLACK,
586 98 : (lierre_pixel_t)grid->align_region, find_leftmost_point_callback, &finder);
587 : }
588 : }
589 :
590 129 : setup_grid_perspective(decoder, grid_index);
591 : }
592 :
593 129 : void extract_qr_code(const decoder_t *decoder, int32_t grid_index, qr_code_t *code)
594 : {
595 : const grid_t *grid;
596 : int32_t row, col, bit_index;
597 :
598 129 : lmemset(code, 0, sizeof(*code));
599 :
600 129 : if (grid_index < 0 || grid_index >= decoder->num_grids) {
601 1 : return;
602 : }
603 :
604 128 : grid = &decoder->grids[grid_index];
605 :
606 128 : perspective_map(grid->c, 0.0, 0.0, &code->corners[0]);
607 129 : perspective_map(grid->c, (double)grid->grid_size, 0.0, &code->corners[1]);
608 128 : perspective_map(grid->c, (double)grid->grid_size, (double)grid->grid_size, &code->corners[2]);
609 129 : perspective_map(grid->c, 0.0, (double)grid->grid_size, &code->corners[3]);
610 :
611 129 : code->size = grid->grid_size;
612 :
613 129 : if (code->size > LIERRE_DECODER_MAX_GRID_SIZE) {
614 0 : return;
615 : }
616 :
617 129 : bit_index = 0;
618 5642 : for (row = 0; row < grid->grid_size; row++) {
619 1073886 : for (col = 0; col < grid->grid_size; col++) {
620 1068373 : if (read_grid_cell(decoder, grid_index, col, row) > 0) {
621 540784 : code->cell_bitmap[bit_index >> 3] |= (1 << (bit_index & 7));
622 : }
623 1063954 : bit_index++;
624 : }
625 : }
626 : }
627 :
628 122 : extern void test_neighbour_pairs(decoder_t *decoder, int32_t capstone_index,
629 : const capstone_neighbour_list_t *horizontal_list,
630 : const capstone_neighbour_list_t *vertical_list)
631 : {
632 : const capstone_neighbour_t *horizontal_neighbour, *vertical_neighbour;
633 : int32_t j, k;
634 : double squareness;
635 :
636 266 : for (j = 0; j < horizontal_list->count; j++) {
637 144 : horizontal_neighbour = &horizontal_list->entries[j];
638 329 : for (k = 0; k < vertical_list->count; k++) {
639 185 : vertical_neighbour = &vertical_list->entries[k];
640 185 : squareness = fabs(1.0 - horizontal_neighbour->distance / vertical_neighbour->distance);
641 :
642 185 : if (squareness < SQUARENESS_THRESHOLD) {
643 129 : create_qr_grid(decoder, horizontal_neighbour->index, capstone_index, vertical_neighbour->index);
644 : }
645 : }
646 : }
647 122 : }
|
