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 wavelet-compressed 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:
- Truncation-keeps 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
- 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
- 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
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 multi-resolution analysis, develops bounded-interval spline wavelets, and describes their use in multi-resolution 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 multi-resolution image querying