RP → Classifier

This module implements methods to detect patterns in image regions. Commonly, classification algorithms are divided by the level of classification (pixel or region), and by the interaction of the user (supervised or unsupervised).

Pixel-based algorithms classify individual pixels according to their resemblance to a specific pattern. Region-based algorithms use regions from segmented images, and classify each region to a specific pattern.

Supervised methods uses a predefined typology, given by the user, who supplies samples of each pattern. Unsupervised methods detect an unknown number of patterns, according to their own method.

The available methods in TerraLib are:

• ISOSeg
• Expectation-Maximization - EM

The following methods will be implemented in TerraLib:

• K-Means
• Spectral Angle Mapper - SAM

This is an unsupervised and region-based classification algorithm.

References:

• Leonardo Bins, Guaraci Erthal, Leila Fonseca. Um método de classificação não supervisionada de regiões (A method for unsupervised classification of regions). SIBGRAPI, 1993.

Input:

• Raster
• Vector of polygons
• Acceptance threshold

Step-by-step:

1. It orders regions by area (larger first), and classify the largest region as Cluster 1.
2. All regions similar to this cluster are inserted in Cluster 1, otherwise new Clusters are created.
3. After all regions belong to a cluster, the algorithm merges similar clusters.

The acceptance threshold is the only parameter given by the user, and it indicates the maximum distance between two regions to be clustered together.

Dependencies: Raster, Geometry

To set an ISOSeg classifier, the following parameters are necessary:

// ... (set input data)
 
// link specific parameters with chosen implementation
te::rp::ClassifierISOSegStrategy::Parameters classifierparameters;
classifierparameters.m_acceptanceThreshold = 99.0;
 
algoInputParameters.m_strategyName = "isoseg";
algoInputParameters.setClassifierStrategyParams(classifierparameters);
 
// ... (set output data and start algorithm)

This is an unsupervised and pixel-based classification algorithm.

Input:

• Raster
• The value of “K”, which stands for the number of patterns to find in the image.
• A convergence threshold. When the clusters move less than this threshold, the algorithm stops.
• Maximum number of iterations.

Step-by-step:

1. Define a random solution, creating K values of mean.
2. Classify each pixel according to the closest mean.
3. Calculate new means using the classified pixels.
4. Go back to step 2, or stop depending on the following checks:
   1. Check if the new means are different from the previous iteration, using the convergence threshold.
   2. Check if maximum number of iterations has achieved.

Dependencies: Raster

To set a K-Means classifier, the following parameters are necessary:

// ... (set input data)
 
// link specific parameters with chosen implementation
te::rp::ClassifierKMeansStrategy::Parameters classifierparameters;
classifierparameters.m_K = 5.0; // the algorithm will find 5 patterns in the image
classifierparameters.m_maxIterations = 40;
classifierparameters.m_convergenceThreshold = 5;
 
algoInputParameters.m_strategyName = "kmeans";
algoInputParameters.setClassifierStrategyParams(classifierparameters);
 
// ... (set output data and start algorithm)

This is an unsupervised and pixel-based classification algorithm. Expectation-Maximization (EM) works iteratively by applying two steps: the E-step (Expectation) and the M-step (Maximization). Formally, $\hat{\theta} (t) = \{\mu_j(t), \Sigma_j(t)\}, j = 1, \dots M$ stands for successive parameter estimates. The method aims to approximate $\hat{\theta} (t)$ to real data distribution when $t = 0, 1, \dots$

• The E-step calculates the conditional expectation of the complete {\it a posteriori} probability function.
• The M-step updates the parameter estimation $\hat{\theta} (t)$.

Input:

• Raster
• The value of “K”, which stands for the number of patterns (or clusters) to find in the image.
• The maximum number of iterations (E/M steps) to perform if convergence is not achieved.
• The maximum number of points used to estimate the clusters (default = 1000).
• A convergence threshold ($\varepsilon$). When the clusters change in a value smaller then epsilon, the convergence is achieved.
• The previously estimated means of the clusters (optional).

Step-by-step:

• Each cluster probability, given a certain attribute-vector, is estimated as following:

$$

