# VFLD: Voxelized Fractal Local Descriptor
## 3 Proposal
### Three-Dimensional Fractal Dimension Algorithm  
In fractal geometry, the concept of the fractal dimension is a generalization of the concept of dimension in classical geometry. To simplify, it can be defined as a measure of how much an object appears to fill the space as it is scaled up or down. A clear example is the Koch snowflake. This figure has a topological dimension of one but cannot be treated as a curve, because as we zoom in on the figure, the distance between its points tends to infinity. This phenomenon is known as the Coastline Paradox [27]. There are many ways to calculate this property (information dimension, correlation dimension, Higuchi dimension, Lyapunov dimension, Hausdorff dimension, etc. ), but we have chosen the box-counting method, also known as the Minkowski-Bouligand dimension. This was successfully used in [6] and is an efficient method to obtain the fractal dimension. In addition, it is one of the most popular ways to calculate the fractal dimension of sets in Euclidean space, being directly applicable to 3D data, and is extremely fast to compute. The name of the box-counting method is highly descriptive, as it involves dividing the space in boxes, and counting the number of cells that contain points. In more detail, the space occupied by the object is divided into square boxes of side size \(\varepsilon\). The cells that are occupied by the object are then counted. This process is repeated \(nIters\) times with a fixed \(BSD_{i}\) decreasing value of \(\varepsilon\), obtaining Equation (1), where \(N(\varepsilon)\) is the number of boxes required to cover the figure according to the side size, \(\varepsilon\) is the side size, and \(D_{BC}\) is the box-counting dimension:  
\[N(\varepsilon)=\varepsilon^{D_{BC}} \tag{1}\]  
The expression obtained is similar to those of Haussdorf and Higuchi, and can be operated with algorithms to generate a linear function as shown in Equation (2). We refer to this function as the log-log curve. As can be seen, \(D_{BC}\) is the slope of the linear function. In our practical application, we apply a least-squares regression to approximate the value of this slope, as proposed in [28]:\[log(N(\epsilon))=D_{BC}\cdot log(\epsilon) \tag{2}\]  
The translation of this algorithm to the 3D Euclidean space is a trivial process, as the only difference is the substitution of the squares boxes of the grid by cubic voxels. To do so, we leverage the voxel grid algorithm. The only parameter to set is the number of iterations \(nIters\). The initial box size \(BSD_{0}\) is the size of the largest dimension of the object, and the box sizes \(BSD_{i}\) for subsequent iterations are calculated following Equation (3), which splits each voxel into eight parts:  
\[BSD_{i}=\frac{BSD_{i-1}}{2} \tag{3}\]  
The voxel grid filter is applied in each iteration, as shown in Figures 1 and 2, with the corresponding size. The number of voxels that are occupied \(occ_{i}\) is then computed. We store the corresponding values of voxel size \(BSD_{i}\) and number of occupied cells in every iteration. The inverse of \(BSD_{i}\) and \(occ_{i}\) are projected to the \(log\) space, creating the mentioned log-log curve. Then, Equation (2) is applied, thus approximating a line fitted with the least-squares regression on the log-log curve. Finally, the slope of the line represents the fractal dimension. Setting the box-counting iterations \(nIters\) correctly is key, as too many iterations would provide an incorrect slope, and thus an incorrect fractal dimension. This is due to a threshold at which more subdivisions of the space does not mean more occupied boxes. Thus, with the \(nIters\) set above that threshold, the fitted line is horizontally flattened. This effect is related to the density of points of the point cloud, and thus denser point clouds would theoretically benefit from a higher \(nIters\) value. Figure 3 shows the effect of different \(nIters\).