More Like this

1. Polylidar3D-Fast Polygon Extraction from 3D Data

   https://doi.org/10.3390/s20174819  

   Castagno, Jeremy; Atkins, Ella (September 2020, Sensors)

   null (Ed.)

   Flat surfaces captured by 3D point clouds are often used for localization, mapping, and modeling. Dense point cloud processing has high computation and memory costs making low-dimensional representations of flat surfaces such as polygons desirable. We present Polylidar3D, a non-convex polygon extraction algorithm which takes as input unorganized 3D point clouds (e.g., LiDAR data), organized point clouds (e.g., range images), or user-provided meshes. Non-convex polygons represent flat surfaces in an environment with interior cutouts representing obstacles or holes. The Polylidar3D front-end transforms input data into a half-edge triangular mesh. This representation provides a common level of abstraction for subsequent back-end processing. The Polylidar3D back-end is composed of four core algorithms: mesh smoothing, dominant plane normal estimation, planar segment extraction, and finally polygon extraction. Polylidar3D is shown to be quite fast, making use of CPU multi-threading and GPU acceleration when available. We demonstrate Polylidar3D’s versatility and speed with real-world datasets including aerial LiDAR point clouds for rooftop mapping, autonomous driving LiDAR point clouds for road surface detection, and RGBD cameras for indoor floor/wall detection. We also evaluate Polylidar3D on a challenging planar segmentation benchmark dataset. Results consistently show excellent speed and accuracy. 

   more » « less
2. Multi-Criteria Dimensionality Reduction with Applications to Fairness

   Tantipongpipat, Uthaipon; Samadi, Samira; Singh, M.; Morgenstern, Jamie H.; Vempala, Santosh S. (January 2019, Advances in neural information processing systems)

   null (Ed.)

   Dimensionality reduction is a classical technique widely used for data analysis. One foundational instantiation is Principal Component Analysis (PCA), which minimizes the average reconstruction error. In this paper, we introduce the multi-criteria dimensionality reduction problem where we are given multiple objectives that need to be optimized simultaneously. As an application, our model captures several fairness criteria for dimensionality reduction such as the Fair-PCA problem introduced by Samadi et al. [NeurIPS18] and the Nash Social Welfare (NSW) problem. In the Fair-PCA problem, the input data is divided into k groups, and the goal is to find a single d-dimensional representation for all groups for which the maximum reconstruction error of any one group is minimized. In NSW the goal is to maximize the product of the individual variances of the groups achieved by the common low-dimensinal space. Our main result is an exact polynomial-time algorithm for the two-criteria dimensionality reduction problem when the two criteria are increasing concave functions. As an application of this result, we obtain a polynomial time algorithm for Fair-PCA for k=2 groups, resolving an open problem of Samadi et al.[NeurIPS18], and a polynomial time algorithm for NSW objective for k=2 groups. We also give approximation algorithms for k>2. Our technical contribution in the above results is to prove new low-rank properties of extreme point solutions to semi-definite programs. We conclude with the results of several experiments indicating improved performance and generalized application of our algorithm on real-world datasets. 

   more » « less
3. Multi-Criteria Dimensionality Reduction with Applications to Fairness

   Tantipongpipat, Uthaipon and (December 2019, Advances in Neural Information Processing Systems 32 (NeurIPS 2019))

   Dimensionality reduction is a classical technique widely used for data analysis. One foundational instantiation is Principal Component Analysis (PCA), which minimizes the average reconstruction error. In this paper, we introduce the multi-criteria dimensionality reduction problem where we are given multiple objectives that need to be optimized simultaneously. As an application, our model captures several fairness criteria for dimensionality reduction such as the Fair-PCA problem introduced by Samadi et al. [NeurIPS18] and the Nash Social Welfare (NSW) problem. In the Fair-PCA problem, the input data is divided into k groups, and the goal is to find a single d-dimensional representation for all groups for which the maximum reconstruction error of any one group is minimized. In NSW the goal is to maximize the product of the individual variances of the groups achieved by the common low-dimensinal space. Our main result is an exact polynomial-time algorithm for the two-criteria dimensionality reduction problem when the two criteria are increasing concave functions. As an application of this result, we obtain a polynomial time algorithm for Fair-PCA for k=2 groups, resolving an open problem of Samadi et al.[NeurIPS18], and a polynomial time algorithm for NSW objective for k=2 groups. We also give approximation algorithms for k>2. Our technical contribution in the above results is to prove new low-rank properties of extreme point solutions to semi-definite programs. We conclude with the results of several experiments indicating improved performance and generalized application of our algorithm on real-world datasets. 

   more » « less
