ConnectedComponentsImpl.C

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/                                              |
 *---------------------------------------------------------------------*/


/**
 * @file   ConnectedComponentsImpl.C
 * @brief  Implementation of class qgar::ConnectedComponentsImpl.
 *
 *         See file ConnectedComponentsImpl.H for the interface.
 *
 * @author <a href="mailto:qgar-develop@loria.fr?subject=Qgar fwd Gérald Masini">Gérald Masini</a>
 * @date   May 28, 2004  17:51
 * @since  Qgar 2.1.1
 */


// STL
#include <deque>
#include <iostream>
#include <limits>
#include <list>
#include <string>
#include <vector>
// QGAR
#include <qgarlib/Component.H>
#include <qgarlib/ConnectedComponents.H>
#include <qgarlib/ConnectedComponentsImpl.H>
#include <qgarlib/GenImage.H>
#include <qgarlib/GenTree.H>
#include <qgarlib/QgarErrorAlgorithm.H>


namespace qgar
{


// -------------------------------------------------------------------
// -------------------------------------------------------------------
// C O N S T R U C T O R
// -------------------------------------------------------------------
// -------------------------------------------------------------------


// INITIALIZE DATA TO CONSTRUCT CONNECTED COMPONENTS

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

  : _width         (aBinImg.width()),      // width of initial binary image
    _height        (aBinImg.height()),     // height of initial binary image
    _ptRow         (aBinImg.pPixMap()),    // pointer to pixel map of binary image
    _labelCnt      (0),                    // label counter
    _finalLabelCnt (0),                    // integer final label count
    _pCompImg      (aPCompImg),            // pointer to component image
    _pMapCCImg     (aPCompImg->pPixMap()), // pointer to pixel map of component image
    _rCompTree     (aRCompTree),           // reference to the component tree
    _rCompTab      (aRCompTab)             // reference to the component table

{
  // Index of last column of CC image
  _colEndIdx = _width - 1;
  // Index of last row of CC image
  _rowEndIdx = _height - 1;

  // Allocate space for run and label rows
  _runRowsTab.reserve(aBinImg.height());
  _labelRowsTab.reserve(aBinImg.height());
}


// -------------------------------------------------------------------
// -------------------------------------------------------------------
// RUN  THE  CONSTRUCTION  OF  CONNECTED  COMPONENTS
// -------------------------------------------------------------------
// -------------------------------------------------------------------


// ALGORITHM TO BUILD CONNECTED COMPONENTS FROM A BINARY IMAGE

void
ConnectedComponentsImpl::run()
  throw(QgarErrorAlgorithm)
{
  // =====================================================================
  // BEGIN run construction of connected components
  // =====================================================================


  // =====================================================================
  // (1) FIRST ROW
  // =====================================================================

  // WARNING: First row (like last row) is considered as WHITE
  // and belongs to component 0 representing the background

  _equivLabelTab.push_back(Component::_NO_LABEL);  // no equivalent label

  // First component

  _inLabel.push_back(0);           // 0 is conventionally included in 0
  _color.push_back(QGE_BW_WHITE);  // color
  _xTopLeftPix.push_back(0);       // top left pixel
  _yTopLeftPix.push_back(0);
  _xTopLeft.push_back(0);          // bounding box
  _yTopLeft.push_back(0);
  _xBottomRight.push_back(_colEndIdx);
  _yBottomRight.push_back(0);
  _areaPixels.push_back(_width);   // area

  // First run row and first label row
  _runRowsTab.push_back(std::vector<int>(1, _width));
  _labelRowsTab.push_back(std::vector<Component::label_type>(1, 0));

  // Run count for this first row,
  // to get correct data when processing next row
  _currRunIdx = 0;


  // =====================================================================
  // (2) PROCESS NEXT ROWS OF THE BINARY IMAGE
  // =====================================================================

  // Initialize pointer to the current row (in the pixel map of the given
  // image) to beginning of the 2nd row
  _ptRow += _width;


  for (_rowIdx = 1 ; _rowIdx < _height ; ++_rowIdx )
    // FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
    // BLOCK-FOR
    // for each row of the given image
    // FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
    {

      // Next row
      // WARNING: Rows are supposed to be consecutively stored
      //          in the pixel map
      _ptRowEnd = _ptRow + _colEndIdx;

      // Index of previous row
      _prevRowIdx = _rowIdx - 1;

      // To save current run row and current label row
      _runRowsTab.push_back(std::vector<int>());
      _labelRowsTab.push_back(std::vector<Component::label_type>());

      // Current run in previous iteration becomes previous run
      // in this iteration
      _prevRunCnt  = _currRunIdx;

      // Initializations to get correct data from function nextPrevRun()
      _prevColor   = QGE_BW_BLACK; // => first run will be WHITE
      _prevRunIdx  = -1;
      _prevRunEndX = -1;

      // pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
      // Get first previous run
      // pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

       // Initializations to get correct data from function nextPrevRun()
      _prevColor   = QGE_BW_BLACK; // => first run will be WHITE
      _prevRunIdx  = -1;
      _prevRunEndX = -1;

      nextPrevRun(); // Get first run
      // pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp


      // cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc
      // Get first current run
      // cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc
      if (_rowIdx == _rowEndIdx)
        {
          // Processing last row
          // WARNING: Last row (like first row) is considered as WHITE
          // and belongs to component 0 representing the background
          // => last row features are known

          _currRunBeginX = 0;
          _currRunEndX   = _colEndIdx;
          _currColor     = QGE_BW_WHITE;           // white run
          _currLabel     = Component::_NO_LABEL;   // not yet labelled
        }
      else
        {
          // Processing any row but the last one

          // Initializations to get correct data from function nextCurrRun()
          _currColor   = QGE_BW_BLACK;  // => first run will be WHITE
          _currRunEndX = -1;
          _currRunIdx  = -1;
          _currLabel   = Component::_NO_LABEL;  // not yet labelled
          
          // WARNING: First pixel is considered as WHITE
          // => skip first pixel, whatever its color is
          ++_ptRow;

          nextCurrRun(); // Get next current run

          // Increment run end index to take first pixel into account
          ++_currRunEndX;
        }
      // cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc


      // Current row is not processed
      _moreCurrentRuns = true;

      while (_moreCurrentRuns)
        // WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
        // WHILE-BLOCK 1
        // while all runs in current row are not processed
        //
        // PREVIOUS RUN AND CURRENT RUN ARE ALWAYS ADJACENT
        // WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
        {

          if (_currColor == _prevColor)
            {
              //____________________________________________________________
              //
              // PREVIOUS RUN AND CURRENT RUN HAVE THE SAME COLOR
              // => current run belongs to the same component as previous run
              
              mergePrevAndCurrComponents();
              //____________________________________________________________
            }


          if (_prevRunEndX < _currRunEndX)
            {
              //____________________________________________________________
              //
              // (i) CURRENT RUN OVERLAPS PREVIOUS RUN
              //     => get next previous run

              nextPrevRun();
              //____________________________________________________________
            }

          else

            {
              // (ii) END OF PREVIOUS AND CURRENT RUNS COINCIDE,
              //      OR PREVIOUS RUN OVERLAPS CURRENT RUN
              // => if current run is not labelled, it starts a new component 

              if (_currLabel == Component::_NO_LABEL)
                {
                  // Get a new label
                  if (_labelCnt == Component::_MAX_LABEL)
                    {
                      std::ostringstream os;
                      os << "Cannot deal with more than " << _labelCnt << " labels!";
                      throw QgarErrorAlgorithm(__FILE__, __LINE__,
                                               "void qgar::ConnectedComponentsImpl::run()",
                                               os.str());
                    }
                  else
                    {
                      ++_labelCnt;
                    }

                  _currLabel = _labelCnt;
                  // Label of the comprising component:
                  // As previous run has a different color, it always belongs
                  // to the component that surrounds the new component
                  _inLabel.push_back(_prevLabel);

                  _equivLabelTab.push_back(Component::_NO_LABEL); // no equivalent label
                  _xTopLeftPix.push_back(_currRunBeginX);         // top left pixel
                  _yTopLeftPix.push_back(_rowIdx);                //
                  _xTopLeft.push_back(_currRunBeginX);            // bounding box
                  _yTopLeft.push_back(_rowIdx);                   //
                  _xBottomRight.push_back(_currRunEndX);          //
                  _yBottomRight.push_back(_rowIdx);               //
                  _color.push_back(_currColor);                   // color
                  _areaPixels.push_back(_currRunEndX - _currRunBeginX + 1); // area

                  // SAVE current run and its label
                  _runRowsTab[_rowIdx].push_back(_currRunEndX - _currRunBeginX + 1);
                  _labelRowsTab[_rowIdx].push_back(_currLabel);
                }


              if (_prevRunEndX > _currRunEndX)
                {
                //__________________________________________________________
                //
                // PREVIOUS RUN OVERLAPS CURRENT RUN
                // => get next current run

                  nextCurrRun();
                //__________________________________________________________
                }

              else

                {
                //__________________________________________________________
                //
                // ENDS OF PREVIOUS RUN AND CURRENT RUN COINCIDE

                  if (_currRunEndX == _colEndIdx)
                    {
                      // END OF ROW IS REACHED
                      _moreCurrentRuns = false;
                    }
                  else
                    {
                      prevAndCurrRunsCoincide();
                    }
                //__________________________________________________________
                }

            } // END (ii) else part of if(current run overlaps previous run)

        }
        // WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
        // END BLOCK-WHILE
        // all runs in current row are processed
        // WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW

    }
    // FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
    // END BLOCK-FOR
    // each row of the given image is processed
    // FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF


  // ============================================================================
  // (3) GET THE FINAL COMPONENTS AND THEIR VALID LABELS
  // ============================================================================

  // At this point:
  //
  //   0  1  2  3  4...  <- component labels (<= _labelCnt)
  //  +--+--+--+--+--+-
  //  |NO|L1|NO|NO|L4|   _equivLabelTab : equivalent labels
  //  +--+--+--+--+--+-
  //
  //  +--+--+--+--+--+-                                                  --+  C
  //  |i0|**|i2|i3|**|   _inLabel      : label of the comprising component |  O
  //  +--+--+--+--+--+-                                                    |  M
  //  |c0|**|c2|c3|**|   _color        : color                             |  P
  //  +--+--+--+--+--+-                                                    |  O
  //  |p0|**|p2|p3|**|   _xTopLeftPix  : X of top left pixel               |  N
  //  +--+--+--+--+--+-                                                    |  E
  //  |P0|**|P2|P3|**|   _yTopLeftPix  : Y of top left pixel               |  N
  //  +--+--+--+--+--+-                                                    |  T
  //  |t0|**|t2|t3|**|   _xTopLeft     : X of top left corner              >
  //  +--+--+--+--+--+-                                                    |
  //  |T0|**|T2|T3|**|   _yTopLeft     : Y of top left corner              |  F
  //  +--+--+--+--+--+-                                                    |  E
  //  |b0|**|b2|b3|**|   _xBottomRight : X of bottom right corner          |  A
  //  +--+--+--+--+--+-                                                    |  T
  //  |B0|**|B2|B3|**|   _yBottomRight : Y of bottom right corner          |  U
  //  +--+--+--+--+--+-                                                    |  R
  //  |a0|**|a2|a3|**|   _areaPixels   : area                              |  E
  //  +--+--+--+--+--+-                                                  --+  S
  //
  //
  // In _equivLabelTab:
  //
  // - 'NO LABEL' (qgar::Component::_NO_LABEL) means that the corresponding
  //   index in the table represents a valid label, thus corresponds to
  //   a valid component. BY CONSTRUCTION, THIS LABEL IS THE SMALLEST OF ALL
  //   THE LABELS (TRANSITIVELY) EQUIVALENT TO IT.
  //   The component features are available in tables _inLabel, _color,
  //    etc. at the same corresponding index.
  // - 'Li' means that the corresponding index does not represent a valid
  //   label, thus corresponds to a component that has been merged into
  //   another one. The features of such a component (**) have no use in
  //   the construction of the final component tree.

  // PURPOSE OF THIS SECTION:
  //
  // - Construct table _finalLabelTab that gives the final labels of the
  //   valid components. New labelling is computed so as to get a consecutive
  //   final numbering.
  //   _finalLabelTab[i] gives the final label of component initially labelled
  //   'i', whose features are still available in _inLabel[i], _color[i], etc.
  // - Update labels in table _inLabel by substituting the final valid
  //   label (given by table _finalLabelTab) for each label (see 3.2 below).
  // - Construct list _validCompIdxList that records the indexes
  //   of the valid components.
  //   Such an index provides a direct access to the features of the
  //   corresponding component in tables _inLabel, _color, etc. In table
  //   _equivLabelTab, the value at such an index always is "NO LABEL"
  //   (see 3.1 below).
  //   Index 0, that always corresponds to the component representing the
  //   background, is not registered in this list (see 3.3 below).
  //
  //        +---+---+---
  //        | | | | |...  _validCompIdxList
  //        +-|-+-|-+---
  //          |   |
  //          |   |
  //          v   v
  //    0  1  2   3  4 ...
  //   +--+--+--+--+--+-
  //   |NO|L1|NO|NO|L4|   _equivLabelTab
  //   +--+--+--+--+--+-
  //
  //   +--+--+--+--+--+-
  //   |I0|**|I2|I3|**|   _inLabel (updated)
  //   +--+--+--+--+--+-
  //   |c0|**|c2|c3|**|   _color
  //   +--+--+--+--+--+-
  //   |  |**|  |  |**|   etc.
  //   +--+--+--+--+--+-
  //
  //   +--+--+--+--+--+-
  //   |l0|l1|l2|l3|  |   _finalLabelTab : final labels
  //   +--+--+--+--+--+-
  //
  // NOTE: Once the required information is computed, table _equivLabelTab
  //       becomes useless...

  // Allocate space for the table of final labels 
  _finalLabelTab.reserve((unsigned int) _labelCnt);

  // By construction, final label of component 0 (background) is 0
  _finalLabelTab.push_back(0);

  // Free labels from the initial equivalence table
  std::deque<Component::label_type> freeLabels;

  // For each initial label, excepting 0
  for (int lab = 1 ; lab <= _labelCnt ; ++lab)
    {
      if (_equivLabelTab[lab] == Component::_NO_LABEL)  // **** (3.1) ****
        {
          // ____________________________________________________________________
          //
          // CURRENT LABEL IS VALID
          // => it corresponds to a valid component
          // => give this component a new label when possible

          if (freeLabels.empty())
            {
              // No free label
              // => the current label number remains unchanged
              _finalLabelTab.push_back(lab);
            }
          else
            {
              // Free labels are available

              // Use first free label
              _finalLabelTab.push_back(freeLabels.back());
              freeLabels.pop_back();

              // Current label is now free
              freeLabels.push_front(lab);
            }

          // Update final label count
          // (by construction, it can never exceed the maximum label count)
          ++_finalLabelCnt;

          // (3.2) Update label of comprising component
          // By construction, the corresponding valid label is already known
          // (the valid label of a set of equivalent labels is the smallest one)
          _inLabel[lab] = _finalLabelTab[_inLabel[lab]];

          // (3.3) Component corresponding to current label is valid
          // => save its index
          _validCompIdxList.push_back(lab);
          // ____________________________________________________________________
        }

      else

        {
          // ____________________________________________________________________
          //
          // CURRENT LABEL IS NOT VALID
          // => get the corresponding valid label and set equivalence
          // By construction, the valid label is not greater than the current label

          _finalLabelTab.push_back(_finalLabelTab[validLabel(lab)]);

          // Current label is now free
          freeLabels.push_front(lab);
          // ____________________________________________________________________
        }

    } // END for


  // ============================================================================
  // (4) CONSTRUCTION OF THE FINAL IMAGE OF LABELS
  // ============================================================================

  // For each row rdx of the given binary image
  // - _runRowsTab[rdx] gives the successive run lengths
  // - _labelRowsTab[rdx] gives the corresponding labels
  //   These labels have not been updated and must be substituted by their
  //   final equivalent label, given by table _finalLabelTab
  
  // Pointer to the current pixel in the related pixel map
  Component::label_type* pMap = _pMapCCImg;

  // For each row
  for (int rdx = 0 ; rdx < _height ; ++rdx)
    {
      int size = (int) (_labelRowsTab[rdx]).size();

      // for each run
      for (int ldx = 0 ; ldx < size ; ++ldx)
        {
          // Get current run length
          int lg = _runRowsTab[rdx][ldx];
          // Get corresponding label and update it
          Component::label_type lab = _finalLabelTab[_labelRowsTab[rdx][ldx]];

          // Copy the labelled run into the pixel map
          for (int idx = 0 ; idx < lg ; ++idx, ++pMap)
            {
              (*pMap) = lab;
            }
        }
    } // END for each row


  // ============================================================================
  // (5) CONSTRUCT THE COMPONENT TREE
  // ============================================================================

  //                     _rCompTree
  //                  ________________
  //                 |                |    0     j     k
  //  +----------+   |      +--+      |   +--+--+--+--+--+- -+--+
  //  |COMPONENT |<----------C0|<----------- |  |  |  |  |   |  |  _rCompTab
  //  |LABELLED 0|   |      +--+      |   +--+--+|-+--+|-+- -+--+
  //  +----------+   |       /\       |          |     |
  //                 |      /  \      |          |     |
  //  +----------+   |  +--+    +--+  |          |     |
  //  |COMPONENT |<------Ci|    |Cj|<------------+     |
  //  |LABELLED i|   |  +--+    +--+  |                |
  //  +----------+   |    |     /||\  |                |
  //  +----------+   |  +--+          |                |
  //  |COMPONENT |<------Ck|<--------------------------+
  //  |LABELLED k|   |  +--+          |
  //  +----------+   |________________|
  //
  // Each component is associated with a label, which is an integer number.
  // In the resulting image, the value of the pixels of the component is this
  // same number. See class qgar::Component for the way a component
  // is represented.
  //
  // The set of components is hierarchically organized as a tree. 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 so-called component table 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.
  //
  // Indexes of valid components are given by list _validCompIdxList.
  // By construction, index 0 (background) is not included in this list.
  // (see section 3)


  // Allocate space for the component table, and initialize it.
  // Each element of this table will be a pointer to the component having
  // the same label as the index of the element.

  _rCompTab.reserve((unsigned int) _finalLabelCnt);
  _rCompTab.insert(_rCompTab.begin(),
                   (unsigned int) _finalLabelCnt + 1,
                   0);

  // Create component 0 (background)
  // and insert it as root of the component tree (initially empty)

  _rCompTree.insertParent
    (new Component(_pCompImg,        // pointer to component image
                   0,                // label
                   0,                // conventional self-inclusion
                   QGE_BW_WHITE,     // color
                   0,                // X top left pixel
                   0,                // Y top left pixel
                   0,                // X top left corner (bounding box)
                   0,                // Y top left corner (bounding box)
                   _colEndIdx,       // X bottom right corner (bounding box)
                   _rowEndIdx ,      // Y bottom right corner (bounding box)
                   _areaPixels[0])); // area

  // Update component table
  _rCompTab[0] = _rCompTree.pRoot();

  // Insert other components
  constructComponentTree(_rCompTree, _rCompTree.pRoot(), _rCompTab);

  // Set root as current node of the resulting tree
  _rCompTree.gotoRoot();

  // ============================================================================
  // END run construction of connected components
  // ============================================================================
}


// -------------------------------------------------------------------
// -------------------------------------------------------------------
// D E S T R U C T O R
// -------------------------------------------------------------------
// -------------------------------------------------------------------


ConnectedComponentsImpl::~ConnectedComponentsImpl()
{
  // VOID
}


// -------------------------------------------------------------------
// -------------------------------------------------------------------
// F U N C T I O N S   W O R K I N G   O N   L A B E L S
// -------------------------------------------------------------------
// -------------------------------------------------------------------


// GET THE VALID LABEL OF (I.E. EQUIVALENT TO) A GIVEN LABEL

int
ConnectedComponentsImpl::validLabel(Component::label_type aLabel)
{
  Component::label_type l = aLabel;

  // The valid label is the smallest equivalent label
  // => just follow the equivalent links until finding no link

  while (_equivLabelTab[l] != Component::_NO_LABEL)
    {
      l = _equivLabelTab[l];
    }

  return l;
}


// -------------------------------------------------------------------
// -------------------------------------------------------------------
// F U N C T I O N S   W O R K I N G   O N   C O M P O N E N T S 
// -------------------------------------------------------------------
// -------------------------------------------------------------------

// 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
ConnectedComponentsImpl::mergePrevAndCurrComponents()
{
  if (_currLabel == Component::_NO_LABEL)

    // ______________________________________________________________
    {
      // CURRENT RUN IS NOT YET LABELLED
      // => merge current run into previous valid component

      // The valid label of the previous run becomes the current label
      _currLabel = validLabel(_prevLabel);

      // The top left pixel of the component should not change
      // No update necessary

      // Update bounding box
      if (_currRunBeginX < _xTopLeft[_currLabel])
        {
          _xTopLeft[_currLabel] = _currRunBeginX;
        }
      if (_currRunEndX > _xBottomRight[_currLabel])
        {
          _xBottomRight[_currLabel] = _currRunEndX;
        }
      _yBottomRight[_currLabel] = _rowIdx;

      // Update area
      _areaPixels[_currLabel] += _currRunEndX - _currRunBeginX + 1;

      // SAVE current run and its label
      _runRowsTab[_rowIdx].push_back(_currRunEndX - _currRunBeginX + 1);
      _labelRowsTab[_rowIdx].push_back(_currLabel);
    }
    // ______________________________________________________________

  else

    {
      // Valid labels of previous and current runs
      Component::label_type prevValidLabel = validLabel(_prevLabel);
      Component::label_type currValidLabel = validLabel(_currLabel);

      if (prevValidLabel == currValidLabel)
        // __________________________________________________________
        {
          // PREVIOUS AND CURRENT RUNS
          // ALREADY BELONG TO THE SAME COMPONENT
          // => nothing to do
          return;
        }
        // __________________________________________________________

      if (prevValidLabel < currValidLabel)

        // __________________________________________________________
        {
          // THE VALID LABEL OF THE PREVIOUS RUN
          // IS SMALLER THAN THE VALID LABEL OF THE CURRENT RUN
          // => merge component of the current run
          //    into component of the previous run

          // Update top left pixel
          if (_yTopLeftPix[currValidLabel] < _yTopLeftPix[prevValidLabel])
            {
              _xTopLeftPix[prevValidLabel] = _xTopLeftPix[currValidLabel];
              _yTopLeftPix[prevValidLabel] = _yTopLeftPix[currValidLabel];
            }

          // Update bounding box
          if (_xTopLeft[currValidLabel] < _xTopLeft[prevValidLabel])
            {
              _xTopLeft[prevValidLabel] = _xTopLeft[currValidLabel];
            }
          if (_yTopLeft[currValidLabel] < _yTopLeft[prevValidLabel])
            {
              _yTopLeft[prevValidLabel] = _yTopLeft[currValidLabel];
            }
          if (_xBottomRight[currValidLabel] > _xBottomRight[prevValidLabel])
            {
              _xBottomRight[prevValidLabel] = _xBottomRight[currValidLabel];
            }
          if (_yBottomRight[currValidLabel] > _yBottomRight[prevValidLabel])
            {
              _yBottomRight[prevValidLabel] = _yBottomRight[currValidLabel];
            }

          // Update area
          _areaPixels[prevValidLabel] += _areaPixels[currValidLabel];
          
          // Update table of equivalent labels
          _equivLabelTab[_currLabel]      = prevValidLabel;
          _equivLabelTab[currValidLabel] = prevValidLabel;

          // Update labels
          _prevLabel = prevValidLabel;
          _currLabel = prevValidLabel;
        }
        // __________________________________________________________

      else

        // __________________________________________________________
        {
          // THE VALID LABEL OF THE CURRENT RUN
          // IS SMALLER THAN THE VALID LABEL OF THE PREVIOUS RUN
          // => merge component of the previous run
          //    into component of the current run

          // Update top left pixel
          if (_yTopLeftPix[prevValidLabel] < _yTopLeftPix[currValidLabel])
            {
              _xTopLeftPix[currValidLabel] = _xTopLeftPix[prevValidLabel];
              _yTopLeftPix[currValidLabel] = _yTopLeftPix[prevValidLabel];
            }

          // Update bounding box
          if (_xTopLeft[prevValidLabel] < _xTopLeft[currValidLabel])
            {
              _xTopLeft[currValidLabel] = _xTopLeft[prevValidLabel];
            }
          if (_yTopLeft[prevValidLabel] < _yTopLeft[currValidLabel])
            {
              _yTopLeft[currValidLabel] = _yTopLeft[prevValidLabel];
            }
          if (_xBottomRight[prevValidLabel] > _xBottomRight[currValidLabel])
            {
              _xBottomRight[currValidLabel] = _xBottomRight[prevValidLabel];
            }
          if (_yBottomRight[prevValidLabel] > _yBottomRight[currValidLabel])
            {
              _yBottomRight[currValidLabel] = _yBottomRight[prevValidLabel];
            }

          // Update area
          _areaPixels[currValidLabel] += _areaPixels[prevValidLabel];

          // Update equivalent labels
          _equivLabelTab[_prevLabel]      = currValidLabel;
          _equivLabelTab[prevValidLabel] = currValidLabel;
          
          // Update labels
          _prevLabel = currValidLabel;
          _currLabel = currValidLabel;
        }
        // __________________________________________________________
    }

}


// -------------------------------------------------------------------
// -------------------------------------------------------------------
// F U N C T I O N S   W O R K I N G   O N   R U N S
// -------------------------------------------------------------------
// -------------------------------------------------------------------

// MOVE TO NEXT RUN IN PREVIOUS ROW

void
ConnectedComponentsImpl::nextPrevRun()
{
  // Increment previous run index
  ++_prevRunIdx;

  // New current run label
  _prevLabel = _labelRowsTab[_prevRowIdx][_prevRunIdx];

  // New current run indexes
  _prevRunBeginX = _prevRunEndX + 1;
  _prevRunEndX   = _prevRunBeginX + _runRowsTab[_prevRowIdx][_prevRunIdx] - 1;

  // New current run color
  _prevColor = qgBWswitch(_prevColor);
}


// MOVE TO NEXT RUN IN CURRENT ROW

void
ConnectedComponentsImpl::nextCurrRun()
{
  if (_ptRow != _ptRowEnd)
    {
      // _____________________________________________________________
      //
      // End of current row is not yet reached

      _currRunBeginX = _currRunEndX + 1;    // new run beginning index
      _currColor = qgBWswitch(_currColor);  // new current color

      // Look for index of new run end (while pixels have the current color)

      while ((*_ptRow == _currColor) && (_ptRow < _ptRowEnd))
        //                               ^^^^^^^^^^^^^^^^^^
        // WARNING: The last pixel pixel is not taken into account
        //          as it is always considered as WHITE
        {
          ++_ptRow;
          ++_currRunEndX;
        }
      
      // WARNING: Last pixel considered as WHITE
      // => If row end is reached and new run is WHITE,
      //    add last pixel to new run

      if ((_ptRow == _ptRowEnd) && (_currColor == QGE_BW_WHITE))
        {
          ++_ptRow;
          ++_currRunEndX;
        }
      // _____________________________________________________________
    }
  else
    {
      // _____________________________________________________________
      //
      // End of current row is reached: Whatever the color
      // of the last pixel is, it is considered as WHITE
      // By construction, current run is BLACK before this point
      // (see above): The last pixel determines a one-pixel WHITE run.

      ++_ptRow;

      // New run includes only 1 pixel and is WHITE
      _currRunEndX += 1;
      _currRunBeginX = _currRunEndX;
      _currColor = QGE_BW_WHITE;
      // _____________________________________________________________
    }

  ++_currRunIdx;                      // New current run index
  _currLabel = Component::_NO_LABEL;  // New run has is not yet labelled
}


// END OF PREVIOUS RUN AND END OF CURRENT RUN COINCIDE
// => PERFORM MOVES ACCORDING TO BLACK- AND WHITE-CONNEXITY
//
// WARNING
// End of current row must be tested before calling this function

void
ConnectedComponentsImpl::prevAndCurrRunsCoincide()
{
  if (_currColor == _prevColor)
    {
      // PREVIOUS RUN AND CURRENT HAVE THE SAME COLOR
      //
      //  end of previous run
      //            v 
      //  -+-+-+-+-+-+-+-+-+-+-
      //   |x|x|x|x|x|y|y|y|y|
      //  -+-+-+-+-+-+-+-+-+-+-
      //   |x|x|x|x|x|y|y|y|y|
      //  -+-+-+-+-+-+-+-+-+-+-
      //            ^
      //  end of current run
      //
      // => just move to next run in previous and current rows

      nextPrevRun();
      nextCurrRun();
    }

  //      b b b               w
  //      b * b             w * w
  //      b b b               w
  //
  //   8-connexity       4-connexity
  //    for BLACK         for WHITE

  else if (_currColor == QGE_BW_WHITE)
    {
      // PREVIOUS RUN IS BLACK AND CURRENT RUN IS WHITE
      //
      //  end of previous run
      //            v 
      //  -+-+-+-+-+-+-+-+-+-+-
      //   |b|b|b|b|b|w|w|w|w|        previous run
      //  -+-+-+-+-+-+-+-+-+-+-       is connex to
      //   |w|w|w|w|w|b|b|b|b|        next current run
      //  -+-+-+-+-+-+-+-+-+-+-
      //            ^
      //  end of current run
      //
      // => move to next run in current row
  
      nextCurrRun();
    }
  else
    {
      // PREVIOUS RUN IS WHITE AND CURRENT RUN IS BLACK
      //
      //  end of previous run
      //            v 
      //  -+-+-+-+-+-+-+-+-+-+-
      //   |w|w|w|w|w|b|b|b|b|        next previous run
      //  -+-+-+-+-+-+-+-+-+-+-       is connex to
      //   |b|b|b|b|b|w|w|w|w|        current run
      //  -+-+-+-+-+-+-+-+-+-+-
      //            ^
      //  end of current run
      //
      // => move to next run in previous row
      
      nextPrevRun();
    }
}


// -------------------------------------------------------------------
// -------------------------------------------------------------------
// FUNCTIONS  WORKING  ON  THE  COMPONENT  TREE
// -------------------------------------------------------------------
// -------------------------------------------------------------------

// CONSTRUCT THE COMPONENT TREE

// Each node represents a component
// Components represented by children nodes are included
// in the component represented by their parent node

// 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 containing pointers to components
//          aCCTab[lab] gives a pointer to the component labelled 'lab'
//          (lab is final valid label)

// _validCompIdxList provides components which are not yet included
// in the tree: Each of its elements is an index of a valid component
// in tables storing component features.

void
ConnectedComponentsImpl::constructComponentTree
  (ConnectedComponents::tree_type& aTree,
   ConnectedComponents::node_type* aPNode,
   std::vector<ConnectedComponents::node_type*>& aCCTab)
{
  // No more component to insert in the tree
  if (_validCompIdxList.size() == 0)
    {
      return;
    }

  // Label of the given component
  Component::label_type parentLabel = (aPNode->accessData())->label();
  
  std::list<int>::iterator itCC = _validCompIdxList.begin();

  while (itCC != _validCompIdxList.end())
    {

    // While there are components
    // ______________________________________________________________
    //
      // Index of the current component
      int ccIdx = *itCC;
      // Valid label of the current component
      Component::label_type lab = _finalLabelTab[ccIdx];

      if (_inLabel[ccIdx] == parentLabel)
        {
          // CURRENT COMPONENT IS INCLUDED IN GIVEN COMPONENT (NODE)
          // => it becomes a child of the given component

          // Instantiation of a new component
          // and insertion in the component tree
          aTree.insertFirstChild
            (new Component(_pCompImg,            // pointer component image
                           lab,                  // label
                           _inLabel[ccIdx],      // comprising component label
                           _color[ccIdx],        // color
                           _xTopLeftPix[ccIdx],  // top left pixel
                           _yTopLeftPix[ccIdx],  //
                           _xTopLeft[ccIdx],     // bounding box
                           _yTopLeft[ccIdx],     //
                           _xBottomRight[ccIdx], //
                           _yBottomRight[ccIdx], //
                           _areaPixels[ccIdx]),  // area
             aPNode);

          // Update component table
          aCCTab[lab] = aPNode->pFirstChild();

          // Remove index of current component from available indexes
          // WARNING: Removal invalidates the iterator that points
          //          to the removed element

          // Save iterator
          std::list<int>::iterator itCCaux = itCC;
          // Increment iterator to get next component index
          ++itCC;
          // Delete used index
          _validCompIdxList.erase(itCCaux);
        }
      else
        {
          // CURRENT COMPONENT IS NOT INCLUDED IN GIVEN COMPONENT (NODE)
          // => just increment iterator to get next component index
          ++itCC;
        }

    } // END while
    // ______________________________________________________________

  
  // Look for children of each new included component

  ConnectedComponents::node_type* pChild = aPNode->pFirstChild();

  while (pChild != 0)
    {
      constructComponentTree(aTree, pChild, aCCTab);
      pChild = pChild->pRSibling();
    }
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------

} // namespace qgar