This is an old course web from 2008
Old 2008 Course Web: Assignments / Written1
CS559 Written Assignment 1: Imaging
Update, September 20th - there were some inconsistencies in terminology that someone pointed out. I have (tried) to clarify things. If you have done the old questions, that's OK. But the new ones might make more sense.
Due Tuesday, September 23rd.
Please turn a hard copy into Blayne before the deadline. Please make sure that every page has your name on it.
You can turn in the hard copy by handing it to Blayne in class, or by leaving it in his mailbox on the 5th floor of CS. (Note: you need to have an access key to get to the 5th floor after hours).
If you type your answers, you can email them to Blayne (before the deadline) and he'll print it.
1. Bayer Mosaics and Interpolation
Most digital cameras actually have a single sensor, and use filters so each sample (pixel?) sees only one color. The common tiling for the pattern of the color is the Bayer Mosaic, which is described in Section 3.8 of Fundamentals of Computer Graphics.
For this question assume pixel values are between 0 and 1.
Imagine a Bayer Mosaic sensor where the left half of the image receives no light, and the right half receives enough that it gets 100% (value 1). You can assume the dividing line goes between pixels (not through a column of pixels)
1.A What values will the samples have?
1.B. The simplest de-mosaicing method is to interpolate each color independently, to obtain R,G,B for each pixel.
What values (R,G,B) will this provide for this example case? (use linear interpolation. you only need to figure the values for an 8x2 block of pixels, since other values will be similar) What would this look like if you looked closely at the image?
Note: in modern cameras, more sophisticated de-mosaicing algorithms are used.
2. 1D Convolution Practice
Let f, g, and h be the discrete signals:
f = [ 1 2 1 3 1 4 1 5 1 6 2 5 3 4 3 ] g = 1/5 [1 1 1 1 1] h = 1/6 [1 2 3]
For these first 3 parts, compute the ``whole sequence'' of the convolution:
2.A compute f*g
For these next 3 parts, assume that f has its ``zero'' at the first entry, g and h are ``zero centered'', and compute the convolutions to provide signals over the same domain as f (your answers should be 15 samples long). For an explanation of the different ways to handle the convolution endpoints see Main.ConvoleEndpoints.
(hint: most of these answers can be copied from 2.A and 2.B)
2.C compute f*g using zero-padding to handle the boundaries
3. Continuous reconstruction
Consider reconstructing the signal from the following samples (the first sample was at t=0):
f = [ 1 2 1 3 1 2 2 ]
Compute the value of the reconstructed signal at t=1.5, t=2, and t=3.25 with the following reconstruction filters (your answer for each part should be 3 numbers).
3.A The unit box (g(t) = 1 if -.5 <= t < .5, 0 otherwise)
Note: in the book (p. 89), this is the continuous case and r=1/2 Note: in the original assignment, I had the equals on the other side there's a reason I did it this way, but being consistent with the book is a better idea
3.B The unit tent (g(t) = (1+t) if -1 < t <= 0, 1-t if 0 < t <= 1, and 0 otherwise)
You can also write this as: g(t) = 1-|t| |t|<=1 Note that since when |t|=1, g(t)=0 whether you have < or <= In the book (p. 89), this is the tent filter of r=1 (I said 1/2 in the original)
3.C The box of r=1 (see the book)
3.D The tent of r=2 (again see the book)
Note: the assignment originally had r=1, but that was before I realized that the width notation was different from box and tent If you did the assignment before seeing this, we won't penalize you.
4. Sampling kernels
Consider resampling the following signal: [ 0 0 4 4 0 0 4 0 4 0 4 0 0 0 4 0 0 0 ] using the pre-filtering kernel 1/4 [1 2 1] 4.A If you resample the signal at half the sampling rate, what result would you get? 4.B If you made a small change in how you sampled in 4.A (say, chose even instead of odd values), would the results be very much different? What does this say about the adequacy of the kernel for doing this resampling? 4.C If you resample the signal at 1/3rd the samping rate (pick every third sample), what result would you get? 4.D If you made a small change in how you sampled in 4.C (say, chose elements 0,3,6 instead of elements 1,4,7), could the results be very much different? What does this say about the adequacy of the kernel for doing this resampling?
5. Seperable Kernels
A seperable kernel is one where you can achieve a 2D convolution by doing two seperate convolutions, one in each dimension. (or in higher dimensions, an nD convolution by doing n seperate convolutions).
What 2D convolution is achieved by doing the following 1D convolutions in one dimension then the other? Your answer should be a 2D ``matrix'' of numbers (the 2D convolution kernel). 5.A 1/5 [ 1 1 1 1 1 ] 5.B 1/16 [ 1 4 6 4 1 ] 5.C 1/2 [1 -1 2 -1 1] Consider doing an NxN convolution that is seperable on an MxM image. Assume that M >> N. What is the assymptotic complexity (big O) of: 5.D Doing the convolution as 2 1D convolutions (of kernel size N)? 5.E Doing the convolution as 1 2D convolution (kernel size of NxN)? Your answer should be a function of M and N. (hint 1: ignore the boundary conditions (since we're talking about assymptotic complexity) - just assume that the kernel always overlaps the image - a few edge cases won't matter when M >> N) (if hint 1 doesn't make sense, think about it this way: in the limit, how you handle a few edge pixels won't make a difference) (hint 2: you just need to count the multiplies)