pcl::segmentation::grabcut::BoykovKolmogorov Class Reference — PointCloudLibrary

Реализация алгоритма максимального потока Бойкова и Колмогорова в boost не поддерживает отрицательные потоки, поэтому она не подходит для данного контекста. Подробнее...

#include <pcl/segmentation/grabcut_segmentation.h>

Открытые типы
using	vertex_descriptor = int
using	edge_capacity_type = double

Открытые функции-члены
	BoykovKolmogorov (std::size_t max_nodes=0)
	создать задачу максимального потока/минимального разреза с оценочным значением max_nodes Подробнее...
virtual	~BoykovKolmogorov ()=default
	деструктор Подробнее...
std::size_t	numNodes () const
	получить количество узлов в графе Подробнее...
void	reset ()
	сбросить пропускные способности всех рёбер до нуля (но не освобождать граф) Подробнее...
void	clear ()
	очистить граф и внутренние структуры данных Подробнее...
int	addNodes (std::size_t n=1)
	добавить узлы в граф (возвращает идентификатор первого добавленного узла) Подробнее...
void	addConstant (double c)
	добавить в граф постоянный поток Подробнее...
void	addSourceEdge (int u, double cap)
	добавить ребро от s к nodeId Подробнее...
void	addTargetEdge (int u, double cap)
	добавить ребро от nodeId к t Подробнее...
void	addEdge (int u, int v, double cap_uv, double cap_vu=0.0)
	добавить ребро от u к v и ребро от v к u (требуется, чтобы cap_uv + cap_vu >= 0) Подробнее...
double	solve ()
	решить задачу максимального потока и вернуть величину потока Подробнее...
bool	inSourceTree (int u) const
	возвращает true, если `u` входит в множество s после вызова solve. Подробнее...
bool	inSinkTree (int u) const
	возвращает true, если `u` входит в множество t после вызова solve Подробнее...
