Extracts the topology from a segmentation label image. More...

#include <vtol_extract_topology.h>

Classes
struct	chain_tree_node
struct	LabelPoint
	Queries into label_img_ return either (label, true) or (0, false). More...
Public Types
typedef vtol_extract_topology_region_type	region_type
	alias for the region type.
typedef vbl_smart_ptr < region_type >	region_type_sptr
typedef vil_image_view < LABEL_TYPE >	label_image_type
	Input label image type.
typedef vil_region_finder < LABEL_TYPE >	finder_type
typedef vtol_extract_topology_data_image_type	data_image_type
	Input data image type.
Public Member Functions
	vtol_extract_topology (label_image_type const &image, vtol_extract_topology_params const &params=vtol_extract_topology_params())
	Prepare to extract the topology from image.
vcl_vector< vtol_vertex_2d_sptr >	vertices () const
	List of vertices in the segmentation.
vcl_vector < vtol_intensity_face_sptr >	faces () const
	List of all the faces in the segmentation.
vcl_vector < vtol_intensity_face_sptr >	faces (data_image_type const &data_img) const
	List of all the faces in the segmentation.
void	add_faces (vcl_vector< vtol_intensity_face_sptr > &faces, finder_type find, data_image_type const img, chain_tree_node *node, bool even_level=false) const
vdgl_edgel_chain_sptr	smooth_chain (vdgl_edgel_chain_sptr chain, unsigned int num_pts) const
Static Public Member Functions
static bool	contains (region_type_sptr a, region_type_sptr b)
static unsigned	num_crosses_x_pos_ray (double x, double y, vdgl_edgel_chain const &chain)
Private Types
typedef vtol_extract_topology_edgel_chain	edgel_chain
typedef vbl_smart_ptr < edgel_chain >	edgel_chain_sptr
typedef vil_image_view< unsigned >	index_image_type
	Image of indices into the vertex node list.
typedef vcl_vector< vcl_vector < region_type_sptr > >	region_collection
Private Member Functions
void	compute_label_range ()
	Determine the max and min labels in the label image.
LabelPoint	label (unsigned i, unsigned j) const
	The label at pixel position (i,j).
bool	is_junction_vertex (unsigned i, unsigned j) const
	Is this a vertex bordering at least three regions?.
bool	is_boundary_vertex (unsigned i, unsigned j) const
	Is this a non-interior vertex?.
bool	is_edge (unsigned i, unsigned j, unsigned dir) const
	True iff there is an edge from vertex (i,j) in direction dir.
void	edge_labels (unsigned i, unsigned j, unsigned dir, LabelPoint &left, LabelPoint &right) const
	The labels of the pixels on either side of the edge.
unsigned	vertex_index (unsigned i, unsigned j) const
	The node index of the vertex at coordinate (i,j).
void	set_vertex_index (unsigned i, unsigned j, unsigned index)
	Marks vertex (i,j) as having the given index.
vtol_extract_topology_vertex_node &	node (unsigned index)
	The vertex node structure given by index.
vtol_extract_topology_vertex_node const &	node (unsigned index) const
	The vertex node structure given by index.
void	move (unsigned dir, unsigned &i, unsigned &j)
	Move ( i, j ) in direction dir.
void	set_mark (unsigned &marker, unsigned dir) const
	Mark direction dir as travelled.
bool	is_marked (unsigned marker, unsigned dir) const
	Check if a direction has been travelled.
void	trace_edge_chain (unsigned i, unsigned j, unsigned dir)
	Add an edge chain into the graph structure.
void	construct_topology ()
	This will create the full graph structure of the vertices.
bool	trace_face_boundary (vcl_vector< unsigned > &markers, unsigned index, unsigned dir, region_type &chain, LabelPoint &region_label) const
	Trace the boundary of a region starting at vertex index going dir.
void	collect_regions (region_collection &out_region_list) const
	Trace the boundary curves and collect up a set of regions.
void	compute_faces (vcl_vector< region_type_sptr > const &chains, vcl_vector< vtol_intensity_face_sptr > &faces, data_image_type const *data_img) const
	Create a set of faces given a set of boundary chains.
Private Attributes
label_image_type const &	label_img_
	The input label image.
vtol_extract_topology_params	params_
	Parameters.
LABEL_TYPE	min_label_
	The label ranges in the image.
LABEL_TYPE	max_label_
vcl_vector < vtol_extract_topology_vertex_node >	node_list_
	List of vertices (which form the nodes of the graph).
index_image_type	index_img_
	Quick conversion from vertex coordinates to vertex node indices.
Friends
struct	vtol_extract_topology_vertex_node
class	test_vtol_extract_topology

