Shape Comparison and Gromov-Hausdorff Distance

Sushovan "Sush" MAJHI
Tulane University (January 21, 2020)

Scan the above QR or hit the following url: smajhi.com/gh-presentation

The Manifesto

  • Introduction to Shape Comparison
  • Hausdorff Distance
  • Gromov-Hausdorff Distance
  • Computing the Gromov-Hausdorff Distance
  • Questions, Discussions, and 🍕 Pizza.

Collaborators

Carola Wenk
Computer Science, Tulane

Jeffrey Vitter
Computer and Information Science, University of Mississippi

Motivation

1. Distinguish Shapes

circle

triangle
2. Classify Shapes

triangular

circular
3. Quality Guarantee

Map Construction from GPS data (Berlin)
https://mapconstruction.org

Shape Comparison

A shape can be modeled as a metric space $(X,d_X)$.

We need an appropriate notion of a distance measure $d_?(X,Y)$ so that


  • $d_?(X,Y)$ defines a pseudo-metric on the class of metric spaces.

  • $d_?(X,Y)$ large $\iff$ very different shape

  • $d_?(X,Y)$ small $\iff$ $X=Y$ up to a class of deformation.

Hausdorff Distance


Nearest neighbor distance (red points $\to$ green points).

Let $A,B\subseteq\mathbb{R}^N$. The directed Hausdorff distance from $A$ to $B$ is defined by $$\overrightarrow{d}_H(A,B)=\sup_{a\in A}\inf_{b\in B}\|a-b\|.$$
For any two compact $X,Y\subset\mathbb{R}^N$, $$d_H(X,Y)=\max\left\{\overrightarrow{d}_H(X,Y),\overrightarrow{d}_H(Y,X)\right\}$$
For any two compact $X,Y\subset(Z,d_Z)$, $$d^Z_H(X,Y)=\max\left\{\overrightarrow{d}^Z_H(X,Y),\overrightarrow{d}^Z_H(Y,X)\right\}$$
  1. $d^Z_H(X,Y)\geq0$,

  2. $d^Z_H(X,Y)=d^Z_H(Y,X)$,

  3. $d^Z_H(X,Y)=0\iff X=Y$, and

  4. $d^Z_H(A,C)\leq d^Z_H(A,B)+d^Z_H(B,C)$.
The Hausdorff distance induces a complete metric space on the set of all compact subsets of a metric space.

💡

$d_H$ is sensitive to Shape + Size + Placement.

Hausdorff under Isometry


$d_H($◤, ◢ $)=$ large.

Let $\mathcal{E}(N)$ denote the class of Euclidean isometries or distance preserving maps $T:\mathbb{R}^N\to\mathbb{R}^N$ i.e. $\|T(a)-T(b)\|=\|a-b\|$.

  1. For $N=1$, $T$ is translation or reflection.

  2. For $N=2$, $T$ is rotation, translation or reflection.
For $X,Y\subseteq\mathbb{R}^N$, we define $$d_{H,iso}(X,Y)=\inf\limits_{T\in\mathcal{E}(N)}d_H\left(X,T(Y)\right)$$
💡

$d_{H,iso}$ is sensitive to Shape + Size + Placement.
$d_{H,iso}($◤, ◢ $)=0$.

Gromov-Hausdorff Distance


How to compare shapes that do not have a common embedding?

Isometric Embedding

For two abstract metric spaces $(X,d_X)$ and $(Y,d_Y)$, we define $$d_{GH}(X,Y)=\inf\limits_{f,g,Z} d^Z_H(f(X),g(Y)).$$

$d_{GH}$ vs $d_{H,iso}$

Let $X,Y\subseteq(\mathbb{R}^N,\|\cdot\|)$ be compact. Then, both $d_{GH}(X,Y)$ and $d_{H,iso}(X,Y)$ are defined. $$d_{GH}(X,Y)\leq d_{H,iso}(X,Y)\leq c_N\sqrt{Md_{GH}(X,Y)},$$ where $M=\max\{diam(X),diam(Y)\}$.
For $X,Y\subseteq\mathbb{R}^1$, we have $$d_{GH}(X,Y)\leq d_{H,iso}(X,Y)\leq\left(1+\frac{1}{4}\right)d_{GH}(X,Y),$$ and the upper bound is tight.

Computing $d_{GH}$

For $|X|,|Y|\leq k$, computing $d_{GH}(X,Y)$ takes $O(2^k)$ time.
For $X,Y\subset\mathbb{R}^1$ and $|X|,|Y|\leq k$, computing $d_{H,iso}(X,Y)$ takes $O(k\log{k})$ time.
Sometimes, computing the exact optimal solution ($s_{opt}$) to an optimization problem is HARD.

💡

Computing an approximate solution ($s_{appx}$) is sometimes more efficient.
For $\rho>1$, if we have $$s_{opt}\leq s_{appx}\leq\rho s_{opt},$$ then the algorithm is called an approximation algorithm with an approximation factor $\rho$ .
$$d_{GH}(X,Y)\leq d_{H,iso}(X,Y)\leq\left(1+\frac{1}{4}\right)d_{GH}(X,Y),$$
💡

$d_{H,iso}$ approximates $d_{GH}$ with an approximate factor of $\left(1+\frac{1}{4}\right)$.

This Presentation

  • The framework is called RevealJS
  • Language: JavaScript
  • Platform: (modern) Web Browsers
  • Latex Support: MathJax
  • Features: Multiplexing, Notes, Timer, Autoslide, and more.
The speaker will now accept
QUESTIONS.

🤔