Abstract
Szemeredi’s regularity lemma is a deep result from extremal
graph theory which states that every graph can be well-approximated by
the union of a constant number of random-like bipartite graphs, called
regular pairs. Although the original proof was non-constructive, efficient
(i.e., polynomial-time) algorithms have been developed to determine regular
partitions for arbitrary graphs. This paper reports a first attempt at
applying Szemeredi’s result to computer vision and pattern recognition
problems. Motivated by a powerful auxiliary result which, given a partitioned
graph, allows one to construct a small reduced graph which inherits
many properties of the original one, we develop a two-step pairwise
clustering strategy in an attempt to reduce computational costs while
preserving satisfactory classification accuracy. Specifically, Szemeredi’s
partitioning process is used as a preclustering step to substantially reduce
the size of the input graph in a way which takes advantage of the
strong notion of edge-density regularity. Clustering is then performed on
the reduced graph using standard algorithms and the solutions obtained
are then mapped back into the original graph to create the final groups.
Experimental results conducted on standard benchmark datasets from
the UCI machine learning repository as well as on image segmentation
tasks confirm the effectiveness of the proposed approach.
Original language | Undefined |
---|---|
Title of host publication | Energy Minimization Methods in Computer Vision and Pattern Recognition Energy Minimization Methods in Computer Vision and Pattern Recognition, 6th International Conference, EMMCVPR 2007 |
Place of Publication | Berlin |
Publisher | Springer |
Pages | 13-27 |
Number of pages | 15 |
ISBN (Print) | 978-3-540-74195-4 |
DOIs | |
Publication status | Published - 14 Aug 2007 |
Event | 6th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition, EMMCVPR 2007 - EZhou, Hubei, China Duration: 27 Aug 2007 → 29 Aug 2007 Conference number: 6 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer Verlag |
Volume | 4679 |
Conference
Conference | 6th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition, EMMCVPR 2007 |
---|---|
Abbreviated title | EMMCVPR |
Country/Territory | China |
City | EZhou, Hubei |
Period | 27/08/07 → 29/08/07 |
Keywords
- EWI-10951
- IR-61893
- METIS-245730