1,720,962 research outputs found
Extensions of dominant sets and their applications in computer vision
No full textMany problems in computer vision can be formulated as a clustering problem, a problem that aims to organize a collection of data objects into groups or clusters, such that objects within a cluster are more “similar” to each other than they are to objects in the other groups.Assuming the feature-based representation, a computer vision problem can be formulated as follows: Given a set of data points in a 'd' dimensional space, find the best partition of the space which gives us meaningful groups. The points in the representative metric space correspond to the feature vectors extracted from the object with their distances reflecting the dissimilarity relations. On the other hand, objects could also be described indirectly by their respective similarity relations, an approach which is more natural than feature-based technique as there are numerous application domains where it is not possible to find satisfactory features, but it is more natural to provide a measure of similarity.
This work proposes similarity based data clustering framework, based on extensions of the dominant sets framework using theories and mathematical tools inherited from graph theory, optimization theory and game theory, that could be adapted ``flexibly'' in a wide range of vision applications, thereby combining the research domain of computer vision and that of machine learning. In our system, clusters are in one-to-one correspondence with Evolutionary Stable Strategies (ESS) - a classic notion of equilibrium in evolutionary game theory field - of a so-called “clustering game”. The clustering game is a non-cooperative game between two-players, where the objects to cluster form the set of strategies, while the affinity matrix provides the players’ payoffs.
The dominant sets framework, a well-known graph-theoretic notion of a cluster which generalizes the concept of a maximal clique to edge-weighted graphs, has proven itself 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 thesis we propose constrained dominant sets, parameterized family of quadratic programs that generalizes both formulations, the dominant sets framework 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 sets clusters which are constrained to contain user-specified 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.
Thanks to the many sensors, which generate a large amount of data every day, distributed in the society, there is a large amount of data for training and testing many computer vision systems. However, real data collected through those sensors is contaminated by outliers, and many computer vision tasks involve processing the available large amounts of data without any assumption on the existence of outliers. Recently, very few computer vision systems have shown that considering presence of outliers while solving computer vision problems help boosting the state-of-the-art results. However, most of the systems either try just to detect outliers from the computer vision datasets or solve their problems by detecting and rejecting outliers before applying the method on the dataset
Path-Based Dominant-Set Clustering
No full textAlthough off-the-shelf clustering algorithms, such as those based on spectral graph theory, do a pretty good job at finding clusters of arbitrary shape and structure, they are inherently unable to satisfactorily deal with situations involving the presence of cluttered backgrounds. On the other hand, dominant sets, a generalization of the notion of maximal clique to edge-weighted graphs, exhibit a complementary nature: they are remarkably effective in dealing with background noise but tend to favor compact groups. In order to take the best of the two approaches, in this paper we propose to combine path-based similarity measures, which exploit connectedness information of the elements to be clustered, with the dominant-set approach. The resulting algorithm is shown to consistently outperform standard clustering methods over a variety of datasets under severe noise conditions
Interactive Image Segmentation Using Constrained Dominant Sets
No full textWe propose a new approach to interactive image segmentation based on some properties of a family of quadratic optimization problems related to dominant sets, a well-known graph-theoretic notion of a cluster which generalizes the concept of a maximal clique to edge-weighted graphs. 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. The resulting algorithm can deal naturally with any type of input modality, including scribbles, sloppy contours, and bounding boxes, and is able to robustly handle noisy annotations on the part of the user. Experiments on standard benchmark datasets show the effectiveness of our approach as compared to state-of-the-art algorithms on a variety of natural images under several input conditions
Simultaneous Clustering and Outlier Detection using Dominant sets
No full textWe present a unified approach for simultaneous clustering and outlier detection in data. We utilize some properties of a family of quadratic optimization problems related to dominant sets, a well-known graph-theoretic notion of a cluster which generalizes the concept of a maximal clique to edge-weighted graphs. Unlike most (all) of the previous techniques, in our framework the number of clusters arises intuitively and outliers are obliterated automatically. The resulting algorithm discovers both parameters from the data. Experiments on real and on large scale synthetic dataset demonstrate the effectiveness of our approach and the utility of carrying out both clustering and outlier detection in a concurrent manner
Constrained Dominant Sets for Retrieval
No full textLearning new global relations based on an initial affinity of the database objects has shown significant improvements in similarity retrievals. Locally constrained diffusion process is one of the recent effective tools in learning the intrinsic manifold structure of a given data. Existing methods, which constrain the diffusion process locally, have problems - manual choice of optimal local neighborhood size, do not allow for intrinsic relation among the neighbors, fix initialization vector to extract dense neighbor - which negatively affect the affinity propagation. We propose a new approach, which alleviate these issues, based on some properties of a family of quadratic optimization problems related to dominant sets, a well-known graph-theoretic notion of a cluster which generalizes the concept of a maximal clique to edge-weighted graphs. 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 dominant set cluster which is constrained to contain user-provided query. Experimental results on standard benchmark datasets show the effectiveness of the proposed approach
Dominant-Set Clustering Using Multiple Affinity Matrices
No full textPairwise (or graph-based) clustering algorithms typically assume the existence of a single affinity matrix, which describes the similarity between the objects to be clustered. In many practical applications, however, several similarity relations might be envisaged and the problem arises as to how properly select or combine them. In this paper we offer a solution to this problem for the case of dominant sets, a well-known formalization of the notion of a cluster, which generalizes the notion of maximal clique to edge-weighted graphs and has intriguing connections to evolutionary game theory. Specifically, it has been shown that dominant sets can be bijectively related to Evolutionary Stable Strategies (ESS) - a classic notion of equilibrium in the evolutionary game theory field - of a so-called “clustering game”. The clustering game is a non-cooperative game between two-players, where the objects to cluster form the set of strategies, while the affinity matrix provides the players’ payoffs. The proposed approach generalizes dominant sets to multiple affinities by extending the clustering game, which has a single payoff, to a multi-payoff game. Accordingly, dominant sets in the multi-affinity setting become equivalent to ESSs of a corresponding multi-payoff clustering game, which can be found by means of so-called Biased Replicator Dynamics. Experiments conducted over standard benchmark datasets consistently show that the proposed combination scheme allows one to substantially improve the performance of dominant-set clustering over its single-affinity counterpart
Multi-Object Tracking using Dominant Sets iet
No full textMulti-object tracking is an interesting but challenging task in the field of computer vision. Most previous works based on data association techniques merely take into account the relationship between detection responses in a locally limited temporal domain, which makes them inherently prone to identity switches and difficulties in handling long-term occlusions. In this study, a dominant set clustering based tracker is proposed, which formulates the tracking task as a problem of finding dominant sets in an auxiliary edge weighted graph. Unlike most techniques which are limited in temporal locality (i.e. few frames are considered), the authors utilised a pairwise relationships (in appearance and position) between different detections across the whole temporal span of the video for data association in a global manner. Meanwhile, temporal sliding window technique is utilised to find tracklets and perform further merging on them. The authors' robust tracklet merging step renders the tracker to long term occlusions with more robustness. The authors present results on three different challenging datasets (i.e. PETS2009-S2L1, TUD-standemitte and ETH dataset ('sunny day' sequence)), and show significant improvements compared with several state-of-art methods
Detecting conversational groups in images and sequences: a robust game-theoretic approach
Full text linkDetecting groups is becoming of relevant interest as an important step for scene (and especially activity) understanding. Differently from what is commonly assumed in the computer vision community, different types of groups do exist, and among these, standing conversational groups (a.k.a. F-formations) play an important role. An F-formation is a common type of people aggregation occurring when two or more persons sustain a social interaction, such as a chat at a cocktail party. Indeed, detecting and subsequently classifying such an interaction in images or videos is of considerable importance in many applicative contexts, like surveillance, social signal processing, social robotics or activity classification, to name a few. This paper presents a principled method to approach to this problem grounded upon the socio-psychological concept of an F-formation. More specifically, a game-theoretic framework is proposed, aimed at modeling the spatial structure characterizing F-formations. In other words, since F-formations are subject to geometrical configurations on how humans have to be mutually located and oriented, the proposed solution is able to account for these constraints while also statistically modeling the uncertainty associated with the position and orientation of the engaged persons. Moreover, taking advantage of video data, it is also able to integrate temporal information over multiple frames utilizing the recent notions from multi-payoff evolutionary game theory. The experiments have been performed on several benchmark datasets, consistently showing the superiority of the proposed approach over the state of the art, and its robustness under severe noise conditions
A Game-Theoretic Probabilistic Approach For Detecting Conversational Groups
No full textA standing conversational group (also known as F-formation) occurs when two or more people sustain a social interaction, such as chatting at a cocktail party. Detecting such interactions in images or videos is of fundamental importance in many contexts, like surveillance, social signal processing, social robotics or activity classification. This paper presents an approach to this problem by modeling the socio-psychological concept of an F-formation and the biological constraints of social attention. Essentially, an F-formation defines some constraints on how subjects have to be mutually located and oriented while the biological constraints defines the plausible zone in which persons can interact. We develop a game-theoretic framework embedding these constraints, which is supported by a statistical modeling of the uncertainty associated with the position and orientation of people. First, we use a novel representation of the affinity between pairs of people expressed as a distance between distributions over the most plausible oriented region of attention.Additionally, we integrate temporal information over multiple frames to smooth noisy head orientation and pose estimates, solve ambiguous situations and establish a more precise social context. We do this in a principled way by using recent notions from multi-payoff evolutionary game theory. Experiments on several benchmark datasets consistently show the superiority of the proposed approach over state of the art and its robustness under severe noise conditions
Poisoning Complete-Linkage Hierarchical Clustering
Full text linkAbstract. Clustering algorithms are largely adopted in security appli-cations as a vehicle to detect malicious activities, although few attention has been paid on preventing deliberate attacks from subverting the clus-tering process itself. Recent work has introduced a methodology for the security analysis of data clustering in adversarial settings, aimed to iden-tify potential attacks against clustering algorithms and to evaluate their impact. The authors have shown that single-linkage hierarchical cluster-ing can be severely affected by the presence of a very small fraction of carefully-crafted poisoning attacks into the input data, highlighting that the clustering algorithm may be itself the weakest link in a security sys-tem. In this paper, we extend this analysis to the case of complete-linkage hierarchical clustering by devising an ad hoc poisoning attack. We verify its effectiveness on artificial data and on application examples related to the clustering of malware and handwritten digits.
- …
