Ridge–Valley graphs: Combinatorial ridge detection using Jacobi sets

Ridges are one of the key features of interest in areas such as computer vision and image processing. Even though a significant amount of research has been directed to defining and extracting ridges some fundamental challenges remain. For example, the most popular ridge definition (height ridge) is not invariant under monotonic transformations and its global structure is typically ignored during numerical computations. Furthermore, many existing algorithms are based on numerical heuristics and are rarely guaranteed to produce consistent results. This paper reexamines a slightly different ridge definition that is consistent with all desired invariants. Nevertheless, we show that this definition results in similar structures compared to height ridges and that both formulations are equivalent for quadratic functions. Furthermore, this definition can be cast in the form of a degenerate Jacobi set, which allows insights into the global structure of ridges. In particular, we introduce the Ridge–Valley graph as the complete description of all ridges in an image. Finally, using the connection to Jacobi sets we describe a new combinatorial algorithm to extract the Ridge–Valley graph from sampled images guaranteed to produce a valid structure.

► We examine a ridge definition which fulfills all desired invariants.
► We compare said definition to the common height ridge definition.
► We formulate “Jacobi ridges” in the form of a non-generic Jacobi set.
► The Ridge–Valley graph, a global structure containing Jacobi ridges is defined.
► A new combinatorial algorithm is developed to extract a correct Ridge–Valley graph.