Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/leptonica/src/readbarcode.c @ 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 (C) 2001 Leptonica. All rights reserved.
3 -
4 - Redistribution and use in source and binary forms, with or without
5 - modification, are permitted provided that the following conditions
6 - are met:
7 - 1. Redistributions of source code must retain the above copyright
8 - notice, this list of conditions and the following disclaimer.
9 - 2. Redistributions in binary form must reproduce the above
10 - copyright notice, this list of conditions and the following
11 - disclaimer in the documentation and/or other materials
12 - provided with the distribution.
13 -
14 - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15 - ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16 - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17 - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANY
18 - CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19 - EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20 - PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21 - PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22 - OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
23 - NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24 - SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 *====================================================================*/
26
27
28 /*!
29 * \file readbarcode.c
30 * <pre>
31 *
32 * Basic operations to locate and identify the line widths
33 * in 1D barcodes.
34 *
35 * Top level
36 * SARRAY *pixProcessBarcodes()
37 *
38 * Next levels
39 * PIXA *pixExtractBarcodes()
40 * SARRAY *pixReadBarcodes()
41 * l_int32 pixReadBarcodeWidths()
42 *
43 * Location
44 * BOXA *pixLocateBarcodes()
45 * static PIX *pixGenerateBarcodeMask()
46 *
47 * Extraction and deskew
48 * PIXA *pixDeskewBarcodes()
49 *
50 * Process to get line widths
51 * NUMA *pixExtractBarcodeWidths1()
52 * NUMA *pixExtractBarcodeWidths2()
53 * NUMA *pixExtractBarcodeCrossings()
54 *
55 * Average adjacent rasters
56 * static NUMA *pixAverageRasterScans()
57 *
58 * Signal processing for barcode widths
59 * NUMA *numaQuantizeCrossingsByWidth()
60 * static l_int32 numaGetCrossingDistances()
61 * static NUMA *numaLocatePeakRanges()
62 * static NUMA *numaGetPeakCentroids()
63 * static NUMA *numaGetPeakWidthLUT()
64 * NUMA *numaQuantizeCrossingsByWindow()
65 * static l_int32 numaEvalBestWidthAndShift()
66 * static l_int32 numaEvalSyncError()
67 *
68 *
69 * NOTE CAREFULLY: This is "early beta" code. It has not been tuned
70 * to work robustly on a large database of barcode images. I'm putting
71 * it out so that people can play with it, find out how it breaks, and
72 * contribute decoders for other barcode formats. Both the functional
73 * interfaces and ABI will almost certainly change in the coming
74 * few months. The actual decoder, in bardecode.c, at present only
75 * works on the following codes: Code I2of5, Code 2of5, Code 39, Code 93
76 * Codabar and UPCA. To add another barcode format, it is necessary
77 * to make changes in readbarcode.h and bardecode.c.
78 * The program prog/barcodetest shows how to run from the top level
79 * (image --> decoded data).
80 * </pre>
81 */
82
83 #ifdef HAVE_CONFIG_H
84 #include <config_auto.h>
85 #endif /* HAVE_CONFIG_H */
86
87 #include <string.h>
88 #include "allheaders.h"
89 #include "readbarcode.h"
90
91 /* Parameters for pixGenerateBarcodeMask() */
92 static const l_int32 MAX_SPACE_WIDTH = 19; /* was 15 */
93 static const l_int32 MAX_NOISE_WIDTH = 50; /* smaller than barcode width */
94 static const l_int32 MAX_NOISE_HEIGHT = 30; /* smaller than barcode height */
95
96 /* Minimum barcode image size */
97 static const l_int32 MIN_BC_WIDTH = 50;
98 static const l_int32 MIN_BC_HEIGHT = 50;
99
100 /* Static functions */
101 static PIX *pixGenerateBarcodeMask(PIX *pixs, l_int32 maxspace,
102 l_int32 nwidth, l_int32 nheight);
103 static NUMA *pixAverageRasterScans(PIX *pixs, l_int32 nscans);
104 static l_int32 numaGetCrossingDistances(NUMA *nas, NUMA **pnaedist,
105 NUMA **pnaodist, l_float32 *pmindist,
106 l_float32 *pmaxdist);
107 static NUMA *numaLocatePeakRanges(NUMA *nas, l_float32 minfirst,
108 l_float32 minsep, l_float32 maxmin);
109 static NUMA *numaGetPeakCentroids(NUMA *nahist, NUMA *narange);
110 static NUMA *numaGetPeakWidthLUT(NUMA *narange, NUMA *nacent);
111 static l_int32 numaEvalBestWidthAndShift(NUMA *nas, l_int32 nwidth,
112 l_int32 nshift, l_float32 minwidth,
113 l_float32 maxwidth,
114 l_float32 *pbestwidth,
115 l_float32 *pbestshift,
116 l_float32 *pbestscore);
117 static l_int32 numaEvalSyncError(NUMA *nas, l_int32 ifirst, l_int32 ilast,
118 l_float32 width, l_float32 shift,
119 l_float32 *pscore, NUMA **pnad);
120
121
122 #ifndef NO_CONSOLE_IO
123 #define DEBUG_DESKEW 0
124 #define DEBUG_WIDTHS 0
125 #endif /* ~NO_CONSOLE_IO */
126
127
128 /*------------------------------------------------------------------------*
129 * Top level *
130 *------------------------------------------------------------------------*/
131 /*!
132 * \brief pixProcessBarcodes()
133 *
134 * \param[in] pixs any depth
135 * \param[in] format L_BF_ANY, L_BF_CODEI2OF5, L_BF_CODE93, ...
136 * \param[in] method L_USE_WIDTHS, L_USE_WINDOWS
137 * \param[out] psaw [optional] sarray of bar widths
138 * \param[in] debugflag use 1 to generate debug output
139 * \return sarray text of barcodes, or NULL if none found or on error
140 */
141 SARRAY *
142 pixProcessBarcodes(PIX *pixs,
143 l_int32 format,
144 l_int32 method,
145 SARRAY **psaw,
146 l_int32 debugflag)
147 {
148 PIX *pixg;
149 PIXA *pixa;
150 SARRAY *sad;
151
152 if (psaw) *psaw = NULL;
153 if (!pixs)
154 return (SARRAY *)ERROR_PTR("pixs not defined", __func__, NULL);
155 if (format != L_BF_ANY && !barcodeFormatIsSupported(format))
156 return (SARRAY *)ERROR_PTR("unsupported format", __func__, NULL);
157 if (method != L_USE_WIDTHS && method != L_USE_WINDOWS)
158 return (SARRAY *)ERROR_PTR("invalid method", __func__, NULL);
159
160 /* Get an 8 bpp image, no cmap */
161 if (pixGetDepth(pixs) == 8 && !pixGetColormap(pixs))
162 pixg = pixClone(pixs);
163 else
164 pixg = pixConvertTo8(pixs, 0);
165
166 pixa = pixExtractBarcodes(pixg, debugflag);
167 pixDestroy(&pixg);
168 if (!pixa)
169 return (SARRAY *)ERROR_PTR("no barcode(s) found", __func__, NULL);
170
171 sad = pixReadBarcodes(pixa, format, method, psaw, debugflag);
172 pixaDestroy(&pixa);
173 return sad;
174 }
175
176
177 /*!
178 * \brief pixExtractBarcodes()
179 *
180 * \param[in] pixs 8 bpp, no colormap
181 * \param[in] debugflag use 1 to generate debug output
182 * \return pixa deskewed and cropped barcodes, or NULL if none found
183 * or on error
184 */
185 PIXA *
186 pixExtractBarcodes(PIX *pixs,
187 l_int32 debugflag)
188 {
189 l_int32 i, n;
190 l_float32 angle, conf;
191 BOX *box;
192 BOXA *boxa;
193 PIX *pix1, *pix2, *pix3;
194 PIXA *pixa;
195
196 if (!pixs || pixGetDepth(pixs) != 8 || pixGetColormap(pixs))
197 return (PIXA *)ERROR_PTR("pixs undefined or not 8 bpp", __func__, NULL);
198
199 /* Locate them; use small threshold for edges. */
200 boxa = pixLocateBarcodes(pixs, 20, &pix2, &pix1);
201 n = boxaGetCount(boxa);
202 L_INFO("%d possible barcode(s) found\n", __func__, n);
203 if (n == 0) {
204 boxaDestroy(&boxa);
205 pixDestroy(&pix2);
206 pixDestroy(&pix1);
207 return NULL;
208 }
209
210 if (debugflag) {
211 boxaWriteStderr(boxa);
212 pixDisplay(pix2, 100, 100);
213 pixDisplay(pix1, 800, 100);
214 }
215 pixDestroy(&pix1);
216
217 /* Deskew each barcode individually */
218 pixa = pixaCreate(n);
219 for (i = 0; i < n; i++) {
220 box = boxaGetBox(boxa, i, L_CLONE);
221 pix3 = pixDeskewBarcode(pixs, pix2, box, 15, 20, &angle, &conf);
222 if (!pix3) conf = 0.0; /* don't use */
223 L_INFO("angle = %6.2f, conf = %6.2f\n", __func__, angle, conf);
224 if (conf > 5.0) {
225 pixaAddPix(pixa, pix3, L_INSERT);
226 pixaAddBox(pixa, box, L_INSERT);
227 } else {
228 pixDestroy(&pix3);
229 boxDestroy(&box);
230 }
231 }
232 pixDestroy(&pix2);
233 boxaDestroy(&boxa);
234
235 #if DEBUG_DESKEW
236 pix3 = pixaDisplayTiledInRows(pixa, 8, 1000, 1.0, 0, 30, 2);
237 pixWrite("/tmp/lept/pix3.png", pix3, IFF_PNG);
238 pixDestroy(&pix3);
239 #endif /* DEBUG_DESKEW */
240
241 return pixa;
242 }
243
244
245 /*!
246 * \brief pixReadBarcodes()
247 *
248 * \param[in] pixa of 8 bpp deskewed and cropped barcodes
249 * \param[in] format L_BF_ANY, L_BF_CODEI2OF5, L_BF_CODE93, ...
250 * \param[in] method L_USE_WIDTHS, L_USE_WINDOWS;
251 * \param[out] psaw [optional] sarray of bar widths
252 * \param[in] debugflag use 1 to generate debug output
253 * \return sa sarray of widths, one string for each barcode found,
254 * or NULL on error
255 */
256 SARRAY *
257 pixReadBarcodes(PIXA *pixa,
258 l_int32 format,
259 l_int32 method,
260 SARRAY **psaw,
261 l_int32 debugflag)
262 {
263 char *barstr, *data;
264 char emptystring[] = "";
265 l_int32 w, h, i, j, n, nbars, ival;
266 NUMA *na;
267 PIX *pix1;
268 SARRAY *saw, *sad;
269
270 if (psaw) *psaw = NULL;
271 if (!pixa)
272 return (SARRAY *)ERROR_PTR("pixa not defined", __func__, NULL);
273 if (format != L_BF_ANY && !barcodeFormatIsSupported(format))
274 return (SARRAY *)ERROR_PTR("unsupported format", __func__, NULL);
275 if (method != L_USE_WIDTHS && method != L_USE_WINDOWS)
276 return (SARRAY *)ERROR_PTR("invalid method", __func__, NULL);
277
278 n = pixaGetCount(pixa);
279 saw = sarrayCreate(n);
280 sad = sarrayCreate(n);
281 for (i = 0; i < n; i++) {
282 /* Extract the widths of the lines in each barcode */
283 pix1 = pixaGetPix(pixa, i, L_CLONE);
284 pixGetDimensions(pix1, &w, &h, NULL);
285 if (w < MIN_BC_WIDTH || h < MIN_BC_HEIGHT) {
286 L_ERROR("pix is too small: w = %d, h = %d\n", __func__, w, h);
287 pixDestroy(&pix1);
288 continue;
289 }
290 na = pixReadBarcodeWidths(pix1, method, debugflag);
291 pixDestroy(&pix1);
292 if (!na) {
293 ERROR_INT("valid barcode widths not returned", __func__, 1);
294 continue;
295 }
296
297 /* Save the widths as a string */
298 nbars = numaGetCount(na);
299 barstr = (char *)LEPT_CALLOC(nbars + 1, sizeof(char));
300 for (j = 0; j < nbars; j++) {
301 numaGetIValue(na, j, &ival);
302 barstr[j] = 0x30 + ival;
303 }
304 sarrayAddString(saw, barstr, L_INSERT);
305 numaDestroy(&na);
306
307 /* Decode the width strings */
308 data = barcodeDispatchDecoder(barstr, format, debugflag);
309 if (!data) {
310 ERROR_INT("barcode not decoded", __func__, 1);
311 sarrayAddString(sad, emptystring, L_COPY);
312 continue;
313 }
314 sarrayAddString(sad, data, L_INSERT);
315 }
316
317 /* If nothing found, clean up */
318 if (sarrayGetCount(saw) == 0) {
319 sarrayDestroy(&saw);
320 sarrayDestroy(&sad);
321 return (SARRAY *)ERROR_PTR("no valid barcode data", __func__, NULL);
322 }
323
324 if (psaw)
325 *psaw = saw;
326 else
327 sarrayDestroy(&saw);
328 return sad;
329 }
330
331
332 /*!
333 * \brief pixReadBarcodeWidths()
334 *
335 * \param[in] pixs of 8 bpp deskewed and cropped barcode
336 * \param[in] method L_USE_WIDTHS, L_USE_WINDOWS;
337 * \param[in] debugflag use 1 to generate debug output
338 * \return na numa of widths (each in set {1,2,3,4}, or NULL on error
339 */
340 NUMA *
341 pixReadBarcodeWidths(PIX *pixs,
342 l_int32 method,
343 l_int32 debugflag)
344 {
345 l_float32 winwidth;
346 NUMA *na;
347
348 if (!pixs)
349 return (NUMA *)ERROR_PTR("pixs not defined", __func__, NULL);
350 if (pixGetDepth(pixs) != 8)
351 return (NUMA *)ERROR_PTR("pixs not 8 bpp", __func__, NULL);
352 if (method != L_USE_WIDTHS && method != L_USE_WINDOWS)
353 return (NUMA *)ERROR_PTR("invalid method", __func__, NULL);
354
355 /* Extract the widths of the lines in each barcode */
356 if (method == L_USE_WIDTHS)
357 na = pixExtractBarcodeWidths1(pixs, 120, 0.25, NULL, NULL,
358 debugflag);
359 else /* method == L_USE_WINDOWS */
360 na = pixExtractBarcodeWidths2(pixs, 120, &winwidth,
361 NULL, debugflag);
362 #if DEBUG_WIDTHS
363 if (method == L_USE_WINDOWS)
364 lept_stderr("Window width for barcode: %7.3f\n", winwidth);
365 numaWriteStderr(na);
366 #endif /* DEBUG_WIDTHS */
367
368 if (!na)
369 return (NUMA *)ERROR_PTR("barcode widths invalid", __func__, NULL);
370
371 return na;
372 }
373
374
375 /*------------------------------------------------------------------------*
376 * Locate barcode in image *
377 *------------------------------------------------------------------------*/
378 /*!
379 * \brief pixLocateBarcodes()
380 *
381 * \param[in] pixs any depth
382 * \param[in] thresh for binarization of edge filter output; typ. 20
383 * \param[out] ppixb [optional] binarized edge filtered input image
384 * \param[out] ppixm [optional] mask over barcodes
385 * \return boxa location of barcodes, or NULL if none found or on error
386 */
387 BOXA *
388 pixLocateBarcodes(PIX *pixs,
389 l_int32 thresh,
390 PIX **ppixb,
391 PIX **ppixm)
392 {
393 BOXA *boxa;
394 PIX *pix8, *pixe, *pixb, *pixm;
395
396 if (!pixs)
397 return (BOXA *)ERROR_PTR("pixs not defined", __func__, NULL);
398
399 /* Get an 8 bpp image, no cmap */
400 if (pixGetDepth(pixs) == 8 && !pixGetColormap(pixs))
401 pix8 = pixClone(pixs);
402 else
403 pix8 = pixConvertTo8(pixs, 0);
404
405 /* Get a 1 bpp image of the edges */
406 pixe = pixSobelEdgeFilter(pix8, L_ALL_EDGES);
407 pixb = pixThresholdToBinary(pixe, thresh);
408 pixInvert(pixb, pixb);
409 pixDestroy(&pix8);
410 pixDestroy(&pixe);
411
412 pixm = pixGenerateBarcodeMask(pixb, MAX_SPACE_WIDTH, MAX_NOISE_WIDTH,
413 MAX_NOISE_HEIGHT);
414 boxa = pixConnComp(pixm, NULL, 8);
415
416 if (ppixb)
417 *ppixb = pixb;
418 else
419 pixDestroy(&pixb);
420 if (ppixm)
421 *ppixm = pixm;
422 else
423 pixDestroy(&pixm);
424
425 return boxa;
426 }
427
428
429 /*!
430 * \brief pixGenerateBarcodeMask()
431 *
432 * \param[in] pixs 1 bpp
433 * \param[in] maxspace largest space in the barcode, in pixels
434 * \param[in] nwidth opening 'width' to remove noise
435 * \param[in] nheight opening 'height' to remove noise
436 * \return pixm mask over barcodes, or NULL if none found or on error
437 *
438 * <pre>
439 * Notes:
440 * (1) For noise removal, 'width' and 'height' are referred to the
441 * barcode orientation.
442 * (2) If there is skew, the mask will not cover the barcode corners.
443 * </pre>
444 */
445 static PIX *
446 pixGenerateBarcodeMask(PIX *pixs,
447 l_int32 maxspace,
448 l_int32 nwidth,
449 l_int32 nheight)
450 {
451 PIX *pixt1, *pixt2, *pixd;
452
453 if (!pixs || pixGetDepth(pixs) != 1)
454 return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
455
456 /* Identify horizontal barcodes */
457 pixt1 = pixCloseBrick(NULL, pixs, maxspace + 1, 1);
458 pixt2 = pixOpenBrick(NULL, pixs, maxspace + 1, 1);
459 pixXor(pixt2, pixt2, pixt1);
460 pixOpenBrick(pixt2, pixt2, nwidth, nheight);
461 pixDestroy(&pixt1);
462
463 /* Identify vertical barcodes */
464 pixt1 = pixCloseBrick(NULL, pixs, 1, maxspace + 1);
465 pixd = pixOpenBrick(NULL, pixs, 1, maxspace + 1);
466 pixXor(pixd, pixd, pixt1);
467 pixOpenBrick(pixd, pixd, nheight, nwidth);
468 pixDestroy(&pixt1);
469
470 /* Combine to get all barcodes */
471 pixOr(pixd, pixd, pixt2);
472 pixDestroy(&pixt2);
473
474 return pixd;
475 }
476
477
478 /*------------------------------------------------------------------------*
479 * Extract and deskew barcode *
480 *------------------------------------------------------------------------*/
481 /*!
482 * \brief pixDeskewBarcode()
483 *
484 * \param[in] pixs input image; 8 bpp
485 * \param[in] pixb binarized edge-filtered input image
486 * \param[in] box identified region containing barcode
487 * \param[in] margin of extra pixels around box to extract
488 * \param[in] threshold for binarization; ~20
489 * \param[out] pangle [optional] in degrees, clockwise is positive
490 * \param[out] pconf [optional] confidence
491 * \return pixd deskewed barcode, or NULL on error
492 *
493 * <pre>
494 * Notes:
495 * (1) The (optional) angle returned is the angle in degrees (cw positive)
496 * necessary to rotate the image so that it is deskewed.
497 * </pre>
498 */
499 PIX *
500 pixDeskewBarcode(PIX *pixs,
501 PIX *pixb,
502 BOX *box,
503 l_int32 margin,
504 l_int32 threshold,
505 l_float32 *pangle,
506 l_float32 *pconf)
507 {
508 l_int32 x, y, w, h, n;
509 l_float32 angle, angle1, angle2, conf, conf1, conf2, score1, score2, deg2rad;
510 BOX *box1, *box2;
511 BOXA *boxa1, *boxa2;
512 PIX *pix1, *pix2, *pix3, *pix4, *pix5, *pix6, *pixd;
513
514 if (pangle) *pangle = 0.0;
515 if (pconf) *pconf = 0.0;
516 if (!pixs || pixGetDepth(pixs) != 8)
517 return (PIX *)ERROR_PTR("pixs undefined or not 8 bpp", __func__, NULL);
518 if (!pixb || pixGetDepth(pixb) != 1)
519 return (PIX *)ERROR_PTR("pixb undefined or not 1 bpp", __func__, NULL);
520 if (!box)
521 return (PIX *)ERROR_PTR("box not defined or 1 bpp", __func__, NULL);
522
523 /* Clip out */
524 deg2rad = 3.1415926535f / 180.f;
525 boxGetGeometry(box, &x, &y, &w, &h);
526 box2 = boxCreate(x - 25, y - 25, w + 51, h + 51);
527 pix1 = pixClipRectangle(pixb, box2, NULL);
528 pix2 = pixClipRectangle(pixs, box2, NULL);
529 boxDestroy(&box2);
530
531 /* Deskew, looking at all possible orientations over 180 degrees */
532 pix3 = pixRotateOrth(pix1, 1); /* look for vertical bar lines */
533 pix4 = pixClone(pix1); /* look for horizontal bar lines */
534 pixFindSkewSweepAndSearchScore(pix3, &angle1, &conf1, &score1,
535 1, 1, 0.0f, 45.0f, 2.5f, 0.01f);
536 pixFindSkewSweepAndSearchScore(pix4, &angle2, &conf2, &score2,
537 1, 1, 0.0f, 45.0f, 2.5f, 0.01f);
538 pixDestroy(&pix1);
539 pixDestroy(&pix3);
540 pixDestroy(&pix4);
541
542 /* Because we're using the boundary pixels of the barcodes,
543 * the peak can be sharper (and the confidence ratio higher)
544 * from the signal across the top and bottom of the barcode.
545 * However, the max score, which is the magnitude of the signal
546 * at the optimum skew angle, will be smaller, so we use the
547 * max score as the primary indicator of orientation. */
548 if (score1 >= score2) {
549 conf = conf1;
550 if (conf1 > 6.0 && L_ABS(angle1) > 0.1) {
551 angle = angle1;
552 pix5 = pixRotate(pix2, deg2rad * angle1, L_ROTATE_AREA_MAP,
553 L_BRING_IN_WHITE, 0, 0);
554 } else {
555 angle = 0.0;
556 pix5 = pixClone(pix2);
557 }
558 } else { /* score2 > score1 */
559 conf = conf2;
560 pix6 = pixRotateOrth(pix2, 1);
561 if (conf2 > 6.0 && L_ABS(angle2) > 0.1) {
562 angle = 90.0 + angle2;
563 pix5 = pixRotate(pix6, deg2rad * angle2, L_ROTATE_AREA_MAP,
564 L_BRING_IN_WHITE, 0, 0);
565 } else {
566 angle = 90.0;
567 pix5 = pixClone(pix6);
568 }
569 pixDestroy(&pix6);
570 }
571 pixDestroy(&pix2);
572
573 /* Extract barcode plus a margin around it */
574 boxa1 = pixLocateBarcodes(pix5, threshold, 0, 0);
575 if ((n = boxaGetCount(boxa1)) != 1) {
576 L_WARNING("barcode mask in %d components\n", __func__, n);
577 boxa2 = boxaSort(boxa1, L_SORT_BY_AREA, L_SORT_DECREASING, NULL);
578 } else {
579 boxa2 = boxaCopy(boxa1, L_CLONE);
580 }
581 box1 = boxaGetBox(boxa2, 0, L_CLONE);
582 boxGetGeometry(box1, &x, &y, &w, &h);
583 box2 = boxCreate(x - margin, y - margin, w + 2 * margin,
584 h + 2 * margin);
585 pixd = pixClipRectangle(pix5, box2, NULL);
586 boxDestroy(&box1);
587 boxDestroy(&box2);
588 boxaDestroy(&boxa1);
589 boxaDestroy(&boxa2);
590 pixDestroy(&pix5);
591
592 if (pangle) *pangle = angle;
593 if (pconf) *pconf = conf;
594
595 if (!pixd)
596 L_ERROR("pixd not made\n", __func__);
597 return pixd;
598 }
599
600
601 /*------------------------------------------------------------------------*
602 * Process to get line widths *
603 *------------------------------------------------------------------------*/
604 /*!
605 * \brief pixExtractBarcodeWidths1()
606 *
607 * \param[in] pixs input image; 8 bpp
608 * \param[in] thresh estimated pixel threshold for crossing
609 * white <--> black; typ. ~120
610 * \param[in] binfract histo binsize as a fraction of minsize; e.g., 0.25
611 * \param[out] pnaehist [optional] histogram of black widths; NULL ok
612 * \param[out] pnaohist [optional] histogram of white widths; NULL ok
613 * \param[in] debugflag use 1 to generate debug output
614 * \return nad numa of barcode widths in encoded integer units,
615 * or NULL on error
616 *
617 * <pre>
618 * Notes:
619 * (1) The widths are alternating black/white, starting with black
620 * and ending with black.
621 * (2) This method uses the widths of the bars directly, in terms
622 * of the (float) number of pixels between transitions.
623 * The histograms of these widths for black and white bars is
624 * generated and interpreted.
625 * </pre>
626 */
627 NUMA *
628 pixExtractBarcodeWidths1(PIX *pixs,
629 l_float32 thresh,
630 l_float32 binfract,
631 NUMA **pnaehist,
632 NUMA **pnaohist,
633 l_int32 debugflag)
634 {
635 NUMA *nac, *nad;
636
637 if (pnaehist) *pnaehist = NULL;
638 if (pnaohist) *pnaohist = NULL;
639 if (!pixs || pixGetDepth(pixs) != 8)
640 return (NUMA *)ERROR_PTR("pixs undefined or not 8 bpp", __func__, NULL);
641
642 /* Get the best estimate of the crossings, in pixel units */
643 if ((nac = pixExtractBarcodeCrossings(pixs, thresh, debugflag)) == NULL)
644 return (NUMA *)ERROR_PTR("nac not made", __func__, NULL);
645
646 /* Get the array of bar widths, starting with a black bar */
647 nad = numaQuantizeCrossingsByWidth(nac, binfract, pnaehist,
648 pnaohist, debugflag);
649
650 numaDestroy(&nac);
651 return nad;
652 }
653
654
655 /*!
656 * \brief pixExtractBarcodeWidths2()
657 *
658 * \param[in] pixs input image; 8 bpp
659 * \param[in] thresh estimated pixel threshold for crossing
660 * white <--> black; typ. ~120
661 * \param[out] pwidth [optional] best decoding window width, in pixels
662 * \param[out] pnac [optional] number of transitions in each window
663 * \param[in] debugflag use 1 to generate debug output
664 * \return nad numa of barcode widths in encoded integer units,
665 * or NULL on error
666 *
667 * <pre>
668 * Notes:
669 * (1) The widths are alternating black/white, starting with black
670 * and ending with black.
671 * (2) The optional best decoding window width is the width of the window
672 * that is used to make a decision about whether a transition occurs.
673 * It is approximately the average width in pixels of the narrowest
674 * white and black bars (i.e., those corresponding to unit width).
675 * (3) The optional return signal %nac is a sequence of 0s, 1s,
676 * and perhaps a few 2s, giving the number of crossings in each window.
677 * On the occasion where there is a '2', it is interpreted as
678 * as ending two runs: the previous one and another one that has length 1.
679 * </pre>
680 */
681 NUMA *
682 pixExtractBarcodeWidths2(PIX *pixs,
683 l_float32 thresh,
684 l_float32 *pwidth,
685 NUMA **pnac,
686 l_int32 debugflag)
687 {
688 NUMA *nacp, *nad;
689
690 if (pwidth) *pwidth = 0;
691 if (pnac) *pnac = NULL;
692 if (!pixs || pixGetDepth(pixs) != 8)
693 return (NUMA *)ERROR_PTR("pixs undefined or not 8 bpp", __func__, NULL);
694
695 /* Get the best estimate of the crossings, in pixel units */
696 if ((nacp = pixExtractBarcodeCrossings(pixs, thresh, debugflag)) == NULL)
697 return (NUMA *)ERROR_PTR("nacp not made", __func__, NULL);
698
699 /* Quantize the crossings to get actual windowed data */
700 nad = numaQuantizeCrossingsByWindow(nacp, 2.0, pwidth, NULL,
701 pnac, debugflag);
702 numaDestroy(&nacp);
703 return nad;
704 }
705
706
707 /*!
708 * \brief pixExtractBarcodeCrossings()
709 *
710 * \param[in] pixs input image; 8 bpp
711 * \param[in] thresh estimated pixel threshold for crossing
712 * white <--> black; typ. ~120
713 * \param[in] debugflag use 1 to generate debug output
714 * \return numa of crossings, in pixel units, or NULL on error
715 *
716 * <pre>
717 * Notes:
718 * (1) Require at least 10 crossings.
719 * </pre>
720 */
721 NUMA *
722 pixExtractBarcodeCrossings(PIX *pixs,
723 l_float32 thresh,
724 l_int32 debugflag)
725 {
726 l_int32 w;
727 l_float32 bestthresh;
728 GPLOT *gplot;
729 NUMA *nas, *nax, *nay, *nad;
730
731 if (!pixs || pixGetDepth(pixs) != 8)
732 return (NUMA *)ERROR_PTR("pixs undefined or not 8 bpp", __func__, NULL);
733
734 /* Scan pixels horizontally and average results */
735 if ((nas = pixAverageRasterScans(pixs, 50)) == NULL)
736 return (NUMA *)ERROR_PTR("nas not made", __func__, NULL);
737
738 /* Interpolate to get 4x the number of values */
739 w = pixGetWidth(pixs);
740 numaInterpolateEqxInterval(0.0, 1.0, nas, L_QUADRATIC_INTERP, 0.0,
741 (l_float32)(w - 1), 4 * w + 1, &nax, &nay);
742
743 if (debugflag) {
744 lept_mkdir("lept/barcode");
745 gplot = gplotCreate("/tmp/lept/barcode/signal", GPLOT_PNG,
746 "Pixel values", "dist in pixels", "value");
747 gplotAddPlot(gplot, nax, nay, GPLOT_LINES, "plot 1");
748 gplotMakeOutput(gplot);
749 gplotDestroy(&gplot);
750 }
751
752 /* Locate the crossings. Run multiple times with different
753 * thresholds, and choose a threshold in the center of the
754 * run of thresholds that all give the maximum number of crossings. */
755 numaSelectCrossingThreshold(nax, nay, thresh, &bestthresh);
756
757 /* Get the crossings with the best threshold. */
758 nad = numaCrossingsByThreshold(nax, nay, bestthresh);
759 numaDestroy(&nas);
760 numaDestroy(&nax);
761 numaDestroy(&nay);
762
763 if (numaGetCount(nad) < 10) {
764 L_ERROR("Only %d crossings; failure\n", __func__, numaGetCount(nad));
765 numaDestroy(&nad);
766 }
767 return nad;
768 }
769
770
771 /*------------------------------------------------------------------------*
772 * Average adjacent rasters *
773 *------------------------------------------------------------------------*/
774 /*!
775 * \brief pixAverageRasterScans()
776 *
777 * \param[in] pixs input image; 8 bpp
778 * \param[in] nscans number of adjacent scans, about the center vertically
779 * \return numa of average pixel values across image, or NULL on error
780 */
781 static NUMA *
782 pixAverageRasterScans(PIX *pixs,
783 l_int32 nscans)
784 {
785 l_int32 w, h, first, last, i, j, wpl, val;
786 l_uint32 *line, *data;
787 l_float32 *array;
788 NUMA *nad;
789
790 if (!pixs || pixGetDepth(pixs) != 8)
791 return (NUMA *)ERROR_PTR("pixs undefined or not 8 bpp", __func__, NULL);
792
793 pixGetDimensions(pixs, &w, &h, NULL);
794 if (nscans > h) {
795 first = 0;
796 last = h - 1;
797 nscans = h;
798 } else {
799 first = (h - nscans) / 2;
800 last = first + nscans - 1;
801 }
802
803 nad = numaCreate(w);
804 numaSetCount(nad, w);
805 array = numaGetFArray(nad, L_NOCOPY);
806 wpl = pixGetWpl(pixs);
807 data = pixGetData(pixs);
808 for (j = 0; j < w; j++) {
809 for (i = first; i <= last; i++) {
810 line = data + i * wpl;
811 val = GET_DATA_BYTE(line, j);
812 array[j] += val;
813 }
814 array[j] = array[j] / (l_float32)nscans;
815 }
816
817 return nad;
818 }
819
820
821 /*------------------------------------------------------------------------*
822 * Signal processing for barcode widths *
823 *------------------------------------------------------------------------*/
824 /*!
825 * \brief numaQuantizeCrossingsByWidth()
826 *
827 * \param[in] nas numa of crossing locations, in pixel units
828 * \param[in] binfract histo binsize as a fraction of minsize; e.g., 0.25
829 * \param[out] pnaehist [optional] histo of even (black) bar widths
830 * \param[out] pnaohist [optional] histo of odd (white) bar widths
831 * \param[in] debugflag 1 to generate plots of histograms of bar widths
832 * \return nad sequence of widths, in unit sizes, or NULL on error
833 *
834 * <pre>
835 * Notes:
836 * (1) This first computes the histogram of black and white bar widths,
837 * binned in appropriate units. There should be well-defined
838 * peaks, each corresponding to a specific width. The sequence
839 * of barcode widths (namely, the integers from the set {1,2,3,4})
840 * is returned.
841 * (2) The optional returned histograms are binned in width units
842 * that are inversely proportional to %binfract. For example,
843 * if %binfract = 0.25, there are 4.0 bins in the distance of
844 * the width of the narrowest bar.
845 * </pre>
846 */
847 NUMA *
848 numaQuantizeCrossingsByWidth(NUMA *nas,
849 l_float32 binfract,
850 NUMA **pnaehist,
851 NUMA **pnaohist,
852 l_int32 debugflag)
853 {
854 l_int32 i, n, ret, ned, nod, iw, width;
855 l_float32 val, minsize, maxsize, factor;
856 GPLOT *gplot;
857 NUMA *naedist, *naodist, *naehist, *naohist, *naecent, *naocent;
858 NUMA *naerange, *naorange, *naelut, *naolut, *nad;
859
860 if (pnaehist) *pnaehist = NULL;
861 if (pnaohist) *pnaohist = NULL;
862 if (!nas)
863 return (NUMA *)ERROR_PTR("nas not defined", __func__, NULL);
864 n = numaGetCount(nas);
865 if (n < 10)
866 return (NUMA *)ERROR_PTR("n < 10", __func__, NULL);
867 if (binfract <= 0.0)
868 return (NUMA *)ERROR_PTR("binfract <= 0.0", __func__, NULL);
869
870 /* Get even and odd crossing distances, and determine the rank
871 * widths for rank 0.1 (minsize) and 0.9 (maxsize). */
872 ret = numaGetCrossingDistances(nas, &naedist, &naodist, &minsize, &maxsize);
873 if (ret || minsize < 1.0 || maxsize / minsize > 8.0) {
874 L_ERROR("bad data, or minsize = %5.2f < 1.0 or max/min = %f > 4.0\n",
875 __func__, minsize, maxsize / minsize);
876 numaDestroy(&naedist);
877 numaDestroy(&naodist);
878 return NULL;
879 }
880
881 /* Bin the spans in units of binfract * minsize. These
882 * units are convenient because they scale to make at least
883 * 1/binfract bins in the smallest span (width). We want this
884 * number to be large enough to clearly separate the
885 * widths, but small enough so that the histogram peaks
886 * have very few if any holes (zeroes) within them. */
887 naehist = numaMakeHistogramClipped(naedist, binfract * minsize,
888 (1.25 / binfract) * maxsize);
889 naohist = numaMakeHistogramClipped(naodist, binfract * minsize,
890 (1.25 / binfract) * maxsize);
891
892 if (debugflag) {
893 lept_mkdir("lept/barcode");
894 gplot = gplotCreate("/tmp/lept/barcode/histw", GPLOT_PNG,
895 "Raw width histogram", "Width", "Number");
896 gplotAddPlot(gplot, NULL, naehist, GPLOT_LINES, "plot black");
897 gplotAddPlot(gplot, NULL, naohist, GPLOT_LINES, "plot white");
898 gplotMakeOutput(gplot);
899 gplotDestroy(&gplot);
900 }
901
902 /* Compute the peak ranges, still in units of binfract * minsize. */
903 naerange = numaLocatePeakRanges(naehist, 1.0 / binfract,
904 1.0 / binfract, 0.0);
905 naorange = numaLocatePeakRanges(naohist, 1.0 / binfract,
906 1.0 / binfract, 0.0);
907
908 /* Find the centroid values of each peak */
909 naecent = numaGetPeakCentroids(naehist, naerange);
910 naocent = numaGetPeakCentroids(naohist, naorange);
911
912 /* Generate the lookup tables that map from the bar width, in
913 * units of (binfract * minsize), to the integerized barcode
914 * units (1, 2, 3, 4), which are the output integer widths
915 * between transitions. */
916 naelut = numaGetPeakWidthLUT(naerange, naecent);
917 naolut = numaGetPeakWidthLUT(naorange, naocent);
918
919 /* Get the widths. Because the LUT accepts our funny units,
920 * we first must convert the pixel widths to these units,
921 * which is what 'factor' does. */
922 nad = numaCreate(0);
923 ned = numaGetCount(naedist);
924 nod = numaGetCount(naodist);
925 if (nod != ned - 1)
926 L_WARNING("ned != nod + 1\n", __func__);
927 factor = 1.0 / (binfract * minsize); /* for converting units */
928 for (i = 0; i < ned - 1; i++) {
929 numaGetFValue(naedist, i, &val);
930 width = (l_int32)(factor * val);
931 numaGetIValue(naelut, width, &iw);
932 numaAddNumber(nad, iw);
933 /* lept_stderr("even: val = %7.3f, width = %d, iw = %d\n",
934 val, width, iw); */
935 numaGetFValue(naodist, i, &val);
936 width = (l_int32)(factor * val);
937 numaGetIValue(naolut, width, &iw);
938 numaAddNumber(nad, iw);
939 /* lept_stderr("odd: val = %7.3f, width = %d, iw = %d\n",
940 val, width, iw); */
941 }
942 numaGetFValue(naedist, ned - 1, &val);
943 width = (l_int32)(factor * val);
944 numaGetIValue(naelut, width, &iw);
945 numaAddNumber(nad, iw);
946
947 if (debugflag) {
948 lept_stderr(" ---- Black bar widths (pixels) ------ \n");
949 numaWriteStderr(naedist);
950 lept_stderr(" ---- Histogram of black bar widths ------ \n");
951 numaWriteStderr(naehist);
952 lept_stderr(" ---- Peak ranges in black bar histogram bins --- \n");
953 numaWriteStderr(naerange);
954 lept_stderr(" ---- Peak black bar centroid width values ------ \n");
955 numaWriteStderr(naecent);
956 lept_stderr(" ---- Black bar lookup table ------ \n");
957 numaWriteStderr(naelut);
958 lept_stderr(" ---- White bar widths (pixels) ------ \n");
959 numaWriteStderr(naodist);
960 lept_stderr(" ---- Histogram of white bar widths ------ \n");
961 numaWriteStderr(naohist);
962 lept_stderr(" ---- Peak ranges in white bar histogram bins --- \n");
963 numaWriteStderr(naorange);
964 lept_stderr(" ---- Peak white bar centroid width values ------ \n");
965 numaWriteStderr(naocent);
966 lept_stderr(" ---- White bar lookup table ------ \n");
967 numaWriteStderr(naolut);
968 }
969
970 numaDestroy(&naedist);
971 numaDestroy(&naodist);
972 numaDestroy(&naerange);
973 numaDestroy(&naorange);
974 numaDestroy(&naecent);
975 numaDestroy(&naocent);
976 numaDestroy(&naelut);
977 numaDestroy(&naolut);
978 if (pnaehist)
979 *pnaehist = naehist;
980 else
981 numaDestroy(&naehist);
982 if (pnaohist)
983 *pnaohist = naohist;
984 else
985 numaDestroy(&naohist);
986 return nad;
987 }
988
989
990 /*!
991 * \brief numaGetCrossingDistances()
992 *
993 * \param[in] nas numa of crossing locations
994 * \param[out] pnaedist [optional] even distances between crossings
995 * \param[out] pnaodist [optional] odd distances between crossings
996 * \param[out] pmindist [optional] min distance between crossings
997 * \param[out] pmaxdist [optional] max distance between crossings
998 * \return 0 if OK, 1 on error
999 */
1000 static l_int32
1001 numaGetCrossingDistances(NUMA *nas,
1002 NUMA **pnaedist,
1003 NUMA **pnaodist,
1004 l_float32 *pmindist,
1005 l_float32 *pmaxdist)
1006 {
1007 l_int32 i, n;
1008 l_float32 val, newval, mindist, maxdist;
1009 NUMA *na1, *na2, *naedist, *naodist;
1010
1011 if (pnaedist) *pnaedist = NULL;
1012 if (pnaodist) *pnaodist = NULL;
1013 if (pmindist) *pmindist = 0.0;
1014 if (pmaxdist) *pmaxdist = 0.0;
1015 if (!nas)
1016 return ERROR_INT("nas not defined", __func__, 1);
1017 if ((n = numaGetCount(nas)) < 2)
1018 return ERROR_INT("n < 2", __func__, 1);
1019
1020 /* Get numas of distances between crossings. Separate these
1021 * into even (e.g., black) and odd (e.g., white) spans.
1022 * For barcodes, the black spans are 0, 2, etc. These
1023 * distances are in pixel units. */
1024 naedist = numaCreate(n / 2 + 1);
1025 naodist = numaCreate(n / 2);
1026 numaGetFValue(nas, 0, &val);
1027 for (i = 1; i < n; i++) {
1028 numaGetFValue(nas, i, &newval);
1029 if (i % 2)
1030 numaAddNumber(naedist, newval - val);
1031 else
1032 numaAddNumber(naodist, newval - val);
1033 val = newval;
1034 }
1035
1036 /* The min and max rank distances of the spans are in pixel units. */
1037 na1 = numaCopy(naedist);
1038 numaJoin(na1, naodist, 0, -1); /* use both bars and spaces */
1039 na2 = numaMakeHistogram(na1, 100, NULL, NULL);
1040 numaHistogramGetValFromRank(na2, 0.1f, &mindist);
1041 numaHistogramGetValFromRank(na2, 0.9f, &maxdist);
1042 numaDestroy(&na1);
1043 numaDestroy(&na2);
1044 L_INFO("mindist = %7.3f, maxdist = %7.3f\n", __func__, mindist, maxdist);
1045
1046 if (pnaedist)
1047 *pnaedist = naedist;
1048 else
1049 numaDestroy(&naedist);
1050 if (pnaodist)
1051 *pnaodist = naodist;
1052 else
1053 numaDestroy(&naodist);
1054 if (pmindist) *pmindist = mindist;
1055 if (pmaxdist) *pmaxdist = maxdist;
1056 return 0;
1057 }
1058
1059
1060 /*!
1061 * \brief numaLocatePeakRanges()
1062 *
1063 * \param[in] nas numa of histogram of crossing widths
1064 * \param[in] minfirst min location of center of first peak
1065 * \param[in] minsep min separation between peak range centers
1066 * \param[in] maxmin max allowed value for min histo value between peaks
1067 * \return nad ranges for each peak found, in pairs, or NULL on error
1068 *
1069 * <pre>
1070 * Notes:
1071 * (1) Units of %minsep are the index into nas.
1072 * This puts useful constraints on peak-finding.
1073 * (2) If maxmin == 0.0, the value of nas[i] must go to 0.0 (or less)
1074 * between peaks.
1075 * (3) All calculations are done in units of the index into nas.
1076 * The resulting ranges are therefore integers.
1077 * (4) The output nad gives pairs of range values for successive peaks.
1078 * Any location [i] for which maxmin = nas[i] = 0.0 will NOT be
1079 * included in a peak range. This works fine for histograms where
1080 * if nas[i] == 0.0, it means that there are no samples at [i].
1081 * (5) For barcodes, when this is used on a histogram of barcode
1082 * widths, use maxmin = 0.0. This requires that there is at
1083 * least one histogram bin corresponding to a width value between
1084 * adjacent peak ranges that is unpopulated, making the separation
1085 * of the histogram peaks unambiguous.
1086 * </pre>
1087 */
1088 static NUMA *
1089 numaLocatePeakRanges(NUMA *nas,
1090 l_float32 minfirst,
1091 l_float32 minsep,
1092 l_float32 maxmin)
1093 {
1094 l_int32 i, n, inpeak, left;
1095 l_float32 center, prevcenter, val;
1096 NUMA *nad;
1097
1098 if (!nas)
1099 return (NUMA *)ERROR_PTR("nas not defined", __func__, NULL);
1100 n = numaGetCount(nas);
1101 nad = numaCreate(0);
1102
1103 inpeak = FALSE;
1104 prevcenter = minfirst - minsep - 1.0;
1105 for (i = 0; i < n; i++) {
1106 numaGetFValue(nas, i, &val);
1107 if (inpeak == FALSE && val > maxmin) {
1108 inpeak = TRUE;
1109 left = i;
1110 } else if (inpeak == TRUE && val <= maxmin) { /* end peak */
1111 center = (left + i - 1.0) / 2.0;
1112 if (center - prevcenter >= minsep) { /* save new peak */
1113 inpeak = FALSE;
1114 numaAddNumber(nad, left);
1115 numaAddNumber(nad, i - 1);
1116 prevcenter = center;
1117 } else { /* attach to previous peak; revise the right edge */
1118 numaSetValue(nad, numaGetCount(nad) - 1, i - 1);
1119 }
1120 }
1121 }
1122 if (inpeak == TRUE) { /* save the last peak */
1123 numaAddNumber(nad, left);
1124 numaAddNumber(nad, n - 1);
1125 }
1126
1127 return nad;
1128 }
1129
1130
1131 /*!
1132 * \brief numaGetPeakCentroids()
1133 *
1134 * \param[in] nahist numa of histogram of crossing widths
1135 * \param[in] narange numa of ranges of x-values for the peaks in %nahist
1136 * \return nad centroids for each peak found; max of 4, corresponding
1137 * to 4 different barcode line widths, or NULL on error
1138 */
1139 static NUMA *
1140 numaGetPeakCentroids(NUMA *nahist,
1141 NUMA *narange)
1142 {
1143 l_int32 i, j, nr, low, high;
1144 l_float32 cent, sum, val;
1145 NUMA *nad;
1146
1147 if (!nahist)
1148 return (NUMA *)ERROR_PTR("nahist not defined", __func__, NULL);
1149 if (!narange)
1150 return (NUMA *)ERROR_PTR("narange not defined", __func__, NULL);
1151 nr = numaGetCount(narange) / 2;
1152
1153 nad = numaCreate(4);
1154 for (i = 0; i < nr; i++) {
1155 numaGetIValue(narange, 2 * i, &low);
1156 numaGetIValue(narange, 2 * i + 1, &high);
1157 cent = 0.0;
1158 sum = 0.0;
1159 for (j = low; j <= high; j++) {
1160 numaGetFValue(nahist, j, &val);
1161 cent += j * val;
1162 sum += val;
1163 }
1164 numaAddNumber(nad, cent / sum);
1165 }
1166
1167 return nad;
1168 }
1169
1170
1171 /*!
1172 * \brief numaGetPeakWidthLUT()
1173 *
1174 * \param[in] narange numa of x-val ranges for the histogram width peaks
1175 * \param[in] nacent numa of centroids of each peak -- up to 4
1176 * \return nalut lookup table from the width of a bar to one of the four
1177 * integerized barcode units, or NULL on error
1178 *
1179 * <pre>
1180 * Notes:
1181 * (1) This generates the lookup table that maps from a sequence of widths
1182 * (in some units) to the integerized barcode units (1, 2, 3, 4),
1183 * which are the output integer widths between transitions.
1184 * (2) The smallest width can be lost in float roundoff. To avoid
1185 * losing it, we expand the peak range of the smallest width.
1186 * </pre>
1187 */
1188 static NUMA *
1189 numaGetPeakWidthLUT(NUMA *narange,
1190 NUMA *nacent)
1191 {
1192 l_int32 i, j, nc, low, high, imax;
1193 l_int32 assign[4];
1194 l_float32 *warray;
1195 l_float32 max, rat21, rat32, rat42;
1196 NUMA *nalut;
1197
1198 if (!narange)
1199 return (NUMA *)ERROR_PTR("narange not defined", __func__, NULL);
1200 if (!nacent)
1201 return (NUMA *)ERROR_PTR("nacent not defined", __func__, NULL);
1202 nc = numaGetCount(nacent); /* half the size of narange */
1203 if (nc < 1 || nc > 4)
1204 return (NUMA *)ERROR_PTR("nc must be 1, 2, 3, or 4", __func__, NULL);
1205
1206 /* Check the peak centroids for consistency with bar widths.
1207 * The third peak can correspond to a width of either 3 or 4.
1208 * Use ratios 3/2 and 4/2 instead of 3/1 and 4/1 because the
1209 * former are more stable and closer to the expected ratio. */
1210 if (nc > 1) {
1211 warray = numaGetFArray(nacent, L_NOCOPY);
1212 if (warray[0] == 0)
1213 return (NUMA *)ERROR_PTR("first peak has width 0.0",
1214 __func__, NULL);
1215 rat21 = warray[1] / warray[0];
1216 if (rat21 < 1.5 || rat21 > 2.6)
1217 L_WARNING("width ratio 2/1 = %f\n", __func__, rat21);
1218 if (nc > 2) {
1219 rat32 = warray[2] / warray[1];
1220 if (rat32 < 1.3 || rat32 > 2.25)
1221 L_WARNING("width ratio 3/2 = %f\n", __func__, rat32);
1222 }
1223 if (nc == 4) {
1224 rat42 = warray[3] / warray[1];
1225 if (rat42 < 1.7 || rat42 > 2.3)
1226 L_WARNING("width ratio 4/2 = %f\n", __func__, rat42);
1227 }
1228 }
1229
1230 /* Set width assignments.
1231 * The only possible ambiguity is with nc = 3 */
1232 for (i = 0; i < 4; i++)
1233 assign[i] = i + 1;
1234 if (nc == 3) {
1235 if (rat32 > 1.75)
1236 assign[2] = 4;
1237 }
1238
1239 /* Put widths into the LUT */
1240 numaGetMax(narange, &max, NULL);
1241 imax = (l_int32)max;
1242 nalut = numaCreate(imax + 1);
1243 numaSetCount(nalut, imax + 1); /* fill the array with zeroes */
1244 for (i = 0; i < nc; i++) {
1245 numaGetIValue(narange, 2 * i, &low);
1246 if (i == 0) low--; /* catch smallest width */
1247 numaGetIValue(narange, 2 * i + 1, &high);
1248 for (j = low; j <= high; j++)
1249 numaSetValue(nalut, j, assign[i]);
1250 }
1251
1252 return nalut;
1253 }
1254
1255
1256 /*!
1257 * \brief numaQuantizeCrossingsByWindow()
1258 *
1259 * \param[in] nas numa of crossing locations
1260 * \param[in] ratio of max window size over min window size in search;
1261 * typ. 2.0
1262 * \param[out] pwidth [optional] best window width
1263 * \param[out] pfirstloc [optional] center of window for first xing
1264 * \param[out] pnac [optional] array of window crossings (0, 1, 2)
1265 * \param[in] debugflag 1 to generate various plots of intermediate results
1266 * \return nad sequence of widths, in unit sizes, or NULL on error
1267 *
1268 * <pre>
1269 * Notes:
1270 * (1) The minimum size of the window is set by the minimum
1271 * distance between zero crossings.
1272 * (2) The optional return signal %nac is a sequence of 0s, 1s,
1273 * and perhaps a few 2s, giving the number of crossings in each window.
1274 * On the occasion where there is a '2', it is interpreted as
1275 * ending two runs: the previous one and another one that has length 1.
1276 * </pre>
1277 */
1278 NUMA *
1279 numaQuantizeCrossingsByWindow(NUMA *nas,
1280 l_float32 ratio,
1281 l_float32 *pwidth,
1282 l_float32 *pfirstloc,
1283 NUMA **pnac,
1284 l_int32 debugflag)
1285 {
1286 l_int32 i, nw, started, count, trans;
1287 l_float32 minsize, minwidth, minshift, xfirst;
1288 NUMA *nac, *nad;
1289
1290 if (!nas)
1291 return (NUMA *)ERROR_PTR("nas not defined", __func__, NULL);
1292 if (numaGetCount(nas) < 2)
1293 return (NUMA *)ERROR_PTR("nas size < 2", __func__, NULL);
1294
1295 /* Get the minsize, which is needed for the search for
1296 * the window width (ultimately found as 'minwidth') */
1297 numaGetCrossingDistances(nas, NULL, NULL, &minsize, NULL);
1298
1299 /* Compute the width and shift increments; start at minsize
1300 * and go up to ratio * minsize */
1301 numaEvalBestWidthAndShift(nas, 100, 10, minsize, ratio * minsize,
1302 &minwidth, &minshift, NULL);
1303
1304 /* Refine width and shift calculation */
1305 numaEvalBestWidthAndShift(nas, 100, 10, 0.98 * minwidth, 1.02 * minwidth,
1306 &minwidth, &minshift, NULL);
1307
1308 L_INFO("best width = %7.3f, best shift = %7.3f\n",
1309 __func__, minwidth, minshift);
1310
1311 /* Get the crossing array (0,1,2) for the best window width and shift */
1312 numaEvalSyncError(nas, 0, 0, minwidth, minshift, NULL, &nac);
1313 if (pwidth) *pwidth = minwidth;
1314 if (pfirstloc) {
1315 numaGetFValue(nas, 0, &xfirst);
1316 *pfirstloc = xfirst + minshift;
1317 }
1318
1319 /* Get the array of bar widths, starting with a black bar */
1320 nad = numaCreate(0);
1321 nw = numaGetCount(nac); /* number of window measurements */
1322 started = FALSE;
1323 count = 0; /* unnecessary init */
1324 for (i = 0; i < nw; i++) {
1325 numaGetIValue(nac, i, &trans);
1326 if (trans > 2)
1327 L_WARNING("trans = %d > 2 !!!\n", __func__, trans);
1328 if (started) {
1329 if (trans > 1) { /* i.e., when trans == 2 */
1330 numaAddNumber(nad, count);
1331 trans--;
1332 count = 1;
1333 }
1334 if (trans == 1) {
1335 numaAddNumber(nad, count);
1336 count = 1;
1337 } else {
1338 count++;
1339 }
1340 }
1341 if (!started && trans) {
1342 started = TRUE;
1343 if (trans == 2) /* a whole bar in this window */
1344 numaAddNumber(nad, 1);
1345 count = 1;
1346 }
1347 }
1348
1349 if (pnac)
1350 *pnac = nac;
1351 else
1352 numaDestroy(&nac);
1353 return nad;
1354 }
1355
1356
1357 /*!
1358 * \brief numaEvalBestWidthAndShift()
1359 *
1360 * \param[in] nas numa of crossing locations
1361 * \param[in] nwidth number of widths to consider
1362 * \param[in] nshift number of shifts to consider for each width
1363 * \param[in] minwidth smallest width to consider
1364 * \param[in] maxwidth largest width to consider
1365 * \param[out] pbestwidth best size of window
1366 * \param[out] pbestshift best shift for the window
1367 * \param[out] pbestscore [optional] average squared error of dist
1368 * of crossing signal from the center of the window
1369 * \return 0 if OK, 1 on error
1370 *
1371 * <pre>
1372 * Notes:
1373 * (1) This does a linear sweep of widths, evaluating at %nshift
1374 * shifts for each width, finding the (width, shift) pair that
1375 * gives the minimum score.
1376 * </pre>
1377 */
1378 static l_int32
1379 numaEvalBestWidthAndShift(NUMA *nas,
1380 l_int32 nwidth,
1381 l_int32 nshift,
1382 l_float32 minwidth,
1383 l_float32 maxwidth,
1384 l_float32 *pbestwidth,
1385 l_float32 *pbestshift,
1386 l_float32 *pbestscore)
1387 {
1388 l_int32 i, j;
1389 l_float32 delwidth, delshift, width, shift, score;
1390 l_float32 bestwidth, bestshift, bestscore;
1391
1392 if (!nas)
1393 return ERROR_INT("nas not defined", __func__, 1);
1394 if (!pbestwidth || !pbestshift)
1395 return ERROR_INT("&bestwidth and &bestshift not defined", __func__, 1);
1396
1397 bestwidth = 0.0f;
1398 bestshift = 0.0f;
1399 bestscore = 1.0;
1400 delwidth = (maxwidth - minwidth) / (nwidth - 1.0);
1401 for (i = 0; i < nwidth; i++) {
1402 width = minwidth + delwidth * i;
1403 delshift = width / (l_float32)(nshift);
1404 for (j = 0; j < nshift; j++) {
1405 shift = -0.5 * (width - delshift) + j * delshift;
1406 numaEvalSyncError(nas, 0, 0, width, shift, &score, NULL);
1407 if (score < bestscore) {
1408 bestscore = score;
1409 bestwidth = width;
1410 bestshift = shift;
1411 #if DEBUG_FREQUENCY
1412 lept_stderr("width = %7.3f, shift = %7.3f, score = %7.3f\n",
1413 width, shift, score);
1414 #endif /* DEBUG_FREQUENCY */
1415 }
1416 }
1417 }
1418
1419 *pbestwidth = bestwidth;
1420 *pbestshift = bestshift;
1421 if (pbestscore)
1422 *pbestscore = bestscore;
1423 return 0;
1424 }
1425
1426
1427 /*!
1428 * \brief numaEvalSyncError()
1429 *
1430 * \param[in] nas numa of crossing locations
1431 * \param[in] ifirst first crossing to use
1432 * \param[in] ilast last crossing to use; use 0 for all crossings
1433 * \param[in] width size of window
1434 * \param[in] shift of center of window w/rt first crossing
1435 * \param[out] pscore [optional] average squared error of dist
1436 * of crossing signal from the center of the window
1437 * \param[out] pnad [optional] numa of 1s and 0s for crossings
1438 * \return 0 if OK, 1 on error
1439 *
1440 * <pre>
1441 * Notes:
1442 * (1) The score is computed only on the part of the signal from the
1443 * %ifirst to %ilast crossings. Use 0 for both of these to
1444 * use all the crossings. The score is normalized for
1445 * the number of crossings and with half-width of the window.
1446 * (2) The optional return %nad is a sequence of 0s and 1s, where a '1'
1447 * indicates a crossing in the window.
1448 * </pre>
1449 */
1450 static l_int32
1451 numaEvalSyncError(NUMA *nas,
1452 l_int32 ifirst,
1453 l_int32 ilast,
1454 l_float32 width,
1455 l_float32 shift,
1456 l_float32 *pscore,
1457 NUMA **pnad)
1458 {
1459 l_int32 i, n, nc, nw, ival;
1460 l_int32 iw; /* cell in which transition occurs */
1461 l_float32 score, xfirst, xlast, xleft, xc, xwc;
1462 NUMA *nad;
1463
1464 if (!nas)
1465 return ERROR_INT("nas not defined", __func__, 1);
1466 if ((n = numaGetCount(nas)) < 2)
1467 return ERROR_INT("nas size < 2", __func__, 1);
1468 if (ifirst < 0) ifirst = 0;
1469 if (ilast <= 0) ilast = n - 1;
1470 if (ifirst >= ilast)
1471 return ERROR_INT("ifirst not < ilast", __func__, 1);
1472 nc = ilast - ifirst + 1;
1473
1474 /* Set up an array corresponding to the (shifted) windows,
1475 * and fill in the crossings. */
1476 score = 0.0;
1477 numaGetFValue(nas, ifirst, &xfirst);
1478 numaGetFValue(nas, ilast, &xlast);
1479 nw = (l_int32) ((xlast - xfirst + 2.0 * width) / width);
1480 nad = numaCreate(nw);
1481 numaSetCount(nad, nw); /* init to all 0.0 */
1482 xleft = xfirst - width / 2.0 + shift; /* left edge of first window */
1483 for (i = ifirst; i <= ilast; i++) {
1484 numaGetFValue(nas, i, &xc);
1485 iw = (l_int32)((xc - xleft) / width);
1486 xwc = xleft + (iw + 0.5) * width; /* center of cell iw */
1487 score += (xwc - xc) * (xwc - xc);
1488 numaGetIValue(nad, iw, &ival);
1489 numaSetValue(nad, iw, ival + 1);
1490 }
1491
1492 if (pscore)
1493 *pscore = 4.0 * score / (width * width * (l_float32)nc);
1494 if (pnad)
1495 *pnad = nad;
1496 else
1497 numaDestroy(&nad);
1498
1499 return 0;
1500 }