ConnectedComponentsImpl.H

Go to the documentation of this file.

/*---------------------------------------------------------------------+
 | Library QgarLib, graphics analysis and recognition                  |
 | Copyright (C) 2002  Qgar Project, LORIA                             |
 |                                                                     |
 | This library is free software; you can redistribute it and/or       |
 | modify it under the terms of the GNU Lesser General Public          |
 | License version 2.1, as published by the Free Software Foundation.  |
 |                                                                     |
 | This library is distributed in the hope that it will be useful,     |
 | but WITHOUT ANY WARRANTY; without even the implied warranty of      |
 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.                |
 | See the GNU Lesser General Public License for more details.         |
 |                                                                     |
 | The GNU Lesser General Public License is included in the file       |
 | LICENSE.LGPL, in the root directory of the Qgar packaging. See      |
 | http://www.gnu.org/licenses/lgpl.html for the terms of the licence. |
 | To receive a paper copy, write to the Free Software Foundation,     |
 | Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.       |
 |                                                                     |
 | Contact Project Qgar for any information:                           |
 |   LORIA - équipe Qgar                                               |
 |   B.P. 239, 54506 Vandoeuvre-lès-Nancy Cedex, France                |
 |   email: qgar-contact@loria.fr                                      |
 |   http://www.qgar.org/                                              |
 *---------------------------------------------------------------------*/


#ifndef __CONNECTEDCOMPONENTSIMPL_H_INCLUDED__
#define __CONNECTEDCOMPONENTSIMPL_H_INCLUDED__

/**
 * @file    ConnectedComponentsImpl.H
 * @brief   Header file of class qgar::ConnectedComponentsImpl.
 *
 * @author <a href="mailto:qgar-develop@loria.fr?subject=Qgar fwd Gérald Masini">Gérald Masini</a>
 * @date   May 28, 2004  15:41
 * @since  Qgar 2.1.1
 */


// For RCS/CVS use: Do not delete
/* $Id: ConnectedComponentsImpl.H,v 1.14 2005/10/14 17:05:45 masini Exp $ */


// STL
#include <list>
#include <vector>
// QGAR
#include <qgarlib/Component.H>
#include <qgarlib/ConnectedComponents.H>
#include <qgarlib/GenImage.H>
#include <qgarlib/GenTree.H>
#include <qgarlib/QgarErrorAlgorithm.H>



namespace qgar
{

/**
 * @ingroup GRAPHPROC_CC
 *
 * @class ConnectedComponentsImpl
 *   ConnectedComponentsImpl.H "qgarlib/ConnectedComponentsImpl.H"
 *
 * @brief Implementation of the construction of connected components
 *        of a binary image.
 *
 * A (connected) component is a region defined by a set of connected
 * pixels having the same color:
@verbatim
      B B B                    w W w
      B * B                    W * W
      B B B                    w W w

   8-connexity              4-connexity
    for BLACK                for WHITE
@endverbatim
 * <ul>
 * <li>
 * Black components are constructed using 8-connexity: When black,
 * the central point ('*' on the figure) is connex to its 8 black
 * neighbors marked <b>B</b>.
 * </li>
 * <li>
 * White components are constructed using 4-connexity: When white,
 * the central point ('*' on the figure) is connex to its 4 white
 * neighbors marked <b>W</b> and is not connex to the 4 white
 * neighbors marked <b>w</b>.
 * </li>
 * </ul>
 *
 * See class qgar::Component for the way a component is represented.
 *
@verbatim
                     aRCompTree
                  ________________
                 |                |    0     j     k
  +----------+   |      +--+      |   +--+--+--+--+--+- -+--+
  |COMPONENT |<----------C0|<----------- |  |  |  |  |   |  |  aRCompTab
  |LABELLED 0|   |      +--+      |   +--+--+|-+--+|-+- -+--+
  +----------+   |       /\       |          |     |
                 |      /  \      |          |     |
  +----------+   |  +--+    +--+  |          |     |
  |COMPONENT |<------Ci|    |Cj|<------------+     |
  |LABELLED i|   |  +--+    +--+  |                |
  +----------+   |    |     /||\  |                |
  +----------+   |  +--+          |                |
  |COMPONENT |<------Ck|<--------------------------+
  |LABELLED k|   |  +--+          |
  +----------+   |________________|
@endverbatim
 *
 * Each component is associated with a label (a number of type
 * <b>qgar::Component::label_type</b>).
 *
 * The set of components is hierarchically organized as a tree,
 * the so-called <i>component tree</i> (given by argument
 * <b>aRCompTree</b> of function qgar::ConnectedComponentsImpl::run).
 * Each node represents a component (in fact, the data associated with
 * the node is a pointer to the component, <b>Ci</b> 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 <b>white</b> component,
 * labelled <b>0</b>. 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 <b>white</b>.
 *
 * The so-called <i>component table</i>
 * (given by argument <b>aRCompTab</b> 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
 * <i>component image</i> (given by argument <b>aRCompImg</b>
 * of function qgar::ConnectedComponentsImpl::ConnectedComponentsImpl):
 * The value of a pixel is the label of the component to which
 * the pixel belongs.
 *
 * @warning
@verbatim
      B B B                    w W w
      B * B                    W * W
      B B B                    w W w

   8-connexity              4-connexity
    for BLACK                for WHITE
@endverbatim
 * <ul>
 * <li>
 * Black components are constructed using 8-connexity: When
 * black, the central point ('*' on the figure) is connex to its
 * 8 black neighbors marked <b>B</b>.
 * </li>
 * <li>
 * White components are constructed using 4-connexity: When
 * white, the central point ('*' on the figure) is connex to its
 * 4 white neighbors marked <b>W</b> and is <i>not connex</i> to the
 * 4 white neighbors marked <b>w</b>.
 * </li>
 * </ul>
 *
 * @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 <a href="mailto:qgar-develop@loria.fr?subject=Qgar fwd Gérald Masini">Gérald Masini</a>
 * @date   May 28, 2004  15:41
 * @since  Qgar 2.1.1
 */
class ConnectedComponentsImpl
{
// -------------------------------------------------------------------
// P U B L I C    M E M B E R S
// -------------------------------------------------------------------
public:

