CSE/EE 576 Lecture Outline for Friday, May 26, 1995
SLT

Methods for matching and retrieval of images from image database.

1. Formulation of the approximate matching problem.

2. The Triangle Trie data structure

 a. Integer-valued distance metrics
 b. Real-valued distance metrics
      In order to construct the i-th level of the trie,
       partition the distances of the database elements to the
       i-th key object into bins.  For each bin, record the
       minimum and maximum as [alpha, omega].


      Correction to the lecture:
        When querying, we do a depth-first search of the trie,
        pruning with the modified rule below.

          If either
              D(x, key ) < alpha - theta  
                      i
              or

              D(x, key ) > omega + theta
                      i
          then prune.

      As before, D(x, key ) gives the distance from the query object x
                         i
      to the i-th key object.  Theta is the distance threshold for
      given in the query.

3. Wavelet encoding of images
    Haar transform for 1-D vectors
    Haar transform for 2-D images

4. The matching metric of Jacobs, Finkelstein, and Salesin (JFS)

5. Indexing and retrieval method of JFS.

References:

For the triangle trie...

Berman, A. 1994. A new data structure for fast approximate matching.
Technical Report 94-03-02. Dept. of Computer Science and Engineering,
University of Washington, Seattle.

For the JFS method...
 http://128.95.2.89/homes/adam/query/query.html

For a related method developed at the Univ. of Florence, Italy...
 http://aguirre.ing.unifi.it/~ist/idbms.html