org.openimaj.image.pixel

Class ConnectedComponent

java.lang.Object

org.openimaj.image.pixel.PixelSet

org.openimaj.image.pixel.ConnectedComponent

All Implemented Interfaces:

Cloneable, Iterable<Pixel>, Readable, ReadableASCII, ReadableBinary, ReadWriteable, Writeable, WriteableASCII, WriteableBinary

Direct Known Subclasses:

PixelsFeature

public class ConnectedComponent
extends PixelSet

This class represents a connected region within an image and provides methods for accessing and manipulating that region.

Nothing stops an unconnected component being constructed, but it is important to realise that some methods may return unexpected results (e.g. boundary tracing). If you are only dealing with unconnected pixel sets, use the PixelSet superclass instead.

Author:

Jonathon Hare (jsh2@ecs.soton.ac.uk), David Dupplaw (dpd@ecs.soton.ac.uk)

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	ConnectedComponent.ConnectMode For boundary representations of ConnectedComponents, this enum determines and specifies how the boundary is calculated; either using a 4-connected rule, or an 8-connected rule.

Field Summary

Fields inherited from class org.openimaj.image.pixel.PixelSet

pixels

Constructor Summary

Constructors

Constructor and Description
ConnectedComponent() Default constructor.
ConnectedComponent(FImage mask, float thresh) Constructs a connected component from a mask image.
ConnectedComponent(int[][] img) Constructs a connected component from a mask image.
ConnectedComponent(int x, int y, int w, int h) Construct a rectangular ConnectedComponent.
ConnectedComponent(Polygon poly) Construct a new connected component from the given polygon.
ConnectedComponent(Set<Pixel> pixels) Construct a connected component from the given set of Pixels.
ConnectedComponent(Shape shape) Construct a new connected component from the given shape.

Method Summary

Modifier and Type	Method and Description
String	asciiHeader() Header for ascii input.
byte[]	binaryHeader() Header for binary input.
double	calculateAreaRatio(ConnectedComponent ch) Calculate the ratio of the area of the given connected component to the area of the connected component.
double	calculateAreaRatio(Polygon ch) Calculate the ratio of the area of the given polygon to the area of this connected component.
gnu.trove.list.array.TFloatArrayList	calculateBoundaryDistanceFromCentre() Calculates the distance from the centroid of every pixel on the 8-connected boundary of this component.
protected Polygon	calculateConvexHull_AndrewsMontone() Calculate the convex hull using Andrew's monotone chain 2D convex hull algorithm.
protected Polygon	calculateConvexHull_Melkman(List<Pixel> V) Calculate convex hull using Melkman's algorithm.
Polygon	calculateConvexHull() Calculates the convex hull polygon for this connected component using Andrew's montone algorithm.
RotatedRectangle	calculateOrientatedBoundingBox() Calculates the polygon that defines the minimum bounding box that best fits the connected component, at whatever angle that may be.
double	calculateOrientatedBoundingBoxAspectRatio() Compute the aspect ratio of the oriented bounding box.
double	calculatePercentageConvexHullFit() Calculate the ratio of the area of this component's convex hull to the actual area of this connected component.
ConnectedComponent	clone() Performs a deep copy on the connected component; that is, all pixels are also cloned.
protected int	code4(Pixel current, Pixel next) For the two pixels, determines the 4-connected chain code that will move from the first pixel to the next.
protected int	code8(Pixel current, Pixel next) For the two pixels, determines the 8-connected chain code that will move from the first pixel to the next.
int	estimateNumberOfVertices(int smoothWidth, int windowWidth) Estimates how many vertices are required to encode the boundary with the given smoothness and window width.
static ConnectedComponent	floodFill(FImage image, Pixel start) Performs a flood fill on the given image starting at the given pixel.
gnu.trove.list.array.TIntArrayList	freemanChainCode(ConnectedComponent.ConnectMode mode) Calculates the Freeman chaincode for this connected component.
List<Pixel>	getInnerBoundary(ConnectedComponent.ConnectMode mode) Returns an ordered list of pixels that are on the inner boundary of the shape.
List<Pixel>	getOuterBoundary() Returns an ordered list of pixels that are on the outer boundary of the shape.
protected int	isLeft(Pixel P0, Pixel P1, Pixel P2)
protected Pixel	nextEdgePixelACW4(Pixel current, int lastdir) Returns the next edge pixel when tracing a boundary in a 4-connected system.
protected Pixel	nextEdgePixelACW4(Pixel current, int lastdir, List<Pixel> outer) Returns the next edge pixel when tracing a boundary in a 4-connected system.
protected Pixel	nextEdgePixelACW8(Pixel current, int lastdir) Returns the next edge pixel when tracing a boundary in an 8-connected system.
static void	process(Collection<ConnectedComponent> components, ConnectedComponentProcessor p) Process the given set of connected components with the given ConnectedComponentProcessor.
ConnectedComponent	process(ConnectedComponentProcessor p) Process this connected component with the given ConnectedComponentProcessor and returns a new component containing the result.
ConnectedComponent	processInplace(ConnectedComponentProcessor p) Process a connected component with the given ConnectedComponentProcessor.
Polygon	toPolygon() Converts this connected component into a Polygon representation by performing a 4-connected boundary trace and converting the resulting pixels into vertices.

