Homework #1 Solution

General Instructions:




Read Homework Guidelines and MATLAB Function Guidelines for the information about homework programming, write-up and submission. If you make any assumptions about a problem, please clearly state them in your report.



You need to understand the USC policy on academic integrity and penalties for cheating and plagiarism. These rules will be strictly enforced.



Problem 1: Image Demosaicing and Histogram Manipulation (50%)




Bilinear Demosaicing (10%)



To capture color images, digital camera sensors are usually arranged in form of a color filter array (CFA), called the Bayer array, as shown in Figure 1. Since each sensor at a pixel location only captures one of the three primary colors (R, G, B), the other two colors have to be re- constructed based on their neighbor pixel values to obtain the full color. Demosaicing is the process of translating this Bayer array of primary colors into a color image that contains the R, G, B values at each pixel.


























































Figure 1: (a) Single CCD sensor covered by a CFA and (b) Bayer pattern [1].




Implement the simplest demosaicing method based on bilinear interpolation. Exemplary demosaicing results are given in Figure 2. With this method, the missing color value at each pixel is approximated by bilinear interpolation using the average of its two or four adjacent pixels of the same color. To give an example, the missing blue and green values at pixel R3,4 are estimated as:































Professor C.-C. Jay Kuo Page 1 of 9
569 Digital Image Processing: Homework #1






As for pixel G3,3, the blue and red values are calculated as:
















Apply the bilinear demosaicing to the cat image in Figure 3 and show your results.



Do you observe any artifacts? If yes, explain the cause of the artifacts and provide your ideas to improve the demosaicing performance.











































































Figure 2: (a) The original lighthouse image and (b) the demosaiced lighthouse image by bilinear interpolation.


























































Figure 3: The cat image with the CFA sensor input.













Professor C.-C. Jay Kuo Page 2 of 9
569 Digital Image Processing: Homework #1






Malvar-He-Cutler (MHC) Demosaicing (20%)



Malvar et al. [1] proposed an improved linear interpolation demosaicing algorithm. It yields a higher quality demosaicing result by adding a 2nd-order cross-channel correction term to the basic bilinear demosaicing result. Both the bilinear and the MHC demosaicing results of the Fruit_Shop image are shown in Figure 4.



































































Figure 4: Demosacing results of Fruit_Shop image: the CFA input (left), the bilinear demosaicing result (middle) and the MHC demosaicing result (right)




The MHC algorithm is stated below.




To estimate a green component at a red pixel location, we have

ˆ
ˆ bl
(i, j) + α R (i, j )
(1)
G(i, j) = G
where the 1st term at the right-hand-side (RHS) is the bilinear interpolation result given in (1) and the 2nd term is a correction term. For the 2nd term, alpha is a weight factor, and DR is the discrete 5-point Laplacian of the red channel:

R (i, j) = R (i, j) −
1
(R (i − 2, j) + R (i + 2, j) + R (i, j − 2) + R (i, j + 2))
(2)


4




To estimate a red component at a green pixel location, we have

ˆ
ˆ bl
(i, j) + β G (i, j )
(3)
R(i, j) = R
where G is a discrete 9-point Laplacian of the green channel.




To estimate a red component at a blue pixel location,




ˆ
ˆ bl
(i, j) + γ B (i, j)
(4)
R(i, j) = R
where B is a discrete 9-point Laplacian of the blue channel. The weights α, β, γ control how much correction is applied, and their default values are:




α=1,β=5,γ=3




(5)



2




8




4



Professor C.-C. Jay Kuo




Page 3 of 9
EE 569 Digital Image Processing: Homework #1







The above formulas can be generalized to missing color components at each sensor location. Consequently, the MHC demosaicing can be implemented by convolution with a set of linear filters. There are eight different filters for interpolating the different color components at different locations as illustrated in Figure 5 [1].

































































































Figure 5: Filter coefficients




Implement the MHC linear demosaicing algorithm and apply it to the Cat image in Figure 3. Show your results.



