2011 | OriginalPaper | Chapter
Efficient Clustering Earth Mover’s Distance
Authors : Jenny Wagner, Björn Ommer
Published in: Computer Vision – ACCV 2010
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The two-class clustering problem is formulated as an integer convex optimisation problem which determines the maximum of the Earth Movers Distance (EMD) between two classes, constructing a bipartite graph with minimum flow and maximum inter-class EMD between two sets. Subsequently including the nearest neighbours of the start point in feature space and calculating the EMD for this labellings quickly converges to a robust optimum. A histogram of grey values with the number of bins
b
as the only parameter is used as feature, which makes run time complexity independent of the number of pixels. After convergence in
$\mathcal{O}(b)$
steps, spatial correlations can be taken into account by total variational smoothing. Testing the algorithm on real world images from commonly used databases reveals that it is competitive to state-of-the-art methods, while it deterministically yields hard assignments without requiring any a priori knowledge of the input data or similarity matrices to be calculated.