Detailed Description

template<typename LABEL_TYPE>
class vtol_extract_topology< LABEL_TYPE >

Extracts the topology from a segmentation label image.

This class contains the functionality to extract a set of regions from an image of region labels. Vertices are created only at junctions where possible. The edges connecting these vertices follow the boundary of the regions, and hence are often not straight lines.

Vertices are formed at the corners of pixels, and edges are formed along the "cracks" between pixels. In this implementation, the vertices are indexed by the top-left corner of the pixel. That is, if the image has M x N pixels, it will have M+1 x N+1 vertices, indexed (0,0) to (M,N). A vertex (i,j) is positioned at (i-0.5,j-0.5) in pixel coordinates.

Now templated; LABEL_TYPE can be vxl_byte, vxl_uint_16, etc.

Definition at line 188 of file vtol_extract_topology.h.

Member Typedef Documentation

template<typename LABEL_TYPE >

typedef vtol_extract_topology_data_image_type vtol_extract_topology< LABEL_TYPE >::data_image_type

Input data image type.

Definition at line 201 of file vtol_extract_topology.h.

template<typename LABEL_TYPE >

typedef vtol_extract_topology_edgel_chain vtol_extract_topology< LABEL_TYPE >::edgel_chain [private]

Definition at line 417 of file vtol_extract_topology.h.

template<typename LABEL_TYPE >

typedef vbl_smart_ptr< edgel_chain > vtol_extract_topology< LABEL_TYPE >::edgel_chain_sptr [private]

Definition at line 418 of file vtol_extract_topology.h.

template<typename LABEL_TYPE >

typedef vil_region_finder< LABEL_TYPE > vtol_extract_topology< LABEL_TYPE >::finder_type

Definition at line 198 of file vtol_extract_topology.h.

template<typename LABEL_TYPE >

typedef vil_image_view< unsigned > vtol_extract_topology< LABEL_TYPE >::index_image_type [private]

Image of indices into the vertex node list.

Definition at line 421 of file vtol_extract_topology.h.

template<typename LABEL_TYPE >

typedef vil_image_view< LABEL_TYPE > vtol_extract_topology< LABEL_TYPE >::label_image_type

Input label image type.

Definition at line 197 of file vtol_extract_topology.h.

template<typename LABEL_TYPE >

typedef vcl_vector< vcl_vector< region_type_sptr > > vtol_extract_topology< LABEL_TYPE >::region_collection [private]

Definition at line 555 of file vtol_extract_topology.h.

template<typename LABEL_TYPE >

typedef vtol_extract_topology_region_type vtol_extract_topology< LABEL_TYPE >::region_type

alias for the region type.

Definition at line 193 of file vtol_extract_topology.h.

template<typename LABEL_TYPE >

typedef vbl_smart_ptr< region_type > vtol_extract_topology< LABEL_TYPE >::region_type_sptr

Definition at line 194 of file vtol_extract_topology.h.

Constructor & Destructor Documentation

template<typename T >

vtol_extract_topology< T >::vtol_extract_topology	(	label_image_type const &	image,
		vtol_extract_topology_params const &	params = `vtol_extract_topology_params()`
	)

Prepare to extract the topology from image.

Definition at line 59 of file vtol_extract_topology.txx.

Member Function Documentation

template<typename LABEL_TYPE >

void vtol_extract_topology< T >::add_faces	(	vcl_vector< vtol_intensity_face_sptr > &	faces,
		finder_type *	find,
		data_image_type const *	img,
		chain_tree_node *	node,
		bool	even_level = `false`
	)		const

Definition at line 782 of file vtol_extract_topology.txx.

template<typename LABEL_TYPE >

void vtol_extract_topology< LABEL_TYPE >::collect_regions ( region_collection & out_region_list ) const [private]

Trace the boundary curves and collect up a set of regions.

The output in out_region_list is a set of regions indexed by the label of the region. So, out_region_list[x] will be a set of closed boundaries bounding regions with label x.

Definition at line 697 of file vtol_extract_topology.txx.

template<typename T >

void vtol_extract_topology< T >::compute_faces	(	vcl_vector< region_type_sptr > const &	chains,
		vcl_vector< vtol_intensity_face_sptr > &	faces,
		data_image_type const *	data_img
	)		const `[private]`

Create a set of faces given a set of boundary chains.

The boundary chains must all bound regions with the same label. This routine will determine which chains should be interior boundaries and which should be exterior. It will add a set of faces to faces based on this determination.

Each face so added will form a single connected component.

If data_img is not null, each face will have a digital region (vdgl_digital_region).

Definition at line 748 of file vtol_extract_topology.txx.

