Persistence 1D incl. Reconstruct1D  1.3
Finding extrema in one dimensional data, filtering them by persistence and reconstructing smooth functions
Public Member Functions | Protected Member Functions | Protected Attributes | List of all members
p1d::Persistence1D Class Reference

Finds extrema and their persistence in one-dimensional data. More...

#include <persistence1d.hpp>

Public Member Functions

 Persistence1D ()
 
 ~Persistence1D ()
 
bool RunPersistence (const std::vector< float > &InputData)
 Call this function with a vector of one dimensional data to find extrema features in the data. More...
 
void PrintPairs (const std::vector< TPairedExtrema > &pairs) const
 Prints the contents of the TPairedExtrema vector. More...
 
void PrintResults (const float threshold=0.0, const bool matlabIndexing=false) const
 Prints the global minimum and all paired extrema whose persistence is greater or equal to threshold. More...
 
bool GetPairedExtrema (std::vector< TPairedExtrema > &pairs, const float threshold=0, const bool matlabIndexing=false) const
 Use this method to get the results of RunPersistence. More...
 
bool GetExtremaIndices (std::vector< int > &min, std::vector< int > &max, const float threshold=0, const bool matlabIndexing=false) const
 Use this method to get two vectors with all indices of PairedExterma. More...
 
int GetGlobalMinimumIndex (const bool matlabIndexing=false) const
 Returns the index of the global minimum. More...
 
float GetGlobalMinimumValue () const
 Returns the value of the global minimum. More...
 
bool VerifyResults ()
 Runs basic sanity checks on results of RunPersistence: More...
 

Protected Member Functions

void MergeComponents (const int firstIdx, const int secondIdx)
 Merges two components by doing the following: More...
 
void CreatePairedExtrema (const int firstIdx, const int secondIdx)
 Creates a new PairedExtrema from the two indices, and adds it to PairedFeatures. More...
 
void CreateComponent (const int minIdx)
 Creates a new component at a local minimum. More...
 
void ExtendComponent (const int componentIdx, const int dataIdx)
 Extends the component's region by one vertex: More...
 
void Init ()
 Initializes main data structures used in class: More...
 
void CreateIndexValueVector ()
 Creates SortedData vector. More...
 
void Watershed ()
 Main algorithm - all of the work happen here. More...
 
void SortPairedExtrema ()
 Sorts the PairedExtrema list according to the persistence of the features. More...
 
std::vector< TPairedExtrema >::const_iterator FilterByPersistence (const float threshold=0) const
 Returns an iterator to the first element in PairedExtrema whose persistence is bigger or equal to threshold. More...
 
bool VerifyAliveComponents ()
 Runs at the end of RunPersistence, after Watershed. More...
 

Protected Attributes

std::vector< float > Data
 Contain a copy of the original input data. More...
 
std::vector< TIdxAndDataSortedData
 Contains a copy the value and index pairs of Data, sorted according to the data values. More...
 
std::vector< int > Colors
 Contains the Component assignment for each vertex in Data. More...
 
std::vector< TComponentComponents
 A vector of Components. More...
 
std::vector< TPairedExtremaPairedExtrema
 A vector of paired extrema features - always a minimum and a maximum. More...
 
unsigned int TotalComponents
 
bool AliveComponentsVerified
 

Detailed Description

Finds extrema and their persistence in one-dimensional data.

Local minima and local maxima are extracted, paired, and sorted according to their persistence. The global minimum is extracted as well.

We assume a connected one-dimensional domain. Think of "data on a line", or a function f(x) over some domain xmin <= x <= xmax.

Examples
FilesAndFilters.cpp, MatlabVisualization.cpp, MatplotlibVisualization.cpp, and SimpleDataVector.cpp.

Definition at line 106 of file persistence1d.hpp.

Constructor & Destructor Documentation

◆ Persistence1D()

p1d::Persistence1D::Persistence1D ( )
inline

Definition at line 109 of file persistence1d.hpp.

◆ ~Persistence1D()

p1d::Persistence1D::~Persistence1D ( )
inline

Definition at line 113 of file persistence1d.hpp.

Member Function Documentation

◆ CreateComponent()

void p1d::Persistence1D::CreateComponent ( const int  minIdx)
inlineprotected

Creates a new component at a local minimum.

Neighboring vertices are assumed to have no color.

  • Adds a new component to the components vector,
  • Initializes its edges and minimum index to minIdx.
  • Updates Colors[minIdx] to the component's color.
Parameters
[in]minIdxIndex of a local minimum.

Definition at line 491 of file persistence1d.hpp.

◆ CreateIndexValueVector()

void p1d::Persistence1D::CreateIndexValueVector ( )
inlineprotected

Creates SortedData vector.

Assumes Data is already set.

Definition at line 583 of file persistence1d.hpp.

