Computationally efficient algorithm that identifies boundary points of a point cloud.

Overview

BoundaryTest

Included are MATLAB and Python packages, each of which implement efficient algorithms for boundary detection and normal vector estimation given a point cloud.

This package implements algorithms described in the paper

Calder, Park, and Slepčev. Boundary Estimation from Point Clouds: Algorithms, Guarantees and Applications. arXiv:2111.03217, 2021.

Download package

You can download the package with the Code button above or by cloning the repository with either of the commands below

git clone [email protected]:sangmin-park0/BoundaryTest
git clone https://github.com/sangmin-park0/BoundaryTest

depending on whether you prefer ssh (first) or https (second).

Usage (MATLAB package)

To use the MATLAB package, simply download the files under the folder bd_test_MATLAB.

  1. If you would like to run some quick examples in a Euclidean space, use the function distballann_norm. You can call the function by
[BP1,BP2,dtb, dtb2] = distballann_norm(n,r,L, eps, domain,dim)

Input arguments are: n (number of points), r (test radius), L (Lipschitz constant of the density from which the points are randomly sampled), eps (boundary thickness), domain (type of domain; 1 for a ball and 2 for an annulus), dim (dimension of the domain).

Outputs are: BP1 and BP2 (boundary points according to 1st order and 2nd order tests respectively, as described in the paper), dtb and dtb2 (the estimated distances from each point to the boundary, again according to 1st and 2nd order tests respectively). For example, the following code

distballann_norm(3000,0.18,2,0.03, 1, 3)

will sample n=3000 points from a ball in d=3 dimensions with radius 0.5 (fixed) from a density with Lipschitz constant L=2, then perform boundary test using the neighborhood radius r=0.18 and boundary thickness eps=0.03. Another example for the annulus, is

distballann_norm(9000,0.18,2,0.03, 2, 3)

This function will also output the following plots:

  • plot of true distance (black) versus dtb (blue hollow dots) and dtb2 (red hollow dots)
  • if the dimension is 2, the plot of the point cloud (black) and the boundary points from the 2nd order test (red hollow dots)
  1. If you already have a point cloud in a Euclidean space and the indices of points you wish to test for boundary, that's also fine! To compute boundary points with test do the following
nvec = estimated_normal(pts,r)
[bdry_pts,bdry_idx,dists] = bd_Test(pts,nvec,eps,r,test_type,test_idx)

here, the input arguments are: pts (point cloud), r (neighborhood radius), eps (thickness of the boundary region we want to identify), test_type (type of the test: 1 for 1st order, 2 for 2nd order; optional, and default value=2) test_idx (indices we wish to test for the boundary;optional, and default setting tests all points). Outputs are bdry_pts (boundary points), bdry_idx (indices of boundary points, as a subset of pts), and dists (estimated distances of tested points).

If you have a point cloud that lies in some lower-dimensional manifold embedded in a Euclidean space, instead of bd_test, use bd_test_manif in the following way

[bdry_pts,bdry_idx,dists] = bd_Test_manif(pts,nvec,eps,r,test_idx)

to obtain the same output. Again, test_idx is an optional argument, and default setting tests all points. In the manifold setting, the algorithm uses only the 2nd order test.

Usage (Python)

The Python boundary statistic is implemented in the GraphLearning Python package. Install the development version of GraphLearning from GitHub

git clone https://github.com/jwcalder/GraphLearning
cd GraphLearning
python setup.py install --user

The other required package is Annoy for fast approximate nearest neighbor searches, which should be automatically installed during the graph learning install. The 3D visualizations from our paper are generated with the Mayavi package. Mayavi can be difficult to install and currently has many issues, so any Python code related to Mayavi is commented out. If you have a working Mayavi installation, you can uncomment that code at your convenience to generate 3D visualizations of the solutions to PDEs on point clouds.

The main function for computing the boundary statistic is graphlearning.boundary_statistic. Below is an example showing how to finding boundary points from a random point cloud on the unit box in two dimensions.

import numpy as np
import graphlearning as gl

n = 5000
X = numpy.random.rand(n,2)  

r = 0.1    #Radius for boundary statistic
eps = 0.02 #Size of boundary tube to detect
S = gl.boundary_statistic(X,r)
bdy_pts = np.arange(n)[S < 3*eps/2]  #Boundary test to find boundary points

The full usage of graphlearning.boundary_statistic is copied below for convenience, and the Python folder has scripts for running the experiments from our paper concerned with solving PDEs on point clouds and detecting the boundary and depth of MNIST images. The only required arguments are X and r. Note that the function supports using a rangesearch or knnsearch for neighborhood identification for the test.

def boundary_statistic(X,r,knn=False,ReturnNormals=False,SecondOrder=True,CutOff=True,I=None,J=None,D=None):
    """Computes boundary detection statistic
    Args:
        X: nxd point cloud of points in dimension d
        r: radius for test (or number of neighbors if knn=True)
        knn: Use knn version of test (interprets r as number of neighbors)
        ReturnNormals: Whether to return normal vectors as well
        SecondOrder: Use second order test
        CutOff: Whether to use CutOff for second order test.
        I,J,D: Output of knnsearch (Optional, improves runtime if already available)
    Returns:
        Length n numpy array of test statistic. If ReturnNormals=True, then normal vectors are return as a second argument.
    """

Contact and questions

Please email [email protected] with any questions or comments.

Acknowledgements

