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