P(C_j|\mathbf{x}) = \frac{|\Sigma_j(t)|^{-1/2} e^{-\frac{1}{2}(\mathbf{x} - \mu_j(t))^T \Sigma_j(t)(\mathbf{x} - \mu_j(t))} P_j(t)}{\sum_{k = 1}^{M} |\Sigma_k(t)|^{-1/2} e^{-\frac{1}{2}(\mathbf{x} - \mu_k(t))^T \Sigma_k(t)(\mathbf{x} - \mu_k(t))} P_k(t)}

$$

• With such probabilities, one can now estimate the mean, covariance, and the a priori probability for each cluster, at time $t + 1$:

$$

\mu_j(t + 1) = \frac{\sum_{k = 1}^N P(C_j|\mathbf{x}_k) \mathbf{x}_k}{\sum_{k = 1}^N P(C_j|\mathbf{x}_k)}

$$ and $$

\Sigma_j(t + 1) = \frac{\sum_{k = 1}^N P(C_j|\mathbf{x}_k) (\mathbf{x}_k - \mu_j(t)) (\mathbf{x}_k - \mu_j(t))^T}{\sum_{k = 1}^N P(C_j|\mathbf{x}_k)}

$$

$$

P_j(t + 1) = \frac{1}{N} \sum_{k = 1}^N P(C_j|\mathbf{x}_k)

$$

These steps are performed until reaching the convergence, according the following equation: $$

\parallel\theta(t + 1) - \theta(t)\parallel < \varepsilon

$$

where $\parallel.\parallel$, in this implementation, is the Euclidean distance between the vectors $\mathbf{\mu}(t + 1)$ and $\mathbf{\mu}(t)$, and $\varepsilon$ is a threshold chosen by the user.

Dependencies: Raster

To set an EM classifier, the following parameters are necessary:

// ... (set input data)
 
// link specific parameters with chosen implementation
te::rp::ClassifierEMStrategy::Parameters classifierparameters;
classifierparameters.m_numberOfClusters = 5;
classifierparameters.m_maxIterations = 100;
classifierparameters.m_maxInputPoints = 1000;
classifierparameters.m_epsilon = 1.0;
classifierparameters.m_clustersMeans = std::vector<std::vector<double> >();
 
algoInputParameters.m_strategyName = "em";
algoInputParameters.setClassifierStrategyParams(classifierparameters);
 
// ... (set output data and start algorithm)

Description of SAM ???

Dependencies: Raster

To set an EM classifier, the following parameters are necessary:

// ... (set input data)
 
// link specific parameters with chosen implementation
te::rp::ClassifierKMeansStrategy::Parameters classifierparameters;
classifierparameters.m_angle = 0.5; // ???
 
algoInputParameters.m_strategyName = "sam";
algoInputParameters.setClassifierStrategyParams(classifierparameters);
 
// ... (set output data and start algorithm)

This example shows how to perform a classification using ISOSeg algorithm.

// first open the input image
std::map<std::string, std::string> rinfo;
rinfo["URI"] = "input.tif";
te::rst::Raster* rin = te::rst::RasterFactory::open(rinfo);
 
// to apply ISOSeg the image must be segmented (function available in terralib rp examples)
std::vector<te::gm::Polygon*> polygons = SegmentImage(rin);
 
// define classification parameters
 
// input parameters
te::rp::Classifier::InputParameters algoInputParameters;
algoInputParameters.m_inputRasterPtr = rin;
algoInputParameters.m_inputRasterBands.push_back(0);
algoInputParameters.m_inputRasterBands.push_back(1);
algoInputParameters.m_inputRasterBands.push_back(2);
algoInputParameters.m_inputPolygons = polygons;
 
// link specific parameters with chosen implementation
te::rp::ClassifierISOSegStrategy::Parameters classifierparameters;
classifierparameters.m_acceptanceThreshold = 99.0;
 
algoInputParameters.m_strategyName = "isoseg";
algoInputParameters.setClassifierStrategyParams(classifierparameters);
 
// output parameters
std::map<std::string, std::string> orinfo;
orinfo["URI"] = "output-isoseg.tif";
te::rp::Classifier::OutputParameters algoOutputParameters;
algoOutputParameters.m_rInfo = orinfo;
algoOutputParameters.m_rType = "GDAL";
 
// execute the algorithm
te::rp::Classifier classifierinstance;
 
if(!classifierinstance.initialize(algoInputParameters))
  throw;
if(!classifierinstance.execute(algoOutputParameters))
  throw;
 
// clean up
delete rin;