Grouping with Asymmetric Affinities: A Game-Theoretic Perspective
Abstract
Pairwise grouping and clustering approaches have traditionally worked under the assumption that the similarities or compatibilities between the elements to be grouped are symmetric. However, asymmetric compatibilities arise naturally in many areas of computer vision and pattern recognition. Hence, there is a need for a new generic approach to clustering and grouping that can deal with asymmetries in the compatibilities. In this paper, we present a generic framework for grouping and clustering derived from a game-theoretic formalization of the competition between the hypotheses of group membership, and apply it to perceptual grouping. In the proposed approach groups correspond to evolutionary stable strategies, a classic notion in evolutionary game theory. We also provide a combinatorial characterization of the stable strategies, and, hence, of the elements that belong to a group. Experiments show that our approach outperforms both state-of-the-art clustering-based perceptual grouping approacheswith symmetric compatibilities, and other approaches explicitly designed to make use of asymmetric compatibilities.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Finding a large set of correspondences with high mutual compatibility can be formulated as an inlier selection process of a non-cooperative game.
“Finding a large set of correspondences that express a high level of mutual compatibility can be formulated as an inlier selection process of a non-cooperative game [101].”
From Registration of 3D Point Clouds and Meshes: A Survey from Rigid to Nonrigid (2013) · cites this paper as [101]
Cites
Normalized cuts and image segmentation
Shi, J., & Malik, J. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.868688 · Cited by 15,842 · see citing works
(2011) · SpringerReference · doi:10.1007/springerreference_60360 · Cited by 2,894 · see citing works
Clustering appearances of objects under varying illumination conditions
Ho, J., Yang, M.-H., Lim, J., et al. (2003) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2003.1211332 · Cited by 539 · see citing works
Structural Saliency: The Detection Of Globally Salient Structures using A Locally Connected Network
Sha'asua, A., & Ullman, S. (2005) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/ccv.1988.590008 · Cited by 539 · see citing works
Trace inference, curvature consistency, and curve detection
Parent, P., & Zucker, S. W. (1989) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.31445 · Cited by 485 · see citing works
Mumford, D. B. (1994) · Springer eBooks · doi:10.1007/978-1-4612-2628-4_31 · Cited by 463 · see citing works
Pairwise data clustering by deterministic annealing
Hofmann, T., & Buhmann, J. M. (1997) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.566806 · Cited by 447 · see citing works
van Damme, E. E. C. (1994) · European Economic Review · doi:10.1016/0014-2921(94)90121-x · Cited by 437 · see citing works
Filling-in the gaps: The shape of subjective contours and a model for their generation
Ullman, S. (1976) · Biological Cybernetics · doi:10.1007/bf00337043 · Cited by 272 · see citing works
Quantitative measures of change based on feature organization: eigenvalues and eigenvectors
Sarkar, S., & Boyer, K. L. (1996) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.1996.517115 · Cited by 213 · see citing works
Classification with nonmetric distances: image retrieval and class representation
Jacobs, D. W., Weinshall, D., & Gdalyahu, Y. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.862197 · Cited by 210 · see citing works
A new graph-theoretic approach to clustering and segmentation
Pavan, M., & Pelillo, M. (2003) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2003.1211348 · Cited by 177 · see citing works
Self-citationOptimal cluster preserving embedding of nonmetric proximity data
Röth, V., Laub, J., Kawanabe, M., et al. (2003) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2003.1251147 · Cited by 171 · see citing works
Figure-ground discrimination: a combinatorial optimization approach
Hérault, L., & Horaud, R. (1993) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.232076 · Cited by 143 · see citing works
Quantitative Measures of Change Based on Feature Organization: Eigenvalues and Eigenvectors
Sarkar, S., & Boyer, K. L. (1998) · Computer Vision and Image Understanding · doi:10.1006/cviu.1997.0637 · Cited by 132 · see citing works
Radial projection: an efficient update rule for relaxation labeling
Parent, P., & Zucker, S. W. (1989) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.31449 · Cited by 99 · see citing works
A Comparison of Measures for Detecting Natural Shapes in Cluttered Backgrounds
Williams, L. R., & Thornber, K. K. (1999) · International Journal of Computer Vision · doi:10.1023/a:1008187804026 · Cited by 97 · see citing works
The response of excitable membrane models to a cyclic input
Holden, A. V. (1976) · Biological Cybernetics · doi:10.1007/bf00326666 · Cited by 67 · see citing works
Grouping with Directed Relationships
Yu, S. X., & Shi, J. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44745-8_19 · Cited by 28 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Registration of 3D Point Clouds and Meshes: A Survey from Rigid to Nonrigid
Tam, G. K. L., Cheng, Z.-Q., Lai, Y.-K., Langbein, F. C., Liu, Y., Marshall, D., Martin, R. R., Sun, X.-F., & Rosin, P. L. (2013) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2012.310 · Cited by 679 · see citing works
- Authors
- Torsello, A., Bulo, S. R., & Pelillo, M.
- Affiliations
- Ca' Foscari University of Venice (IT)
- ORCID
- Pelillo, M.
- Venue
- 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition - Volume 1 (CVPR'06)
- Publisher
- IEEE
- Published
- 2006-07-10
- Volume
- 1
- Pages
- 292-299
- ISSN
- 1063-6919 (ISSN-L)
- OpenAlex
- W2171707672
- Cited by
- 71
- References
- 19
- Citations by year
- 2025: 3 · 2024: 2 · 2021: 1 · 2020: 1 · 2019: 1 · 2018: 3 · 2017: 9 · 2016: 6 · 2015: 6 · 2014: 8 · 2013: 7 · 2012: 6
- FWCI
- 1.92
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings (publishedVersion)
- ARCA (Università Ca' Foscari Venezia) (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Advanced Clustering Algorithms Research
- Social Sciences › Economics, Econometrics and Finance › Economics and Econometrics › Game Theory and Voting Systems
- Social Sciences › Sociology and Political Science › Evolutionary Game Theory and Cooperation
- Keywords
- perceptual grouping, clustering, evolutionarily stable strategy, evolutionary game theory, combinatorial characterization, computer vision
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
