×

Feature-preserving, mesh-free empirical mode decomposition for point clouds and its applications. (English) Zbl 1381.65021

Summary: Point clouds have been extensively employed to represent 3D shapes with the increasing availability of various data acquisition devices/technologies. As a result, more novel techniques are urgently needed for point clouds’ analysis and processing. To date, empirical mode decomposition (EMD) has become a powerful and effective analytical tool for non-stationary, non-linear signals, and has been widely applied to time series processing. Despite the fact that EMD has exhibited its potential in 3D geometry processing, extending the existing techniques of EMD to operate directly on point clouds remains to be extremely challenging. This is primarily because of imperfect point clouds, as well as their absence of topological information.
In this paper, we develop a multi-scale mesh-free EMD algorithm for point clouds and their analysis and processing. The multi-scale mesh-free EMD is achieved by iteratively extracting the detail level from the input signal and leaving the overall shape in residue. Furthermore, in order to preserve sharp features during point-based EMD analysis/processing, we devise an anisotropic structure measurement assisted envelope computation scheme. The structure measurement is computed by the eigenvalue decomposition of voting tensor, which could faithfully characterize the structure of any input model. Under the guidance of the structure measurement, the envelope is computed in a structure-aware manner and the sharp features are well preserved. Unlike previous feature-preserving EMD methods for meshed models, our algorithm does not explicitly resort to sharp feature detection, which is more suitable for complex geometric models. With the well decomposed multi-scale representation, we could explore various applications of point clouds, such as detail enhancement and smoothing, feature points extraction, and feature-preserving denoising. We showcase comprehensive experimental results to demonstrate the utility of our novel multi-scale mesh-free EMD algorithm.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ali, H.; Hariharan, M.; Yaacob, S.; Adom, A. H., Facial emotion recognition using empirical mode decomposition, Expert Syst. Appl., 42, 3, 1261-1277 (2015)
[2] Baghaie, A.; Yu, Z., Image interpolation method based on structure tensor, J. Comput. Appl., 26, 7, 1570-1572 (2006)
[3] Belkin, M.; Sun, J.; Wang, Y., Constructing Laplace operator from point clouds in \(R^d\), (Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (2009)), 1031-1040 · Zbl 07051273
[4] Bernardini, F.; Mittleman, J.; Rushmeier, H.; Silva, C.; Taubin, G., The ball-pivoting algorithm for surface reconstruction, IEEE Trans. Vis. Comput. Graph., 5, 4, 349-359 (1999)
[5] Çelebi, A. T.; Ertürk, S., Visual enhancement of underwater images using empirical mode decomposition, Expert Syst. Appl., 39, 1, 800-805 (2012)
[6] Di, C.; Yang, X.; Wang, X., A four-stage hybrid model for hydrological time series forecasting, PLoS ONE, 9, 8, Article e104663 pp. (2014)
[7] Fleishman, S.; Drori, I.; Cohen-Or, D., Bilateral mesh denoising, ACM Trans. Graph., 22, 3, 950-953 (2003)
[8] Gao, Y.; Li, C.-F.; Ren, B.; Hu, S.-M., View-dependent multiscale fluid simulation, IEEE Trans. Vis. Comput. Graph., 19, 2, 178-188 (2013)
[9] Gemmrich, J. R.; Farmer, D. M., Near-surface turbulence in the presence of breaking waves, J. Phys. Oceanogr., 34, 5, 1067-1086 (2004)
[10] Guennebaud, G.; Gross, M., Algebraic point set surfaces, ACM Trans. Graph., 26, 3, 23:1-23:9 (2007)
[11] Hammond, D. K.; Vandergheynst, P.; Gribonval, R., Wavelets on graphs via spectral graph theory, Appl. Comput. Harmon. Anal., 30, 2, 129-150 (2011) · Zbl 1213.42091
[12] Hu, J.; Wang, X.; Qin, H., Improved, feature-centric EMD for 3D surface modeling and processing, Graph. Models, 76, 5, 340-354 (2014)
[13] Hu, J.; Wang, X.; Qin, H., Novel and efficient computation of Hilbert Huang transform on surfaces, Comput. Aided Geom. Des., 43, 95-108 (2016) · Zbl 1418.68231
[14] Huang, N. E.; Shen, Z.; Long, S. R.; Wu, M. C.; Shih, H. H.; Zheng, Q.; Yen, N.-C.; Tung, C. C.; Liu, H. H., The empirical mode decomposition and the Hilbert spectrum for nonlinear and non-stationary time series analysis, Proc. R. Soc. Lond., Ser. A, Math. Phys. Eng. Sci., 454, 1971, 903-995 (1998) · Zbl 0945.62093
[15] Huang, N. E.; Wu, M.-L. C.; Long, S. R.; Shen, S. S.; Qu, W.; Gloersen, P.; Fan, K. L., A confidence limit for the empirical mode decomposition and Hilbert spectral analysis, Proc. R. Soc. Lond., Ser. A, Math. Phys. Eng. Sci., 459, 2037, 2317-2345 (2003) · Zbl 1045.94503
[16] Huang, H.; Li, D.; Zhang, H.; Ascher, U.; Cohen-Or, D., Consolidation of unorganized point clouds for surface reconstruction, ACM Trans. Graph., 28, 5, 176-182 (2009)
[17] Huang, H.; Wu, S.; Gong, M.; Cohen-Or, D.; Ascher, U.; Zhang, H. R., Edge-aware point set resampling, ACM Trans. Graph., 32, 1, 9:1-9:12 (2013) · Zbl 1322.68222
[18] Kim, H. S.; Choi, H. K.; Lee, K. H., Feature detection of triangular meshes based on tensor voting theory, Comput-Aided Des., 41, 1, 47-58 (2009)
[19] Kopsinis, Y.; McLaughlin, S., Development of EMD-based denoising methods inspired by wavelet thresholding, IEEE Trans. Signal Process., 57, 4, 1351-1362 (2009) · Zbl 1391.94277
[20] Kramer, H. P.; Bruckner, J. B., Iterations of a non-linear transformation for enhancement of digital images, Pattern Recognit., 7, 1-2, 53-58 (1975) · Zbl 0318.68062
[21] Krinidis, S.; Krinidis, M., Empirical mode decomposition on skeletonization pruning, Image Vis. Comput., 31, 8, 533-541 (2013)
[22] Linderhed, A., 2D empirical mode decompositions in the spirit of image compression, (Wavelet and Independent Component Analysis Applications IX (2002)), 1-8
[23] Liu, J.; Cao, J.; Liu, X.; Wang, J.; Wang, X.; Shi, X., Mendable consistent orientation of point clouds, Comput-Aided Des., 55, 26-36 (2014)
[24] Long, S. R., Applications of HHT in image analysis, (Hilbert-Huang Transform and Its Applications (2005)), 289-305
[25] Luo, C., Laplace-Based Spectral Method for Point Cloud Processing (2014), The Ohio State University, Ph.D. thesis
[26] Luo, Y.; Al-Dossary, S.; Marhoon, M.; Alfaraj, M., Generalized Hilbert transform and its applications in geophysics, Lead. Edge, 22, 3, 198-202 (2003)
[27] Luo, C.; Safa, I.; Wang, Y., Approximating gradients for meshes and point clouds via diffusion metric, (Proceedings of the Symposium on Geometry Processing. Proceedings of the Symposium on Geometry Processing, SGP’09 (2009)), 1497-1508
[28] Mandic, D.; Rehman, N.; Wu, Z.; Huang, N., Empirical mode decomposition-based time-frequency analysis of multivariate signals: the power of adaptive data analysis, Signal Process. Mag., IEEE, 30, 6, 74-86 (2013)
[29] Manh, H. T.; Yeo, J.; Lee, G., Saliency detection by tensor voting based Gaussian modeling, (Proceedings of the 9th International Conference on Ubiquitous Information Management and Communication. Proceedings of the 9th International Conference on Ubiquitous Information Management and Communication, IMCOM’15 (2015)), 68-75
[30] Niang, O.; Thioune, A.; Gueirea, M. C.E.; Del Échelle, E.; Lemoine, J., Partial differential equation-based approach for empirical mode decomposition: application on image analysis, IEEE Trans. Image Process., 21, 9, 3991-4001 (2012) · Zbl 1373.94305
[31] Nunes, J.; Bouaoune, Y.; Delechelle, E.; Niang, O.; Bunel, P., Image analysis by bidimensional empirical mode decomposition, Image Vis. Comput., 21, 12, 1019-1026 (2003)
[32] Osher, S.; Rudin, L. I., Feature-oriented image enhancement using shock filters, SIAM J. Numer. Anal., 27, 4, 919-940 (1990) · Zbl 0714.65096
[33] Öztireli, A. C.; Guennebaud, G.; Gross, M., Feature preserving point set surfaces based on non-linear kernel regression, Comput. Graph. Forum, 28, 2, 493-501 (2009)
[34] Park, M. K.; Lee, S. J.; Lee, K. H., Multi-scale tensor voting for feature extraction from unstructured point clouds, Graph. Models, 74, 4, 197-208 (2012)
[35] Prada, M. K. Fabian, Unconditionally stable shock filters for image and geometry processing, Comput. Graph. Forum, 34, 5, 201-210 (2015)
[36] Qin, X.; Hong, C. X.; Zhang, S. Q.; Wang, W. H., EMD based fairing algorithm for mesh surface, (CAD/Graphics’09 (2009)), 606-609
[37] Ren, B.; Li, C.-F.; Lin, M.; Kim, T.; Hu, S.-M., Flow field modulation, IEEE Trans. Vis. Comput. Graph., 19, 10, 1708-1719 (2013)
[38] Schneider, E. K.; Fennessy, M. J.; Kinter, J. L., A statistical-dynamical estimate of winter ENSO teleconnections in a future climate, J. Climate, 22, 24, 6624-6638 (2009)
[39] Subr, K.; Soler, C.; Durand, F., Edge-preserving multiscale image decomposition based on local extrema, ACM Trans. Graph., 28, 5, 147-155 (2009)
[40] Tsuchie, S.; Higashi, M., Surface mesh denoising with normal tensor framework, Graph. Models, 74, 4, 130-139 (2012)
[41] Vallet, B.; Lévy, B., Spectral geometry processing with manifold harmonics, Comput. Graph. Forum, 27, 2, 251-260 (2008)
[42] Wang, X.; Cao, J.; Liu, X.; Li, B.; Shi, X.; Sun, Y., Feature detection of triangular meshes via neighbor supporting, J. Zhejiang Univ. Sci. C, 13, 6, 440-451 (2012)
[43] Wang, H.; Su, Z.; Cao, J.; Wang, Y.; Zhang, H., Empirical mode decomposition on surfaces, Graph. Models, 74, 4, 173-183 (2012)
[44] Wang, X.; Hu, J.; Zhang, D.; Qin, H., Efficient EMD and Hilbert spectra computation for 3D geometry processing and analysis via space-filling curve, Vis. Comput., 31, 6, 1135-1145 (2015)
[45] Wang, X.; Hu, J.; Zhang, D.; Guo, L.; Qin, H.; Hao, A., Multi-scale geometry detail recovery on surfaces via empirical mode decomposition, Comput. Graph., 1-10 (2017)
[46] Weickert, J., Coherence-enhancing shock filters, (Pattern Recognition. Pattern Recognition, Lecture Notes in Computer Science, vol. 2781 (2003), Springer: Springer Berlin, Heidelberg), 1-8
[47] Wu, Z.; Schneider, E. K.; Kirtman, B. P.; Sarachik, E. S.; Huang, N. E.; Tucker, C. J., The modulated annual cycle: an alternative reference frame for climate anomalies, Clim. Dyn., 31, 7-8, 823-841 (2008)
[48] Wu, Z.; Huang, N. E.; Chen, X., The multi-dimensional ensemble empirical mode decomposition method, Adv. Adapt. Data Anal., 01, 03, 339-372 (2009)
[49] Xie, X., Illumination preprocessing for face images based on empirical mode decomposition, Signal Process., 103, 250-257 (2014)
[50] Xu, Y.; Liu, B.; Liu, J.; Riemenschneider, S., Two-dimensional empirical mode decomposition by finite elements, Proc. R. Soc. Lond., Ser. A, Math. Phys. Eng. Sci., 462, 3081-3096 (2006) · Zbl 1149.74395
[51] Xu, G.; Wang, X. T.; Xu, X. G., Improved bi-dimensional EMD and Hilbert spectrum for the analysis of textures, Pattern Recognit., 42, 5, 718-734 (2009) · Zbl 1178.68491
[52] Xu, K.; Zhang, H.; Cohen-Or, D.; Xiong, Y., Dynamic harmonic fields for surface processing, Comput. Graph., 33, 3, 391-398 (2009)
[53] Zang, Y.; Huang, H.; Zhang, L., Efficient structure-aware image smoothing by local extrema on space-filling curve, IEEE Trans. Vis. Comput. Graph., 20, 9, 1253-1265 (2014)
[54] Zang, Y.; Huang, H.; Zhang, L., Guided adaptive image smoothing via directional anisotropic structure measurement, IEEE Trans. Vis. Comput. Graph., 21, 9, 1015-1027 (2015)
[55] Zhang, D.; Wang, X.; Hu, J.; Qin, H., Interactive modeling of complex geometric details based on empirical mode decomposition for multi-scale 3D shapes, Comput-Aided Des., 87, 1-10 (2017)
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.