CS

 510  Midterm  –  Spring  2012  

Name  _____  ANSWER  KEY    _______  
EID  ____________________________________________  

Question   Max  Points   Points  

1   15    

2   15    

3   20    

4   20    

5   10    

6   10    

7   10    

TOTAL   100    
 

CS  510  Midterm    –  Spring  2012   1  

<This  Page  Left  Blank  on  Purpose>  
   

CS  510  Midterm    –  Spring  2012   2  

Q1  Applications  of  Computer  Vision  (15  Points)  
 

We  devoted  two  lectures  to  student  presentations  of  commercial  applications  of  
computer  vision.    Please  succinctly  summarize  three  distinct  applications,  one  
paragraph  for  each.  
 
Application  1:  

There  is  no  single  correct  answer.  Indeed,  any  reasonably  substantive  discourse  on  any  
three  of  the  topics  covered  by  the  term  papers  would  constitute  a  good  answer.  For  the  
record,  those  topics  are:      

Film  and  Video  Production  

Security:  Monitoring  and  Surveillance  
3D  Object  Modeling  
Medical  Imaging  
People  Tracking  for  Sales  and  Marketing  
Driver  Assistance  
Biometrics  
Gesture  Recognition  
Autonomous  Vehicles    
Security:  Threat  Detection  
Sports  Video  -­‐  Referee  
Sports  Video  -­‐  Broadcast  
 
Application  2:  
 
 

 
Application  3:  
 

   
   

CS  510  Midterm    –  Spring  2012   3  

Q2  Limitations  of  Discrete  Sampling  (15  Points)  
The  two  related  concepts  of  Nyquist  Rate  and  aliasing  play  a  critical  role  in  
understanding  one  of  the  most  troublesome  risks  associated  with  discrete  sampling  of  
an  analogue  signal  or  even  down  sampling  a  discrete  signal.      
Below  is  a  picture  of  an  analogue  signal,  a  pure  cosine  wave  with  a  periodicity  of  one  
cycle  per  second.    Use  this  signal  to  illustrate  aliasing  and  precisely  define  the  Nyquist  
rate  under  the  presumption  that  reliable  encoding  of  signals  up  to  one  cycle  per  second  
is  desired.  
 
1.0
0.5
Signal

0.0
-1.0 -0.5

0 1 2 3 4 5 6

Seconds
 
Here  is  what  happens  of  samples  are  spaced  at  ¾  of  a  cycle  (second)  intervals.
1.0
0.5
Signal

0.0
-1.0 -0.5

0 1 2 3 4 5 6

Seconds
 
This  is  sampling  below  the  Nyquist  rate  of  2  samples  per  second  (no  more  than  0.5  
seconds  between  samples).    Note  on  the  curve,  over  6  seconds  there  are  only  9  samples  
as  opposed  to  the  required  12.  Further,  12  is  a  special  case  because  it  can  end  up  
sampling  straight  down  the  zero  crossings,  missing  the  sine  wave  entirely.  Thus,  one  
says  sampling  must  be  carried  out  above  (not  equal  to)  the  Nyquist  rate.      

CS  510  Midterm    –  Spring  2012   4  

Q3  Comparing  Vectors  /  Images  (20  Points)  
There  is  a  circumstance  fully  discussed  in  lecture  in  which  maximizing  correlation  is  
mathematically  equivalent  to  minimizing  L2  distance.      
First,  please  precisely  define  L2  distance  between  two  vectors  denoted  as:  
𝑣! 𝑤!
𝑣 𝑤
𝑣 = !          𝑤 = !            
𝑣! 𝑤!

𝐿! = 𝑣! − 𝑤! !  

Now  precisely  define  Pearson’s  Correlation  

𝑣! − 𝑣 𝑤! − 𝑤
𝐶=  
𝑣! − 𝑣 !   𝑤! − 𝑤 !

Finally,  state  the  circumstances  under  which  maximizing  correlation  is  equivalent  to  
minimizing  L2  distance  and  use  the  formal  statement  of  these  circumstances  to  derive  
(prove)  the  equivalence.  
First  condition,  subtract  off  means    
𝑣! − 𝑣 𝑤! − 𝑤
𝑣 = 𝑣! − 𝑣          𝑤 = 𝑤! − 𝑤            
𝑣! − 𝑣 𝑤! − 𝑤

 
Second  condition,  make  each  vector  unit  length  
𝑣 𝑤
𝑣=            𝑤 =  
𝑣 𝑤
Now,  start  with  L2  and  manipulate    

𝐿! = 𝑣! − 𝑤! ! = 𝑣! ! + 𝑤! ! −2 𝑣! 𝑤! =   1 + 1 − 2 𝑣! 𝑤!  

The  sum  of  the  squares  is  just  one  because  of  step  two  and  correlation  is  the  dot  product  
because  of  both  steps,  so  maximizing  L2  above  is  equivalent  to  minimizing  the  dot  
product/correlation.  
 
   

CS  510  Midterm    –  Spring  2012   5  

