
viso2(1)                     Khoros                      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 clus-
                    ter (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 clus-
                    ter 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 cal-
     culated.  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 aver-
     age 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.
9
     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 Mega-
     Bytes 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 dis-
     carded, 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 clus-
     ters.  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 (pix-
     els) 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 expla-
     nation 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 max-
                 imum 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 deter-
                 mines 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).
9
     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 dis-
                 carded.  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 posi-
                 tions when splitting occurs.  Larger splitting
                 parameter values will cause the new cluster
                 centers to be placed further away from the ori-
                 ginal 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 clus-
                 ter 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 posi-
                 tion of a starting cluster center. The x-y loca-
                 tions 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 itera-
                 tions.  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 dur-
            ing 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 conver-
     gence (-mc), and the split convergence (-sc) were set a ran-
     dom 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.

Khoros                    Release: 1.0                          1

