Point Transformer

Lecturer 1

Hao-Yu Hsu

Problem Formulation

Point Cloud

Downstream Application

Quick recap of previous point-based networks

• Direct on point clouds: PointNet, PointNet++
• Graph-based methods: DGCNN, DeepGCN
• Continuous convolutions: PCNN, PointConv, KPConv, PointCNN

• In this paper, self-attention networks are used for processing point clouds.

Qi, Charles R., et al. "Pointnet: Deep learning on point sets for 3d classification and segmentation." CVPR. 2017.

Qi, Charles Ruizhongtai, et al. "Pointnet++: Deep hierarchical feature learning on point sets in a metric space." NeurIPS. 2017.

Wang, Yue, et al. "Dynamic graph cnn for learning on point clouds." ACM ToG. 2019.

Li, Guohao, et al. "Deepgcns: Can gcns go as deep as cnns?." ICCV. 2019.

Wang, Shenlong, et al. "Deep parametric continuous convolutional neural networks." CVPR. 2018.

Wu, Wenxuan, Zhongang Qi, and Li Fuxin. "Pointconv: Deep convolutional networks on 3d point clouds." CVPR. 2019.

Thomas, Hugues, et al. "Kpconv: Flexible and deformable convolution for point clouds." ICCV. 2019.

Li, Yangyan, et al. "Pointcnn: Convolution on x-transformed points." NeurIPS. 2018.

​

Quick recap of Transformer

Transformer → multi-head self-attention layers → self-attention layers

Vaswani, A. "Attention is all you need." NeurIPS. 2017.

ML Courses: https://speech.ee.ntu.edu.tw/~tlkagk/courses/ML_2019/Lecture/Transformer%20(v5).pdf

ML Courses: https://speech.ee.ntu.edu.tw/~tlkagk/courses/ML_2019/Lecture/Transformer%20(v5).pdf

ML Courses: https://speech.ee.ntu.edu.tw/~tlkagk/courses/ML_2019/Lecture/Transformer%20(v5).pdf

ML Courses: https://speech.ee.ntu.edu.tw/~tlkagk/courses/ML_2019/Lecture/Transformer%20(v5).pdf

ML Courses: https://speech.ee.ntu.edu.tw/~tlkagk/courses/ML_2019/Lecture/Transformer%20(v5).pdf

ML Courses: https://speech.ee.ntu.edu.tw/~tlkagk/courses/ML_2019/Lecture/Transformer%20(v5).pdf

ML Courses: https://speech.ee.ntu.edu.tw/~tlkagk/courses/ML_2019/Lecture/Transformer%20(v5).pdf

ML Courses: https://speech.ee.ntu.edu.tw/~tlkagk/courses/ML_2019/Lecture/Transformer%20(v5).pdf

Point Transformer Layer & Positional Encoding

• Positional encoding is important in self-attention to allow the operator to focus on local structure.
• 3D point coordinates themselves are a natural candidate for positional encoding.

• Transformer layer is in essence a set operator which is invariant to point permutations.

Key & Query

Value

P.E.

Value

Value

P.E.

P.E.

Key

Key

Query

Query

P.E.

relation op.

mlp

mlp

relation op.

softmax

softmax

Network Architecture (overall structure)

Zhao, Hengshuang, et al. "Point transformer." ICCV. 2021.

Network Architecture (overall structure)

Qi, Charles Ruizhongtai, et al. "Pointnet++: Deep hierarchical feature learning on point sets in a metric space." NeurIPS. 2017.

Network Architecture (layer design)

PTv1 Results

Wu, Zhirong, et al. "3d shapenets: A deep representation for volumetric shapes." CVPR. 2015.

​

PTv1 Results

Armeni, Iro, et al. "3d semantic parsing of large-scale indoor spaces." CVPR. 2016.

PTv1 Ablations on P.E.

Takeaway

• Simple yet effective idea, a key part is how to make it work.

​

Point Transformer v2/v3

Rachel Moan

The story so far

PTv1 Limitations

1. Attention layer is prone to overfitting and doesn’t scale well
2. Doesn’t exploit 3D information for positional encoding
3. Uses sampling based pooling, which is not spatially well aligned