Q4  The  2-­‐D  Fourier  Transform  (20  Points)  
Recall  the  Fourier  Transform  Applet  on  the  BrainFlux  website  by  Jason  Gallicchio.    I  have  
used  this  tool  to  create  12  pairs  –  an  image  at  its  corresponding  Fourier  transform.    
Images  are  grayscale  and  the  magnitude  of  the  Fourier  transform  is  shown  as  a  
grayscale  image.  The  images  are  lettered  and  the  transforms  are  numbered.  At  the  end  
of  this  question  is  a  table  where  you  must  write  the  number  of  the  corresponding  
transform  under  the  letter  of  the  corresponding  image.      

       
A   B   C   D  

       
E   F   G   H  

       
I   J   K   L  

 
   

CS  510  Midterm    –  Spring  2012   6  

Q5  The  2-­‐D  Fourier  Transform  (continued)  

       
1   2   3   4  

       
5   6   7   8  

       
9   10   11   12  

 
Write  your  answer  in  the  table  below.  

A   B   C   D   E   F   G   H   I   J   K   L  

11   7   2   1   12   4   10   8   5   6   9   3  

 
   

CS  510  Midterm    –  Spring  2012   7  

Q5  Geometric  Transformations  (10  Points)  
The  following  linear  algebraic  equation  is  taken  directly  from  the  CS  510  course  lecture  
notes:  

 
What  is  the  vector  on  the  left  hand  side  of  the  equation?  
These  are  coordinates  of  four  points  after  application  of  a  2-­‐D  projective  transform.  
What  is  the  vector  on  the  right  hand  side  of  the  equation?  
They  are  the  8  parameters  in  an  8-­‐DOF  projective  transform  defined  as  

 
What  do  the  terms  in  the  matrix  signify?  

They  signify  the  coordinates  of  four  points  prior  to  application  of  the  2-­‐D  projective  
transformation  as  well  as  the  u,  v  coordinates  after  the  transformation  in  such  a  way  
that  it  will  be  possible  to  solve  for  the  parameters  of  the  transformation  (see  next  
question).  

How  is  this  equation,  which  simplifying  is  in  the  form  𝐴 = 𝑀  𝑍  ultimately  put  to  good  
use?  In  other  words,  with  it,  what  can  be  accomplished?  

By  solving  for,  𝑍 = 𝑀!!  𝐴  we  can  directly  determine  the  transformation  mapping  the  
four  points  in  x,y  space  to  their  corresponding  locations  in  u,v  space.  
 
   

CS  510  Midterm    –  Spring  2012   8  

Q6  Correlation  Space  (10  Points)  
Consider  the  following  image  

 
Using  the  image  to  demonstrate,  show  the  three  steps  needed  to  normalize  this  image  so  
that  it  may  be  considered  to  reside  in  correlation  space.  

Step  1   Step  2   Step  3  

Unroll  the  image   Subtract  the  mean,   Divide  through  by  length,  
yielding  a  unit  length  
6 Which  is  48  /  12  =  4   vector.  Length  is  square  
root  of  
2 2 8*2*2+2*4*4=32+32=64,  or  
0 −2 8  
6 −4 2
6 2 −2
2 2 −4
 
4 −2 2
 
2 0 2
2 −2 1 −2
6 −2 8 0
 

8 2 −2
4 4 −2
0 2
4
0

 
   

CS  510  Midterm    –  Spring  2012   9  

Q7  Basics  of  Principal  Component  Analysis  (  10  Points)  
Consider  for  the  sake  of  illustration  an  extremely  simple  problem  involving  three  data  
points  defined  in  2-­‐D.  
3 9 6
𝑝! =    𝑝! =    𝑝! =  
1 3 2
 Illustrate  the  process  of  constructing  the  covariance  matrix  from  which  the  first  and  
second  principal  components  may  then  be  determined.    To  guide  your  answer,  follow  
these  steps.  
Create  the  data  matrix.  Since  this  problem  is  so  simple,  avoid  normalizing  the  individual  
data  points  (vectors)  in  any  way.    However,  do  show  the  data  matrix  before  and  after  it  
is  ‘centered’.    

3 9 6
𝑋=    
1 3 2
−3 3 0
𝑋=  
−1 1 0
Compute  the  covariance  matrix  from  the  centered  data  matrix  

−3 −1
−3 3 0 18 6
Ω= 3 1 =  
−1 1 0 6 2
0 0
 Draw  a  simple  sketch  of  the  three  data  points.  See  if  you  can  also  sketch  in  the  first  
principal  component  simply  by  inspection.  

 
This  can  be  done  by  inspection  because  it  is  such  a  simple  case.    The  three  points  lie  on  a  
line,  with  the  middle  point  at  the  origin  after  centering.    The  principal  component  is  an  
axis  defined  by  the  vector  from  the  origin  to  the  point  (3,1)  [or  alternatively  to  the  point  
(-­‐3,-­‐1),  the  are  the  same  axis.]  

CS  510  Midterm    –  Spring  2012   10