Acceleration
of Histogram-Based
Contrast
Enhancement
Accelerate Histogram-Based
Contrast
Enhancement
by
via Selective Downsampling
Selective Downsampling
Gang Cao1*, Huawei Tian2, Lifang Yu3, Xianglin Huang1 and Yongbin Wang1
1

School of Computer Science, Communication University of China, Beijing, China
2

3

People’s Public Security University of China, Beijing, China

School of Information Engineering, Beijing Institute of Graphic Communication, Beijing, China
Correspondence author: gangcao@cuc.edu.cn

Abstract
In this paper, we propose a general framework to accelerate the universal histogram-based
image contrast enhancement (CE) algorithms. Both spatial and gray-level selective downsampling of digital images are adopted to decrease computational cost, while the visual
quality of enhanced images is still preserved and without apparent degradation. Mapping
function calibration is novelly proposed to reconstruct the pixel mapping on the gray levels
missed by downsampling. As two case studies, accelerations of histogram equalization (HE)
and the state-of-the-art global CE algorithm, i.e., spatial mutual information and PageRank
(SMIRANK), are presented detailedly. Both quantitative and qualitative assessment results
have verified the effectiveness of our proposed CE acceleration framework. In typical tests,
computational efficiencies of HE and SMIRANK have been speeded up by about 3.9 and
13.5 times, respectively.

Index terms
Image processing, contrast enhancement, acceleration, speed up, downsampling, histogram.

1. Introduction
Contrast enhancement (CE) of digital images refers to the operations which improve the
perceived contrast. Such contrast is typically defined as the dynamic range of pixel graylevels within global or local image regions. CE is a widely used image enhancement tool in
real applications [1]. Generally, a good CE technique is expected to have: 1) more contrast
improvement with less image distortion; 2) low computational cost.
In consideration of its importance in image processing, plenty of previous works have
1

presented image CE techniques. In terms of the mapping applied to pixel gray-levels, the
existing CE algorithms can be generally categorized as global, local and hybrid ones [2].
Global CE modifies an image via an identical pixel value mapping, such that the gray-level
histogram of the processed image resembles the desired one and becomes more spread than
that of the original image [2, 3]. Local CE improves contrast by altering pixels in terms of
local properties, and typically operates in the image transform domains, such as the discrete
cosine transform (DCT) [4] and the discrete wavelet transform (DWT) [5]. Local CE can
also be enforced by adaptively applying the global CE to local image regions [3]. Hybrid
CE, which combines the global and local CE together, can improve the unified perception
of both global and local contrasts [6].
Note that most of existing global CE techniques need to use the gray-level or transform
coefficient histogram of input images. As summarized in [3], histogram modification-based
CE received the most attention due to straightforward and intuitive implementation qualities.
One popular global CE method is histogram equalization (HE) [1], which improves contrast
by redistributing the probability density of gray-levels towards uniformity. The prominent
merit of HE lies in its high computational efficiency. However, HE might incur excessive
enhancement and unnatural artifacts on the images with high peaks in histograms. In order
to attenuate such deficiency, lots of improved HE algorithms [3, 7-11] have been proposed,
where the histogram modification framework (HMF) [3] is an influential one. HMF treats
CE as an optimization problem by minimizing a cost function which includes the penalty of
the histogram deviation from original to uniform. Gu et al. [10] proposed an optimal histogram mapping for automatic CE based on a novel reduced reference image quality metric
for contrast change. In [11], a complete HMF is presented by integrating the automatic
parameter selection via saliency preservation. T. Celik [6] proposed spatial entropy based
CE (SECE) by novelly incorporating the spatial distribution characteristics of pixels into the
design of gray-level mapping function. SECE can always slightly improve image contrast
without incurring serious image quality degradation. Recently, T. Celik [2] proposes the
state-of-the-art global image CE method, SMIRANK, by using spatial mutual information
of pixels and PageRank. Although good enhancement quality is achieved, such a algorithm
runs rather slower than most of other CE algorithms including HE, HMF, SECE and the
adaptive gamma correction with weighting distribution (AGCWD) [12]. Besides, the transform coefficient histogram has also been used in CE design [4].
Low computational complexity is an important requirement for the real applications of
CE techniques, such as those in low-power embedded imaging systems and the internet of
2

y  m' (x)

Fig. 1. The proposed CE acceleration framework. The new operations integrated into a general histogram-based CE are plotted in dotted-line boxes.