Following people have contributed to the development of this software:

  1. Jeff Calder (University of Minnesota)

  2. Dejan Slepčev (Carnegie Mellon University)

License

MIT

CTRL-C: Camera calibration TRansformer with Line-Classification

CTRL-C: Camera calibration TRansformer with Line-Classification This repository contains the official code and pretrained models for CTRL-C (Camera ca

57 Nov 14, 2022
JAX-based neural network library

Haiku: Sonnet for JAX Overview | Why Haiku? | Quickstart | Installation | Examples | User manual | Documentation | Citing Haiku What is Haiku? Haiku i

DeepMind 2.3k Jan 04, 2023
Adversarial Framework for (non-) Parametric Image Stylisation Mosaics

Fully Adversarial Mosaics (FAMOS) Pytorch implementation of the paper "Copy the Old or Paint Anew? An Adversarial Framework for (non-) Parametric Imag

Zalando Research 120 Dec 24, 2022
CausalNLP is a practical toolkit for causal inference with text as treatment, outcome, or "controlled-for" variable.

CausalNLP CausalNLP is a practical toolkit for causal inference with text as treatment, outcome, or "controlled-for" variable. Install pip install -U

Arun S. Maiya 95 Jan 03, 2023
In this project we predict the forest cover type using the cartographic variables in the training/test datasets.

Kaggle Competition: Forest Cover Type Prediction In this project we predict the forest cover type (the predominant kind of tree cover) using the carto

Marianne Joy Leano 1 Mar 15, 2022
A Distributional Approach To Controlled Text Generation

A Distributional Approach To Controlled Text Generation This is the repository code for the ICLR 2021 paper "A Distributional Approach to Controlled T

NAVER 102 Jan 07, 2023
Learning Pixel-level Semantic Affinity with Image-level Supervision for Weakly Supervised Semantic Segmentation, CVPR 2018

Learning Pixel-level Semantic Affinity with Image-level Supervision This code is deprecated. Please see https://github.com/jiwoon-ahn/irn instead. Int

Jiwoon Ahn 337 Dec 15, 2022
Backdoor Attack through Frequency Domain

Backdoor Attack through Frequency Domain DEPENDENCIES python==3.8.3 numpy==1.19.4 tensorflow==2.4.0 opencv==4.5.1 idx2numpy==1.2.3 pytorch==1.7.0 Data

5 Jun 18, 2022
Hand Gesture Volume Control | Open CV | Computer Vision

Gesture Volume Control Hand Gesture Volume Control | Open CV | Computer Vision Use gesture control to change the volume of a computer. First we look i

Jhenil Parihar 3 Jun 15, 2022
Open-source implementation of Google Vizier for hyper parameters tuning

Advisor Introduction Advisor is the hyper parameters tuning system for black box optimization. It is the open-source implementation of Google Vizier w

tobe 1.5k Jan 04, 2023
Traditional deepdream with VQGAN+CLIP and optical flow. Ready to use in Google Colab

VQGAN-CLIP-Video cat.mp4 policeman.mp4 schoolboy.mp4 forsenBOG.mp4

23 Oct 26, 2022
Official PyTorch implementation of "Uncertainty-Based Offline Reinforcement Learning with Diversified Q-Ensemble" (NeurIPS'21)

Uncertainty-Based Offline Reinforcement Learning with Diversified Q-Ensemble This is the code for reproducing the results of the paper Uncertainty-Bas

43 Nov 23, 2022
ALFRED - A Benchmark for Interpreting Grounded Instructions for Everyday Tasks

ALFRED A Benchmark for Interpreting Grounded Instructions for Everyday Tasks Mohit Shridhar, Jesse Thomason, Daniel Gordon, Yonatan Bisk, Winson Han,

ALFRED 204 Dec 15, 2022
Learning Confidence for Out-of-Distribution Detection in Neural Networks

Learning Confidence Estimates for Neural Networks This repository contains the code for the paper Learning Confidence for Out-of-Distribution Detectio

235 Jan 05, 2023
This is the implementation of the paper "Self-supervised Outdoor Scene Relighting"

Self-supervised Outdoor Scene Relighting This is the implementation of the paper "Self-supervised Outdoor Scene Relighting". The model is implemented

Ye Yu 24 Dec 17, 2022
Modelisation on galaxy evolution using PEGASE-HR

model_galaxy Modelisation on galaxy evolution using PEGASE-HR This is a labwork done in internship at IAP directed by Damien Le Borgne (https://github

Adrien Anthore 1 Jan 14, 2022
OMAMO: orthology-based model organism selection

OMAMO: orthology-based model organism selection OMAMO is a tool that suggests the best model organism to study a biological process based on orthologo

Dessimoz Lab 5 Apr 22, 2022
Official PyTorch implementation of "RMGN: A Regional Mask Guided Network for Parser-free Virtual Try-on" (IJCAI-ECAI 2022)

RMGN-VITON RMGN: A Regional Mask Guided Network for Parser-free Virtual Try-on In IJCAI-ECAI 2022(short oral). [Paper] [Supplementary Material] Abstra

27 Dec 01, 2022
[3DV 2021] A Dataset-Dispersion Perspective on Reconstruction Versus Recognition in Single-View 3D Reconstruction Networks

dispersion-score Official implementation of 3DV 2021 Paper A Dataset-dispersion Perspective on Reconstruction versus Recognition in Single-view 3D Rec

Yefan 7 May 28, 2022