Skip to content


Folders and files

Last commit message
Last commit date

Latest commit



86 Commits

Repository files navigation

This is the code for the paper:

"Normalized Cut Meets MRF"
Meng Tang, Dmitrii Marin, Ismail Ben Ayed, Yuri Boykov
In European Conference on Computer Vision (ECCV), Amsterdam, the Netherlands, October, 2016

The CORE of our algorithm is linearization or unary bound for Normalized Cut (NC).
Simple implementation of such linearization is given in a FEW lines in "matlab/KernelBound.m" and "matlab/SpectralBound.m".

[ unaries ] = KernelBound( A, K, current_clustering)
% KERNELBOUND simply takes affinity, cluster number and current clustering and gives unary terms.
[ unaries ] = SpectralBound( A, K, dim, current_clustering)
% SPECTRALBOUND requires an extra argument dim, the dimensionality of spectral embedding
% When dim is the number of data points, SpectralBound is algorithmically EQUIVALENT to KernelCut.

Example of optimizing NC or AA (avearge association) ONLY is in "matlab/syntheticclustering.m". Below is sample result with KernelCut for NC:

Motion Segmentation using KernelCut

Multilabel example: Input image frames: directory "motionsegmentation/ducks01/images"
Initial Strokes for the first frame: directory "motionsegmentation/ducks01/seedsmulti"
Binary example: Input image frames: directory "motionsegmentation/horses01/images"
Initial Strokes for the first frame: directory "motionsegmentation/horses01/seeds"

Build dependency libraries (maxflow and easybmp)

$ cd libs
$ make all

Build main program

$ cd ../kernelcut
$ make main
$ cd ../

Download executable for optical flow

$ wget
$ unzip -d libs/LDOF

Compute optical flow, flow and its visualization saved into opticalflow directory

$ chmod +x libs/LDOF/ldof
$ matlab -nojvm -nosplash -nodisplay -r "cd motionsegmentation/ducks01; computeopticalflow; exit()"

Compute KNN graph for joint LAB + XY + M space

$ matlab -nojvm -nosplash -nodisplay -r "cd motionsegmentation/ducks01; getsubpixelimages; exit();"
$ matlab -nojvm -nosplash -nodisplay -r "cd motionsegmentation/ducks01; computeknn; exit()"

(Visualization of KNN graph is by clicking on image pixel, simply run motionsegmentation/visualizeknnbyclick.m)

Go to motionsegmentation/, change codepath, and run script

$ chmod +x ./motionsegmentation/
$ ./motionsegmentation/

Output segmentations are in the directory "motionsegmentation/ducks01/output".

(note that if initialized from seeds, the colors has to be of the following: {white,red,blue,green,black,navy})

Binary example "horses01" is similar to multilabel example "ducks01".

KernelCut in Python

Python implementation of KernelCut for binary segmentation is provided. See directory 'PyKernelCut'. Example Usage:

$ cd PyKernelCut
$ python -h
$ python -i 124084.jpg -b 10 20 300 300 -k 100
$ python -i 0_5_5303.bmp -b 50 100 200 200 -s 0
$ python -i 0_5_5303.bmp -b 50 100 200 200
$ python -i 314016.jpg -b 10 80 300 300 --hard

Note that To use PyKernelCut several dependencies (skimage, scipy, PyMaxflow) have to be installed.

License & Copyright



No description, website, or topics provided.







No releases published


No packages published