Abstract. In this paper, we revisit the notion of perimeter on graphs, introduced in El Chakik, Elmoataz, and Desquesnes [ Signal Process., 105 (2014), pp. 449–463], and we extend it to so-called inner and outer perimeters. We will also extend the notion of total variation on graphs. Thanks to the co-area formula, we show that discrete total variations can be expressed through these perimeters. Then, we propose a novel class of curvature operators on graphs that unifies both local and nonlocal mean curvature on an Euclidean domain. This leads us to translate and adapt the notion of the mean curvature flow on graphs as well as the level set mean curvature, which can be seen as approximate schemes. Finally, we exemplify the usefulness of these methods in image processing, 3D point cloud processing, and high dimensional data classification.

Visual saliency is a computational process that seeks to identify the most attention drawing regions from a visual point. In this study, the authors propose a new algorithm to estimate the saliency based on partial difference equations (PDEs) method. A local or non‐local graph is first constructed from the geometry of images. Then, the transcription of PDE on graph is done and resolved by using the mean curvature flow that can be used to perform regularisation and the Eikonal equation for segmentation. Finally, an extended region adjacency graph is built, which is extended with a k ‐nearest neighbour graph, in the mean RGB colour space of each region in order to estimate saliency. The proposed algorithm allows to unify a local or non‐local graph processing for saliency computing. Furthermore, it works on discrete data of arbitrary topology. For evaluation, the proposed method is tested on two different datasets and 3D point clouds. Extensive experimental results show the applicability and effectiveness of the proposed algorithm.

In this paper, we study a nonlocal variational problem which consists of minimizing in $L^2$ the sum of a quadratic data fidelity and a regularization term corresponding to the $L^p$-norm of the nonlocal gradient. In particular, we study convergence of the numerical solution to a discrete version of this nonlocal variational problem to the unique solution of the continuum one. To do so, we derive an error bound and highlight the role of the initial data and the kernel governing the nonlocal interactions. When applied to variational problems on graphs, this error bound allows us to show the consistency of the discretized variational problem as the number of vertices goes to infinity. More precisely, for networks in convergent graph sequences (simple and weighted deterministic dense graphs as well as random inhomogeneous graphs), we prove convergence and provide rates of convergence of solutions for the discrete models to the solution of the continuum problem as the number of vertices grows.

This paper is devoted to the study of the discrete formulations of the weighted Total Variation (TV) based on upwind schemes that have been proposed for imaging problems in a local setting in [1] and in a non-local setting for graphs and point-clouds in [2]. We focus on two new symmetric formulations based on the l2and l∞norms respectively and propose a dedicated optimization algorithm to solve convex problems based on such TV penalties. We demonstrate the theoretical and practical interest of such formulations for image processing tasks.

In this paper we introduce a new family of partial difference operators on graphs and study equations involving these operators. This family covers local variational $p$-Laplacian, $\infty$-Laplacian, nonlocal $p$-Laplacian and $\infty$-Laplacian, $p$-Laplacian with gradient terms, and gradient operators used in morphology based on the partial differential equation. We analyze a corresponding parabolic equation involving these operators which enables us to interpolate adaptively between $p$-Laplacian diffusion-based filtering and morphological filtering, i.e., erosion and dilation. Then, we consider the elliptic partial difference equation with its corresponding Dirichlet problem and we prove the existence and uniqueness of respective solutions. For $p=\infty$, we investigate the connection with Tug-of-War games. Finally, we demonstrate the adaptability of this new formulation for different tasks in image and point cloud processing, such as filtering, segmentation, clustering, and inpainting.

In this paper we propose to use the Eikonal equation on graphs for generalized data clustering. We introduce a new potential function that favors the creation of homogeneous clusters together with an iterative algorithm that place seeds vertices at smart locations. Oversegmentation application shows the effectiveness of our approach and gives results comparable to the state-of-the-art methods.

