# EDC-Net: Edge Detection Capsule Network for 3D Point Clouds
## 3 Proposed Method
### Network Architecture
#### 3.1.2 Features Graph  
In the first layers of EDC-Net, the raw input point cloud \(\mathcal{X}=\{x_{1},...,x_{N}\}\subset\mathbb{R}^{3}\) is converted to a k-NN (k nearest neighbors) graph structure based on its euclidean and eigenvalues features. This pre-processing step is used for building a k-NN features graph before applying the first convolution operation of the network. In order to build a neighbors graph, we select the k neighbors of each point. We extract the k nearest neighbors of each point of a raw point cloud in a pre-processing step before feeding the features into the main blocks of the network, as is shown in Figure 1. The nearest neighboring process is measured based on \(L^{2}\)_norm_: \(Distance(x_{i},x_{j})=||x_{i}-x_{j}||_{2}\), where \(1\leq i,j\leq N\). Once the k nearest neighbors of each point in the euclidean space are determined, we search for the nearest neighbors in the eigenvalues space. To this end, we compute the covariance matrix to extract the eigenvalues inspired from [27]. Covariance is a measurement that explores the variance of each dimension from the mean with respect to each other. From a point cloud with \(N\) points, for a 3-dimensional sample point \(x_{i}=(x_{i}^{1},x_{i}^{2},x_{i}^{3})\), where \(1\leq i\leq N\), the \(3\times 3\) covariance matrix \(C_{i}\) is given by:  
\[C_{i}= \begin{bmatrix}Cov\big{(}x_{i}^{1},x_{i}^{1}\big{)}&Cov\big{(}x_{i}^{1},x_{i}^{2}\big{)}&Cov\big{(}x_{i}^{1},x_{i}^{3}\big{)}\\ Cov\big{(}x_{i}^{2},x_{i}^{1}\big{)}&Cov\big{(}x_{i}^{2},x_{i}^{2}\big{)}&Cov \big{(}x_{i}^{2},x_{i}^{3}\big{)}\\ Cov\big{(}x_{i}^{3},x_{i}^{1}\big{)}&Cov\big{(}x_{i}^{3},x_{i}^{2}\big{)}&Cov \big{(}x_{i}^{3},x_{i}^{3}\big{)}\end{bmatrix} , \tag{1}\]  
where, for instance, \(Cov(x_{i}^{1},x_{i}^{2})\) is the covariance of \(x_{i}^{1}\); \(x_{i}^{2}\) by k nearest neighbor points is computed as:  
\[Cov\big{(}x_{i}^{1},x_{i}^{2}\big{)}=\frac{\sum_{j=1}^{k}\big{(}x_{j}^{1}- \tilde{x}_{i}^{1}\big{)}\big{(}x_{j}^{2}-\tilde{x}_{i}^{2}\big{)}}{k-1}, \tag{2}\]  
where \(\tilde{x}_{i}^{1}\) is the average of the neighbors of \(x_{i}\) over the first dimension and \(\tilde{x}_{i}^{2}\) is the average over the second dimension. The eigenvalues and eigenvectors of \(x_{i}\) are computed as: \(C_{i}V_{i}=\lambda_{i}V_{i}\), where \(C_{i}\) is a \(3\times 3\) covariance matrix, \(V_{i}\) is an eigenvector and \(\lambda_{i}\) is an eigenvalue. Then, the eigenvalues of the covariance matrix of the point cloud are defined as \(\lambda=\{\lambda_{1},...,\lambda_{N}\}\subset\mathbb{R}^{3}\); each point of a point cloud contains three values in eigenvalues space denoted by \(\lambda_{i}=(\lambda_{i}^{1},\lambda_{i}^{2},\lambda_{i}^{3})\) and ordered as: \(\lambda_{i}^{1}\leq\lambda_{i}^{2}\leq\lambda_{i}^{3}\). The nearest neighboring process in eigenvalues space is measured based on \(L^{2}\)_norm_: \(Distance(\lambda_{i},\lambda_{i})=||\lambda_{i}-\lambda_{i}||_{2}\), where \(1\leq i,j\leq N\). We define a directed edge-weighted graph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) representing point cloud structure based on its euclidean and eigenvalues features, where the vertices are \(\mathcal{V}=\{\mathcal{V}_{1},...,\mathcal{V}_{N}\}\) and the edges are \(\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}\). We construct \(\mathcal{G}\) as a k-NN edge-weighted graph in \(\mathbb{R}^{\mathcal{A}}\), where \(\mathcal{A}\) is the feature space dimension of the graph. The k nearest neighbors are based on the similarities of the points in \(\mathcal{X}\). The similarities are exploited by \(L^{2}\) norm. The edge-weighted graph \(\mathcal{G}\) is constructed by connecting all the nearest neighbors of shape \(N\times k\times\mathcal{A}\). The graph \(\mathcal{G}\) includes self-loops, meaning each vertex also points to itself. We exploit the k nearest neighbors in both the euclidean and eigenvalues spaces and concatenate the features inspired by [48]; however, the eigenvalues in this work are different since they are based on the covariance matrix.