FUZ

Description

Implements an unsupervised fuzzy clustering algorithm. A maximum of 255 clusters can be generated from 16 image channels. Each cluster is stored in a separate image channel. The intensity value of each pixel in each image channel is proportional to the degree of membership of that pixel corresponding to the channel's corresponding cluster.

Parameters

fuz(file, dbic, dboc, dbiw, fnorms, maxclus, maxiter, movethrs, maxpd)

Name	Type	Caption	Length	Value range
FILE *	str	Input file name	1 -
DBIC *	List[int]	Input raster channel(s)	1 - 16
DBOC *	List[int]	Output classified raster channels	1 - 255
DBIW	List[int]	Raster input window	0 - 4	Xoffset, Yoffset, Xsize, Ysize
FNORMS *	List[float]	Fuzzy-K and fuzzy-MLE norms	2 - 2
MAXCLUS	List[int]	Maximum number of clusters	0 - 1	0 - 16 Default: 16
MAXITER	List[int]	Maximum number of iterations	0 - 1	0 - 1001 Default: 20
MOVETHRS	List[float]	Movement threshold	0 - 1	0.0 - 100.0 Default: 0.01
MAXPD	List[float]	Partition density limit	0 - 1	Default: 20

* Required parameter

Parameter descriptions

FILE

Specifies the name of the PCIDSK file on which to perform clustering.

DBIC

Specifies the channels (maximum 16) to use as input to the clustering algorithm.

DBOC

Specifies the output channels to receive the clustering results. One channel is written per cluster.

A range of output channels can be specified using the following notation: m,-n. This is equivalent to: m,m+1,m+2,m+3,...,n.

For example:

DBOC=2,5,-8,23

is equivalent to:

DBOC=2,5,6,7,8,23

This parameter must list sufficient free channels to record the results for the specified number of clusters (MAXCLUS); otherwise, an error message is reported. If an input window (DBIW) is specified, only the area under DBIW is written to the output channels.

DBIW

Optionally specifies the raster window (Xoffset, Yoffset, Xsize, Ysize) that is read from the input image. If this parameter is not specified, the entire image is processed by default.

Xoffset, Yoffset define the upper-left starting pixel coordinates of the window. Xsize is the number of pixels that define the window width. Ysize is the number of lines that define the window height.

FNORMS

Specifies the parameters that determine the fuzzy norm. Two norms must be provided: the first for the fuzzy K-means, and the second for the fuzzy MLE (Maximum Likehood Estimation) clustering. Increasing the fuzzy K-mean norm decreases the fuzziness of its iterations.

The fuzzy MLE norm is actually the exponent applied to the squared Mahalanobis distance measure before it is used in the MLE equation. Increasing the fuzzy MLE norm decreases the fuzziness of its iterations.

MAXCLUS

Specifies the maximum number of clusters allowed. The algorithm may terminate before this value is reached if the maximum partition density (MAXPD) is positive. By default, a maximum of 16 clusters are allowed.

MAXITER

Specifies the total number of iterations for calculating the cluster mean positions after a new cluster has been initialized. This value is applied separately to both fuzzy K-means and fuzzy MLE stages. For example, if three clusters are required, MAXITER is set to 20 and the algorithm always reaches MAXITER; a total of 60 fuzzy K-Means and 60 fuzzy MLE iterations will have occurred. The default value is 20 iterations.

MOVETHRS

Specifies the movement threshold as a percentage of the cluster means. If the movement of all existing cluster means is less than the specified movement threshold value at either fuzzy K-means or fuzzy MLE stages, the algorithm considers the clusters to be stable for that stage. If the movement threshold is not exceeded for fuzzy K-means, the algorithm proceeds with fuzzy MLE. If the movement threshold is not exceeded for fuzzy MLE, the algorithm checks if another cluster should be added, based on the specified maximum iterations (MAXITER) and partition density limit (MAXPD).

      (New cluster mean position - Old cluster mean position)
_____________________________________________________   MOVETHRS
          Old cluster mean position

MAXPD

