在影像處理中角點偵測是非常重要的一環，幾乎所有的應用都會用到，可以說角點偵測為影像辨識的根本之一。隨著行動裝置的普及，影像辨識也開始廣泛的應用到行動裝置上，然而礙於行動裝置硬體資源的缺乏和限制，要讓角點偵測可以在這些裝置上達到即時的處理是件很困難的一件工作。為了強化它的計算速度，我們使用了行動裝置上的GPU平行運算來加速FAST角點偵測演算法。根據實驗結果，透過GPU加速的FAST比一般版本快上了22.36倍，而相較於SURF演算法的角點偵測，更快上了448.5倍。

Corner detection is an extremely important technique in image recognition, which is widely employed in various applications for image recognition. With the widespread use of mobile devices, image recognition techniques are frequently applied in such devices. However, the hardware resource of smartphones are lacked and restricted, it is a difficult task to apply the techniques of corner detection smoothly in these devices. To enhance the computational speed, the FAST corner detection algorithm is implemented with parallel computing of GPU in mobile devices. In the experiments, the computational speed of the FAST corner detection algorithm increases 22.36 times after using GPU parallel computing. Compared with the widely known SURF algorithm, which is computed with mobile CPU only, the proposed technique in this study is 448.5 times faster than SURF algorithm.

目錄
第一章	緒論	1
1.1	研究背景	1
1.2	研究動機與目的	2
第二章	基礎理論與背景知識	3
2.1	GPU、GPGPU與CUDA	3
2.2	OpenGL與OpenGL ES	5
2.3	GLSL (OpenGL Shading Language) 	6
2.4	OpenCV (Open Source Computer Vision Library) 	7
2.5	灰階處理（Gray scale）	9
2.6	角點偵測 (Corner Detection) 	10
2.7	FAST角點偵測演算法	11
2.8	SURF (Speeded Up Robust Features) 	11
第三章	GPU於影像處理的相關研究	13
3.1	FFT and Convolution Performance on GPU	13
3.2	Image Parallel Processing Based on GPU	18
3.3	GPU-based face tracking at 500 fps	22
第四章	結合GPU於FAST的研究方法	27
第五章	實驗結果	30
5.1	實驗平台介紹	30
5.2	實驗一iPhone 3GS與iPhone 4上的執行速度比較	32
5.3	實驗二FAST GPU、FAST與SURF角點偵測比較	37
5.4	實驗三五張不同影像的角點偵測速度比較	42
5.4.1 512x512 實驗結果	44
5.4.2 1024x1024實驗結果	49
5.4.3 1536x1536 實驗結果	54
5.4.4 2048x2048 實驗結果	59
第六章	結論與未來展望	64
參考文獻	66
附錄	68