template<typename T >

void vtol_extract_topology< T >::compute_label_range ( ) [private]

Determine the max and min labels in the label image.

Definition at line 143 of file vtol_extract_topology.txx.

template<typename T >

void vtol_extract_topology< T >::construct_topology ( ) [private]

This will create the full graph structure of the vertices.

It will find all the vertices and connecting edges necessary to describe the topology of the segmentation. It will try to create as few vertices as possible to do so.

Definition at line 491 of file vtol_extract_topology.txx.

template<typename T >

bool vtol_extract_topology< T >::contains	(	region_type_sptr	a,
		region_type_sptr	b
	)		`[static]`

Definition at line 803 of file vtol_extract_topology.txx.

template<typename LABEL_TYPE >

void vtol_extract_topology< LABEL_TYPE >::edge_labels	(	unsigned	i,
		unsigned	j,
		unsigned	dir,
		LabelPoint &	left,
		LabelPoint &	right
	)		const `[private]`

The labels of the pixels on either side of the edge.

Left and right correspond to the displayed image. That is, left and right are defined on a left-handed coordinate system.

Definition at line 241 of file vtol_extract_topology.txx.

template<typename T >

vcl_vector< vtol_intensity_face_sptr > vtol_extract_topology< T >::faces ( ) const

List of all the faces in the segmentation.

These will be intensity faces without a digital region. This function should probably return vtol_face_2d objects, not vtol_intensity_face objects.

Definition at line 118 of file vtol_extract_topology.txx.

template<typename T >

vcl_vector< vtol_intensity_face_sptr > vtol_extract_topology< T >::faces ( data_image_type const & data_img ) const

List of all the faces in the segmentation.

The faces will have digital regions formed using data_img. data_img must have the same size as the label image.

Definition at line 96 of file vtol_extract_topology.txx.

template<typename LABEL_TYPE >

bool vtol_extract_topology< LABEL_TYPE >::is_boundary_vertex	(	unsigned	i,
		unsigned	j
	)		const `[private]`

Is this a non-interior vertex?.

Definition at line 205 of file vtol_extract_topology.txx.

template<typename LABEL_TYPE >

bool vtol_extract_topology< LABEL_TYPE >::is_edge	(	unsigned	i,
		unsigned	j,
		unsigned	dir
	)		const `[private]`

True iff there is an edge from vertex (i,j) in direction dir.

The directions are

               3
  
               ^
               |
               |
      2 <--- (i,j) ---> 0           +----->
               |                    |       i
               |                    |
               v                    v
                                      j
               1

