Leptonica 1.83.1
Image processing and image analysis suite
Loading...
Searching...
No Matches
seedfill.c
Go to the documentation of this file.
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
166
167#ifdef HAVE_CONFIG_H
168#include <config_auto.h>
169#endif /* HAVE_CONFIG_H */
170
171#include <math.h>
172#include "allheaders.h"
173
174struct L_Pixel
175{
176 l_int32 x;
177 l_int32 y;
178};
179typedef struct L_Pixel L_PIXEL;
180
181static void seedfillBinaryLow(l_uint32 *datas, l_int32 hs, l_int32 wpls,
182 l_uint32 *datam, l_int32 hm, l_int32 wplm,
183 l_int32 connectivity);
184static void seedfillGrayLow(l_uint32 *datas, l_int32 w, l_int32 h,
185 l_int32 wpls, l_uint32 *datam, l_int32 wplm,
186 l_int32 connectivity);
187static void seedfillGrayInvLow(l_uint32 *datas, l_int32 w, l_int32 h,
188 l_int32 wpls, l_uint32 *datam, l_int32 wplm,
189 l_int32 connectivity);
190static void seedfillGrayLowSimple(l_uint32 *datas, l_int32 w, l_int32 h,
191 l_int32 wpls, l_uint32 *datam, l_int32 wplm,
192 l_int32 connectivity);
193static void seedfillGrayInvLowSimple(l_uint32 *datas, l_int32 w, l_int32 h,
194 l_int32 wpls, l_uint32 *datam,
195 l_int32 wplm, l_int32 connectivity);
196static void distanceFunctionLow(l_uint32 *datad, l_int32 w, l_int32 h,
197 l_int32 d, l_int32 wpld, l_int32 connectivity);
198static void seedspreadLow(l_uint32 *datad, l_int32 w, l_int32 h, l_int32 wpld,
199 l_uint32 *datat, l_int32 wplt, l_int32 connectivity);
200
201
202static l_int32 pixQualifyLocalMinima(PIX *pixs, PIX *pixm, l_int32 maxval);
203
204#ifndef NO_CONSOLE_IO
205#define DEBUG_PRINT_ITERS 0
206#endif /* ~NO_CONSOLE_IO */
207
208 /* Two-way (UL --> LR, LR --> UL) sweep iterations; typically need only 4 */
209static const l_int32 MaxIters = 40;
210
211
212/*-----------------------------------------------------------------------*
213 * Vincent's Iterative Binary Seedfill method *
214 *-----------------------------------------------------------------------*/
246PIX *
247pixSeedfillBinary(PIX *pixd,
248 PIX *pixs,
249 PIX *pixm,
250 l_int32 connectivity)
251{
252l_int32 i, boolval;
253l_int32 hd, hm, wpld, wplm;
254l_uint32 *datad, *datam;
255PIX *pixt;
256
257 if (!pixs || pixGetDepth(pixs) != 1)
258 return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", __func__, pixd);
259 if (!pixm || pixGetDepth(pixm) != 1)
260 return (PIX *)ERROR_PTR("pixm undefined or not 1 bpp", __func__, pixd);
261 if (connectivity != 4 && connectivity != 8)
262 return (PIX *)ERROR_PTR("connectivity not in {4,8}", __func__, pixd);
263
264 /* Prepare pixd as a copy of pixs if not identical */
265 if ((pixd = pixCopy(pixd, pixs)) == NULL)
266 return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
267 pixSetPadBits(pixd, 0); /* be safe: */
268 pixSetPadBits(pixm, 0); /* avoid using uninitialized memory */
269
270 /* pixt is used to test for completion */
271 if ((pixt = pixCreateTemplate(pixs)) == NULL)
272 return (PIX *)ERROR_PTR("pixt not made", __func__, pixd);
273
274 hd = pixGetHeight(pixd);
275 hm = pixGetHeight(pixm); /* included so seedfillBinaryLow() can clip */
276 datad = pixGetData(pixd);
277 datam = pixGetData(pixm);
278 wpld = pixGetWpl(pixd);
279 wplm = pixGetWpl(pixm);
280
281
282 for (i = 0; i < MaxIters; i++) {
283 pixCopy(pixt, pixd);
284 seedfillBinaryLow(datad, hd, wpld, datam, hm, wplm, connectivity);
285 pixEqual(pixd, pixt, &boolval);
286 if (boolval == 1) {
287#if DEBUG_PRINT_ITERS
288 lept_stderr("Binary seed fill converged: %d iters\n", i + 1);
289#endif /* DEBUG_PRINT_ITERS */
290 break;
291 }
292 }
293
294 pixDestroy(&pixt);
295 return pixd;
296}
297
298
332PIX *
333pixSeedfillBinaryRestricted(PIX *pixd,
334 PIX *pixs,
335 PIX *pixm,
336 l_int32 connectivity,
337 l_int32 xmax,
338 l_int32 ymax)
339{
340l_int32 w, h;
341PIX *pix1, *pix2;
342
343 if (!pixs || pixGetDepth(pixs) != 1)
344 return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", __func__, pixd);
345 if (!pixm || pixGetDepth(pixm) != 1)
346 return (PIX *)ERROR_PTR("pixm undefined or not 1 bpp", __func__, pixd);
347 if (connectivity != 4 && connectivity != 8)
348 return (PIX *)ERROR_PTR("connectivity not in {4,8}", __func__, pixd);
349 if (xmax == 0 && ymax == 0) /* no filling permitted */
350 return pixClone(pixs);
351 if (xmax < 0 || ymax < 0) {
352 L_ERROR("xmax and ymax must be non-negative", __func__);
353 return pixClone(pixs);
354 }
355
356 /* Full fill from the seed into the mask. */
357 if ((pix1 = pixSeedfillBinary(NULL, pixs, pixm, connectivity)) == NULL)
358 return (PIX *)ERROR_PTR("pix1 not made", __func__, pixd);
359
360 /* Dilate the seed. This gives the maximal region where changes
361 * are permitted. Invert to get the region where pixs is
362 * not allowed to change. */
363 pix2 = pixDilateCompBrick(NULL, pixs, 2 * xmax + 1, 2 * ymax + 1);
364 pixInvert(pix2, pix2);
365
366 /* Blank the region of pix1 specified by the fg of pix2.
367 * This is not yet the final result, because it may have fg pixels
368 * that are not accessible from the seed in the restricted distance.
369 * For example, such pixels may be connected to the original seed,
370 * but through a path that goes outside the permitted region. */
371 pixGetDimensions(pixs, &w, &h, NULL);
372 pixRasterop(pix1, 0, 0, w, h, PIX_DST & PIX_NOT(PIX_SRC), pix2, 0, 0);
373
374 /* To get the accessible pixels in the restricted region, do
375 * a second seedfill from the original seed, using pix1 as
376 * a mask. The result, in pixd, will not have any bad fg
377 * pixels that were in pix1. */
378 pixd = pixSeedfillBinary(pixd, pixs, pix1, connectivity);
379
380 pixDestroy(&pix1);
381 pixDestroy(&pix2);
382 return pixd;
383}
384
385
398static void
399seedfillBinaryLow(l_uint32 *datas,
400 l_int32 hs,
401 l_int32 wpls,
402 l_uint32 *datam,
403 l_int32 hm,
404 l_int32 wplm,
405 l_int32 connectivity)
406{
407l_int32 i, j, h, wpl;
408l_uint32 word, mask;
409l_uint32 wordabove, wordleft, wordbelow, wordright;
410l_uint32 wordprev; /* test against this in previous iteration */
411l_uint32 *lines, *linem;
412
413 h = L_MIN(hs, hm);
414 wpl = L_MIN(wpls, wplm);
415
416 switch (connectivity)
417 {
418 case 4:
419 /* UL --> LR scan */
420 for (i = 0; i < h; i++) {
421 lines = datas + i * wpls;
422 linem = datam + i * wplm;
423 for (j = 0; j < wpl; j++) {
424 word = *(lines + j);
425 mask = *(linem + j);
426
427 /* OR from word above and from word to left; mask */
428 if (i > 0) {
429 wordabove = *(lines - wpls + j);
430 word |= wordabove;
431 }
432 if (j > 0) {
433 wordleft = *(lines + j - 1);
434 word |= wordleft << 31;
435 }
436 word &= mask;
437
438 /* No need to fill horizontally? */
439 if (!word || !(~word)) {
440 *(lines + j) = word;
441 continue;
442 }
443
444 while (1) {
445 wordprev = word;
446 word = (word | (word >> 1) | (word << 1)) & mask;
447 if ((word ^ wordprev) == 0) {
448 *(lines + j) = word;
449 break;
450 }
451 }
452 }
453 }
454
455 /* LR --> UL scan */
456 for (i = h - 1; i >= 0; i--) {
457 lines = datas + i * wpls;
458 linem = datam + i * wplm;
459 for (j = wpl - 1; j >= 0; j--) {
460 word = *(lines + j);
461 mask = *(linem + j);
462
463 /* OR from word below and from word to right; mask */
464 if (i < h - 1) {
465 wordbelow = *(lines + wpls + j);
466 word |= wordbelow;
467 }
468 if (j < wpl - 1) {
469 wordright = *(lines + j + 1);
470 word |= wordright >> 31;
471 }
472 word &= mask;
473
474 /* No need to fill horizontally? */
475 if (!word || !(~word)) {
476 *(lines + j) = word;
477 continue;
478 }
479
480 while (1) {
481 wordprev = word;
482 word = (word | (word >> 1) | (word << 1)) & mask;
483 if ((word ^ wordprev) == 0) {
484 *(lines + j) = word;
485 break;
486 }
487 }
488 }
489 }
490 break;
491
492 case 8:
493 /* UL --> LR scan */
494 for (i = 0; i < h; i++) {
495 lines = datas + i * wpls;
496 linem = datam + i * wplm;
497 for (j = 0; j < wpl; j++) {
498 word = *(lines + j);
499 mask = *(linem + j);
500
501 /* OR from words above and from word to left; mask */
502 if (i > 0) {
503 wordabove = *(lines - wpls + j);
504 word |= (wordabove | (wordabove << 1) | (wordabove >> 1));
505 if (j > 0)
506 word |= (*(lines - wpls + j - 1)) << 31;
507 if (j < wpl - 1)
508 word |= (*(lines - wpls + j + 1)) >> 31;
509 }
510 if (j > 0) {
511 wordleft = *(lines + j - 1);
512 word |= wordleft << 31;
513 }
514 word &= mask;
515
516 /* No need to fill horizontally? */
517 if (!word || !(~word)) {
518 *(lines + j) = word;
519 continue;
520 }
521
522 while (1) {
523 wordprev = word;
524 word = (word | (word >> 1) | (word << 1)) & mask;
525 if ((word ^ wordprev) == 0) {
526 *(lines + j) = word;
527 break;
528 }
529 }
530 }
531 }
532
533 /* LR --> UL scan */
534 for (i = h - 1; i >= 0; i--) {
535 lines = datas + i * wpls;
536 linem = datam + i * wplm;
537 for (j = wpl - 1; j >= 0; j--) {
538 word = *(lines + j);
539 mask = *(linem + j);
540
541 /* OR from words below and from word to right; mask */
542 if (i < h - 1) {
543 wordbelow = *(lines + wpls + j);
544 word |= (wordbelow | (wordbelow << 1) | (wordbelow >> 1));
545 if (j > 0)
546 word |= (*(lines + wpls + j - 1)) << 31;
547 if (j < wpl - 1)
548 word |= (*(lines + wpls + j + 1)) >> 31;
549 }
550 if (j < wpl - 1) {
551 wordright = *(lines + j + 1);
552 word |= wordright >> 31;
553 }
554 word &= mask;
555
556 /* No need to fill horizontally? */
557 if (!word || !(~word)) {
558 *(lines + j) = word;
559 continue;
560 }
561
562 while (1) {
563 wordprev = word;
564 word = (word | (word >> 1) | (word << 1)) & mask;
565 if ((word ^ wordprev) == 0) {
566 *(lines + j) = word;
567 break;
568 }
569 }
570 }
571 }
572 break;
573
574 default:
575 L_ERROR("connectivity must be 4 or 8\n", __func__);
576 }
577}
578
579
602PIX *
603pixHolesByFilling(PIX *pixs,
604 l_int32 connectivity)
605{
606PIX *pixsi, *pixd;
607
608 if (!pixs || pixGetDepth(pixs) != 1)
609 return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", __func__, NULL);
610 if (connectivity != 4 && connectivity != 8)
611 return (PIX *)ERROR_PTR("connectivity not 4 or 8", __func__, NULL);
612
613 if ((pixd = pixCreateTemplate(pixs)) == NULL)
614 return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
615 if ((pixsi = pixInvert(NULL, pixs)) == NULL) {
616 pixDestroy(&pixd);
617 return (PIX *)ERROR_PTR("pixsi not made", __func__, NULL);
618 }
619
620 pixSetOrClearBorder(pixd, 1, 1, 1, 1, PIX_SET);
621 pixSeedfillBinary(pixd, pixd, pixsi, connectivity);
622 pixOr(pixd, pixd, pixs);
623 pixInvert(pixd, pixd);
624 pixDestroy(&pixsi);
625 return pixd;
626}
627
628
651PIX *
652pixFillClosedBorders(PIX *pixs,
653 l_int32 connectivity)
654{
655PIX *pixsi, *pixd;
656
657 if (!pixs || pixGetDepth(pixs) != 1)
658 return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", __func__, NULL);
659 if (connectivity != 4 && connectivity != 8)
660 return (PIX *)ERROR_PTR("connectivity not 4 or 8", __func__, NULL);
661
662 if ((pixd = pixCreateTemplate(pixs)) == NULL)
663 return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
664 pixSetOrClearBorder(pixd, 1, 1, 1, 1, PIX_SET);
665 pixSubtract(pixd, pixd, pixs);
666 if ((pixsi = pixInvert(NULL, pixs)) == NULL) {
667 pixDestroy(&pixd);
668 return (PIX *)ERROR_PTR("pixsi not made", __func__, NULL);
669 }
670
671 pixSeedfillBinary(pixd, pixd, pixsi, connectivity);
672 pixInvert(pixd, pixd);
673 pixDestroy(&pixsi);
674
675 return pixd;
676}
677
678
687PIX *
688pixExtractBorderConnComps(PIX *pixs,
689 l_int32 connectivity)
690{
691PIX *pixd;
692
693 if (!pixs || pixGetDepth(pixs) != 1)
694 return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", __func__, NULL);
695 if (connectivity != 4 && connectivity != 8)
696 return (PIX *)ERROR_PTR("connectivity not 4 or 8", __func__, NULL);
697
698 /* Start with 1 pixel wide black border as seed in pixd */
699 if ((pixd = pixCreateTemplate(pixs)) == NULL)
700 return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
701 pixSetOrClearBorder(pixd, 1, 1, 1, 1, PIX_SET);
702
703 /* Fill in pixd from the seed, using pixs as the filling mask.
704 * This fills all components from pixs that are touching the border. */
705 pixSeedfillBinary(pixd, pixd, pixs, connectivity);
706
707 return pixd;
708}
709
710
724PIX *
725pixRemoveBorderConnComps(PIX *pixs,
726 l_int32 connectivity)
727{
728PIX *pixd;
729
730 if (!pixs || pixGetDepth(pixs) != 1)
731 return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", __func__, NULL);
732 if (connectivity != 4 && connectivity != 8)
733 return (PIX *)ERROR_PTR("connectivity not 4 or 8", __func__, NULL);
734
735 /* Fill from a 1 pixel wide seed at the border into all components
736 * in pixs (the filling mask) that are touching the border */
737 pixd = pixExtractBorderConnComps(pixs, connectivity);
738
739 /* Save in pixd only those components in pixs not touching the border */
740 pixXor(pixd, pixd, pixs);
741 return pixd;
742}
743
744
772PIX *
773pixFillBgFromBorder(PIX *pixs,
774 l_int32 connectivity)
775{
776PIX *pixd;
777
778 if (!pixs || pixGetDepth(pixs) != 1)
779 return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", __func__, NULL);
780 if (connectivity != 4 && connectivity != 8)
781 return (PIX *)ERROR_PTR("connectivity not 4 or 8", __func__, NULL);
782
783 /* Invert to turn bg touching the border to a fg component.
784 * Extract this by filling from a 1 pixel wide seed at the border. */
785 pixInvert(pixs, pixs);
786 pixd = pixExtractBorderConnComps(pixs, connectivity);
787 pixInvert(pixs, pixs); /* restore pixs */
788
789 /* Bit-or the filled bg component with pixs */
790 pixOr(pixd, pixd, pixs);
791 return pixd;
792}
793
794
795/*-----------------------------------------------------------------------*
796 * Hole-filling of components to bounding rectangle *
797 *-----------------------------------------------------------------------*/
830PIX *
831pixFillHolesToBoundingRect(PIX *pixs,
832 l_int32 minsize,
833 l_float32 maxhfract,
834 l_float32 minfgfract)
835{
836l_int32 i, x, y, w, h, n, nfg, nh, ntot, area;
837l_int32 *tab;
838l_float32 hfract; /* measured hole fraction */
839l_float32 fgfract; /* measured fg fraction */
840BOXA *boxa;
841PIX *pixd, *pixfg, *pixh;
842PIXA *pixa;
843
844 if (!pixs || pixGetDepth(pixs) != 1)
845 return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", __func__, NULL);
846 maxhfract = L_MIN(L_MAX(maxhfract, 0.0), 1.0);
847 minfgfract = L_MIN(L_MAX(minfgfract, 0.0), 1.0);
848
849 pixd = pixCopy(NULL, pixs);
850 boxa = pixConnComp(pixd, &pixa, 8);
851 n = boxaGetCount(boxa);
852 tab = makePixelSumTab8();
853 for (i = 0; i < n; i++) {
854 boxaGetBoxGeometry(boxa, i, &x, &y, &w, &h);
855 area = w * h;
856 if (area < minsize)
857 continue;
858 pixfg = pixaGetPix(pixa, i, L_COPY);
859 pixh = pixHolesByFilling(pixfg, 4); /* holes only */
860 pixCountPixels(pixfg, &nfg, tab);
861 pixCountPixels(pixh, &nh, tab);
862 hfract = (l_float32)nh / (l_float32)nfg;
863 ntot = nfg;
864 if (hfract <= maxhfract) /* we will fill the holes (at least) */
865 ntot = nfg + nh;
866 fgfract = (l_float32)ntot / (l_float32)area;
867 if (fgfract >= minfgfract) { /* fill to bounding rect */
868 pixSetAll(pixfg);
869 pixRasterop(pixd, x, y, w, h, PIX_SRC, pixfg, 0, 0);
870 } else if (hfract <= maxhfract) { /* fill just the holes */
871 pixRasterop(pixd, x, y, w, h, PIX_DST | PIX_SRC , pixh, 0, 0);
872 }
873 pixDestroy(&pixfg);
874 pixDestroy(&pixh);
875 }
876 boxaDestroy(&boxa);
877 pixaDestroy(&pixa);
878 LEPT_FREE(tab);
879 return pixd;
880}
881
882
883/*-----------------------------------------------------------------------*
884 * Vincent's hybrid Grayscale Seedfill method *
885 *-----------------------------------------------------------------------*/
910l_ok
911pixSeedfillGray(PIX *pixs,
912 PIX *pixm,
913 l_int32 connectivity)
914{
915l_int32 h, w, wpls, wplm;
916l_uint32 *datas, *datam;
917
918 if (!pixs || pixGetDepth(pixs) != 8)
919 return ERROR_INT("pixs not defined or not 8 bpp", __func__, 1);
920 if (!pixm || pixGetDepth(pixm) != 8)
921 return ERROR_INT("pixm not defined or not 8 bpp", __func__, 1);
922 if (connectivity != 4 && connectivity != 8)
923 return ERROR_INT("connectivity not in {4,8}", __func__, 1);
924
925 /* Make sure the sizes of seed and mask images are the same */
926 if (pixSizesEqual(pixs, pixm) == 0)
927 return ERROR_INT("pixs and pixm sizes differ", __func__, 1);
928
929 datas = pixGetData(pixs);
930 datam = pixGetData(pixm);
931 wpls = pixGetWpl(pixs);
932 wplm = pixGetWpl(pixm);
933 pixGetDimensions(pixs, &w, &h, NULL);
934 seedfillGrayLow(datas, w, h, wpls, datam, wplm, connectivity);
935
936 return 0;
937}
938
939
967l_ok
968pixSeedfillGrayInv(PIX *pixs,
969 PIX *pixm,
970 l_int32 connectivity)
971{
972l_int32 h, w, wpls, wplm;
973l_uint32 *datas, *datam;
974
975 if (!pixs || pixGetDepth(pixs) != 8)
976 return ERROR_INT("pixs not defined or not 8 bpp", __func__, 1);
977 if (!pixm || pixGetDepth(pixm) != 8)
978 return ERROR_INT("pixm not defined or not 8 bpp", __func__, 1);
979 if (connectivity != 4 && connectivity != 8)
980 return ERROR_INT("connectivity not in {4,8}", __func__, 1);
981
982 /* Make sure the sizes of seed and mask images are the same */
983 if (pixSizesEqual(pixs, pixm) == 0)
984 return ERROR_INT("pixs and pixm sizes differ", __func__, 1);
985
986 datas = pixGetData(pixs);
987 datam = pixGetData(pixm);
988 wpls = pixGetWpl(pixs);
989 wplm = pixGetWpl(pixm);
990 pixGetDimensions(pixs, &w, &h, NULL);
991 seedfillGrayInvLow(datas, w, h, wpls, datam, wplm, connectivity);
992
993 return 0;
994}
995
996
1042static void
1043seedfillGrayLow(l_uint32 *datas,
1044 l_int32 w,
1045 l_int32 h,
1046 l_int32 wpls,
1047 l_uint32 *datam,
1048 l_int32 wplm,
1049 l_int32 connectivity)
1050{
1051l_uint8 val1, val2, val3, val4, val5, val6, val7, val8;
1052l_uint8 val, maxval, maskval, boolval;
1053l_int32 i, j, imax, jmax, queue_size;
1054l_uint32 *lines, *linem;
1055L_PIXEL *pixel;
1056L_QUEUE *lq_pixel;
1057
1058 if (connectivity != 4 && connectivity != 8) {
1059 L_ERROR("connectivity must be 4 or 8\n", __func__);
1060 return;
1061 }
1062
1063 imax = h - 1;
1064 jmax = w - 1;
1065
1066 /* In the worst case, most of the pixels could be pushed
1067 * onto the FIFO queue during anti-raster scan. However this
1068 * will rarely happen, and we initialize the queue ptr size to
1069 * the image perimeter. */
1070 lq_pixel = lqueueCreate(2 * (w + h));
1071
1072 switch (connectivity)
1073 {
1074 case 4:
1075 /* UL --> LR scan (Raster Order)
1076 * If I : mask image
1077 * J : marker image
1078 * Let p be the currect pixel;
1079 * J(p) <- (max{J(p) union J(p) neighbors in raster order})
1080 * intersection I(p) */
1081 for (i = 0; i < h; i++) {
1082 lines = datas + i * wpls;
1083 linem = datam + i * wplm;
1084 for (j = 0; j < w; j++) {
1085 if ((maskval = GET_DATA_BYTE(linem, j)) > 0) {
1086 maxval = 0;
1087 if (i > 0)
1088 maxval = GET_DATA_BYTE(lines - wpls, j);
1089 if (j > 0) {
1090 val4 = GET_DATA_BYTE(lines, j - 1);
1091 maxval = L_MAX(maxval, val4);
1092 }
1093 val = GET_DATA_BYTE(lines, j);
1094 maxval = L_MAX(maxval, val);
1095 val = L_MIN(maxval, maskval);
1096 SET_DATA_BYTE(lines, j, val);
1097 }
1098 }
1099 }
1100
1101 /* LR --> UL scan (anti-raster order)
1102 * Let p be the currect pixel;
1103 * J(p) <- (max{J(p) union J(p) neighbors in anti-raster order})
1104 * intersection I(p) */
1105 for (i = imax; i >= 0; i--) {
1106 lines = datas + i * wpls;
1107 linem = datam + i * wplm;
1108 for (j = jmax; j >= 0; j--) {
1109 boolval = FALSE;
1110 if ((maskval = GET_DATA_BYTE(linem, j)) > 0) {
1111 maxval = 0;
1112 if (i < imax)
1113 maxval = GET_DATA_BYTE(lines + wpls, j);
1114 if (j < jmax) {
1115 val5 = GET_DATA_BYTE(lines, j + 1);
1116 maxval = L_MAX(maxval, val5);
1117 }
1118 val = GET_DATA_BYTE(lines, j);
1119 maxval = L_MAX(maxval, val);
1120 val = L_MIN(maxval, maskval);
1121 SET_DATA_BYTE(lines, j, val);
1122
1123 /*
1124 * If there exists a point (q) which belongs to J(p)
1125 * neighbors in anti-raster order such that J(q) < J(p)
1126 * and J(q) < I(q) then
1127 * fifo_add(p) */
1128 if (i < imax) {
1129 val7 = GET_DATA_BYTE(lines + wpls, j);
1130 if ((val7 < val) &&
1131 (val7 < GET_DATA_BYTE(linem + wplm, j))) {
1132 boolval = TRUE;
1133 }
1134 }
1135 if (j < jmax) {
1136 val5 = GET_DATA_BYTE(lines, j + 1);
1137 if (!boolval && (val5 < val) &&
1138 (val5 < GET_DATA_BYTE(linem, j + 1))) {
1139 boolval = TRUE;
1140 }
1141 }
1142 if (boolval) {
1143 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1144 pixel->x = i;
1145 pixel->y = j;
1146 lqueueAdd(lq_pixel, pixel);
1147 }
1148 }
1149 }
1150 }
1151
1152 /* Propagation step:
1153 * while fifo_empty = false
1154 * p <- fifo_first()
1155 * for every pixel (q) belong to neighbors of (p)
1156 * if J(q) < J(p) and I(q) != J(q)
1157 * J(q) <- min(J(p), I(q));
1158 * fifo_add(q);
1159 * end
1160 * end
1161 * end */
1162 queue_size = lqueueGetCount(lq_pixel);
1163 while (queue_size) {
1164 pixel = (L_PIXEL *)lqueueRemove(lq_pixel);
1165 i = pixel->x;
1166 j = pixel->y;
1167 LEPT_FREE(pixel);
1168 lines = datas + i * wpls;
1169 linem = datam + i * wplm;
1170
1171 if ((val = GET_DATA_BYTE(lines, j)) > 0) {
1172 if (i > 0) {
1173 val2 = GET_DATA_BYTE(lines - wpls, j);
1174 maskval = GET_DATA_BYTE(linem - wplm, j);
1175 if (val > val2 && val2 != maskval) {
1176 SET_DATA_BYTE(lines - wpls, j, L_MIN(val, maskval));
1177 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1178 pixel->x = i - 1;
1179 pixel->y = j;
1180 lqueueAdd(lq_pixel, pixel);
1181 }
1182
1183 }
1184 if (j > 0) {
1185 val4 = GET_DATA_BYTE(lines, j - 1);
1186 maskval = GET_DATA_BYTE(linem, j - 1);
1187 if (val > val4 && val4 != maskval) {
1188 SET_DATA_BYTE(lines, j - 1, L_MIN(val, maskval));
1189 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1190 pixel->x = i;
1191 pixel->y = j - 1;
1192 lqueueAdd(lq_pixel, pixel);
1193 }
1194 }
1195 if (i < imax) {
1196 val7 = GET_DATA_BYTE(lines + wpls, j);
1197 maskval = GET_DATA_BYTE(linem + wplm, j);
1198 if (val > val7 && val7 != maskval) {
1199 SET_DATA_BYTE(lines + wpls, j, L_MIN(val, maskval));
1200 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1201 pixel->x = i + 1;
1202 pixel->y = j;
1203 lqueueAdd(lq_pixel, pixel);
1204 }
1205 }
1206 if (j < jmax) {
1207 val5 = GET_DATA_BYTE(lines, j + 1);
1208 maskval = GET_DATA_BYTE(linem, j + 1);
1209 if (val > val5 && val5 != maskval) {
1210 SET_DATA_BYTE(lines, j + 1, L_MIN(val, maskval));
1211 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1212 pixel->x = i;
1213 pixel->y = j + 1;
1214 lqueueAdd(lq_pixel, pixel);
1215 }
1216 }
1217 }
1218
1219 queue_size = lqueueGetCount(lq_pixel);
1220 }
1221 break;
1222
1223 case 8:
1224 /* UL --> LR scan (Raster Order)
1225 * If I : mask image
1226 * J : marker image
1227 * Let p be the currect pixel;
1228 * J(p) <- (max{J(p) union J(p) neighbors in raster order})
1229 * intersection I(p) */
1230 for (i = 0; i < h; i++) {
1231 lines = datas + i * wpls;
1232 linem = datam + i * wplm;
1233 for (j = 0; j < w; j++) {
1234 if ((maskval = GET_DATA_BYTE(linem, j)) > 0) {
1235 maxval = 0;
1236 if (i > 0) {
1237 if (j > 0)
1238 maxval = GET_DATA_BYTE(lines - wpls, j - 1);
1239 if (j < jmax) {
1240 val3 = GET_DATA_BYTE(lines - wpls, j + 1);
1241 maxval = L_MAX(maxval, val3);
1242 }
1243 val2 = GET_DATA_BYTE(lines - wpls, j);
1244 maxval = L_MAX(maxval, val2);
1245 }
1246 if (j > 0) {
1247 val4 = GET_DATA_BYTE(lines, j - 1);
1248 maxval = L_MAX(maxval, val4);
1249 }
1250 val = GET_DATA_BYTE(lines, j);
1251 maxval = L_MAX(maxval, val);
1252 val = L_MIN(maxval, maskval);
1253 SET_DATA_BYTE(lines, j, val);
1254 }
1255 }
1256 }
1257
1258 /* LR --> UL scan (anti-raster order)
1259 * Let p be the currect pixel;
1260 * J(p) <- (max{J(p) union J(p) neighbors in anti-raster order})
1261 * intersection I(p) */
1262 for (i = imax; i >= 0; i--) {
1263 lines = datas + i * wpls;
1264 linem = datam + i * wplm;
1265 for (j = jmax; j >= 0; j--) {
1266 boolval = FALSE;
1267 if ((maskval = GET_DATA_BYTE(linem, j)) > 0) {
1268 maxval = 0;
1269 if (i < imax) {
1270 if (j > 0) {
1271 maxval = GET_DATA_BYTE(lines + wpls, j - 1);
1272 }
1273 if (j < jmax) {
1274 val8 = GET_DATA_BYTE(lines + wpls, j + 1);
1275 maxval = L_MAX(maxval, val8);
1276 }
1277 val7 = GET_DATA_BYTE(lines + wpls, j);
1278 maxval = L_MAX(maxval, val7);
1279 }
1280 if (j < jmax) {
1281 val5 = GET_DATA_BYTE(lines, j + 1);
1282 maxval = L_MAX(maxval, val5);
1283 }
1284 val = GET_DATA_BYTE(lines, j);
1285 maxval = L_MAX(maxval, val);
1286 val = L_MIN(maxval, maskval);
1287 SET_DATA_BYTE(lines, j, val);
1288
1289 /* If there exists a point (q) which belongs to J(p)
1290 * neighbors in anti-raster order such that J(q) < J(p)
1291 * and J(q) < I(q) then
1292 * fifo_add(p) */
1293 if (i < imax) {
1294 if (j > 0) {
1295 val6 = GET_DATA_BYTE(lines + wpls, j - 1);
1296 if ((val6 < val) &&
1297 (val6 < GET_DATA_BYTE(linem + wplm, j - 1))) {
1298 boolval = TRUE;
1299 }
1300 }
1301 if (j < jmax) {
1302 val8 = GET_DATA_BYTE(lines + wpls, j + 1);
1303 if (!boolval && (val8 < val) &&
1304 (val8 < GET_DATA_BYTE(linem + wplm, j + 1))) {
1305 boolval = TRUE;
1306 }
1307 }
1308 val7 = GET_DATA_BYTE(lines + wpls, j);
1309 if (!boolval && (val7 < val) &&
1310 (val7 < GET_DATA_BYTE(linem + wplm, j))) {
1311 boolval = TRUE;
1312 }
1313 }
1314 if (j < jmax) {
1315 val5 = GET_DATA_BYTE(lines, j + 1);
1316 if (!boolval && (val5 < val) &&
1317 (val5 < GET_DATA_BYTE(linem, j + 1))) {
1318 boolval = TRUE;
1319 }
1320 }
1321 if (boolval) {
1322 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1323 pixel->x = i;
1324 pixel->y = j;
1325 lqueueAdd(lq_pixel, pixel);
1326 }
1327 }
1328 }
1329 }
1330
1331 /* Propagation step:
1332 * while fifo_empty = false
1333 * p <- fifo_first()
1334 * for every pixel (q) belong to neighbors of (p)
1335 * if J(q) < J(p) and I(q) != J(q)
1336 * J(q) <- min(J(p), I(q));
1337 * fifo_add(q);
1338 * end
1339 * end
1340 * end */
1341 queue_size = lqueueGetCount(lq_pixel);
1342 while (queue_size) {
1343 pixel = (L_PIXEL *)lqueueRemove(lq_pixel);
1344 i = pixel->x;
1345 j = pixel->y;
1346 LEPT_FREE(pixel);
1347 lines = datas + i * wpls;
1348 linem = datam + i * wplm;
1349
1350 if ((val = GET_DATA_BYTE(lines, j)) > 0) {
1351 if (i > 0) {
1352 if (j > 0) {
1353 val1 = GET_DATA_BYTE(lines - wpls, j - 1);
1354 maskval = GET_DATA_BYTE(linem - wplm, j - 1);
1355 if (val > val1 && val1 != maskval) {
1356 SET_DATA_BYTE(lines - wpls, j - 1,
1357 L_MIN(val, maskval));
1358 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1359 pixel->x = i - 1;
1360 pixel->y = j - 1;
1361 lqueueAdd(lq_pixel, pixel);
1362 }
1363 }
1364 if (j < jmax) {
1365 val3 = GET_DATA_BYTE(lines - wpls, j + 1);
1366 maskval = GET_DATA_BYTE(linem - wplm, j + 1);
1367 if (val > val3 && val3 != maskval) {
1368 SET_DATA_BYTE(lines - wpls, j + 1,
1369 L_MIN(val, maskval));
1370 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1371 pixel->x = i - 1;
1372 pixel->y = j + 1;
1373 lqueueAdd(lq_pixel, pixel);
1374 }
1375 }
1376 val2 = GET_DATA_BYTE(lines - wpls, j);
1377 maskval = GET_DATA_BYTE(linem - wplm, j);
1378 if (val > val2 && val2 != maskval) {
1379 SET_DATA_BYTE(lines - wpls, j, L_MIN(val, maskval));
1380 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1381 pixel->x = i - 1;
1382 pixel->y = j;
1383 lqueueAdd(lq_pixel, pixel);
1384 }
1385
1386 }
1387 if (j > 0) {
1388 val4 = GET_DATA_BYTE(lines, j - 1);
1389 maskval = GET_DATA_BYTE(linem, j - 1);
1390 if (val > val4 && val4 != maskval) {
1391 SET_DATA_BYTE(lines, j - 1, L_MIN(val, maskval));
1392 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1393 pixel->x = i;
1394 pixel->y = j - 1;
1395 lqueueAdd(lq_pixel, pixel);
1396 }
1397 }
1398 if (i < imax) {
1399 if (j > 0) {
1400 val6 = GET_DATA_BYTE(lines + wpls, j - 1);
1401 maskval = GET_DATA_BYTE(linem + wplm, j - 1);
1402 if (val > val6 && val6 != maskval) {
1403 SET_DATA_BYTE(lines + wpls, j - 1,
1404 L_MIN(val, maskval));
1405 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1406 pixel->x = i + 1;
1407 pixel->y = j - 1;
1408 lqueueAdd(lq_pixel, pixel);
1409 }
1410 }
1411 if (j < jmax) {
1412 val8 = GET_DATA_BYTE(lines + wpls, j + 1);
1413 maskval = GET_DATA_BYTE(linem + wplm, j + 1);
1414 if (val > val8 && val8 != maskval) {
1415 SET_DATA_BYTE(lines + wpls, j + 1,
1416 L_MIN(val, maskval));
1417 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1418 pixel->x = i + 1;
1419 pixel->y = j + 1;
1420 lqueueAdd(lq_pixel, pixel);
1421 }
1422 }
1423 val7 = GET_DATA_BYTE(lines + wpls, j);
1424 maskval = GET_DATA_BYTE(linem + wplm, j);
1425 if (val > val7 && val7 != maskval) {
1426 SET_DATA_BYTE(lines + wpls, j, L_MIN(val, maskval));
1427 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1428 pixel->x = i + 1;
1429 pixel->y = j;
1430 lqueueAdd(lq_pixel, pixel);
1431 }
1432 }
1433 if (j < jmax) {
1434 val5 = GET_DATA_BYTE(lines, j + 1);
1435 maskval = GET_DATA_BYTE(linem, j + 1);
1436 if (val > val5 && val5 != maskval) {
1437 SET_DATA_BYTE(lines, j + 1, L_MIN(val, maskval));
1438 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1439 pixel->x = i;
1440 pixel->y = j + 1;
1441 lqueueAdd(lq_pixel, pixel);
1442 }
1443 }
1444 }
1445
1446 queue_size = lqueueGetCount(lq_pixel);
1447 }
1448 break;
1449
1450 default:
1451 L_ERROR("shouldn't get here!\n", __func__);
1452 }
1453
1454 lqueueDestroy(&lq_pixel, TRUE);
1455}
1456
1457
1491static void
1492seedfillGrayInvLow(l_uint32 *datas,
1493 l_int32 w,
1494 l_int32 h,
1495 l_int32 wpls,
1496 l_uint32 *datam,
1497 l_int32 wplm,
1498 l_int32 connectivity)
1499{
1500l_uint8 val1, val2, val3, val4, val5, val6, val7, val8;
1501l_uint8 val, maxval, maskval, boolval;
1502l_int32 i, j, imax, jmax, queue_size;
1503l_uint32 *lines, *linem;
1504L_PIXEL *pixel;
1505L_QUEUE *lq_pixel;
1506
1507 if (connectivity != 4 && connectivity != 8) {
1508 L_ERROR("connectivity must be 4 or 8\n", __func__);
1509 return;
1510 }
1511
1512 imax = h - 1;
1513 jmax = w - 1;
1514
1515 /* In the worst case, most of the pixels could be pushed
1516 * onto the FIFO queue during anti-raster scan. However this
1517 * will rarely happen, and we initialize the queue ptr size to
1518 * the image perimeter. */
1519 lq_pixel = lqueueCreate(2 * (w + h));
1520
1521 switch (connectivity)
1522 {
1523 case 4:
1524 /* UL --> LR scan (Raster Order)
1525 * If I : mask image
1526 * J : marker image
1527 * Let p be the currect pixel;
1528 * tmp <- max{J(p) union J(p) neighbors in raster order}
1529 * if (tmp > I(p))
1530 * J(p) <- tmp
1531 * end */
1532 for (i = 0; i < h; i++) {
1533 lines = datas + i * wpls;
1534 linem = datam + i * wplm;
1535 for (j = 0; j < w; j++) {
1536 if ((maskval = GET_DATA_BYTE(linem, j)) < 255) {
1537 maxval = GET_DATA_BYTE(lines, j);
1538 if (i > 0) {
1539 val2 = GET_DATA_BYTE(lines - wpls, j);
1540 maxval = L_MAX(maxval, val2);
1541 }
1542 if (j > 0) {
1543 val4 = GET_DATA_BYTE(lines, j - 1);
1544 maxval = L_MAX(maxval, val4);
1545 }
1546 if (maxval > maskval)
1547 SET_DATA_BYTE(lines, j, maxval);
1548 }
1549 }
1550 }
1551
1552 /* LR --> UL scan (anti-raster order)
1553 * If I : mask image
1554 * J : marker image
1555 * Let p be the currect pixel;
1556 * tmp <- max{J(p) union J(p) neighbors in anti-raster order}
1557 * if (tmp > I(p))
1558 * J(p) <- tmp
1559 * end */
1560 for (i = imax; i >= 0; i--) {
1561 lines = datas + i * wpls;
1562 linem = datam + i * wplm;
1563 for (j = jmax; j >= 0; j--) {
1564 boolval = FALSE;
1565 if ((maskval = GET_DATA_BYTE(linem, j)) < 255) {
1566 val = maxval = GET_DATA_BYTE(lines, j);
1567 if (i < imax) {
1568 val7 = GET_DATA_BYTE(lines + wpls, j);
1569 maxval = L_MAX(maxval, val7);
1570 }
1571 if (j < jmax) {
1572 val5 = GET_DATA_BYTE(lines, j + 1);
1573 maxval = L_MAX(maxval, val5);
1574 }
1575 if (maxval > maskval)
1576 SET_DATA_BYTE(lines, j, maxval);
1577 val = GET_DATA_BYTE(lines, j);
1578
1579 /*
1580 * If there exists a point (q) which belongs to J(p)
1581 * neighbors in anti-raster order such that J(q) < J(p)
1582 * and J(p) > I(q) then
1583 * fifo_add(p) */
1584 if (i < imax) {
1585 val7 = GET_DATA_BYTE(lines + wpls, j);
1586 if ((val7 < val) &&
1587 (val > GET_DATA_BYTE(linem + wplm, j))) {
1588 boolval = TRUE;
1589 }
1590 }
1591 if (j < jmax) {
1592 val5 = GET_DATA_BYTE(lines, j + 1);
1593 if (!boolval && (val5 < val) &&
1594 (val > GET_DATA_BYTE(linem, j + 1))) {
1595 boolval = TRUE;
1596 }
1597 }
1598 if (boolval) {
1599 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1600 pixel->x = i;
1601 pixel->y = j;
1602 lqueueAdd(lq_pixel, pixel);
1603 }
1604 }
1605 }
1606 }
1607
1608 /* Propagation step:
1609 * while fifo_empty = false
1610 * p <- fifo_first()
1611 * for every pixel (q) belong to neighbors of (p)
1612 * if J(q) < J(p) and J(p) > I(q)
1613 * J(q) <- min(J(p), I(q));
1614 * fifo_add(q);
1615 * end
1616 * end
1617 * end */
1618 queue_size = lqueueGetCount(lq_pixel);
1619 while (queue_size) {
1620 pixel = (L_PIXEL *)lqueueRemove(lq_pixel);
1621 i = pixel->x;
1622 j = pixel->y;
1623 LEPT_FREE(pixel);
1624 lines = datas + i * wpls;
1625 linem = datam + i * wplm;
1626
1627 if ((val = GET_DATA_BYTE(lines, j)) > 0) {
1628 if (i > 0) {
1629 val2 = GET_DATA_BYTE(lines - wpls, j);
1630 maskval = GET_DATA_BYTE(linem - wplm, j);
1631 if (val > val2 && val > maskval) {
1632 SET_DATA_BYTE(lines - wpls, j, val);
1633 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1634 pixel->x = i - 1;
1635 pixel->y = j;
1636 lqueueAdd(lq_pixel, pixel);
1637 }
1638
1639 }
1640 if (j > 0) {
1641 val4 = GET_DATA_BYTE(lines, j - 1);
1642 maskval = GET_DATA_BYTE(linem, j - 1);
1643 if (val > val4 && val > maskval) {
1644 SET_DATA_BYTE(lines, j - 1, val);
1645 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1646 pixel->x = i;
1647 pixel->y = j - 1;
1648 lqueueAdd(lq_pixel, pixel);
1649 }
1650 }
1651 if (i < imax) {
1652 val7 = GET_DATA_BYTE(lines + wpls, j);
1653 maskval = GET_DATA_BYTE(linem + wplm, j);
1654 if (val > val7 && val > maskval) {
1655 SET_DATA_BYTE(lines + wpls, j, val);
1656 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1657 pixel->x = i + 1;
1658 pixel->y = j;
1659 lqueueAdd(lq_pixel, pixel);
1660 }
1661 }
1662 if (j < jmax) {
1663 val5 = GET_DATA_BYTE(lines, j + 1);
1664 maskval = GET_DATA_BYTE(linem, j + 1);
1665 if (val > val5 && val > maskval) {
1666 SET_DATA_BYTE(lines, j + 1, val);
1667 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1668 pixel->x = i;
1669 pixel->y = j + 1;
1670 lqueueAdd(lq_pixel, pixel);
1671 }
1672 }
1673 }
1674
1675 queue_size = lqueueGetCount(lq_pixel);
1676 }
1677 break;
1678
1679 case 8:
1680 /* UL --> LR scan (Raster Order)
1681 * If I : mask image
1682 * J : marker image
1683 * Let p be the currect pixel;
1684 * tmp <- max{J(p) union J(p) neighbors in raster order}
1685 * if (tmp > I(p))
1686 * J(p) <- tmp
1687 * end */
1688 for (i = 0; i < h; i++) {
1689 lines = datas + i * wpls;
1690 linem = datam + i * wplm;
1691 for (j = 0; j < w; j++) {
1692 if ((maskval = GET_DATA_BYTE(linem, j)) < 255) {
1693 maxval = GET_DATA_BYTE(lines, j);
1694 if (i > 0) {
1695 if (j > 0) {
1696 val1 = GET_DATA_BYTE(lines - wpls, j - 1);
1697 maxval = L_MAX(maxval, val1);
1698 }
1699 if (j < jmax) {
1700 val3 = GET_DATA_BYTE(lines - wpls, j + 1);
1701 maxval = L_MAX(maxval, val3);
1702 }
1703 val2 = GET_DATA_BYTE(lines - wpls, j);
1704 maxval = L_MAX(maxval, val2);
1705 }
1706 if (j > 0) {
1707 val4 = GET_DATA_BYTE(lines, j - 1);
1708 maxval = L_MAX(maxval, val4);
1709 }
1710 if (maxval > maskval)
1711 SET_DATA_BYTE(lines, j, maxval);
1712 }
1713 }
1714 }
1715
1716 /* LR --> UL scan (anti-raster order)
1717 * If I : mask image
1718 * J : marker image
1719 * Let p be the currect pixel;
1720 * tmp <- max{J(p) union J(p) neighbors in anti-raster order}
1721 * if (tmp > I(p))
1722 * J(p) <- tmp
1723 * end */
1724 for (i = imax; i >= 0; i--) {
1725 lines = datas + i * wpls;
1726 linem = datam + i * wplm;
1727 for (j = jmax; j >= 0; j--) {
1728 boolval = FALSE;
1729 if ((maskval = GET_DATA_BYTE(linem, j)) < 255) {
1730 maxval = GET_DATA_BYTE(lines, j);
1731 if (i < imax) {
1732 if (j > 0) {
1733 val6 = GET_DATA_BYTE(lines + wpls, j - 1);
1734 maxval = L_MAX(maxval, val6);
1735 }
1736 if (j < jmax) {
1737 val8 = GET_DATA_BYTE(lines + wpls, j + 1);
1738 maxval = L_MAX(maxval, val8);
1739 }
1740 val7 = GET_DATA_BYTE(lines + wpls, j);
1741 maxval = L_MAX(maxval, val7);
1742 }
1743 if (j < jmax) {
1744 val5 = GET_DATA_BYTE(lines, j + 1);
1745 maxval = L_MAX(maxval, val5);
1746 }
1747 if (maxval > maskval)
1748 SET_DATA_BYTE(lines, j, maxval);
1749 val = GET_DATA_BYTE(lines, j);
1750
1751 /*
1752 * If there exists a point (q) which belongs to J(p)
1753 * neighbors in anti-raster order such that J(q) < J(p)
1754 * and J(p) > I(q) then
1755 * fifo_add(p) */
1756 if (i < imax) {
1757 if (j > 0) {
1758 val6 = GET_DATA_BYTE(lines + wpls, j - 1);
1759 if ((val6 < val) &&
1760 (val > GET_DATA_BYTE(linem + wplm, j - 1))) {
1761 boolval = TRUE;
1762 }
1763 }
1764 if (j < jmax) {
1765 val8 = GET_DATA_BYTE(lines + wpls, j + 1);
1766 if (!boolval && (val8 < val) &&
1767 (val > GET_DATA_BYTE(linem + wplm, j + 1))) {
1768 boolval = TRUE;
1769 }
1770 }
1771 val7 = GET_DATA_BYTE(lines + wpls, j);
1772 if (!boolval && (val7 < val) &&
1773 (val > GET_DATA_BYTE(linem + wplm, j))) {
1774 boolval = TRUE;
1775 }
1776 }
1777 if (j < jmax) {
1778 val5 = GET_DATA_BYTE(lines, j + 1);
1779 if (!boolval && (val5 < val) &&
1780 (val > GET_DATA_BYTE(linem, j + 1))) {
1781 boolval = TRUE;
1782 }
1783 }
1784 if (boolval) {
1785 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1786 pixel->x = i;
1787 pixel->y = j;
1788 lqueueAdd(lq_pixel, pixel);
1789 }
1790 }
1791 }
1792 }
1793
1794 /* Propagation step:
1795 * while fifo_empty = false
1796 * p <- fifo_first()
1797 * for every pixel (q) belong to neighbors of (p)
1798 * if J(q) < J(p) and J(p) > I(q)
1799 * J(q) <- min(J(p), I(q));
1800 * fifo_add(q);
1801 * end
1802 * end
1803 * end */
1804 queue_size = lqueueGetCount(lq_pixel);
1805 while (queue_size) {
1806 pixel = (L_PIXEL *)lqueueRemove(lq_pixel);
1807 i = pixel->x;
1808 j = pixel->y;
1809 LEPT_FREE(pixel);
1810 lines = datas + i * wpls;
1811 linem = datam + i * wplm;
1812
1813 if ((val = GET_DATA_BYTE(lines, j)) > 0) {
1814 if (i > 0) {
1815 if (j > 0) {
1816 val1 = GET_DATA_BYTE(lines - wpls, j - 1);
1817 maskval = GET_DATA_BYTE(linem - wplm, j - 1);
1818 if (val > val1 && val > maskval) {
1819 SET_DATA_BYTE(lines - wpls, j - 1, val);
1820 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1821 pixel->x = i - 1;
1822 pixel->y = j - 1;
1823 lqueueAdd(lq_pixel, pixel);
1824 }
1825 }
1826 if (j < jmax) {
1827 val3 = GET_DATA_BYTE(lines - wpls, j + 1);
1828 maskval = GET_DATA_BYTE(linem - wplm, j + 1);
1829 if (val > val3 && val > maskval) {
1830 SET_DATA_BYTE(lines - wpls, j + 1, val);
1831 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1832 pixel->x = i - 1;
1833 pixel->y = j + 1;
1834 lqueueAdd(lq_pixel, pixel);
1835 }
1836 }
1837 val2 = GET_DATA_BYTE(lines - wpls, j);
1838 maskval = GET_DATA_BYTE(linem - wplm, j);
1839 if (val > val2 && val > maskval) {
1840 SET_DATA_BYTE(lines - wpls, j, val);
1841 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1842 pixel->x = i - 1;
1843 pixel->y = j;
1844 lqueueAdd(lq_pixel, pixel);
1845 }
1846
1847 }
1848 if (j > 0) {
1849 val4 = GET_DATA_BYTE(lines, j - 1);
1850 maskval = GET_DATA_BYTE(linem, j - 1);
1851 if (val > val4 && val > maskval) {
1852 SET_DATA_BYTE(lines, j - 1, val);
1853 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1854 pixel->x = i;
1855 pixel->y = j - 1;
1856 lqueueAdd(lq_pixel, pixel);
1857 }
1858 }
1859 if (i < imax) {
1860 if (j > 0) {
1861 val6 = GET_DATA_BYTE(lines + wpls, j - 1);
1862 maskval = GET_DATA_BYTE(linem + wplm, j - 1);
1863 if (val > val6 && val > maskval) {
1864 SET_DATA_BYTE(lines + wpls, j - 1, val);
1865 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1866 pixel->x = i + 1;
1867 pixel->y = j - 1;
1868 lqueueAdd(lq_pixel, pixel);
1869 }
1870 }
1871 if (j < jmax) {
1872 val8 = GET_DATA_BYTE(lines + wpls, j + 1);
1873 maskval = GET_DATA_BYTE(linem + wplm, j + 1);
1874 if (val > val8 && val > maskval) {
1875 SET_DATA_BYTE(lines + wpls, j + 1, val);
1876 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1877 pixel->x = i + 1;
1878 pixel->y = j + 1;
1879 lqueueAdd(lq_pixel, pixel);
1880 }
1881 }
1882 val7 = GET_DATA_BYTE(lines + wpls, j);
1883 maskval = GET_DATA_BYTE(linem + wplm, j);
1884 if (val > val7 && val > maskval) {
1885 SET_DATA_BYTE(lines + wpls, j, val);
1886 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1887 pixel->x = i + 1;
1888 pixel->y = j;
1889 lqueueAdd(lq_pixel, pixel);
1890 }
1891 }
1892 if (j < jmax) {
1893 val5 = GET_DATA_BYTE(lines, j + 1);
1894 maskval = GET_DATA_BYTE(linem, j + 1);
1895 if (val > val5 && val > maskval) {
1896 SET_DATA_BYTE(lines, j + 1, val);
1897 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1898 pixel->x = i;
1899 pixel->y = j + 1;
1900 lqueueAdd(lq_pixel, pixel);
1901 }
1902 }
1903 }
1904
1905 queue_size = lqueueGetCount(lq_pixel);
1906 }
1907 break;
1908
1909 default:
1910 L_ERROR("shouldn't get here!\n", __func__);
1911 }
1912
1913 lqueueDestroy(&lq_pixel, TRUE);
1914}
1915
1916
1917/*-----------------------------------------------------------------------*
1918 * Vincent's Iterative Grayscale Seedfill method *
1919 *-----------------------------------------------------------------------*/
1944l_ok
1945pixSeedfillGraySimple(PIX *pixs,
1946 PIX *pixm,
1947 l_int32 connectivity)
1948{
1949l_int32 i, h, w, wpls, wplm, boolval;
1950l_uint32 *datas, *datam;
1951PIX *pixt;
1952
1953 if (!pixs || pixGetDepth(pixs) != 8)
1954 return ERROR_INT("pixs not defined or not 8 bpp", __func__, 1);
1955 if (!pixm || pixGetDepth(pixm) != 8)
1956 return ERROR_INT("pixm not defined or not 8 bpp", __func__, 1);
1957 if (connectivity != 4 && connectivity != 8)
1958 return ERROR_INT("connectivity not in {4,8}", __func__, 1);
1959
1960 /* Make sure the sizes of seed and mask images are the same */
1961 if (pixSizesEqual(pixs, pixm) == 0)
1962 return ERROR_INT("pixs and pixm sizes differ", __func__, 1);
1963
1964 /* This is used to test for completion */
1965 if ((pixt = pixCreateTemplate(pixs)) == NULL)
1966 return ERROR_INT("pixt not made", __func__, 1);
1967
1968 datas = pixGetData(pixs);
1969 datam = pixGetData(pixm);
1970 wpls = pixGetWpl(pixs);
1971 wplm = pixGetWpl(pixm);
1972 pixGetDimensions(pixs, &w, &h, NULL);
1973 for (i = 0; i < MaxIters; i++) {
1974 pixCopy(pixt, pixs);
1975 seedfillGrayLowSimple(datas, w, h, wpls, datam, wplm, connectivity);
1976 pixEqual(pixs, pixt, &boolval);
1977 if (boolval == 1) {
1978#if DEBUG_PRINT_ITERS
1979 L_INFO("Gray seed fill converged: %d iters\n", __func__, i + 1);
1980#endif /* DEBUG_PRINT_ITERS */
1981 break;
1982 }
1983 }
1984
1985 pixDestroy(&pixt);
1986 return 0;
1987}
1988
1989
2013l_ok
2014pixSeedfillGrayInvSimple(PIX *pixs,
2015 PIX *pixm,
2016 l_int32 connectivity)
2017{
2018l_int32 i, h, w, wpls, wplm, boolval;
2019l_uint32 *datas, *datam;
2020PIX *pixt;
2021
2022 if (!pixs || pixGetDepth(pixs) != 8)
2023 return ERROR_INT("pixs not defined or not 8 bpp", __func__, 1);
2024 if (!pixm || pixGetDepth(pixm) != 8)
2025 return ERROR_INT("pixm not defined or not 8 bpp", __func__, 1);
2026 if (connectivity != 4 && connectivity != 8)
2027 return ERROR_INT("connectivity not in {4,8}", __func__, 1);
2028
2029 /* Make sure the sizes of seed and mask images are the same */
2030 if (pixSizesEqual(pixs, pixm) == 0)
2031 return ERROR_INT("pixs and pixm sizes differ", __func__, 1);
2032
2033 /* This is used to test for completion */
2034 if ((pixt = pixCreateTemplate(pixs)) == NULL)
2035 return ERROR_INT("pixt not made", __func__, 1);
2036
2037 datas = pixGetData(pixs);
2038 datam = pixGetData(pixm);
2039 wpls = pixGetWpl(pixs);
2040 wplm = pixGetWpl(pixm);
2041 pixGetDimensions(pixs, &w, &h, NULL);
2042 for (i = 0; i < MaxIters; i++) {
2043 pixCopy(pixt, pixs);
2044 seedfillGrayInvLowSimple(datas, w, h, wpls, datam, wplm, connectivity);
2045 pixEqual(pixs, pixt, &boolval);
2046 if (boolval == 1) {
2047#if DEBUG_PRINT_ITERS
2048 L_INFO("Gray seed fill converged: %d iters\n", __func__, i + 1);
2049#endif /* DEBUG_PRINT_ITERS */
2050 break;
2051 }
2052 }
2053
2054 pixDestroy(&pixt);
2055 return 0;
2056}
2057
2058
2092static void
2093seedfillGrayLowSimple(l_uint32 *datas,
2094 l_int32 w,
2095 l_int32 h,
2096 l_int32 wpls,
2097 l_uint32 *datam,
2098 l_int32 wplm,
2099 l_int32 connectivity)
2100{
2101l_uint8 val2, val3, val4, val5, val7, val8;
2102l_uint8 val, maxval, maskval;
2103l_int32 i, j, imax, jmax;
2104l_uint32 *lines, *linem;
2105
2106 imax = h - 1;
2107 jmax = w - 1;
2108
2109 switch (connectivity)
2110 {
2111 case 4:
2112 /* UL --> LR scan */
2113 for (i = 0; i < h; i++) {
2114 lines = datas + i * wpls;
2115 linem = datam + i * wplm;
2116 for (j = 0; j < w; j++) {
2117 if ((maskval = GET_DATA_BYTE(linem, j)) > 0) {
2118 maxval = 0;
2119 if (i > 0)
2120 maxval = GET_DATA_BYTE(lines - wpls, j);
2121 if (j > 0) {
2122 val4 = GET_DATA_BYTE(lines, j - 1);
2123 maxval = L_MAX(maxval, val4);
2124 }
2125 val = GET_DATA_BYTE(lines, j);
2126 maxval = L_MAX(maxval, val);
2127 val = L_MIN(maxval, maskval);
2128 SET_DATA_BYTE(lines, j, val);
2129 }
2130 }
2131 }
2132
2133 /* LR --> UL scan */
2134 for (i = imax; i >= 0; i--) {
2135 lines = datas + i * wpls;
2136 linem = datam + i * wplm;
2137 for (j = jmax; j >= 0; j--) {
2138 if ((maskval = GET_DATA_BYTE(linem, j)) > 0) {
2139 maxval = 0;
2140 if (i < imax)
2141 maxval = GET_DATA_BYTE(lines + wpls, j);
2142 if (j < jmax) {
2143 val5 = GET_DATA_BYTE(lines, j + 1);
2144 maxval = L_MAX(maxval, val5);
2145 }
2146 val = GET_DATA_BYTE(lines, j);
2147 maxval = L_MAX(maxval, val);
2148 val = L_MIN(maxval, maskval);
2149 SET_DATA_BYTE(lines, j, val);
2150 }
2151 }
2152 }
2153 break;
2154
2155 case 8:
2156 /* UL --> LR scan */
2157 for (i = 0; i < h; i++) {
2158 lines = datas + i * wpls;
2159 linem = datam + i * wplm;
2160 for (j = 0; j < w; j++) {
2161 if ((maskval = GET_DATA_BYTE(linem, j)) > 0) {
2162 maxval = 0;
2163 if (i > 0) {
2164 if (j > 0)
2165 maxval = GET_DATA_BYTE(lines - wpls, j - 1);
2166 if (j < jmax) {
2167 val2 = GET_DATA_BYTE(lines - wpls, j + 1);
2168 maxval = L_MAX(maxval, val2);
2169 }
2170 val3 = GET_DATA_BYTE(lines - wpls, j);
2171 maxval = L_MAX(maxval, val3);
2172 }
2173 if (j > 0) {
2174 val4 = GET_DATA_BYTE(lines, j - 1);
2175 maxval = L_MAX(maxval, val4);
2176 }
2177 val = GET_DATA_BYTE(lines, j);
2178 maxval = L_MAX(maxval, val);
2179 val = L_MIN(maxval, maskval);
2180 SET_DATA_BYTE(lines, j, val);
2181 }
2182 }
2183 }
2184
2185 /* LR --> UL scan */
2186 for (i = imax; i >= 0; i--) {
2187 lines = datas + i * wpls;
2188 linem = datam + i * wplm;
2189 for (j = jmax; j >= 0; j--) {
2190 if ((maskval = GET_DATA_BYTE(linem, j)) > 0) {
2191 maxval = 0;
2192 if (i < imax) {
2193 if (j > 0)
2194 maxval = GET_DATA_BYTE(lines + wpls, j - 1);
2195 if (j < jmax) {
2196 val8 = GET_DATA_BYTE(lines + wpls, j + 1);
2197 maxval = L_MAX(maxval, val8);
2198 }
2199 val7 = GET_DATA_BYTE(lines + wpls, j);
2200 maxval = L_MAX(maxval, val7);
2201 }
2202 if (j < jmax) {
2203 val5 = GET_DATA_BYTE(lines, j + 1);
2204 maxval = L_MAX(maxval, val5);
2205 }
2206 val = GET_DATA_BYTE(lines, j);
2207 maxval = L_MAX(maxval, val);
2208 val = L_MIN(maxval, maskval);
2209 SET_DATA_BYTE(lines, j, val);
2210 }
2211 }
2212 }
2213 break;
2214
2215 default:
2216 L_ERROR("connectivity must be 4 or 8\n", __func__);
2217 }
2218}
2219
2220
2246static void
2247seedfillGrayInvLowSimple(l_uint32 *datas,
2248 l_int32 w,
2249 l_int32 h,
2250 l_int32 wpls,
2251 l_uint32 *datam,
2252 l_int32 wplm,
2253 l_int32 connectivity)
2254{
2255l_uint8 val1, val2, val3, val4, val5, val6, val7, val8;
2256l_uint8 maxval, maskval;
2257l_int32 i, j, imax, jmax;
2258l_uint32 *lines, *linem;
2259
2260 imax = h - 1;
2261 jmax = w - 1;
2262
2263 switch (connectivity)
2264 {
2265 case 4:
2266 /* UL --> LR scan */
2267 for (i = 0; i < h; i++) {
2268 lines = datas + i * wpls;
2269 linem = datam + i * wplm;
2270 for (j = 0; j < w; j++) {
2271 if ((maskval = GET_DATA_BYTE(linem, j)) < 255) {
2272 maxval = GET_DATA_BYTE(lines, j);
2273 if (i > 0) {
2274 val2 = GET_DATA_BYTE(lines - wpls, j);
2275 maxval = L_MAX(maxval, val2);
2276 }
2277 if (j > 0) {
2278 val4 = GET_DATA_BYTE(lines, j - 1);
2279 maxval = L_MAX(maxval, val4);
2280 }
2281 if (maxval > maskval)
2282 SET_DATA_BYTE(lines, j, maxval);
2283 }
2284 }
2285 }
2286
2287 /* LR --> UL scan */
2288 for (i = imax; i >= 0; i--) {
2289 lines = datas + i * wpls;
2290 linem = datam + i * wplm;
2291 for (j = jmax; j >= 0; j--) {
2292 if ((maskval = GET_DATA_BYTE(linem, j)) < 255) {
2293 maxval = GET_DATA_BYTE(lines, j);
2294 if (i < imax) {
2295 val7 = GET_DATA_BYTE(lines + wpls, j);
2296 maxval = L_MAX(maxval, val7);
2297 }
2298 if (j < jmax) {
2299 val5 = GET_DATA_BYTE(lines, j + 1);
2300 maxval = L_MAX(maxval, val5);
2301 }
2302 if (maxval > maskval)
2303 SET_DATA_BYTE(lines, j, maxval);
2304 }
2305 }
2306 }
2307 break;
2308
2309 case 8:
2310 /* UL --> LR scan */
2311 for (i = 0; i < h; i++) {
2312 lines = datas + i * wpls;
2313 linem = datam + i * wplm;
2314 for (j = 0; j < w; j++) {
2315 if ((maskval = GET_DATA_BYTE(linem, j)) < 255) {
2316 maxval = GET_DATA_BYTE(lines, j);
2317 if (i > 0) {
2318 if (j > 0) {
2319 val1 = GET_DATA_BYTE(lines - wpls, j - 1);
2320 maxval = L_MAX(maxval, val1);
2321 }
2322 if (j < jmax) {
2323 val2 = GET_DATA_BYTE(lines - wpls, j + 1);
2324 maxval = L_MAX(maxval, val2);
2325 }
2326 val3 = GET_DATA_BYTE(lines - wpls, j);
2327 maxval = L_MAX(maxval, val3);
2328 }
2329 if (j > 0) {
2330 val4 = GET_DATA_BYTE(lines, j - 1);
2331 maxval = L_MAX(maxval, val4);
2332 }
2333 if (maxval > maskval)
2334 SET_DATA_BYTE(lines, j, maxval);
2335 }
2336 }
2337 }
2338
2339 /* LR --> UL scan */
2340 for (i = imax; i >= 0; i--) {
2341 lines = datas + i * wpls;
2342 linem = datam + i * wplm;
2343 for (j = jmax; j >= 0; j--) {
2344 if ((maskval = GET_DATA_BYTE(linem, j)) < 255) {
2345 maxval = GET_DATA_BYTE(lines, j);
2346 if (i < imax) {
2347 if (j > 0) {
2348 val6 = GET_DATA_BYTE(lines + wpls, j - 1);
2349 maxval = L_MAX(maxval, val6);
2350 }
2351 if (j < jmax) {
2352 val8 = GET_DATA_BYTE(lines + wpls, j + 1);
2353 maxval = L_MAX(maxval, val8);
2354 }
2355 val7 = GET_DATA_BYTE(lines + wpls, j);
2356 maxval = L_MAX(maxval, val7);
2357 }
2358 if (j < jmax) {
2359 val5 = GET_DATA_BYTE(lines, j + 1);
2360 maxval = L_MAX(maxval, val5);
2361 }
2362 if (maxval > maskval)
2363 SET_DATA_BYTE(lines, j, maxval);
2364 }
2365 }
2366 }
2367 break;
2368
2369 default:
2370 L_ERROR("connectivity must be 4 or 8\n", __func__);
2371 }
2372}
2373
2374
2375/*-----------------------------------------------------------------------*
2376 * Gray seedfill variations *
2377 *-----------------------------------------------------------------------*/
2409PIX *
2410pixSeedfillGrayBasin(PIX *pixb,
2411 PIX *pixm,
2412 l_int32 delta,
2413 l_int32 connectivity)
2414{
2415PIX *pixbi, *pixmi, *pixsd;
2416
2417 if (!pixb || pixGetDepth(pixb) != 1)
2418 return (PIX *)ERROR_PTR("pixb undefined or not 1 bpp", __func__, NULL);
2419 if (!pixm || pixGetDepth(pixm) != 8)
2420 return (PIX *)ERROR_PTR("pixm undefined or not 8 bpp", __func__, NULL);
2421 if (connectivity != 4 && connectivity != 8)
2422 return (PIX *)ERROR_PTR("connectivity not in {4,8}", __func__, NULL);
2423
2424 if (delta <= 0) {
2425 L_WARNING("delta <= 0; returning a copy of pixm\n", __func__);
2426 return pixCopy(NULL, pixm);
2427 }
2428
2429 /* Add delta to every pixel in pixm */
2430 pixsd = pixCopy(NULL, pixm);
2431 pixAddConstantGray(pixsd, delta);
2432
2433 /* Prepare the seed. Write 255 in all pixels of
2434 * ([pixm] + delta) where pixb is 0. */
2435 pixbi = pixInvert(NULL, pixb);
2436 pixSetMasked(pixsd, pixbi, 255);
2437
2438 /* Fill the inverse seed, using the inverse clipping mask */
2439 pixmi = pixInvert(NULL, pixm);
2440 pixInvert(pixsd, pixsd);
2441 pixSeedfillGray(pixsd, pixmi, connectivity);
2442
2443 /* Re-invert the filled seed */
2444 pixInvert(pixsd, pixsd);
2445
2446 pixDestroy(&pixbi);
2447 pixDestroy(&pixmi);
2448 return pixsd;
2449}
2450
2451
2452/*-----------------------------------------------------------------------*
2453 * Vincent's Distance Function method *
2454 *-----------------------------------------------------------------------*/
2498PIX *
2499pixDistanceFunction(PIX *pixs,
2500 l_int32 connectivity,
2501 l_int32 outdepth,
2502 l_int32 boundcond)
2503{
2504l_int32 w, h, wpld;
2505l_uint32 *datad;
2506PIX *pixd;
2507
2508 if (!pixs || pixGetDepth(pixs) != 1)
2509 return (PIX *)ERROR_PTR("!pixs or pixs not 1 bpp", __func__, NULL);
2510 if (connectivity != 4 && connectivity != 8)
2511 return (PIX *)ERROR_PTR("connectivity not 4 or 8", __func__, NULL);
2512 if (outdepth != 8 && outdepth != 16)
2513 return (PIX *)ERROR_PTR("outdepth not 8 or 16 bpp", __func__, NULL);
2514 if (boundcond != L_BOUNDARY_BG && boundcond != L_BOUNDARY_FG)
2515 return (PIX *)ERROR_PTR("invalid boundcond", __func__, NULL);
2516
2517 pixGetDimensions(pixs, &w, &h, NULL);
2518 if ((pixd = pixCreate(w, h, outdepth)) == NULL)
2519 return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
2520 datad = pixGetData(pixd);
2521 wpld = pixGetWpl(pixd);
2522
2523 /* Initialize the fg pixels to 1 and the bg pixels to 0 */
2524 pixSetMasked(pixd, pixs, 1);
2525
2526 if (boundcond == L_BOUNDARY_BG) {
2527 distanceFunctionLow(datad, w, h, outdepth, wpld, connectivity);
2528 } else { /* L_BOUNDARY_FG: set boundary pixels to max val */
2529 pixRasterop(pixd, 0, 0, w, 1, PIX_SET, NULL, 0, 0); /* top */
2530 pixRasterop(pixd, 0, h - 1, w, 1, PIX_SET, NULL, 0, 0); /* bot */
2531 pixRasterop(pixd, 0, 0, 1, h, PIX_SET, NULL, 0, 0); /* left */
2532 pixRasterop(pixd, w - 1, 0, 1, h, PIX_SET, NULL, 0, 0); /* right */
2533
2534 distanceFunctionLow(datad, w, h, outdepth, wpld, connectivity);
2535
2536 /* Set each boundary pixel equal to the pixel next to it */
2537 pixSetMirroredBorder(pixd, 1, 1, 1, 1);
2538 }
2539
2540 return pixd;
2541}
2542
2543
2547static void
2548distanceFunctionLow(l_uint32 *datad,
2549 l_int32 w,
2550 l_int32 h,
2551 l_int32 d,
2552 l_int32 wpld,
2553 l_int32 connectivity)
2554{
2555l_int32 val1, val2, val3, val4, val5, val6, val7, val8, minval, val;
2556l_int32 i, j, imax, jmax;
2557l_uint32 *lined;
2558
2559 /* One raster scan followed by one anti-raster scan.
2560 * This does not re-set the 1-boundary of pixels that
2561 * were initialized to either 0 or maxval. */
2562 imax = h - 1;
2563 jmax = w - 1;
2564 switch (connectivity)
2565 {
2566 case 4:
2567 if (d == 8) {
2568 /* UL --> LR scan */
2569 for (i = 1; i < imax; i++) {
2570 lined = datad + i * wpld;
2571 for (j = 1; j < jmax; j++) {
2572 if ((val = GET_DATA_BYTE(lined, j)) > 0) {
2573 val2 = GET_DATA_BYTE(lined - wpld, j);
2574 val4 = GET_DATA_BYTE(lined, j - 1);
2575 minval = L_MIN(val2, val4);
2576 minval = L_MIN(minval, 254);
2577 SET_DATA_BYTE(lined, j, minval + 1);
2578 }
2579 }
2580 }
2581
2582 /* LR --> UL scan */
2583 for (i = imax - 1; i > 0; i--) {
2584 lined = datad + i * wpld;
2585 for (j = jmax - 1; j > 0; j--) {
2586 if ((val = GET_DATA_BYTE(lined, j)) > 0) {
2587 val7 = GET_DATA_BYTE(lined + wpld, j);
2588 val5 = GET_DATA_BYTE(lined, j + 1);
2589 minval = L_MIN(val5, val7);
2590 minval = L_MIN(minval + 1, val);
2591 SET_DATA_BYTE(lined, j, minval);
2592 }
2593 }
2594 }
2595 } else { /* d == 16 */
2596 /* UL --> LR scan */
2597 for (i = 1; i < imax; i++) {
2598 lined = datad + i * wpld;
2599 for (j = 1; j < jmax; j++) {
2600 if ((val = GET_DATA_TWO_BYTES(lined, j)) > 0) {
2601 val2 = GET_DATA_TWO_BYTES(lined - wpld, j);
2602 val4 = GET_DATA_TWO_BYTES(lined, j - 1);
2603 minval = L_MIN(val2, val4);
2604 minval = L_MIN(minval, 0xfffe);
2605 SET_DATA_TWO_BYTES(lined, j, minval + 1);
2606 }
2607 }
2608 }
2609
2610 /* LR --> UL scan */
2611 for (i = imax - 1; i > 0; i--) {
2612 lined = datad + i * wpld;
2613 for (j = jmax - 1; j > 0; j--) {
2614 if ((val = GET_DATA_TWO_BYTES(lined, j)) > 0) {
2615 val7 = GET_DATA_TWO_BYTES(lined + wpld, j);
2616 val5 = GET_DATA_TWO_BYTES(lined, j + 1);
2617 minval = L_MIN(val5, val7);
2618 minval = L_MIN(minval + 1, val);
2619 SET_DATA_TWO_BYTES(lined, j, minval);
2620 }
2621 }
2622 }
2623 }
2624 break;
2625
2626 case 8:
2627 if (d == 8) {
2628 /* UL --> LR scan */
2629 for (i = 1; i < imax; i++) {
2630 lined = datad + i * wpld;
2631 for (j = 1; j < jmax; j++) {
2632 if ((val = GET_DATA_BYTE(lined, j)) > 0) {
2633 val1 = GET_DATA_BYTE(lined - wpld, j - 1);
2634 val2 = GET_DATA_BYTE(lined - wpld, j);
2635 val3 = GET_DATA_BYTE(lined - wpld, j + 1);
2636 val4 = GET_DATA_BYTE(lined, j - 1);
2637 minval = L_MIN(val1, val2);
2638 minval = L_MIN(minval, val3);
2639 minval = L_MIN(minval, val4);
2640 minval = L_MIN(minval, 254);
2641 SET_DATA_BYTE(lined, j, minval + 1);
2642 }
2643 }
2644 }
2645
2646 /* LR --> UL scan */
2647 for (i = imax - 1; i > 0; i--) {
2648 lined = datad + i * wpld;
2649 for (j = jmax - 1; j > 0; j--) {
2650 if ((val = GET_DATA_BYTE(lined, j)) > 0) {
2651 val8 = GET_DATA_BYTE(lined + wpld, j + 1);
2652 val7 = GET_DATA_BYTE(lined + wpld, j);
2653 val6 = GET_DATA_BYTE(lined + wpld, j - 1);
2654 val5 = GET_DATA_BYTE(lined, j + 1);
2655 minval = L_MIN(val8, val7);
2656 minval = L_MIN(minval, val6);
2657 minval = L_MIN(minval, val5);
2658 minval = L_MIN(minval + 1, val);
2659 SET_DATA_BYTE(lined, j, minval);
2660 }
2661 }
2662 }
2663 } else { /* d == 16 */
2664 /* UL --> LR scan */
2665 for (i = 1; i < imax; i++) {
2666 lined = datad + i * wpld;
2667 for (j = 1; j < jmax; j++) {
2668 if ((val = GET_DATA_TWO_BYTES(lined, j)) > 0) {
2669 val1 = GET_DATA_TWO_BYTES(lined - wpld, j - 1);
2670 val2 = GET_DATA_TWO_BYTES(lined - wpld, j);
2671 val3 = GET_DATA_TWO_BYTES(lined - wpld, j + 1);
2672 val4 = GET_DATA_TWO_BYTES(lined, j - 1);
2673 minval = L_MIN(val1, val2);
2674 minval = L_MIN(minval, val3);
2675 minval = L_MIN(minval, val4);
2676 minval = L_MIN(minval, 0xfffe);
2677 SET_DATA_TWO_BYTES(lined, j, minval + 1);
2678 }
2679 }
2680 }
2681
2682 /* LR --> UL scan */
2683 for (i = imax - 1; i > 0; i--) {
2684 lined = datad + i * wpld;
2685 for (j = jmax - 1; j > 0; j--) {
2686 if ((val = GET_DATA_TWO_BYTES(lined, j)) > 0) {
2687 val8 = GET_DATA_TWO_BYTES(lined + wpld, j + 1);
2688 val7 = GET_DATA_TWO_BYTES(lined + wpld, j);
2689 val6 = GET_DATA_TWO_BYTES(lined + wpld, j - 1);
2690 val5 = GET_DATA_TWO_BYTES(lined, j + 1);
2691 minval = L_MIN(val8, val7);
2692 minval = L_MIN(minval, val6);
2693 minval = L_MIN(minval, val5);
2694 minval = L_MIN(minval + 1, val);
2695 SET_DATA_TWO_BYTES(lined, j, minval);
2696 }
2697 }
2698 }
2699 }
2700 break;
2701
2702 default:
2703 L_ERROR("connectivity must be 4 or 8\n", __func__);
2704 }
2705}
2706
2707
2708/*-----------------------------------------------------------------------*
2709 * Seed spread (based on distance function) *
2710 *-----------------------------------------------------------------------*/
2751PIX *
2752pixSeedspread(PIX *pixs,
2753 l_int32 connectivity)
2754{
2755l_int32 w, h, wplt, wplg;
2756l_uint32 *datat, *datag;
2757PIX *pixm, *pixt, *pixg, *pixd;
2758
2759 if (!pixs || pixGetDepth(pixs) != 8)
2760 return (PIX *)ERROR_PTR("!pixs or pixs not 8 bpp", __func__, NULL);
2761 if (connectivity != 4 && connectivity != 8)
2762 return (PIX *)ERROR_PTR("connectivity not 4 or 8", __func__, NULL);
2763
2764 /* Add a 4 byte border to pixs. This simplifies the computation. */
2765 pixg = pixAddBorder(pixs, 4, 0);
2766 pixGetDimensions(pixg, &w, &h, NULL);
2767
2768 /* Initialize distance function pixt. Threshold pixs to get
2769 * a 0 at the seed points where the pixs pixel is nonzero, and
2770 * a 1 at all points that need to be filled. Use this as a
2771 * mask to set a 1 in pixt at all non-seed points. Also, set all
2772 * pixt pixels in an interior boundary of width 1 to the
2773 * maximum value. For debugging, to view the distance function,
2774 * use pixConvert16To8(pixt, L_LS_BYTE) on small images. */
2775 pixm = pixThresholdToBinary(pixg, 1);
2776 pixt = pixCreate(w, h, 16);
2777 pixSetMasked(pixt, pixm, 1);
2778 pixRasterop(pixt, 0, 0, w, 1, PIX_SET, NULL, 0, 0); /* top */
2779 pixRasterop(pixt, 0, h - 1, w, 1, PIX_SET, NULL, 0, 0); /* bot */
2780 pixRasterop(pixt, 0, 0, 1, h, PIX_SET, NULL, 0, 0); /* left */
2781 pixRasterop(pixt, w - 1, 0, 1, h, PIX_SET, NULL, 0, 0); /* right */
2782 datat = pixGetData(pixt);
2783 wplt = pixGetWpl(pixt);
2784
2785 /* Do the interpolation and remove the border. */
2786 datag = pixGetData(pixg);
2787 wplg = pixGetWpl(pixg);
2788 seedspreadLow(datag, w, h, wplg, datat, wplt, connectivity);
2789 pixd = pixRemoveBorder(pixg, 4);
2790
2791 pixDestroy(&pixm);
2792 pixDestroy(&pixg);
2793 pixDestroy(&pixt);
2794 return pixd;
2795}
2796
2797
2803static void
2804seedspreadLow(l_uint32 *datad,
2805 l_int32 w,
2806 l_int32 h,
2807 l_int32 wpld,
2808 l_uint32 *datat,
2809 l_int32 wplt,
2810 l_int32 connectivity)
2811{
2812l_int32 val1t, val2t, val3t, val4t, val5t, val6t, val7t, val8t;
2813l_int32 i, j, imax, jmax, minval, valt, vald;
2814l_uint32 *linet, *lined;
2815
2816 /* One raster scan followed by one anti-raster scan.
2817 * pixt is initialized to have 0 on pixels where the
2818 * input is specified in pixd, and to have 1 on all
2819 * other pixels. We only change pixels in pixt and pixd
2820 * that are non-zero in pixt. */
2821 imax = h - 1;
2822 jmax = w - 1;
2823 switch (connectivity)
2824 {
2825 case 4:
2826 /* UL --> LR scan */
2827 for (i = 1; i < h; i++) {
2828 linet = datat + i * wplt;
2829 lined = datad + i * wpld;
2830 for (j = 1; j < jmax; j++) {
2831 if ((valt = GET_DATA_TWO_BYTES(linet, j)) > 0) {
2832 val2t = GET_DATA_TWO_BYTES(linet - wplt, j);
2833 val4t = GET_DATA_TWO_BYTES(linet, j - 1);
2834 minval = L_MIN(val2t, val4t);
2835 minval = L_MIN(minval, 0xfffe);
2836 SET_DATA_TWO_BYTES(linet, j, minval + 1);
2837 if (val2t < val4t)
2838 vald = GET_DATA_BYTE(lined - wpld, j);
2839 else
2840 vald = GET_DATA_BYTE(lined, j - 1);
2841 SET_DATA_BYTE(lined, j, vald);
2842 }
2843 }
2844 }
2845
2846 /* LR --> UL scan */
2847 for (i = imax - 1; i > 0; i--) {
2848 linet = datat + i * wplt;
2849 lined = datad + i * wpld;
2850 for (j = jmax - 1; j > 0; j--) {
2851 if ((valt = GET_DATA_TWO_BYTES(linet, j)) > 0) {
2852 val7t = GET_DATA_TWO_BYTES(linet + wplt, j);
2853 val5t = GET_DATA_TWO_BYTES(linet, j + 1);
2854 minval = L_MIN(val5t, val7t);
2855 minval = L_MIN(minval + 1, valt);
2856 if (valt > minval) { /* replace */
2857 SET_DATA_TWO_BYTES(linet, j, minval);
2858 if (val5t < val7t)
2859 vald = GET_DATA_BYTE(lined, j + 1);
2860 else
2861 vald = GET_DATA_BYTE(lined + wplt, j);
2862 SET_DATA_BYTE(lined, j, vald);
2863 }
2864 }
2865 }
2866 }
2867 break;
2868 case 8:
2869 /* UL --> LR scan */
2870 for (i = 1; i < h; i++) {
2871 linet = datat + i * wplt;
2872 lined = datad + i * wpld;
2873 for (j = 1; j < jmax; j++) {
2874 if ((valt = GET_DATA_TWO_BYTES(linet, j)) > 0) {
2875 val1t = GET_DATA_TWO_BYTES(linet - wplt, j - 1);
2876 val2t = GET_DATA_TWO_BYTES(linet - wplt, j);
2877 val3t = GET_DATA_TWO_BYTES(linet - wplt, j + 1);
2878 val4t = GET_DATA_TWO_BYTES(linet, j - 1);
2879 minval = L_MIN(val1t, val2t);
2880 minval = L_MIN(minval, val3t);
2881 minval = L_MIN(minval, val4t);
2882 minval = L_MIN(minval, 0xfffe);
2883 SET_DATA_TWO_BYTES(linet, j, minval + 1);
2884 if (minval == val1t)
2885 vald = GET_DATA_BYTE(lined - wpld, j - 1);
2886 else if (minval == val2t)
2887 vald = GET_DATA_BYTE(lined - wpld, j);
2888 else if (minval == val3t)
2889 vald = GET_DATA_BYTE(lined - wpld, j + 1);
2890 else /* minval == val4t */
2891 vald = GET_DATA_BYTE(lined, j - 1);
2892 SET_DATA_BYTE(lined, j, vald);
2893 }
2894 }
2895 }
2896
2897 /* LR --> UL scan */
2898 for (i = imax - 1; i > 0; i--) {
2899 linet = datat + i * wplt;
2900 lined = datad + i * wpld;
2901 for (j = jmax - 1; j > 0; j--) {
2902 if ((valt = GET_DATA_TWO_BYTES(linet, j)) > 0) {
2903 val8t = GET_DATA_TWO_BYTES(linet + wplt, j + 1);
2904 val7t = GET_DATA_TWO_BYTES(linet + wplt, j);
2905 val6t = GET_DATA_TWO_BYTES(linet + wplt, j - 1);
2906 val5t = GET_DATA_TWO_BYTES(linet, j + 1);
2907 minval = L_MIN(val8t, val7t);
2908 minval = L_MIN(minval, val6t);
2909 minval = L_MIN(minval, val5t);
2910 minval = L_MIN(minval + 1, valt);
2911 if (valt > minval) { /* replace */
2912 SET_DATA_TWO_BYTES(linet, j, minval);
2913 if (minval == val5t + 1)
2914 vald = GET_DATA_BYTE(lined, j + 1);
2915 else if (minval == val6t + 1)
2916 vald = GET_DATA_BYTE(lined + wpld, j - 1);
2917 else if (minval == val7t + 1)
2918 vald = GET_DATA_BYTE(lined + wpld, j);
2919 else /* minval == val8t + 1 */
2920 vald = GET_DATA_BYTE(lined + wpld, j + 1);
2921 SET_DATA_BYTE(lined, j, vald);
2922 }
2923 }
2924 }
2925 }
2926 break;
2927 default:
2928 L_ERROR("connectivity must be 4 or 8\n", __func__);
2929 break;
2930 }
2931}
2932
2933
2934/*-----------------------------------------------------------------------*
2935 * Local extrema *
2936 *-----------------------------------------------------------------------*/
2974l_ok
2975pixLocalExtrema(PIX *pixs,
2976 l_int32 maxmin,
2977 l_int32 minmax,
2978 PIX **ppixmin,
2979 PIX **ppixmax)
2980{
2981PIX *pixmin, *pixmax, *pixt1, *pixt2;
2982
2983 if (!pixs || pixGetDepth(pixs) != 8)
2984 return ERROR_INT("pixs not defined or not 8 bpp", __func__, 1);
2985 if (!ppixmin && !ppixmax)
2986 return ERROR_INT("neither &pixmin, &pixmax are defined", __func__, 1);
2987 if (maxmin <= 0) maxmin = 254;
2988 if (minmax <= 0) minmax = 1;
2989
2990 if (ppixmin) {
2991 pixt1 = pixErodeGray(pixs, 3, 3);
2992 pixmin = pixFindEqualValues(pixs, pixt1);
2993 pixDestroy(&pixt1);
2994 pixQualifyLocalMinima(pixs, pixmin, maxmin);
2995 *ppixmin = pixmin;
2996 }
2997
2998 if (ppixmax) {
2999 pixt1 = pixInvert(NULL, pixs);
3000 pixt2 = pixErodeGray(pixt1, 3, 3);
3001 pixmax = pixFindEqualValues(pixt1, pixt2);
3002 pixDestroy(&pixt2);
3003 pixQualifyLocalMinima(pixt1, pixmax, 255 - minmax);
3004 *ppixmax = pixmax;
3005 pixDestroy(&pixt1);
3006 }
3007
3008 return 0;
3009}
3010
3011
3036static l_int32
3037pixQualifyLocalMinima(PIX *pixs,
3038 PIX *pixm,
3039 l_int32 maxval)
3040{
3041l_int32 n, i, j, k, x, y, w, h, xc, yc, wc, hc, xon, yon;
3042l_int32 vals, wpls, wplc, ismin;
3043l_uint32 val;
3044l_uint32 *datas, *datac, *lines, *linec;
3045BOXA *boxa;
3046PIX *pix1, *pix2, *pix3;
3047PIXA *pixa;
3048
3049 if (!pixs || pixGetDepth(pixs) != 8)
3050 return ERROR_INT("pixs not defined or not 8 bpp", __func__, 1);
3051 if (!pixm || pixGetDepth(pixm) != 1)
3052 return ERROR_INT("pixm not defined or not 1 bpp", __func__, 1);
3053 if (maxval <= 0) maxval = 254;
3054
3055 pixGetDimensions(pixs, &w, &h, NULL);
3056 datas = pixGetData(pixs);
3057 wpls = pixGetWpl(pixs);
3058 boxa = pixConnComp(pixm, &pixa, 8);
3059 n = pixaGetCount(pixa);
3060 for (k = 0; k < n; k++) {
3061 boxaGetBoxGeometry(boxa, k, &xc, &yc, &wc, &hc);
3062 pix1 = pixaGetPix(pixa, k, L_COPY);
3063 pix2 = pixAddBorder(pix1, 1, 0);
3064 pix3 = pixDilateBrick(NULL, pix2, 3, 3);
3065 pixXor(pix3, pix3, pix2); /* exterior boundary pixels */
3066 datac = pixGetData(pix3);
3067 wplc = pixGetWpl(pix3);
3068 nextOnPixelInRaster(pix1, 0, 0, &xon, &yon);
3069 pixGetPixel(pixs, xc + xon, yc + yon, &val);
3070 if (val > maxval) { /* too large; erase */
3071 pixRasterop(pixm, xc, yc, wc, hc, PIX_XOR, pix1, 0, 0);
3072 pixDestroy(&pix1);
3073 pixDestroy(&pix2);
3074 pixDestroy(&pix3);
3075 continue;
3076 }
3077 ismin = TRUE;
3078
3079 /* Check all values in pixs that correspond to the exterior
3080 * boundary pixels of the c.c. in pixm. Verify that the
3081 * value in the c.c. is always less. */
3082 for (i = 0, y = yc - 1; i < hc + 2 && y >= 0 && y < h; i++, y++) {
3083 lines = datas + y * wpls;
3084 linec = datac + i * wplc;
3085 for (j = 0, x = xc - 1; j < wc + 2 && x >= 0 && x < w; j++, x++) {
3086 if (GET_DATA_BIT(linec, j)) {
3087 vals = GET_DATA_BYTE(lines, x);
3088 if (vals <= val) { /* not a minimum! */
3089 ismin = FALSE;
3090 break;
3091 }
3092 }
3093 }
3094 if (!ismin)
3095 break;
3096 }
3097 if (!ismin) /* erase it */
3098 pixRasterop(pixm, xc, yc, wc, hc, PIX_XOR, pix1, 0, 0);
3099 pixDestroy(&pix1);
3100 pixDestroy(&pix2);
3101 pixDestroy(&pix3);
3102 }
3103
3104 boxaDestroy(&boxa);
3105 pixaDestroy(&pixa);
3106 return 0;
3107}
3108
3109
3142l_ok
3143pixSelectedLocalExtrema(PIX *pixs,
3144 l_int32 mindist,
3145 PIX **ppixmin,
3146 PIX **ppixmax)
3147{
3148PIX *pixmin, *pixmax, *pixt, *pixtmin, *pixtmax;
3149
3150 if (!pixs || pixGetDepth(pixs) != 8)
3151 return ERROR_INT("pixs not defined or not 8 bpp", __func__, 1);
3152 if (!ppixmin || !ppixmax)
3153 return ERROR_INT("&pixmin and &pixmax not both defined", __func__, 1);
3154
3155 pixt = pixErodeGray(pixs, 3, 3);
3156 pixmin = pixFindEqualValues(pixs, pixt);
3157 pixDestroy(&pixt);
3158 pixt = pixDilateGray(pixs, 3, 3);
3159 pixmax = pixFindEqualValues(pixs, pixt);
3160 pixDestroy(&pixt);
3161
3162 /* Remove all points that are within the prescribed distance
3163 * from each other. */
3164 if (mindist < 0) { /* remove no points */
3165 *ppixmin = pixmin;
3166 *ppixmax = pixmax;
3167 } else if (mindist == 0) { /* remove points belonging to both sets */
3168 pixt = pixAnd(NULL, pixmin, pixmax);
3169 *ppixmin = pixSubtract(pixmin, pixmin, pixt);
3170 *ppixmax = pixSubtract(pixmax, pixmax, pixt);
3171 pixDestroy(&pixt);
3172 } else {
3173 pixtmin = pixDilateBrick(NULL, pixmin,
3174 2 * mindist + 1, 2 * mindist + 1);
3175 pixtmax = pixDilateBrick(NULL, pixmax,
3176 2 * mindist + 1, 2 * mindist + 1);
3177 *ppixmin = pixSubtract(pixmin, pixmin, pixtmax);
3178 *ppixmax = pixSubtract(pixmax, pixmax, pixtmin);
3179 pixDestroy(&pixtmin);
3180 pixDestroy(&pixtmax);
3181 }
3182 return 0;
3183}
3184
3185
3200PIX *
3201pixFindEqualValues(PIX *pixs1,
3202 PIX *pixs2)
3203{
3204l_int32 w1, h1, w2, h2, w, h;
3205l_int32 i, j, val1, val2, wpls1, wpls2, wpld;
3206l_uint32 *datas1, *datas2, *datad, *lines1, *lines2, *lined;
3207PIX *pixd;
3208
3209 if (!pixs1 || pixGetDepth(pixs1) != 8)
3210 return (PIX *)ERROR_PTR("pixs1 undefined or not 8 bpp", __func__, NULL);
3211 if (!pixs2 || pixGetDepth(pixs2) != 8)
3212 return (PIX *)ERROR_PTR("pixs2 undefined or not 8 bpp", __func__, NULL);
3213 pixGetDimensions(pixs1, &w1, &h1, NULL);
3214 pixGetDimensions(pixs2, &w2, &h2, NULL);
3215 w = L_MIN(w1, w2);
3216 h = L_MIN(h1, h2);
3217 pixd = pixCreate(w, h, 1);
3218 datas1 = pixGetData(pixs1);
3219 datas2 = pixGetData(pixs2);
3220 datad = pixGetData(pixd);
3221 wpls1 = pixGetWpl(pixs1);
3222 wpls2 = pixGetWpl(pixs2);
3223 wpld = pixGetWpl(pixd);
3224
3225 for (i = 0; i < h; i++) {
3226 lines1 = datas1 + i * wpls1;
3227 lines2 = datas2 + i * wpls2;
3228 lined = datad + i * wpld;
3229 for (j = 0; j < w; j++) {
3230 val1 = GET_DATA_BYTE(lines1, j);
3231 val2 = GET_DATA_BYTE(lines2, j);
3232 if (val1 == val2)
3233 SET_DATA_BIT(lined, j);
3234 }
3235 }
3236
3237 return pixd;
3238}
3239
3240
3241/*-----------------------------------------------------------------------*
3242 * Selection of minima in mask connected components *
3243 *-----------------------------------------------------------------------*/
3265l_ok
3266pixSelectMinInConnComp(PIX *pixs,
3267 PIX *pixm,
3268 PTA **ppta,
3269 NUMA **pnav)
3270{
3271l_int32 bx, by, bw, bh, i, j, c, n;
3272l_int32 xs, ys, minx, miny, wpls, wplt, val, minval;
3273l_uint32 *datas, *datat, *lines, *linet;
3274BOXA *boxa;
3275NUMA *nav;
3276PIX *pixt, *pixs2, *pixm2;
3277PIXA *pixa;
3278PTA *pta;
3279
3280 if (!ppta)
3281 return ERROR_INT("&pta not defined", __func__, 1);
3282 *ppta = NULL;
3283 if (pnav) *pnav = NULL;
3284 if (!pixs || pixGetDepth(pixs) != 8)
3285 return ERROR_INT("pixs undefined or not 8 bpp", __func__, 1);
3286 if (!pixm || pixGetDepth(pixm) != 1)
3287 return ERROR_INT("pixm undefined or not 1 bpp", __func__, 1);
3288
3289 /* Crop to the min size if necessary */
3290 if (pixCropToMatch(pixs, pixm, &pixs2, &pixm2)) {
3291 pixDestroy(&pixs2);
3292 pixDestroy(&pixm2);
3293 return ERROR_INT("cropping failure", __func__, 1);
3294 }
3295
3296 /* Find value and location of min value pixel in each component */
3297 boxa = pixConnComp(pixm2, &pixa, 8);
3298 n = boxaGetCount(boxa);
3299 pta = ptaCreate(n);
3300 *ppta = pta;
3301 nav = numaCreate(n);
3302 datas = pixGetData(pixs2);
3303 wpls = pixGetWpl(pixs2);
3304 for (c = 0; c < n; c++) {
3305 pixt = pixaGetPix(pixa, c, L_CLONE);
3306 boxaGetBoxGeometry(boxa, c, &bx, &by, &bw, &bh);
3307 if (bw == 1 && bh == 1) {
3308 ptaAddPt(pta, bx, by);
3309 numaAddNumber(nav, GET_DATA_BYTE(datas + by * wpls, bx));
3310 pixDestroy(&pixt);
3311 continue;
3312 }
3313 datat = pixGetData(pixt);
3314 wplt = pixGetWpl(pixt);
3315 minx = miny = 1000000;
3316 minval = 256;
3317 for (i = 0; i < bh; i++) {
3318 ys = by + i;
3319 lines = datas + ys * wpls;
3320 linet = datat + i * wplt;
3321 for (j = 0; j < bw; j++) {
3322 xs = bx + j;
3323 if (GET_DATA_BIT(linet, j)) {
3324 val = GET_DATA_BYTE(lines, xs);
3325 if (val < minval) {
3326 minval = val;
3327 minx = xs;
3328 miny = ys;
3329 }
3330 }
3331 }
3332 }
3333 ptaAddPt(pta, minx, miny);
3334 numaAddNumber(nav, GET_DATA_BYTE(datas + miny * wpls, minx));
3335 pixDestroy(&pixt);
3336 }
3337
3338 boxaDestroy(&boxa);
3339 pixaDestroy(&pixa);
3340 if (pnav)
3341 *pnav = nav;
3342 else
3343 numaDestroy(&nav);
3344 pixDestroy(&pixs2);
3345 pixDestroy(&pixm2);
3346 return 0;
3347}
3348
3349
3350/*-----------------------------------------------------------------------*
3351 * Removal of seeded connected components from a mask *
3352 *-----------------------------------------------------------------------*/
3376PIX *
3377pixRemoveSeededComponents(PIX *pixd,
3378 PIX *pixs,
3379 PIX *pixm,
3380 l_int32 connectivity,
3381 l_int32 bordersize)
3382{
3383PIX *pixt;
3384
3385 if (!pixs || pixGetDepth(pixs) != 1)
3386 return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", __func__, pixd);
3387 if (!pixm || pixGetDepth(pixm) != 1)
3388 return (PIX *)ERROR_PTR("pixm undefined or not 1 bpp", __func__, pixd);
3389 if (pixd && pixd != pixm)
3390 return (PIX *)ERROR_PTR("operation not inplace", __func__, pixd);
3391
3392 pixt = pixCopy(NULL, pixs);
3393 pixSeedfillBinary(pixt, pixt, pixm, connectivity);
3394 pixd = pixXor(pixd, pixm, pixt);
3395 if (bordersize > 0)
3396 pixSetOrClearBorder(pixd, bordersize, bordersize, bordersize,
3397 bordersize, PIX_CLR);
3398 pixDestroy(&pixt);
3399 return pixd;
3400}
NUMA
struct Numa NUMA
Definition array.h:66
GET_DATA_TWO_BYTES
#define GET_DATA_TWO_BYTES(pdata, n)
Definition arrayaccess.h:212
SET_DATA_BIT
#define SET_DATA_BIT(pdata, n)
Definition arrayaccess.h:127
SET_DATA_TWO_BYTES
#define SET_DATA_TWO_BYTES(pdata, n, val)
Definition arrayaccess.h:222
GET_DATA_BYTE
#define GET_DATA_BYTE(pdata, n)
Definition arrayaccess.h:188
SET_DATA_BYTE
#define SET_DATA_BYTE(pdata, n, val)
Definition arrayaccess.h:198
GET_DATA_BIT
#define GET_DATA_BIT(pdata, n)
Definition arrayaccess.h:123
PIX_DST
#define PIX_DST
Definition pix.h:445
PTA
struct Pta PTA
Definition pix.h:264
L_COPY
@ L_COPY
Definition pix.h:505
L_CLONE
@ L_CLONE
Definition pix.h:506
PIX_XOR
#define PIX_XOR
Definition pix.h:454
PIX
struct Pix PIX
Definition pix.h:228
PIX_SRC
#define PIX_SRC
Definition pix.h:444
PIX_CLR
#define PIX_CLR
Definition pix.h:447
PIX_NOT
#define PIX_NOT(op)
Definition pix.h:446
PIX_SET
#define PIX_SET
Definition pix.h:448
PIXA
struct Pixa PIXA
Definition pix.h:243
BOXA
struct Boxa BOXA
Definition pix.h:255
pixSeedfillGrayInvSimple
l_ok pixSeedfillGrayInvSimple(PIX *pixs, PIX *pixm, l_int32 connectivity)
pixSeedfillGrayInvSimple()
Definition seedfill.c:2014
pixSeedspread
PIX * pixSeedspread(PIX *pixs, l_int32 connectivity)
pixSeedspread()
Definition seedfill.c:2752
distanceFunctionLow
static void distanceFunctionLow(l_uint32 *datad, l_int32 w, l_int32 h, l_int32 d, l_int32 wpld, l_int32 connectivity)
distanceFunctionLow()
Definition seedfill.c:2548
pixQualifyLocalMinima
static l_int32 pixQualifyLocalMinima(PIX *pixs, PIX *pixm, l_int32 maxval)
pixQualifyLocalMinima()
Definition seedfill.c:3037
seedfillBinaryLow
static void seedfillBinaryLow(l_uint32 *datas, l_int32 hs, l_int32 wpls, l_uint32 *datam, l_int32 hm, l_int32 wplm, l_int32 connectivity)
seedfillBinaryLow()
Definition seedfill.c:399
seedfillGrayInvLowSimple
static void seedfillGrayInvLowSimple(l_uint32 *datas, l_int32 w, l_int32 h, l_int32 wpls, l_uint32 *datam, l_int32 wplm, l_int32 connectivity)
seedfillGrayInvLowSimple()
Definition seedfill.c:2247
seedspreadLow
static void seedspreadLow(l_uint32 *datad, l_int32 w, l_int32 h, l_int32 wpld, l_uint32 *datat, l_int32 wplt, l_int32 connectivity)
seedspreadLow()
Definition seedfill.c:2804
pixExtractBorderConnComps
PIX * pixExtractBorderConnComps(PIX *pixs, l_int32 connectivity)
pixExtractBorderConnComps()
Definition seedfill.c:688
seedfillGrayLow
static void seedfillGrayLow(l_uint32 *datas, l_int32 w, l_int32 h, l_int32 wpls, l_uint32 *datam, l_int32 wplm, l_int32 connectivity)
seedfillGrayLow()
Definition seedfill.c:1043
pixRemoveSeededComponents
PIX * pixRemoveSeededComponents(PIX *pixd, PIX *pixs, PIX *pixm, l_int32 connectivity, l_int32 bordersize)
pixRemoveSeededComponents()
Definition seedfill.c:3377
pixDistanceFunction
PIX * pixDistanceFunction(PIX *pixs, l_int32 connectivity, l_int32 outdepth, l_int32 boundcond)
pixDistanceFunction()
Definition seedfill.c:2499
seedfillGrayLowSimple
static void seedfillGrayLowSimple(l_uint32 *datas, l_int32 w, l_int32 h, l_int32 wpls, l_uint32 *datam, l_int32 wplm, l_int32 connectivity)
seedfillGrayLowSimple()
Definition seedfill.c:2093
pixSelectedLocalExtrema
l_ok pixSelectedLocalExtrema(PIX *pixs, l_int32 mindist, PIX **ppixmin, PIX **ppixmax)
pixSelectedLocalExtrema()
Definition seedfill.c:3143
pixSeedfillGrayBasin
PIX * pixSeedfillGrayBasin(PIX *pixb, PIX *pixm, l_int32 delta, l_int32 connectivity)
pixSeedfillGrayBasin()
Definition seedfill.c:2410
pixSeedfillGrayInv
l_ok pixSeedfillGrayInv(PIX *pixs, PIX *pixm, l_int32 connectivity)
pixSeedfillGrayInv()
Definition seedfill.c:968
pixSeedfillBinary
PIX * pixSeedfillBinary(PIX *pixd, PIX *pixs, PIX *pixm, l_int32 connectivity)
pixSeedfillBinary()
Definition seedfill.c:247
pixSelectMinInConnComp
l_ok pixSelectMinInConnComp(PIX *pixs, PIX *pixm, PTA **ppta, NUMA **pnav)
pixSelectMinInConnComp()
Definition seedfill.c:3266
pixFillHolesToBoundingRect
PIX * pixFillHolesToBoundingRect(PIX *pixs, l_int32 minsize, l_float32 maxhfract, l_float32 minfgfract)
pixFillHolesToBoundingRect()
Definition seedfill.c:831
pixLocalExtrema
l_ok pixLocalExtrema(PIX *pixs, l_int32 maxmin, l_int32 minmax, PIX **ppixmin, PIX **ppixmax)
pixLocalExtrema()
Definition seedfill.c:2975
pixFillBgFromBorder
PIX * pixFillBgFromBorder(PIX *pixs, l_int32 connectivity)
pixFillBgFromBorder()
Definition seedfill.c:773
pixFindEqualValues
PIX * pixFindEqualValues(PIX *pixs1, PIX *pixs2)
pixFindEqualValues()
Definition seedfill.c:3201
pixSeedfillBinaryRestricted
PIX * pixSeedfillBinaryRestricted(PIX *pixd, PIX *pixs, PIX *pixm, l_int32 connectivity, l_int32 xmax, l_int32 ymax)
pixSeedfillBinaryRestricted()
Definition seedfill.c:333
pixFillClosedBorders
PIX * pixFillClosedBorders(PIX *pixs, l_int32 connectivity)
pixFillClosedBorders()
Definition seedfill.c:652
pixHolesByFilling
PIX * pixHolesByFilling(PIX *pixs, l_int32 connectivity)
pixHolesByFilling()
Definition seedfill.c:603
seedfillGrayInvLow
static void seedfillGrayInvLow(l_uint32 *datas, l_int32 w, l_int32 h, l_int32 wpls, l_uint32 *datam, l_int32 wplm, l_int32 connectivity)
seedfillGrayInvLow()
Definition seedfill.c:1492
pixSeedfillGray
l_ok pixSeedfillGray(PIX *pixs, PIX *pixm, l_int32 connectivity)
pixSeedfillGray()
Definition seedfill.c:911
pixSeedfillGraySimple
l_ok pixSeedfillGraySimple(PIX *pixs, PIX *pixm, l_int32 connectivity)
pixSeedfillGraySimple()
Definition seedfill.c:1945
pixRemoveBorderConnComps
PIX * pixRemoveBorderConnComps(PIX *pixs, l_int32 connectivity)
pixRemoveBorderConnComps()
Definition seedfill.c:725
L_Pixel
Definition seedfill.c:175