things. Moreover, existing histogram-based CE algorithms may become computationally
inefficient in enhancing the images with large spatial resolution and high dynamic range
(HDR). In such frequently encountered scenarios, both the one- and two-dimensional gray
level histograms involved calculations would become highly time-consuming. Therefore, it
is essential and significant to speed up general histogram-based CE algorithms. However,
despite some particularly designed fast CE methods [13, 14], to the best of our knowledge,
there does not exist any prior work focusing on the acceleration of general histogram-based
CE. In this work, we study such a universal problem by proposing a general acceleration
framework to improve the existing CE algorithms themselves, instead of applying parallel
computing or device-dependent computational strategies [15, 16]. Selective downsampling
in both spatial and gray-level domains is employed to decrease computational cost, while
the visual quality of enhanced images is still preserved. As case studies, the accelerations of
HE and SMIRANK are presented detailedly.
The remainder of this paper is organized as follows. Section 2 proposes the acceleration
framework for general histogram-based CE techniques. Section 3 presents the detailed case
studies on HE and SMIRANK, followed by the experimental results and discussion given in
Section 4. The conclusions are drawn in Section 5.

2. Proposed CE Acceleration Framework
As illustrated by the solid-line boxes of Fig.1, a general gray level histogram-based CE
technique typically consists of three basic steps: histogram computation, mapping function
generation and image transform. Specifically, a single global or dense local histogram(s) of
an input image is first computed. Then an elaborately designed mapping function is derived
from such statistics and the image. Lastly, the pixel gray-level mapping is globally applied
to the input image.
3

In order to accelerate such histogram-based CE processing, we propose to speed up the
histogram computation by selective spatial and gray level downsampling. The yielded lowresolution histogram would benefit the fast generation of a low-resolution mapping function,
which is merely defined in the quantized gray levels. However, such a mapping function is
improper to be directly applied to neither downsampled nor primary input images, because
the abnormal stratification artifacts are incurred and the function on missed gray levels are
undefined. As another contribution of this framework, we novelly propose to calibrate such
a low-resolution mapping function so that it reasonably covers the full gray level dynamic
range of input images.

2.1 Fast Histogram Computation via Selective Downsampling
Histogram construction is an essential and fundamental step in general histogram-based
CE methods, which can be accelerated by decreasing the computational costs of histogram
computation and histogram-involved operations in mapping function generation. As such,
the cost-effective selective spatial and gray-level downsampling is proposed to be used as
acceleration strategies, as plotted in the dotted-line boxes of Fig. 1.
In order to decrease the number of counted pixels, spatial downsampling is first applied
to the B-bit input grayscale image denoted by X(i, j), i=0, 1, …, M-1, j=0, 1, …, N-1, where
[M, N] denote the image size. Without loss of generality, the uniform downsampling with
the sampling step s is used to diminish the computational cost. The spatially downsampled
image Xs is generated as
Xs(i, j)=X(s·i, s·j)

(1)

where i=0, 1, …,  M s  -1, j=0, 1, …,  N s  -1, and  denotes rounding towards zero. If s
is limited within a proper range, gray-level histogram of the downsampled image can keep
consistent shape as that of the input. The integer, instead of fraction, datatype of s values are
adopted to decrease the additional computational cost incurred by downsampling. s can also
be larger for large size of images due to the higher correlationship between local pixels.
The gray-level histogram of Xs can be obtained as
h(k) =

 M s  1  N s  1

 
i 0

j 0

  X  i, j  

l  s
 k



  


(2)

where k=0, 1, ..., Ng-1.  is the quantization step of gray levels. Ng  2 B  is the number of
histogram bins. l   is an indicator function. h(k) would be used to yield the mapping
function, where post operations typically run on such a histogram. As such, the histogram
4

dimension, Ng, also affects the computational cost of CE algorithms. Here, we propose to
decrease the statistical precision of histograms properly by reducing the number of bins.
Such histogram coarsening can be treated as the gray-level downsampling of images.
Overall, we can see that spatial downsampling benefits CE of large size of images, and
gray-level downsampling accelerates histogram-dependent mapping function generation.

