Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/leptonica/src/selgen.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 * \file selgen.c
29 * <pre>
30 *
31 * This file contains functions that generate hit-miss Sels
32 * for doing a loose match to a small bitmap. The hit-miss
33 * Sel is made from a given bitmap. Several "knobs"
34 * are available to control the looseness of the match.
35 * In general, a tight match will have fewer false positives
36 * (bad matches) but more false negatives (missed patterns).
37 * The values to be used depend on the quality and variation
38 * of the image in which the pattern is to be searched,
39 * and the relative penalties of false positives and
40 * false negatives. Default values for the three knobs --
41 * minimum distance to boundary pixels, number of extra pixels
42 * added to selected sides, and minimum acceptable runlength
43 * in eroded version -- are provided.
44 *
45 * The generated hit-miss Sels can always be used in the
46 * rasterop implementation of binary morphology (in morph.h).
47 * If they are small enough (not more than 31 pixels extending
48 * in any direction from the Sel origin), they can also be used
49 * to auto-generate dwa code (fmorphauto.c).
50 *
51 * In production, use pixGenerateSelBoundary().
52 *
53 * Generate a subsampled structuring element
54 * SEL *pixGenerateSelBoundary()
55 * SEL *pixGenerateSelWithRuns()
56 * SEL *pixGenerateSelRandom()
57 *
58 * Accumulate data on runs along lines
59 * NUMA *pixGetRunCentersOnLine()
60 * NUMA *pixGetRunsOnLine()
61 *
62 * Subsample boundary pixels in relatively ordered way
63 * PTA *pixSubsampleBoundaryPixels()
64 * PTA *adjacentOnPixelInRaster()
65 *
66 * Display generated sel with originating image
67 * PIX *pixDisplayHitMissSel()
68 * </pre>
69 */
70
71 #ifdef HAVE_CONFIG_H
72 #include <config_auto.h>
73 #endif /* HAVE_CONFIG_H */
74
75 #include "allheaders.h"
76
77 /* Default minimum distance of a hit-miss pixel element to
78 * a boundary pixel of its color. */
79 static const l_int32 DefaultDistanceToBoundary = 1;
80 static const l_int32 MaxDistanceToBoundary = 4;
81
82 /* Default min runlength to accept a hit or miss element located
83 * at its center */
84 static const l_int32 DefaultMinRunlength = 3;
85
86 /* Default scalefactor for displaying image and hit-miss sel
87 * that is derived from it */
88 static const l_int32 DefaultSelScalefactor = 7;
89 static const l_int32 MaxSelScalefactor = 31; /* should be big enough */
90
91 #ifndef NO_CONSOLE_IO
92 #define DEBUG_DISPLAY_HM_SEL 0
93 #endif /* ~NO_CONSOLE_IO */
94
95
96 /*-----------------------------------------------------------------*
97 * Generate a subsampled structuring element *
98 *-----------------------------------------------------------------*/
99
100 /*!
101 * \brief pixGenerateSelBoundary()
102 *
103 * \param[in] pixs 1 bpp, typically small, to be used as a pattern
104 * \param[in] hitdist min distance from fg boundary pixel
105 * \param[in] missdist min distance from bg boundary pixel
106 * \param[in] hitskip number of boundary pixels skipped between hits
107 * \param[in] missskip number of boundary pixels skipped between misses
108 * \param[in] topflag flag for extra pixels of bg added above
109 * \param[in] botflag flag for extra pixels of bg added below
110 * \param[in] leftflag flag for extra pixels of bg added to left
111 * \param[in] rightflag flag for extra pixels of bg added to right
112 * \param[out] ppixe [optional] input pix expanded by extra pixels
113 * \return sel hit-miss for input pattern, or NULL on error
114 *
115 * <pre>
116 * Notes:
117 * (1) All fg elements selected are exactly hitdist pixels away from
118 * the nearest fg boundary pixel, and ditto for bg elements.
119 * Valid inputs of hitdist and missdist are 0, 1, 2, 3 and 4.
120 * For example, a hitdist of 0 puts the hits at the fg boundary.
121 * Usually, the distances should be > 0 avoid the effect of
122 * noise at the boundary.
123 * (2) Set hitskip < 0 if no hits are to be used. Ditto for missskip.
124 * If both hitskip and missskip are < 0, the sel would be empty,
125 * and NULL is returned.
126 * (3) The 4 flags determine whether the sel is increased on that side
127 * to allow bg misses to be placed all along that boundary.
128 * The increase in sel size on that side is the minimum necessary
129 * to allow the misses to be placed at mindist. For text characters,
130 * the topflag and botflag are typically set to 1, and the leftflag
131 * and rightflag to 0.
132 * (4) The input pix, as extended by the extra pixels on selected sides,
133 * can optionally be returned. For debugging, call
134 * pixDisplayHitMissSel() to visualize the hit-miss sel superimposed
135 * on the generating bitmap.
136 * (5) This is the best of the three sel generators: it gives the most
137 * flexibility with the smallest number of hits and misses.
138 * The other two generators are presented as examples of other
139 * approaches, but they should not be used in production.
140 * </pre>
141 */
142 SEL *
143 pixGenerateSelBoundary(PIX *pixs,
144 l_int32 hitdist,
145 l_int32 missdist,
146 l_int32 hitskip,
147 l_int32 missskip,
148 l_int32 topflag,
149 l_int32 botflag,
150 l_int32 leftflag,
151 l_int32 rightflag,
152 PIX **ppixe)
153 {
154 l_int32 ws, hs, w, h, x, y, ix, iy, i, npt;
155 PIX *pixt1, *pixt2, *pixt3, *pixfg, *pixbg;
156 SEL *selh, *selm, *sel_3, *sel;
157 PTA *ptah = NULL, *ptam = NULL;
158
159 if (ppixe) *ppixe = NULL;
160 if (!pixs)
161 return (SEL *)ERROR_PTR("pixs not defined", __func__, NULL);
162 if (pixGetDepth(pixs) != 1)
163 return (SEL *)ERROR_PTR("pixs not 1 bpp", __func__, NULL);
164 if (hitdist < 0 || hitdist > 4 || missdist < 0 || missdist > 4)
165 return (SEL *)ERROR_PTR("dist not in {0 .. 4}", __func__, NULL);
166 if (hitskip < 0 && missskip < 0)
167 return (SEL *)ERROR_PTR("no hits or misses", __func__, NULL);
168
169 /* Locate the foreground */
170 pixClipToForeground(pixs, &pixt1, NULL);
171 if (!pixt1)
172 return (SEL *)ERROR_PTR("pixt1 not made", __func__, NULL);
173 ws = pixGetWidth(pixt1);
174 hs = pixGetHeight(pixt1);
175 w = ws;
176 h = hs;
177
178 /* Crop out a region including the foreground, and add pixels
179 * on sides depending on the side flags */
180 if (topflag || botflag || leftflag || rightflag) {
181 x = y = 0;
182 if (topflag) {
183 h += missdist + 1;
184 y = missdist + 1;
185 }
186 if (botflag)
187 h += missdist + 1;
188 if (leftflag) {
189 w += missdist + 1;
190 x = missdist + 1;
191 }
192 if (rightflag)
193 w += missdist + 1;
194 pixt2 = pixCreate(w, h, 1);
195 pixRasterop(pixt2, x, y, ws, hs, PIX_SRC, pixt1, 0, 0);
196 } else {
197 pixt2 = pixClone(pixt1);
198 }
199 if (ppixe)
200 *ppixe = pixClone(pixt2);
201 pixDestroy(&pixt1);
202
203 /* Identify fg and bg pixels that are exactly hitdist and
204 * missdist (rsp) away from the boundary pixels in their set.
205 * Then get a subsampled set of these points. */
206 sel_3 = selCreateBrick(3, 3, 1, 1, SEL_HIT);
207 if (hitskip >= 0) {
208 selh = selCreateBrick(2 * hitdist + 1, 2 * hitdist + 1,
209 hitdist, hitdist, SEL_HIT);
210 pixt3 = pixErode(NULL, pixt2, selh);
211 pixfg = pixErode(NULL, pixt3, sel_3);
212 pixXor(pixfg, pixfg, pixt3);
213 ptah = pixSubsampleBoundaryPixels(pixfg, hitskip);
214 pixDestroy(&pixt3);
215 pixDestroy(&pixfg);
216 selDestroy(&selh);
217 }
218 if (missskip >= 0) {
219 selm = selCreateBrick(2 * missdist + 1, 2 * missdist + 1,
220 missdist, missdist, SEL_HIT);
221 pixt3 = pixDilate(NULL, pixt2, selm);
222 pixbg = pixDilate(NULL, pixt3, sel_3);
223 pixXor(pixbg, pixbg, pixt3);
224 ptam = pixSubsampleBoundaryPixels(pixbg, missskip);
225 pixDestroy(&pixt3);
226 pixDestroy(&pixbg);
227 selDestroy(&selm);
228 }
229 selDestroy(&sel_3);
230 pixDestroy(&pixt2);
231
232 /* Generate the hit-miss sel from these point */
233 sel = selCreateBrick(h, w, h / 2, w / 2, SEL_DONT_CARE);
234 if (hitskip >= 0) {
235 npt = ptaGetCount(ptah);
236 for (i = 0; i < npt; i++) {
237 ptaGetIPt(ptah, i, &ix, &iy);
238 selSetElement(sel, iy, ix, SEL_HIT);
239 }
240 }
241 if (missskip >= 0) {
242 npt = ptaGetCount(ptam);
243 for (i = 0; i < npt; i++) {
244 ptaGetIPt(ptam, i, &ix, &iy);
245 selSetElement(sel, iy, ix, SEL_MISS);
246 }
247 }
248
249 ptaDestroy(&ptah);
250 ptaDestroy(&ptam);
251 return sel;
252 }
253
254
255 /*!
256 * \brief pixGenerateSelWithRuns()
257 *
258 * \param[in] pixs 1 bpp, typically small, to be used as a pattern
259 * \param[in] nhlines number of hor lines along which elements are found
260 * \param[in] nvlines number of vert lines along which elements are found
261 * \param[in] distance min distance from boundary pixel; use 0 for default
262 * \param[in] minlength min runlength to set hit or miss; use 0 for default
263 * \param[in] toppix number of extra pixels of bg added above
264 * \param[in] botpix number of extra pixels of bg added below
265 * \param[in] leftpix number of extra pixels of bg added to left
266 * \param[in] rightpix number of extra pixels of bg added to right
267 * \param[out] ppixe [optional] input pix expanded by extra pixels
268 * \return sel hit-miss for input pattern, or NULL on error
269 *
270 * <pre>
271 * Notes:
272 * (1) The horizontal and vertical lines along which elements are
273 * selected are roughly equally spaced. The actual locations of
274 * the hits and misses are the centers of respective run-lengths.
275 * (2) No elements are selected that are less than 'distance' pixels away
276 * from a boundary pixel of the same color. This makes the
277 * match much more robust to edge noise. Valid inputs of
278 * 'distance' are 0, 1, 2, 3 and 4. If distance is either 0 or
279 * greater than 4, we reset it to the default value.
280 * (3) The 4 numbers for adding rectangles of pixels outside the fg
281 * can be use if the pattern is expected to be surrounded by bg
282 * (white) pixels. On the other hand, if the pattern may be near
283 * other fg (black) components on some sides, use 0 for those sides.
284 * (4) The pixels added to a side allow you to have miss elements there.
285 * There is a constraint between distance, minlength, and
286 * the added pixels for this to work. We illustrate using the
287 * default values. If you add 5 pixels to the top, and use a
288 * distance of 1, then you end up with a vertical run of at least
289 * 4 bg pixels along the top edge of the image. If you use a
290 * minimum runlength of 3, each vertical line will always find
291 * a miss near the center of its run. However, if you use a
292 * minimum runlength of 5, you will not get a miss on every vertical
293 * line. As another example, if you have 7 added pixels and a
294 * distance of 2, you can use a runlength up to 5 to guarantee
295 * that the miss element is recorded. We give a warning if the
296 * constraint does not guarantee a miss element outside the
297 * image proper.
298 * (5) The input pix, as extended by the extra pixels on selected sides,
299 * can optionally be returned. For debugging, call
300 * pixDisplayHitMissSel() to visualize the hit-miss sel superimposed
301 * on the generating bitmap.
302 * (6) This method is inferior to the boundary method.
303 * </pre>
304 */
305 SEL *
306 pixGenerateSelWithRuns(PIX *pixs,
307 l_int32 nhlines,
308 l_int32 nvlines,
309 l_int32 distance,
310 l_int32 minlength,
311 l_int32 toppix,
312 l_int32 botpix,
313 l_int32 leftpix,
314 l_int32 rightpix,
315 PIX **ppixe)
316 {
317 l_int32 ws, hs, w, h, x, y, xval, yval, i, j, nh, nm;
318 l_float32 delh, delw;
319 NUMA *nah, *nam;
320 PIX *pixt1, *pixt2, *pixfg, *pixbg;
321 PTA *ptah, *ptam;
322 SEL *seld, *sel;
323
324 if (ppixe) *ppixe = NULL;
325 if (!pixs)
326 return (SEL *)ERROR_PTR("pixs not defined", __func__, NULL);
327 if (pixGetDepth(pixs) != 1)
328 return (SEL *)ERROR_PTR("pixs not 1 bpp", __func__, NULL);
329 if (nhlines < 1 && nvlines < 1)
330 return (SEL *)ERROR_PTR("nvlines and nhlines both < 1", __func__, NULL);
331
332 if (distance <= 0)
333 distance = DefaultDistanceToBoundary;
334 if (minlength <= 0)
335 minlength = DefaultMinRunlength;
336 if (distance > MaxDistanceToBoundary) {
337 L_WARNING("distance too large; setting to max value\n", __func__);
338 distance = MaxDistanceToBoundary;
339 }
340
341 /* Locate the foreground */
342 pixClipToForeground(pixs, &pixt1, NULL);
343 if (!pixt1)
344 return (SEL *)ERROR_PTR("pixt1 not made", __func__, NULL);
345 ws = pixGetWidth(pixt1);
346 hs = pixGetHeight(pixt1);
347 w = ws;
348 h = hs;
349
350 /* Crop out a region including the foreground, and add pixels
351 * on sides depending on the side flags */
352 if (toppix || botpix || leftpix || rightpix) {
353 x = y = 0;
354 if (toppix) {
355 h += toppix;
356 y = toppix;
357 if (toppix < distance + minlength)
358 L_WARNING("no miss elements in added top pixels\n", __func__);
359 }
360 if (botpix) {
361 h += botpix;
362 if (botpix < distance + minlength)
363 L_WARNING("no miss elements in added bot pixels\n", __func__);
364 }
365 if (leftpix) {
366 w += leftpix;
367 x = leftpix;
368 if (leftpix < distance + minlength)
369 L_WARNING("no miss elements in added left pixels\n", __func__);
370 }
371 if (rightpix) {
372 w += rightpix;
373 if (rightpix < distance + minlength)
374 L_WARNING("no miss elements in added right pixels\n", __func__);
375 }
376 pixt2 = pixCreate(w, h, 1);
377 pixRasterop(pixt2, x, y, ws, hs, PIX_SRC, pixt1, 0, 0);
378 } else {
379 pixt2 = pixClone(pixt1);
380 }
381 if (ppixe)
382 *ppixe = pixClone(pixt2);
383 pixDestroy(&pixt1);
384
385 /* Identify fg and bg pixels that are at least 'distance' pixels
386 * away from the boundary pixels in their set */
387 seld = selCreateBrick(2 * distance + 1, 2 * distance + 1,
388 distance, distance, SEL_HIT);
389 pixfg = pixErode(NULL, pixt2, seld);
390 pixbg = pixDilate(NULL, pixt2, seld);
391 pixInvert(pixbg, pixbg);
392 selDestroy(&seld);
393 pixDestroy(&pixt2);
394
395 /* Accumulate hit and miss points */
396 ptah = ptaCreate(0);
397 ptam = ptaCreate(0);
398 if (nhlines >= 1) {
399 delh = (l_float32)h / (l_float32)(nhlines + 1);
400 for (i = 0, y = 0; i < nhlines; i++) {
401 y += (l_int32)(delh + 0.5);
402 nah = pixGetRunCentersOnLine(pixfg, -1, y, minlength);
403 nam = pixGetRunCentersOnLine(pixbg, -1, y, minlength);
404 nh = numaGetCount(nah);
405 nm = numaGetCount(nam);
406 for (j = 0; j < nh; j++) {
407 numaGetIValue(nah, j, &xval);
408 ptaAddPt(ptah, xval, y);
409 }
410 for (j = 0; j < nm; j++) {
411 numaGetIValue(nam, j, &xval);
412 ptaAddPt(ptam, xval, y);
413 }
414 numaDestroy(&nah);
415 numaDestroy(&nam);
416 }
417 }
418 if (nvlines >= 1) {
419 delw = (l_float32)w / (l_float32)(nvlines + 1);
420 for (i = 0, x = 0; i < nvlines; i++) {
421 x += (l_int32)(delw + 0.5);
422 nah = pixGetRunCentersOnLine(pixfg, x, -1, minlength);
423 nam = pixGetRunCentersOnLine(pixbg, x, -1, minlength);
424 nh = numaGetCount(nah);
425 nm = numaGetCount(nam);
426 for (j = 0; j < nh; j++) {
427 numaGetIValue(nah, j, &yval);
428 ptaAddPt(ptah, x, yval);
429 }
430 for (j = 0; j < nm; j++) {
431 numaGetIValue(nam, j, &yval);
432 ptaAddPt(ptam, x, yval);
433 }
434 numaDestroy(&nah);
435 numaDestroy(&nam);
436 }
437 }
438
439 /* Make the Sel with those points */
440 sel = selCreateBrick(h, w, h / 2, w / 2, SEL_DONT_CARE);
441 nh = ptaGetCount(ptah);
442 for (i = 0; i < nh; i++) {
443 ptaGetIPt(ptah, i, &x, &y);
444 selSetElement(sel, y, x, SEL_HIT);
445 }
446 nm = ptaGetCount(ptam);
447 for (i = 0; i < nm; i++) {
448 ptaGetIPt(ptam, i, &x, &y);
449 selSetElement(sel, y, x, SEL_MISS);
450 }
451
452 pixDestroy(&pixfg);
453 pixDestroy(&pixbg);
454 ptaDestroy(&ptah);
455 ptaDestroy(&ptam);
456 return sel;
457 }
458
459
460 /*!
461 * \brief pixGenerateSelRandom()
462 *
463 * \param[in] pixs 1 bpp, typically small, to be used as a pattern
464 * \param[in] hitfract fraction of allowable fg pixels that are hits
465 * \param[in] missfract fraction of allowable bg pixels that are misses
466 * \param[in] distance min distance from boundary pixel; use 0 for default
467 * \param[in] toppix number of extra pixels of bg added above
468 * \param[in] botpix number of extra pixels of bg added below
469 * \param[in] leftpix number of extra pixels of bg added to left
470 * \param[in] rightpix number of extra pixels of bg added to right
471 * \param[out] ppixe [optional] input pix expanded by extra pixels
472 * \return sel hit-miss for input pattern, or NULL on error
473 *
474 * <pre>
475 * Notes:
476 * (1) Either of hitfract and missfract can be zero. If both are zero,
477 * the sel would be empty, and NULL is returned.
478 * (2) No elements are selected that are less than 'distance' pixels away
479 * from a boundary pixel of the same color. This makes the
480 * match much more robust to edge noise. Valid inputs of
481 * 'distance' are 0, 1, 2, 3 and 4. If distance is either 0 or
482 * greater than 4, we reset it to the default value.
483 * (3) The 4 numbers for adding rectangles of pixels outside the fg
484 * can be use if the pattern is expected to be surrounded by bg
485 * (white) pixels. On the other hand, if the pattern may be near
486 * other fg (black) components on some sides, use 0 for those sides.
487 * (4) The input pix, as extended by the extra pixels on selected sides,
488 * can optionally be returned. For debugging, call
489 * pixDisplayHitMissSel() to visualize the hit-miss sel superimposed
490 * on the generating bitmap.
491 * (5) This method is inferior to both the boundary and run based methods.
492 * </pre>
493 */
494 SEL *
495 pixGenerateSelRandom(PIX *pixs,
496 l_float32 hitfract,
497 l_float32 missfract,
498 l_int32 distance,
499 l_int32 toppix,
500 l_int32 botpix,
501 l_int32 leftpix,
502 l_int32 rightpix,
503 PIX **ppixe)
504 {
505 l_int32 ws, hs, w, h, x, y, i, j, thresh;
506 l_uint32 val;
507 PIX *pixt1, *pixt2, *pixfg, *pixbg;
508 SEL *seld, *sel;
509
510 if (ppixe) *ppixe = NULL;
511 if (!pixs)
512 return (SEL *)ERROR_PTR("pixs not defined", __func__, NULL);
513 if (pixGetDepth(pixs) != 1)
514 return (SEL *)ERROR_PTR("pixs not 1 bpp", __func__, NULL);
515 if (hitfract <= 0.0 && missfract <= 0.0)
516 return (SEL *)ERROR_PTR("no hits or misses", __func__, NULL);
517 if (hitfract > 1.0 || missfract > 1.0)
518 return (SEL *)ERROR_PTR("fraction can't be > 1.0", __func__, NULL);
519
520 if (distance <= 0)
521 distance = DefaultDistanceToBoundary;
522 if (distance > MaxDistanceToBoundary) {
523 L_WARNING("distance too large; setting to max value\n", __func__);
524 distance = MaxDistanceToBoundary;
525 }
526
527 /* Locate the foreground */
528 pixClipToForeground(pixs, &pixt1, NULL);
529 if (!pixt1)
530 return (SEL *)ERROR_PTR("pixt1 not made", __func__, NULL);
531 ws = pixGetWidth(pixt1);
532 hs = pixGetHeight(pixt1);
533 w = ws;
534 h = hs;
535
536 /* Crop out a region including the foreground, and add pixels
537 * on sides depending on the side flags */
538 if (toppix || botpix || leftpix || rightpix) {
539 x = y = 0;
540 if (toppix) {
541 h += toppix;
542 y = toppix;
543 }
544 if (botpix)
545 h += botpix;
546 if (leftpix) {
547 w += leftpix;
548 x = leftpix;
549 }
550 if (rightpix)
551 w += rightpix;
552 pixt2 = pixCreate(w, h, 1);
553 pixRasterop(pixt2, x, y, ws, hs, PIX_SRC, pixt1, 0, 0);
554 } else {
555 pixt2 = pixClone(pixt1);
556 }
557 if (ppixe)
558 *ppixe = pixClone(pixt2);
559 pixDestroy(&pixt1);
560
561 /* Identify fg and bg pixels that are at least 'distance' pixels
562 * away from the boundary pixels in their set */
563 seld = selCreateBrick(2 * distance + 1, 2 * distance + 1,
564 distance, distance, SEL_HIT);
565 pixfg = pixErode(NULL, pixt2, seld);
566 pixbg = pixDilate(NULL, pixt2, seld);
567 pixInvert(pixbg, pixbg);
568 selDestroy(&seld);
569 pixDestroy(&pixt2);
570
571 /* Generate the sel from a random selection of these points */
572 sel = selCreateBrick(h, w, h / 2, w / 2, SEL_DONT_CARE);
573 if (hitfract > 0.0) {
574 thresh = (l_int32)(hitfract * (l_float64)RAND_MAX);
575 for (i = 0; i < h; i++) {
576 for (j = 0; j < w; j++) {
577 pixGetPixel(pixfg, j, i, &val);
578 if (val) {
579 if (rand() < thresh)
580 selSetElement(sel, i, j, SEL_HIT);
581 }
582 }
583 }
584 }
585 if (missfract > 0.0) {
586 thresh = (l_int32)(missfract * (l_float64)RAND_MAX);
587 for (i = 0; i < h; i++) {
588 for (j = 0; j < w; j++) {
589 pixGetPixel(pixbg, j, i, &val);
590 if (val) {
591 if (rand() < thresh)
592 selSetElement(sel, i, j, SEL_MISS);
593 }
594 }
595 }
596 }
597
598 pixDestroy(&pixfg);
599 pixDestroy(&pixbg);
600 return sel;
601 }
602
603
604 /*-----------------------------------------------------------------*
605 * Accumulate data on runs along lines *
606 *-----------------------------------------------------------------*/
607 /*!
608 * \brief pixGetRunCentersOnLine()
609 *
610 * \param[in] pixs 1 bpp
611 * \param[in] x, y set one of these to -1; see notes
612 * \param[in] minlength minimum length of acceptable run
613 * \return numa of fg runs, or NULL on error
614 *
615 * <pre>
616 * Notes:
617 * (1) Action: this function computes the fg (black) and bg (white)
618 * pixel runlengths along the specified horizontal or vertical line,
619 * and returns a Numa of the "center" pixels of each fg run
620 * whose length equals or exceeds the minimum length.
621 * (2) This only works on horizontal and vertical lines.
622 * (3) For horizontal runs, set x = -1 and y to the value
623 * for all points along the raster line. For vertical runs,
624 * set y = -1 and x to the value for all points along the
625 * pixel column.
626 * (4) For horizontal runs, the points in the Numa are the x
627 * values in the center of fg runs that are of length at
628 * least 'minlength'. For vertical runs, the points in the
629 * Numa are the y values in the center of fg runs, again
630 * of length 'minlength' or greater.
631 * (5) If there are no fg runs along the line that satisfy the
632 * minlength constraint, the returned Numa is empty. This
633 * is not an error.
634 * </pre>
635 */
636 NUMA *
637 pixGetRunCentersOnLine(PIX *pixs,
638 l_int32 x,
639 l_int32 y,
640 l_int32 minlength)
641 {
642 l_int32 w, h, i, r, nruns, len;
643 NUMA *naruns, *nad;
644
645 if (!pixs)
646 return (NUMA *)ERROR_PTR("pixs not defined", __func__, NULL);
647 if (pixGetDepth(pixs) != 1)
648 return (NUMA *)ERROR_PTR("pixs not 1 bpp", __func__, NULL);
649 if (x != -1 && y != -1)
650 return (NUMA *)ERROR_PTR("x or y must be -1", __func__, NULL);
651 if (x == -1 && y == -1)
652 return (NUMA *)ERROR_PTR("x or y cannot both be -1", __func__, NULL);
653
654 if ((nad = numaCreate(0)) == NULL)
655 return (NUMA *)ERROR_PTR("nad not made", __func__, NULL);
656 w = pixGetWidth(pixs);
657 h = pixGetHeight(pixs);
658 if (x == -1) { /* horizontal run */
659 if (y < 0 || y >= h)
660 return nad;
661 naruns = pixGetRunsOnLine(pixs, 0, y, w - 1, y);
662 } else { /* vertical run */
663 if (x < 0 || x >= w)
664 return nad;
665 naruns = pixGetRunsOnLine(pixs, x, 0, x, h - 1);
666 }
667 nruns = numaGetCount(naruns);
668
669 /* extract run center values; the first run is always bg */
670 r = 0; /* cumulative distance along line */
671 for (i = 0; i < nruns; i++) {
672 if (i % 2 == 0) { /* bg run */
673 numaGetIValue(naruns, i, &len);
674 r += len;
675 continue;
676 } else {
677 numaGetIValue(naruns, i, &len);
678 if (len >= minlength)
679 numaAddNumber(nad, r + len / 2);
680 r += len;
681 }
682 }
683
684 numaDestroy(&naruns);
685 return nad;
686 }
687
688
689 /*!
690 * \brief pixGetRunsOnLine()
691 *
692 * \param[in] pixs 1 bpp
693 * \param[in] x1, y1, x2, y2
694 * \return numa, or NULL on error
695 *
696 * <pre>
697 * Notes:
698 * (1) Action: this function uses the bresenham algorithm to compute
699 * the pixels along the specified line. It returns a Numa of the
700 * runlengths of the fg (black) and bg (white) runs, always
701 * starting with a white run.
702 * (2) If the first pixel on the line is black, the length of the
703 * first returned run (which is white) is 0.
704 * </pre>
705 */
706 NUMA *
707 pixGetRunsOnLine(PIX *pixs,
708 l_int32 x1,
709 l_int32 y1,
710 l_int32 x2,
711 l_int32 y2)
712 {
713 l_int32 w, h, x, y, npts;
714 l_int32 i, runlen, preval;
715 l_uint32 val;
716 NUMA *numa;
717 PTA *pta;
718
719 if (!pixs)
720 return (NUMA *)ERROR_PTR("pixs not defined", __func__, NULL);
721 if (pixGetDepth(pixs) != 1)
722 return (NUMA *)ERROR_PTR("pixs not 1 bpp", __func__, NULL);
723
724 w = pixGetWidth(pixs);
725 h = pixGetHeight(pixs);
726 if (x1 < 0 || x1 >= w)
727 return (NUMA *)ERROR_PTR("x1 not valid", __func__, NULL);
728 if (x2 < 0 || x2 >= w)
729 return (NUMA *)ERROR_PTR("x2 not valid", __func__, NULL);
730 if (y1 < 0 || y1 >= h)
731 return (NUMA *)ERROR_PTR("y1 not valid", __func__, NULL);
732 if (y2 < 0 || y2 >= h)
733 return (NUMA *)ERROR_PTR("y2 not valid", __func__, NULL);
734
735 if ((pta = generatePtaLine(x1, y1, x2, y2)) == NULL)
736 return (NUMA *)ERROR_PTR("pta not made", __func__, NULL);
737 if ((npts = ptaGetCount(pta)) == 0) {
738 ptaDestroy(&pta);
739 return (NUMA *)ERROR_PTR("pta has no pts", __func__, NULL);
740 }
741 if ((numa = numaCreate(0)) == NULL) {
742 ptaDestroy(&pta);
743 return (NUMA *)ERROR_PTR("numa not made", __func__, NULL);
744 }
745
746 for (i = 0; i < npts; i++) {
747 ptaGetIPt(pta, i, &x, &y);
748 pixGetPixel(pixs, x, y, &val);
749 if (i == 0) {
750 if (val == 1) { /* black pixel; append white run of size 0 */
751 numaAddNumber(numa, 0);
752 }
753 preval = val;
754 runlen = 1;
755 continue;
756 }
757 if (val == preval) { /* extend current run */
758 preval = val;
759 runlen++;
760 } else { /* end previous run */
761 numaAddNumber(numa, runlen);
762 preval = val;
763 runlen = 1;
764 }
765 }
766 numaAddNumber(numa, runlen); /* append last run */
767
768 ptaDestroy(&pta);
769 return numa;
770 }
771
772
773 /*-----------------------------------------------------------------*
774 * Subsample boundary pixels in relatively ordered way *
775 *-----------------------------------------------------------------*/
776 /*!
777 * \brief pixSubsampleBoundaryPixels()
778 *
779 * \param[in] pixs 1 bpp, with only boundary pixels in fg
780 * \param[in] skip number to skip between samples as you traverse boundary
781 * \return pta, or NULL on error
782 *
783 * <pre>
784 * Notes:
785 * (1) If skip = 0, we take all the fg pixels.
786 * (2) We try to traverse the boundaries in a regular way.
787 * Some pixels may be missed, and these are then subsampled
788 * randomly with a fraction determined by 'skip'.
789 * (3) The most natural approach is to use a depth first (stack-based)
790 * method to find the fg pixels. However, the pixel runs are
791 * 4-connected and there are relatively few branches. So
792 * instead of doing a proper depth-first search, we get nearly
793 * the same result using two nested while loops: the outer
794 * one continues a raster-based search for the next fg pixel,
795 * and the inner one does a reasonable job running along
796 * each 4-connected coutour.
797 * </pre>
798 */
799 PTA *
800 pixSubsampleBoundaryPixels(PIX *pixs,
801 l_int32 skip)
802 {
803 l_int32 x, y, xn, yn, xs, ys, xa, ya, count;
804 PIX *pixt;
805 PTA *pta;
806
807 if (!pixs)
808 return (PTA *)ERROR_PTR("pixs not defined", __func__, NULL);
809 if (pixGetDepth(pixs) != 1)
810 return (PTA *)ERROR_PTR("pixs not 1 bpp", __func__, NULL);
811 if (skip < 0)
812 return (PTA *)ERROR_PTR("skip < 0", __func__, NULL);
813
814 if (skip == 0)
815 return ptaGetPixelsFromPix(pixs, NULL);
816
817 pta = ptaCreate(0);
818 pixt = pixCopy(NULL, pixs);
819 xs = ys = 0;
820 while (nextOnPixelInRaster(pixt, xs, ys, &xn, &yn)) { /* new series */
821 xs = xn;
822 ys = yn;
823
824 /* Add first point in this series */
825 ptaAddPt(pta, xs, ys);
826
827 /* Trace out boundary, erasing all and saving every (skip + 1)th */
828 x = xs;
829 y = ys;
830 pixSetPixel(pixt, x, y, 0);
831 count = 0;
832 while (adjacentOnPixelInRaster(pixt, x, y, &xa, &ya)) {
833 x = xa;
834 y = ya;
835 pixSetPixel(pixt, x, y, 0);
836 if (count == skip) {
837 ptaAddPt(pta, x, y);
838 count = 0;
839 } else {
840 count++;
841 }
842 }
843 }
844
845 pixDestroy(&pixt);
846 return pta;
847 }
848
849
850 /*!
851 * \brief adjacentOnPixelInRaster()
852 *
853 * \param[in] pixs 1 bpp
854 * \param[in] x, y current pixel
855 * \param[out] pxa, pya adjacent ON pixel, found by simple CCW search
856 * \return 1 if a pixel is found; 0 otherwise or on error
857 *
858 * <pre>
859 * Notes:
860 * (1) Search is in 4-connected directions first; then on diagonals.
861 * This allows traversal along a 4-connected boundary.
862 * </pre>
863 */
864 l_int32
865 adjacentOnPixelInRaster(PIX *pixs,
866 l_int32 x,
867 l_int32 y,
868 l_int32 *pxa,
869 l_int32 *pya)
870 {
871 l_int32 w, h, i, xa, ya, found;
872 l_int32 xdel[] = {-1, 0, 1, 0, -1, 1, 1, -1};
873 l_int32 ydel[] = {0, 1, 0, -1, 1, 1, -1, -1};
874 l_uint32 val;
875
876 if (!pixs)
877 return ERROR_INT("pixs not defined", __func__, 0);
878 if (pixGetDepth(pixs) != 1)
879 return ERROR_INT("pixs not 1 bpp", __func__, 0);
880 w = pixGetWidth(pixs);
881 h = pixGetHeight(pixs);
882 found = 0;
883 for (i = 0; i < 8; i++) {
884 xa = x + xdel[i];
885 ya = y + ydel[i];
886 if (xa < 0 || xa >= w || ya < 0 || ya >= h)
887 continue;
888 pixGetPixel(pixs, xa, ya, &val);
889 if (val == 1) {
890 found = 1;
891 *pxa = xa;
892 *pya = ya;
893 break;
894 }
895 }
896 return found;
897 }
898
899
900
901 /*-----------------------------------------------------------------*
902 * Display generated sel with originating image *
903 *-----------------------------------------------------------------*/
904 /*!
905 * \brief pixDisplayHitMissSel()
906 *
907 * \param[in] pixs 1 bpp
908 * \param[in] sel hit-miss in general
909 * \param[in] scalefactor an integer >= 1; use 0 for default
910 * \param[in] hitcolor RGB0 color for center of hit pixels
911 * \param[in] misscolor RGB0 color for center of miss pixels
912 * \return pixd RGB showing both pixs and sel, or NULL on error
913 * <pre>
914 * Notes:
915 * (1) We don't allow scalefactor to be larger than MaxSelScalefactor
916 * (2) The colors are conveniently given as 4 bytes in hex format,
917 * such as 0xff008800. The least significant byte is ignored.
918 * </pre>
919 */
920 PIX *
921 pixDisplayHitMissSel(PIX *pixs,
922 SEL *sel,
923 l_int32 scalefactor,
924 l_uint32 hitcolor,
925 l_uint32 misscolor)
926 {
927 l_int32 i, j, type;
928 l_float32 fscale;
929 PIX *pixt, *pixd;
930 PIXCMAP *cmap;
931
932 if (!pixs)
933 return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
934 if (pixGetDepth(pixs) != 1)
935 return (PIX *)ERROR_PTR("pixs not 1 bpp", __func__, NULL);
936 if (!sel)
937 return (PIX *)ERROR_PTR("sel not defined", __func__, NULL);
938
939 if (scalefactor <= 0)
940 scalefactor = DefaultSelScalefactor;
941 if (scalefactor > MaxSelScalefactor) {
942 L_WARNING("scalefactor too large; using max value\n", __func__);
943 scalefactor = MaxSelScalefactor;
944 }
945
946 /* Generate a version of pixs with a colormap */
947 pixt = pixConvert1To8(NULL, pixs, 0, 1);
948 cmap = pixcmapCreate(8);
949 pixcmapAddColor(cmap, 255, 255, 255);
950 pixcmapAddColor(cmap, 0, 0, 0);
951 pixcmapAddColor(cmap, hitcolor >> 24, (hitcolor >> 16) & 0xff,
952 (hitcolor >> 8) & 0xff);
953 pixcmapAddColor(cmap, misscolor >> 24, (misscolor >> 16) & 0xff,
954 (misscolor >> 8) & 0xff);
955 pixSetColormap(pixt, cmap);
956
957 /* Color the hits and misses */
958 for (i = 0; i < sel->sy; i++) {
959 for (j = 0; j < sel->sx; j++) {
960 selGetElement(sel, i, j, &type);
961 if (type == SEL_DONT_CARE)
962 continue;
963 if (type == SEL_HIT)
964 pixSetPixel(pixt, j, i, 2);
965 else /* type == SEL_MISS */
966 pixSetPixel(pixt, j, i, 3);
967 }
968 }
969
970 /* Scale it up */
971 fscale = (l_float32)scalefactor;
972 pixd = pixScaleBySampling(pixt, fscale, fscale);
973
974 pixDestroy(&pixt);
975 return pixd;
976 }