double	operator() (int u, int v) const
	возвращает остаточную пропускную способность ребра (для терминала используйте -1; (-1,-1) — это текущий поток Подробнее...
double	getSourceEdgeCapacity (int u) const
double	getTargetEdgeCapacity (int u) const

Защищённые типы
enum	nodestate { FREE = 0x00 , SOURCE = 0x01 , TARGET = 0x02 }
	состояния деревьев Подробнее...
using	capacitated_edge = std::map< int, double >
	ребро с пропускной способностью Подробнее...
using	edge_pair = std::pair< capacitated_edge::iterator, capacitated_edge::iterator >
	пара рёбер Подробнее...

Защищённые функции-члены
void	preAugmentPaths ()
	предварительно увеличить потоки по путям s-u-t и s-u-v-t Подробнее...
void	initializeTrees ()
	инициализировать деревья от источника и стока Подробнее...
std::pair< int, int >	expandTrees ()
	расширять деревья, пока не будет найден путь (или пока не выяснится, что пути нет (-1, -1)) Подробнее...
void	augmentPath (const std::pair< int, int > &path, std::deque< int > &orphans)
	увеличить поток по пути, найденному expandTrees; вернуть осиротевшие поддеревья Подробнее...
void	adoptOrphans (std::deque< int > &orphans)
	присоединить осиротевшие поддеревья Подробнее...
void	clearActive ()
	очистить активное множество Подробнее...
bool	isActiveSetEmpty () const
bool	isActive (int u) const
	активен, если головной или предыдущий узел не является терминалом Подробнее...
void	markActive (int u)
	пометить вершину как активную Подробнее...
void	markInactive (int u)
	пометить вершину как неактивную Подробнее...

Защищённые атрибуты
std::vector< double >	source_edges_
	рёбра, исходящие из источника Подробнее...
std::vector< double >	target_edges_
	рёбра, входящие в сток Подробнее...
std::vector< capacitated_edge >	nodes_
	узлы и исходящие из них внутренние рёбра Подробнее...
double	flow_value_ {0.0}
	текущее значение потока (включает константу) Подробнее...
std::vector< unsigned char >	cut_
	указывает, по какую сторону разреза находится узел Подробнее...

Подробное описание

Реализация алгоритма максимального потока Бойкова и Колмогорова в boost не поддерживает отрицательные потоки, поэтому она не подходит для данного контекста.

Однако реализация алгоритма максимального потока Бойкова и Колмогорова, созданная Stephen Gould в DARWIN под лицензией BSD, справляется с этой задачей, хотя работает медленнее исходной реализации. steph.nosp@m.en.g.nosp@m.ould@.nosp@m.anu..nosp@m.edu.a.nosp@m.u

Определение в строке 63 файла grabcut_segmentation.h.

Документация псевдонимов типов-членов

capacitated_edge

using pcl::segmentation::grabcut::BoykovKolmogorov::capacitated_edge = std::map<int, double>

protected

ребро с пропускной способностью

Определение в строке 121 файла grabcut_segmentation.h.

edge_capacity_type

using pcl::segmentation::grabcut::BoykovKolmogorov::edge_capacity_type = double

Определение в строке 67 файла grabcut_segmentation.h.

edge_pair

using pcl::segmentation::grabcut::BoykovKolmogorov::edge_pair = std::pair<capacitated_edge::iterator, capacitated_edge::iterator>

protected

пара рёбер

Определение в строке 123 файла grabcut_segmentation.h.

vertex_descriptor

using pcl::segmentation::grabcut::BoykovKolmogorov::vertex_descriptor = int

Определение в строке 66 файла grabcut_segmentation.h.

Документация перечисления-члена

nodestate

enum pcl::segmentation::grabcut::BoykovKolmogorov::nodestate

protected

состояния деревьев

Элемент перечисления
FREE
SOURCE
TARGET

Определение в строке 119 файла grabcut_segmentation.h.

Документация конструкторов и деструкторов

BoykovKolmogorov()

pcl::segmentation::grabcut::BoykovKolmogorov::BoykovKolmogorov ( std::size_t max_nodes = 0 )

создать задачу максимального потока/минимального разреза с оценочным значением max_nodes

~BoykovKolmogorov()

virtual pcl::segmentation::grabcut::BoykovKolmogorov::~BoykovKolmogorov ( )

virtualdefault

деструктор

Документация функций-членов

addConstant()

void pcl::segmentation::grabcut::BoykovKolmogorov::addConstant ( double c )

inline

добавить постоянный поток в граф

Определение в строке 87 файла grabcut_segmentation.h.

addEdge()

void pcl::segmentation::grabcut::BoykovKolmogorov::addEdge	(	int	u,
		int	v,
		double	cap_uv,
		double	cap_vu = `0.0`
	)

добавить ребро из u в v и ребро из v в u (требуется cap_uv + cap_vu >= 0)

addNodes()

int pcl::segmentation::grabcut::BoykovKolmogorov::addNodes ( std::size_t n = 1 )

добавить узлы в граф (возвращает идентификатор первого добавленного узла)

addSourceEdge()

void pcl::segmentation::grabcut::BoykovKolmogorov::addSourceEdge	(	int	u,
		double	cap
	)

добавить ребро от s к узлу nodeId

addTargetEdge()

void pcl::segmentation::grabcut::BoykovKolmogorov::addTargetEdge	(	int	u,
		double	cap
	)

добавить ребро от узла nodeId к t

adoptOrphans()

void pcl::segmentation::grabcut::BoykovKolmogorov::adoptOrphans ( std::deque< int > & orphans )

protected

присоединить осиротевшие поддеревья

augmentPath()

void pcl::segmentation::grabcut::BoykovKolmogorov::augmentPath	(	const std::pair< int, int > &	path,
		std::deque< int > &	orphans
	)

protected

увеличить поток по пути, найденному функцией expandTrees; вернуть осиротевшие поддеревья

clear()

void pcl::segmentation::grabcut::BoykovKolmogorov::clear ( )

очистить граф и внутренние структуры данных

clearActive()

void pcl::segmentation::grabcut::BoykovKolmogorov::clearActive ( )

protected

очистить множество активных узлов

expandTrees()

std::pair<int, int> pcl::segmentation::grabcut::BoykovKolmogorov::expandTrees ( )

protected

расширять деревья до нахождения пути (или отсутствия пути (-1, -1))

getSourceEdgeCapacity()

double pcl::segmentation::grabcut::BoykovKolmogorov::getSourceEdgeCapacity ( int u ) const

getTargetEdgeCapacity()

double pcl::segmentation::grabcut::BoykovKolmogorov::getTargetEdgeCapacity ( int u ) const

initializeTrees()

void pcl::segmentation::grabcut::BoykovKolmogorov::initializeTrees ( )

protected

инициализировать деревья от истока и стока

inSinkTree()

bool pcl::segmentation::grabcut::BoykovKolmogorov::inSinkTree ( int u ) const

inline

возвращает true, если u находится в t-множестве после вызова solve

Определение в строке 106 файла grabcut_segmentation.h.

inSourceTree()

bool pcl::segmentation::grabcut::BoykovKolmogorov::inSourceTree ( int u ) const

inline

возвращает true, если u находится в s-множестве после вызова solve.

Определение в строке 103 файла grabcut_segmentation.h.

Используется функцией pcl::GrabCut< PointT >::isSource().

isActive()

bool pcl::segmentation::grabcut::BoykovKolmogorov::isActive ( int u ) const

inlineprotected

активен, если головной или предыдущий узел не является терминальным

Определение в строке 146 файла grabcut_segmentation.h.

isActiveSetEmpty()

bool pcl::segmentation::grabcut::BoykovKolmogorov::isActiveSetEmpty ( ) const

inlineprotected

Возвращает: true, если множество активных узлов пусто

Определение в строке 143 файла grabcut_segmentation.h.

markActive()

void pcl::segmentation::grabcut::BoykovKolmogorov::markActive ( int u )

protected

пометить вершину как активную

markInactive()

void pcl::segmentation::grabcut::BoykovKolmogorov::markInactive ( int u )

protected

пометить вершину как неактивную

numNodes()

std::size_t pcl::segmentation::grabcut::BoykovKolmogorov::numNodes ( ) const

inline

получить количество узлов в графе

Определение в строке 75 файла grabcut_segmentation.h.

operator()()

double pcl::segmentation::grabcut::BoykovKolmogorov::operator()	(	int	u,
		int	v
	)		const

возвращает остаточную пропускную способность ребра (используйте -1 для терминала; (-1,-1) — текущий поток)

preAugmentPaths()

void pcl::segmentation::grabcut::BoykovKolmogorov::preAugmentPaths ( )

предварительно увеличить поток по путям s-u-t и s-u-v-t

reset()

void pcl::segmentation::grabcut::BoykovKolmogorov::reset ( )

сбросить пропускную способность всех рёбер до нуля (граф при этом не освобождается)

solve()

double pcl::segmentation::grabcut::BoykovKolmogorov::solve ( )

решить задачу о максимальном потоке и вернуть величину потока

Документация данных-членов

cut_

std::vector<unsigned char> pcl::segmentation::grabcut::BoykovKolmogorov::cut_

protected

определяет, к какой стороне разреза относится узел

Определение в строке 162 файла grabcut_segmentation.h.

flow_value_

double pcl::segmentation::grabcut::BoykovKolmogorov::flow_value_ {0.0}

protected

текущее значение потока (включая константу)

Определение в строке 160 файла grabcut_segmentation.h.

nodes_

std::vector<capacitated_edge> pcl::segmentation::grabcut::BoykovKolmogorov::nodes_

protected

узлы и исходящие из них внутренние рёбра

Определение в строке 158 файла grabcut_segmentation.h.

source_edges_

std::vector<double> pcl::segmentation::grabcut::BoykovKolmogorov::source_edges_

protected

рёбра, выходящие из истока

Определение в строке 154 файла grabcut_segmentation.h.

target_edges_

std::vector<double> pcl::segmentation::grabcut::BoykovKolmogorov::target_edges_

protected

рёбра, входящие в сток

Определение в строке 156 файла grabcut_segmentation.h.

Документация для этого класса создана на основе следующего файла:

pcl/segmentation/grabcut_segmentation.h

© 2009–2012, Willow Garage, Inc.
© 2012–, Open Perception, Inc.
Licensed under the BSD License.
https://pointclouds.org/documentation/classpcl_1_1segmentation_1_1grabcut_1_1_boykov_kolmogorov.html

Открытые типы

Открытые функции-члены

Защищённые типы

Защищённые функции-члены

Защищённые атрибуты

Подробное описание

Документация псевдонимов типов-членов

capacitated_edge

edge_capacity_type

edge_pair

vertex_descriptor

Документация перечисления-члена

nodestate

Документация конструкторов и деструкторов

BoykovKolmogorov()

~BoykovKolmogorov()

Документация функций-членов

addConstant()

addEdge()

addNodes()

addSourceEdge()

addTargetEdge()

adoptOrphans()

augmentPath()

clear()

clearActive()

expandTrees()

getSourceEdgeCapacity()

getTargetEdgeCapacity()

initializeTrees()

inSinkTree()

inSourceTree()

isActive()

isActiveSetEmpty()

markActive()

markInactive()

numNodes()

operator()()

preAugmentPaths()

reset()

solve()

Документация данных-членов

cut_

flow_value_

nodes_

source_edges_

target_edges_