PTv2 Solution

1. Grouped vector attention (GVA) instead of vector attention
2. Additional position encoding multiplier
3. Partition based pooling strategy

PTv2: GVA and Position Encoding

• Vector Attention
• a weight encoding function encodes the relation between query and key to a vector
• Omega is the learnable weight encoding

​

• Grouped Vector Attention
• Divide the c channels of the value vector into g groups
• Each channel in a group will share the same scalar attention weight

PTv2: Partition based pooling

• Separate the point cloud into non-overlapping partitions
• Get the point and feature representing each partitioned group

​

​

​

​

PTv1

PTv2

V2 Results

S3DIS

ScanNet

The story so far

PTv3: Efficiency and Scalability

• PTv1 & PTv2 weakness: scalability
• PTv3 Solution:
• Used serialized method instead of KNN
• Replace complex attention patch interaction mechanisms with methods intended for streamlined point clouds
• Replace relative positional encoding with prepositive sparse convolutional layer

Point Cloud Serialization

1. Use a space-filling curve to order the points
2. Use serialized encoding to convert each point’s position to an integer that represents its order in the curve
3. Sort the points
4. Group points into patches

PTv3 Results: Efficiency

PTv3 Results: Scalability

Blue dot indicates training with multi-dataset joint training (increasing the scale of the model)

The End

Archaeologist 1

Kulbir

Previous work

​

• Attention mechanism:
• Window attention
• Attention is localized:
• Applied to every point’s K nearest neighbors
• Computes a weighted aggregation of features from the neighboring points
• No shared intermediate computations are reused
• Lack of global context�
• Relative Positional Encoding�
• Extract hierarchical features + Downsample:
• Farthest Point Sampling ⇒ can lead to information loss

Figure: Attention is applied to k-nearest neighbors of each point� [Reference: Peng-Shuai Wang. 2023. OctFormer: Octree-based Transformers for 3D Point Clouds.]

​

Window attention

• Partition of point cloud:
• uses cubic windows �
• Unequal no. of points/window
• Due to sparse point clouds�
• Attention is constrained in each “non-overlapping” 3D cuboid window
• Each point attends to the points in the same window�
• Limitation:
• Unequal points per window ⇒ Parallelization is challenging
• Increased computation cost because of varying no. of points/window

Figure: Window attention on a point cloud with front and back view. Each color represents a window.

Refer: Stratified Transformer for 3D Point Cloud Segmentation. (CVPR 2022)

Octree attention

• Partition of point cloud:
• Use sorted shuffled keys of the octree
• “Sort points by building octrees”�
• Equal no. of points/window�
• Efficient execution of attention modules using GPUs�
• Limitation:
• Computation overhead in dynamic environments
• Irregular shapes can lead to inconsistent receptive fields
• Cannot capture local geometric structures uniformly across the point cloud for non-uniform complex geometries

Figure: Octree attention on a point cloud with front and back view. Note that each window has the same number of points. Each color represents a window.

Window attention v/s Octree attention

Test SAM 2! : Automatic Mask Generation

• Does not maintain mask consistency over multiple viewpoints if the continuity of the mask is broken
• Despite points being in the same irregular window�
• Some low quality stray masks are generated�
• Need to tune parameters for controlling:
• Density of point sampling
• Thresholds for low quality mask or duplicate mask removal

OctFormer

• Octree Attention avoids KNN + FPS
• uses Conditional Positional Encoding (CPE) that depends on octree-based depth-wise convolutions�
• CPE incorporates positional information into the attention mechanism. �
• Dynamically generates positional encodings based on the features and the octree structure.

Figure: OctFormer architecture

Figure: Window partition for the octree attention.

Refer: Peng-Shuai Wang. 2023. OctFormer: Octree-based Transformers for 3D Point Clouds. ACM Trans. Graph. (SIGGRAPH) 42, 4 (August 2023)

Why choose Octree attention?

Strengths:

1. Adaptive Partitioning for Varying Point Densities
2. Hierarchical Representation for Multi-Scale Feature Learning
1. captures both local and global context

