Efficient feature matching for UAV images based on compact GPU data scheduling

1. Problem Statement

Feature matching is the most time-consuming step in Structure from Motion (SfM) workflows, particularly for large-scale Unmanned Aerial Vehicle (UAV) datasets. The primary bottlenecks are:

• Quadratic Complexity: The sheer number of potential image pairs and the need for Nearest Neighbor Search (NNS) in high-dimensional feature spaces.
• Sparse Connectivity: In oblique photogrammetry, image connections are often sparse. Existing GPU-based data scheduling strategies (which rely on dense connections) fail to utilize GPU computing power efficiently when connections are sparse, leading to low throughput.
• I/O and Parallelism Limitations: Current methods often prioritize Input/Output (I/O) management over maximizing GPU parallelism, resulting in scenarios where only one image is matched against others in GPU memory at a time.
• Outlier Removal: The use of binary hashing codes for similarity scoring increases false matches, making subsequent outlier removal (e.g., RANSAC) computationally expensive.

2. Methodology

The authors propose a Matrix Band Reduction (MBR) based GPU data scheduling algorithm integrated with Cascade Hashing. The workflow consists of three main stages:

A. View Graph Construction (Image Retrieval)

• Technique: Instead of relying on onboard POS data (which may lack precision or adaptability), the system uses visual similarity.
• Implementation:
  • Descriptors: SIFT features are extracted and aggregated into global descriptors using VLAD (Vector of Locally Aggregated Descriptors) with a minimal codebook.
  • Indexing: An HNSW (Hierarchical Navigable Small World) graph structure is used to index these VLAD vectors, enabling fast approximate nearest neighbor search.
  • Output: A view graph (adjacency matrix) is constructed where nodes are images and edges represent overlapping pairs.

B. Schedule Block Generation via Matrix Band Reduction (MBR)

This is the core innovation for handling sparse connections and optimizing GPU memory usage.

• Concept: The adjacency matrix of the view graph is often sparse and scattered. MBR permutes the rows and columns of this matrix to concentrate non-zero elements (image connections) near the diagonal.
• Algorithm: The Gibbs-Poole-Stockmeyer (GPS) algorithm is used to calculate the permutation order.
• Block Generation:
  • The compressed MBR matrix is divided into "schedule blocks" based on GPU memory limits.
  • Because connections are now clustered near the diagonal, each block contains a high density of valid image pairs.
  • Iterative Process: As blocks are processed, the matrix is updated (matched pairs are removed), and the process repeats until the matrix is empty.
• Benefit: This strategy ensures that when data is loaded into the GPU, it is maximally utilized for parallel matching, minimizing idle time and I/O overhead.

C. Cascade Hashing Feature Matching with Hybrid Outlier Removal

• Cascade Hashing: Converts real-valued SIFT descriptors into binary codes using a three-layer structure (Coarse-to-Fine):
  1. Lookup: Multiple hash tables map descriptors to buckets.
  2. Remapping: Coarse matches are refined with longer binary codes.
  3. Ranking: Top-K nearest neighbors are selected based on Hamming distance.
  4. Verification: Euclidean distance and ratio tests are applied to the top candidates.
• Hybrid Outlier Removal: To address the noise introduced by binary hashing:
  • Local Constraint: Uses Spatial Angular Order (SAO) based on Delaunay triangulation to filter matches locally on the CPU.
  • Global Constraint: Uses RANSAC for global geometric verification.
  • Parallelism: Feature matching runs on the GPU, while outlier removal runs on the CPU, operating asynchronously to maximize hardware utilization.

3. Key Contributions

1. MBR-Based Data Scheduling: A novel strategy that transforms sparse view graphs into compact blocks, specifically designed to adapt to the memory constraints of GPUs and the sparse nature of oblique UAV imagery.
2. GPU-CPU Parallel Pipeline: A workflow that integrates GPU-accelerated cascade hashing with CPU-based geometric constraints (SAO and RANSAC), allowing for simultaneous processing of matching and outlier removal.
3. Optimized Image Retrieval: The integration of VLAD and HNSW for efficient, scalable match pair selection that scales well to massive datasets without the overhead of traditional Bag-of-Words (BoW) methods.
4. Comprehensive Validation: Extensive testing on large-scale datasets (up to 21,654 images) comparing against state-of-the-art open-source (ColMap, AliceVision) and commercial (Metashape, Pix4D) solutions.

4. Experimental Results

The algorithm was tested on three large-scale UAV datasets (ranging from ~3,700 to ~21,600 images) using an NVIDIA RTX 4090 GPU.

• Efficiency (Speedup):
  • The proposed method achieved speedup ratios of 77.0 to 100.0 compared to traditional KD-Tree based methods (like ColMap-CPU).
  • Compared to ColMap-GPU, the proposed method was 3x faster on datasets with sparse connections (Dataset 1 & 2) due to superior data scheduling.
  • Matching speeds reached 340.8 to 362.1 pairs/second, significantly outperforming other GPU-accelerated methods like TLBDS and GraphPart.
• Accuracy:
  • Relative BA: The number of registered images and 3D points was comparable to ColMap-GPU and TLBDS, proving the matching quality is sufficient for reconstruction.
  • Absolute BA: Using Ground Control Points (GCPs), the method achieved a geo-referencing accuracy better than 2.0x (horizontal) and 3.5x (vertical) the Ground Sample Distance (GSD), ranking second only to the commercial Pix4Dmapper.
• Parameter Sensitivity:
  • Optimal Schedule Block Size was found to be 400 (for the tested hardware).
  • Optimal Ratio Test Threshold was determined to be 0.5 (lower than the standard 0.8 in SIFTGPU) due to the pre-filtering nature of cascade hashing.

5. Significance

This paper presents a significant advancement in UAV photogrammetry by solving the "sparse connection" bottleneck in GPU-accelerated feature matching.

• Scalability: It enables the processing of massive, high-resolution oblique datasets that were previously too slow for efficient SfM reconstruction.
• Hardware Efficiency: By decoupling I/O scheduling from computation logic via MBR, it maximizes the utilization of expensive GPU resources, making high-precision 3D modeling more accessible and faster.
• Practical Application: The method provides a reliable, open-source alternative to expensive commercial software for large-scale urban and infrastructure monitoring, balancing extreme speed with high geometric accuracy.