Specifies the maximum increase in partition density allowable for the algorithm to continue; values above this limit cause the execution to terminate. The partition density is a statistical measure of the cluster effectiveness. The partition density is reported to the user and can be used to set this parameter. Setting MAXPD to a non-positive value will disable partition density checking and result in the maximum number of clusters (MAXCLUS) being generated. A useful limit for this parameter depends on the imagery being clustered and must be established through trial and error, based on the partition density statistics reported for trial runs.

Details

FUZ is an adaptation of Unsupervised Optimal Fuzzy Clustering described by Gath and Geva (see References). This adaptation accepts as input a rectangular window or region under a specified bitmap from a multispectral image of any data type. The algorithm then clusters the data using maximum likelihood clusters, assuming Gaussian distributions for each cluster. A new cluster is added at each iteration as long as the maximum number of clusters (MAXCLUS) is not exceeded and the partition density has not reached the specified limit (MAXPD). This algorithm may encounter local minima and thus not achieve MLE fuzzy clustering.

The fuzzy MLE portion of the algorithm is designed to handle correlations between channels and unequal channel variances. Nevertheless, highly correlated channels will lead to numerical problems in computing fuzzy MLE iterations and will add noise rather than be of significant use. The user is advised to chose a set of large principal components as input channels.

The clustering results are recorded on in output database file, with each cluster assigned an image channel. The intensity of a pixel in each image channel is proportional to the degree of membership of that pixel to the channel's corresponding cluster.

The report records the partition density statistics and percentage movement of cluster mean vectors as they are calculated. The report also records the cluster means after each fuzzy K-means and fuzzy MLE stage has completed.

The output fuzzy cluster maps can be used to make theme maps or bitmaps for various types of cover classes using the threshold function THR. The operator must decide the upper and lower levels for each cover class in the fuzzy cluster map. This can be done using feature space exploration. The user can then use THR to identify regions that match a cover class description. It is possible to use color composites of fuzzy cluster maps to indicate regions where pixels contain varying amounts of mixed cover class content.

RAM usage

Fuzzy clustering requires that the membership of every pixel to every cluster be recored and updated. This is unlike k-Means or Isoclus, which only record the most likely cluster to which each pixel belongs. As a result, fuzzy clustering can require large amounts of memory. The following formula can be used to estimate the amount of RAM required for clustering a generic image under a rectangular input window.

Number of input channels = N
MAXCLUS = M
DBIW = P pixels by L lines

APPROXIMATE RAM REQUIRED = (5*M*P*L + 4*N*P*L + 3*M*N*N) bytes

For example, finding eight clusters in a five channel, 512x512 pixel image requires approximately 16 Megabytes of RAM.

Example

Use PCIMOD to add four real channels to the demo file irvine.pix, to receive the fuzzy cluster maps.

Cluster a full image window of channels 1 and 2 of the input file (irvine.pix). Allow at most three clusters, and request that no checking of the Partition Density take place. Make use of a fuzzy K-means norm of 2.5 and an MLE norm of 1.1. Also, specify an iteration stopping criteria of 0.01 and limit the number of fuzzy K-means and fuzzy MLE iterations to 20 each. The clustering results are stored into the three real channels created by PCIMOD (channels 12, 13, and 14, if using an unmodified irvine.pix file).

from pci.fuz import fuz

file	=	"irvine.pix"	# input image file name
dbic	=	[1,2]	# input channels to be clustered
dboc	=	[12,13,14]	# output channels for cluster maps
dbiw	=	[]	# output entire image
fnorms	=	[2.5,1.1]	# fuzziness norms
maxclus	=	[3]	#	maximum number of clusters
maxiter	=	[20]	# maximum iterations
movethrs	=	[0.01]	# iteration stopping criteria
maxpd	=	[0]	# do not check partition density

fuz( file, dbic, dboc, dbiw, fnorms, maxclus, maxiter, movethrs, maxpd )

References

Gath, I. and Geva, A. (1989). Unsupervised Optimal Fuzzy Clustering. IEEE Trans. PAMI, Vol II, No. 7, pp. 773-789.