CS549-Homework 9 Solved

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 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]

Compare this code with the 4-connected chain code that takes on values from {0, … , 3}.
 

Show that for any shape S, the corresponding code C has the property that
∑𝑐(𝑖) = 0

𝑖

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.

 

Suppose one takes the Discrete Fourier Transform of this code according to
𝑁−1

𝑖𝜔

𝐶(𝜔) = ∑ 𝑐(𝑖)𝑒−2𝜋𝑗𝑁

𝑖=0

What is 𝐶(𝜔 = 0)?

 

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

                                                                                      𝑁                                                                    𝑁

𝑥(𝑡) = ∑ 𝑎𝑖 𝑡𝑖  and  𝑦(𝑡) = ∑𝑏𝑖 𝑡𝑖

                                                                                    𝑖=0                                                               𝑖=0

 

where 𝑎𝑖 and 𝑏𝑖 are coefficients.  

 

In general, is this representation invariant to translation, scaling, and rotation? Explain.
 

For the unit circle, 𝑥(𝑡) = cos 𝜋𝑡 and 𝑦(𝑡) = sin 𝜋𝑡, what are the coefficients 𝑎𝑖 and 𝑏𝑖 for 0 ≤ 𝑖 ≤ 3? Hint: Consider a series expansion of sin and cos.
 

Object Representation (10 pts): We can represent an object by its boundary
(𝑥(𝑠), 𝑦(𝑠)),0 ≤ 𝑠 ≤ 𝑆 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

𝑘𝑠

𝑧(𝑠) =𝑒+2𝜋𝑗 𝑆 𝑍(𝑘), 0 ≤ 𝑘 ≤ 𝑆 − 1

𝑘=0

 

Suppose that the object is translated by (∆𝑥, ∆𝑦), that is, 𝑧′(𝑠) = 𝑧(𝑠) + ∆𝑥 + 𝑗∆𝑦. How is 𝑧′’s DFT 𝑍′(𝑘) related to 𝑍(𝑘)?
 

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 𝑍(𝑘)? 
 

What object has 𝑧(𝑠) = [𝑥0 + 𝑅 cos 2𝜋𝑠𝑆 ] + 𝑗[𝑦0 + 𝑅 sin2𝜋𝑠𝑆 ]? Sketch it.
 

What is 𝑍(𝑘) corresponding to 𝑧(𝑠) from Part c? Hint: Most coefficients are 0.