Limitations:

1. Window attention: REduced receptive field + No info propagation amongst windows
1. Solution: Dilated Octree Attention
2. Loss of details in regions with high point density or intricate structures
3. Dynamically changing point clouds:
• Rebuilding octree is expensive for every frame

Figure: Octree Attention [Refer: Peng-Shuai Wang. 2023. OctFormer: Octree-based Transformers for 3D Point Clouds. ACM Trans. Graph. (SIGGRAPH) 42, 4 (August 2023)]

Improvements in Point Transformer - v3

1. Transformers for 3D point cloud processing
1. Larger receptive field for same efficiency
1. 16 ⇒ 1024 points �
2. Attention mechanism:
• Window + Dot product attn�
3. Positional encoding:
• Conditional PE�
4. Serialize point clouds into structured sequences
• Various space filling curves
• Z order
• Hilbert

Figure: Point Transformer-v3 architecture

Why use “Structured point clouds”?

• Capture local and global spatial structures
• w/o KNN search�
• Hence:
• Scalable�
• Maintains spatial proximity�
• Spatially close points are also close in the sorted list��

Figure: Z-order point cloud serialization space filling curve, grouped patches for local attention

​

Figure: Trans Z-order point cloud serialization and other additional space filling curve can help capture various spatial relationships and contexts

​

Archaeologist 2

Wenqi Jia

Impact of Point Transformer

• Inspire other transformer-based model on point-cloud segmentation
• Trigger series of debates over architecture selection: which one is the best?

Stratified Transformer for 3D Point Cloud Segmentation

• Use a stratified Transformer to capture both local and global contexts in a hierarchical manner. It improves segmentation accuracy on standard benchmarks
• Shows that Transformer models can be further enhanced on large-scale 3D point cloud segmentation tasks

Lai, Xin, et al. "Stratified transformer for 3d point cloud segmentation." (CVPR, 2022). https://openaccess.thecvf.com/content/CVPR2022/papers/Lai_Stratified_Transformer_for_3D_Point_Cloud_Segmentation_CVPR_2022_paper.pdf

Fast Point Transformer

• Introduces optimizations to the original Point Transformer to reduce the computational cost of self-attention
• Improves scalability and efficiency, enabling faster processing of large point cloud datasets without significantly sacrificing accuracy in tasks like classification and segmentation
• Making it more practical for real-world large-scale applications

Park, Chunghyun, et al. "Fast point transformer." (CVPR, 2022).

https://openaccess.thecvf.com/content/CVPR2022/papers/Park_Fast_Point_Transformer_CVPR_2022_paper.pdf

Debate Over Architecture Design:

is transformer really all you need?

PointMLP

• An alternative approach to the Point Transforme; using simpler Multi-Layer Perceptrons (MLPs) layers
• Better performance on tasks like classification and segmentation
• Significantly faster and more efficient, especially in terms of computation and memory usage, by avoiding the computational overhead of attention

Ma, Xu, et al. "Rethinking network design and local geometry in point cloud: A simple residual MLP framework." (ICLR, 2022).

https://arxiv.org/pdf/2202.07123

PointConvFormer: a hybrid architecture

• Local convolution for capturing fine-grained local features and transformer attention for capturing long-range dependencies
• Achieves a balance between efficiency and accuracy by integrating the best aspects of both convolutions and transformers

Wu, Wenxuan, Li Fuxin, and Qi Shan. "Pointconvformer: Revenge of the point-based convolution." (CVPR, 2023). https://openaccess.thecvf.com/content/CVPR2023/papers/Wu_PointConvFormer_Revenge_of_the_Point-Based_Convolution_CVPR_2023_paper.pdf

Private Investigator

David Yao

Zhao Hengshuang

Wu Xiaoyang

• Powerful and flexible codebase for point cloud perception research

​

• Pointcloud preprocessing, training, evaluation pipelines

​

​

Industrial Practitioner

Steven Gao

Infrastructure Inspection

1. Costly
2. Dangerous

Non-Destructive Inspection

Why RGB sometimes aren’t enough?

