Grant: Discovery Grants Program - Individual
The University of British Columbia
$27,000.00
Understanding and computing with geometric data using nearest neighbour sampling
FY 2024-25
Summary
Our daily lives generate lots of data! Much of this data arrives as "point clouds", a very unstructured format where each value is measured in a feature space of all possible values. A point cloud can have "shape", as in the physical world (e.g., 3-d position values), or it might have some more abstract idea of connectivity and locality. Either way, the geometry of data is often of crucial importance. However, a disadvantage of point clouds is that their unstructured nature, combined with their ever-increasing size, makes mathematical operations unwieldy, especially with high-dimensional abstract data.
Our main objectives are to design, study and apply new general strategies to sample from point cloud in way that makes calculations tractable while retaining useful geometric information. The common theme to our proposed work is to sample nearest neighbours from the point cloud on simpler (often lower-dimensional) objects such as line segments.
Our preliminary study shows that this sampling along randomly-chosen line segments, combined with convolutional neural networks results in an algorithm for point-cloud classification (e.g., "is this point cloud a stop sign or a tree?") that achieves results on par with state-of-the-art specialized (more complicated) models. Why does it work so well? Our intuition is that this sampling encodes a good mix of randomness, dimension reduction, and geometric information. That intuition is largely based on experience from our long-term research on solving differential equations on surfaces (which also involves nearest-neighbour sampling).
This project will assemble a team of students to:
� Adapt this novel sampling idea to other computer vision problems including registration, segmentation and data compression. Labelling parts of a point cloud of an airplane as "wing", "wheel", "engine" is an example of a segmentation problem.
� Investigate mathematical connections to integral geometry, and generalize our results.
� Design domain decomposition techniques to extend our computations to objects defined using a tree structure of set operations.
� Study sampling in high-dimensional point clouds. A preliminary experiment on handwritten digits shows an "importance sampling" effect: less-common handwriting styles are more likely to occur (compared to random sampling).
Sampling via nearest neighbours along random lines or planes is a novel idea, not yet explored in numerical analysis, data sampling, computer vision, or machine learning. Our work will provide new algorithms and software for those communities, both for fundamental research and for use in emerging applications.
Program
Discovery Grants Program - Individual
Recipient
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2023-05286
Name nom
Macdonald, Colin
Department département
Mathematics
Organization id
2
Institution établissement
The University of British Columbia
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2023
Award amount
27000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2955
Research subject group en
Applied mathematics
Research subject group fr
Mathématiques appliquées
Research subject en
Numerical analysis
Research subject fr
Analyse numérique
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Understanding and computing with geometric data using nearest neighbour sampling
Keywords
point clouds; numerical analysis; scientific computing; data science; machine learning; computer vision; sampling; k nearest neighbours; partial differential equations
Application summary
Our daily lives generate lots of data! Much of this data arrives as "point clouds", a very unstructured format where each value is measured in a feature space of all possible values. A point cloud can have "shape", as in the physical world (e.g., 3-d position values), or it might have some more abstract idea of connectivity and locality. Either way, the geometry of data is often of crucial importance. However, a disadvantage of point clouds is that their unstructured nature, combined with their ever-increasing size, makes mathematical operations unwieldy, especially with high-dimensional abstract data.
Our main objectives are to design, study and apply new general strategies to sample from point cloud in way that makes calculations tractable while retaining useful geometric information. The common theme to our proposed work is to sample nearest neighbours from the point cloud on simpler (often lower-dimensional) objects such as line segments.
Our preliminary study shows that this sampling along randomly-chosen line segments, combined with convolutional neural networks results in an algorithm for point-cloud classification (e.g., "is this point cloud a stop sign or a tree?") that achieves results on par with state-of-the-art specialized (more complicated) models. Why does it work so well? Our intuition is that this sampling encodes a good mix of randomness, dimension reduction, and geometric information. That intuition is largely based on experience from our long-term research on solving differential equations on surfaces (which also involves nearest-neighbour sampling).
This project will assemble a team of students to:
� Adapt this novel sampling idea to other computer vision problems including registration, segmentation and data compression. Labelling parts of a point cloud of an airplane as "wing", "wheel", "engine" is an example of a segmentation problem.
� Investigate mathematical connections to integral geometry, and generalize our results.
� Design domain decomposition techniques to extend our computations to objects defined using a tree structure of set operations.
� Study sampling in high-dimensional point clouds. A preliminary experiment on handwritten digits shows an "importance sampling" effect: less-common handwriting styles are more likely to occur (compared to random sampling).
Sampling via nearest neighbours along random lines or planes is a novel idea, not yet explored in numerical analysis, data sampling, computer vision, or machine learning. Our work will provide new algorithms and software for those communities, both for fundamental research and for use in emerging applications.