Homework 09 Solution

    1. Chain Code (7 pts): A shape may be represented in a similar fashion to a chain code by

using real and imaginary numbers to represent consecutive edge segments in the same direction. A run of length 1 in the positive horizontal=direction√−1 would be represented by 1, a
run of length 1 in the positive vertical direction by, and runs in the negative

directions by −1 and −j. A run of length n is represented by n, nj, −n, or −nj as appropriate.

For example the shape:










is represented by: [1, j, 2, j,−3,−2j]

a.    Compare this code with the 4-connected chain code that takes on values from {0, … , 3}.
b.    Show that for any shape S, the corresponding∑  (  ) =code0 C has the property that


    c. We can consider smoothing this shape representation by combining adjacent short real and imaginary runs into a single complex run. For example,

[1, j, 2, j,−3,−2j] → [1+j, 2, j,−3,−2j] → [1+j, 2+j,−3,−2j] etc.

The more runs are combined, the more smoothing takes place. Give examples of:

        ◦ A shape that can be reasonably smoothed this way

        ◦ A shape that cannot be reasonably smoothed this way.

Be sure to define “reasonably” in this context.
  −1


d.  Suppose one takes the Discrete Fourier Transform of this code according to
( ) = ∑   (  )  −2    

  =0




What is   (  = 0)?


2.    Object Representation()by Basis  (  )Functions−1≤ (8≤pts)::+1 Ima Robot proposes=to−represent1
shapes by functions    and    for    . A shape begins at    and ends at
= +1. In order to represent the shape more compactly, the functions  ( ) and   (  ) can be
treated as Nth-degree polynomials.









and  ( ) = ∑  


( )
= ∑



where



  =0


  =0












and    are coefficients.






    a. In general, is this representation invariant to translation, scaling, and rotation? Explain.
    b. For the0 unit≤ circle,≤3  ( ) = cos  and  ( ) = sin  , what are the coefficients    and

for?  Hint: Consider a series expansion of sin and cos.
3.    (Object(),  (  )Representation),0≤≤ (10 pts): We can represent an object by its boundary
where S is the length of the object’s boundary and s is distance along
that boundary from (some)= arbitrary()+    (  )starting point. We can combine x and y into a single
complex function    . The Discrete Fourier Transform (DFT) of z is


  −1








( ) = ∑  −2    

( ),0≤  ≤  −1






  =0









We can use the coefficients  ( ) to represent the object boundary. The limit on s is S-1
because for a closed contour  ( )
=  (0). The Inverse Discrete Fourier Transform is
1
  −1
+2    





































( ) =    =0∑





( ),0≤  ≤  −1
a.  Suppose that the object is translated by

(∆  , ∆  ), that is,   ′(  ) =  ( ) + ∆   +   ∆  .
How is   ′’s DFT    ′( ) related to  ( )?



b.  Suppose that the object is scaled by integer constant c, that is,   ′(  ) =  (⌊  /  ⌋),
where ⌊∙⌋ is the floor function with ⌊1.5⌋ = 1, etc. Note that the length of the scaled
object  ′ =  . How is   ′’s DFT
  ′( ) related to  ( )?
c.  What object has  ( ) = [  
0
+  cos
2    
] +   [  
+  sin
2    
]? Sketch it.
















0


d.    What is    ( ) corresponding to  ( ) from Part c? Hint: Most coefficients are 0.