viso2(1)

PROGRAM
viso2 - Performs the ISO2 clustering algorithm on an image.

SYNTAX

viso2

-i1 input image

-o1 output image specifying which vector belongs to what cluster

-o2 output image for cluster centers

-o3 output variance

[-f2]
    output file for kmeans statistics

[-n]
    specifies minimum number of samples per cluster (default = 1)

[-s]
    specifies splitting factor (splitting factor increase -> less splitting) (default = 10000000)

[-m]
    specifies merging factor (merging factor decreases -> less merging) (default = 0)

[-sc]
    specifies splitting convergence (default = 0)

[-mc]
    specifies merging convergence (default = 0)

[-p]
    specifies placement of new cluster centers during splitting (default = 0.5)

[-ik]
    specifies maximum number of iterations for kmeans (default = 100000)

[-ii]
    specifies maximum number of iterations for iso2 (default = 100000)

[-k]
    specifies maximum number of clusters (default = 50)

[-b]
     specifies the border width in pixels (default = 0)

[-c]
    use First K Vectors As Cluster Centers (default = 5)
    -OR-

[-f1]
    input ASCII file for x-y coordinates of cluster centers
    -OR-

[-i2]
    input image cluster center values

[-V]
    Gives the version for viso2

[-U]
    Gives the usage for viso2

[-P]
    Prompts for command line options

[-A [file1]]
    Creates the answer file called viso2.ans or file1

[-a [file1]]
    Uses viso2.ans or file1 as the answer file

DESCRIPTION
Viso2 is a clustering algorithm which is derived from the ISODATA clustering algorithm. Iso2 initially clusters the data using a standard K-means clustering algorithm. Then, any cluster, along with its associated vectors, is discarded if the membership of that cluster is below a user specified threshold. Next, clusters exhibiting large variances are split in two, and clusters that are too close together are merged. After these operations, K-means is reiterated, and the iso2 rules tested again. This sequence is repeated until no clusters are discarded, split, or merged, or until the maximum number of iterations has been met.

The merging and splitting rules used in iso2 are similar to those used in ISODATA, except that several modifications have been made which simplify parameter selection for the user. The most significant change is that the splitting and merging rules are now relative to the statistics of the data rather than being dependent on absolute limits, and these relative limits can be made to converge so that splitting and merging are reduced as the algorithm progresses. Secondly, the splitting rules are no longer dependent on a user specified "desired number of clusters" nor on the iteration index. Defining the splitting and merging requirements so that they are relative to the data set removes the need for the user to know the range of the data, and makes characterization of the algorithm for the general case possible. The methods of splitting and merging are described below.

Splitting: relative standard deviation approach

The standard deviation in each dimension of each cluster is computed, and the average of these standard deviations calculated. The maximum standard deviation for each cluster is then compared against the average standard deviation times a user specified scaling factor (splitting factor). If the maximum standard deviation is greater than that value, the cluster is split in two in the dimension of maximum standard deviation. Two other splitting conditions also exist: (1) the number of points in the cluster must satisfy a minimum condition, and (2) the average distance between members of a cluster and their cluster center must be less than the average of this distance over all clusters. After all eligible clusters have been split, the splitting factor is updated. A cluster can only be split once per iteration.

Merging: relative distance approach

The merging process is similar to the splitting process described above. The pairwise distances between cluster centers are computed as is done in the original ISODATA algorithm and, in addition, the average pairwise distance is computed. If any distance between two cluster centers is less than the average pairwise distance multiplied by a scaling factor (merging factor), the two clusters are merged. The user has the option to specify the maximum number of cluster pairs that can be merged. Cluster pairs with the smallest pairwise distances are merged first, and a cluster can only be merged once per iteration. After all eligible clusters are merged, the merging factor is updated.

viso2 will generate a statistics file which will contain various information about the results from the clustering.

A word of caution, viso2 will require a large amount of memory. This means that you will need a minimum of 16 MegaBytes of memory and about 80 Megabytes of swap space for a 512 x 512 image. The computation time will be anywhere from 3 hours to 3 days depending on the machine and parameters specified.

Some Conventions:

