CS 559 Quiz 1						login: KEY

Please write your name and login on all pages!		name:  gleicher
This quiz has 3 pages.
Please read the directions for each question carefully.
Please answer concisely. If you feel the need to write more than 2 or
       3 sentences for a question, think about it harder.

In addition to the 3 pages of the quiz, there are 2 pages of ungraded
surveys. You have 30 minutes for the quiz. You may return the survey
later. 

*** KEY 
*** My answers (with explanations, usually) are shown after *** in the
*** left column
+++ scoring info follows the +++

Question 1: Sampling Theory (15 pts)

From class you should know that resampling can be achieved by combining
point sampling and low-pass filtering. One of these must be applied
first, otherwise the problems of improper sampling are not avoided.

1A: Which must come first?  (1 pt)

*** Filtering must happen first
*** (since the signal must be band-limited for sampling to work, we
***  filter out the high frequencies to make sure it is band-limited
***  before sampling)
+++ right or wrong

For an assignment in a signal processing class, students worked on
discrete 1D signals. Their task was to implement the "half" operation
(which made the signal be half as long). They used the filter kernel
1/3, 1/3, 1/3. The point sampling takes every other sample from the
original. 

1B: Apply this filter to the following signal: (3 pts)
    [ 0 0 0 3 3 3 6 6 6 9 9 9 6 6 6 3 3 3 0 0 0]

    You may assume that the signal extends infinitely in both
    directions with zero values.

***  0 1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1 0 
***  with an infinite number of zeros on either side
***  (as long as you have at least 1 of the zeros at each end its OK)

*** NOTE: we asked you to filter this, not to down sample it!

+++ 3 points for getting it right, -1 if you downsampled it (say gave
+++ 0 2 4 ...)

1C: Some students implemented the half operation incorrectly, doing
    the operations in the wrong order (e.g. they got Question 1A
    wrong). They did implement the sampling part and the filtering
    part correctly, but they applied them out of order.

    They said that they tested their programs on some examples and it
    worked correctly.
    Give a non-zero signal that their program would work correctly on.
    (2 pts)

*** any constant value signal: e.g. [3 3 3 3 3 3 3 3 3 3]
*** any signal with only low frequencies (like an ascending ramp)
***     [ 1 2 3 4 5 6 7 8 9 10 ... ]
*** or  [ 3 3 3 6 6 6 9 9 9 12 12 12 ...]

+++ 2 pts for a correct answer, partial credit for something that's
+++ close 

1D: Give a non-zero signal that their program would not work correctly
    on, and give the correct resampling. (4 pts)

*** any signal with high frequencies in it
*** note: because we didn't do a real LPF, we still might get some
*** aliasing (different results if we pick the even vs. the odd
*** samples). Here are some examples:

*** this, suprisingly, turns out to be not be a right answer since it
*** works with the broken reconstruction!
*** 0 0 3 0 0 3 0 0 3 0 0 3 ...
*** filtered (with averaging): 1 1 1 1 1 1 1 1 1 ...
*** downsampled: 1 1 1 1 1 1 ...

*** 0 6 0 6 0 6 0 6 0 6 0 6 0 6 0 6 0 6 ...
*** filtered (with averaging kernel): 2 4 2 4 2 4 2 4
*** downsampled to either 2 2 2 2 2 or 4 4 4 4 4 
*** note: because the averaging filter isn't a real lpf, we still
*** have aliasing. ideally, we might have expected to get
*** 3 3 3 3 3 3 3 as the result

*** 0 0 0 3 3 3 0 0 0 3 3 3 0 0 0 3 3 3 ...
*** filtered (with averaging kernerl) -> 0 1 2 3 2 1 0 1 2 3 ...
*** note: depending on whether we sampled even or odd we do get
*** slightly different results (0 2 2 0 2 2 0) or (1 3 1 1 3 1 1)
*** they aren't exactly the same because we didn't use a true low pass
*** filter. 

+++ 2 points for a correct signal
+++ 2 points for a correct resampling
+++ note: when there is more than one possible resample, we'll give
+++ full credit for one of them

1E: Give more than one of the possible outputs of their program given
    the input of 1D. HINT: remember, they implemented the pieces
    described after 1A correctly. (3 pts)

*** the key insight here is that picking the even or the odd samples
*** (which are both legitimate implementations of the down sampling)
*** will give radically different results (even more different than
*** what we saw above)
*** or, we will see frequencies that were not in the original

*** for signal 1 above, we might pick either:
*** 0 3 0 0 3 0 0 3 0 0 3 0   or    0 0 3 0 0 3 0 0 3 0 0 3
*** averaging, we get:
*** 1 1 1 1 1 1 1 1 1 (in both cases, modulo the start up) which is
*** why I said above that this is not a right answer

*** for signal 2 above, we might sample to
*** 0 0 0 0 0 0 0 0 0   or   6 6 6 6 6 6 6 6 6 6 6 6
*** which average to 0 0 0 0 0  or   6 6 6 6 6 6 6
*** which are both much further from the "right" answer than the ones
*** I described in 1D

*** for signal 3 above, we might sample to
*** 0 0 3 0 0 3 0 0 3   or   0 3 3 0 3 3 0 3 3 0 3 3 0
*** 1 1 1 1 1 1 1 1 1   or   1 2 2 2 2 2 2 2 2 2 2 2 2
*** (note that we lose the alternations, unlike the "correct" answers
***  above) 

+++ 2 points for 1 correct answer
+++ 3 points for 2 correct answers