  /** @name Constructors */
  //        ============
  //@{

  /**
   * @brief Initialize data
   *        in order to run the construction of components.
   *
   * @param aBinImg      binary image from which components are extracted
   * @param aPCompImg    pointer to component image
   * @param aRCompTree   reference to the component tree
   *                     (see class qgar::ConnectedComponents)
   * @param aRCompTab    reference to the component table
   *                     (see class qgar::ConnectedComponents)
   */
  ConnectedComponentsImpl(const BinaryImage& aBinImg,
                          ConnectedComponents::image_type* aPCompImg,
                          ConnectedComponents::tree_type& aRCompTree,
                          std::vector<ConnectedComponents::node_type*>&
                          aRCompTab);

  //@}


  /** @name Destructor */
  //        ==========
  //@{

  /**
   * @brief Non-virtual destructor.
   */
  ~ConnectedComponentsImpl();

  //@}


  /** @name Construction of connected components */
  //        ====================================
  //@{

  /**
   * @brief Run the construction of connected components.
   *
   * @exception qgar::QgarErrorAlgorithm (maximum label exceeded)
   */
  void run() throw(QgarErrorAlgorithm);

  //@}


// -------------------------------------------------------------------
// P R O T E C T E D    M E M B E R S
// -------------------------------------------------------------------
protected:

  /** @name (I) The initial binary image */
  //        ============================
  //@{

  /**
   * @brief Width of the initial binary image
   * (and of the component image).
   */
  int _width;

  /**
   * @brief Height of the initial binary image
   * (and of the component image).
   */
  int _height;

  /**
   * @brief Index of the last column of the initial binary image
   * (and of the component image).
   */
  int _colEndIdx;

  /**
   * @brief Index of the last row of the initial binary image
   * (and of the component image).
   */
  int _rowEndIdx;

  //@}


  // =================================================================
  /** @name (II) Runs in the given binary image

  For each row (of the given image), whose index is <b>_rowIdx</b>:

@verbatim
                          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
@endverbatim

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

  - The label row, stored in <b>_labelRowsTab[_rowIdx]</b>, gives the labels
    of the corresponding runs: <b>_labelRowsTab[_rowIdx][rdx]</b> gives
    the label of the run whose length is <b>runRowsTab[_rowIdx][rdx]</b>.
  */
  // =================================================================
  //@{

  /**
   * @brief Table of run rows:
   *        1 run row for each row of the given binary image.
   */
  std::vector< std::vector<int> > _runRowsTab;

  /**
   * @brief Table of label rows:
   *        1 label row for each row of the given binary image.
   */
  std::vector< std::vector<Component::label_type> > _labelRowsTab;

  /**
   * @brief True while all runs in a row are not processed.
   */
  bool _moreCurrentRuns;

  //@}


  /** @name (III) Previous row of the given binary image */
  //        ============================================
  //@{

  /**
   * @brief 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.
   */
  int _prevRowIdx;

