Fast Generation of Image’s Histogram Using Approximation Technique for Image Processing Algorithms

Full Text (PDF, 766KB), PP.25-35

Views: 0 Downloads: 0

Author(s)

ObedAppiah 1,* James Ben Hayfron-Acquah 2

1. Department of Computer Science and Informatics University of Energy and Natural Resources

2. Department of Computer Science Kwame Nkrumah University of Science and Technology

* Corresponding author.

DOI: https://doi.org/10.5815/ijigsp.2018.03.04

Received: 20 Oct. 2017 / Revised: 4 Nov. 2017 / Accepted: 17 Nov. 2017 / Published: 8 Mar. 2018

Index Terms

Histogram, Approximated Histogram, Histogram Equalization, Contrast Enhancement, Approximation, Automatic Threshold Estimation, Otsu Automatic Threshold Method

Abstract

The process of generating histogram from a given image is a common practice in the image processing domain.  Statistical information that is generated using histograms enables various algorithms to perform a lot of pre-processing task within the field of image processing and computer vision. The statistical subtasks of most algorithms are normally effectively computed when the histogram of the image is known.  Information such as mean, median, mode, variance, standard deviation, etc. can easily be computed when the histogram of a given dataset is provided.  Image brightness, entropy, contrast enhancement, threshold value estimation and image compression models or algorithms employ histogram to get the work done successfully.  The challenge with the generation of the histogram is that, as the size of the image increases, the time expected to traverse all elements in the image also increases.  This results in high computational time complexity for algorithms that employs the generation histogram as subtask.  Generally the time complexity of histogram algorithms can be estimated as O(N2) where the height of the image and its width are almost the same.  This paper proposes an approximated method for the generation of the histogram that can reduce significantly the time expected to complete a histogram generation and also produce histograms that are acceptable for further processing.  The method can theoretically reduce the computational time to a fraction of the time expected by the actual method and still generate outputs of acceptable level for algorithms such as Histogram Equalization (HE) for contrast enhancement and Otsu automatic threshold estimation.

Cite This Paper

Obed Appiah, James Ben Hayfron-Acquah," Fast Generation of Image’s Histogram Using Approximation technique for Image Processing Algorithms", International Journal of Image, Graphics and Signal Processing(IJIGSP), Vol.10, No.3, pp. 25-35, 2018. DOI: 10.5815/ijigsp.2018.03.04

Reference

[1]V. Kumar, and P. Gupta, "Importance of Statistical Measures in Digital Image Processing", International Journal of Emerging Technology and Advanced Engineering; Volume 2, Issue 8, August 2012

[2]Z. Wei, H. Lidong, W. Jun, and S Zebin, “Entropy maximisation histogram modification scheme for image enhancement”, IET Image Processing, 9(3), 226-235.

[3]Y. T. Kim, “Contrast enhancement using brightness preserving bi histogram equalization” IEEE Trans.  Consumer Electronics, vol. 43, no. ac1, pp. 1-8, Feb. 1997. 

[4]Y. Wang, Q. Chen, and B. Zhang, “Image enhancement based on equal area dualistic sub-image histogram equalization method” IEEE Trans. Consumer Electronics, vol. 45, no. 1, pp. 68-75, Feb. 1999.

[5]T. K. Kim, J. K. Paik, and B. S. Kang, “Contrast enhancement system using spatially adaptive histogram equalization with temporal filtering” IEEE Trans. Consumer Electronics, vol. 44, no. 1, pp. 82-87, Feb. 1998. 

[6]S. D. Chen, and A. R. Ramli, “Contrast enhancement using recursive mean-separate histogram equalization for scalable brightness preservation” IEEE Trans. Consumer Electronics, vol. 49, no. 4, pp. 1301-1309, Nov. 2003. 

[7]Q. Wang, and R. K. Ward, “Fast image/video contrast enhancement based on weighted threshold histogram equalization” IEEE Trans. Consumer Electronics, vol. 53, no. 2, pp. 757-764, May. 2007.

[8]H. Yoon, Y. Han, and H. Hahn, “Image contrast enhancement based sub histogram equalization technique without over-equalized noise” International conference on control, automation and system engineering, pp. 176-182, 2009. 

[9]T. L. Ji, M. K. Sundareshan, and H. Roehrig, “Adaptive image contrast enhancement based on human visual” Medical Imaging, IEEE Transactions on, 1994, 13(4): 573-586

[10]T. Arici, S. Dikbas, and Y. Altunbasak, “A histogram modification framework and its application for image contrast enhancement,” IEEE Trans. Image Process., vol. 18, no. 9, pp. 1921–1935, Sep. 2009.

[11]Y. Hongbo, and H. Xia, “Histogram modification using grey-level co-occurrence matrix for image contrast enhancement”, IET Image Processing, vol. 8, no. 12, 2014, pp. 782 - 793 

[12]M . Tiwari, B. Gupta, and M. Shrivastava, “High-speed quantile-based histogram equalisation for brightness preservation and contrast enhancement”  IET Image Processing, vol. 9, no 1, 2015, pp. 80 - 89

