Hypergraphs are generalizations of graphs. In conventional graphs, the vertex set is partitioned into a number of pairs called edges. In hypergraphs, the vertex set is partitioned into a number of hyperedges with possibly more than two vertices. Hypergraphs are gaining popularity in image processing, as they can represent richer neighborhood relations than conventional graphs. Like conventional graphs, hypergraphs can be directed. Then, vertices in a hyperedge are partitioned into head set and tail set. This paper investigates the applicability of directed hypergraphs to interactive segmentation problems.

In the authors’ algorithm, pixels are grouped into a set of directed hyperedges by both spatial and chromatic proximity. A random walk process guides a pixel in the tail set to a pixel in the head set of a hyperedge until it reaches one of the pre-labeled pixels. An advantage of the hypergraph over the conventional graph is that context-dependent transition probability can be implemented more naturally. Experiments show that the directed hypergraph is superior to the undirected one, and the algorithm is comparable to the state of the art in terms of accuracy and speed. However, the performance metric used in this study is not tied to our perception; thus, the practical significance of the difference is not clear.

The paper is clearly written and provides a concise review of the field. If you are interested in image segmentation and familiar with graph algorithms, you will find the paper interesting.