Nearest Neighbor Sampling of Point Sets Using Rays

doi:10.1007/s42967-023-00318-1

Abstract

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.

TrendMD

References

[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)