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


//////////////////////////////////////////////////////////////////////////////
#include <iostream>
//////////////////////////////////////////////////////////////////////////////

// STD
#include <cmath>
// STL
#include <list>
// QGAR
#include <qgarlib/BoundingBox.H>
#include <qgarlib/Component.H>
#include <qgarlib/GenImage.H>
#include <qgarlib/Maer.H>
#include <qgarlib/primitives.H>



namespace qgar
{

// -------------------------------------------------------------------
// -------------------------------------------------------------------
// S P E C I A L   L A B E L S   (STATIC)
// -------------------------------------------------------------------
// -------------------------------------------------------------------


// MAXIMUM LABEL

const Component::label_type
Component::_MAX_LABEL = std::numeric_limits<Component::label_type>::max();


// NO LABEL

const Component::label_type
Component::_NO_LABEL = -1;


// -------------------------------------------------------------------
// -------------------------------------------------------------------
// AUXILIARY DATA FOR CONTOUR FOLLOWING (STATIC)
// -------------------------------------------------------------------
// -------------------------------------------------------------------


// TABLE FOR X COORDINATES INCREMENTS

const int Component::_s_incr_x[14] =
{
  -1, // W  (N  entry)
  -1, // NW (NE entry)
   0, // N  (E  entry)
   1, // NE (SE entry)
   1, // E  (S  entry)
   1, // SE (SW entry)
   0, // S  (W  entry)
  -1, // SW (NW entry)
  -1, // W
  -1, // NW
   0, // N
   1, // NE
   1, // E
   1  // SE
};


// TABLE FOR Y COORDINATES INCREMENTS

const int Component::_s_incr_y[14] =
{
   0, // W  (N  entry)
  -1, // NW (NE entry)
  -1, // N  (E  entry)
  -1, // NE (SE entry)
   0, // E  (S  entry)
   1, // SE (SW entry)
   1, // S  (W  entry)
   1, // SW (NW entry)
   0, // W
  -1, // NW
  -1, // N
  -1, // NE
   0, // E
   1  // SE
};


// TABLE FOR NEW CONTOUR DIRECTIONS

const int Component::_s_new_dir[14] =
{
  6, // W
  7, // NW
  0, // N
  1, // NE
  2, // E
  3, // SE
  4, // S
  5, // SW
  6, // W
  7, // NW
  0, // N
  1, // NE
  2, // E
  3  // SE
};


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


// DEFAULT CONSTRUCTOR.

Component::Component()
{
  // VOID
}

// CONSTRUCT FROM FULL DATA

Component::Component(GenImage<Component::label_type>* aPCompImg,
                     int   aLabel,
                     int   anInLabel,
                     QGEbw aBW,
                     int   aXTopLeftPix,
                     int   aYTopLeftPix,
                     int   aXTopLeft,
                     int   aYTopLeft,
                     int   aXBottomRight,
                     int   aYBottomRight,
                     int   anAreaPixels)

  : _pCompImg    (aPCompImg),
    _label       (aLabel),
    _inLabel     (anInLabel),
    _color       (aBW),
    _xTopLeftPix (aXTopLeftPix),
    _yTopLeftPix (aYTopLeftPix),
    _boundingBox (aXTopLeft, aYTopLeft, aXBottomRight, aYBottomRight),
    _areaPixels  (anAreaPixels),
    _maer(0)

{
  // VOID
}

// COPY CONSTRUCTOR.

Component::Component(const Component& aCComp)

