Class RegionMergeTree

All Implemented Interfaces:
Direct Known Subclasses:
ClusterLabeledImage, MergeRegionMeanShift, MergeSmallRegions

public class RegionMergeTree extends Object implements Stoppable
Merges regions together quickly and efficiently using a directed tree graph. To merge two segments together first call markMerge(int, int). Then after all the regions which are to be merged are marked call performMerge(boofcv.struct.image.GrayS32, org.ddogleg.struct.DogArray_I32). Internally a disjoint-set forest tree graph is maintained using an array. When two regions are marked to be merged (set-union) path-compression is done. After merging hsa finished, the graph is fully compressed so that all nodes point to their root directly. Then the output is computed.
  • Field Details

    • mergeList

      protected DogArray_I32 mergeList
    • tmpMemberCount

      protected DogArray_I32 tmpMemberCount
    • rootID

      protected DogArray_I32 rootID
    • stopRequested

      protected boolean stopRequested
  • Constructor Details

    • RegionMergeTree

      public RegionMergeTree()
  • Method Details

    • initializeMerge

      public void initializeMerge(int numRegions)
      Must call before any other functions.
      numRegions - Total number of regions.
    • performMerge

      public void performMerge(GrayS32 pixelToRegion, DogArray_I32 regionMemberCount)
      Merges regions together and updates the provided data structures for said changes.
      pixelToRegion - (Input/Output) Image used to convert pixel location in region ID. Modified.
      regionMemberCount - (Input/Output) List containing how many pixels belong to each region. Modified.
    • flowIntoRootNode

      protected void flowIntoRootNode(DogArray_I32 regionMemberCount)
      For each region in the merge list which is not a root node, find its root node and add to the root node its member count and set the index in mergeList to the root node. If a node is a root node just note what its new ID will be after all the other segments are removed.
    • setToRootNodeNewID

      protected void setToRootNodeNewID(DogArray_I32 regionMemberCount)
      Does much of the work needed to remove the redundant segments that are being merged into their root node. The list of member count is updated. mergeList is updated with the new segment IDs.
    • markMerge

      protected void markMerge(int regionA, int regionB)

      This function will mark two regions for merger. Equivalent to set-union operation.

      If the two regions have yet to be merged into any others then regionB will become a member of regionA. Otherwise a quick heck is done to see if they are already marked for merging. If that fails it will traverse down the tree for each region until it gets to their roots. If the roots are not the same then they are merged. Either way the path is updated such that the quick check will pass.

    • requestStop

      public void requestStop()
      Specified by:
      requestStop in interface Stoppable
    • isStopRequested

      public boolean isStopRequested()
      Specified by:
      isStopRequested in interface Stoppable