qgar::ConnectedComponents Class Reference
[Connected components]

#include <qgarlib/ConnectedComponents.H>

List of all members.

Detailed Description

Connected components extracted from a binary image.

A (connected) component is a region defined by a set of connected pixels having the same color:

      b b b                    . w .
      b B b                    w W w
      b b b                    . w .

   8-connexity              4-connexity
    for BLACK                for WHITE

Black components are constructed using 8-connexity: When black, the central point ('B' on the figure) is connex to its 8 black neighbors marked 'b'.
White components are constructed using 4-connexity: When white, the central point ('W' on the figure) is connex to its 4 white neighbors marked w and is not connex to the 4 white neighbors marked '.'.

Each component is associated with a label, which is an integer number of type qgar::Component::label_type. See class qgar::Component for the way a component is represented.

                 _componentTree
                ________________
               |                |    0     j     k
+----------+   |      +--+      |   +--+--+--+--+--+- -+--+
|COMPONENT |<----------C0|<----------- |  |  |  |  |   |  |  _componentTab
|LABELLED 0|   |      +--+      |   +--+--+|-+--+|-+- -+--+
+----------+   |       /\       |          |     |
               |      /  \      |          |     |
+----------+   |  +--+    +--+  |          |     |
|COMPONENT |<------Ci|    |Cj|<------------+     |
|LABELLED i|   |  +--+    +--+  |                |
+----------+   |    |     /||\  |                |
+----------+   |  +--+          |                |
|COMPONENT |<------Ck|<--------------------------+
|LABELLED k|   |  +--+          |
+----------+   |________________|

The set of components is hierarchically organized as a tree, the so-called component tree (see functions qgar::ConnectedComponents::accessComponentTree and qgar::ConnectedComponents::componentTree). Each node represents a component (in fact, the data associated with the node is a pointer to the component, Ci in the figure above), and its children represent the components which are directly included into (i.e. has a common border with) the component.

The root of the tree is always a white component labelled 0. It represents the background of the given binary image, in which all the other components are (transitively) included.

To be sure to get a component representing the background, the first and last rows of the given binary image, as well as its first and last columns, are considered as being white.

The so-called component table (see functions qgar::ConnectedComponents::accessComponentTab and qgar::ConnectedComponents::componentTab). provides a direct access to the nodes representing the components, using their labels to index the table In other words, an element of this table is a pointer to the node of the tree representing the component having the same label as the table index of the element. Operator qgar::ConnectedComponents::operator[] gives a direct access to a component using its label.

The location of the components is given by the so-called component image (see qgar::ConnectedComponents::_componentImg): The value of a pixel is the label of the component to which the pixel belongs.

Todo:: Give the user the choice between implementing components as labelled regions in an image (like now) and implementing components through tables of runs and labels (presently, these tables are deleted once components are constructed)

Todo:: qgar::ConnectedComponents::PRIVATEcopyCC perfoms a deep copy of a tree. This method should be moved to class qgar::GenTree.

Author:: Gérald Masini

Date:: April 21, 2004 12:58

Since:: Qgar 2.1.1

Definition at line 160 of file ConnectedComponents.H.

Public Types

Types related to connected components

typedef GenImage< Component::label_type > image_type

Type of the pixels of the component image.

typedef image_type & reference

Reference to qgar::ConnectedComponents::image_type.

typedef const image_type & const_reference

Constant reference to qgar::ConnectedComponents::image_type.

typedef image_type * pointer

Pointer to qgar::ConnectedComponents::image_type.

typedef const image_type * const_pointer

Constant pointer to qgar::ConnectedComponents::image_type.

typedef GenTree< Component * > tree_type

Type of the component tree.

typedef GenTreeNode< Component * > node_type

Type of a node of the component tree.

Public Member Functions

Constructors

ConnectedComponents (const BinaryImage &aBinImg)

Construct from given binary image.

ConnectedComponents (const ConnectedComponents &aCC)

No default constructor provided. Copy constructor.

Destructor

~ConnectedComponents ()

Non-virtual destructor.

Access to the component image

const image_type & accessComponentImage () const

Get the component image.

image_type componentImage () const

Get a copy of the component image.

Access to the component tree

const tree_type & accessComponentTree () const

Get the component tree.

tree_type componentTree () const

Get a copy of the component tree.

node_type * pRoot () const

