The internal structure and mechanics of the ﬁbre materials, such as yarn or woven textile, are highly complex. Ex- ploring the ﬁbre structure is an essential step in material engineering either from the experimental or computational point of view. In this study, a new method to extract geometrical and morphological parameters of ﬁbre structures is proposed. The method beneﬁts from standard image analysis and machine learning technique to e ciently extract ﬁbre segments from microcomputer tomography data. The proposed algorithm is tested on the yarn and woven textile materials with di erent resolution and quality. The developed method can extract the individual ﬁbres with varying accuracy from 73–100% with processing time 2–5s on the tested samples. Keywords: ﬁbre extraction, multilevel tracing, micro CT, ﬁbre morphology, Gaussian Mixture, computer model 1. Introduction Extracting the geometrical and topological features of complex ﬁbrous structures, e.g. yarn, from micro-structural tomographic data is challenging. Hence, understanding the internal structure of yarn is a crucial step for determin- ing how macro-mechanical parameters are inﬂuenced by inter-ﬁbre mechanics and other physical e ects. Using an adequately deﬁned micro-structural model of yarn, a computational model can be established to ﬁnd out the yarn micro-mechanics concerning full-resolution models [1, 2] or more e cient multi-scale models [3, 4, 5]. Nevertheless, prior to any computational modelling, an accurate geometry representation of the yarn structure must be provided. A few studies have focused on the tracing the individual ﬁbres. Geisselmann et al. used a combination of the distance transform and skeletonisation methods to separate ﬁbres individually. However, owing to noise and irregularity in the three-dimensional (3D) data, the ﬁbres might not be continuous and the skeletonisation algorithm may generate the so-called ‘H’ connectivity (Figure 1) [6, 7]. The challenging step is to properly connect the disconnected part to obtain the original ﬁbres. Hence, a suitable criterion must be met to connect the appropriate segments. Geiselmann et al. proposed the use of stochastic models wherein the angle and length of the interconnecting segment were utilised to control the actual connection probability [6, 7]. Hu et al. used a multilevel tracing algorithm that simpliﬁed the decision criteria of pair selection [8]. Another method, which enjoys the beneﬁts of popular geometrical structures (e.g. cylindrical structures), employed the Hessian eigenvalues to extract ﬁbres [9]. Jerome et al. proposed another skeleton-based method suitable for low-density materials [10]. Vigui ´e et al. used a local orientation map combined with dilatation operations to extract ﬁbres and their contacts [11]. Sencu et al proposed an extraction algorithm, which used a combination of standard image methods to ﬁlter raw CT data and applied an enhanced Bayesian ﬁlter and Bayeisan inference to track ﬁbres in unidirectional composite [12]. Another methods are based on searching ﬁbre centres according to a certain template with suitable correlation metric [13, 14, 15]. Although ﬁbre-like structures are speciﬁc structures from the perspective of segmentation algorithms, geometrical extraction can be signiﬁcantly simpliﬁed by reusing several speciﬁc properties provided by a certain ﬁbre model. The simplest extraction can be observed in long and almost homogeneously oriented ﬁbres. This is the case of a wide range of composite ﬁbres Corresponding author Email address: lukas.capek@tul.cz (Luk ´aˇsˇCapek) Preprint submitted to Engrxiv December 29, 2020 Figure 1: H-type connection occurring during skeletonisation of a noisy structure. and algorithms used the regularity and straight ﬁbre assumption were proposed (a more enhanced approach has been presented in previous research [16, 17]). The straight ﬁbres allow us to extract centres from individual computer to- mography (CT) stack cross sections by employing regular Hough-like methods. However, even in these simple cases, the computational cost can be minimised and more e ective methods should be explored. Most algorithms use at least the basic morphological methods to extract useful information from 3D images. A very e ective method can be observed when combining the distance map and skeletonisation algorithms, which are used to extract the ﬁbre centres [7]. Enhanced methods, e.g. Hessian eigenvalues-based method, can be used for further extraction of structure-based information [9]. In recent years, deep neural network variants have been designed to extract ﬁbres from CT [18, 19]. Nevertheless, deep learning methods require e ective training, which is di cult to achieve for high dimensional CT data in a reasonable time. Herein, we propose a new method based on an e cient combination of well established 3D image analysis and a machine learning technique to e ciently extract individual ﬁbres from micro-CT data. Our method is able to: handle spatially complex ﬁbres with many contacts (not possible or untested with methods in [16, 17, 12]) extract ﬁbres in a reasonable time (compared to [7, 6]), use more robust pairing criteria (than used in [8]), and extract ﬁbres without time consuming training (compared to deep learning models in [18, 19]). Proposed method is a fusion of methods introduced in [6, 8], but with enhanced speed and robustness thanks to e ective spatial partitioning of space and machine learning method to check the ﬁbre pairing validity. 2. Materials and Methods The overall working-ﬂow of the image analysis on the CT data is shown in Figure 2. The analysis is composed of optimal de-noising of the raw data CT up to ﬁnal step consisting of re-sampling and proper tracking of the ﬁbre segments. The steps are discussed in detail in the following subsections. Figure 2: The work-ﬂow of extraction of ﬁbres from microCT data. 2 2.1. Tested Textile Materials The tested materials represent planar textile named TEX-2DW and yarn structure named TEX-Y . The planar textile is made of polyamide multiﬁlament yarns with ﬁneness 167 [dtex], yarn twist 420 [1 /m], and warp /weft sets 16/22 [1 /cm]. The second structure of yarn is made of polyester with a ﬁbre diameter of 12m, yarn diameter of 131m and ﬁneness of 25 [tex]. Both structures are shown in Figure 3. The series of images are represented by an Figure 3: Electron microscopy slice of woven structure TEX-2DW with region of interest(yellow window) used for 3D scanning (a). A slice cut of yarn TEX-Y with visible individual ﬁbre cross-sections made by light microscopy (b). array with orthogonal indices, where each member represents a grey value in range 0–255. An example of raw grey structure slices is shown in Figure 4. Figure 4: Gray slice (z axis) example of TEX-2DW (a) and TEX-Y (b). 2.2. Scanner Setting The micro CT scanner Rigaku nano3DX was used with tube voltage in range from 20 to 50 kV and current up to 30 mA. The dimension of the TEX-Y is [1427 14421250] with voxel resolution [0 :5280:5280:528]m. The TEX-2DW has dimension [204 1201551] with voxel resolution [1 11]m. 2.3. Image Preprocessing The resultant CT stacks were converted to 3D array with metadata regarding to resolution and origins. The noise was removed by median ﬁlter with spherical structure element. Further, the binarisation based on the Otsu’s method was performed. Once the binarised images were obtained, the Euclidean distance map was computed. It beneﬁts from the circular cross-section of individual ﬁbres. At ﬁbre centre, a distance is minimal with respect to the background and peak occurs. Optimally, the peak has the half value of ﬁbre diameter, but due to a noise, the peak ﬁlter works in 3 range 4.7–6.3 micro meters for TEX-Y and 4.5–7 for the woven structure TEX-2DW . The ﬁbre diameter is known either from manufacturer (see subsection 2.1) or can be estimated from distance map histogram. Moreover, the crossing ﬁbres can be separated by the distance peaks and thus no additional step is required (Figure 5). The new binarised data is obtained from ﬁlter the distance peaks deﬁned by range above. Due to small gaps in the peaks, the morphological dilatation with small structuring element was used to close such gaps. The ﬁnal step is to apply the skeletonisation on binary array and get one-pixel centres of ﬁbre parts. In order to remove the ‘H’ like connections and another crossings, the pixel were tested for the neighbourhoods by 26-connectivity and those with more than two neighbourhoods were removed. Finally, the disconnected parts were labelled and sorted ascendantly according to ﬁbre segment length. Figure 5: A regular skeletonisation issue (middle) with two ﬁbres (left). The distance map disconnecting two ﬁbre segments 2.4. Segment Vectorisation For further work with disconnected discrete parts of the ﬁbres, the transformation into continuous representation is useful. Let call the disconnected parts of ﬁbres as ‘segments’. Each segment represented a structure containing the unsorted number of pixels, but with known ends, is approximated by the b-spline curve (Figure 6). Once two candidates for the merging are found, the b-spline curve is also used to connect them by approximating the missing coordinates between the candidate segments. The spline approximation quality was carefully investigated in depen- dence on the smoothing factor s (for details, see the Scipy library manual [20]). The smoothing factor inﬂuences a compromise between the accuracy of interpolation and smoothness. The smoothing parameter in the range 0.01-0.05 was usually given good b-spline approximations. The spline is of cubic order and also the ﬁrst derivative is used to get a segment direction. The more details of how the spline approximation is constructed can be found in Scipy library documentation [20]. Figure 6: Fibre segment with cubic spline approximation (a). Merging of two segments by spline curve with smooth transition (b). 2.5. Fibre Reconstruction Each segment contains two end-points (start /end). The initial connection of two segments is deﬁned by a straight line, which is called intermediate segment. Segments can be connected only by their end-points. A potential pair of two segments that belong to a ﬁbre is searched based on geometrical relations inspired by work of Geiselmann [7, 6]. Consider two segments iandjin a pair. We can deﬁne Euclidean length li jof intermediate segment and angles i j; ji (see Figure 7). Introducing the weighting factor wrand maximal values lmax; max, we can write down the criterion function as weighted sum of normalized partial members: ci j=(1wr)li j lmax+wr i j+ ji max<1 (1) Every pair of segments satisfying the above criteria is taken into account as a potential candidate. The ﬁnal pair is selected according the smallest value of ci jand should also pass the back checking deﬁned later. Increasing the maximal distance between ﬁbre ends leads to decreasing of the maximal angles, so there is a clear geometrical relation [7]. But we found that separating both criterion (distance, angles) can provide more ﬂexibility in some cases. 4 Figure 7: Geometrical quantities deﬁned between end-points of segments. The red line represents an intermediate segment. Dashed line represents true ﬁbre trajectory. 2.6. Back Checking Once the two segments are merged, the newly constructed segment should be evaluated whether it corresponds with original CT data. The spline curve of the intermediate segment is discretised onto the original CT data space and dilated with small structuring element sphere. The mean of grey values in CT data corresponding to newly occurred intermediate segment (see Figure 6) was evaluated with help of clustering algorithm [21]. Firstly, we let a Gaussian clustering algorithm detects two density clusters in CT data. The clusters separated the CT data on grey density belongs to ﬁbre structure and background noise. Secondly, we computed a probability that a newly occurred intermediate segments belongs to a one of the cluster (see the details in clustering algorithm implementation in [21]). We found a that a probability level 85 % was optimal for tested examples in this study. 2.7. Algorithms and Implementation Details The image algorithms work usually with large data collections and in 3D it is even more demanding issue. In the proposed algorithms in Figure 8 main steps required for the successfully extraction of ﬁbres are introduced. The input required by algorithm composed of distance map ﬁeld and raw CT data. Both arrays are encoded in hdf5 format [22] with uint8 /ﬂoat64 data type. The vectorisation is one of the most computationally intensive task, as it requires to compute ﬁltering (if required), binarisation and skeletonisation. The initial control parameters are set by the user and are deﬁned by following python dictionary: ”lmax”: [...,...,...] a list of maximal distance parameters ” max”: [...,...,...] a list of alpha angles ”wr”: [...,...,...] a list of weighting constants From a programming language point of view, a segment is represented by the object allowing recursive merging of segments and respecting the parent-child relation. As the segment connectivity is deﬁned by spatial coordinates of the segment end-points, neighbourhood lookup (Kd tree [20]) is constructed before main loop begins in order to signiﬁcantly speed up searching of segment pairs. At current point, the pairing of segments runs on the two queues named as ﬁnished andunﬁnished . Once the pair of two matching segments is found and matched back-checking criteria, they are merged and partial segments are drop out from queue unﬁnished and the new segment is pushed to queue named ﬁnished . If necessary the matching criteria can be adapted during each level. The main code is developed in python language with critical parts (graph construction, searching, merging and b-spline interpolation) written in C ++. The code is written in objective manner. 5 Figure 8: Algorithm scheme of ﬁbre segmentation. The unﬁnished ,ﬁnished ,unpaired are queries. 3. Results & Discussion The model parameters l max; max;wrare experimentally estimated based on the parametric approach and careful investigating the initial and level-based potentially matched pair of segments. The mean values of grey data for both models were estimated by Gaussian mixed clustering (see the Figure 9). The clustering algorithm is used to decide whether the newly created segment corresponds to grey values. The pairs which do not pass the quality criteria are excluded. It must be pointed out that proposed algorithm could be more improved in control parameter evaluation. The current model relies on the simple deterministic criteria, which need usually a user initial set-up and due to multilevel approach can be adapted during the level iteration. Nevertheless, the unique decision on the best suited segment pair is not always detectable (especially in case of noisy CT data) and mismatches occur. Although the mismatches are detected by evaluation of the newly created segment which leads to delete the newly created segment, still some mismatched segments propagate up to end of level iteration or some potentially connectible segments with long proximity are not correctly detected. Using more advanced criteria can help to improve the decision sensitivity and should be supported by probabilistic approach either proposed in [7] or some another approach such machine learning classiﬁer or Fuzzy logic [23]. The optimal model parameters are deﬁned in the Table 1. To decide whether to start new level, the algorithm checks the number of new pairs for the previous set of control parameters and if it is non-zero, it continues to another level with the same parameters or if the number of new pairs is zero, the algorithm increases the control parameters and starts new pairing level. The control parameters can be also controlled interactively, but it is not e cient. Nevertheless in some cases the manual correction may be required or the weighting parameter w rcan be corrected to get more ﬁne control. Optimal values of parameters i j; ji;li jshould be as smallest 6 Figure 9: Gaussian mixture cluster classiﬁcation [21, 24] for woven textile and yarn CT data. Two clusters of grey values were identiﬁed for each materials. The red colour corresponds to a mask of clustered data. The following density clusters corresponding to ﬁbre materials and background noise were identiﬁed: TEX-Y [Cluster 1 (165 12.5); Cluster 2 (210 13.8)]; TEX-2DW :[Cluster 1 (90 10.5); Cluster 2 (85 5.0)] Table 1: Optimal control parameters and number of levels for both models. The weighting parameter w rwas set to 0.5. There is a couple of numbers: the ﬁrst means the l max[mm] and second means max. [°] number of levels TEX-2DW 0.01; 10 0.01; 10 0.03; 30 0.03; 30 0.05; 40 0.08; 40 0.1; 40 TEX-Y 0.01; 50 0.01; 50 0.01; 50 0.015; 50 0.015; 50 – – as possible, which indicates that two ﬁbre segments could potentially belong to a ﬁbre. Nevertheless, in some cases the ﬁbre segment ends are close and excentered a bit. The angles can be close to 90, while distance can be still small. In such case, the user’s careful intervention can be required. The control parameters are yet adjusted by a user, which allows us to interactively control segment pairing each level, but on the other hand it requires a certain manual tuning of those parameters by a user to get valid results. The automatic optimal selection of control parameters and their levels is intensively developed by authors and will be a part of future study. The segmentation results of the yarn model TEX-Y are shown in Figure 10. With given level-controlled parame- ters, the resultant ﬁbres are correctly identiﬁed with 100 % success. There are 136 ﬁbres at total (counted from slice cuts). The mean radius of ﬁbres is 0.0051 mm. The initial number of ﬁbre segments is shown in the most left in Figure 10. The results of ﬁbre extraction for high noise and corrupted CT data for model TEX-2DW are shown in Figure 11. The only 73% of ﬁbres were correctly identiﬁed (at total there are 255 ﬁbres counted by careful looking at the CT data). Lower accuracy is caused by corrupted segments, which cannot be uniquely recognised by the deterministic approach used. The ﬁbre mean radius of TEX-2DW is 0.0057 mm. The multilevel strategy allows us to adaptively change pairing criteria (one of the main di erence from [8]), which may lead to enhanced segmentation results. The extracting accuracy can be further improved by clever using of morphological operations and more advanced ﬁltering techniques. Nevertheless, the most critical part is to have su cient quality of CT data, which is seen in our results. The computational sources needed for the ﬁbre segmentation are relative low (136 ﬁbres identiﬁed in 2s and 186 ﬁbres identiﬁed in 5s) in comparison with stochastic algorithm (83 minutes for 903 ﬁbres) proposed in [7]. Nev- ertheless, it can depend on ﬁbre-structure complexity and segment-ends proximity. The critical part is the quick nearest-neighbour lookup, which needs to be implemented e ciently by building optimal graph such KD-tree al- gorithm [25]. Euclidean distance and skeletonisation algorithms are already implemented e ciently in library [20]. They are not usually the performance bottleneck for moderate size CT. 7 Figure 10: The initial ﬁbre segments before algorithm applying(left). Segmented yarn with 100% success in all available ﬁbre segments(right). The proposed algorithm has not been tested on large CT data set containing thousands of ﬁbres. This fact can be considered as a shortcoming of this study because Euclidean distance and skeletonisation algorithms are computer memory-intensive. Hence they may become a performance bottleneck for a large data set. 8 Figure 11: Extracted woven ﬁbres and their properties from highly noisy and corrupted micro-CT data: initial ﬁbre segments (left); ﬁnal ﬁbre segments with ﬁbre radius is shown (right). 9 4. Conclusion Building a complex and physically relevant model is of great interest in the scientiﬁc community. The ﬁbre-like structures can be seen in many materials. The inspection of their physics is an important task. Although the computer tomography can provide an important view of the structure of ﬁbres, often more than is required, especially in the computational models, where the geometry is of great interest. Due to the complexity of ﬁbre structures with many contact bonds and overlapping, the proper individual ﬁbre identiﬁcation is a challenging task. Although a few studies are dealing with ﬁbre extraction, a consistent family of methods is not well developed. The method relies on the multilevel strategy, where at each level pairs of segments are searched so it matches the given control criteria. The method is based on the common morphological image operations enriched by machine learning classiﬁer. The method was tested on the two ﬁbre structure samples and shown high e ciency and good identiﬁcation accuracy. 5. Conﬂict of interest statement The authors declare no conﬂict of interest.