In this paper we introduce a new unified framework for multi-scale detail manipulation of graph signals. The key to this unification is to model any kind of data as signals defined on appropriate weighted graphs. Graph signals are represented as the sum of successive layers, each capturing a given scale of detail. Detail layers are obtained through a series of regularization procedures based on total variation penalization over graphs. Layers are then processed separately before being recombined, thus achieving detail manipulation. The benefit of the approach is shown on images, 3D meshes and 3D colored point clouds.

In this paper, we consider the adaptation of two Partial Differential Equations (PDEs) on weighted graphs, p-Laplacian and eikonal equations, for semi-supervised classification tasks. These equations are a discrete analogue of well known geometric PDEs, which are widely used in image processing. While the p-Laplacian on graphs was intensively used in data classification, few works relate to the eikonal equation for data classification. The methods are illustrated through semi-supervised classification tasks on databases, where we compare the two algorithms. The results show that these methods perform well regarding the state-of-the-art and are applicable to the task of semi-supervised classification.

Partial difference equations (PDEs) and variational methods for image processing on Euclidean domains spaces are very well established because they permit to solve a large range of real computer vision problems. With the recent advent of many 3D sensors, there is a growing interest in transposing and solving PDEs on surfaces and point clouds. In this paper, we propose a simple method to solve such PDEs using the framework of PDEs on graphs. This latter approach enables us to transcribe, for surfaces and point clouds, many models and algorithms designed for image processing. To illustrate our proposal, three problems are considered: (1) p -Laplacian restoration and inpainting; (2) PDEs mathematical morphology; and (3) active contours segmentation.

In this paper, we propose an adaptation and transcription of the mean curvature level set equation on a general discrete domain (weighted graphs with arbitrary topology). We introduce the perimeters on graph using difference operators and define the curvature as the first variation of these perimeters. Our proposed approach of mean curvature unifies both local and non local notions of mean curvature on Euclidean domains. Furthermore, it allows the extension to the processing of manifolds and data which can be represented by graphs.

We propose a transcription on graphs of recent continuous global active contours proposed for image segmentation to address the problem of binary partitioning of data represented by graphs. To do so, using the framework of Partial difference Equations (PdEs), we propose a family of nonlocal regularization functionals that verify the co-area formula on graphs. The gradients of a sub-graph are introduced and their properties studied. Relations, for the case of a sub-graph, between the introduced nonlocal regularization functionals and nonlocal discrete perimeters are exhibited and the co-area formula on graphs is introduced. Finally, nonlocal global minimizers can be considered on graphs with the associated energies. Experiments show the benefits of the approach for nonlocal image segmentation and high dimensional data clustering.

The generalization of mathematical morphology to multivariate images is addressed in this paper. The proposed approach is fully unsupervised and consists in constructing a complete lattice from an image as a rank transformation together with a learned ordering of vectors. This unsupervised ordering of vectors relies on three steps: dictionary learning, manifold learning and out of sample extension. In addition to providing an efficient way to construct a vectorial ordering, nonlocal configurations based on color patches can be easily handled and provide much better results than with classical local morphological approaches.

In this paper we propose an adaptation of PDEs level sets over weighted graphs of arbitrary structure, based on PdEs and using a framework of discrete operators. A general PDEs level sets formulation is presented and an algorithm to solve such equation is described. Some transcriptions of well-known models under this formalism, as the mean-curvature-motion or active contours, are also provided. Then, we present several applications of our formalism, including image segmentation with active contours, using weighted graphs of arbitrary topologies.

In this paper, we introduce fast and robust digital algorithms for solving the Dirichlet problem with ∞-harmonic functions on graphs. Several PDEs and variational techniques have been proposed for a number of interpolation problems. Our motivation for this work is to extend some of these PDEs on graphs to deal with interpolation problems with a new approach in a discrete framework using the ∞-Laplacian on weighted graphs arbitrary topology. We show the experimental results for some applications of image interpolation that demonstrate the efficiency of our method and point out the interest of the novel algorithm with p = ∞ for interpolation problems.