Get a pointer to the root of the component tree.

node_type * pNode (Component::label_type aLabel) const

Get a pointer to the node of the component tree representing the component of given label.

Access to components

int componentCnt () const

Get number of components.

const std::vector< node_type * > & accessComponentTab () const

Get the component table.

std::vector< node_type * > componentTab () const

Get a copy of the component table.

Component * pComponent (Component::label_type aLabel) const

Get a pointer to the component of given label.

Reconstruct a binary image from components

BinaryImage * makeBinaryImg (const std::vector< Component::label_type > &aLabSet)

Return a pointer to a binary image reconstructed from components corresponding to given labels.

Operators

ConnectedComponents & operator= (const ConnectedComponents &aCC)

Assignment.

Component & operator[] (Component::label_type aLabel)

Get component of given label.

const Component & operator[] (Component::label_type aLabel) const

Get component of given label (to be applied to a constant object).

Protected Attributes

Representation of the components

image_type _componentImg

Component image.

tree_type _componentTree

Tree of the components.

std::vector< node_type * > _componentTab

Table of the components.

Private Member Functions

Auxiliaries

void PRIVATEcopyCC (node_type *aPNodeIn, node_type *aPNodeOut)

Copy components stored in tree whose root is node in and store them in corresponding nodes of tree whose root is node out (in fact, the current component tree).

Member Typedef Documentation

typedef const image_type* qgar::ConnectedComponents::const_pointer

Constant pointer to qgar::ConnectedComponents::image_type.

Definition at line 194 of file ConnectedComponents.H.

typedef const image_type& qgar::ConnectedComponents::const_reference

Constant reference to qgar::ConnectedComponents::image_type.

Definition at line 184 of file ConnectedComponents.H.

typedef GenImage<Component::label_type> qgar::ConnectedComponents::image_type

Type of the pixels of the component image.

Definition at line 174 of file ConnectedComponents.H.

typedef GenTreeNode<Component*> qgar::ConnectedComponents::node_type

Type of a node of the component tree.

Definition at line 204 of file ConnectedComponents.H.

typedef image_type* qgar::ConnectedComponents::pointer

Pointer to qgar::ConnectedComponents::image_type.

Definition at line 189 of file ConnectedComponents.H.

typedef image_type& qgar::ConnectedComponents::reference

Reference to qgar::ConnectedComponents::image_type.

Definition at line 179 of file ConnectedComponents.H.

typedef GenTree<Component*> qgar::ConnectedComponents::tree_type

Type of the component tree.

Definition at line 199 of file ConnectedComponents.H.

Constructor & Destructor Documentation

qgar::ConnectedComponents::ConnectedComponents ( const BinaryImage & aBinImg )

Construct from given binary image.

Definition at line 64 of file ConnectedComponents.C.
References _componentImg, _componentTab, and _componentTree.

qgar::ConnectedComponents::ConnectedComponents ( const ConnectedComponents & aCC )

No default constructor provided. Copy constructor.

Parameters:

aCC connected components to be copied

Warning:
Perform a deep copy: The component image (including its pixel map), the component tree and all the components are duplicated.

Definition at line 84 of file ConnectedComponents.C.
References _componentTree, PRIVATEcopyCC(), and qgar::GenTree< T >::pRoot().

qgar::ConnectedComponents::~ConnectedComponents ( )

Non-virtual destructor.

Definition at line 107 of file ConnectedComponents.C.
References _componentTab.

Member Function Documentation

const ConnectedComponents::image_type & qgar::ConnectedComponents::accessComponentImage ( ) const [inline]

Get the component image.

Definition at line 492 of file ConnectedComponents.H.
References _componentImg.
Referenced by qgar::NiblackBinaryImage::NiblackBinaryImage(), and qgar::TTBinaryImage::TTBinaryImage().

const std::vector< ConnectedComponents::node_type * > & qgar::ConnectedComponents::accessComponentTab ( ) const [inline]

Get the component table.

Definition at line 564 of file ConnectedComponents.H.
References _componentTab.

const ConnectedComponents::tree_type & qgar::ConnectedComponents::accessComponentTree ( ) const [inline]

Get the component tree.

Definition at line 515 of file ConnectedComponents.H.
References _componentTree.

int qgar::ConnectedComponents::componentCnt ( ) const [inline]

Get number of components.

