圖像內容檢索（CBIR）為一種電腦視覺技術，使用圖像的內容在大型資料庫中進行檢索，如顏色、形狀、紋理等而非關鍵字、標籤或其他描述方法。許多圖像運算與電腦視覺的技術皆需要擷取圖像中的內容，大部分皆透過尺度不變特徵轉換演算法（SIFT）來達成。尺度不變特徵轉換被廣泛應用於物件辨識、圖像拼接、立體對照、描述圖像特徵等。在特定的應用如圖像內容檢索中，特徵點擷取被視為預處理程序，之後的特徵點比對便成為運算最密集的程序。圖形處理器（GPU）因其在大量資料平行運算的卓越能力收到關注，因此，本研究提出基於圖形處理器平行化的尺度不變特徵轉換演算法，藉此加速線性搜尋法與k-近鄰搜尋法。於實驗結果中，相較於傳統的最近鄰居搜尋法，本研究得到22倍的加速；而相較於傳統的k-近鄰搜尋法，得到11倍的加速。

Content-based image retrieval (CBIR) is the application of computer vision techniques to the searching for digital images from large databases using image actual contents such as colors, shapes, and textures rather than the metadata such as keywords, tags, and/or descriptions associated with the image. Many techniques of image processing and computer vision are applied to capture the image contents. Among them, the scale invariant features transform (SIFT) has been widely adopted in many applications, such as object recognition, image stitching, and stereo correspondence to extract and describe local features in images. In certain application such as CBIR, feature extraction is a preprocessing process and feature matching is the most computing-intensive process. Graphic Processing Units (GPUs) have attracted a lot of attention because of their dramatic power of parallel computing on massive data. In this thesis, we propose a GPU-based SIFT by accelerating linear search and K-Nearest Neighbor (KNN) on GPUs. The proposed approach achieves 22 times faster than the ordinary Nearest Neighbor (NN) performed on CPUs, and 11 times faster than the ordinary linear search and KNN performed on CPUs.

Bellman, R. E. (2003). Dynamic Programming. Mineola, NY: Courier Dover Publications.
Bentley, J. L. (1975). Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9), 509-517.
Bonato, V., Marques, E., & Constantinides, G. A. (2008). A parallel hardware architecture for scale and rotation invariant feature detection. IEEE Transactions on Circuits and Systems for Video Technology, 18(12), 1703-1712.
Bosch, A., Zisserman, A., & Muñoz, X. (2008). Scene classification using a hybrid generative/discriminative approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, 30(4), 712-727.
Do, T., Kijak, E., Furon, T., & Amsaleg, L. (2010, October). Deluding image recognition in SIFT-based CBIR systems. Paper presented at the Proceedings of the 2nd ACM workshop on Multimedia in forensics, security and intelligence, Firenze, Italy, 2010.
Finley, D. R. (2005). Optimized QuickSort — C Implementation (Non-Recursive). Retrieved June 18, 2013 from http://alienryderflex.com/quicksort/
Garcia, V., & Debreuve, E. (2008, June). Fast k nearest neighbor search using GPU. Paper presented at the 2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, Anchorage, Alaska, USA, 2008.
Garcia, V., Debreuve, E., Nielsen, F., & Barlaud, M. (2010, September). K-nearest neighbor search: fast GPU-based implementations and application to high-dimensional feature matching. Paper presented at the International Conference on Image Processing (ICIP), Hong Kong, 2010.
Heymann, S., Muller, K., Smolic, A., Frohlich, B., & Wiegand, T. (2007, February). Sift implementation and optimization for general-purpose gpu. Paper presented at the 15-th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision, Bory, Czech Republic, 2007.
Huang, F. C., Huang, S. Y., Ker, J. W., & Chen, Y. C. (2012). High-performance SIFT hardware acceleration for real-time image feature extraction. IEEE Transactions on Circuits and Systems for Video Technology, 22(3), 340-351.
Huo, C., Pan, C., Huo, L., & Zhou, Z. (2012). Multilevel SIFT matching for large-size VHR image registration. IEEE Geoscience and Remote Sensing Letters, 9(2), 171-175.
Jégou, H., Douze, M., & Schmid, C. (2011). Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(1), 117-128.
Kuang, Q., & Zhao, L. (2009, December). A practical GPU based kNN algorithm. Paper presented at the International Symposium on Computer Science and Computation Technology (ISCSCT), Huangshan, China, 2009.
Li, B., Kong, X., Wang, Z., & Fu, H. (2009, September). SIFT-based image retrieval combining the distance measure of global image and sub-image. Paper presented at the fifth International Conference on Intelligent Information Hiding and Multimedia Signal Procseeing, Kyoto, Japan, 2009.
Liu, C., Yuen, J., & Torralba, A. (2011). SIFT flow: dense correspondence across scenes and its applications. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(5), 978-994.
Lowe, D. G. (2004). Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 60(2), 91.
NVIDIA Corporation. (2012). CUDA: Compute Unified Device Architecture (Version 5.0) [Software]. Available from http://www.nvidia.com/object/cuda_home_new.html
NVIDIA Corporation. (2012). CUDA C Programming Guide. Retrieved July 2, 2013, from http://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html
OpenCV. (2013). OpenCV: Open Source Computer Vision (Version 2.4.5) [Software]. Available from http://opencv.org/
Sinha, U. (2010). SIFT: Scale Invariant Feature Transform. Retrieved October 5, 2012, from http://www.aishack.in/2010/05/sift-scale-invariant-feature-transform/
Sismanis, N., Pitsianis, N., & Sun, X. (2012, September). Parallel search of k-nearest neighbor with synchronous operations. Paper presented at the 2012 IEEE Conference on High Performance Extreme Computing (HPEC), Waltham, Massachusetts, USA, 2012.
Tarhini, A. (2011). Parallel k-Nearest Neighbor. Retrieved October 5, 2012, from http://alitarhini.wordpress.com/2011/02/26/parallel-k-nearest-neighbor/
Xu, W., Wu, J., Liu, X., Zhu, L., & Shi, G. (2008, December). Application of image SIFT features to the context of CBIR. Paper presented at the 2008 International Conference on Computer Science and Software Engineering, Wuhan, Hubei, China, 2008.
Zhang, C., Li, F., & Jestes, J. (2012, March). Efficient parallel kNN joins for large data in MapReduce. Paper presented at the Proceedings of the 15th International Conference on Extending Database Technology, Berlin, Germany, 2012.