boofcv.alg.segmentation.fh04

Class SegmentFelzenszwalbHuttenlocher04<T extends ImageBase>

java.lang.Object

boofcv.alg.segmentation.fh04.SegmentFelzenszwalbHuttenlocher04<T>

public class SegmentFelzenszwalbHuttenlocher04<T extends ImageBase>
extends java.lang.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.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	SegmentFelzenszwalbHuttenlocher04.Edge Describes the relationship between to adjacent pixels in the image.

Constructor Summary

Constructors

Constructor and Description
SegmentFelzenszwalbHuttenlocher04(float k, int minimumSize, FhEdgeWeights<T> computeWeights) Specifies tuning parameter

Method Summary

Modifier and Type	Method and Description
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.
ImageType<T>	getInputType()
GrowQueue_I32	getRegionId() List of ID's for each region in the segmented image.
GrowQueue_I32	getRegionSizes() Number of pixels in each region
void	process(T input, GrayS32 output) Segments the image.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

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 Detail

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.

getRegionId

public GrowQueue_I32 getRegionId()

List of ID's for each region in the segmented image.

getRegionSizes

public GrowQueue_I32 getRegionSizes()

Number of pixels in each region

getInputType

public ImageType<T> getInputType()