Opportunity
Finding correspondences between features in images is critical for computer vision tasks like object detection, tracking, and image classification. Traditional graph matching uses pairwise (second-order) compatibility but fails under rotation and scaling deformations. Higher-order (hypergraph) matching integrates better geometric information and handles transformations more robustly, but suffers from exponentially increased computational complexity. A third-order compatibility tensor for matching 1000 points requires over 7 terabytes of memory—impractical for real-time applications or high-definition medical imaging. Existing methods like approximate nearest neighbor (ANN) reduce complexity but still require exhaustive computation for large-scale problems and cannot scale beyond a few hundred points under typical memory constraints. There is an urgent need for a scalable hypergraph matching framework that can handle thousands of points with high accuracy and acceptable memory usage.
Technology
This patent presents a cascaded second- and third-order hypergraph matching framework based on CUR decomposition. The system first performs CUR-based second-order graph matching to obtain a rough matching result. Instead of computing the full compatibility matrix (which would require terabytes), it randomly samples a small number of columns and rows to form matrix C, then computes U* via optimization, approximating H ≈ C U* Cᵀ. This reduces memory from O((n₁n₂)²) to O(c n₁n₂) where c << n₁n₂.
Next, using the second-order result to guide sampling, the system performs fiber-CUR-based compatibility tensor generation. Rather than calculating entire tensor blocks, it computes only selected fibers along each mode, drastically reducing computation. The result is a sparse third-order compatibility tensor with far fewer nonzero entries than ANN-based methods.
Finally, a Probability Relaxation Labeling (PRL) based matching algorithm iteratively updates assignment probabilities using a normalized power iteration that leverages tensor sparsity for fast convergence. The algorithm can be expressed with a normalized update rule incorporating first-order compatibility and tensor-vector products. The system scales to matching 1000-vs-1000 points with over 98% accuracy, while ANN-based methods fail beyond 300 points under the same memory constraint.
Advantages
- Massive Scalability: Handles 1000-vs-1000 point matching (10⁶ candidate pairs) where existing methods exceed memory at ~300 points.
- Exponential Memory Reduction: CUR decomposition reduces second-order matrix memory from terabytes to gigabytes or megabytes.
- Sparse Tensor Generation: Fiber-CUR generates compatibility tensors with >10× sparser nonzero entries than ANN, enabling larger problems.
- Fast Convergence: PRL algorithm converges quickly on sparse tensors (often within tens of iterations).
- High Accuracy Under Deformation: Outperforms ANN-based methods under scaling, noise, and outliers (e.g., scaling case accuracy significantly higher).
- Unified Model: Works across different datasets without retraining, unlike deep learning methods that require dataset-specific training.
Applications
- Medical Image Registration: Matching anatomical landmarks in MRI/CT scans across patients or time points with high accuracy and large point sets.
- Object Recognition in Cluttered Scenes: Matching features despite rotation, scale changes, partial occlusion, or background clutter.
- 3D Reconstruction: Establishing correspondences between multiple views for structure-from-motion or stereo matching.
- Feature Tracking in Video: Following hundreds or thousands of feature points across long sequences without drift.
- Drug-Gene Association Discovery: Matching biological entities in high-dimensional interaction networks.
