view release on metacpan or  search on metacpan

lib/Image/Leptonica/Func/seedfill.pm  view on Meta::CPAN

               l_int32   pixSeedfillGray()
               l_int32   pixSeedfillGrayInv()

      Gray seedfill (source: Luc Vincent: sequential-reconstruction algorithm)
               l_int32   pixSeedfillGraySimple()
               l_int32   pixSeedfillGrayInvSimple()

      Gray seedfill variations
               PIX      *pixSeedfillGrayBasin()

      Distance function (source: Luc Vincent)
               PIX      *pixDistanceFunction()

      Seed spread (based on distance function)
               PIX      *pixSeedspread()

      Local extrema:
               l_int32   pixLocalExtrema()
        static l_int32   pixQualifyLocalMinima()
               l_int32   pixSelectedLocalExtrema()
               PIX      *pixFindEqualValues()

      Selection of minima in mask of connected components
               PTA      *pixSelectMinInConnComp()

      Removal of seeded connected components from a mask
               PIX      *pixRemoveSeededComponents()


           ITERATIVE RASTER-ORDER SEEDFILL

      The basic method in the Vincent seedfill (aka reconstruction)
      algorithm is simple.  We describe here the situation for
      binary seedfill.  Pixels are sampled in raster order in
      the seed image.  If they are 4-connected to ON pixels
      either directly above or to the left, and are not masked
      out by the mask image, they are turned on (or remain on).
      (Ditto for 8-connected, except you need to check 3 pixels
      on the previous line as well as the pixel to the left
      on the current line.  This is extra computational work
      for relatively little gain, so it is preferable
      in most situations to use the 4-connected version.)
      The algorithm proceeds from UR to LL of the image, and
      then reverses and sweeps up from LL to UR.
      These double sweeps are iterated until there is no change.
      At this point, the seed has entirely filled the region it
      is allowed to, as delimited by the mask image.

      The grayscale seedfill is a straightforward generalization
      of the binary seedfill, and is described in seedfillLowGray().

      For some applications, the filled seed will later be OR'd
      with the negative of the mask.   This is used, for example,
      when you flood fill into a 4-connected region of OFF pixels
      and you want the result after those pixels are turned ON.

      Note carefully that the mask we use delineates which pixels
      are allowed to be ON as the seed is filled.  We will call this
      a "filling mask".  As the seed expands, it is repeatedly
      ANDed with the filling mask: s & fm.  The process can equivalently
      be formulated using the inverse of the filling mask, which
      we will call a "blocking mask": bm = ~fm.   As the seed
      expands, the blocking mask is repeatedly used to prevent
      the seed from expanding into the blocking mask.  This is done
      by set subtracting the blocking mask from the expanded seed:
      s - bm.  Set subtraction of the blocking mask is equivalent
      to ANDing with the inverse of the blocking mask: s & (~bm).
      But from the inverse relation between blocking and filling
      masks, this is equal to s & fm, which proves the equivalence.

      For efficiency, the pixels can be taken in larger units
      for processing, but still in raster order.  It is natural
      to take them in 32-bit words.  The outline of the work
      to be done for 4-cc (not including special cases for boundary
      words, such as the first line or the last word in each line)
      is as follows.  Let the filling mask be m.  The
      seed is to fill "under" the mask; i.e., limited by an AND
      with the mask.  Let the current word be w, the word
      in the line above be wa, and the previous word in the
      current line be wp.   Let t be a temporary word that
      is used in computation.  Note that masking is performed by
      w & m.  (If we had instead used a "blocking" mask, we
      would perform masking by the set subtraction operation,
      w - m, which is defined to be w & ~m.)

      The entire operation can be implemented with shifts,
      logical operations and tests.  For each word in the seed image
      there are two steps.  The first step is to OR the word with
      the word above and with the rightmost pixel in wp (call it "x").
      Because wp is shifted one pixel to its right, "x" is ORed
      to the leftmost pixel of w.  We then clip to the ON pixels in
      the mask.  The result is
               t  <--  (w | wa | x000... ) & m
      We've now finished taking data from above and to the left.
      The second step is to allow filling to propagate horizontally
      in t, always making sure that it is properly masked at each
      step.  So if filling can be done (i.e., t is neither all 0s
      nor all 1s), iteratively take:
           t  <--  (t | (t >> 1) | (t << 1)) & m
      until t stops changing.  Then write t back into w.

      Finally, the boundary conditions require we note that in doing
      the above steps:
          (a) The words in the first row have no wa
          (b) The first word in each row has no wp in that row
          (c) The last word in each row must be masked so that
              pixels don't propagate beyond the right edge of the
              actual image.  (This is easily accomplished by
              setting the out-of-bound pixels in m to OFF.)

=head1 FUNCTIONS

=head2 pixDistanceFunction

PIX * pixDistanceFunction ( PIX *pixs, l_int32 connectivity, l_int32 outdepth, l_int32 boundcond )

  pixDistanceFunction()

      Input:  pixs  (1 bpp source)
              connectivity  (4 or 8)
              outdepth (8 or 16 bits for pixd)