  : _pCompImg    (aCComp._pCompImg),
    _label       (aCComp._label),
    _inLabel     (aCComp._inLabel),
    _color       (aCComp._color),
    _xTopLeftPix (aCComp._xTopLeftPix),
    _yTopLeftPix (aCComp._yTopLeftPix),
    _boundingBox (aCComp._boundingBox),
    _areaPixels  (aCComp._areaPixels)

{
  // Copy MAER if and only if it is computed
  if (_maer != 0)
    {
      _maer = new Maer(*(aCComp._maer));
    }
}

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


Component::~Component()
{
//////////////////////////////////////////////////////////////////////////////
//  std::cout << "Component> Destruction de la composante " << _label << std::endl;
//////////////////////////////////////////////////////////////////////////////

  delete _maer;
}


// -------------------------------------------------------------------
// -------------------------------------------------------------------
// C O O R D I N A T E S
// -------------------------------------------------------------------
// -------------------------------------------------------------------


// GET BOUNDING BOX

const BoundingBox&
Component::accessBoundingBox() const
{
  return _boundingBox;
}

// GET A COPY OF THE BOUNDING BOX

BoundingBox
Component::boundingBox() const
{
  return _boundingBox;
}

// GET DENSITY WITH REGARD TO THE BOUNDING BOX

double
Component::densityBox() const
{
  double a = _boundingBox.area();

  if (a < 1.)
    {
      // When the area is less than 1, it should mean that the component
      // is a degenerated one, with a null length and/or width
      return 1.;
    }
  else
    {
      return ((double) _areaPixels) / a;
    }
}


// -------------------------------------------------------------------
// -------------------------------------------------------------------
// A C C E S S   T O   M A E R   (MINIMUM-AREA ENCASING RECTANGLE)
// -------------------------------------------------------------------
// -------------------------------------------------------------------


// GET THE MAER

const Maer&
Component::accessMaer()
{
  if (_maer == 0)
    {
      PRIVATEcomputeMaer();
    }

  return *_maer;
}

// GET A COPY OF THE MAER

Maer
Component::maer()
{
  if (_maer == 0)
    {
      PRIVATEcomputeMaer();
    }

  return *_maer;
}

// GET MAER AREA

int
Component::maerAreaPixels()
{
  if (_maer == 0)
    {
      PRIVATEcomputeMaer();
    }

  return _maerAreaPixels;
}

// GET DENSITY WITH REGARD TO THE MAER

double
Component::densityMaer()
{
  if (_maer == 0)
    {
      PRIVATEcomputeMaer();
    }

  return ((double) _areaPixels) / ((double) _maerAreaPixels);
}


// -------------------------------------------------------------------
// -------------------------------------------------------------------
// A C C E S S   T O   T H E   C O N T O U R
// -------------------------------------------------------------------
// -------------------------------------------------------------------


// GET A POINTER TO THE COMPONENT CONTOUR

const std::list<DPoint>& 
Component::accessContour()
{
  if (_contour.empty())
    {
      PRIVATEcomputeContour();
    }

  return _contour;
}

// GET A COPY OF THE COMPONENT CONTOUR

std::list<DPoint>
Component::contour()
{
  if (_contour.empty())
    {
      PRIVATEcomputeContour();
    }

  return _contour;
}


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


Component&
Component::operator=(const Component& aCComp)
{
  // Are left hand side and right hand side different objects?
  if (this != &aCComp)
    {
      _pCompImg    = aCComp._pCompImg;
      _label       = aCComp._label;
      _inLabel     = aCComp._inLabel;
      _color       = aCComp._color;
      _xTopLeftPix = aCComp._xTopLeftPix;
      _yTopLeftPix = aCComp._yTopLeftPix;
      _boundingBox = aCComp._boundingBox;
      _areaPixels  = aCComp._areaPixels;

      // Copy MAER if it is computed
      if (_maer != 0)
        {
          _maer = new Maer(*(aCComp._maer));
        }
    }

  return *this;
}


// -------------------------------------------------------------------
// -------------------------------------------------------------------
// C O N S T R U C T   T H E   C O N T O U R   (PRIVATE FUNCTION)
// -------------------------------------------------------------------
// -------------------------------------------------------------------


// Compute the component contour

void
Component::PRIVATEcomputeContour()
{
  if (_label == 0)

  // _________________________________________________________________
  //
  // WARNING: COMPONENT 0 (BACKGROUND) IS A PARTICULAR CASE
    {
      _contour.push_back(DPoint((double) _boundingBox.xTopLeft(),
                                (double) _boundingBox.yTopLeft()));
      _contour.push_back(DPoint((double) _boundingBox.xBottomRight(),
                                (double) _boundingBox.yTopLeft()));
      _contour.push_back(DPoint((double) _boundingBox.xBottomRight(),
                                (double) _boundingBox.yBottomRight()));
      _contour.push_back(DPoint((double) _boundingBox.xTopLeft(),
                                (double) _boundingBox.yBottomRight()));
    }
  // _________________________________________________________________


  else if (_areaPixels != 1)

  // _________________________________________________________________
  //
  // The component is not a single point
  // WARNING: Contour following does not work if component is a single
  // point, as starting point (the point constituting the component)
  // cannot be reached again when searching for a new contour point
  // around the starting point!
  // _________________________________________________________________
  //

    {
      // Component image width
      int width = _pCompImg->width();

      // Compute offset table to get pointers to 8-connexity neighbors
      // See NOTE (1) in comments of BLOCK-WHILE
      int mapPtOffset[14];
      for (int idx = 0 ; idx < 14 ; ++idx)
        {
          mapPtOffset[idx] = _s_incr_y[idx] * width;
        }

      // Pointer to the first contour point
      Component::label_type* pMap =
        _pCompImg->pPixMap() + (_yTopLeftPix * width) + _xTopLeftPix;

      // Mark this first point
      (*pMap) = _NO_LABEL;

      // Because of the way the component is constructed, current
      // direction can always be EAST (i.e. 2) in the beginning
      int currDir = 2;

      // Coordinates of the current contour point
      int currX = _xTopLeftPix;
      int currY = _yTopLeftPix;

      bool notBackToStartingPoint = true;

      while (notBackToStartingPoint)
        // WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
        // BLOCK-WHILE
        // while the new contour point is not the starting point
        // WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
        {

          for (int iCnt = 0 ; iCnt < 8 ; ++iCnt)
            //           ^^^        ^^^
            // for each direction around the current point,
            // from NORTH (0) to NORTH-WEST (7)
            {
            // COORDINATES AND DIRECTION COMPUTATION

            //  +---+---+---+
            //  |   | 1 | 2 |
            //  +---+---+---+
            //  | 7 | *-->3 |
            //  +---+---+---+
            //  | 6 | 5 | 4 |
            //  +---+---+---+
            //
            //  The outside of the component is always on the left 
            //  when moving along the contour direction. The figure
            // above gives an example: When following a contour in
            // the EAST direction, the first new possible contour
            // point (1) is left-perpendicular to the direction,
            // i.e. at NORTH of the current point (*), the second
            // point (2) is then at NORTH-EAST, and so on.

            //               0  1  2  3  4  5  6  7  8  9 10 11 12 13
            //             +--+--+--+--+--+--+--+--+--+--+--+--+--+--+
            // _s_incr_x   |-1|-1| 0| 1| 1| 1| 0|-1|-1|-1| 0| 1| 1| 1|
            //             +--+--+--+--+--+--+--+--+--+--+--+--+--+--+
            //
            //             +--+--+--+--+--+--+--+--+--+--+--+--+--+--+
            // _s_incr_y   | 0|-1|-1|-1| 0| 1| 1| 1| 0|-1|-1|-1| 0| 1|
            //             +--+--+--+--+--+--+--+--+--+--+--+--+--+--+
            //             +--+--+--+--+--+--+--+--+--+--+--+--+--+--+
            // mapPtOffset | 0|-w|-w|-w| 0| w| w| w| 0|-w|-w|-w| 0| w|
            //             +--+--+--+--+--+--+--+--+--+--+--+--+--+--+
            // initial       N NE  E SE  S SW  W NW
            // incrIdx
            //
            //             +--+--+--+--+--+--+--+--+--+--+--+--+--+--+
            // _s_new_dir  | 6| 7| 0| 1| 2| 3| 4| 5| 6| 7| 0| 1| 2| 3|
            //             +--+--+--+--+--+--+--+--+--+--+--+--+--+--+
            // newDir        W NW  N NE  E SE  S SW  W NW  N NE  E SE
            //               new contour directions
            //
            // The _s_incr_x (resp. y) table contains the X (resp. Y)
            // increment to get the X (resp. Y) coordinates of the 7
            // possible next contour points (points 1 to 7 on 1st
            // figure) from the X (resp. Y) coordinate of the current
            // point (*). The current contour direction (EAST on 1st
            // figure) determines the first index to enter the tables.
            //
            // Once a new contour point is found, table _s_new_dir
            // gives the corresponding new contour direction, using
            // the index corresponding to the new contour point in
            // table _s_incr_x or _s_incr_y. For example, if the new
            // contour point is at position 5 (on 1st figure), the
            // corresponding index in table _s_new_dir is 2 (for EAST,
            // current contour direction) + 4 (index of point at
            // position 5 among the neighbors of central point) = 6,
            // which gives SOUTH as new contour direction.

            // -------------------------------------------------------
            // NOTE (1) To avoid multiplications, table _s_incr_y
            // is substituted by table mapPtOffset, in which each
            // element is multiplied by the width (w) of the image.
            // -------------------------------------------------------

              // Index to look for possible contour points around the
              // current point (points 1 to 7 on the example above),
              // using tables _s_incr_x and _s_incr_y
              int incrIdx = currDir + iCnt;

              // Pointer to the point corresponding to this direction
              // in the pixel map of the component image
              Component::label_type* newPMap
                = pMap + mapPtOffset[incrIdx] + _s_incr_x[incrIdx];
              //         ********************
              // See NOTE (1) in comments above

              if (*newPMap == _NO_LABEL)
                {
                  //__________________________________________________
                  //
                  // THE NEW POINT IS MARKED
                  // => starting point is reached

                  // New contour direction corresponding to the point
                  // under consideration (see figure above)
                  int newDir = _s_new_dir[incrIdx];

                  if (currDir != newDir)
                    {
                      // Contour direction is changed => store the current
                      // point in the list representing the contour
                      _contour.push_back(DPoint((double) currX, (double) currY));
                    }

                  // Check that the starting point is not recorded
                  // in the contour before storing it
                  if (   ((int) (_contour.front()).x() != _xTopLeftPix)
                      || ((int) (_contour.front()).y() != _yTopLeftPix) )
                    {
                      _contour.push_front
                        (DPoint((double) _xTopLeftPix, (double) _yTopLeftPix));
                    }

                  // Unmark the starting point
                  (*newPMap) = _label;

                  // Leave loops
                  notBackToStartingPoint = false;
                  break;
                  //__________________________________________________
                }
              else if (*newPMap == _label)
                {
                  //__________________________________________________
                  //
                  // THE NEW POINT IS LABELLED LIKE THE COMPONENT
                  // => new contour point
                  pMap = newPMap;

                  // New contour direction corresponding to the point
                  // under consideration (see figure above)
                  int newDir = _s_new_dir[incrIdx];

                  if (currDir != newDir)
                    {
                      // Contour direction is changed => store the current
                      // point in the list representing the contour
                      _contour.push_back(DPoint((double) currX, (double) currY));

                      // Set new contour direction
                      currDir = newDir;
                    }

                  // Update coordinates of the new contour point
                  currX += _s_incr_x[incrIdx];
                  currY += _s_incr_y[incrIdx];

                  // Leave loop
                  break;
                  //__________________________________________________
                }

            } // END for

        }
        // WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
        // END BLOCK-WHILE
        // back to the starting point
        // WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
    }

  else

  // _________________________________________________________________
  //
  // The component is a single point
  // _________________________________________________________________
  //

    {
      _contour.push_back(DPoint((double) _boundingBox.xTopLeft(),
                                (double) _boundingBox.yTopLeft()));
    }

  // _________________________________________________________________
  //
  // END if
  // _________________________________________________________________
  //

} // END Component::PRIVATEcomputeContour()


// -------------------------------------------------------------------
// -------------------------------------------------------------------
// M A E R (PRIVATE FUNCTION)
// -------------------------------------------------------------------
// -------------------------------------------------------------------


// Compute the MAER (Minimum-Area Encasing Rectangle)

void
Component::PRIVATEcomputeMaer()
{
  // Construct the maer
  _maer = new Maer(accessContour());

  // WARNING: The computation of the MAER is performed in the continuous
  // 2D space, while the computation of connected components features is
  // performed in the 2D discrete space. In particular, a component area
  // is provided in terms of a number of pixels, but its MAER area is not
  // => calculate an APPROXIMATION of the MAER area in pixels,
  //    by adding 1 to the width and length of the MAER

  const std::list<DPoint>& lv = _maer->accessVertices();
  std::list<DPoint>::const_iterator itV1 = lv.begin();
  std::list<DPoint>::const_iterator itV2 = itV1;
  ++itV2;

  double dx12 = itV1->x() - itV2->x();
  double dy12 = itV1->y() - itV2->y();

  ++itV1;
  ++itV2;
  double dx23 = itV1->x() - itV2->x();
  double dy23 = itV1->y() - itV2->y();

  _maerAreaPixels = (int) std::ceil(  (hypot(dx12, dy12) + 1.)
                                    * (hypot(dx23, dy23) + 1.) );
}

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

} // namespace qgar