UC Davis

When dealing with data residing on irregular and complex structures, graph signal processing(GSP) offers the ability to model and process them directly. While most existing GSP methods use graphs and edges to model pairwise relationships of such data, practical data may reside on more complex structures with multilateral interactions, which motivates processing methods with high-dimensional graphs like hypergraphs and multilayer graphs (MLG). Although both hypergraph signal processing (HGSP) and MLG have enjoyed additional notable successes in segmentation, clustering, and classification, it is not clear whether they can provide an advantage in specific applications such as point cloud resampling and motion segmentation. Also, it is shown that high-dimensional graph processing algorithms with high-dimensional graphs constructed for the whole data are computationally costly, especially when the number of nodes is large. Efficient processing and feature extraction of large-scale datasets are important in related computer vision and cyber-physical systems. In this dissertation, we investigate two applications for advanced graph approaches. The first application is point cloud resampling based on hypergraph signal processing to better explore the underlying relationship among different points in the point cloud and to extract contour-enhanced features. Specifically, we design hypergraph spectral filters to capture multi-lateral interactions among the signal nodes of point clouds and to better preserve their surface outlines. Without the need and the computation to first construct the underlying hypergraph, our low complexity approach directly estimates the hypergraph spectrum of point clouds by leveraging hypergraph stationary processes from the observed 3D coordinates. The second application is multilayer graph signal processing (M-GSP) based approaches to human motion segmentation. Specifically, our approach involves modeling spatial-temporal relationships of the human motion capture data via MLG and incorporating M-GSP spectrum analysis for feature extraction. Furthermore, this dissertation optimizes the computational complexity of key algorithms in iigraph based spectral analysis and processing methodologies. We propose an incremental EVD algorithm for low rank symmetric matrices (IEVD-LR) to update the top k eigen-pairs of the graph representation matrix. This algorithm has a novel error correction branch whenever the approximation error exceeds the defined tolerance. Equipped with the techniques presented in this dissertation, we extend the current research on advanced graph based processing to a variety of new directions. Based on our success in applying advanced graph-based processing algorithms to static point clouds and time-varying motion capture data, our exploration can extend to further applications of high-dimensional graph processing techniques on diverse multimedia datasets with varying structures, such as dynamic point clouds. We will also extend the low-complexity eigen-updating algorithm to general dynamic systems, where the number of data points may decrease over time. Another direction is to consider the singular space updating problem for the representation tensor of high-dimensional graphs, initialized by orthogonal CP decomposition or higher-order singular value decomposition result.