Definition at line 556 of file ConnectedComponents.H.
References _componentTab.
Referenced by qgar::NiblackBinaryImage::NiblackBinaryImage(), and qgar::TTBinaryImage::TTBinaryImage().

ConnectedComponents::image_type qgar::ConnectedComponents::componentImage ( ) const [inline]

Get a copy of the component image.

Definition at line 501 of file ConnectedComponents.H.
References _componentImg.

std::vector< ConnectedComponents::node_type * > qgar::ConnectedComponents::componentTab ( ) const [inline]

Get a copy of the component table.

Definition at line 572 of file ConnectedComponents.H.
References _componentTab.

ConnectedComponents::tree_type qgar::ConnectedComponents::componentTree ( ) const [inline]

Get a copy of the component tree.

Definition at line 523 of file ConnectedComponents.H.
References _componentTree.

BinaryImage * qgar::ConnectedComponents::makeBinaryImg ( const std::vector< Component::label_type > & aLabSet )

Return a pointer to a binary image reconstructed from components corresponding to given labels.

Parameters:

aLabSet a vector of component labels

A pixel of the resulting image is black (see qgar::QGEbw) if it belongs to a black component whose label is in the set of given labels. Otherwise, the pixel is white.

Warning:

Given labels out of the range of current labels are ignored.
The client is responsible for the deletion of the provided image.

Definition at line 135 of file ConnectedComponents.C.
References qgar::Component::_NO_LABEL, qgar::GenImage< T, CheckPolicy >::pPixMap(), qgar::QGE_BW_BLACK, and qgar::QGE_BW_WHITE.

ConnectedComponents & qgar::ConnectedComponents::operator= ( const ConnectedComponents & aCC )

Assignment.

Parameters:

aCC connected components to be assigned

Warning:
Perform a deep copy: The component image (including its pixel map), the component tree and all the components are duplicated.

Definition at line 199 of file ConnectedComponents.C.
References _componentImg, _componentTab, _componentTree, PRIVATEcopyCC(), and qgar::GenTree< T >::pRoot().

const Component & qgar::ConnectedComponents::operator[] ( Component::label_type aLabel ) const [inline]

Get component of given label (to be applied to a constant object).

Parameters:

aLabel a component label

Warning:
If the label is out of the range of current labels, the operator behavior is undefined.

Definition at line 603 of file ConnectedComponents.H.
References _componentTab.

Component & qgar::ConnectedComponents::operator[] ( Component::label_type aLabel ) [inline]

Get component of given label.

Parameters:

aLabel a component label

Warning:
If the label is out of the range of current labels, the operator behavior is undefined.

Definition at line 594 of file ConnectedComponents.H.
References _componentTab.

Component * qgar::ConnectedComponents::pComponent ( Component::label_type aLabel ) const [inline]

Get a pointer to the component of given label.

Parameters:

aLabel a component label

Warning:
If the label is out of the range of current labels, the function behavior is undefined.

Definition at line 580 of file ConnectedComponents.H.
References _componentTab.

ConnectedComponents::node_type * qgar::ConnectedComponents::pNode ( Component::label_type aLabel ) const [inline]

Get a pointer to the node of the component tree representing the component of given label.

Parameters:

aLabel a component label

Warning:
If the label is out of the range of current labels, the function behavior is undefined.

Definition at line 542 of file ConnectedComponents.H.
References _componentTab.

void qgar::ConnectedComponents::PRIVATEcopyCC ( node_type * aPNodeIn,

node_type * aPNodeOut

) [private]

Copy components stored in tree whose root is node in and store them in corresponding nodes of tree whose root is node out (in fact, the current component tree).
The component table of the current tree is subsequently updated.

Parameters:

aPNodeIn pointer to the root of the tree including component to be copied

aPNodeOut pointer to the root of the tree where to store copied components

Warning:
Both trees must have the same structure: The tree including node out (the current tree) is supposed to be a copy of the tree including node in.

Definition at line 234 of file ConnectedComponents.C.
References _componentTab, qgar::GenTreeNode< T >::data(), qgar::Component::label(), qgar::GenTreeNode< T >::pFirstChild(), qgar::GenTreeNode< T >::pRSibling(), and qgar::GenTreeNode< T >::setData().
Referenced by ConnectedComponents(), and operator=().

ConnectedComponents::node_type * qgar::ConnectedComponents::pRoot ( ) const [inline]