Methods inherited from class org.openimaj.image.pixel.PixelSet

addPixel, addPixel, bottomRightMostPixel, calculateArea, calculateAverageHeightWidth, calculateAverageHeightWidth, calculateBinaryMask, calculateCentroid, calculateCentroidPixel, calculateDirection, calculateMoment, calculateMoment, calculateMomentNormalised, calculateRegularBoundingBox, calculateRegularBoundingBoxAspectRatio, crop, extractPixels1d, extractPixels1d, extractPixels2d, find, find, fromShape, getPixels, iterator, merge, normMatrix, readASCII, readBinary, reposition, toFImage, toFImage, topLeftMostPixel, toString, toStringImage, transform, translate, writeASCII, writeBinary

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Detail

ConnectedComponent

public ConnectedComponent()

Default constructor. Has an empty implementation.

ConnectedComponent

public ConnectedComponent(Shape shape)

Construct a new connected component from the given shape. Pixels are created for the connected component that lie within the shape; but these pixels will not have specific values as they are not associated to any particular image.

Parameters:

shape - The shape from which to construct the connected component.

ConnectedComponent

public ConnectedComponent(Polygon poly)

Construct a new connected component from the given polygon. Pixels are created for the connected component that lie within the shape; but these pixels will not have specific values as they are not associated to any particular image.

Parameters:

poly - The polygon from which to construct the connected component.

ConnectedComponent

public ConnectedComponent(int x,
                          int y,
                          int w,
                          int h)

Construct a rectangular ConnectedComponent. Pixels are created for the area within the rectangle but these will not have any specific value as they are not associated to any particular image.

Parameters:

x - The top-left x-coordinate of the rectangle

y - The top-left y-coordinate of the rectangle

w - The width of the rectangle

h - The height of the rectangle

ConnectedComponent

public ConnectedComponent(int[][] img)

Constructs a connected component from a mask image. Pixels are created for areas within the mask image that are non-zero. Note that this may result in a connected component definition that is unconnected and some methods may not return expected results.

Parameters:

img - The mask image to construct a connected component from.

ConnectedComponent

public ConnectedComponent(FImage mask,
                          float thresh)

Constructs a connected component from a mask image. Pixels are created for areas within the mask image that are above the given threshold. Note that this may result in a connected component definition that is unconnected and some methods may not return expected results.

Parameters:

mask - The mask image to construct a connected component from.

thresh - the threshold value.

ConnectedComponent

public ConnectedComponent(Set<Pixel> pixels)

Construct a connected component from the given set of Pixels. The pixels are shallow copied into the connected component. If the pixels do not form a connected component then some methods in this class may not return expected results.

Parameters:

pixels - A Set of Pixels.

Method Detail

estimateNumberOfVertices

public int estimateNumberOfVertices(int smoothWidth,
                                    int windowWidth)

Estimates how many vertices are required to encode the boundary with the given smoothness and window width. Basically it determines how many strong peaks there are in the boundary, where the peak strength is determined by the two parameters. The window width determines how many boundary points are considered when iterating through the binary, while the smoothness determines how smooth the resulting boundary representation can be.