1. Can’t measure depth of cracks, spalling, etc
1. Reconstruction might fail due to occlusions
2. Damages internal to structural components

Non-Destructive Inspection

Attach to a drone

• LiDAR
• Phase-Array Ultrasound

​

​

Analyzing collected data is laborious!

Automating Non-Destructive Inspection

• NTSB has a trough of annotated data collected in investigations
• Classification
• Binary or categorical (ordinal rating)
• Segmentation
• Ask engineers to label damaged segments in the point cloud

​

Automating Non-Destructive Inspection

Segmentation of damages and anomalies for further inspection

Natural Language Interactions

• PointTransformer adapter for LLaMA
• Pretrain adapter using unsupervised methods
• Self-contrastive learning
• Siamese
• Instruction fine-tuning
• Freeze model parameters and fine-tune adapter using RLHF

PointTransformer

Point Cloud

Supervised Fine-Tuning

User: Identify the structure damages in this bridge

Assistant: [paste in curated NTSB report]

RLHF

User: Identify the structure damages in this bridge. For each point of damage, reason step by step on how you arrived at your conclusion. Finally, provide an overall rating of the bridge.

Assistant: [Correctly itemized damages and overall assessment] 👍

Assistant: What’s a bridge? 👎

Critic

Haozhen

Point Transformer V1

• Inefficient Memory Usage Calculate per-point features and kNN
• 1702M/2064M/2800M/4266M for 10k/20k/40k/80k input points
• Scaling Inefficient
• No distributed optimization mentioned
• Difficult to adopt parallelization to kNN, V2 decreased sampling but still takes around 28% latency
• Insufficient experiment for large-scale scenes
• >100k points / Outdoor Scenes (Stpls3d, etc.)
• Limit to model depth
• MLP increase encoding parameters drastically as model depth increases, leading to severe overfitting

​

Hu, Qingyong, et al. "Towards semantic segmentation of urban-scale 3D point clouds: A dataset, benchmarks and challenges." Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2021.

Point Transformer V2

• Lack of mathematical proof that employing an additional multiplier to the positional encoding enhance the model’s capability on learning complex point cloud positional relations. (ablation study only show slight increase)

OpenReview:

​

https://openreview.net/forum?id=I3mLa12s_H

Point Transformer V2

​

• Lack of complexity analysis of grid-based sampling (params, time)

​

​

​

OpenReview:

​

https://openreview.net/forum?id=I3mLa12s_H

Graduate Student

Junzhe Wu

Multiple modalities

Point cloud serialization provides a robust methodology for transforming n-dimensional data into a structured 1D format. This technique can similarly be applied to image data, enabling its conversion into a language-style 1D structure that PTv3 can efficiently encode.

Multiple modalities

This encoding method for both image and pointcloud enables the development of multimodal models that bridge 2D and 3D spaces, integrates both image and point cloud data to get a better segmentation result.

Autonomous Off-Road Vehicles with 3D Terrain Adaptation

Point Transformer V3 could be applied to autonomous off-road vehicles (e.g., self-driving trucks, ATVs, or exploratory robots) to handle unstructured and unpredictable terrains. By processing detailed 3D point cloud data of rugged landscapes, these vehicles can make real-time navigation decisions and adapt to dynamic environments like forests, mountains, or desert dunes.

Hacker 1

Tianhang Cheng

Data Preparation

randomly sample 2d point cloud in image where the pixel value > 0

Result

Experiment 1: train on 30 sparse points

Input dimension: 30*2, Accuracy: 2743/10000 (27%), #Params: 25610

​

Experiment 2: train on sparse points, with z-ordered (row * 28 + column)

Input dimension: 30*2, Accuracy: 6662/10000 (67%), #Params: 25610

Result

Experiment 3: train on 100 sparse points

Input dimension: 100*2, Accuracy: 2056/10000 (21%), #Params: 43530

​

Experiment 4: train on sparse points, with z-ordered (row * 28 + column)

Input dimension: 100*2, Accuracy: 8195/10000 (82%) , #Params: 43530

Result

Experiment 3: train on 300 sparse points

Input dimension: 100*2, Accuracy: 2513/10000 (25%), #Params: 94730

