CS6643-Midterm Solved

1.               In Hough transforms, is it always better to use a smaller step size for the parameters when forming the accumulator array (thereby resulting in smaller cells) so that we can have higher precision for the detected lines, curves or shapes? Why or why not? Do not write more than six sentences.  

 

2.               ] What is histogram equalization used for? Explain how it works. Do not write more than six sentences.  

 

3.               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 sum of the absolute values of the horizontal and vertical gradients. (b) Apply non-maxima suppression to pixel locations 𝑖𝑖, 𝑗𝑗 = 2 to 4  (center 3 × 3 region.) (c) Use simple thresholding with 𝑇𝑇 = 3 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 
5 
1 
1 
1 
1 
1 
5 
9 
1 
1 
1 
1 
5 
9 
9 
1 
1 
1 
5 
9 
9 
9 
1 
1 
5 
9 
9 
9 
9 
1 
5 
9 
9 
9 
9 
9 
5 
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. Input image and Prewitt’s operator. 

 

4.               [15 points] The Connected Component Labeling algorithm below is for finding 4-connected regions. Modify the algorithm so that it can find 8-connected regions.  

 

•        Sequential algorithm for connected component labeling (for 4-connected regions)

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

2.  If the pixel is 1,then

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

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

c)               If the two neighbors have different labels, copy the upper neighbor’s label and enter         the two labels in the equivalence table as equivalent labels.      d) Otherwise, assign a new label to this pixel.  

3.  If there are more pixels to consider, go to step 2

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

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

 

5.               In a certain machine part inspection application, we know that the image contains three machine parts (A, B and C) and the background.  We also know the following:

 

•        Object A occupies 9% of the image in size. Object B is twice as big as A, and C is twice as big as B.  

•        𝐼𝐼𝐴𝐴 < 𝐼𝐼𝐵𝐵 < 𝐼𝐼𝐶𝐶 < 𝐼𝐼𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵 where I is the gray level value of the individual pixels that belong to the three objects and the background, as indicted by the subscript.

 

Given the grayscale histogram of the input image in the figure below, determine three threshold values, 𝑇𝑇1, 𝑇𝑇2 and 𝑇𝑇3, that can be used to segment the three objects from the background. Give the grayscale intervals for each of the objects and the background based on the threshold values that you have determined.

 

  

Grayscale histogram of the input image.  

(The number above each bar is the pixel count.)

 

6.               Given the 5 × 5 grayscale image below, apply the Laplacian operator below to detect edges. For your answer, first give the Laplacian response as a 2D array and then mark the detected edges on the array. Let the output response be undefined if the Laplacian template goes outside of the border of the image.

             

 

 
 
4
4
12
12
12
4
4
12
12
12
4
4
12
12
12
4
4
8
8
8
4
4
8
8
8
 

Grayscale Image 
 
 

 

0 
1 
0 
1 
-4 
1 
0 
1 
0 
Laplacian Operator. The center pixel is the reference center. 
 
 

7.                (a) Apply the iterative distance transform algorithm below to the input image 𝑓𝑓(𝑟𝑟, 𝑐𝑐) in the figure below, where the 1’s represent foreground pixels and background pixels are unlabeled (assumed to have a value of 0.)

 

                                         f 0[r,c] = f [r,c]

                                    f m[r,c] = f 0[r,c]+ min( f m−1[u,v])

                            Stop when 𝑓𝑓𝑚𝑚[𝑟𝑟, 𝑐𝑐] = 𝑓𝑓𝑚𝑚−1[𝑟𝑟, 𝑐𝑐]

                                    

Show the image result after each iteration. You must execute Step 3 in the algorithm above so the algorithm knows when to stop. (b) From the distance transform, circle those pixels that belong to the medial axis. The image uses the (𝑟𝑟, 𝑐𝑐) coordinate system with the upper-left corner pixel having 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
 
 
 
 
1
 
1
1
 
 
 
1
1
 
 
1
 
 
 
 
 
 
 
 
 
                                           Input image f(r,c)

 

8.               Hough transform is used to detect circles having a radius of 2 pixels in an input image. Below is the content of the accumulator array for parameters a and b after applying Hough transform to the edges in the input image. The range for both a and b in the accumulator array is [0,40] pixels. We know that there is only one circle in the image. Write the equations of the detected circle.

 

 

 

 

 

 

9.               [15 points] One way to test whether two adjacent regions should be merged together in the split and merge algorithm is by computing the likelihood ratio L defined as

                                       pp((gg1,g2,....| H1)) = σm0m11.σ+m2m22

L  =
,g ,....| H

                                                              1       2                       0 σ1

 

where σ1 and σ2 are the standard deviations of the gray level values of the pixels in region 1 and region 2, respectively, σ0 is the standard deviation of the gray level values of the pixels in the two regions combined, m1and m2are the number of pixels in regions 1 and 2, respectively. Starting with the equation of a normal distribution given below, show (by mathematical derivation) that the joint probability density under hypothesis 𝐻𝐻1 is

 

  p(g1, g2,......, gm1 , gm1+1,........, gm1+m2 | H1) = (      2π1σ1)m1 e−m21 . ( 2π1σ2 )m2 e−m22

 

 

Normal distribution:  

                                                          p(gi ) = 1                    (g −µ)2

                                                                            ,  𝑔𝑔𝑖𝑖 is the gray level value of pixel i.