Nearest Neighbor Sampling of Point Sets Using Rays

doi:10.1007/s42967-023-00318-1

Communications on Applied Mathematics and Computation ›› 2024, Vol. 6 ›› Issue (2): 1131-1174.doi: 10.1007/s42967-023-00318-1

• ORIGINAL PAPERS • 上一篇下一篇

Nearest Neighbor Sampling of Point Sets Using Rays

Liangchen Liu¹, Louis Ly², Colin B. Macdonald³, Richard Tsai^1,2

1. Department of Mathematics, The University of Texas at Austin, 2515 Speedway, Austin, TX 78712, USA;
2. Oden Institute for Computational Engineering and Sciences, The University of Texas at Austin, 201 E 24th St, Austin, TX 78712, USA;
3. Department of Mathematics, University of British Columbia, 1984 Mathematics Rd, Vancouver, BC V6T 1Z2, Canada

收稿日期:2022-11-08 修回日期:2023-09-13 接受日期:2023-09-13 出版日期:2023-12-11 发布日期:2023-12-11
通讯作者: Liangchen Liu,E-mail:lcliu@utexas.edu;Louis Ly,E-mail:louisly@utexas.edu;Colin B. Macdonald,E-mail:cbm@math.ubc.ca;Richard Tsai,E-mail:ytsai@math.utexas.edu E-mail:lcliu@utexas.edu;louisly@utexas.edu;cbm@math.ubc.ca;ytsai@math.utexas.edu
基金资助:
Part of this research was performed while Macdonald and Tsai were visiting the Institute for Pure and Applied Mathematics (IPAM), which is supported by the National Science Foundation (Grant No. DMS-1440415). This work was partially supported by a grant from the Simons Foundation, NSF Grants DMS-1720171 and DMS-2110895, and a Discovery Grant from Natural Sciences and Engineering Research Council of Canada.

Nearest Neighbor Sampling of Point Sets Using Rays

Liangchen Liu¹, Louis Ly², Colin B. Macdonald³, Richard Tsai^1,2

1. Department of Mathematics, The University of Texas at Austin, 2515 Speedway, Austin, TX 78712, USA;
2. Oden Institute for Computational Engineering and Sciences, The University of Texas at Austin, 201 E 24th St, Austin, TX 78712, USA;
3. Department of Mathematics, University of British Columbia, 1984 Mathematics Rd, Vancouver, BC V6T 1Z2, Canada

Received:2022-11-08 Revised:2023-09-13 Accepted:2023-09-13 Online:2023-12-11 Published:2023-12-11
Contact: Liangchen Liu,E-mail:lcliu@utexas.edu;Louis Ly,E-mail:louisly@utexas.edu;Colin B. Macdonald,E-mail:cbm@math.ubc.ca;Richard Tsai,E-mail:ytsai@math.utexas.edu E-mail:lcliu@utexas.edu;louisly@utexas.edu;cbm@math.ubc.ca;ytsai@math.utexas.edu
Supported by:
Part of this research was performed while Macdonald and Tsai were visiting the Institute for Pure and Applied Mathematics (IPAM), which is supported by the National Science Foundation (Grant No. DMS-1440415). This work was partially supported by a grant from the Simons Foundation, NSF Grants DMS-1720171 and DMS-2110895, and a Discovery Grant from Natural Sciences and Engineering Research Council of Canada.

摘要/Abstract

摘要： We propose a new framework for the sampling, compression, and analysis of distributions of point sets and other geometric objects embedded in Euclidean spaces. Our approach involves constructing a tensor called the RaySense sketch, which captures nearest neighbors from the underlying geometry of points along a set of rays. We explore various operations that can be performed on the RaySense sketch, leading to different properties and potential applications. Statistical information about the data set can be extracted from the sketch, independent of the ray set. Line integrals on point sets can be efficiently computed using the sketch. We also present several examples illustrating applications of the proposed strategy in practical scenarios.

关键词: Point clouds, Sampling, Classification, Registration, Deep learning, Voronoi cell analysis

