ISOData.h

Go to the documentation of this file.

/*  Copyright (C) 2008 National Institute For Space Research (INPE) - Brazil.

    This file is part of the TerraLib - a Framework for building GIS enabled applications.

    TerraLib is free software: you can redistribute it and/or modify
    it under the terms of the GNU Lesser General Public License as published by
    the Free Software Foundation, either version 3 of the License,
    or (at your option) any later version.

    TerraLib 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.

    You should have received a copy of the GNU Lesser General Public License
    along with TerraLib. See COPYING. If not, write to
    TerraLib Team at <terralib-team@terralib.org>.
 */

/*!
  \file terralib/classification/ISOData.h

  \brief ISOData strategy for classification.
*/

#ifndef __TERRALIB_CLASSIFICATION_INTERNAL_ISODATA_H
#define __TERRALIB_CLASSIFICATION_INTERNAL_ISODATA_H

// TerraLib
#include "../common/AbstractParameters.h"
#include "../common/MatrixUtils.h"
#include "../common/progress/TaskProgress.h"
#include "Adaptors.h"
#include "Config.h"
#include "Exception.h"

// STL
#include <vector>
#include <map>

namespace te
{
  namespace cl
  {
    /*!
      \class ISOData
      \brief ISOData strategy for an unsupervised pixel-based classification algorithm.
      \note Based on Reference: IsoData Algorithm - Pattern Recognition Principles - Rafael Gonzalez, Julius T. Tou - Addison Wesley Publishing Company - 1974.
    */

    class TECLEXPORT ISOData
    {
      public:

        /*!
          \class Parameters
          \brief Classifier Parameters
        */
        class TECLEXPORT Parameters : public te::common::AbstractParameters
        {
          public:

            unsigned int m_clustersNumber; //!< Desired number of clusters (This is a mean number. Final clusters number can go from 0 up to k+(k/2). Minimum:2, default:2).
            unsigned int m_maxIterationsNumber; //!< Maximum number of iterations (minimum:1, default:0=automatic).
            unsigned int m_maxMergesPerIteration;  //!< Maximum number of clusters merges per iteration (zero=automatic, defaul:1 ).
            unsigned int m_maxSplitsPerIteration;  //!< Maximum number of clusters splits per iteration (zero=automatic, defaul:1 ).
            double m_minClusterSizePercent;  //!< Minimum cluster size (percentual proportion related to the total input elments size. Valid values: from zero up to 100, default:0).
            double m_stdDevSplitThreshold;  //!< A standart deviation threshold to split clusters (lower values tend to create more clusters by splitting. Valid values: zero or positive values. Defaul: 0.1).
            double m_mergeDistThreshold;  //!< A distance treshold to control the merge process (higher values will allow to merge more clusters. Valid values: zero or positive values. Default:0.1 ).
            
            Parameters();

            ~Parameters();
            //overload
            const Parameters& operator=(const Parameters& params);

            //overload
            void reset();

            //overload
            AbstractParameters* clone() const;
        };

        /*!
          \class ClusterData
          \brief Cluster data
        */
        class TECLEXPORT ClusterData
        {
          public:

            /*!
              \typedef ClusterLabelT Cluster label type definition.
            */
            typedef unsigned int ClusterLabelT;

            double m_avgDistToClusterCenter;  //!< Average distance from all samples to the cluster center.
            unsigned int m_size; //!< Cluster size (elements number).
            ClusterLabelT m_label; //!< Cluster label.
            std::vector< double > m_means; //!< Cluster means (one for each cluster feature dimention).
            std::vector< double > m_sums; //!< Sums of all cluster pixel values(one sum for each cluster feature dimention).
            std::vector< double > m_stdDevs; //!< Cluster standart deviations (one for each cluster feature dimention).

            ClusterData();
            ~ClusterData();
        };

        ISOData();

        ~ISOData();

        /*!
          \brief Initialize this classifier instance with new parameters.
          \param params New initialization parameters.
        */
        bool initialize(const Parameters& params);

        /*!
          \brief Classify an input iterated data and save the result on the output iterated data.
          \param input Input data to be classified.
          \param attributesIndices The attributes indexes to process from the iterated train data.
          \param inputNoDataValues A vector of no-data values for each attribute dimension or an empty vector if no-data values are not used.
          \param output Output classified data.
          \param outputIndex The output attribute index.
          \param outputNoDataValue A output label value to use when dealing with input no-data.
          \param enableProgressInterface Enable/disable the use of a progress interface.
          \param clustersDataPtr A pointer to a vector where the current clusters data will be storer or a null pointer.
        */
        bool classify( const InputAdaptor< double >& input,
                      const std::vector<unsigned int>& attributesIndices,
                      const std::vector< double >& inputNoDataValues,
                      InputOutputAdaptor< ClusterData::ClusterLabelT >& output,
                      const unsigned int outputIndex,
                      const ClusterData::ClusterLabelT outputNoDataValue,
                      const bool enableProgressInterface,
                      std::vector< ClusterData >* clustersDataPtr );

      protected:

        /*!
          \typedef ClustersContainerT Clusters container type definition.
        */
        typedef std::map< ClusterData::ClusterLabelT, ISOData::ClusterData >
          ClustersContainerT;

        bool m_isInitialized;    //!< True if this instance is initialized.
        Parameters m_parameters; //!< Internal execution parameters.

        /*! \brief Reset this instance to its initial state */
        void reset();