圖目錄
圖2.1 CPU與GPU架構	4
圖2.2 OPENCV架構概略圖	8
圖2.3 影像灰階處理	10
圖2.4 角點偵測範例	11
圖2.5 SURF範例圖	12
圖3.1 運用GPGPU處理的前後結果圖	14
圖3.2 256與512影像大小於CPU與GPU 卷積之效能比較	16
圖3.3 不同大小核的FFT與卷積之效能比較	16
圖3.4 多次的FFT與卷積之效能比較	17
圖3.5 SOBEL卷積用的矩陣	19
圖3.6 同態濾波的處理程序	19
圖3.7 於CPU與GPU做SOBEL邊緣偵測之效能比較	20
圖3.8 GPU SOBEL邊緣偵測處理之前後結果圖	20
圖3.9 GPU同態濾波處理之前後結果圖	21
圖3.10 臉部辨識系統處理程序圖	23
圖3.11 左右移動的臉部辨識位置的追蹤結果圖	25
圖3.12 大小變化的臉部辨識位置追蹤結果圖	26
圖4.1 FAST 角點偵測的計算方式	28
圖4.2 FAST 角點偵測的處理流程	29
圖5.1 開發與測試環境	31
圖5.2 測試影像LENA	33
圖5.3 512X512 IPHONE 3GS實驗擷圖	34
圖5.4 512X512 IPHONE 4實驗擷圖	34
圖5.5 10242X1024 IPHONE 3GS實驗擷圖	35
圖5.6 10242X1024 IPHONE 4實驗擷圖	35
圖5.7 1536X1536 IPHONE 3GS實驗擷圖	35
圖5.8 1536X1536 IPHONE 4實驗擷圖	35
圖5.9 2048X2048 IPHONE 3GS實驗擷圖	36
圖5.10 2048X2048 IPHONE 4實驗擷圖	36
圖5.11 IPHONE 4 512X512 FAST GPU實驗結果擷圖	38
圖5.12 IPHONE 4 512X512 FAST CPU實驗結果擷圖	38
圖5.13 IPHONE 4 512X512 SURF實驗結果擷圖	38
圖5.14 IPHONE 4 1024X1024 FAST GPU實驗結果擷圖	39
圖5.15 IPHONE 4 1024X1024 FAST CPU實驗結果擷圖	39
圖5.16 IPHONE 4 1024X1024 SURF實驗結果擷圖	39
圖5.17 IPHONE 4 1536X1536 FAST GPU實驗結果擷圖	40
圖5.18 IPHONE 4 1536X1536 FAST CPU實驗結果擷圖	40
圖5.19 IPHONE 4 1536X1536 SURF實驗結果擷圖	40
圖5.20 IPHONE 4 2048X2048 FAST GPU實驗結果擷圖	41
圖5.21 IPHONE 4 2048X2048 FAST CPU實驗結果擷圖	41
圖5.22 IPHONE 4 2048X2048 SURF實驗結果擷圖	41
圖5.23 實驗三所使用的五張圖片	43
圖5.24 圖片(A) 512X512 FAST GPU實驗結果擷圖	44
圖5.25 圖片(A) 512X512 FAST CPU實驗結果擷圖	44
圖5.26 圖片(A) 512X512 SURF實驗結果擷圖	44
圖5.27 圖片(B) 512X512 FAST GPU實驗結果擷圖	45
圖5.28 圖片(B) 512X512 FAST CPU實驗結果擷圖	45
圖5.29 圖片(B) 512X512 SURF實驗結果擷圖	45
圖5.30 圖片(C) 512X512 FAST GPU實驗結果擷圖	46
圖5.31 圖片(C) 512X512 FAST CPU實驗結果擷圖	46
圖5.32 圖片(C) 512X512 SURF實驗結果擷圖	46
圖5.33 圖片(D) 512X512 FAST GPU實驗結果擷圖	47
圖5.34 圖片(D) 512X512 FAST CPU實驗結果擷圖	47
圖5.35 圖片(D) 512X512 SURF實驗結果擷圖	47
圖5.36 圖片(E) 512X512 FAST GPU實驗結果擷圖	48
圖5.37 圖片(E) 512X512 FAST CPU實驗結果擷圖	48
圖5.38 圖片(E) 512X512 SURF實驗結果擷圖	48
圖5.39 圖片(A) 1024X1024 FAST GPU實驗結果擷圖	49
圖5.40 圖片(A) 1024X1024 FAST CPU實驗結果擷圖	49
圖5.41 圖片(A) 1024X1024 SURF實驗結果擷圖	49
圖5.42 圖片(B) 1024X1024 FAST GPU實驗結果擷圖	50
圖5.43 圖片(B) 1024X1024 FAST CPU實驗結果擷圖	50
圖5.44 圖片(B) 1024X1024 SURF實驗結果擷圖	50
圖5.45 圖片(C) 1024X1024 FAST GPU實驗結果擷圖	51
圖5.46 圖片(C) 1024X1024 FAST CPU實驗結果擷圖	51
圖5.47 圖片(C) 1024X1024 SURF實驗結果擷圖	51
圖5.48 圖片(D) 1024X1024 FAST GPU實驗結果擷圖	52
圖5.49 圖片(D) 1024X1024 FAST CPU實驗結果擷圖	52
圖5.50 圖片(D) 1024X1024 SURF實驗結果擷圖	52
圖5.51 圖片(E) 1024X1024 FAST GPU實驗結果擷圖	53
圖5.52 圖片(E) 1024X1024 FAST CPU實驗結果擷圖	53
圖5.53 圖片(E) 1024X1024 SURF實驗結果擷圖	53
圖5.54 圖片(A) 1536X1536 FAST GPU實驗結果擷圖	54
圖5.55 圖片(A) 1536X1536 FAST CPU實驗結果擷圖	54
圖5.56 圖片(A) 1536X1536 SURF實驗結果擷圖	54
圖5.57 圖片(B) 1536X1536 FAST GPU實驗結果擷圖	55
圖5.58 圖片(B) 1536X1536 FAST CPU實驗結果擷圖	55
圖5.59 圖片(B) 1536X1536 SURF實驗結果擷圖	55
圖5.60 圖片(C) 1536X1536 FAST GPU實驗結果擷圖	56
圖5.61 圖片(C) 1536X1536 FAST CPU實驗結果擷圖	56
圖5.62 圖片(C) 1536X1536 SURF實驗結果擷圖	56
圖5.63 圖片(D) 1536X1536 FAST GPU實驗結果擷圖	57
圖5.64 圖片(D) 1536X1536 FAST CPU實驗結果擷圖	57
圖5.65 圖片(D) 1536X1536 SURF實驗結果擷圖	57
圖5.66 圖片(E) 1536X1536 FAST GPU實驗結果擷圖	58
圖5.67 圖片(E) 1536X1536 FAST CPU實驗結果擷圖	58
圖5.68 圖片(E) 1536X1536 SURF實驗結果擷圖	58
圖5.69 圖片(A) 2048X2048 FAST GPU實驗結果擷圖	59
圖5.70 圖片(A) 2048X2048 FAST CPU實驗結果擷圖	59
圖5.71 圖片(A) 2048X2048 SURF實驗結果擷圖	59
圖5.72 圖片(B) 2048X2048 FAST GPU實驗結果擷圖	60
圖5.73 圖片(B) 2048X2048 FAST CPU實驗結果擷圖	60
圖5.74 圖片(B) 2048X2048 SURF實驗結果擷圖	60
圖5.75 圖片(C) 2048X2048 FAST GPU實驗結果擷圖	61
圖5.76 圖片(C) 2048X2048 FAST CPU實驗結果擷圖	61
圖5.77 圖片(C) 2048X2048 SURF實驗結果擷圖	61
圖5.78 圖片(D) 2048X2048 FAST GPU實驗結果擷圖	62
圖5.79 圖片(D) 2048X2048 FAST CPU實驗結果擷圖	62
圖5.80 圖片(D) 2048X2048 SURF實驗結果擷圖	62
圖5.81 圖片(E) 2048X2048 FAST GPU實驗結果擷圖	63
圖5.82 圖片(E) 2048X2048 FAST C實驗結果擷圖	63
圖5.83 圖片(E) 2048X2048 SURF實驗結果擷圖	63

