NAME

ncut_dense_bipartition - Ncuts bi-partitioning of dense weight matrix.

SYNOPSIS

#include "seg/seg_ncuts.h"

Example compile flags (system dependent):
  -DLINUX_X86_64 -DLINUX_X86_64_OPTERON  -DGNU_COMPILER 
   -I/home/kobus/include
   -L/home/kobus/misc/load/linux_x86_64_opteron -L/usr/lib/x86_64-linux-gnu
  -lKJB                               -lfftw3  -lgsl -lgslcblas -ljpeg  -lSVM -lstdc++                    -lpthread -lSLATEC -lg2c    -lacml -lacml_mv -lblas -lg2c      -lncursesw 


int ncut_dense_bipartition
(
	Vector **softpartition_vpp,
	const Matrix *weight_mp
);

DESCRIPTION

This routine implements the Normalized Cut partitioning technique for splitting up a set of points into two sub-sets such that the normalized cut between the two sub-sets is minimum. For details about the Normalized Cut criterion for bipartitioning a set of points, please refer to the website: http://www.cs.berkeley.edu/projects/vision/grouping. The input to this routine is a square matrix containing the weights between each point-pair of the set of points. It returns a soft approximation to the actual bipartition that minimizes the normalized cut value of any bipartition. Further thresholding of the vector is needed to break up the set into two groups.

RETURNS

On error this routine returns ERROR with an error message being set. On success it returns NO_ERROR.

WARNING

The assumption is that the weight values between point pairs indicate affinity between them. The weight values are assumed to be positive. It is not guaranteed to work in a system where weight values may be negative. Also the weight matrix is assumed to be symmetric. If it is not, then it is forced to be symmetric by replicating the upper-right triangle into the lower-left triangle. This routine does not take advantage of sparseness of an input weight matrix (if it exists). It does brute force Normalized Cut approximation using the eigen solver from the LAPACK library. This routine is not adequately tested. This routine results in memory leaks when fails to execute completely.

DISCLAIMER

This software is not adequatedly tested. It is recomended that results are checked independantly where appropriate.

AUTHOR

Kobus Barnard

DOCUMENTER

Kobus Barnard