IP Library › Granted Patent US 12,688,585
Granted Patent B2
US 12,688,585 · App. 18/709,290 · Granted Jul 21, 2026

Concavity-based grouping for unorganized 3D point cloud segmentation and abstraction

Inventors: Ruoyu Wang (New York, NY); Chen Feng (Scotch Plains, NJ); Dong Tian (Boxborough, MA)
Assignees: INTERDIGITAL VC HOLDINGS, INC.; NEW YORK UNIVERSITY
G06T7/12G06T3/40G06T7/187G06T7/64G06T2207/10028G06T2207/20081
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,688,585
App. No.
18/709,290
Filed
May 10, 2024
Granted
Jul 21, 2026
Kind
B2
Art Unit
2661
USPC
382/174
Abstract

Points are grouped from a point cloud using Concavity-induced Distance (CID). First, a set of seed points is sampled from the input point cloud. Then a grouping of points is conducted based on a nearest neighbor search computed using CID. These two steps enable two novel solutions in point cloud segmentation and scene abstraction. In one embodiment, CID is determined between two points residing within an object surface. In a second embodiment, a CID is determined between groups of points.

Claims (42)

1 . A method, comprising:

sampling an input point cloud to generate seed points; and,

generating point groups by assigning each point of said input point cloud to its nearest seed point based on concavity-induced distance (CID) wherein concavity-induced distance is a maximum distance from any point on a line segment to an object surface.

2 . The method of claim 1 , wherein each seed point has access to its semantic or instance label, further comprising:

propagating each seed point's label to all points in said point group of this seed point.

3 . The method of claim 1 , further comprising:

computing a CID between each pair of point groups;

merging said pairs of point groups whose CID is less than a predefined threshold; and,

Iterating computing and merging steps until no further merging is possible.

4 . The method of claim 3 , further comprising:

computing a convex hull of each point group; and,

determining a set of convex hulls as an abstract representation of a scene.

5 . The method of claim 3 , wherein said CID between a pair of groups is calculated as an average CID between point pairs sampled from two groups.

6 . The method of claim 3 , wherein computing a CID between a pair of groups comprises:

selecting a first point in a first group and a second point in a second group;

computing the CID between said first and second points; and,

using said computed CID as the CID between the pair of groups.

7 . The method of claim 6 , wherein said computing of CID between said pair of groups comprises:

iterating selection of point pairs and said computed CID; and,

using an averaged CID as the CID between said pair of groups.

8 . The method of claim 3 , wherein merging starts from closest pairs in terms of CID.

9 . The method of claim 1 , wherein said seed points are sampled via farthest point sampling based on CID.

10 . The method of claim 1 , wherein the input point cloud is augmented by CID-distance matrix between input points and said seed points as features, and then trained on a deep learning point cloud segmentation network.

11 . The method of claim 10 , wherein clustering is performed on all points in training point clouds, and cluster centers are used as said seed points.

12 . The method of claim 10 , wherein said seed points are randomly sampled from all points in the training point clouds.

13 . The method of claim 10 , wherein said seed points are parameters of a single-layer neural network that is learned while training the deep learning point cloud segmentation network.

14 . The method of claim 10 , wherein said seed points are proposed by a different deep neural network based on the input point cloud.

15 . An apparatus, comprising:

a processor, configured to perform:

sampling an input point cloud to generate seed points; and,

generating point groups by assigning each point of said input point cloud to its nearest seed point based on concavity-induced distance wherein concavity-induced distance (CID) is a maximum distance from any point on a line segment to an object surface.

16 . The apparatus of claim 15 , wherein each seed point has access to its semantic or instance label, further comprising:

propagating each seed point's label to all points in said point group of this seed point.

17 . The apparatus of claim 15 , further comprising:

computing a CID between each pair of point groups;

merging said pairs of point groups whose CID is less than a predefined threshold; and,

Iterating computing and merging steps until no further merging is possible.

18 . The apparatus of claim 17 , further comprising:

computing a convex hull of each point group; and,

determining a set of convex hulls as an abstract representation of a scene.

19 . The method or apparatus of claim 17 , wherein said CID between a pair of groups is calculated as an average CID between point pairs sampled from two groups.

20 . The apparatus of claim 15 , wherein said seed points are sampled via farthest point sampling based on CID.

