Transcript Image Processing Fundamentals

Fast multiresolution image querying
CS474/674 – Prof. Bebis
Case Study
• C. Jacobs, A. Finkelstein, and D. Salesin, “Fast
multiresolution image quering”, Proceedings of
SIGGRAPH, pp. 277-286, 1995
Problem
• Search an image database to retrieve images that are
similar to a query image.
“query by content” or
“query by example”
Typically, the K best
matches are returned.
Challenges
• How to represent an image?
– i.e., what features to use?
• How to tolerate image distortions?
• How to organize the images for fast retrieval?
• How to reduce storage requirements?
Image Distortions
• This paper considers two types of image distortion:
– A low-resolution image from a scanner or camera.
– A rough sketch of the image painted by the user.
painted
low resolution
target
Traditional Metrics
• Traditional metrics based on the L1 and L2 norms
cannot handle inexact matching and are expensive to
compute.
L1
Q: query
L2
T: target
Experiments using these metrics have shown that the target image
is in the highest 1% of the retrieved images only 3% of the time.
Proposed Method: Key Ideas
• Multi-resolution image decomposition using Haar
wavelets.
• Uses a metric that compares how many significant
wavelet coefficients the query has in common with
potential targets.
• Efficient data organization to facilitate fast
computation of the metric and speed-up search.
User Interface
Processes a 128 x 128
image query on a
database of 20,000
images in under 0.5
seconds*.
Returns 20 highestranked targets at
interactive rates!
*Faster
processing times should be
possible using current technology!
Why using wavelets?
• The use of wavelets allows the resolution of the query
and target images to be different.
• Wavelet decompositions are fast to compute and
contain a small number of non-zero coefficients.
• Wavelet-compressed images could be used directly.
What color space to use?
• Experimented with RGB, HSV, and YIQ color spaces.
– Wavelet transform was applied on each color channel
separately.
– YIQ yielded the best performance.
What wavelet to use?
• Haar wavelets are the fastest to compute and simplest
to implement.
• Other types of wavelets might give better results but at
a higher cost.
What wavelet decomposition to use?
• Experimented both with standard and non-standard
decompositions for all three color spaces.
– Standard decomposition worked best (i.e., both for scanned
and painted queries).
– Basis functions were normalized to become orthonormal to
each other.
First Idea: Coefficient Truncation
• Keep only coefficients with large magnitude.
– Improves discriminatory power of metric.
– Improves speed and reduces storage requirements.
• 128 x 128 image  1282 = 16,384 wavelet coefficients
in each color channel.
– The 60 largest coefficients in each channel worked best for
painted queries (180 coefficients total).
– The 40 largest coefficients in each channel worked best for
scanned queries (120 coefficients total).
Coefficient Truncation (cont’d)
Wavelet
decomposition
Truncated
coefficients
White: positive coefficient
Black: negative coefficient
Second Idea: Coefficient Quantization
• The mere presence or absence of large coefficients
appears to be more important than their precise
magnitude.
– Improves speed and reduce storage requirements.
– Improves discriminatory power of metric.
• Quantize coefficients into three levels: +1, 0 and -1
– Large positive coefficients are quantized to +1
– Large negative coefficients are quantized to -1
– The rest are set to 0
Components of the metric (cont’d)
Truncated
coefficients
Truncated and
quantized coefficients
Third Idea: Wavelet-based Metric
Q: Query and T: Target (single color channel)
• Let Q[0, 0] and T[0, 0] be the scaling coefficients (i.e.,
average intensity of that channel).
• Let Qˆ [i, j ] and Tˆ[i, j ] represent the truncated, quantized
wavelet coefficients of Q and T (i.e., -1,0,1).
Metric:
wi,j : weights (determined statistically)
Simplify the metric
(1) Replace (Qˆ [i, j ]  Tˆ[i, j ])
with
(Qˆ [i, j ]  Tˆ[i, j ])
(1 if true; 0 otherwise)
Simplify the metric (cont’d)
(2) Group terms together into "buckets" so that only a
smaller number of weights wi,j is needed.
i,j
Simplify the metric (cont’d)
• The function bin(i, j) groups different coefficients into a
small number of bins (i.e., 6 bins per color channel):
bin(i, j) = min(max(i, j), 5)
• Each bin is weighted by w[b]
– Weights were determined using a statistical test.
0
1 2 3 4
5
0
1 2 3 4
5
Simplify the metric (cont’d)
(3) Consider only the terms for which Qˆ [i, j ]  0
– Leads to even faster computations.
– Allows for a query without much detail to match a detailed
target image.
i,j
Simplify the metric (cont’d)
(4) Count the number of matching coefficients than the
number of mismatching coefficients.
(1 if true; 0 otherwise)
– The majority of database images will not match the query.
– Use “search arrays” to implement this idea efficiently.
Simplify the metric (cont’d)
Simplify the metric (cont’d)
• The term
does not depend on the target
image and can be ignored:
Final Metric
Example
Search Arrays
• Use a set of six 2D arrays (i.e. search arrays) to organize
the m coefficients from every target image T.
– There is an array for every combination of sign (+ or -) and color
channel (Y, I, and Q):
Dc [i, j ] contains a list of all target images T having a large
positive wavelet coefficient at [i, j] location, in color channel c.
Search Arrays (cont’d)
Dc [0, 0]
c

D [0,1]
T1, T9, T22, …
T3, T9, T40, …
Qˆ [i, j ]  0
…
Dc [i, j ]
…
T1, T22, T98, …
Compute a score for
each target image
found in Dc /  [i, j ]
Querying Using Search Arrays
• Steps (for each color channel c)
(1) Compute the difference between the query’s average
intensity Qc[0, 0] and those in the database.
(2) For each of the m nonzero, truncated wavelet coefficients
Qc[i, j], go through the list corresponding to Dc+[i, j] or
Dc- [i, j] (i.e., depending on the sign of Qc[i, j]).
(3) Update the score of each target image found in those lists.
Algorithm
• Preprocessing
(1) Perform a standard 2D Haar wavelet decomposition of
every image in the database.
(2) Store T[0,0] for each color channel as well as the indices
and signs of the m largest wavelet coefficients (2D search
arrays).
Algorithm (cont’d)
• Querying
(1) Perform a standard 2D Haar wavelet decomposition on the
query image.
(2) Compute T[0,0] for each color channel as well as the
indices and signs of the m largest wavelet coefficients
(3) Compute the score of each target image using:
(4) Return 20 highest-ranked target images
Examples
• Query examples using painted/scanned queries
(ranks for database sizes: 1093 | 20,558)
Examples (cont’d)
Interactive query using painted query:
(ranks for database sizes: 1093 | 20,558)
Success Rate
Lq : proposed metric
Percentage of queries
whose correct target
was ranked among the
top 1% of images in
a database of 1093
images.
Time requirements
Lq : proposed metric
Average times to match
a single query in a
database of 1093/20,558
images.
Extension
• V. Nikulin and G. Bebis, "Multiresolution Image
Retrieval Through Fusion", SPIE Electronic Imaging
(Storage and Retrieval Methods and Applications for
Multimedia), San Jose, January 2004.