臺灣博碩士論文加值系統

Retinex是一種可將影像還原成原始面貌之影像還原方法。在各種方法中，center/surround Retinex演算法是最有利於平行化，這是因為此演算法利用大的核心尺寸來實現動態範圍壓縮與色彩/亮度的呈現。此演算法對於影像強化密集計算能力非常地強大，而且時間複雜度非常地高，其時間複雜度為O(M3)。本文提出的一個名為GPURetinex的演算法，此演算法是一種藉由GPGPU/CUDA來平行化Retinex之資料平行演算法，並利用大規模的平行架構與階層式記憶體來改善效率。此外在本文中，我們詳細地討論Retinex的計算分析，包含循序的時間複雜度、平行的時間複雜度與理想的加速比。在實驗中，我們使用了GT200 GPU與CUDA 3.2。其實驗結果表示在影像解析度為4096 x 4096時，此GPURetinex與藉由OpenCV實作出最佳的單執行緒CPU版本相比較，其GPURetinex能夠獲得74倍的加速而其平行效率為71.37%。此方法也超越一個基於NPP之平行的Retinex實作。我們的實驗結果指出，使用GPGPU/CUDA能夠獲得大量的效能加速與即時的性能。

Retinex is an image restoration method that can restore the image’s original appearance. Among various approaches the center/surround Retinex algorithm is favorable for parallelization because it utilizes a convolution operation with large kernel size to achieve dynamic range compression and color/lightness rendition. Its great capability in image enhancement comes with intensive computation and has the high time complexity of O(M3). This paper presents a GPURetinex algorithm, which is a data parallel algorithm devised by parallelizing the Retinex based on GPGPU/CUDA. The GPURetinex algorithm exploits GPGPU’s massively parallel architecture and hierarchical memory to improve efficiency. In addition, a computational analysis of Retinex is discussed in detail in this paper, including serial time complexity, parallel time complexity, and ideal speedup. In our experiments, the GT200 GPU and CUDA 3.2 are employed. The experimental results show that the GPURetinex can gain 74 times speedup compared with the optimized single-threaded CPU implementation by OpenCV for the images with 4096 x 4096 resolution and the parallel efficiency is 71.37%. The proposed method also outperforms a parallel Retinex implementation based on the NPP. Our experimental results indicate that using GPGPU/CUDA can acquire great performance acceleration and gain real-time performance.

Abstract (in Chinese)......................................i
Abstract..................................................ii
Acknowledgement (in Chinese).............................iii
Contents..................................................iv
List of Tables.............................................v
List of Figures...........................................vi
Chapter 1 Introduction.....................................1
Chapter 2 Background.......................................6
2.1 Computational Model of Retinex Algorithms..............6
2.2 Parallel Processing by GPGPU’s Many-core..............11
Chapter 3 The GPURetinex Method...........................15
Chapter 4 Computational Analysis of the Parallel Retinex Algorithm.................................................31
Chapter 5 Experimental Results............................41
5.1 Enhanced Results......................................42
5.2 Speedups of Retinex Algorithms........................52
5.3 Time Proportions of each Retinex Step.................57
5.4 Speedups of each Retinex Step.........................60
5.5 Gflops Performance....................................63
5.6 K.....................................................66
5.7 Analysis and Discussion of Parallel Histogramming.....70
5.8 Discussion for one Additional Implementation..........73
Chapter 6 Conclusions.....................................75
References................................................77
Appendix A. Serial Analysis of Retinex....................84
Appendix B. Parallel Analysis of Retinex..................86
Appendix C. Execution Time of Seven Parts in the Retinex Algorithm.................................................93

