A Weighted Histogram-Based Tone Mapping Algorithm for CT Images
<p>Indicator array generation: <span class="html-italic">z</span> coordinates are calculated from the pixel value of the 2D image.</p> "> Figure 2
<p>Columns in the <span class="html-italic">z</span>-direction contain the weighted histograms for corresponding pixels. Every pixel has its own local weighted histogram.</p> "> Figure 3
<p>Local histograms might be clipped to reduce noise over-amplification.</p> "> Figure 4
<p>Harbour in sunset, taken by the first author. The fine details of the deck and the buildings are hidden in the shadow.</p> "> Figure 5
<p>Tone mapped chest CT scan with eight common operators and the proposed method. Parameters are summarized in <a href="#algorithms-11-00111-t001" class="html-table">Table 1</a>; a quantitative comparison is presented in <a href="#algorithms-11-00111-t002" class="html-table">Table 2</a>.</p> "> Figure 5 Cont.
<p>Tone mapped chest CT scan with eight common operators and the proposed method. Parameters are summarized in <a href="#algorithms-11-00111-t001" class="html-table">Table 1</a>; a quantitative comparison is presented in <a href="#algorithms-11-00111-t002" class="html-table">Table 2</a>.</p> "> Figure 6
<p>Tone mapped head CT scan with eight common operators and the proposed method. Parameters are summarized in <a href="#algorithms-11-00111-t001" class="html-table">Table 1</a>; a quantitative comparison is presented in <a href="#algorithms-11-00111-t002" class="html-table">Table 2</a>.</p> "> Figure 7
<p>The effect of the <math display="inline"><semantics> <mrow> <mn>1</mn> <mo>/</mo> <msup> <mi>r</mi> <mi>a</mi> </msup> </mrow> </semantics></math> weighting function and clipping. Rows from top to bottom have <span class="html-italic">a</span> = 0.7, 1.0, 1.5, 2.0, respectively, and the clip limits in the columns from left to right are 1, 5, 10 and 20, using <math display="inline"><semantics> <mrow> <mn>1</mn> <mo>/</mo> <mi>N</mi> </mrow> </semantics></math> units where <span class="html-italic">N</span> is the number of histogram bins.</p> "> Figure 8
<p>The effect of the <math display="inline"><semantics> <mrow> <mn>1</mn> <mo>/</mo> <msup> <mi>r</mi> <mi>a</mi> </msup> </mrow> </semantics></math> weighting function and clipping. Rows from top to bottom have <span class="html-italic">a</span> = 0.7, 1.0, 1.5, 2.0, respectively, and the clip limits in the columns from left to right are 1, 5, 10 and 20, using <math display="inline"><semantics> <mrow> <mn>1</mn> <mo>/</mo> <mi>N</mi> </mrow> </semantics></math> units where <span class="html-italic">N</span> is the number of histogram bins.</p> "> Figure 9
<p>Structural similarity map for the head CT example. Brighter shades belong to higher local structural similarity (white = 1.0, black = 0.0).</p> "> Figure 9 Cont.
<p>Structural similarity map for the head CT example. Brighter shades belong to higher local structural similarity (white = 1.0, black = 0.0).</p> "> Figure 10
<p>Parameter sensitivity of the algorithm for (<b>a</b>) the chest CT, and (<b>b</b>) the head CT image.</p> "> Figure 11
<p>Calculating the histograms using a decreasing number of discretization levels. While quality slightly degrades after a while, the linear interpolation and dithering make the algorithm robust. TMQI structural similarity slowly decreases as the approximation becomes coarser.</p> "> Figure 12
<p>Calculating the histograms using spatial downsampling along each axis. Even significant downsampling does not cause very visible artefacts, which is also reflected in the TMQI score. However, local differences might appear, e.g., compare the middle region of the left lung in (<b>a</b>) and (<b>f</b>).</p> "> Figure 13
<p>Approximate execution time scales with the number of pixels and the number of discretization levels plus a constant overhead because of data pre- and post-processing.</p> ">
Abstract
:1. Introduction
1.1. Histogram Methods
1.2. Tone Mapping
2. Problem Statement
3. Theory
- Local neighborhood is important in order to determine a given pixel’s intensity.
- Neighborhood should not have a strong cut-off; the weighted contribution of the whole image should be taken into account.
- The contribution is a decreasing function of the distance.
- The contribution can be calculated using a Fast Fourier transform (FFT) [36].
- The intensity of the pixel is determined based on the local relative intensities in the source image.
- Locality and noise tolerance are equally important.
3.1. Indicator Array
- create a 3D array putting a column over every pixel in the 2D image,
- the height of the column equals the number of discrete pixel value levels,
- the cells are filled with zeros, except the ones where the z coordinate of the cell equals the pixel value in the same (x,y) position in the image.
3.2. Weighted Contribution
3.3. Relative Intensity
3.4. Contrast Limit
3.5. Algorithm Summary
- read data →,
- reduce bit depth with dithering →I,
- generate weight array,
- loop over pixel values (z),
- −
- ∗
- use superpixels, if downscaling is required,
- −
- convolve in x,y plane with W in order to get H,
- clip H peaks,
- redistribute clipped areas along the z-axis,
- determine local intensity from the local histogram and the original image
- −
- use bilinear interpolation, if superpixels were defined,
- convert the final result from float to integer with Floyd–Steinberg dithering.
4. Materials and Methods
4.1. Evaluation
4.2. Implementation
5. Discussion
5.1. Distance Metric
5.2. Locality and Clipping Limits
5.3. Edge Enhancement and Auto-Leveling
5.4. Asymptotic Complexity
5.5. Memory Consumption
6. Optimization
7. Conclusions
Supplementary Materials
Author Contributions
Funding
Conflicts of Interest
References
- Barrett, J.F.; Keat, N. Artifacts in CT: recognition and avoidance. RadioGraphics 2004, 24, 1679–1691. [Google Scholar] [CrossRef] [PubMed]
- John, A.; Huda, W.; Scalzetti, E.M.; Ogden, K.M.; Roskopf, M.L. Performance of a single lookup table (LUT) for displaying chest CT images1. Acad. Radiol. 2004, 11, 609–616. [Google Scholar] [CrossRef] [PubMed]
- Fayad, L.M.; Jin, Y.; Laine, A.F.; Berkmen, Y.M.; Pearson, G.D.; Freedman, B.; Van Heertum, R. Chest CT window settings with multiscale adaptive histogram equalization: Pilot study. Radiology 2002, 223, 845–852. [Google Scholar] [CrossRef] [PubMed]
- Chang, A.E.; Matory, Y.L.; Dwyer, A.J.; Hill, S.C.; Girton, M.E.; Steinberg, S.M.; Knop, R.H.; Frank, J.A.; Hyams, D.; Doppman, J.L. Magnetic resonance imaging versus computed tomography in the evaluation of soft tissue tumors of the extremities. Ann. Surg. 1987, 205, 340–348. [Google Scholar] [CrossRef] [PubMed]
- Seeram, E. Computed Tomography-E-Book: Physical Principles, Clinical Applications, and Quality Control; Elsevier Health Sciences: St. Louis, Missouri, USA, 2015. [Google Scholar]
- Lehr, J.L.; Capek, P. Histogram equalization of CT images. Radiology 1985, 154, 163–169. [Google Scholar] [CrossRef] [PubMed]
- Zuiderveld, K. Graphics Gems IV; Chapter Contrast Limited Adaptive Histogram Equalization; Academic Press Professional, Inc.: San Diego, CA, USA, 1994; pp. 474–485. [Google Scholar]
- Cohen-Duwek, H.; Spitzer, H.; Weitzen, R.; Apter, S. A biologically-based algorithm for companding computerized tomography (CT) images. Comput. Biol. Med. 2011, 41, 367–379. [Google Scholar] [CrossRef] [PubMed]
- Acharya, T.; Ray, A.K. Image Processing: Principles and Applications; John Wiley & Sons: Hoboken, NJ, USA, 2005. [Google Scholar]
- Nikvand, N.; Yeganeh, H.; Wang, Z. Adaptive windowing for optimal visualization of medical images based on normalized information distance. In Proceedings of the 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Florence, Italy, 4–9 May 2014. [Google Scholar] [CrossRef]
- Pizer, S.M.; Amburn, E.P.; Austin, J.D.; Cromartie, R.; Geselowitz, A.; Greer, T.; ter Haar Romeny, B.; Zimmerman, J.B.; Zuiderveld, K. Adaptive histogram equalization and its variations. Comput. Vis. Gr. Image Process. 1987, 39, 355–368. [Google Scholar] [CrossRef]
- Kim, Y.T. Contrast enhancement using brightness preserving bi-histogram equalization. IEEE Trans. Consum. Electron. 1997, 43, 1–8. [Google Scholar] [CrossRef]
- Nikolova, M.; Wen, Y.W.; Chan, R. Exact Histogram Specification for Digital Images Using a Variational Approach. J. Math. Imaging Vis. 2012, 46, 309–325. [Google Scholar] [CrossRef] [Green Version]
- Stark, J. Adaptive image contrast enhancement using generalizations of histogram equalization. IEEE Trans. Image Process. 2000, 9, 889–896. [Google Scholar] [CrossRef] [PubMed] [Green Version]
- Pattanaik, S.N.; Ferwerda, J.A.; Fairchild, M.D.; Greenberg, D.P. A multiscale model of adaptation and spatial vision for realistic image display. In Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques—SIGGRAPH ’98, Orlando, FL, USA, 19–24 July 1998; ACM Press: New York, NY, USA, 1998. [Google Scholar]
- Farbman, Z.; Fattal, R.; Lischinski, D.; Szeliski, R. Edge-preserving decompositions for multi-scale tone and detail manipulation. In ACM SIGGRAPH 2008 Papers on—SIGGRAPH ’08; ACM Press: New York, NY, USA, 2008. [Google Scholar]
- Zhang, Z.; Su, Z. Tone mapping via edge-preserving total variation model. In Proceedings of the 2012 5th International Congress on Image and Signal Processing, Chongqing, China, 16–18 October 2012. [Google Scholar] [CrossRef]
- Tan, L.; Liu, X.; Xue, K. A Retinex-Based Local Tone Mapping Algorithm Using L 0 Smoothing Filter. In Communications in Computer and Information Science; Springer: Berlin, Germany, 2014; pp. 40–47. [Google Scholar]
- Durand, F.; Dorsey, J. Fast bilateral filtering for the display of high-dynamic-range images. ACM Trans. Gr. 2002, 21. [Google Scholar] [CrossRef] [Green Version]
- Reinhard, E.; Stark, M.; Shirley, P.; Ferwerda, J. Photographic tone reproduction for digital images. In Proceedings of the 29th Annual Conference on Computer Graphics and Interactive Techniques—SIGGRAPH ’02, San Antonio, TX, USA, 21–26 July 2002; ACM Press: New York, NY, USA, 2002. [Google Scholar]
- Fattal, R.; Lischinski, D.; Werman, M. Gradient domain high dynamic range compression. In Proceedings of the 29th Annual Conference on Computer Graphics and Interactive Techniques—SIGGRAPH ’02, San Antonio, TX, USA, 21–26 July 2002; ACM Press: New York, NY, USA, 2002. [Google Scholar] [CrossRef]
- Drago, F.; Myszkowski, K.; Annen, T.; Chiba, N. Adaptive Logarithmic Mapping For Displaying High Contrast Scenes. Comput. Gr. Forum 2003, 22, 419–426. [Google Scholar] [CrossRef] [Green Version]
- Reinhard, E.; Devlin, K. Dynamic range reduction inspired by photoreceptor physiology. IEEE Trans. Vis. Comput. Gr. 2005, 11, 13–24. [Google Scholar] [CrossRef] [PubMed]
- Ferradans, S.; Bertalmio, M.; Provenzi, E.; Caselles, V. An Analysis of Visual Adaptation and Contrast Perception for Tone Mapping. IEEE Trans. Pattern Anal. Mach. Intell. 2011, 33, 2002–2012. [Google Scholar] [CrossRef] [PubMed] [Green Version]
- Mantiuk, R.; Daly, S.; Kerofsky, L. Display adaptive tone mapping. In ACM SIGGRAPH 2008 Papers on—SIGGRAPH ’08; ACM Press: New York, NY, USA, 2008. [Google Scholar]
- Meylan, L.; Susstrunk, S. High dynamic range image rendering with a retinex-based adaptive filter. IEEE Trans. Image Process. 2006, 15, 2820–2830. [Google Scholar] [CrossRef] [PubMed] [Green Version]
- Fairchild, M.D.; Johnson, G.M. Meet iCAM: A next-generation color appearance model. In Color and Imaging Conference; Society for Imaging Science and Technology: Springfield, VA, USA, 2002; Number 1; pp. 33–38. [Google Scholar]
- Reinhard, E.; Heidrich, W.; Debevec, P.; Pattanaik, S.; Ward, G.; Myszkowski, K. High Dynamic Range Imaging; Morgan Kaufman: San Francisco, CA, USA, 2006. [Google Scholar]
- Mantiuk, R.K.; Karol, M.; Hans-Peter, S. High Dynamic Range Imaging. In Wiley Encyclopedia of Electrical and Electronics Engineering; John Wiley & Sons, Inc.: Hoboken, NJ, USA, 2015; pp. 1–42. [Google Scholar]
- Banterle, F.; Artusi, A.; Debattista, K.; Chalmers, A. Advanced High Dynamic Range Imaging: Theory and Practice, 2nd ed.; AK Peters (CRC Press): Natick, MA, USA, 2017. [Google Scholar]
- Kalender, W.A. Computed Tomography: Fundamentals, System Technology, Image Quality, Applications; Publicis: Erlangen, Germany, 2011. [Google Scholar]
- Barrow, H.; Tenenbaum, J. Recovering intrinsic scene characteristics. Comput. Vis. Syst. 1978, 2, 3–26. [Google Scholar]
- Lepor, H. Prostatic Diseases; Number p. 966, v. 2000 in Prostatic Diseases; W.B. Saunders Company: Philadelphia, PA, USA, 2000. [Google Scholar]
- Gross, B.H.; Kazerooni, E.A. Cardiopulmonary Imaging; Lippincott Williams & Wilkins: Philadelphia, PA, USA, 2004. [Google Scholar]
- Wright, F.W. Radiology of the Chest and Related Conditions; Taylor & Francis: London, UK, 2001. [Google Scholar]
- Cooley, J.W.; Tukey, J.W. An algorithm for the machine calculation of complex Fourier series. Math. Comput. 1965, 19, 297. [Google Scholar] [CrossRef]
- Blommaert, F.J.; Martens, J.B. An object-oriented model for brightness perception. Spat. Vis. 1990, 5, 15–41. [Google Scholar] [CrossRef] [PubMed]
- Mantiuk, R.; Myszkowski, K.; Seidel, H.P. A perceptual framework for contrast processing of high dynamic range images. ACM Trans. Appl. Percep. 2006, 3, 286–308. [Google Scholar] [CrossRef] [Green Version]
- Yeganeh, H.; Wang, Z. Objective Quality Assessment of Tone-Mapped Images. IEEE Trans. Image Process. 2013, 22, 657–667. [Google Scholar] [CrossRef] [PubMed]
- Van Rossum, G.; Drake, F.L. Python 3 Reference Manual; CreateSpace: Paramount, CA, USA, 2009. [Google Scholar]
- Oliphant, T. Guide to NumPy; Continuum Press: Austin, TX, USA, 2015. [Google Scholar]
- Jones, E.; Oliphant, T.; Peterson, P. SciPy: Open Source Scientific Tools for Python. 2001. Available online: https://www.scipy.org (accessed on 12 June 2018).
- Lam, S.K.; Pitrou, A.; Seibert, S. Numba. In Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC—LLVM ’15, Austin, TX, USA, 15–20 November 2015; ACM Press: New York, NY, USA, 2015. [Google Scholar]
- Van der Walt, S.; Schönberger, J.L.; Nunez-Iglesias, J.; Boulogne, F.; Warner, J.D.; Yager, N.; Gouillart, E.; Yu, T. scikit-image: Image processing in Python. PeerJ 2014, 2, e453. [Google Scholar] [CrossRef] [PubMed]
- Van Rossum, G. PEP 8—Style Guide for Python Code. 2001. Available online: https://www.python.org/dev/peps/pep-0008 (accessed on 12 June 2018).
- Rota, G.; Comida, F.; Anastasia, D. Luminance HDR. 2006–2017. Available online: chttp://qtpfsgui.sourceforge.net (accessed on 12 June 2018).
- Eaton, J.W.; Bateman, D.; Hauberg, S.; Wehbring, R. GNU Octave Version 4.2.2 Manual: A High-Level Interactive Language for Numerical Computations. 2017. Available online: https://www.gnu.org/software/octave/doc/v4.2.2 (accessed on 12 June 2018).
- Floyd, R.W.; Steinberg, L. An Adaptive Algorithm for Spatial Greyscale. Proc. Soc. Inf. Disp. 1976, 17, 75–77. [Google Scholar]
Algorithm | Chest CT | Head CT | Chest CT | Head CT | Chest CT | Head CT |
---|---|---|---|---|---|---|
TMQI | TMQI | grad.mag. | grad.mag. | Entropy | Entropy | |
Drago | 0.904 | 0.794 | 0.208 | 0.202 | 5.96 | 5.85 |
Durand | 0.899 | 0.749 | 0.212 | 0.207 | 6.12 | 6.18 |
Fattal | 0.971 | 0.836 | 0.217 | 0.202 | 6.89 | 6.15 |
Ferradans | 0.916 | 0.835 | 0.014 | 0.019 | 6.71 | 7.08 |
Mantiuk’06 | 0.918 | 0.828 | 0.226 | 0.231 | 7.38 | 7.10 |
Mantiuk’08 | 0.976 | 0.783 | 0.216 | 0.207 | 6.77 | 6.26 |
Reinhard’02 | 0.898 | 0.803 | 0.206 | 0.202 | 5.81 | 5.86 |
Reinhard’05 | 0.908 | 0.798 | 0.208 | 0.200 | 6.00 | 5.80 |
proposed | 0.957 | 0.949 | 0.226 | 0.224 | 7.03 | 6.73 |
Algorithm | Parameters | |||
---|---|---|---|---|
Durand | = 7 | = 1.5 | base contrast = 4 | |
Drago | bias = 1.0 | |||
Fattal | alpha = 0.5 | beta = 0.95 | saturation = 1 | noise = 0.002 |
Ferradans | rho = 0.4 | invAlpha = 5.5 | ||
Mantiuk’06 | scaleFactor = 0.25 | saturationFactor = 0.5 | detailFactor = 7.0 | |
Mantiuk’08 | saturation = 1 | contrast enhancement = 4.3 | ||
Reinhard’02 | key = 0.02 | phi = 1.0 | no scales used | |
Reinhard’05 | brightness = 7 | lightness adapt. = 1 | chromatic adapt. = 1 | |
proposed | exponent = 1.0 | contrast limit = 6 |
© 2018 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).
Share and Cite
Völgyes, D.; Martinsen, A.C.T.; Stray-Pedersen, A.; Waaler, D.; Pedersen, M. A Weighted Histogram-Based Tone Mapping Algorithm for CT Images. Algorithms 2018, 11, 111. https://doi.org/10.3390/a11080111
Völgyes D, Martinsen ACT, Stray-Pedersen A, Waaler D, Pedersen M. A Weighted Histogram-Based Tone Mapping Algorithm for CT Images. Algorithms. 2018; 11(8):111. https://doi.org/10.3390/a11080111
Chicago/Turabian StyleVölgyes, David, Anne Catrine Trægde Martinsen, Arne Stray-Pedersen, Dag Waaler, and Marius Pedersen. 2018. "A Weighted Histogram-Based Tone Mapping Algorithm for CT Images" Algorithms 11, no. 8: 111. https://doi.org/10.3390/a11080111
APA StyleVölgyes, D., Martinsen, A. C. T., Stray-Pedersen, A., Waaler, D., & Pedersen, M. (2018). A Weighted Histogram-Based Tone Mapping Algorithm for CT Images. Algorithms, 11(8), 111. https://doi.org/10.3390/a11080111