Mid-Level Vision: Segmentation (Artificial) 1. Briefly describe the role of mid-level vision.
To group together image elements that belong together, and to segment them from all other image elements.
2. One simple method of segmentation is thresholding. (a) Briefly explain how an appropriate threshold might by obtained by using an intensity histogram. (b) Explain the procedure used when applying hysteresis thresholding.
(a) This method assumes that the histogram of pixel intensities will have two peaks. The threshold is placed (midway) between those peaks.
(b) This method requires two thresholds to be defined (a high threshold and a low threshold). These may be obtained using the intensity histogram by placing the thresholds on either side of the valley between the two peaks. Pixels above the high threshold are classified as figure and below the low threshold as background. Pixels between the low and high thresholds are classified as figure only if they are adjacent to other figure pixels.
3. The array below shows the intensity values in a 3-by-3 pixel greyscale image, I.
0.4 0.1 0.4 I = 0.2 0.2 0.7 0.3 0.8 0.9
Generate a binary image by performing hysteresis thresholding on I using a high threshold of th = 0.75 and a low threshold of tl = 0.25. Assume each pixel has four neighbours (horizontal and vertical).
Set values above th to one and values below tl to zero:
0.4 0 0.4 I= 0 0 0.7
0.3 1 1
For each pixel with a value between the thresholds, give a value of 1 if a neighbouring pixel has a value of 1, or 0 otherwise.
000 I=001 111
22
4. The figure shows a 7 by 9 pixel binary image.
1
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
2
3
4
5
6
7
123456789
(a) Draw the image that results from performing erosion followed by dilation on this image, assuming each pixel has 4 (horizontal and vertical) neighbours.
(b) Draw the image that results from performing dilation followed by erosion on this image, assuming each pixel has 8 (horizontal, vertical and diagonal) neighbours.
erosion
dilation
1
2
3
4
5
6
7
123456789
1
2
3
4
5
6
7
123456789
23
1
2
3
4
5
6
7
123456789
dilation
erosion
5. Write pseudo-code for the region growing algorithm.
1. While not all pixels have been assigned a region label
2. Choose an unlabelled pixel at random
3. Assign chosen pixel the next unused region label
4. For all neighbouring pixels which haven’t been assigned a label
5. Calculate similarity to chosen pixel
6. For each pixel within the similarity threshold
7. Give that pixel the same region label as the chosen pixel
8. Make that pixel the chosen pixel and repeat from step 4 9. Repeat from step 2
6. The array below shows feature vectors for each pixel in a 3 by 3 image.
1
2
3
4
5
6
7
123456789
(5, 10, 15) (10, 10, 15)
(5, 5, 15)
(10, 15, 30) (5, 20, 15) (30, 10, 5)
(10, 10, 25) (10, 5, 30)
(30, 10, 10)
Apply the region growing algorithm to assign each pixel to a region. Assume that (1) the method used to assess similarity is the sum of absolute differences (SAD), (2) the criteria for deciding if elements are similar is that the SAD is less than 12, (3) the seed pixel is the top-left corner, (4) pixels have horizontal, vertical and diagonal neighbours.
24
Label top-left pixel 1. Calculate SAD values for pixels neighbouring the top-left pixel:
(5,10,15) : 1 25 → 5↓ 10↘
(10,15,30) (5,20,15) : 1
(10,10,25)
(10,5,30)
(10,10,15) : 1
(5, 5, 15) (30, 10, 5) Calculate SAD values to unlabelled pixels from middle-left pixel:
(30, 10, 10)
(10,10,25)
(10,5,30)
(30,10,10)
(5,10,15) : 1 25 → 5↓ 10↘ (10,10,15) : 1
10 ↓
(10,15,30) (5,20,15) : 1 (30,10,5)
(5,5,15) : 1
Calculate SAD values to unlabelled pixels from middle-middle pixel:
(10, 10, 25)
(10,5,30)
(30, 10, 10)
(10, 10, 25)
(10, 5, 30)
(30, 10, 10)
1 (10,15,30) : 2 10 → (10,10,25) : 2 10↘
1 1 (10,5,30):2
1 (30, 10, 5) (30, 10, 10) Calculate SAD values to unlabelled pixels from right-middle pixel:
(5,10,15) : 1 5 ↓ (10,10,15) : 1 10 ↓ (5,5,15) : 1
25 → 10 ↘
30 ↘
(10,15,30) 25 ↑ (5,20,15) : 1 45 ↓ (30,10,5)
25↗ 35 → 40↘
25↗ 35→ 40↘
Calculate SAD values to unlabelled pixels from left-bottom pixel:
(5, 10, 15) : 1 5↓ (10,10,15):1 10 ↓ (5,5,15) : 1
25 → (10, 15, 30) 10↘ 25↑
(5, 20, 15) : 1 30↘ 45↓
40 → (30, 10, 5)
Region 1 cannot grow further. Choose another seed pixel: middle-top:
30 ↘
1
1
1
122
11 2
1 (30,10,5) : 3 5 ← (30,10,10) : 3
(30, 10, 10) Region 2 cannot grow further. Choose another seed pixel: bottom-right:
(10,15,30) : 2 1
(30, 10, 5)
10 → (10,10,25) : 2 10↘ (10,5,30):2 50↙45↓
25
122 Region labels: 1 1 2
133
7. Write pseudo-code for the region merging algorithm.
1. Give every pixel a unique region label
2. Randomly choose a region which has not been marked final
3. Compare the chosen region’s properties with those of its neighbours 4. For all regions with properties which are within the similarity threshold
5. Re-label them with the region label of the chosen region
6. Calculate properties of the merged region as mean of all its constituents 7. If no regions can be merged with chosen region, mark it as final
8. Repeat from step 2 until all image regions are marked final.
8. The array below shows feature vectors for each pixel in a 3 by 3 image.
(5, 10, 15) (10, 10, 15)
(5, 5, 15)
(10, 15, 30) (5, 20, 15) (30, 10, 5)
(10, 10, 25) (10, 5, 30)
(30, 10, 10)
Apply the region merging algorithm to assign each pixel to a region. Assume that (1) the method used to assess similarity is the sum of absolute differences (SAD), (2) the criteria for deciding if regions are similar is that the SAD is less than 12, (3) the first chosen region is the top-left corner, (4) regions have horizontal, vertical and diagonal neighbours.
Give each pixel a unique label.
Calculate SAD values for regions neighbouring the top-left region:
(5,10,15) : 1 25 → 5↓ 10↘
(10,15,30) : 2 (5,20,15) : 5
(10,10,25) : 3
(10,10,15) : 4
(10,5,30) : 6
(5,5,15) : 7 (30,10,5) : 8 (30,10,10) : 9 Merge similar regions, and calculate properties of the merged region:
(6.67,13.33,15) : 1 (10,15,30) : 2 (10,10,25) : 3
(6.67, 13.33, 15) : 1 (6.67, 13.33, 15) : 1 (10, 5, 30) : 6
(5,5,15) : 7 (30,10,5) : 8 (30,10,10) : 9 Calculate SAD values for neighbouring regions:
(6.67,13.33,15) : 1 (10,15,30) : 2 (10,10,25) : 3 20↑16.67↗
(6.67, 13.33, 15) : 1 10 ↓
(5,5,15) : 7
(6.67, 13.33, 15) : 1 36.67 ↓ (30,10,5) : 8
26.67 → 31.67 ↘
(10, 5, 30) : 6
(30,10,10) : 9
26
Merge similar regions, and calculate properties of the merged region:
(6.25,11.25,15) : 1 (10,15,30) : 2 (10,10,25) : 3
(6.25, 11.25, 15) : 1 (6.25, 11.25, 15) : 1 (10, 5, 30) : 6
(6.25,11.25,15) : 1 (30,10,5) : 8 (30,10,10) : 9 Calculate SAD values for neighbouring regions:
(6.25,11.25,15) : 1 (10,15,30) : 2 (10,10,25) : 3 22.5↑15↗ (6.25,11.25,15) : 1 (6.25,11.25,15) : 1 25 → (10,5,30) : 6 35↓30↘ (6.25,11.25,15) : 1 (30,10,5) : 8 (30,10,10) : 9
Mark region 1 as final.
Randomly choose region 2 and calculate SAD values for neighbouring regions:
1 (10,15,30) : 2 10 → (10,10,25) : 3 10↘
1 1 (10,5,30):6
1 (30,10,5) : 8 (30,10,10) : 9 Merge similar regions, and calculate properties of the merged region:
1 (10,10,28.33) : 2 (10,10,28.33) : 2
1 1 (10,10,28.33) : 2
1 (30,10,5) : 8 (30,10,10) : 9 Calculate SAD values for neighbouring regions:
Mark region 2 as final.
1 (10,10,28.33) : 2 (10,10,28.33) : 2
1
1
1 (30,10,5) : 8
43.33 ↙
(10,10,28.33) : 2 38.33 ↓
(30,10,10) : 9
Randomly choose region 8 and calculate SAD values for neighbouring regions:
122
11 2
1 (30,10,5) : 8 5 → (30,10,10) : 9
27
Merge similar regions, and mark region 8 as final:
122
1 1 2
188
9. Write pseudo-code for the split and merge algorithm.
1. Label every pixel with the same region label 2. For each region
3. If not all pixels are similar
4. Assign the four quadrants different region labels
5. Repeat from 2 until all regions homogeneous 6. For each region
7. Compare the region’s properties with those of its neighbours
8. For all regions with properties which are within the similarity threshold
9. Re-label them with the region label of the chosen region
10. Calculate properties of the merged region as mean of all its constituents 11. Repeat from step 6 until no more regions can be merged.
10. The array below shows feature vectors for each pixel in a 3 by 3 image.
(5, 10, 15) (10, 10, 15)
(5, 5, 15)
(10, 15, 30) (5, 20, 15) (30, 10, 5)
(10, 10, 25) (10, 5, 30)
(30, 10, 10)
Apply the split and merging algorithm to assign each pixel to a region. Assume that (1) the method used to assess similarity is the sum of absolute differences (SAD), (2) the criteria for deciding if regions are similar is that the SAD is less than 12, (3) regions have horizontal, vertical and diagonal neighbours.
Give each pixel the same label.
Determine if SAD value for any pair of pixels within the the region exceeds 12:
(5,10,15) : 1 25 → (10,15,30) : 1 (10,10,25) : 1
(10,10,15) : 1 (5,20,15) : 1 (10,5,30) : 1
(5,5,15) : 1 (30,10,5) : 1 (30,10,10) : 1 Split the region into quadrants (pad image to do so):
(5,10,15) : 1 (10,15,30) : 1 (10,10,25) : 2 (10,10,25) : 2
(10,10,15) : 1 (5,20,15) : 1 (10,5,30) : 2 (10,5,30) : 2
(5,5,15) : 3 (30,10,5) : 3 (5,5,15) : 3 (30,10,5) : 3
(30,10,10) : 4 (30,10,10) : 4 (30,10,10) : 4 (30,10,10) : 4
28
Determine if SAD value for any pair of pixels within the region 1 exceeds 12:
(5,10,15) : 1 25 → (10,15,30) : 1 5↓ 10↗ 25↓
(10,10,25) : 2 (10,10,25) : 2
(10,5,30) : 2 (10,5,30) : 2
(10,10,15) : 1 15 → (5,20,15) : 1
(30,10,10) : 4 (30,10,10) : 4 (30,10,10) : 4 (30,10,10) : 4
(10,10,25) : 2 (10,10,25) : 2
(5,5,15) : 3 (30,10,5) : 3 (30,10,10) : 4 (30,10,10) : 4
(5,5,15) : 3 (30,10,5) : 3 (30,10,10) : 4 (30,10,10) : 4 Determine if SAD value for any pair of pixels within the region 2 exceeds 12:
(5,5,15) : 3 (5,5,15) : 3
Split region 1 into quadrants:
(30,10,5) : 3 (30,10,5) : 3
(5,10,15) : 1
(10,15,30) : 5
(10,10,15) : 6 (5,20,15) : 7 (10,5,30) : 2 (10,5,30) : 2
(5,10,15) : 1
(10,15,30) : 5
(10,10,25) : 2
10 ↓
0 →
10 ↗
(10,10,25) : 2 10 ↓ (10,5,30) : 2
(10,10,15) : 6
(5,5,15) : 3 (30,10,5) : 3 (30,10,10) : 4
(5,5,15) : 3 (30,10,5) : 3 (30,10,10) : 4 Determine if SAD value for any pair of pixels within the region 3 exceeds 12:
0 →
(10,5,30) : 2
(5,5,15) : 3 40 → (30,10,5) : 3 0↓ 40↘ 0↓
(5,5,15) : 3 40 → (30,10,5) : 3 Split region 3 into quadrants:
(30,10,10) : 4 (30,10,10) : 4
(30,10,10) : 4
(30,10,10) : 4
(5,20,15) : 7
(10,10,25) : 2 (10,10,15) : 6 (5,20,15) : 7 (10,5,30) : 2 (10,5,30) : 2
(5,10,15) : 1 (10,15,30) : 5 (10,10,25) : 2
(10,10,25) : 2
(5,5,15) : 3 (30,10,5) : 8 (30,10,10) : 4 (30,10,10) : 4
(5,5,15) : 9 (30,10,5) : 10 (30,10,10) : 4 (30,10,10) : 4 Determine if SAD value for any pair of pixels within the region 4 exceeds 12:
(5,10,15) : 1 (10,15,30) : 5 (10,10,25) : 2 (10,10,25) : 2
(10,10,15) : 6 (5,20,15) : 7 (10,5,30) : 2 (10,5,30) : 2
(5,10,15) : 1 (10,15,30) : 5
(10,10,25) : 2
(10,10,15) : 6 (5,20,15) : 7 (10,5,30) : 2 (10,5,30) : 2
(5,5,15) : 3
(5,5,15) : 9
(30,10,5) : 8 (30,10,5) : 10
(30,10,10) : 4 0 → (30,10,10) : 4 0↓ 0↘ 0↓
(30,10,10) : 4 0 → (30,10,10) : 4
29
(30,10,10) : 4 (30,10,10) : 4
Can not split any further. So perform merge operation for region 1 (using mean properties for each region):
(5,10,15) : 1 25 → 5↓ 10↘
(10,7.5,27.5) : 2
(10,7.5,27.5) : 2 (10,7.5,27.5) : 2
(5,5,15) : 3 (30,10,5) : 8 (30,10,10) : 4 (30,10,10) : 4
(10,15,30) : 5 (5,20,15) : 1
(10,7.5,27.5) : 2
(10,10,15) : 1
(5,5,15) : 9 Continue merging region 1:
(30,10,5) : 10 (30,10,10) : 4 (30,10,10) : 4
(6.67,13.33,15) : 1 (6.67, 13.33, 15) : 1
(10,15,30) : 5
20 ↑
(6.67, 13.33, 15) : 1
36.67 ↓
21.67 ↗ 21.67 → 31.67 ↘
(10,7.5,27.5) : 2
(10, 7.5, 27.5) : 2
(10,7.5,27.5) : 2
(10, 7.5, 27.5) : 2
10 ↓ (5,5,15) : 1
(30,10,10) : 4 (30,10,10) : 4
(10,7.5,27.5) : 2
(10, 7.5, 27.5) : 2
(30,10,10) : 4
(30,10,10) : 4
(30,10,5) : 8
(30,10,10) : 4
(5,5,15) : 9 Continue merging region 1:
(30,10,5) : 10
(10,15,30) : 5 22.5 ↑ (6.25, 11.25, 15) : 1 35 ↓ (30,10,5) : 8
(30,10,5) : 10
(10,15,30) : 5 24↑19↗
(30,10,10) : 4
(10,7.5,27.5) : 2 (10, 7.5, 27.5) : 2 (30,10,10) : 4 (30,10,10) : 4
(6.25,11.25,15) : 1
(6.25, 11.25, 15) : 1
(6.25,11.25,15) : 1 7.5 ↓ (5,5,15) : 1
20 ↗ 20 → 30 ↘
Continue merging region 1:
(6,10,15) : 1
(6,10,15) : 1
(6,10,15) : 1
(6,10,15) : 1 34 ↓ (30,10,5) : 8
(30,10,5) : 10
19 → 29 ↘
(10,7.5,27.5) : 2 (10,7.5,27.5) : 2 (30,10,10) : 4 (30,10,10) : 4
(10,7.5,27.5) : 2
(10,7.5,27.5) : 2
(30,10,10) : 4
(30,10,10) : 4
(6,10,15) : 1 Mark region 1 as final.
Continue merging with another region…
35 ↘
34 ↘
11. Write pseudo-code for the k-means clustering algorithm.
1. Randomly choose k points to act as cluster centres 2. For each data point
3. Calculate its similarity to each cluster centre
4. Allocate data point to closest cluster centre 5. Repeat from step 2 for each data point
6. For each cluster centre
7. Calculate its new position as the mean position its elements 8. Repeat from step 6 for each cluster centre
9. Repeat from step 2 until the cluster centres are unchanged
30
12. The array below shows feature vectors for each pixel in a 3 by 3 image.
(5, 10, 15) (10, 10, 15)
(5, 5, 15)
(10, 15, 30) (5, 20, 15) (30, 10, 5)
(10, 10, 25) (10, 5, 30)
(30, 10, 10)
Apply the k-means clustering algorithm to assign each pixel to a region. Assume that (1) the method used to assess similarity is the sum of absolute differences (SAD), (2) there are two clusters, and the cluster centres are initially positioned at these positions in feature space: (5, 10, 15) and (10, 10, 25).
Calculate distance of each data point to each cluster centre:
0 25 15 15 10 0 distance from (5, 10, 15): 5 10 25 distance from (10, 10, 25): 10 25 10
5 35 30
122 Allocate each data point to closest cluster centre: 1 1 2
111
20 40 35
Calculate new cluster centres as mean of elements belonging to that cluster:
c1 = (5,10,15)+(10,10,15)+(5,20,15)+(5,5,15)+(30,10,5)+(30,10,10) =(14.167,10.833,12.50) 6
c2 = (10,15,30)+(10,10,25)+(10,5,30) =(10,10,28.33) 3
Calculate distance of each data point to each cluster centre:
12.5 25.834 17.5 distance from (14.167, 10.833, 12.50): 7.5 20.834 27.5
17.5 24.166 19.166 18.33 6.67 3.33
distance from (10, 10, 28.33): 13.33 28.33 6.67 23.33 43.33 38.33
122 Allocate each data point to closest cluster centre: 1 1 2
111
Allocation is unchanged, so cluster centres are also unchanged and algorithm has converged.
13. Write pseudo-code for the agglomerative hierarchical clustering algorithm.
31
1. Assign each data point to a unique cluster
2. Compute the similarity between each pair of clusters (store this in a proximity matrix) 3. Repeat
4. Merge the two closest clusters
5. Update the proximity matrix 6. Until only a single cluster remains
14. The are a number of methods for calculating the distance between clusters in the agglomerative hierarchical clustering algorithm. Briefly describe each of the following methods. (a) single-link clustering, (b) complete-link clustering, (c) group-average clustering, (d) centroid clustering.
(a) single-link clustering
Distance between clusters is shortest distance between elements (MIN distance)
(b) complete-link clustering
distance between clusters is longest distance between elements (MAX distance)
(c) group-average clustering
distance between clusters is average distance between all pairs of elements (AVERAGE distance)
(d) centroid clustering
distance between clusters is distance between their averages.
15. The array below shows feature vectors for each pixel in a 3 by 3 image.
c1: c2: c3: c4: c5: c6: c7: c8: c9:
(5, 10, 15) (10, 10, 15)
(5, 5, 15)
(10, 15, 30) (5, 20, 15) (30, 10, 5)
(10, 10, 25) (10, 5, 30)
(30, 10, 10)
Apply the agglomerative hierarchical clustering algorithm to assign pixels in to three regions. Assume that (1) the method used to assess similarity is the sum of absolute differences (SAD), (2) centroid clustering is used to calculate the distance between clusters.
Each point is a separate cluster initially. Compute the distance between each pair of clusters:
c1 : (5, 10, 15)
c2 : (10, 15, 30) 25
c3 : (10, 10, 25) 15 10
c4 : (10, 10, 15) 5 20 10
c5 : (5, 20, 15) 10 25 25
15
20 35 10 15 20 30 455040 25 4045355
c6 : (10, 5, 30) c7 : (5, 5, 15) c8 : (30, 10, 5) c9 : (30, 10, 10)
25 10 10 5 30 20 35 50 40 30 45 35
32
Merge closest clusters (there are 3 equally close, so merge them all), and update the proximity matrix:
c1+c4+c7: (6.67,8.33,15)
c1+c4+c7: c2: c3: c5: c6: c8+c9:
c2 : c3 : c5 : c6 : c8 + c9 :
(10, 15, 30) 25
(10, 10, 25) 15 10
(5, 20, 15) 13.33 25 25
(10, 5, 30) 21.66 10 10 35 (30, 10, 7.5) 32.5 47.5 37.5 42.5
Merge closest clusters (there are 3 equally close, so merge them all), and update the proximity matrix:
c1+c4+c7: (6.67,8.33,15)
c1+c4+c7: c2+c3+c6: c5: c8+c9:
c2+c3+c6: c5 :
c8 + c9 :
Merge closest clusters, and update the proximity matrix:
c1+c4+c5+c7: (6.25,11.25,15) c2 + c3 + c6 : (10, 10, 28.33)
c8 + c9 : (30, 10, 7.5)
We have three regions, so stop.
16. Write pseudo-code for the Normalised Cuts algorithm.
(10,10,28.33) 18.33 (5, 20, 15) 13.33
28.33 40.83
(30, 10, 7.5) 32.5
42.5
c1+c4+c5+c7: c2+c3+c6: c8+c9:
1. Form a graph such that each vertex represents an image element and each edge represents the similarity (eij ) between the connected elements
2. For two sets of vertices A and B calculate:
Ncut(A,B) = cut(A,B) + assoc(A, V )
cut(A,B) assoc(B, V )
18.33 32.5
40.83
47.5
Where:
cut(A,B)= epq p∈A,q∈B
assoc(A, V ) = epq p∈A,q∈V
3. Repeat from step 2 for every possible combination of nodes in A and B
4. Cut the edges between the sets A and B for which Ncut(A,B) is minimum
5. Repeat from step 2 for all subgraphs until minimum value of Ncut(A,B) exceeds a threshold for each subgraph or maximum number of segments have been reached.
17. Write pseudo-code for the Hough transform for straight lines
33
1. Initialise all elements in the accumulator array with a value of zero. 2. For each “edge” pixel
3. For each value of θ
4. Calculate the corresponding value of r (where r = ycos(θ) − xsin(θ))
5. Increment by one the value stored in the accumulator array nearest to the coordinates (θ, r)
6. Repeat from Step 3 for all θ. 7. Repeat from Step 2 for all pixels.
18. Following some initial processing, a 4 by 3 pixel region of an image has been converted into the following binary image:
Perform the Hough transform for straight lines on this image region, using the following values for θ: [0,45,90,135], and quantizing r to the nearest integer.
Note that for the purposes of calculating the Hough transform, the top-left corner of the image is the origin (0,0).
The absolute value of r will not be greater than the length of the diagonal (i.e (32 + 22) = 3.6, so rounding up, maximum absolute value of r is 4).
Hence, initialise the accumulator array to:
r40000
30000
20000
0
1
2
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0123
Recall, we are parameterising straight lines as shown:
10000 00000
−1 −2 −3 −4
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 04590135
θ
34
However, for images the y-axes points down, so a value of θ > 0 corresponds to a clockwise rotation:
For pixel at (0,0), the following lines are possible:
r = 0cos(135) − 0sin(135) = 0
θ = 0,
θ = 45, θ = 90, θ = 135,
r = 0cos(0)−0sin(0) = 0
r = 0cos(45)−0sin(45) = 0 r = 0cos(90)−0sin(90) = 0
Update accumulator array:
For pixel at (1,1), the following lines are possible:
r = 1cos(135) − 1sin(135) = −1.414 ≈ −1
θ = 0,
θ = 45, θ = 90, θ = 135,
r = 1cos(0)−1sin(0) = 1
r = 1cos(45)−1sin(45) = 0
r = 1cos(90) − 1sin(90) = −1
r40000
30000
20000
10000 01111
−1 −2 −3 −4
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 04590135
θ
35
Update accumulator array:
For pixel at (2,2), the following lines are possible:
r = 2cos(135) − 2sin(135) = −2.828 ≈ −3
θ = 0,
θ = 45, θ = 90, θ = 135,
r = 2cos(0)−2sin(0) = 2
r = 2cos(45)−2sin(45) = 0
r = 2cos(90) − 2sin(90) = −2
Update accumulator array:
For pixel at (3,0), the following lines are possible:
r = 0cos(0)−3sin(0) = 0
r = 0cos(45) − 3sin(45) = −2.121 ≈ −2 r = 0cos(90) − 3sin(90) = −3
r = 0cos(135) − 3sin(135) = −2.121 ≈ −2
θ = 0,
θ = 45, θ = 90, θ = 135,
Update accumulator array:
r40000
30000
20000
11000 01211
−1 −2 −3 −4
0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 04590135
θ
r40000
30000
21000
11000 01311
−1 −2 −3 −4
0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 04590135
θ
r40000
30000
21000
11000 02311
−1 −2 −3 −4
0 0 1 1 0 1 1 1 0 0 1 1 0 0 0 0 04590135
θ
Peak of accumulator array (3) is at (θ,r)=(45,0), which corresponds to the line of three edge pixels in the image.
36
19. Repeat the previous question using the following values for θ: [0,30,60,90,120,150]
Initialise the accumulator array to:
r4000000
3000000
Update accumulator array:
2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 30 60 90 120 150
θ
1
0 −1 −2 −3 −4
For pixel at (0,0), the following lines are possible:
r = 0cos(120) − 0sin(120) = 0 r = 0cos(150) − 0sin(150) = 0
θ = 0, θ=30, θ=60, θ=90, θ = 120, θ = 150,
r = 0cos(0)−0sin(0) = 0
r = 0cos(30) − 0sin(30) = 0 r = 0cos(60) − 0sin(60) = 0 r = 0cos(90) − 0sin(90) = 0
r4000000
3000000
2
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 30 60 90 120 150
θ
1
0 −1 −2 −3 −4
For pixel at (1,1), the following lines are possible:
r = 1cos(0)−1sin(0) = 1 r=1cos(30)−1sin(30)=0.366≈0
r = 1cos(60) − 1sin(60) = −0.366 ≈ 0 r = 1cos(90) − 1sin(90) = −1
r = 1cos(120) − 1sin(120) = −1.366 ≈ −1 r = 1cos(150) − 1sin(150) = −1.366 ≈ −1
θ = 0, θ=30, θ=60, θ=90, θ = 120, θ = 150,
37
Update accumulator array:
For pixel at (2,2), the following lines are possible:
r = 2cos(0)−2sin(0) = 2 r=2cos(30)−2sin(30)=0.732≈1
r = 2cos(60) − 2sin(60) = −0.732 ≈ −1 r = 2cos(90) − 2sin(90) = −2
r = 2cos(120) − 2sin(120) = −2.732 ≈ −3 r = 2cos(150) − 2sin(150) = −2.732 ≈ −3
θ = 0, θ=30, θ=60, θ=90, θ = 120, θ = 150,
Update accumulator array:
For pixel at (3,0), the following lines are possible:
r = 0cos(0)−3sin(0) = 0 r=0cos(30)−3sin(30)=−1.5≈−2
r = 0cos(60) − 3sin(60) = −2.598 ≈ −3 r = 0cos(90) − 3sin(90) = −3
r = 0cos(120) − 3sin(120) = −2.598 ≈ −3 r = 0cos(150) − 3sin(150) = −1.5 ≈ −2
θ = 0, θ=30, θ=60, θ=90, θ = 120, θ = 150,
Update accumulator array:
r4000000
3000000
2
0 0 0 0 0 0 1 0 0 0 0 0 1 2 2 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 30 60 90 120 150
θ
1
0 −1 −2 −3 −4
r4000000
3000000
2
1 0 0 0 0 0 1 1 0 0 0 0 1 2 2 1 1 1 0 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 30 60 90 120 150
θ
1
0 −1 −2 −3 −4
r4000000
3000000
2
1 0 0 0 0 0 1 1 0 0 0 0 2 2 2 1 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 0 1 1 2 1 0 0 0 0 0 0 0 30 60 90 120 150
θ
1
0 −1 −2 −3 −4
Note, that there is no clear peak in the accumulator array: results are sensitive to the quantisation of the parameters!
38
20. Briefly describe the two terms that form the energy function that an active contour attempts to minimise.
Energy = Internal energy + External energy
Internal energy is a function of the shape of the contour, it is reduced if the curve is short and smooth.
External energy is a function of the image features near the contour, it is reduced if the intensity gradient is high.
39