lvkmeans(3)

LIBRARY ROUTINE
lvkmeans - Performs the kmeans clustering algorithm on an image

LIBRARY CALL
#include "vinclude.h"
lvkmeans (img, img1, img1_flag, sqd_img, sqd_img_flag, iter, cluster, border,
          init_cluster, printdev, cc_flg, map_flag, cc_img)
struct xvimage *img,            /* input image */
               *img1,           /* output image */
               *sqd_img,        /* square distance image */
               *cc_img;         /* cluster center image */
int     cluster,                /* number of desired clusters */
        iter;                   /* max number iterations */
int    *init_cluster[],         /* array of initial cluster centers x-y
                                   pairs */
        border,                 /* specifies number of border pixels */
        cc_flg,                 /* use cluster center as input */
        img1_flag,              /* flag for outputting cc image */
        sqd_img_flag,           /* flag for outputting variance image */
        map_flag;               /* flag for outputting cc in img map */
FILE * printdev;                /* output ascii file descriptor */

INPUT

img input image structure.

img1_flag
    Output cluster centers in the "img1" image.

sqd_img_flag
    Output cluster variance in the "sqd_img" image.

iter
    maximum number of iterations.

cluster
    number of desired clusters.

border
    specifies number of border pixels.

init_cluster
    array of initial cluster centers.

cc_flg
    indicator to use cluster center image as input.

cc_img
    cluster center image structure.

map_flag
    If true output cluster center values in the map of the cluster number image. If false do not output cluster center values in the map of the cluster number image.

OUTPUT

img1
    image structure for cluster center image.

sqd_img
    image structure for square distance values (variance).

printdev
    output ASCII file for cluster centers.

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

MODIFICATIONS

DESCRIPTION
vkmeans converts an input image into vectors of equal size and performs the kmeans clustering algorithm on the vectors using the K initial cluster centers. The size of each vector is determined by the number of bands in the input image.

The K-means algorithm is based on the minimization of the sum of the squared distances from all points in a cluster to a cluster center. The user chooses K initial cluster centers and the image vectors are iteratively distributed among the K cluster domains. New cluster centers are computed from these results, such that the sum of the squared distances from all points in a cluster to the new cluster center is minimized.

Although the k-means algorithm does not really converge, a practical upper limit is chosen for convergence. The user has the option of specifying the maximum number of iterations using the iter variable.

Results obtained by the k-means 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.

User variables for the k-means algorithm are passed in as:

cc_flg
    If the cc_flg is set, a cluster center image, passed in as cc_img, is used as input for the K initial cluster centers. This image MUST contain the same number of data bands as the input image (img).

cc_img
    an image of type struct xvimage that contains the first K cluster center values. This image must have the same number of data bands as img and as cluster.

sqd_img
    an image of type struct xvimage that will contain the variance of the cluster centers. This image must have the same number of data bands as img and as cluster.

sqd_img_flag
    If this flag is set to TRUE, the "sqd_img" image will contain the variance of the cluster centers. If set to false, this information is not output.

img a multiband image of type struct xvimage that contains the data to be clustered.

img1
    The cluster centers for the output image are returned in the struct xvimage structure img1.

img1_flag
    If this flag is set to TRUE, the "img1" image will contain the cluster centers. If set to false, this information is not output.

map_flag
    If "map_flag" is set to TRUE, the cluster centers are output in the map of the cluster number image "img". The number of rows in the map is equal to the number of desired clusters, while the number of columns is equal to the dimensionality of the data. Also, the ispare1 field in the image header is set to 0 and the ispare2 field in the image header is set to the dimension of the vector. By setting the "map_flag" to true, the output of vkmeans is compatable with the spectrum classification application.

iter
    the maximum number of iterations that the algorithm will perform to achieve the clustering.

cluster
    the number of desired clusters; MUST match the number of clusters in the cluster center image (cc_img) or in the array of initial cluster centers (init_cluster[]).

border
    specifies the number of border pixels, encompassing the desired region of the image to be clustered using the k-means algorithm. Class zero is reserved for the border pixels, while the remainder of the image uses classes one through k. The number of classes corresponds to the number of cluster centers specified in the variable cluster.

*init_cluster[]
    The array of initial cluster centers (init_cluster[][]) must be passed in as x-y pairs, which specify the coordinates of the initial cluster centers for the k-means algorithm.

printdev
    The cluster centers are written to a file specified by the 'printdev' argument.

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

SEE ALSO
vkmeans(1), intro(3), vipl(3), verror(3), vutils(3)

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

AUTHOR
Tom Sauer, Charlie Gage

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