×

Computation of circular area and spherical volume invariants via boundary integrals. (English) Zbl 07198503

Summary: We show how to compute the circular area invariant of planar curves, and the spherical volume invariant of surfaces, in terms of line and surface integrals, respectively. We use the divergence theorem to express the area and volume integrals as line and surface integrals, respectively, against particular kernels; our results also extend to higher-dimensional hypersurfaces. The resulting surface integrals are computable analytically on a triangulated mesh. This gives a simple computational algorithm for computing the spherical volume invariant for triangulated surfaces that does not involve discretizing the ambient space. We discuss potential applications to feature detection on broken bone fragments of interest in anthropology.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
65D30 Numerical integration
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
65N38 Boundary element methods for boundary value problems involving PDEs

Software:

ASIFT
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] PWN2PLY: Converter from PWN Format to PLY Format, https://www.mathworks.com/matlabcentral/fileexchange/56709-pwn2ply.
[2] M. Ankerst, G. Kastenmüller, H.-P. Kriegel, and T. Seidl, \(3\) d shape histograms for similarity search and classification in spatial databases, in Advances in Spatial Databases. R.H. Güting, D. Papadias, and F. Lochovsky, eds., Lecture Notes in Comput. Sci. 1651, Springer, New York, 1999, pp. 207-226.
[3] P. K. Banerjee and R. Butterfield, Boundary Element Methods in Engineering Science, Vol. 17, McGraw-Hill, London, 1981. · Zbl 0499.73070
[4] L. E. Bartram Jr. and C. W. Marean, Explaining the “klasies pattern”: Kua ethnoarchaeology, the Die Kelders middle stone age archaeofauna, long bone fragmentation and carnivore ravaging, J. Archaeol. Sci., 26 (1999), pp. 9-29.
[5] S. Belongie, J. Malik, and J. Puzicha, Shape matching and object recognition using shape contexts, IEEE Trans. Pattern Anal. Mach. Intell. 24 (2002), pp. 509-522.
[6] A. Bertozzi, S. Esedoḡlu, and A. Gillette, Inpainting of binary images using the Cahn-Hilliard equation, IEEE Trans. Image Process. 16 (2007), pp. 285-291. · Zbl 1279.94008
[7] A. Bugeau, M. Bertalmío, V. Caselles, and G. Sapiro, A comprehensive framework for image inpainting, IEEE Trans. Image Process. 19 (2010), pp. 2634-2645. · Zbl 1371.94065
[8] J. Calder and S. Esedoḡlu, On the circular area signature for graphs, SIAM J. Imaging Sci., 5 (2012), pp. 1355-1379. · Zbl 1259.45010
[9] V. Caselles, R. Kimmel, and G. Sapiro, Geodesic active contours, Int. J. Comput. Vis., 22 (1997), pp. 61-79. · Zbl 0894.68131
[10] T. Chan and J. Shen, Image Processing and Analysis. Variational, PDE, Wavelet, and Stochastic Methods. SIAM, Philadelphia, 2005. · Zbl 1095.68127
[11] T. Chan and J. Shen, Variational image inpainting, Comm. Pure Appl. Math., 58 (2005), pp. 579-619. · Zbl 1067.68168
[12] R. Coil, M. Tappen, and K. Yezzi-Woodley, New analytical methods for comparing bone fracture angles: A controlled study of hammerstone and hyena (crocuta crocuta) long bone breakage, Archaeometry, 59 (2017), pp. 900-917.
[13] B. Curless and M. Levoy, A volumetric method for building complex models from range images, SIGGRAPH ’96, ACM, New York, 1996, pp. 303-312.
[14] C. H. Ding, X. He, H. Zha, M. Gu, and H. D. Simon, A min-max cut algorithm for graph partitioning and data clustering, in Proceedings 2001 IEEE International Conference on Data Mining, IEEE Computer Society, Los Alamitos, CA, 2001, pp. 107-114.
[15] S. Feng, I. Kogan, and H. Krim, Classification of curves in 2D and 3D via affine integral signatures, Acta. Appl. Math., 109 (2010), pp. 903-937. · Zbl 1203.53001
[16] V. A. García, R. B. Egido, J. M. B. del Pino, A. B. C. Ruiz, A. I. E. Vidal, Á. F. Aparicio, S. H. Calleja, A. I. Jiménez, M. M. González, M. P. Gil, V. P. Tello, J. R. Calvo, J. Yravedra, A. Vidal, and M. Domínguez-Rodrigo, Determinación de procesos de fractura sobre huesos frescos: Un sistema de análisis de los ángulos de los planos de fracturación como discriminador de agentes bióticos, Trabajos Prehistoria, 63 (2006), pp. 37-45.
[17] A. Grim, T. O’Connor, P. Olver, C. Shakiban, R. Slechta, and R. Thompson, Automatic reassembly of three-dimensional jigsaw puzzles, Int. J. Image Graph., 16 (2016), 1650009.
[18] C. Hann and M. Hickman, Projective curvature and integral invariants, Acta Appl. Math., 74 (2002), pp. 177-193. · Zbl 1035.53026
[19] D. Hoff and P. Olver, Automatic solution of jigsaw puzzles, J. Math. Imaging Vision, 49 (2014), pp. 234-250. · Zbl 1361.68291
[20] L. P. Karr and A. K. Outram, Actualistic research into dynamic impact and its implications for understanding differential bone fragmentation and survivorship, J. Archaeol. Sci., 39 (2012), pp. 3443-3449.
[21] D. Lowe, Object recognition from local scale-invariant features, in Integration of Speech and Image Understanding, IEEE Computer Society, Los Alamitos, CA, 1999, pp. 1150-1157.
[22] S. Manay, D. Cremers, B.-W. Hong, A. Yezzi, and S. Soatto, Integral invariants and shape matching, in Statistics and Analysis of Shapes. H. Krim and A. Yezzi, eds., Birkhäuser, Boston, 2006, pp. 137-166. · Zbl 1171.68699
[23] E. Merkurjev, T. Kostić, and A. L. Bertozzi, An MBO scheme on graphs for classification and image processing, SIAM J. Imaging Sci., 6 (2013), pp. 1903-1930. · Zbl 1279.68335
[24] E. Merkurjev, J. Sunu, and A. L. Bertozzi, Graph MBO method for multiclass segmentation of hyperspectral stand-off detection video, in 2014 IEEE International Conference on Image Processing (ICIP), IEEE, Piscataway, NJ, 2014, pp. 689-693.
[25] S. R. Merritt and K. M. Davis, Diagnostic properties of hammerstone-broken long bone fragments, specimen identifiability, and early stone age butchered assemblage interpretation, J. Archaeol. Sci., 85 (2017), pp. 114-123.
[26] S. Nintcheu Fata, Explicit expressions for 3d boundary integrals in potential theory, Internat. J. Numer. Methods Engrg., 78 (2009), pp. 32-47. · Zbl 1183.65155
[27] R. Osada, T. Funkhouser, B. Chazelle, and D. Dobkin, Shape distributions, ACM Trans. Graph., 21 (2002), pp. 807-832. · Zbl 1331.68256
[28] O. Pele and M. Werman, A linear time histogram for improved SIFT matching, in Computer Vision - ECCV 2008. Part III, D. Forsyth, P. Torr, and A. Zisserman, eds., Lecture Notes in Comput. Sci. 5304, Springer, Berlin, 2008, pp. 495-508.
[29] T. R. Pickering, M. Domínguez-Rodrigo, C. P. Egeland, and C. Brain, The contribution of limb bone fracture patterns to reconstructing early hominid behaviour at Swartkrans cave (South Africa): Archaeological application of a new analytical method, Internat. J. Osteoarchaeol., 15 (2005), pp. 247-260.
[30] H. Pottmann, J. Wallner, Q.-X. Huang, and Y.-L. Yang, Integral invariants for robust geometry processing, Comput. Aided Geom. Design, 26 (2009), pp. 37-60. · Zbl 1205.53012
[31] H. Pottmann, J. Wallner, Y.-L. Yang, Y.-K. Lai, and S.-M. Hu, Principal curvatures from the integral invariant viewpoint, Comput. Aided Geom. Design, 24 (2007), pp. 428-442. · Zbl 1171.65350
[32] M. Sa\ugiro\uglu and A. Er\ccil · Zbl 1213.68546
[33] M. Sa\ugiro\uglu and A. Er\ccil, A texture based approach to reconstruction of archaeological finds, in Proceedings of the 6th International Conference on Virtual Reality, Archaeology and Intelligent Cultural Heritage, VAST05. M. Mudge, N. Ryan, and R. Scopigno, eds., Eurographics Association, Aire-la-Ville, Switzerland, 2005, pp. 137-142.
[34] G. Sapiro, Geometric Partial Differential Equations and Image Analysis, Cambridge University Press, Cambridge, 2001. · Zbl 0968.35001
[35] E. \cSaykol, U. Güdükbaya, and O. Ulusoya, A histogram-based approach for object-based query-by-shape-and-color in image and video databases, Image Vision Comput., 23 (2005), pp. 1170-1180.
[36] M. Sonka, V. Havlac, and R. Boyle, Image Processing: Analysis and Machine Vision, Brooks/Cole, Pacific Grove, CA, 1999.
[37] R. Thompson, private communication, 2016.
[38] Y.-L. Yang, Y.-K. Lai, S.-M. Hu, and H. Pottmann, Robust principal curvatures on multiple scales, in Symposium on Geometry Processing, Eurograpics Association, Aire-la-Ville, Switzerland, 2006, pp. 223-226.
[39] G. Yu and J.-M. Morel, ASIFT: An algorithm for fully affine invariant comparison, IPOL J. Image Process. Online, 1 (2011), pp. 11-38.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.