A new hierarchical representation of general discrete data sets living on graphs is proposed. The approach takes advantage of recent works on graph regularization. The different levels of the hierarchy are discovered as the regularization process is performed. The role of the merging criterion that is common to hierarchical representations is greatly reduced due to the regularization step. This yields a robust representation of data sets. Moreover, the approach is particularly well adapted to the processing of digital images, where nonlocal processing allows to better handle repetitive patterns usually present in natural images.

Mathematical morphology (MM) offers a wide range of operators to address various image processing problems. These operators can be defined in terms of algebraic (discrete) sets or as partial differential equations (PDEs). In this paper, we introduce a nonlocal PDEs-based morphological framework defined on weighted graphs. We present and analyze a set of operators that leads to a family of discretized morphological PDEs on weighted graphs. Our formulation introduces nonlocal patch-based configurations for image processing and extends PDEs-based approach to the processing of arbitrary data such as nonuniform high dimensional data. Finally, we show the potentialities of our methodology in order to process, segment and classify images and arbitrary data.

Weighted Graph regularization provides a rich framework that allows to regularize functions defined over the vertices of a weighted graph. Until now, such a framework has been only defined for real or multivalued functions hereby restricting the regularization framework to numerical data. On the other hand, several kernels have been defined on structured objects such as strings or graphs. Using definite positive kernels, each original object is associated by the ``kernel trick'' to one element of an Hilbert space. As a consequence, this paper proposes to extend the weighted graph regularization framework to objects implicitly defined by their kernel hereby performing the regularization within the Hilbert space associated to the kernel. This work opens the door to the regularization of structured objects.

We present an inpainting method for images and videos based on nonlocal discrete p-Laplace regularization on weighted graphs. Our work has the advantage of unifying local geometric methods and nonlocal exemplar-based ones in the same framework. Our image inpainting benefits from local and nonlocal regularities within the image. In addition to that, our video inpainting exploits temporal and spatial redundancies in order to obtain high quality results by considering a video sequence as a volume and not as a sequence of still frames. However, our method does not employ any motion estimation for video inpainting. Experiments demonstrate that our nonlocal method outperforms the local one by completing missing data with finer and more consistent details for textured and non-textured images and videos.

The main tools of Mathematical Morphology are a broad class of nonlinear image operators. They can be defined in terms of algebraic set operators or as Partial Differential Equations (PDEs). We propose a framework of partial difference equations on arbitrary graphs for introducing and analyzing morphological operators in local and non local configurations. The proposed framework unifies the classical local PDEs-based morphology for image processing, generalizes them for non local configurations and extends them to the processing of any discrete data living on graphs.

We present local and nonlocal algorithms for video denoising based on discrete regularization on graphs. The main difference between video and image denoising is the temporal redundancy in video sequences. Recent works in the literature showed that motion compensation is counter-productive for video denoising. Our algorithms do not require any motion estimation. In this paper, we consider a video sequence as a volume and not as a sequence of frames. Hence, we combine the contribution of temporal and spatial redundancies in order to obtain high quality results for videos. To enhance the denoising quality, we develop a nonlocal method that benefits from local and nonlocal regularities within the video. Experiments show that the nonlocal method outperforms the local one by preserving finer details at the expense of an increase in the computational effort. We propose an optimized method that is faster than the nonlocal approach, while producing equally attractive results.

In this paper we present a method for impulse noise removal that makes use of spectral clustering and graph regularization. The image is modeled as a graph and local spectral analysis is performed to identify noisy and noise free pixels. On the set of noise free pixels, a topology adapted graph regularization is performed. Experimental results show the benefits of the proposed approach regarding the standard VMF when noise proportion is high.

In this paper we present a simple colorization method that relies on nonlocal graph regularization. We introduce nonlocal discrete differential operators and a family of weighted p-Laplace operators. Then, p-Laplace regularization on weighted graphs problem is presented and the associated filter family. Image colorization is then considered as a graph regularization problem for a function mapping vertices to chrominances. Several results illustrate our framework and demonstrate the benefits of nonlocal graph regularization for image colorization.

