tda

README

tda : Topological data analysis in Golang

The tda package provides support for a few methods from topological data analysis.

Currently, methods for gridded data (images) are provided, including:

• Connected component labeling for binary images

• Object persistence analysis

• Landscape profiles

• Convex hull peels

See the examples directory for some use cases.

Below is a scatterplot of object birth/death times for this image, with 90%, 95%, and 99% convex hull peels plotted in red. See examples/persistence for the code used to produce this plot.

Below is a landscape plot based on the same image used above. See examples/landscape for the code used to produce this plot.

Below is an animated PNG showing part of the image above being thresholded at a sequence of values. See examples/animate_threshold for the code used to produce this plot.

Documentation

Index

• func AnimateThreshold(img []int, rows, steps int, outfile string)
• func GetImage(filename string) ([]int, int)
• type ConvexPeel
  • func NewConvexPeel(x, y []float64) *ConvexPeel
  • func (cp *ConvexPeel) Area() float64
  • func (cp *ConvexPeel) Centroid() [2]float64
  • func (cp *ConvexPeel) HullPoints(buf [][2]float64) [][2]float64
  • func (cp *ConvexPeel) NumPoints() int
  • func (cp *ConvexPeel) Peel()
  • func (cp *ConvexPeel) PeelTo(frac float64)
  • func (cp *ConvexPeel) Perimeter() float64
  • func (cp *ConvexPeel) Reset()
  • func (cp *ConvexPeel) Stats(depth []float64) []Stat
• type ConvexPeelPlot
  • func (cpp *ConvexPeelPlot) Plot()
• type Label
  • func NewLabel(mask []uint8, rows int, buf []int) *Label
  • func (la *Label) Bboxes(buf []image.Rectangle) []image.Rectangle
  • func (la *Label) Cols() int
  • func (la *Label) Labels() []int
  • func (la *Label) Mask() []uint8
  • func (la *Label) NumComponents() int
  • func (la *Label) Rows() int
  • func (la *Label) Sizes(buf []int) []int
• type Landscape
  • func NewLandscape(birth, death []float64) *Landscape
  • func (ls *Landscape) Eval(t float64, depth []int) []float64
  • func (ls *Landscape) Stats(depth []int, npoints int) []Stat
• type LandscapePlot
  • func (lsp *LandscapePlot) Plot()
• type Persistence
  • func NewPersistence(img []int, rows, steps int) *Persistence
  • func (ps *Persistence) BirthDeath() ([]float64, []float64)
  • func (ps *Persistence) Labels() []int
  • func (ps *Persistence) Sort()
  • func (ps *Persistence) Trajectories() []Trajectory
• type Pstate
• type Stat
• type Trajectory

Functions

func AnimateThreshold

func AnimateThreshold(img []int, rows, steps int, outfile string)

AnimateThreshold constructs an animated PNG showing a sequence of thresholded versions of an image. The image pixel data are provided as a slice of integers, which must conform to a rectangular image with the given number of rows. The animation is based on a series of steps in which the image is thresholded at a linear sequence of values ranging from the minimum to the maximum pixel intensity. The image is written in animated png (.apng) format to the given file.

func GetImage

func GetImage(filename string) ([]int, int)

GetImage returns the pixel levels of a jpeg or png file as greyscale values, along with the number of rows in the image.

Types

type ConvexPeel

type ConvexPeel struct {
	// contains filtered or unexported fields
}

ConvexPeel supports calculation of a sequence of convex hulls for a point set.

func NewConvexPeel

func NewConvexPeel(x, y []float64) *ConvexPeel

NewConvexPeel calculates a sequence of peeled convex hulls for the given points.

func (*ConvexPeel) Area

func (cp *ConvexPeel) Area() float64

Area returns the area of the current convex hull.

func (*ConvexPeel) Centroid

func (cp *ConvexPeel) Centroid() [2]float64

Centroid returns the centroid of the current point set, i.e. the points that have not been peeled.

func (*ConvexPeel) HullPoints

func (cp *ConvexPeel) HullPoints(buf [][2]float64) [][2]float64

HullPoints returns the points that are on the current convex hull.

func (*ConvexPeel) NumPoints

func (cp *ConvexPeel) NumPoints() int

NumPoints returns the number of active points (i.e. the number of points that have not been peeled).

func (*ConvexPeel) Peel

func (cp *ConvexPeel) Peel()

Peel removes the current hull points and recomputes the hull.

func (*ConvexPeel) PeelTo

func (cp *ConvexPeel) PeelTo(frac float64)

PeelTo peels until no more than the given fraction of points remains.

func (*ConvexPeel) Perimeter

func (cp *ConvexPeel) Perimeter() float64

Perimeter returns the perimeter of the current convex hull.

func (*ConvexPeel) Reset

func (cp *ConvexPeel) Reset()

Reset returns to the original state, with no points having been peeled.

func (*ConvexPeel) Stats

func (cp *ConvexPeel) Stats(depth []float64) []Stat

Stats obtains the area, perimeter, and centroid for a series of convex peel profiles of a point set. The convex peel is constructed for a grid of npoints depth values spanning from from high to low.

type ConvexPeelPlot