​

Experiment 4: train on sparse points, with z-ordered (row * 28 + column)

Input dimension: 100*2, Accuracy: 8237/10000 (82%) , #Params: 94730

Summary

From bottom to up:

​

More point, less accuray

​

When there are no order

Summary

From up to bottom:

​

More point, more accuracy (may saturate)

​

When there exists an order

Hacker 2

Shaowei Liu

Short recap of KNN used in Point Transformer

• Point Transformer v1:
• KNN for Local Neighborhood Selection: KNN is applied to select a fixed number of nearest neighbors for each point, which helps in defining the local neighborhood over which self-attention is applied.
• Feature Aggregation: After selecting the neighbors using KNN, features are aggregated from the local neighborhood
• KNN implementation: Heap Sort

Short recap of KNN used in Point Transformer

• Point Transformer v2
• Adaptive KNN: KNN is used more dynamically in conjunction with ball query or radius-based neighborhood search to allow for adaptive neighborhood sizes depending on the local point density.
• Improved Attention Mechanism: KNN helps by focusing attention on the most relevant neighboring points, improving both the efficiency and accuracy of local feature extraction

​

Short recap of KNN used in Point Transformer

• Point Transformer v3
• Serialized Neighborhoods: Instead of using KNN to find neighbors, Point Transformer v3 organizes point clouds into serialized sequences using space-filling curves (e.g., Hilbert and Z-order curves).
• Efficient Attention Mechanism: serialized allows for the use of patch attention rather than neighborhood attention, grouping points into non-overlapping patches for attention.

KNN efficiency

• Data Structures:
• Use KD-Tree, Ball Tree, or R-Tree to organize data and reduce search complexity.
• Approximate Methods:
• Leverage ANN methods (e.g., LSH) to speed up search by finding approximate neighbors.
• CUDA/GPU Acceleration:
• Utilize GPU-based libraries (e.g., cuML, FAISS) for parallel distance computations.
• Optimized Search:
• Use branch-and-bound techniques and priority queues to minimize unnecessary searches.
• Dimensionality Reduction:
• Reduce the number of dimensions to speed up distance calculations.
• Distributed Computing:
• Parallelize KNN computation across multiple machines or nodes for large datasets.

Interactive demo of different KNN methods

KD Tree

• K-Dimensional Tree
• organizes data points in a k-dimensional space. It partitions the space into hyperplanes, each node representing a region of the space.
• Advantages:
• Efficient for low-dimensional data
• Limitations:
• Performance degrades as dimensionality increases (curse of dimensionality)
• Side note for KNN:
• Maintain a max heap of size k. Keep on searching in k-d tree using dimensional splitting
• Host Demo: https://shaoweiliu.web.illinois.edu/cs598_knn_benchmark/kd-tree/

Ball Tree

• Structure:
• Each node in the tree represents a ball containing data points, and the tree is built by recursively partitioning the dataset into smaller balls.
• Compare:
• Instead of using axis-aligned hyperplanes like KD-Tree, Ball Tree uses Euclidean distance to form the balls, making it more adaptable in high-dimensional spaces.
• Advantages:
• More efficient than KD-Tree for higher-dimensional data
• Limitations:
• While better than KD-Tree for high dimensions, performance can still degrade significantly in very high-dimensional spaces.
• Host demo
• https://shaoweiliu.web.illinois.edu/cs598_knn_benchmark/ball-tree/

KNN methods comparison

Benchmark 5 algorithms

• Naive brute force KNN
• KD-Tree
• Ball-Tree
• ANN
• Hashing (LSN)

​

• Ablation on number of points
• Ablation on dimension per points

Number of points

• 1000 pts, 5 dimension

Number of points

• 10000 pts, 5 dimension

Number of points

• 100000 pts, 5 dimension

Number of dim

• 10000 pts, 5 dimension

Number of dim

• 10000 pts, 20 dimension

Number of dim

• 10000 pts, 100 dimension

Number of dim

• 10000 pts, 1000 dimension

Open-benchmarks

• https://ann-benchmarks.com/

Conclusion