Parameters:

smoothWidth - The smoothness of the resulting boundary

windowWidth - The number of edge points to consider

Returns:

The estimated number of vertices required to encode the boundary.

isLeft

protected int isLeft(Pixel P0,
                     Pixel P1,
                     Pixel P2)

Parameters:

P0 -

P1 -

P2 -

Returns:

calculateConvexHull

public Polygon calculateConvexHull()

Calculates the convex hull polygon for this connected component using Andrew's montone algorithm.

Returns:

The polygon defining the convex hull shape for this component.

calculateAreaRatio

public double calculateAreaRatio(ConnectedComponent ch)

Calculate the ratio of the area of the given connected component to the area of the connected component. This does not consider whether the areas overlap.

Parameters:

ch - The connected component to test.

Returns:

The area ratio of the given connected component to this connected component.

calculateAreaRatio

public double calculateAreaRatio(Polygon ch)

Calculate the ratio of the area of the given polygon to the area of this connected component. This does not consider whether the areas overlap.

Parameters:

ch - The polygon to test again.

Returns:

The area ratio of the given polygon to this connected component.

calculatePercentageConvexHullFit

public double calculatePercentageConvexHullFit()

Calculate the ratio of the area of this component's convex hull to the actual area of this connected component. This gives an idea of how well the calculated convex hull fits the component. The value returned is a percentage (0-1).

Returns:

The area ratio of this component's convex hull its area.

calculateConvexHull_Melkman

protected Polygon calculateConvexHull_Melkman(List<Pixel> V)

Calculate convex hull using Melkman's algorithm. Based on http://softsurfer.com/Archive/algorithm_0203/algorithm_0203.htm

Copyright 2001, softSurfer (www.softsurfer.com) This code may be freely used and modified for any purpose providing that this copyright notice is included with it. SoftSurfer makes no warranty for this code, and cannot be held liable for any real or imagined damage resulting from its use. Users of this code must verify correctness for their application.

Parameters:

V - List of pixels containing within the region

Returns:

A polygon defining the shape of the convex hull

calculateConvexHull_AndrewsMontone

protected Polygon calculateConvexHull_AndrewsMontone()

Calculate the convex hull using Andrew's monotone chain 2D convex hull algorithm.

Returns:

A polygon defining the shape of the convex hull.

nextEdgePixelACW4

protected Pixel nextEdgePixelACW4(Pixel current,
                                  int lastdir)

Returns the next edge pixel when tracing a boundary in a 4-connected system.

Parameters:

current - The current pixel

lastdir - The last direction traversed

Returns:

The next pixel in the edge

nextEdgePixelACW4

protected Pixel nextEdgePixelACW4(Pixel current,
                                  int lastdir,
                                  List<Pixel> outer)

Returns the next edge pixel when tracing a boundary in a 4-connected system.

Parameters:

current - The current pixel

lastdir - The last direction traversed

outer - A list to fill with the outer boundary

Returns:

The next pixel in the edge

nextEdgePixelACW8

protected Pixel nextEdgePixelACW8(Pixel current,
                                  int lastdir)

Returns the next edge pixel when tracing a boundary in an 8-connected system.

Parameters:

current - The current pixel

lastdir - The last direction traversed

Returns:

The next pixel in the edge

code4

protected int code4(Pixel current,
                    Pixel next)

For the two pixels, determines the 4-connected chain code that will move from the first pixel to the next. If the pixels are not adjacent the method returns -1.

Parameters:

current - The current pixel

next - The next pixel

Returns:

The Freeman 4-connected chain code

code8

protected int code8(Pixel current,
                    Pixel next)

For the two pixels, determines the 8-connected chain code that will move from the first pixel to the next. If the pixels are not adjacent or diagonal then the method returns -1.

Parameters:

current - The current pixel

next - The next pixel

Returns:

The Freeman 8-connected chain code

toPolygon

public Polygon toPolygon()

Converts this connected component into a Polygon representation by performing a 4-connected boundary trace and converting the resulting pixels into vertices.

Returns:

A Polygon representing the inner boundary of the component.