2.2 Calibration of Mapping Function
Let the low-resolution mapping function derived from h(k) be denoted by y=m(k), k=0,
1, ..., Ng-1. Mapping function calibration aims to reconstruct a proper full dynamic mapping
function y=m’(x), x=0, 1, ..., 2B-1 from y=m(k). Generally, there exist two candidate image
transform schemes which are discussed detailedly as follows.
1) As Matlab function imhisteq, y=m(k), k=0, 1, ..., Ng-1 is upsampled into y=m’(x)=
m(  x   ), x=0, 1, ..., 2B-1 by nearest neighboring interpolation. Then y=m’(x) is applied to
Xs, and the result is reversely upsampled to yield an enhanced image Y with the same size
as X. Note that in some CE algorithms, such as SMIRANK, the y=m’(x) here can not be
directly applied to X, since some kinds of gray levels in X may be missed by the spatial
downsampling and excluded from histograms. Nevertheless, annoying stratification artifacts
are easily incurred in Y due to degraded gray-level resolution, especially in the X with large
smooth regions and histogram peaks. As a result, such a transform scheme is undesirable.
2) y=m(k) is linearly completed and upsampled into y=m’(x) for covering all the gray
levels of X, and then applied to X for yielding an enhanced image Y. The stratification
artifacts can be attenuated efficiently in this scheme, which is adopted as mapping function
calibration in our proposed CE acceleration framework.
Specifically, in order to reduce additional computational burden, the simple yet efficient
one-dimensional linear interpolation is used to implement the upsampling and completing
of y=m(k). In terms of generation methods of mapping function, the completing operation
may be selectively used to estimate the gray levels missed by either spatial or gray-level
downsampling, as that enforced in the accelerated SMIRANK algorithm (see Section 3.1).

3. Case Studies on HE and SMIRANK
This section presents the case studies of our acceleration scheme on two typical CE algorithms: HE and SMIRANK. For the input B-bit grayscale image X, CE algorithms aim to
yield an enhanced image Y with higher contrast and less distortion than X. As the prior
5

works [2, 3, 6], CE of color images is realized by applying CE to luminance channel images
and preserving the chrominance components in HSV color space.

