Voxelisation Algorithms and Data Structures: A Review.

Voxel-based data structures, algorithms, frameworks, and interfaces have been used in computer graphics and many other applications for decades. There is a general necessity to seek adequate digital representations, such as voxels, that would secure unified data structures, multi-resolution options, robust validation procedures and flexible algorithms for different 3D tasks. In this review, we evaluate the most common properties and algorithms for voxelisation of 2D and 3D objects. Thus, many voxelisation algorithms and their characteristics are presented targeting points, lines, triangles, surfaces and solids as geometric primitives. For lines, we identify three groups of algorithms, where the first two achieve different voxelisation connectivity, while the third one presents voxelisation of curves. We can say that surface voxelisation is a more desired voxelisation type compared to solid voxelisation, as it can be achieved faster and requires less memory if voxels are stored in a sparse way. At the same time, we evaluate in the paper the available voxel data structures. We split all data structures into static and dynamic grids considering the frequency to update a data structure. Static grids are dominated by SVO-based data structures focusing on memory footprint reduction and attributes preservation, where SVDAG and SSVDAG are the most advanced methods. The state-of-the-art dynamic voxel data structure is NanoVDB which is superior to the rest in terms of speed as well as support for out-of-core processing and data management, which is the key to handling large dynamically changing scenes. Overall, we can say that this is the first review evaluating the available voxelisation algorithms for different geometric primitives as well as voxel data structures.

Significant Geo-Social Group Discovery over Location-Based Social Network.

Geo-social community detection over location-based social networks combining both location and social factors to generate useful computational results has attracted increasing interest from both industrial and academic communities. In this paper, we formulate a novel community model, termed geo-social group (GSG), to enforce both spatial and social factors to generate significant computational patterns and to investigate the problem of community detection over location-based social networks. Specifically, GSG detection aims to extract all group-venue clusters, where users are similar to each other in the same group and they are located in a minimum covering circle (MCC) for which the radius is no greater than a distance threshold γ. Then, we present a GSGD algorithm following a three-step paradigm to enumerate all qualified GSGs in a large network. We propose effective optimization techniques to efficiently enumerate all communities in a network. Furthermore, we extend a significant GSG detection problem to top-k geo-social group (TkGSG) mining. Rather than extracting all qualified GSGs in a network, TkGSG aims to return k feasibility groups to guarantee the diversity. We prove the hardness of computing the TkGSGs. Nevertheless, we propose the effective greedy approach with a guaranteed approximation ratio of 1-1/e. Extensive empirical studies on real and synthetic networks show the superiority of our algorithm when compared with existing methods and demonstrate the effectiveness of our new community model and the efficiency of our optimization techniques.

Accurate calibration of standard plenoptic cameras using corner features from raw images.

Light field cameras capture spatial and angular information simultaneously. A scene point in the 3D space appears many times on the raw image, bringing challenges to light field camera calibration. This paper proposes a novel calibration method for standard plenoptic cameras by using corner features from raw images. We select appropriate micro-lens images on raw images and detect corner features on them. During calibration, we first build the relationship of corner features and points in object space by using a few intrinsic parameters and then perform a linear calculation of these parameters, which are further refined via a non-linear optimization. Experiments on Lytro and Lytro Illum cameras demonstrate that the accuracy and efficiency of the proposed method are superior to the state-of-the-art methods based on features of raw images.

Classification of Power Facility Point Clouds from Unmanned Aerial Vehicles Based on Adaboost and Topological Constraints.

Machine learning algorithms can be well suited to LiDAR point cloud classification, but when they are applied to the point cloud classification of power facilities, many problems such as a large number of computational features and low computational efficiency can be encountered. To solve these problems, this paper proposes the use of the Adaboost algorithm and different topological constraints. For different objects, the top five features with the best discrimination are selected and combined into a strong classifier by the Adaboost algorithm, where coarse classification is performed. For power transmission lines, the optimum scales are selected automatically, and the coarse classification results are refined. For power towers, it is difficult to distinguish the tower from vegetation points by only using spatial features due to the similarity of their proposed key features. Therefore, the topological relationship between the power line and power tower is introduced to distinguish the power tower from vegetation points. The experimental results show that the classification of power transmission lines and power towers by our method can achieve the accuracy of manual classification results and even be more efficient.