4. Development of a PointNet for Detecting Morphologies of Self-Assembled Block Oligomers in Atomistic Simulations

   Shen, Z.; Sun, Y.; Lodge, T.P.; Siepmann, J.I. (May 2021, The journal of physical chemistry)

   ABSTRACT: Molecular simulations with atomistic or coarse- 6 grained force fields are a powerful approach for understanding and 7 predicting the self-assembly phase behavior of complex molecules. 8 Amphiphiles, block oligomers, and block polymers can form 9 mesophases with different ordered morphologies describing the 10 spatial distribution of the blocks, but entirely amorphous nature for 11 local packing and chain conformation. Screening block oligomer 12 chemistry and architecture through molecular simulations to find 13 promising candidates for functional materials is aided by effective 14 and straightforward morphology identification techniques. Captur- 15 ing 3-dimensional periodic structures, such as ordered network 16 morphologies, is hampered by the requirement that the number of 17 molecules in the simulated system and the shape of the periodic simulation box need to be commensurate with those of the resulting 18 network phase. Common strategies for structure identification include structure factors and order parameters, but these fail to 19 identify imperfect structures in simulations with incorrect system sizes. Building upon pioneering work by DeFever et al. [Chem. Sci. 20 2019, 10, 7503−7515] who implemented a PointNet (i.e., a neural network designed for computer vision applications using point 21 clouds) to detect local structure in simulations of single-bead particles and water molecules, we present a PointNet for detection of 22 nonlocal ordered morphologies of complex block oligomers. Our PointNet was trained using atomic coordinates from molecular 23 dynamics simulation trajectories and synthetic point clouds for ordered network morphologies that were absent from previous 24 simulations. In contrast to prior work on simple molecules, we observe that large point clouds with 1000 or more points are needed 25 for the more complex block oligomers. The trained PointNet model achieves an accuracy as high as 0.99 for globally ordered 26 morphologies formed by linear diblock, linear triblock, and 3-arm and 4-arm star-block oligomers, and it also allows for the discovery 27 of emerging ordered patterns from nonequilibrium systems. 

   more » « less
5. Neural Collapse Meets Differential Privacy: Curious Behaviors of NoisyGD with Near-perfect Representation Learning

   Wang, Chendi; Zhu, Yuqing; Su, Weijie; Wang, Yu-Xiang (July 2024, International Conference on Machine Learning (ICML-24))

   A recent study by De et al. (2022) has reported that large-scale representation learning through pre-training on a public dataset significantly enhances differentially private (DP) learning in downstream tasks, despite the high dimensionality of the feature space. To theoretically explain this phenomenon, we consider the setting of a layer-peeled model in representation learning, which results in interesting phenomena related to learned features in deep learning and transfer learning, known as Neural Collapse (NC). Within the framework of NC, we establish an error bound indicating that the misclassification error is independent of dimension when the distance between actual features and the ideal ones is smaller than a threshold. Additionally, the quality of the features in the last layer is empirically evaluated under different pre-trained models within the framework of NC, showing that a more powerful transformer leads to a better feature representation. Furthermore, we reveal that DP fine-tuning is less robust compared to fine-tuning without DP, particularly in the presence of perturbations. These observations are supported by both theoretical analyses and experimental evaluation. Moreover, to enhance the robustness of DP fine-tuning, we suggest several strategies, such as feature normalization or employing dimension reduction methods like Principal Component Analysis (PCA). Empirically, we demonstrate a significant improvement in testing accuracy by conducting PCA on the last-layer features. 

   more » « less