# Semantic Component Association within Object Classes Based on Convex Polyhedrons
## 4 Semantic Correspondence Likelihood
### Neighborhood Similarity  
Let us assume two segments \(C_{i}\) and \(C_{j}\), described by CTI descriptors \(d_{i}\) and \(d_{j}\), belonging to the same model. In order to describe the geometrical arrangement of segments in the model, we introduce  
Figure 3: Representation of objects by convex template instances (CTIs). the TRED that describes topological relations between two segments. The TRED represents a tuple \(T(C_{i},C_{j})=(\mu_{ij},v_{ij},\sigma_{ij}^{v})\). The relation type coefficient, \(\mu_{ij}\), is computed by:  
\[\mu_{ij}=\min_{m=1,\dots,n_{d}}\rho_{ijm}, \tag{7}\]  
where:  
\[\rho_{ijm}=\frac{d_{im}+d_{\overline{m}}}{d_{im}+d_{i\overline{m}}}. \tag{8}\]  
In Equation (8), \(m\) and \(\overline{m}\) represent the indexes of two opposite unit vectors \(a_{m},a_{\overline{m}}\in A\). Five types of topological relation between two segments \(C_{i}\) and \(C_{j}\), defined by \(\mu_{ij}\), are considered:  
Type 1: \(C_{j}\) contains \(C_{i}\):  
\[\mu_{ij}\geq 1\wedge\mu_{ij}>\mu_{ji}\]  
Type 2: \(C_{i}\) and \(C_{j}\) are identical:  
\[\mu_{ij}=\mu_{ji}=1\]  
Type 3: \(C_{i}\) and \(C_{j}\) intersect:  
\[0<\mu_{ij}<1\wedge 0<\mu_{ji}<1\]  
Type 4: \(C_{i}\) touches \(C_{j}\):  
\[\mu_{ij}=0\]  
Type 5: \(C_{i}\) and \(C_{j}\) are disjoint:  
\[\mu_{ij}<0.\]  
The relation type between two segments is denoted in this paper by \(type(T(C_{i},C_{j}))\). Three of these relations are illustrated by Figure 4: a segment \(C_{i}\) is inside a segment \(C_{j}\) (left); two segments \(C_{i}\) and \(C_{j}\) intersect (middle); and a segment \(C_{i}\) touches a segment \(C_{j}\) (right). If two segments are touching (Type 4), \(v_{ij}\) and \(\sigma_{ij}^{v}\) are computed by:  
\[v_{ij}=\frac{\sum\limits_{m=1}^{n_{d}}w_{ijm}a_{m}}{\left\|\sum\limits_{m=1}^ {n_{d}}w_{ijm}a_{m}\right\|}, \tag{9}\]  
\[\mu_{ij}=\min_{m=1,\dots,n_{d}}\rho_{ijm}, \tag{7}\]0 Topological relation descriptor (TRED). The CTI descriptor elements \(d_{xm}\) that are denoted with arrows directed opposite the corresponding vector \(a_{m}\) have negative values. and:  
\[\mu_{ij}=\min_{m=1,\dots,n_{d}}\rho_{ijm}, \tag{7}\]1  
where:  
\[\mu_{ij}=\min_{m=1,\dots,n_{d}}\rho_{ijm}, \tag{7}\]2  
Vector \(v_{ij}\) is approximately orthogonal to the plane that separates \(C_{i}\) and \(C_{j}\), and it is directed from \(C_{i}\) to \(C_{j}\). Its purpose is to describe the touching direction. This vector is computed as a weighted average of all vectors \(a_{m}\), where vectors corresponding to smaller values \(\rho_{ijm}\) have greater weights. Value \(\sigma_{ij}^{v}\) describes the uncertainty of vector \(v_{ij}\), where \(\sigma_{v0}\) is a constant that models the uncertainty due to the measurement noise. TREDs are computed for every pair of model segments. A segment \(C_{j}\) is a neighbor of a segment \(C_{i}\) if \(type(T(C_{i},C_{j}))\) is 1 or 4. In order to make the method robust to noise, the definitions of the topological relation types are relaxed by introducing a suitable tolerance. As a consequence of this relaxation, the topological relation of Type 2 includes not only identical segments, but also segments that occupy approximately the same space. Furthermore, if two segments are of different convexity types (convex or concave), then they are considered to be neighbors only if their topological relation is of Type 1 or Type 2. The neighbors of each segment are grouped into clusters according to the associated TRED descriptors. These clusters are denoted in this paper by \(\Gamma\), and the cluster set assigned to a segment \(C_{p}^{X}\) is denoted by \(N_{p}^{X}\), where \(X\) stands for the query (\(Q\)) or representative (\(M\)) model. Two neighbors of \(C_{i}\) are grouped into a cluster only if their topological relation to \(C_{i}\) is of the same type. In the case of the Type 4 relation, two neighbors \(C_{j}\) and \(C_{k}\) can be grouped in the same cluster if their vectors \(v_{ij}\) and \(v_{ik}\) are similar.