[13]C. Lee, C. Lee and C. Kim, “Contrast Enhancement Based on Layered Difference Representation of 2D Histograms”, IEEE Transactions on Image Processing, vol. 22, no. 12, Dec. 2013

[14]X. Wang, and L. Chen. "An effective histogram modification scheme for image contrast enhancement." Signal Processing: Image Communication 58 (2017): 187-198.

[15]S. Chaudhury, and A. Kumar Roy, "Histogram Equalization-A Simple but Efficient Technique for Image Enhancement", International Journal of Image, Graphics and Signal Processing(IJIGSP), 2013, 10, 55-62, DOI: 10.5815/ijigsp.2013.10.07

[16]V. Buzuloiu, M. Ciuc, R. M. Rangayyan, and C. Vertan, “Adaptive neighborhood histogram equalization of color images” Journal of Electron Imaging, vol. 10, no. 2, pp. 445-459, 2001.

[17]N. Otsu, “ Threshold Selection Method from Gray-Level Histogram”, IEEE Trans. Systems Man. and Cybernetics, vol 9. 1979, pp62-66.

[18]J. N Kapur, P. K. Sahoo, and A. K. Wong, “A New Method for Gray-Level Picture Thresholding Using the Entropy of the Histogram” Computer Vision, Graphics and Image Processing , 29, 1985 273-285.

[19]K. N. Zhu, G. Wang, G. Yang, and W. Dai “A Fast 2D Otsu Thresholding Algorithm Based on Improved Histogram” Pattern Recognition. China. (2009)

[20]R. Brunelli and M. Ornella, "Histograms analysis for image retrieval." Pattern Recognition 34.8 (2001): 1625-1637.

[21]K. Laaroussi, A. Saaidi, M. Masrar, and K. Satori, “ Human tracking using joint color-texture features and foreground-weighted histogram”. Multimedia Tools and Applications, 1-35. (2017)

[22]S. Mishra, and M. Panda, "A Histogram-based Classification of Image Database Using Scale Invariant Features", International Journal of Image, Graphics and Signal Processing(IJIGSP), Vol.9, No.6, pp.55-64, 2017.DOI: 10.5815/ijigsp.2017.06.07

[23]K. Shriram, P. L. K Priyandarsini, V. Subashri,  "An Efficient and Generalized Approach for Content Based Image Retrieval in MatLab", International Journal of Image, Graphics and Signal Processing(IJIGSP), 2012, 4, 42-48, DOI: 105815/ijigsp.2012.04.06

[24]S. Basavaraj Anami, S. Suvarna Nandyal, A. Govardhan, "Colour and Edge Histogram Based Medical Plant's Image Retrieval", International Journal of Image, Graphics and Signal Processing (IJIGSP),  2012, 8, 24-35

[25][25] G. J. dos Santos, D. H. Linares, and A. J. Ramirez-Pastor. "Histogram-based methodology for the determination of the critical point in condensation-evaporation systems." J. Stat. Mech (2017): 073211. Journal of Statistical Mechanics Theory and Experiment 2017(7):073211 · July 2017

[26]O. Appiah, M.  Asante, J. B. Hayfron-Acquah, "Adaptive Approximated Median Filtering Algorithm For Impulse Noise Reduction", Asian Journal of Mathematics and Computer  Research,  12(2): 134-144, 2016 ISSN: 2395-4205 (P), ISSN: 2395-4213

[27]O. Appiah, J. B. Hayfron-Acquah, "A Robust Median-based Background Updating Algorithm", International Journal of Image, Graphics and Signal Processing(IJIGSP), Vol.9, No.2, pp.1-8, 2017.DOI: 10.5815/ijigsp.2017.02.01

[28]P. B. Gibbons, Y. Matias and V. Poosala, “Fast Incremental Maintenance of Approximate Histograms” Bell Laboratories, 600 Mountain Avenue, Murray Hill NJ 07974 fgibbons,matias,poosalag@research.bell-labs.com http://theory.stanford.edu/~matias/papers/vldb97.pdf

[29]R. Lesser, Jasmina Pavlin, & Edmund Durfee “Approximate Processing in Real-Time Problem Solving Victor”, AI Magazine Volume 9 Number I (1988) (AAAI) Spring 1988

[30]S. Hamid Nawab, Alan V. Oppenheim, Anantha P. Chandrakasan, Joseph M. Winograd, Jeffrey T. Ludwig: , “Approximate Signal Processing”, VLSI Signal Processing 15(1-2): 177-200 (1997) 

[31]V. Katkovnik, K. Egiazarian, and J. Astola “Local Approximation Techniques in Signal and Image Processing “, SPIE Press, Monograph Vol. PM157, September 2006. Hardcover, 576 pages, ISBN 0-8194-6092-3

[32]A. V. Sergeev and O. A. Titova “An Approximation-Based Approach to Computing Image Moment Invariants”  Pattern Recognition and Image Analysis, Vol 17, No. 2 2007