E186 Project 6 (due April 24)


This project is on image representation and description. We concentrate on line feature detection and representation. The image used is this project is /e186/imagedata/gumby.pgm, which contains some figure -- a 2D object. In order to detect and represent its boundary and structure, consider the following steps:
  1. Edge detection:
    detect the edges in this image using any method best for this image and convert the result into a binary image (the edges are represented by 1's and the background is represented by 0's).

    Hint: to achieve good result, you may consider preprocessing (e.g. thresholding, etc.) the given image before edge detection.

  2. Linking:
    link locally the edge pieces if the previous step did not give you a complete boundary of the object. This process should also remove isolated edge pixels caused by noise. (I don't really intend to have you do this. The image is clean enough and if your edge detection algorithm works well, the complete edge should be obtained.)

  3. Thinning:
    make the boundary a one-pixel wide curve; (Hint: if you properly threshold the image after edge detection, a one-pixel wide boundary may be obtained without actually going through this thinning process.)

  4. Representation:

    (a) Extracting Boundary Pixels
    To use FD method, you need to extract the coordinates {x,y} of every pixel on the boundary. To do so, you will need to write a function in which the boundary is traversed pixel by pixel to obtain their coordinates. After the coordinates of a boundary pixel are recorded, you mark it and move on to the next one by searching all 8 neighbors to find a non-zero neighbor which is not yet marked. Keep doing this until you come back to the starting point (marked previously).

    (b) Fourier Descriptors
    DFT the boundary pixels z(m)=x(m)+jy(m), (m=0, ...., N-1) to find the Fourier Descriptors. Note that the number of boundary pixels $N$ may not be a power of 2, so you need to use the DFT definition with N^2 computational complexity. (Use "/home/adder/classes/e186/programs/mydft.c").

    Next, recover the boundary by IDFT only the low frequency components (with the remaining frequency components set to zero). (Hint: make sure you know where the low and high frequency components are in the {\em periodic} DFT spectrum.) Try to change the number of low frequency components used to see the fact that the more high frequency components thrown away, the less detail recovered. In other words, the first few low frequency components can be used to represent the location, the basic shape and the orientation of the 2D shape. Submit two images recovered using different number of low frequency components to show this effect.

    (c) Skeletonization
    Properly threshold the original image so that all pixels inside the shape are 1 and all background pixels are 0. Then use both the thinning (N(P) and S(P), etc.) and skeletonization (firelines) algorithms discussed in class to find the ``skeleton'' of the figure.