表目錄
表3.1 FFT與卷積的優缺點比較表	17
表3.2 於CPU與GPU做同態濾波之效能比較表	21
表3.3 臉部辨識運算時間統計表	24
表5.1 IPHONE 3GS 與 IPHONE 4 硬體規格表	33
表5.2 IPHONE 3GS 與IPHONE 4執行結果表	34
表5.3 IPHONE 4執行時間列表	37
表5.4 實驗二 512X512執行時間表	38
表5.5 實驗二 512X512執行時間表	39
表5.6 實驗二 1536X1536執行時間表	40
表5.7 實驗二 2048X2048執行時間表	41
表5.8 三種方法處理測試影像所需的平均運算時間表	42
表5.9 圖片(A) 512X512執行時間表	44
表5.10 圖片(B) 512X512執行時間表	45
表5.11 圖片(C) 512X512執行時間表	46
表5.12 圖片(D) 512X512執行時間表	47
表5.13 圖片(E) 512X512執行時間表	48
表5.14 圖片(A) 1024X1024執行時間表	49
表5.15 圖片(B) 1024X1024執行時間表	50
表5.16 圖片(C) 1024X1024執行時間表	51
表5.17 圖片(D) 1024X1024執行時間表	52
表5.18 圖片(E) 1024X1024執行時間表	53
表5.19 圖片(A) 1536X1536執行時間表	54
表5.20 圖片(B) 1536X1536執行時間表	55
表5.21 圖片(C) 1536X1536執行時間表	56
表5.22 圖片(D) 1536X1536執行時間表	57
表5.23 圖片(E) 1536X1536執行時間表	58
表5.24 圖片(A) 2048X2048執行時間表	59
表5.25 圖片(B) 2048X2048執行時間表	60
表5.26 圖片(C) 2048X2048執行時間表	61
表5.27 圖片(D) 2048X2048執行時間表	62
表5.28 圖片(E) 2048X2048執行時間表	63

