lviso2(3)

LIBRARY ROUTINE
lviso2 - Performs the ISO2 clustering algorithm on an image.

LIBRARY CALL
#include "vinclude.h"
lviso2 (img, outcc_img, outvar_img, min_pts_allowed, max_cl_allowed, n_clusters, split_factor, merge_factor, placement, split_converge, merge_converge, max_n_iters_iso, max_n_iters_kmeans, border, init_cluster, cc_flg, cc_img, printdev2  )
struct xvimage *img,            /* input image                 */
               **outcc_img,     /* cluster center image        */
               **outvar_img,    /* variance image              */
               *cc_img;         /* input cluster center image  */
int     min_pts_allowed,        /* min number vectors/cluster  */
        max_cl_allowed,         /* max number cluster          */
        n_clusters,             /* inital number cluster       */
        max_n_iters_iso,        /* max iso data iterations     */
        max_n_iters_kmeans,     /* max kmeans data iterations  */
        border,                 /* image border                */
        cc_flg,                 /* initial cluster locations   */
       *init_cluster[];       /* array of initial cluster centers x-y pairs */
float   split_factor,           /* splitting factor            */
        merge_factor,           /* merging factor              */
        placement,              /* splitting placement factor  */
        split_converge,         /* splitting convergence       */
        merge_converge;         /* merging convergence         */
FILE * printdev2;               /* output ascii file descriptor */

INPUT

*img
    input image

*cc_img
    input cluster center image

min_pts_allowed
    min number vectors/cluster

max_cl_allowed
    max number cluster

n_clusters
    inital number cluster

max_n_iters_iso
    max iso data iterations

max_n_iters_kmeans
    max kmeans data iterations

border
    image border

cc_flg
    initial cluster locations

*init_cluster[]
    array of initial cluster centers x-y pairs

split_factor
    splitting factor

merge_factor
    merging factor

placement
    splitting placement factor

split_converge
    splitting convergence

merge_converge
    merging convergence

*printdev2
    output ascii file descriptor

OUTPUT

*img
    output image

**outcc_img
    cluster center image

**outvar_img
    variance image

MODIFICATIONS

DESCRIPTION
lviso2 converts an input image into vectors of equal size and performs the iso2 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.

lviso2 is a clustering algorithm which is derived from the ISODATA clustering algorithm. lviso2 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.

If the cc_flg is set to TRUE, then lviso2 will use the *cc_img image for the initial cluster center values, otherwise it will use the *init_clusters[] array of x-y image corrdinates. lviso2 takes the list of x-y corrdinates and maps them to that location in the image and uses those pixel values as the initial cluster centers.

lviso2 will output a cluster center image, which is an image of 1 row by N columns, where the N refers to the number of clusters. The variance image is an 1 row by N column image that specifies the variance for each cluster center. A cluster number image is also computed. This image represents the cluster number the vector (pixel) at that location in the original image now belongs to. A statistics file is also genterated and output to the printdev device.

Some Convensions:

lviso2 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 (min_pts_allowed) 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 all means that viso2 will produce N+1 clusters. This is considered the incompatable mode. This mode will still actually have valid input for other algorithms but will give strange results. To avoid this, use min_pts_allowed = 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.

Even though this man page contains much of the information that the manual page for viso2 contains, it is highly recommened that one reads the viso2 manual page. It will further explain the parameters such as merge and split convergence.

All input images must be of data storage type FLOAT.

struct xvimage *img
    Pointer to the input image to be clustered. Must be data storage type FLOAT.

struct xvimage **outcc_img
    Address of image that will contain the resulting cluster center image.

struct xvimage **outvar_img
    Address of image that will contain the resulting cluster variance image.

int min_pts_allowed
    The minimum number of vectors per cluster allowed.

int max_cl_allowed
    The Maximum number of clusters desired.

int n_clusters
    The initial number of cluster centers to start with.

int max_n_iters_iso
    Maximum number of isodata iterations.

int max_n_iters_kmeans
    Maximum number of k-means iterations per isodata iteration.

int border
    Specifies the border size, number of pixels, in the image that will be ignored during clustering. The border size is equal on all sides.

int cc_flg
    This flag is set if the initial cluster centers will be specified by the *cc_img.

struct xvimage *cc_img
    Pointer to the image that will contain the initial input cluster centers. This image must have the same number of data bands as the *img does. cc_flg must be set for this to be used.

int *init_cluster[]
    A 2-d array containing the initial cluster center positions in the input image. The array is organized as a list of x-y pairs that correspond to the position on the initial cluster centers in the input image. This is used only if cc_flg is set to FALSE.

float split_factor
    specifies the splitting factor.

float merge factor
    specifies the merge factor.

float placement
    Specifies the distance between cluster centers when they are split.

float split_converge
    Specifies the splitting convergence.

float merge_converge
    Specifies the merge convergence.

FILE * printdev2
    Specifes the output device for the statistics information.

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

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

AUTHOR
Tom Sauer, Donna Koechner

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