
vwmdd(1)                     Khoros                      vwmdd(1)

PROGRAM
     vwmdd - Weighted minimum distance detector

SYNTAX
     vwmdd

     -i1            Input Image

     -i2            Input Center/Class Image

     -i3            Input Variance Image

     -o             output image specifying which vector belongs
                    to what cluster

     [-k]            specifies the scaling factor (default = 1)

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

     [-s]           Use Summed Method

     [-V]           Gives the version for vwmdd

     [-U]           Gives the usage for vwmdd

     [-P]           Prompts for command line options

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

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

DESCRIPTION
     vwmdd is an Weighted minimum distance detector or Classif-
     ier.  The main idea behind this detector is that it will
     distinguish a single class form the rest of the data. How-
     ever, it will also work to distinguish multiple classes from
     each other.

     Theory

     To classify or detect spatial patterns in an image, we must
     have a template to compare against. Creating a template can
     be thought of as training on representative (ideal) data.
     This can be done by using a clustering algorithm on the
     representative data. Clustering routines such as vkmeans,
     vquant, isodata, etc can be used to create a template.  The
     idea here is to over cluster the representative data, and
     quantize that into k classes.  Pseudo color in xvdisplay,
     and vcustom can be used to create a class image. When the
     clustering is performed, two items need to be computed; (1)
     the cluster center values, and (2) the variances for each
     axis in the cluster. The variances can be obtained by look-
     ing at the diagonal of the covariance matrix.

     Explained below is a method of creating a the class assign-
     ments for each cluster center. The class assignments may,
     for example, quantize the space from 12 clusters to 2
     classes. Example

             Cluster Center               Class
                   1 ---------------------  2
                   2 ---------------------  2
                   3 ---------------------  1
                   4 ---------------------  2
                         .
                         .
                         .
                  12 ---------------------  1

     This routine expects an image that contains the diagonal
     terms of the covariance matrix, called the variance image,
     and an image that contains the cluster center values and
     class assignment for each cluster center. And of course the
     image to be classified.  This detector is to approximate the
     following equation:

              (X - Mi)~ Inv(C) (X - Mi)
     (1)

     where Mi is the mean, inv(C) is the inverse of the Covari-
     ance matrix, and X is the data points, and ~ denotes tran-
     spose. This can be written as

          (d1 d2 ... dn)~ - Q1           - (d1 d2 ... dn)     (2)
                          |    Q2        |
                          |      .   0   |
                          |        .     |
                          |  0       .   |
                          |           Qn |
                          -              -

            Which equals

               sq(d1)   sq(d2)           sq(dn)
               ------ + ------ + ..... + ------             (3)
                 Q1       Q2               Qn

           Notation:
                sq => square
                Qi => the ith variance
                di => the ith (X - Mi) value
                the matrix is actually the inverse of C

     Since the inverse of the Covariance matrix can not be easily
     determined, we only consider the diagonal terms or simply
     the variance terms.

     There are two methods for detecting classes in the input
     image. Each data point is put through a test based on the
     ideas above. The detector works in two modes as follows:

     (1) uses the summed method -s option set to yes. This is an
     approximation to method (2).

                 sq( || X - Mi || )   <
          Vi =   ------------------   >   1
                     K x sq(Si)

          where:    sq( || X - Mi || ) =  sq(di)
                                       = Euclidean Distance
     Squared
                    sq(Si) = trace(C)
                       the trace of C is the sum of the
                       diagonal terms (variances).
                    K is a Constant

     (2) non summed method (default).

                  sq(d1)   sq(d2)           sq(dn)   <
          Vi =    ------ + ------ + ..... + ------   >   1
                  Q1 x K   Q2 x K           Qn x K

          where:  sq(dj) = sq( || xj - Mi || )
                         = Euclidean Distance Squared of the
                           jth element of the vector X.
                  Qj = the jth variance element of the variance
                       vector for the ith cluster center.
                  K = Constant

     In both cases the constant K is used. This is used to adjust
     the variance value(s). If K is large, Qi can increase such
     that Vi is always less than 1. There are no specific rules
     as to the optimal value for K.

     The data point X is put through the test for each cluster,
     the data point X is assigned to a Class based on the follow-
     ing criteria:

     1.   choose the smallest Vi value, where Vi is the result
          for cluster i.

     2.   If Vi is greater than 1, assign X to the NULL class
          (NULL class is always 0).  Otherwise assign Vi to class
          that corresponds to the ith cluster.

     This routine accepts three images as the input. The image
     that corresponds to the -i1 argument is the image that needs
     to be classified. This image can be have as many data bands
     as necessary. The number of data bands depicts the dimen-
     sionality of the vectors. Each pixel in the image is a vec-
     tor with dimensionality of the number of data bands.

     The second input image corresponds to the -i2 argument and
     is the prototype image.  This image contains two pieces of
     information.  (1) the cluster center values for each cluster
     center, and (2) the class assignments for each cluster
     center.  The last data band of this image contains the class
     assignments for each cluster center value. This image must
     contain the same number of data bands as the other input
     image plus an extra data band that represents the class map-
     ping. This image would most likely have been created by
     vkmeans or some other routine that will give cluster
     centers. This image contains vectors that correspond to the
     prototype of each class.

     As stated above the center image's last data band is a class
     data band. The class data band simply maps each cluster
     center vector to a final class.

     At this point most class images must be created manually.  A
     class image can be created by using pseudo color in
     xvdisplay on the resulting clustered image from the vkmeans
     routine. Vcustom can then be used to create the class image.
     Finally vbandcomb can be used to add the class image data to
     the center image. Normally one would over cluster using
     vkmeans then reduce the space down. So vkmeans might produce
     100 clusters but, really only 3 classes are desired. Pseudo
     color in xvdisplay and vcustom can be used to reduce the
     space down and create a class image. The class data might
     map cluster center vectors 1-50 to class 1, vectors 51-60 to
     class 2 and vectors 61-100 to class 3. When the vwmdd rou-
     tine is run, the result would be a classified image of three
     classes.

     The third input image corresponds to the -i3 argument.  This
     image contains the variance values for each cluster center.
     This image contains the same number of data bands as the
     input image (-i1 image), and contains the same number of
     vectors as the center image (-i2 image).  Each element in
     the variance vector is the variance value along an axis in
     the n-dimensional space.  The variance values can be found
     by computing the diagonal of the covariance matrix for each
     cluster. The cluster center values would be used as the mean
     values.  Note, vkmeans will compute this image for you.

     The scale factor (-k) must be chosen by trial and error. It
     has been found that if the summed method is being used a
     small (1.0 - 3.0) value for k is sufficient. If the average
     method is not being used a larger k (8.0 - 10.0) value is
     sufficient. Note, this may change based on the data, so
     these ranges are only a starting point.

     The border option (-b) allows the user to specify a border
     width, in pixels, encompassing the image. The border region
     is skipped by vwmdd when classification is performed. This
     useful if neighborhood operators have been used previously
     and have not updated edge pixels.

     All input images must be of data storage type FLOAT.

     This routine was written with the help of and ideas from Dr.
     Don Hush, University of New Mexico, Dept. of EECE.

REQUIRED ARGUMENTS
     -i1    type: infile
            desc: Input Image

     -i2    type: infile
            desc: Input Center/Class Image

     -i3    type: infile
            desc: Input Variance Image

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

OPTIONAL ARGUMENTS
     -k     type: float
            desc:  specifies the scaling factor (default = 1)
            default: 1
            bounds: value > 0.0

     -b     type: integer
            desc:  specifies the border width in pixels (default
            = 0)
            default: 0
            bounds: 0 < [-b] < 100

     -s     type: boolean
            desc: Use Summed Method
            default: false

EXAMPLES
     vwmdd -i1 ariel_image.xv -i2 centers_class -i3 variance -b 5
     -k 8.0 -o test

     ariel_image is a 5 band image; thus, each vector has dimen-
     sionality of 5, centers_class image is a 6 band image, 5
     bands that contain the cluster center values  and 1 class
     band.  The border that vwmdd will ignore is 5 pixels wide.
     The output image will be a single band image called test.
     The scalar to multiply the denominator by is 8.0.  By
     default the non-summing method is used.

SEE ALSO
     intro(1), verror(3), vgparms(3), vutils(3), lvwmdd(3)
     vkmeans(1)

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