Abstract: We propose a new framework for the sampling, compression, and analysis of distributions of point sets and other geometric objects embedded in Euclidean spaces. Our approach involves constructing a tensor called the RaySense sketch, which captures nearest neighbors from the underlying geometry of points along a set of rays. We explore various operations that can be performed on the RaySense sketch, leading to different properties and potential applications. Statistical information about the data set can be extracted from the sketch, independent of the ray set. Line integrals on point sets can be efficiently computed using the sketch. We also present several examples illustrating applications of the proposed strategy in practical scenarios.

Key words: Point clouds, Sampling, Classification, Registration, Deep learning, Voronoi cell analysis

Liangchen Liu, Louis Ly, Colin B. Macdonald, Richard Tsai. Nearest Neighbor Sampling of Point Sets Using Rays[J]. Communications on Applied Mathematics and Computation, 2024, 6(2): 1131-1174.

参考文献

[1] Atzmon, M., Maron, H., Lipman, Y.: Point convolutional neural networks by extension operators. arXiv:1803.10091 (2018)
[2] Bentley, J.L.: Multidimensional binary search trees used for associative searching. Commun. ACM 18(9), 509-517 (1975)
[3] Besl, P.J., McKay, N.D.: Method for registration of 3-D shapes. In: Sensor Fusion IV: Control Paradigms and Data Structures, vol. 1611 (1992)
[4] Caflisch, R.E.: Monte Carlo and quasi-Monte Carlo methods. Acta Numer. 7, 1-49 (1998)
[5] Chang, A.X., Funkhouser, T., Guibas, L., Hanrahan, P., Huang, Q., Li, Z., Savarese, S., Savva, M., Song, S., Su, H., Xiao, J.X., Yi, L., Yu, F.: ShapNet: an information-rich 3D model repository. arXiv:1512.03012 (2015)
[6] Corless, R.M., Gonnet, G.H., Hare, D.E., Jeffrey, D.J., Knuth, D.E.: On the LambertW function. Adv. Comput. Math. 5(1), 329-359 (1996)
[7] Curless, B., Levoy, M.: A volumetric method for building complex models from range images computer graphics. In: SIGGRAPH 1996 Proceedings (1996)
[8] Cutler, A., Breiman, L.: Archetypal analysis. Technometrics 36(4), 338-347 (1994)
[9] Daley, D.J., Vere-Jones, D.: An Introduction to the Theory of Point Processes. Volume I: Elementary Theory and Methods. Springer, New York (2003)
[10] De Bruijn, N.G.: Asymptotic Methods in Analysis, vol. 4. Courier Corporation, USA (1981)
[11] Doerr, B.: Probabilistic tools for the analysis of randomized optimization heuristics. In: Theory of Evolutionary Computation, pp. 1-87. Springer, Cham, Switzerland (2020)
[12] Draug, C., Gimpel, H., Kalma, A.: The Octave Image package (version 2.14.0) (2022). https://gnu-octave.github.io/packages/image
[13] Dvoretzky, A., Kiefer, J., Wolfowitz, J.: Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. Ann. Math. Stat. 27(3), 642-669 (1956)
[14] Eldar, Y., Lindenbaum, M., Porat, M., Zeevi, Y.Y.: The farthest point strategy for progressive image sampling. IEEE Trans. Image Process. 6(9), 1305-1315 (1997)
[15] Fang, Y., Xie, J., Dai, G., Wang, M., Zhu, F., Xu, T., Wong, E.: 3D deep shape descriptor. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2319-2328 (2015)
[16] Graham, R., Oberman, A.M.: Approximate convex hulls: sketching the convex hull using curvature. arXiv:1703.01350 (2017)
[17] Hadwiger, H.: Vorlesungen Über Inhalt, Oberfläche und Isoperimetrie, vol. 93. Springer, Berlin (1957)
[18] Helgason, S., Helgason, S.: The Radon Transform, vol. 2. Springer, New York (1980)
[19] Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 604-613 (1998)
[20] Ioffe, S., Szegedy, C.: Batch normalization: accelerating deep network training by reducing internal covariate shift. arXiv:1502.03167 (2015)
[21] Jiménez, P., Thomas, F., Torras, C.: 3D collision detection: a survey. Comput. Gr. 25(2), 269-285 (2001)
[22] Johnson, J., Douze, M., Jégou, H.: Billion-scale similarity search with GPUs. IEEE Trans. Big Data 7(3), 535-547 (2019)
[23] Jones, P.W., Osipov, A., Rokhlin, V.: A randomized approximate nearest neighbors algorithm. Applied and Computational Harmonic Analysis 34(3), 415-444 (2013)
[24] Kazmi, I.K., You, L., Zhang, J.J.: A survey of 2D and 3D shape descriptors. In: 2013 10th International Conference Computer Graphics, Imaging and Visualization, pp. 1-10. IEEE (2013)
[25] Kingma, D.P., Ba, J.: Adam: a method for stochastic optimization. arXiv:1412.6980 (2014)
[26] Klain, D.A., Rota, G.-C.: Introduction to Geometric Probability. Cambridge University Press, Cambridge (1997)
[27] Klokov, R., Lempitsky, V.: Escape from cells: deep KD-networks for the recognition of 3D point cloud models. In: Proceedings of the IEEE International Conference on Computer Vision, pp. 863-872 (2017)
[28] Krig, S.: Interest point detector and feature descriptor survey. In: Computer Vision Metrics, pp. 187-246. Springer, Cham (2016)
[29] LeCun, Y.: The MNIST database of handwritten digits (1998). http://yann.lecun.com/exdb/mnist/
[30] Li, J.X., Chen, B.M., Lee, H.: SO-Net: self-organizing network for point cloud analysis. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 9397-9406 (2018)
[31] Li, Y., Bu, R., Sun, M., Wu, W., Di, X., Chen, B.: PointCNN: convolution on X-transformed points. In: Advances in Neural Information Processing Systems, pp. 820-830 (2018)
[32] Lin, M., Gottschalk, S.: Collision detection between geometric models: a survey. Proc. IMA Conf. Math. Surf. 1, 602-608 (1998)
[33] Macdonald, C.B., Merriman, B., Ruuth, S.J.: Simple computation of reaction-diffusion processes on point clouds. Proc. Natl. Acad. Sci. 110(23), 9209-9214 (2013)
[34] Macdonald, C.B., Miller, M., Vong, A., et al.: The Octave Symbolic package (version 3.0.1) (2022). https://gnu-octave.github.io/packages/symbolic
[35] Mahalanobis, P.C.: On the generalised distance in statistics. Proc. Natl. Inst. Sci. India 2, 49-55 (1936)
[36] Massart, P.: The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality. Ann. Prob. 1990, 1269-1283 (1990)
[37] Meurer, A., Smith, C.P., Paprocki, M., Čertík, O., Kirpichev, S.B., Rocklin, M., Kumar, A., Ivanov, S., Moore, J.K., Singh, S., Rathnayake, T., Vig, S., Granger, B.E., Muller, R.P., Bonazzi, F., Gupta, H., Vats, S., Johansson, F., Pedregosa, F., Curry, M.J., Terrel, A.R., Roučka, Š., Saboo, A., Fernando, I., Kulal, S., Cimrman, R., Scopatz, A.: SymPy: symbolic computing in Python. PeerJ Comput. Sci. 3, e103 (2017). https://doi.org/10.7717/peerj-cs.103
[38] Nair, V., Hinton, G.E.: Rectified linear units improve restricted Boltzmann machines. In: Proceedings of the 27th International Conference on Machine Learning (ICML-10), pp. 807-814 (2010)
[39] Natterer, F.: The Mathematics of Computerized Tomography. Society for Industrial and Applied Mathematics, USA (2001)
[40] Osting, B., Wang, D., Xu, Y., Zosso, D.: Consistency of archetypal analysis. SIAM J. Math. Data Sci. 3(1), 1-30 (2021).
[41] Paszke, A., Gross, S., Chintala, S., Chanan, G., Yang, E., DeVito, Z., Lin, Z., Desmaison, A., Antiga, L., Lerer, A.: Automatic differentiation in PyTorch. In: NIPS Autodiff Workshop (2017)
[42] Peyré, G., Cuturi, M., et al.: Computational optimal transport: with applications to data science. Found. Trends^® Mach. Learn. 11(5-6), 355-607 (2019)
[43] Pollard, D.: Convergence of Stochastic Processes. Springer, New York (1984)
[44] Qi, C.R., Su, H., Mo, K., Guibas, L.J.: Pointnet: deep learning on point sets for 3D classification and segmentation. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (2017)
[45] Qi, C.R., Yi, L., Su, H., Guibas, L.J.: Pointnet++: deep hierarchical feature learning on point sets in a metric space. In: Advances in Neural Information Processing Systems, pp. 5099-5108 (2017)
[46] Radon, J.: über die bestimmung von funktionen durch ihre integralwerte längs gewisser mannigfaltigkeiten. Class. Pap. Mod. Diagn. Radiol. 5(21), 124 (2005)
[47] Rostami, R., Bashiri, F.S., Rostami, B., Yu, Z.: A survey on data-driven 3D shape descriptors. Comput. Graph. Forum 38(1), 356-393 (2019)
[48] Ruuth, S.J., Merriman, B.: A simple embedding method for solving partial differential equations on surfaces. J. Comput. Phys. 227(3), 1943-1961 (2008)
[49] Santaló, L.A.: Integral Geometry and Geometric Probability. Cambridge University Press, New York (2004)
[50] Sedaghat, N., Zolfaghari, M., Amiri, E., Brox, T.: Orientation-boosted voxel nets for 3D object recognition. arXiv:1604.03351 (2016)
[51] Settles, B.: Active learning literature survey. Technical report, University of Wisconsin-Madison Department of Computer Sciences (2009)
[52] Shen, Y., Feng, C., Yang, Y., Tian, D.: Mining point cloud local structures by kernel correlation and graph pooling. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2018)
[53] Simonovsky, M., Komodakis, N.: Dynamic edge-conditioned filters in convolutional neural networks on graphs. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 3693-3702 (2017)
[54] Sinha, A., Bai, J., Ramani, K.: Deep learning 3D shape surfaces using geometry images. In: European Conference on Computer Vision. Springer, Berlin (2016)
[55] Solmon, D.C.: The X-ray transform. J. Math. Anal. Appl. 56(1), 61-83 (1976)
[56] The mpmath development team: mpmath: a Python library for arbitrary-precision floating-point arithmetic (version 1.2.1). (2021). https://mpmath.org/
[57] Trefethen, L.N., Weideman, J.A.C.: The exponentially convergent trapezoidal rule. SIAM Rev. 56(3), 385-458 (2014)
[58] Tsai, Y.-H.R.: Rapid and accurate computation of the distance function using grids. J. Comput. Phys. 178(1), 175-195 (2002)
[59] Villani, C.: Optimal Transport: Old and New, vol. 338. Springer, Berlin (2009)
[60] Wang, P.-S., Liu, Y., Guo, Y.-X., Sun, C.-Y., Tong, X.: O-CNN: Octree-based convolutional neural networks for 3D shape analysis. ACM Trans. Gr. (TOG) 36(4), 72 (2017)
[61] Wang, Y., Sun, Y., Liu, Z., Sarma, S.E., Bronstein, M.M., Solomon, J.M.: Dynamic graph CNN for learning on point clouds. ACM Trans. Gr. (TOG) 38(5), 146 (2019)
[62] Wu, Z., Song, S., Khosla, A., Yu, F., Zhang, L., Tang, X., Xiao, J.: 3D shapenets: a deep representation for volumetric shapes. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1912-1920 (2015)
[63] Xia, F., et al.: PointNet.pytorch Git repository. https://github.com/fxia22/pointnet.pytorch
[64] Xie, J., Dai, G., Zhu, F., Wong, E.K., Fang, Y.: Deepshape: deep-learned shape descriptor for 3D shape retrieval. IEEE Trans. Pattern Anal. Mach. Intell. 39(7), 1335-1345 (2016)
[65] Zhou, Y., Tuzel, O.: VoxelNet: end-to-end learning for point cloud based 3D object detection. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 4490-4499 (2018)

Nearest Neighbor Sampling of Point Sets Using Rays

Nearest Neighbor Sampling of Point Sets Using Rays

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价

[1]	Senwei Liang, Yuehaw Khoo, Haizhao Yang. Drop-Activation: Implicit Parameter Reduction and Harmonious Regularization[J]. Communications on Applied Mathematics and Computation, 2021, 3(2): 293-311.
[2]	Kailiang Wu, Dongbin Xiu. Sequential Approximation of Functions in Sobolev Spaces Using Random Samples[J]. Communications on Applied Mathematics and Computation, 2019, 1(3): 449-466.