◆ CreatePairedExtrema()

void p1d::Persistence1D::CreatePairedExtrema ( const int  firstIdx,
const int  secondIdx 
)
inlineprotected

Creates a new PairedExtrema from the two indices, and adds it to PairedFeatures.

Parameters
[in]firstIdx,secondIdxIndices of vertices to be paired. Order does not matter.

Definition at line 438 of file persistence1d.hpp.

◆ ExtendComponent()

void p1d::Persistence1D::ExtendComponent ( const int  componentIdx,
const int  dataIdx 
)
inlineprotected

Extends the component's region by one vertex:

  • Updates the matching component's edge to dataIdx..
  • updates Colors[dataIdx] to the component's color.
Parameters
[in]componentIdxIndex of component (the value of a neighboring vertex in Colors[]).
[in]dataIdxIndex of vertex which the component is extended to.

Definition at line 521 of file persistence1d.hpp.

◆ FilterByPersistence()

std::vector<TPairedExtrema>::const_iterator p1d::Persistence1D::FilterByPersistence ( const float  threshold = 0) const
inlineprotected

Returns an iterator to the first element in PairedExtrema whose persistence is bigger or equal to threshold.

If threshold is set to 0, returns an iterator to the first object in PairedExtrema.

Parameters
[in]thresholdMinimum persistence of features to be returned.

Definition at line 705 of file persistence1d.hpp.

◆ GetExtremaIndices()

bool p1d::Persistence1D::GetExtremaIndices ( std::vector< int > &  min,
std::vector< int > &  max,
const float  threshold = 0,
const bool  matlabIndexing = false 
) const
inline

Use this method to get two vectors with all indices of PairedExterma.

Returns false if no paired features were found. Returned vectors have the same length. Overwrites any data contained in min, max vectors.

Parameters
[out]minVector of indices of paired local minima.
[out]maxVector of indices of paired local maxima.
[in]thresholdReturn only indices for pairs whose persistence is greater than or equal to threshold.
[in]matlabIndexingSet this to true to change all indices to match Matlab's 1-indexing.
Examples
FilesAndFilters.cpp, MatlabVisualization.cpp, and MatplotlibVisualization.cpp.

Definition at line 241 of file persistence1d.hpp.

◆ GetGlobalMinimumIndex()

int p1d::Persistence1D::GetGlobalMinimumIndex ( const bool  matlabIndexing = false) const
inline

Returns the index of the global minimum.

The global minimum does not get paired and is not returned via GetPairedExtrema and GetExtremaIndices.

Examples
FilesAndFilters.cpp, MatlabVisualization.cpp, MatplotlibVisualization.cpp, and SimpleDataVector.cpp.

Definition at line 269 of file persistence1d.hpp.

◆ GetGlobalMinimumValue()

float p1d::Persistence1D::GetGlobalMinimumValue ( ) const
inline

Returns the value of the global minimum.

The global minimum does not get paired and is not returned via GetPairedExtrema and GetExtremaIndices.

Examples
FilesAndFilters.cpp, and SimpleDataVector.cpp.

Definition at line 287 of file persistence1d.hpp.

◆ GetPairedExtrema()

bool p1d::Persistence1D::GetPairedExtrema ( std::vector< TPairedExtrema > &  pairs,
const float  threshold = 0,
const bool  matlabIndexing = false 
) const
inline

Use this method to get the results of RunPersistence.

Returned pairs are sorted according to persistence, from least to most persistent.

Parameters
[out]pairsDestination vector for PairedExtrema
[in]thresholdMinimal persistence value of returned features. All PairedExtrema with persistence equal to or above this value will be returned. If left to default, all PairedMaxima will be returned.
[in]matlabIndexingSet this to true to change all indices of features to Matlab's 1-indexing.
Examples
FilesAndFilters.cpp, and SimpleDataVector.cpp.

Definition at line 206 of file persistence1d.hpp.

◆ Init()

void p1d::Persistence1D::Init ( )
inlineprotected

Initializes main data structures used in class:

  • Sets Colors[] to NO_COLOR
  • Reserves memory for Components and PairedExtrema

Note: SortedData is should be created before, separately, using CreateIndexValueVector()

Definition at line 557 of file persistence1d.hpp.

◆ MergeComponents()

void p1d::Persistence1D::MergeComponents ( const int  firstIdx,
const int  secondIdx 
)
inlineprotected

Merges two components by doing the following:

  • Destroys component with smaller hub (sets Alive=false).
  • Updates surviving component's edges to span the destroyed component's region.
  • Updates the destroyed component's edge vertex colors to the survivor's color in Colors[].
Parameters
[in]firstIdx,secondIdxIndices of components to be merged. Their order does not matter.

Definition at line 389 of file persistence1d.hpp.

◆ PrintPairs()

