wavelet-signature

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?

  1. The use of wavelets allows the resolutions of the query and target images to be different .
  2. Wavelet decompositions are fast to compute and yield a small number of coefficients.
    • Haar wavelets are the fastest to compute and simplest to implement.
  3. 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:

  1. 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.
  2. 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
  3. 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 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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

生活在西班牙

自己动手丰衣足食

BlueAsteroid

Just another WordPress.com site

Jing's Blog

Just another WordPress.com site

Start from here......

我的心情魔方

天才遠私廚

希望能做一個分享各種資訊的好地方

语义噪声

西瓜大丸子汤的博客

笑对人生,傲立寰宇

Just another WordPress.com site

Where On Earth Is Waldo?

A Project By Melanie Coles

the Serious Computer Vision Blog

A blog about computer vision and serious stuff

Cauthy's Blog

paper review...

Cornell Computer Vision Seminar Blog

Blog for CS 7670 - Special Topics in Computer Vision

datarazzi

Life through nerd-colored glasses

Luciana Haill

Brainwaves Augmenting Consciousness

槑烎

1,2,∞

Dr Paul Tennent

and the university of nottingham

turn off the lights, please

A bunch of random, thinned and stateless thoughts around the Web

%d bloggers like this: