淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-2206201215345800
中文論文名稱 於行動裝置上利用GPU平行運算實現FAST角點偵測演算法
英文論文名稱 Implementation of Parallel Computing FAST Algorithm on Mobile GPU
校院名稱 淡江大學
系所名稱(中) 電機工程學系碩士在職專班
系所名稱(英) Department of Electrical Engineering
學年度 100
學期 2
出版年 101
研究生中文姓名 吳臺宜
研究生英文姓名 Tai-Yi Wu
學號 798440094
學位類別 碩士
語文別 中文
口試日期 2012-06-21
論文頁數 68頁
口試委員 指導教授-劉寅春
共同指導教授-周建興
委員-蘇木春
委員-劉志旭
委員-蔡奇謚
中文關鍵字 GPU  GPU平行運算  FAST  SURF  角點偵測  行動裝置  FAST演算法 
英文關鍵字 GPU  FAST  SURF  Corner Detection  Mobile Device  FAST Algorithm 
學科別分類 學科別應用科學電機及電子
中文摘要 在影像處理中角點偵測是非常重要的一環,幾乎所有的應用都會用到,可以說角點偵測為影像辨識的根本之一。隨著行動裝置的普及,影像辨識也開始廣泛的應用到行動裝置上,然而礙於行動裝置硬體資源的缺乏和限制,要讓角點偵測可以在這些裝置上達到即時的處理是件很困難的一件工作。為了強化它的計算速度,我們使用了行動裝置上的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.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2014-07-19公開。
  • 同意授權瀏覽/列印電子全文服務,於2014-07-19起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信