Opened 7 years ago

Last modified 12 months ago

#1908 new enhancement

Request for a native GRASS implementation of the ISODATA clustering algorithm

Reported by: Nikos Alexandris Owned by: grass-dev@…
Priority: minor Milestone: 7.6.2
Component: Imagery Version: unspecified
Keywords: clustering, k-means, i.cluster, isodata Cc:
CPU: Unspecified Platform: Unspecified

Description

The ISODATA clustering algorithm

The ISODATA algorithm is a(nother) modification of the k-means algorithm. Roughly, the difference lies in that the former allows for user-defined number of clusters while the latter pre-assumes a fixed number of clusters.

Quoting [details from A Fast Implementation of the ISODATA Clustering Algorithm][1]:

...the algorithm tries to find the best set of cluster centers for a given set of points in d-dimensional space through an iterative approach until some maximum number of iterations are performed. It uses a number of different heuristics to determine when to merge or split clusters. [[BR]]
 
At a high level, in each iteration of the algorithm the following takes place: points are assigned to their closest cluster centers, cluster centers are updated to be the centroid of their associated points, clusters with very few points are deleted, large clusters satisfying some heuristics are split, and small clusters satisfying other heuristics are merged. The algorithm continues until maximum number of iterations are performed. Here we go over the algorithm in more detail. See the related publications below for further information. [[BR]]

Clustering in GRASS

The current clustering implementation in GRASS GIS' module i.cluster is also another modification of the k-means clustering algorith. One difference, from an end-user point-of-view, is that i.cluster exptects at least two input raster maps (variables) in order to run.

Differences for end-users

The ISODATA algorithm, contrary to i.cluster, can run on a single raster map (variable) which makes it an easy and quick alternative for pixel-based unsupervised image classification tasks.

This makes it, be it a good or bad choice, attractive for many (commercial) remote sensing projects.

Proprietary Implementations

Most proprietary & commercial GIS & Remote Sensing packages have integrated an option for the ISODATA unsupervised (and pixel-based) classification algorithm. Some sources below:

  • Iso Cluster Unsupervised Classification (Spatial Analyst) [2] in ArcGIS
  • ISODATA Clustering [3] in ERDAS
  • Classification Tutorial (PDF) [4] for ENVI
  • Technical Specifications, Geomatica Core (PDF [5] about Geomatica
  • Idrisi Selva Technical Specifications (PDF) [6] about Idrisi Selva

FOSS Implementations

Some FOSS implementations of the ISODATA clustering/classification algorithm include:

  • the "Fast Implementation of the ISODATA Clustering Algorithm" by Nargess Memarsadeghi, David M. Mount, Nathan S. Netanyahu, and Jacqueline Le Moigne [1]
    which has found its way in Opticks [7]
  • the biOps package for R [8]

However, those are not easy alternatives for a GRASS GIS user.

References

[1] http://www.cs.umd.edu/~mount/Projects/ISODATA/
[2] http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#//009z000000pn000000.htm
[3] http://geospatial.intergraph.com/fieldguide/wwhelp/wwhimpl/js/html/wwhelp.htm
[4] http://www.exelisvis.com/portals/0/tutorials/envi/ClassificationTutorial.pdf
[5] http://www.pcigeomatics.com/products/pdfs/Geomatica_Core_1032.pdf
[6] http://www.clarklabs.org/products/upload/IDRISI-Selva-GIS-Image-Processing-Specifications.pdf
[7] http://cran.r-project.org/web/packages/biOps/index.html
[8] http://www.opticks.org

Change History (10)

comment:1 Changed 7 years ago by benducke

GPL'd implementations in C++ can be found here: http://www.cs.umd.edu/~mount/Projects/ISODATA/

comment:2 Changed 7 years ago by Nikos Alexandris

Link to "historical" i.cluster material (kindly pointed to by Markus N)

http://lists.osgeo.org/pipermail/grass-user/1997-December/000912.html

comment:3 Changed 4 years ago by martinl

Milestone: 7.0.07.0.5

comment:4 Changed 4 years ago by martinl

Milestone: 7.0.57.3.0

comment:5 Changed 4 years ago by martinl

Milestone: 7.3.07.4.0

Milestone renamed

comment:6 Changed 2 years ago by neteler

Milestone: 7.4.07.4.1

Ticket retargeted after milestone closed

comment:7 Changed 22 months ago by neteler

Milestone: 7.4.17.4.2

comment:8 Changed 18 months ago by martinl

Milestone: 7.4.27.6.0

All enhancement tickets should be assigned to 7.6 milestone.

comment:9 Changed 14 months ago by martinl

Milestone: 7.6.07.6.1

Ticket retargeted after milestone closed

comment:10 Changed 12 months ago by martinl

Milestone: 7.6.17.6.2

Ticket retargeted after milestone closed

Note: See TracTickets for help on using tickets.