  /**
   * @brief Considering the current run in the (previous) row,
   * index of this run in the run/label row.
   */
  int _prevRunIdx;

  /**
   * @brief Considering the current run in the (previous) row,
   * number of runs (starting from <b>0</b>) in the run row.
   */
  int _prevRunCnt;

  /**
   * @brief Considering the current run in the (previous) row,
   * label number of this run.
   */
  Component::label_type _prevLabel;

  /**
   * @brief Considering the current run in the (previous) row,
   * color of this run.
   */
  QGEbw _prevColor;

  /**
   * @brief Considering the current run in the (previous) row,
   * index  (in image row) of the beginning of this run.
   */
  int _prevRunBeginX;

  /**
   * @brief Considering the current run in the (previous) row,
   * index  (in image row) of the end of this run.
   */
  int _prevRunEndX;

  //@}


  /** @name (IV) Current row of the given binary image */
  //        ===========================================
  //@{

  /**
   * @brief Pointer to the current row in the pixel map
   *        of the given binary image.
   */
  BinaryImage::value_type* _ptRow;

  /**
   * @brief Pointer to the end of the current row in the pixel map
   *        of the given binary image.
   */
  BinaryImage::value_type* _ptRowEnd;

  /**
   * @brief 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.
   */
  int _rowIdx;

  /**
   * @brief Considering the current run in the (current) row,
   * index of this run in the run/label row.
   */
  int _currRunIdx;

  /**
   * @brief Considering the current run in the (current) row,
   * label number of this run.
   */
  Component::label_type _currLabel;

  /**
   * @brief Considering the current run in the (current) row,
   * color of this run.
   */
  QGEbw _currColor;

  /**
   * @brief Considering the current run in the (current) row,
   * index (in image row) of the beginning of this run.
   */
  int _currRunBeginX;

  /**
   * @brief Considering the current run in the (current) row,
   * index (in image row) of the end of the run.
   */
  int _currRunEndX;

  //@}


  // =================================================================
  /** @name (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).
  */
  // =================================================================
  //@{

  /**
   * @brief Current label count.
   */
  Component::label_type _labelCnt;

  /**
   * @brief Table of equivalent labels.
   *
@verbatim
                                 _labelCnt
                                     |
                  0  1  2  3  4  ... v     <- labels
                 +--+--+--+--+--+- -+--+
 _equivLabelTab  |NO|E1|NO|NO|E4|   |  |   <- equivalent labels
                 +--+--+--+--+--+- -+--+
@endverbatim
   *
   * - When a component is created, it is associated with a label
   *   <b>Li</b> and <b>_equivLabelTab[Li]</b> is set to <i>NO LABEL</i>
   *   which means that the component is a <i>valid</i> one.
   *
   * - When components labelled <b>Lj</b> and <b>Lk (Lj < Lk)</b> have
   *   to be merged, the component with the greatest label (<b>Lk</b>)
   *   is merged into the component with the smallest label (<b>Lj</b>).
   *   <b>_equivLabelTab[Lk]</b> is set to <b>Lj</b>, to indicate that
   *   labels <b>Lj</b> and <b>Lk</b> are <i>equivalent</i>,
   *   i.e. are associated with the same component.
   *
   *   <b>NOTES</b>
   *
   *   - The smallest label of a set of equivalent labels is called
   *     the <i>valid label</i>, and the component corresponding to a
   *     valid label is called the <i>valid component</i>.
   *   - By construction, component labelled <b>0</b> is always valid
   *     and represents the background.
   */
  std::vector<Component::label_type> _equivLabelTab;

  /**
   * @brief Table giving the final label numbering.
   *
@verbatim
                              _labelCnt
                                  |
                  0  1  2  3  ... v    <- initial label numbers
                 +--+--+--+--+- -+--+
 _finalLabelTab  |0 |F1|F2|F3|   |  |  final labels
                 +--+--+--+--+- -+--+  0 <= Fi <= _finalLabelCnt
@endverbatim
   *
   * <b>_finalLabelTab[Li]</b> gives the final valid label, equivalent
   * to initial label <b>Li</b>. Final label numbers are computed
   * so as to get a consecutive final numbering.
   *
   * <b>NOTE</b>
   *
   * By construction, the final label of component <b>0</b>
   * (background) is always <b>0</b>.
   */
  std::vector<Component::label_type> _finalLabelTab;

  /**
   * @brief Final label count.
   */
  Component::label_type _finalLabelCnt;

