Constrained Dominant Sets with Applications in Computer Vision

Leulseged Tesfaye

Ca' Foscari University

13 July 2017, 2:00 pm


Dominant sets, a well-known graph-theoretic notion of a cluster which generalizes the concept of a maximal clique to edge-weighted graphs, has proven to be relevant in many computer vision problems such as action recognition, image segmentation, tracking, group detection and others. Its regularized counterpart, determining the global shape of the energy landscape as well as the location of its extrema, is able to organize the data to be clustered in a hierarchical manner. It generalizes the dominant sets framework in that putting the regularization parameter to zero results local solutions that are in one-to-one correspondence with dominant sets. In this work we propose constrained dominant sets, parameterized family of quadratic programs that generalizes both formulations, dominant sets and its regularized counterpart, in that here, only a subset of elements in the main diagonal is allowed to take the parameter, the other ones being set to zero. In particular, we show that by properly controlling a regularization parameter which determines the structure and the scale of the underlying problem, we are in a position to extract groups of dominant-set clusters which are constrained to contain user-selected elements. We provide bounds that allow us to control this process, which are based on the spectral properties of certain submatrices of the original affinity matrix. This increased flexibility leads to an efficient method that we apply on different computer vision problems: image co-segmentation and retrieval systems. Experiments on standard benchmark datasets show the effectiveness of our approach as compared to state-of-the-art algorithms.


Leulseged Tesfaye Received his BSc in computer science from Jimma University in 2012. After working for two years as EUC engineer at Kifiya financial Technology he joined Ca’ Foscari University of Venice where he received his MSc in computer science in June 2016. He is Currently working towards his PhD degree at Ca’ Foscari University of Venice, Italy under the supervision of prof. Marcello Pelillo . His research interest includes Computer Vision, Pattern Recognition, Machine Learning, Game Theory and Graph Theory.