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