  /**
   * @brief List recording the indexes of valid components
   * in the table of equivalent labels, <b>_equivLabelTab</b>
   * (see above).
   *
@verbatim
       +---+---+---
       | | | | |...  _validCompIdxList
       +-|-+-|-+---
         |   |
         |   |    _labelCnt
         v   v        |
   0  1  2   3  4 ... v
  +--+--+--+--+--+- -+--+
  |NO|E1|NO|NO|E4|   |  |  _equivLabelTab
  +--+--+--+--+--+- -+--+
@endverbatim
   * 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 <b>0</b> (which always
   * represents the background) is not recorded in the list.
   */
  std::list<int> _validCompIdxList;

  //@}

 
  // =================================================================
  /** @name (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 <i>comprising component</i>.

@verbatim
   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
@endverbatim

   For component labelled <b>Li</b>, <b>_inLabel[Li]</b> gives
   the label of its comprising component, <b>color[Li]</b> gives
   its color, etc.
  */
  // =================================================================
  //@{

  /**
   * @brief Label of the comprising component of each component.
   */
  std::vector<Component::label_type> _inLabel;

  /**
   * @brief Color of each component.
   */
  std::vector<QGEbw> _color;

  /**
   * @brief X coordinate of the top left pixel of each component.
   */
  std::vector<int> _xTopLeftPix;

  /**
   * @brief Y coordinate of the top left pixel of each component.
   */
  std::vector<int> _yTopLeftPix;

  /**
   * @brief X coordinate of the top left corner of the bounding box
   *        of each component.
   */
  std::vector<int> _xTopLeft;

  /**
   * @brief Y coordinate of the top left corner of the bounding box
   *        of each component.
   */
  std::vector<int> _yTopLeft;

  /**
   * @brief X coordinate of the bottom right corner of the bounding
   *        box of each component.
   */
  std::vector<int> _xBottomRight;

  /**
   * @brief Y coordinate of the bottom right corner of the bounding
   *        box of each component.
   */
  std::vector<int> _yBottomRight;

  /**
   * @brief Area (in pixels) of each component.
   */
  std::vector<int> _areaPixels;

  //@}


  /** @name (VII) The connected components */
  //        ==============================
  //@{

  /**
   * @brief Pointer to the component image.
   */
  ConnectedComponents::image_type* _pCompImg;

  /**
   * @brief Pointer to the pixel map of the component image.
   */
  Component::label_type* _pMapCCImg;

  /**
   * @brief Reference to the component tree.
   *
   * See class qgar::ConnectedComponents.
   */
  ConnectedComponents::tree_type& _rCompTree;

  /**
   * @brief Reference to the component table.
   *
   * See class qgar::ConnectedComponents.
   */
  std::vector<ConnectedComponents::node_type*>& _rCompTab;

  //@}


// -------------------------------------------------------------------
// P R I V A T E    M E M B E R S
// -------------------------------------------------------------------
private:

  /** @name Functions working on labels */
  //        ===========================
  //@{

  /**
   * @brief Get the <i>valid label</i> of (i.e. equivalent to)
   *        a given label.
   * @param aLabel  a label
   */
  int validLabel(Component::label_type aLabel);

  //@}


  /** @name Functions working on components */
  //        ===============================
  //@{

  /**
   * @brief 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.
   */
  void mergePrevAndCurrComponents();

  //@}


  /** @name Functions working on runs */
  //        =========================
  //@{

  /**
   * @brief Move to next run in previous row
   * (see section (III) about previous row).
   */
  void nextPrevRun();

  /**
   * @brief Move to next run in current row
   * (see section (IV) about current row).
   */
  void nextCurrRun();

  /**
   * @brief 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.
   */
  void prevAndCurrRunsCoincide();

  //@}


  /** @name Functions working on the component tree */
  //        =======================================
  //@{

  /**
   * @brief Construction the component tree.
   *
   * @param aTree    reference to the tree being constructed
   * @param aPNode   pointer to a node representing a component
   *                 which has not yet children
   * @param aCCTab   reference to the table of pointers to nodes
   *                 representing components: <b>aCCTab[lab]</b>
   *                 gives a pointer to the node representing
   *                 the component labelled <b>lab</b>
   *                 (<b>lab</b> is a <i>valid</i> label)
   */
  void constructComponentTree
    (ConnectedComponents::tree_type&               aTree,
     ConnectedComponents::node_type*               aPNode,
     std::vector<ConnectedComponents::node_type*>& aCCTab);

  //@}


// -------------------------------------------------------------------
}; // class ConnectedComponentsImpl


} // namespace qgar


#endif /* __CONNECTEDCOMPONENTSIMPL_H_INCLUDED__ */