        /*!
          \brief Initialize clusters.
          \param input Input data to be classified.
          \param attributesIndices The attributes indexes to process from the iterated train data.
          \param inputNoDataValues A vector of no-data values for each attribute dimension or an empty vector if no-data values are not used.
          \param clustersMap Clusters map.
          \param nextAvaliableClusterLabel Reference to the global clusters labels counter.
          \param inputElementsOffsetsAndGains Elements offsets (first) and gains (second).
          \note Updated clusters members: ClusterData::m_means, ClusterData::m_label.
          \note Output = ( input + offset ) * gain;
        */
        bool initializeClusters( const InputAdaptor<double>& input,
          const std::vector<unsigned int>& attributesIndices,
          ClustersContainerT& clustersMap,
          ClusterData::ClusterLabelT& nextAvaliableClusterLabel,
          const std::vector<double>& inputNoDataValues,
          std::vector< std::pair< double, double > >& inputElementsOffsetsAndGains ) const;

        /*!
          \brief Classify each element following clusers centers.
          \param input Input data to be classified.
          \param attributesIndices The attributes indexes to process from the iterated train data.
          \param inputNoDataValues A vector of no-data values for each attribute dimension or an empty vector if no-data values are not used.
          \param output Output classified data.
          \param outputIndex The output attribute index.
          \param clustersMap Clusters map.
          \param outputNoDataValue Output no-data value.
          \param inputElementsOffsetsAndGains Elements offsets (first) and gains (second).
          \note Only the member ClusterData::m_means is used for this operation.
          \note Valid updated members after: ClusterData::m_label, ClusterData::m_means, ClusterData::m_sums, ClusterData::m_size
        */
        bool classifyElements( const InputAdaptor<double>& input,
          const std::vector<unsigned int>& attributesIndices,
          const std::vector<double>& inputNoDataValues,
          ClustersContainerT& clustersMap,
          InputOutputAdaptor<unsigned int>& output,
          const unsigned int outputIndex,
          const unsigned int outputNoDataValue,
          const std::vector< std::pair< double, double > >& inputElementsOffsetsAndGains ) const;

        /*!
          \brief Remove too mall clusters following the current parameters.
          \param inputElelementsCount Input data elements counte.
          \param clustersMap Clusters map.
          \note Only the member ClusterData::m_size is used for this operation.
        */
        bool removeSmallClusters(
          const unsigned int inputElelementsCount,
          ClustersContainerT& clustersMap ) const;

        /*!
          \brief Update clusters statistical data.
          \param input Input data to be classified.
          \param attributesIndices The attributes indexes to process from the iterated train data.
          \param inputNoDataValues A vector of no-data values for each attribute dimension or an empty vector if no-data values are not used.
          \param output Output classified data.
          \param outputIndex The output attribute index.
          \param clustersMap Clusters map.
          \param inputElementsOffsetsAndGains Elements offsets (first) and gains (second).
          \note Used clusters members: ClusterData::m_label, ClusterData::m_means, ClusterData::m_size
          \note Updated clusters members: ClusterData::m_avgDistToClusterCenter, ClusterData::m_stdDevs.
        */
        bool updateClustersStats(
          const InputAdaptor<double>& input,
          const std::vector<unsigned int>& attributesIndices,
          const std::vector<double>& inputNoDataValues,
          ClustersContainerT& clustersMap,
          const InputOutputAdaptor<unsigned int>& output,
          const unsigned int outputIndex,
          const std::vector< std::pair< double, double > >& inputElementsOffsetsAndGains ) const;

        /*!
          \brief Split clusters.
          \param clustersMap Clusters map.
          \param inputElementsCount Input data total elements number.
          \param maxNumberOfSplits Maximum number of splits.
          \param nextAvaliableClusterLabel Reference to the global clusters labels counter.
          \note Only the members ClusterData::m_label, ClusterData::m_means, ClusterData::m_stdDevs, ClusterData::m_size, ClusterData::m_avgDistToClusterCenter are used for this operation.
          \note Only the following members will be valid after splitting: ClusterData::m_means, ClusterData::m_label.
        */
        bool splitClusters(
          const unsigned int inputElementsCount,
          const unsigned int maxNumberOfSplits,
          ClusterData::ClusterLabelT& nextAvaliableClusterLabel,
          ClustersContainerT& clustersMap ) const;

        /*!
          \brief Merge clusters.
          \param clustersMap Clusters map.
          \param mergeDistThreshold A distance treshold to control the merge process (higher values will allow the merge more clusters. Valid values: zero or positive values ).
          \param maxNumberOfMerges Maximum number of merges.
          \note Only the members ClusterData::m_label, ClusterData::m_means, ClusterData::m_size are used for this operation.
          \note Only the following members will be valid after merging: ClusterData::m_means, ClusterData::m_label, ClusterData::m_size.
        */
        static bool mergeClusters(
          const double mergeDistThreshold,
          const unsigned int maxNumberOfMerges,
          ClustersContainerT& clustersMap );

        static void printClusters( const ClustersContainerT& clustersMap );
        
        /*!
          \brief Recode clusters labels to be in range zero up to the number of clusters - 1.
          \param clustersMap Clusters map.
        */
        static void recodeClustersLabels( ClustersContainerT& clustersMap );
    };

  } // end namespace cl
}  // end namespace te

#endif // __TERRALIB_CLASSIFICATION_INTERNAL_ISODATA_H