[1]M. Ebner, Color constancy, John Wiley & Sons Ltd, Chichester, England, pp. 143-153, 2007.
[2]E. Land, “The Retinex,” Amer. Scient., vol. 52, no. 2, pp. 247-264, June 1964.
[3]D. J. Jobson, Z. Rahman, and G. A. Woodell, “Properties and performance of a center/surround Retinex,” IEEE Trans. on Image Processing, vol. 6, no. 3, pp. 451-462, March 1997.
[4]Z. Rahman, D. Jobson, and G. A.Woodell, “Multiscale Retinex for color image enhancement,” in Proc. IEEE Int. Conf. on Image Processing, Lausanne, Switzerland, vol. 3, pp. 1003-1006, 1996.
[5]D. J. Jobson, Z. Rahman, and G. A. Woodell, “A multiscale Retinex for bridging the gap between color images and the human observation of scenes,” IEEE Trans. on Image Processing: Special Issue on Color Processing, vol. 6, no. 7, pp. 965-976, July 1997.
[6]Z. Rahman, D. Jobson, and G. Woodell, “Retinex processing for automatic image enhancement,” J. of Electronic Imaging, vol. 13, no. 1, pp. 100-110, 2004.
[7]S. Che, M. Boyer, J. Meng, D. Tarjan, J. W. Sheaffer, and K. Skadron, “A performance study of general-purpose applications on graphics processors using CUDA,” J. of Parallel and Distributed Computing, vol. 68, no. 10, pp. 1370-1380, 2008.
[8]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,” in Proc. 13th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming, Salt Lake City, USA, pp. 73-82, February 2008.
[9] E. Land and J. McCann, “Lightness and Retinex theory,” J. of Opt. Soc. Amer., vol. 61, no. 1, pp. 1-11, January 1971.
[10]E. Land, “Recent advances in Retinex theory,” Vision Research, vol. 26, no. 1, pp. 7-21, 1986.
[11]B. K. P. Horn, “Determining lightness from an image,” Comput. Graph. Image Process., vol. 3, no. 4, pp. 277-299, 1974.
[12]D. Brainard and B. Wandell, “Analysis of the Retinex theory of color vision,” J. of Opt. Soc. Amer. A, vol. 3, no. 10, pp. 1651-1661, October 1986.
[13]A. Rizzi, C. Gatta, and D. Marini, “From Retinex to automatic color equalization issues in developing a new algorithm for unsupervised color equalization,” J. of Electronic Imaging, vol. 13, no. 1, pp. 15-28, January 2004.
[14]E. Provenzi, L. D. Carli, A. Rizzi, and D. Marini, “Mathematical definition and analysis of the Retinex algorithm,” J. of Opt. Soc. Amer. A, vol. 22, no. 12, pp. 2613-2621, 2005.
[15]J. Frankle and J. McCann, “Method and apparatus for lightness imaging,” US Patent, 4384336, May 1983.
[16]J. McCann, “Lesson learned from mondrians applied to real images and color gamuts,” in Proc. IS&T/SID 7th Color Imaging Conference, Scottsdale, USA, vol. 14, pp. 1-8, 1999.
[17] B. Funt, F. Ciurea, and J. McCann, “Retinex in matlab,” J. of Electronic Imaging, vol. 13, no. 1, pp. 48-57, January 2004.
[18] F. Ciurea and B. Funt, “Tuning Retinex parameters,” J. of Electronic Imaging, vol. 13, no. 1, pp. 58-64, January 2004.
[19]R. Sobol, “Improving the Retinex algorithm for rendering wide dynamic range photographs,” J. of Electronic Imaging, vol. 13, no. 1, pp. 65-74, January 2004.
[20]E. Land, “An alternative technique for the computation of the designator in the Retinex theory of color vision,” in Proc. National Academy of Science, USA, vol. 83, pp. 3078-3080, 1986.
[21]L. Tao and V. Asari, “Modified luminance based MSR for fast and efficient image enhancement,” in Proc. 32nd Applied Imagery Pattem Recognition Workshop, Washington, USA, pp. 174-179, 2003.
[22]K. Moreland and E. Angel, “The FFT on a GPU,” in Proc. SIGGRAPH/Eurographics Workshop on Graphics Hardware, Aire-la-Ville, Switzerland, pp. 112-119, 2003.
[23]R. Strzodka and C. Garbe, “Real-time motion estimation and visualization on graphics cards,” in Proc. IEEE Visualization Conference, Austin, USA, pp. 545-552, 2004.
[24]G. Shen, G. P. Gao, S. Li, H. Shum, and Y. Zhang, “Accelerate video decoding with generic GPU,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 15, no. 5, pp. 685-693, May 2005.
[25]“GPU4Vision,” http://www.gpu4vision.org, 2011
[26]J. Fung, S. Mann, and C. Aimone, “OpenVIDIA: Parallel GPU computer vision,” in Proc. ACM international conference on Multimedia, Hilton, Singapore, pp. 849-852, November 2005.
[27]Y. Allusse, P. Horain, A. Agarwal, and C. Saipriyadarshan, “GpuCV: An opensource gpu-accelerated framework for image processing and computer vision,” in Proc. ACM international conference on Multimedia, Vancouver, Canada, pp. 1089-1092, October 2008.
[28]P. Babenko and M. Shah, “MinGPU: A minimum GPU library for computer vision,” J. of Real-Time Image Proc., vol. 3, no. 4, pp. 255-268, December 2008.
[29]J. D. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Krger, A. E. Lefohn, and T. J. Purcell, “A survey of general-purpose computation on graphics hardware,” Computer Graphics Forum, vol. 26, no. 1, pp. 80-113, March 2007.
[30]Y. Luo and R. Duraiswami, “Canny edge detection on NVIDIA CUDA,” in Proc. IEEE Computer Society Conference on CVPR Workshops, Anchorage, USA, pp. 1-8, 2008.
[31]M. Lozano and K. Otsuka, “Real-time visual tracker by stream processing,” J. of Sign. Process. Syst., vol. 57, no. 2, pp. 674-679, 2009.
[32]M. Garland, S. L. Grand, J. Nickolls, J. Anderson, J. Hardwick, S. Morton, E. Phillips, Y. Zhang, and V. Volkov, “Parallel computing experiences with CUDA,” IEEE MICRO, vol. 28, no. 4, pp. 13-27, 2008.
[33]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.
[34]D. Castano-Diez, D. Moser, A. Schoenegger, S. Pruggnaller, and A. S. Frangakis, “Performance evaluation of image processing algorithms on the GPU,” J. of Structural Biology, vol. 164, no. 1, pp. 153-160, October 2008.
[35]Y. K. Wang and W. B. Huang, “Acceleration of the Retinex algorithm for image restoration by GPGPU/CUDA,” in Proc. IS&T/SPIE Electronic Imaging, San Francisco, USA, vol. 7872, pp. 78720E-78720E-11, January 2011.
[36]Y. K. Wang and W. B. Huang, “Acceleration of an improved Retinex algorithm,” in Proc. 7th IEEE Workshop on Embedded Computer Vision, in Conjunction with the IEEE Conference on CVPR2011, Colorado Springs, USA, pp. 72-77, June 2011.
[37]NVIDIA Performance Primitives (NPP), Version 4.0, NVIDIA Corporation, 2011.
[38]H. J. Siegel, L. Wang, J. E. So, and M. Maheswaran, “Data parallel algorithms,” Parallel and Distributed Computing Handbook, McGraw-Hill, New York, USA, pp. 466-499, 1996.
[39]M. Harris, “Optimizing parallel reduction in CUDA,” NVIDIA Developer Technology, 2007.
[40]W. Burger and M. J. Burge, Digital Image Processing: An Algorithmic Introduction using java, Springer, first ed., New York, USA, pp. 53-86, 2008.
[41]V. Podlozhnyuk, “Histogram calculation in CUDA,” NVIDIA white paper, November 2007.
[42]R. Shams and R. A. Kennedy, “Efficient histogram algorithms for NVIDIA CUDA compatible devices,” in Proc. Int. Conf. Signal Processing and Communications Systems (ICSPCS), Gold Coast, Australia, pp. 418-422, Dec. 2007.
[43]D. B. Kirk and W. W. Hwu, Programming Massively Parallel Processors: A Hands-on Approach, Elsevier, Burlington, USA, pp. 77-94, 2010.