Image matching is a critical but computationally expensive component of 3D reconstruction pipelines. We propose a Cascade Hashing strategy to speed up image matching using a three-layer framework: hashing lookup, hashing remapping, and hashing ranking. Each layer employs distinct distance measures and filtering strategies designed to progressively reduce the candidate set while maintaining high matching accuracy. Our approach accelerates image matching by hundreds of times compared to brute force matching and achieves ten times or more speedup over Kd-tree based matching while retaining comparable accuracy.

Structure-from-Motion (SfM) and Multi-View Stereo (MVS) pipelines rely on establishing feature correspondences across images as a fundamental step. For large-scale 3D reconstruction involving thousands or tens of thousands of images, the pairwise matching of feature descriptors (typically SIFT) becomes the dominant computational bottleneck. With millions of features per image, brute force nearest neighbor search is intractable. Approximate nearest neighbor methods such as Kd-trees and locality-sensitive hashing (LSH) offer speedups but either degrade in high dimensions or sacrifice too much accuracy.

Approximate Nearest Neighbor (ANN) search is a well-studied problem. Kd-trees partition the feature space hierarchically but their performance degrades exponentially with dimensionality — the so-called "curse of dimensionality." Locality-Sensitive Hashing (LSH) provides sub-linear query time with theoretical guarantees but requires large numbers of hash tables to achieve high recall. Product quantization methods compress descriptors for efficient distance computation but introduce quantization error. Our Cascade Hashing differs from these by using multiple complementary hashing stages with increasing precision, achieving a better speed-accuracy tradeoff.

The first layer performs coarse filtering using binary hash codes. Each feature descriptor is projected to a compact binary code via random hyperplane hashing. Features are grouped into hash buckets, and for each query feature, only features in the same or nearby buckets (within Hamming distance threshold) are retained as candidates. This step reduces the candidate set by orders of magnitude with minimal computational cost — only bitwise operations and popcount instructions are needed. The key insight is that this coarse filter need not be highly precise; it only needs to ensure that true matches are not eliminated.

The second layer applies multiple independent hashing functions to remap the remaining candidates into shorter hash codes. By using different random projections than the first layer, this stage provides a complementary view of the feature space, filtering out candidates that passed the first layer by coincidence. The intersection of candidate sets from multiple hash functions significantly reduces noise while preserving true correspondences. This layer is designed to be less sensitive to the specific hash function choice than a single-stage approach.

The third layer performs fine-grained ranking of the remaining candidates using weighted Hamming distance with dimension-specific weights learned from data. Unlike the binary hash codes in the first two layers, this stage uses real-valued hash projections to compute more discriminative distances. The final top-k candidates are verified using the original descriptor distance (e.g., Euclidean distance on SIFT descriptors) to produce the matching result. This three-layer cascade ensures that the expensive exact distance computation is only applied to a tiny fraction of the original candidate pool.

We evaluate on large-scale 3D reconstruction benchmarks including internet photo collections with up to 15,000 images. Compared to brute force SIFT matching, Cascade Hashing achieves speedups of 100-300x with less than 1% loss in matching accuracy. Against FLANN (randomized Kd-trees), speedups of 10-30x are observed with comparable or better accuracy. On the Rome16K dataset, the total SfM pipeline time is reduced from days to hours with negligible impact on reconstruction quality. The reconstruction results (number of registered cameras and 3D points) remain nearly identical, confirming that the speed improvements do not come at the cost of geometric accuracy.

We have presented Cascade Hashing, a three-layer hashing framework for fast and accurate image matching in large-scale 3D reconstruction. By progressively filtering candidates through coarse-to-fine hashing stages, our method achieves dramatic speedups over both brute force and Kd-tree methods while maintaining the accuracy necessary for high-quality geometric reconstruction. The approach is general and can be integrated into any SfM or MVS pipeline as a drop-in replacement for the matching module. Future work includes learning hash functions end-to-end and extending the cascade framework to GPU-accelerated implementations.