The Signed Cumulative Distribution Transform for 1-D signal analysis and classification

Akram Aldroubi; Rocio Diaz Martin; Ivan Medri; Gustavo K. Rohde; Sumati Thareja

doi:10.3934/fods.2022001

Article Contents

2022, Volume 4, Issue 1: 137-163. Doi: 10.3934/fods.2022001

This issue Previous Article Smart Gradient - An adaptive technique for improving gradient estimation Next Article

The Signed Cumulative Distribution Transform for 1-D signal analysis and classification

1.
Department of Mathematics, Vanderbilt University, 1326 Stevenson Center, Nashville, TN 37240, USA
2.
Department of Biomedical Engineering, Department of Electrical and Computer Engineering, University of Virginia, Charlottesville, VA 22904, USA

^*Corresponding author: Ivan Medri
^*Corresponding author: Ivan Medri

Received: June 2021

Revised: October 2021

Early access: January 2022

Published: March 2022

This work is partially supported by NIH award GM130825. The second author was partially supported by CONICET

Abstract / Introduction Full Text(HTML) Figure(6) Related Papers Cited by

Abstract

This paper presents a new mathematical signal transform that is especially suitable for decoding information related to non-rigid signal displacements. We provide a measure theoretic framework to extend the existing Cumulative Distribution Transform [29] to arbitrary (signed) signals on $ \overline {\mathbb{R}} $. We present both forward (analysis) and inverse (synthesis) formulas for the transform, and describe several of its properties including translation, scaling, convexity, linear separability and others. Finally, we describe a metric in transform space, and demonstrate the application of the transform in classifying (detecting) signals under random displacements.

Keywords:

Mathematics Subject Classification: Primary: 94A12, 94A16; Secondary: 68T01, 68T10.

Citation:

Full Text(HTML)

Figure 1. The (modified) Cumulative Distribution Transform (CDT) enables data representation that facilitates learning. Hand signal images are preprocessed for edge map extraction and their respective X and Y projections are computed. The X, Y projections are then transformed using the CDT. Linear classification methods are then applied to the data in CDT space, as well as in original (projection) space for comparison. The middle row displays the 2D linear discriminant embedding [41] of test data in original signal space and transform space. Test (held out from training) data in transform space is clearly more convex and linearly separable than data in original signal space. This is confirmed by test accuracy results of 3 different linear classifiers (bottom row)

Download: Full-size image PowerPoint slide

Figure 2. Translation property of the SCDT. Left panel: A signal and its translation. Right panel: A transforms of the signals and its translation (the reference measure $ \mu_0 $ was taken with uniform distribution on $ [0,1] $)

Download: Full-size image PowerPoint slide

Figure 3. Scaling property of the SCDT. Left panel: A signal and its scaling. Right panel: A transforms of the signals and its scaling (the reference measure $ \mu_0 $ was taken with uniform distribution on $ [0,1] $)

Download: Full-size image PowerPoint slide

Figure 4. The set of signals generated from the algebraic generative model stated in Proposition 2 becomes convex in the SCDT space

Download: Full-size image PowerPoint slide

Figure 5. Three signal classes: A Gabor wave, an apodized sawtooth wave, and an apodized square wave are randomly translated and scaled to form three signal classes. Seven example training signals are shown per class

Download: Full-size image PowerPoint slide

