qgar::ConnectedComponentsImpl Class Reference
[Connected components]

#include <ConnectedComponentsImpl.H>

List of all members.

Detailed Description

Implementation of the construction of connected components of a binary image.

ConnectedComponentsImpl.H "qgarlib/ConnectedComponentsImpl.H"

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

      B B B                    w W w
      B * B                    W * W
      B B B                    w W w

   8-connexity              4-connexity
    for BLACK                for WHITE

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

See class qgar::Component for the way a component is represented.

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

Each component is associated with a label (a number of type qgar::Component::label_type).

The set of components is hierarchically organized as a tree, the so-called component tree (given by argument aRCompTree of function qgar::ConnectedComponentsImpl::run). Each node represents a component (in fact, the data associated with the node is a pointer to the component, Ci on 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 initial 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 (given by argument aRCompTab of function qgar::ConnectedComponentsImpl::run) 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 element index.

The location of the components is given by the so-called component image (given by argument aRCompImg of function qgar::ConnectedComponentsImpl::ConnectedComponentsImpl): The value of a pixel is the label of the component to which the pixel belongs.

Warning:

      B B B                    w W w
      B * B                    W * W
      B B B                    w W w

   8-connexity              4-connexity
    for BLACK                for WHITE

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

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 (these tables are presently deleted once components are constructed)

Author:: Gérald Masini

Date:: May 28, 2004 15:41

Since:: Qgar 2.1.1

Definition at line 181 of file ConnectedComponentsImpl.H.

Public Member Functions

Constructors

ConnectedComponentsImpl (const BinaryImage &aBinImg, ConnectedComponents::image_type *aPCompImg, ConnectedComponents::tree_type &aRCompTree, std::vector< ConnectedComponents::node_type * > &aRCompTab)

Initialize data in order to run the construction of components.

Destructor

~ConnectedComponentsImpl ()

Non-virtual destructor.

Construction of connected components

void run () throw (QgarErrorAlgorithm)

Run the construction of connected components.

Protected Attributes

(I) The initial binary image

int _width

Width of the initial binary image (and of the component image).

int _height

Height of the initial binary image (and of the component image).

int _colEndIdx

Index of the last column of the initial binary image (and of the component image).

int _rowEndIdx

Index of the last row of the initial binary image (and of the component image).

(II) Runs in the given binary image

For each row (of the given image), whose index is _rowIdx:

0 1 2 3 4 5 6 7 8 9 <- column numbers row #_rowIdx +-+-+-+-+-+-+-+-+-+-+ of the given image |b|w|b|b|b|w|w|b|b|b| <- pixels +-+-+-+-+-+-+-+-+-+-+ ^ ^ |_ considered _| as WHITE 0 1 2 3 4 <- run numbers +--+--+--+--+--+ _runRowsTab[_rowIdx] |2 |3 |2 |2 |1 | <- run lengths +--+--+--+--+--+ +--+--+--+--+--+ _labelRowsTab[_rowIdx] |L0|L1|L2|L3|L4| <- run labels +--+--+--+--+--+ => Even indexes in a run/label row correspond to <b>white</b> runs Odd indexes in a run/label row correspond to <b>black</b> runs

The run row, stored in runRowsTab[_rowIdx], gives the lengths of the runs of same-colored consecutive pixels in the row. First and last rows are considered as completely white. First and last pixels of a given row are considered as white.

The label row, stored in _labelRowsTab[_rowIdx], gives the labels of the corresponding runs: _labelRowsTab[_rowIdx][rdx] gives the label of the run whose length is runRowsTab[_rowIdx][rdx].

std::vector< std::vector<
int > > _runRowsTab

Table of run rows: 1 run row for each row of the given binary image.

std::vector< std::vector<
Component::label_type > > _labelRowsTab

Table of label rows: 1 label row for each row of the given binary image.

bool _moreCurrentRuns

True while all runs in a row are not processed.

(III) Previous row of the given binary image

int _prevRowIdx

Index of the previous row in the given image, and in the tables of run/label rows.

int _prevRunIdx

Considering the current run in the (previous) row, index of this run in the run/label row.

int _prevRunCnt

Considering the current run in the (previous) row, number of runs (starting from 0) in the run row.

Component::label_type _prevLabel

Considering the current run in the (previous) row, label number of this run.

QGEbw _prevColor

Considering the current run in the (previous) row, color of this run.

int _prevRunBeginX

Considering the current run in the (previous) row, index (in image row) of the beginning of this run.

int _prevRunEndX

Considering the current run in the (previous) row, index (in image row) of the end of this run.

(IV) Current row of the given binary image

BinaryImage::value_type * _ptRow

Pointer to the current row in the pixel map of the given binary image.

BinaryImage::value_type * _ptRowEnd

Pointer to the end of the current row in the pixel map of the given binary image.

int _rowIdx

Index of the current row in the given binary image, and in the tables of run/label rows.

int _currRunIdx

Considering the current run in the (current) row, index of this run in the run/label row.

Component::label_type _currLabel

Considering the current run in the (current) row, label number of this run.

QGEbw _currColor

Considering the current run in the (current) row, color of this run.

int _currRunBeginX

Considering the current run in the (current) row, index (in image row) of the beginning of this run.

int _currRunEndX

Considering the current run in the (current) row, index (in image row) of the end of the run.

(V) Labels

Each created component is associated with a label, that is used as an index to store/access information about the component in the different tables representing the components (see section VI about component features).

Component::label_type _labelCnt

Current label count.

std::vector< Component::label_type > _equivLabelTab

Table of equivalent labels.

std::vector< Component::label_type > _finalLabelTab

Table giving the final label numbering.

Component::label_type _finalLabelCnt

Final label count.

std::list< int > _validCompIdxList

List recording the indexes of valid components in the table of equivalent labels, _equivLabelTab (see above).

(VI) Tables to store component features

The component in which a given component is directly included (i.e. has a common border) is called the comprising component.

0 1 2 3 4... <- component labels (<= _labelCnt) +--+--+--+--+--+- --+ C |i0|i1|i2|i3|i4| _inLabel : label of the comprising component | O +--+--+--+--+--+- | M |c0|c1|c2|c3|c4| _color : color | P +--+--+--+--+--+- | O |p0|p1|p2|p3|p4| _xTopLeftPix : X of top left pixel | N +--+--+--+--+--+- | E |P0|P1|P2|P3|P4| _yTopLeftPix : Y of top left pixel | N +--+--+--+--+--+- | T |t0|t1|t2|t3|t4| _xTopLeft : X of top left corner > +--+--+--+--+--+- | |T0|T1|T2|T3|T4| _yTopLeft : Y of top left corner | F +--+--+--+--+--+- | E |b0|b1|b2|b3|b4| _xBottomRight: X of bottom right corner | A +--+--+--+--+--+- | T |B0|B1|B2|B3|B4| _yBottomRight: Y of bottom right corner | U +--+--+--+--+--+- | R |a0|a1|a2|a3|a4| _areaPixels : area | E +--+--+--+--+--+- --+ S
For component labelled Li, _inLabel[Li] gives the label of its comprising component, color[Li] gives its color, etc.

std::vector< Component::label_type > _inLabel

Label of the comprising component of each component.

std::vector< QGEbw > _color

Color of each component.

std::vector< int > _xTopLeftPix

X coordinate of the top left pixel of each component.

std::vector< int > _yTopLeftPix

Y coordinate of the top left pixel of each component.

std::vector< int > _xTopLeft

X coordinate of the top left corner of the bounding box of each component.

std::vector< int > _yTopLeft

Y coordinate of the top left corner of the bounding box of each component.

std::vector< int > _xBottomRight

X coordinate of the bottom right corner of the bounding box of each component.

std::vector< int > _yBottomRight

Y coordinate of the bottom right corner of the bounding box of each component.

std::vector< int > _areaPixels

Area (in pixels) of each component.

(VII) The connected components

ConnectedComponents::image_type * _pCompImg

Pointer to the component image.

Component::label_type * _pMapCCImg

Pointer to the pixel map of the component image.

ConnectedComponents::tree_type & _rCompTree

Reference to the component tree.

std::vector< ConnectedComponents::node_type * > & _rCompTab

Reference to the component table.

Private Member Functions

Functions working on labels

int validLabel (Component::label_type aLabel)

Get the valid label of (i.e. equivalent to) a given label.

Functions working on components

void mergePrevAndCurrComponents ()

merge component including previous run and component including current run.

Functions working on runs

void nextPrevRun ()

Move to next run in previous row (see section (III) about previous row).

void nextCurrRun ()

Move to next run in current row (see section (IV) about current row).

void prevAndCurrRunsCoincide ()

Perform moves according to black- and white-connexity when end of previous run and end of current run coincide.

Functions working on the component tree

void constructComponentTree (ConnectedComponents::tree_type &aTree, ConnectedComponents::node_type *aPNode, std::vector< ConnectedComponents::node_type * > &aCCTab)

Construction the component tree.

Constructor & Destructor Documentation

qgar::ConnectedComponentsImpl::ConnectedComponentsImpl ( const BinaryImage & aBinImg,

ConnectedComponents::image_type * aPCompImg,

ConnectedComponents::tree_type & aRCompTree,

std::vector< ConnectedComponents::node_type * > & aRCompTab

)

Initialize data in order to run the construction of components.

Parameters:

aBinImg binary image from which components are extracted

aPCompImg pointer to component image

aRCompTree reference to the component tree (see class qgar::ConnectedComponents)

aRCompTab reference to the component table (see class qgar::ConnectedComponents)

Definition at line 70 of file ConnectedComponentsImpl.C.

qgar::ConnectedComponentsImpl::~ConnectedComponentsImpl ( )

Non-virtual destructor.

Definition at line 642 of file ConnectedComponentsImpl.C.

Member Function Documentation

void qgar::ConnectedComponentsImpl::constructComponentTree ( ConnectedComponents::tree_type & aTree,

ConnectedComponents::node_type * aPNode,

std::vector< ConnectedComponents::node_type * > & aCCTab

) [private]

Construction the component tree.

Parameters:

aTree reference to the tree being constructed

aPNode pointer to a node representing a component which has not yet children

aCCTab reference to the table of pointers to nodes representing components: aCCTab[lab] gives a pointer to the node representing the component labelled lab (lab is a valid label)

Definition at line 1022 of file ConnectedComponentsImpl.C.
References qgar::GenTreeNode< T >::pRSibling().
Referenced by run().

void qgar::ConnectedComponentsImpl::mergePrevAndCurrComponents ( ) [private]

merge component including previous run and component including current run.

Warning:
By construction, component with the greatest label must be merged into component with the smallest label.

Definition at line 687 of file ConnectedComponentsImpl.C.
References _areaPixels, _currLabel, _currRunBeginX, _currRunEndX, _equivLabelTab, _labelRowsTab, qgar::Component::_NO_LABEL, _prevLabel, _rowIdx, _runRowsTab, _xBottomRight, _xTopLeft, _xTopLeftPix, _yBottomRight, _yTopLeft, _yTopLeftPix, and validLabel().
Referenced by run().

void qgar::ConnectedComponentsImpl::nextCurrRun ( ) [private]

Move to next run in current row (see section (IV) about current row).

Definition at line 866 of file ConnectedComponentsImpl.C.
References _currColor, _currLabel, _currRunBeginX, _currRunEndX, _currRunIdx, qgar::Component::_NO_LABEL, _ptRow, _ptRowEnd, qgar::qgBWswitch(), and qgar::QGE_BW_WHITE.
Referenced by prevAndCurrRunsCoincide(), and run().

void qgar::ConnectedComponentsImpl::nextPrevRun ( ) [private]

Move to next run in previous row (see section (III) about previous row).

Definition at line 846 of file ConnectedComponentsImpl.C.
References _labelRowsTab, _prevColor, _prevLabel, _prevRowIdx, _prevRunBeginX, _prevRunEndX, _prevRunIdx, _runRowsTab, and qgar::qgBWswitch().
Referenced by prevAndCurrRunsCoincide(), and run().

void qgar::ConnectedComponentsImpl::prevAndCurrRunsCoincide ( ) [private]

Perform moves according to black- and white-connexity when end of previous run and end of current run coincide.

Warning:
End of current row must be tested before calling this function.

Definition at line 929 of file ConnectedComponentsImpl.C.
References _currColor, _prevColor, nextCurrRun(), nextPrevRun(), and qgar::QGE_BW_WHITE.
Referenced by run().

void qgar::ConnectedComponentsImpl::run ( ) throw (QgarErrorAlgorithm)

Run the construction of connected components.

Exceptions:

qgar::QgarErrorAlgorithm (maximum label exceeded)

Definition at line 107 of file ConnectedComponentsImpl.C.
References _areaPixels, _colEndIdx, _color, _currColor, _currLabel, _currRunBeginX, _currRunEndX, _currRunIdx, _equivLabelTab, _finalLabelCnt, _finalLabelTab, _height, _inLabel, _labelCnt, _labelRowsTab, qgar::Component::_MAX_LABEL, _moreCurrentRuns, qgar::Component::_NO_LABEL, _pCompImg, _pMapCCImg, _prevColor, _prevLabel, _prevRowIdx, _prevRunCnt, _prevRunEndX, _prevRunIdx, _ptRow, _ptRowEnd, _rCompTab, _rCompTree, _rowEndIdx, _rowIdx, _runRowsTab, _validCompIdxList, _width, _xBottomRight, _xTopLeft, _xTopLeftPix, _yBottomRight, _yTopLeft, _yTopLeftPix, constructComponentTree(), qgar::GenTree< T >::gotoRoot(), qgar::GenTree< T >::insertParent(), mergePrevAndCurrComponents(), nextCurrRun(), nextPrevRun(), prevAndCurrRunsCoincide(), qgar::GenTree< T >::pRoot(), qgar::QGE_BW_BLACK, qgar::QGE_BW_WHITE, and validLabel().

int qgar::ConnectedComponentsImpl::validLabel ( Component::label_type aLabel ) [private]

Get the valid label of (i.e. equivalent to) a given label.

Parameters:

aLabel a label

Definition at line 658 of file ConnectedComponentsImpl.C.
References _equivLabelTab, and qgar::Component::_NO_LABEL.
Referenced by mergePrevAndCurrComponents(), and run().

Member Data Documentation

std::vector<int> qgar::ConnectedComponentsImpl::_areaPixels [protected]

Area (in pixels) of each component.

Definition at line 631 of file ConnectedComponentsImpl.H.
Referenced by mergePrevAndCurrComponents(), and run().

int qgar::ConnectedComponentsImpl::_colEndIdx [protected]

Index of the last column of the initial binary image (and of the component image).

Definition at line 263 of file ConnectedComponentsImpl.H.
Referenced by run().

std::vector<QGEbw> qgar::ConnectedComponentsImpl::_color [protected]

Color of each component.

Definition at line 592 of file ConnectedComponentsImpl.H.
Referenced by run().

QGEbw qgar::ConnectedComponentsImpl::_currColor [protected]

Considering the current run in the (current) row, color of this run.

Definition at line 427 of file ConnectedComponentsImpl.H.
Referenced by nextCurrRun(), prevAndCurrRunsCoincide(), and run().

Component::label_type qgar::ConnectedComponentsImpl::_currLabel [protected]

Considering the current run in the (current) row, label number of this run.

Definition at line 421 of file ConnectedComponentsImpl.H.
Referenced by mergePrevAndCurrComponents(), nextCurrRun(), and run().

int qgar::ConnectedComponentsImpl::_currRunBeginX [protected]

Considering the current run in the (current) row, index (in image row) of the beginning of this run.

Definition at line 433 of file ConnectedComponentsImpl.H.
Referenced by mergePrevAndCurrComponents(), nextCurrRun(), and run().

int qgar::ConnectedComponentsImpl::_currRunEndX [protected]

Considering the current run in the (current) row, index (in image row) of the end of the run.

Definition at line 439 of file ConnectedComponentsImpl.H.
Referenced by mergePrevAndCurrComponents(), nextCurrRun(), and run().

int qgar::ConnectedComponentsImpl::_currRunIdx [protected]

Considering the current run in the (current) row, index of this run in the run/label row.

Definition at line 415 of file ConnectedComponentsImpl.H.
Referenced by nextCurrRun(), and run().

std::vector<Component::label_type> qgar::ConnectedComponentsImpl::_equivLabelTab [protected]

Table of equivalent labels.

_labelCnt | 0 1 2 3 4 ... v <- labels +--+--+--+--+--+- -+--+ _equivLabelTab |NO|E1|NO|NO|E4| | | <- equivalent labels +--+--+--+--+--+- -+--+

When a component is created, it is associated with a label Li and _equivLabelTab[Li] is set to NO LABEL which means that the component is a valid one.

When components labelled Lj and Lk (Lj < Lk) have to be merged, the component with the greatest label (Lk) is merged into the component with the smallest label (Lj). _equivLabelTab[Lk] is set to Lj, to indicate that labels Lj and Lk are equivalent, i.e. are associated with the same component.

NOTES

The smallest label of a set of equivalent labels is called the valid label, and the component corresponding to a valid label is called the valid component.
By construction, component labelled 0 is always valid and represents the background.

Definition at line 491 of file ConnectedComponentsImpl.H.
Referenced by mergePrevAndCurrComponents(), run(), and validLabel().

Component::label_type qgar::ConnectedComponentsImpl::_finalLabelCnt [protected]

Final label count.

Definition at line 519 of file ConnectedComponentsImpl.H.
Referenced by run().

std::vector<Component::label_type> qgar::ConnectedComponentsImpl::_finalLabelTab [protected]

Table giving the final label numbering.

_labelCnt | 0 1 2 3 ... v <- initial label numbers +--+--+--+--+- -+--+ _finalLabelTab |0 |F1|F2|F3| | | final labels +--+--+--+--+- -+--+ 0 <= Fi <= _finalLabelCnt
_finalLabelTab[Li] gives the final valid label, equivalent to initial label Li. Final label numbers are computed so as to get a consecutive final numbering.
NOTE
By construction, the final label of component 0 (background) is always 0.
Definition at line 514 of file ConnectedComponentsImpl.H.
Referenced by run().

int qgar::ConnectedComponentsImpl::_height [protected]

Height of the initial binary image (and of the component image).

Definition at line 257 of file ConnectedComponentsImpl.H.
Referenced by run().

std::vector<Component::label_type> qgar::ConnectedComponentsImpl::_inLabel [protected]

Label of the comprising component of each component.

Definition at line 587 of file ConnectedComponentsImpl.H.
Referenced by run().

Component::label_type qgar::ConnectedComponentsImpl::_labelCnt [protected]

Current label count.

Definition at line 458 of file ConnectedComponentsImpl.H.
Referenced by run().

std::vector< std::vector<Component::label_type> > qgar::ConnectedComponentsImpl::_labelRowsTab [protected]

Table of label rows: 1 label row for each row of the given binary image.

Definition at line 322 of file ConnectedComponentsImpl.H.
Referenced by mergePrevAndCurrComponents(), nextPrevRun(), and run().

bool qgar::ConnectedComponentsImpl::_moreCurrentRuns [protected]

True while all runs in a row are not processed.

Definition at line 327 of file ConnectedComponentsImpl.H.
Referenced by run().

ConnectedComponents::image_type* qgar::ConnectedComponentsImpl::_pCompImg [protected]

Pointer to the component image.

Definition at line 643 of file ConnectedComponentsImpl.H.
Referenced by run().

Component::label_type* qgar::ConnectedComponentsImpl::_pMapCCImg [protected]

Pointer to the pixel map of the component image.

Definition at line 648 of file ConnectedComponentsImpl.H.
Referenced by run().

QGEbw qgar::ConnectedComponentsImpl::_prevColor [protected]

Considering the current run in the (previous) row, color of this run.

Definition at line 368 of file ConnectedComponentsImpl.H.
Referenced by nextPrevRun(), prevAndCurrRunsCoincide(), and run().

Component::label_type qgar::ConnectedComponentsImpl::_prevLabel [protected]

Considering the current run in the (previous) row, label number of this run.

Definition at line 362 of file ConnectedComponentsImpl.H.
Referenced by mergePrevAndCurrComponents(), nextPrevRun(), and run().

int qgar::ConnectedComponentsImpl::_prevRowIdx [protected]

Index of the previous row in the given image, and in the tables of run/label rows.
See qgar::ConnectedComponentsImpl::_runRowsTab and qgar::ConnectedComponentsImpl::_labelRowsTab, in section II about runs.
Definition at line 344 of file ConnectedComponentsImpl.H.
Referenced by nextPrevRun(), and run().

int qgar::ConnectedComponentsImpl::_prevRunBeginX [protected]

Considering the current run in the (previous) row, index (in image row) of the beginning of this run.

Definition at line 374 of file ConnectedComponentsImpl.H.
Referenced by nextPrevRun().

int qgar::ConnectedComponentsImpl::_prevRunCnt [protected]

Considering the current run in the (previous) row, number of runs (starting from 0) in the run row.

Definition at line 356 of file ConnectedComponentsImpl.H.
Referenced by run().

int qgar::ConnectedComponentsImpl::_prevRunEndX [protected]

Considering the current run in the (previous) row, index (in image row) of the end of this run.

Definition at line 380 of file ConnectedComponentsImpl.H.
Referenced by nextPrevRun(), and run().

int qgar::ConnectedComponentsImpl::_prevRunIdx [protected]

Considering the current run in the (previous) row, index of this run in the run/label row.

Definition at line 350 of file ConnectedComponentsImpl.H.
Referenced by nextPrevRun(), and run().

BinaryImage::value_type* qgar::ConnectedComponentsImpl::_ptRow [protected]

Pointer to the current row in the pixel map of the given binary image.

Definition at line 393 of file ConnectedComponentsImpl.H.
Referenced by nextCurrRun(), and run().

BinaryImage::value_type* qgar::ConnectedComponentsImpl::_ptRowEnd [protected]

Pointer to the end of the current row in the pixel map of the given binary image.

Definition at line 399 of file ConnectedComponentsImpl.H.
Referenced by nextCurrRun(), and run().

std::vector<ConnectedComponents::node_type*>& qgar::ConnectedComponentsImpl::_rCompTab [protected]

Reference to the component table.
See class qgar::ConnectedComponents.
Definition at line 662 of file ConnectedComponentsImpl.H.
Referenced by run().

ConnectedComponents::tree_type& qgar::ConnectedComponentsImpl::_rCompTree [protected]

Reference to the component tree.
See class qgar::ConnectedComponents.
Definition at line 655 of file ConnectedComponentsImpl.H.
Referenced by run().

int qgar::ConnectedComponentsImpl::_rowEndIdx [protected]

Index of the last row of the initial binary image (and of the component image).

Definition at line 269 of file ConnectedComponentsImpl.H.
Referenced by run().

int qgar::ConnectedComponentsImpl::_rowIdx [protected]

Index of the current row in the given binary image, and in the tables of run/label rows.
See qgar::ConnectedComponentsImpl::_runRowsTab and qgar::ConnectedComponentsImpl::_labelRowsTab, in section II about runs.
Definition at line 409 of file ConnectedComponentsImpl.H.
Referenced by mergePrevAndCurrComponents(), and run().

std::vector< std::vector<int> > qgar::ConnectedComponentsImpl::_runRowsTab [protected]

Table of run rows: 1 run row for each row of the given binary image.

Definition at line 316 of file ConnectedComponentsImpl.H.
Referenced by mergePrevAndCurrComponents(), nextPrevRun(), and run().

std::list<int> qgar::ConnectedComponentsImpl::_validCompIdxList [protected]

List recording the indexes of valid components in the table of equivalent labels, _equivLabelTab (see above).

+---+---+--- | | | | |... _validCompIdxList +-|-+-|-+--- | | | | _labelCnt v v | 0 1 2 3 4 ... v +--+--+--+--+--+- -+--+ |NO|E1|NO|NO|E4| | | _equivLabelTab +--+--+--+--+--+- -+--+
This list is constructed once all the rows of the given binary image are processed, and it is used to construct the final component tree. Component labelled 0 (which always represents the background) is not recorded in the list.
Definition at line 543 of file ConnectedComponentsImpl.H.
Referenced by run().

int qgar::ConnectedComponentsImpl::_width [protected]

Width of the initial binary image (and of the component image).

Definition at line 251 of file ConnectedComponentsImpl.H.
Referenced by run().

std::vector<int> qgar::ConnectedComponentsImpl::_xBottomRight [protected]

X coordinate of the bottom right corner of the bounding box of each component.

Definition at line 620 of file ConnectedComponentsImpl.H.
Referenced by mergePrevAndCurrComponents(), and run().

std::vector<int> qgar::ConnectedComponentsImpl::_xTopLeft [protected]

X coordinate of the top left corner of the bounding box of each component.

Definition at line 608 of file ConnectedComponentsImpl.H.
Referenced by mergePrevAndCurrComponents(), and run().

std::vector<int> qgar::ConnectedComponentsImpl::_xTopLeftPix [protected]

X coordinate of the top left pixel of each component.

Definition at line 597 of file ConnectedComponentsImpl.H.
Referenced by mergePrevAndCurrComponents(), and run().

std::vector<int> qgar::ConnectedComponentsImpl::_yBottomRight [protected]

Y coordinate of the bottom right corner of the bounding box of each component.

Definition at line 626 of file ConnectedComponentsImpl.H.
Referenced by mergePrevAndCurrComponents(), and run().

std::vector<int> qgar::ConnectedComponentsImpl::_yTopLeft [protected]

Y coordinate of the top left corner of the bounding box of each component.

Definition at line 614 of file ConnectedComponentsImpl.H.
Referenced by mergePrevAndCurrComponents(), and run().

std::vector<int> qgar::ConnectedComponentsImpl::_yTopLeftPix [protected]

Y coordinate of the top left pixel of each component.

Definition at line 602 of file ConnectedComponentsImpl.H.
Referenced by mergePrevAndCurrComponents(), and run().

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


Public Member Functions
Constructors
	ConnectedComponentsImpl (const BinaryImage &aBinImg, ConnectedComponents::image_type aPCompImg, ConnectedComponents::tree_type &aRCompTree, std::vector< ConnectedComponents::node_type > &aRCompTab)
	Initialize data in order to run the construction of components.
Destructor
	~ConnectedComponentsImpl ()
	Non-virtual destructor.
Construction of connected components
void	run () throw (QgarErrorAlgorithm)
	Run the construction of connected components.
Protected Attributes
(I) The initial binary image
int	_width
	Width of the initial binary image (and of the component image).
int	_height
	Height of the initial binary image (and of the component image).
int	_colEndIdx
	Index of the last column of the initial binary image (and of the component image).
int	_rowEndIdx
	Index of the last row of the initial binary image (and of the component image).
(II) Runs in the given binary image
For each row (of the given image), whose index is _rowIdx: 0 1 2 3 4 5 6 7 8 9 <- column numbers row #_rowIdx +-+-+-+-+-+-+-+-+-+-+ of the given image \|b\|w\|b\|b\|b\|w\|w\|b\|b\|b\| <- pixels +-+-+-+-+-+-+-+-+-+-+ ^ ^ \|_ considered _\| as WHITE 0 1 2 3 4 <- run numbers +--+--+--+--+--+ _runRowsTab[_rowIdx] \|2 \|3 \|2 \|2 \|1 \| <- run lengths +--+--+--+--+--+ +--+--+--+--+--+ _labelRowsTab[_rowIdx] \|L0\|L1\|L2\|L3\|L4\| <- run labels +--+--+--+--+--+ => Even indexes in a run/label row correspond to <b>white</b> runs Odd indexes in a run/label row correspond to <b>black</b> runs The run row, stored in runRowsTab[_rowIdx], gives the lengths of the runs of same-colored consecutive pixels in the row. First and last rows are considered as completely white. First and last pixels of a given row are considered as white. The label row, stored in _labelRowsTab[_rowIdx], gives the labels of the corresponding runs: _labelRowsTab[_rowIdx][rdx] gives the label of the run whose length is runRowsTab[_rowIdx][rdx].
std::vector< std::vector< int > >	_runRowsTab
	Table of run rows: 1 run row for each row of the given binary image.
std::vector< std::vector< Component::label_type > >	_labelRowsTab
	Table of label rows: 1 label row for each row of the given binary image.
bool	_moreCurrentRuns
	True while all runs in a row are not processed.
(III) Previous row of the given binary image
int	_prevRowIdx
	Index of the previous row in the given image, and in the tables of run/label rows.
int	_prevRunIdx
	Considering the current run in the (previous) row, index of this run in the run/label row.
int	_prevRunCnt
	Considering the current run in the (previous) row, number of runs (starting from 0) in the run row.
Component::label_type	_prevLabel
	Considering the current run in the (previous) row, label number of this run.
QGEbw	_prevColor
	Considering the current run in the (previous) row, color of this run.
int	_prevRunBeginX
	Considering the current run in the (previous) row, index (in image row) of the beginning of this run.
int	_prevRunEndX
	Considering the current run in the (previous) row, index (in image row) of the end of this run.
(IV) Current row of the given binary image
BinaryImage::value_type *	_ptRow
	Pointer to the current row in the pixel map of the given binary image.
BinaryImage::value_type *	_ptRowEnd
	Pointer to the end of the current row in the pixel map of the given binary image.
int	_rowIdx
	Index of the current row in the given binary image, and in the tables of run/label rows.
int	_currRunIdx
	Considering the current run in the (current) row, index of this run in the run/label row.
Component::label_type	_currLabel
	Considering the current run in the (current) row, label number of this run.
QGEbw	_currColor
	Considering the current run in the (current) row, color of this run.
int	_currRunBeginX
	Considering the current run in the (current) row, index (in image row) of the beginning of this run.
int	_currRunEndX
	Considering the current run in the (current) row, index (in image row) of the end of the run.
(V) Labels
Each created component is associated with a label, that is used as an index to store/access information about the component in the different tables representing the components (see section VI about component features).
Component::label_type	_labelCnt
	Current label count.
std::vector< Component::label_type >	_equivLabelTab
	Table of equivalent labels.
std::vector< Component::label_type >	_finalLabelTab
	Table giving the final label numbering.
Component::label_type	_finalLabelCnt
	Final label count.
std::list< int >	_validCompIdxList
	List recording the indexes of valid components in the table of equivalent labels, _equivLabelTab (see above).
(VI) Tables to store component features
The component in which a given component is directly included (i.e. has a common border) is called the comprising component. 0 1 2 3 4... <- component labels (<= _labelCnt) +--+--+--+--+--+- --+ C \|i0\|i1\|i2\|i3\|i4\| _inLabel : label of the comprising component \| O +--+--+--+--+--+- \| M \|c0\|c1\|c2\|c3\|c4\| _color : color \| P +--+--+--+--+--+- \| O \|p0\|p1\|p2\|p3\|p4\| _xTopLeftPix : X of top left pixel \| N +--+--+--+--+--+- \| E \|P0\|P1\|P2\|P3\|P4\| _yTopLeftPix : Y of top left pixel \| N +--+--+--+--+--+- \| T \|t0\|t1\|t2\|t3\|t4\| _xTopLeft : X of top left corner > +--+--+--+--+--+- \| \|T0\|T1\|T2\|T3\|T4\| _yTopLeft : Y of top left corner \| F +--+--+--+--+--+- \| E \|b0\|b1\|b2\|b3\|b4\| _xBottomRight: X of bottom right corner \| A +--+--+--+--+--+- \| T \|B0\|B1\|B2\|B3\|B4\| _yBottomRight: Y of bottom right corner \| U +--+--+--+--+--+- \| R \|a0\|a1\|a2\|a3\|a4\| _areaPixels : area \| E +--+--+--+--+--+- --+ S For component labelled Li, _inLabel[Li] gives the label of its comprising component, color[Li] gives its color, etc.
std::vector< Component::label_type >	_inLabel
	Label of the comprising component of each component.
std::vector< QGEbw >	_color
	Color of each component.
std::vector< int >	_xTopLeftPix
	X coordinate of the top left pixel of each component.
std::vector< int >	_yTopLeftPix
	Y coordinate of the top left pixel of each component.
std::vector< int >	_xTopLeft
	X coordinate of the top left corner of the bounding box of each component.
std::vector< int >	_yTopLeft
	Y coordinate of the top left corner of the bounding box of each component.
std::vector< int >	_xBottomRight
	X coordinate of the bottom right corner of the bounding box of each component.
std::vector< int >	_yBottomRight
	Y coordinate of the bottom right corner of the bounding box of each component.
std::vector< int >	_areaPixels
	Area (in pixels) of each component.
(VII) The connected components
ConnectedComponents::image_type *	_pCompImg
	Pointer to the component image.
Component::label_type *	_pMapCCImg
	Pointer to the pixel map of the component image.
ConnectedComponents::tree_type &	_rCompTree
	Reference to the component tree.
std::vector< ConnectedComponents::node_type * > &	_rCompTab
	Reference to the component table.
Private Member Functions
Functions working on labels
int	validLabel (Component::label_type aLabel)
	Get the valid label of (i.e. equivalent to) a given label.
Functions working on components
void	mergePrevAndCurrComponents ()
	merge component including previous run and component including current run.
Functions working on runs
void	nextPrevRun ()
	Move to next run in previous row (see section (III) about previous row).
void	nextCurrRun ()
	Move to next run in current row (see section (IV) about current row).
void	prevAndCurrRunsCoincide ()
	Perform moves according to black- and white-connexity when end of previous run and end of current run coincide.
Functions working on the component tree
void	constructComponentTree (ConnectedComponents::tree_type &aTree, ConnectedComponents::node_type aPNode, std::vector< ConnectedComponents::node_type > &aCCTab)
	Construction the component tree.

qgar::ConnectedComponentsImpl Class Reference [Connected components]

Detailed Description

Public Member Functions

Protected Attributes

Private Member Functions

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

qgar::ConnectedComponentsImpl Class Reference
[Connected components]