Homework 06 Solution

Exam 1 will be on Wednesday 9 Oct. The exam will be open book and open notes; however, no electronic devices are allowed. If you wish to use lecture notes from the whiteboard that have been captured as images, either copy them into written form or print them out because you may not use a computer, cellphone, or other electronic viewing device during the exam.

    1. (5 pts) Project Teams: The CS/RBE 549 final project is to recognize an assigned object. These will be distributed at class on Monday 7 October; therefore, you must organize into teams before the class meets. Your challenge is to “make the problem interesting”.

Recognizing an object from a single pose against a white background is too easy. You may use multiple objects, multiple object orientations, different scales, occlusion, stereo, motion, machine learning, or other technique.

Teams may propose alternative projects to replace the object recognition problem. However, these must be approved in advance by the instructor. If you wish to do this, submit a 1-page description of your problem, including a definition of the problem and your approach, including what computer vision techniques you will use.

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 with prior approval of the instructor.

Submit, as a PDF, the names and email addresses of all team members. For this problem, and only this problem – team members should submit the identical file by 4:00 PM Monday 7 October.

Final Project Grading: 20 Approach
10  Justification

15  Analysis

15  Testing & examples

10  Documentation

10  Difficulty

20  Presentation

100 Total
2.    (6 pts) Ima Robot uses a quadtree to represent a 4 × 4 binary image. Each quadtree block starts at the upper left and proceeds clockwise.

a.    What image is represented by 1(1001)0(1100)?

b.    The image in part a is shifted down by 1 pixel. What is the new image quadtree?

c.    Must the number of 0s and 1s in the quadtree representation remain constant whenever a binary image is shifted? (The quadtree in part a has 5 1s.) Explain why or provide a counterexample. Ignore edge effects, that is, assume that no pixels fall off the edge of the image when shifting.

same in the original and transformed image. Let   ⃗
=     ⃗

⃗⃗
and show that ‖  ⃗1 −   ⃗
0
‖ =




+









1
0

0


3.  (3 pts) Show that if we rotate and translate an image, the distance between any 2 points is the

‖  ⃗1
−   ⃗ 01
‖. Hint: Use the fact that for a rotation matrix R,
= .


4.  (6 pts) A 5x5 image has class labels as follows:





















1
1

0
1
1








1
1

0
1
0








1
1

1
1
0








1
1

2
0
0








1
1

2
2
0








Assume that the outside world is region #-1 with class -1.

    a. List all the regions and their classes. List all edges, indicating which regions it separates. E.g.,


Region
Class

Edge


Regions




-1
-1

0


-1, 0





0
1

1


-1,1





. . .
. . .

. . .


. . .





There is no single correct way to list the regions and edges. However, there is an

exactly correct number of regions and edges.



b.  How many vertices are there?







5.  (3 pts) We saw that point matching could be treated as energy minimization, as in







1
0
⃗⃗
2




= ∑‖  ⃗
− (    ⃗








−  )‖











If we allow scale factor s between image 0 and 1, how does that change the equation for E?