lib/Image/Leptonica/Func/seedfill.pm  view on Meta::CPAN

=head2 pixSeedfillBinary

PIX * pixSeedfillBinary ( PIX *pixd, PIX *pixs, PIX *pixm, l_int32 connectivity )

  pixSeedfillBinary()

      Input:  pixd  (<optional>; this can be null, equal to pixs,
                     or different from pixs; 1 bpp)
              pixs  (1 bpp seed)
              pixm  (1 bpp filling mask)
              connectivity  (4 or 8)
      Return: pixd always

  Notes:
      (1) This is for binary seedfill (aka "binary reconstruction").
      (2) There are 3 cases:
            (a) pixd == null (make a new pixd)
            (b) pixd == pixs (in-place)
            (c) pixd != pixs
      (3) If you know the case, use these patterns for clarity:
            (a) pixd = pixSeedfillBinary(NULL, pixs, ...);
            (b) pixSeedfillBinary(pixs, pixs, ...);
            (c) pixSeedfillBinary(pixd, pixs, ...);
      (4) The resulting pixd contains the filled seed.  For some
          applications you want to OR it with the inverse of
          the filling mask.
      (5) The input seed and mask images can be different sizes, but
          in typical use the difference, if any, would be only
          a few pixels in each direction.  If the sizes differ,
          the clipping is handled by the low-level function
          seedfillBinaryLow().

=head2 pixSeedfillBinaryRestricted

PIX * pixSeedfillBinaryRestricted ( PIX *pixd, PIX *pixs, PIX *pixm, l_int32 connectivity, l_int32 xmax, l_int32 ymax )

  pixSeedfillBinaryRestricted()

      Input:  pixd  (<optional>; this can be null, equal to pixs,
                     or different from pixs; 1 bpp)
              pixs  (1 bpp seed)
              pixm  (1 bpp filling mask)
              connectivity  (4 or 8)
              xmax (max distance in x direction of fill into the mask)
              ymax (max distance in y direction of fill into the mask)
      Return: pixd always

  Notes:
      (1) See usage for pixSeedfillBinary(), which has unrestricted fill.
          In pixSeedfillBinary(), the filling distance is unrestricted
          and can be larger than pixs, depending on the topology of
          th mask.
      (2) There are occasions where it is useful not to permit the
          fill to go more than a certain distance into the mask.
          @xmax specifies the maximum horizontal distance allowed
          in the fill; @ymax does likewise in the vertical direction.
      (3) Operationally, the max "distance" allowed for the fill
          is a linear distance from the original seed, independent
          of the actual mask topology.
      (4) Another formulation of this problem, not implemented,
          would use the manhattan distance from the seed, as
          determined by a breadth-first search starting at the seed
          boundaries and working outward where the mask fg allows.
          How this might use the constraints of separate xmax and ymax
          is not clear.

=head2 pixSeedfillGray

l_int32 pixSeedfillGray ( PIX *pixs, PIX *pixm, l_int32 connectivity )

  pixSeedfillGray()

      Input:  pixs  (8 bpp seed; filled in place)
              pixm  (8 bpp filling mask)
              connectivity  (4 or 8)
      Return: 0 if OK, 1 on error

  Notes:
      (1) This is an in-place filling operation on the seed, pixs,
          where the clipping mask is always above or at the level
          of the seed as it is filled.
      (2) For details of the operation, see the description in
          seedfillGrayLow() and the code there.
      (3) As an example of use, see the description in pixHDome().
          There, the seed is an image where each pixel is a fixed
          amount smaller than the corresponding mask pixel.
      (4) Reference paper :
            L. Vincent, Morphological grayscale reconstruction in image
            analysis: applications and efficient algorithms, IEEE Transactions
            on  Image Processing, vol. 2, no. 2, pp. 176-201, 1993.

=head2 pixSeedfillGrayBasin

PIX * pixSeedfillGrayBasin ( PIX *pixb, PIX *pixm, l_int32 delta, l_int32 connectivity )

  pixSeedfillGrayBasin()

      Input:  pixb  (binary mask giving seed locations)
              pixm  (8 bpp basin-type filling mask)
              delta (amount of seed value above mask)
              connectivity  (4 or 8)
      Return: pixd (filled seed) if OK, null on error

  Notes:
      (1) This fills from a seed within basins defined by a filling mask.
          The seed value(s) are greater than the corresponding
          filling mask value, and the result has the bottoms of
          the basins raised by the initial seed value.
      (2) The seed has value 255 except where pixb has fg (1), which
          are the seed 'locations'.  At the seed locations, the seed
          value is the corresponding value of the mask pixel in pixm
          plus @delta.  If @delta == 0, we return a copy of pixm.
      (3) The actual filling is done using the standard grayscale filling
          operation on the inverse of the mask and using the inverse
          of the seed image.  After filling, we return the inverse of
          the filled seed.
      (4) As an example of use: pixm can describe a grayscale image
          of text, where the (dark) text pixels are basins of
          low values; pixb can identify the local minima in pixm (say, at
          the bottom of the basins); and delta is the amount that we wish