## 4 The M_HERACLES Toolbox
### From Edifices to Architectural Elements (2): Automatic Segmentation of Building Framework
The computed edges for each beam facet  
Figure 12: A flowchart of the main steps in the beamdetect.m function of M_HERACLES showing the intermediate and final results. were thereafter averaged to obtain the centre axis for each beam facet. When the axis is detected, the L or Y-shaped facet was segmented into individual elongated or I-shaped clusters. Once the individual facets of individual beams are detected, two geometrical constraints were applied to group the facets into clusters of beams. The two constraints were similar to the ones used in [72], although in this algorithm only two out of the three mentioned in that paper was used. This reduction in geometric constraints was done in order to prevent over-constraining the problem. The two constraints applied in the algorithm are as follows:  
* _Adjacency constraint_: the neighborhood or adjacency constraint was enforced to limit candidate facets of each beam to only facet clusters which are located adjacent to the current facet reference. In [72], this constraint was defined by the distance between the facet centroids. In M_HERACLES, we modified this approach by performing another octree-based region growing on the facets, this time around by enforcing a distance threshold between adjacent octrees from different facets. In this way, adjacency is defined by whether any edge of the facet cluster is near another one. * _Parallelism constraint_: once the adjacency between the different facets is defined (via an adjacency matrix), the search for candidate beam facets is reduced to neighbors. Between neighbors, another geometric constraint on the parallelism of clusters was enforced. Firstly, the major principal axis of the facet clusters was computed using PCA. Two facets are considered parallel if their first PCA components satisfy Equation (1): \[\overrightarrow{OA_{1}}-\overrightarrow{OA_{2}}\approx 0\] (1) where \(\overrightarrow{OA_{1}}\) is the first PCA component of the first (or reference) facet cluster, and \(\overrightarrow{OA_{2}}\) the analogous vector for the second (or tested) facet cluster. Since the first adjacency constraint already limited the candidate facet clusters for a beam, this second geometric constraint was deemed enough to detect the beam. Using these two constraints, the function was able to group the facets into beams. An optional further processing involves using the RANSAC algorithm to generate a best-fit cuboid for each beam cluster. This was however done by a third-party Matlab(r) library ([[https://fr.mathworks.com/matlabcentral/fileexchange/65168-cuboid-fit-ransac](https://fr.mathworks.com/matlabcentral/fileexchange/65168-cuboid-fit-ransac)]([https://fr.mathworks.com/matlabcentral/fileexchange/65168-cuboid-fit-ransac](https://fr.mathworks.com/matlabcentral/fileexchange/65168-cuboid-fit-ransac)), retrieved 28 January 2020). This part of the algorithm is still under development; however, a preliminary result (as shown in Table 7) conducted on a subset of the HK-Castle dataset showed that the algorithm managed to correctly identify the individual beams. The small dataset consists of 100k points and was processed in 3 min 42 s. The algorithm gave very good results in terms of precision (median value of 94.45%), but quite low values of recall (median value of 75.58%). The low recall value can be explained by the fact that the algorithm also performs noise reduction, in which detected regions having less than a set threshold number of points are eliminated. The resulting cluster is therefore cleaner than the manual segmentation, but this means a sharp decrease in recall value. The precision value is however very satisfactory. Furthermore, the algorithm correctly deduced the number of beams that are present in the input point cloud. However, the algorithm still suffers in terms of processing time. More than half of the processing time was taken by the curvature computation at the beginning of the function; this requires therefore more investigation and optimization. Furthermore, these preliminary results concern only a small dataset.