Grouping with Directed Relationships
- Stella X. YU and Jianbo SHI
Lecture Notes in Computer Science 2134, pp. 283-297.
Third International Workshop on
Energy Minimization Methods in Computer Vision and Pattern Recognition
INRIASophia-Antipolis, France, September 3 - 5, 2001.
Grouping is a global partitioning process that integrates local cues
distributed over the entire image. We identify four types of
pairwise relationships, attraction and repulsion, each of which can
be symmetric or asymmetric. We represent these relationships with
two directed graphs. We generalize the normalized cuts criteria to
partitioning on directed graphs. Our formulation results in Rayleigh
quotients on Hermitian matrices, where the real part describes
undirected relationships, with positive numbers for attraction,
negative numbers for repulsion, and the imaginary part describes
directed relationships. Globally optimal solutions can be obtained
by eigendecomposition. The eigenvectors characterize the optimal
partitioning in the complex phase plane, with phase angle separation
determining the partitioning of vertices and the relative phase
advance indicating the ordering of partitions. We use directed
repulsion relationships to encode relative depth cues and
demonstrate that our method leads to simultaneous image segmentation
and depth segregation.
image segmentation, figure-ground, graph partitioning, repulsion, directed relationships