(JBE Vol. 19, No. 3, May 2014) (Special Paper) 19 3, 2014 5 (JBE Vol. 19, No. 3, May 2014) http://dx.doi.org/10.5909/jbe.2014.19.3.316 ISSN 2287-9137 (Online) ISSN 1226-7953 (Print) OpenCL Embedded GPU a), a), a), a) Parallelization of Feature Detection and Panorama Image Generation using OpenCL and Embedded GPU Seung Heon Kang a), Seung-Jae Lee a), Man Hee Lee a), and In Kyu Park a) embedded GPU (SIFT, SURF), GPU. GPGPU(general purpose computation on GPU) embedded GPU OpenCL. GPU OpenGL Shading Language(GLSL) OpenCL., OpenCL GLSL embedded CPU 3~4., GPU. Abstract In this paper, we parallelize the popular feature detection algorithms, i.e. SIFT and SURF, and its application to fast panoramic image generation on the latest embedded GPU. Parallelized algorithms are implemented using recently developed OpenCL as the embedded GPGPU software platform. We compare the implementation efficiency and speed performance of conventional OpenGL Shading Language and OpenCL. Experimental result shows that implementation on OpenCL has comparable performance with GLSL. Compared with the performance on the embedded CPU in the same application processor, the embedded GPU runs 3~4 times faster. As an example of using feature extraction, panorama image synthesis is performed on embedded GPU by applying image matching using detected features. Keyword : Embedded GPGPU, OpenCL, OpenGL, SIFT, SURF, panorama image a) (Department of Information and Communication) Corresponding Author : (In Kyu Park) E-mail: pik@inha.ac.kr Tel: +82-32-860-9190.[10041664, Shader GPU ].. Manuscript received March 17, 2014 Revised May 2, 2014 Accepted May 8, 2014
3 : OpenCL Embedded GPU (Seung Heon Kang et al. : Parallelization of Feature Detection and Panorama Image Generation using OpenCL and Embedded GPU). embedded GPU(graphic processing unit) 3,. GPGPU(general purpose computation on GPU),. Embedded GPU GPU. Qualcomm, Imagination Technologies, ARM, NVIDIA embedded GPU ( 4~16),., GPGPU SIMD (single instruction multiple data), GPGPU [1][2][3]., (feature extraction) (feature descriptor) SIFT(scale-invariant feature transform) [4] SURF(speeded up robust features) [5] OpenCL embedded GPU. embedded CPU. OpenGL Shading Language (GLSL) [6] GPU OpenCL [7]., embedded GPU. [8]. OpenCL 3 GPU, GPU NVIDIA CUDA. OpenCL, embedded GPU OpenCL. embedded GPU OpenCL. Embedded GPU,. SIFT, SURF, embedded GPU OpenCL embedded GPU.. 2 GPGPU. 3 SIFT SURF. 4 SIFT. 5. 6.. GPGPU OpenCL CPU, GPU, DSP [7]. OpenCL embedded GPU GPGPU. GLSL GPGPU OpenGL GPGPU.. OpenCL GPGPU
(JBE Vol. 19, No. 3, May 2014) image2d_t CPU,. OpenCL. CPU. OpenCL OpenGL... Embedded GPU SIFT SURF, OpenCL OpenGL embedded GPU, GPGPU. 1. SIFT SIFT, [4]. SIFT 1. 1) RGB 2) 3) Difference of Gaussian (DoG) 4) (keypoint localization) 5) (orientation) 6) (descriptor) OpenCL. RGB. (per-pixel),. (octave). (local memory). 4. Difference of Gaussian. CPU work-item., non-maximum suppression (NMS)..,.. 1. SIFT Fig 1. Structure of SIFT algorithm
3 : OpenCL Embedded GPU (Seung Heon Kang et al. : Parallelization of Feature Detection and Panorama Image Generation using OpenCL and Embedded GPU) 1. SIFT OpenCL Table 1. OpenCL implementation structure of SIFT feature extraction algorithm Work-Item (Work-Group ) RGB2Gray 1 Per-pixel 16 16 Pyramid 1 Per-pixel using local memory 16 8 DoG 1 Per-pixel 8 8 Keypoint Localization 1 Per-pixel 16 16 Orientation Computation 1 Per-pixel 16 16 Descriptor Generation 1 Per-feature using local memory 16 1 2. SURF SURF SIFT [5]. SURF 2. 1) RGB 2) (integral image) 3) (box) Hessian determinant 4) Non-maximum suppression (NMS) 5) Harr response 6) OpenCL. RGB.,., workgroup work-item (reduction)., work-item 64 1,. work-item. GLSL 255. OpenCL image2d_t.. Hessian (determinant), 4 4 Hessian 10. 2. SURF Fig 2. Structure of SURF algorithm
(JBE Vol. 19, No. 3, May 2014), work-item. Hessian. NMS NMS. CPU GPU. work-item. GPU., OpenCL GLSL (21 2 ).. GPU GPU embedded GPU GPGPU. GLSL OpenCL, (51 23 ). OpenCL GLSL GPGPU., OpenCL. 3. GPU Embedded GPU GPGPU. GPU GPGPU, GPU embedded GPU GPGPU [1][2]. (1), (2) Loop unrolling for, (3), (4) Work-item work-group work-item. work-item work-group.,,.. SIFT (homography) (warping) [9]. 2. SURF OpenCL Table 2. OpenCL implementation structure of SURF feature extraction algorithm Work-Item (Work-Group ) RGB2Gray 1 Per-pixel 16 16 Integral Image 2 Reduction using local memory 64 1, 1 64 Hessian Determinant 10 Per-pixel 8 8, 4 16, 16 2, 16 1 NMS 8 Per-pixel 16 8, 32 4, 32 2, 16 2 Orientation Computation 1 Per-feature using local memory 16 1 Descriptor Generation 1 Per-feature using local memory 16 1
3 : OpenCL Embedded GPU (Seung Heon Kang et al. : Parallelization of Feature Detection and Panorama Image Generation using OpenCL and Embedded GPU) 3. Fig 3. Block diagram of panorama image generation 3. 1) SIFT 2) 3) RANSAC 4) (inlier)/ (outlier) 5) 3), 4) 6) Embedded GPU OpenCL. III SIFT. SIFT. work-item, 128 SIFT.. RANSAC (random sample consensus) [10],. 256, work-item.,.. embedded GPU. 3. OpenCL Table 3. OpenCL implementation structure of panorama image generation Work-Item (Work-Group ) SIFT 1 Per-feature using local memory 16 1 2 Per-feature 16 16 (RANSAC) Homography 1 Per-sample 16 1 (RANSAC) Inlier/Outlier 1 Per-sample 16 1
322 방송공학회논문지 제19권 제3호, 2014년 5월 (JBE Vol. 19, No. 3, May 2014) 전자의 Galaxy S4 LTE-A이며, 이는 Qualcomm의 Snapdragon 800 응용 프로세서를 장착하였다. Snapdragon 800 응용프로세서는 Krait공정의 쿼드코어 2.3GHz CPU와 Adreno 330 쿼드코어 450MHz GPU를 탑재하고 있다. 스 마트폰의 운영체제는 Android 4.2이고, 실험 영상의 해상 도는 1280 720이다. 스마트폰에서의 인터페이스 프로그램 을 이용하여 파일로 저장된 영상에 대한 처리와 카메라에 서의 라이브 입력 비디오를 캡처한 영상에 대한 처리를 선 택적으로 수행할 수 있다. 1. SIFT (a) (b) SIFT 실험영상 알고리즘 결과 알고리즘 그림 4(a)의 실험 영상에 대하여 OpenCL을 이용하여 구 현한 SIFT 알고리즘의 세부 단계 별 수행속도는 표 4에 제 시한 바와 같다. 본 실험 영상에 대하여 추출된 특징점의 개수는 354개이다. 피라미드 영상 생성은 지역메모리를 사 용함으로 속도 개선을 기대할 수 있으나, 각 피라미드별 화 소당 차이를 구하는 양이 많기 때문에 수행 시간이 길어질 수밖에 없다. 또한 특징점 방향계산과 특징점 특징기술자 생성에서는 특징점의 개수만큼의 병렬처리를 수행하기 때 문에 영상의 복잡도와 특징 추출 문턱치 값에 따라 이 두 단계의 수행시간은 변경될 수 있다. 다양한 실험 영상에 대 한 SIFT 특징점 추출 결과는 그림 5(a)에 추가적으로 제시 하였다. Embedded GPU 환경에서의 SIFT 알고리즘 구현 은 두 언어 모두 병렬 알고리즘의 구조가 유사하기 때문에 GLSL(301.4ms/frame)과 OpenCL(331.5ms/frame)에서 평 균적으로 대등한 성능을 보인다. 같은 알고리즘이 구현되 어있는 Android용 OpenCV에서의 수행 결과는 1227ms/ frame이다. 따라서 GPU에서의 SIFT 특징 추출 수행 속도 표 4. 그림 4의 실험 영상에 대한 OpenCL 기반 SIFT 알고리즘 단계별 수행 속도 Table 4. Step-by-step execution time of SIFT implementation on OpenCL SIFT 알고리즘 결과 그림 4. 수행시간 측정에 사용한 실험 영상과 SIFT, SURF 알고리즘 수행 결과 (c) SURF Fig 4. Test image used in execution time measurement and its SIFT, SURF results 알고리즘 세부 단계 수행시간 (ms) RGB2Gray 9.14 Pyramid 93.71 DoG 15.79 Keypoint Localization 91.54 Orientation Computation 50.32 Descriptor Generation 62.13 합계 322.63
3 : OpenCL Embedded GPU (Seung Heon Kang et al. : Parallelization of Feature Detection and Panorama Image Generation using OpenCL and Embedded GPU) CPU 3.7. 2. SURF 4(a) OpenCL SURF 5. 296. 5 NMS.,. 5 4 Hessian. 8,. SURF embedded GPU, OpenGL OpenCL 192.4ms/frame 272.1ms/frame., OpenCV CPU SURF 981.3ms/frame GPU CPU 3.6. SIFT SURF, Hessian 5. 4 OpenCL SURF Table 5. Step-by-step execution time of SURF implementation on OpenCL SURF (ms) RGB2Gray 6.25 Integral Image 57.36 Hessian Determinant 88.28 NMS 23.49 Orientation Computation 45.13 Descriptor Generation 30.12 250.63. Embedded GPU, SURF OpenCL SIFT. 3. SIFT. 5(a) SIFT. 5(b). 5(c) RANSAC. 5(d). 157, 127, SIFT 81.5ms. 6.. RANSAC 6. 5 Table 6. Execution time of panorama image generation step SIFT (ms) 270.42 ( ) 242.64 ( ) 46.98 (RANSAC) Homography 8.28 (RANSAC) Inlier/Outlier 7.29 10.32 585.93
324 방송공학회논문지 제19권 제3호, 2014년 5월 (JBE Vol. 19, No. 3, May 2014) 에서는 반복 횟수만큼 스레드가 생성됨으로 반복 횟수가 늘어나는 만큼 확률적으로 정확도가 높아질 수도 있으나 (a) (b) 그림 5. 파노라마 영상 합성 중간 결과 두 장의 입력 영상 초기 특징점 정합 결과 (c) RANSAC (d) 이에 따라 수행시간은 늘어나게 된다. 본 논문에서는 실험 적으로 RANSAC의 반복 회수를 256회로 결정하였다. 또 단계 후 최적의 특징점 네 쌍 합성된 파노라마 영상 Fig 5. Intermediate result of panorama image synthesis
강승헌 외 인 및 를 이용한 영상 특집 추출 및 파노라마 영상 생성의 병렬화 3 : OpenCL Embedded GPU (Seung Heon Kang et al. : Parallelization of Feature Detection and Panorama Image Generation using OpenCL and Embedded GPU) 325 (a) (b) 그림 6. Embedded GPU(Adreno 330)및 OpenCL을 이용한 특징점 추출 결과 (a) SIFT, (b) SURF Fig 6. Feature extraction results using OpenCL on the embedded GPU (Adreno 330). They are captured on the smartphone s screen. (a) SIFT. (b) SURF 한 정합 성능 향상을 위하여 영상 간 중첩되는 영역은 좌우 50% 일 경우로 제한하여 실험을 진행하였다. 다양한 영상 에 대한 파노라마 영상 생성 실험 결과를 그림 7에 제시하 였다.
326 방송공학회논문지 제19권 제3호, 2014년 5월 (JBE Vol. 19, No. 3, May 2014) (a) (b) (a) 세장의 입력 영상 (실내) 의 영상을 이용하여 합성된 파노라마 영상 (c) 세장의 입력 영상 (야외) 의 영상을 이용하여 합성된 파노라마 영상 그림 7. Embedded GPU(Adreno 330)및 OpenCL을 이용한 파노라마 영상 생성 결과 (d) (c) Fig 7. Result of panorama generation using OpenCL on the embedded GPU (Adreno 330)
3 : OpenCL Embedded GPU (Seung Heon Kang et al. : Parallelization of Feature Detection and Panorama Image Generation using OpenCL and Embedded GPU). embedded GPU OpenCL SIFT SURF,. embedded CPU GLSL, CPU 3.7 OpenCL GLSL. OpenCL OpenGL. embedded GPU. (References) [1] I. K. Park, N. Singhal, M. H. Lee, S. Cho, and C. Kim, Design and performance evaluation of image processing algorithms on GPUs, IEEE Trans. on Parallel and Distributed Systems, vol. 22, no. 1, pp. 91 104, January 2011. [2] N. Singhal, J. W. Yoo, H. Y. Choi, and I. K. Park, Implementation and optimization of image processing algorithms on embedded GPU, IEICE Trans. on Information and Systems, E95-D(5):1475 1484, May 2012 [3] J. Lee, S. H. Kang, M. H. Lee, S. Li, H. Kim, I. K. Park,, Real-time parallel image processing library using mobile GPU, Journal of KIISE: Computing Practices and Letters, vol. 20, no. 2, pp. 96-100, February 2014. [4] D. Lowe, Distinctive image features from scale-invariant keypoints, International Journal of Computer Vision, vol. 60, no. 2, pp. 91 110, November 2004. [5] H. Bay, A. Ess, T. Tuytelaars, and L. V. Gool, Speeded-up robust features, Computer Vision and Image Understanding, vol. 110, no. 3, pp. 346 359, June 2008. [6] The Khronos Group, OpenGL Shading Language, https://www.opengl. org/ documentation/glsl/. [7] The Khronos Group, Open Computing Language (OpenCL), http://www.khronos.org/opencl/. [8] S. H. Kang, S.-J. Lee, and I. K. Park, Parallelization and optimization of feature dtection algorithms on embedded GPU, Proc. International Workshop on Advanced Image Technology, pp. 164-167, January 2014. [9] R. I. Hartley and A. Zisserman, Multiple View Geometry in Computer Vision, Second Edition, Cambridge University Press, 2004. [10] M. A. Fischler and R. C. Bolles, Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography, Communications of the ACM, vol. 24, no. 6, pp. 381-395, June 1981. - 2012 2 : - 2012 3 ~ : - :, GPGPU - 2013 2 : - 2013 3 ~ : - :, GPGPU
(JBE Vol. 19, No. 3, May 2014) - 2006 2 : - 2007 3 ~ 2008 2 : (ETRI) - 2008 8 : - 2011 1 ~ 2011 8 : Harvard University - 2008 9 ~ : - :, 3, GPGPU - 1995 2 : - 1997 2 : - 2001 8 : - 2001 9 ~ 2004 3 : - 2007 1 ~ 2008 2 : Mitsubishi Electric Research Laboratories (MERL) - 2004 3 ~ : - : ( 3, 3, computational photography), GPGPU