Compare the MHC and the bilinear demosaicing results and explain the performance differences between these two algorithms in your own words.






















































Professor C.-C. Jay Kuo Page 4 of 9
569 Digital Image Processing: Homework #1






Histogram Manipulation (20%)



Implement two histogram equalization techniques:

Method A: the transfer-function-based histogram equalization method



Method B: the cumulative-probability-based histogram equalization method



Enhance the contrast of images rose_dark and rose_bright in Figure 6 using both methods. Describe the procedure and show final results with the following steps.




Plot the histograms of all images (2 input and 4 output images). The figure should have the intensity value as the x-axis and the number of pixels as the y-axis.
Apply Method A to rose_dark and rose_bright and show the enhanced image. Plot the transfer function for each testing image.



Apply Method B to rose_dark and rose_bright and show the enhanced image. Plot the cumulative histogram for each testing image.



Discuss your observations on these two enhancement results. Do you have any idea to improve the current result?
Apply your implemented Method A and Method B to rose_mix in Figure 4 and show the result. Can you get similar result as in previous part? If not, how to modify your implementation? Please justify your answer with discussion.



Note that MATLAB users CANNOT use functions from the Image Processing Toolbox except displaying function like imshow().














































(a) rose_dark (b) rose_bright (c) rose_mix




Figure 6: Three rose images with different gray-scale histograms.




















































Professor C.-C. Jay Kuo Page 5 of 9
EE 569 Digital Image Processing: Homework #1







Problem 2: Image Denoising (50%)




(a) Gray-level image (20%)




Remove noise in the image in Figure 7(b), compare it with the original image in Figure 7(a), and answer the following questions:




















































(a) (b)




Figure 7: (a) the original pepper image and (b) the pepper image with added noise.




What is the type of embedded noise in Figure 7(b)?



Apply a linear filter of size N by N to the noisy image. Compare the performance of two choices of the filter parameters – the uniform weight function and the Gaussian weight function and study the effect of the window size (i.e. parameter N). Plot the peak-to-signal-noise (PSNR) value as a function of N for both weighting functions.
Note: The PSNR value between images I and Y can be calculated as:

where
PSNR(dB) = 10log&' (
)*+)-.,
/
2


(1)




MSE =
1
( ,
)
− ( , ))


(2)
and where I is the noise-free image of














∑ =1 ∑ =1 (






M, Max
for 8-bit image is 255.


size N
×
M, Y is the filtered image of size N
×

























In most low-pass linear filters, we often see degradation of edges. However, using some non-linear filters, we can preserve the edges. Bilateral filters are one such kind of filters. A discrete bilateral filter is given by:
( , ) = ∑A,B ( , ) ( , , , )




∑A,B ( , , , )

(3)

( , , , ) = G−
( − )H + ( − )H
−
‖ ( , ) − ( , )‖H
N
2 KH
2 MH



(4)

where ( , ) is the neighboring pixel location within the window centered around ( , ), I is the

image with noise, Y is the filtered image. K and M are the spread parameters. Implement the




bilateral denoising filter and apply it to the noisy image.




Professor C.-C. Jay Kuo Page 6 of 9

569 Digital Image Processing: Homework #1






The non-local mean filter utilizes the pixel value from a larger region rather the mean of a local window centered around the target pixel. A discrete non-local mean filter with Gaussian weighting function is as follows:
∑S ∑Q ( , ) ( , , , )

( , ) = AR&S BR&Q




∑AR& ∑BR& ( , , , )

(5)

H

( , , , ) = exp W− X ( Y,Z) − ( A,B)XH,[]




(6)

where I, Y are the noisy and filtered images respectively, ^,_ is the window centered around

location (x, y), and ℎ is the filtering parameter.

The Gaussian weighted Euclidian distance between window ` Y,Za and ` A,Ba is defined as:

X ` Y,Za − ( A,B)XHH,[ = b [( &, H)( ( − &, − H) − ( − &, − H))H

ef,e,∈S

(7)

and

2+ 2 ( 1, 2) =√2 exp (− 12 2 2)






(8)

where denotes the local neighborhood centered at the origin, &, H ∈ denotes the relative




position in the neighborhood window. a 0 is the standard deviation of the Gaussian kernel.

Implement the non-local mean filter and apply to the noisy image.























































(a) (b)




Figure 8: (a) the original rose image (b) the rose image with mixed noise.




(b) Color image (20%)




Figure 8 (b) is a noisy color image, where each channel is corrupted by both impulse and uniform noises.




Try your best to remove noise and compare the result with the original image as shown in Figure 8(a).




Discuss your denoising strategy and answer the following questions:




(1) Should you perform filtering on individual channels separately for both noise types?




Professor C.-C. Jay Kuo Page 7 of 9

569 Digital Image Processing: Homework #1






What filters would you like use to remove mixed noise?



Can you cascade these filters in any order? Justify your answer.



It could be difficult to remove uniform noise satisfactorily. Filters may blur the object’s edge when smoothing noise. A successful design of a uniform noise filter depends on its ability to distinguish the pattern between the noise and the edges. Please suggest an alternative to low pass filter with Gaussian weight function and discuss why such solution can potentially work better. (You are welcome to implement the filter, but it is not required)



Shot noise (10%)



Electronic camera image sensor, especially the CMOS sensor typically has noise in the dark parts of the captured image. Such noise is called shot noise, which is caused by statistical quantum (the photon) fluctuations.
































































(a) (b)




Figure 9: (a) the original pepper image and (b) the pepper image with shot noise.




Figure 9(b) shows a typical image with shot noise. Unlike uniform noise, shot noise is Poisson distributed.




A common solution is firstly applying the Anscombe root transformation on each pixel z:

( ) = 2l + mn




to the input image, resulting an image with additive Gaussian noise of unit variance. Then, a conventional denoising filter for Gaussian noise is used. The denoised image is finally inverse transformed. The detailed denoising steps can be found in [3].




Implement the denoising method in [3] and apply it to Figure 9(b), where you can remove the additive Gaussian noise using two methods.



Use a Gaussian low pass filter



Use the MATLAB code for block-matching and 3-D (BM3D) transform from [4].



Show the final noise-removed pepper images and compare the PSNR values and visual quality of the resulting images.












Professor C.-C. Jay Kuo Page 8 of 9


EE 569 Digital Image Processing: Homework #1


Appendix:






Problem 1: Image Demosaicing and Histogram Manipulation


cat_ori.raw
390x300x3
24-bit
color(RGB)
cat.raw
390x300
8-bit
gray
rose_ori.raw
400x400
8-bit
gray
rose_dark.raw
400x400
8-bit
gray
rose_bright.raw
400x400
8-bit
gray
rose_mix.raw
400x400
8-bit
gray



Problem 2: Noise Removal




pepper.raw
256x256
8-bit
gray
pepper_noise.raw
256x256
8-bit
gray
rose_color.raw
256x256x3
8-bit
color(RGB)
rose_color_noise.raw
256x256x3
8-bit
color(RGB)
pepper_dark.raw
256x256
8-bit
gray
pepper_dark_noise.raw
256x256
8-bit
gray



Reference Images




All images in this homework are from the USC-SIPI image database [5] or Google images [6].




References




M. E. Celebi et al. (eds.), Color Image and Video Enhancement
Malvar, Henrique S., Li-wei He, and Ross Cutler. "High-quality linear interpolation for demosaicing of Bayer-patterned color images." Acoustics, Speech, and Signal Processing, 2004. Proceedings. (ICASSP'04). IEEE International Conference on. Vol. 3. IEEE, 2004.



Makitalo, Markku, and Alessandro Foi. "Optimal inversion of the Anscombe transformation in low-count Poisson image denoising." IEEE transactions on Image Processing 20.1 (2011): 99-109.
[Online]. Available: http://www.cs.tut.fi/~foi/GCF-BM3D/
[Online] http://sipi.usc.edu/database/
[Online] http://images.google.com/































































Professor C.-C. Jay Kuo Page 9 of 9