The `crack' between two pixels forms an edge iff the pixels have different labels.

Definition at line 225 of file vtol_extract_topology.txx.

template<typename T >

bool vtol_extract_topology< T >::is_junction_vertex	(	unsigned	i,
		unsigned	j
	)		const `[private]`

Is this a vertex bordering at least three regions?.

Definition at line 184 of file vtol_extract_topology.txx.

template<typename T >

bool vtol_extract_topology< T >::is_marked	(	unsigned	marker,
		unsigned	dir
	)		const `[private]`

Check if a direction has been travelled.

The directions that have been travelled is extracted from marker.

Definition at line 366 of file vtol_extract_topology.txx.

template<typename LABEL_TYPE >

vtol_extract_topology< LABEL_TYPE >::LabelPoint vtol_extract_topology< LABEL_TYPE >::label	(	unsigned	i,
		unsigned	j
	)		const `[private]`

The label at pixel position (i,j).

If (i,j) falls inside the input image, return the value of pixel (i,j) of the input image. Otherwise, it will return min_label_ - 1.

Definition at line 167 of file vtol_extract_topology.txx.

template<typename T >

void vtol_extract_topology< T >::move	(	unsigned	dir,
		unsigned &	i,
		unsigned &	j
	)		`[private]`

Move ( i, j ) in direction dir.

Definition at line 325 of file vtol_extract_topology.txx.

template<typename T >

vtol_extract_topology_vertex_node & vtol_extract_topology< T >::node ( unsigned index ) [private]

The vertex node structure given by index.

Definition at line 300 of file vtol_extract_topology.txx.

template<typename T >

vtol_extract_topology_vertex_node const & vtol_extract_topology< T >::node ( unsigned index ) const [private]

The vertex node structure given by index.

Definition at line 311 of file vtol_extract_topology.txx.

template<typename T >

unsigned vtol_extract_topology< T >::num_crosses_x_pos_ray	(	double	x,
		double	y,
		vdgl_edgel_chain const &	chain
	)		`[static]`

Definition at line 827 of file vtol_extract_topology.txx.

template<typename T >

void vtol_extract_topology< T >::set_mark	(	unsigned &	marker,
		unsigned	dir
	)		const `[private]`

Mark direction dir as travelled.

marker is updated to reflect the new movement.

Definition at line 354 of file vtol_extract_topology.txx.

template<typename T >

void vtol_extract_topology< T >::set_vertex_index	(	unsigned	i,
		unsigned	j,
		unsigned	index
	)		`[private]`

Marks vertex (i,j) as having the given index.

Definition at line 285 of file vtol_extract_topology.txx.

template<typename T >

vdgl_edgel_chain_sptr vtol_extract_topology< T >::smooth_chain	(	vdgl_edgel_chain_sptr	chain,
		unsigned int	num_pts
	)		const

Definition at line 861 of file vtol_extract_topology.txx.

template<typename T >

void vtol_extract_topology< T >::trace_edge_chain	(	unsigned	i,
		unsigned	j,
		unsigned	dir
	)		`[private]`

Add an edge chain into the graph structure.

This will trace the edgel chain starting at the vertex at (i,j), starting in direction dir. It will update the graph nodes to reflect the new chain.

Definition at line 378 of file vtol_extract_topology.txx.

template<typename LABEL_TYPE >

bool vtol_extract_topology< LABEL_TYPE >::trace_face_boundary	(	vcl_vector< unsigned > &	markers,
		unsigned	index,
		unsigned	dir,
		region_type &	chain,
		LabelPoint &	region_label
	)		const `[private]`

Trace the boundary of a region starting at vertex index going dir.

It will output, in chain, the one chain of edges corresponding to the closed contour bounding a region. It will also return the label of the enclosed region.

It will only trace regions interior to the image. That is, it will not trace a "face" containing the region outside the image boundaries. The return value will indicate this. A return value of "true" indicates that the a region was successfully extracted, and that chain_list and region_label are valid. A return value of "false" indicates that a region was not traced.

Definition at line 600 of file vtol_extract_topology.txx.

template<typename T >

unsigned vtol_extract_topology< T >::vertex_index	(	unsigned	i,
		unsigned	j
	)		const `[private]`

The node index of the vertex at coordinate (i,j).

Definition at line 270 of file vtol_extract_topology.txx.

template<typename T >

vcl_vector< vtol_vertex_2d_sptr > vtol_extract_topology< T >::vertices ( ) const

List of vertices in the segmentation.

Definition at line 75 of file vtol_extract_topology.txx.

Friends And Related Function Documentation

template<typename LABEL_TYPE >

friend class test_vtol_extract_topology [friend]

Definition at line 429 of file vtol_extract_topology.h.

template<typename LABEL_TYPE >

friend struct vtol_extract_topology_vertex_node [friend]

Definition at line 424 of file vtol_extract_topology.h.

Member Data Documentation

template<typename LABEL_TYPE >

index_image_type vtol_extract_topology< LABEL_TYPE >::index_img_ [private]

Quick conversion from vertex coordinates to vertex node indices.

Definition at line 598 of file vtol_extract_topology.h.

template<typename LABEL_TYPE >

label_image_type const& vtol_extract_topology< LABEL_TYPE >::label_img_ [private]

The input label image.

Definition at line 586 of file vtol_extract_topology.h.

template<typename LABEL_TYPE >

LABEL_TYPE vtol_extract_topology< LABEL_TYPE >::max_label_ [private]

Definition at line 592 of file vtol_extract_topology.h.

template<typename LABEL_TYPE >

LABEL_TYPE vtol_extract_topology< LABEL_TYPE >::min_label_ [private]

The label ranges in the image.

Definition at line 592 of file vtol_extract_topology.h.

template<typename LABEL_TYPE >

vcl_vector< vtol_extract_topology_vertex_node > vtol_extract_topology< LABEL_TYPE >::node_list_ [private]

List of vertices (which form the nodes of the graph).

Definition at line 595 of file vtol_extract_topology.h.

template<typename LABEL_TYPE >

vtol_extract_topology_params vtol_extract_topology< LABEL_TYPE >::params_ [private]

Parameters.

Definition at line 589 of file vtol_extract_topology.h.

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

contrib/gel/vtol/algo/vtol_extract_topology.h
contrib/gel/vtol/algo/vtol_extract_topology.txx

Classes

Public Types

Public Member Functions

Static Public Member Functions

Private Types

Private Member Functions

Private Attributes

Friends

Detailed Description

template<typename LABEL_TYPE> class vtol_extract_topology< LABEL_TYPE >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation

template<typename LABEL_TYPE>
class vtol_extract_topology< LABEL_TYPE >