Package boofcv.alg.segmentation.fh04

Class SegmentFelzenszwalbHuttenlocher04<T extends ImageBase<T>>

java.lang.Object
boofcv.alg.segmentation.fh04.SegmentFelzenszwalbHuttenlocher04<T>
public class SegmentFelzenszwalbHuttenlocher04<T extends ImageBase<T>> extends Object

Implementation of Felzenszwalb-Huttenlocher [1] image segmentation algorithm. It is fast and uses a graph based heuristic with a tuning parameter that can be used to adjust region size. Regions are irregularly shaped.

It works by constructing a graph in which pixels are the nodes and edges describe the relationship between adjacent pixels. Each pixel has a weight that is determined from the difference in pixel values using the F-norm. The weights for all the edges are computed first and sorted from smallest to largest. In the next step the first edge in the list is selected and is tested to see if the nodes should be connected or not. This process is repeated for all edges. Small regions are then merged into large ones. For more details see [1].

NOTE:

  • Region ID's in output image will NOT be sequential. You need to call getRegionId() to find out what the ID's are.
  • The output image can't be a sub-image because it is used internally and needs to be a continuous block of memory.
  • Pixel connectivity rule and weight metric is by the FhEdgeWeights class passed in to the constructor.
  • To emulate the reference implementation use a

Algorithmic Changes:
This implementation is a faithful of the original and has been compared against the authors reference source code. It does produce different results from the reference, some times significant, due to the sensitivity of the algorithm to minor differences. The sensitivity arises from it being a greedy algorithm.

Here is a list of minor differences that cause different regions due to its sensitivity. The order in which edges with identical weights are sorted is arbitrary. The order that edges are computed is arbitrary. Floating point error in weight calculation gradually causes segmentation to diverge to a different solution even when given the same input.

One difference from the original is that Gaussian blur is not applied to the input image by default. That should be done prior to the image being passed in.

[1] Felzenszwalb, Pedro F., and Daniel P. Huttenlocher. "Efficient graph-based image segmentation." International Journal of Computer Vision 59.2 (2004): 167-181.

  • Field Details

  • Constructor Details

    • SegmentFelzenszwalbHuttenlocher04

      public SegmentFelzenszwalbHuttenlocher04(float k, int minimumSize, FhEdgeWeights<T> computeWeights)
      Specifies tuning parameter
      Parameters:
      k - Tuning parameter. Larger regions are preferred for larger values of K. Try 300
      minimumSize - Regions smaller than this are merged into larger regions
      computeWeights - Function used to compute the weight for all the edges.

  • Method Details

    • configureApproximateSort

      public void configureApproximateSort(int numBins)
      If this function is called the exact sort routine will not be used and instead an approximate routine will be used.
      Parameters:
      numBins - Number of bins. Try 2000. More bins the more accurate it will be

    • process

      public void process(T input, GrayS32 output)
      Segments the image. Each region in the output image is given a unique ID. To find out what the ID of each region is call getRegionId(). To get a list of number of pixels in each region call getRegionSizes().
      Parameters:
      input - Input image. Not modified.
      output - Output segmented image. Modified.

    • initialize

      protected void initialize(T input, GrayS32 output)
      Predeclares all memory required and sets data structures to their initial values

    • mergeRegions

      protected void mergeRegions()
      Follows the merge procedure output in [1]. Two regions are merged together if the edge linking them has a weight which is ≤ the minimum of the heaviest edges in the two regions.

    • mergeSmallRegions

      protected void mergeSmallRegions()
      Look at the remaining regions and if there are any small ones marge them into a larger region

    • find

      protected int find(int child)
      Finds the root given child. If the child does not point directly to the parent find the parent and make the child point directly towards it.

    • computeOutput

      protected void computeOutput()
      Searches for root nodes in the graph and adds their size to the list of region sizes. Makes sure all other nodes in the graph point directly at their root.

    • getRegionId

      public DogArray_I32 getRegionId()
      List of ID's for each region in the segmented image.

    • getRegionSizes

      public DogArray_I32 getRegionSizes()
      Number of pixels in each region

    • getInputType

      public ImageType<T> getInputType()