CS549-Homework 5 Solved

(3 pts) Use OpenCV or Matlab to compute and display the Hough Transform of the Sobel or LoG edges of an image that you found last week. Where is the peak and what line does it correspond to? Submit the HT image. You do not need to submit your code.
 

(9 pts) In this Hough Transform problem x, y, b, c, m and n may be positive or negative, integers or fractions. 2 lines in (m,b) space are given by
L1: 𝑏𝑏 = 2

L2: 𝑏𝑏 = −3𝑚𝑚 + 3

Hint: It might help to construct (x,y) and (m,b) spaces.

What are points P1 and P2 in (x,y) space corresponding to each of these lines?
 

What equation describes the line passing through points P1 and P2?
 

Line L3 in (m,b) space passes through (m,b) = (0,0). What is its corresponding P3 such that P3 lies along the line from part b?
 

Point P4 in (n,c) space is at (1/3,0) corresponding to line L4 in (x,y). Where does L4 intersect the line from part b?
 

(8 pts) Ima Robot proposes to use the Hough Transform to detect squares in images. First, edges are detected, then every edge point causes certain bins (accumulators) to be incremented in the Hough array. If the image contains a square, she expects to find that the bin corresponding to that location and size will have the highest count.
 

For simplicity, we only consider squares that are aligned with the x and y axes.

Suggest a parametrization of the Square Hough space such that every possible square corresponds to a single point in that space. What are the Square Hough space axes?
 

Draw the Square Hough space that corresponds to detecting an edge point at (3, 2) in an image.
 

A second edge point is detected at (1,3) in the image. Describe all possible squares that these two points together define. If possible, relate your description to the Square Hough space.
 

(3 pts) In the SIFT algorithm, the local histogram of edge directions is computed. In 1 or 2 sentences, describe how this information is used and why it is needed.
 

(4 pts) SURF gets much of its speed from using integral images to quickly approximate derivatives of 𝑔𝑔𝜎𝜎 ∗ 𝐼𝐼, where I is the image. The integral image is defined as
𝑖𝑖′≤𝑖𝑖 𝑗𝑗′≤𝑗𝑗

𝐼𝐼Σ(𝑖𝑖, 𝑗𝑗) =   𝐼𝐼(𝑖𝑖′, 𝑗𝑗′)

𝑖𝑖′=0𝑗𝑗′=0

Show how to compute the sum over a rectangular region of the image using only 3 operations on the integral image. Let the rectangular region have lower left corner
(𝑥𝑥0, 𝑦𝑦0) and upper right corner (𝑥𝑥1, 𝑦𝑦1).

 

The desired sum is  

𝑖𝑖′≤𝑥𝑥1 𝑗𝑗′≤𝑦𝑦1

                                                                                                              𝐼𝐼(𝑖𝑖′, 𝑗𝑗′)

𝑖𝑖′=𝑥𝑥0 𝑗𝑗′=𝑦𝑦0

You can assume that any pixels outside the range (0 … 𝑀𝑀 − 1, 0 … 𝑁𝑁 − 1) are 0.

 

How can you compute the 𝐷𝐷𝑦𝑦𝑦𝑦 approximation given in the SURF paper Fig. 1 using
𝐼𝐼Σ?