void p1d::Persistence1D::PrintPairs ( const std::vector< TPairedExtrema > &  pairs) const
inline

Prints the contents of the TPairedExtrema vector.

If called directly with a TPairedExtrema vector, the global minimum is not printed.

Parameters
[in]pairsVector of pairs to be printed.
Examples
FilesAndFilters.cpp.

Definition at line 153 of file persistence1d.hpp.

◆ PrintResults()

void p1d::Persistence1D::PrintResults ( const float  threshold = 0.0,
const bool  matlabIndexing = false 
) const
inline

Prints the global minimum and all paired extrema whose persistence is greater or equal to threshold.

By default, all pairs are printed. Supports Matlab indexing.

Parameters
[in]thresholdThreshold value for pair persistence.
[in]matlabIndexingUse Matlab indexing for printing.
Examples
FilesAndFilters.cpp.

Definition at line 172 of file persistence1d.hpp.

◆ RunPersistence()

bool p1d::Persistence1D::RunPersistence ( const std::vector< float > &  InputData)
inline

Call this function with a vector of one dimensional data to find extrema features in the data.

The function runs once for, results can be retrieved with different persistent thresholds without further data processing.

Input data vector is assumed to be of legal size and legal values.

Use PrintResults, GetPairedExtrema or GetExtremaIndices to get results of the function.

Parameters
[in]InputDataVector of data to find features on, ordered according to its axis.
Examples
FilesAndFilters.cpp, MatlabVisualization.cpp, MatplotlibVisualization.cpp, and SimpleDataVector.cpp.

Definition at line 128 of file persistence1d.hpp.

◆ SortPairedExtrema()

void p1d::Persistence1D::SortPairedExtrema ( )
inlineprotected

Sorts the PairedExtrema list according to the persistence of the features.

Orders features with equal persistence according the the index of their minima.

Definition at line 693 of file persistence1d.hpp.

◆ VerifyAliveComponents()

bool p1d::Persistence1D::VerifyAliveComponents ( )
inlineprotected

Runs at the end of RunPersistence, after Watershed.

Algorithm results should be as followed:

  • All but one components should not be Alive.
  • The Alive component contains the global minimum.
  • The Alive component should be the first component in the Component vector

Definition at line 722 of file persistence1d.hpp.

◆ VerifyResults()

bool p1d::Persistence1D::VerifyResults ( )
inline

Runs basic sanity checks on results of RunPersistence:

  • Number of unique minima = number of unique maxima - 1 (Morse property)
  • All returned indices are unique (no index is returned as two extrema)
  • Global minimum is within domain indices or at default value
  • Global minimum is not returned as any other extrema.
  • Global minimum is not paired.

Returns true if run results pass these sanity checks.

Examples
MatlabVisualization.cpp, and MatplotlibVisualization.cpp.

Definition at line 304 of file persistence1d.hpp.

◆ Watershed()

void p1d::Persistence1D::Watershed ( )
inlineprotected

Main algorithm - all of the work happen here.

Use only after calling CreateIndexValueVector and Init functions.

Iterates over each vertex in the graph according to their ordered values:

  • Creates a segment for each local minima
  • Extends a segment is data has only one neighboring component
  • Merges segments and creates new PairedExtrema when a vertex has two neighboring components.

Definition at line 612 of file persistence1d.hpp.

Member Data Documentation

◆ AliveComponentsVerified

bool p1d::Persistence1D::AliveComponentsVerified
protected

Definition at line 377 of file persistence1d.hpp.

◆ Colors

std::vector<int> p1d::Persistence1D::Colors
protected

Contains the Component assignment for each vertex in Data.

Only edges of destroyed components are updated to the new component color. The Component values in this vector are invalid at the end of the algorithm.

Definition at line 360 of file persistence1d.hpp.

◆ Components

std::vector<TComponent> p1d::Persistence1D::Components
protected

A vector of Components.

The component index within the vector is used as its Colors in the Watershed function.

Definition at line 367 of file persistence1d.hpp.

◆ Data

std::vector<float> p1d::Persistence1D::Data
protected

Contain a copy of the original input data.

Definition at line 346 of file persistence1d.hpp.

◆ PairedExtrema

std::vector<TPairedExtrema> p1d::Persistence1D::PairedExtrema
protected

A vector of paired extrema features - always a minimum and a maximum.

Definition at line 373 of file persistence1d.hpp.

◆ SortedData

std::vector<TIdxAndData> p1d::Persistence1D::SortedData
protected

Contains a copy the value and index pairs of Data, sorted according to the data values.

Definition at line 352 of file persistence1d.hpp.

◆ TotalComponents

unsigned int p1d::Persistence1D::TotalComponents
protected

Definition at line 376 of file persistence1d.hpp.


The documentation for this class was generated from the following file: