Nearest Neighbor Sampling of Point Sets Using Rays

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.

Keywords

Point clouds / Sampling / Classification / Registration / Deep learning / Voronoi cell analysis

References

[1.] Atzmon, M., Maron, H., Lipman, Y.: Point convolutional neural networks by extension operators. arXiv:1803.10091 (2018)

[2.] Bentley JL. Multidimensional binary search trees used for associative searching. Commun. ACM, 1975, 18(9): 509-517,

[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 RE. Monte Carlo and quasi-Monte Carlo methods. Acta Numer., 1998, 7: 1-49,

[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 RM, Gonnet GH, Hare DE, Jeffrey DJ, Knuth DE. On the LambertW function. Adv. Comput. Math., 1996, 5(1): 329-359,

[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, 1994, 36(4): 338-347,

[9.] Daley DJ, Vere-Jones D. . An Introduction to the Theory of Point Processes. Volume I: Elementary Theory and Methods, 2003 New York Springer

[10.] De Bruijn NG. . Asymptotic Methods in Analysis, 1981 USA Courier Corporation

[11.] Doerr B. Probabilistic tools for the analysis of randomized optimization heuristics. Theory of Evolutionary Computation, 2020 Cham, Switzerland Springer 1-87,

[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., 1956, 27(3): 642-669,

[14.] Eldar Y, Lindenbaum M, Porat M, Zeevi YY. The farthest point strategy for progressive image sampling. IEEE Trans. Image Process., 1997, 6(9): 1305-1315,

[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, 1957 Berlin Springer,

[18.] Helgason S, Helgason S. . The Radon Transform, 1980 New York Springer,

[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., 2001, 25(2): 269-285,

[22.] Johnson J, Douze M, Jégou H. Billion-scale similarity search with GPUs. IEEE Trans. Big Data, 2019, 7(3): 535-547,

[23.] Jones PW, Osipov A, Rokhlin V. A randomized approximate nearest neighbors algorithm. Applied and Computational Harmonic Analysis, 2013, 34(3): 415-444,

[24.] Kazmi IK, You L, Zhang JJ. A survey of 2D and 3D shape descriptors. 2013 10th International Conference Computer Graphics, Imaging and Visualization, pp 1–10, 2013 IEEE

[25.] Kingma, D.P., Ba, J.: Adam: a method for stochastic optimization. arXiv:1412.6980 (2014)

[26.] Klain DA, Rota G-C. . Introduction to Geometric Probability, 1997 Cambridge Cambridge University Press

[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. Computer Vision Metrics, 2016 Cham Springer 187-246,

[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., 1998, 1: 602-608

[33.] Macdonald CB, Merriman B, Ruuth SJ. Simple computation of reaction-diffusion processes on point clouds. Proc. Natl. Acad. Sci., 2013, 110(23): 9209-9214,

[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 PC. On the generalised distance in statistics. Proc. Natl. Inst. Sci. India, 1936, 2: 49-55

[36.] Massart P. The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality. Ann. Prob., 1990, 1990: 1269-1283

[37.] Meurer A, Smith CP, Paprocki M, Čertík O, Kirpichev SB, Rocklin M, Kumar A, Ivanov S, Moore JK, Singh S, Rathnayake T, Vig S, Granger BE, Muller RP, Bonazzi F, Gupta H, Vats S, Johansson F, Pedregosa F, Curry MJ, Terrel AR, Roučka Š, Saboo A, Fernando I, Kulal S, Cimrman R, Scopatz A. SymPy: symbolic computing in Python. PeerJ Comput. Sci., 2017, 3,

[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, 2001 USA Society for Industrial and Applied Mathematics,

[40.] Osting B, Wang D, Xu Y, Zosso D. Consistency of archetypal analysis. SIAM J. Math. Data Sci., 2021, 3(1): 1-30,

[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., 2019, 11(5–6): 355-607,

[43.] Pollard D. . Convergence of Stochastic Processes, 1984 New York Springer,

[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., 2005, 5(21): 124

[47.] Rostami R, Bashiri FS, Rostami B, Yu Z. A survey on data-driven 3D shape descriptors. Comput. Graph. Forum, 2019, 38(1): 356-393,

[48.] Ruuth SJ, Merriman B. A simple embedding method for solving partial differential equations on surfaces. J. Comput. Phys., 2008, 227(3): 1943-1961,

[49.] Santaló LA. . Integral Geometry and Geometric Probability, 2004 New York Cambridge University Press,

[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. European Conference on Computer Vision, 2016 Berlin Springer

[55.] Solmon DC. The X-ray transform. J. Math. Anal. Appl., 1976, 56(1): 61-83,

[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 LN, Weideman JAC. The exponentially convergent trapezoidal rule. SIAM Rev., 2014, 56(3): 385-458,

[58.] Tsai Y-HR. Rapid and accurate computation of the distance function using grids. J. Comput. Phys., 2002, 178(1): 175-195,

[59.] Villani C. . Optimal Transport: Old and New, 2009 Berlin Springer

[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), 2017, 36(4): 72

[61.] Wang Y, Sun Y, Liu Z, Sarma SE, Bronstein MM, Solomon JM. Dynamic graph CNN for learning on point clouds. ACM Trans. Gr. (TOG), 2019, 38(5): 146

[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 EK, Fang Y. Deepshape: deep-learned shape descriptor for 3D shape retrieval. IEEE Trans. Pattern Anal. Mach. Intell., 2016, 39(7): 1335-1345,

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

Funding

National Science Foundation(DMS-144041); Simons Foundation(DMS-211089); Natural Sciences and Engineering Research Council of Canada; National Science Foundation(DMS-172017)