viso2 can be run in 2 modes, one which produces all valid centers and numbers and one that produces a cluster number without a corresponding center. If minimum points (-n option) is set such that some vectors (pixels) are discarded, then these vectors (pixels) are not associated with any cluster. So, these vectors (pixels) will be assigned to cluster 0, and the cluster center and variance values will be set to zero. This means that viso2 will produce N+1 clusters. This is considered the incompatible mode. This mode will still actually have valid input for other algorithms but will give strange results. To avoid this, use the default for the -n option, which is 1. If no vectors (pixels) are discarded, then cluster number 0 will be a valid cluster and contain a non-zero center and variance. In this case there will be N clusters resulting.

Results obtained by the viso2 algorithm can be influenced by the number and choice of initial cluster centers and the geometrical properties of the data.

All input images must be of data storage type FLOAT.

Characterization of Parameters:

viso2 has many variables that can be specified by the user. These variables are defined below, with those to which the algorithm is most sensitive listed first, and a brief explanation of how they affect the algorithm. If all default values are used when running iso2, the algorithm defaults to the standard K-means algorithm.

split factor (-s):
    This factor multiplied by the overall average cluster standard deviation determines the maximum standard deviation that a cluster is allowed before it will be split in two. In other words, a higher splitting factor allows for less compact clusters, which results in less splitting. The default value is "infinity" (no splitting).
    (typical range: 1.0 <= split factor < 1.1).

merge factor (-m)
    This factor multiplied by the overall average pairwise distance between cluster centers determines the minimum distance allowed between two cluster centers before the clusters will be merged. This means that a lower merging factor allows distances between cluster centers to be smaller and therefore less merging occurs. The default value is 0.0 (no merging).
    (typical range: 0.3 <= merge factor < 1.0).

split converge (-sc)
    The splitting convergence parameter is used to update split factor. Large convergence values will force the splitting factor out of range more quickly than small values. The default value is 0.0 (split factor is not altered). Split factor is updated using the following relation.
    split_factor (k+1) = split_factor(k) x ( 1 + split_converge )
    (typical range: 0.01 <= merge factor < 0.1).

merge converge (-mc)
    The merging convergence parameter is used to update merge factor. Large convergence values will force the converging factor out of range more quickly than small values. The default value is 0.0 (merge factor is not altered). Merge factor is updated using the following relation.
    merge_factor (k+1) = merge_factor(k) x ( 1 - merge_converge )
    (typical range: 0.0 <= merge converge < 0.2).

minimum points (-n)
    This parameter specifies the minimum number of samples allowed in a cluster before it is discarded. The default value is 1 (no discarding occurs).

split placement (-p)
    This parameter is a value between 0 and 1 and is used in calculating the new cluster center positions when splitting occurs. Larger splitting parameter values will cause the new cluster centers to be placed further away from the original cluster center. The default value is 0.5.

Initial number clusters (-c)
    This parameter specifies the initial number of of cluster centers. Due to the relative nature of the splitting and merging factors, the minimum number of initial clusters must be greater than 2. The default value is 5.

Initial cluster center file (-i2)
    This specifies a file which contains the initial cluster center vectors. If this option is specified, the number of points in the file overrides the initial number clusters (-c) parameter. This is an image with 1 row and n columns, where n is the number of initial cluster centers desired. This image must contain the same number of data bands as the input image to be clustered. This image must be of data storage type FLOAT.

Initial xy position cluster centers file (-f1)
    This specifies a file which contains the x-y locations in the input image for the initial cluster centers. Each x-y pair defines the position of a starting cluster center. The x-y locations must be inside the image dimensions. This file is an ascii file of x-y pairs.

max iso iterations (-ii) 1.25i
    This specifies the maximum number of iso2 iterations. The default is to allow the algorithm to run until it converges.

max kmeans iterations (-ik)
    This specifies the maximum number of K-means iterations allowed per iso2 iteration. The default is to allow the algorithm to run until it converges.

border width (-b)
    This parameter allows the user to specify a border width, in pixels, encompassing the desired region of the image to be clustered. In the resulting cluster number image, the border pixels will be assigned the value 0. From this point on the border should be ignored. The border pixels in no way contribute to the center and variance values specified for class 0. They are not considered part of class 0. If the border produced causes any problems, then a subimage may be extracted from the original cluster number image using vextract.