Assignments (2)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded May 15, 2024
From: WANG, RUOYU; FENG, CHEN
To: NEW YORK UNIVERSITY
Reel/Frame 067421/0051 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded May 15, 2024
From: TIAN, DONG
To: INTERDIGITAL VC HOLDINGS, INC.
Reel/Frame 067420/0834 →
Continuity (2)
Provisional Application 63278527 · Nov 12, 2021
Related Publication 20250005764A1 · Jan 2, 2025
References Cited (41)
US 20090122378A1 · Tomioka · 2009 [cited by examiner]
US 20100145961A1 · Hu · 2010 [cited by examiner]
US 20160044295A1 · Unten · 2016 [cited by examiner]
US 20210019918A1 · Li · 2021 [cited by examiner]
US 20220156483A1 · Sun · 2022 [cited by examiner]
US 20230080574A1 · Li · 2023 [cited by examiner]
US 20230306559A1 · Wang · 2023 [cited by examiner]
US 20230410254A1 · Wang · 2023 [cited by examiner]
US 20240212164A1 · Li · 2024 [cited by examiner]
US 20250014187A1 · Yoon · 2025 [cited by examiner]
US 20250069324A1 · Murudkar · 2025 [cited by examiner]
US 20250232557A1 · Osep · 2025 [cited by examiner]
US 20260003038A1 · Alkanat · 2026 [cited by examiner]
CN 108510516 · 2018 [cited by applicant]
CN 109191484B · 2019 [cited by applicant]
CN 118967495A · 2024 [cited by examiner]
Chen; Hui et al. (Power Equipment Segmentation of 3D Point Clouds Based on Geodesic Distance with K-means Clustering), Sep. 17, 2021, IEEE (Year: 2021). [cited by examiner]
Hao; Su et al. (Approximate Convex Decomposition for 3D Meshes with Collision-Aware Concavity and Tree Search), May 5, 2022, arXiv (Year: 2022). [cited by examiner]
Rui; Song et al. (Point cloud segmentation based on Euclidean clustering and multi-plane extraction in rugged field), May 28, 2021, IOP Publishing (Year: 2021). [cited by examiner]
Li et al., Supervised Fitting of Geometric Primitives to 3D Point Clouds, In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), Jun. 2019. [cited by applicant]
Lien et al., Approximate Convex Decomposition of Polyhedra, In Proceedings of the 2007 ACM Symposium on Solid and Physical Modeling, pp. 121-131, 2007. [cited by applicant]
Gong et al., Point Cloud Segmentation of 3D Scattered Parts Sampled by Realsense, In 2017 IEEE International Conference on Information and Automation (ICIA), pp. 1-6. IEEE, 2017. [cited by applicant]
Lien et al., Approximate Convex Decomposition of Polyhedra and its Applications, Computer Aided Geometric Design, 25(7), pp. 503-522, 2008. [cited by applicant]
Asafi et al., Weak Convex Decomposition by Lines-of-Sight, In Computer Graphics Forum, vol. 32, pp. 23-31. Wiley Online Library, 2013. [cited by applicant]
Tateno et al., Real-Time and Scalable Incremental Segmentation on Dense SLAM, In 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 4465-4472. IEEE, 2015. [cited by applicant]
Roychoudhury et al., Plane Segmentation in Organized Point Clouds Using Flood Fill, 2021 IEEE International Conference on Robotics and Automation (ICRA), May 30, 2021, pp. 13532-13538. [cited by applicant]
Zou et al., 3d-PRNN: Generating Shape Primitives With Recurrent Neural Networks, In Proceedings of the IEEE International Conference on Computer Vision, pp. 900-909, 2017. [cited by applicant]
Qi et al., Pointnet++: Deep Hierarchical Feature Learning on Point Sets in a Metric Space, arXiv preprint arXiv:1706.02413, 2017. [cited by applicant]
Kreavoy et al., Model Composition From Interchangeable Components, In 15th Pacific Conference on Computer Graphics and Applications (PG'07), pp. 129-138, IEEE, 2007. [cited by applicant]
Tulsiani et al., Learning Shape Abstractions by Assembling Volumetric Primitives, In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2635-2643, 2017. [cited by applicant]
Omidalizarandi et al., Segmentation and Classification of Point Clouds from Dense Aerial Image Matching, International Journal of Multimedia & Its Applications (IJMA), vol. 5, No. 4, Aug. 31, 2013, pp. 33-51. [cited by applicant]
Kaick et al., Shape Segmentation by Approximate Convexity Analysis, ACM Transactions on Graphics (TOG), 34(1), pp. 1-11, 2014. [cited by applicant]
Poppinga et al., Fast Plane Detection and Polygonalization in Noisy 3D Range Images, Intelligent Robots and Systems, 2008, IROS, IEEE/RSJ International Conference on, Sep. 22, 2008, pp. 3378-3383. [cited by applicant]
Stein et al., Object Partitioning Using Local Convexity, In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 304-311, 2014. [cited by applicant]
Feng et al., Fast Plane Extraction in Organized Point Clouds Using Agglomerative Hierarchical Clustering, In 2014 IEEE International Conference on Robotics and Automation (ICRA), pp. 6218-6225, IEEE, 2014. [cited by applicant]
Ghosh et al., Fast Approximate Convex Decomposition Using Relative Concavity, Computer-Aided Design, 45(2), pp. 494-504, 2013. [cited by applicant]
Rabbani et al., Segmentation of Point Clouds Using Smoothness Constraints, ISPRS 2006, Procceedings of the ISPRS Commission V. Symposium vol. 35, Part 6, Image Engineering and Vision Metrology, Dresden, Germany Sep. 25-… [cited by applicant]
Stein et al., Convexity Based Object Partitioning for Robot Applications, In 2014 IEEE International Conference on Robotics and Automation (ICRA), pp. 3213-3220. IEEE, 2014. [cited by applicant]
Gadelha et al., Label-Efficient Learning on Point Clouds Using Approximate Convex Decompositions, In European Conference on Computer Vision, pp. 473-491. Springer, 2020. [cited by applicant]
Deng et al., CvxNet: Learnable Convex Decomposition, In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 31-44, 2020. [cited by applicant]
Wang et al., Adaptive O-CNN: A Patch-Based Deep Representation of 3d Shapes, ACM Transactions on Graphics (TOG), 37(6), pp. 1-11, 2018. [cited by applicant]