3.1 Acceleration of HE
The accelerated HE algorithm is proposed as follows,
(1) Spatially downsampling X to Xs as Eq. (1).
(2) Compute the downsampled gray-level histogram h of Xs as Eq. (2).
(3) Obtain cumulative distribution function (CDF) c from h.
(4) Calibrate c to c' with 2B items by upsampling it with linear interpolation.
(5) Perform pixel value transform Y(i, j)=[(2B-1)  c'(X(i, j))], where [  ] means converting to unsigned B-bit integers.
Comparing with the baseline HE algorithm [1], the integrated acceleration measures are
included in the steps (1), (2), (4). Specifically, in the step (1), spatial image downsampling
decreases the number of counted pixels, which can accelerate the generation of histogram.
The shorter histogram (Ng<2B) yielded in the step (2) benefits the fast calculation of CDF.
In the calibration phase, i.e., the step (4), the computationally cost-effective upsampling of
CDF is used to reconstruct a continuous mapping function covering the full dynamic range
[0, 2B-1] of X.

3.2 Acceleration of SMIRANK
The accelerated SMIRANK algorithm is proposed as follows,
(1) Compute 2D joint-spatial histogram hb(k) of the spatially downsampled image Xs as
Eqs. (1)(2). Here, b=1, 2, ..., Nb are the indexes of divided non-overlapped image blocks in
Xs, and k=0, 1, ..., Ng-1 are the bin indexes of blockwise gray level histograms.
(2) Normalize hb(k) to be hb(k)／((  M s  )(  N s  )).
(3) Compute the mutual spatial information as
Nb

I(k ,l )   hb' (k ,l )log
b 0

hb' (k ,l )
hb (k )hb (l )

(3)

where h'b(k, l) = min(hb(k), hb(l)), k, l  X={xn |  b hb ( xn )  0 , n=1, 2, ..., K}. K denotes the
number of non-zero columns within the matrix H which consists of Hb, k +1=hb(k).
(4) Calculate G=S+(1- )ovT , where S is created by normalizing each column of I.
o  R K1 is unit vector and v  R K1 is uniform vector, i.e., oT v=1 .   [0,1]
 is the adjustable

damping factor.
6

(5) The gray-level rank vector r  R K 1 is gained by solving Gr = r, where r = (1-  )
(E-  S)-1v, and E is K×K identity matrix.
(6) Map input gray-levels in X to output
yk = yk-1 +  k-1, k  (2B-1)

(4)

 is defined as
where k=2, 3, ..., K and y1=0.  k-1, k  [0,1]

k 1,k 

r(k  1)  r(k ) r(1)  r( K )

.
2
2( K  1)

(5)

(7) Complete F(xk)=yk , k =1, 2, ..., K, to F(k) , k=0, 1, ..., Ng-1, by filling the lost items
via linear interpolation. Then F is linearly upsampled to be with 2B items, i.e., F(x) , x=0,
1, ..., 2B-1. Lastly, output Y(i, j)=[(2B-1)  F(X(i, j))].
Comparing with SMIRANK [2], the main changes lie in the steps (1), (7). Specifically,
both spatial and gray-level downsampling are implemented to speed up the generation of 2D
joint-spatial histograms in the step (1). The low-dimensional blockwise histograms hb
could evidently speed up the post computations of mutual information I and gray-level rank
vector r, which correspond to the steps (3) and (5), respectively. Such two steps constitute
the main part of SMIRANK, and serve to generate an incomplete low-resolution mapping
function {F(xk)=yk | k=1, 2, …, K} in the step (6). In the calibration step (7), F is completed
and upsampled by linear interpolation to recover the full dynamic mapping function {F(x) |
x=1, 2, …, 2B-1}. Such processing refers to mapping function calibration in the acceleration
framework. Lastly, the enhanced image Y is outputted via pixel value mapping.

4. Experimental Results and Discussion
4.1 Datasets, Algorithms and Performance Measures
Test images are collected from four standard databases, i.e., TID2013 [17], CSIQ [18],
CCID2014 [10] and RGB-NIR [19]. TID2013 image dataset includes 25 reference images
and their contrast-changed versions at Levels 1~5, which respectively correspond to small
contrast decreasing/increasing, larger contrast decreasing/increasing and the largest contrast
decreasing. In CSIQ, 30 reference images are degraded at 5 consecutive levels, where the
Levels 1 and 5 signify the smallest and largest contrast degrading, respectively. CCID2014
consists of 15 representative Kodak images [20] and their 655 contrast-distorted copies.
RGB-NIR image dataset has 477 images captured in RGB and near-infrared (NIR), where
7

RGB images are used in our tests. The size of TID2013, CSIQ, CCID2014 and RGB-NIR
images are 512×384, 512×512, 768×512 and 1024×(620~768) pixels, respectively. CE
algorithms are applied to the corresponding 8-bit luminance images in HSV color space.
Our proposed fast HE (FHE) and fast SMIRANK (FSMIRANK) are compared with
naive HE [1], SMIRANK [2], HMF [3], AGCWD [12] and SECE [6]. Default parameter
settings of primary algorithms are used. Without loss of generality,  = 0.9 is set in both
SMIRANK and FSMIRANK.
Currently, the performance assessment of image CE algorithms is still a challenge task
[2, 10, 21-23]. In order to keep consistency with prior works, the state-of-art CE metrics,
QRCM (quality-aware relative contrast measure) [2] and BIQME (blind image quality
measure of enhanced images) [23] are used in all the tests. QRCM is a full-reference image
quality assessment for measuring both the contrast change and image quality degradation
between input and outputs. It yields a number within [-1, 1], where -1 and 1 denote the full
level of contrast degradation and improvement, respectively. As a no-reference CE metric,
BIQME captures five influencing factors: contrast, sharpness, brightness, colorfulness and
naturalness. A larger BIQME score signifies better visual perceptual quality.

4.2 Effectiveness Evaluation of Acceleration Strategies
Perceptual quality of enhanced images and average processing time per image are two
important criteria for evaluating CE methods. In order to evaluate the visual quality change
incurred by proposed accelerations, the QRCM difference between the images yielded by
accelerated and naive algorithms ( QRCM=QRCMfast－QRCMnaive) is computed for each
RGB-NIR image. CDF statistics of such QRCM values are plotted in Fig. 2, where (a)(c)
and (b)(d) correspond to the HE and SMIRANK groups, respectively.
We also investigate the performance varying with Ng and s. Fig. 2(a)(b) plots QRCM
statistics varying with Ng for HE and SMIRANK groups, respectively. For HE, QRCM
values of nearly all samples are above a rather small value, i.e., -0.005. Moreover, more
than 60% sample values are positive, which signifies higher QRCM gained by FHE. Overall,
visual quality of the image enhanced by FHE is comparative or even better than that of HE,
and is insensitive to Ng. Fig. 2(b) shows that QRCM values of more than 90% samples for
FSMIRANK are lower than those for SMIRANK. However, there are about 99%, 90%,
70% sample values above -0.01 (a negligible degradation) for Ng=128, 64, 32, respectively.
Such results verify that FSMIRANK is comparative or slightly worse than SMIRANK on
the visual quality of outputs.

8

1

1

Ng=256, s=1
Ng=128, s=1
Ng=64, s=1
Ng=32, s=1

0.9
0.8

0.9
0.8
0.7

0.6

0.6

Percent

Percent

0.7

Ng=256, s=1
Ng=128, s=1
Ng=64, s=1
Ng=32, s=1

0.5

0.5

0.4

0.4

0.3

0.3

0.2

0.2

0.1

0.1

0
-0.03

-0.02

-0.01

0

QRCM

0.01

0.02

0
-0.03

0.03

-0.02

-0.01

0

QRCM

(a)

0.02

0.03

0.01

0.02

0.03

(b)

1

1

0.9

0.9

0.8

0.8

0.7

0.7

0.6

0.6

Percent

Percent

0.01

0.5

0.5

0.4

0.4

0.3

0.3

0.2

0.2

0.1

0.1

0
-0.01

0

0.01

QRCM

0.02

0
-0.03

0.03

-0.02

-0.01

0

QRCM

(c)

(d)

Fig. 2. Cumulative distribution of the difference between QRCM values yielded by (a)(c) FHE and
HE; (b)(d) FSMIRANK and SMIRANK on RGB-NIR dataset under different s and Ng settings.

TABLE I
AVERAGE COMPUTATION TIME (MS) PER IMAGE ON RGB-NIR DATASET FOR FHE AND FSMIRANK
UNDER DIFFERENT s AND Ng SETTINGS.
Ng
s

256

FHE
FSMIRANK

48.6
530.2

128

64

32

1
42.4
156.0

36.4
86.3

32.7
64.9

9

64
1

4

8

16

36.4
86.3

12.6
34.5

11.7
35.3

11.0
29.7

The computational complexity decrease incurred by accelerations is tested by running
CE algorithms on a computer with Intel Core i5-5200U CPU @ 2.2 GHz and 8G RAM
under MATLAB R2013a. As shown in Table I, the average processing time for one image
decreases monotonously with Ng. Without loss of generality, Ng=64 is selected for limiting
the degradation and computational complexity.
Results on the visual quality varying with s are shown in Fig. 2(c)(d). Overall, the performances at s=1, 4, 8 are comparative, and far better than that at s=16. Table I shows that
the computing speed also decreases monotonously with s. In terms of the trade-off between
computation cost and visual quality, s=8 is selected. In conclusion, the effectiveness of our
proposed CE acceleration strategies can be verified by such baseline evaluation results.

4.3 Comparing with Other CE Methods
Objective and subjective performance assessment of the accelerated CE methods is also
enforced by comparing with other CE algorithms on extensive datasets. Table II shows the
average QRCM values for different CE algorithms on four databases. It shows that FHE is
comparative or slightly better than HE, where the increment falls within [-0.003, 0.044].
Among all methods, SMIRANK ranks first and is nearly followed by FSMIRANK, which
owns comparative or slightly lower QRCM values. The decrement falls within [-0.01, 0]

TABLE II
AVERAGE QRCM (X10 ) FOR DIFFERENT CE ALGORITHMS ON EACH DATASET. HERE, S=8, Ng=64.
LEVEL 0 MEANS UNALTERED IMAGES. THE LARGEST TWO PER ROW ARE LINED.
-2

Algorithm

HMF

AGCWD

SECE

HE

FHE

Level 0
Level 1
Level 2
TID2013
Level 3
Level 4
Level 5
Level 0
Level 1
Level 2
CSIQ
Level 3
Level 4
Level 5
CCID2014
RGB-NIR

10.1
11.5
7.7
14.1
5.5
17.1
7.6
10.5
14.2
17.5
17.8
17.8
13.0
12.9

9.1
12.3
5.6
17.8
2.7
28.8
6.3
10.5
17.0
30.0
35.0
35.0
9.8
9.4

7.5
11.8
4.0
18.8
1.8
31.2
3.1
9.3
18.1
33.0
37.7
37.7
11.9
7.8

10.7
15.8
4.6
22.1
-1.9
33.0
3.3
9.3
17.8
31.5
36.1
36.1
11.8
11.0

12.0
15.5
7.2
22.0
2.5
32.8
3.4
9.1
17.6
31.5
36.1
36.1
13.9
11.7

10

SMIRANK FSMIRANK
13.5
17.5
9.3
23.9
5.9
34.9
7.9
13.7
21.9
35.0
38.9
38.9
17.3
14.9

13.5
17.3
9.3
23.7
5.9
34.9
7.7
13.2
21.3
34.1
37.9
37.9
17.4
14.7

TABLE III
AVERAGE BIQME (X10 ) FOR DIFFERENT CE ALGORITHMS ON EACH DATASET. HERE, S=8, Ng=64.
-1

UNEN MEANS UNENHANCED IMAGES. THE LARGEST TWO PER ROW ARE LINED.

Algorithm
Level 0
Level 1
Level 2
TID2013
Level 3
Level 4
Level 5
Level 0
Level 1
Level 2
CSIQ
Level 3
Level 4
Level 5
CCID2014
RGB-NIR

UNEN HMF AGCWD SECE
59.0
56.3
62.3
51.5
63.7
41.9
60.1
55.6
51.2
42.2
38.0
38.0
50.1
54.6

63.0
61.5
64.8
58.5
65.2
50.8
62.8
60.5
57.8
49.6
45.0
45.0
57.3
60.2

Input

HMF

AGCWD

Image 1

0.21

Image 2

60.9
59.1
63.8
56.3
65.0
51.0
62.4
58.9
56.7
52.2
49.6
49.6
55.2
56.8

61.6
61.1
63.4
60.4
64.1
59.2
61.4
59.4
58.6
57.8
57.2
57.2
57.9
57.3

HE

FHE SMIRANK FSMIRANK

64.1
64.4
64.1
64.2
63.1
63.9
65.2
62.8
62.1
61.3
60.4
60.4
63.2
62.0

64.6
64.1
65.1
64.0
64.8
63.5
65.3
62.8
62.2
61.3
59.9
59.9
63.9
62.3

63.5
63.2
64.7
62.8
64.8
62.3
63.4
61.7
61.4
61.0
60.5
60.5
61.1
60.4

63.7
63.3
64.9
62.9
65.0
62.2
62.6
61.7
61.4
60.8
60.1
60.1
60.8
60.6

SECE

HE

FHE

SMIRANK

FSMIRANK

0.19

0.15

0.27

0.27

0.26

0.25

0.16

0.20

0.07

0.11

0.11

0.20

0.21

Image 3

0.14

0.19

0.13

0.24

0.24

0.22

0.22

Image 4

0.16

0.20

0.07

0.11

0.11

0.20

0.21

Fig. 3. Results for different CE methods on four example images. The corresponding QRCM value
of each image is shown below.
11

with the average of -0.004, which is rather smaller than the margins above the other CE
methods including HMF, AGCWD and SECE. Table III lists the corresponding test results
achieved by the BIQME metric. Although the measurements are prone to HE, the consistent
conclusion as that of QRCM could also be obtained. All such quantitative and objective
assessment results verify that the accelerated methods can preserve the visual enhancement
quality of naive CE methods, and generally behave better than HMF, AGCWD and SECE.
Fig. 3 shows the qualitative visual quality assessment enforced on four example images.
The images 1-2, 3, 4 are from CSIQ, BSD500 [24] and RGB-NIR databases, respectively.
From both visual observation and QRCM measurements, we can see that perceptual quality
of the enhanced images yielded by accelerated methods is preserved successfully. Except
for those inherently brought by naive CE methods, no additional unnatural artifacts would
be incurred by the corresponding accelerated methods.

4.4 Complexity Comparison
Time complexity of different CE algorithms is also tested. The average processing time
for each image of the four different datasets is shown in Table IV, which indicates that FHE
outperforms other methods remarkably. Although HE is famous for its fast processing speed,
it is still speeded up by about 3.9 times by our proposed acceleration scheme. Moreover,
SMIRANK is impressively speeded up by about 13.5 times by FSMIRAMK. Such evident
improvement should attribute to both the spatial and gray-level downsampling. FSMRANK
runs much faster than SECE and AGCWD. Comparing with HMF, FSMIRANK behaves
comparatively on TID2013 and CSIQ, but better on CCID2014 and RGB-NIR. Such results
should attribute to the benefit of our proposed methods on enhancing the relatively large
size of images, such as those from RGB-NIR and CCID 2014.
We also analyze the theoretical time complexity of CE algorithms in enhancing a M×N
B-bit grayscale image. The analysis results are shown in Table V. For HE, computing the
TABLE IV
AVERAGE COMPUTATION TIME (MS) PER IMAGE FOR DIFFERENT CE ALGORITHMS ON EACH
DATASET. HERE, S=8, Ng=64. THE FASTEST TWO PER ROW ARE LINED.

Algorithm

HMF

AGCWD

SECE

HE

FHE

TID2013
CSIQ
CCID2014
RGB-NIR

18.0
23.9
34.8
56.9

37.2
50.7
68.8
118.6

54.3
60.8
75.7
116.4

14.7
19.6
29.1
47.4

4.0
5.3
6.9
11.7

12

SMIRANK FSMIRANK
314.0
283.0
307.8
519.4

22.6
21.0
25.5
35.3

TABLE V
THEORETICAL TIME COMPLEXITY OF NAIVE AND ACCELERATED CE ALGORITHMS.

Algorithm

Time Complexity

HE
FHE
SMIRANK
FSMIRANK

O(2MN+2B)
O((1/s2+1)MN +Ng)
O(2MN +K22B+K3)
O((1/s2+1)MN+KNg2+ (KNg/2B) 3)

histogram requires time O(MN). Generating the mapping function requires time O(2B), and
finally applying pixel-wise transform to yield the enhanced image requires time O(MN). As
a result, the total time complexity of HE is O(2MN+2B) [3]. For FHE, such corresponding
three items require times O(MN/s2), O(Ng) and O(MN), respectively. The mapping function
calibration costs time O(1). So the total time complexity of FHE is O((1/s2+1)MN +Ng).
For SMIRANK, the whole computational cost mainly comes from the computations of
blockwise histograms, mutual information matrix, the rank vector and pixel value mapping.
Such four items requires times O(MN), O(K22B), O(K3) and O(MN), respectively. Here, K
denotes the number of gray levels existing in the primary input image. Therefore, the total
time complexity for SMIRANK is O(2MN+K22B+K3). Correspondingly, the total time complexity of FSMIRANK is O((1/s2+1)MN+KNg2+(KNg/2B)3), where the mutual information
matrix and rank vector are calculated in terms of downsampled gray levels.
We also noted that  can be set automatically based on the gradient magnitude map of
input images [2]. We also conduct related experiments and find that such automatic setting
may slightly improve the visual quality at a cost of increasing a little computational time.
Nevertheless, comparing with the prior art, the computational performance superiority of
FSMIRAMK gained by the integrated acceleration strategies is still rather evident.

5. Conclusions
In this paper, a fundamental framework is proposed to accelerate general histogram-based
image CE algorithms. Both spatial downsampling and histogram simplifying mechanisms
are investigated deeply and adapted to significantly decrease the computational complexity
of prior CE techniques. Mapping function calibration is novelly proposed to reconstruct the
transform on the gray levels missed by downsampling. The case studies on two typical CE
algorithms, i.e., HE and SMIRANK, are presented detailedly. Effectiveness of our proposed
CE acceleration scheme has been validated by the extensive experimental results on four
13

standard databases. In conclusion, our proposed CE acceleration framework can be friendly
used to remarkably improve the computational efficiency of histogram-based CE algorithms,
while perceptual quality of enhanced images can still be preserved.

Reference
[1] R. C. Gonzalez and R. E. Woods, “Digital Image Processing,” 3rd ed. Upper Saddle River, NJ,
USA: Prentice-Hall, 2006.
[2] T. Celik, “Spatial mutual information and PageRank-based contrast enhancement and qualityaware relative contrast measure,” IEEE Trans. on Image Process., vol. 25, no. 10, pp. 47194728, 2016.
[3] 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,
2009.
[4] S. Agaian, B. Silver and K. Panetta, “Transform coefficient histogram based image enhancement
algorithms using contrast entropy,” IEEE Trans. Image Process., vol. 16, no. 3, pp. 741-758,
Mar 2007.
[5] R. Fattal, “Edge-avoiding wavelets and their applications,” ACM Trans. on Graphics, vol. 28, no.
3, pp. 1-10, 2009.
[6] T. Celik, “Spatial entropy-based global and local image contrast enhancement,” IEEE Trans.

Image Process., vol. 23, no. 12, pp. 5298-5308, 2014.
[7] Y.-T. Kim, “Contrast enhancement using brightness preserving bi-histogram equalization,” IEEE

Trans Consum. Electron., vol. 43, no. 1, pp.1-8, 1997.
[8] T. Celik and T. Tjahjadi, “Automatic image equalization and contrast enhancement using gaussian mixture modeling,” IEEE Trans. on Image Process., vol. 21, no. 1, pp. 145-156, 2012
[9] O. Ghita, D. E. Ilea and P. F. Whelan, “Texture enhanced histogram equalization using TV-L1
image decomposition,” IEEE Trans. on Image Process., vol. 22, no. 8, pp. 3133-3144, 2013
[10] K. Gu, G. Zhai, W. Lin and M. Liu, “The analysis of image contrast: from quality assessment to
automatic enhancement,” IEEE Trans. Cybernetics, vol. 46, no. 1, pp. 284-297, 2016.
[11] K. Gu, G. Zhai, X. Yang, W. Zhang and C. W. Chen, “Automatic contrast enhancement technology with saliency preservation,” IEEE Trans. Circuits and Systems for Video Technology, vol.
25, no. 9, pp. 1480-1494, 2015.
[12] S.-C. Huang, F.-C. Cheng and Y.-S. Chiu, “Efficient contrast enhancement using adaptive
gamma correction with weighting distribution”, IEEE Trans. Image Process., vol. 22, no. 3, pp.
1032-1041, 2013.
[13] Z. Yu and C. Bajaj, “A fast and adaptive method for image contrast enhancement,” Proc. Intl.

Conf. on Image Process., pp. 1001-1004, 2004.

14

[14] Q. Wang and R. K. Ward, “Fast image/video contrast enhancement based on weighted thresholded histogram equalization,” IEEE Trans. on Consumer Electronics, vo. 53, no. 2, pp.
757-764, 2007.
[15] S. R. Sternberg, “Parallel architectures for image processing,” Real-Time Parallel Computing,
Springer US, pp. 347-359, 1981.
[16] B. Wilkinson and M. Allen, “Parallel programming: techniques and applications using networked workstations and parallel computers,” Prentice-Hall, 1999.
[17] N. Ponomarenko, L. Jin, O. Ieremeiev, V. Lukin, K. Egiazarian, J. Astola, B. Vozel, K. Chehdi,
M. Carli, F. Battisti and C.-C. J. Kuo, “Image database tid2013: Peculiarities, results and
perspectives,” Signal Processing: Image Communication, vol. 30, pp. 57-77, 2015.
[18] E. Larson and D. Chandler, “Most apparent distortion: full-reference image quality assessment
and the role of strategy,” Journal of Electronic Imaging, vol. 19, no. 1, pp. 011 006(1-21), 2010.
[19] M. Brown and S. Susstrunk, “Multispectral SIFT for scene category recognition,” in Proc.

Computer Vision and Pattern Recognition, pp. 177-184, 2011.
[20] Kodak Lossless True Color Image Suite. Online available: http://r0k.us/graphics/kodak/, 2010.
[21] W. Xue, L. Zhang, X. Mou and A. C. Bovik, “Gradient magnitude similarity deviation: a highly
efficient perceptual image quality index,” IEEE Trans. Image Process., vol. 23, no. 2, pp. 684695, 2014.
[22] S. Wang, K. Ma, H. Yeganeh, Z. Wang and W. Lin, “A patch-structure representation method
for quality assessment of contrast changed images,” IEEE Signal Process. Lett., vol. 22, no. 12,
2387-2390, 2015.
[23] K. Gu, D. Tao, J.-F. Qiao and W. Lin, “Learning a no-reference quality assessment model of
enhanced images with big data,” IEEE Trans. Neural Networks and Learning Systems, 10.1109/
TNNLS.2017.2649101, in press, 2017.
[24] P. Arbelaez, M. Maire, C. Fowlkes and J. Malik, “Contour detection and hierarchical image
segmentation,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 3, no. 5, pp. 898-916, 2011.

15

