# A Weighted Histogram-Based Tone Mapping Algorithm for CT Images
## 6 Optimization  
There are two easy ways to optimize performance. First, the number of shades can be effectively reduced. Locally, the only factor taken into account for a single pixel is the weighted number of pixels which have lower or higher values than the current given pixel. The number of shades could be reduced significantly without a noticeable difference in the output, if the values are binned with error diffusion, also known as dithering. When the local histograms are ready, the final intensities should be calculated using linear interpolation between the discretization levels. Usual histogram processing methods are not sensitive to a large amount of gray levels, and this dithered downsampling of the histogram has not been used before, to the best of our knowledge. Dithering is also used after the tone mapping in order to decorrelate the discretization error. Both dithering steps use the Floyd-Steinberg algorithm [48].  
Another optimization possibility is to downsample the image during the histogram calculation, and perform the tone mapping using the downsampled histogram. Technically, this means a histogram column gets a contribution from several image pixels. No pixel data is lost during this downsampling, but the spatial resolution of the histogram array is decreased. This interpolation technique is mentioned in [11]. These histograms can be bilinearly interpolated for any interior point when it is required for the tone mapping.  
Both spatial downsampling and dithering build on the fact that important features in the images usually have a larger area than a few pixels, and the local histograms do not change too fast; therefore, the 3D histogram can be approximated well with one which has reduced resolution along all axes. As long as these assumptions are valid, the tone mapping can approximately linearly speed up with downsampling in terms of the number of pixels and/or shades. Memory consumption scales down in a similar manner. The effect of the techniques can be seen in Figures 11 and 12 for dithering and downscaling, respectively. Note that the downscaling is meant for each axis. For instance, a 64\(\times\) downsample means only eight samples along each axis, and 64 samples in total for a CT image with 512 \(\times\) 512 pixels.  
In both cases, the linear interpolation makes the approximation robust, which to a certain extent can compensate for the downsampling error, both in spatial and in color space. In exchange for precision loss, the computation time could be greatly reduced, as is shown in Figure 13. The execution time (\(t\)) is approximately linear in the number of pixels and in the discretizaton levels (\(D\)), not counting a small constant overhead (\(O\)). The number of pixels is inversely proportional to the square of the downscaling factor(\(x\)):  
\[t\approx O+c\frac{D}{x^{2}}, \tag{19}\]  
where \(c\) is a constant. The same result could be derived from Equation (18), with the \(\log n\approx\) constant approximation.  
Figure 11: 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.  
Figure 12: 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 (**a**) and (**f**).