(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.
What image is represented by 1(1001)0(1100)?
The image in part a is shifted down by 1 pixel. What is the new image quadtree?
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.
(3 pts) Show that if we rotate and translate an image, the distance between any 2 points is the same in the original and transformed image. Let 𝑥⃗𝑖1 = 𝑅𝑥⃗𝑖0 + 𝑇⃗⃗ and show that ‖𝑥⃗10 − 𝑥⃗00‖ =
‖𝑥⃗11 − 𝑥⃗01‖. Hint: Use the fact that for a rotation matrix R, 𝑅𝑇𝑅 = 𝐼.
(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.
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.
How many vertices are there?
(3 pts) We saw that point matching could be treated as energy minimization, as in 2
𝐸 = ∑‖𝑥⃗𝑖1 − (𝑅𝑥⃗𝑖0 − 𝑇⃗⃗)‖
𝑖
If we allow scale factor s between image 0 and 1, how does that change the equation for E
