lvwmdd(3)

LIBRARY ROUTINE
lvwmdd - Weighted minimum distance detector

LIBRARY CALL
#include "vinclude.h"
lvwmdd (img, center, varimg,  border, k_factor, use_avg )
struct xvimage *img,            /* input image */
               *varimg,
               *center;         /* cluster center image */
int     border;
int     use_avg;                /* if set use the average method */
float   k_factor;

INPUT

img the input image that is to be classified.

center
    the image containing the center values (or prototype vectors) with the last data band being the class image. This image must have n + 1 data bands where n is the number of data bands in img.

varimg
    the image containing the variance values for the clusters. Should have the same number of data bands as the input image (img).

border
    the border width on the image. The border corresponds to a no class assignment. i.e. the border region is ignored during the classification process.

k_factor
    scalar, fudge factor.

use_avg
    1 - use summing method 0 - use non-summing method

OUTPUT

img a single band classified image.

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

MODIFICATIONS

DESCRIPTION
lvwmdd is an Weighted minimum distance detector or Classifier. The main idea behind this detector is that it will distinguish a single class form the rest of the data. However, 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 representive (ideal) data. This can be done by using a clustering algorithm on the representive data. Clustering routines such as vkmeans, vquant, isodata, etc can be used to create a template. The idea here is to over cluster the representive 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 looking at the diagonal of the covariance matrix.

Explained below is a method of creating a the class assignments 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 Covariance matrix, and X is the data points, and ~ denotes transpose. 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 simlpy 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 -a option set to yes. This is an apprioximation to method (2).
            sq( || X - Mi || ) <
     Vi = ------------------ > 1
                K x sq(Si)
     where: sq( || X - Mi || ) = sq(di)
                        = Eucludian 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 || )
                    = Eucludian Distance Squared of the
                      jth element of the vector X.
             Qj = the jth variance element of the varance
                  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 throught the test for each cluster, the data point X is assigned to a Class based on the following 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.

The scale factor (k_factor) must be choosen 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 sufficent. 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.

All input images must be of data storage type FLOAT.

img - struct xvimage
    the input image that is to be classified. This is also used as the output classified image, so must be careful not to overwrite important data.

center - struct xvimage
    the image containing the center values (or prototype vectors) with the last data band being the class image. This image must contain n + 1 data bands, where n = # of data bands in the img image, and 1 data band that specifies the class assignments.

varimg - struct xvimage
    the image containing the variance values. This image must have the same row and column size of the center image, and have the same number of data bands as the input image (img).

border - int
    the border width on the image. The border corresponds to a no class assignment. The border area is ignored during the classification.

k_factor - float
    the fudge factor, explained in detail above.

use_avg - int
    if use_avg = 1, use the summing method, if use_avg = 0 use the non-summing method, as explained above.

lvwmdd will return a 1 upon sucess and a 0 upon failure.

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

SEE ALSO
vwmdd(1), intro(3), vipl(3), verror(3), vutils(3) lvkmeans(3)

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

AUTHOR
Tom Sauer

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