EN161 - Image Processing and Understanding
Lab 6 - Edge Detection & Linking, Corner Detection
Due Tuesday 10/22
NOTE: Problems should be done in MATLAB.  Type up your solutions for each one including: (1) The answer to any questions posed, (2) any resulting images (include in document), and (3) the name of any functions you used. 

Zip or tar your document with your source code (m-files) into a file called [Lastname_FirstInitial_Lab6.zip/tar] and email it to mcchang@lems.brown.edu with the subject "EN161 Lab6".
 
Overview:
This lab addresses some of the finer points of edge detection and linking, boundary following, and corner detection. There are often problems with the output of edge detectors that can be addressed with these techniques.

Problem 1:
Type of Edges.
Give a few examples of each of these types of edges in the Images A and B.
  • Reflectance Edges
  • Texture Edges
  • Highlight Edges
  • Shadow Edge
For example:

 
                                                           Image A                                                                                                                        Image B
 
 

Problem 2:
Canny Edge Detection.
Run Matlab's Canny edge detection ("help edge" in Matlab) over the above Image A and Image B and report your observation as you did in Problem 1 of Lab 5.

Determine the strengths and weaknesses of one relative to the other. 
Specifically look for the success of each algorithm with respect to corners, curved edges, noise inclusion/exclusion, etc. 
Which of the edge types above are most easily detected; which are more difficult.
Provide specific examples and images to illustrate your findings.

Problem 3:
Cubic Image Approximation Edge Detection.
Implement an edge detection using a Cubic Image Approximation (refer to the hand out of Image Approximation page 165). 

I have provided the masks k1-k10 in the matlab file k_coef.mat, download it into a matlab directory and type load k_coef to load the masks into your workspace.  I recommend using filter2 to apply the masks (don't forget to scale them by the value given below each mask).

Hints: You will want to filter the image first to eliminate noise.  Also, if your edges are too thick, try reducing the pixel radius.  Also, when checking to make sure the first derivative is not zero, you will probably want to say something like:

d > gamma
instead of
d ~= 0

Try it out on Images A and B.  Show the resulting edge images.

 
Problem 4:
Edge Linkging.
Perform dual threshold edge linking using your edge detector from lab 5. 

a. At the stage in which you threshold the gradient magnitude image, create two images, one using a high threshold Th and another using a low threshold Tl.
b.  Visit every edge point in the image created from Th.  For this point, determine the edge direction (hint: it's normal to the gradient direction) and round to the closest of the 8 pixel directions.
c.  Look at the pixel in that direction.  If the pixel had a gradient magnitide Tl > m>Th, then add that point to the binary edge map (the one created from Th), move to that pixel and repeat.  If the pixel has a gradient magnitude <Tl, or >Th (already in the edge map), then stop and visit the next pixel.

The effect should be to fill in gaps in contours that are created by setting the threshold too high. Test on Images A and B.


Problem 5:
Boundary Edge Following.
In this problem you will implement a boundary following algorithm. 

a. Once again start with the gradient of an image (magnitide and direction).
b. Do a raster scan through the gradient magnitude until you come upon a point that falls above a threshold.
c. Check the two neighboring pixels along the gradient direction to make sure it is a local maximum.
d. In the edge direction, consider the neighboring pixels in that direction and two adjacent directions.  Select the pixel with the lowest cost function where the cost function considers two factors, the first being the gradient magnitude, the second being the difference in gradient direction between the two pixels.  A large difference in direction would give a high cost.  Move to the "best" pixel and repeat.  Also set a threshold for this cost and stop if none of the pixels can offer a low enough cost.
e. Repeat the previous step in the oposite edge direction from the original pixel.
f.  If the total number of points that you collected in the last 2 steps is greater than some number (like 3), then store the points in a boundary list.
g. Proceed to the next pixel and repeat the process.  Any pixel that already belongs to the boundary list cannot be considered again.
 

Test on Images A and B.
 

 
Problem 6:
Corner Detection.
One major problem with edge detectors is that they don't handle corners very well.  We can detect corners in an image using the following algorithm:

a.  Smooth the image and take the gradient (Ax,Ay).
b.  For each pont in the image, construct the following matrix:

   [ Sum(Ax^2)   Sum(AxAy) ]
   [ Sum(AxAy)  Sum(Ay^2)  ]

Where the sums are taken over a square neighborhood of size 2*N+1, 

i.e.  sum(sum(Ax(i-N:i+N,j-N:j+N).^2))

c.  The eigenvalues of this matrix represent the magnitude of the two gradient directions.  If both are large, then it is likely a corner.  Threshold the smaller eigenvalue and store the value and location in a list.  In MATLAB:

eigenvalues = eig(M);

d.  Take the final list and sort it.  Starting from the top, eliminate all points below that ocupy the same neighborhood.  This will ensure detection of the local maximum.
e.  Come up with a good way of marking these corners and submit the image.

Use this method to fill in the missing corners of an edge image by checking the ends of edge segments for a nearby corner and linking them.  Submit the images before and after this correction.

Test on Images A and B.