Modelling Convex Shape Priors and Matching Based on the Gromov-Wasserstein Distance

Abstract

We present a novel convex shape prior functional with potential for application in variational image segmentation. Starting point is the Gromov-Wasserstein Distance which is successfully applied in shape recognition and classification tasks but involves solving a non-convex optimization problem and which is non-convex as a function of the involved shape representations. In two steps we derive a convex approximation which takes the form of a modified transport problem and inherits the ability to incorporate vast classes of geometric invariances beyond rigid isometries. We propose ways to counterbalance the loss of descriptiveness induced by the required approximations and to process additional (non-geometric) feature information. We demonstrate combination with a linear appearance term and show that the resulting functional can be minimized by standard linear programming methods and yields a bijective registration between a given template shape and the segmented foreground image region. Key aspects of the approach are illustrated by numerical experiments.

Appendix

Step 2 of the Proof of Proposition 4.5

We show by construction for any $\rho\in\mathcal{M}(\phi_{X\,\sharp} \mu_{X}, \phi_{Y\,\sharp}\mu_{Y})$ the existence of some $\mu\in\mathcal {M}(\mu_{X},\mu_{Y})$ such that ρ=ϕ _♯ μ. For any element (s _X ,s _Y )∈S _X ×S _Y construct the pre-image measure

where this element wise definition for each (x,y) is extended to all subsets of X×Y by

$$\mu_{(s_X,s_Y)}(\sigma) = \sum_{(x,y) \in\sigma} \mu_{(s_X,s_Y)}(x,y). $$

Now consider $\mu= \sum_{(s_{X},s_{Y}) \in S_{X} \times S_{Y}} \mu_{(s_{X},s_{Y})}$: First verify that it is indeed contained in $\mathcal {M}(\mu_{X},\mu_{Y})$:

since μ(x,y)≥0 for all (x,y). Furthermore

and likewise

for all measurable subsets σ⊆X×Y, σ _X ⊆X, σ _Y ⊆Y.

Now check whether ϕ _♯ μ=ρ:

Consequently any $\rho\in\mathcal{M}(\phi_{X\,\sharp} \mu_{X}, \phi_{Y\,\sharp}\mu_{Y})$ is also contained in $\phi_{\sharp}\mathcal{M}(\mu_{X},\mu_{Y})$ and the two sets are equal.