Leptonica 1.82.0
Image processing and image analysis suite
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
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 PROCNAME("pixSeedfillBinary");
258
259 if (!pixs || pixGetDepth(pixs) != 1)
260 return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, pixd);
261 if (!pixm || pixGetDepth(pixm) != 1)
262 return (PIX *)ERROR_PTR("pixm undefined or not 1 bpp", procName, pixd);
263 if (connectivity != 4 && connectivity != 8)
264 return (PIX *)ERROR_PTR("connectivity not in {4,8}", procName, pixd);
265
266 /* Prepare pixd as a copy of pixs if not identical */
267 if ((pixd = pixCopy(pixd, pixs)) == NULL)
268 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
269 pixSetPadBits(pixd, 0); /* be safe: */
270 pixSetPadBits(pixm, 0); /* avoid using uninitialized memory */
271
272 /* pixt is used to test for completion */
273 if ((pixt = pixCreateTemplate(pixs)) == NULL)
274 return (PIX *)ERROR_PTR("pixt not made", procName, pixd);
275
276 hd = pixGetHeight(pixd);
277 hm = pixGetHeight(pixm); /* included so seedfillBinaryLow() can clip */
278 datad = pixGetData(pixd);
279 datam = pixGetData(pixm);
280 wpld = pixGetWpl(pixd);
281 wplm = pixGetWpl(pixm);
282
283
284 for (i = 0; i < MaxIters; i++) {
285 pixCopy(pixt, pixd);
286 seedfillBinaryLow(datad, hd, wpld, datam, hm, wplm, connectivity);
287 pixEqual(pixd, pixt, &boolval);
288 if (boolval == 1) {
289#if DEBUG_PRINT_ITERS
290 lept_stderr("Binary seed fill converged: %d iters\n", i + 1);
291#endif /* DEBUG_PRINT_ITERS */
292 break;
293 }
294 }
295
296 pixDestroy(&pixt);
297 return pixd;
298}
299
300
334PIX *
335pixSeedfillBinaryRestricted(PIX *pixd,
336 PIX *pixs,
337 PIX *pixm,
338 l_int32 connectivity,
339 l_int32 xmax,
340 l_int32 ymax)
341{
342l_int32 w, h;
343PIX *pix1, *pix2;
344
345 PROCNAME("pixSeedfillBinaryRestricted");
346
347 if (!pixs || pixGetDepth(pixs) != 1)
348 return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, pixd);
349 if (!pixm || pixGetDepth(pixm) != 1)
350 return (PIX *)ERROR_PTR("pixm undefined or not 1 bpp", procName, pixd);
351 if (connectivity != 4 && connectivity != 8)
352 return (PIX *)ERROR_PTR("connectivity not in {4,8}", procName, pixd);
353 if (xmax == 0 && ymax == 0) /* no filling permitted */
354 return pixClone(pixs);
355 if (xmax < 0 || ymax < 0) {
356 L_ERROR("xmax and ymax must be non-negative", procName);
357 return pixClone(pixs);
358 }
359
360 /* Full fill from the seed into the mask. */
361 if ((pix1 = pixSeedfillBinary(NULL, pixs, pixm, connectivity)) == NULL)
362 return (PIX *)ERROR_PTR("pix1 not made", procName, pixd);
363
364 /* Dilate the seed. This gives the maximal region where changes
365 * are permitted. Invert to get the region where pixs is
366 * not allowed to change. */
367 pix2 = pixDilateCompBrick(NULL, pixs, 2 * xmax + 1, 2 * ymax + 1);
368 pixInvert(pix2, pix2);
369
370 /* Blank the region of pix1 specified by the fg of pix2.
371 * This is not yet the final result, because it may have fg pixels
372 * that are not accessible from the seed in the restricted distance.
373 * For example, such pixels may be connected to the original seed,
374 * but through a path that goes outside the permitted region. */
375 pixGetDimensions(pixs, &w, &h, NULL);
376 pixRasterop(pix1, 0, 0, w, h, PIX_DST & PIX_NOT(PIX_SRC), pix2, 0, 0);
377
378 /* To get the accessible pixels in the restricted region, do
379 * a second seedfill from the original seed, using pix1 as
380 * a mask. The result, in pixd, will not have any bad fg
381 * pixels that were in pix1. */
382 pixd = pixSeedfillBinary(pixd, pixs, pix1, connectivity);
383
384 pixDestroy(&pix1);
385 pixDestroy(&pix2);
386 return pixd;
387}
388
389
402static void
403seedfillBinaryLow(l_uint32 *datas,
404 l_int32 hs,
405 l_int32 wpls,
406 l_uint32 *datam,
407 l_int32 hm,
408 l_int32 wplm,
409 l_int32 connectivity)
410{
411l_int32 i, j, h, wpl;
412l_uint32 word, mask;
413l_uint32 wordabove, wordleft, wordbelow, wordright;
414l_uint32 wordprev; /* test against this in previous iteration */
415l_uint32 *lines, *linem;
416
417 PROCNAME("seedfillBinaryLow");
418
419 h = L_MIN(hs, hm);
420 wpl = L_MIN(wpls, wplm);
421
422 switch (connectivity)
423 {
424 case 4:
425 /* UL --> LR scan */
426 for (i = 0; i < h; i++) {
427 lines = datas + i * wpls;
428 linem = datam + i * wplm;
429 for (j = 0; j < wpl; j++) {
430 word = *(lines + j);
431 mask = *(linem + j);
432
433 /* OR from word above and from word to left; mask */
434 if (i > 0) {
435 wordabove = *(lines - wpls + j);
436 word |= wordabove;
437 }
438 if (j > 0) {
439 wordleft = *(lines + j - 1);
440 word |= wordleft << 31;
441 }
442 word &= mask;
443
444 /* No need to fill horizontally? */
445 if (!word || !(~word)) {
446 *(lines + j) = word;
447 continue;
448 }
449
450 while (1) {
451 wordprev = word;
452 word = (word | (word >> 1) | (word << 1)) & mask;
453 if ((word ^ wordprev) == 0) {
454 *(lines + j) = word;
455 break;
456 }
457 }
458 }
459 }
460
461 /* LR --> UL scan */
462 for (i = h - 1; i >= 0; i--) {
463 lines = datas + i * wpls;
464 linem = datam + i * wplm;
465 for (j = wpl - 1; j >= 0; j--) {
466 word = *(lines + j);
467 mask = *(linem + j);
468
469 /* OR from word below and from word to right; mask */
470 if (i < h - 1) {
471 wordbelow = *(lines + wpls + j);
472 word |= wordbelow;
473 }
474 if (j < wpl - 1) {
475 wordright = *(lines + j + 1);
476 word |= wordright >> 31;
477 }
478 word &= mask;
479
480 /* No need to fill horizontally? */
481 if (!word || !(~word)) {
482 *(lines + j) = word;
483 continue;
484 }
485
486 while (1) {
487 wordprev = word;
488 word = (word | (word >> 1) | (word << 1)) & mask;
489 if ((word ^ wordprev) == 0) {
490 *(lines + j) = word;
491 break;
492 }
493 }
494 }
495 }
496 break;
497
498 case 8:
499 /* UL --> LR scan */
500 for (i = 0; i < h; i++) {
501 lines = datas + i * wpls;
502 linem = datam + i * wplm;
503 for (j = 0; j < wpl; j++) {
504 word = *(lines + j);
505 mask = *(linem + j);
506
507 /* OR from words above and from word to left; mask */
508 if (i > 0) {
509 wordabove = *(lines - wpls + j);
510 word |= (wordabove | (wordabove << 1) | (wordabove >> 1));
511 if (j > 0)
512 word |= (*(lines - wpls + j - 1)) << 31;
513 if (j < wpl - 1)
514 word |= (*(lines - wpls + j + 1)) >> 31;
515 }
516 if (j > 0) {
517 wordleft = *(lines + j - 1);
518 word |= wordleft << 31;
519 }
520 word &= mask;
521
522 /* No need to fill horizontally? */
523 if (!word || !(~word)) {
524 *(lines + j) = word;
525 continue;
526 }
527
528 while (1) {
529 wordprev = word;
530 word = (word | (word >> 1) | (word << 1)) & mask;
531 if ((word ^ wordprev) == 0) {
532 *(lines + j) = word;
533 break;
534 }
535 }
536 }
537 }
538
539 /* LR --> UL scan */
540 for (i = h - 1; i >= 0; i--) {
541 lines = datas + i * wpls;
542 linem = datam + i * wplm;
543 for (j = wpl - 1; j >= 0; j--) {
544 word = *(lines + j);
545 mask = *(linem + j);
546
547 /* OR from words below and from word to right; mask */
548 if (i < h - 1) {
549 wordbelow = *(lines + wpls + j);
550 word |= (wordbelow | (wordbelow << 1) | (wordbelow >> 1));
551 if (j > 0)
552 word |= (*(lines + wpls + j - 1)) << 31;
553 if (j < wpl - 1)
554 word |= (*(lines + wpls + j + 1)) >> 31;
555 }
556 if (j < wpl - 1) {
557 wordright = *(lines + j + 1);
558 word |= wordright >> 31;
559 }
560 word &= mask;
561
562 /* No need to fill horizontally? */
563 if (!word || !(~word)) {
564 *(lines + j) = word;
565 continue;
566 }
567
568 while (1) {
569 wordprev = word;
570 word = (word | (word >> 1) | (word << 1)) & mask;
571 if ((word ^ wordprev) == 0) {
572 *(lines + j) = word;
573 break;
574 }
575 }
576 }
577 }
578 break;
579
580 default:
581 L_ERROR("connectivity must be 4 or 8\n", procName);
582 }
583}
584
585
608PIX *
609pixHolesByFilling(PIX *pixs,
610 l_int32 connectivity)
611{
612PIX *pixsi, *pixd;
613
614 PROCNAME("pixHolesByFilling");
615
616 if (!pixs || pixGetDepth(pixs) != 1)
617 return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
618 if (connectivity != 4 && connectivity != 8)
619 return (PIX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
620
621 if ((pixd = pixCreateTemplate(pixs)) == NULL)
622 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
623 if ((pixsi = pixInvert(NULL, pixs)) == NULL) {
624 pixDestroy(&pixd);
625 return (PIX *)ERROR_PTR("pixsi not made", procName, NULL);
626 }
627
628 pixSetOrClearBorder(pixd, 1, 1, 1, 1, PIX_SET);
629 pixSeedfillBinary(pixd, pixd, pixsi, connectivity);
630 pixOr(pixd, pixd, pixs);
631 pixInvert(pixd, pixd);
632 pixDestroy(&pixsi);
633 return pixd;
634}
635
636
659PIX *
660pixFillClosedBorders(PIX *pixs,
661 l_int32 connectivity)
662{
663PIX *pixsi, *pixd;
664
665 PROCNAME("pixFillClosedBorders");
666
667 if (!pixs || pixGetDepth(pixs) != 1)
668 return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
669 if (connectivity != 4 && connectivity != 8)
670 return (PIX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
671
672 if ((pixd = pixCreateTemplate(pixs)) == NULL)
673 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
674 pixSetOrClearBorder(pixd, 1, 1, 1, 1, PIX_SET);
675 pixSubtract(pixd, pixd, pixs);
676 if ((pixsi = pixInvert(NULL, pixs)) == NULL) {
677 pixDestroy(&pixd);
678 return (PIX *)ERROR_PTR("pixsi not made", procName, NULL);
679 }
680
681 pixSeedfillBinary(pixd, pixd, pixsi, connectivity);
682 pixInvert(pixd, pixd);
683 pixDestroy(&pixsi);
684
685 return pixd;
686}
687
688
697PIX *
698pixExtractBorderConnComps(PIX *pixs,
699 l_int32 connectivity)
700{
701PIX *pixd;
702
703 PROCNAME("pixExtractBorderConnComps");
704
705 if (!pixs || pixGetDepth(pixs) != 1)
706 return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
707 if (connectivity != 4 && connectivity != 8)
708 return (PIX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
709
710 /* Start with 1 pixel wide black border as seed in pixd */
711 if ((pixd = pixCreateTemplate(pixs)) == NULL)
712 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
713 pixSetOrClearBorder(pixd, 1, 1, 1, 1, PIX_SET);
714
715 /* Fill in pixd from the seed, using pixs as the filling mask.
716 * This fills all components from pixs that are touching the border. */
717 pixSeedfillBinary(pixd, pixd, pixs, connectivity);
718
719 return pixd;
720}
721
722
736PIX *
737pixRemoveBorderConnComps(PIX *pixs,
738 l_int32 connectivity)
739{
740PIX *pixd;
741
742 PROCNAME("pixRemoveBorderConnComps");
743
744 if (!pixs || pixGetDepth(pixs) != 1)
745 return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
746 if (connectivity != 4 && connectivity != 8)
747 return (PIX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
748
749 /* Fill from a 1 pixel wide seed at the border into all components
750 * in pixs (the filling mask) that are touching the border */
751 pixd = pixExtractBorderConnComps(pixs, connectivity);
752
753 /* Save in pixd only those components in pixs not touching the border */
754 pixXor(pixd, pixd, pixs);
755 return pixd;
756}
757
758
786PIX *
787pixFillBgFromBorder(PIX *pixs,
788 l_int32 connectivity)
789{
790PIX *pixd;
791
792 PROCNAME("pixFillBgFromBorder");
793
794 if (!pixs || pixGetDepth(pixs) != 1)
795 return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
796 if (connectivity != 4 && connectivity != 8)
797 return (PIX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
798
799 /* Invert to turn bg touching the border to a fg component.
800 * Extract this by filling from a 1 pixel wide seed at the border. */
801 pixInvert(pixs, pixs);
802 pixd = pixExtractBorderConnComps(pixs, connectivity);
803 pixInvert(pixs, pixs); /* restore pixs */
804
805 /* Bit-or the filled bg component with pixs */
806 pixOr(pixd, pixd, pixs);
807 return pixd;
808}
809
810
811/*-----------------------------------------------------------------------*
812 * Hole-filling of components to bounding rectangle *
813 *-----------------------------------------------------------------------*/
846PIX *
847pixFillHolesToBoundingRect(PIX *pixs,
848 l_int32 minsize,
849 l_float32 maxhfract,
850 l_float32 minfgfract)
851{
852l_int32 i, x, y, w, h, n, nfg, nh, ntot, area;
853l_int32 *tab;
854l_float32 hfract; /* measured hole fraction */
855l_float32 fgfract; /* measured fg fraction */
856BOXA *boxa;
857PIX *pixd, *pixfg, *pixh;
858PIXA *pixa;
859
860 PROCNAME("pixFillHolesToBoundingRect");
861
862 if (!pixs || pixGetDepth(pixs) != 1)
863 return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
864 maxhfract = L_MIN(L_MAX(maxhfract, 0.0), 1.0);
865 minfgfract = L_MIN(L_MAX(minfgfract, 0.0), 1.0);
866
867 pixd = pixCopy(NULL, pixs);
868 boxa = pixConnComp(pixd, &pixa, 8);
869 n = boxaGetCount(boxa);
870 tab = makePixelSumTab8();
871 for (i = 0; i < n; i++) {
872 boxaGetBoxGeometry(boxa, i, &x, &y, &w, &h);
873 area = w * h;
874 if (area < minsize)
875 continue;
876 pixfg = pixaGetPix(pixa, i, L_COPY);
877 pixh = pixHolesByFilling(pixfg, 4); /* holes only */
878 pixCountPixels(pixfg, &nfg, tab);
879 pixCountPixels(pixh, &nh, tab);
880 hfract = (l_float32)nh / (l_float32)nfg;
881 ntot = nfg;
882 if (hfract <= maxhfract) /* we will fill the holes (at least) */
883 ntot = nfg + nh;
884 fgfract = (l_float32)ntot / (l_float32)area;
885 if (fgfract >= minfgfract) { /* fill to bounding rect */
886 pixSetAll(pixfg);
887 pixRasterop(pixd, x, y, w, h, PIX_SRC, pixfg, 0, 0);
888 } else if (hfract <= maxhfract) { /* fill just the holes */
889 pixRasterop(pixd, x, y, w, h, PIX_DST | PIX_SRC , pixh, 0, 0);
890 }
891 pixDestroy(&pixfg);
892 pixDestroy(&pixh);
893 }
894 boxaDestroy(&boxa);
895 pixaDestroy(&pixa);
896 LEPT_FREE(tab);
897 return pixd;
898}
899
900
901/*-----------------------------------------------------------------------*
902 * Vincent's hybrid Grayscale Seedfill method *
903 *-----------------------------------------------------------------------*/
928l_ok
929pixSeedfillGray(PIX *pixs,
930 PIX *pixm,
931 l_int32 connectivity)
932{
933l_int32 h, w, wpls, wplm;
934l_uint32 *datas, *datam;
935
936 PROCNAME("pixSeedfillGray");
937
938 if (!pixs || pixGetDepth(pixs) != 8)
939 return ERROR_INT("pixs not defined or not 8 bpp", procName, 1);
940 if (!pixm || pixGetDepth(pixm) != 8)
941 return ERROR_INT("pixm not defined or not 8 bpp", procName, 1);
942 if (connectivity != 4 && connectivity != 8)
943 return ERROR_INT("connectivity not in {4,8}", procName, 1);
944
945 /* Make sure the sizes of seed and mask images are the same */
946 if (pixSizesEqual(pixs, pixm) == 0)
947 return ERROR_INT("pixs and pixm sizes differ", procName, 1);
948
949 datas = pixGetData(pixs);
950 datam = pixGetData(pixm);
951 wpls = pixGetWpl(pixs);
952 wplm = pixGetWpl(pixm);
953 pixGetDimensions(pixs, &w, &h, NULL);
954 seedfillGrayLow(datas, w, h, wpls, datam, wplm, connectivity);
955
956 return 0;
957}
958
959
987l_ok
988pixSeedfillGrayInv(PIX *pixs,
989 PIX *pixm,
990 l_int32 connectivity)
991{
992l_int32 h, w, wpls, wplm;
993l_uint32 *datas, *datam;
994
995 PROCNAME("pixSeedfillGrayInv");
996
997 if (!pixs || pixGetDepth(pixs) != 8)
998 return ERROR_INT("pixs not defined or not 8 bpp", procName, 1);
999 if (!pixm || pixGetDepth(pixm) != 8)
1000 return ERROR_INT("pixm not defined or not 8 bpp", procName, 1);
1001 if (connectivity != 4 && connectivity != 8)
1002 return ERROR_INT("connectivity not in {4,8}", procName, 1);
1003
1004 /* Make sure the sizes of seed and mask images are the same */
1005 if (pixSizesEqual(pixs, pixm) == 0)
1006 return ERROR_INT("pixs and pixm sizes differ", procName, 1);
1007
1008 datas = pixGetData(pixs);
1009 datam = pixGetData(pixm);
1010 wpls = pixGetWpl(pixs);
1011 wplm = pixGetWpl(pixm);
1012 pixGetDimensions(pixs, &w, &h, NULL);
1013 seedfillGrayInvLow(datas, w, h, wpls, datam, wplm, connectivity);
1014
1015 return 0;
1016}
1017
1018
1064static void
1065seedfillGrayLow(l_uint32 *datas,
1066 l_int32 w,
1067 l_int32 h,
1068 l_int32 wpls,
1069 l_uint32 *datam,
1070 l_int32 wplm,
1071 l_int32 connectivity)
1072{
1073l_uint8 val1, val2, val3, val4, val5, val6, val7, val8;
1074l_uint8 val, maxval, maskval, boolval;
1075l_int32 i, j, imax, jmax, queue_size;
1076l_uint32 *lines, *linem;
1077L_PIXEL *pixel;
1078L_QUEUE *lq_pixel;
1079
1080 PROCNAME("seedfillGrayLow");
1081
1082 if (connectivity != 4 && connectivity != 8) {
1083 L_ERROR("connectivity must be 4 or 8\n", procName);
1084 return;
1085 }
1086
1087 imax = h - 1;
1088 jmax = w - 1;
1089
1090 /* In the worst case, most of the pixels could be pushed
1091 * onto the FIFO queue during anti-raster scan. However this
1092 * will rarely happen, and we initialize the queue ptr size to
1093 * the image perimeter. */
1094 lq_pixel = lqueueCreate(2 * (w + h));
1095
1096 switch (connectivity)
1097 {
1098 case 4:
1099 /* UL --> LR scan (Raster Order)
1100 * If I : mask image
1101 * J : marker image
1102 * Let p be the currect pixel;
1103 * J(p) <- (max{J(p) union J(p) neighbors in raster order})
1104 * intersection I(p) */
1105 for (i = 0; i < h; i++) {
1106 lines = datas + i * wpls;
1107 linem = datam + i * wplm;
1108 for (j = 0; j < w; j++) {
1109 if ((maskval = GET_DATA_BYTE(linem, j)) > 0) {
1110 maxval = 0;
1111 if (i > 0)
1112 maxval = GET_DATA_BYTE(lines - wpls, j);
1113 if (j > 0) {
1114 val4 = GET_DATA_BYTE(lines, j - 1);
1115 maxval = L_MAX(maxval, val4);
1116 }
1117 val = GET_DATA_BYTE(lines, j);
1118 maxval = L_MAX(maxval, val);
1119 val = L_MIN(maxval, maskval);
1120 SET_DATA_BYTE(lines, j, val);
1121 }
1122 }
1123 }
1124
1125 /* LR --> UL scan (anti-raster order)
1126 * Let p be the currect pixel;
1127 * J(p) <- (max{J(p) union J(p) neighbors in anti-raster order})
1128 * intersection I(p) */
1129 for (i = imax; i >= 0; i--) {
1130 lines = datas + i * wpls;
1131 linem = datam + i * wplm;
1132 for (j = jmax; j >= 0; j--) {
1133 boolval = FALSE;
1134 if ((maskval = GET_DATA_BYTE(linem, j)) > 0) {
1135 maxval = 0;
1136 if (i < imax)
1137 maxval = GET_DATA_BYTE(lines + wpls, j);
1138 if (j < jmax) {
1139 val5 = GET_DATA_BYTE(lines, j + 1);
1140 maxval = L_MAX(maxval, val5);
1141 }
1142 val = GET_DATA_BYTE(lines, j);
1143 maxval = L_MAX(maxval, val);
1144 val = L_MIN(maxval, maskval);
1145 SET_DATA_BYTE(lines, j, val);
1146
1147 /*
1148 * If there exists a point (q) which belongs to J(p)
1149 * neighbors in anti-raster order such that J(q) < J(p)
1150 * and J(q) < I(q) then
1151 * fifo_add(p) */
1152 if (i < imax) {
1153 val7 = GET_DATA_BYTE(lines + wpls, j);
1154 if ((val7 < val) &&
1155 (val7 < GET_DATA_BYTE(linem + wplm, j))) {
1156 boolval = TRUE;
1157 }
1158 }
1159 if (j < jmax) {
1160 val5 = GET_DATA_BYTE(lines, j + 1);
1161 if (!boolval && (val5 < val) &&
1162 (val5 < GET_DATA_BYTE(linem, j + 1))) {
1163 boolval = TRUE;
1164 }
1165 }
1166 if (boolval) {
1167 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1168 pixel->x = i;
1169 pixel->y = j;
1170 lqueueAdd(lq_pixel, pixel);
1171 }
1172 }
1173 }
1174 }
1175
1176 /* Propagation step:
1177 * while fifo_empty = false
1178 * p <- fifo_first()
1179 * for every pixel (q) belong to neighbors of (p)
1180 * if J(q) < J(p) and I(q) != J(q)
1181 * J(q) <- min(J(p), I(q));
1182 * fifo_add(q);
1183 * end
1184 * end
1185 * end */
1186 queue_size = lqueueGetCount(lq_pixel);
1187 while (queue_size) {
1188 pixel = (L_PIXEL *)lqueueRemove(lq_pixel);
1189 i = pixel->x;
1190 j = pixel->y;
1191 LEPT_FREE(pixel);
1192 lines = datas + i * wpls;
1193 linem = datam + i * wplm;
1194
1195 if ((val = GET_DATA_BYTE(lines, j)) > 0) {
1196 if (i > 0) {
1197 val2 = GET_DATA_BYTE(lines - wpls, j);
1198 maskval = GET_DATA_BYTE(linem - wplm, j);
1199 if (val > val2 && val2 != maskval) {
1200 SET_DATA_BYTE(lines - wpls, j, L_MIN(val, maskval));
1201 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1202 pixel->x = i - 1;
1203 pixel->y = j;
1204 lqueueAdd(lq_pixel, pixel);
1205 }
1206
1207 }
1208 if (j > 0) {
1209 val4 = GET_DATA_BYTE(lines, j - 1);
1210 maskval = GET_DATA_BYTE(linem, j - 1);
1211 if (val > val4 && val4 != maskval) {
1212 SET_DATA_BYTE(lines, j - 1, L_MIN(val, maskval));
1213 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1214 pixel->x = i;
1215 pixel->y = j - 1;
1216 lqueueAdd(lq_pixel, pixel);
1217 }
1218 }
1219 if (i < imax) {
1220 val7 = GET_DATA_BYTE(lines + wpls, j);
1221 maskval = GET_DATA_BYTE(linem + wplm, j);
1222 if (val > val7 && val7 != maskval) {
1223 SET_DATA_BYTE(lines + wpls, j, L_MIN(val, maskval));
1224 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1225 pixel->x = i + 1;
1226 pixel->y = j;
1227 lqueueAdd(lq_pixel, pixel);
1228 }
1229 }
1230 if (j < jmax) {
1231 val5 = GET_DATA_BYTE(lines, j + 1);
1232 maskval = GET_DATA_BYTE(linem, j + 1);
1233 if (val > val5 && val5 != maskval) {
1234 SET_DATA_BYTE(lines, j + 1, L_MIN(val, maskval));
1235 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1236 pixel->x = i;
1237 pixel->y = j + 1;
1238 lqueueAdd(lq_pixel, pixel);
1239 }
1240 }
1241 }
1242
1243 queue_size = lqueueGetCount(lq_pixel);
1244 }
1245 break;
1246
1247 case 8:
1248 /* UL --> LR scan (Raster Order)
1249 * If I : mask image
1250 * J : marker image
1251 * Let p be the currect pixel;
1252 * J(p) <- (max{J(p) union J(p) neighbors in raster order})
1253 * intersection I(p) */
1254 for (i = 0; i < h; i++) {
1255 lines = datas + i * wpls;
1256 linem = datam + i * wplm;
1257 for (j = 0; j < w; j++) {
1258 if ((maskval = GET_DATA_BYTE(linem, j)) > 0) {
1259 maxval = 0;
1260 if (i > 0) {
1261 if (j > 0)
1262 maxval = GET_DATA_BYTE(lines - wpls, j - 1);
1263 if (j < jmax) {
1264 val3 = GET_DATA_BYTE(lines - wpls, j + 1);
1265 maxval = L_MAX(maxval, val3);
1266 }
1267 val2 = GET_DATA_BYTE(lines - wpls, j);
1268 maxval = L_MAX(maxval, val2);
1269 }
1270 if (j > 0) {
1271 val4 = GET_DATA_BYTE(lines, j - 1);
1272 maxval = L_MAX(maxval, val4);
1273 }
1274 val = GET_DATA_BYTE(lines, j);
1275 maxval = L_MAX(maxval, val);
1276 val = L_MIN(maxval, maskval);
1277 SET_DATA_BYTE(lines, j, val);
1278 }
1279 }
1280 }
1281
1282 /* LR --> UL scan (anti-raster order)
1283 * Let p be the currect pixel;
1284 * J(p) <- (max{J(p) union J(p) neighbors in anti-raster order})
1285 * intersection I(p) */
1286 for (i = imax; i >= 0; i--) {
1287 lines = datas + i * wpls;
1288 linem = datam + i * wplm;
1289 for (j = jmax; j >= 0; j--) {
1290 boolval = FALSE;
1291 if ((maskval = GET_DATA_BYTE(linem, j)) > 0) {
1292 maxval = 0;
1293 if (i < imax) {
1294 if (j > 0) {
1295 maxval = GET_DATA_BYTE(lines + wpls, j - 1);
1296 }
1297 if (j < jmax) {
1298 val8 = GET_DATA_BYTE(lines + wpls, j + 1);
1299 maxval = L_MAX(maxval, val8);
1300 }
1301 val7 = GET_DATA_BYTE(lines + wpls, j);
1302 maxval = L_MAX(maxval, val7);
1303 }
1304 if (j < jmax) {
1305 val5 = GET_DATA_BYTE(lines, j + 1);
1306 maxval = L_MAX(maxval, val5);
1307 }
1308 val = GET_DATA_BYTE(lines, j);
1309 maxval = L_MAX(maxval, val);
1310 val = L_MIN(maxval, maskval);
1311 SET_DATA_BYTE(lines, j, val);
1312
1313 /* If there exists a point (q) which belongs to J(p)
1314 * neighbors in anti-raster order such that J(q) < J(p)
1315 * and J(q) < I(q) then
1316 * fifo_add(p) */
1317 if (i < imax) {
1318 if (j > 0) {
1319 val6 = GET_DATA_BYTE(lines + wpls, j - 1);
1320 if ((val6 < val) &&
1321 (val6 < GET_DATA_BYTE(linem + wplm, j - 1))) {
1322 boolval = TRUE;
1323 }
1324 }
1325 if (j < jmax) {
1326 val8 = GET_DATA_BYTE(lines + wpls, j + 1);
1327 if (!boolval && (val8 < val) &&
1328 (val8 < GET_DATA_BYTE(linem + wplm, j + 1))) {
1329 boolval = TRUE;
1330 }
1331 }
1332 val7 = GET_DATA_BYTE(lines + wpls, j);
1333 if (!boolval && (val7 < val) &&
1334 (val7 < GET_DATA_BYTE(linem + wplm, j))) {
1335 boolval = TRUE;
1336 }
1337 }
1338 if (j < jmax) {
1339 val5 = GET_DATA_BYTE(lines, j + 1);
1340 if (!boolval && (val5 < val) &&
1341 (val5 < GET_DATA_BYTE(linem, j + 1))) {
1342 boolval = TRUE;
1343 }
1344 }
1345 if (boolval) {
1346 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1347 pixel->x = i;
1348 pixel->y = j;
1349 lqueueAdd(lq_pixel, pixel);
1350 }
1351 }
1352 }
1353 }
1354
1355 /* Propagation step:
1356 * while fifo_empty = false
1357 * p <- fifo_first()
1358 * for every pixel (q) belong to neighbors of (p)
1359 * if J(q) < J(p) and I(q) != J(q)
1360 * J(q) <- min(J(p), I(q));
1361 * fifo_add(q);
1362 * end
1363 * end
1364 * end */
1365 queue_size = lqueueGetCount(lq_pixel);
1366 while (queue_size) {
1367 pixel = (L_PIXEL *)lqueueRemove(lq_pixel);
1368 i = pixel->x;
1369 j = pixel->y;
1370 LEPT_FREE(pixel);
1371 lines = datas + i * wpls;
1372 linem = datam + i * wplm;
1373
1374 if ((val = GET_DATA_BYTE(lines, j)) > 0) {
1375 if (i > 0) {
1376 if (j > 0) {
1377 val1 = GET_DATA_BYTE(lines - wpls, j - 1);
1378 maskval = GET_DATA_BYTE(linem - wplm, j - 1);
1379 if (val > val1 && val1 != maskval) {
1380 SET_DATA_BYTE(lines - wpls, j - 1,
1381 L_MIN(val, maskval));
1382 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1383 pixel->x = i - 1;
1384 pixel->y = j - 1;
1385 lqueueAdd(lq_pixel, pixel);
1386 }
1387 }
1388 if (j < jmax) {
1389 val3 = GET_DATA_BYTE(lines - wpls, j + 1);
1390 maskval = GET_DATA_BYTE(linem - wplm, j + 1);
1391 if (val > val3 && val3 != maskval) {
1392 SET_DATA_BYTE(lines - wpls, j + 1,
1393 L_MIN(val, maskval));
1394 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1395 pixel->x = i - 1;
1396 pixel->y = j + 1;
1397 lqueueAdd(lq_pixel, pixel);
1398 }
1399 }
1400 val2 = GET_DATA_BYTE(lines - wpls, j);
1401 maskval = GET_DATA_BYTE(linem - wplm, j);
1402 if (val > val2 && val2 != maskval) {
1403 SET_DATA_BYTE(lines - wpls, j, L_MIN(val, maskval));
1404 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1405 pixel->x = i - 1;
1406 pixel->y = j;
1407 lqueueAdd(lq_pixel, pixel);
1408 }
1409
1410 }
1411 if (j > 0) {
1412 val4 = GET_DATA_BYTE(lines, j - 1);
1413 maskval = GET_DATA_BYTE(linem, j - 1);
1414 if (val > val4 && val4 != maskval) {
1415 SET_DATA_BYTE(lines, j - 1, L_MIN(val, maskval));
1416 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1417 pixel->x = i;
1418 pixel->y = j - 1;
1419 lqueueAdd(lq_pixel, pixel);
1420 }
1421 }
1422 if (i < imax) {
1423 if (j > 0) {
1424 val6 = GET_DATA_BYTE(lines + wpls, j - 1);
1425 maskval = GET_DATA_BYTE(linem + wplm, j - 1);
1426 if (val > val6 && val6 != maskval) {
1427 SET_DATA_BYTE(lines + wpls, j - 1,
1428 L_MIN(val, maskval));
1429 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1430 pixel->x = i + 1;
1431 pixel->y = j - 1;
1432 lqueueAdd(lq_pixel, pixel);
1433 }
1434 }
1435 if (j < jmax) {
1436 val8 = GET_DATA_BYTE(lines + wpls, j + 1);
1437 maskval = GET_DATA_BYTE(linem + wplm, j + 1);
1438 if (val > val8 && val8 != maskval) {
1439 SET_DATA_BYTE(lines + wpls, j + 1,
1440 L_MIN(val, maskval));
1441 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1442 pixel->x = i + 1;
1443 pixel->y = j + 1;
1444 lqueueAdd(lq_pixel, pixel);
1445 }
1446 }
1447 val7 = GET_DATA_BYTE(lines + wpls, j);
1448 maskval = GET_DATA_BYTE(linem + wplm, j);
1449 if (val > val7 && val7 != maskval) {
1450 SET_DATA_BYTE(lines + wpls, j, L_MIN(val, maskval));
1451 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1452 pixel->x = i + 1;
1453 pixel->y = j;
1454 lqueueAdd(lq_pixel, pixel);
1455 }
1456 }
1457 if (j < jmax) {
1458 val5 = GET_DATA_BYTE(lines, j + 1);
1459 maskval = GET_DATA_BYTE(linem, j + 1);
1460 if (val > val5 && val5 != maskval) {
1461 SET_DATA_BYTE(lines, j + 1, L_MIN(val, maskval));
1462 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1463 pixel->x = i;
1464 pixel->y = j + 1;
1465 lqueueAdd(lq_pixel, pixel);
1466 }
1467 }
1468 }
1469
1470 queue_size = lqueueGetCount(lq_pixel);
1471 }
1472 break;
1473
1474 default:
1475 L_ERROR("shouldn't get here!\n", procName);
1476 }
1477
1478 lqueueDestroy(&lq_pixel, TRUE);
1479}
1480
1481
1515static void
1516seedfillGrayInvLow(l_uint32 *datas,
1517 l_int32 w,
1518 l_int32 h,
1519 l_int32 wpls,
1520 l_uint32 *datam,
1521 l_int32 wplm,
1522 l_int32 connectivity)
1523{
1524l_uint8 val1, val2, val3, val4, val5, val6, val7, val8;
1525l_uint8 val, maxval, maskval, boolval;
1526l_int32 i, j, imax, jmax, queue_size;
1527l_uint32 *lines, *linem;
1528L_PIXEL *pixel;
1529L_QUEUE *lq_pixel;
1530
1531 PROCNAME("seedfillGrayInvLow");
1532
1533 if (connectivity != 4 && connectivity != 8) {
1534 L_ERROR("connectivity must be 4 or 8\n", procName);
1535 return;
1536 }
1537
1538 imax = h - 1;
1539 jmax = w - 1;
1540
1541 /* In the worst case, most of the pixels could be pushed
1542 * onto the FIFO queue during anti-raster scan. However this
1543 * will rarely happen, and we initialize the queue ptr size to
1544 * the image perimeter. */
1545 lq_pixel = lqueueCreate(2 * (w + h));
1546
1547 switch (connectivity)
1548 {
1549 case 4:
1550 /* UL --> LR scan (Raster Order)
1551 * If I : mask image
1552 * J : marker image
1553 * Let p be the currect pixel;
1554 * tmp <- max{J(p) union J(p) neighbors in raster order}
1555 * if (tmp > I(p))
1556 * J(p) <- tmp
1557 * end */
1558 for (i = 0; i < h; i++) {
1559 lines = datas + i * wpls;
1560 linem = datam + i * wplm;
1561 for (j = 0; j < w; j++) {
1562 if ((maskval = GET_DATA_BYTE(linem, j)) < 255) {
1563 maxval = GET_DATA_BYTE(lines, j);
1564 if (i > 0) {
1565 val2 = GET_DATA_BYTE(lines - wpls, j);
1566 maxval = L_MAX(maxval, val2);
1567 }
1568 if (j > 0) {
1569 val4 = GET_DATA_BYTE(lines, j - 1);
1570 maxval = L_MAX(maxval, val4);
1571 }
1572 if (maxval > maskval)
1573 SET_DATA_BYTE(lines, j, maxval);
1574 }
1575 }
1576 }
1577
1578 /* LR --> UL scan (anti-raster order)
1579 * If I : mask image
1580 * J : marker image
1581 * Let p be the currect pixel;
1582 * tmp <- max{J(p) union J(p) neighbors in anti-raster order}
1583 * if (tmp > I(p))
1584 * J(p) <- tmp
1585 * end */
1586 for (i = imax; i >= 0; i--) {
1587 lines = datas + i * wpls;
1588 linem = datam + i * wplm;
1589 for (j = jmax; j >= 0; j--) {
1590 boolval = FALSE;
1591 if ((maskval = GET_DATA_BYTE(linem, j)) < 255) {
1592 val = maxval = GET_DATA_BYTE(lines, j);
1593 if (i < imax) {
1594 val7 = GET_DATA_BYTE(lines + wpls, j);
1595 maxval = L_MAX(maxval, val7);
1596 }
1597 if (j < jmax) {
1598 val5 = GET_DATA_BYTE(lines, j + 1);
1599 maxval = L_MAX(maxval, val5);
1600 }
1601 if (maxval > maskval)
1602 SET_DATA_BYTE(lines, j, maxval);
1603 val = GET_DATA_BYTE(lines, j);
1604
1605 /*
1606 * If there exists a point (q) which belongs to J(p)
1607 * neighbors in anti-raster order such that J(q) < J(p)
1608 * and J(p) > I(q) then
1609 * fifo_add(p) */
1610 if (i < imax) {
1611 val7 = GET_DATA_BYTE(lines + wpls, j);
1612 if ((val7 < val) &&
1613 (val > GET_DATA_BYTE(linem + wplm, j))) {
1614 boolval = TRUE;
1615 }
1616 }
1617 if (j < jmax) {
1618 val5 = GET_DATA_BYTE(lines, j + 1);
1619 if (!boolval && (val5 < val) &&
1620 (val > GET_DATA_BYTE(linem, j + 1))) {
1621 boolval = TRUE;
1622 }
1623 }
1624 if (boolval) {
1625 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1626 pixel->x = i;
1627 pixel->y = j;
1628 lqueueAdd(lq_pixel, pixel);
1629 }
1630 }
1631 }
1632 }
1633
1634 /* Propagation step:
1635 * while fifo_empty = false
1636 * p <- fifo_first()
1637 * for every pixel (q) belong to neighbors of (p)
1638 * if J(q) < J(p) and J(p) > I(q)
1639 * J(q) <- min(J(p), I(q));
1640 * fifo_add(q);
1641 * end
1642 * end
1643 * end */
1644 queue_size = lqueueGetCount(lq_pixel);
1645 while (queue_size) {
1646 pixel = (L_PIXEL *)lqueueRemove(lq_pixel);
1647 i = pixel->x;
1648 j = pixel->y;
1649 LEPT_FREE(pixel);
1650 lines = datas + i * wpls;
1651 linem = datam + i * wplm;
1652
1653 if ((val = GET_DATA_BYTE(lines, j)) > 0) {
1654 if (i > 0) {
1655 val2 = GET_DATA_BYTE(lines - wpls, j);
1656 maskval = GET_DATA_BYTE(linem - wplm, j);
1657 if (val > val2 && val > maskval) {
1658 SET_DATA_BYTE(lines - wpls, j, val);
1659 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1660 pixel->x = i - 1;
1661 pixel->y = j;
1662 lqueueAdd(lq_pixel, pixel);
1663 }
1664
1665 }
1666 if (j > 0) {
1667 val4 = GET_DATA_BYTE(lines, j - 1);
1668 maskval = GET_DATA_BYTE(linem, j - 1);
1669 if (val > val4 && val > maskval) {
1670 SET_DATA_BYTE(lines, j - 1, val);
1671 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1672 pixel->x = i;
1673 pixel->y = j - 1;
1674 lqueueAdd(lq_pixel, pixel);
1675 }
1676 }
1677 if (i < imax) {
1678 val7 = GET_DATA_BYTE(lines + wpls, j);
1679 maskval = GET_DATA_BYTE(linem + wplm, j);
1680 if (val > val7 && val > maskval) {
1681 SET_DATA_BYTE(lines + wpls, j, val);
1682 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1683 pixel->x = i + 1;
1684 pixel->y = j;
1685 lqueueAdd(lq_pixel, pixel);
1686 }
1687 }
1688 if (j < jmax) {
1689 val5 = GET_DATA_BYTE(lines, j + 1);
1690 maskval = GET_DATA_BYTE(linem, j + 1);
1691 if (val > val5 && val > maskval) {
1692 SET_DATA_BYTE(lines, j + 1, val);
1693 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1694 pixel->x = i;
1695 pixel->y = j + 1;
1696 lqueueAdd(lq_pixel, pixel);
1697 }
1698 }
1699 }
1700
1701 queue_size = lqueueGetCount(lq_pixel);
1702 }
1703 break;
1704
1705 case 8:
1706 /* UL --> LR scan (Raster Order)
1707 * If I : mask image
1708 * J : marker image
1709 * Let p be the currect pixel;
1710 * tmp <- max{J(p) union J(p) neighbors in raster order}
1711 * if (tmp > I(p))
1712 * J(p) <- tmp
1713 * end */
1714 for (i = 0; i < h; i++) {
1715 lines = datas + i * wpls;
1716 linem = datam + i * wplm;
1717 for (j = 0; j < w; j++) {
1718 if ((maskval = GET_DATA_BYTE(linem, j)) < 255) {
1719 maxval = GET_DATA_BYTE(lines, j);
1720 if (i > 0) {
1721 if (j > 0) {
1722 val1 = GET_DATA_BYTE(lines - wpls, j - 1);
1723 maxval = L_MAX(maxval, val1);
1724 }
1725 if (j < jmax) {
1726 val3 = GET_DATA_BYTE(lines - wpls, j + 1);
1727 maxval = L_MAX(maxval, val3);
1728 }
1729 val2 = GET_DATA_BYTE(lines - wpls, j);
1730 maxval = L_MAX(maxval, val2);
1731 }
1732 if (j > 0) {
1733 val4 = GET_DATA_BYTE(lines, j - 1);
1734 maxval = L_MAX(maxval, val4);
1735 }
1736 if (maxval > maskval)
1737 SET_DATA_BYTE(lines, j, maxval);
1738 }
1739 }
1740 }
1741
1742 /* LR --> UL scan (anti-raster order)
1743 * If I : mask image
1744 * J : marker image
1745 * Let p be the currect pixel;
1746 * tmp <- max{J(p) union J(p) neighbors in anti-raster order}
1747 * if (tmp > I(p))
1748 * J(p) <- tmp
1749 * end */
1750 for (i = imax; i >= 0; i--) {
1751 lines = datas + i * wpls;
1752 linem = datam + i * wplm;
1753 for (j = jmax; j >= 0; j--) {
1754 boolval = FALSE;
1755 if ((maskval = GET_DATA_BYTE(linem, j)) < 255) {
1756 maxval = GET_DATA_BYTE(lines, j);
1757 if (i < imax) {
1758 if (j > 0) {
1759 val6 = GET_DATA_BYTE(lines + wpls, j - 1);
1760 maxval = L_MAX(maxval, val6);
1761 }
1762 if (j < jmax) {
1763 val8 = GET_DATA_BYTE(lines + wpls, j + 1);
1764 maxval = L_MAX(maxval, val8);
1765 }
1766 val7 = GET_DATA_BYTE(lines + wpls, j);
1767 maxval = L_MAX(maxval, val7);
1768 }
1769 if (j < jmax) {
1770 val5 = GET_DATA_BYTE(lines, j + 1);
1771 maxval = L_MAX(maxval, val5);
1772 }
1773 if (maxval > maskval)
1774 SET_DATA_BYTE(lines, j, maxval);
1775 val = GET_DATA_BYTE(lines, j);
1776
1777 /*
1778 * If there exists a point (q) which belongs to J(p)
1779 * neighbors in anti-raster order such that J(q) < J(p)
1780 * and J(p) > I(q) then
1781 * fifo_add(p) */
1782 if (i < imax) {
1783 if (j > 0) {
1784 val6 = GET_DATA_BYTE(lines + wpls, j - 1);
1785 if ((val6 < val) &&
1786 (val > GET_DATA_BYTE(linem + wplm, j - 1))) {
1787 boolval = TRUE;
1788 }
1789 }
1790 if (j < jmax) {
1791 val8 = GET_DATA_BYTE(lines + wpls, j + 1);
1792 if (!boolval && (val8 < val) &&
1793 (val > GET_DATA_BYTE(linem + wplm, j + 1))) {
1794 boolval = TRUE;
1795 }
1796 }
1797 val7 = GET_DATA_BYTE(lines + wpls, j);
1798 if (!boolval && (val7 < val) &&
1799 (val > GET_DATA_BYTE(linem + wplm, j))) {
1800 boolval = TRUE;
1801 }
1802 }
1803 if (j < jmax) {
1804 val5 = GET_DATA_BYTE(lines, j + 1);
1805 if (!boolval && (val5 < val) &&
1806 (val > GET_DATA_BYTE(linem, j + 1))) {
1807 boolval = TRUE;
1808 }
1809 }
1810 if (boolval) {
1811 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1812 pixel->x = i;
1813 pixel->y = j;
1814 lqueueAdd(lq_pixel, pixel);
1815 }
1816 }
1817 }
1818 }
1819
1820 /* Propagation step:
1821 * while fifo_empty = false
1822 * p <- fifo_first()
1823 * for every pixel (q) belong to neighbors of (p)
1824 * if J(q) < J(p) and J(p) > I(q)
1825 * J(q) <- min(J(p), I(q));
1826 * fifo_add(q);
1827 * end
1828 * end
1829 * end */
1830 queue_size = lqueueGetCount(lq_pixel);
1831 while (queue_size) {
1832 pixel = (L_PIXEL *)lqueueRemove(lq_pixel);
1833 i = pixel->x;
1834 j = pixel->y;
1835 LEPT_FREE(pixel);
1836 lines = datas + i * wpls;
1837 linem = datam + i * wplm;
1838
1839 if ((val = GET_DATA_BYTE(lines, j)) > 0) {
1840 if (i > 0) {
1841 if (j > 0) {
1842 val1 = GET_DATA_BYTE(lines - wpls, j - 1);
1843 maskval = GET_DATA_BYTE(linem - wplm, j - 1);
1844 if (val > val1 && val > maskval) {
1845 SET_DATA_BYTE(lines - wpls, j - 1, val);
1846 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1847 pixel->x = i - 1;
1848 pixel->y = j - 1;
1849 lqueueAdd(lq_pixel, pixel);
1850 }
1851 }
1852 if (j < jmax) {
1853 val3 = GET_DATA_BYTE(lines - wpls, j + 1);
1854 maskval = GET_DATA_BYTE(linem - wplm, j + 1);
1855 if (val > val3 && val > maskval) {
1856 SET_DATA_BYTE(lines - wpls, j + 1, val);
1857 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1858 pixel->x = i - 1;
1859 pixel->y = j + 1;
1860 lqueueAdd(lq_pixel, pixel);
1861 }
1862 }
1863 val2 = GET_DATA_BYTE(lines - wpls, j);
1864 maskval = GET_DATA_BYTE(linem - wplm, j);
1865 if (val > val2 && val > maskval) {
1866 SET_DATA_BYTE(lines - wpls, j, val);
1867 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1868 pixel->x = i - 1;
1869 pixel->y = j;
1870 lqueueAdd(lq_pixel, pixel);
1871 }
1872
1873 }
1874 if (j > 0) {
1875 val4 = GET_DATA_BYTE(lines, j - 1);
1876 maskval = GET_DATA_BYTE(linem, j - 1);
1877 if (val > val4 && val > maskval) {
1878 SET_DATA_BYTE(lines, j - 1, val);
1879 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1880 pixel->x = i;
1881 pixel->y = j - 1;
1882 lqueueAdd(lq_pixel, pixel);
1883 }
1884 }
1885 if (i < imax) {
1886 if (j > 0) {
1887 val6 = GET_DATA_BYTE(lines + wpls, j - 1);
1888 maskval = GET_DATA_BYTE(linem + wplm, j - 1);
1889 if (val > val6 && val > maskval) {
1890 SET_DATA_BYTE(lines + wpls, j - 1, val);
1891 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1892 pixel->x = i + 1;
1893 pixel->y = j - 1;
1894 lqueueAdd(lq_pixel, pixel);
1895 }
1896 }
1897 if (j < jmax) {
1898 val8 = GET_DATA_BYTE(lines + wpls, j + 1);
1899 maskval = GET_DATA_BYTE(linem + wplm, j + 1);
1900 if (val > val8 && val > maskval) {
1901 SET_DATA_BYTE(lines + wpls, j + 1, val);
1902 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1903 pixel->x = i + 1;
1904 pixel->y = j + 1;
1905 lqueueAdd(lq_pixel, pixel);
1906 }
1907 }
1908 val7 = GET_DATA_BYTE(lines + wpls, j);
1909 maskval = GET_DATA_BYTE(linem + wplm, j);
1910 if (val > val7 && val > maskval) {
1911 SET_DATA_BYTE(lines + wpls, j, val);
1912 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1913 pixel->x = i + 1;
1914 pixel->y = j;
1915 lqueueAdd(lq_pixel, pixel);
1916 }
1917 }
1918 if (j < jmax) {
1919 val5 = GET_DATA_BYTE(lines, j + 1);
1920 maskval = GET_DATA_BYTE(linem, j + 1);
1921 if (val > val5 && val > maskval) {
1922 SET_DATA_BYTE(lines, j + 1, val);
1923 pixel = (L_PIXEL *)LEPT_CALLOC(1, sizeof(L_PIXEL));
1924 pixel->x = i;
1925 pixel->y = j + 1;
1926 lqueueAdd(lq_pixel, pixel);
1927 }
1928 }
1929 }
1930
1931 queue_size = lqueueGetCount(lq_pixel);
1932 }
1933 break;
1934
1935 default:
1936 L_ERROR("shouldn't get here!\n", procName);
1937 }
1938
1939 lqueueDestroy(&lq_pixel, TRUE);
1940}
1941
1942
1943/*-----------------------------------------------------------------------*
1944 * Vincent's Iterative Grayscale Seedfill method *
1945 *-----------------------------------------------------------------------*/
1970l_ok
1971pixSeedfillGraySimple(PIX *pixs,
1972 PIX *pixm,
1973 l_int32 connectivity)
1974{
1975l_int32 i, h, w, wpls, wplm, boolval;
1976l_uint32 *datas, *datam;
1977PIX *pixt;
1978
1979 PROCNAME("pixSeedfillGraySimple");
1980
1981 if (!pixs || pixGetDepth(pixs) != 8)
1982 return ERROR_INT("pixs not defined or not 8 bpp", procName, 1);
1983 if (!pixm || pixGetDepth(pixm) != 8)
1984 return ERROR_INT("pixm not defined or not 8 bpp", procName, 1);
1985 if (connectivity != 4 && connectivity != 8)
1986 return ERROR_INT("connectivity not in {4,8}", procName, 1);
1987
1988 /* Make sure the sizes of seed and mask images are the same */
1989 if (pixSizesEqual(pixs, pixm) == 0)
1990 return ERROR_INT("pixs and pixm sizes differ", procName, 1);
1991
1992 /* This is used to test for completion */
1993 if ((pixt = pixCreateTemplate(pixs)) == NULL)
1994 return ERROR_INT("pixt not made", procName, 1);
1995
1996 datas = pixGetData(pixs);
1997 datam = pixGetData(pixm);
1998 wpls = pixGetWpl(pixs);
1999 wplm = pixGetWpl(pixm);
2000 pixGetDimensions(pixs, &w, &h, NULL);
2001 for (i = 0; i < MaxIters; i++) {
2002 pixCopy(pixt, pixs);
2003 seedfillGrayLowSimple(datas, w, h, wpls, datam, wplm, connectivity);
2004 pixEqual(pixs, pixt, &boolval);
2005 if (boolval == 1) {
2006#if DEBUG_PRINT_ITERS
2007 L_INFO("Gray seed fill converged: %d iters\n", procName, i + 1);
2008#endif /* DEBUG_PRINT_ITERS */
2009 break;
2010 }
2011 }
2012
2013 pixDestroy(&pixt);
2014 return 0;
2015}
2016
2017
2041l_ok
2042pixSeedfillGrayInvSimple(PIX *pixs,
2043 PIX *pixm,
2044 l_int32 connectivity)
2045{
2046l_int32 i, h, w, wpls, wplm, boolval;
2047l_uint32 *datas, *datam;
2048PIX *pixt;
2049
2050 PROCNAME("pixSeedfillGrayInvSimple");
2051
2052 if (!pixs || pixGetDepth(pixs) != 8)
2053 return ERROR_INT("pixs not defined or not 8 bpp", procName, 1);
2054 if (!pixm || pixGetDepth(pixm) != 8)
2055 return ERROR_INT("pixm not defined or not 8 bpp", procName, 1);
2056 if (connectivity != 4 && connectivity != 8)
2057 return ERROR_INT("connectivity not in {4,8}", procName, 1);
2058
2059 /* Make sure the sizes of seed and mask images are the same */
2060 if (pixSizesEqual(pixs, pixm) == 0)
2061 return ERROR_INT("pixs and pixm sizes differ", procName, 1);
2062
2063 /* This is used to test for completion */
2064 if ((pixt = pixCreateTemplate(pixs)) == NULL)
2065 return ERROR_INT("pixt not made", procName, 1);
2066
2067 datas = pixGetData(pixs);
2068 datam = pixGetData(pixm);
2069 wpls = pixGetWpl(pixs);
2070 wplm = pixGetWpl(pixm);
2071 pixGetDimensions(pixs, &w, &h, NULL);
2072 for (i = 0; i < MaxIters; i++) {
2073 pixCopy(pixt, pixs);
2074 seedfillGrayInvLowSimple(datas, w, h, wpls, datam, wplm, connectivity);
2075 pixEqual(pixs, pixt, &boolval);
2076 if (boolval == 1) {
2077#if DEBUG_PRINT_ITERS
2078 L_INFO("Gray seed fill converged: %d iters\n", procName, i + 1);
2079#endif /* DEBUG_PRINT_ITERS */
2080 break;
2081 }
2082 }
2083
2084 pixDestroy(&pixt);
2085 return 0;
2086}
2087
2088
2122static void
2123seedfillGrayLowSimple(l_uint32 *datas,
2124 l_int32 w,
2125 l_int32 h,
2126 l_int32 wpls,
2127 l_uint32 *datam,
2128 l_int32 wplm,
2129 l_int32 connectivity)
2130{
2131l_uint8 val2, val3, val4, val5, val7, val8;
2132l_uint8 val, maxval, maskval;
2133l_int32 i, j, imax, jmax;
2134l_uint32 *lines, *linem;
2135
2136 PROCNAME("seedfillGrayLowSimple");
2137
2138 imax = h - 1;
2139 jmax = w - 1;
2140
2141 switch (connectivity)
2142 {
2143 case 4:
2144 /* UL --> LR scan */
2145 for (i = 0; i < h; i++) {
2146 lines = datas + i * wpls;
2147 linem = datam + i * wplm;
2148 for (j = 0; j < w; j++) {
2149 if ((maskval = GET_DATA_BYTE(linem, j)) > 0) {
2150 maxval = 0;
2151 if (i > 0)
2152 maxval = GET_DATA_BYTE(lines - wpls, j);
2153 if (j > 0) {
2154 val4 = GET_DATA_BYTE(lines, j - 1);
2155 maxval = L_MAX(maxval, val4);
2156 }
2157 val = GET_DATA_BYTE(lines, j);
2158 maxval = L_MAX(maxval, val);
2159 val = L_MIN(maxval, maskval);
2160 SET_DATA_BYTE(lines, j, val);
2161 }
2162 }
2163 }
2164
2165 /* LR --> UL scan */
2166 for (i = imax; i >= 0; i--) {
2167 lines = datas + i * wpls;
2168 linem = datam + i * wplm;
2169 for (j = jmax; j >= 0; j--) {
2170 if ((maskval = GET_DATA_BYTE(linem, j)) > 0) {
2171 maxval = 0;
2172 if (i < imax)
2173 maxval = GET_DATA_BYTE(lines + wpls, j);
2174 if (j < jmax) {
2175 val5 = GET_DATA_BYTE(lines, j + 1);
2176 maxval = L_MAX(maxval, val5);
2177 }
2178 val = GET_DATA_BYTE(lines, j);
2179 maxval = L_MAX(maxval, val);
2180 val = L_MIN(maxval, maskval);
2181 SET_DATA_BYTE(lines, j, val);
2182 }
2183 }
2184 }
2185 break;
2186
2187 case 8:
2188 /* UL --> LR scan */
2189 for (i = 0; i < h; i++) {
2190 lines = datas + i * wpls;
2191 linem = datam + i * wplm;
2192 for (j = 0; j < w; j++) {
2193 if ((maskval = GET_DATA_BYTE(linem, j)) > 0) {
2194 maxval = 0;
2195 if (i > 0) {
2196 if (j > 0)
2197 maxval = GET_DATA_BYTE(lines - wpls, j - 1);
2198 if (j < jmax) {
2199 val2 = GET_DATA_BYTE(lines - wpls, j + 1);
2200 maxval = L_MAX(maxval, val2);
2201 }
2202 val3 = GET_DATA_BYTE(lines - wpls, j);
2203 maxval = L_MAX(maxval, val3);
2204 }
2205 if (j > 0) {
2206 val4 = GET_DATA_BYTE(lines, j - 1);
2207 maxval = L_MAX(maxval, val4);
2208 }
2209 val = GET_DATA_BYTE(lines, j);
2210 maxval = L_MAX(maxval, val);
2211 val = L_MIN(maxval, maskval);
2212 SET_DATA_BYTE(lines, j, val);
2213 }
2214 }
2215 }
2216
2217 /* LR --> UL scan */
2218 for (i = imax; i >= 0; i--) {
2219 lines = datas + i * wpls;
2220 linem = datam + i * wplm;
2221 for (j = jmax; j >= 0; j--) {
2222 if ((maskval = GET_DATA_BYTE(linem, j)) > 0) {
2223 maxval = 0;
2224 if (i < imax) {
2225 if (j > 0)
2226 maxval = GET_DATA_BYTE(lines + wpls, j - 1);
2227 if (j < jmax) {
2228 val8 = GET_DATA_BYTE(lines + wpls, j + 1);
2229 maxval = L_MAX(maxval, val8);
2230 }
2231 val7 = GET_DATA_BYTE(lines + wpls, j);
2232 maxval = L_MAX(maxval, val7);
2233 }
2234 if (j < jmax) {
2235 val5 = GET_DATA_BYTE(lines, j + 1);
2236 maxval = L_MAX(maxval, val5);
2237 }
2238 val = GET_DATA_BYTE(lines, j);
2239 maxval = L_MAX(maxval, val);
2240 val = L_MIN(maxval, maskval);
2241 SET_DATA_BYTE(lines, j, val);
2242 }
2243 }
2244 }
2245 break;
2246
2247 default:
2248 L_ERROR("connectivity must be 4 or 8\n", procName);
2249 }
2250}
2251
2252
2278static void
2279seedfillGrayInvLowSimple(l_uint32 *datas,
2280 l_int32 w,
2281 l_int32 h,
2282 l_int32 wpls,
2283 l_uint32 *datam,
2284 l_int32 wplm,
2285 l_int32 connectivity)
2286{
2287l_uint8 val1, val2, val3, val4, val5, val6, val7, val8;
2288l_uint8 maxval, maskval;
2289l_int32 i, j, imax, jmax;
2290l_uint32 *lines, *linem;
2291
2292 PROCNAME("seedfillGrayInvLowSimple");
2293
2294 imax = h - 1;
2295 jmax = w - 1;
2296
2297 switch (connectivity)
2298 {
2299 case 4:
2300 /* UL --> LR scan */
2301 for (i = 0; i < h; i++) {
2302 lines = datas + i * wpls;
2303 linem = datam + i * wplm;
2304 for (j = 0; j < w; j++) {
2305 if ((maskval = GET_DATA_BYTE(linem, j)) < 255) {
2306 maxval = GET_DATA_BYTE(lines, j);
2307 if (i > 0) {
2308 val2 = GET_DATA_BYTE(lines - wpls, j);
2309 maxval = L_MAX(maxval, val2);
2310 }
2311 if (j > 0) {
2312 val4 = GET_DATA_BYTE(lines, j - 1);
2313 maxval = L_MAX(maxval, val4);
2314 }
2315 if (maxval > maskval)
2316 SET_DATA_BYTE(lines, j, maxval);
2317 }
2318 }
2319 }
2320
2321 /* LR --> UL scan */
2322 for (i = imax; i >= 0; i--) {
2323 lines = datas + i * wpls;
2324 linem = datam + i * wplm;
2325 for (j = jmax; j >= 0; j--) {
2326 if ((maskval = GET_DATA_BYTE(linem, j)) < 255) {
2327 maxval = GET_DATA_BYTE(lines, j);
2328 if (i < imax) {
2329 val7 = GET_DATA_BYTE(lines + wpls, j);
2330 maxval = L_MAX(maxval, val7);
2331 }
2332 if (j < jmax) {
2333 val5 = GET_DATA_BYTE(lines, j + 1);
2334 maxval = L_MAX(maxval, val5);
2335 }
2336 if (maxval > maskval)
2337 SET_DATA_BYTE(lines, j, maxval);
2338 }
2339 }
2340 }
2341 break;
2342
2343 case 8:
2344 /* UL --> LR scan */
2345 for (i = 0; i < h; i++) {
2346 lines = datas + i * wpls;
2347 linem = datam + i * wplm;
2348 for (j = 0; j < w; j++) {
2349 if ((maskval = GET_DATA_BYTE(linem, j)) < 255) {
2350 maxval = GET_DATA_BYTE(lines, j);
2351 if (i > 0) {
2352 if (j > 0) {
2353 val1 = GET_DATA_BYTE(lines - wpls, j - 1);
2354 maxval = L_MAX(maxval, val1);
2355 }
2356 if (j < jmax) {
2357 val2 = GET_DATA_BYTE(lines - wpls, j + 1);
2358 maxval = L_MAX(maxval, val2);
2359 }
2360 val3 = GET_DATA_BYTE(lines - wpls, j);
2361 maxval = L_MAX(maxval, val3);
2362 }
2363 if (j > 0) {
2364 val4 = GET_DATA_BYTE(lines, j - 1);
2365 maxval = L_MAX(maxval, val4);
2366 }
2367 if (maxval > maskval)
2368 SET_DATA_BYTE(lines, j, maxval);
2369 }
2370 }
2371 }
2372
2373 /* LR --> UL scan */
2374 for (i = imax; i >= 0; i--) {
2375 lines = datas + i * wpls;
2376 linem = datam + i * wplm;
2377 for (j = jmax; j >= 0; j--) {
2378 if ((maskval = GET_DATA_BYTE(linem, j)) < 255) {
2379 maxval = GET_DATA_BYTE(lines, j);
2380 if (i < imax) {
2381 if (j > 0) {
2382 val6 = GET_DATA_BYTE(lines + wpls, j - 1);
2383 maxval = L_MAX(maxval, val6);
2384 }
2385 if (j < jmax) {
2386 val8 = GET_DATA_BYTE(lines + wpls, j + 1);
2387 maxval = L_MAX(maxval, val8);
2388 }
2389 val7 = GET_DATA_BYTE(lines + wpls, j);
2390 maxval = L_MAX(maxval, val7);
2391 }
2392 if (j < jmax) {
2393 val5 = GET_DATA_BYTE(lines, j + 1);
2394 maxval = L_MAX(maxval, val5);
2395 }
2396 if (maxval > maskval)
2397 SET_DATA_BYTE(lines, j, maxval);
2398 }
2399 }
2400 }
2401 break;
2402
2403 default:
2404 L_ERROR("connectivity must be 4 or 8\n", procName);
2405 }
2406}
2407
2408
2409/*-----------------------------------------------------------------------*
2410 * Gray seedfill variations *
2411 *-----------------------------------------------------------------------*/
2443PIX *
2444pixSeedfillGrayBasin(PIX *pixb,
2445 PIX *pixm,
2446 l_int32 delta,
2447 l_int32 connectivity)
2448{
2449PIX *pixbi, *pixmi, *pixsd;
2450
2451 PROCNAME("pixSeedfillGrayBasin");
2452
2453 if (!pixb || pixGetDepth(pixb) != 1)
2454 return (PIX *)ERROR_PTR("pixb undefined or not 1 bpp", procName, NULL);
2455 if (!pixm || pixGetDepth(pixm) != 8)
2456 return (PIX *)ERROR_PTR("pixm undefined or not 8 bpp", procName, NULL);
2457 if (connectivity != 4 && connectivity != 8)
2458 return (PIX *)ERROR_PTR("connectivity not in {4,8}", procName, NULL);
2459
2460 if (delta <= 0) {
2461 L_WARNING("delta <= 0; returning a copy of pixm\n", procName);
2462 return pixCopy(NULL, pixm);
2463 }
2464
2465 /* Add delta to every pixel in pixm */
2466 pixsd = pixCopy(NULL, pixm);
2467 pixAddConstantGray(pixsd, delta);
2468
2469 /* Prepare the seed. Write 255 in all pixels of
2470 * ([pixm] + delta) where pixb is 0. */
2471 pixbi = pixInvert(NULL, pixb);
2472 pixSetMasked(pixsd, pixbi, 255);
2473
2474 /* Fill the inverse seed, using the inverse clipping mask */
2475 pixmi = pixInvert(NULL, pixm);
2476 pixInvert(pixsd, pixsd);
2477 pixSeedfillGray(pixsd, pixmi, connectivity);
2478
2479 /* Re-invert the filled seed */
2480 pixInvert(pixsd, pixsd);
2481
2482 pixDestroy(&pixbi);
2483 pixDestroy(&pixmi);
2484 return pixsd;
2485}
2486
2487
2488/*-----------------------------------------------------------------------*
2489 * Vincent's Distance Function method *
2490 *-----------------------------------------------------------------------*/
2534PIX *
2535pixDistanceFunction(PIX *pixs,
2536 l_int32 connectivity,
2537 l_int32 outdepth,
2538 l_int32 boundcond)
2539{
2540l_int32 w, h, wpld;
2541l_uint32 *datad;
2542PIX *pixd;
2543
2544 PROCNAME("pixDistanceFunction");
2545
2546 if (!pixs || pixGetDepth(pixs) != 1)
2547 return (PIX *)ERROR_PTR("!pixs or pixs not 1 bpp", procName, NULL);
2548 if (connectivity != 4 && connectivity != 8)
2549 return (PIX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
2550 if (outdepth != 8 && outdepth != 16)
2551 return (PIX *)ERROR_PTR("outdepth not 8 or 16 bpp", procName, NULL);
2552 if (boundcond != L_BOUNDARY_BG && boundcond != L_BOUNDARY_FG)
2553 return (PIX *)ERROR_PTR("invalid boundcond", procName, NULL);
2554
2555 pixGetDimensions(pixs, &w, &h, NULL);
2556 if ((pixd = pixCreate(w, h, outdepth)) == NULL)
2557 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
2558 datad = pixGetData(pixd);
2559 wpld = pixGetWpl(pixd);
2560
2561 /* Initialize the fg pixels to 1 and the bg pixels to 0 */
2562 pixSetMasked(pixd, pixs, 1);
2563
2564 if (boundcond == L_BOUNDARY_BG) {
2565 distanceFunctionLow(datad, w, h, outdepth, wpld, connectivity);
2566 } else { /* L_BOUNDARY_FG: set boundary pixels to max val */
2567 pixRasterop(pixd, 0, 0, w, 1, PIX_SET, NULL, 0, 0); /* top */
2568 pixRasterop(pixd, 0, h - 1, w, 1, PIX_SET, NULL, 0, 0); /* bot */
2569 pixRasterop(pixd, 0, 0, 1, h, PIX_SET, NULL, 0, 0); /* left */
2570 pixRasterop(pixd, w - 1, 0, 1, h, PIX_SET, NULL, 0, 0); /* right */
2571
2572 distanceFunctionLow(datad, w, h, outdepth, wpld, connectivity);
2573
2574 /* Set each boundary pixel equal to the pixel next to it */
2575 pixSetMirroredBorder(pixd, 1, 1, 1, 1);
2576 }
2577
2578 return pixd;
2579}
2580
2581
2585static void
2586distanceFunctionLow(l_uint32 *datad,
2587 l_int32 w,
2588 l_int32 h,
2589 l_int32 d,
2590 l_int32 wpld,
2591 l_int32 connectivity)
2592{
2593l_int32 val1, val2, val3, val4, val5, val6, val7, val8, minval, val;
2594l_int32 i, j, imax, jmax;
2595l_uint32 *lined;
2596
2597 PROCNAME("distanceFunctionLow");
2598
2599 /* One raster scan followed by one anti-raster scan.
2600 * This does not re-set the 1-boundary of pixels that
2601 * were initialized to either 0 or maxval. */
2602 imax = h - 1;
2603 jmax = w - 1;
2604 switch (connectivity)
2605 {
2606 case 4:
2607 if (d == 8) {
2608 /* UL --> LR scan */
2609 for (i = 1; i < imax; i++) {
2610 lined = datad + i * wpld;
2611 for (j = 1; j < jmax; j++) {
2612 if ((val = GET_DATA_BYTE(lined, j)) > 0) {
2613 val2 = GET_DATA_BYTE(lined - wpld, j);
2614 val4 = GET_DATA_BYTE(lined, j - 1);
2615 minval = L_MIN(val2, val4);
2616 minval = L_MIN(minval, 254);
2617 SET_DATA_BYTE(lined, j, minval + 1);
2618 }
2619 }
2620 }
2621
2622 /* LR --> UL scan */
2623 for (i = imax - 1; i > 0; i--) {
2624 lined = datad + i * wpld;
2625 for (j = jmax - 1; j > 0; j--) {
2626 if ((val = GET_DATA_BYTE(lined, j)) > 0) {
2627 val7 = GET_DATA_BYTE(lined + wpld, j);
2628 val5 = GET_DATA_BYTE(lined, j + 1);
2629 minval = L_MIN(val5, val7);
2630 minval = L_MIN(minval + 1, val);
2631 SET_DATA_BYTE(lined, j, minval);
2632 }
2633 }
2634 }
2635 } else { /* d == 16 */
2636 /* UL --> LR scan */
2637 for (i = 1; i < imax; i++) {
2638 lined = datad + i * wpld;
2639 for (j = 1; j < jmax; j++) {
2640 if ((val = GET_DATA_TWO_BYTES(lined, j)) > 0) {
2641 val2 = GET_DATA_TWO_BYTES(lined - wpld, j);
2642 val4 = GET_DATA_TWO_BYTES(lined, j - 1);
2643 minval = L_MIN(val2, val4);
2644 minval = L_MIN(minval, 0xfffe);
2645 SET_DATA_TWO_BYTES(lined, j, minval + 1);
2646 }
2647 }
2648 }
2649
2650 /* LR --> UL scan */
2651 for (i = imax - 1; i > 0; i--) {
2652 lined = datad + i * wpld;
2653 for (j = jmax - 1; j > 0; j--) {
2654 if ((val = GET_DATA_TWO_BYTES(lined, j)) > 0) {
2655 val7 = GET_DATA_TWO_BYTES(lined + wpld, j);
2656 val5 = GET_DATA_TWO_BYTES(lined, j + 1);
2657 minval = L_MIN(val5, val7);
2658 minval = L_MIN(minval + 1, val);
2659 SET_DATA_TWO_BYTES(lined, j, minval);
2660 }
2661 }
2662 }
2663 }
2664 break;
2665
2666 case 8:
2667 if (d == 8) {
2668 /* UL --> LR scan */
2669 for (i = 1; i < imax; i++) {
2670 lined = datad + i * wpld;
2671 for (j = 1; j < jmax; j++) {
2672 if ((val = GET_DATA_BYTE(lined, j)) > 0) {
2673 val1 = GET_DATA_BYTE(lined - wpld, j - 1);
2674 val2 = GET_DATA_BYTE(lined - wpld, j);
2675 val3 = GET_DATA_BYTE(lined - wpld, j + 1);
2676 val4 = GET_DATA_BYTE(lined, j - 1);
2677 minval = L_MIN(val1, val2);
2678 minval = L_MIN(minval, val3);
2679 minval = L_MIN(minval, val4);
2680 minval = L_MIN(minval, 254);
2681 SET_DATA_BYTE(lined, j, minval + 1);
2682 }
2683 }
2684 }
2685
2686 /* LR --> UL scan */
2687 for (i = imax - 1; i > 0; i--) {
2688 lined = datad + i * wpld;
2689 for (j = jmax - 1; j > 0; j--) {
2690 if ((val = GET_DATA_BYTE(lined, j)) > 0) {
2691 val8 = GET_DATA_BYTE(lined + wpld, j + 1);
2692 val7 = GET_DATA_BYTE(lined + wpld, j);
2693 val6 = GET_DATA_BYTE(lined + wpld, j - 1);
2694 val5 = GET_DATA_BYTE(lined, j + 1);
2695 minval = L_MIN(val8, val7);
2696 minval = L_MIN(minval, val6);
2697 minval = L_MIN(minval, val5);
2698 minval = L_MIN(minval + 1, val);
2699 SET_DATA_BYTE(lined, j, minval);
2700 }
2701 }
2702 }
2703 } else { /* d == 16 */
2704 /* UL --> LR scan */
2705 for (i = 1; i < imax; i++) {
2706 lined = datad + i * wpld;
2707 for (j = 1; j < jmax; j++) {
2708 if ((val = GET_DATA_TWO_BYTES(lined, j)) > 0) {
2709 val1 = GET_DATA_TWO_BYTES(lined - wpld, j - 1);
2710 val2 = GET_DATA_TWO_BYTES(lined - wpld, j);
2711 val3 = GET_DATA_TWO_BYTES(lined - wpld, j + 1);
2712 val4 = GET_DATA_TWO_BYTES(lined, j - 1);
2713 minval = L_MIN(val1, val2);
2714 minval = L_MIN(minval, val3);
2715 minval = L_MIN(minval, val4);
2716 minval = L_MIN(minval, 0xfffe);
2717 SET_DATA_TWO_BYTES(lined, j, minval + 1);
2718 }
2719 }
2720 }
2721
2722 /* LR --> UL scan */
2723 for (i = imax - 1; i > 0; i--) {
2724 lined = datad + i * wpld;
2725 for (j = jmax - 1; j > 0; j--) {
2726 if ((val = GET_DATA_TWO_BYTES(lined, j)) > 0) {
2727 val8 = GET_DATA_TWO_BYTES(lined + wpld, j + 1);
2728 val7 = GET_DATA_TWO_BYTES(lined + wpld, j);
2729 val6 = GET_DATA_TWO_BYTES(lined + wpld, j - 1);
2730 val5 = GET_DATA_TWO_BYTES(lined, j + 1);
2731 minval = L_MIN(val8, val7);
2732 minval = L_MIN(minval, val6);
2733 minval = L_MIN(minval, val5);
2734 minval = L_MIN(minval + 1, val);
2735 SET_DATA_TWO_BYTES(lined, j, minval);
2736 }
2737 }
2738 }
2739 }
2740 break;
2741
2742 default:
2743 L_ERROR("connectivity must be 4 or 8\n", procName);
2744 }
2745}
2746
2747
2748/*-----------------------------------------------------------------------*
2749 * Seed spread (based on distance function) *
2750 *-----------------------------------------------------------------------*/
2791PIX *
2792pixSeedspread(PIX *pixs,
2793 l_int32 connectivity)
2794{
2795l_int32 w, h, wplt, wplg;
2796l_uint32 *datat, *datag;
2797PIX *pixm, *pixt, *pixg, *pixd;
2798
2799 PROCNAME("pixSeedspread");
2800
2801 if (!pixs || pixGetDepth(pixs) != 8)
2802 return (PIX *)ERROR_PTR("!pixs or pixs not 8 bpp", procName, NULL);
2803 if (connectivity != 4 && connectivity != 8)
2804 return (PIX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
2805
2806 /* Add a 4 byte border to pixs. This simplifies the computation. */
2807 pixg = pixAddBorder(pixs, 4, 0);
2808 pixGetDimensions(pixg, &w, &h, NULL);
2809
2810 /* Initialize distance function pixt. Threshold pixs to get
2811 * a 0 at the seed points where the pixs pixel is nonzero, and
2812 * a 1 at all points that need to be filled. Use this as a
2813 * mask to set a 1 in pixt at all non-seed points. Also, set all
2814 * pixt pixels in an interior boundary of width 1 to the
2815 * maximum value. For debugging, to view the distance function,
2816 * use pixConvert16To8(pixt, L_LS_BYTE) on small images. */
2817 pixm = pixThresholdToBinary(pixg, 1);
2818 pixt = pixCreate(w, h, 16);
2819 pixSetMasked(pixt, pixm, 1);
2820 pixRasterop(pixt, 0, 0, w, 1, PIX_SET, NULL, 0, 0); /* top */
2821 pixRasterop(pixt, 0, h - 1, w, 1, PIX_SET, NULL, 0, 0); /* bot */
2822 pixRasterop(pixt, 0, 0, 1, h, PIX_SET, NULL, 0, 0); /* left */
2823 pixRasterop(pixt, w - 1, 0, 1, h, PIX_SET, NULL, 0, 0); /* right */
2824 datat = pixGetData(pixt);
2825 wplt = pixGetWpl(pixt);
2826
2827 /* Do the interpolation and remove the border. */
2828 datag = pixGetData(pixg);
2829 wplg = pixGetWpl(pixg);
2830 seedspreadLow(datag, w, h, wplg, datat, wplt, connectivity);
2831 pixd = pixRemoveBorder(pixg, 4);
2832
2833 pixDestroy(&pixm);
2834 pixDestroy(&pixg);
2835 pixDestroy(&pixt);
2836 return pixd;
2837}
2838
2839
2845static void
2846seedspreadLow(l_uint32 *datad,
2847 l_int32 w,
2848 l_int32 h,
2849 l_int32 wpld,
2850 l_uint32 *datat,
2851 l_int32 wplt,
2852 l_int32 connectivity)
2853{
2854l_int32 val1t, val2t, val3t, val4t, val5t, val6t, val7t, val8t;
2855l_int32 i, j, imax, jmax, minval, valt, vald;
2856l_uint32 *linet, *lined;
2857
2858 PROCNAME("seedspreadLow");
2859
2860 /* One raster scan followed by one anti-raster scan.
2861 * pixt is initialized to have 0 on pixels where the
2862 * input is specified in pixd, and to have 1 on all
2863 * other pixels. We only change pixels in pixt and pixd
2864 * that are non-zero in pixt. */
2865 imax = h - 1;
2866 jmax = w - 1;
2867 switch (connectivity)
2868 {
2869 case 4:
2870 /* UL --> LR scan */
2871 for (i = 1; i < h; i++) {
2872 linet = datat + i * wplt;
2873 lined = datad + i * wpld;
2874 for (j = 1; j < jmax; j++) {
2875 if ((valt = GET_DATA_TWO_BYTES(linet, j)) > 0) {
2876 val2t = GET_DATA_TWO_BYTES(linet - wplt, j);
2877 val4t = GET_DATA_TWO_BYTES(linet, j - 1);
2878 minval = L_MIN(val2t, val4t);
2879 minval = L_MIN(minval, 0xfffe);
2880 SET_DATA_TWO_BYTES(linet, j, minval + 1);
2881 if (val2t < val4t)
2882 vald = GET_DATA_BYTE(lined - wpld, j);
2883 else
2884 vald = GET_DATA_BYTE(lined, j - 1);
2885 SET_DATA_BYTE(lined, j, vald);
2886 }
2887 }
2888 }
2889
2890 /* LR --> UL scan */
2891 for (i = imax - 1; i > 0; i--) {
2892 linet = datat + i * wplt;
2893 lined = datad + i * wpld;
2894 for (j = jmax - 1; j > 0; j--) {
2895 if ((valt = GET_DATA_TWO_BYTES(linet, j)) > 0) {
2896 val7t = GET_DATA_TWO_BYTES(linet + wplt, j);
2897 val5t = GET_DATA_TWO_BYTES(linet, j + 1);
2898 minval = L_MIN(val5t, val7t);
2899 minval = L_MIN(minval + 1, valt);
2900 if (valt > minval) { /* replace */
2901 SET_DATA_TWO_BYTES(linet, j, minval);
2902 if (val5t < val7t)
2903 vald = GET_DATA_BYTE(lined, j + 1);
2904 else
2905 vald = GET_DATA_BYTE(lined + wplt, j);
2906 SET_DATA_BYTE(lined, j, vald);
2907 }
2908 }
2909 }
2910 }
2911 break;
2912 case 8:
2913 /* UL --> LR scan */
2914 for (i = 1; i < h; i++) {
2915 linet = datat + i * wplt;
2916 lined = datad + i * wpld;
2917 for (j = 1; j < jmax; j++) {
2918 if ((valt = GET_DATA_TWO_BYTES(linet, j)) > 0) {
2919 val1t = GET_DATA_TWO_BYTES(linet - wplt, j - 1);
2920 val2t = GET_DATA_TWO_BYTES(linet - wplt, j);
2921 val3t = GET_DATA_TWO_BYTES(linet - wplt, j + 1);
2922 val4t = GET_DATA_TWO_BYTES(linet, j - 1);
2923 minval = L_MIN(val1t, val2t);
2924 minval = L_MIN(minval, val3t);
2925 minval = L_MIN(minval, val4t);
2926 minval = L_MIN(minval, 0xfffe);
2927 SET_DATA_TWO_BYTES(linet, j, minval + 1);
2928 if (minval == val1t)
2929 vald = GET_DATA_BYTE(lined - wpld, j - 1);
2930 else if (minval == val2t)
2931 vald = GET_DATA_BYTE(lined - wpld, j);
2932 else if (minval == val3t)
2933 vald = GET_DATA_BYTE(lined - wpld, j + 1);
2934 else /* minval == val4t */
2935 vald = GET_DATA_BYTE(lined, j - 1);
2936 SET_DATA_BYTE(lined, j, vald);
2937 }
2938 }
2939 }
2940
2941 /* LR --> UL scan */
2942 for (i = imax - 1; i > 0; i--) {
2943 linet = datat + i * wplt;
2944 lined = datad + i * wpld;
2945 for (j = jmax - 1; j > 0; j--) {
2946 if ((valt = GET_DATA_TWO_BYTES(linet, j)) > 0) {
2947 val8t = GET_DATA_TWO_BYTES(linet + wplt, j + 1);
2948 val7t = GET_DATA_TWO_BYTES(linet + wplt, j);
2949 val6t = GET_DATA_TWO_BYTES(linet + wplt, j - 1);
2950 val5t = GET_DATA_TWO_BYTES(linet, j + 1);
2951 minval = L_MIN(val8t, val7t);
2952 minval = L_MIN(minval, val6t);
2953 minval = L_MIN(minval, val5t);
2954 minval = L_MIN(minval + 1, valt);
2955 if (valt > minval) { /* replace */
2956 SET_DATA_TWO_BYTES(linet, j, minval);
2957 if (minval == val5t + 1)
2958 vald = GET_DATA_BYTE(lined, j + 1);
2959 else if (minval == val6t + 1)
2960 vald = GET_DATA_BYTE(lined + wpld, j - 1);
2961 else if (minval == val7t + 1)
2962 vald = GET_DATA_BYTE(lined + wpld, j);
2963 else /* minval == val8t + 1 */
2964 vald = GET_DATA_BYTE(lined + wpld, j + 1);
2965 SET_DATA_BYTE(lined, j, vald);
2966 }
2967 }
2968 }
2969 }
2970 break;
2971 default:
2972 L_ERROR("connectivity must be 4 or 8\n", procName);
2973 break;
2974 }
2975}
2976
2977
2978/*-----------------------------------------------------------------------*
2979 * Local extrema *
2980 *-----------------------------------------------------------------------*/
3018l_ok
3019pixLocalExtrema(PIX *pixs,
3020 l_int32 maxmin,
3021 l_int32 minmax,
3022 PIX **ppixmin,
3023 PIX **ppixmax)
3024{
3025PIX *pixmin, *pixmax, *pixt1, *pixt2;
3026
3027 PROCNAME("pixLocalExtrema");
3028
3029 if (!pixs || pixGetDepth(pixs) != 8)
3030 return ERROR_INT("pixs not defined or not 8 bpp", procName, 1);
3031 if (!ppixmin && !ppixmax)
3032 return ERROR_INT("neither &pixmin, &pixmax are defined", procName, 1);
3033 if (maxmin <= 0) maxmin = 254;
3034 if (minmax <= 0) minmax = 1;
3035
3036 if (ppixmin) {
3037 pixt1 = pixErodeGray(pixs, 3, 3);
3038 pixmin = pixFindEqualValues(pixs, pixt1);
3039 pixDestroy(&pixt1);
3040 pixQualifyLocalMinima(pixs, pixmin, maxmin);
3041 *ppixmin = pixmin;
3042 }
3043
3044 if (ppixmax) {
3045 pixt1 = pixInvert(NULL, pixs);
3046 pixt2 = pixErodeGray(pixt1, 3, 3);
3047 pixmax = pixFindEqualValues(pixt1, pixt2);
3048 pixDestroy(&pixt2);
3049 pixQualifyLocalMinima(pixt1, pixmax, 255 - minmax);
3050 *ppixmax = pixmax;
3051 pixDestroy(&pixt1);
3052 }
3053
3054 return 0;
3055}
3056
3057
3082static l_int32
3083pixQualifyLocalMinima(PIX *pixs,
3084 PIX *pixm,
3085 l_int32 maxval)
3086{
3087l_int32 n, i, j, k, x, y, w, h, xc, yc, wc, hc, xon, yon;
3088l_int32 vals, wpls, wplc, ismin;
3089l_uint32 val;
3090l_uint32 *datas, *datac, *lines, *linec;
3091BOXA *boxa;
3092PIX *pix1, *pix2, *pix3;
3093PIXA *pixa;
3094
3095 PROCNAME("pixQualifyLocalMinima");
3096
3097 if (!pixs || pixGetDepth(pixs) != 8)
3098 return ERROR_INT("pixs not defined or not 8 bpp", procName, 1);
3099 if (!pixm || pixGetDepth(pixm) != 1)
3100 return ERROR_INT("pixm not defined or not 1 bpp", procName, 1);
3101 if (maxval <= 0) maxval = 254;
3102
3103 pixGetDimensions(pixs, &w, &h, NULL);
3104 datas = pixGetData(pixs);
3105 wpls = pixGetWpl(pixs);
3106 boxa = pixConnComp(pixm, &pixa, 8);
3107 n = pixaGetCount(pixa);
3108 for (k = 0; k < n; k++) {
3109 boxaGetBoxGeometry(boxa, k, &xc, &yc, &wc, &hc);
3110 pix1 = pixaGetPix(pixa, k, L_COPY);
3111 pix2 = pixAddBorder(pix1, 1, 0);
3112 pix3 = pixDilateBrick(NULL, pix2, 3, 3);
3113 pixXor(pix3, pix3, pix2); /* exterior boundary pixels */
3114 datac = pixGetData(pix3);
3115 wplc = pixGetWpl(pix3);
3116 nextOnPixelInRaster(pix1, 0, 0, &xon, &yon);
3117 pixGetPixel(pixs, xc + xon, yc + yon, &val);
3118 if (val > maxval) { /* too large; erase */
3119 pixRasterop(pixm, xc, yc, wc, hc, PIX_XOR, pix1, 0, 0);
3120 pixDestroy(&pix1);
3121 pixDestroy(&pix2);
3122 pixDestroy(&pix3);
3123 continue;
3124 }
3125 ismin = TRUE;
3126
3127 /* Check all values in pixs that correspond to the exterior
3128 * boundary pixels of the c.c. in pixm. Verify that the
3129 * value in the c.c. is always less. */
3130 for (i = 0, y = yc - 1; i < hc + 2 && y >= 0 && y < h; i++, y++) {
3131 lines = datas + y * wpls;
3132 linec = datac + i * wplc;
3133 for (j = 0, x = xc - 1; j < wc + 2 && x >= 0 && x < w; j++, x++) {
3134 if (GET_DATA_BIT(linec, j)) {
3135 vals = GET_DATA_BYTE(lines, x);
3136 if (vals <= val) { /* not a minimum! */
3137 ismin = FALSE;
3138 break;
3139 }
3140 }
3141 }
3142 if (!ismin)
3143 break;
3144 }
3145 if (!ismin) /* erase it */
3146 pixRasterop(pixm, xc, yc, wc, hc, PIX_XOR, pix1, 0, 0);
3147 pixDestroy(&pix1);
3148 pixDestroy(&pix2);
3149 pixDestroy(&pix3);
3150 }
3151
3152 boxaDestroy(&boxa);
3153 pixaDestroy(&pixa);
3154 return 0;
3155}
3156
3157
3190l_ok
3191pixSelectedLocalExtrema(PIX *pixs,
3192 l_int32 mindist,
3193 PIX **ppixmin,
3194 PIX **ppixmax)
3195{
3196PIX *pixmin, *pixmax, *pixt, *pixtmin, *pixtmax;
3197
3198 PROCNAME("pixSelectedLocalExtrema");
3199
3200 if (!pixs || pixGetDepth(pixs) != 8)
3201 return ERROR_INT("pixs not defined or not 8 bpp", procName, 1);
3202 if (!ppixmin || !ppixmax)
3203 return ERROR_INT("&pixmin and &pixmax not both defined", procName, 1);
3204
3205 pixt = pixErodeGray(pixs, 3, 3);
3206 pixmin = pixFindEqualValues(pixs, pixt);
3207 pixDestroy(&pixt);
3208 pixt = pixDilateGray(pixs, 3, 3);
3209 pixmax = pixFindEqualValues(pixs, pixt);
3210 pixDestroy(&pixt);
3211
3212 /* Remove all points that are within the prescribed distance
3213 * from each other. */
3214 if (mindist < 0) { /* remove no points */
3215 *ppixmin = pixmin;
3216 *ppixmax = pixmax;
3217 } else if (mindist == 0) { /* remove points belonging to both sets */
3218 pixt = pixAnd(NULL, pixmin, pixmax);
3219 *ppixmin = pixSubtract(pixmin, pixmin, pixt);
3220 *ppixmax = pixSubtract(pixmax, pixmax, pixt);
3221 pixDestroy(&pixt);
3222 } else {
3223 pixtmin = pixDilateBrick(NULL, pixmin,
3224 2 * mindist + 1, 2 * mindist + 1);
3225 pixtmax = pixDilateBrick(NULL, pixmax,
3226 2 * mindist + 1, 2 * mindist + 1);
3227 *ppixmin = pixSubtract(pixmin, pixmin, pixtmax);
3228 *ppixmax = pixSubtract(pixmax, pixmax, pixtmin);
3229 pixDestroy(&pixtmin);
3230 pixDestroy(&pixtmax);
3231 }
3232 return 0;
3233}
3234
3235
3250PIX *
3251pixFindEqualValues(PIX *pixs1,
3252 PIX *pixs2)
3253{
3254l_int32 w1, h1, w2, h2, w, h;
3255l_int32 i, j, val1, val2, wpls1, wpls2, wpld;
3256l_uint32 *datas1, *datas2, *datad, *lines1, *lines2, *lined;
3257PIX *pixd;
3258
3259 PROCNAME("pixFindEqualValues");
3260
3261 if (!pixs1 || pixGetDepth(pixs1) != 8)
3262 return (PIX *)ERROR_PTR("pixs1 undefined or not 8 bpp", procName, NULL);
3263 if (!pixs2 || pixGetDepth(pixs2) != 8)
3264 return (PIX *)ERROR_PTR("pixs2 undefined or not 8 bpp", procName, NULL);
3265 pixGetDimensions(pixs1, &w1, &h1, NULL);
3266 pixGetDimensions(pixs2, &w2, &h2, NULL);
3267 w = L_MIN(w1, w2);
3268 h = L_MIN(h1, h2);
3269 pixd = pixCreate(w, h, 1);
3270 datas1 = pixGetData(pixs1);
3271 datas2 = pixGetData(pixs2);
3272 datad = pixGetData(pixd);
3273 wpls1 = pixGetWpl(pixs1);
3274 wpls2 = pixGetWpl(pixs2);
3275 wpld = pixGetWpl(pixd);
3276
3277 for (i = 0; i < h; i++) {
3278 lines1 = datas1 + i * wpls1;
3279 lines2 = datas2 + i * wpls2;
3280 lined = datad + i * wpld;
3281 for (j = 0; j < w; j++) {
3282 val1 = GET_DATA_BYTE(lines1, j);
3283 val2 = GET_DATA_BYTE(lines2, j);
3284 if (val1 == val2)
3285 SET_DATA_BIT(lined, j);
3286 }
3287 }
3288
3289 return pixd;
3290}
3291
3292
3293/*-----------------------------------------------------------------------*
3294 * Selection of minima in mask connected components *
3295 *-----------------------------------------------------------------------*/
3317l_ok
3318pixSelectMinInConnComp(PIX *pixs,
3319 PIX *pixm,
3320 PTA **ppta,
3321 NUMA **pnav)
3322{
3323l_int32 bx, by, bw, bh, i, j, c, n;
3324l_int32 xs, ys, minx, miny, wpls, wplt, val, minval;
3325l_uint32 *datas, *datat, *lines, *linet;
3326BOXA *boxa;
3327NUMA *nav;
3328PIX *pixt, *pixs2, *pixm2;
3329PIXA *pixa;
3330PTA *pta;
3331
3332 PROCNAME("pixSelectMinInConnComp");
3333
3334 if (!ppta)
3335 return ERROR_INT("&pta not defined", procName, 1);
3336 *ppta = NULL;
3337 if (pnav) *pnav = NULL;
3338 if (!pixs || pixGetDepth(pixs) != 8)
3339 return ERROR_INT("pixs undefined or not 8 bpp", procName, 1);
3340 if (!pixm || pixGetDepth(pixm) != 1)
3341 return ERROR_INT("pixm undefined or not 1 bpp", procName, 1);
3342
3343 /* Crop to the min size if necessary */
3344 if (pixCropToMatch(pixs, pixm, &pixs2, &pixm2)) {
3345 pixDestroy(&pixs2);
3346 pixDestroy(&pixm2);
3347 return ERROR_INT("cropping failure", procName, 1);
3348 }
3349
3350 /* Find value and location of min value pixel in each component */
3351 boxa = pixConnComp(pixm2, &pixa, 8);
3352 n = boxaGetCount(boxa);
3353 pta = ptaCreate(n);
3354 *ppta = pta;
3355 nav = numaCreate(n);
3356 datas = pixGetData(pixs2);
3357 wpls = pixGetWpl(pixs2);
3358 for (c = 0; c < n; c++) {
3359 pixt = pixaGetPix(pixa, c, L_CLONE);
3360 boxaGetBoxGeometry(boxa, c, &bx, &by, &bw, &bh);
3361 if (bw == 1 && bh == 1) {
3362 ptaAddPt(pta, bx, by);
3363 numaAddNumber(nav, GET_DATA_BYTE(datas + by * wpls, bx));
3364 pixDestroy(&pixt);
3365 continue;
3366 }
3367 datat = pixGetData(pixt);
3368 wplt = pixGetWpl(pixt);
3369 minx = miny = 1000000;
3370 minval = 256;
3371 for (i = 0; i < bh; i++) {
3372 ys = by + i;
3373 lines = datas + ys * wpls;
3374 linet = datat + i * wplt;
3375 for (j = 0; j < bw; j++) {
3376 xs = bx + j;
3377 if (GET_DATA_BIT(linet, j)) {
3378 val = GET_DATA_BYTE(lines, xs);
3379 if (val < minval) {
3380 minval = val;
3381 minx = xs;
3382 miny = ys;
3383 }
3384 }
3385 }
3386 }
3387 ptaAddPt(pta, minx, miny);
3388 numaAddNumber(nav, GET_DATA_BYTE(datas + miny * wpls, minx));
3389 pixDestroy(&pixt);
3390 }
3391
3392 boxaDestroy(&boxa);
3393 pixaDestroy(&pixa);
3394 if (pnav)
3395 *pnav = nav;
3396 else
3397 numaDestroy(&nav);
3398 pixDestroy(&pixs2);
3399 pixDestroy(&pixm2);
3400 return 0;
3401}
3402
3403
3404/*-----------------------------------------------------------------------*
3405 * Removal of seeded connected components from a mask *
3406 *-----------------------------------------------------------------------*/
3430PIX *
3431pixRemoveSeededComponents(PIX *pixd,
3432 PIX *pixs,
3433 PIX *pixm,
3434 l_int32 connectivity,
3435 l_int32 bordersize)
3436{
3437PIX *pixt;
3438
3439 PROCNAME("pixRemoveSeededComponents");
3440
3441 if (!pixs || pixGetDepth(pixs) != 1)
3442 return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, pixd);
3443 if (!pixm || pixGetDepth(pixm) != 1)
3444 return (PIX *)ERROR_PTR("pixm undefined or not 1 bpp", procName, pixd);
3445 if (pixd && pixd != pixm)
3446 return (PIX *)ERROR_PTR("operation not inplace", procName, pixd);
3447
3448 pixt = pixCopy(NULL, pixs);
3449 pixSeedfillBinary(pixt, pixt, pixm, connectivity);
3450 pixd = pixXor(pixd, pixm, pixt);
3451 if (bordersize > 0)
3452 pixSetOrClearBorder(pixd, bordersize, bordersize, bordersize,
3453 bordersize, PIX_CLR);
3454 pixDestroy(&pixt);
3455 return pixd;
3456}
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
boxaGetBoxGeometry
l_ok boxaGetBoxGeometry(BOXA *boxa, l_int32 index, l_int32 *px, l_int32 *py, l_int32 *pw, l_int32 *ph)
boxaGetBoxGeometry()
Definition: boxbasic.c:879
boxaGetCount
l_int32 boxaGetCount(BOXA *boxa)
boxaGetCount()
Definition: boxbasic.c:734
boxaDestroy
void boxaDestroy(BOXA **pboxa)
boxaDestroy()
Definition: boxbasic.c:583
pixEqual
l_ok pixEqual(PIX *pix1, PIX *pix2, l_int32 *psame)
pixEqual()
Definition: compare.c:156
pixConnComp
BOXA * pixConnComp(PIX *pixs, PIXA **ppixa, l_int32 connectivity)
pixConnComp()
Definition: conncomp.c:151
nextOnPixelInRaster
l_int32 nextOnPixelInRaster(PIX *pixs, l_int32 xstart, l_int32 ystart, l_int32 *px, l_int32 *py)
nextOnPixelInRaster()
Definition: conncomp.c:457
pixDilateGray
PIX * pixDilateGray(PIX *pixs, l_int32 hsize, l_int32 vsize)
pixDilateGray()
Definition: graymorph.c:278
pixErodeGray
PIX * pixErodeGray(PIX *pixs, l_int32 hsize, l_int32 vsize)
pixErodeGray()
Definition: graymorph.c:162
pixThresholdToBinary
PIX * pixThresholdToBinary(PIX *pixs, l_int32 thresh)
pixThresholdToBinary()
Definition: grayquant.c:447
pixDilateBrick
PIX * pixDilateBrick(PIX *pixd, PIX *pixs, l_int32 hsize, l_int32 vsize)
pixDilateBrick()
Definition: morph.c:688
pixDilateCompBrick
PIX * pixDilateCompBrick(PIX *pixd, PIX *pixs, l_int32 hsize, l_int32 vsize)
pixDilateCompBrick()
Definition: morph.c:1244
numaAddNumber
l_ok numaAddNumber(NUMA *na, l_float32 val)
numaAddNumber()
Definition: numabasic.c:478
numaDestroy
void numaDestroy(NUMA **pna)
numaDestroy()
Definition: numabasic.c:366
numaCreate
NUMA * numaCreate(l_int32 n)
numaCreate()
Definition: numabasic.c:194
pixDestroy
void pixDestroy(PIX **ppix)
pixDestroy()
Definition: pix1.c:621
pixGetDimensions
l_ok pixGetDimensions(const PIX *pix, l_int32 *pw, l_int32 *ph, l_int32 *pd)
pixGetDimensions()
Definition: pix1.c:1113
pixSizesEqual
l_int32 pixSizesEqual(const PIX *pix1, const PIX *pix2)
pixSizesEqual()
Definition: pix1.c:1985
pixClone
PIX * pixClone(PIX *pixs)
pixClone()
Definition: pix1.c:593
pixCreateTemplate
PIX * pixCreateTemplate(const PIX *pixs)
pixCreateTemplate()
Definition: pix1.c:383
pixCreate
PIX * pixCreate(l_int32 width, l_int32 height, l_int32 depth)
pixCreate()
Definition: pix1.c:315
pixCopy
PIX * pixCopy(PIX *pixd, const PIX *pixs)
pixCopy()
Definition: pix1.c:705
pixGetData
l_uint32 * pixGetData(PIX *pix)
pixGetData()
Definition: pix1.c:1763
pixGetPixel
l_ok pixGetPixel(PIX *pix, l_int32 x, l_int32 y, l_uint32 *pval)
pixGetPixel()
Definition: pix2.c:190
pixRemoveBorder
PIX * pixRemoveBorder(PIX *pixs, l_int32 npix)
pixRemoveBorder()
Definition: pix2.c:1972
pixSetAll
l_ok pixSetAll(PIX *pix)
pixSetAll()
Definition: pix2.c:817
pixSetPadBits
l_ok pixSetPadBits(PIX *pix, l_int32 val)
pixSetPadBits()
Definition: pix2.c:1382
pixSetOrClearBorder
l_ok pixSetOrClearBorder(PIX *pixs, l_int32 left, l_int32 right, l_int32 top, l_int32 bot, l_int32 op)
pixSetOrClearBorder()
Definition: pix2.c:1514
pixSetMirroredBorder
l_ok pixSetMirroredBorder(PIX *pixs, l_int32 left, l_int32 right, l_int32 top, l_int32 bot)
pixSetMirroredBorder()
Definition: pix2.c:1718
pixAddBorder
PIX * pixAddBorder(PIX *pixs, l_int32 npix, l_uint32 val)
pixAddBorder()
Definition: pix2.c:1823
pixOr
PIX * pixOr(PIX *pixd, PIX *pixs1, PIX *pixs2)
pixOr()
Definition: pix3.c:1560
makePixelSumTab8
l_int32 * makePixelSumTab8(void)
makePixelSumTab8()
Definition: pix3.c:2411
pixCountPixels
l_ok pixCountPixels(PIX *pixs, l_int32 *pcount, l_int32 *tab8)
pixCountPixels()
Definition: pix3.c:1937
pixAnd
PIX * pixAnd(PIX *pixd, PIX *pixs1, PIX *pixs2)
pixAnd()
Definition: pix3.c:1624
pixSubtract
PIX * pixSubtract(PIX *pixd, PIX *pixs1, PIX *pixs2)
pixSubtract()
Definition: pix3.c:1753
pixSetMasked
l_ok pixSetMasked(PIX *pixd, PIX *pixm, l_uint32 val)
pixSetMasked()
Definition: pix3.c:163
pixInvert
PIX * pixInvert(PIX *pixd, PIX *pixs)
pixInvert()
Definition: pix3.c:1509
pixXor
PIX * pixXor(PIX *pixd, PIX *pixs1, PIX *pixs2)
pixXor()
Definition: pix3.c:1688
pixCropToMatch
l_ok pixCropToMatch(PIX *pixs1, PIX *pixs2, PIX **ppixd1, PIX **ppixd2)
pixCropToMatch()
Definition: pix5.c:1224
PIX_DST
#define PIX_DST
Definition: pix.h:331
L_COPY
@ L_COPY
Definition: pix.h:712
L_CLONE
@ L_CLONE
Definition: pix.h:713
PIX_XOR
#define PIX_XOR
Definition: pix.h:340
PIX_SRC
#define PIX_SRC
Definition: pix.h:330
PIX_CLR
#define PIX_CLR
Definition: pix.h:333
PIX_NOT
#define PIX_NOT(op)
Definition: pix.h:332
PIX_SET
#define PIX_SET
Definition: pix.h:334
pixaDestroy
void pixaDestroy(PIXA **ppixa)
pixaDestroy()
Definition: pixabasic.c:412
pixaGetCount
l_int32 pixaGetCount(PIXA *pixa)
pixaGetCount()
Definition: pixabasic.c:650
pixaGetPix
PIX * pixaGetPix(PIXA *pixa, l_int32 index, l_int32 accesstype)
pixaGetPix()
Definition: pixabasic.c:691
pixAddConstantGray
l_ok pixAddConstantGray(PIX *pixs, l_int32 val)
pixAddConstantGray()
Definition: pixarith.c:119
ptaCreate
PTA * ptaCreate(l_int32 n)
ptaCreate()
Definition: ptabasic.c:120
ptaAddPt
l_ok ptaAddPt(PTA *pta, l_float32 x, l_float32 y)
ptaAddPt()
Definition: ptabasic.c:343
lqueueGetCount
l_int32 lqueueGetCount(L_QUEUE *lq)
lqueueGetCount()
Definition: queue.c:286
lqueueDestroy
void lqueueDestroy(L_QUEUE **plq, l_int32 freeflag)
lqueueDestroy()
Definition: queue.c:134
lqueueRemove
void * lqueueRemove(L_QUEUE *lq)
lqueueRemove()
Definition: queue.c:257
lqueueAdd
l_ok lqueueAdd(L_QUEUE *lq, void *item)
lqueueAdd()
Definition: queue.c:188
lqueueCreate
L_QUEUE * lqueueCreate(l_int32 nalloc)
lqueueCreate()
Definition: queue.c:93
pixRasterop
l_ok pixRasterop(PIX *pixd, l_int32 dx, l_int32 dy, l_int32 dw, l_int32 dh, l_int32 op, PIX *pixs, l_int32 sx, l_int32 sy)
pixRasterop()
Definition: rop.c:204
pixSeedfillGrayInvSimple
l_ok pixSeedfillGrayInvSimple(PIX *pixs, PIX *pixm, l_int32 connectivity)
pixSeedfillGrayInvSimple()
Definition: seedfill.c:2042
pixSeedspread
PIX * pixSeedspread(PIX *pixs, l_int32 connectivity)
pixSeedspread()
Definition: seedfill.c:2792
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:2586
pixQualifyLocalMinima
static l_int32 pixQualifyLocalMinima(PIX *pixs, PIX *pixm, l_int32 maxval)
pixQualifyLocalMinima()
Definition: seedfill.c:3083
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:403
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:2279
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:2846
pixExtractBorderConnComps
PIX * pixExtractBorderConnComps(PIX *pixs, l_int32 connectivity)
pixExtractBorderConnComps()
Definition: seedfill.c:698
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:1065
pixRemoveSeededComponents
PIX * pixRemoveSeededComponents(PIX *pixd, PIX *pixs, PIX *pixm, l_int32 connectivity, l_int32 bordersize)
pixRemoveSeededComponents()
Definition: seedfill.c:3431
pixDistanceFunction
PIX * pixDistanceFunction(PIX *pixs, l_int32 connectivity, l_int32 outdepth, l_int32 boundcond)
pixDistanceFunction()
Definition: seedfill.c:2535
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:2123
pixSelectedLocalExtrema
l_ok pixSelectedLocalExtrema(PIX *pixs, l_int32 mindist, PIX **ppixmin, PIX **ppixmax)
pixSelectedLocalExtrema()
Definition: seedfill.c:3191
pixSeedfillGrayBasin
PIX * pixSeedfillGrayBasin(PIX *pixb, PIX *pixm, l_int32 delta, l_int32 connectivity)
pixSeedfillGrayBasin()
Definition: seedfill.c:2444
pixSeedfillGrayInv
l_ok pixSeedfillGrayInv(PIX *pixs, PIX *pixm, l_int32 connectivity)
pixSeedfillGrayInv()
Definition: seedfill.c:988
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:3318
pixFillHolesToBoundingRect
PIX * pixFillHolesToBoundingRect(PIX *pixs, l_int32 minsize, l_float32 maxhfract, l_float32 minfgfract)
pixFillHolesToBoundingRect()
Definition: seedfill.c:847
pixLocalExtrema
l_ok pixLocalExtrema(PIX *pixs, l_int32 maxmin, l_int32 minmax, PIX **ppixmin, PIX **ppixmax)
pixLocalExtrema()
Definition: seedfill.c:3019
pixFillBgFromBorder
PIX * pixFillBgFromBorder(PIX *pixs, l_int32 connectivity)
pixFillBgFromBorder()
Definition: seedfill.c:787
pixFindEqualValues
PIX * pixFindEqualValues(PIX *pixs1, PIX *pixs2)
pixFindEqualValues()
Definition: seedfill.c:3251
pixSeedfillBinaryRestricted
PIX * pixSeedfillBinaryRestricted(PIX *pixd, PIX *pixs, PIX *pixm, l_int32 connectivity, l_int32 xmax, l_int32 ymax)
pixSeedfillBinaryRestricted()
Definition: seedfill.c:335
pixFillClosedBorders
PIX * pixFillClosedBorders(PIX *pixs, l_int32 connectivity)
pixFillClosedBorders()
Definition: seedfill.c:660
pixHolesByFilling
PIX * pixHolesByFilling(PIX *pixs, l_int32 connectivity)
pixHolesByFilling()
Definition: seedfill.c:609
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:1516
pixSeedfillGray
l_ok pixSeedfillGray(PIX *pixs, PIX *pixm, l_int32 connectivity)
pixSeedfillGray()
Definition: seedfill.c:929
pixSeedfillGraySimple
l_ok pixSeedfillGraySimple(PIX *pixs, PIX *pixm, l_int32 connectivity)
pixSeedfillGraySimple()
Definition: seedfill.c:1971
pixRemoveBorderConnComps
PIX * pixRemoveBorderConnComps(PIX *pixs, l_int32 connectivity)
pixRemoveBorderConnComps()
Definition: seedfill.c:737
Boxa
Definition: pix.h:492
L_Pixel
Definition: seedfill.c:175
L_Queue
Definition: queue.h:65
Numa
Definition: array.h:71
Pix
Definition: pix.h:139
Pixa
Definition: pix.h:456
Pta
Definition: pix.h:517
lept_stderr
void lept_stderr(const char *fmt,...)
lept_stderr()
Definition: utils1.c:306