This paper presents an efficient coarse-to-fine strategy for near duplicate image detection in a Riemannian space. At the coarse level, we use the faster but less accurate log-Euclidean Riemannian metric to search the entire database to retrieve a subset of the images that are likely to contain the near duplicates of the querying image; and at the fine level, we use the more accurate but computationally more demanding affine-invariant Riemannian metric to search the coarse level results to accurately identify near-duplicates. We present experimental results to show that the new coarse to fine strategy can be over 20 times faster than existing techniques using affine-invariant Riemannian metric without sacrificing accuracy.