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.
