Line data Source code
1 : /*
2 : * liblierre - decoder_detect.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 FINDER_PATTERN_MODULES 5
17 : #define FINDER_PATTERN_CENTER_RATIO 3
18 : #define FINDER_PATTERN_SCALE_FACTOR 16
19 : #define FINDER_TOLERANCE_DIVISOR 4
20 : #define FINDER_TOLERANCE_MULTIPLIER 3
21 :
22 : #define CAPSTONE_AREA_RATIO_MIN 10
23 : #define CAPSTONE_AREA_RATIO_MAX 70
24 : #define CAPSTONE_AREA_RATIO_FACTOR 100
25 :
26 : #define FINDER_PATTERN_SIZE 7.0
27 : #define FINDER_PATTERN_CENTER 3.5
28 : #define NEIGHBOR_ALIGNMENT_THRESHOLD 0.2
29 :
30 : #define NUM_CORNERS 4
31 : #define NUM_EDGE_SAMPLES 2
32 :
33 2056113 : static inline void flood_fill_line(decoder_t *decoder, int32_t x, int32_t y, lierre_pixel_t source_color,
34 : lierre_pixel_t target_color, span_callback_t callback, void *user_data,
35 : int32_t *left_out, int32_t *right_out)
36 : {
37 : lierre_pixel_t *row;
38 : int32_t left, right, i;
39 :
40 2056113 : row = decoder->pixels + y * decoder->w;
41 2056113 : left = x;
42 2056113 : right = x;
43 :
44 3110332 : while (left > 0 && row[left - 1] == source_color) {
45 1054219 : left--;
46 : }
47 :
48 42670792 : while (right < decoder->w - 1 && row[right + 1] == source_color) {
49 40614679 : right++;
50 : }
51 :
52 45781124 : for (i = left; i <= right; i++) {
53 43725011 : row[i] = target_color;
54 : }
55 :
56 2056113 : *left_out = left;
57 2056113 : *right_out = right;
58 :
59 2056113 : if (callback) {
60 2055352 : callback(user_data, y, left, right);
61 : }
62 2056113 : }
63 :
64 7185022 : static inline flood_fill_vars_t *flood_fill_scan_next(decoder_t *decoder, lierre_pixel_t *row,
65 : lierre_pixel_t source_color, lierre_pixel_t target_color,
66 : span_callback_t callback, void *user_data,
67 : flood_fill_vars_t *current_state, int32_t direction)
68 : {
69 : int32_t *scan_position, next_left;
70 : flood_fill_vars_t *next_state;
71 :
72 7185022 : scan_position = (direction < 0) ? ¤t_state->left_up : ¤t_state->left_down;
73 :
74 93332955 : while (*scan_position <= current_state->right) {
75 88175152 : if (row[*scan_position] == source_color) {
76 2027219 : next_state = current_state + 1;
77 2027219 : next_state->y = current_state->y + direction;
78 :
79 2027219 : flood_fill_line(decoder, *scan_position, next_state->y, source_color, target_color, callback, user_data,
80 : &next_left, &next_state->right);
81 2027219 : next_state->left_down = next_left;
82 2027219 : next_state->left_up = next_left;
83 :
84 2027219 : return next_state;
85 : }
86 :
87 86147933 : (*scan_position)++;
88 : }
89 :
90 5157803 : return NULL;
91 : }
92 :
93 28894 : void flood_fill_seed(decoder_t *decoder, int32_t seed_x, int32_t seed_y, lierre_pixel_t source_color,
94 : lierre_pixel_t target_color, span_callback_t callback, void *user_data)
95 : {
96 : flood_fill_vars_t *stack, *next_state, *current_state, *stack_limit;
97 : lierre_pixel_t *row;
98 : int32_t next_left;
99 :
100 28894 : if (source_color == target_color || decoder->pixels[seed_y * decoder->w + seed_x] != source_color) {
101 0 : return;
102 : }
103 :
104 28894 : stack = decoder->flood_fill_vars;
105 28894 : stack_limit = &stack[decoder->num_flood_fill_vars - 1];
106 :
107 28894 : next_state = stack;
108 28894 : next_state->y = seed_y;
109 :
110 28894 : flood_fill_line(decoder, seed_x, next_state->y, source_color, target_color, callback, user_data, &next_left,
111 : &next_state->right);
112 28894 : next_state->left_down = next_left;
113 28894 : next_state->left_up = next_left;
114 :
115 : for (;;) {
116 3993985 : current_state = next_state;
117 :
118 3993985 : if (current_state == stack_limit) {
119 186 : break;
120 : }
121 :
122 3993799 : if (current_state->y > 0) {
123 3991800 : row = decoder->pixels + (current_state->y - 1) * decoder->w;
124 : next_state =
125 3991800 : flood_fill_scan_next(decoder, row, source_color, target_color, callback, user_data, current_state, -1);
126 3991800 : if (next_state) {
127 800550 : continue;
128 : }
129 : }
130 :
131 3193249 : if (current_state->y < decoder->h - 1) {
132 3193222 : row = decoder->pixels + (current_state->y + 1) * decoder->w;
133 : next_state =
134 3193222 : flood_fill_scan_next(decoder, row, source_color, target_color, callback, user_data, current_state, 1);
135 3193222 : if (next_state) {
136 1226669 : continue;
137 : }
138 : }
139 :
140 1966580 : if (current_state > stack) {
141 1937872 : next_state = current_state - 1;
142 1937872 : continue;
143 : }
144 :
145 28708 : break;
146 : }
147 : }
148 :
149 1949161 : static inline void region_area_callback(void *user_data, int32_t y, int32_t left, int32_t right)
150 : {
151 : (void)y;
152 :
153 : region_t *region;
154 :
155 1949161 : region = (region_t *)user_data;
156 1949161 : region->count += right - left + 1;
157 1949161 : }
158 :
159 907685 : int32_t get_or_create_region(decoder_t *decoder, int32_t x, int32_t y)
160 : {
161 : lierre_pixel_t pixel;
162 : region_t *region_data;
163 : int32_t region_id;
164 :
165 907685 : if (x < 0 || y < 0 || x >= decoder->w || y >= decoder->h) {
166 87780 : return -1;
167 : }
168 :
169 819905 : pixel = decoder->pixels[y * decoder->w + x];
170 :
171 819905 : if (pixel >= LIERRE_PIXEL_REGION) {
172 476148 : return (int32_t)pixel;
173 : }
174 :
175 343757 : if (pixel == LIERRE_PIXEL_WHITE) {
176 17831 : return -1;
177 : }
178 :
179 325926 : if (decoder->num_regions >= LIERRE_DECODER_MAX_REGIONS) {
180 297960 : return -1;
181 : }
182 :
183 27966 : region_id = decoder->num_regions;
184 27966 : region_data = &decoder->regions[decoder->num_regions++];
185 :
186 27966 : lmemset(region_data, 0, sizeof(*region_data));
187 27966 : region_data->seed.x = x;
188 27966 : region_data->seed.y = y;
189 27966 : region_data->capstone = -1;
190 :
191 27966 : flood_fill_seed(decoder, x, y, pixel, (lierre_pixel_t)region_id, region_area_callback, region_data);
192 :
193 27966 : return region_id;
194 : }
195 :
196 52715 : static inline void find_farthest_corner_callback(void *user_data, int32_t y, int32_t left, int32_t right)
197 : {
198 : corner_finder_data_t *finder;
199 : int32_t x_coords[2], delta_y, delta_x, distance_squared, i;
200 :
201 52715 : finder = (corner_finder_data_t *)user_data;
202 52715 : x_coords[0] = left;
203 52715 : x_coords[1] = right;
204 52715 : delta_y = y - finder->reference.y;
205 :
206 158145 : for (i = 0; i < 2; i++) {
207 105430 : delta_x = x_coords[i] - finder->reference.x;
208 105430 : distance_squared = delta_x * delta_x + delta_y * delta_y;
209 :
210 105430 : if (distance_squared > finder->scores[0]) {
211 9734 : finder->scores[0] = distance_squared;
212 9734 : finder->corners[0].x = x_coords[i];
213 9734 : finder->corners[0].y = y;
214 : }
215 : }
216 52715 : }
217 :
218 52715 : static inline void find_remaining_corners_callback(void *user_data, int32_t y, int32_t left, int32_t right)
219 : {
220 : corner_finder_data_t *finder;
221 : int32_t x_coords[2], up_score, right_score, scores[4], i, j;
222 :
223 52715 : finder = (corner_finder_data_t *)user_data;
224 52715 : x_coords[0] = left;
225 52715 : x_coords[1] = right;
226 :
227 158145 : for (i = 0; i < 2; i++) {
228 105430 : up_score = x_coords[i] * finder->reference.x + y * finder->reference.y;
229 105430 : right_score = x_coords[i] * -finder->reference.y + y * finder->reference.x;
230 105430 : scores[0] = up_score;
231 105430 : scores[1] = right_score;
232 105430 : scores[2] = -up_score;
233 105430 : scores[3] = -right_score;
234 :
235 527150 : for (j = 0; j < 4; j++) {
236 421720 : if (scores[j] > finder->scores[j]) {
237 35771 : finder->scores[j] = scores[j];
238 35771 : finder->corners[j].x = x_coords[i];
239 35771 : finder->corners[j].y = y;
240 : }
241 : }
242 : }
243 52715 : }
244 :
245 366 : void find_region_corners(decoder_t *decoder, int32_t region_id, const decoder_point_t *reference,
246 : decoder_point_t *corners)
247 : {
248 : region_t *region;
249 366 : corner_finder_data_t finder = {0};
250 : int32_t i;
251 :
252 366 : region = &decoder->regions[region_id];
253 :
254 366 : finder.corners = corners;
255 366 : finder.reference = *reference;
256 366 : finder.scores[0] = -1;
257 :
258 366 : flood_fill_seed(decoder, region->seed.x, region->seed.y, (lierre_pixel_t)region_id, LIERRE_PIXEL_BLACK,
259 : find_farthest_corner_callback, &finder);
260 :
261 366 : finder.reference.x = finder.corners[0].x - reference->x;
262 366 : finder.reference.y = finder.corners[0].y - reference->y;
263 :
264 1830 : for (i = 0; i < 4; i++) {
265 1464 : corners[i] = region->seed;
266 : }
267 :
268 366 : i = region->seed.x * finder.reference.x + region->seed.y * finder.reference.y;
269 366 : finder.scores[0] = i;
270 366 : finder.scores[2] = -i;
271 366 : i = region->seed.x * -finder.reference.y + region->seed.y * finder.reference.x;
272 366 : finder.scores[1] = i;
273 366 : finder.scores[3] = -i;
274 :
275 366 : flood_fill_seed(decoder, region->seed.x, region->seed.y, LIERRE_PIXEL_BLACK, (lierre_pixel_t)region_id,
276 : find_remaining_corners_callback, &finder);
277 366 : }
278 :
279 366 : static inline void record_capstone(decoder_t *decoder, int32_t ring_region_id, int32_t stone_region_id)
280 : {
281 : region_t *stone_region, *ring_region;
282 : capstone_t *capstone;
283 : int32_t capstone_index;
284 :
285 366 : if (decoder->num_capstones >= LIERRE_DECODER_MAX_CAPSTONES) {
286 0 : return;
287 : }
288 :
289 366 : stone_region = &decoder->regions[stone_region_id];
290 366 : ring_region = &decoder->regions[ring_region_id];
291 :
292 366 : capstone_index = decoder->num_capstones;
293 366 : capstone = &decoder->capstones[decoder->num_capstones++];
294 :
295 366 : lmemset(capstone, 0, sizeof(*capstone));
296 366 : capstone->qr_grid = -1;
297 366 : capstone->ring = ring_region_id;
298 366 : capstone->stone = stone_region_id;
299 366 : stone_region->capstone = capstone_index;
300 366 : ring_region->capstone = capstone_index;
301 :
302 366 : find_region_corners(decoder, ring_region_id, &stone_region->seed, capstone->corners);
303 366 : perspective_setup(capstone->c, capstone->corners, FINDER_PATTERN_SIZE, FINDER_PATTERN_SIZE);
304 366 : perspective_map(capstone->c, FINDER_PATTERN_CENTER, FINDER_PATTERN_CENTER, &capstone->center);
305 : }
306 :
307 262936 : static inline void test_capstone(decoder_t *decoder, uint32_t x, uint32_t y, uint32_t *pattern_widths)
308 : {
309 : region_t *stone_region_data, *ring_region_data;
310 : uint32_t area_ratio;
311 : int32_t ring_right_region, stone_region, ring_left_region;
312 :
313 262936 : ring_right_region = get_or_create_region(decoder, (int32_t)(x - pattern_widths[4]), (int32_t)y);
314 262936 : stone_region = get_or_create_region(
315 262936 : decoder, (int32_t)(x - pattern_widths[4] - pattern_widths[3] - pattern_widths[2]), (int32_t)y);
316 262936 : ring_left_region = get_or_create_region(decoder,
317 262936 : (int32_t)(x - pattern_widths[4] - pattern_widths[3] - pattern_widths[2] -
318 262936 : pattern_widths[1] - pattern_widths[0]),
319 : (int32_t)y);
320 :
321 262936 : if (ring_left_region < 0 || ring_right_region < 0 || stone_region < 0) {
322 100916 : return;
323 : }
324 :
325 162020 : if (ring_left_region != ring_right_region) {
326 129934 : return;
327 : }
328 :
329 32086 : if (ring_left_region == stone_region) {
330 24261 : return;
331 : }
332 :
333 7825 : stone_region_data = &decoder->regions[stone_region];
334 7825 : ring_region_data = &decoder->regions[ring_left_region];
335 :
336 7825 : if (stone_region_data->capstone >= 0 || ring_region_data->capstone >= 0) {
337 6728 : return;
338 : }
339 :
340 1097 : area_ratio = (stone_region_data->count * CAPSTONE_AREA_RATIO_FACTOR) / ring_region_data->count;
341 1097 : if (area_ratio < CAPSTONE_AREA_RATIO_MIN || area_ratio > CAPSTONE_AREA_RATIO_MAX) {
342 731 : return;
343 : }
344 :
345 366 : record_capstone(decoder, ring_left_region, stone_region);
346 : }
347 :
348 88941 : void scan_finder_patterns(decoder_t *decoder, uint32_t y)
349 : {
350 : lierre_pixel_t *row, current_color;
351 88941 : uint32_t x, previous_color, run_length, run_count, pattern_widths[5] = {0}, average_width, tolerance, i;
352 : int32_t is_valid, scale_factor;
353 :
354 88941 : row = decoder->pixels + y * decoder->w;
355 88941 : previous_color = 0;
356 88941 : run_length = 0;
357 88941 : run_count = 0;
358 :
359 123494522 : for (x = 0; x < (uint32_t)decoder->w; x++) {
360 123405581 : current_color = row[x] ? 1 : 0;
361 :
362 123405581 : if (x && current_color != previous_color) {
363 9867592 : lmemmove(pattern_widths, pattern_widths + 1, sizeof(pattern_widths[0]) * (FINDER_PATTERN_MODULES - 1));
364 9867592 : pattern_widths[FINDER_PATTERN_MODULES - 1] = run_length;
365 9867592 : run_length = 0;
366 9867592 : run_count++;
367 :
368 9867592 : if (!current_color && run_count >= FINDER_PATTERN_MODULES) {
369 4764371 : scale_factor = FINDER_PATTERN_SCALE_FACTOR;
370 4764371 : average_width = (pattern_widths[0] + pattern_widths[1] + pattern_widths[3] + pattern_widths[4]) *
371 : scale_factor / FINDER_TOLERANCE_DIVISOR;
372 4764371 : tolerance = average_width * FINDER_TOLERANCE_MULTIPLIER / FINDER_TOLERANCE_DIVISOR;
373 4764371 : is_valid = 1;
374 :
375 4764371 : if ((pattern_widths[0] * scale_factor < average_width - tolerance ||
376 4648805 : pattern_widths[0] * scale_factor > average_width + tolerance) ||
377 4111230 : (pattern_widths[1] * scale_factor < average_width - tolerance ||
378 4079128 : pattern_widths[1] * scale_factor > average_width + tolerance) ||
379 3627898 : (pattern_widths[2] * scale_factor < FINDER_PATTERN_CENTER_RATIO * average_width - tolerance ||
380 456435 : pattern_widths[2] * scale_factor > FINDER_PATTERN_CENTER_RATIO * average_width + tolerance) ||
381 315144 : (pattern_widths[3] * scale_factor < average_width - tolerance ||
382 314774 : pattern_widths[3] * scale_factor > average_width + tolerance) ||
383 299109 : (pattern_widths[4] * scale_factor < average_width - tolerance ||
384 299041 : pattern_widths[4] * scale_factor > average_width + tolerance)) {
385 4501435 : is_valid = 0;
386 : }
387 :
388 4764371 : if (is_valid) {
389 262936 : test_capstone(decoder, x, y, pattern_widths);
390 : }
391 : }
392 : }
393 :
394 123405581 : run_length++;
395 123405581 : previous_color = current_color;
396 : }
397 88941 : }
398 :
399 366 : void find_capstone_groups(decoder_t *decoder, int32_t capstone_index)
400 : {
401 : capstone_t *current_capstone, *other_capstone;
402 : capstone_neighbour_list_t horizontal_list, vertical_list;
403 : capstone_neighbour_t *neighbour;
404 : int32_t j;
405 : double grid_u, grid_v;
406 :
407 366 : current_capstone = &decoder->capstones[capstone_index];
408 366 : horizontal_list.count = 0;
409 366 : vertical_list.count = 0;
410 :
411 1732 : for (j = 0; j < decoder->num_capstones; j++) {
412 1366 : if (capstone_index == j) {
413 366 : continue;
414 : }
415 :
416 1000 : other_capstone = &decoder->capstones[j];
417 1000 : perspective_unmap(current_capstone->c, &other_capstone->center, &grid_u, &grid_v);
418 :
419 1000 : grid_u = fabs(grid_u - FINDER_PATTERN_CENTER);
420 1000 : grid_v = fabs(grid_v - FINDER_PATTERN_CENTER);
421 :
422 1000 : if (grid_u < NEIGHBOR_ALIGNMENT_THRESHOLD * grid_v) {
423 266 : neighbour = &horizontal_list.entries[horizontal_list.count++];
424 266 : neighbour->index = j;
425 266 : neighbour->distance = grid_v;
426 : }
427 :
428 1000 : if (grid_v < NEIGHBOR_ALIGNMENT_THRESHOLD * grid_u) {
429 269 : neighbour = &vertical_list.entries[vertical_list.count++];
430 269 : neighbour->index = j;
431 269 : neighbour->distance = grid_u;
432 : }
433 : }
434 :
435 366 : if (horizontal_list.count && vertical_list.count) {
436 122 : test_neighbour_pairs(decoder, capstone_index, &horizontal_list, &vertical_list);
437 : }
438 366 : }
|