In this paper, a novel approach to mathematical morphology operations is proposed. Morphological operators based on partial differential equations (PDEs) are extended to weighted graphs of the arbitrary topologies by considering partial difference equations. We focus on a general class of morphological filters, the levelings; and propose a novel approach of such filters. Indeed, our methodology recovers classical local PDEs-based levelings in image processing, generalizes them to nonlocal configurations and extends them to process any discrete data that can be represented by a graph. Experimental results show applications and the potential of our levelings to textured image processing, region adjacency graph based multiscale leveling and unorganized data set filtering.

We introduce a nonlocal discrete regularization framework on weighted graphs of the arbitrary topologies for image and manifold processing. The approach considers the problem as a variational one, which consists of minimizing a weighted sum of two energy terms: a regularization one that uses a discrete weighted p-Dirichlet energy and an approximation one. This is the discrete analogue of recent continuous Euclidean nonlocal regularization functionals. The proposed formulation leads to a family of simple and fast nonlinear processing methods based on the weighted p-Laplace operator, parameterized by the degree p of regularity, the graph structure and the graph weight function. These discrete processing methods provide a graph-based version of recently proposed semi-local or nonlocal processing methods used in image and mesh processing, such as the bilateral filter, the TV digital filter or the nonlocal means filter. It works with equal ease on regular 2-D and 3-D images, manifolds or any data. We illustrate the abilities of the approach by applying it to various types of images, meshes, manifolds, and data represented as graphs.

Many practical applications in the field of medical image processing require robust and valid 3D image segmentation results. In this paper, we present a semi-automatic iterative segmentation approach for 3D medical image by combining a 2D boundary tracking algorithm and a boundary mapping process. Upon each of the consecutive slice, the boundary tracking process is accomplished in an alternate procedure of the morphological dilatation and the multi-label front propagation. The multi-label front propagation method is developed based on the minimal path theory and fast sweeping evolution method to ensure the efficiency, and speed of the boundary tracking algorithm. This 3D image segmentation approach can easily extract the close and smooth boundary of the desired object from a 2D medical image series. This approach is efficient and reliable, and requires very limited user intervention. Some experimental results are also presented to demonstrate the efficiency of this approach.

In this paper, we present a fast and simple discrete approach for active contours. It is based on discrete contour evolution, which operates on the boundary of digital shape, by iterative growth processes on the boundary of the shape. We consider a curve to be the boundary of a discrete shape. We attach at each point of the boundary a cost function and deform this shape according to that cost function. The method presents some advantages. It is a discrete method, which takes an implicit representation and uses discrete algorithm with a simple data structure.

We address the problem of automatically segmenting cell nuclei or cluster of cell nuclei in image medical microscopy. We present a system of automatic segmentation combining fuzzy clustering and multiple active contour models. An automatic initialization algorithm based on fuzzy clustering is used to robustly identify and classify all possible seed regions in the image. These seeds are propagated outward simultaneously to localize the final contours of all objects. We present examples of quantitative segmentation on biomedical images: segmentation of lobules in color images of histology and segmentation of nuclei in cytological images.

This article deals with the design of a system that automates the generation of image processing applications. Users describe tasks to perform on images and the system constructs a specific plan, which, after being executed, should yield the desired results. Our approach to this problem belongs to a more general category of systems for the supervision of a library of operators. The generation of an application is considered as the dynamic building of chains of image processing through the selection, parameter tuning and scheduling of existing operators. To develop such a system, we suggest to use a knowledge-rich resolution model and to integrate seven design rules. The Borg system has been developed following these prescriptions. It hinges on hierarchical, opportunistic and incremental planning by means of knowledge sources of the blackboard model, which enable to take into account the planning, evaluation and knowledge acquisition issues.