Class Notes: Computational Problems and Research in GIS

Fall 1997 - Mon 10th Period, Tue 6th Period, Thu 7th Period CSE/E221

Instructors: G.X. Ritter and M.S. Schmalz

Project 1 Assignment

• Goal. The purpose of this project is to provide basic hands-on experience with cepstral-based coregistration, as well as provide the opportunity to help you build a library of advanced GIS computational capabilities.

• Sources. We will be using the papers we handed out in class, namely:
  • Yeshurun, Y. and E.L. Schwartz. "Cepstral filtering on a columnar image architecture: a fast algorithm for binocular stereo segmentation", IEEE Transactions on Pattern Analysis and Machine Intelligence 11(7):759-767 (1989).

  • Smith, P.N. and N. Nandhakumar. "Improved power cepstrum based stereo correspondence method for textured scenes", IEEE Transactions on Pattern Analysis and Machine Intelligence 18(3):338-348 (1996).

• Features. Additionally, we will be making a modular program by breaking a simple program up into pieces, as demonstrated previously in class.

• Concept. The program Proj1 will print your name, SSN, class, and date to your computer screen.

• Procedure. Implement the following steps:

  Step 1. Produce a program that implements Yeshurun and Schwartz' cepstral-based coregistration algorithm. Test the program on the following imagery:

  • Easy Image #1. Left part of Lena image and Right part of Lena image
    where neither image has noise, but nonuniform disparity exists;

  • Easy Image #2. Left part of Lena image and Right part of Lena image
    where neither image has noise, but the right-hand image has greater disparity than Image #1;

  • Medium Difficulty. Right part of Lena image ,
    which is corrupted with noise; and

  • Difficult. Left part of GUI image and Right part of GUI image ,
    where both have periodic structure.

  Step 2. Apply the program to the preceding imagery, generating a disparity map for each neighborhood configuration chosen. Start with large neighborhoods (e.g., 32x32 pixels) and work downward to smaller neighborhoods (e.g., 32x32, 16x16, 8x8, 4x4) to see the limitations of the technique.

  Step 3. Apply the program to the preceding imagery, generating a histogram of the scalar disparity for each neighborhood configuration chosen. Recall that a histogram is a graph of frequency-of-occurrence. You start with about 50 bins in the histogram, but no fewer than 20 and no more than 200.

  Step 4. Discuss the sampling error as a function of neighborhood size and histogram bin width. What conclusions can you reliably make about the difference between the noiseless and noisy Lena images? Explain mathematically why the GUI image may be hard to work with -- how many disparity peaks are present for different blocksize?

• Programming Hints. You will find the project easier if you observe the following suggestions:
  1. Use a standard programming library for your Fourier Transform. The GAMS library, available on the Internet, is a good place to start. Or, you can share FT code to reduce your time spent on this step.

  2. Share your code for the histogramming routine, and try to make the bin selection as accurate as possible by using double-precision rounding (datatype double in C).

  3. Test your program thoroughly on an image that you make (not the Lena image) so that you can control the program's input. Then, test it on the "easy" Lena image before applying it to the medium or difficult image.