Report

Fast and Accurate Image Matching with Cascade Hashing for 3D Reconstruction J Cheng CVPR14 Hyunchul Yang( 양현철 ) 1. 2. 3. 4. 5. 6. Background Related work Approach Experiments Result Conclusion Background 3D Reconstruction technology is similar with image retrieval Background Feature Matching is very computational cost in 3D reconstruction Around 50% Running time Feature Extraction Feature Matching (Hashing) Track Generation 3D Reconstruction Geometric Estimation Related work KD-Tree Well known nearest neighbor search algorithm. But it not suitable for high dimensional space Related work LDAHash(Linear Discriminant Analysis) PAMI 2012 Related work LDAHash(Linear Discriminant Analysis) PAMI 2012 Related work LDAHash(Linear Discriminant Analysis) PAMI 2012 Related work LDAHash(Linear Discriminant Analysis) PAMI 2012 Px + t = 0 P is projection matrix that is designed either to solely minimize the in-class covariance of the descriptor or to jointly minimize the in-class covariance and maximize the covariance across classes t is threshold matrix so that the resulting binary strings maximize recognition rates. 3. Approach Approach • Cascade Hashing ( 3 Step ) 1. Hashing Lookup with Multiple tables 2. Hashing Remapping 3. Top k Ranking via Hashing Coarse search Approach • Cascade Hashing ( 3 Step ) 1. Hashing Lookup with Multiple tables 2. Hashing Remapping 3. Top k Ranking via Hashing Refined search Approach • Cascade Hashing ( 3 Step ) 1. Hashing Lookup with Multiple tables 2. Hashing Remapping 3. Top k Ranking via Hashing Brute search Approach 1. Hashing Lookup with Multiple tables 1st hash table L = Try Count, Number of tables m = Number of hyper-planes Approach 1. Hashing Lookup with Multiple tables 2nd hash table L = Try Count, Number of tables m = Number of hyper-planes Approach 1. Hashing Lookup with Multiple tables Lth hash table L = Try Count, Number of tables m = Number of hyper-planes Approach 1. Hashing Lookup with Multiple tables L = Number of tables m = Number of hyper-planes Ex) m=8 L=6 Coarse search Approach 2. Hashing Remapping Approach 2. Hashing Remapping n = Number of hyper-planes Approach 2. Hashing Remapping n = Number of hyper-planes 3 1 2 2 3 0 3 2 2 4 Approach 2. Hashing Remapping n = Number of hyper-planes Ex) n = 128 Refined search Approach 3. Top k Ranking via Hashing Approach 3. Top k Ranking via Hashing Brute-force search on top k bucket 4. Result Result Standard Oxford dataset with SIFT key points Result Standard Oxford dataset with SIFT key points x 10 Result Standard Oxford dataset with SIFT key points x 15 Result Standard Oxford dataset with SIFT key points x 100 Conclusion Paper proposed a Cascade Hashing method to speed Accelerated by our approach in hundreds Even achieves ten times While retaining comparable times up the image matching than brute force matching or more than Kd-tree based matching accuracy. How about apply this idea to spherical hashing? Thank you Q&A