Get a pointer to the root of the component tree.

Definition at line 532 of file ConnectedComponents.H.
References _componentTree, and qgar::GenTree< T >::pRoot().

Member Data Documentation

image_type qgar::ConnectedComponents::_componentImg [protected]

Component image.
It gives the location of the components: The value of a pixel is the label of the component to which the pixel belongs.
Definition at line 415 of file ConnectedComponents.H.
Referenced by accessComponentImage(), componentImage(), ConnectedComponents(), and operator=().

std::vector<node_type*> qgar::ConnectedComponents::_componentTab [protected]

Table of the components.
Vector of pointers to the nodes (in the component tree) representing the components labelled by the corresponding indexes in the vector. In other words, _componentTab[i] points to the node representing the component labelled i.
Definition at line 436 of file ConnectedComponents.H.
Referenced by accessComponentTab(), componentCnt(), componentTab(), ConnectedComponents(), operator=(), operator[](), pComponent(), pNode(), PRIVATEcopyCC(), and ~ConnectedComponents().

tree_type qgar::ConnectedComponents::_componentTree [protected]

Tree of the components.
The root component is always labelled 0 and represents the (WHITE) background of the image. The children of a given component represent the components which are directly included in the given component, i.e. which have a common border with the given component.
Definition at line 426 of file ConnectedComponents.H.
Referenced by accessComponentTree(), componentTree(), ConnectedComponents(), operator=(), and pRoot().

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


Public Types
Types related to connected components
typedef GenImage< Component::label_type >	image_type
	Type of the pixels of the component image.
typedef image_type &	reference
	Reference to qgar::ConnectedComponents::image_type.
typedef const image_type &	const_reference
	Constant reference to qgar::ConnectedComponents::image_type.
typedef image_type *	pointer
	Pointer to qgar::ConnectedComponents::image_type.
typedef const image_type *	const_pointer
	Constant pointer to qgar::ConnectedComponents::image_type.
typedef GenTree< Component * >	tree_type
	Type of the component tree.
typedef GenTreeNode< Component * >	node_type
	Type of a node of the component tree.
Public Member Functions
Constructors
	ConnectedComponents (const BinaryImage &aBinImg)
	Construct from given binary image.
	ConnectedComponents (const ConnectedComponents &aCC)
	No default constructor provided. Copy constructor.
Destructor
	~ConnectedComponents ()
	Non-virtual destructor.
Access to the component image
const image_type &	accessComponentImage () const
	Get the component image.
image_type	componentImage () const
	Get a copy of the component image.
Access to the component tree
const tree_type &	accessComponentTree () const
	Get the component tree.
tree_type	componentTree () const
	Get a copy of the component tree.
node_type *	pRoot () const
	Get a pointer to the root of the component tree.
node_type *	pNode (Component::label_type aLabel) const
	Get a pointer to the node of the component tree representing the component of given label.
Access to components
int	componentCnt () const
	Get number of components.
const std::vector< node_type * > &	accessComponentTab () const
	Get the component table.
std::vector< node_type * >	componentTab () const
	Get a copy of the component table.
Component *	pComponent (Component::label_type aLabel) const
	Get a pointer to the component of given label.
Reconstruct a binary image from components
BinaryImage *	makeBinaryImg (const std::vector< Component::label_type > &aLabSet)
	Return a pointer to a binary image reconstructed from components corresponding to given labels.
Operators
ConnectedComponents &	operator= (const ConnectedComponents &aCC)
	Assignment.
Component &	operator[] (Component::label_type aLabel)
	Get component of given label.
const Component &	operator[] (Component::label_type aLabel) const
	Get component of given label (to be applied to a constant object).
Protected Attributes
Representation of the components
image_type	_componentImg
	Component image.
tree_type	_componentTree
	Tree of the components.
std::vector< node_type * >	_componentTab
	Table of the components.
Private Member Functions
Auxiliaries
void	PRIVATEcopyCC (node_type aPNodeIn, node_type aPNodeOut)
	Copy components stored in tree whose root is node in and store them in corresponding nodes of tree whose root is node out (in fact, the current component tree).

qgar::ConnectedComponents Class Reference [Connected components]

Detailed Description

Public Types

Public Member Functions

Protected Attributes

Private Member Functions

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

qgar::ConnectedComponents Class Reference
[Connected components]