EN161 - Image Processing and Understanding
Lab 6 - Edge Linking & Boundary Following
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.  There are often problems with the output of edge detectors that can be addressed with these techniques.

 
Data:
 
Image A
Image B

 

 
Problem 1:
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 2:
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 3:
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.