Voxelization algorithms for geospatial applications: Computational methods for voxelating spatial datasets of 3D city models containing 3D surface, curve and point data models.

Voxel representations have been used for years in scientific computation and medical imaging. The main focus of our research is to provide easy access to methods for making large-scale voxel models of built environment for environmental modelling studies while ensuring they are spatially correct, meaning they correctly represent topological and semantic relations among objects. In this article, we present algorithms that generate voxels (volumetric pixels) out of point cloud, curve, or surface objects. The algorithms for voxelization of surfaces and curves are a customization of the topological voxelization approach [1]; we additionally provide an extension of this method for voxelization of point clouds. The developed software has the following advantages:•It provides easy management of connectivity levels in the resulting voxels.•It is not dependant on any external library except for primitive types and constructs; therefore, it is easy to integrate them in any application.•One of the algorithms is implemented in C++ and C for platform independence and efficiency.

Sensors for Indoor Mapping and Navigation.

With the growth of cities and increased urban population there is a growing demand for spatial information of large indoor environments.[...].

Indoor pedestrian navigation using foot-mounted IMU and portable ultrasound range sensors.

Many solutions have been proposed for indoor pedestrian navigation. Some rely on pre-installed sensor networks, which offer good accuracy but are limited to areas that have been prepared for that purpose, thus requiring an expensive and possibly time-consuming process. Such methods are therefore inappropriate for navigation in emergency situations since the power supply may be disturbed. Other types of solutions track the user without requiring a prepared environment. However, they may have low accuracy. Offline tracking has been proposed to increase accuracy, however this prevents users from knowing their position in real time. This paper describes a real time indoor navigation system that does not require prepared building environments and provides tracking accuracy superior to previously described tracking methods. The system uses a combination of four techniques: foot-mounted IMU (Inertial Motion Unit), ultrasonic ranging, particle filtering and model-based navigation. The very purpose of the project is to combine these four well-known techniques in a novel way to provide better indoor tracking results for pedestrians.

Automatic Registration of Terrestrial Laser Scanning Point Clouds using Panoramic Reflectance Images.

This paper presents a new approach to the automatic registration of terrestrial laser scanning (TLS) point clouds using panoramic reflectance images. The approach follows a two-step procedure that includes both pair-wise registration and global registration. The pair-wise registration consists of image matching (pixel-to-pixel correspondence) and point cloud registration (point-to-point correspondence), as the correspondence between the image and the point cloud (pixel-to-point) is inherent to the reflectance images. False correspondences are removed by a geometric invariance check. The pixel-to-point correspondence and the computation of the rigid transformation parameters (RTPs) are integrated into an iterative process that allows for the pair-wise registration to be optimised. The global registration of all point clouds is obtained by a bundle adjustment using a circular self-closure constraint. Our approach is tested with both indoor and outdoor scenes acquired by a FARO LS 880 laser scanner with an angular resolution of 0.036° and 0.045°, respectively. The results show that the pair-wise and global registration accuracies are of millimetre and centimetre orders, respectively, and that the process is fully automatic and converges quickly.

Risk-maps informing land-use planning processes A survey on the Netherlands and the United Kingdom recent developments.

The definition of safety distances as required by Art 12 of the Seveso II Directive on dangerous substances (96/82/EC) is necessary to minimize the consequences of potential major accidents. As they affect the land-use destinations of involved areas, safety distances can be considered as risk tolerability criteria with a territorial reflection. Recent studies explored the suitability of using Geographical Information System technologies to support their elaboration and visual rendering. In particular, the elaboration of GIS "risk-maps" has been recognized as functional to two objectives: connecting spatial planners and safety experts during decision making processes and communicating risk to non-experts audiences. In order to elaborate on these findings and to verify their reflection on European practices, the article presents the result of a comparative study between the United Kingdom and the Netherlands recent developments. Their land-use planning practices for areas falling under Seveso II requirements are explored. The role of GIS risk-maps within decisional processes is analyzed and the reflection on the transparency and accessibility of risk-information is commented. Recommendations for further developments are given.