1F: Explain (in terms of sampling theory) why their program worked on
    1C. You can pretend that the averaging filter was a true low-pass
    filter, even though we know that it isn't. (2 pts)

*** If the signal did not contain any high frequencies to begin with, we
*** did not need to remove them using the LPF before downsampling.

*** In the first example of 1D and 1E, there is actually aliasing going on
*** - it's just that the fundamental frequency is aliasing itself to the
*** "zero" frequency.

+++ 2 pts for mentioning the lack of high frequencies
+++ 1 pt (e.g. -1) if you did not mention that the reason that a
+++ constant signal worked is that it has no high-frequencies that need to
+++ be filtered


CS559 Quiz - Page 2 of 2			login:	____________
	
						name:   ____________
Question 2: Color (12 pts)

2A: Given an image that looks like:

    RRRRRRRR  (red)
    GGGGGGGG  (green)
    BBBBBBBB  (blue)

    where each color's value has equal intensity, sketch what a
    perceptually correct grayscale image would look like. (2 pts)

*** 22222222222  (medium gray)
*** 33333333333  (bright gray)
*** 11111111111  (dark gray)
*** remember the perceptual weights - even though the red and blue
*** have equal intensity as the green, they appear darker

+++ 1 point for getting that there are different bands
+++ 1 point for having the right relative darknesses

2B: Even though we have 3 different types of photoreceptors, the CIE
    chromaticity diagram is only 2 dimensional. Explain why this works.
    (4 pts)

*** the CIE chromaticity diagram is for an a constant brightness
*** (typically fx+fy+fz = 1). Therefore, given any two of the numbers,
*** we can trivially get the third.

+++ 4 points for saying constant brightness
+++ 3 points for saying sums to 1

2C: A Symptom of excessive graphics hacking is a temporary failure of
    the blue-sensitive photoreceptors in your eyes, causing a
    temporary form of color-blindness. As a public service, we want to
    make sure that 559 students know how to test themselves for this
    condition. Assuming that you weren't color blind to begin with,
    which of the following pairs would you not be able to distinguish
    on your standard RGB CRT if you were suffering from this
    condition: (3 pts) 

    (circle with ones you would not be able to distinguish)
    A. Blue and Green
    B. Blue and Cyan
    C. Blue and White
    D. Magenta and Yellow
    E. Magenta and Red
    F. Yellow and White

*** you could not distinguish colors that differed only in their blue
*** value
*** E and F
***    (for example, blue and green would look like black and green,
***     or blue and cyan would look like black and green as well - not
***	what you're used to, but certainly distinguishable)

+++ 1/2 point for each piece

2D: An inkjet printer uses 3 colors of ink (one for each subtractive
    primary) to combine to make all other colors within its gamut.

    The printer runs out of one color of ink. You find that it cannot
    print yellow. Which other of the 5 primary colors will the printer
    not be able to print. (3 pts)

*** red (=yellow+magenta) and green (=yellow+cyan)

CS559 Quiz - Page 2 of 2			login:	____________
	
						name:   ____________

Question 3 Multiple-Multiple Choice 

*** Hint - these are true false questions. don't think of them as multiple
*** choice. 
*** There are some questions that were neither well covered in lecture or
*** the text. You get the point for these no matter what you answered
*** (they are marked with a ?)

*** There are 2 of these T/F questions for which I believe there is an
*** argument against the question. In both cases, I feel that this
*** argument requires a greater degree of depth than we either covered
*** in class or was in the readings. If you are totally convinced that
*** your answer is right (and different than mine), send me email with
*** your argument.
*** HOWEVER: if your argument is wrong, you will lose a point. 

The fovea:
? A) Is an area of the retina that has lots of rods
T B) Is an area of the retina that has lots of cones
F C) Is an area where there are no photo-receptors, so it is known as
      the blind spot
F D) Is one of many parts of the eye that focuses light

*** I believe that the fovea only has lots of cones and few rods, but
*** since I am not sure if its in the readings (nor did I say it in
*** class), ... 
*** (It could be that the fovea does have lots of rods)


Low pass filtering:
T A) Cannot be implemented exactly using discrete convolution in the
     time domain
T B) Can be implemented by multiplication in the frequency domain
F C) Requires the use of the "sinc" function as a kernel in the
     frequency domain

*** LPF is a multiplication by a "box" in the frequency domain, or a
*** convolution with sinc in the time domain. Since sinc has infinite
*** extent (and is hard to sample) it is impossible to implement
*** convolution by it in the discrete case.

Forward mapping algorithms for image warps are:
F A) implemented in the frequency domain by convolution
F B) good because they can use bi-cubic interpolation of the original
   image to get sharp features between pixels
F C) good because they do not leave gaps in the resulting target image

*** I believe this is the only question that absolutely required you
*** to have been in class. 
*** Part C is something we discussed in detail: the problem with
*** forward maps is you have to be very careful not to introduce gaps
*** in the results. 

Gamma correction:
F  A) is only important on color displays
T  B) corrects for the power law of cathode energies on CRTs
T- C) compares halftone and gray levels to compute an approximate system
      transfer function of the entire display system (including the
      viewer)
F  D) adjusts the black level of computer displays
T  E) linearizes the coding of intensities so that the values between 0
      and the number of steps are utilized as well as possible

The Floyd-Steinberg Algorithm:
F A) Implements ordered dithering
F B) Does globally optimal dithering
T C) Is a greedy algorithm for spreading quantization error around the
     image