type ConvexPeelPlot struct {

	// Input image file name, should be a png or jpeg image file
	Filename string

	// Output filename for the plot, suffix determines format
	Outfile string

	// The number of image thresholding steps
	Isteps int

	// Plot these convex peel fractions (e.g. Depth=0.95 trims off 5% of the data)
	Depth []float64
}

ConvexPeelPlot supports constructing plots of convex hull peels.

func (*ConvexPeelPlot) Plot

func (cpp *ConvexPeelPlot) Plot()

Plot generates a plot of a set of birth/death times along with several convex hull peels.

type Label

type Label struct {
	// contains filtered or unexported fields
}

Label finds the connected components in a binary image.

func NewLabel

func NewLabel(mask []uint8, rows int, buf []int) *Label

NewLabel finds the connected components of a given binary image (mask), which is rectangular with the given number of rows. buf is an optional memory buffer having the same length as mask. Use the methods of the returned Label value to obtain information about the labels.

The algorithm implemented here is the run-based algorithm of He et al. (2008), IEEE Transactions on Image Processing, 17:5. https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=4472694

func (*Label) Bboxes

func (la *Label) Bboxes(buf []image.Rectangle) []image.Rectangle

Bboxes returns the bounding boxes for every labeled component. The bounding box for the component with label k is held in position k of the returned slice. The provided slice is used if large enough.

func (*Label) Cols

func (la *Label) Cols() int

Cols returns the number of columns in the image that is being labeled.

func (*Label) Labels

func (la *Label) Labels() []int

Labels returns the component labels.

func (*Label) Mask

func (la *Label) Mask() []uint8

Mask returns the image that is being labeled.

func (*Label) NumComponents

func (la *Label) NumComponents() int

NumComponents returns the number of components, including the background component. The maximum component label is one less than the number of components.

func (*Label) Rows

func (la *Label) Rows() int

Rows returns the number of rows in the image that is being labeled.

func (*Label) Sizes

func (la *Label) Sizes(buf []int) []int

Sizes returns the sizes (number of pixels) in every labeled component of the array. The size of the component with label k is held in position k of the returned slice. The provided buffer will be used if large enough.

type Landscape

type Landscape struct {
	// contains filtered or unexported fields
}

Landscape supports construction of landscape diagrams for describing the persistence homology of an image.

func NewLandscape

func NewLandscape(birth, death []float64) *Landscape

NewLandscape returns a Landscape value for the given object birth and death times. Call the Eval method to evaluate the landscape function at prescribed depths.

func (*Landscape) Eval

func (ls *Landscape) Eval(t float64, depth []int) []float64

Eval evaluates the landscape function at a given point t, at a given series of depths. Depth=0 corresponds to the maximum landscape pofile, depth=1 corresponds to the second highest landscape profile etc.

func (*Landscape) Stats

func (ls *Landscape) Stats(depth []int, npoints int) []Stat

Stats obtains the area, perimeter, and centroid for a series of landscape profiles. The landscape function is evaluated on a grid of npoints points over the range of the landscape function.

type LandscapePlot

type LandscapePlot struct {

	// Input image file name, should be a png or jpeg image file
	Filename string

	// Output filename for the plot, suffix determines format
	Outfile string

	// The number of image thresholding steps
	Isteps int

	// The number of steps along the landscape profile
	Lsteps int

	// Plot these landscape depths
	Depth []int
}

LandscapePlot supports creation of plots of landscape functions.

func (*LandscapePlot) Plot

func (lsp *LandscapePlot) Plot()

Plot generates a landscape plom a LandscapePlot value.

type Persistence

type Persistence struct {
	// contains filtered or unexported fields
}

Persistence constructs object persistence trajectories for an image.

func NewPersistence

func NewPersistence(img []int, rows, steps int) *Persistence

NewPersistence calculates an object persistence diagram for the given image, which must be rectangular with the given number of rows. The steps argument determines the threshold increments used to produce the persistence diagram.

func (*Persistence) BirthDeath

func (ps *Persistence) BirthDeath() ([]float64, []float64)

BirthDeath returns the object birth and death times as float64 slices.

func (*Persistence) Labels

func (ps *Persistence) Labels() []int

Labels returns the current object labels.

func (*Persistence) Sort

func (ps *Persistence) Sort()

Sort gives a deterministic order to the persistence trajectories.

func (*Persistence) Trajectories

func (ps *Persistence) Trajectories() []Trajectory

Trajectories returns the persistence trajectories. Each outer element of the returned slice is a sequence of states defining a trajectory. The order of the trajectories may be non-deterministic, calling Sort before calling Trajectories ensures a deterministic order.

type Pstate

type Pstate struct {

	// The connected component label for the object (not
	// comparable across points on a trajectory).
	Label int

	// The size in pixels of the object.
	Size int

	// The maximum intensity of the object.
	Max int

	// The step of the algorithm at which the state is defined.
	Step int

	// The threshold used to define the image used at this step of
	// the algorithm.
	Threshold int

	// A bounding box for the object
	Bbox image.Rectangle
}

Pstate defines a state in a persistence trajectory.

type Stat

type Stat struct {
	Depth     float64
	Area      float64
	Perimeter float64
	Centroid  [2]float64
}

Stat contains summary statistics about a landscape or convex peel profile at a given depth.

type Trajectory

type Trajectory []Pstate

Trajectory is a sequence of persistence states defined by labeling an image thresholded at an increasing sequence of threshold values.