getInnerBoundary

public List<Pixel> getInnerBoundary(ConnectedComponent.ConnectMode mode)

Returns an ordered list of pixels that are on the inner boundary of the shape. That means that the boundary points are all within the region. The list is ordered such that adjacent boundary pixels are adjacent in the list. The first pixel in the list should be the same as PixelSet.topLeftMostPixel().

Parameters:

mode - The ConnectedComponent.ConnectMode to use.

Returns:

An ordered list of pixels defining the inner boundary

getOuterBoundary

public List<Pixel> getOuterBoundary()

Returns an ordered list of pixels that are on the outer boundary of the shape. That means that the boundary points are all outside of the region. The list is ordered such that adjacent boundary pixels are adjacent in the list.

Returns:

An ordered list of pixels defining the outer boundary

freemanChainCode

public gnu.trove.list.array.TIntArrayList freemanChainCode(ConnectedComponent.ConnectMode mode)

Calculates the Freeman chaincode for this connected component. The chaincode is returned as a list of direction codes defining the path of the boundary.

The Freeman chaincode is a means for encoding the paths between nodes on the boundary of a shape, thereby reducing the encoding of a shape to a single start coordinate and a list of direction codes. The Freeman direction codes are 0-4 for 4-connected boundaries and 0-7 for 8-connected boundaries.

Parameters:

mode - 4 or 8 connectivity

Returns:

the chain code

process

public static void process(Collection<ConnectedComponent> components,
                           ConnectedComponentProcessor p)

Process the given set of connected components with the given ConnectedComponentProcessor.

Parameters:

components - The components to process

p - The process to process the components with

process

public ConnectedComponent process(ConnectedComponentProcessor p)

Process this connected component with the given ConnectedComponentProcessor and returns a new component containing the result.

Parameters:

p - The processor to process this component with

Returns:

A new component containing the result.

processInplace

public ConnectedComponent processInplace(ConnectedComponentProcessor p)

Process a connected component with the given ConnectedComponentProcessor. Side-affects this component.

Parameters:

p - The processor to process this component with

Returns:

A reference to this connected component.

floodFill

public static ConnectedComponent floodFill(FImage image,
                                           Pixel start)

Performs a flood fill on the given image starting at the given pixel. The result of the flood fill is returned as a ConnectedComponent.

Parameters:

image - The image on which to perform a flood fill

start - The start pixel to begin the flood

Returns:

A ConnectedComponent containing the resulting region.

clone

public ConnectedComponent clone()

Performs a deep copy on the connected component; that is, all pixels are also cloned.

Overrides:

clone in class Object

calculateBoundaryDistanceFromCentre

public gnu.trove.list.array.TFloatArrayList calculateBoundaryDistanceFromCentre()

Calculates the distance from the centroid of every pixel on the 8-connected boundary of this component. Returns a TFloatArrayList that contains the list of distances (in order of the boundary).

Returns:

A list (TFloatArrayList) of distances of boundary points to the centroid.

asciiHeader

public String asciiHeader()

Description copied from interface: ReadableASCII

Header for ascii input. Will be automatically read by IOUtils when using readASCII().

Specified by:

asciiHeader in interface ReadableASCII

Specified by:

asciiHeader in interface WriteableASCII

Overrides:

asciiHeader in class PixelSet

Returns:

header

binaryHeader

public byte[] binaryHeader()

Description copied from interface: ReadableBinary

Header for binary input. Will be automatically read by IOUtils when using readBinary().

Specified by:

binaryHeader in interface ReadableBinary

Specified by:

binaryHeader in interface WriteableBinary

Overrides:

binaryHeader in class PixelSet

Returns:

header

calculateOrientatedBoundingBoxAspectRatio

public double calculateOrientatedBoundingBoxAspectRatio()

Compute the aspect ratio of the oriented bounding box.

Returns:

the aspect ratio of the oriented bounding box.

calculateOrientatedBoundingBox

public RotatedRectangle calculateOrientatedBoundingBox()

Calculates the polygon that defines the minimum bounding box that best fits the connected component, at whatever angle that may be.

Returns:

A RotatedRectangle that defines the minimum bounding box.