Introduction
In modern computer vision, high-dimensional data such as human skeletal movements, object shapes, and optical flow are increasingly represented as points on non-Euclidean manifolds. While these geometric representations—including Grassmann manifolds, hyperspheres, and Special Euclidean groups—offer robust mathematical frameworks for modeling complex dynamics, they introduce significant computational overhead.
Standard operations in Euclidean space, such as calculating an average or determining the distance between two points, become iterative and computationally expensive "geodesic" calculations on curved surfaces. When processing long sequences of data, such as video streams, the cumulative cost of these calculations makes real-time sequence matching and large-scale database retrieval nearly impossible. This paper proposes a framework to bridge the gap between the accuracy of manifold-based representations and the efficiency required for practical applications through a manifold-aware generalization of Symbolic Aggregate Approximation (SAX).
Methodology
The proposed framework transforms complex geometric sequences into ultra-low bandwidth symbolic strings, enabling the use of optimized string-matching algorithms. The process consists of three primary stages:
1. Piece-wise Aggregation on Manifolds
To reduce the dimensionality of a temporal sequence, the data is divided into small time windows. Unlike standard SAX, which uses an arithmetic mean, this method calculates the Fréchet mean (the Riemannian center of mass) for each window. This ensures that the local "average" state remains faithful to the underlying geometry of the manifold.
2. Equiprobable Symbol Learning
The conversion of Fréchet means into discrete symbols requires a codebook or "alphabet." The authors developed a Conscience-based Competitive Learning algorithm specifically for manifolds. While traditional clustering (like K-Means) minimizes reconstruction error, it often leads to an uneven distribution of symbols. The conscience-based approach ensures that each symbol in the alphabet is utilized with approximately equal frequency. This equiprobability is critical for maximizing the efficiency of downstream indexing structures, such as suffix trees.
3. Symbolic Matching and Look-up Tables
Once sequences are converted into strings, the distance between them is no longer calculated via geodesics. Instead, the system uses a pre-computed look-up table containing the distances between symbols. This reduces the matching process to a simple memory retrieval task, transforming a complex geometric problem into a high-speed string comparison with $O(m+n)$ complexity.
Experimental Evaluation
The framework was evaluated across four diverse datasets representing different manifold geometries:
- UMD Human Activity: Silhouette-based shapes on a Grassmann manifold.
- Weizmann Dataset: Histogram of Oriented Optical Flow (HOOF) features on a Hypersphere.
- UTKinect: 3D skeleton data represented as a product space of Special Euclidean groups (SE(3)).
- UCSD Traffic: Video sequences of highway traffic patterns.
Key Results
The experimental results demonstrate that symbolic approximation offers a massive leap in efficiency with minimal impact on recognition performance:
- Computational Speed: Sequence matching was approximately 100x faster than traditional geodesic-based Dynamic Time Warping (DTW). The system processed features at roughly 445 frames per second (fps), far exceeding the 30fps requirement for real-time video.
- Data Compression: The symbolic representation achieved a compression ratio between 97.5% and 99.9% compared to the original high-dimensional feature data.
- Accuracy: On the UMD dataset, the method achieved 98% accuracy. This significantly outperformed Principal Geodesic Analysis (90%) and remained within 2% of the accuracy achieved by the original, computationally heavy features.
Discussion and Future Work
The primary advantage of this framework lies in its ability to move the heavy computational lifting—learning the manifold geometry and the symbol dictionary—to an offline phase. The online phase is reduced to simple look-ups, making it ideal for mobile platforms, robotics, and low-power embedded systems.
However, the method is currently data-dependent. Unlike Euclidean SAX, which can assume a Gaussian distribution, the manifold version requires a training set to learn the specific distribution of the data. Future research directions include integrating automatic temporal segmentation into the symbolic framework and extending the methodology to more abstract structures, such as graphs or complex "bag-of-words" models.
Summary updated