Triangle dissimilarity (part 1)

Locational (L), orientational (O) and scale (S) invariance are three imprtant invariances for 2D and 3D object recognition purposes. Many matching methods come with an increasing price when invariances are added. A good shape dissimilarity method should  have all three (LOS) with a small price tag. The simplest shapes are segments and triangles.

Usually, the application is about sparse point clouds, after a preliminary object detection and before a SLAM. Sparse PC matching or ditching is based on points, and then developing a nearest neighborhood (NN) characterization of each point is important. This characterization can be based directly on NN points, or NN segments and triangles.

How similar (or dissimilar) triangles are? Four dissimilarity measures come to mind:

1. vertex error (---) 
2. ratio of the overlapping area (---)
3. Groth (1989) triangle matching algorithm (LOS)
4. Cole (2006) planar triangle method (LOS)

The first two are rather 'metric', because they have to be made LOS invariant by centering to mean (L), minimizing by sparse rotation (O) and scaling e.g. by area (S). The Groth approach is naturally LOS.

Therefore, what kind of combinations of these triangle dissimilarity methods one can find for various uses? 

1 Mean vertex error requires a NN match between points. The error is 

$e(t_1,t_2)= 2\,mean_{p\in t_1, q=NN_1(p | t_2)} ||p-q||/(P_1+P_2),$ where $P_i$ is the perimeter length of the triangle $i$. Of course, the max error at the matching edges is also possible. The orientation difference can be eliminated by rotating other triangle (after both are centered to the origo): $e^*= \text{min}_{\theta\in[0,2\pi]} e(t_1,t_2 R(\theta))$, where $R(\theta)$ is the rotation operator (concerning directly the vertex points $PC(t,.)$ ) and $\Delta\theta:= \Delta\theta/2$ after each detection of the temporary minimum.

2 Ratio of the overlapping area is somewhat more tedious. One has to:

1. find all the segment intersections between two triangles $t_1$ and $t_2$,
2. create a Delaunay triangularization $T$ (fast for max 12 points),
3. check if center points of $t\in T$ are within either triangle $\rightarrow$ two subsets $T_1,T_2\subset T$,
4. then sum up the triangle areas at the intersection and the union:

The overlapping ratio $t$ is now: \[t= \frac{\sum_{t\in T_1\cap T_2} A_t}{\sum_{t\in T_1\cup T_2} A_t}\].

The above Fig. shows two triangles, their vertices and common intersection points and the common triangularization. Red triangles are outside the union $t_1\cup t_2$.

A similar rotational search can be done here as in the case of the vertex error.

3 The Groth approach separates the shape and the size. The shape descriptor of a triangle $t$ is
a pair $(r,c)$ where $r=b/a$ is the ratio of the largest length $b=\|\bar{b}\|$ and the shortest length $a=\|\bar{a}\|$ among the edges of $t$. The corresponding edge vectors are $\|-\bar{a}\|$ and
$\|\bar{b}\|$, both starting from the vertex $p_1$ between the edges in question.
$C=-\bar{a}^0\cdot\bar{b}^0=\cos\phi$ is the $cos(\phi)$ value of the angle $\phi$ at the vertex $p_1$.

If one assumes a radial perturbance $\epsilon$ at each vertex point, one gets the following
perturbation $(\delta_r, \delta_C)$ at the shape descriptor: ${\delta}_r^2 = 2r^2F$, 

$\delta_C^2 = 2S^2F+ 3C^2F^2$, where $S=\sqrt{1-C^2}$ is the $sin$ value of the angle at 

the vertex 1. A common coefficient $F$ shortens the equations above:
\[ F= \epsilon^2(1/b^2- \frac{C}{ab}+1/a^2) \]

For two triangles $t_1$ and $t_2$ with shape descriptors $(r_1,C_1)$ and $(r_2,C_2)$,
a match happens if the following inequality holds:
$$
min\left(  \frac{(r_1-r_2)^2}{\delta_{r1}^2+ \delta_{r2}^2},
           \frac{(C_1-C_2)^2}{\delta_{C1}^2+ \delta_{C2}^2}   \right) < 1
$$

4 The planar triangle method focuses on two characteristics of a triangle $t$. The area $A_t=\sqrt{s(s-a)(s-b)(s-c)}$ is defined by Heron's formula, where $s=(a+b+c)/2$ is the
half-length of the perimeter of the triangle $t$ and $a,b,c$ are the side lengths. The second
characteristic entity is the polar moment $I_t=A_t(a^2+b^2+c^2)/36$ The area and the polar
moment are rather independent of each other. Naturally, the scale invariance requires
scaling by the area, and position invariance centering to the triangle mean.

One needs a matrix
$H_A=[A_{t,\bar{a}},A_{t,\bar{b}},A_{t,\bar{c}}]\in\mathbb{R}^{1\times 6}$, which is
an assembly of three sub-matrices, each by differentiation of the area w.r.t. each vertex.
Similarly, $H_I= [I_{t,\bar{a}},I_{t,\bar{b}},I_{t,\bar{c}}]$. See the details of the terms
of these two matrices from the publication Cole (2006). Now, one can state
the variances of area and polar moment:
$$
\begin{eqnarray}
    \sigma_A^2&=& \sigma^2 H_A \cdot H_A\\
    \sigma_I^2&=& \sigma^2 H_I \cdot H_I^T\\
\end{eqnarray}
$$

Just as previously, the final test for matching of triangles $t_1,t_2$ is:
$$
  min\left(  \frac{(A_1-A_2)^2}{\sigma_{A1}^2+ \sigma_{A2}^2},
           \frac{(I_1-I_2)^2}{\sigma_{I1}^2+ \sigma_{I2}^2}   \right) < 1,
$$
where the upper limit can be chosen depending on the application (here 2 s.t.d's have been chosen).

So, how are these four dissimilarities related in the presence of noise? That is a good topic for another blog post.