這篇論文提出了一個在大量影像中辨識影像的方法，我們使用局部不變性特徵點和二次雜湊的技巧讓影像辨識的時間不會因為影像的增加讓影像辨識的時間複雜度也隨著增加。
尺寸不變性特徵點在數位版權管理中的浮水印及影像辨識的領域中已經是被廣泛使用的方法。尺寸不變性特徵點轉換法是用來擷取影像中的特徵點，用此方法索取出的特徵點用於不同影像之間的辨識具有相當的可靠性；用此方法取出的特徵點不會受尺寸縮放，旋轉，影像轉檔等變化等影響，然而在大量的影像中辨識影像將是一個重要的挑戰，影像的特徵點會因為影像數量的增加而呈線性成長，因此影像辨識的時間也會線性增加。
我們提出一個方法，利用二元化精簡的表示尺寸不變性特徵。二元化的尺寸不變性特徵可以維持很高的匹配準確率；此外，為了能降低比對特徵點的時間複雜度，我們使用完美雜湊法的特性去建立一組外部雜湊表，然後用一個規則去決定每個影像的特徵點是位於哪個外部雜湊表。實驗數據顯示我們提出的方法在影像辨識的應用中，可以有效率的將影像辨識的時間維持在一個常數時間，不會受到影像資料量的擴充所影響。

This paper presents a method for the image recognition in a large database. The local invariant features and two-tier hashing are used so that the time complexity of image matching is not affected by the size of the image database.
The local invariant features have been widely used in the Digital Right Management (DRM) applications and in the image recognition applications. Among all the local invariant features, the Scale Invariant Feature Transform (SIFT) is one of the most adopted method. The feature keypoints extracted by the SIFT are invariant to image scaling, rotation, translation, scaling, etc. However, the large number of images poses a scalability problem in the matching stage as the number of images to be matched increases.
We propose a method to simplify the PCA-SIFT descriptor via binarization. The binarized PCA-SIFT keypoint descriptors still keep very high distinctiveness for the image matching process. Furthermore, the binarized PCA-SIFT keypoint descriptors can be indexed by our proposed two-tier hashing method very efficiently. Moreover, to reduce the time complexity of matching keypoint descriptors, minimal perfect hashing is applied to build a number of external hash tables. Through computation we can determine which external hash table is hit by the distinct keypoint descriptor without searching. The experiment result suggests that the proposed method can effectively keep the time complexity to O(1) irrespective to the number of images in the matching applications.

[1] D. G. Lowe, Object recognition from local scale-invariant features. Proceedings of International Conference on Computer Vision, pages. 1150–1157, 1999.
[2] D. G. Lowe, Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, pages.91-110, 2004.
[3] Y. Ke and R. Sukthankar, PCA-SIFT: A More Distinctive Representation for Local Image Descriptors. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages. 511-517, 2004.
[4] Y. Rui, T.S. Huang, and S. Chang, Image Retrieval: Current Techniques, Promising Directions and Open Issues, Visual Comm. and Image Representation, vol. 10, no. 4, pages. 39-62, 1999.
[5] R. C. Veltkamp and M. Tanase, Content-Based Image Retrieval Systems: A Survey. Technical Report UU-CS-2000-34, Dept. of Computing Science, Utrecht University, 2000.
[6] Ritendra Datta , Jia Li , James Z. Wang, Content-based image retrieval: approaches and trends of the new age. Proceedings of the 7th ACM SIGMM international workshop on Multimedia information retrieval, pages. 253-262, 2005.
[7] A. E. Abdel-Hakim and A. A. Farag, CSIFT: A SIFT descriptor with color invariant characteristics. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages. 1978–1983, 2006.
[8] J.M. Geusebroek, R. van den Boomgaard, A.W.M. Smeulders, and H. Geerts. “Color Invariance. IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 23, no. 12, pages. 1338-1350, 2001.
[9] Fox, Heath, Chen, and Daoud, Practical minimal perfect hash functions for large databases. Communications of the ACM, January 1992
[10] I.T. Jollife, Principal Component Analysis. New York: Springer-Verlag, 1986.
[11] V Gaede and O Gunther. Multidimensional Access Methods. ACM Computing Surveys, vol. 30, no. 2, pages. 123-169, 1998.
[12] Jon Louis Bentley, Multidimensional binary search trees used for associative searching. Communications of the ACM, vol.18 no. 9, pages.509-517, 1975.
[13] Piotr Indyk and Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality. Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages. 604-613, 1998.
[14] Alex Andoni’s LSH page, http://web.mit.edu/andoni/www/LSH/index.html
[15] Yan Ke, Rahul Sukthankar, and Larry Huston, An efficient parts-based near-duplicate and sub-image retrieval system. Proceedings of the 12th annual ACM international conference on Multimedia, pages. 869-876 , 2004.
[16] A. Gionis, P. Indyk, and R. Motwani, Similarity search in high dimensions via hashing. Proceedings of International Conference on Very Large Databases, pages. 518-529, 1999.
[17] H. Y. Lee, H. Kim, and H.K. Lee, Robust image watermarking using local invariant features. Optical Engineering, v.45 n.3, 037002, 2006.
[18] Bob Jenkins, Minimal perfect hashing.
http://burtleburtle.net/bob/hash/perfect.html
[19] Tsung-Da Ho, A Scalable Indexing Method for Local Invariant Features, Master Thesis, Department of Computer Science and Information Engineering, National Taiwan University of Science and Technology, June 2008.