On the p-Laplacian and ∞-Laplacian on Graphs with Applications in Image and Data Processing

Elmoataz Abderrahim, Toutain Matthieu, Tenbrinck Daniel

Abstract

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, ∞-Laplacian, nonlocal p-Laplacian and ∞-Laplacian, p-Laplacian with gradient terms, and gradient operators used in morphology based on partial differential equation. We analyze a corresponding parabolic equation involving these operators which enables 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 = ∞, 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.