Matching segments

There are a lot of heuristics for segment matching. Most of them can be grouped by how many invariances they support (none , L, O, S, LO, OS, LS). Note that the full invariance (LOS) makes all segments equal! We provide a 'none' version with 3 numerical indicators. It can be tuned to other 6 invariance categories easily. Two segments $s_1=(a,b)$ and $s_2=(c,d)$ with lengths $l_1,l_2$ and the orientation angle are depicted below.

The mutual orientation of two segments comes first.
We use edge vectors $v_1=a-b,\,v_2=c-d$ where the orientation of the edges ($(a,b)$ or $(b,a)$))  does not matter as long as we choose the orientation angle $\phi:=min(\phi,\pi-\phi)$ afterwards.
One can utilize the following differentials: $d\|v\|=v^0\cdot dv$ and: \[
d(v^0)= \|v\|^{-1}\left[I- v^0v^{0T}\right]dv
\]
So, e.g. the orientation $\phi=\cos^{-1}(v_1^0\cdot v_2^0)$ and, by defining $s=v_1^0\cdot v_2^0$ ($s$ for 'scalar product), one gets: \[
   d\phi= -(1-s^2)^{-1/2}\left[
      \|v_1\|^{-1}(1-v_1^0v_1^{0T})dv_1\cdot v_2^0 +
      \|v_2\|^{-1}(1-v_2^0v_2^{0T})dv_2\cdot v_1^0
     \right]
\]
To get a statistical limit $\Phi= ...$, one has to assume e.g. the i.i.d distribution of points, which
leads to: $dv_1=dv_2= \sigma\mathbf{1}$ to be substituted to the above Equation, with a slight abuse of differential analysis conventions.

The relative location of the segments can be addressed by observing the difference $v_3=(a+b)/2 - (c+d)/2$ between segment centers. Then $dv_3= (da+db-dc-dd)/2$, and the statistical limit is: $V=4\sigma$.

The scale difference is addressed by the difference $\Delta l$ of the lengths $\Delta l= l_1 - l_2$.
Now: $d\Delta l=v_1^0\cdot dv_1 - v_2^0\cdot dv_2$ and the statistical limit: \[
L= \sqrt{2}\sigma(v_1^0+ v_2^0)\cdot\mathbf{1}.
\]

Now, all three aspects can be addressed e.g. by: \[
   f= \max(d\phi/\Phi, dv_3/V, d\Delta l/L),
\]
where $\sigma$ is chosen suitably, e.g. to match 1 s.t.d. or 2 s.t.d. Note that the $d\phi$ has
some simplifications and approximations, especially for the term
$\sigma(1-v_1^0v_1^{0T})\mathbf{1}\cdot v_2^0$.

Registering sparse point sets

Sparse point sets arise after registering e.g. tree stems or other formations of the nature or 

built environment. There are problems with obstruction (some objects stay behind another 

for a long time, then appear again), failed registration, inexact placement of one representative point to each object, etc. These problems cause disparity between two

point sets, and one has to chase for subsets with more effort than normal registration algorithms allow. 

There are basically three similarity approaches to be used: 

• point-by-point. The Fig. above has five good matches between squares and circles.
• segment-by-segment. Four good matches above.
• triangle-by-triangle. One good match (*) depicted, also three half-matches (+) shown. 

First two approaches are rather trivial. The segment-by-segment error between points $p_1$ and $p_2$ can be e.g. the geometric mean $e_{12}=\sqrt{e_1e_2}$ of the point matching errors $e_1$ and $e_2$. There are also more specific segment matching, e.g. 
for penalizing more the case, when the errors at each end are opposite, diverting 
the segment alignment. 

The triangle-wise matching is more complex, and includes the categories of half-match (+) between three triangles and full match (*) between two triangles. If all three (or at least the best two of three) above approaches are employed cleverly, one has a good chance in matching two sparse point clouds with a lot of noise and missing point pairs.  

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.