ConnectedComponents.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   ConnectedComponents.C
 * @brief  Implementation of class qgar::ConnectedComponents.
 *
 *         See file ConnectedComponents.H for the interface.
 *
 * @author <a href="mailto:qgar-develop@loria.fr?subject=Qgar fwd Gérald Masini">Gérald Masini</a>
 * @date   April 21, 2004  12:58
 * @since  Qgar 2.1.1
 */


// STL
#include <deque>
#include <list>
#include <vector>
// QGAR
#include <qgarlib/Component.H>
#include <qgarlib/ConnectedComponents.H>
#include <qgarlib/ConnectedComponentsImpl.H>
#include <qgarlib/GenImage.H>



namespace qgar
{

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


// CONSTRUCT FROM GIVEN BINARY IMAGE

ConnectedComponents::ConnectedComponents(const BinaryImage& aBinImg)

  : _componentImg(ConnectedComponents::image_type(aBinImg.width(),
                                                  aBinImg.height()))

{
  // Initialize data in order to run the construction of components
  ConnectedComponentsImpl ccImpl(aBinImg,
                                 &_componentImg,
                                 _componentTree,
                                 _componentTab);

   // Run the construction of connected components
  ccImpl.run();
}


// COPY CONSTRUCTOR
// WARNING: Perform a deep copy

ConnectedComponents::ConnectedComponents(const ConnectedComponents& aCC)

  : _componentImg(aCC._componentImg),
    _componentTree(aCC._componentTree),
    _componentTab((aCC._componentTab).size(), 0)

{
  // Components are not duplicated as data stored in tree nodes
  // are pointers to components
  // => effective duplication of components
  //    and subsequent updating of the component table

  PRIVATEcopyCC((aCC._componentTree).pRoot(), _componentTree.pRoot());
}


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


ConnectedComponents::~ConnectedComponents()
{
  // Delete components

  for(std::vector<ConnectedComponents::node_type*>::iterator itN
        = _componentTab.begin();
      itN != _componentTab.end();
      ++itN)
    {
      delete (*itN)->data();
    }
}


// -------------------------------------------------------------------
// -------------------------------------------------------------------
// R E C O N S T R U C T   B I N A R Y   I M A G E S 
// -------------------------------------------------------------------
// -------------------------------------------------------------------


// RECONSTRUCT A BINARY IMAGE FROM GIVEN LABELS
// A pixel of the resulting image is BLACK if it belongs to a black
// component whose label is in the set of given labels.
// Given labels out of the range of current labels are ignored.

BinaryImage*
ConnectedComponents::makeBinaryImg
  (const std::vector<Component::label_type>& aLabSet)
{
  // Create the resulting image
  BinaryImage* pImgBin = new BinaryImage(_componentImg.width(),
                                         _componentImg.height());

  // Pointers to pixels maps
  Component::label_type*   pMapCC  = _componentImg.pPixMap();
  BinaryImage::value_type* pMapBin = pImgBin->pPixMap();

  // Current label and color
  Component::label_type currLab = Component::_NO_LABEL;
  QGEbw currColor;

  // Number of pixels of both images
  int size = _componentImg.width() * _componentImg.height();

  // For each pixel of the component image

  for (int iCnt = 0 ; iCnt< size ; ++iCnt, ++pMapCC, ++pMapBin)
    {
      if (*pMapCC != currLab)
        {
          // The new pixel belongs to a new component
          
          currLab = *pMapCC;

          std::vector<Component::label_type>::const_iterator it =
            find(aLabSet.begin(), aLabSet.end(), currLab);

          if (   (it == aLabSet.end())
              || ((*this)[currLab].color() == QGE_BW_WHITE))
            {
              // Current label does not belong to the given set
              // or belongs to a WHITE component
              currColor = QGE_BW_WHITE;
            }
          else
            {
              // Current label belongs to a BLACK component
              currColor = QGE_BW_BLACK;
            }
        }

      // Set the corresponding pixel of the resulting image
      // to current color
      *pMapBin = currColor;
    }

  // Return a pointer to the resulting image
  return pImgBin;
}


// -------------------------------------------------------------------
// -------------------------------------------------------------------
// O P E R A T O R S
// -------------------------------------------------------------------
// -------------------------------------------------------------------


// ASSIGNMENT

ConnectedComponents&
ConnectedComponents::operator=(const ConnectedComponents& aCC)
{
  // Are left hand side and right hand side different objects?
  if (this != &aCC)
    {
      // Copy component tree and component table
      _componentImg  = aCC._componentImg;
      _componentTree = aCC._componentTree;
      _componentTab  = aCC._componentTab;

      // The tree of the given CC image is duplicated, but the data
      // pointed by nodes (i.e. components) are not

      // Effective duplication of components
      // and subsequent updating of the component table
      PRIVATEcopyCC((aCC._componentTree).pRoot(),
                    _componentTree.pRoot());
    }

  return *this;
}


// -------------------------------------------------------------------
// -------------------------------------------------------------------
// A U X I L I A R I E S
// -------------------------------------------------------------------
// -------------------------------------------------------------------

// Copy components stored in tree whose root is node IN
// and store them in corresponding nodes of tree whose root is node OUT.
// WARNING: Both trees must have the same structure (the tree including
// node OUT is supposed to be a copy of the tree including node IN).

void
ConnectedComponents::PRIVATEcopyCC(ConnectedComponents::node_type* aPNodeIn,
                                   ConnectedComponents::node_type* aPNodeOut)
{
  if (aPNodeIn != 0)
    {
      // Copy current component
      Component* cc = new Component(*(aPNodeIn->data()));

      // Store copy and update component table
      aPNodeOut->setData(cc);
      _componentTab[cc->label()] = aPNodeOut;

      // Copy children and siblings
      PRIVATEcopyCC(aPNodeIn->pFirstChild(), aPNodeOut->pFirstChild());
      PRIVATEcopyCC(aPNodeIn->pRSibling(),   aPNodeOut->pRSibling());
    }
}

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

} // namespace qgar