Publication
Theoretical Analysis of Active Contours on Graphs
Christos Sakaridis,
Kimon Drakopoulos,
and Petros Maragos
SIAM Journal on Imaging Sciences (SIIMS), 2017
[PDF]
[BibTeX]
[arXiv]
Overview
We introduce geometric approximations of gradient and curvature on arbitrary graphs, which enable a straightforward extension of active contour models that are formulated through level sets to such general inputs. We prove convergence in probability of our gradient approximation to the true gradient value and derive an asymptotic upper bound for the error of this approximation for the class of random geometric graphs. Two different approaches for the approximation of curvature are presented, and both are also proved to converge in probability in the case of random geometric graphs. We propose neighborhood-based filtering on graphs to improve the accuracy of the aforementioned approximations and define two variants of Gaussian smoothing on graphs which include normalization in order to adapt to graph nonuniformities. The performance of our active contour framework on graphs is demonstrated in the segmentation of regular images and geographical data defined on arbitrary graphs, using geodesic active contours and active contours without edges as representative models in our experiments.
Results
We equip two exemplar active contour models, namely geodesic active contours and active contours without edges, with our approximations of their two main terms, i.e. gradient and curvature, and apply iterative algorithms that stem from the PDE formulations of these models to segment arbitrary graphs defined from regular images or containing geographical data. In the following, we present selected experiments and results from our article.
Geodesic Active Contours
We apply our algorithm for geodesic active contours on graphs to segment natural color images from the Berkeley Segmentation Dataset BSDS500. The segmentation results are shown below, where the final contour is marked white.
|
|
|
|
|
Our approach is particularly tailored for segmenting geographical data with arbitrary spatial configuration, for which the two spatial coordinates are longitude and latitude and each vertex of the graph corresponds to a sample of a real-valued signal. We demonstrate two examples of this application below:
- measurements of the signal strength of a cellular network across the north-eastern part of Attica basin, Greece.
- average annual wind speed data from Epirus territory, Greece.
| Normalized input signal | Segmentation result - contour interior in red |
|---|---|
|
|
|
|
Active Contours Without Edges
We demonstrate the generality of our proposed approximations as a base for translating various active contour models to graphs by additionally employing an alternative model, namely active contours without edges, in our experiments. We use our algorithm for active contours without edges on graphs to segment images from BSDS500 as well as a grayscale image with four coins. The segmentation results presented below are of high quality, e.g. capturing the thin feathers at the eagle's wing very precisely.
|
|
|
Code
We provide a MATLAB implementation of our active contour framework on graphs.
Citation
Please cite our publication if you find our method's formulation or implementation useful for your work.