Wavelets allows the query image to be of any resolution.
Wavelets are a mathematical tool for hierarchically decomposing functions. Most of the literature uses terminology from signal processing and pure mathematics.
Why using wavelets?
 The use of wavelets allows the resolutions of the query and target images to be different .
 Wavelet decompositions are fast to compute and yield a small number of coefficients.
 Haar wavelets are the fastest to compute and simplest to implement.
 The signature can be extracted from a waveletcompressed version of the image directly.
 Standard decomposition worked best
Wavelet signature is a collection of m largest Haar decomposition coefficients quantized to 2 levels (positive or negative).
 Value at (0,0) gives us the average intensity level for that color plane;
 Rest of the coefficients give the detail of the image
Compute a “signature” for each image, based on (truncated and quantized) Haar wavelet coefficients with low storage:
 Truncationkeeps discriminatory power of metric:: 128 x 128 image, 16,384 wavelet coefficients for each color channel, only keep largest magnitude coefficients
 The 60 largest coefficients in each channel worked best for painted queries.
 The 40 largest coefficients in each channel worked best for scanned queries.
 Quantization Quantize each of the retained coefficients into three levels: +1, 0 and 1:
 Large positive coefficients are quantized to +1

Large negative coefficients are quantized to 1
 Improves discriminatory power of metric, Improves speed and reduces storage requirements
 Normalization: they become orthonormal to each other
Haar wavelet transform for preprocessing
(1)Perform a standard 2D Haar wavelet decomposition of every image in the database.
(2) Store T[0,0] for each color channel and the indices and signs of the m wavelet coefficients of largest magnitude.
(3) Organize the indices for all the images into a single data structure to optimize searching.
Small signature database
All the images are preprocessed to store their wavelet signatures. The database also stores the links to original images
 preprocessing
 Resize the image to predefined size (128×128 in current implementation)
 Convert it to YIQ color model
 Do Haar decomposition

Truncate all other coeffcients except T(0,0) to m largest values. Or in
other words, keep m largest Haar wavelet coeffcients, and discard
others (m=30 in my implementation)
 Quantize the coeffcients to +1 (positive) or 1 (negative)

Add the image to one of the six search arrays (positive and negative
for each of the 3 color channels). E.g. If an image has a large positive
coeffcient for Y color channel at (3,100) then it will be added to the
list at location (3,100) in search array Y
+
 Querying
 Perform the same wavelet decomposition on the query image.

Throw away all but the average color and the largest m coefficients.

Compute the score of each target image using the above equation.
 The images with least score are the best matches and n such images are returned as n matches to the
query.
reference
An Introduction to Wavelets[pdf]
Eric J. Stollnitz, Tony D. DeRose, and David H. Salesin. Wavelets for computer graphics: A primer, part 1[pdf] (we discuss the simple case of Haar wavelets in one and two dimensions, and show how they can be used for image compression.) part2[pdf](presents the mathematical theory of multiresolution analysis, develops boundedinterval spline wavelets, and describes their use in multiresolution curve and surface editing.)
Wavelets for Computer Graphics: Theory and Applications. Eric J. Stollnitz, Tony D. DeRose, and David H. Salesin.
Morgan Kaufmann, San Francisco, 1996.
Python implementation of fast multiresolution image querying