NCH: closing the gap

Introduction

Following up with my last post on NCH being roto-translation invariant, the idea of this one is to cover what I consider the most important gaps left by the original brief paper. My expectation is that doing this will help understand better why NCH works, and hopefully gain some insight into how to improve it.

Equivalence of formulations

Equation (4) in the paper says:

f_{i}^{r_{i}} (x) = \frac{1}{2 r _{i}} (r_{i}^{2} - ∣∣ x - (p_{i} + r_{i} n_{i}) ∣ ∣^{2})

However, the definition used in (2) is slightly different. Where does (2) come from? from expanding inner products in the second term of the sum:

∣∣ x - (p_{i} + r_{i} n_{i}) ∣ ∣^{2} = ⟨ x - p_{i} - r_{i} n_{i}, x - p_{i} - r_{i} n_{i} ⟩ = ⟨ x - p_{i}, x - p_{i} ⟩ + ⟨ x - p_{i}, - r_{i} n_{i} ⟩ + ⟨ - r_{i} n_{i}, x - p_{i} ⟩ + ⟨ - r_{i} n_{i}, - r_{i} n_{i} ⟩ = ∣∣ x - p_{i} ∣ ∣^{2} + (- 2 r_{i}) ⟨ n_{i}, x - p_{i} ⟩ + r_{i}^{2}

Thus, when you replace in the original definition:

f_{i}^{r_{i}} (x) = \frac{1}{2 r _{i}} (r_{i}^{2} - (∣∣ x - p_{i} ∣ ∣^{2} + (- 2 r_{i}) ⟨ n_{i}, x - p_{i} ⟩ + r_{i}^{2})) = \frac{1}{2 r _{i}} (- ∣∣ x - p_{i} ∣ ∣^{2} + (2 r_{i}) ⟨ n_{i}, x - p_{i} ⟩) = ⟨ n_{i}, x - p_{i} ⟩ - \frac{1}{2 r _{i}} ∣∣ x - p_{i} ∣ ∣^{2}

Which is exactly what we wanted

Fantastic ρᵢs and where to find them

In equation (3), the author says what the value of $ρ_i$ should be. He later defines $r_{i}$ as the largest value of $r$ such that $f_{i}^{r} (p_{j}) \leq 0\forall p_{j} \in P, j \neq = i$ . If you actually write it out:

0 \geq f_{i}^{r} (p_{j}) = ⟨ n_{i}, p_{j} - p_{i} ⟩ - \frac{1}{2 r _{i}} ∣∣ p_{j} - p_{i} ∣ ∣^{2}

And thus

\frac{1}{2 r _{i}} \geq \frac{⟨ n _{i} , p _{j} - p _{i} ⟩}{∣∣ p _{j} - p _{i} ∣ ∣ ^{2}}

If you gather the constraints for all $p_{j}$ s together, then you have that

ρ_i \geq p_{j} \in P, i \neq = j max \frac{⟨ n _{i} , p _{j} - p _{i} ⟩}{∣∣ p _{j} - p _{i} ∣ ∣ ^{2}}

And we further need that $ρ_i \geq 0$ in the case the supporting set actually ends up being just the linear half space (as should happen when fitting planes, for example).

ρs and θs

One interesting thing to notice out of the estimation of $ρ$ is that (in non-standard notation, but good enough for understanding):

ρ_{i} = p_{j} \in P, i \neq = j max {0, \frac{⟨ n _{i} , p _{j} - p _{i} ⟩}{∣∣ p _{j} - p _{i} ∣ ∣ ^{2}}} = p_{j} \in P, i \neq = j max {0, \frac{1}{∣∣ p _{j} - p _{i} ∣∣} ⟨ n_{i}, \frac{p _{j} - p _{i}}{∣∣ p _{j} - p _{i} ∣∣} ⟩} = p_{j} \in P, i \neq = j max {0, \frac{cos_sim ( n _{i} , p _{j} - p _{i} )}{∣∣ p _{j} - p _{i} ∣∣}}

Where $cos_sim$ denotes the cosine similarity between the two vectors; i.e. the angle between them. The following plots show the component in the maximum above for a given $p_{i}$ and $n_{i}$ (notice $p_{i}$ is NOT included in the plot, for obvious reasons), as well as the cosine similarity. You can tune the parameters:

Results are as you would expect: towards the outside of the surface (i.e. in the inverse direction as the normal) we get negative values, and towards the inside we get positive. However, contribution of a point to the maximum decreases really fast as you move away from the center point, because the cosine similarity is bounded between $- 1$ and $1$ , while the distance it is divided by can be arbitrarily large.

This may be an interesting way to construct an heuristic to speed up NCH: process only the $O (N)$ points that are closest when computing the rho.

Introduction

Equivalence of formulations

Fantastic ρᵢs and where to find them

ρs and θs

More in the “Non-Convex Hull” series

Related