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