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 
174 struct L_Pixel
175 {
176  l_int32 x;
177  l_int32 y;
178 };
179 typedef struct L_Pixel L_PIXEL;
180 
181 static 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);
184 static 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);
187 static 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);
190 static 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);
193 static 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);
196 static void distanceFunctionLow(l_uint32 *datad, l_int32 w, l_int32 h,
197  l_int32 d, l_int32 wpld, l_int32 connectivity);
198 static 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 
202 static 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 */
209 static const l_int32 MaxIters = 40;
210 
211 
212 /*-----------------------------------------------------------------------*
213  * Vincent's Iterative Binary Seedfill method *
214  *-----------------------------------------------------------------------*/
246 PIX *
248  PIX *pixs,
249  PIX *pixm,
250  l_int32 connectivity)
251 {
252 l_int32 i, boolval;
253 l_int32 hd, hm, wpld, wplm;
254 l_uint32 *datad, *datam;
255 PIX *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 
334 PIX *
336  PIX *pixs,
337  PIX *pixm,
338  l_int32 connectivity,
339  l_int32 xmax,
340  l_int32 ymax)
341 {
342 l_int32 w, h;
343 PIX *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 
402 static void
403 seedfillBinaryLow(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 {
411 l_int32 i, j, h, wpl;
412 l_uint32 word, mask;
413 l_uint32 wordabove, wordleft, wordbelow, wordright;
414 l_uint32 wordprev; /* test against this in previous iteration */
415 l_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 
608 PIX *
610  l_int32 connectivity)
611 {
612 PIX *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 
659 PIX *
661  l_int32 connectivity)
662 {
663 PIX *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 
697 PIX *
699  l_int32 connectivity)
700 {
701 PIX *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 
736 PIX *
738  l_int32 connectivity)
739 {
740 PIX *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 
786 PIX *
788  l_int32 connectivity)
789 {
790 PIX *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  *-----------------------------------------------------------------------*/
846 PIX *
848  l_int32 minsize,
849  l_float32 maxhfract,
850  l_float32 minfgfract)
851 {
852 l_int32 i, x, y, w, h, n, nfg, nh, ntot, area;
853 l_int32 *tab;
854 l_float32 hfract; /* measured hole fraction */
855 l_float32 fgfract; /* measured fg fraction */
856 BOXA *boxa;
857 PIX *pixd, *pixfg, *pixh;
858 PIXA *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  *-----------------------------------------------------------------------*/
928 l_ok
930  PIX *pixm,
931  l_int32 connectivity)
932 {
933 l_int32 h, w, wpls, wplm;
934 l_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 
987 l_ok
989  PIX *pixm,
990  l_int32 connectivity)
991 {
992 l_int32 h, w, wpls, wplm;
993 l_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 
1064 static void
1065 seedfillGrayLow(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 {
1073 l_uint8 val1, val2, val3, val4, val5, val6, val7, val8;
1074 l_uint8 val, maxval, maskval, boolval;
1075 l_int32 i, j, imax, jmax, queue_size;
1076 l_uint32 *lines, *linem;
1077 L_PIXEL *pixel;
1078 L_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 
1515 static void
1516 seedfillGrayInvLow(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 {
1524 l_uint8 val1, val2, val3, val4, val5, val6, val7, val8;
1525 l_uint8 val, maxval, maskval, boolval;
1526 l_int32 i, j, imax, jmax, queue_size;
1527 l_uint32 *lines, *linem;
1528 L_PIXEL *pixel;
1529 L_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  *-----------------------------------------------------------------------*/
1970 l_ok
1972  PIX *pixm,
1973  l_int32 connectivity)
1974 {
1975 l_int32 i, h, w, wpls, wplm, boolval;
1976 l_uint32 *datas, *datam;
1977 PIX *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 
2041 l_ok
2043  PIX *pixm,
2044  l_int32 connectivity)
2045 {
2046 l_int32 i, h, w, wpls, wplm, boolval;
2047 l_uint32 *datas, *datam;
2048 PIX *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 
2122 static void
2123 seedfillGrayLowSimple(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 {
2131 l_uint8 val2, val3, val4, val5, val7, val8;
2132 l_uint8 val, maxval, maskval;
2133 l_int32 i, j, imax, jmax;
2134 l_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 
2278 static void
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 {
2287 l_uint8 val1, val2, val3, val4, val5, val6, val7, val8;
2288 l_uint8 maxval, maskval;
2289 l_int32 i, j, imax, jmax;
2290 l_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  *-----------------------------------------------------------------------*/
2443 PIX *
2445  PIX *pixm,
2446  l_int32 delta,
2447  l_int32 connectivity)
2448 {
2449 PIX *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  *-----------------------------------------------------------------------*/
2534 PIX *
2536  l_int32 connectivity,
2537  l_int32 outdepth,
2538  l_int32 boundcond)
2539 {
2540 l_int32 w, h, wpld;
2541 l_uint32 *datad;
2542 PIX *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 
2585 static void
2586 distanceFunctionLow(l_uint32 *datad,
2587  l_int32 w,
2588  l_int32 h,
2589  l_int32 d,
2590  l_int32 wpld,
2591  l_int32 connectivity)
2592 {
2593 l_int32 val1, val2, val3, val4, val5, val6, val7, val8, minval, val;
2594 l_int32 i, j, imax, jmax;
2595 l_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  *-----------------------------------------------------------------------*/
2791 PIX *
2793  l_int32 connectivity)
2794 {
2795 l_int32 w, h, wplt, wplg;
2796 l_uint32 *datat, *datag;
2797 PIX *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 
2845 static void
2846 seedspreadLow(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 {
2854 l_int32 val1t, val2t, val3t, val4t, val5t, val6t, val7t, val8t;
2855 l_int32 i, j, imax, jmax, minval, valt, vald;
2856 l_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  *-----------------------------------------------------------------------*/
3018 l_ok
3020  l_int32 maxmin,
3021  l_int32 minmax,
3022  PIX **ppixmin,
3023  PIX **ppixmax)
3024 {
3025 PIX *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 
3082 static l_int32
3084  PIX *pixm,
3085  l_int32 maxval)
3086 {
3087 l_int32 n, i, j, k, x, y, w, h, xc, yc, wc, hc, xon, yon;
3088 l_int32 vals, wpls, wplc, ismin;
3089 l_uint32 val;
3090 l_uint32 *datas, *datac, *lines, *linec;
3091 BOXA *boxa;
3092 PIX *pix1, *pix2, *pix3;
3093 PIXA *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 
3190 l_ok
3192  l_int32 mindist,
3193  PIX **ppixmin,
3194  PIX **ppixmax)
3195 {
3196 PIX *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 
3250 PIX *
3252  PIX *pixs2)
3253 {
3254 l_int32 w1, h1, w2, h2, w, h;
3255 l_int32 i, j, val1, val2, wpls1, wpls2, wpld;
3256 l_uint32 *datas1, *datas2, *datad, *lines1, *lines2, *lined;
3257 PIX *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  *-----------------------------------------------------------------------*/
3317 l_ok
3319  PIX *pixm,
3320  PTA **ppta,
3321  NUMA **pnav)
3322 {
3323 l_int32 bx, by, bw, bh, i, j, c, n;
3324 l_int32 xs, ys, minx, miny, wpls, wplt, val, minval;
3325 l_uint32 *datas, *datat, *lines, *linet;
3326 BOXA *boxa;
3327 NUMA *nav;
3328 PIX *pixt, *pixs2, *pixm2;
3329 PIXA *pixa;
3330 PTA *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  *-----------------------------------------------------------------------*/
3430 PIX *
3432  PIX *pixs,
3433  PIX *pixm,
3434  l_int32 connectivity,
3435  l_int32 bordersize)
3436 {
3437 PIX *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 }
#define GET_DATA_TWO_BYTES(pdata, n)
Definition: arrayaccess.h:212
#define SET_DATA_BIT(pdata, n)
Definition: arrayaccess.h:127
#define SET_DATA_TWO_BYTES(pdata, n, val)
Definition: arrayaccess.h:222
#define GET_DATA_BYTE(pdata, n)
Definition: arrayaccess.h:188
#define SET_DATA_BYTE(pdata, n, val)
Definition: arrayaccess.h:198
#define GET_DATA_BIT(pdata, n)
Definition: arrayaccess.h:123
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
l_int32 boxaGetCount(BOXA *boxa)
boxaGetCount()
Definition: boxbasic.c:734
void boxaDestroy(BOXA **pboxa)
boxaDestroy()
Definition: boxbasic.c:583
l_ok pixEqual(PIX *pix1, PIX *pix2, l_int32 *psame)
pixEqual()
Definition: compare.c:156
BOXA * pixConnComp(PIX *pixs, PIXA **ppixa, l_int32 connectivity)
pixConnComp()
Definition: conncomp.c:151
l_int32 nextOnPixelInRaster(PIX *pixs, l_int32 xstart, l_int32 ystart, l_int32 *px, l_int32 *py)
nextOnPixelInRaster()
Definition: conncomp.c:457
PIX * pixDilateGray(PIX *pixs, l_int32 hsize, l_int32 vsize)
pixDilateGray()
Definition: graymorph.c:278
PIX * pixErodeGray(PIX *pixs, l_int32 hsize, l_int32 vsize)
pixErodeGray()
Definition: graymorph.c:162
PIX * pixThresholdToBinary(PIX *pixs, l_int32 thresh)
pixThresholdToBinary()
Definition: grayquant.c:447
PIX * pixDilateBrick(PIX *pixd, PIX *pixs, l_int32 hsize, l_int32 vsize)
pixDilateBrick()
Definition: morph.c:688
PIX * pixDilateCompBrick(PIX *pixd, PIX *pixs, l_int32 hsize, l_int32 vsize)
pixDilateCompBrick()
Definition: morph.c:1244
l_ok numaAddNumber(NUMA *na, l_float32 val)
numaAddNumber()
Definition: numabasic.c:478
NUMA * numaCreate(l_int32 n)
numaCreate()
Definition: numabasic.c:194
void numaDestroy(NUMA **pna)
numaDestroy()
Definition: numabasic.c:366
l_uint32 * pixGetData(PIX *pix)
pixGetData()
Definition: pix1.c:1763
void pixDestroy(PIX **ppix)
pixDestroy()
Definition: pix1.c:621
l_ok pixGetDimensions(const PIX *pix, l_int32 *pw, l_int32 *ph, l_int32 *pd)
pixGetDimensions()
Definition: pix1.c:1113
l_int32 pixSizesEqual(const PIX *pix1, const PIX *pix2)
pixSizesEqual()
Definition: pix1.c:1985
PIX * pixCopy(PIX *pixd, const PIX *pixs)
pixCopy()
Definition: pix1.c:705
PIX * pixCreateTemplate(const PIX *pixs)
pixCreateTemplate()
Definition: pix1.c:383
PIX * pixCreate(l_int32 width, l_int32 height, l_int32 depth)
pixCreate()
Definition: pix1.c:315
PIX * pixClone(PIX *pixs)
pixClone()
Definition: pix1.c:593
l_ok pixGetPixel(PIX *pix, l_int32 x, l_int32 y, l_uint32 *pval)
pixGetPixel()
Definition: pix2.c:190
PIX * pixAddBorder(PIX *pixs, l_int32 npix, l_uint32 val)
pixAddBorder()
Definition: pix2.c:1823
PIX * pixRemoveBorder(PIX *pixs, l_int32 npix)
pixRemoveBorder()
Definition: pix2.c:1972
l_ok pixSetAll(PIX *pix)
pixSetAll()
Definition: pix2.c:817
l_ok pixSetPadBits(PIX *pix, l_int32 val)
pixSetPadBits()
Definition: pix2.c:1382
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
l_ok pixSetMirroredBorder(PIX *pixs, l_int32 left, l_int32 right, l_int32 top, l_int32 bot)
pixSetMirroredBorder()
Definition: pix2.c:1718
PIX * pixInvert(PIX *pixd, PIX *pixs)
pixInvert()
Definition: pix3.c:1509
l_ok pixCountPixels(PIX *pixs, l_int32 *pcount, l_int32 *tab8)
pixCountPixels()
Definition: pix3.c:1937
PIX * pixOr(PIX *pixd, PIX *pixs1, PIX *pixs2)
pixOr()
Definition: pix3.c:1560
PIX * pixAnd(PIX *pixd, PIX *pixs1, PIX *pixs2)
pixAnd()
Definition: pix3.c:1624
l_ok pixSetMasked(PIX *pixd, PIX *pixm, l_uint32 val)
pixSetMasked()
Definition: pix3.c:163
l_int32 * makePixelSumTab8(void)
makePixelSumTab8()
Definition: pix3.c:2411
PIX * pixXor(PIX *pixd, PIX *pixs1, PIX *pixs2)
pixXor()
Definition: pix3.c:1688
PIX * pixSubtract(PIX *pixd, PIX *pixs1, PIX *pixs2)
pixSubtract()
Definition: pix3.c:1753
l_ok pixCropToMatch(PIX *pixs1, PIX *pixs2, PIX **ppixd1, PIX **ppixd2)
pixCropToMatch()
Definition: pix5.c:1224
#define PIX_DST
Definition: pix.h:331
@ L_COPY
Definition: pix.h:712
@ L_CLONE
Definition: pix.h:713
#define PIX_XOR
Definition: pix.h:340
#define PIX_SRC
Definition: pix.h:330
#define PIX_CLR
Definition: pix.h:333
#define PIX_NOT(op)
Definition: pix.h:332
#define PIX_SET
Definition: pix.h:334
void pixaDestroy(PIXA **ppixa)
pixaDestroy()
Definition: pixabasic.c:412
l_int32 pixaGetCount(PIXA *pixa)
pixaGetCount()
Definition: pixabasic.c:650
PIX * pixaGetPix(PIXA *pixa, l_int32 index, l_int32 accesstype)
pixaGetPix()
Definition: pixabasic.c:691
l_ok pixAddConstantGray(PIX *pixs, l_int32 val)
pixAddConstantGray()
Definition: pixarith.c:119
l_ok ptaAddPt(PTA *pta, l_float32 x, l_float32 y)
ptaAddPt()
Definition: ptabasic.c:343
PTA * ptaCreate(l_int32 n)
ptaCreate()
Definition: ptabasic.c:120
l_int32 lqueueGetCount(L_QUEUE *lq)
lqueueGetCount()
Definition: queue.c:286
void lqueueDestroy(L_QUEUE **plq, l_int32 freeflag)
lqueueDestroy()
Definition: queue.c:134
void * lqueueRemove(L_QUEUE *lq)
lqueueRemove()
Definition: queue.c:257
l_ok lqueueAdd(L_QUEUE *lq, void *item)
lqueueAdd()
Definition: queue.c:188
L_QUEUE * lqueueCreate(l_int32 nalloc)
lqueueCreate()
Definition: queue.c:93
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
PIX * pixFillHolesToBoundingRect(PIX *pixs, l_int32 minsize, l_float32 maxhfract, l_float32 minfgfract)
pixFillHolesToBoundingRect()
Definition: seedfill.c:847
l_ok pixSeedfillGrayInvSimple(PIX *pixs, PIX *pixm, l_int32 connectivity)
pixSeedfillGrayInvSimple()
Definition: seedfill.c:2042
PIX * pixSeedspread(PIX *pixs, l_int32 connectivity)
pixSeedspread()
Definition: seedfill.c:2792
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
static l_int32 pixQualifyLocalMinima(PIX *pixs, PIX *pixm, l_int32 maxval)
pixQualifyLocalMinima()
Definition: seedfill.c:3083
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
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
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
PIX * pixSeedfillBinary(PIX *pixd, PIX *pixs, PIX *pixm, l_int32 connectivity)
pixSeedfillBinary()
Definition: seedfill.c:247
PIX * pixFillClosedBorders(PIX *pixs, l_int32 connectivity)
pixFillClosedBorders()
Definition: seedfill.c:660
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
PIX * pixSeedfillGrayBasin(PIX *pixb, PIX *pixm, l_int32 delta, l_int32 connectivity)
pixSeedfillGrayBasin()
Definition: seedfill.c:2444
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
PIX * pixFindEqualValues(PIX *pixs1, PIX *pixs2)
pixFindEqualValues()
Definition: seedfill.c:3251
l_ok pixSelectedLocalExtrema(PIX *pixs, l_int32 mindist, PIX **ppixmin, PIX **ppixmax)
pixSelectedLocalExtrema()
Definition: seedfill.c:3191
l_ok pixSeedfillGrayInv(PIX *pixs, PIX *pixm, l_int32 connectivity)
pixSeedfillGrayInv()
Definition: seedfill.c:988
PIX * pixExtractBorderConnComps(PIX *pixs, l_int32 connectivity)
pixExtractBorderConnComps()
Definition: seedfill.c:698
l_ok pixSelectMinInConnComp(PIX *pixs, PIX *pixm, PTA **ppta, NUMA **pnav)
pixSelectMinInConnComp()
Definition: seedfill.c:3318
PIX * pixHolesByFilling(PIX *pixs, l_int32 connectivity)
pixHolesByFilling()
Definition: seedfill.c:609
l_ok pixLocalExtrema(PIX *pixs, l_int32 maxmin, l_int32 minmax, PIX **ppixmin, PIX **ppixmax)
pixLocalExtrema()
Definition: seedfill.c:3019
PIX * pixSeedfillBinaryRestricted(PIX *pixd, PIX *pixs, PIX *pixm, l_int32 connectivity, l_int32 xmax, l_int32 ymax)
pixSeedfillBinaryRestricted()
Definition: seedfill.c:335
PIX * pixRemoveBorderConnComps(PIX *pixs, l_int32 connectivity)
pixRemoveBorderConnComps()
Definition: seedfill.c:737
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
l_ok pixSeedfillGray(PIX *pixs, PIX *pixm, l_int32 connectivity)
pixSeedfillGray()
Definition: seedfill.c:929
PIX * pixFillBgFromBorder(PIX *pixs, l_int32 connectivity)
pixFillBgFromBorder()
Definition: seedfill.c:787
l_ok pixSeedfillGraySimple(PIX *pixs, PIX *pixm, l_int32 connectivity)
pixSeedfillGraySimple()
Definition: seedfill.c:1971
PIX * pixRemoveSeededComponents(PIX *pixd, PIX *pixs, PIX *pixm, l_int32 connectivity, l_int32 bordersize)
pixRemoveSeededComponents()
Definition: seedfill.c:3431
PIX * pixDistanceFunction(PIX *pixs, l_int32 connectivity, l_int32 outdepth, l_int32 boundcond)
pixDistanceFunction()
Definition: seedfill.c:2535
Definition: pix.h:492
Definition: queue.h:65
Definition: array.h:71
Definition: pix.h:139
Definition: pix.h:456
Definition: pix.h:517
void lept_stderr(const char *fmt,...)
lept_stderr()
Definition: utils1.c:306