Homework 05 Solution

    0. Project Teams: The CS/RBE 549 final project is to recognize an assigned object. These will be distributed in class on Monday 7 October. You should organize into teams of 4 students (including yourself). If you cannot find a 4th team member, let a TA or the instructor know and we will try to help you find teammates. 5-student teams are not allowed – they are too unwieldy. 3-student teams may be allowed in case of extenuating circumstances. HW #6 will ask you to list your teammates. You do not need to list them yet, but it is a good idea to form teams now.

Teams may propose alternative projects to replace the object recognition problem. However, these must be approved in advance by the instructor.

Project details will be available later on Canvas.


    1. (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.


    2. (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.

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

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

    c. 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?

    d. 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?
3.    (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.

a.    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?

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

c.    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.


4.    (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.

5.    (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
    a. 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 .

1    1
    • 0

The desired sum is
′≤    1
′≤    1
(′, ′)






You can assume that any pixels
�′
�′



=    
=    

(0…  −1,0…  −1)


outside0 the
0range

are 0.





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

1

-2

1