Clustering with hypergraphs: the case for large hyperedges
Date
2014
Authors
Purkait, P.
Chin, T.
Ackermann, H.
Suter, D.
Editors
Fleet, D.
Pajdla, T.
Schiele, B.
Tuytelaars, T.
Pajdla, T.
Schiele, B.
Tuytelaars, T.
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Lecture Notes in Artificial Intelligence, 2014 / Fleet, D., Pajdla, T., Schiele, B., Tuytelaars, T. (ed./s), vol.8692 LNCS, iss.PART 4, pp.672-687
Statement of Responsibility
Pulak Purkait, Tat-Jun Chin, Hanno Ackermann, David Suter
Conference Name
13th European Conference on Computer Vision (ECCV 2014) (6 Sep 2014 - 12 Sep 2014 : Zurich, Switzerland)
Abstract
The extension of conventional clustering to hypergraph clustering, which involves higher order similarities instead of pairwise similarities, is increasingly gaining attention in computer vision. This is due to the fact that many grouping problems require an affinity measure that must involve a subset of data of size more than two, i.e., a hyperedge. Almost all previous works, however, have considered the smallest possible hyperedge size, due to a lack of study into the potential benefits of large hyperedges and effective algorithms to generate them. In this paper, we show that large hyperedges are better from both theoretical and empirical standpoints. We then propose a novel guided sampling strategy for large hyperedges, based on the concept of random cluster models. Our method can generate pure large hyperedges that significantly improve grouping accuracy without exponential increases in sampling costs. In the important applications of face clustering and motion segmentation, our method demonstrates substantially better accuracy and efficiency.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
©Springer International Publishing Switzerland 2014