Digital Image Process Note: Contrast Stretching

I Piecewise contrast stretching

s is the output intensity, and r is the input intensity. \(s = T(r)\) From the piecewise linear function we have \(T(r) = \begin{cases}a_1x+b_1, & x\ge r_2 \\ a_2x+b_2, & r_1\le x < r_2\\ a_3x+b_3, & x< r_1 \end{cases}\) where the coefficients are \(\begin{aligned} &a_1=\frac{L-1-s_2}{L-1-r_2},\quad b_1 = L-La_1,\quad (r_2<L-1)\\ &a_2=\frac{s_1-s_2}{r_2-r_1},\quad b_2=s_1-a_2r_1,\quad (r_1\ne r_2)\\ &a_2=0,\quad b_2=0,\quad (r_1= r_2)\\ &a_3=\frac{s_1}{r_1},\quad b_3=0,\quad (r_1>0) \end{aligned}\)

II Evaluate the joint histogram

Suppose we have a histogram H, and $h_i,i=1,\dots,p$ denotes the height of the ith bin of the histogram, p is the number of bins, then \(h_i = \frac{n_i}{N}\) where $n_i$ denotes the number of the pixels with gray lever / intensity level i, and $N$ denotes the total number of the pixels in this image. Or express this in density form \(p(k)=\frac{n_k}{N},\ k=1,\dots,K-1\) where $n_k$ is the number of pixels having intensity level k, and K is the total number of possible intensity levels.

III Efficient update of local histogram method

Since only one row or column of the neighborhood changes in a one-pixel translation of the neighborhood (assume the window is a rectangle), and the improved formula derived from problem 2.1, \(p(k)=\frac{n_k}{n}\) where for now $n$ denotes the total number of pixels in the neighborhoods. Then we have \(\begin{aligned} p'(k)&=\frac{1}{n}[n_k-n_{old\ edge} + n_{new\ edge}]\\ &=p(k) +\frac{1}{n}[n_{new\ edge}-n_{old\ edge}] \end{aligned}\) where $n_{new\ edge}$ is the number of pixels with value $k$ in the window introduced by the move, and $n_{old\ edge}$ is the corresponding number deleted by the move.

To better leverage the characteristic, we move the window following the “zig-zag” trajectory, that is, move from left to right for the previous row, then go down a row and move from right to left for this row, until we come to the finish one.

IV Global histogram equalization

In the class we’ve already proved the mathematical principles of equalization.

For the function like \(s=T(r)=(L-1)\int_o^rp_r(w)dw\) where $r$ is the value of input pixel, and $s$ is the value of output pixel. Then it satisfies

(a) $T(r)$ is the monotonically increasing function on $[0,L-1]$.

(b) When $r\in[0,L-1]$, $T(r)\in [0,L-1]$.

And since \(\frac{\mbox{d}s}{\mbox{d}r}=\frac{\mbox{d}T(r)}{\mbox{d}r}=(L-1)\frac{\mbox{d}}{\mbox{d}r}\left[\int_0^rp_r(w)\mbox{d}w\right]=(L-1)p_r(r)\) Therefore \(p_s(s)=p_r(r)\left|\frac{\mbox{d}r}{\mbox{d}s}\right|=p_r(r)\left|\frac{1}{(L-1)p_r(r)}\right|=\frac{1}{L-1},\ 0\le s\le L-1\) which means $s\sim U(0,\frac{1}{L-1})$. Then it’s possible to use just the information from the original image and transform itself into an appearance of high contrast and with a large variety of gray tones. (occupy the entire range of possible intensity levels and be distributed uniformly)

Here, for discrete values, we work with probabilities and summations instead of probability density functions integrals. \(p_r(r_j)=\frac{n_k}{MN}\) where $MN$ represents the total pixels in the image. The transformation here is \(\begin{aligned}s_k&=T(r_k) =(L-1)\sum_{j=1}^kp_r(r_j)\\ &=(L-1)\sum_{j=1}^k\frac{n_k}{MN},\quad k=0,1,\dots,L-1\end{aligned}\)

We found that p1_equalized.png is somewhat “brighter” than p1_gray_Stretched.png, changed from equalization and contrast stretching respectively. This is due to the characteristic of histogram equalization. From the process of contrast stretching we know the minimum and maximum gray levels of p1.tif are 91 and 138 respectively, and the number of total pixels of this image is $889\times 889$. So from calculation we have \(s_{91}=(L-1)\sum_{i=0}^{91}\frac{n_{91}}{MN}=255\frac{55171}{889\times 889}=17.799\) which shows there’s no pixel in p1_equalized.png that with gray level less than or equal to $17.799$. However, if we implement piecewise linear transformation, we can set (r1,s1) by ourselves.

V Local histogram equalization (efficient computation)

This algorithm is exactly the same as the one describes in problem 2.2, except for a few lines to calculate the equalization. Both the method to evaluate local histograms efficiently and the feasibility of calculating equalization have been explained above. Here we introduce the way to calculate some statistics of the image which will be used later.

Here we implemented two ways to expand the image for local histogram calculation. One of them requires the computation of average gray level, or the mean of the gray levels. Which is \(m=\sum_{i=1}^{L-1}r_ip(r_i)=\frac{1}{MN}\sum_{x=0}^{M-1}\sum_{y=0}^{N-1}f(x,y)\) where $x=0,1,2,\dots,M-1,\ y=0,1,2,\dots,N-1$ are the coordinates of the pixel, and $f(x,y)$ represents the intensity value of the pixel at $(x,y)$.