Resulting cluster centers (-o2)
    This argument will assign the cluster center image to a file. The cluster center image will always have a row size of 1 and a column size of the number of clusters, the number of data bands will be equal to the dimension of the vectors.

Resulting cluster variance (-o3)
    This argument will assign the variance image of the cluster centers to a file. The variance image will follow the same format as the cluster center images.

Resulting cluster number image (-o1)
    This image represents the cluster number the vector (pixel) at the current location in the original image now belongs to.

Statistics file (-f2)
    This file contains statistics obtained during the execution of viso2. This file includes the following information:

    Total Number of ISO2 Iterations

    Total Number of Clusters

    Total Number of Discarded Pixels

    Number of kmeans Iterations Per Iso Iteration

    Number of Vectors Per Cluster

    Cluster Center Values

    Cluster Center Variance Values

    Trace of Covariance Matrix

REQUIRED ARGUMENTS

-i1 type: infile
    desc: input image

-o1 type: outfile
    desc: output image specifying which vector belongs to what cluster

-o2 type: outfile
    desc: output image for cluster centers

-o3 type: outfile
    desc: output variance

OPTIONAL ARGUMENTS

-f2 type: outfile
    desc: output file for kmeans statistics

-n  type: integer
    desc: specifies minimum number of samples per cluster (default = 1)
    default: 1
    bounds: value >= 0

-s  type: float
    desc: specifies splitting factor (splitting factor increase -> less splitting) (default = 10000000)
    default: 1e+07
    bounds: value >= 0.0

-m  type: float
    desc: specifies merging factor (merging factor decreases -> less merging) (default = 0)
    default: 0
    bounds: value >= 0.0

-sc type: float
    desc: specifies splitting convergence (default = 0)
    default: 0
    bounds: value >= 0.0

-mc type: float
    desc: specifies merging convergence (default = 0)
    default: 0
    bounds: value >= 0.0

-p  type: float
    desc: specifies placement of new cluster centers during splitting (default = 0.5)
    default: 0.5
    bounds: 0.000000 < [-p] < 1.000000

-ik type: integer
    desc: specifies maximum number of iterations for kmeans (default = 100000)
    default: 100000
    bounds: value > 0

-ii type: integer
    desc: specifies maximum number of iterations for iso2 (default = 100000)
    default: 100000
    bounds: value > 0

-k  type: integer
    desc: specifies maximum number of clusters (default = 50)
    default: 50
    bounds: value > 0

-b  type: integer
    desc: specifies the border width in pixels (default = 0)
    default: 0
    bounds: value >= 0

*** These arguments are MUTUALLY EXCLUSIVE ***
 If desired, you may provide ONE AND ONLY ONE of:

-c  desc: use First K Vectors As Cluster Centers (default = 5)
    default: 5
    bounds: 3 < [-c] < 1000000

-f1 desc: input ASCII file for x-y coordinates of cluster centers

-i2 desc: input image cluster center values
    ********

EXAMPLES

viso2 -i1 image1 -c -ii 10000 -k 6 -b 4 -o1 image2 -o2 image3 -o3 image4 -m 0.5 -s 1.01 -sc 0.075 -mc 0.05

this will apply the viso2 clustering algorithm to image1 using the first K vectors as cluster centers. The number of iterations selected is 10000 for the iso2 algorithm, the maximum number of clusters selected is 6, and a border (-b) width of 4 pixels is specified. Image2 (-o1) specifies which vector belongs to what cluster, while image3 (-o2) is the output image for the cluster centers. Image4 (-o3) is the output image for the variance of the clusters. The merging factor (-m), splitting factor (-s), merge convergence (-mc), and the split convergence (-sc) were set a random following the typical range stated above for each.

SEE ALSO
intro(1), verror(3), vgparms(3), vutils(3), lviso2(3)

RESTRICTIONS
All input images must be of data storage type FLOAT.

COPYRIGHT
Copyright 1991, University of New Mexico. All rights reserved.