Figure 6. Classification of test signals (from the three classes depicted in Figure 5): Projection to LDA subspace learned from training data. Left panel: The linear classification method is unsuccessful classifying signal data in its original space. Right panel: Test data is much better separated in SCDT space

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	A. Aldroubi, S. Li and G. K. Rohde, Partitioning signal classes using transport transforms for data analysis and machine learning, Sampl. Theory Signal Process. Data Anal., 19 (2021), 25pp. doi: 10.1007/s43670-021-00009-z.
[2]	L. Ambrosio, Lecture notes on optimal transport problems, in Mathematical Aspects of Evolving Interfaces (Funchal, 2000), Lecture Notes in Math., 1812, Springer, Berlin, 2003 1–52. doi: 10.1007/978-3-540-39189-0_1.
[3]	M. Arjovsky, S. Chintala and L. Bottou, Wasserstein generative adversarial networks, International Conference on Machine Learning PMLR, 2017,214–223.
[4]	S. Basu, S. Kolouri and G. K. Rohde, Detecting and visualizing cell phenotype differences from microscopy images using transport-based morphometry, PNAS, 111 (2014), 3448-3453. doi: 10.1073/pnas.1319779111.
[5]	T. Cai, J. Cheng, N. Craig and K. Craig, Linearized optimal transport for collider events, Phys. Rev. D, 102 (2020). doi: 10.1103/PhysRevD.102.116019.
[6]	T. Cai, J. Cheng, B. Schmitzer and M. Thorpe, The Linearized Hellinger–Kantorovich Distance, SIAM J. Imaging Sci., 15 (2022), 45-83. doi: 10.1137/21M1400080.
[7]	L. Chizat, G. Peyré, B. Schmitzer and F.-X. Vialard, Unbalanced optimal transport: Dynamic and Kantorovich formulations, J. Funct. Anal., 274 (2018), 3090-3123. doi: 10.1016/j.jfa.2018.03.008.
[8]	N. Courty, R. Flamary, D. Tuia and A. Rakotomamonjy, Optimal transport for domain adaptation, IEEE Trans. Pattern Anal. Mach. Intell., 39 (2017), 1853-1865. doi: 10.1109/TPAMI.2016.2615921.
[9]	P. Embrechts and M. Hofert, A note on generalized inverses, Math. Methods Oper. Res., 77 (2013), 423-432. doi: 10.1007/s00186-013-0436-7.
[10]	B. Engquist and B. D. Froese, Application of the Wasserstein metric to seismic signals, Commun. Math. Sci., 12 (2014), 979-988. doi: 10.4310/CMS.2014.v12.n5.a7.
[11]	B. Engquist, B. D. Froese and Y. Yang, Optimal transport for seismic full waveform inversion, Commun. Math. Sci., 14 (2016), 2309-2330. doi: 10.4310/CMS.2016.v14.n8.a9.
[12]	R. A. Fisher, The use of multiple measurements in taxonomic problems, Ann. Eugenics, 7 (1936), 179-188. doi: 10.1111/j.1469-1809.1936.tb02137.x.
[13]	W. Gangbo, W. Li, Wuchen, S. Osher and M. Puthawala, Unnormalized optimal transport, J. Comput. Phys., 399 (2019), 17pp. doi: 10.1016/j.jcp.2019.108940.
[14]	S. Haker, L. Zhu, A. Tannenbaum and S. Angenent, Optimal mass transport for registration and warping, Phys. Rev. D, 60 (2004), 225-240. doi: 10.1023/B:VISI.0000036836.66311.97.
[15]	S.-W. Huang, G. K. Rohde, H.-M. Cheng and S.-F. Lin, Discretized target size detection in electrical impedance tomography using neural network classifier, J. Nondestructive Evaluation, 39 (2020), 1-9. doi: 10.1007/s10921-020-00723-z.
[16]	D. W. Kammler, A First Course in Fourier Analysis, 2^nd edition, Cambridge University Press, Cambridge, 2007.
[17]	S. Kolouri, K. Nadjahi, U. Şimşekli, R. Badeau and G. K. Rohde, Generalized sliced Wasserstein distances, preprint, 2019, arXiv: 1902.00434.
[18]	S. Kolouri, S. R. Park and G. K. Rohde, The radon cumulative distribution transform and its application to image classification, IEEE Trans. Image Process., 25 (2016), 920-934. doi: 10.1109/TIP.2015.2509419.
[19]	S. Kolouri, S. R. Park, M. Thorpe, D. Slepcev and G. K. Rohde, Optimal mass transport: Signal processing and machine-learning applications, IEEE Signal Process. Magazine, 34 (2017), 43-59. doi: 10.1109/MSP.2017.2695801.
[20]	S. Kolouri and G. K. Rohde, Transport-based single frame super resolution of very low resolution face images, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Boston, MA, USA, 2015. doi: 10.1109/CVPR.2015.7299121.
[21]	S. Kolouri, A. B. Tosun, J. A. Ozolek and G. K. Rohde, A continuous linear optimal transport approach for pattern analysis in image datasets, Pattern Recognition, 51 (2016), 453-462. doi: 10.1016/j.patcog.2015.09.019.
[22]	S. Kolouri, Y. Zou and G. K. Rohde, Sliced Wasserstein kernels for probability distributions, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Las Vegas, NV, USA, 2016. doi: 10.1109/CVPR.2016.568.
[23]	S. Kundu, B. G. Ashinsky, M. Bouhrara, E. B. Dam and S. Demehri, et al., Enabling early detection of osteoarthritis from presymptomatic cartilage texture maps via transport-based learning, PNAS, 117 (2020), 24709-24719. doi: 10.1073/pnas.1917405117.
[24]	S. Kundu, S. Kolouri, K. I. Erickson, A. F. Kramer, E. McAuley and G. K. Rohde, Discovery and visualization of structural biomarkers from MRI using transport-based morphometry, NeuroImage, 167 (2018), 256-275. doi: 10.1016/j.neuroimage.2017.11.006.
[25]	S. Mallat, Group invariant scattering, Comm. Pure Appl. Math., 65 (2012), 1331-1398. doi: 10.1002/cpa.21413.
[26]	S. Mallat, A Wavelet Tour of Signal Processing, Academic Press, Inc., San Diego, CA, 1998.
[27]	J. A. Ozolek, A. B. Tosun, W. Wang, C. Chen and S. Kolouri, et al., Accurate diagnosis of thyroid follicular lesions from nuclear morphology using supervised learning, Medical Image Analysis, 18 (2014), 772-780. doi: 10.1016/j.media.2014.04.004.
[28]	S. R. Park, L. Cattell, J. M. Nichols, A. Watnik, T. Doster and G. K. Rohde, De-multiplexing vortex modes in optical communications using transport-based pattern recognition, Optics Express, 26 (2018), 4004-4022. doi: 10.1364/OE.26.004004.
[29]	S. R. Park, S. Kolouri, S. Kundu and G. K. Rohde, The cumulative distribution transform and linear pattern classification, Appl. Comput. Harmon. Anal., 45 (2018), 616-641. doi: 10.1016/j.acha.2017.02.002.
[30]	F. Pedregosa, et al., Scikit-Learn: Machine Learning in Python, Python package. Available from: http://jmlr.org/papers/v12/pedregosa11a.html
[31]	J. G. Proakis, Digital Communications, McGraw-Hill, 1983.
[32]	G. K. Rohde, et al., PyTranskit, Python package. Available from: https://github.com/rohdelab/PyTransKit.
[33]	H. L. Royden, Real Analysis, The Macmillan Company, New York; Collier-Macmillan Ltd., London, 1963.
[34]	A. H. M. Rubaiyat, K. M. Hallam, J. M. Nichols, M. N. Hutchinson, S. Li and G. K. Rohde, Parametric signal estimation using the cumulative distribution transform, IEEE Trans. Signal Process., 68 (2020), 3312-3324. doi: 10.1109/TSP.2020.2997181.
[35]	F. Santambrogio, Optimal Transport for Applied Mathematicians. Calculus of Variations, PDEs, and Modeling, Progress in Nonlinear Differential Equations and their Applications, 87, Birkhäuser/Springer, Cham, 2015. doi: 10.1007/978-3-319-20828-2.
[36]	M. Shifat-E-Rabbi, X. Yin, A. H. M. Rubaiyat, S. Li and S. Kolouri, et al., Radon cumulative distribution transform subspace modeling for image classification, J. Math. Imaging Vision, 63 (2021), 1185-1203. doi: 10.1007/s10851-021-01052-0.
[37]	M. Thorpe, Introduction to Optimal Transport, 2018. Available from: https://www.math.cmu.edu/mthorpe/OTNotes.
[38]	M. Thorpe, S. Park, S. Kolouri, G. K. Rohde and D. Slepčev, A transportation $L^p$ distance for signal analysis, J. Math. Imaging Vision, 59 (2017), 187-210. doi: 10.1007/s10851-017-0726-4.
[39]	A. B. Tosun, O. Yergiyev, S. Kolouri, J. F. Silverman and G. K. Rohde, Detection of malignant mesothelioma using nuclear structure of mesothelial cells in effusion cytology specimens, Cytometry Part A, 87 (2015), 326-333. doi: 10.1002/cyto.a.22602.
[40]	C. Villani, Topics in Optimal Transportation, Graduate Studies in Mathematics, 58, American Mathematical Society, Providence, RI, 2003. doi: 10.1090/gsm/058.
[41]	W. Wang, Y. Mo, J. A. Ozolek and G. K. Rohde, Penalized Fisher discriminant analysis and its application to image-based morphometry, Pattern Recog. Lett., 32 (2011), 2128-2135. doi: 10.1016/j.patrec.2011.08.010.
[42]	W. Wang, D. Slepčev, S. Basu, J. A. Ozolek and G. K. Rohde, A linear optimal transportation framework for quantifying and visualizing variations in sets of images, Int. J. Comput. Vis., 101 (2013), 254-269. doi: 10.1007/s11263-012-0566-z.
[43]	L. Zhu, Y. Yang, S. Haker and A. Tannenbaum, An image morphing technique based on optimal mass preserving mapping, IEEE Trans. Image Process., 16 (2007), 1481-1495. doi: 10.1109/TIP.2007.896637.