參考文獻 
[1]	M. Pollefeys, R. Koch, M. Vergauwen, L. Van Gool , “Automated reconstruction of 3D scenes from sequences of images,” ISPRS Journal of Photogrammetry and Remote Sensing, vol. 55, no. 4, pp. 251-267, 2000.
[2]	D. G. Lowe, “Object recognition from local scale-invariant features,” Proceedings of the International Conference on Computer Vision, vol. 2, pp. 1150-1157, 1999.
[3]	P. F. McLauchlan and A. Jaenicke, “Image mosaicing using sequential bundle adjustment,” Image and Vision Computing, vol. 20, no. 9-10, pp. 751–759, 2002.
[4]	H. Wang and M. Brady, “Real-time corner detection algorithm for motion estimation,” Image and Vision Computing, vol. 13, no. 9, pp 695-703, 1995.
[5]	G. Takacs, V. Chandrasekhar, N. Gelfand, Y. Xiong, W.-C. Chen, T. Bismpigiannis, R. Grzeszczuk, K. Pulli and B. Girod, “Outdoors augmented reality on mobile phone using loxel-based visual feature organization,” Proceedings of the 1st ACM international conference on Multimedia information retrieval, pp. 427-434, 2008.
[6]	M. Brown and D. Lowe, “Automatic Panoramic Image Stitching using Invariant Features,” International Journal of Computer Vision, vol. 74, pp. 59-73, Aug 2007.
[7]	iPhone App Autostitch, http://www.cloudburstresearch.com/autostitch/autostitch.html. 
[8]	Shai Avidan, Ariel Shamir and Seam Carving, “Content-Aware Image Resizing, ACM Transactions on Graphics,” SIGGRAPH, vol. 26, no. 3, 2007.
[9]	Michael Rubinstein, Ariel Shamir and Shai Avidan, “Improved Seam Carving for Video Retargeting,” ACM Transactions on Graphics, vol. 27, no. 3, Aug 2008.
[10]	iPhone App Liquidscale, http://www.savoysoftware.com/liquidscale/.
[11]	CUDA, http://developer.nvidia.com/object/cuda.html.
[12]	S. Ryoo, C. I. Rodrigues, S. S. Baghsorkhi, S. S. Stone, D. B. Kirk and W. W. Hwu, “Optimization principles and application performance evaluation of a multithreaded GPU using CUDA,” PPoPP 2008, pp. 73-82, 2008.
[13]	Y. Sun, X. Sun and H. Zhang, “Research on parallel cone-beam CT image reconstruction on CUDA-Enabled GPU,” the Proceeding of IEEE International Conference on Image Processing, pp. 4501-4504, 2010.
[14]	GPU architecture. http://blog.goldenhelix.com/?p=374.
[15]	OpenCV. http://opencv.willowgarage.com/wiki/
[16]	The Glowing Python Corner Detection. http://glowingpython.blogspot.tw/2011/10/corner-detection-with-opencv.html
[17]	Momma's SURF sample. http://www.eml.ele.cst.nihon-u.ac.jp/~momma/wiki/wiki.cgi/OpenCV/OpenCV2.x/matcher_simple.html
[18]	Fialka and Prague Cadik, “FFT and Convolution Performance in Image Filtering on GPU,” Information Visualization. Tenth International Conferenc, pp. 609-614, July 2006.
[19]	Nan Zhang, Jian-li Wang and Yun-shan Chen, “Image Parallel Processing Based on GPU,” Advanced Computer Control (ICACC), 2010 2nd International Conference, pp. 367-370, Mar 2010.
[20]	Idaku Ishii, Hiroki Ichida, and Takeshi Takaki, “ GPU-based face tracking at 500 fps,” Image Processing (ICIP), 2011 18th IEEE International Conference, pp. 557-560, Sept 2011.
[21]	Edward Rosten and Tom Drummond, "Machine learning for high-speed corner detection,” Department of Engineering, Cambridge University, UK.