CS6643-Homework 2 Solved

1.                 Given the 7 × 7 grayscale image in Figure 1(a) below, use the Canny’s edge detector to produce a binary edge map. The image has already been smoothed by a Gaussian filter. (a) Use the Prewitt’s edge operator in Figure 1(b) below to compute edge magnitudes and gradient angles for pixel locations  𝑖𝑖, 𝑗𝑗 = 1 to 5 (center 5 × 5  region.) Compute edge magnitude by taking the square root of the sum of squares of horizontal and vertical gradients. (b) Apply non-maxima suppression to pixel locations 𝑖𝑖, 𝑗𝑗 = 2 to 4  (center 4 × 4 3 × 3 region.) (c) Use simple thresholding with 𝑇𝑇 = 2 to produce a binary edge map for pixel locations 𝑖𝑖, 𝑗𝑗 = 2 to 4. Show results after each step from (a) to (c) above.

 

 

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
5
5
5
5
5
5
5
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
9
(a) The image uses the i-j coordinate system with i pointing downward and j points to the right. The upper left corner pixel has coordinates

(𝑖𝑖, 𝑗𝑗) = (0,0).  
 
 
                             Figure 1. (a) 7 x 7 grayscale image and (b) Prewitt’s edge detector. 

 

2.                 Apply the Double Tresholding Algorithm below to segment the 8 x 8 image in Figure 2.  Let 𝑇𝑇1 = 100 and 𝑇𝑇2 = 160 in the algorithm. In step 3 of the algorithm, use the 4-connectedness definition for neighbors. Under this definition, the four pixels to the left, to the right, above and below the current pixel are considered neighbors. In your answer, show: (a) an 8 x 8 array with a region label for each pixel after step 2, and (b) an 8 x 8 array showing the final region label for each pixel after step 5.  

 

1.  Select two thresholds T1 and T2

2.  Partition the image into three regions: R1, containing all pixels with gray values below T1; R2, containing all pixels with gray values between T1 and T2, inclusive; and R3, containing all pixels with gray values above T2

3.  Visit each pixel assigned to region R2. If the pixel has a neighbor in region R3, then reassign the pixel to region R3.

4.  Repeat Step 3 until no pixels are reassigned.

5.  Reassign any pixels left in region R2 to region R1.

    

       Double Thresholding Algorithm. 

 

 

20
30
35
99
89
90
55
99
66
67
87
88
99
87
86
85
77
162
163
189
98
99
93
89
75
180
188
97
120
78
130
98
70
165
170
65
110
70
140
45
98
200
65
75
85
95
130
75
70
100
130
89
160
159
140
99
33
43
54
66
77
86
96
99
                                              Figure 2. An 𝟖𝟖 × 𝟖𝟖 grayscal image. 

 

3.                For the histogram in Figure 3, use the Peakiness Algorithm as covered in lecture to select the best threshold value to segment the image. In step 2 of the algorithm, set the minimum distance d to be 2. To detect local maxima in the histogram, use a sliding window of size 1 x 3 and compare the value of the center point with the values of the left and right neighbors. Show all work to get full credits.  

 

               

                           Figure 3. Grayscale histogram  

 

 

4.                Draw the Region Adjacency Graph for the regions in Figure 4 below. Your graph should include a node to represent the region outside of the border of the image.  

                                         

                                     Figure 4. Image segmented into regions.  

 

 

 

5.                 (a) How many 4-connected regions are there in the binary image in Figure 5 below where the 1’s represent foreground pixels? (b) How many 8-connected regions are there in the image? (c) What is the area (in pixels) of the largest 4-connected region in the image? (d) Compute the centroid of the largest 4connected region in the image in the (𝑖𝑖, 𝑗𝑗) coordinate system. (The i axis points downward, the j axis points to the right and the pixel at the upper left corner has coordinates (𝑖𝑖, 𝑗𝑗) = (0,0)).

             

 
 
 
 
 
 
 
 
  
1
1
 
 
1
 
 
 
1
1
1
1
1
1
 
 
1
1
1
1
1
 
 
 
1
1
1
 
 
1
 
 
1
1
 
 
 
1
 
 
 
 
 
 
1
 
 
 
 
 
 
 
 
 
 
 

Figure 5. A binary image. 

 

6.                Apply the Connected-Component Labeling Algorithm given below to the binary image in Figure 6 below.  In your answer, write (a) the label map and the content of the equivalence table after the algorithm finishes Steps 2 and 3 and (b) the final label map after Step 5.

 

 
 
 
 
 
 
 
 
  
 1
1
 
 
1
 
 
 
1
1
1
1
1
1
 
 
1
1
1
1
1
 
 
 
 
 
1
 
 
1
 
 
1
1
1
 
 
1
 
 
 
 
 
 
1
 
 
 
 
 
 
 
 
 
 
              

Figure 6. A binary image. 

 

1.  Scan the image from left to right, top to bottom

2.  If the pixel is 1 (foreground), then

a)  If only one of its upper and left neighbors has a label, copy the label

b)  If both have the same label, copy the label

c)  If the two neighbors have different labels, copy the upper’s label and enter both neighbors’ labels in the equivalence table and record them as equivalent.

d)  Otherwise, assign a new label to this pixel  3. If there are more pixels to consider, go to step 2

4.  Find the smallest label for each equivalent set in the equivalence table

5.  Scan the label map. Replace each label by the smallest label in its equivalent set