Improved Integral Histogram Algorithm for Big Sized Images in CUDA Environment

Chang Won Lee, Tae-Young Choe
Department of Computer Engineering, Kumoh national Institute of Technology, 61 Daehak-ro, Gumi, Gyeongbuk 730-701, Korea
Contemporary Engineering Sciences, Vol. 7, no. 24, 1415-1423, 2014


   title={Improved Integral Histogram Algorithm for Big Sized Images in CUDA Environment},

   author={Lee, Chang Won and Choe, Tae-Young},



Download Download (PDF)   View View   Source Source   



Although integral histogram enables histogram computation of a sub-area within constant time, construction of the integral histogram requires O(nm) steps for n x m sized image. Such construction time can be reduced using parallel prefix sum algorithm. Mark Harris proposed an efficient parallel prefix sum and implemented it using CUDA GPGPU. Mark Harris’ algorithm has two problems: leakage of shared memory and inefficiency against big sized images. In this paper, we propose a parallel prefix sum algorithm that prevents the leakage and deals big sized images efficiently. Our proposed algorithm corrects the memory leakage using exact indexing against bank conflicts and eliminates inefficient global memory access by allocating multiple pixels to each thread. As the result, average execution time of the proposed algorithm ranges 95.6% ~ 101.9% compared to that of Harris’ algorithm.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: